宋 冰，孫 莉，史大偉，韓勝杰

(1.河南警察學(xué)院 網(wǎng)絡(luò)安全系，鄭州 450000；2.駐馬店正陽縣公安局 刑警大隊(duì)，河南 駐馬店 463600；3.新鄉(xiāng)市公安局 電信網(wǎng)絡(luò)犯罪偵查支隊(duì)，河南 新鄉(xiāng) 453000)

近年來隨著科技的飛速發(fā)展與日新月異，手機(jī)已經(jīng)從最簡單的語音文字通訊工具，變?yōu)榇钶d各種功能的智能設(shè)備，正走進(jìn)千家萬戶，成為現(xiàn)代社會(huì)不可缺的一部分。手機(jī)中的各種App存儲(chǔ)著重要的線索，在犯罪偵查中，手機(jī)中的數(shù)據(jù)往往是案件查破的關(guān)鍵。SQLite數(shù)據(jù)庫作為一種輕量級數(shù)據(jù)庫，普遍使用在手機(jī)的各種應(yīng)用程序中，包含賬戶信息、通信記錄、網(wǎng)頁瀏覽記錄、交易記錄、位置信息等大量的用戶痕跡。隨著人們廣泛使用智能設(shè)備，以及對智能手機(jī)各項(xiàng)功能的了解，犯罪分子對其中存儲(chǔ)的數(shù)據(jù)進(jìn)行有意的刪除、更改、覆蓋等操作，這無疑對犯罪線索的獲取帶來阻力。因此，針對SQLite數(shù)據(jù)庫刪除數(shù)據(jù)恢復(fù)的研究，對于案件偵查有著重要的意義。

目前針對SQLite數(shù)據(jù)庫進(jìn)行數(shù)據(jù)恢復(fù)的方法主要有三種：一是基于手機(jī)文件系統(tǒng)的工作機(jī)制。從文件屬性入手，在存儲(chǔ)設(shè)備中的未分配空間中恢復(fù)SQLite文件[1]；二是基于SQLite文件結(jié)構(gòu)。通過在SQLite文件中頁面的未分配區(qū)域中遍歷尋找刪除記錄，從而達(dá)到數(shù)據(jù)恢復(fù)的目的[2]；三是基于SQLite數(shù)據(jù)庫日志。對SQLite數(shù)據(jù)庫自動(dòng)創(chuàng)建的日志文件，根據(jù)記錄的存儲(chǔ)模式，分析其中的數(shù)據(jù)，恢復(fù)數(shù)據(jù)記錄。SQLite數(shù)據(jù)庫支持的日志類型有兩種：一種是早期使用的回滾日志，另一種是預(yù)寫日志(WAL)，相較于回滾日志，預(yù)寫日志在并發(fā)讀寫操作和磁盤I/O方面具有較好的性能[3]，再加上手機(jī)存儲(chǔ)容量的不斷增加，從Android9開始，越來越多的手機(jī)以空間換取更好的性能，從而將預(yù)寫日志作為SQLite數(shù)據(jù)庫的日志模式[4]。

本文通過分析SQLite數(shù)據(jù)庫及預(yù)寫日志文件的文件格式、存儲(chǔ)及刪除機(jī)制，提出了一種基于SQLite數(shù)據(jù)庫日志的數(shù)據(jù)恢復(fù)方法。該方法是提取SQLite數(shù)據(jù)庫文件中頁和WAL日志文件中各個(gè)框包含的頁，通過分析記錄的存儲(chǔ)模式，綜合兩種頁中存儲(chǔ)的記錄數(shù)據(jù)進(jìn)行恢復(fù)。實(shí)驗(yàn)表明，該方法具有較好的恢復(fù)效果。

1 SQLite數(shù)據(jù)庫參數(shù)設(shè)置

SQLite數(shù)據(jù)庫的配置中，存在影響運(yùn)行和刪除數(shù)據(jù)恢復(fù)的兩個(gè)重要參數(shù)。第一個(gè)參數(shù)是頁大小。SQLite文件中頁類似于文件系統(tǒng)的簇，頁是SQLite數(shù)據(jù)庫內(nèi)部能夠被尋址的最小單位，如果當(dāng)前的SQLite文件不夠存放新的數(shù)據(jù)時(shí)，頁大小將決定新分配的空間大小。第二個(gè)重要的參數(shù)是PRAGMA命令。PRAGMA命令是一個(gè)特殊命令，可以用在SQLite 環(huán)境內(nèi)，控制各種環(huán)境變量和狀態(tài)標(biāo)志，一個(gè)PRAGMA值可以被讀取，也可以根據(jù)需求進(jìn)行設(shè)置。通常在第一次創(chuàng)建SQLite數(shù)據(jù)庫時(shí)PRAGMA就會(huì)被自定義，其中決定數(shù)據(jù)成功恢復(fù)的PRAGMA命令有三個(gè)：

