基于WindowsFAT32的數(shù)據(jù)恢復(fù)原理分析及算法研究

1、基于WindowsFAT32的數(shù)據(jù)恢復(fù)原理分析及算法研究論文導(dǎo)讀：本文首先就Windows下FAT32文件系統(tǒng)的結(jié)構(gòu)做了介紹。本文分析了FAT32文件系統(tǒng)下基于數(shù)據(jù)簇連續(xù)分配情況和非連續(xù)分配情況的數(shù)據(jù)恢復(fù)原理。并提出了這兩種情況下的數(shù)據(jù)恢復(fù)算法。根據(jù)B圖和C圖情況下的數(shù)據(jù)恢復(fù)原理。關(guān)鍵詞：數(shù)據(jù)恢復(fù)，數(shù)據(jù)恢復(fù)原理，數(shù)據(jù)恢復(fù)算法，簇分配，F(xiàn)AT321 引言數(shù)據(jù)恢復(fù);，顧名思義，就是在數(shù)據(jù)存儲設(shè)備遭受用戶誤操作、黑客攻擊、病毒侵襲、硬件故障、物理環(huán)境損害等事件之后，從存儲介質(zhì)中分析并提取出原數(shù)據(jù)的過程【1】【2】。隨著我國信息化步伐的加快和互聯(lián)網(wǎng)的快速開展，計算機(jī)的應(yīng)用滲入到了各行各業(yè)以及人們的日常

2、生活中。越來越多的企業(yè)和個人都會將許多重要的數(shù)據(jù)存儲到計算機(jī)系統(tǒng)中。而一旦我們的系統(tǒng)由于人為或其他原因出現(xiàn)過失從而導(dǎo)致數(shù)據(jù)的喪失，那么如何能夠快速且準(zhǔn)確的恢復(fù)出原數(shù)據(jù)將成為一個至關(guān)重要的問題。這就使得數(shù)據(jù)恢復(fù)技術(shù)不管對于個人、企業(yè)還是國家都顯得日益重要起來。本文首先就Windows下FAT32文件系統(tǒng)的結(jié)構(gòu)做了介紹，并闡述了文件刪除的原理。在此根底上，本文分析了FAT32文件系統(tǒng)下基于數(shù)據(jù)簇連續(xù)分配情況和非連續(xù)分配情況的數(shù)據(jù)恢復(fù)原理，并提出了這兩種情況下的數(shù)據(jù)恢復(fù)算法。最后對這兩種算法進(jìn)行了分析和比擬。2 FAT32文件系統(tǒng)2.1 FAT32文件系統(tǒng)總體結(jié)構(gòu)FAT32文件系統(tǒng)由引導(dǎo)扇區(qū)，文件分

3、配表FAT，根目錄，數(shù)據(jù)區(qū)和保存扇區(qū)組成。如圖1所示。 引導(dǎo)扇區(qū) 保存扇區(qū) 文件分配表FAT #1 文件分配表 FAT #2 根目錄 文件數(shù)據(jù)區(qū) 未使用空間 圖1 FAT32文件系統(tǒng)總體結(jié)構(gòu)2.2 引導(dǎo)扇區(qū)引導(dǎo)扇區(qū)含有JMP指令、廠商信息、BPB參數(shù)塊、FAT32區(qū)段和結(jié)束標(biāo)志。其數(shù)據(jù)結(jié)構(gòu)如表1【3】所示。 序號 偏移 說明 1 0H02H 跳轉(zhuǎn)指令 2 03H0AH 廠商名和系統(tǒng)版本 3 0BH0CH 每扇區(qū)字節(jié)數(shù) 4 0DH 每簇扇區(qū)數(shù) 5 0EH0FH 保存扇區(qū)數(shù) 6 10H FAT個數(shù) 7 8 1CH1FH 隱藏扇區(qū)數(shù)，即引導(dǎo)扇區(qū)的邏輯扇區(qū)號 9 20H23H 該分區(qū)所占扇區(qū)數(shù)，即分區(qū)

