基于多结构信息的FAT文件系统数据恢复算法*

廖根为

（华东政法大学司法鉴定中心 上海 200042）

当计算机网络中存在入侵行为时，即使入侵痕迹被删除或破坏，也有可能通过数据恢复手段找到痕迹。在计算机司法鉴定中，常需要对被删除的数据文件进行数据恢复。

FAT是一种使用广泛的文件系统，很多操作系统平台都支持FAT文件系统。当需要对其进行数据恢复时常需要借助数据恢复软件。笔者在实践中发现，目前多数数据恢复软件无法成功恢复非连续存放的数据文件。当存在非连续存放的数据文件时，需要进行人工分析，既容易出错，工作量又大，而且在司法鉴定中，越少人工干预，恢复出的数据越具有客观性，证据的可靠性越高，越容易被法院接受。因此，研究与开发成功率高的数据恢复软件十分必要。本文充分利用FAT文件系统中FAT表簇分配信息、文件记录表中起始簇的信息以及文件的创建时间、修改时间和最近访问时间等信息[1]，提出了一种改进的数据恢复算法，可以恢复出大多数非连续存放的被删除的文件，提高了恢复成功率。

1 FAT文件系统删除的原理和数据恢复的思想

FAT文件系统主要分为 FAT12、FAT16、FAT32几种文件系统，其结构大体相似，均有引导区、FAT表结构、目录表结构、数据区，但引导区中BPB表结构、FAT表每一项的大小、根目录的定位方法有一定差异。另外，在FAT32文件系统中，有一个FSINFO数据结构以及文件的根目录处在数据区位置[2]。

FAT文件系统中文件被删除时 （这里仅指彻底删除，本文不讨论一般删除情形），内容发生改变的结构为文件目录表、FAT表、FSINFO结构。其中文件目录表中对应某一文件的短文件名和长文件名项目第一个字节被修改成特殊的字符、该文件在FAT表中的簇链结构全部清空，备份FAT表中对应的簇信息会相应更新。另外，在FAT32文件系统中，当删除一个文件时，FSINFO结构中下一个可用的簇的信息会发生变化，如果在Windows系统中删除一个文件时，文件目录项的最近访问时间也会进行更新，但数据区文件的内容没有发生任何变化，除非有新的数据覆盖到该文件存储的区域。因此，理论上没有被覆盖的被删除的文件是可以被恢复的[3]。

目前，比较常见的数据恢复算法有两类，一类是基于文件系统的数据恢复算法，一种是不依赖文件系统，直接依赖文件特征的数据恢复算法。通常后者恢复的文件较多，但可恢复文件类型有限，且很多文件恢复结果都是错误的。基于文件系统的数据恢复算法主要依赖目录结构的信息进行数据恢复，是目前主流的一种数据恢复算法。采用基于目录结构信息的数据恢复算法时，由于删除文件后，目录结构中对应的该文件项目的信息并未被真正地删除，因此，可以根据目录结构中部分文件名信息、文件的起始簇号、文件的大小等信息，找到数据区对应的簇，并从此读出长度为文件大小的数据，即为被删除文件的内容。但是此算法成功恢复文件的前提之一是，待恢复的被删除文件必须连续存放在存储设备中[4,5]。

虽然，FAT文件系统中文件大多数是连续存放的，但是，也有一些文件不是连续存放的。在文件的头尾之间的连续簇内，有一些簇可能已经被现有文件占用，有一些是已经删除的其他文件信息，恢复这些非连续被删除的文件对于司法鉴定业务来说是十分重要的。如果待恢复的被删除文件是完整的，非连续存放时现有算法不能成功进行数据恢复。为此，需要提出新的算法以改进现有算法不能恢复不连续存储文件的缺陷。

2 FAT文件系统被删除文件恢复算法的改进

2.1 被删除的不连续文件的形态

当被删除文件不连续时，不连续部分有可能是已分配空间的现有系统文件存放数据的簇，也有可能是曾被删除文件的簇。而且不连续空间有可能存在多个，为了研究便利，首先定义某一不连续文件内非本文件的一个连续簇段的形态，再推导出各种复杂的组合。

2.1.1 实包

实包指的是不连续文件内非属于本文件数据的连续簇全被现有文件系统中某一个或多个文件占用（即该簇段内不存在未实际分配的簇），简称R形态，如图1所示（File1为待恢复文件，虚线表示文件已被删除，实线表示文件未被删除，以下同）。

由于R形态中每一簇都被现有系统文件占有，因此在FAT结构表中均包含非空信息。在数据恢复算法中如果跳开已经分配的簇，在进行数据恢复时，都可以避开R形态的干扰。如果待恢复的被删除文件中只有R形态数据时，则该文件是完全可以恢复的。

