张 雪,狄 芳,苏 铓,俞 研

(1.南京理工大学 计算机科学与工程学院,江苏 南京 210094;2.三江学院 数理部,江苏 南京 210012)

安卓(Android)系统与应用程序作为一种新的、便捷的信息交流与传播方式日益为犯罪人员所关注。恶意应用程序通常会通过植入恶意代码来篡改和采集用户信息、窃取账号、构建僵尸网络以及获取root 权限等,对Android设备用户的数据资产安全造成了极大危害[1-3]。然而,在Android应用程序成为实施犯罪活动有利工具的同时,其活动的信息与过程也自动存储在Android设备的非易失性内存中,从内存中恢复的数据包含了与非法犯罪行为直接相关的重要证据数据。因此,针对Android取证的内存镜像数据恢复技术研究对于网络犯罪活动的调查有着重要意义。

目前,Android设备的数据恢复方法主要分为基于逻辑数据恢复方法和基于物理数据恢复方法。基于逻辑数据恢复方法是在逻辑层面获取特定应用程序的部分数据进行分析。Menahil等[4]通过Magnet AXIOM、XRY和Autopsy取证工具分析设备逻辑镜像中存储的证据数据。基于物理数据恢复方法是对通过物理通信电缆转储的非易失性内存镜像进行分析与恢复。基于物理数据恢复方法主要有文件系统分析、SQLite数据库分析等技术。在文件系统分析方面,Li等[5]基于用户数据分区镜像还原Ext4文件系统的目录,从而实现了对关键数据的定位。Jiang等[6]对基于MTK的Android设备内存镜像进行逆向解析,将文件系统的逻辑路径转换为相应的物理资源,然后根据证据数据的逻辑路径即可找到相应的物理资源。而在SQLite数据恢复方面,Jeon等[7]通过分析SQLite数据库文件的格式,提出了SQLite数据库自由块中数据记录的恢复方法。张艳姣等[8]通过分析QQ应用程序生成的SQLite数据库文件结构,提出一种基于SQLite内部记录格式的已删除数据恢复算法。

然而,上述数据恢复方法仍旧存在一些问题和挑战。基于逻辑数据恢复方法不能恢复已删除的数据,所以恢复的信息是有限的。基于物理数据恢复方法不仅可以恢复被删除的数据,还可以恢复被设备安全码锁定的数据[9],因此更受研究人员的青睐。但是其基于文件系统的数据恢复方法完全依赖于内存中的文件系统元数据,而随着系统中数据文件的更新、写入会导致部分元数据被擦除和丢失;同时,此方法不能识别由于内存异地更新机制[10]和copy-back操作[11]而被标记为无效的垃圾页;进一步地,仅仅针对某一文件系统进行研究所提出的数据恢复方法并不具有通用性,很难推广到其他文件系统。鉴于基于文件系统的数据恢复方法的局限性,SQLite数据恢复方法得到了越来越多的研究,这是因为SQLite数据库被广泛应用于各种厂商的Android设备,同时也不依赖于文件系统。目前,针对SQLite数据恢复方法的研究,多局限在操作系统层和数据库层,需要获取完整的数据库文件,当SQLite数据库文件损坏时,则无法有效恢复相关的数据。

针对上述不足,本文提出了一种面向Android取证的内存镜像数据恢复方法,这一方法对物理提取的非易失性内存镜像进行分析,实现未删除、已删除和垃圾页中数据的恢复;在内存镜像中根据页面特征定位有效内存页并根据页面类型提取页中存储数据的区域,进而恢复有价值的证据数据,可以确保只要内存页是完整的,即可恢复与之关联的数据,从而解决了不同文件系统存储机制差异所带来的挑战,并且能够恢复隐藏在文件系统之外的数据,对数据恢复的覆盖率较高。

1 非易失性内存与SQLite页结构分析

通常,对非易失性内存数据的操作涉及读、写、删除以及擦除操作。其中块是执行擦除操作的最小单元,而页则是执行读写与删除操作的最小单元。SQLite数据库中包含了与取证分析相关的重要数据,分片存储于内存中,其基本存储单元是页,所有读取、写入和删除操作均发生在页中,页的大小与内存页相对应,一般小于或等于内存页的大小。

1.1 非易失性内存

