基于SQLite内容雕刻的恢复技术

马庆杰，李炳龙，位丽娜

(1.信息工程大学，郑州 450004; 2.数学工程与先进计算国家重点实验室，郑州 450004)

(*通信作者电子邮箱lblc2006@163.com)

基于SQLite内容雕刻的恢复技术

马庆杰1,2，李炳龙1,2*，位丽娜1,2

(1.信息工程大学，郑州 450004; 2.数学工程与先进计算国家重点实验室，郑州 450004)

(*通信作者电子邮箱lblc2006@163.com)

SQLite数据库被众多即时通信软件用于存储历史数据。在即时通信取证过程中，犯罪分子为阻碍司法部门的调查，往往隐藏、删除或覆盖重要的通信数据。目前的数据恢复方法效率较低，无法恢复被覆盖的数据。针对上述问题，提出了一种基于SQLite的内容雕刻算法，分析SQLite数据库文件的存储特性和数据删除机制，以空闲域为单位形成空闲域链表，以页结构为单位进行细粒度的内容雕刻，并根据数据被覆盖的位置对零散数据块进行有效拼接。实验结果表明，SQLite内容雕刻算法可有效在本地和移动终端恢复即时通信的历史数据，当数据库未受损时，恢复率可达到100%；而当删除域受到不同程度的覆盖时，恢复率仍然可达到50%左右，并具有较高的效率。

SQLite；删除域；即时通信；取证调查；内容雕刻；恢复率

0 引言

即时通信(Instant Messaging，IM)以其即时性、稳定性、安全性，以及多格式交流等特性，已成为当今通信的主要手段之一。据中国互联网络信息中心(China Internet Network Information Center, CNNIC)统计数据[1]，截止2016年1月，我国网民中即时通信用户的规模达到6.24亿，占网民总体的90.7%，其中手机即时通信用户5.57亿，占手机网民的89.9%，在我国网络应用使用率中排名第一。与此同时，利用即时通信软件进行经济诈骗、毒品交易等的恶意犯罪事件逐年上升。尤其对于市场份额增长迅速的WhatsApp、微信、陌陌等移动即时通信软件，谣言、暴力、色情等问题在这些新型社交平台上快速泛滥。2015年5月，北京市网络安全反诈骗联盟共接到网络诈骗报案4 920例，报案总金额高达1 772.3万元，其中借助即时通信的案件占比例为37.2%[2]。

SQLite[3-4]是一款轻量级嵌入式的关系型数据库，完全兼容数据库事务正确执行的四要素Atomicity，Consistency，Isolation，Durability(ACID)，并实现了大部分SQL标准，使用动态类型的SQL语法。由于SQLite具有较好的灵活性和兼容性，以及本地存储特性，许多即时通信软件采用SQLite数据库来存储其产生的历史数据[5]，例如QQ、Skype、微信等。但犯罪分子往往对SQLite中的数据进行隐藏、删除、覆盖等反取证破坏，在取证过程中，应最大限度地恢复出已被破坏的重要数据。文献[6]中针对恶意销毁行为，研究了二进制可执行文件的恢复方法；文献[7]通过分析Ext2/3文件系统，研究了提高恢复效率的方法；文献[8]研究了如何根据YAFFS2 和SQLite重构用户行为，但并未对其数据恢复进行深入研究，恢复重构率较低；文献[9]利用YAFFS2文件系统的out-of-place-write策略，以时间线为依据来恢复数据库内用户操作记录，但对于数据库中被覆盖破坏的数据无法有效恢复。

本文提出一种基于SQLite内容雕刻的即时通信取证方法，利用SQLite的存储特性和数据删除机制，以空闲域为单位形成空闲域链表，以页结构为单位进行细粒度的内容雕刻，并根据数据被覆盖的位置对零散数据块进行有效拼接。该方法能实现细粒度的恢复效果，提高信息恢复的恢复率，为取证人员提供了一种有效的即时通信取证方法。

