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

研究与开发　

基于多结构信息的ＦＡＴ文件系统数据恢复算法　

廖根为　

（华东政法大学司法鉴定中心上海２０００４２）　

当计算机网络中存在人侵行为时，即使入侵痕迹被　删除或破坏，也有可能通过数据恢复手段找到痕迹。在　

计算机司法鉴定中，常需要对被删除的数据文件进行数　据恢复。　

ＦＡＴ是一种使用广泛的文件系统，很多操作系统平台　

都支持ＦＡＴ文件系统。当需要对其进行数据恢复时常需要　

借助数据恢复软件。笔者在实践中发现，目前多数数据恢　

复软件无法成功恢复非连续存放的数据文件。当存在非连　续存放的数据文件时，需要进行人工分析．既容易出错，工　

作量又大，而且在司法鉴定中，越少人工干预，恢复出的数　

据越具有客观性，证据的可靠性越高，越容易被法院接受。　

因此，研究与开发成功率高的数据恢复软件十分必要。本　

文充分利用ＦＡＴ文件系统中ＦＡＴ表簇分配信息、文件记　录表中起始簇的信息以及文件的创建时间、修改时间和最　

近访问时间等信息ｆｌＪ．提出了一种改进的数据恢复算法．可　

国家社科基金青年项目（Ｎｏ．０７ＣＦＸ０３４），上海市教委科研创新　项目（Ｎｏ．０８ＹＳ１３８）　以恢复出大多数非连续存放的被删除的文件，提高了恢复　

成功率。　

１　ＦＡＴ文件系统删除的原理和数据恢复　

的思想　

ＦＡＴ文件系统主要分为ＦＡＴ１２、ＦＡＴ１６、ＦＡＴ３２几种文　

件系统，其结构大体相似．均有引导区、ＦＡＴ表结构、目录　

表结构、数据区，但引导区中ＢＰＢ表结构、ＦＡＴ表每一项　的大小、根目录的定位方法有一定差异。另外，在ＦＡＴ３２　

文件系统中，有一个ＦＳＩＮＦＯ数据结构以及文件的根目录　

处在数据区位置口１。　

ＦＡＴ文件系统中文件被删除时（这里仅指彻底删除，　

本文不讨论一般删除情形），内容发生改变的结构为文件　目录表、ＦＡＴ表、ＦＳＩＮＦＯ结构。其中文件目录表中对应某　

文件的短文件名和长文件名项目第一个字节被修改成　

特殊的字符、该文件在ＦＡＴ表中的簇链结构全部清空，备　

份ＦＡＴ表中对应的簇信息会相应更新。另外，在ＦＡＴ３２文　

件系统中，当删除一个文件时，ＦＳＩ

ＮＦＯ结构中下一个可用　电信科学ｉ２　

的簇的信息会发生变化，如果在Ｗｉｎｄｏｗｓ系统中删除一个　文件时．文件目录项的最近访问时间也会进行更新，但数　

据区文件的内容没有发生任何变化，除非有新的数据覆盖　到该文件存储的区域。因此，理论上没有被覆盖的被删除　

的文件是可以被恢复的　１。　

目前．比较常见的数据恢复算法有两类，一类是基于　

文件系统的数据恢复算法，一种是不依赖文件系统，直接　

依赖文件特征的数据恢复算法。通常后者恢复的文件较　多，但可恢复文件类型有限．且很多文件恢复结果都是错　

误的。基于文件系统的数据恢复算法主要依赖目录结构的　

信息进行数据恢复，是目前主流的一种数据恢复算法。采　

用基于目录结构信息的数据恢复算法时，由于删除文件　

后，目录结构中对应的该文件项目的信息并未被真正地删　

除，因此，可以根据目录结构中部分文件名信息、文件的起　始簇号、文件的大小等信息，找到数据区对应的簇，并从此　

读出长度为文件大小的数据，即为被删除文件的内容。但　

是此算法成功恢复文件的前提之一是，待恢复的被删除文　

件必须连续存放在存储设备中＿４－一１。　虽然．ＦＡＴ文件系统中文件大多数是连续存放的，但　

是，也有一些文件不是连续存放的。在文件的头尾之间的　

连续簇内．有一些簇可能已经被现有文件占用，有一些是　已经删除的其他文件信息，恢复这些非连续被删除的文件　

对于司法鉴定业务来说是十分重要的。如果待恢复的被删　

除文件是完整的．非连续存放时现有算法不能成功进行数　

据恢复。为此，需要提出新的算法以改进现有算法不能恢　

复不连续存储文件的缺陷。　

２　ＦＡＴ文件系统被删除文件恢复算法的　

改进　

２．１　被删除的不连续文件的形态　当被删除文件不连续时，不连续部分有可能是已分配　空间的现有系统文件存放数据的簇，也有可能是曾被删除　

