基于MDA的SQLite碎片数据清除技术

叶清明 刘晓燕* 付晓东,2

1(昆明理工大学信息工程与自动化学院 云南 昆明 650500)2(云南省计算机技术应用重点实验室 云南 昆明 650500)

基于MDA的SQLite碎片数据清除技术

叶清明1刘晓燕1*付晓东1,2

1(昆明理工大学信息工程与自动化学院 云南 昆明 650500)2(云南省计算机技术应用重点实验室 云南 昆明 650500)

清除SQLite数据库中含有用户重要信息的碎片数据是保障用户信息安全的重要手段。在国内尚未有数据清除标准的情况下，提出一种基于MDA(Model Driven Architecture)的SQLite碎片数据清除技术。该技术将SQLite主文件映射成页位图集合，并根据页位图进行碎片清除，以提高碎片数据的完整性以及碎片数据定位和清除的准确性。同时，采用基于MDA的EMF(Eclipse Modeling Framework)框架建立SQLite碎片数据清除技术的平台无关模型，使用MDA工具解决该技术跨平台软件复用的问题。

SQLite 碎片数据 清除 信息安全 MDA

0 引 言

SQLite 是独立、无服务、零配置、事务性的SQL数据库引擎，是在各种嵌入式平台上广泛使用的数据库之一。Adobe的 Photoshop Lightroom、 Airbus的 A350 XWB以及Android、 iPhone等智能手机中的大部分应用都采用SQLite数据库作为数据的存储和管理方式。

在使用SQLite过程中，系统提供的删除API只对数据做删除标记，并没有对物理层上的数据做清除，因此大量的碎片数据会驻留在SQLite的物理层。这些碎片数据中残留有大量用户信息，会涉及到个人、企业、军队、国家机关尤其是保密机关的重要隐私和机密，对用户的隐私安全乃至国家安全构成严重的威胁。例如，在Android手机中的短信、通话记录等大部分应用在删除数据后，仍然有很大的概率被恢复。笔者经过对碎片数据的研究分析得出，数据库碎片数据量会随着数据库的增大而增多。SQLite引擎没有提供具体API或命令对物理层上的碎片数据做专门的清除。SQLite的vacuum命令通过将数据库中的数据以页为单位覆写到空闲页中，以重新利用数据库中的空闲页。这种写覆盖方式只对空闲页具有一定的清除效果，而数据库中其它页的碎片数据仍然存在。在此背景下，需要一种彻底清除SQLite物理层碎片数据的技术以保障用户的信息安全。

在国内，尚未形成数据清除标准，文献[1]对硬盘数据的清除与安全性研究对数据清除有一定的指导意义。针对SQLite物理层数据的研究主要集中在数据恢复领域，对数据清除领域涉及较少。文献[2-6]描述的SQLite删除数据恢复方法中也需要对SQLite底层碎片数据进行研究，但其主要针对BTree页自由块数据的研究，而没有对SQLite中的其他页进行解析。在国外，SQLite物理层数据的研究也是针对数据恢复领域，文献[7-8]中讲述了对SQLite溢出页碎片数据的分析。然而，上述研究都不能清晰完整地表示SQLite碎片数据的分布状态，且不能直接用于数据清除领域。

由于在Andriod、iPhone等平台下的大多数应用都采用SQLite对数据进行存储和管理，这些平台的多样性导致清除不同平台上的SQLite碎片数据会增加重复开发的工作量，降低了开发效率。OMG提出的模型驱动架构MDA很好地解决了软件复用的问题。MDA中系统的功能需求被描述为机器可读、独立于平台且标准化存储的模型，再通过对不同平台或实现技术的模型之间映射规则的定义，实现了抽象模型到代码的转换[9-13]。由此，引入MDA到SQLite碎片数据清除技术以解决不同平台下软件复用的问题。