1 SQLite文件结构分析

1.1 数据库文件头

SQLite数据库的基本存储单位是页(page)，页的大小默认为210Byte。数据库中信息的读、写、删除操作均是以页为单位进行，页的类型有B-tree页、B+tree页、空闲页、溢出页等，页的编号从1到n。

SQLite数据库中的数据存储在多个Btree页中，一个完整的Btree页主要包含三种类型的数据结构：文件头(根页)、页头和单元内容区。数据库文件的第一个页(根页)包含100Byte的文件头信息，称作文件头页。数据页采用B+tree页，索引页采用B-tree页。

文件头主要用于记录数据库的头标识、页大小、空闲页地址、编码方式和版本等重要信息，用WinHex打开微信中存储位置信息的数据库revsers_geo_cache.db，如图1所示，其中偏移地址0x00 00～0x00 63为文件头详细信息，文件头的部分元素解析如表1所示。

图1 SQLite文件头

表1 SQLite文件头格式解析

文件头前16Byte是固定标识，即字符串“SQLitefromat300”；

第17、18Byte“0x10 00”表示页大小为4 096Byte；

第19、20Byte“0x01 01”表示该数据库为可读可写版本；

第25、26、27、28Byte“0x00 00 00 03”表示该数据库事务操作次数为3；

第97、98、99、100Byte“0x00 2DE2 25”表示该数据库的版本号。

1.2 Btree页结构

在数据库中每张表或者每个索引对应一个Btree页，一个Btree页一般由页头、单元指针数组、未分配空间、单元内容区、保留区组成，如图2中间部分所示;Btree页页头的结构组成如图2上半部分，其格式解析如表2所示;页单元结构由单元头和单元内容组成，如图2下半部分所示，其相应的格式解析如表3所示。

图2 Btree页单元结构

图3是数据库revsers_geo_cache.db文件中一个完整的页结构，从偏移地址0x10 00～0x1FF0是该页所包含的物理数据。

0x0C31表示单元内容区起始地址偏移量为0x0C31，即0x10 00+0x0C31=0x1C31；

0x87 4C表示Payload数据的字节数，转化为定长为0x03CC；

0x01表示在sqlite_master表中对应记录的RowID，值为0x01；

0x05表示记录头包含5Byte；

0x03表示字段1，其长度为3Byte的整数，内容为：“0x05 4FFC”，换算成十进制为348 156；

0x03表示字段2，其长度为3Byte的整数，内容为：“0x11 54 99”，换算成十进制为1 135 769；

0x8F0F表示字段3，该字段的类型是TEXT，长度不固定，0x8F0F表示字段长度，转换为定长为0x07 8F=1 935，可知字段长度为(1 935-13)/2=961=0x03C1，对应数据为地址0x1C3F～0x1FFF之间的物理数据[10]。

表2 Btree页页头格式解析

表3 Btree页页单元格式解析

图3 Btree页结构

2 SQLite数据删除机制

通过分析SQLite文件的逻辑层和物理层，一个逻辑表中的数据主要存储在B+tree叶子页中，但是从逻辑层对该叶子页数据进行操作时，需要文件中的根页和内部页的配合才能正常操作。而当数据库删除表中部分数据时，其删除操作只是将指向该数据单元的指针进行重定向，将其定向到空闲块链表中[11]，其单元内的Payload并没有改变。从物理层分析，该区域仍然存在相应的物理数据[12]，因此，当数据库执行一些删除操作时，数据库的大小并没减小[13]；但是从逻辑层分析，因为指向删除单元的指针告诉逻辑层，该数据块为空闲区域[9]，其所占的空间已释放，新数据可以占用。其数据删除前后的对照如图4所示。

