廖根為

（華東政法大學(xué)司法鑒定中心 上海 200042）

當(dāng)計(jì)算機(jī)網(wǎng)絡(luò)中存在入侵行為時(shí)，即使入侵痕跡被刪除或破壞，也有可能通過數(shù)據(jù)恢復(fù)手段找到痕跡。在計(jì)算機(jī)司法鑒定中，常需要對被刪除的數(shù)據(jù)文件進(jìn)行數(shù)據(jù)恢復(fù)。

FAT是一種使用廣泛的文件系統(tǒng)，很多操作系統(tǒng)平臺(tái)都支持FAT文件系統(tǒng)。當(dāng)需要對其進(jìn)行數(shù)據(jù)恢復(fù)時(shí)常需要借助數(shù)據(jù)恢復(fù)軟件。筆者在實(shí)踐中發(fā)現(xiàn)，目前多數(shù)數(shù)據(jù)恢復(fù)軟件無法成功恢復(fù)非連續(xù)存放的數(shù)據(jù)文件。當(dāng)存在非連續(xù)存放的數(shù)據(jù)文件時(shí)，需要進(jìn)行人工分析，既容易出錯(cuò)，工作量又大，而且在司法鑒定中，越少人工干預(yù)，恢復(fù)出的數(shù)據(jù)越具有客觀性，證據(jù)的可靠性越高，越容易被法院接受。因此，研究與開發(fā)成功率高的數(shù)據(jù)恢復(fù)軟件十分必要。本文充分利用FAT文件系統(tǒng)中FAT表簇分配信息、文件記錄表中起始簇的信息以及文件的創(chuàng)建時(shí)間、修改時(shí)間和最近訪問時(shí)間等信息[1]，提出了一種改進(jìn)的數(shù)據(jù)恢復(fù)算法，可以恢復(fù)出大多數(shù)非連續(xù)存放的被刪除的文件，提高了恢復(fù)成功率。

1 FAT文件系統(tǒng)刪除的原理和數(shù)據(jù)恢復(fù)的思想

FAT文件系統(tǒng)主要分為 FAT12、FAT16、FAT32幾種文件系統(tǒng)，其結(jié)構(gòu)大體相似，均有引導(dǎo)區(qū)、FAT表結(jié)構(gòu)、目錄表結(jié)構(gòu)、數(shù)據(jù)區(qū)，但引導(dǎo)區(qū)中BPB表結(jié)構(gòu)、FAT表每一項(xiàng)的大小、根目錄的定位方法有一定差異。另外，在FAT32文件系統(tǒng)中，有一個(gè)FSINFO數(shù)據(jù)結(jié)構(gòu)以及文件的根目錄處在數(shù)據(jù)區(qū)位置[2]。

FAT文件系統(tǒng)中文件被刪除時(shí) （這里僅指徹底刪除，本文不討論一般刪除情形），內(nèi)容發(fā)生改變的結(jié)構(gòu)為文件目錄表、FAT表、FSINFO結(jié)構(gòu)。其中文件目錄表中對應(yīng)某一文件的短文件名和長文件名項(xiàng)目第一個(gè)字節(jié)被修改成特殊的字符、該文件在FAT表中的簇鏈結(jié)構(gòu)全部清空，備份FAT表中對應(yīng)的簇信息會(huì)相應(yīng)更新。另外，在FAT32文件系統(tǒng)中，當(dāng)刪除一個(gè)文件時(shí)，F(xiàn)SINFO結(jié)構(gòu)中下一個(gè)可用的簇的信息會(huì)發(fā)生變化，如果在Windows系統(tǒng)中刪除一個(gè)文件時(shí)，文件目錄項(xiàng)的最近訪問時(shí)間也會(huì)進(jìn)行更新，但數(shù)據(jù)區(qū)文件的內(nèi)容沒有發(fā)生任何變化，除非有新的數(shù)據(jù)覆蓋到該文件存儲(chǔ)的區(qū)域。因此，理論上沒有被覆蓋的被刪除的文件是可以被恢復(fù)的[3]。

