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

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

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

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

5、0H時表示對應的簇是空簇，未被分配使用，當值為0FFFFFFFH時表示對應的簇是某文件的最后一個數據簇。當值為00000001H0FFFFFEFH時表示該簇已分配使用，且該FAT表項值是對應文件的下一個數據簇的簇號。【3】在FAT文件系統中，系統通過FAT鏈來讀取和寫入文件數據。文件系統在目錄項中存放著文件數據的起始簇號，在FAT區中，該起始簇號對應的FAT項中記錄著該文件占用的下一個簇的簇號，該簇號對應的FAT項中又記錄著文件數據占用的下一個簇的簇號，一直到下一個簇號所對應的FAT表項值是結束標志0FFFFFFFH為止，這個FAT鏈才算結束。這樣，系統在訪問文件數據時，首先找到該文件的目錄項

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

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

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

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

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

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

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

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

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

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

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

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

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