基于WindowsFAT32的数据恢复原理分析及算法研究

论文导读：本文首先就Windows下FAT32文件系统的结构做了介绍。本文分析了FAT32文件系统下基于数据簇连续分配情况和非连续分配情况的数据恢复原理。并提出了这两种情况下的数据恢复算法。根据B图和C图情况下的数据恢复原理。
关键词：数据恢复，数据恢复原理，数据恢复算法，簇分配，FAT32
 

1 引言

“数据恢复”，顾名思义，就是在数据存储设备遭受用户误操作、黑客攻击、病毒侵袭、硬件故障、物理环境损害等事件之后，从存储介质中分析并提取出原数据的过程[1][2]。随着我国信息化步伐的加快和互联网的快速发展，计算机的应用渗入到了各行各业以及人们的日常生活中。越来越多的企业和个人都会将许多重要的数据存储到计算机系统中。而一旦我们的系统由于人为或其他原因出现差错从而导致数据的丢失，那么如何能够快速且准确的恢复出原数据将成为一个至关重要的问题。这就使得数据恢复技术不论对于个人、企业还是国家都显得日益重要起来。

本文首先就Windows下FAT32文件系统的结构做了介绍，并阐述了文件删除的原理。在此基础上，本文分析了FAT32文件系统下基于数据簇连续分配情况和非连续分配情况的数据恢复原理，并提出了这两种情况下的数据恢复算法。最后对这两种算法进行了分析和比较。

2 FAT32文件系统

2.1 FAT32文件系统总体结构

FAT32文件系统由引导扇区，文件分配表FAT，根目录，数据区和保留扇区组成。如图1所示。

图1 FAT32文件系统总体结构

2.2 引导扇区

引导扇区含有JMP指令、厂商信息、BPB参数块、FAT32区段和结束标志。其数据结构如表1[3]所示。

表1 引导扇区结构

如图1所示，根目录通常位于第二个FAT之后。由此，我们可以由表1引导扇区信息中的保留扇区数、FAT个数、每个FAT所占扇区数来定位到根目录的起始位置。即根目录起始位置 = 保留扇区数 + FAT个数×每个FAT所占扇区数。这里的根目录起始位置是相对于引导扇区而言的。

2.3 文件分配表FAT

文件分配表由FAT表项组成。在FAT32文件系统中，每个FAT表项占用32位。每个FAT表项都对应着一个簇号。而且，当FAT表项的值为00000000H时表示对应的簇是空簇，未被分配使用，当值为0FFFFFFFH时表示对应的簇是某文件的最后一个数据簇。当值为00000001H～0FFFFFEFH时表示该簇已分配使用，且该FAT表项值是对应文件的下一个数据簇的簇号。[3]

在FAT文件系统中，系统通过FAT链来读取和写入文件数据。文件系统在目录项中存放着文件数据的起始簇号，在FAT区中，该起始簇号对应的FAT项中记录着该文件占用的下一个簇的簇号，该簇号对应的FAT项中又记录着文件数据占用的下一个簇的簇号，一直到下一个簇号所对应的FAT表项值是结束标志0FFFFFFFH为止，这个FAT链才算结束。这样，系统在访问文件数据时，首先找到该文件的目录项，从中找出起始簇号，然后根据对应的FAT链就可以找出文件的所有数据簇。

簇号和FAT项的对应关系为：簇号乘以4，将乘积作为相对文件分配表起始位置的偏移（从0开始计算），就找到了该簇号对应的FAT项。 [3]

2.4 目录项

操作系统通过目录树结构来管理一个分区中的文件，根节点存放盘符，每一个叶节点存放一个文件，而中间节点则是文件夹。从根节点到叶节点的路径就形成了该文件的绝对路径。这种管理方法对应于磁盘上，就是文件系统创建根目录区，根目录区中的每一个目录项指示目录树中根节点下的一个文件或文件夹的各种属性和数据的存放位置。文件夹，又叫做子目录。它对应的目录项中所指向的数据起始簇中的内容不是数据而是该文件夹内的各个文件的目录项。同样，子目录下的目录项集合中还可以有子目录目录项，这样的子目录目录项所指向的数据起始簇内，同样存放着一个目录项集合。FAT32文件系统通过这种方式来管理和组织一个个的文件。

不管是根目录下的目录项还是子目录中的目录项，大小均为32字节，其数据结构及表示的含义是相同的。目录项的结构[3]如表2所示。

表2 FAT32目录项结构

根据上面的目录项信息，我们可以得到文件的起始簇号和文件大小。这两个数据对文件数据的恢复至关重要。

2 文件删除原理

在Windows操作系统中删除文件分为两类，一类是暂时删除，另一类是彻底删除。暂时删除文件，就是不是真正的删除文件，只是把文件移动到了回收站中。论文格式。这个文件的FAT簇链并没有任何变化，所以可以从回收站中直接还原文件。论文格式。[4]

彻底删除文件，会把文件目录项的首字节改为删除标志“E5H”，同时这个文件的FAT链中的所有FAT表项值全部改为空簇标志“00000000H”。此外，文件目录项中偏移为14H～15H处的起始簇号的两个高字节被清零。彻底删除文件不和回收站发生任何联系[4]。这样，彻底删除文件后，就不能直接还原文件了。但彻底删除文件后，原文件的数据还是在数据区中的，只要不被覆盖掉，我们就可以恢复出原文件的数据。

