数字复活：挽救被格式化硬盘的照片

一张梗图：如遇火灾，请提交代码后逃离建筑

最近在 B 站看了蒋炎岩老师开设的《操作系统》课程，我非常推荐这门课。蒋老师上课的最大特点是直击本质，将复杂的计算机组件抽象为简单的模型。例如，蒋老师将 I/O 设备接口的本质定义为“几组约定好功能的线”，将文件系统比作“磁盘上的数据结构”。这种方法的好处是，即使学生将来忘记了具体的内容，仍然能够从基础概念和蓝图推导和绘制出全貌。

课上有一个与文件系统相关的实验引起了我的兴趣，实验的主要内容是从被格式化的 FAT32 文件系统中恢复图片操作系统：设计与实现 (2023 春季学期), M5: File Recovery。本文记录了完成实验的过程。

恢复任务

我们有一个大小为 64 MiB 的 FAT32 文件系统，其中在 /DCIM 目录DCIM （Digital Camera Images）目录是数码相机、手机等拍照设备中用于存放照片与视频的标准目录名称。下进行了很多次照片读写的操作（这意味着文件系统中存在碎片）。在这些操作之后，我们使用命令 mkfs.fat 格式化了文件系统。我们的任务是尽可能多地从这个格式化的文件系统中恢复照片的名称和内容。

恢复的基本原理是：当我们删除文件或者“快速格式化”磁盘时，实际上只是将文件的索引删除，而文件的实际数据仍然存在于磁盘上。因此，只要我们能够找到这些被标记为可用的文件，并恢复它们的索引和数据，就有机会恢复被删除的照片。

恢复流程

了解 FAT32 存储格式

首先我们要弄明白 FAT32 系统的存储格式。FAT32 包含三个重要的部分：

  1. 保留区（Reserved Region）
  2. FAT 区（FAT Region），包含有两份一样的文件分配表。
  3. 文件和目录数据区（File and Directory Data Region）

结合文档Microsoft FAT Specification，并观察文件系统的内容（这里推荐一个浏览二进制文件的工具 Hexed ItHexed It: Browser-based Online and Offline Hex Editor），我们能得到下面的关键信息：

  1. 卷（Volume）的第一个扇区是引导扇区（Boot Sector）和 BPB（BIOS Parameter Block）。从引导扇区我们可以知道每个扇区有 512 个字节（bytes），每个簇（cluster）有 8 个扇区，所以 簇的大小是 0x1000。保留区的大小是 0x32 个扇区，也就是说 FAT 区的开始位置是 0x4000。一个 FAT 占用 128 个扇区，一共有两个 FAT，还要除去前两个不用的簇，所以 第一个簇的偏移量是 128 x 512 x 2 + 0x4000 - 2 x 0x1000 = 0x22000。第二个扇区是文件系统信息（FSInfo）结构，是辅助系统优化的数据，可以忽略。
  2. 每个 FAT entry 的大小为 32 位（4 字节），前两个 FAT entry（即 0x4000~0x4008）用于记录系统状态。在被格式化的文件系统中，表示文件占用的 FAT entries 被置为零，这导致我们无法知道某个簇的下一个簇的位置。
  3. 根目录位于第三个簇（从零开始计数是编号为 2 的簇），也就是地址是 0x24000。
  4. 在格式化后，数据和目录（除去根目录）仍然存在。但是 FAT 的信息没有了，我们需要根据目录项来恢复文件名、文件大小、文件第一个簇的位置，以及根据文件数据的相关性来恢复图片数据。

恢复目录项

由于图片文件都在 /DCIM 目录而不是根目录 / 下，所以在格式化时，根目录被清除了，而图片文件名得到了保留。这样的设计简化了问题。否则，如果图片都放在根目录下，格式化之后就无法找回图片名字了。