本文首先介绍SQLite物理层布局，然后详细介绍笔者对SQLite物理层碎片数据的研究结论以及将SQLite主文件映射到位图算法，并给出SQLite碎片数据清除技术SFDET(SQLite Fragment Data Erasure Technique)的业务流程。最后针对SFDET的业务功能采用基于EMF的Eclipse Modeling Tools 可视化工具建立SFDET的平台无关模型PIM(Platform Independent Model)，通过工具提供的模型转换和代码生成技术实现了基于MDA的SFDET框架代码的生成。

1 SQLite数据存储布局

SQLite最终将用户的数据存储在“主数据库文件”的单文件中，本文称为主文件，页是其基本组成单位，页从1开始编号且每页大小相同。相关用户数据存储在表和索引中，并使用master表来记录所有表和索引的元数据。

SQLite主文件包含BTree页、溢出页、空闲页，每一个页的类型唯一。Btree页又包括索引内部页、索引叶子页、表内部页和表叶子页；空闲页包括空闲枝干页和空闲叶子页。SQLite使用不同的数据结构来管理这些不同类型的页，其中，索引采用B-tree管理索引内部页和索引叶子页；表采用B+tree管理表内部页和表叶子页；空闲页用空闲链表的方式管理空闲枝干页，在每个空闲枝干页下又拥有其空闲叶子页指针数组；溢出页采用链式存储结构。

Btree页中每一条数据称为单元，不同类型的Btree页其单元格式不同。当Btree页的某个单元数据量超过该Btree页负载时，会产生该单元的一个或多个溢出页，只有表内部页没有溢出页。文献[14]给出了主文件的官方定义。

2 SQLite碎片数据清除技术

笔者在某手机隐私清除项目中，为了清除SQLite主文件中的碎片数据，使用Winhex工具对Android平台下的浏览器、通话记录、通讯录、短信、百度地图等含用户高危隐私数据应用的数据库进行研究分析，得出SQLite碎片数据来源与分布。在此基础上提出将主文件映射成页位图集合的算法，最后根据页位图集合对SQLite主文件中的碎片数据进行清除。

2.1 SQLite碎片数据来源与分布

通过对SQLite系统删除API的原理的研究以及大量的手机app数据库分析，总结得到碎片数据的两个重要来源: ①用户对数据库中的用户数据执行删除操作后，被删除的数据在物理层没有被清除。②页A与页B之间的覆盖会导致B的数据出现在A的未分配区。

进一步对大量碎片数据的统计发现，SQLite用户数据的删除过程以及SQLite页与页之间的写覆盖方式，都会导致碎片数据在数据库主文件中呈散列状排布。笔者采用图1描述了对Bree页、溢出页和空闲枝干页中碎片数据分布的研究结果。其中，BTree页的碎片数据会出现在其未分配区、自由块以及页内碎片中；溢出页的页内未占用区域和空闲枝干页的未占用区域均为碎片数据，空闲叶子页全为碎片数据。后文所述的空闲页是指空闲枝干页。

图1 Btree页、溢出页和空闲页的碎片分布图

2.2 SQLite主文件到页位图集合的映射

在SFDET中为了能精确定位主文件中的碎片数据，并将其清晰地提供给清除模块，笔者从数据有效性的角度出发，把SQLite数据库中的数据分为有效数据和无效数据，使用位图中的一位来表示一字节数据的有效性，其中1表示有效数据，0表示无效数据，由此，可将SQLite主文件映射成页位图集合。为了实现该映射，给出如下定义：

定义1 非空集合S={s1, …,si, …,sn}，表示SQLite主文件。其中n=主文件大小/页大小，1≤i≤n；si表示第i页的页内容。

定义2btpi=，该三元组表示定义1中si的页位图。其中pn表示页号，pn=i，ptr是指向bmp的指针，bmp表示为位图块，其大小等于页大小/8。

定义3 非空集合B={btp1, …,btpj, …,btpn}，表示由定义2中页位图btp构成的页位图集合。其中n=主文件大小/页大小，1≤j≤n；btpj表示第j页的页位图。

