В этой статье я хотел бы рассказать об алгоритме, который мы использовали при создании программы для восстановления данных Hetman Partition Recovery.
Windows система разделов содержит одну или несколько таблиц, при этом каждая запись таблицы описывает один раздел. В данных записи обычно указывается начальный сектор раздела, конечный сектор раздела (или длина) и тип раздела.
Для поиска файловой системы наша программа исходит из предположения, что в каждом разделе находилась файловая система. Многие файловые системы начинаются со структуры данных с постоянной сигнатурой. Например, файловая система FAT содержит значения 0x55 и 0хАА в байтах 510 и 511 первого сектора. Программа восстановления ищет сигнатуры и определяет по ним возможное начало раздела. При обнаружении сигнатуры часто выполняются дополнительные проверки с диапазонами значений, допустимых для некоторых полей структуры данных. Например, одно из полей файловой системы FAT определяет количество секторов в кластере; значение поля представляет собой степень 2 (например, 1, 2, 4, 8, 16, 32, 64 или 128). Любое другое значение свидетельствует о том, что сектор не является частью загрузочного сектора файловой системы FAT, хотя он и заканчивается сигнатурой 0х55АА.
Как найти файл в FAT таблице
Основная концепция файловой системы FAT заключается в том, что каждому файлу и каталогу выделяется структура данных, называемая записью каталога. В этой структуре хранится имя файла, его размер, начальный адрес содержимого файла и другие метаданные. Содержимое файлов и каталогов хранится в блоках данных, называемых кластерами. Если файлу или каталогу выделяется более одного кластера, остальные кластеры находятся при помощи структуры данных, называемой FAT. Структура FAT используется как для идентификации следующих кластеров в файлах, так и для определения состояния выделения кластеров.
Файловая система FAT делится на три физические области. Первая область называется зарезервированной, в ней хранятся данные из категории файловой системы. В FAT12 и FAT16 зарезервированная область занимает всего 1 сектор, но формально ее размер определяется в загрузочном секторе. Вторая область FAT — содержит основные и резервные структуры FAT. Она начинается в секторе, следующем за зарезервированной областью, а ее размер определяется количеством и размером структур FAT. Третья область — область данных содержит кластеры, выделяемые для хранения файлов и содержимого каталогов.
Одной из первых задач при анализе файловой системы FAT должна стать идентификация трех физических областей. Зарезервированная область начинается в секторе 0 файловой системы, а ее размер указан в загрузочном секторе. В FAT 12/16 она обычно занимает всего 1 сектор, а в FAT32 для нее резервируются несколько секторов.
Область FAT содержит одну или несколько структур FAT и начинается в секторе, следующем за зарезервированной областью. Ее размер вычисляется умножением количества структур FAT на размер одной структуры; оба значения хранятся в загрузочном секторе (зарезервированная область).
Восстановление файлов
При удалении файла в Windows его запись каталога помечается как неиспользуемая, а записи кластеров в FAT обнуляются (рис. 9.18). Начало и размер файла известны, но информация об остальных кластерах файла отсутствует.
Можно попытаться восстановить содержимое файла, прочитав данные из известного начального кластера. Что касается выбора остальных кластеров, у программы восстановления есть два метода: читать объем данных, соответствующий размеру файла, не обращая внимания на состояние выделения, или же читать данные только из свободных кластеров.
В случае, если файлы фрагментированы и файловая система повреждена или уничтожена (например, после форматирования диска), инструменты восстановления данных используют алгоритмы поиска по сигнатурам, считывающие все данные с поверхности жёсткого диска с целью обнаружения известных типов файлов.
И здесь кроется основная сложность. Алгоритмы сигнатурного поиска в своей работе зависят от структур заголовков файлов, проанализировав которые, возможно определить размер файла. Обладая информацией о местоположении заголовка и зная точный размер файла, программы вычисляют сектора на диске, которые, по их мнению, содержат данные файла. Как вы понимаете, корректно работать эти алгоритмы будут только в условиях, когда весь файл целиком хранится в виде одного непрерывного фрагмента. Если же файл был сохранён в виде множества разрозненных фрагментов, восстановить его в отсутствие записи в файловой системе будет чрезвычайно тяжело, практически невозможно.
Но и для таких случаев существуют специальные методы, которыми пользуются спецслужбы и криминалисты, позволяющие восстановить содержимое некоторых типов файлов буквально по кусочкам. Их работа похожа на сбор пазла: различные фрагменты данных пробуются в разных местах файла, после чего с помощью эвристических алгоритмов файл анализируется на целостность. Нужно ли говорить, что работа таких алгоритмов чрезвычайно ресурсоёмка, но при этом настолько медленна и ненадёжна, что использовать их вне стен криминалистических лабораторий просто невыгодно.
Автор: cigulev