文件的簇。而且不连续空间有可能存在多个，为了研究便　利，首先定义某一不连续文件内非本文件的一个连续簇段　

的形态，再推导出各种复杂的组合。　

２．１．１　实包　实包指的是不连续文件内非属于本文件数据的连续　

簇全被现有文件系统中某一个或多个文件占用（即该簇段　内不存在未实际分配的簇），简称Ｒ形态，如图１所示　

（Ｆｉｌｅｌ为待恢复文件，虚线表示文件已被删除，实线表示　

文件未被删除，以下同）。　

由于Ｒ形态中每一簇都被现有系统文件占有．因此在　

ＦＡＴ结构表中均包含非空信息。在数据恢复算法中如果跳　

开已经分配的簇，在进行数据恢复时，都可以避开Ｒ形态　的干扰。如果待恢复的被删除文件中只有Ｒ形态数据时，　

则该文件是完全可以恢复的。　

２．１．２虚包　

虚包指的是不连续文件内非属于本文件数据的连续　簇全被已经删除的一个或多个文件占有．这些文件是连续　

存放的且均为完整的文件或者具备完整的文件信息，简称　

Ｖ形态，如图２所示。　

Ｖ形态存在时．如果Ｖ形态数据是待恢复的被删除文　

件之前被删除的，则Ｖ形态文件不会出现尾部被待删除文　件覆盖的情形。如果Ｖ形态数据是待恢复的被删除文件之　

后删除的，则文件不可能被待恢复的被删除文件覆盖。根　

据常见的分配算法，也不会存在待删除文件被删除后．Ｖ　形态文件跳空覆盖待删除文件。因此，当Ｖ形态数据的起始　

部分和结尾部分都处在不连续文件内非属于本文件数据的　

连续簇之内时，只要在存储设备数据区内找到确定Ｖ形态　

文件的信息，则数据恢复可以避开Ｖ形态数据的干扰。　

２．１．３　半开　

半开指的是不连续文件内非属于本文件数据的连续簇　

图１　Ｒ形态　

图２　Ｖ形态　谤究与歼发　

图３　Ｏ形态　

全被已经删除的一个或多个文件占有，其中存在一个被　

删除的文件其头部信息不在该连续区域内，或者一个文件　

中间或尾部信息不在该连续区域内，简称０形态，如图３所示。　

出现０形态时，根据常见的分配算法，０形态数据不　

可能被待删除的文件覆盖．一种常见的情形是，０形态数　据与待删除文件数据同时存在，并相继被删除，如果Ｏ形　

态数据半开文件头能够在文件目录表中找到，则文件被恢　

复的概率大。如果０形态数据文件尾半开，则表明待恢复　

数据与被删除文件过程中有中间文件在该数据区形成，如　果中间文件没有覆盖待恢复文件，则文件结束数据区必然　

在连续文件内．如果新的文件刚好构成Ｖ形态，则文件可　

能被恢复，否则较难进行恢复。　

２．１．４全开　

全开指的是不连续文件内非属于本文件数据的连续　簇全被已经删除的一个或多个文件占有．其中存在一个被　

删除的文件其头部信息不在该连续区域内，同时一个文件　

中间或尾部信息不在该连续区域内，简称Ｘ形态，如图４、　图５所示。　

全开Ｘ形态存在时，表明Ｘ形态数据所在文件在形　成过程中，必然存在中间文件的生成和删除，且中间文件　

刚好填充连续簇内剩余的簇，否则不会形成Ｘ形态。因此　恢复Ｘ形态文件，必须对Ｘ形态内数据相关文件进行回　

溯，如果不存在相关文件的头部信息或起始簇，则文件难　

以恢复。否则，可以通过寻找中间文件信息参照Ｖ形态方　

法恢复．对一些特殊情况下的文件有可能进行恢复。　２．１．５各种形态的综合分析　

在一个不连续文件所占用的连续空间内，存在着若干　个连续的簇段不属于本文件。每一个簇段内数据形态可能　为上述４种形态之一，还有可能存在部分簇已经分配给现　

有文件，部分簇处于空闲状态。此时，可能存在Ｒ　Ｖ、Ｒ　０、　

Ｒ　ｘ三种组合形式，其中Ｒ　Ｖ表示在不连续文件内某一连　

续簇段内存在若干个已分配的簇被现有文件系统中文件　

占有，若将这些已经分配的簇去除．簇段内其他簇构成Ｖ　形态，则称Ｒ　Ｖ形态，其他组合类似。因此，对于单独的连　

续的簇段，可用以下式子表示：　

ｙ＝｛Ｒ，Ｖ，０，Ｘ，Ｒ　，Ｒ　０，ＷＸ）；　ｖ表示与被恢复文件无关的某一连续数据。所有连续　的簇段可以用下述式子表示：　

