Каталоги
Каталог представляется записью MFT и содержит ссылки на файлы и другие каталоги. NTFS умеет быстро находить определенный файл в каталоге, потому что каталог хранит информацию о содержащихся в нем файлах в формате дерева. Поиск файла по упорядоченному дереву занимает намного меньше времени, чем при линейном поиске. В свою очередь, это накладывает дополнительные, незначительные временные издержки, при добавлении файлов/каталогов в дерево, на поддержании дерева в упорядоченном виде.
В NTFS используется понятие индекса, которое пришло из баз данных. Индекс - это коллекция элементов (атрибутов), хранящихся в отсортированном порядке. NTFS использует B+ деревья для организации индекса. Для таких деревьев в одном узле дерева может содержаться несколько значений. В NTFS эти значения называются индексными элементами. В качестве индексного элемента может выступать любой атрибут, по которому будет производиться индексация. Для индексов каталогов это всегда атрибут $FILE_NAME, для каждого файла/каталога, содержащегося в нем. Т. о. на каждый файл/каталог приходится как минимум две структуры FILE_NAME, первый как атрибут у файла, а второй, используемый для индекса. Узел дерева хранит последовательность атрибутов $FILE_NAME. Для хранения узлов дерева используются два типа атрибутов $INDEX_ROOT, который присутствует всегда для любой директории и $INDEX_ALLOCATION, который может и не присутствовать для небольших каталогов.
Индексы также используются для метафайла $Secure, который содержит дескрипторы защиты для файлов.
Рис. 4. Дерево каталога NTFS.
Индексный узел наделен заголовком INDEX_HEADER.
typedef struct _INDEX_HEADER //заголовок узла { /*0x00*/ ULONG entries_offset; //байтовое смещение первого индексного элемента, //относительно заголовка узла /*0x04*/ ULONG index_length; //размер узла в байтах /*0x08*/ ULONG allocated_size; //выделенный размер узла /*0x0C*/ ULONG flags; } INDEX_HEADER, *PINDEX_HEADER;
Индексные узлы хранятся в атрибутах $INDEX_ROOT и $INDEX_ALLOCATION.
Первый является резидентным и, следовательно, может хранить только один индексный узел, а второй является нерезидентным и хранить неограниченное число узлов.
Индексный элемент каталога наделен заголовком INDEX_ENTRY_HEADER_DIR.
typedef enum _INDEX_ENTRY_FLAGS { INDEX_ENTRY_NODE = 1, INDEX_ENTRY_END = 2 //последний элемент в узле } INDEX_ENTRY_FLAGS;
typedef struct _INDEX_ENTRY_HEADER_DIR //заголовок индексного элемента { /*0x00*/ MFT_REF indexed_file; //адрес MFT файла /*0x08*/ USHORT length; //смещение следующего элемента, относительно текущего /*0x0A*/ USHORT key_length; //длина атрибута $FILE_NAME /*0x0C*/ INDEX_ENTRY_FLAGS flags; //флаги /*0x10*/ FILE_NAME_ATTR file_name;//сам атрибут $FILE_NAME, если key_length //больше нуля. } INDEX_ENTRY_HEADER_DIR, *PINDEX_ENTRY_HEADER_DIR;
Теперь рассмотрим атрибут $INDEX_ROOT. В самом начале его тела располагается заголовок INDEX_ROOT.
typedef struct _INDEX_ROOT //заголовок $INDEX_ROOT { /*0x00*/ ATTR_TYPES type; //тип индексируемого атрибута /*0x04*/ ULONG collation_rule; //правило упорядочения в дереве /*0x08*/ ULONG index_block_size; //размер индексной записи в байтах /*0x0C*/ UCHAR clusters_per_index_block; //size of each index block (record) in clusters //либо логарифм размера /*0x0D*/ UCHAR reserved[3]; //unused /*0x10*/ INDEX_HEADER index; //заголовок индексного узла } INDEX_ROOT, *PINDEX_ROOT;
Наглядно, INDEX_ROOT представляется следующим образом.
Рис. 5. Тело атрибута $INDEX_ROOT.
Для перечисления всех индексных элементов в узле, необходимо вычислить адрес начального индексного элемента как сумму смещения заголовка INDEX_HEADER, и значения поля entries_offset заголовка узла, а затем перебрать все индексные элементы, пока в очередном элементе не будет встречен флаг INDEX_ENTRY_END. Для перехода от одного элемента к другому следует к адресу индексного элемента добавлять поле length.
Если индексные элементы не вмещаются в атрибуте $INDEX_ROOT, то для их хранения выделяется атрибут $INDEX_ALLOCATION, который по своему строению отличается от $INDEX_ROOT.
Тело атрибута $INDEX_ALLOCATION хранит индексные элементы в индексных записях, каждая из которых обладает заголовком. Индексная запись имеет статический размер и представляет один узел дерева. Ее размер указывается либо в поле index_block_size в INDEX_ROOT либо в поле загрузочного сектора, где может быть байтовый размер записи или двоичный логарифм размера.
Каждая индексная запись обладает заголовком INDEX_ALLOCATION.
typedef struct _INDEX_ALLOCATION //заголовок индексной записи { /*0x00*/ ULONG magic; //сигнатура "INDX" /*0x04*/ USHORT usa_ofs; /*0x06*/ USHORT usa_count; /*0x08*/ ULARGE_INTEGER lsn; /*0x10*/ ULARGE_INTEGER index_block_vcn; //VCN индексной записи /*0x18*/ INDEX_HEADER index; //заголовок узла } INDEX_ALLOCATION, *PINDEX_ALLOCATION;
Атрибут $INDEX_ALLOCATION представляет собой последовательность индексных записей, количество которых может быть вычислено делением размера атрибута на размер индексной записи (AttrRec->u.nr.data_size.QuadPart / IndexRootAttr->index_block_size). Зная количество индексных записей, мы можем их обойти как линейный массив элементов.
Индексные записи могут быть выделены для хранения узлов, а могут и нет. Для определения статуса выделения нужно при проходе учитывать атрибут $BITMAP, который хранит в своем теле последовательность бит, каждый из которых соответствует номеру индексной записи (начиная с нуля). Атрибут $BITMAP делится на байты и хранит состояние выделения индексных записей по следующей схеме: если старший бит байта N содержал состояние выделения индексной записи X, тогда младший бит следующего байта N+1 содержит состояние выделения записи X + 1. Рассмотрим пример. ff 5f 70 ff 05 11111111 01011111 01110000 11111111 00000101
Все индексные записи, начиная с нуля и заканчивая номером 12 выделены, т. к. первый байт содержит все единицы (анализ байтов происходит слева направо, а битов справа налево), следовательно, индексные записи с номерами 0-7 выделены. Переходим к следующему байту, видим, что первые пять бит равны единице, следовательно записи 8-12 выделены для использования.
Следующая запись, 13 не выделена.
Для определения байта, в котором хранится бит, характеризующий выделение, нужно индекс записи разделить нацело на восемь. Чтобы рассчитать позицию бита в байте, нужно взять остаток от этого деления.
Если PUCHAR StartBitmap – содержит адрес считанного в память битмапа, тогда X = StartBitmap[N / 8], f = (X >> (N % 8)) & 1,
переменная f будет содержать статус выделения индексной записи N.
Пусть для примера N = 20. Разделим целочисленно 20 на 8, 20/8 = 2. Получаем второй байт - 01110000. Возьмем остаток 20 % 8 = 4. Сдвигая байт на 4 и обнуляя все байты, кроме первого получаем 1. Следовательно, индексная запись N выделена.
Как показывает практика, свободная индексная запись будет содержать нормальный заголовок индекса, но в первом индексном элементе будет установлен флаг INDEX_ENTRY_END и поле key_length будет обнулено.
Рис. 6. Организация индексных записей в атрибуте INDEX_ALLOCATION.
Мы рассмотрели механизм, с помощью которого NTFS проходится по дереву каталогов, например, когда нужно открыть конкретный файл. В начале просматривается содержимое первого каталога как дерева и там ищется имя следующего каталога, затем для него выполняется та же операция, пока не будет найден искомый файл.
Индексные записи удобно просматривать с помощью той же DiskExplorer. Для этого нужно выбрать каталог и поставить внизу галочку на пункте Details. В таком случае для директории отобразятся все ее атрибуты. Чтобы просмотреть содержимое атрибута $INDEX_ALLOCATION в бинарном виде, нужно перейти по кластеру с которого начинаются его данные и нажать F3 для просмотра их в бинарном виде.
Рис. 7. Заголовок атрибута $INDEX_ALLOCATION, чтобы перейти к его содержимому, нужно кликнуть на подсвеченном стартовом кластере – x0131439F.
Рис. 8. Содержимое $INDEX_ALLOCATION в бинарном виде. Для перехода к просмотру в виде дерева – F5. Байт перед именем файла, есть тип имени, 3 – DOS и Win32 имя. Например, перед $AttrDef стоит тройка по смещению 0xA9, а по 0xAA уже первый буква имени файла.Также и для $BadClus, по смещению 0x111 стоит 3, т. е. DOS | Win32 имя.
Тема индексов очень хорошо рассмотрена у того же Кэрриэ в «Криминалистическом анализе».