使用上述定义，构成从SQLite主文件到页位图集合的映射关系f：S->B。由于SQLite主文件包含3种类型的页，f的实现需要3个映射算法。采用映射算法MapBtreePg、MapOvfwPg和MapFreePg分别实现Btree页、溢出页和空闲页的映射关系f。

在映射算法的伪代码中，Setbmp(num ,start , len, valid)函数的参数依次表示页号、数据的页内偏移、数据长度、有效位标志，其作用是设置定义2中的页位图btp，其中pn=num,位图块bmp内从start位置开始长度为len的一段位图有效性置为valid。

算法 1MapBtreePg(PgNum,PgSize)

Input: PgNum, PgSize

//输入页号、页大小

Output: btp

//输出位图

01 call Setbmp(PgNum ,0, PgSize,0)

//初始化页位图

02 FreeblkPtr=first freeblock offset

//取自由块的首指针

03 while FreeblkPtr != 0x0000 do

04 call Setbmp(PgNum ,FreeblkPtr,2,1)

05 FreeblkPtr=next freeblock offset

//取下一个自由块

06 endwhile

07 while I in cell count do

08 get CellLenth

//获取单元长度

09 if cell has overflow page

10 get OvfwPgNum and OvfwBytes

//取溢出页号和溢出字数

11 call MapOvfwPg(OvfwPgNum, PgSize, OvfwBytes)

12 call Setbmp(PgNum ,cell[i], CellLenth,1)

//将单元有效性置1

13 endwhile

14 call Setbmp(PgNum ,0, PgHeaderLenth,1)

//将页头有效性置1

15 output btp

算法 2 MapOvfwPg(OvfwPgNum, PgSize, OvfwBytes)

Input: OvfwPgNum, PgSize, OvfwBytes

//页号、大小、溢出字数

Output: btp

//输出位图

01 call Setbmp(OvfwPgNum,0, PgSize, 0)

02 NextOvfwPg= first 4 bytes

//获取下一个溢出页号

03 if NextOvfwPg=0 and OvfwBytes<=PgSize-4

04 call Setbmp(OvfwPgNum,0, 4+OvfwBytes,1)

05 else if NextOvfwPg != 0 and OvfwBytes>PgSize-4

06 call Setbmp(OvfwPgNum,0, PgSize,1)

07 OvfwBytes -=PgSize-4

//计算下一个溢出字节数

08 call MapOvfwPg(NextOvfwPg, PgSize, OvfwBytes)

09 else

call Setbmp(OvfwPgNum,0, PageSize,1)

10 endif

11 output btp

算法 3 MapFreePg(FstTrkPgNum, PgSize)

Input: FstTrkPgNum, PgSize

//输入第一个空闲枝干页号、页大小

Output: btp

//输出位图

01 call Setbmp(FstTrkPgNum,0, PgSize, 0)

02 NextTrkPg= first 4 bytes

//获取下一个空闲枝干页

03 FreeLfPgCnt =next 4 bytes

//获取空闲叶子页个数

04 FreeLfPg[]=contents from offset 8 to (8+ FreeLf-PgCnt*4)

05 for i in FreeLfPgCnt do

06 call Setbmp(FreeLfPg[i],0, PgSize,0)

//将空闲页有效性置0

07 if NextTrkPg!=0

08 call MapFreePg (NextTrkPg, PgSize)

09 endif

10 call Setbmp(FirstTrkPgNum,0, 8+FreeLfPgCnt*4,1)

11 output btp

2.3 SFDET的业务流程

本节给出的SFDET流程如图2所示，master表、表和索引的解析过程都采用先序遍历BTree页的方式解析，在此不再赘述先序遍历的流程。在具体解析某个BTree页时，使用BTree映射算法MapBtreePg。此外，在解析空闲页链表的过程中，使用空闲页映射算法MapFreePg。

图2 SQLite碎片数据清除技术流程图

3 SFDET的MDA建模

为了能跨平台使用SFDET技术，采用MDA工具对该技术的业务领域进行建模。笔者选用EMF框架对其建模，以实现模型到Java代码的转换。