由图4可知，数据被删除后，本页单元数由0x00 01变成了0x00 00；本页的第一单元起始地址偏移量由0x0C31变成下一页的地址偏移量0x10 00，即将地址为0x1C31～0x1FFF的区域作为空闲域。同时页单元数据区中Payload的大小由0x87 4C变成0x00 00，表示该页单元的数据为0。但Payload内的物理数据值并未改变，如图4阴影区域所示。因此通过分析SQLite的存储特性，设计相应的恢复算法即可恢复出数据库中被删除的数据。

图4 数据删除前后对比

3 基于SQLite的内容雕刻算法

在逻辑层[3]，数据都存储在数据库的表结构中，对于未删除的数据我们可以直观地浏览，而对于已删除的数据，只有从数据库物理文件中恢复才能看到。

根据SQLite数据库的结构和其数据存储特性，本文设计了基于SQLite的内容雕刻算法，其主要思想是以空闲单元为单位，形成删除域链表，并根据其数据是否被覆盖，以及被覆盖的部位进行细粒度的数据恢复。其算法如下：

Algorithm:fine-grainedrecoveryinSQLiteInput:DB_files;Output:SegmentandPages./*获取恢复数据库表*/

1)

if∀table∈Object_table

2)

For ∀page∈table

3)

Pages=Pages+page

4)

End For

/*未被覆盖区域的雕刻恢复*/

5)

For ∀freeblock∈table

6)

freeblocks=freeblocks+freeblock

7)

End For

/*被覆盖区域的拼接雕刻恢复*/

8)

For ∀freeblock[i] ∈freeblocks

9)

Iffreeblock[i] is covered

10)

If covered in top

11)

Segment[i]=freeblock[max]

12)

Else If covered in middle

13)

Segment[i]=Segment[i]+Segment[i-1]+Segment[i+1]

14)

Else covered in buttom

15)

Segment[i]=freeblock[i]

16)

ElsePages=Pages+freeblock[i]

17)

End For

18)

End If

该算法主要分为两个阶段：第一阶段遍历表中的页节点和空闲单元，根据页节点将所有叶子内的数据提取并保存为正常数据；第二阶段将所有空闲单元形成删除域链表，遍历删除域链表，并根据删除域是否被覆盖，以及其覆盖的位置，如头部、中间、尾部，来最大化恢复删除域内的信息。

传统的文件恢复算法一般以文件为单位进行数据恢复，即设计相应算法匹配文件头标识和文件尾标识，读取中间相应的数据即可恢复出相应的文件。但是对于像SQLite这种具有结构化离散存储特点的文件，当数据被删除，其填充的新数据将干扰数据恢复的逻辑性、真实性和准确性。本文所设计的基于SQLite的内容雕刻算法在SQLite数据恢复过程中，以文件中的空闲页为单位组成的删除链表为恢复对象，避免填充的新数据对删除数据恢复的干扰，并根据被覆盖部位的特性最大化获取删除域中的信息，既保证了新数据和删除数据的逻辑结构性，又实现了最大化恢复效果，该算法实现的具体流程如图5所示。

图5 基于SQLite的内容雕刻算法流程

4 实验及结果分析

实验平台：ThinkPad L440笔记本电脑(Windows 7)、IPhone 4S手机(IOS 6.1.3)、PE-UL00华为手机(Android OS 4.4)；VS2010、SQLite Database Browser 2.1[14]等软件。

实验准备：正常使用实验设备上微信、陌陌、QQ进行信息交流两个月，并使用各即时通信的特色功能，如位置服务设计功能等正常操作。

文件删除方法：SQLite Database Brower是一款可以编辑db数据库，对其进行删除、插入操作的数据库管理软件。从三种平台上获取的db文件统一在Windows 7平台上基于SQLite Database Brower进行删除。文件的删除以页(记录)为单位，一次删除一页，完全清空一个db文件的内容需要进行多次删除操作。记录的大小采用默认值1 KB。

文件插入操作：在电脑平台上，可以使用SQLite Database Brower插入数据，在手机平台中可直接产生新的即时通信数据。