Ｙ＝ｆＲ，Ｖ，０，Ｘ，Ｒ　Ｖ，Ｒ　０，Ｒ　ｘ／　；　其中Ｙ表示待恢复文件连续空间中与Ｙ无关的簇。　

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

分析如下。　（１）若Ｙ为空集，即被恢复文件是连续空间，则可以直　

接读出文件。　

（２）若Ｙ中只有Ｒ元素，由于Ｒ所占用簇段在ＦＡＴ簇　链中有完整记录，因此只要参考ＦＡＴ表信息，便可成功恢　

复文件。　

（３）若Ｙ中只有Ｒ、Ｖ或Ｒ　Ｖ，如果Ｖ形态对应文件信　

息在文件记录表中存在，则Ｖ对应文件可以恢复，即可以　将Ｖ占用的簇排除，同理根据ＦＡＴ表排除Ｒ，则文件也可　

以成功恢复．但是若Ｖ对应文件信息在文件目录表中被覆　

盖，则文件不能成功恢复。　（４）若Ｙ中存在０，不存在Ｘ形态时，若０头部半开，　

表明０文件在待恢复文件之前形成。且０文件连续空间　

中Ｙ部分的文件内容在Ｙ形成前刚好是完整的文件。如　

果不符合，根据分配算法，不可能存在０半开情形；或者Ｙ　

图４　Ｘ形态　

图５　Ｘ形态（交叉）

　电信　科学　

文件在其之前形成，形成时，Ｙ文件包含的该连续簇段是　个或若干个完整文件，并且被删除，删除后形成Ｏ。因　

此，可以结合文件目录表中Ｏ形成前删除文件记录信息进　

行分析。若存在这样一个或几个记录且该记录成功检索　到．则该文件可以成功恢复，否则无法恢复。　

（５）若Ｙ中存在Ｘ，则Ｙ与Ｘ形成先后关系，且Ｘ、Ｙ　

不连续空间文件删除行为十分复杂。出现这种情形的可能　

性十分小。出现的情形类似第４步所述，但Ｘ和Ｙ不可能　是先后直接形成的，中间伴随着其他文件的删除。　

根据上述５种情况分析可知，如果存储设备中某个未　

知的待恢复文件是完整的，则可恢复的可能性比较大。因　

为ＦＡＴ中最常见的情形是（１）所述，只有少数情况下属于　

（２）～（５）情形。而少数情况中最常见的又是（２），其次是　

（３）；（４）与（５）一般只在特殊软件写存储介质或者十分特　殊的情形时才会出现，而且也有可能进行部分恢复。因此，　

可以看出根据上述思路制定的算法的成功率提高了。　

２．２改进算法核心片段　

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

核心片段描述如下：　

在文件目录表ＦＤＴ中。查找被删除文件ｆｉｌｅＮａｍｅ起　

始簇的簇号ｋ　

术，　

ｋ＝ｇｅｔＦｉｒｓｔＣｌｕｓｔｅｒ（ＦＤＴ，ｆｉｌｅＮａｍｅ）；　根据文件目录表ＦＤＴ中文件ｆｉｌｅＮａｍｅ的大小等信　

息．计算出其所占用簇的数目Ｍ　

丰／　

Ｍ＝ｇｅｔＣｌｕｓｔｅｒｓ（ＦＤＴ，ｆｉｌｅＮａｍｅ）；　／　如果该文件ｆｉｌｅＮａｍｅ起始簇ｋ非空闲，表明该文件　

已被覆盖，无法恢复，返回错误　

丰／　

ｉｆ（！ｉｓＩｄｌｅＣｌｕｓｔｅｒ（ｋ））ｒｅｔｕｒｎ　ＥＲＲＯＲ；　Ｍ个元素的数组Ｃ存放文件ｆｉｌｅＮａｍｅ占用的所有　

簇号，Ｃｆ０１存放起始簇号ｋ　

术／　Ｃ［０】＝ｋ；　ｋ＝ｋ＋１：　ｆｏｒ（ｉ＿１；ｉ＜Ｍ；ｉ＋＋）　

｛　／／循环查找到下一个空闲簇的簇号　ｗｈｉｌｅ（！ｉｓｌｄｌｅＣｌｕｓｔｅｒ（ｋ））｛ｋ＝ｋ＋１；｝　ｓｗｉｔｃｈ（ｇｅｔＣａｓｅｓ（ＦＤＴ，ｋ））｛　，半函数ｇｅｔＣａｓｅｓ判定空闲簇ｋ是否为其他删除文件　

的起始簇号：　

返回值０．表明该空闲簇ｋ不是其他删除文件的起始　

簇号：　返回值１．表明该空闲簇ｋ曾为其他删除文件的起始　簇号，该删除文件创建在先，删除可能在先也可能在后，恢