非易失性内存使用扇区的概念,扇区是一组块的集合,通常由256～1 024个块组成,而每个块由固定数量的页组成[10]。此外,页中包含一些“空闲区域”字节,通常用于存储元数据。

非易失性内存具有异地更新机制,即,在物理存储级别删除或更新数据后,将分配一个新的内存页来写入原内存页更新后的数据,而原内存页仅标记为无效,成为垃圾页,不做擦除操作,等待垃圾回收机制进行回收[12]。

当在非易失性内存中写入数据时,遵循空间局部性[13]原则。若在特定时刻引用了特定的存储位置,则随后的操作很可能会引用邻近的内存位置。

1.2 SQLite页结构分析

SQLite数据以大端对齐的形式存储于Android内存镜像中,其数据结构主要为B+树和B-树。其中,B+树结构主要用于存储数据表,其叶子页存储数据信息,而内部页则存储指向叶子页的指针信息;B-树结构主要用于存储数据库索引,其叶子页存储索引信息,而内部页则既存储索引信息,也存储指向叶子页的指针信息[7]。

B+树叶子页结构用于存储用户或应用程序数据。在其结构中,页头占8字节,其后为单元偏移量列表,单元偏移量列表存储指向同一页的每个单元的偏移量,每个偏移量均为2字节,存储数据的单元从页底部向上分配,所有单元集中在页的底部,称为“单元内容区”,单元偏移量列表和单元内容区之间的区域是空闲区域,属于内存页中的未分配空间[14]。

内存页中的未分配空间除空闲区域之外,还包括自由块,穿插于单元之间,存储已删除的数据,并以链的形式组织,页头指向自由块链的链首。

SQLite页中最小的实体是单元(Cell),每个单元包含3个部分:单元头、记录头和数据记录区域,其中,单元头由单元大小和ROWID组成,单元大小包含记录头和数据记录区域大小,ROWID表示这个数据记录在数据表中的行号。记录头包含记录头大小和字段类型(Type1至TypeN),其后是数据记录区域(Data1至DataN),通过分析Type,可以获得各个Data类型和对应的长度,进而进行数据恢复。单元大小、ROWID、记录头大小均以整型存储且长度可变,字段类型Type既可以是基本数据类型,也可以是BLOB或者TEXT,若为后者,则以可变长度的整型存储。可变长度整型以8 bit对齐,其最高位为标志位,值为0表示当前字节为这个整数的最后一个字节,值为1表示这个整数包含有后续字节。

SQLite数据库中所有表或索引的结构信息存储在SQLite_master模式表中,以B+树叶子页形式组织。SQLite_master模式表通常存储在SQLite数据库的第1页面中,对于较大的数据库文件,则存储在多个叶子页的单元内容区中。

1.3 数据删除机制

通过对SQLite页结构进行分析,可以发现B+树叶子页中存在未分配空间。当SQLite数据库执行删除操作时,并没有真正在内存中将数据记录删除,而是以未分配空间的形式标记此数据记录所在的存储单元。在B+树叶子页中,已删除数据通常以两种状态存在:①空闲区域,若空闲区域非零,则其中可能存在已删除数据;②自由块。当执行数据删除操作时,内存分配可以分为以下两种情况:

(1)若删除单元与空闲区域相邻,则合并为空闲区域,且结构保持不变。因此,空闲区域中既可能包含完整结构的单元,也可能包含自由块结构的单元。

(2)若删除单元与空闲区域不相邻,则删除单元变成自由块。

2 数据恢复方法

非易失性内存的磨损均衡[12]策略,使得文件在内存空间中的存储区域是不连续的,但是根据空间局部性原理,内存页中存储的数据均属于相同的文件,鉴于此,本文提出了一种面向Android取证的内存镜像数据恢复方法,其基本思想是:

扫描内存页,识别并提取存储有价值证据数据的有效内存页;利用Android非易失性内存与SQLite页结构的特点,根据其异地更新机制和空间局部性原理,恢复内存页中的数据,恢复对象涵盖了未删除数据、已删除数据和被标记为无效的垃圾页中的数据;利用模式匹配方法,判别恢复数据所归属的目标数据表,从而实现表结构与记录的恢复,进而完成SQLite数据库的重构。

2.1 有效内存页识别