数据恢复方法：根据SQLite的文件结构，读取文件的十六进制数据，对其疑似删除区域的数据进行保存，不同于传统的文件雕刻，本文的雕刻方法能够选择性地雕刻文件中的特定数据块。

恢复率：恢复出来的字段占删除字段的百分比，如删除记录“今天天气太热”，恢复结果为“今天天气”，则恢复率为67%。

三个实验平台中微信、QQ的db文件数据恢复实验结果如表4～6所示。

表4 Windows 7平台数据恢复实验结果

表5 iPhone平台数据恢复实验结果

表6 Android平台数据恢复实验结果

实验结果表明，本文设计的基于SQLite的内容雕刻算法在恢复较多的删除记录时，性能稳定，恢复时间不随插入操作的增多而受到影响，具有较高的效率。当数据库被删除域未被覆盖的情况下，恢复率可达到100%；当新创建数据占原数据大小的30%以下时，删除域已被部分覆盖，恢复率可达80%以上；当新创建数据占原数据大小的50%左右时，恢复率保持在60%～70%；当新创建数据占原数据大小的80%以上时，删除域受到的破坏较为严重，其恢复率仍然可达到50%左右。可以看出，本文方法能实现在不同的本地和移动终端最大限度恢复出数据的目的。

传统的文件恢复算法以整个文件为数据恢复单位，而本文算法的恢复单位为数据库内部空闲单元组成的删除域，即数据库中结构性信息块；同时根据删除域被新数据覆盖的情况，对零散删除域进行有效的拼接，实现细粒度的恢复效果，从而尽可能恢复出被删除的数据，针对数据库内结构性的数据恢复具有较强的实用性。

即时通信会话的特点是口语化和随意性，会话中的某些关键字段可能成为案件审理和侦破中的关键证据，通过细粒度的恢复，即使部分已删除数据被覆盖，仍可以获取即时通信中的会话片断。而文献[8-9]提出的方法只是将数据库中未被覆盖的区域进行雕刻恢复，无法有效恢复覆盖区域的数据，所以本文提出的文件雕刻算法的取证价值更强。

5 结语

本文提出一种基于SQLite的内容雕刻算法，提高了即时通信取证数据恢复率。通过分析SQLite数据存储的结构特性和其删除机制，以空闲域为单位形成删除域链表，以页结构为单位进行细粒度的数据雕刻，并根据删除域被覆盖的位置情况进行零散数据域的有效拼接，达到最大化的恢复效果。但是部分删除域被多次覆盖形成的多段碎片信息无法有效拼接，因此下一步的研究工作主要是研究SQLite数据库中多段碎片信息的深度挖掘与跨域重组。

References)

[1] 中国互联网络信息中心.第37次中国互联网发展状况统计报告[R/OL].[2016- 02- 12].http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm.(China Internet Network Information Center.The 37th statistical report on Internet development of China [R/OL].[2016- 02- 12].http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm.)

[2] 中国电子银行网.2015年第一季度网络犯罪数据研究报告 [R/OL].[2016- 04- 29].http://hy.cebnet.com.cn/20150504/101173514.html.(CEBNET.Cybercrime data report of the first quarter of 2015 [R/OL].[2016- 04- 29].http://hy.cebnet.com.cn/20150504/101173514.html.)

[3] RAMISCH F, RIEGER M.Recovery of SQLite data using expired indexes [C]// IMF 2015: Proceedings of the 9th International Conference on IT Security Incident Management & IT Forensics.Piscataway, NJ: IEEE, 2015: 19-25.

[4] KANG W-H, LEE S-W, MOON B, et al.X-FTL: transactional FTL for SQLite databases [C]// SIGGMOD 2013: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data.New York: ACM, 2013: 97-108.

[5] 孟贺.基于Android的即时通讯系统的设计与实现 [D].济南:山东大学, 2014：17-23.(MENG H.The design and development of instant messaging system based on Android platform [D].Jinan: Shandong University, 2014: 17-23.)

