Android系统删除数据恢复方法研究

方冬蓉,张秋余,董瑞洪,文 森

(兰州理工大学计算机与通信学院,兰州730050)

Android系统删除数据恢复方法研究

方冬蓉,张秋余,董瑞洪,文 森

(兰州理工大学计算机与通信学院,兰州730050)

随着移动通信技术的发展和应用的推广,手机犯罪成为新的犯罪趋势,手机取证是打击该类犯罪的一个有效手段。直接调用API方法不能恢复Android手机数据,现有方法存在无法恢复删除数据部分被覆盖的问题。为此,通过分析Android系统SQLite数据库的文件结构和数据记录的寻址方式,提出一种Android系统删除数据恢复方法,即探测估算预提取数据所在表的每个Type字段,提取恢复删除数据,结合尽最大努力恢复方法,针对删除数据部分被覆盖的情况,讨论其恢复的可能性并进行获取。在Android手机模拟器上进行验证,结果表明,该方法能成功恢复删除数据,与传统方法相比,在不影响信息提取精确度的前提下,提高了删除数据的恢复率。

手机取证;Android系统;SQLite数据库;数据删除;逻辑提取;物理提取

1 概述

当前,智能手机随着其功能越来越强大且便携,手机成为犯罪分子的一种新型作案工具,为打击犯罪,手机取证显得尤为重要。所谓手机取证是指在健全的取证环境中,使用恰当的方法从手机及相关设备中提取并恢复数字证据的科学[1]。这些数字证据包括通话记录、短信息、电话簿等。

在手机取证中,最重要的是删除数据的恢复。目前,国内外已有不少研究人员对手机数据提取恢复进行研究,文献[2]指出由于手机操作系统的权限问题,只能提取系统允许访问的内容,称为“逻辑提取”。随后,文献[3-4]分别提出将手机芯片拆除,直接对芯片进行数据读取解析,这样可得到删除数据,但面临的问题是难度系数较高,称为“物理提取”。文献[5]在2010年提出flasher boxes获取方法,它是绕过手机操作系统对手机底层信息进行获取,该方法的局限性在于对每一型号手机存在一款flasher box,且无法得知在使用过程中是否改变手机数据。近年来,有很多手机取证工具[6]由于其便携、易操作及删除数据可恢复等,已广泛被司法部门采用。但是,手机取证工具的使用,会开启手机内存中的某些进程[7],改变了手机状态,减弱了证据的证明力。

安卓平台运用SQLite进行数据管理,早在2004年Pereira MT[8]针对火狐浏览器历史记录,提出基于SQLite的数据恢复,使得从数据库恢复技术入手进行手机数据的恢复成为可能。文献[9]提出从SQLite数据库通过估算PayloadSize、RowID及Header-size占据字节大小,即“暴力估算”方法来恢复删除记录的恢复方法,文中提出一个单元部分覆盖(非删除修改)的情况,恢复是不可能的。根据上述情况,本文依据安卓平台SQLite存储格式及删除存储原理,提出探测预提取数据所在表Type各字段大小的方法来恢复删除数据。并且对删除单元被新进入数据覆盖部分的情况,讨论其恢复的可能性。该方法可获取删除的数据,且不用在手机终端安装应用,提高证据可采性。

2 SQLite

2.1 SQLite物理结构

SQLite数据库文件由固定大小的“页”(page)组成,页的类型可以是Btree页、空闲(free)页或溢出(overflow)页。Btree页内部以单元(cell)为单位来组织数据,一个单元包含一个 payload(也称为Btree记录),单元是Btree页内部进行空间分配和回收的基本单位。从逻辑上讲,SQLite数据库文件实际是由多个多重的Btree构成[10]。每一个Btree存储一个表的数据或一个表的索引,索引采用B-tree,而表采用B+tree。

2.2 SQLite删除数据存储原理

根据SQLite数据管理机制,当手机删除数据后,手机终端无法看到删除的数据。但事实上,删除数据后仅是存储数据的单元头部信息改变,这块区域被识别为自由块,而真正的数据并未删除。因此,只要此区域未被新进数据覆盖,那么恢复是可能的。在SQLite中,根据删除区域包含的单元数量,删除区域可分为3种:删除区域包含部分单元,删除区域包含一个单元,删除区域包含多个单元。