2.1.2 虚包

虚包指的是不连续文件内非属于本文件数据的连续簇全被已经删除的一个或多个文件占有，这些文件是连续存放的且均为完整的文件或者具备完整的文件信息，简称V形态，如图2所示。

V形态存在时，如果V形态数据是待恢复的被删除文件之前被删除的，则V形态文件不会出现尾部被待删除文件覆盖的情形。如果V形态数据是待恢复的被删除文件之后删除的，则文件不可能被待恢复的被删除文件覆盖。根据常见的分配算法，也不会存在待删除文件被删除后，V形态文件跳空覆盖待删除文件。因此，当V形态数据的起始部分和结尾部分都处在不连续文件内非属于本文件数据的连续簇之内时，只要在存储设备数据区内找到确定V形态文件的信息，则数据恢复可以避开V形态数据的干扰。

2.1.3 半开

半开指的是不连续文件内非属于本文件数据的连续簇全被已经删除的一个或多个文件占有，其中存在一个被删除的文件其头部信息不在该连续区域内，或者一个文件中间或尾部信息不在该连续区域内，简称O形态，如图3所示。

出现O形态时，根据常见的分配算法，O形态数据不可能被待删除的文件覆盖，一种常见的情形是，O形态数据与待删除文件数据同时存在，并相继被删除，如果O形态数据半开文件头能够在文件目录表中找到，则文件被恢复的概率大。如果O形态数据文件尾半开，则表明待恢复数据与被删除文件过程中有中间文件在该数据区形成，如果中间文件没有覆盖待恢复文件，则文件结束数据区必然在连续文件内，如果新的文件刚好构成V形态，则文件可能被恢复，否则较难进行恢复。

2.1.4 全开

全开指的是不连续文件内非属于本文件数据的连续簇全被已经删除的一个或多个文件占有，其中存在一个被删除的文件其头部信息不在该连续区域内，同时一个文件中间或尾部信息不在该连续区域内，简称X形态，如图4、图5所示。

全开X形态存在时，表明X形态数据所在文件在形成过程中，必然存在中间文件的生成和删除，且中间文件刚好填充连续簇内剩余的簇，否则不会形成X形态。因此恢复X形态文件，必须对X形态内数据相关文件进行回溯，如果不存在相关文件的头部信息或起始簇，则文件难以恢复。否则，可以通过寻找中间文件信息参照V形态方法恢复，对一些特殊情况下的文件有可能进行恢复。

2.1.5 各种形态的综合分析

在一个不连续文件所占用的连续空间内，存在着若干个连续的簇段不属于本文件。每一个簇段内数据形态可能为上述4种形态之一，还有可能存在部分簇已经分配给现有文件，部分簇处于空闲状态。此时，可能存在R+V、R+O、R+X三种组合形式，其中R+V表示在不连续文件内某一连续簇段内存在若干个已分配的簇被现有文件系统中文件占有，若将这些已经分配的簇去除，簇段内其他簇构成V形态，则称R+V形态，其他组合类似。因此，对于单独的连续的簇段，可用以下式子表示：

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

y表示与被恢复文件无关的某一连续数据。所有连续的簇段可以用下述式子表示：

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

其中Y表示待恢复文件连续空间中与Y无关的簇。

对于某一次数据恢复，根据待恢复文件存在各种情形分析如下。

（1）若Y为空集，即被恢复文件是连续空间，则可以直接读出文件。

（2）若Y中只有R元素，由于R所占用簇段在FAT簇链中有完整记录，因此只要参考FAT表信息，便可成功恢复文件。

（3）若Y中只有R、V或R+V，如果V形态对应文件信息在文件记录表中存在，则V对应文件可以恢复，即可以将V占用的簇排除，同理根据FAT表排除R，则文件也可以成功恢复，但是若V对应文件信息在文件目录表中被覆盖，则文件不能成功恢复。

（4）若Y中存在O，不存在X形态时，若O头部半开，表明O文件在待恢复文件之前形成，且O文件连续空间中Y部分的文件内容在Y形成前刚好是完整的文件。如果不符合，根据分配算法，不可能存在O半开情形；或者Y文件在其之前形成，形成时，Y文件包含的该连续簇段是一个或若干个完整文件，并且被删除，删除后形成O。因此，可以结合文件目录表中O形成前删除文件记录信息进行分析。若存在这样一个或几个记录且该记录成功检索到，则该文件可以成功恢复，否则无法恢复。