(1)secure_delete。默認(rèn)值是0，這個(gè)參數(shù)可設(shè)置為0、1或FAST。值為0表示關(guān)閉，通常為關(guān)閉狀體，可以減少CPU周期數(shù)和磁盤I/O數(shù)量以提高性能。如果希望避免在內(nèi)容被刪除或更新后留下痕跡，可以將該值設(shè)置為1。這個(gè)參數(shù)特殊設(shè)置是FAST選項(xiàng)，它將在B+tree頁中的自由列表下留下取證數(shù)據(jù)。

(2)auto_vacuum。默認(rèn)值是0，表示數(shù)據(jù)庫文件大小不會(huì)自動(dòng)縮小。如果這個(gè)參數(shù)設(shè)置為1，數(shù)據(jù)庫會(huì)刪除未使用的頁面，并且不會(huì)將這些頁面保留在自由列表中。

(3)journal_mode。用于啟用或禁用日志。這個(gè)參數(shù)有六個(gè)選項(xiàng)，分別是DELETE、TRUNCATE、PERSIST、MEMORY、WAL和OFF。除WAL和OFF以外，其余選項(xiàng)都會(huì)創(chuàng)建一個(gè)以“-journal”結(jié)尾的日志文件，如果將該參數(shù)設(shè)置為WAL，則會(huì)創(chuàng)建一個(gè)以“-wal”結(jié)尾的日志文件，在數(shù)據(jù)庫打開期間，WAL日志文件永遠(yuǎn)不會(huì)被刪除，但由于它有一個(gè)固定的大小，一旦數(shù)據(jù)填充到WAL的末尾，SQLite會(huì)覆蓋WAL前面用于暫存數(shù)據(jù)的頁。

這三個(gè)PRAGMA參數(shù)的設(shè)置都會(huì)對SQLite數(shù)據(jù)庫是否在主數(shù)據(jù)庫文件中和可選日志文件中保留被刪除記錄產(chǎn)生影響，從而直接影響SQLite數(shù)據(jù)恢復(fù)的效果。

2 SQLite文件及WAL文件格式

SQLite數(shù)據(jù)庫完整數(shù)據(jù)通常包含于磁盤上“主數(shù)據(jù)庫”文件中。在事務(wù)模式下，額外的信息會(huì)存儲(chǔ)在第二個(gè)文件中，也就是回滾日志或者預(yù)寫日志。同一數(shù)據(jù)庫內(nèi)所有頁大小相同，頁的單位大小定義在數(shù)據(jù)庫文件頭部中。

2.1 SQLite數(shù)據(jù)庫文件格式分析

一個(gè)SQLite數(shù)據(jù)庫文件是以B+tree結(jié)構(gòu)組成的[5]，分為SQLite頭部和SQLite主體。SQLite頭部包括文件的前100個(gè)字節(jié)，它提供了該SQLite數(shù)據(jù)庫文件的基本信息，如頭部類型字符串、頁大小、數(shù)據(jù)庫文件的大小、文本編碼等，其中在文件偏移18和19的十六進(jìn)制值若為0x01則是回滾日志模式，值為0x02則是WAL日志模式，可以使用“PRAGMA journal_mode”命令查看日志模式。在SQLite文件偏移量100處，SQLite主體從它的第一個(gè)頁開始，這個(gè)頁包含一個(gè)名為“sqlite_master”表的結(jié)構(gòu)，“sqlite_master”表保存著數(shù)據(jù)庫的表和索引結(jié)構(gòu)的基本信息，其中存儲(chǔ)了每個(gè)表和索引的第一頁入口點(diǎn)?！皊qlite_master”表中內(nèi)容如圖1所示，“sqlite_master”表中顯示表名稱是“tel”，表所在的根頁(rootpage)是第2頁，“sqlite_master”表中包含創(chuàng)建該表的SQL語句。

圖1 “sqlite_master”表中內(nèi)容

SQLite數(shù)據(jù)庫主體中的頁分為四種不同類型，每個(gè)類型都有自己的作用和結(jié)構(gòu)。其類型如下：