当删除区域包含部分单元,根据覆盖范围大小,部分数据是可能恢复的。当删除区域包含一个单元,确定单元每个Type字段值,即可恢复记录数据区的数据。由于单元头部信息被修改,无法确定Type字段占据字节大小,本文提出估算Type字段大小的方法来恢复数据。

3 Type字段估算法

SQLite中,真正的数据存储在B+tree叶子页的单元Data区中,其单元结构如图1所示。其中, Type字段表示表的各字段,单元头和记录头均以可变长整数形式来存储数据值,可变长整数由1个～9个字节组成。事实上,当分析删除记录时,SQLite保存的整数在可变长度区域可能模糊定位。因此,恢复删除的数据,每个单元的可变长度区域的精确长度必须被识别。

图1 B+tree叶子页单元结构

当SQLite删除数据发生后,SQLite重新初始化单元的前4个字节,其中前2个字节表示下一个自由块的偏移量,后2个字节表示这个自由块的大小。

SQLite规定[11]:SQLite会对所有整型主键字段应用自动增长属性。针对该规定,对单元Payload中Type1进一步说明:由于RowID值已经在单元头部保存,因此将Type1类型设为NULL(占1个字节: 0x00),这样既节省空间又容易保持数据一致性。同时这样给恢复数据带来好处:由于删除操作改变单元前4个字节,且Type1是NULL,因此“有用的”Type(2～N)和Data区域均未改变。

图2为删除单元前4个字节修改后的几种情况,由于PayloadSize、RowID、Header-size及Type均以可变长整数形式来存储数据值,对上述“Type(2～N)和Data区域均未改变”结论做以下说明:

(1)若PayloadSize、RowID及Header-size每个区域占据1字节,Type1值为“0x00”占据1个字节,那么删除操作发生后,前4个字节改变,Type(2～N)字段和Data区域未变;

(2)若PayloadSize、RowID及Header-size共占据4字节,删除操作发生后,前4个字节改变,存留有Type(1～N)字段和Data区域;

(3)若PayloadSize、RowID及Header-size共占据大于4个字节,删除操作发生后,前4个字节改变,PayloadSize、RowID及Header-size会遗留部分, Type(1～N)字段和Data区域全部存在。

图2 删除单元前4个字节修改后的情况

综上所述,无论PayloadSize、RowID及Headersize每个区域占据多少字节(3个区域至少占据1个字节),Type(2～N)和Data区域均未改变。

恢复表中存储的具体数据,需要确定单元Payload中每个Type值来确定Data区域的数据信息。由于删除修改单元前4个字节,无法精确得知各字段大小。为了解决这个问题,根据删除操作后Type(2～N)和Data区域均未改变,通过估算Type字段大小,确定预提取的数据对应在表中的哪些字段中,来恢复数据。

4 数据提取恢复过程

在数据提取进行之前,首先要获得手机的最高权限。Android手机的短信息保存在mmssms.db文件中,若要恢复短信息,这里分两大过程,首先要获取mmssms.db文件,找到删除区域;然后对删除区域进行估算分析。提取恢复过程具体如图3所示。

图3 数据提取流程

4.1 预提取数据所在的数据库文件

连接手机后使用“adb pull”命令,可直接获取数据库文件。也可以在安卓开发工具 ADT中的DDMS下 “pull a file from the device”按钮一键获取。安卓平台用户数据存储在data/data文件夹下,存储有短信息、通信录及通信记录等数据库文件,可根据需求进行获取。

4.2 删除区域的收集

首先查找预提取表对应的树根页,定位预提取数据所在区域。根据预提取表名可在sqlite_master表中得知其根页编号。定位到根页后分析Btree中所有的页节点,根据页头中页类型标志找到所有B+tree叶子页,即可依据页的大小偏移量定位到预提取表的数据所在页。页头结构如表1所示。

表1 Btree页头格式

页类型标志:页头中的第一个字节是区分内部页和叶子页的标志位。该字节值为0x0D时,表示是B+tree的叶子页;为0x05时,表示B+tree的内部页;为0x0A时,表示B-tree的叶子页;为0x02时,表示B-tree的内部页。要找到预提取表所有B+tree叶子页,根据页类型标志,找到页启始为“0D”标志,即找到所有数据存储区域。