目前，比較常見的數(shù)據(jù)恢復(fù)算法有兩類，一類是基于文件系統(tǒng)的數(shù)據(jù)恢復(fù)算法，一種是不依賴文件系統(tǒng)，直接依賴文件特征的數(shù)據(jù)恢復(fù)算法。通常后者恢復(fù)的文件較多，但可恢復(fù)文件類型有限，且很多文件恢復(fù)結(jié)果都是錯(cuò)誤的。基于文件系統(tǒng)的數(shù)據(jù)恢復(fù)算法主要依賴目錄結(jié)構(gòu)的信息進(jìn)行數(shù)據(jù)恢復(fù)，是目前主流的一種數(shù)據(jù)恢復(fù)算法。采用基于目錄結(jié)構(gòu)信息的數(shù)據(jù)恢復(fù)算法時(shí)，由于刪除文件后，目錄結(jié)構(gòu)中對應(yīng)的該文件項(xiàng)目的信息并未被真正地刪除，因此，可以根據(jù)目錄結(jié)構(gòu)中部分文件名信息、文件的起始簇號(hào)、文件的大小等信息，找到數(shù)據(jù)區(qū)對應(yīng)的簇，并從此讀出長度為文件大小的數(shù)據(jù)，即為被刪除文件的內(nèi)容。但是此算法成功恢復(fù)文件的前提之一是，待恢復(fù)的被刪除文件必須連續(xù)存放在存儲(chǔ)設(shè)備中[4,5]。

雖然，F(xiàn)AT文件系統(tǒng)中文件大多數(shù)是連續(xù)存放的，但是，也有一些文件不是連續(xù)存放的。在文件的頭尾之間的連續(xù)簇內(nèi)，有一些簇可能已經(jīng)被現(xiàn)有文件占用，有一些是已經(jīng)刪除的其他文件信息，恢復(fù)這些非連續(xù)被刪除的文件對于司法鑒定業(yè)務(wù)來說是十分重要的。如果待恢復(fù)的被刪除文件是完整的，非連續(xù)存放時(shí)現(xiàn)有算法不能成功進(jìn)行數(shù)據(jù)恢復(fù)。為此，需要提出新的算法以改進(jìn)現(xiàn)有算法不能恢復(fù)不連續(xù)存儲(chǔ)文件的缺陷。

2 FAT文件系統(tǒng)被刪除文件恢復(fù)算法的改進(jìn)

2.1 被刪除的不連續(xù)文件的形態(tài)

當(dāng)被刪除文件不連續(xù)時(shí)，不連續(xù)部分有可能是已分配空間的現(xiàn)有系統(tǒng)文件存放數(shù)據(jù)的簇，也有可能是曾被刪除文件的簇。而且不連續(xù)空間有可能存在多個(gè)，為了研究便利，首先定義某一不連續(xù)文件內(nèi)非本文件的一個(gè)連續(xù)簇段的形態(tài)，再推導(dǎo)出各種復(fù)雜的組合。

2.1.1 實(shí)包

實(shí)包指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被現(xiàn)有文件系統(tǒng)中某一個(gè)或多個(gè)文件占用（即該簇段內(nèi)不存在未實(shí)際分配的簇），簡稱R形態(tài)，如圖1所示（File1為待恢復(fù)文件，虛線表示文件已被刪除，實(shí)線表示文件未被刪除，以下同）。

由于R形態(tài)中每一簇都被現(xiàn)有系統(tǒng)文件占有，因此在FAT結(jié)構(gòu)表中均包含非空信息。在數(shù)據(jù)恢復(fù)算法中如果跳開已經(jīng)分配的簇，在進(jìn)行數(shù)據(jù)恢復(fù)時(shí)，都可以避開R形態(tài)的干擾。如果待恢復(fù)的被刪除文件中只有R形態(tài)數(shù)據(jù)時(shí)，則該文件是完全可以恢復(fù)的。

2.1.2 虛包

虛包指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被已經(jīng)刪除的一個(gè)或多個(gè)文件占有，這些文件是連續(xù)存放的且均為完整的文件或者具備完整的文件信息，簡稱V形態(tài)，如圖2所示。

V形態(tài)存在時(shí)，如果V形態(tài)數(shù)據(jù)是待恢復(fù)的被刪除文件之前被刪除的，則V形態(tài)文件不會(huì)出現(xiàn)尾部被待刪除文件覆蓋的情形。如果V形態(tài)數(shù)據(jù)是待恢復(fù)的被刪除文件之后刪除的，則文件不可能被待恢復(fù)的被刪除文件覆蓋。根據(jù)常見的分配算法，也不會(huì)存在待刪除文件被刪除后，V形態(tài)文件跳空覆蓋待刪除文件。因此，當(dāng)V形態(tài)數(shù)據(jù)的起始部分和結(jié)尾部分都處在不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇之內(nèi)時(shí)，只要在存儲(chǔ)設(shè)備數(shù)據(jù)區(qū)內(nèi)找到確定V形態(tài)文件的信息，則數(shù)據(jù)恢復(fù)可以避開V形態(tài)數(shù)據(jù)的干擾。