[6] HAND S, LIN Z, GU G, et al.Bin-Carver: automatic recovery of binary executable files [J].Digital Investigation, 2012, 9(Supp.): S108-S117.

[7] LEE S, SHON T.Improved deleted file recovery technique for Ext2/3 file system [J].The Journal of Supercomputing, 2014, 70(1): 20-30.

[8] XU M, YAO J, REN Y, et al.A reconstructing Android user behavior approach based on YAFFS2 and SQLite [J].Journal of Computers, 2014, 9(10): 2294-2302.

[9] WU B, XU M, ZHANG H, et al.A recovery approach for SQLite history recorders from YAFFS2 [C]// ICT-EurAsia 2013: Proceedings of the 2013 International Conference on Information and Communication Technology, LNCS 7804.Berlin: Springer-Verlag, 2013: 295-299.

[10] SQLite.File format For SQLite databases [EB/OL].[2016- 04- 29].http://www.sqlite.org/fileformat2.html.

[11] PARK J, CHUNG H, LEE S.Forensic analysis techniques for fragmented flash memory pages in smartphones [J].Digital Investigation, 2012, 9(2): 109-118.

[12] PEREIRA M T.Forensic analysis of the Firefox 3 Internet history and recovery of deleted SQLite records [J].Digital Investigation, 2009, 5(3/4): 93-103.

[13] JEON S, BANG J, BYUN K, et al.A recovery method of deleted record for SQLite database [J].Personal & Ubiquitous Computing, 2012, 16(6): 707-715.

[14] AL MUTAWA N, BAGGILI I, MARRINGTON A.Forensic analysis of social networking applications on mobile devices[J].Digital Investigation, 2012, 9(Supp.): S24-S33.

This work is partially supported by the National Natural Science Foundation of China (60903220), the Science and Technology Project of Zhengzhou (10PTGG3415).

MA Qingjie, born in 1987, M.S.His research interests include digital forensics.

LI Binglong, born in 1974, Ph.D., associate professor.His research interests include digital forensics, information system disaster recovery.

WEI Lina, born in 1990, M.S.Her research interests include Linux file system forensics.

File recovery based on SQlite content carving

MA Qingjie1,2, LI Binglong1,2*, WEI Lina1,2

(1.InformationEngineeringUniversity,ZhengzhouHenan450004,China;2.StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,ZhengzhouHenan450004,China)

The SQLite is applied by a number of Instant Messaging (IM) softwares for history data storing.In the process of IM forensics, to impede the investigation of the judiciary, the important SQLite data are often hidden, deleted or overwritten by criminals.The current data recovery methods are inefficient and cannot extract the overwritten data.A content carving algorithm based on SQLite was proposed to resolve the above problems.According to SQLite database storage characteristics and data deletion mechanism, the free domain was regarded as units to form idle list, the page content was used to grain structural units of engraving, and the scattered blocks of data were spliced efficiently on the basis of the position of data overwritten.The experimental results show that the propsed SQLite content carving algorithm can effectively recover IM data in local and mobile terminals; the recovery rate reaches 100% when the database is not damaged, and the recovery rate still reaches about 50% when the delete area is overwritten in different degrees.

SQLite; delete area; Instant Messaging (IM); forensics and investigation; content carving; recovery rate

2016- 08- 15;

2016- 08- 30。

国家自然科学基金资助项目(60903220);郑州市科技攻关项目(10PTGG3415)。

马庆杰(1987—),男,河南安阳人,硕士,主要研究方向:数字取证; 李炳龙(1974—),男,河南新乡人,副教授,博士,CCF会员,主要研究方向:数字取证、信息系统容灾处理; 位丽娜(1990—),女,河南周口人,硕士,主要研究方向:Linux文件系统取证。

1001- 9081(2017)02- 0392- 05

10.11772/j.issn.1001- 9081.2017.02.0392

TP309.2;TP

A