SQLite是一款轻型数据库，它能够支持Windows/Linux/Unix等主流的操作系统，能够跟很多的程序语言相结合。SQLite以占用资源非常低、处理速度快、使用方便、代码开源等一系列特性，已经被广泛的应用于嵌入式设备、Android设备和各种各样的应用平台等领域。此外，SQLite存放的数据信息丰富多样，包含Android设备的通讯录、短信、通话记录、微信、QQ聊天记录以及各种浏览器上网访问记录等。
SQLite
随着SQLite的广泛应用,针对其删除记录恢复的研究技术也层出不穷。如何恢复SQLlite数据库中删除的数据记录？本期唐老师给我们介绍一种针对数据记录存储单元块删除恢复的方法。
一、操作原理
众所周知，SQLite 数据库文件由固定大小的“页 (page)”组成，第1页的前100个字节为SQLite文件的二进制头，每个页由Btree结构存储。二进制结构不再详细介绍，万能的网络一搜一大把，这里详细介绍下数据记录单元的存储结构。
1、数据记录单元（cell）储存结构
在SQLite数据库中，同一张表中的数据记录单元（cell）具有相似的数据类型。如图表1，展示了cell的存储结构，从Header_Size到DataN称为一个Payload。
Payload_SizeRowidHeader_SizeType1......TypeNData1......DataN
表1：数据库记录cell存储结构
Payload_Size:可变长整数，占用1～9个字节，表示Payload数据大小；
Rowid:可变长整数，占用1～9个字节，数据库记录的Rowid值；
Head_Size:可变长整数，占用1～9个字节，表示从Header_Size到TypeN的数据大小；
Type1...TypeN:可变长整数，占用1～9个字节，表示后面对应各字段DataN的数据类型和宽度，具体的解释见表2；
Data1...DataN:数据库表中各字段的数据；
表2：数据库字段类型和宽度详解
SQLite 中被删除的数据记录单元（cell）称为自由块（free_block），数据记录单元被删除后，cell的前4个字节被抹掉,1-2字节被标记为下一个自由块的偏移（free_block_offset），3-4字节表示整个自由块大小（free_block_size）。而第一个自由块的偏移在子页头结构中标记。free_block的存储结构如表3所示。其中Data区域包含部分的Header_Size或Type1，完整的Type2～TypeN，完整的Data1～DataN。
请输入图片描述
表3：free_block存储结构
2、恢复操作详细步骤
基于上述的存储结构描述，从表3中知道，删除记录cell的前4个字节已经被抹掉，被free_block的头给覆盖掉了，造成Payload_Size、Rowid、Header_Size和Type1这四个数据丢失，无法正确解析后续的Type和Data数据。要实现删除记录数据的恢复，就需要对PayLoad_Size、Rowid、Header_Size和Type1进行推算重构。具体实现步骤如下：
1
S01:计算Rowid宽度（占用字节数）。因为Rowid值是连续的，所以删除记录cell的Rowid宽度可通过相邻的未删除记录cell的Rowid计算得到。
2
S02:计算Payload_Size宽度（占用字节数）。由于free_block_size和Payload_Size相差范围为2～18个字节，即Payload_Size和Rowid的宽度，因此通过free_block_size的值范围计算得到Payload_Size。计算方法：由于可变长整型范围是1～9，因此可变长整型定义述规律即可计算具体数值占用的字节数。例如：free_block_size在0～0x7f之间，则宽度为1字节；在0x80～0x3FFF之间，则宽度为2字节等等，依次类推。
3
S03:Payload_Size=
free_block_size-PayLoad_Size宽度-Rowid宽度。得到Payload_Size和Rowid的宽度后，即能够准确定位到Header_Size的偏移起始位置。
4
S04:计算Header_Size值和宽度。因为删除记录cell只有前4个字节被占用，因此针对这4个字节长度的分情况分析，即可准确的计算出Header_Size和Type1。具体分类情况如下：
S041:若Payload_Size宽度+Rowid宽度>=4，则说明Header_Size和Type1未被覆盖，因此按表1存储结构即可完整解析Payload_Size、Rowid、Header_Size、Type1，实现此free_block的数据恢复。
S042:若Payload_Size宽度+Rowid宽度<4，又分为下述四种情况：
T1、Payload_Size宽度为1,Rowid宽度为1，Header_Size宽度为1，剩下1个字节属于Type1；
T2、Payload_Size宽度为1,Rowid宽度为1，剩下2字节属于Header_Size；
T3、Payload_Size宽度为1,Rowid宽度为2，剩下1字节属于Header_Size；
T4、Payload_Size宽度为2,Rowid宽度为1，剩下1字节属于Header_Size；
3、归纳总结
以上四种情况，利用枚举法即可计算出对应的Header_Size和Type1，根据宽度值可知四种情况的枚举最大次数分别是T1:16129，T2：16383，T3:127，T4:127，在实际计算过程其实用不了这么多次即可枚举出来，具体可结合数据表的字段类型和取值范围筛选过滤掉不符合条件的枚举情况，从而大大减少了枚举量。
由上述步骤精确的推算出PayLoad_Size值、Rowid宽度、Header_Size值和Type1值，完成一个free_block的cell头则重构完成，实现SQLite数据库删除记录的恢复。
二、金石之言
本文介绍的删除记录恢复方法，针对单个完整独立的删除块（free_block）能精确的推算重构出被覆盖的控制头信息，并且此方法很巧妙的利用了删除记录块相邻的未删除记录的Rowid来推算此自身的Rowid宽度，这个是关系整个方法能否准确计算Payload_Size的关键点。在S042步中结合表属性筛选过滤不符合要求的枚举情况，加速恢复过程也是本方法的一大亮点。
然而本方法的缺陷在于针对有连续删除块被整个到一块的情况，则会形成误判，导致枚举校验次数较多或者校验失效等情况。针对这种情况需结合表特征和数据记录上下文进行分析处理。
更多精彩技术资讯，只在公众号“ansheng47”和“ANSCEN-ISEC”