0 引言

即时通信(Instant Messaging，IM)以其即时性、稳定性、安全性，以及多格式交流等特性，已成为当今通信的主要手段之一。据中国互联网络信息中心(China Internet Network Information Center,CNNIC)统计数据^[1]，截止2016年1月，我国网民中即时通信用户的规模达到6.24亿，占网民总体的90.7%，其中手机即时通信用户5.57亿，占手机网民的89.9%，在我国网络应用使用率中排名第一。与此同时，利用即时通信软件进行经济诈骗、毒品交易等的恶意犯罪事件逐年上升。尤其对于市场份额增长迅速的WhatsApp、微信、陌陌等移动即时通信软件，谣言、暴力、色情等问题在这些新型社交平台上快速泛滥。2015年5月，北京市网络安全反诈骗联盟共接到网络诈骗报案4920例，报案总金额高达1772.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)，页的大小默认为2¹⁰ Byte。数据库中信息的读、写、删除操作均是以页为单位进行，页的类型有B-tree页、B+tree页、空闲页、溢出页等，页的编号从1到n。

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

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

文件头前16 Byte是固定标识，即字符串“SQLite fromat3\000”；

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

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

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

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

1.2 Btree页结构

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

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

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

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

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

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

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

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

0x8F 0F表示字段3，该字段的类型是TEXT，长度不固定，0x8F 0F表示字段长度，转换为定长为0x 07 8F=1935，可知字段长度为(1935-13) /2=961=0x 03 C1，对应数据为地址0x1C 3F~0x1F FF之间的物理数据^[10]。

2 SQLite数据删除机制

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

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

3 基于SQLite的内容雕刻算法

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

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

  Algorithm: fine-grained recovery in SQLite

  Input: DB_files;

  Output: Segment and Pages.

  /*获取恢复数据库表*/

  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)    If freeblock_[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)    Else Pages=Pages+freeblock_[i]

  17)   End For

  18)  End If

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

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

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所示。

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

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

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

5 结语

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