基于孩子兄弟樹的ＦＡＴ３２文件刪除恢復算法
2009-01-01 00:00:00章華劉乃琦郭建東
計算機應用研究 2009年3期
(電子科技大學 計算機科學與工程學院， 成都 610054)
摘 要：針對由主觀或客觀因素造成計算機中數據丟失的情況，提出一種Windows FAT32文件系統下基于孩子兄弟樹的數據刪除恢復算法。 介紹FAT32文件系統和孩子兄弟樹，詳細闡述了如何基于孩子兄弟樹重建FAT32文件系統的目錄樹，快速搜索到被刪除文件的目錄項，并通過分析文件刪除前后目錄項中屬性值的變化來恢復被刪除的文件。
關鍵詞：數據恢復； FAT32 文件系統； 文件分配表； 孩子兄弟樹
中圖分類號：TP309.03 文獻標志碼：A
文章編號：10013695(2009)03111603
Childbrother treebased deleted file recovery algorithm on Windows FAT32
ZHANG Hua， LIU Naiqi， GUO Jiandong
(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu610054， China)
Abstract:For the subjective or objective factors caused the loss of data on the computer，this paper proposed a childbrother treebased deleted file recovery algorithm on Windows FAT32 file system. It introduced the structure of Windows FAT32 file system on disk and childbrother tree， an deeply expatiation that how to reconstruct the Windows FAT32 file system directory based on the childbrother tree， and how to quickly search and obtained the delete file directory table which could be used to recovery its related deleted FAT file by analyzing its value variety after removed was displayed by the paper as well as.
Key words：data recovery； FAT32 file system； file access table； childbrother tree
0 引言
隨著信息技術的不斷發展，計算機在社會和生活中扮演著日益重要的角色。越來越多的企業、商家、政府機關和個人將自己最重要的信息以數據文件的形式保存在計算機中。這樣一旦電腦或者軟件系統不可避免地出現差錯從而導致數據丟失，如何能夠迅速而正確地恢復就成為了至關重要的問題，這就使得數據恢復技術不論對個人、企業還是國家都顯得日益重要[1]。目前，Windows操作系統在個人桌面系統中占有很大分量，FAT32是Windows操作系統主要使用和大力發展的文件系統。本文提出了一種基于孩子兄弟樹的FAT32文件刪除恢復算法。
1 FAT32文件系統
1.1 FAT32在磁盤上的結構
如圖1所示，FAT32文件系統將邏輯盤的空間劃分成為五大部分[2]，依次是MBR或虛擬MBR、引導區（DBR區）、文件分配表區（FAT區）、數據區（DATA區）、目錄項區（FDT區，雖然FAT32中FDT已經被DATA區包含，但由于FDT的重要性仍將其單獨劃分）。引導區和文件分配表區又合稱為系統區。
在Windows 2000 Professional 和Windows XP Professional下，使用WinHex對FAT32文件系統的分析表明：
a）MBR區或虛擬MBR區占據著分區的前63個扇區，目前只有第一個扇區被FAT32文件系統真正使用。該扇區的前446 Byte為main boot recorder，存放系統主引導程序和引導參數。接下來的64 Byte為disk partition table，記錄磁盤分區基本信息。最后2 Byte固定為0x55AA，用來判斷引導區是否合法[3]。
b）引導區從第63號扇區開始，主要由三部分組成：跳轉指令語句，跳轉到引導記錄；BPB參數表，其中保存了該邏輯盤的每扇區字節數、每簇對應的扇區數、根目錄起始簇號等重要參數；引導記錄，即引導程序。引導區之后還留有若干保留扇區，其中備份了引導區的信息。
c）文件分配表區共保存了兩個相同的文件分配表。因為文件所占用的存儲空間（簇鏈）及空閑空間的管理都是通過文件分配表實現的。文件分配表十分重要，保存兩個以便第一個損壞時，還有第二個可用。
d）FAT32文件系統的文件目錄項FDT占用32 Byte的存儲空間，其中存儲著文件或目錄的名稱、文件的各種屬性，以及文件內容起始簇號或目錄子目錄的起始簇號、文件的大小等重要參數。
1.2 FAT32系統的文件管理
FAT32文件系統對數據區存儲空間按簇進行劃分和管理。簇是空間分配和回收的基本單位，即一個文件總是占用若干個整簇，文件所使用最后一簇的剩余空間就不再使用，而是浪費掉了。
簇的大小對文件系統的性能影響很大：當簇較大時，磁盤空間浪費往往較大，但存取效率往往較高；當簇較小時，磁盤空間可以得到有效利用，但存取效率往往很低。一般來說，一個簇往往取2的整數冪的扇區大小，大分區一個簇分配的扇區數往往要比小分區多。實際應用中簇所占的扇區數大小存放在分區的BPB表中。
FAT32文件系統對文件采用顯示鏈接分配方式[4]，在文件分配表中顯示鏈接文件各簇塊的指針。
1.3 FAT32系統文件刪除
分析FAT32文件刪除前后各區域數據的變化是恢復刪除文件的前提。在Windows 2000 Professional和Windows XP Professional 環境下，FAT32系統文件刪除后磁盤各區域數據的變化如表1所示。
2 孩子兄弟樹
在數據結構領域，孩子兄弟樹是用來保存樹的有效邏輯結構。算法中主要利用孩子兄弟樹存儲生成的目錄樹結構，包括搜索和存儲被刪除的目錄樹。
孩子兄弟樹又稱為二叉樹表示法，或二叉鏈表表示法，即以二叉鏈表作為樹的存儲結構。鏈表中節點的兩個鏈域分別指向該節點的第一個孩子節點和下一個兄弟節點，分別命名為firstchild域nextsibling域[5]。
//樹的二叉鏈表（孩子—兄弟）存儲表示
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild， *nextsibling;
}CSNode， *CSTree;
利用孩子兄弟存儲結構易于實現找節點孩子操作，即通過firstchild域找到節點的第一個孩子，這樣就相當于找到了節點下轄孩子的單鏈表，該鏈表由nextsibling域的指針連接。因此用該結構來保存FAT32系統的目錄樹時，由父目錄項搜索子目錄項十分方便。
3 恢復算法
3.1 總體算法
總體算法思想：先使用目錄樹生成算法，將分區的所有目錄項包括被刪除文件的目錄項保存在一棵孩子兄弟樹中，再對需要恢復的文件使用文件恢復算法進行恢復。目錄樹生成算法和文件恢復算法將在后面兩節介紹。
3.2 目錄樹生成算法
3.2.1 目錄項類的結構
class CDir
{ public:
CDir();
~CDir();
//插入孩子節點
void InsertChild( CDir* pDirChild );
//插入兄弟節點
void InsertBrother( CDir* pDirBrother );
//插入兄弟節點
void InsertBrother( CDir* pDir ， CDir* pDirBrother );
//生成所有子節點，非遞歸
void GenerateChildTree( CDir* pDirParent );
//生成所有子節點，非遞歸
void GenerateChildTree();
//文件名
TCHAR m_szFileName[14];
//起始簇號
DWORD m_dwStartCluster;
//文件長度
DWORD m_dwLength;
//是否是目錄
BOOLm_bIsDir;
//子節點指針
CDir* m_pChildDir;
//兄弟節點指針
CDir* m_pBrotherDir;
//是否被刪除
BOOLm_bIsDeleted;
//指向所屬分區的指針
Cpartition* m_pPartition;
//刪除位的標記，用來識別是否需要匹配起始簇高位
BOOLm_bIsDeletedByte;};
3.2.2 目錄項的存儲
目錄項由二叉樹數據結構的孩子兄弟表示法表示。
3.2.3 子目錄生成基本算法
目錄項的生成由于可以從分區BPB表得到根目錄的起始簇號，可從根目錄出發，遞推地得到所有的子目錄項。假定在遞推過程中已經得到了目錄節點pDir，那么生成pDir的所有子節點的遞推過程如圖2所示。
這種算法對完整的目錄表項奏效，但如果父目錄項是被Shift+Delete刪除的話，其中起始簇號的高16位被置零，那么就必須對該算法進行改進才能生成父目錄的孩子鏈。
3.2.4 高字匹配法
高字匹配法是在父目錄項被Shift+Delete刪除，父目錄項中起始簇號的高16位被置零時，用來搜索子目錄并生成相應孩子兄弟樹的算法。其算法流程如圖3所示。
該算法的主要思想在于：依次從分區的第一簇向最后一簇搜索，如果當前搜索簇號的低16位與被刪除父目錄項中起始簇號的低16位相同，而且該簇為首目錄簇時，則該簇為父目錄項下轄的首目錄簇，該簇簇號即為父目錄項中的起始簇號，找到起始簇號后即可按照圖2的子目錄生成算法生成兄弟孩子子目錄樹。
首目錄簇指的是某個父目錄項包含的目錄內容的首簇，首目錄簇的第一個目錄項就是“.”目錄項，因此判定是否為首目錄簇的方法就是查看該簇第一扇區的32 Byte是否是特殊目錄項“.”。
3.3 文件恢復算法
通過遞推的算法生成了所有的目錄項，并把它們放在一棵二叉樹里面。其中，所有找到的已刪除文件也是作為一個節點放在這棵樹中的。要恢復已刪除文件，就可以利用起始簇號信息訪問FAT表對應的4 Byte，查看文件起始對應的雙字是否被置零，如果相應的雙字已經不為0，那么說明文件已經被覆蓋，不可恢復。得到文件恢復的基本算法如圖4所示。
與目錄恢復算法一樣。這種算法對完整的文件目錄項奏效，但如果文件是被Shift+Delete刪除的話，文件的目錄項的起始簇號的高16位被置零，那么就必須對該算法進行改進才能正確恢復文件。改進的思路和前面介紹的高字匹配法類似。
4 結束語
利用該算法完成了數據恢復軟件DataRecovery，在Windows 2000 Professional和Windows XP Professional 環境下對該軟件進行測試發現：
a）在一個20 GB左右的FAT32分區上，只要文件刪除后不對磁盤進行寫操作，對于4 KB左右的小文件基本上可以完全恢復。這是因為FAT32系統為20GB的分區設置的系統簇的大小一般為8個扇區，即4 KB的空間。
b）對于20 MB以內文件的恢復也是比較理想的。進行了10次測試，10次都完全恢復。這主要是由于系統在管理分區時，當分區剩余空間低于60~70 MB左右時就會提示磁盤空間不夠，使得分區剩余空間一般不少于60~70MB，而當磁盤有剩余空間時系統就連續為文件分配存儲空間的緣故。
c）對大文件的恢復進行了測試，在有1 GB剩余空間的磁盤中拷入了一個300 MB左右的影音文件，徹底刪除后用DataRecovery進行恢復。結果，部分恢復了230 MB的數據。
d）DataRecovery對系統盤文件恢復的效果不是很理想，這主要是系統盤經常進行讀寫或數據交換工作，這就導致了被刪除的文件可能很快就被系統的臨時文件覆蓋而無法恢復。該軟件對離散文件的恢復效果也不好。當磁盤的離散程度較大時，只能部分恢復較大的文件。
參考文獻：
［1］趙雙峰，費金龍，劉楠，等.Windows NTFS下數據恢復的研究與實現［J］.計算機工程與設計，2008，29(1):306308.
[2]涂彥暉，戴士劍.數據安全與編程技術［M］.北京:清華大學出版社，2005:740.
[3]鄧劍，楊曉非，廖俊卿.FAT 文件系統原理及實現［J］.計算機與數字工程，2005，33(9):105108.
[4]湯子瀛，哲鳳屏，湯小丹.計算機操作系統［M］.西安:西安電子科技大學出版社，2001:142.
[5]嚴蔚敏，吳偉民.數據結構［M］.北京:清華大學出版社，1999:136137.
(上接第1115頁)
參考文獻：
［1］王睿，韓芳溪，張曉麗.無線傳感器網絡密鑰預分配與動態分配策略[J].計算機工程與應用，2006，43(3): 120122.
[2]ESCHENAUER L， GLIGOR V. A key management scheme for distributed sensor networks[C]// Proc of the 9th ACM Conf on Computer and Communications Security.New York:ACM Press，2002:4147.
[3]PANJAB， MADRIA S， BHARGAVA B. Energy and communication efficient group key management protocol for hierarchical sensor networks[C]// Proc of IEEE Inernational Conference on Sensor Networks，Ubiquitions，and Trustworthy Computing.Taichong:IEEE Press，2006:384393.
[4]ZHU Sencun，SETIA S，JAJODIA S.LEAP:efficient security mechanisms for largescale distributed sensor networks[C]// Proc of the 10th ACM Conf on Computer and Communications Security.New York:ACM Press，2003:6272.
[5]MOKAMMEL M，CHOI G.An efficient PKCbased security architecture for wireless sensor networks[C]//Proc of Military Communications Conference.Orlando:IEEE Press，2007:17.
[6]王國軍， 呂婷婷， 過敏意. 無線傳感器網絡中基于臨時初始密鑰的密鑰管理協議[J]. 傳感技術學報， 2007， 20(7): 15811586.
[7]LANDSTRA T， ZAWODNIOK M， JAGANNATHAN S.Energyefficient hybrid key management protocol for wireless sensor networks[C]// Proc of the 32nd IEEE Conference on Local Computer Networks.Dublin:IEEE Press，2007:10091016.