(1)Freelist主干頁(Freelist trunk page)：Freelist主干頁以頁面指針組織起來，每個(gè)頁面指針大小是4個(gè)字節(jié)。第一個(gè)指針將指向下一個(gè)自由列表主干頁的頁碼，之后的每一個(gè)指針都會(huì)指向一個(gè)自由列表葉子頁的頁碼。第一個(gè)Freelist主干頁的指針存儲(chǔ)在SQLite頭部的偏移量32處。

(2)Freelist葉子頁(Freelist leaf page)：Freelist葉子頁是一個(gè)可以分配給新記錄存儲(chǔ)的自由頁。這種類型的頁面不保存分配數(shù)據(jù)或任何其他類型的內(nèi)容。

(3)表B+tree內(nèi)部頁(Table B+tree interior page)：表B+tree內(nèi)部頁中包含指向它的下一級B+tree頁和最右子頁(序號最大的子頁)的頁碼。類似于Freelist主干頁，指針的大小為4個(gè)字節(jié)。

高校產(chǎn)出具有公共品的特征，從表面上看，是培養(yǎng)的學(xué)生、取得的科研成果以及為社會(huì)提供的服務(wù)，實(shí)質(zhì)上則是蘊(yùn)含在人才和成果中的專門知識(shí)的發(fā)明和創(chuàng)造。由于功能具有二重屬性，客觀功能可以用一定的數(shù)值來表示大小，而主觀功能取決于人的主觀感受，缺乏可度量性，需要采用定性方法來表示。因此，在進(jìn)行指標(biāo)選擇時(shí)，一方面要盡量選取能夠量化和可以采集的指標(biāo)，另一方面也要將一些概念化的指標(biāo)轉(zhuǎn)變?yōu)榭刹僮骰闹笜?biāo)。例如，在挖掘定性指標(biāo)內(nèi)涵的基礎(chǔ)上，盡量選取信息重疊度高的定量指標(biāo)來替代，以保證績效價(jià)值評估方法的可操作性。

(4)表B+tree葉子頁(Table B+tree leaf page)：表B+tree葉子頁是SQLite數(shù)據(jù)庫中存儲(chǔ)記錄的關(guān)鍵結(jié)構(gòu)。這種類型的表B+tree葉子頁是唯一可以包含有效數(shù)據(jù)的B+tree頁。

每個(gè)表B+tree葉子頁分為頁頭部和頁主體，B+tree葉子頁的內(nèi)部結(jié)構(gòu)如圖2所示。在一個(gè)SQLite文件中，只有這種類型的頁保存著用戶或應(yīng)用程序數(shù)據(jù)。頁頭部大小占8個(gè)字節(jié)，后面是單元指針數(shù)組，單元指針數(shù)組存儲(chǔ)了指向同一頁內(nèi)每個(gè)記錄單元的指針(每個(gè)指針長度為2個(gè)字節(jié))。SQLite在數(shù)據(jù)單元內(nèi)容區(qū)中優(yōu)先從頁最后部開始逆序存儲(chǔ)數(shù)據(jù)，即第一個(gè)單元指針指向頁的最后一個(gè)記錄單元，而最后一個(gè)單元指針指向單元內(nèi)容區(qū)域中的第一個(gè)記錄單元。單元指針數(shù)組的最后一個(gè)指針之后至單元內(nèi)容區(qū)域中的第一個(gè)單元格之前的區(qū)域則是未分配區(qū)。

圖2 B+tree葉子頁的內(nèi)部結(jié)構(gòu)

頁頭部中的一個(gè)重要指針是偏移量為1處的自由塊指針。自由塊包含了單元內(nèi)容區(qū)中被刪除的單元記錄，并以鏈表的形式組織起來，自由塊指針是鏈表的入口點(diǎn)(即第一個(gè)自由塊)，每個(gè)自由塊都包含一個(gè)指向下一個(gè)自由塊的指針。一個(gè)自由塊被分隔成三個(gè)字段：(1)指向下一個(gè)自由塊的指針，大小2個(gè)字節(jié)；(2)當(dāng)前自由塊的長度，大小2個(gè)字節(jié)；(3)空閑區(qū)域的內(nèi)容，被刪除的數(shù)據(jù)就存儲(chǔ)在此處。如果一個(gè)自由塊是鏈表的最后一個(gè)，那么第一個(gè)字段將被設(shè)置為0。對于我們而言，值得關(guān)注的是自由塊的第三個(gè)字段。