3 FAT32文件系统数据恢复原理和算法

3.1 FAT32文件系统数据恢复原理

由2中文件彻底删除的原理，我们可以知道文件的数据如果未被覆盖，则文件的数据还存在于数据区中。因此，要想把这些数据恢复出来，重建我们的文件，则需要首先找到这些数据的入口在哪里，即找到数据的起始簇号。如果该文件的起始簇号小于两个字节所能表示的最大值65535，则用目录项中偏移为1AH～1BH处的低位字即可存储该起始簇号值。这种情况下，删除文件时，就不存在起始簇号高字被清零的问题，我们可以直接从目录项中偏移为1AH～1BH处找到文件数据的起始簇号。但如果起始簇号超出了低位字所能表示的最大值，则需要用目录项中偏移为14H～15H处的高位字来存储其值。这样，删除文件时，起始簇号的两个高字节就会被清零，仅保留了两个低字节。这种情况下，我们要想得到起始簇号的两个高字节，就需要参照创建时间值与之接近的其他正常文件的起始簇号来确定两个高字节[5]。实际进行恢复时，我们可以根据该文件目录项前后的正常文件的目录项中的偏移为14H～15H处的值来判断起始簇号的两个高字节值。

其次，我们还需要知道文件数据存放在其余哪些簇上。在此之前，我们需要先了解一下Windows操作系统的簇的分配策略。Windows操作系统对文件分配簇时，采用下一可用分配策略。论文格式。即为一个文件分配了一个簇后，直接由此簇位置向后搜索下一个可用簇，继续为其分配，而不会从文件系统的开始处进行重新搜索。[5]基于这个分配策略，一个文件的数据存储有三种可能的情况。我们用图2来一一说明。

图2 文件存储情况

图2中显示了三种不同的文件数据存储情况。淡灰色方框表示分配给这个文件使用的簇，深灰色方框表示分配给其他文件使用的簇，白色方框表示未分配的空簇。A图表示这个文件数据只占用了一个簇。B图表示这个文件占用了4个簇，簇号为5、6、7、8，而且系统给这个文件分配的这四个簇是连续的。C图表示这个文件数据占用了4个簇，簇号为5、7、8、10，但系统给这个文件分配的这四个簇是非连续的。

对于A图所示情况，恢复时，只需在确定起始簇号后，对起始簇中的相应文件大小的数据进行提取即可恢复文件。对于B图情况，恢复时，在确定起始簇号后，从起始簇开始，一直向后提取数据，直到提取出的数据大小等于文件大小时为止，这样就恢复出了原文件的数据。

对于C图情况，该文件数据是非连续存放的。删除文件后，簇5、7、8、10所对应的FAT表项值为“00000000H”。此时，如果簇6、9所对应的文件未被删除，则6、9所对应的FAT表项值为有效值00000001H～0FFFFFFFH。这样，恢复时，先由目录项中的文件大小计算出所对应的簇数。在确定起始簇号后，就可以从起始簇号对应的FAT表项开始向后搜索，记录下FAT表项值为“00000000H”的所对应的簇号。当记录下的簇号数等于文件大小所对应的簇数时，停止搜索。然后根据记录下的簇号，提取出对应簇中的数据，直到提取出的数据大小等于文件大小时为止，这样就恢复出了原文件的数据。

根据B图和C图情况下的数据恢复原理，提出以下基于数据簇连续分配的文件恢复算法和基于数据簇非连续分配的文件恢复算法。

3.2 基于数据簇连续分配的文件恢复算法

算法步骤如下：

⑴ 确定被删除文件所在分区的引导扇区的位置。可以由主引导扇区中的分区表确定。

⑵ 从引导扇区中读取 “每扇区字节数”、“每簇扇区数”、“保留扇区数”、“FAT个数”和“每个FAT所占扇区数”的参数值。并计算根目录相对于引导扇区的起始位置（从0开始）。根目录相对起始位置=保留扇区数+FAT个数×每个FAT所占扇区数。

⑶ 根据被删除文件的文件路径，从根目录开始逐层往下遍历找到该文件所在目录的目录项集合，并遍历该目录项集合，找到文件名与被删除文件的文件名部分匹配，且后缀名一致的目录项。

⑷ 从找到的目录项中读取偏移为1AH～1BH的两个字节，确定起始簇号的低位字。读取偏移为1CH～1FH的四个字节，确定文件数据的大小。

⑸ 遍历该目录项集合的所有正常文件的目录项，记录每个目录项中偏移为14H～15H处的值，并找出出现频次最高的值，把该值作为起始簇号的高位字。

⑹ 根据确定的起始簇号和文件大小，找到文件数据的起始簇，并读取数据，直到所读取数据大小等于文件大小时为止。

⑺ 保存数据，并重命名文件。

⑻ 如果得到的文件不是我们想要的原文件，则需从⑸中记录的起始簇号高位字的集合中选择另一个出现频次较高的值作为该文件起始簇号的高位字，重复步骤⑹⑺，直到恢复出原文件或遍历完高位字集合为止。如果遍历完⑸中的高位字集合还未恢复出原文件，则需遍历0000H～FFFFH的值并作为该文件起始簇号的高位字，重复步骤⑹⑺直到恢复出原文件或遍历结束为止。

 1/2    1 2 下一页 尾页