4、總大小 10 24H27H 每個FAT所占扇區(qū)數(shù) 11 12 2CH2FH 根目錄起始簇 13 14 1FE1FFH 結(jié)束標(biāo)志，55H AAH 表1 引導(dǎo)扇區(qū)結(jié)構(gòu)如圖1所示，根目錄通常位于第二個FAT之后。由此，我們可以由表1引導(dǎo)扇區(qū)信息中的保存扇區(qū)數(shù)、FAT個數(shù)、每個FAT所占扇區(qū)數(shù)來定位到根目錄的起始位置。即根目錄起始位置 = 保存扇區(qū)數(shù) + FAT個數(shù)x每個FAT所占扇區(qū)數(shù)。這里的根目錄起始位置是相對于引導(dǎo)扇區(qū)而言的。2.3 文件分配表FAT文件分配表由FAT表項組成。在FAT32文件系統(tǒng)中，每個FAT表項占用32位。每個FAT表項都對應(yīng)著一個簇號。而且，當(dāng)FAT表項的值為0000000

5、0H時表示對應(yīng)的簇是空簇，未被分配使用，當(dāng)值為0FFFFFFFH時表示對應(yīng)的簇是某文件的最后一個數(shù)據(jù)簇。當(dāng)值為00000001H0FFFFFEFH時表示該簇已分配使用，且該FAT表項值是對應(yīng)文件的下一個數(shù)據(jù)簇的簇號?！?】在FAT文件系統(tǒng)中，系統(tǒng)通過FAT鏈來讀取和寫入文件數(shù)據(jù)。文件系統(tǒng)在目錄項中存放著文件數(shù)據(jù)的起始簇號，在FAT區(qū)中，該起始簇號對應(yīng)的FAT項中記錄著該文件占用的下一個簇的簇號，該簇號對應(yīng)的FAT項中又記錄著文件數(shù)據(jù)占用的下一個簇的簇號，一直到下一個簇號所對應(yīng)的FAT表項值是結(jié)束標(biāo)志0FFFFFFFH為止，這個FAT鏈才算結(jié)束。這樣，系統(tǒng)在訪問文件數(shù)據(jù)時，首先找到該文件的目錄項

6、，從中找出起始簇號，然后根據(jù)對應(yīng)的FAT鏈就可以找出文件的所有數(shù)據(jù)簇。簇號和FAT項的對應(yīng)關(guān)系為：簇號乘以4，將乘積作為相對文件分配表起始位置的偏移從0開始計算，就找到了該簇號對應(yīng)的FAT項。 【3】2.4 目錄項操作系統(tǒng)通過目錄樹結(jié)構(gòu)來管理一個分區(qū)中的文件，根節(jié)點(diǎn)存放盤符，每一個葉節(jié)點(diǎn)存放一個文件，而中間節(jié)點(diǎn)那么是文件夾。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑就形成了該文件的絕對路徑。這種管理方法對應(yīng)于磁盤上，就是文件系統(tǒng)創(chuàng)立根目錄區(qū)，根目錄區(qū)中的每一個目錄項指示目錄樹中根節(jié)點(diǎn)下的一個文件或文件夾的各種屬性和數(shù)據(jù)的存放位置。文件夾，又叫做子目錄。它對應(yīng)的目錄項中所指向的數(shù)據(jù)起始簇中的內(nèi)容不是數(shù)據(jù)而是該文件夾

7、內(nèi)的各個文件的目錄項。同樣，子目錄下的目錄項集合中還可以有子目錄目錄項，這樣的子目錄目錄項所指向的數(shù)據(jù)起始簇內(nèi)，同樣存放著一個目錄項集合。FAT32文件系統(tǒng)通過這種方式來管理和組織一個個的文件。不管是根目錄下的目錄項還是子目錄中的目錄項，大小均為32字節(jié)，其數(shù)據(jù)結(jié)構(gòu)及表示的含義是相同的。目錄項的結(jié)構(gòu)【3】如表2所示。 序號 偏移 數(shù)據(jù)含義 1 00H07H 文件的文件名 2 08H0AH 文件的擴(kuò)展名 3 0BH 文件屬性 各個位為1時表示的含義：BO只讀，B1隱藏，B2系統(tǒng)，B3卷標(biāo)，B4子目錄，B5歸檔，B6B7未使用 4 0CH 保存未用 5 0EH0FH 文件創(chuàng)立時間 6 10H11H