其次解析预提取数据区域,收集所有删除域。根据Btree页头格式,页头偏移为1的2个字节指向空闲块链表的头。由于空闲块前2个字节指向下一个空闲块,将单元内容区域中没有使用的空间收集起来形成一个空闲块链表,依据空闲块链表,可得到所有的空闲块,即删除域。

4.3 删除区域的检查

检查删除区域,并按单元对Type字段估算进行提取。当SQLite删除数据发生后,SQLite重新初始化一个单元的前4个字节。如图4所示,有颜色背景部分是一个单元的内容。

图4 单元删除前后对比

删除后无法精确各字段大小,需对各字段占据字节进行估算分析。

对于单元的各字段的估算法,其伪代码描述如下:

通过空闲块链表,找出每个空闲块,将每个空闲块存储到相应的一维数组中,现在读取一个数组,数组名为bb;查预提取表设定字段数量为k;初始从第i位开始读数据(i=4)。

当从数组第i位开始读取,判断其值大小来决定每个Type字段占据字节数,以此类推往后读取,直到读了k次结束,计算k个Type值之和sum1及k个Type字段占据字节数目和b。通过Type区占据字节b以及单元头未读数目i,计算 sum2值,即为Type区域紧接的Data域大小。

匹配sum1和sum2值,相等则估算成功,否则估算失败。继续从第i+1读取,依次匹配,直到bb数组结束为止。这样最终确定预提取的数据对应在表中的哪些字段中,就可从各字段中提取数据。

4.4 部分被覆盖单元的恢复

如果上述匹配恢复不成功,说明有可能是部分被覆盖或是几个单元合成一个空闲块,对空闲块包含几个单元的情况将其分割成一个一个单元进行恢复。一个单元部分被覆盖的情形如图5所示。

图5 单元部分被覆盖

对一个单元部分被覆盖的情形,恢复可能性根据被覆盖率来决定。覆盖率不能用一个精确的百分比数字来表示,因为一个单元的存储实际数据区域(Data区域)的大小是根据实际情况动态分配的,但是对于覆盖率可以根据实际情况用区域类型来描述。如图5灰色部分所示,是Data区域部分被覆盖的情形,现针对实验部分所选实验环境(android4.2模拟器),描述覆盖率所指大致范围。

删除一条信息又进入一条后,是从单元后部进行覆盖(如图5灰色部分所示)。单元部分被覆盖前后对比如图6所示。在android4.2中,存储短信息的表字段有17项,分别是_id,thread_id,address, person,date,date_sent,protocol,read,ststus,type, reply_path_present,subject,body,service_center, locked,error_code,seen。这17项占据Type区域,如图6(a)方框标记所示。这17个字段对应图5中的Type区域,即Type1～Type17,说明了Data区域的Data1～Data17的内容具体信息。

图6 单元部分被覆盖前后对比

综上所述,覆盖率是指Data区域被覆盖的范围。由于一个单元的Data区域大小根据实际情况动态分配,因此不能用一个精确的定量关系来表示覆盖率和可恢复程度之间的关系。用逻辑表示,可恢复程度根据Data区域覆盖率的大小而定:覆盖率越小,可恢复性越高;覆盖率越大,可恢复性越低,直到Data区域完全被覆盖,可恢复性为0。

4.5 尽最大努力恢复方法

若Data区域完全被覆盖,则完全无法恢复,但可知这里存在过短信息;若只覆盖Data区域的一部分,那么恢复数据是有可能的。但对于这片区域,由于删除后改变了单元头内容,无法精确定位Data区域从哪里开始、到哪里结束以及每个数据类型占据字节数,提出使用“尽最大努力恢复”方法来恢复。

所谓的尽最大努力恢复方法,实际就是将这个无法精确分段的整片区域从头到尾完全转译,之后在转译后的数据信息中进行语义分析,找到有用的数据信息、识别电话号码等。

如图6(a)所示,偏移量从23B5～23FF是之前一条短信息存储单元,后被23D6～23FF这条短信单元部分覆盖。如图6(b)所示,灰色部分为新进信息单元,椭圆框是原信息被覆盖后Data域剩余部分。从右边的“1399487xxxx”可发现,信息中的电话号码仍存在,而短信内容被覆盖。