SQLite數(shù)據(jù)庫中最小的實(shí)體是單元(cell)。單元中的數(shù)字由一個(gè)可變長度的整數(shù)表示，稱為varint編碼。varint的長度為1～9個(gè)字節(jié)。計(jì)算方法是在輸入的字節(jié)數(shù)組(例如，單元的序列類型)上進(jìn)行運(yùn)算，遍歷所有的字節(jié)，直到找到一個(gè)最高位等于0的字節(jié)(即作為無符號整數(shù)的字節(jié)數(shù)值小于128)。移除所有獲得字節(jié)中的最高位，重新組合就得到實(shí)際的數(shù)值。

每個(gè)單元以兩個(gè)varint整數(shù)開始，表示有效載荷的字節(jié)數(shù)和行的id，后面是一個(gè)字節(jié)數(shù)組，最后是一個(gè)可選的4個(gè)字節(jié)指針，指向overflow頁。字節(jié)數(shù)組以varint編碼存儲(chǔ)，其中包括字節(jié)數(shù)組的頭部長度、數(shù)據(jù)類型和實(shí)際的有效載荷。除了TEXT和BLOB類型之外，所有的數(shù)據(jù)類型都是用一個(gè)特定值來編碼。BLOB類型由大于或等于12的偶數(shù)數(shù)字定義，而TEXT類型由大于或等于13的奇數(shù)數(shù)字定義。最后，存儲(chǔ)在有效載荷中記錄的大小可以通過數(shù)據(jù)類型計(jì)算出來。

2.2 WAL日志文件格式分析

WAL日志文件的存儲(chǔ)結(jié)構(gòu)頭部字段如表1所示，頭部字段由日志頭部和固定大小的幀(Frame)組成[6]。WAL日志頭部大小固定為32個(gè)字節(jié)，以4個(gè)字節(jié)為一組，分為8組代表日志文件的8個(gè)屬性。magic number是固定值0x377f0682或0x377f0683，頁面大小與對應(yīng)數(shù)據(jù)庫相同；checkpoint序列表示經(jīng)過的檢查點(diǎn)的次數(shù)；salt-1與salt-2是隨機(jī)數(shù)，隨著checkpoint的執(zhí)行，前者增加1，后者隨機(jī)變化；checksum-1與checksum-2分別是文件頭校驗(yàn)和的第1部分與第2部分。

表1 WAL日志文件的存儲(chǔ)結(jié)構(gòu)頭部字段

WAL日志幀頭部字段如表2所示。WAL日志頭部后面是0到多個(gè)幀。每個(gè)幀由一個(gè)24字節(jié)的幀頭(frame-header)和一個(gè)大小等于數(shù)據(jù)庫頁大小的頁組成。幀頭部為6個(gè)32位大端無符號整數(shù)。page number表示該幀數(shù)據(jù)對應(yīng)的數(shù)據(jù)庫頁；size after commit表示幀數(shù)據(jù)提交后，數(shù)據(jù)庫的大??；salt-1/2與日志文件頭中對應(yīng)數(shù)值相同，若不同則表示該幀無效。幀頭后是大小等于頁大小的幀數(shù)據(jù)部分。

表2 WAL日志幀頭部字段

3 SQLite數(shù)據(jù)庫刪除特殊機(jī)制簡述

3.1 單元內(nèi)容區(qū)的數(shù)據(jù)刪除機(jī)制及恢復(fù)原理

在SQLite數(shù)據(jù)庫中，用戶進(jìn)行刪除、更新等操作時(shí)，表B+tree葉子頁上的單元數(shù)據(jù)將成為自由塊形式存在，自由塊與單元數(shù)據(jù)互相交錯(cuò)。根據(jù)上述對表B+tree葉子頁結(jié)構(gòu)的分析，頁頭部中偏移量為1處的自由塊指針指向第一個(gè)自由塊，每個(gè)自由塊指針大小為4個(gè)字節(jié)，前2個(gè)字節(jié)指向下一個(gè)自由塊，一直到該自由塊指針值為0，表示結(jié)束，從而形成自由塊鏈表。每個(gè)自由塊指針的后2個(gè)字節(jié)表示該自由塊的大小。因此，表B+tree葉子頁上的單元數(shù)據(jù)在刪除后，只是前4個(gè)字節(jié)的值發(fā)生變化，其余字節(jié)保持不變。