在SQLite页结构中,有效内存页可以是B+树或B-树的内部页或叶子页,其中B+树叶子页中存储了应用程序生成的证据数据或者SQLite_master模式表。当执行删除或写等更新操作时,由于异地更新机制,将分配一个新的内存页来写入更新之后的页面内容,原内存页被标记为无效,成为垃圾页,其结构保持不变,当有新的内存页覆盖垃圾页时,对应的单元被新数据覆盖,而未被覆盖的单元及数据则残留于空闲区域中,新的内存页可能是B+树或B-树的内部页或叶子页。

在本文SQLite数据恢复算法中,页标志flag和字段特征可以有效识别非易失性内存中所有存储SQLite数据的有效内存页。SQLite页头结构如图1所示,若页标志为0x05、0x0D、0x02或0x0A则根据页头结构依次获取第一个自由块偏移量、单元数、单元起始地址和单元偏移量列表,然后对这些特征进行模式匹配,从而可以判断此页是否为有效内存页。

图1 SQLite页头结构

2.2 数据区域提取

识别有效内存页后,需要从不同类型的内存页中提取存储数据的区域,B+树叶子页中包括单元内容区、空闲区域和自由块区域,而其他类型的内存页中只需要考虑空闲区域即可。

对于B+树叶子页,如图1所示,读取其第一个自由块偏移量,若值非零,则获取这一页面的自由块链表,若自由块值为0x0000,则表示自由块链结束;从单元偏移量列表中读取每个单元的地址偏移,定位并提取单元内容区;空闲区域位于单元偏移量列表和单元内容区之间。而对于其他类型的内存页,使用相同的方法提取空闲区域。

2.3 数据恢复

2.3.1 表结构恢复

数据区域中既可能存储应用程序生成的用户数据,也可能是SQLite_master模式表,因此首先需要从数据区域中恢复表结构,作为判别数据所归属的目标数据表。

存储SQLite_master模式表的数据区域由类型、名称、对应的表名、根页和建表语句组成,因此利用关键字匹配方法识别存储SQLite_master模式表的区域,并从相关区域中提取建表语句,解析获得所有数据表表名和对应的字段类型和数量。

2.3.2 记录恢复

为了恢复有意义的证据数据,需要从数据区域中恢复数据记录,然后利用模式匹配方法,判别数据记录所归属的目标数据表并写入。根据内存数据的空间局部性原理,内存页中存储相同文件的数据,且其结构保持一致,因此仅需识别完整的数据结构,即可将这一页中的所有数据写入归属的目标数据表中。

(1)B+树叶子页。

B+树叶子页包含了单元内容区、自由块和空闲区域。对于单元内容区记录,从单元内容区中提取Type区域,利用模式匹配方法,与目标数据表列表的字段结构进行匹配,若成功则得到这一页数据所归属的数据表,此时,仅需要根据数据类型Type和数据记录Data的对应关系,将数据记录写入相应的目标数据表中即可。相应地,相同页面的自由块区域和空闲区域的数据记录也必然属于相同的数据表。

当单元内容删除后成为自由块时,单元结构中的Type1字段可能被覆盖,而其他后续字段值保持不变。为了保证数据一致性,Type1的缺省值设置为0x00。因此,对于自由块区域记录,仅需根据其缺省值确定Type1字段的位置,即可估计出自由块的Type区域,从而对应恢复数据记录Data。自由块区域记录恢复算法如表1所示。

表1所示自由块区域记录恢复算法中,首先定位自由块,通过自由块偏移量和大小提取相应的自由块;在单元中搜索值0x00,若这个值存在,则利用模式匹配方法将单元字段值与目标数据表中的字段类型进行匹配,直至Type区域与目标数据表中的字段类型匹配成功;若这个值不存在,则Type1字段可能被覆盖,此时,将自由块第4个字节值设置为0x00,重复上述模式匹配过程;若失败,则说明这一自由块Data区域已被全部覆盖,无法进行恢复。

表1 自由块区域记录恢复算法

若匹配成功,则提取Type区域和Data区域,将数据记录写入目标数据表中。若自由块中有多条数据记录,则重复上述过程。

空闲区域中既可能包含完整结构的单元,也可能包含自由块结构的单元,鉴于此,对于空闲区域记录,需要判断其单元结构,从而对应地恢复数据记录。空闲区域记录恢复算法如表2所示。