5 实验结果及分析

5.1 实验验证

为了证明上述恢复方法的可行性,将通过实验对该方法进行验证。实验选取4.2版本android手机模拟器作为实验对象,使用SQLite数据库浏览器以及WinHex作为辅助,以提取短信息内容为目的,运用安卓开发工具ADK来对底层数据库文件进行解析。作为删除数据恢复的对比,分别从逻辑提取和物理提取2个方面进行提取分析。最后针对部分被覆盖的信息进行单独提取恢复。

为实现结果清晰明了,现对sms表中信息设置如下:

(1)从手机终端加入4条短信息,其中第一条短信息较长,获取mmssms.db文件;

(2)从手机终端删除 2条短信息,获取mmssms.db文件;

(3)从手机终端再加入1条较短的信息,获取mmssms.db文件。

5.2 逻辑提取分析

逻辑提取[12](logical acquisition)是在当前文件目录下寻找相关证据,不涉及删除的信息。所有与应用程序相关的信息都存放在/data/data目录下,安卓系统短信息存储在datadatacom.android.providers. Telephonydatabases下。利用ADB命令可将其取出。图7和图8分别是最初的4条短信息和删除2条后的结果。

图7 4条短信息的逻辑提取

图8 2条短信息的逻辑提取

5.3 物理提取分析

物理提取(physical acquisition)是指用一定的方式从镜像文件或底层数据存储文件中寻找并恢复删除的数据。图 9是删除 2条短信后的提取恢复结果。

图9 删除的2条短信恢复结果

5.4 部分被覆盖提取分析

在实验设置中,最后加入一条较短信息,其目的是实现删除的较长信息被较短信息部分覆盖后的恢复。先来用WinHex分析底层文件,分析如图10所示。

在图10中,图10(a)偏移量9F29～9FFF是最初删除的较长短信存储区域,存储空间大小为00D7。图10(b)画框部分,偏移量9FB7处开始,直到9FFF结束,是新进入短信单元,占73 Byte。这个自由块的大小由之前的00D7(215 Byte)变为008E (142 Byte)。

图10 删除信息被覆盖前后对比

由于Data区域未被全部覆盖,恢复是可能的。图11是部分被覆盖后恢复的结果,可根据语义分析或常识来判断,电话号码是“1364-X”,部分短信息内容为“今天是您的生日,愿所有的快乐,所有的幸福,所有的温馨,所有的好运”。

图11 部分被覆盖后的恢复结果

5.5 结果分析

本文采用的实验环境是android4.2,实验数据是发送的多条短信,包括删除的和未删除的。最后用训练好的参数实现物理提取,获取信息条数,将实际添加的信息和提取结果相比较,验证探测估算法和“尽最大努力恢复”法相结合的有效性及精确度。

5.5.1 提取性能的对比

从表2的数据可看出,“暴力估算”信息提取率为93%。而本文方法不仅对手机中删除的信息能够恢复,并且对删除信息部分被覆盖的数据也能部分恢复,信息提取率提升到95%。即在手机终端无法看到25%的信息,通过探测估算结合尽最大努力恢复方法后,可以大部分恢复提取。

表2 提取性能的对比

5.5.2 恢复性能对比

从表3的数据可看出,“暴力估算”能提取删除的短信息,信息提取率为92%,对删除的25条信息,实际恢复了18条,恢复率为72%。通过探测估算结合尽最大努力恢复方法,对删除的25条信息,实际恢复20条,恢复率达到80%,恢复信息条数增加,恢复率提高。

表3 恢复性能的对比

总之,由提取结果分析得出:本文提出的恢复方法可以对手机中现存的信息、删除的信息以及删除部分被覆盖的短信息进行较为准确的获取,提取率及恢复率优于仅估算PayloadSize、RowID及Headersize占据字节大小来恢复删除记录的“暴力估算”恢复方法。并且本文对于部分被覆盖的单元使用尽最大努力恢复法,恢复部分被覆盖的已删信息,进一步提高恢复率。

6 结束语