3.1 EMF描述的SFDET-PIM

EMF是Eclipse的模型框架，它是MDA的—个实现[15]。使用基于EMF的Eclipse Modeling Tools可视化工具，对SFDET进行建模，抽象出的SFDET主框架类图PIM如图3所示，类的功能介绍如下：

SQLiteIO类提供对数据库进行加载、关闭、读写的函数。ReadPage函数和WritePage函数分别用于对指定页号的读写。LoadFile函数和CloseFile函数实现对SQLite文件的加载和卸载。

SQLiteControl类提供解析SQLite数据库必要的参数和解析函数。InitialSQLite函数用于初始化参数，ParseBtree函数解析表和索引，ParseFreeList函数解析空闲页，ClearSQLiteFrag-ment函数清除指定页的数据。

SQLiteBitMap类提供对位图的管理，m_BitMapArray属性用于存放由SQLitePage类解析后生成的位图，ClearBitmap函数用于对位图的清零和回收。

SQLiteBtree是一个抽象类， 提供ParseBtree-Page抽象函数对某一个数据表或索引表解析， GetPageProduct函数生成具体的SQLitePage对象。

抽象类SQLitePage提供对某一个Btree页解析的抽象函数ParsePage，并使用CreatPageBitmap将解析的结果映射成位图。

SQLiteCell也是一个抽象类，它负责对某一个Btree页中的单元进行解析，抽象函数ParseCell完成这一解析。

图3 SFDET主框架PIM

图4是SQLiteBtree、SQLitePage、SQLiteCell抽象类泛化子类的PIM，子类通过实现其父类的抽象函数具体地实现各个页的解析。单元进行解析，抽象函数ParseCell完成这一解析。

图4 抽象类泛化PIM

3.2 EMF的模型转换和代码生成

在基于EMF的Eclipse Modeling Tools工具中， 首先将PIM模型描述为如图4所示的ecore 模型并存放在.ecore文件中，利用其模型转换器将.ecore模型转化为平台相关模型(Platform Specific Model, PSM)，即genmodel模型，然后以genmodel模型为输入，使用JET利用模板生成java代码。每个类模型产生一个Java接口和一个Java实现。在类模型中，将每个属性映射成包含具体数据类型的Java类属性，同时为每个属性根据其修饰符的不同自动生成某个或全部的set()/get()方法。类模型中所有方法只生成空的函数体，具体的内容通过开发人员在此基础上进行函数体的编写。

4 应用结果论证

该技术已运用到某手机隐私清除软件产品中，并对Android手机下的通话记录、通讯录、短信、QQ、百度地图等含用户高危隐私数据应用的数据库做了充分的实验及测试，结果如表1所示。

表1 碎片数据清除前后对比

表1中数据来自某用户日常使用的手机，360卫士app仅有扫描删除短信以及删除通话记录功能。在未作清除以前，通过360卫士能发现删除的短信、通话记录等信息。同时，通过该技术的产品进行扫描，能够扫描更多的删除短信和通话记录，原因在于该技术对溢出页和索引页、以及空闲页进行了全面扫描。进一步研究发现，除了删除的信息，还可能在碎片数据中扫描到“正常数据”的信息，这是因为“正常数据”来源于页之间的覆盖，也进一步说明了数据恢复和数据清除的差异，即数据恢复仅关注一条数据的恢复，数据清除更倾向于全部碎片。

在使用该技术的产品进行清除以后，仍然能够扫描到极少量的残缺信息，通过进一步研究发现，这些残缺信息并非是未彻底清除的结果，而是应用程序缓存数据再次写进了数据库，从而对结果产生了影响。

在实践中发现，绝大多数app的数据库碎片均未作处理，目前，常用app中只有腾讯公司的微信，在数据删除后，对删除数据做了处理，同是其旗下的QQ却未作处理。尽管QQ数据库是加密的，但仍然被破解，并能明文取出删除数据。

5 结 语

