SQLite是一款輕型數據庫,它能夠支持Windows/Linux/Unix等主流的操作系統,能夠跟很多的程序語言相結合.SQLite以占用資源非常低、處理速度快、使用方便、代碼開源等一系列特性,已經被廣泛的應用于嵌入式設備、Android設備和各種各樣的應用平臺等領域.此外,SQLite存放的數據信息豐富多樣,包含Android設備的通訊錄、短信、通話記錄、微信、QQ聊天記錄以及各種瀏覽器上網拜訪記錄等.

SQLite

隨著SQLite的廣泛應用,針對其刪除記錄恢復的研究技術也層出不窮.如何恢復SQLlite數據庫中刪除的數據記錄?本期唐老師給我們介紹一種針對數據記錄存儲單元塊刪除恢復的辦法.

一、操作原理

眾所周知,SQLite 數據庫文件由固定大小的“頁 (page)”組成,第1頁的前100個字節為SQLite文件的二進制頭,每個頁由Btree布局存儲.二進制布局不再詳細介紹,萬能的網絡一搜一大把,這里詳細介紹下數據記錄單元的存儲布局.

1、數據記錄單元(cell)儲存布局

在SQLite數據庫中,同一張表中的數據記錄單元(cell)具有相似的數據類型.如圖表1,展示了cell的存儲布局,從Header_Size到DataN稱為一個Payload.

表1：數據庫記錄cell存儲布局

Payload_Size:可變長整數,占用1～9個字節,表現Payload數據大小；

Rowid:可變長整數,占用1～9個字節,數據庫記錄的Rowid值；

Head_Size:可變長整數,占用1～9個字節,表現從Header_Size到TypeN的數據大小；

Type1...TypeN:可變長整數,占用1～9個字節,表現后面對應各字段DataN的數據類型和寬度,具體的解釋見表2；

Data1...DataN:數據庫表中各字段的數據；

表2：數據庫字段類型和寬度詳解

SQLite 中被刪除的數據記錄單元(cell)稱為自由塊(free_block),數據記錄單元被刪除后,cell的前4個字節被抹掉,1-2字節被標記為下一個自由塊的偏移(free_block_offset),3-4字節表示整個自由塊大小(free_block_size).而第一個自由塊的偏移在子頁頭結構中標記.free_block的存儲結構如表3所示.其中Data區域包括部分的Header_Size或Type1,完整的Type2～TypeN,完整的Data1～DataN.

請輸入圖片描述

表3：free_block存儲布局

2、恢復操作詳細步調

基于上述的存儲結構描述,從表3中知道,刪除記錄cell的前4個字節已經被抹掉,被free_block的頭給覆蓋掉了,造成Payload_Size、Rowid、Header_Size和Type1這四個數據丟失,無法正確解析后續的Type和Data數據.要實現刪除記錄數據的恢復,就必要對PayLoad_Size、Rowid、Header_Size和Type1進行推算重構.具體實現步驟如下：

1

S01:計算Rowid寬度(占用字節數).因為Rowid值是持續的,所以刪除記錄cell的Rowid寬度可通過相鄰的未刪除記錄cell的Rowid計算得到.

2

S02:計算Payload_Size寬度(占用字節數).由于free_block_size和Payload_Size相差范圍為2～18個字節,即Payload_Size和Rowid的寬度,因此通過free_block_size的值范圍計算得到Payload_Size.計算辦法：由于可變長整型范圍是1～9,因此可變長整型定義述規律即可計算具體數值占用的字節數.例如：free_block_size在0～0x7f之間,則寬度為1字節；在0x80～0x3FFF之間,則寬度為2字節等等,依次類推.

3

S03:Payload_Size=free_block_size-PayLoad_Size寬度-Rowid寬度.得到Payload_Size和Rowid的寬度后,即能夠準確定位到Header_Size的偏移起始位置.

4

S04:計算Header_Size值和寬度.因為刪除記錄cell只有前4個字節被占用,因此針對這4個字節長度的分情況闡發,即可準確的計算出Header_Size和Type1.具體分類情況如下：

S041:若Payload_Size寬度+Rowid寬度>=4,則說明Header_Size和Type1未被覆蓋,因此按表1存儲布局即可完整解析Payload_Size、Rowid、Header_Size、Type1,實現此free_block的數據恢復.

S042:若Payload_Size寬度+Rowid寬度<4,又分為下述四種情況：

T1、Payload_Size寬度為1,Rowid寬度為1,Header_Size寬度為1,剩下1個字節屬于Type1；

T2、Payload_Size寬度為1,Rowid寬度為1,剩下2字節屬于Header_Size；

T3、Payload_Size寬度為1,Rowid寬度為2,剩下1字節屬于Header_Size；

T4、Payload_Size寬度為2,Rowid寬度為1,剩下1字節屬于Header_Size；

3、歸納總結

以上四種情況,利用枚舉法即可計算出對應的Header_Size和Type1,根據寬度值可知四種情況的枚舉最大次數分別是T1:16129,T2：16383,T3:127,T4:127,在實際計算過程其實用不了這么多次即可枚舉出來,具體可結合數據表的字段類型和取值范圍篩選過濾掉不符合條件的枚舉情況,從而大大減少了枚舉量.

由上述步調精確的推算出PayLoad_Size值、Rowid寬度、Header_Size值和Type1值,完成一個free_block的cell頭則重構完成,實現SQLite數據庫刪除記錄的恢復.

二、金石之言

本文介紹的刪除記錄恢復辦法,針對單個完整獨立的刪除塊(free_block)能精確的推算重構出被覆蓋的控制頭信息,并且此辦法很巧妙的利用了刪除記錄塊相鄰的未刪除記錄的Rowid來推算此自身的Rowid寬度,這個是關系整個辦法能否準確計算Payload_Size的關鍵點.在S042步中結合表屬性篩選過濾不符合要求的枚舉情況,加速恢復過程也是本辦法的一大亮點.

然而本辦法的缺陷在于針對有連續刪除塊被整個到一塊的情況,則會形成誤判,導致枚舉校驗次數較多或者校驗失效等情況.針對這種情況需結合表特征和數據記錄上下文進行分析處理.

更多出色技術資訊,只在公眾號“ansheng47”和“ANSCEN-ISEC”