现在我们来恢复目录项。首先，我们要找到 /DCIM 目录的第一个簇编号，因为这个目录是整个文件系统中第一个创建的东西，所以它紧跟在下一个可用的簇之后，即编号为 3 的簇。这引出了一个新问题：由于目录下的图片太多了，一个簇无法存储 /DCIM 目录下的所有目录项，同时第二个簇的编号并不是紧跟在第一个簇之后（即编号不是 4），所以现在我们需要猜测哪些簇存放着目录项。我观察到目录项有一个明显特征：在我们的问题中，DIR_Attr 属性只能是 ATTR_LONG_NAME、ATTR_ARCHIVE 或 ATTR_DIRECTORY 中的一个，因此我们可以先假设所有簇都存放着目录项，然后检查 DIR_Attr 属性，如果不满足我们的观察，那么这个簇存储的就是图片数据。这样，排除了非目录项的簇，我们就找到了所有存放目录项的簇。

接下来，我们根据文档Microsoft FAT Specification的第六章（Directory Structure）和第七章（Long File Name Implementation）的详细描述，就可以恢复所有的图片文件名、图片文件大小和图片第一个簇的编号。在实现过程中，有两个小细节需要注意：

首先，长文件名可能会跨越两个簇的边界，我们可以根据 LDIR_Ord 的值来判断和恢复。由于这种情况出现的次数不多（即一个簇最多出现一次这种情况），所以我偷懒没有实现这部分功能。

其次，已删除的文件可能仍然存在于目录项中。下面的示例中的 0x00025c20 处就是一个例子。

12345678910111213141516171819# Previous directory entry
00025bc0: 4262 006d 0070 0000 00ff ff0f 00ac ffff  Bb.m.p..........
00025bd0: ffff ffff ffff ffff ffff 0000 ffff ffff  ................
00025be0: 0143 0036 0062 0073 0075 000f 00ac 6200  .C.6.b.s.u....b.
00025bf0: 4f00 4400 6700 5200 3300 0000 5000 2e00  O.D.g.R.3...P...
00025c00: 4336 4253 5542 7e31 424d 5020 0064 2b5a  C6BSUB~1BMP .d+Z
00025c10: ac50 cc56 0000 2b5a ac50 e115 bec8 0900  .P.V..+Z.P......

# An empty file (?)
00025c20: e534 534e 4d42 7e31 424d 5020 0064 275a  .4SNMB~1BMP .d'Z
00025c30: ac50 ac50 0000 275a ac50 0000 0000 0000  .P.P..'Z.P......

# Next directory entry
00025c40: 4230 0053 005a 002e 0062 000f 006d 6d00  B0.S.Z...b...mm.
00025c50: 7000 0000 ffff ffff ffff 0000 ffff ffff  p...............
00025c60: 0138 0075 0047 0069 0043 000f 006d 5a00  .8.u.G.i.C...mZ.
00025c70: 6d00 5300 5600 6600 7600 0000 7700 6800  m.S.V.f.v...w.h.
00025c80: 3855 4749 435a 7e31 424d 5020 0064 2a5a  8UGICZ~1BMP .d*Z
00025c90: ac50 cc56 0000 2a5a ac50 741b fae9 0f00  .P.V..*Z.Pt.....

一开始遇到这种情况时我很困惑，以为是一个空文件（因为文件大小为零），但是在挂载之后又找不到同样名字的文件。后来我注意到这个目录项的短文件名的第一个字符不是可读的 ASCII 字符，怀疑它可能有特殊含义。在文档中搜索“E5”，果然发现了相关的说明：

0xE5 indicates the directory entry is free (available). However, 0xE5 is a valid KANJI日本汉字，是书写日语时所使用的汉字 lead byte value for the character set used in Japan. For KANJI character set based names, the value 0x05 is stored in DIR_Name[0] - if required - to represent 0xE5. If the FAT file system implementation reads DIR_NAME[0] = 0x05 and if the character set used is KANJI, it must perform the appropriate substitution in memory prior to returning the name to the application.