在表B+tree葉子頁中，數(shù)據(jù)單元頭的記錄大小、行id、載荷大小、數(shù)據(jù)類型等字段都可能根據(jù)刪除操作變?yōu)樽杂蓧K后，發(fā)生改變。因此，由數(shù)據(jù)類型字段來匹配具體數(shù)據(jù)字段會(huì)變得困難。數(shù)據(jù)類型字段以1～n順序排列形式出現(xiàn)，對應(yīng)著數(shù)據(jù)字段中相應(yīng)的1～n的數(shù)據(jù)，并且儲(chǔ)存著數(shù)據(jù)字段的各項(xiàng)信息，包括大小位置等。所以，要恢復(fù)數(shù)據(jù)字段中的數(shù)據(jù)，必須從數(shù)據(jù)類型字段入手，使兩者一一對應(yīng)，形成映射關(guān)系。

(1)當(dāng)記錄大小、行id、載荷大小總共占用3個(gè)字節(jié)時(shí)，刪除記錄數(shù)據(jù)后，由于自由塊指針大小為4個(gè)字節(jié)，此時(shí)數(shù)據(jù)類型字段的第一個(gè)varint被覆蓋，而數(shù)據(jù)類型字段剩余的varint字段和數(shù)據(jù)字段均保持不變，此時(shí)數(shù)據(jù)可以絕大部分恢復(fù)。被覆蓋的數(shù)據(jù)類型字段的第一個(gè)varint表示的是數(shù)據(jù)庫表定義中的第一個(gè)字段。通常情況下，該值為自增型關(guān)鍵字，用于表示該條記錄的序號。

(2)當(dāng)記錄大小、行id、載荷大小總共占用4個(gè)字節(jié)或超過4個(gè)字節(jié)時(shí)，刪除記錄數(shù)據(jù)后，數(shù)據(jù)類型varint字段和數(shù)據(jù)字段均保持不變，此時(shí)數(shù)據(jù)可以完全恢復(fù)。

綜上所述，在原數(shù)據(jù)單元成為自由塊過程中，數(shù)據(jù)類型字段的第一個(gè)varint被覆蓋，而其余都完整，通過劃分識(shí)別這些數(shù)據(jù)，就可以較為精確地恢復(fù)出已刪除的數(shù)據(jù)。

3.2 WAL日志文件中數(shù)據(jù)恢復(fù)機(jī)制

對數(shù)據(jù)庫進(jìn)行記錄刪除、更新等操作后，只要未觸發(fā)checkpoint，則數(shù)據(jù)預(yù)先存儲(chǔ)在WAL日志文件中，并未對主數(shù)據(jù)庫文件進(jìn)行修改，每次進(jìn)行的事務(wù)操作將在WAL日志文件中留下記錄。因此，可以從WAL日志文件中得到前一段時(shí)間更新操作留下的記錄。當(dāng)觸發(fā)checkpoint后，如果WAL日志文件中幀頭部的salt-1′字段值與日志文件頭部中salt-1字段值相同，則表示該幀內(nèi)的數(shù)據(jù)已經(jīng)被覆蓋，數(shù)據(jù)無法恢復(fù)；如果幀頭部的salt-1′字段值比日志文件頭部中salt-1字段值小1，則表示該幀內(nèi)的數(shù)據(jù)尚未被覆蓋，數(shù)據(jù)庫對應(yīng)頁中的數(shù)據(jù)可以被恢復(fù)。由于前面已對數(shù)據(jù)庫文件中頁的單元結(jié)構(gòu)進(jìn)行過解析，而WAL日志文件中的幀包含的頁與數(shù)據(jù)庫頁結(jié)構(gòu)一致，因此，可使用上述方法直接對WAL日志文件中滿足條件的幀進(jìn)行解析，從而恢復(fù)數(shù)據(jù)庫記錄。

4 SQLite數(shù)據(jù)庫恢復(fù)數(shù)據(jù)的方法

本文采用對SQLite主數(shù)據(jù)庫文件和WAL日志文件中的頁包含的數(shù)據(jù)綜合分析，進(jìn)行數(shù)據(jù)恢復(fù)，以達(dá)到較好的數(shù)據(jù)恢復(fù)效果。首先通過對SQLite主數(shù)據(jù)庫文件中各個(gè)頁包含的單元內(nèi)容區(qū)進(jìn)行數(shù)據(jù)恢復(fù)，其次對SQLite數(shù)據(jù)庫對應(yīng)的WAL日志文件中各個(gè)框包含的頁進(jìn)行數(shù)據(jù)恢復(fù)。

4.1 單元內(nèi)容區(qū)數(shù)據(jù)恢復(fù)原理

首先根據(jù)文件頭部簽名“SQLite format 3