8、 文件最后訪問日期 7 12H13H 文件創(chuàng)立日期 8 14H15H 文件起始簇號的高16位 9 16H17H 文件最后修改時間 10 18H19H 文件最后修改日期 11 1AH1BH 文件的起始簇號的低16位 12 1CH1FH 文件長度，以字節(jié)為單位 表2 FAT32目錄項結(jié)構(gòu)根據(jù)上面的目錄項信息，我們可以得到文件的起始簇號和文件大小。這兩個數(shù)據(jù)對文件數(shù)據(jù)的恢復(fù)至關(guān)重要。2 文件刪除原理在Windows操作系統(tǒng)中刪除文件分為兩類，一類是暫時刪除，另一類是徹底刪除。暫時刪除文件，就是不是真正的刪除文件，只是把文件移動到了回收站中。論文格式。這個文件的FAT簇鏈并沒有任何變化，所以可以從回收

9、站中直接復(fù)原文件。論文格式?！?】徹底刪除文件，會把文件目錄項的首字節(jié)改為刪除標(biāo)志E5H;，同時這個文件的FAT鏈中的所有FAT表項值全部改為空簇標(biāo)志00000000H;。此外，文件目錄項中偏移為14H15H處的起始簇號的兩個高字節(jié)被清零。徹底刪除文件不和回收站發(fā)生任何聯(lián)系【4】。這樣，徹底刪除文件后，就不能直接復(fù)原文件了。但徹底刪除文件后，原文件的數(shù)據(jù)還是在數(shù)據(jù)區(qū)中的，只要不被覆蓋掉，我們就可以恢復(fù)出原文件的數(shù)據(jù)。3 FAT32文件系統(tǒng)數(shù)據(jù)恢復(fù)原理和算法3.1 FAT32文件系統(tǒng)數(shù)據(jù)恢復(fù)原理由2中文件徹底刪除的原理，我們可以知道文件的數(shù)據(jù)如果未被覆蓋，那么文件的數(shù)據(jù)還存在于數(shù)據(jù)區(qū)中。因此，要

10、想把這些數(shù)據(jù)恢復(fù)出來，重建我們的文件，那么需要首先找到這些數(shù)據(jù)的入口在哪里，即找到數(shù)據(jù)的起始簇號。如果該文件的起始簇號小于兩個字節(jié)所能表示的最大值65535，那么用目錄項中偏移為1AH1BH處的低位字即可存儲該起始簇號值。這種情況下，刪除文件時，就不存在起始簇號高字被清零的問題，我們可以直接從目錄項中偏移為1AH1BH處找到文件數(shù)據(jù)的起始簇號。但如果起始簇號超出了低位字所能表示的最大值，那么需要用目錄項中偏移為14H15H處的高位字來存儲其值。這樣，刪除文件時，起始簇號的兩個高字節(jié)就會被清零，僅保存了兩個低字節(jié)。這種情況下，我們要想得到起始簇號的兩個高字節(jié)，就需要參照創(chuàng)立時間值與之接近的其他正

11、常文件的起始簇號來確定兩個高字節(jié)【5】。實際進(jìn)行恢復(fù)時，我們可以根據(jù)該文件目錄項前后的正常文件的目錄項中的偏移為14H15H處的值來判斷起始簇號的兩個高字節(jié)值。其次，我們還需要知道文件數(shù)據(jù)存放在其余哪些簇上。在此之前，我們需要先了解一下Windows操作系統(tǒng)的簇的分配策略。Windows操作系統(tǒng)對文件分配簇時，采用下一可用分配策略。論文格式。即為一個文件分配了一個簇后，直接由此簇位置向后搜索下一個可用簇，繼續(xù)為其分配，而不會從文件系統(tǒng)的開始處進(jìn)行重新搜索?！?】基于這個分配策略，一個文件的數(shù)據(jù)存儲有三種可能的情況。我們用圖2來一一說明。 5 5 6 7 8 9 10 5 6 7 8 9 10

12、圖2 文件存儲情況圖2中顯示了三種不同的文件數(shù)據(jù)存儲情況。淡灰色方框表示分配給這個文件使用的簇，深灰色方框表示分配給其他文件使用的簇，白色方框表示未分配的空簇。A圖表示這個文件數(shù)據(jù)只占用了一個簇。B圖表示這個文件占用了4個簇，簇號為5、6、7、8，而且系統(tǒng)給這個文件分配的這四個簇是連續(xù)的。C圖表示這個文件數(shù)據(jù)占用了4個簇，簇號為5、7、8、10，但系統(tǒng)給這個文件分配的這四個簇是非連續(xù)的。對于A圖所示情況，恢復(fù)時，只需在確定起始簇號后，對起始簇中的相應(yīng)文件大小的數(shù)據(jù)進(jìn)行提取即可恢復(fù)文件。對于B圖情況，恢復(fù)時，在確定起始簇號后，從起始簇開始，一直向后提取數(shù)據(jù)，直到提取出的數(shù)據(jù)大小等于文件大小時為止