2.1.3 半開

半開指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被已經(jīng)刪除的一個(gè)或多個(gè)文件占有，其中存在一個(gè)被刪除的文件其頭部信息不在該連續(xù)區(qū)域內(nèi)，或者一個(gè)文件中間或尾部信息不在該連續(xù)區(qū)域內(nèi)，簡稱O形態(tài)，如圖3所示。

出現(xiàn)O形態(tài)時(shí)，根據(jù)常見的分配算法，O形態(tài)數(shù)據(jù)不可能被待刪除的文件覆蓋，一種常見的情形是，O形態(tài)數(shù)據(jù)與待刪除文件數(shù)據(jù)同時(shí)存在，并相繼被刪除，如果O形態(tài)數(shù)據(jù)半開文件頭能夠在文件目錄表中找到，則文件被恢復(fù)的概率大。如果O形態(tài)數(shù)據(jù)文件尾半開，則表明待恢復(fù)數(shù)據(jù)與被刪除文件過程中有中間文件在該數(shù)據(jù)區(qū)形成，如果中間文件沒有覆蓋待恢復(fù)文件，則文件結(jié)束數(shù)據(jù)區(qū)必然在連續(xù)文件內(nèi)，如果新的文件剛好構(gòu)成V形態(tài)，則文件可能被恢復(fù)，否則較難進(jìn)行恢復(fù)。

2.1.4 全開

全開指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被已經(jīng)刪除的一個(gè)或多個(gè)文件占有，其中存在一個(gè)被刪除的文件其頭部信息不在該連續(xù)區(qū)域內(nèi)，同時(shí)一個(gè)文件中間或尾部信息不在該連續(xù)區(qū)域內(nèi)，簡稱X形態(tài)，如圖4、圖5所示。

全開X形態(tài)存在時(shí)，表明X形態(tài)數(shù)據(jù)所在文件在形成過程中，必然存在中間文件的生成和刪除，且中間文件剛好填充連續(xù)簇內(nèi)剩余的簇，否則不會(huì)形成X形態(tài)。因此恢復(fù)X形態(tài)文件，必須對X形態(tài)內(nèi)數(shù)據(jù)相關(guān)文件進(jìn)行回溯，如果不存在相關(guān)文件的頭部信息或起始簇，則文件難以恢復(fù)。否則，可以通過尋找中間文件信息參照V形態(tài)方法恢復(fù)，對一些特殊情況下的文件有可能進(jìn)行恢復(fù)。

2.1.5 各種形態(tài)的綜合分析

在一個(gè)不連續(xù)文件所占用的連續(xù)空間內(nèi)，存在著若干個(gè)連續(xù)的簇段不屬于本文件。每一個(gè)簇段內(nèi)數(shù)據(jù)形態(tài)可能為上述4種形態(tài)之一，還有可能存在部分簇已經(jīng)分配給現(xiàn)有文件，部分簇處于空閑狀態(tài)。此時(shí)，可能存在R+V、R+O、R+X三種組合形式，其中R+V表示在不連續(xù)文件內(nèi)某一連續(xù)簇段內(nèi)存在若干個(gè)已分配的簇被現(xiàn)有文件系統(tǒng)中文件占有，若將這些已經(jīng)分配的簇去除，簇段內(nèi)其他簇構(gòu)成V形態(tài)，則稱R+V形態(tài)，其他組合類似。因此，對于單獨(dú)的連續(xù)的簇段，可用以下式子表示：

y={R，V，O，X，R+V，R+O，R+X}；

y表示與被恢復(fù)文件無關(guān)的某一連續(xù)數(shù)據(jù)。所有連續(xù)的簇段可以用下述式子表示：

Y={R，V，O，X，R+V，R+O，R+X}*；

其中Y表示待恢復(fù)文件連續(xù)空間中與Y無關(guān)的簇。

對于某一次數(shù)據(jù)恢復(fù)，根據(jù)待恢復(fù)文件存在各種情形分析如下。