（5）若Y中存在 X，则 Y与 X形成先后关系，且 X、Y不连续空间文件删除行为十分复杂。出现这种情形的可能性十分小。出现的情形类似第4步所述，但X和Y不可能是先后直接形成的，中间伴随着其他文件的删除。

根据上述5种情况分析可知，如果存储设备中某个未知的待恢复文件是完整的，则可恢复的可能性比较大。因为FAT中最常见的情形是（1）所述，只有少数情况下属于（2）～（5）情形。而少数情况中最常见的又是（2），其次是（3）；（4）与（5）一般只在特殊软件写存储介质或者十分特殊的情形时才会出现，而且也有可能进行部分恢复。因此，可以看出根据上述思路制定的算法的成功率提高了。

2.2 改进算法核心片段

根据上述对不连续空间文件不同形态的分析以及恢复思想，笔者研制了基于多结构信息的数据恢复算法，其核心片段描述如下：

/*在文件目录表FDT中，查找被删除文件fileName起始簇的簇号k

*/

k=getFirstCluster(FDT,fileName);

/*根据文件目录表FDT中文件fileName的大小等信息，计算出其所占用簇的数目M

*/

M=getClusters(FDT,fileName);

/*如果该文件fileName起始簇k非空闲，表明该文件已被覆盖，无法恢复，返回错误

*/

if(!isIdleCluster(k))return ERROR;

/*M个元素的数组C存放文件fileName占用的所有簇号，C[0]存放起始簇号k

*/

C[0]=k;

k=k+1;

for(i=1;i

{

//循环查找到下一个空闲簇的簇号

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

switch(getCases(FDT,k)){

/*函数getCases判定空闲簇k是否为其他删除文件的起始簇号；

返回值0，表明该空闲簇k不是其他删除文件的起始簇号；

返回值1，表明该空闲簇k曾为其他删除文件的起始簇号，该删除文件创建在先，删除可能在先也可能在后，恢复时跳过该删除文件所占用的所有空闲簇；

返回值2，表明该空闲簇k曾为其他删除文件的起始簇号，且该删除文件创建在后，其覆盖了文件fileName，而此后其自身亦被删除。

*/

//空闲簇k不是其他删除文件的起始簇号

case 0:C[i]=k;

k=k+1;

break;

/*空闲簇k曾为其他非覆盖删除文件的起始簇号；跳过其他非覆盖的删除文件所占用的簇；定位文件fileName下一个空闲簇

*/

case 1:k=getNextFreeCluster(k);

break;

/*空闲簇k曾为其他覆盖删除文件的起始簇号文件无法恢复，返回错误信息

*/

case 2:return ERROR;

}

}

//读出被删除文件所占用簇的数据

return readClusters(C);

上述改进算法的核心片段最终可读出被删除文件所占用簇的数据，再根据删除文件的大小，便可恢复被删除文件。在进行数据恢复时，首先需要定位被删除的文件目录。定位被删除的文件目录，依据该文件的短文件名目录确定；当在目录项中确定了文件大小后，根据引导扇区中每簇扇区数信息可以确定文件内容占用的簇空间。在读数据区内容时，读取的是空闲簇的数据信息，这样可以完全避免R形态、R+V形态、R+O形态、R+X形态中R数据的干扰。判断删除在先时，综合根据文件创建时间、最近访问时间（如果在Windows平台删除文件，最近访问时间会更新）等信息进行综合判断，以确定删除先后和覆盖关系。算法能恢复大多数未覆盖的被删除文件。

3 改进算法的性能分析

传统的恢复算法能很好地恢复连续存储的被彻底删除的文件数据，在此基础上，改进的算法还能较好地恢复非连续存储的被删除的文件数据。如果待恢复的非连续存储的删除文件所在的簇空间内，仅包括该被删除文件和其他未被删除文件，则该待恢复文件可以被恢复。如果待恢复的非连续存储文件所在的簇空间内，同时包括有其他连续存储的被删除文件，只要其他文件的创建时间在先、删除在后，也就是待恢复文件数据非被覆盖，待恢复文件依然可以被完全恢复。而且该算法适合不同平台下删除的FAT文件系统文件的恢复。总之，该算法比较适合应用于司法鉴定业务，特别当需要对特定文件进行数据恢复时，性能更佳。

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 戴士剑，涂彦晖.数据恢复技术（第2版）.北京：电子工业出版社，2007

4 章华，刘乃琦，郭建东.基于孩子兄弟树的FAT32文件删除恢复算法.计算机应用研究，2009（3）：1116～1118

5 钟秀玉.基于FAT32的数据恢复系统的设计.计算机应用与软件，2008（11）：56～57

6 王中杉，刘乃琦等.基于FAT32文件系统的取证研究与实现.计算机工程，2009（9）：176～178