13、，這樣就恢復(fù)出了原文件的數(shù)據(jù)。對于C圖情況，該文件數(shù)據(jù)是非連續(xù)存放的。刪除文件后，簇5、7、8、10所對應(yīng)的FAT表項值為00000000H;。此時，如果簇6、9所對應(yīng)的文件未被刪除，那么6、9所對應(yīng)的FAT表項值為有效值00000001H0FFFFFFFH。這樣，恢復(fù)時，先由目錄項中的文件大小計算出所對應(yīng)的簇數(shù)。在確定起始簇號后，就可以從起始簇號對應(yīng)的FAT表項開始向后搜索，記錄下FAT表項值為00000000H;的所對應(yīng)的簇號。當(dāng)記錄下的簇號數(shù)等于文件大小所對應(yīng)的簇數(shù)時，停止搜索。然后根據(jù)記錄下的簇號，提取出對應(yīng)簇中的數(shù)據(jù)，直到提取出的數(shù)據(jù)大小等于文件大小時為止，這樣就恢復(fù)出了原文件的數(shù)據(jù)

14、。根據(jù)B圖和C圖情況下的數(shù)據(jù)恢復(fù)原理，提出以下基于數(shù)據(jù)簇連續(xù)分配的文件恢復(fù)算法和基于數(shù)據(jù)簇非連續(xù)分配的文件恢復(fù)算法。3.2 基于數(shù)據(jù)簇連續(xù)分配的文件恢復(fù)算法算法步驟如下： 確定被刪除文件所在分區(qū)的引導(dǎo)扇區(qū)的位置?？梢杂芍饕龑?dǎo)扇區(qū)中的分區(qū)表確定。 從引導(dǎo)扇區(qū)中讀取 每扇區(qū)字節(jié)數(shù);、每簇扇區(qū)數(shù);、保存扇區(qū)數(shù);、FAT個數(shù);和每個FAT所占扇區(qū)數(shù);的參數(shù)值。并計算根目錄相對于引導(dǎo)扇區(qū)的起始位置從0開始。根目錄相對起始位置=保存扇區(qū)數(shù)+FAT個數(shù)x每個FAT所占扇區(qū)數(shù)。 根據(jù)被刪除文件的文件路徑，從根目錄開始逐層往下遍歷找到該文件所在目錄的目錄項集合，并遍歷該目錄項集合，找到文件名與被刪除文件的文件名

15、局部匹配，且后綴名一致的目錄項。 從找到的目錄項中讀取偏移為1AH1BH的兩個字節(jié)，確定起始簇號的低位字。讀取偏移為1CH1FH的四個字節(jié)，確定文件數(shù)據(jù)的大小。 遍歷該目錄項集合的所有正常文件的目錄項，記錄每個目錄項中偏移為14H15H處的值，并找出出現(xiàn)頻次最高的值，把該值作為起始簇號的高位字。 根據(jù)確定的起始簇號和文件大小，找到文件數(shù)據(jù)的起始簇，并讀取數(shù)據(jù)，直到所讀取數(shù)據(jù)大小等于文件大小時為止。 保存數(shù)據(jù)，并重命名文件。 如果得到的文件不是我們想要的原文件，那么需從中記錄的起始簇號高位字的集合中選擇另一個出現(xiàn)頻次較高的值作為該文件起始簇號的高位字，重復(fù)步驟，直到恢復(fù)出原文件或遍歷完高位字集合