SQLite碎片数据清除技术在信息安全领域是一个新型技术，该技术采用位图映射方法能彻底清除SQLite数据库中的碎片数据，从而充分保护用户的隐私，尤其是保证了用户对数据进行的删除操作是真正意义上的删除。同时，结合MDA思想建立该技术的PIM，以提高其可移植性和开发效率。

该技术也存在着不足，没有对SQLite内存数据库以及-wal文件进行研究，从而导致清除某些app数据库的结果受到影响。未来的工作是将该技术用于SQLite的-wal文件的碎片清除。

[1] 周开明, 赵强, 张晓, 等. 数据残留的清除与安全性的研究[J]. 科学技术与工程, 2006, 6(17):2769-2771.

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

[3] 张开翔, 周安民. iPhone短信删除数据恢复方法的研究[J]. 现代计算机, 2015(1):3-8.

[4] 刘琼, 叶猛. 基于SQLite的iPhone 数据恢复方法研究[J]. 信息网络安全, 2013(11):90-93.

[5] 沙晶, 蔡立明. SQLite数据库结构分析在司法鉴定中的应用[J]. 中国司法鉴定, 2013(6):73-78.

[6] 陈明辉, 方均滩, 吴世雄. 对SQLite中删除的数据进行恢复的方法和装置：中国, CN104376091 A[P]. 2015.

[7] Jeon S, Bang J, Byun K, et al. A recovery method of deleted record for SQLite data-base[J]. Personal and Ubiquitous Computing, 2012, 16(6):707-715.

[8] Lee G W, Yang S J, Hwang H U, et al. A Recovery Scheme for the Deleted Overflow Data in SQLite Database[J]. Journal of Korean Institute of Information Technology, 2012, 10(11):143-153.

[9] 曾一, 周吉, 孙政, 等. 支持MDA的设计模式建模与模型转换方法研究[J]. 计算机工程与应用, 2012, 48(1):76-80.

[10] 王永涛, 刘勇. 基于MDA的模型转换研究与应用[J]. 计算机工程, 2011, 37(16):84-85,103.

[11] 侯金奎, 万建成, 张玉艳. 一种支持MDA的PIM建模方法[J]. 计算机工程, 2007, 33(8):71-73.

[12] OM. Meta object facility core specification v2.0[OL]. [2015-08-03]. http://www.om.org/cgi-bin/apps/doc?forma/06-01-01.

[13] OM. Unified modeling language: Superstructure v2.0[OL]. [2015-7-21]. http://www.omg.org/docs/formal/05-07-04.

[14] SQLite Official Documents. The SQLite Database File For-mat[OL]. [2015-07-25]. http://www.sqlite.org/fileformat2.html.

[15] Eclipse Juno. EMF Developer Guide[OL]. [2015-08-15]. http://help.eclipse.org/helios/index.jsp.

SQLITE FRAGMENT DATA ERASURE TECHNIQUE BASED ON MDA

Ye Qingming1Liu Xiaoyan1*Fu Xiaodong1,2

1(FacultyofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,Kunming650500,Yunnan,China)2(YunnanKeyLaboratoryofComputerTechnologyApplications,Kunming650500,Yunnan,China)

Erasing the fragment data which contains the user’s significant information in SQLite database is an important measure to ensure information security. In the case of nodata eliminating standard, an SQLite fragment data erasure technique based on MDA is proposed. This technique maps the SQLite main file to a bitmap collection that helps to erase the fragment, which improves accuracy of the fragment data location and the integrity. At the same time, this measure builds the platform independent model of the method which uses EMF based on MDA and uses MDA tools that improves the reusability of the technique in different platform.

SQLite Fragment data Erasure Information Security MDA

2015-10-24。国家自然科学基金项目(61462056)；云南省应用基础研究计划重点项目(2014FA028)。叶清明，硕士生，主研领域：软件工程，信息安全。刘晓燕，副教授。付晓东，教授。

TP311.1

A

10.3969/j.issn.1000-386x.2017.01.009