（1）若Y為空集，即被恢復(fù)文件是連續(xù)空間，則可以直接讀出文件。

（2）若Y中只有R元素，由于R所占用簇段在FAT簇鏈中有完整記錄，因此只要參考FAT表信息，便可成功恢復(fù)文件。

（3）若Y中只有R、V或R+V，如果V形態(tài)對應(yīng)文件信息在文件記錄表中存在，則V對應(yīng)文件可以恢復(fù)，即可以將V占用的簇排除，同理根據(jù)FAT表排除R，則文件也可以成功恢復(fù)，但是若V對應(yīng)文件信息在文件目錄表中被覆蓋，則文件不能成功恢復(fù)。

（4）若Y中存在O，不存在X形態(tài)時(shí)，若O頭部半開，表明O文件在待恢復(fù)文件之前形成，且O文件連續(xù)空間中Y部分的文件內(nèi)容在Y形成前剛好是完整的文件。如果不符合，根據(jù)分配算法，不可能存在O半開情形；或者Y文件在其之前形成，形成時(shí)，Y文件包含的該連續(xù)簇段是一個(gè)或若干個(gè)完整文件，并且被刪除，刪除后形成O。因此，可以結(jié)合文件目錄表中O形成前刪除文件記錄信息進(jìn)行分析。若存在這樣一個(gè)或幾個(gè)記錄且該記錄成功檢索到，則該文件可以成功恢復(fù)，否則無法恢復(fù)。

（5）若Y中存在 X，則 Y與 X形成先后關(guān)系，且 X、Y不連續(xù)空間文件刪除行為十分復(fù)雜。出現(xiàn)這種情形的可能性十分小。出現(xiàn)的情形類似第4步所述，但X和Y不可能是先后直接形成的，中間伴隨著其他文件的刪除。

根據(jù)上述5種情況分析可知，如果存儲(chǔ)設(shè)備中某個(gè)未知的待恢復(fù)文件是完整的，則可恢復(fù)的可能性比較大。因?yàn)镕AT中最常見的情形是（1）所述，只有少數(shù)情況下屬于（2）～（5）情形。而少數(shù)情況中最常見的又是（2），其次是（3）；（4）與（5）一般只在特殊軟件寫存儲(chǔ)介質(zhì)或者十分特殊的情形時(shí)才會(huì)出現(xiàn)，而且也有可能進(jìn)行部分恢復(fù)。因此，可以看出根據(jù)上述思路制定的算法的成功率提高了。

2.2 改進(jìn)算法核心片段

根據(jù)上述對不連續(xù)空間文件不同形態(tài)的分析以及恢復(fù)思想，筆者研制了基于多結(jié)構(gòu)信息的數(shù)據(jù)恢復(fù)算法，其核心片段描述如下：

/*在文件目錄表FDT中，查找被刪除文件fileName起始簇的簇號(hào)k

*/

k=getFirstCluster(FDT,fileName);

/*根據(jù)文件目錄表FDT中文件fileName的大小等信息，計(jì)算出其所占用簇的數(shù)目M

*/

M=getClusters(FDT,fileName);

/*如果該文件fileName起始簇k非空閑，表明該文件已被覆蓋，無法恢復(fù)，返回錯(cuò)誤

*/

if(!isIdleCluster(k))return ERROR;

/*M個(gè)元素的數(shù)組C存放文件fileName占用的所有簇號(hào)，C[0]存放起始簇號(hào)k

*/

C[0]=k;

k=k+1;

