基于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