表2 空闲区域记录恢复算法

表2所示空闲区域记录恢复算法中,首先提取空闲区域中非零值,根据完整单元结构提取Type区域,利用模式匹配方法与目标数据表中的字段类型进行匹配。若成功,根据数据类型Type和数据记录Data的对应关系,将数据记录写入目标数据表中;否则根据表1所示自由块记录恢复算法进行记录恢复。若空闲区域中有多条数据记录,则重复上述过程。

(2)其余类型的内存页。

其余类型的内存页中仅需针对空闲区域中的数据进行恢复,其方法同B+树叶子页中的空闲区域记录恢复方法,但是由于B+树内部页存储指向B+树叶子页的指针信息,而B-树结构用于存储SQLite数据库的索引信息,其单元内容区未存储用户数据,因此不能简单依靠单元内容区的字段结构获得本页中的目标数据表。

内存中B+树内部页的部分空闲区域如图2所示,可见空闲区域起始处存在残留单元偏移量,是垃圾页未被覆盖的单元偏移量列表中的部分指针,因此残留单元偏移量指定的单元一定具有完整结构,B-树结构的内存页与之相似。从空闲区域中提取残留单元偏移量指定的单元并按照完整单元结构进行恢复,即可获取此页数据所归属的目标数据表,剩余数据记录则根据表2所示空闲区域记录恢复算法进行恢复。

图2 B+树内部页空闲区域

3 试验与结果分析

为了验证本文提出方法的有效性,使用真实手机验证了提出的恢复方法在真实场景中的有效性。所有的算法均使用Java语言实现,并运行在一台Intel(R)Core(TM)i7-2600 CPU@3.40 GHz 3.40 GHz处理器和16 GB内存的计算机上。

3.1 试验设计

在试验中,使用了4款由不同厂家生产的Android设备,其硬件和软件信息如表3所示。

表3 试验设备的硬件和软件信息

在运行恢复算法之前,首先获取Android设备的非易失性内存镜像,在对Android设备进行取证研究过程中,使用的设备、环境和技术均符合电子取证的基本规则,提取镜像确保证据数据的完整性。当前,Cellebrite UFED被认为是电子取证领域最好的硬件设备之一,因此,试验中使用Cellebrite UFED(V 7.34.1.23)提取Android设备的非易失性内存镜像。

非易失性内存镜像获取完成后,执行本文给出的内存镜像数据恢复方法。

3.2 试验结果分析

试验中,本文方法主要从恢复数据量、通用性、数据恢复能力、文件完整性和数据恢复效率等方面进行验证与分析,并与代表性的Android设备数据恢复方法以及商用取证工具进行了比较分析。由于已有研究大多从不同角度对数据恢复方法进行研究,因而本文方法在不同指标的比较分析方面选择了不同的已有研究进行比较分析。

恢复数据量是指从内存镜像中恢复的数据量。本文方法与Cellebrite Physical Analyzer(7.34.0.38)实现恢复数据量的试验结果如图3所示。从图中可以看出,与Cellebrite Physical Analyzer相比,本文方法恢复的数据表和SQLite数据记录的数据量均明显增加。这是因为Cellebrite Physical Analyzer基于元数据还原文件系统进行数据恢复,但是由于内存的异地更新机制,导致部分数据隐藏在文件系统之外的垃圾页中,无法对其进行恢复,而本文方法则能有效恢复出这些被标记为无效的垃圾页中的残留数据,从而恢复出更多已删除的数据表和记录。

图3 数据恢复结果对比

通用性是指数据恢复方法针对不同厂商的Android设备所使用的不同文件系统是否通用,可以使用召回率来量化验证其恢复效果。文献[5]通过分析EXT4文件系统存储特征和存储结构,将内存镜像中的data分区重建为文件系统,提出了针对性的数据恢复方法;文献[15]根据YAFFS2的特点提出了恢复YAFFS2文件的方法,使用这两种方法将内存镜像重建为文件系统并从中提取出SQLite数据记录。本文方法与上述方法在通用性方面的试验结果如图4所示。可见,本文方法可以对EXT4、EXT3和YAFFS2等不同文件系统的SQLite数据进行恢复,而文献[5]仅能恢复EXT4文件系统中的数据,文献[15]仅能恢复YAFFS2文件系统中的数据,这是由于基于文件系统的数据恢复方法依赖文件系统本身的格式,而本文方法不依赖于文件系统,因此具有通用性。另外,若部分记录已经被覆盖或回收,导致无法对其进行恢复,则会对召回率产生一定影响。

