Как пройти «тест бесплатных программ восстановления данных»

Ранее мой коллега Viktor-Flash проводил тест бесплатных программ для восстановления данных (первая и вторая части). Он рассмотрел две проблемы, которые часто встречаются на флешках с файловой системой FAT32. Несмотря на повреждения, некоторым программам удалось хорошо восстановить данные. Я попробую рассказать о том как именно работают методы, позволяющие вернуть данные и насколько это вообще возможно.

 Статья получилась большой, поэтому я разбил ее на части. В первой части расскажу про устройство FAT32 и как восстановить данные в первом тесте (где было стерто все до таблиц FAT).

Как добраться до файла в FAT32

 Начну с поверхностного описания того, как хранятся данные внутри FAT32, благо, ее структура достаточно проста в сравнении с другими ФС. Предположим, на флешке есть файл «\documents\Secret.doc». Разберемся какой путь проходит драйвер файловой системы, чтобы прочитать данные этого документа.

Когда мы подключаем флешку к компьютеру, то первым делом ОС проверяет ее 0й сектор. В нем почти всегда записан Master Boot Record (MBR), там перечислены диапазоны секторов, которые заняты разделами. На флешках раздел почти всегда один, начинается он обычно (но не всегда) в 63 или 2048 секторе и занимает почти все доступное пространство.

 В MBR записана байтовая метка, которая указывает на тип раздела. У FAT32 это 0x0B или 0x0С. Далее, надо прочитать первый сектор раздела, в котором должен находиться BootFAT32. Из него мы можем узнать много полезной информации: 

размер кластера (блок которым оперирует ФС);

количество, размер и расположение таблиц FAT (обычно 1 или 2, про их назначение расскажу дальше);

начало области кластеризации — той области, которая разбита на кластеры и которая доступна для записи пользовательских данных;

кластер с корневым каталогом, он же Root (часто это 2й кластер)*.

*Примечание: в FAT32 область кластеризации нумеруется со 2го кластера, т. е. Root нередко находится в самом начале этой области.

Каждой папке в FAT соответствует списочная структура, которая так и называется — FAT Folder (или каталог FAT). Это список подкаталогов и файлов, которые содержит конкретный каталог. В каждом элементе списка указаны: имя, размер для файла, даты создания, удаления, модификации, атрибуты и стартовый кластер (начало файла или расположение соответствующей структуры FAT Folder для подкаталога).

 Важный момент, которым мы потом воспользуемся. Любой каталог FAT, кроме корневого, начинается с 2х стандартных элементов. Это описатели самого себя '.' и родителя '..'. А уже далее описатели всех остальных подкаталогов и файлов. Т.е. мы можем проверить номер текущего кластера (стартовый кластер у '.'), а также можем подняться на уровень выше в иерархии (перейти к каталогу '..').

Итак, мы нашли и разобрали корневой каталог, нашли в нем запись об подкаталоге с именем «documents». Перешли на указанный кластер, чтобы узнать содержимое папки «documents», разобрали соответствующий FAT Folder. Там нашли описатель для файла «Secret.doc» из которого, в числе прочего, узнали первый кластер файла и размер файла. 

 Если бы все файлы были непрерывными, то этого уже было бы достаточно для того, чтобы прочитать данные файла. Но для фрагментированных файлов надо еще построить размещение. Таблица FAT как раз и нужна для того, чтобы выставить в правильном порядке кластеры, относящиеся к файлу. Если «TopSecrect.doc» начинается в кластере №100, то в 100й ячейке таблицы будет указано, какой кластер брать следующим, т.е. где лежит второй кластер файла. И так далее по цепочке. В конце цепочки кластеров будет стоять маркер конца. Свободные кластеры также помечены специальным значением 0 (помните, что 0-го кластера нет?), таблица FAT служит еще и для отслеживания свободного/занятого места в разделе.

Теперь, когда мы более-менее знакомы с устройством FAT32, можно порассуждать о том, как ее лечить.

Тест первый: без boot'ов

Первый тест заключался в том, что было стерто все до начала таблиц FAT. Это значит, что мы потеряли BootFAT32 и его копию (если она была). А вместе с ними еще и кучу полезной информации. Но так ли трудно ее восстановить? Оказывается, что просто.

 Начну с таблиц FAT. Мы не знаем где именно их искать, но знаем что они есть. К счастью, таблицы имеют узнаваемую и проверяемую структуру. Поиск основан на следующих наблюдениях: 

таблица FAT имеет характерное начало (помните 0й и 1й «мифические» кластеры?) — часто 0xF8FFFF0FFFFFFFFF

ячейки в таблице FAT (4х байтовые беззнаковые целые) могут содержать либо служебные значения, либо ограничены размером раздела;

помимо этого, во всей таблице FAT не должно быть одинаковых значений (кроме служебных);

для многих ячеек в таблице можно утверждать, что ячейка N содержит значение N+1, т. е. после кластера N идет кластер N+1. Это сугубо эвристическое наблюдение. Оно справедливо потому, что драйвер ФС все-таки старается размещать данные непрерывно

Таким образом, мы можем найти таблицу или таблицы FAT и даже определить их размер (как минимум размер значимой части). Сразу после последней таблицы часто находится корневой каталог и, одновременно, начало области кластеризации. Можно проверить это предположение, но есть более универсальный способ.

 Помните, что все каталоги FAT, кроме корневого, начинаются с 2х стандартных записей? Так вот, эти записи позволяют очень хорошо их находить среди всех остальных данных. Если мы найдем всего 2 каталога, то получим 2 пары значений: (LBA1, ClusterNo1), (LBA2, ClusterNo2). А это уже школьная задачка на пропорции, из которой сразу находим размер кластера 

ClusterSize = (LBA1-LBA2)/(ClusterNo1-ClusterNo2)

и начало области кластеризации (помним «съеденных» кластерах 0 и 1) 

ClusterizationStart = LBA1 – (ClusterNo1-2)*ClusterSize

 Осталось найти Root. В любом каталоге есть запись о родительском каталоге '..'. Если мы будем подниматься по иерархии вверх, то достаточно быстро дойдем до Root (который узнаем, например, по отсутствию записей '.' и '..'). 

Заключение по первому тесту

 Пришлось немного постараться, но все что нужно для полноценного восстановления данных мы нашли: таблицы FAT, начало области кластеризации, размер кластера, положение Root. Можно утверждать, что для таких повреждений есть методика, которая позволяет в большинстве случаев вернуть 100% данных (получить такую же ФС, как раньше), lost forever still can be found… «Меньшинство» случаев — это когда не получилось найти даже парочку FAT Folder или были проблемы с обнаружением таблиц FAT. Однако такие ситуации скорее редкость.