依据SQLite存储的数据删除后并未进行物理删除,采用数据库恢复技术,可进行删除数据恢复提取。本文根据探测估算恢复表中每个Type字段占据字节大小,结合尽最大努力恢复的方法,对删除数据及删除数据部分被覆盖的信息进行恢复提取。此外,尽最大努力恢复方法针对部分覆盖的短信息,在不改变信息提取精确度的前提下,为恢复部分覆盖的短信息提供了可能。本文方法是针对数据提取与恢复,对于司法部门,提取与恢复的数据将作为证据被法庭采用,需要保证数据的可采性与真实性。所以下一步的研究工作是实现证据提取过程中数据的完整性,即进一步提高恢复数据的可采性。

[1] 张明旺.基于手机的电子证据获取技术研究[J].电脑知识与技术,2012,13(8):3093-3095.

[2] Paul M C.Forensic Analysis of Mobile Phones[D]. Adelaide,Australia:University of South Australia,2005.

[3] Svein W.Forensic Analysis of Mobile Phone Internal Memory[J].Advances in Digital Forensics,2006, (194):191-204.

[4] Marcel B,Coert K.Forensic Data Recovery from Flash Memory[J].Small Scale Digital Device Forensics Journal,2007,1(1):1-17.

[5] Jonkers K.The Forensic use of Mobile Phone Flasher Boxes[J].Digital Investigation,2010,(6):168-178.

[6] Jansen W,Ayers R.Guidelines on Cell Phone Forensic: Recommendations of the National Institute of Standards and Technology[EB/OL].[2013-09-20].http:// www.docin.com/p-437911651.html.

[7] 赵亚杰,陈 龙.面向手机取证的细粒度数据完整性检验方法[J].计算机工程与设计,2012,33(11): 4091-4094.

[8] Pereira M T.Forensic Analysis of the Firefox 3 Internet History and Recovery of Deleted SQLite records[J]. Digit Investigation,2009,5(3):93-103.

[9] Jeon S,Bang J,Byun K.A Recovery Method of Deleted Record for SQLite Database[J].Pers Ubiquit Computer,2012,16(6):707-715.

[10] Hipp D R.The SQLite Database File Format[EB/OL]. (2013-05-30).http://www.sqlite.org/fileformat.html.

[11] Owens M.TheDefinitiveGuidetoSQLite[M]. New York,USA:Springer-Verlag,2006.

[12] 姚 伟,沙 晶.Android智能手机的取证[J].中国司法鉴定,2012,(1):45-49.

编辑 索书志

Research on Recovery Method of Deleted Data for Android System

FANG Dong-rong,ZHANG Qiu-yu,DONG Rui-hong,WEN Sen
(School of Computer Technology and Communication, Lanzhou University of Science and Technology,Lanzhou 730050,China)

With the development and the wide application of mobile communication technology,mobile phone crimes become a new trend,and mobile phone forensics is an effective means to crack down on mobile phone crimes.In view of the problems that the traditional method calling API directly cannot restore the data of Android mobile phone and existing methods cannot restore the deleted data that section covered,through deep analysis of Android SQLite database file structure and the addressing mode of data record,the method that detects and estimates each Type field in the table is proposed.This method uses extraction recovery to process deleted data,combines“restore method with best effort”to discuss the recovery possibility of the deleted data that part covered,and obtains the deleted data.This method is carried out on the Android emulator.Experimental result shows that this method can restore deleted data successfully,and compared with traditional algorithm,it improves the recovery rate of deleted data with no affection of the information extraction accuracy.

mobile phone forensics;Android system;SQLite database;data deletion;logical extraction;physical extraction

1000-3428(2014)10-0275-06

A

TP309

10.3969/j.issn.1000-3428.2014.10.051

方冬蓉(1988-),女,硕士研究生,主研方向:电子取证;张秋余,研究员、博士生导师;董瑞洪,副教授;文 森,工程师。

2013-08-12

2013-10-07E-mail:fangdrgo@163.com

中文引用格式:方冬蓉,张秋余,董瑞洪,等.Android系统删除数据恢复方法研究[J].计算机工程,2014,40(10):275-280.

英文引用格式:Fang Dongrong,Zhang Qiuyu,Dong Ruihong,et al.Research on Recovery Method of Deleted Data for Android System[J].Computer Engineering,2014,40(10):275-280.