图4 通用性对比

Android内存镜像包含了单元内容区域、自由块区域、空闲区域和垃圾页等不同区域,不同区域中含有删除或更新操作后的残留数据。数据恢复能力是指从内存镜像的不同区域中恢复数据的能力,是衡量数据恢复方法能否从不同区域中恢复数据的重要指标。文献[16]提出了一个解析和处理删除记录并实现SQLite数据恢复的工具Bring2Lite,文献[7]提出了一种已删除数据的恢复工具SQLiteRecover。为了验证数据恢复能力,本文方法与上述方法分别从华为设备中对短消息数据记录进行恢复,试验结果如表4所示。

表4 数据恢复能力对比

由表4可见,本文方法能够成功恢复单元内容区域、自由块区域、空闲区域和垃圾页中的数据,而Bring2lite可以恢复单元内容区域、自由块区域和空闲区域,但其从自由块区域和空闲区域恢复的记录数均较少,这是因为若自由块中包含多条记录,Bring2Lite仅能恢复此自由块中的第一条记录;同时,Bring2Lite也无法恢复被部分覆盖的自由块。在空闲区域方面,Bring2Lite仅考虑了B+树叶子页的空闲区域,而没有考虑其他类型内存页的空闲区域,且没有区分完整单元结构和自由块结构。另外,虽然Bring2Lite考虑了垃圾页,但其在Auto-Vacuum数据库中无法对垃圾页进行定位,因而无法恢复垃圾页中的数据。SQLiteRecover仅关注自由块区域结构,因此只能恢复自由块区域中的数据,但是不能恢复被部分覆盖的自由块数据。文献[5]则只能恢复映射到文件系统中的单元内容区域中的数据。

文件完整性是指当数据库文件被破坏时是否能够对其进行恢复。试验中,我们人为地破坏了华为设备内存中mmssms.db的数据库头信息,然后分别使用本文方法以及对比方法进行试验,试验结果如表5所示。

表5 文件完整性对比

从表5中可见,仅有本文方法能够成功恢复被破坏的数据库记录,而对比方法均需要完整的数据库文件才能进行分析及恢复。

数据恢复效率是指执行数据恢复所花费的时间开销。由于Bring2Lite和SQLiteRecover面向SQLite数据库文件而非内存镜像,因此在数据恢复效率方面进行比较没有意义。而文献[9]提出了从片段内存页面恢复SQLite数据的方法,其面向内存镜像而不依赖于文件系统,因此将本文方法与文献[9]方法在数据恢复效率方面进行了比较分析,试验结果如图5所示。

图5 恢复时长对比

由图5可见,本文方法比文献[9]所花费的时间更短,这是因为本文采用了内存空间局部性特性,大大提高了数据恢复速度。文献[5]直接借助文件系统元数据进行数据恢复,虽然其数据恢复速度更快,但无法恢复隐藏在文件系统之外以及被删除的数据。

综上所述,通过试验结果分析可知,本文方法在恢复数据量、通用性、数据恢复能力、文件完整性和数据恢复效率等方面均具有优势,进一步证明本文方法的有效性和通用性。

4 结束语

为了从内存镜像中恢复证据数据,本文基于内存镜像异地更新和空间局部性的特点,提出了一种面向Android取证的内存镜像数据恢复方法,实现了未删除、已删除和未被覆盖的垃圾页中的数据恢复。通过对比试验验证了本文方法的通用性和有效性,和代表性的Android设备数据恢复方法以及商用取证工具相比,本文方法恢复数据量最多、数据恢复效率最高、数据恢复能力最强,可以通用于各种文件系统,且当文件被破坏时,本文方法也是有效的。此方法在数据加密方面有一定的局限性,当SQLite文件加密存储于内存中时,SQLite页的相关元数据均被加密,使用本文方法无法恢复其中数据。采用反编译等技术实现对加密数据的恢复将是下一步研究的重点。