一種基于SQLite數據庫日志的手機數據恢復方法

2021-07-24 04:36:00史大偉韓勝杰

西安航空學院學報 2021年1期

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

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

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

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

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

1 SQLite數據庫參數設置

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

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

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

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

這三個PRAGMA參數的設置都會對SQLite數據庫是否在主數據庫文件中和可選日志文件中保留被刪除記錄產生影響，從而直接影響SQLite數據恢復的效果。

2 SQLite文件及WAL文件格式

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

2.1 SQLite數據庫文件格式分析

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

圖1 “sqlite_master”表中內容

SQLite數據庫主體中的頁分為四種不同類型，每個類型都有自己的作用和結構。其類型如下：

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

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

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

高校產出具有公共品的特征，從表面上看，是培養的學生、取得的科研成果以及為社會提供的服務，實質上則是蘊含在人才和成果中的專門知識的發明和創造。由于功能具有二重屬性，客觀功能可以用一定的數值來表示大小，而主觀功能取決于人的主觀感受，缺乏可度量性，需要采用定性方法來表示。因此，在進行指標選擇時，一方面要盡量選取能夠量化和可以采集的指標，另一方面也要將一些概念化的指標轉變為可操作化的指標。例如，在挖掘定性指標內涵的基礎上，盡量選取信息重疊度高的定量指標來替代，以保證績效價值評估方法的可操作性。

(4)表B+tree葉子頁(Table B+tree leaf page)：表B+tree葉子頁是SQLite數據庫中存儲記錄的關鍵結構。這種類型的表B+tree葉子頁是唯一可以包含有效數據的B+tree頁。

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

圖2 B+tree葉子頁的內部結構

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

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

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

2.2 WAL日志文件格式分析

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

表1 WAL日志文件的存儲結構頭部字段

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

表2 WAL日志幀頭部字段

3 SQLite數據庫刪除特殊機制簡述

3.1 單元內容區的數據刪除機制及恢復原理

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

在表B+tree葉子頁中，數據單元頭的記錄大小、行id、載荷大小、數據類型等字段都可能根據刪除操作變為自由塊后，發生改變。因此，由數據類型字段來匹配具體數據字段會變得困難。數據類型字段以1～n順序排列形式出現，對應著數據字段中相應的1～n的數據，并且儲存著數據字段的各項信息，包括大小位置等。所以，要恢復數據字段中的數據，必須從數據類型字段入手，使兩者一一對應，形成映射關系。

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

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

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

3.2 WAL日志文件中數據恢復機制

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

4 SQLite數據庫恢復數據的方法

本文采用對SQLite主數據庫文件和WAL日志文件中的頁包含的數據綜合分析，進行數據恢復，以達到較好的數據恢復效果。首先通過對SQLite主數據庫文件中各個頁包含的單元內容區進行數據恢復，其次對SQLite數據庫對應的WAL日志文件中各個框包含的頁進行數據恢復。

4.1 單元內容區數據恢復原理

首先根據文件頭部簽名“SQLite format 3