Поиск удаленных файлов: файловая система FAT
В этой статье я хотел бы рассказать об алгоритмах, которые мы использовали при создании программы для восстановления данных Hetman Partition Recovery.
Но для начала стоит сказать, что восстановление файлов вообще возможно, потому-что они хранятся в виде блоков информации, записанных на секторах жёсткого диска. Секторы могут располагаться как последовательно, один за другим, так и быть хаотично разбросанными по всей поверхности диска. Расположение секторов зависит от того, какие именно блоки были свободны в момент сохранения файла на диск. Если система не обнаружила на диске непрерывного свободного блока секторов достаточного размера для того, чтобы сохранить файл в виде непрерывной последовательности данных, система будет фрагментировать файл, записывая его отдельные части в свободные блоки.
Кстати, в случае, если файлы фрагментированы и файловая система повреждена или уничтожена (например, после форматирования диска), инструменты восстановления данных используют алгоритмы поиска по сигнатурам, считывающие все данные с поверхности жёсткого диска с целью обнаружения известных типов файлов.
И здесь кроется основная сложность. Алгоритмы сигнатурного поиска в своей работе зависят от структур заголовков файлов, проанализировав которые, возможно определить размер файла. Обладая информацией о местоположении заголовка и зная точный размер файла, программы вычисляют сектора на диске, которые, по их мнению, содержат данные файла. Как вы понимаете, корректно работать эти алгоритмы будут только в условиях, когда весь файл целиком хранится в виде одного непрерывного фрагмента. Если же файл был сохранён в виде множества разрозненных фрагментов, восстановить его в отсутствие записи в файловой системе будет чрезвычайно тяжело, практически невозможно.
Но и для таких случаев существуют специальные методы, которыми пользуются спецслужбы и криминалисты, позволяющие восстановить содержимое некоторых типов файлов буквально по кусочкам. Их работа похожа на сбор паззла: различные фрагменты данных пробуются в разных местах файла, после чего с помощью эвристических алгоритмов файл анализируется на целостность. Нужно ли говорить, что работа таких алгоритмов чрезвычайно ресурсоёмка, но при этом настолько медленна и ненадёжна, что использовать их вне стен криминалистических лабораторий просто невыгодно.
Так вот, для того, чтобы ориентироваться в записанной информации, Windows создает запись в файловой системе с указанием того, какие именно секторы на диске занимает содержимое конкретного файла.
В момент, когда пользователь удаляет файл, Windows не стирает и не перезаписывает содержимое секторов на диске. В случае с удалением файла с SSD память может очищаться включенной функцией TRIM. Содержимое записи о файле в файловой системе также не удаляется, но подвергается модификации: система помечает запись как принадлежащую удалённому файлу. Теперь Windows может сохранить в это пространство какой-нибудь другой файл. Но пока этого не произошло, можно попробовать восстановить содержимое удалённого файла. Инструменты по восстановлению удалённых файлов сканируют файловую систему в поиске записей, помеченных как удалённые. Проанализировав такие записи, становится возможным узнать точные адреса секторов на диске, в которые было записано содержимое оригинального файла. После быстрой дополнительной проверки – не принадлежат ли эти сектора какому-либо другому файлу, – программа считает данные из нужных секторов и сохранит их в новом файле. Что происходит, если в файловой системе не осталось записи, указывающей на удалённый файл? В этом случае простейшие инструменты не срабатывают.
Далее я опишу алгоритм поиска и восстановления удаленных файлов с FAT раздела который мы применили при разработки нашей программы, лучше всего этот алгоритм описан в книге "Криминалистический анализ файловых систем” автора Брайана Кэрриэ.
Windows система разделов содержит одну или несколько таблиц, при этом каждая запись таблицы описывает один раздел. В данных записи обычно указывается начальный сектор раздела, конечный сектор раздела (или длина) и тип раздела.
Для поиска файловой системы наша программа исходит из предположения, что в каждом разделе находилась файловая система. Многие файловые системы начинаются со структуры данных с постоянной сигнатурой. Например, файловая система FAT содержит значения 0x55 и 0хАА в байтах 510 и 511 первого сектора. Программа восстановления ищет сигнатуры и определяет по ним возможное начало раздела. При обнаружении сигнатуры часто выполняются дополнительные проверки с диапазонами значений, допустимых для некоторых полей структуры данных. Например, одно из полей файловой системы FAT определяет количество секторов в кластере; значение поля представляет собой степень 2 (например, 1, 2, 4, 8, 16, 32, 64 или 128). Любое другое значение свидетельствует о том, что сектор не является частью загрузочного сектора файловой системы FAT, хотя он и заканчивается сигнатурой 0х55АА.
Основная концепция файловой системы FAT заключается в том, что каждому файлу и каталогу выделяется структура данных, называемая записью каталога. В этой структуре хранится имя файла, его размер, начальный адрес содержимого файла и другие метаданные. Содержимое файлов и каталогов хранится в блоках данных, называемых кластерами. Если файлу или каталогу выделяется более одного кластера, остальные кластеры находятся при помощи структуры данных, называемой FAT. Структура FAT используется как для идентификации следующих кластеров в файлах, так и для определения состояния выделения кластеров.
Файловая система FAT делится на три физические области. Первая область называется зарезервированной, в ней хранятся данные из категории файловой системы. В FAT12 и FAT16 зарезервированная область занимает всего 1 сектор, но формально ее размер определяется в загрузочном секторе. Вторая область FAT — содержит основные и резервные структуры FAT. Она начинается в секторе, следующем за зарезервированной областью, а ее размер определяется количеством и размером структур FAT. Третья область — область данных содержит кластеры, выделяемые для хранения файлов и содержимого каталогов.
Одной из первых задач при анализе файловой системы FAT должна стать идентификация трех физических областей. Зарезервированная область начинается в секторе 0 файловой системы, а ее размер указан в загрузочном секторе. В FAT 12/16 она обычно занимает всего 1 сектор, а в FAT32 для нее резервируются несколько секторов.
Область FAT содержит одну или несколько структур FAT и начинается в секторе, следующем за зарезервированной областью. Ее размер вычисляется умножением количества структур FAT на размер одной структуры; оба значения хранятся в загрузочном секторе (зарезервированная область).
При удалении файла в Windows его запись каталога помечается как неиспользуемая, а записи кластеров в FAT обнуляются. Начало и размер файла известны, но информация об остальных кластерах файла отсутствует.
Можно попытаться восстановить содержимое файла, прочитав данные из известного начального кластера. Что касается выбора остальных кластеров, у программы восстановления есть два метода: читать объем данных, соответствующий размеру файла, не обращая внимания на состояние выделения, или же читать данные только из свободных кластеров.
Второй метод чаще приводит к успеху, потому что он восстанавливает некоторые фрагментированные файлы. Рисунок 5 поясняет происходящее:
на нем показаны шесть кластеров файловой системы и три разных сценария. Размер файла составляет 7094 байт, а размер кластера — 2048 байт; следовательно, для файла были выделены четыре кластера. Мы также знаем, что файл начинается с кластера 56. Светло-серые кластеры представляют фактическое местонахождение содержимого файла в каждом сценарии.
В сценарии на рис. 5 (А) файл занимает четыре смежных кластера. В этом случае в обоих вариантах правильно восстанавливаются кластеры 56-59. На рис. 5 (В) файл был разделен на три фрагмента, а кластеры между фрагментами (57 и 60) были выделены другому файлу во время восстановления. В этом сценарии первый метод восстанавливает кластеры 56-59 и ошибочно включает содержимое кластера 57. Второй метод правильно восстанавливает секторы 56, 58,59 и 61. На рис. 5 (С) показан сценарий, при котором файлу выделены те же фрагменты, что и на рис. 5 (В), но кластеры между фрагментами не были выделены другим файлам на момент восстановления. В этом сценарии оба метода ошибочно восстановят кластеры 56-59, как это было сделано в предыдущем примере. В процессе восстановления файла возможны и другие ситуации, но в них часть файла оказывается стертой, и ни один способ уже не сможет точно восстановить данные. Таким образом, метод 2 (с учетом состояния выделения кластеров) способен восстанавливать удаленные файлы чаще, чем метод 1.
В заключение скажу что файловая система NTFS устроена гораздо сложнее FAT, поиск удаленных файлов в ней тема отдельной статьи.
Но для начала стоит сказать, что восстановление файлов вообще возможно, потому-что они хранятся в виде блоков информации, записанных на секторах жёсткого диска. Секторы могут располагаться как последовательно, один за другим, так и быть хаотично разбросанными по всей поверхности диска. Расположение секторов зависит от того, какие именно блоки были свободны в момент сохранения файла на диск. Если система не обнаружила на диске непрерывного свободного блока секторов достаточного размера для того, чтобы сохранить файл в виде непрерывной последовательности данных, система будет фрагментировать файл, записывая его отдельные части в свободные блоки.
Кстати, в случае, если файлы фрагментированы и файловая система повреждена или уничтожена (например, после форматирования диска), инструменты восстановления данных используют алгоритмы поиска по сигнатурам, считывающие все данные с поверхности жёсткого диска с целью обнаружения известных типов файлов.
И здесь кроется основная сложность. Алгоритмы сигнатурного поиска в своей работе зависят от структур заголовков файлов, проанализировав которые, возможно определить размер файла. Обладая информацией о местоположении заголовка и зная точный размер файла, программы вычисляют сектора на диске, которые, по их мнению, содержат данные файла. Как вы понимаете, корректно работать эти алгоритмы будут только в условиях, когда весь файл целиком хранится в виде одного непрерывного фрагмента. Если же файл был сохранён в виде множества разрозненных фрагментов, восстановить его в отсутствие записи в файловой системе будет чрезвычайно тяжело, практически невозможно.
Но и для таких случаев существуют специальные методы, которыми пользуются спецслужбы и криминалисты, позволяющие восстановить содержимое некоторых типов файлов буквально по кусочкам. Их работа похожа на сбор паззла: различные фрагменты данных пробуются в разных местах файла, после чего с помощью эвристических алгоритмов файл анализируется на целостность. Нужно ли говорить, что работа таких алгоритмов чрезвычайно ресурсоёмка, но при этом настолько медленна и ненадёжна, что использовать их вне стен криминалистических лабораторий просто невыгодно.
Так вот, для того, чтобы ориентироваться в записанной информации, Windows создает запись в файловой системе с указанием того, какие именно секторы на диске занимает содержимое конкретного файла.
В момент, когда пользователь удаляет файл, Windows не стирает и не перезаписывает содержимое секторов на диске. В случае с удалением файла с SSD память может очищаться включенной функцией TRIM. Содержимое записи о файле в файловой системе также не удаляется, но подвергается модификации: система помечает запись как принадлежащую удалённому файлу. Теперь Windows может сохранить в это пространство какой-нибудь другой файл. Но пока этого не произошло, можно попробовать восстановить содержимое удалённого файла. Инструменты по восстановлению удалённых файлов сканируют файловую систему в поиске записей, помеченных как удалённые. Проанализировав такие записи, становится возможным узнать точные адреса секторов на диске, в которые было записано содержимое оригинального файла. После быстрой дополнительной проверки – не принадлежат ли эти сектора какому-либо другому файлу, – программа считает данные из нужных секторов и сохранит их в новом файле. Что происходит, если в файловой системе не осталось записи, указывающей на удалённый файл? В этом случае простейшие инструменты не срабатывают.
Далее я опишу алгоритм поиска и восстановления удаленных файлов с FAT раздела который мы применили при разработки нашей программы, лучше всего этот алгоритм описан в книге "Криминалистический анализ файловых систем” автора Брайана Кэрриэ.
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 обнуляются. Начало и размер файла известны, но информация об остальных кластерах файла отсутствует.
Можно попытаться восстановить содержимое файла, прочитав данные из известного начального кластера. Что касается выбора остальных кластеров, у программы восстановления есть два метода: читать объем данных, соответствующий размеру файла, не обращая внимания на состояние выделения, или же читать данные только из свободных кластеров.
Второй метод чаще приводит к успеху, потому что он восстанавливает некоторые фрагментированные файлы. Рисунок 5 поясняет происходящее:
на нем показаны шесть кластеров файловой системы и три разных сценария. Размер файла составляет 7094 байт, а размер кластера — 2048 байт; следовательно, для файла были выделены четыре кластера. Мы также знаем, что файл начинается с кластера 56. Светло-серые кластеры представляют фактическое местонахождение содержимого файла в каждом сценарии.
В сценарии на рис. 5 (А) файл занимает четыре смежных кластера. В этом случае в обоих вариантах правильно восстанавливаются кластеры 56-59. На рис. 5 (В) файл был разделен на три фрагмента, а кластеры между фрагментами (57 и 60) были выделены другому файлу во время восстановления. В этом сценарии первый метод восстанавливает кластеры 56-59 и ошибочно включает содержимое кластера 57. Второй метод правильно восстанавливает секторы 56, 58,59 и 61. На рис. 5 (С) показан сценарий, при котором файлу выделены те же фрагменты, что и на рис. 5 (В), но кластеры между фрагментами не были выделены другим файлам на момент восстановления. В этом сценарии оба метода ошибочно восстановят кластеры 56-59, как это было сделано в предыдущем примере. В процессе восстановления файла возможны и другие ситуации, но в них часть файла оказывается стертой, и ни один способ уже не сможет точно восстановить данные. Таким образом, метод 2 (с учетом состояния выделения кластеров) способен восстанавливать удаленные файлы чаще, чем метод 1.
В заключение скажу что файловая система NTFS устроена гораздо сложнее FAT, поиск удаленных файлов в ней тема отдельной статьи.
