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

SQLite

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

一、操作原理

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

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

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

表1：數(shù)據(jù)庫記錄cell存儲布局

Payload_Size:可變長整數(shù),占用1～9個(gè)字節(jié),表現(xiàn)Payload數(shù)據(jù)大小；

Rowid:可變長整數(shù),占用1～9個(gè)字節(jié),數(shù)據(jù)庫記錄的Rowid值；

Head_Size:可變長整數(shù),占用1～9個(gè)字節(jié),表現(xiàn)從Header_Size到TypeN的數(shù)據(jù)大小；

Type1...TypeN:可變長整數(shù),占用1～9個(gè)字節(jié),表現(xiàn)后面對應(yīng)各字段DataN的數(shù)據(jù)類型和寬度,具體的解釋見表2；

Data1...DataN:數(shù)據(jù)庫表中各字段的數(shù)據(jù)；

表2：數(shù)據(jù)庫字段類型和寬度詳解

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

請輸入圖片描述

表3：free_block存儲布局

2、恢復(fù)操作詳細(xì)步調(diào)

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

1

S01:計(jì)算Rowid寬度(占用字節(jié)數(shù)).因?yàn)镽owid值是持續(xù)的,所以刪除記錄cell的Rowid寬度可通過相鄰的未刪除記錄cell的Rowid計(jì)算得到.

2

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

3

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

4

S04:計(jì)算Header_Size值和寬度.因?yàn)閯h除記錄cell只有前4個(gè)字節(jié)被占用,因此針對這4個(gè)字節(jié)長度的分情況闡發(fā),即可準(zhǔn)確的計(jì)算出Header_Size和Type1.具體分類情況如下：

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

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

T1、Payload_Size寬度為1,Rowid寬度為1,Header_Size寬度為1,剩下1個(gè)字節(jié)屬于Type1；

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

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

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

3、歸納總結(jié)

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

由上述步調(diào)精確的推算出PayLoad_Size值、Rowid寬度、Header_Size值和Type1值,完成一個(gè)free_block的cell頭則重構(gòu)完成,實(shí)現(xiàn)SQLite數(shù)據(jù)庫刪除記錄的恢復(fù).

二、金石之言

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

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

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