16、為止。如果遍歷完中的高位字集合還未恢復(fù)出原文件，那么需遍歷0000HFFFFH的值并作為該文件起始簇號的高位字，重復(fù)步驟直到恢復(fù)出原文件或遍歷結(jié)束為止。3.3 基于數(shù)據(jù)簇非連續(xù)分配的文件恢復(fù)算法算法步驟如下： 同3.2中的步驟。 由文件數(shù)據(jù)占用簇數(shù)N =文件數(shù)據(jù)大小/每簇扇區(qū)數(shù)x每扇區(qū)字節(jié)數(shù)，計算出文件數(shù)據(jù)占用簇數(shù)N。 根據(jù)中確定的起始簇號，由FAT表項偏移量=簇號x4，確定起始簇號對應(yīng)的FAT表項。 對起始簇號對應(yīng)的FAT表項及其后面的每一個表項進(jìn)行如下判斷：假設(shè)表項值為00000000H，那么由簇號=FAT表項偏移量/4，計算并記錄該FAT表項對應(yīng)的簇號，否那么跳過該表項，繼續(xù)進(jìn)行下一個F

17、AT表項的判斷。直到記錄的簇號數(shù)為N 時停止。 遍歷中已經(jīng)記錄下的簇號，讀取每個簇號相應(yīng)簇中的數(shù)據(jù)，直到所讀取數(shù)據(jù)總大小等于文件大小時為止。 保存數(shù)據(jù)，重命名文件。 如果得到的文件不是我們想要的原文件，那么需從中記錄的起始簇號高位字的集合中選擇另一個出現(xiàn)頻次較高的值作為該文件起始簇號的高位字，重復(fù)步驟，直到恢復(fù)出原文件或遍歷完高位字集合為止。如果遍歷完中的高位字集合還未恢復(fù)出原文件，那么需遍歷0000HFFFFH的值并作為該文件起始簇號的高位字，重復(fù)步驟直到恢復(fù)出原文件或遍歷結(jié)束為止。4 算法分析與比擬4.1 時間和空間復(fù)雜性分析基于數(shù)據(jù)簇非連續(xù)分配的文件恢復(fù)算法與基于數(shù)據(jù)簇連續(xù)分配的文件恢復(fù)

18、算法相比，添加了對FAT項的判定和存儲起始簇之后的未分配簇的簇號的操作，但因為這兩種操作所需的時間和空間都不是很多，因此，這兩種算法在時間和空間復(fù)雜性上相差不大。4.2 恢復(fù)成功率比擬分析第一種算法是基于數(shù)據(jù)簇連續(xù)分配情況考慮的，因此第一種算法只適用于數(shù)據(jù)簇連續(xù)的情況，對于數(shù)據(jù)簇非連續(xù)的情況不能恢復(fù)。第二種算法是基于數(shù)據(jù)簇非連續(xù)分配情況考慮的，而且這種算法是選擇文件起始簇后面的未分配簇來恢復(fù)數(shù)據(jù)的，因此第二種算法不僅適用于數(shù)據(jù)簇非連續(xù)的情況，也適用于數(shù)據(jù)簇連續(xù)的情況。但如果圖2的C圖中簇6、9所對應(yīng)的文件也被刪除了，那么第二種算法也不能成功恢復(fù)，但這種情況發(fā)生的概率比擬小。綜上分析，基于數(shù)據(jù)簇非連續(xù)分配的文件恢復(fù)算法具有恢復(fù)成功率高且易于實現(xiàn)的優(yōu)點(diǎn)。因此采用第二種算法進(jìn)行數(shù)據(jù)恢復(fù)的程序設(shè)計比擬適宜。5 結(jié)語本文詳細(xì)分析了數(shù)據(jù)簇連續(xù)分配情況下和非連續(xù)分配情況下的數(shù)據(jù)恢復(fù)原理，并提出了這兩種情況下的數(shù)據(jù)恢復(fù)算法。經(jīng)過對這兩種算法的分析和比擬，得出基于數(shù)據(jù)簇非連續(xù)分配的文件恢復(fù)算法即適用于數(shù)據(jù)簇連續(xù)分配又適用于非連續(xù)分配的情況，因此具有恢復(fù)成功率高的優(yōu)點(diǎn)，且該算法易于實現(xiàn)。數(shù)據(jù)恢復(fù)是數(shù)據(jù)平安遭受侵犯后所做的一個重點(diǎn)工作，但數(shù)據(jù)恢復(fù)不是萬能的。因此，我們應(yīng)盡量保護(hù)數(shù)據(jù)的平安，防止數(shù)據(jù)遭受損害。另外日常應(yīng)及時備份重要的數(shù)據(jù)文件，以免數(shù)據(jù)恢復(fù)不成功，喪失數(shù)