for(i=1;i

{

//循環(huán)查找到下一個(gè)空閑簇的簇號(hào)

while(!isIdleCluster(k)){k=k+1;}

switch(getCases(FDT,k)){

/*函數(shù)getCases判定空閑簇k是否為其他刪除文件的起始簇號(hào)；

返回值0，表明該空閑簇k不是其他刪除文件的起始簇號(hào)；

返回值1，表明該空閑簇k曾為其他刪除文件的起始簇號(hào)，該刪除文件創(chuàng)建在先，刪除可能在先也可能在后，恢復(fù)時(shí)跳過該刪除文件所占用的所有空閑簇；

返回值2，表明該空閑簇k曾為其他刪除文件的起始簇號(hào)，且該刪除文件創(chuàng)建在后，其覆蓋了文件fileName，而此后其自身亦被刪除。

*/

//空閑簇k不是其他刪除文件的起始簇號(hào)

case 0:C[i]=k;

k=k+1;

break;

/*空閑簇k曾為其他非覆蓋刪除文件的起始簇號(hào)；跳過其他非覆蓋的刪除文件所占用的簇；定位文件fileName下一個(gè)空閑簇

*/

case 1:k=getNextFreeCluster(k);

break;

/*空閑簇k曾為其他覆蓋刪除文件的起始簇號(hào)文件無法恢復(fù)，返回錯(cuò)誤信息

*/

case 2:return ERROR;

}

}

//讀出被刪除文件所占用簇的數(shù)據(jù)

return readClusters(C);

上述改進(jìn)算法的核心片段最終可讀出被刪除文件所占用簇的數(shù)據(jù)，再根據(jù)刪除文件的大小，便可恢復(fù)被刪除文件。在進(jìn)行數(shù)據(jù)恢復(fù)時(shí)，首先需要定位被刪除的文件目錄。定位被刪除的文件目錄，依據(jù)該文件的短文件名目錄確定；當(dāng)在目錄項(xiàng)中確定了文件大小后，根據(jù)引導(dǎo)扇區(qū)中每簇扇區(qū)數(shù)信息可以確定文件內(nèi)容占用的簇空間。在讀數(shù)據(jù)區(qū)內(nèi)容時(shí)，讀取的是空閑簇的數(shù)據(jù)信息，這樣可以完全避免R形態(tài)、R+V形態(tài)、R+O形態(tài)、R+X形態(tài)中R數(shù)據(jù)的干擾。判斷刪除在先時(shí)，綜合根據(jù)文件創(chuàng)建時(shí)間、最近訪問時(shí)間（如果在Windows平臺(tái)刪除文件，最近訪問時(shí)間會(huì)更新）等信息進(jìn)行綜合判斷，以確定刪除先后和覆蓋關(guān)系。算法能恢復(fù)大多數(shù)未覆蓋的被刪除文件。

3 改進(jìn)算法的性能分析

傳統(tǒng)的恢復(fù)算法能很好地恢復(fù)連續(xù)存儲(chǔ)的被徹底刪除的文件數(shù)據(jù)，在此基礎(chǔ)上，改進(jìn)的算法還能較好地恢復(fù)非連續(xù)存儲(chǔ)的被刪除的文件數(shù)據(jù)。如果待恢復(fù)的非連續(xù)存儲(chǔ)的刪除文件所在的簇空間內(nèi)，僅包括該被刪除文件和其他未被刪除文件，則該待恢復(fù)文件可以被恢復(fù)。如果待恢復(fù)的非連續(xù)存儲(chǔ)文件所在的簇空間內(nèi)，同時(shí)包括有其他連續(xù)存儲(chǔ)的被刪除文件，只要其他文件的創(chuàng)建時(shí)間在先、刪除在后，也就是待恢復(fù)文件數(shù)據(jù)非被覆蓋，待恢復(fù)文件依然可以被完全恢復(fù)。而且該算法適合不同平臺(tái)下刪除的FAT文件系統(tǒng)文件的恢復(fù)?？傊撍惴ū容^適合應(yīng)用于司法鑒定業(yè)務(wù)，特別當(dāng)需要對特定文件進(jìn)行數(shù)據(jù)恢復(fù)時(shí)，性能更佳。

1 Microsoft MSDN library.File system behavior overview,http://download.microsoft.com/download/4/3/8/43889780-8d45-4b2e-9d3a-c696a890309f/File%20System%20Behavior%20Overview.pdf,2009-10-8

2 Brian C.File system forensic analysis.Boston:Addison Wesley Professional,2005

3 戴士劍，涂彥暉.數(shù)據(jù)恢復(fù)技術(shù)（第2版）.北京：電子工業(yè)出版社，2007

4 章華，劉乃琦，郭建東.基于孩子兄弟樹的FAT32文件刪除恢復(fù)算法.計(jì)算機(jī)應(yīng)用研究，2009（3）：1116～1118

5 鐘秀玉.基于FAT32的數(shù)據(jù)恢復(fù)系統(tǒng)的設(shè)計(jì).計(jì)算機(jī)應(yīng)用與軟件，2008（11）：56～57

6 王中杉，劉乃琦等.基于FAT32文件系統(tǒng)的取證研究與實(shí)現(xiàn).計(jì)算機(jī)工程，2009（9）：176～178