至此，我们已经恢复了所有图片文件的名称、大小和第一个簇的编号。

恢复图片数据

在上一步，我们得到了存放每个图片数据的第一个簇的位置，以及图片的大小。现在我们需要根据这个线索，找出接下来的所有存放某张图片的所有簇。

最简单的想法是假设图片数据是完全连续存储的。然而，在多次对文件系统进行读写操作后，可能会导致系统中存在“碎片”，即图片数据并不完全连续存储。

针对这个问题，蒋老师在作业中给出了提示：针对 bitmap 连续存储像素的特性去判断两个簇是否处于同一张图片。本来我是打算按这个思路来进行的，但是写了一些代码后发现解析 BMP 格式图片文件有点麻烦了。我们不仅需要根据图片文件的头部信息计算像素存储位置的偏移量，还需要考虑用于行间像素对齐的填充字节。

因此，我选择了另一种更简单的实现方式。我的想法是，对于同一张图片的两个局部区域来说，如果它们代表了相似的内容和颜色分布，则它们的直方图很可能是相似的。直方图是用于表示图像中不同颜色或灰度级别出现频率的统计工具。在我们的任务中，每个簇都包含图片局部区域的像素数据。为了简化操作，我们可以直接将每个字节视为灰度级别，而不考虑 RGB 颜色通道。然后，我们可以计算两个直方图的相似度，以确定两个簇是否属于同一张图片。我咨询了 ChatGPT，并最终选择了 Bhattacharyya 距离作为衡量两个直方图相似度的指标。

当然，这种方案存在一些限制。首先，尽管同一张图片的两个局部区域可能具有相似的直方图，但这并不是绝对的，而是取决于局部内容的相似性和差异性。其次，我们只能判断两个簇是否属于同一张图片，而很难确定这两个簇是否相邻。

恢复结果

我使用了课程提供的公开样例对代码进行了测试。样例文件系统大小为 64 MiB，包含 97 张图片。我实现的代码可以在恢复被格式化的 FAT32 硬盘中的照片时使用，具体代码请参见这里。以下是主要的恢复结果：

  • 文件名恢复成功率：99.0%，达成课程要求的 75% 的目标
  • 图片数据恢复成功率：
    • 方案一“假设图片数据是完全连续存储的”：47.4%
    • 方案二“利用直方图判断两个簇是否处于同一张图片”：69.0%，达成课程要求的 50% 的目标
  • 恢复时间：所有操作均在 2 秒内完成，满足时间限制的 10 秒要求

成功例子

Gérôme - Bathers by the Edge of a River

失败例子 1

Francois Boucher - Summer Pastoral

在这个例子中，图片恢复一半后找不到接下来的簇了。（在 BMP 格式中，像素是按行存储的。每行的像素从左到右依次排列，从图像的底部逐行向上存储。）

失败例子 2

Honoré Daumier - Different Monomanias of Political Madmen

在这个例子中，中间部分的数据没有被正确恢复。结尾部分的数据被拼接到了开头正常恢复的数据后面，由于像素数据没有对齐（包括 RGB 通道数据和纵向坐标），所以颜色有偏差并且图像有偏移。

总结

本次实验中我们学习了文件恢复的基本原理和方法，并了解了 FAT32 文件系统的存储格式和相关信息。通过恢复目录项和图片数据，成功实现了照片的恢复，并利用直方图相似度判断两个簇是否属于同一张图片。实验结果显示，所提出的方法部分达到了恢复的目标。

从实际应用的角度来看，尽管我们可以在实验环境中恢复被格式化的 FAT32 硬盘中的照片，但仍然可以说它只是一个玩具级别的工具。虽然 FAT32 是一种兼容性较好的文件系统，在 SD 卡、U 盘等设备中广泛使用，但在真正遇到这种情况时，还是建议依赖专业的数据恢复软件来获得可靠的结果。