Index Attributes and Data Structures

The previous sections covered the attributes and concepts that apply to all files. This section focuses on the data structures and attributes that are specific to indexes. Recall that the basic concept behind indexes is that there is a data structure that is in a sorted tree. The tree has one or more nodes, and each node has one or more index entries. The root of the tree is located in the $INDEX_ROOT attribute, and the other nodes are located in index records in the $INDEX_ALLOCATION attribute. The $BITMAP attribute is used to manage the allocation status of the index records.

In this section, we start on the outside and work in. We will start with the attributes and then describe the data structures that are common to both of them.

$INDEX_ROOT Attribute

The $INDEX_ROOT attribute is always resident and has a type identifier of 144. It is always the root of the index tree and can store only a small list of index entries. The $INDEX_ROOT attribute has a 16-byte header, which is followed by the node header and a list of index entries. This can be seen in Figure 13.5. The node header will be described in the "Index Node Header Data Structure" section and the index entries will be described in the "Generic Index Entry Data Structure" section. Here we will focus on the $INDEX_ROOT header.

Figure 13.5. The internal layout of an $INDEX_ROOT attribute with its header, a node header, and index entries.

The $INDEX_ROOT header has the values given in Table 13.12 and starts at byte 0 of the attribute content.

This data structure identifies the type of attribute that the index entries will contain, how they are sorted, and the size of each index record in the $INDEX_ALLOCATION attribute. The value in bytes 8 to 11 are the size in bytes, and the value in byte 12 is either the number of clusters or the logarithm of the size. The "$Boot File" section describes this encoding method in more detail. Note that the size of the index record was also given in the boot sector.

To look at the contents of an $INDEX_ROOT attribute, we use icat and supply the 144 type:

# icat -f ntfs ntfs1.dd 7774-144 | xxd 0000000: 3000 0000 0100 0000 0010 0000 0400 0000 0............... 0000016: 1000 0000 a000 0000 a000 0000 0100 0000 ................ [REMOVED]

Bytes 0 to 3 show that the attribute in the index is for the attribute type 48 (0x30), which is the $FILE_NAME attribute, and bytes 8 to 11 show that each index record will be 4,096 bytes.

$INDEX_ALLOCATION Attribute

Large directories cannot fit all their index entries into the resident $INDEX_ROOT attribute, so they need a non-resident $INDEX_ALLOCATION attribute. The $INDEX_ALLOCATION attribute is filled with index records. An index record has a static size and contains one node in the sorted tree. The index record size is defined in the $INDEX_ROOT attribute header and in the boot sector, but the typical size is 4,096 bytes. The $INDEX_ALLOCATION attribute has type identifier of 160 and should not exist without an $INDEX_ROOT attribute.

Each index record starts with a special header data structure, which is followed by a node header and a list of index entries. The node header and index entries are the same data structures that are used in the $INDEX_ROOT attribute. The first index record starts at byte 0 of the attribute. We can see this in Figure 13.6, which has two index records in the $INDEX_ALLOCATION attribute.

Figure 13.6. The internal layout of an $INDEX_ALLOCATION attribute with its record headers, node headers, and index entries.

The index record header has the values given in Table 13.13.

The first four fields are almost identical to the fields for an MFT entry, but the signature is different. Refer to the beginning of this chapter for the discussion of fixup arrays.

The VCN value in bytes 16 to 23 identifies where this record fits into the tree. The $INDEX_ALLOCATION attribute is filled with index records, which could be out of order. The VCN value in the header identifies where this index record fits into the larger buffer. When an index entry points to its child node, it uses the VCN address in the node's index record header.

Let's look at the contents of the $INDEX_ALLOCATION attribute from the same directory whose $INDEX_ROOT attribute was examined:

# icat f ntfs ntfs1.dd 7774-160 | xxd 0000000: 494e 4458 2800 0900 4760 2103 0000 0000 INDX(...G`!..... 0000016: 0000 0000 0000 0000 2800 0000 f808 0000 ........(....... [REMOVED]

We can see the signature value "INDX" in the first line, and bytes 4 to 5 and 6 to 7 show the fixup record values. Bytes 16 to 23 show that this index record is VCN 0 buffer. The node header starts at byte 24. The $INDEX_ALLOCATION attribute is 8,192 bytes in size, so there is room for another index record. It starts at byte 4,096:

[REMOVED] 0004096: 494e 4458 2800 0900 ed5d 2103 0000 0000 INDX(....]!..... 0004112: 0400 0000 0000 0000 2800 0000 6807 0000 ........(...h... 0004128: e80f 0000 0000 0000 3b00 0500 6900 c401 ........;...i... [REMOVED]

We see the "INDX" signature and bytes 4,112 to 4,119 show us that this is VCN 4 (each cluster in this file system is 1,024 bytes). We will return to this example after discussing the node header and index entries.

$BITMAP Attribute

In the previous section, we saw an $INDEX_ALLOCATION attribute with two 4,096-byte index records. It is possible for some of the index records to not be in use. The $BITMAP attribute is used to keep track of which index records in the $INDEX_ALLOCATION attribute are allocated to an index record. Typically, Windows allocates index records only when needed, but a directory may have unneeded records after deleting many files or because each cluster is larger than one index record. Note that this attribute was also used by $MFT to keep track of which MFT entries were allocated.

The $BITMAP attribute has a type identifier of 176 and is organized by bytes, and each bit corresponds to an index record. We can view the $BITMAP attribute for the previous directory by using icat:

# icat -f ntfs ntfs1.dd 7774-176 | xxd 0000000: 0300 0000 0000 0000 ........

We can see the value 0x03 in byte 0, which is 0000 0011 in binary. Therefore, index records 0 and 1 are allocated.

Index Node Header Data Structure

So far, we have seen the $INDEX_ROOT and $INDEX_ALLOCATION attributes, and they both have some header data that is followed by the node header and a list of index entries. In this section, we describe the node header data structure. This header occurs in the $INDEX_ROOT and in each index record data structure and is used to show where the list of index entries starts and ends. The header has the fields given in Table 13.14.

The index entries for an $INDEX_ROOT node will start immediately after the node header, but the index entries in an index buffer may not because of the fixup values. When we are looking for remnant data from deleted index entries, we will examine the data in between the end of the used portion of the buffer and the end of the allocated buffer.

The flags field has only one flag, and the 0x01 flag is set when there are children nodes that are pointed to by the entries in this list. This same flag exists in each index entry.

Let us look at the previous attributes that were dissected. The $INDEX_ROOT attribute had the following data:

# icat -f ntfs ntfs1.dd 7774-144 | xxd 0000000: 3000 0000 0100 0000 0010 0000 0400 0000 0............... 0000016: 1000 0000 a000 0000 a000 0000 0100 0000 ................ [REMOVED]

The node header starts at byte 16, and bytes 16 to 19 show that the list starts 16 bytes (0x10) away, which is byte 32, and ends 160 bytes (0xa0) away, which is byte 176. In this case, the allocated space and used space are the same because they are from an $INDEX_ROOT attribute, which is resident and must be as small as possible. Byte 28 has the 0x01 flag set, so there are children nodes to this node (which are located in $INDEX_ALLOCATION).

Now let us look at the $INDEX_ALLOCATION attribute again:

# icat f ntfs ntfs1.dd 7774-160 | xxd 0000000: 494e 4458 2800 0900 4760 2103 0000 0000 INDX(...G`!..... 0000016: 0000 0000 0000 0000 2800 0000 f808 0000 ........(....... 0000032: e80f 0000 0000 0000 2100 0000 0600 0000 ........!....... [REMOVED]

The first 24 bytes are for the index record header, and the node header starts after that. Bytes 24 to 27 show that the index entry list starts at byte offset 40 (0x28). Note that this is relative to the start of the node header, so we need to add 24 to it, which gives us 64. This is a case where the index entry list does not immediately follow the index entry list header because the fixup record array is in between the index entry list header and the actual list. Recall that bytes 4 to 5 of the index record header show that the fixup array is located at offset 40 (0x28).

Bytes 28 to 31 show that the offset to the end of the last list entry is 2,296 bytes (0x08f8), and bytes 32 to 35 show that the offset to the end of the allocated list buffer is 4,072 bytes (0x0fe8). Therefore, there are 1,776 bytes of unused space in the buffer that may contain data from files with names stored in those node entries. Bytes 36 to 39 show that the flag value is 0, so there are no children nodes to this node.

Generic Index Entry Data Structure

So far, we have discussed the general concepts of NTFS indexes, and the only thing missing is the discussion of index entries. From this point on, the data structures will be specific to the type of index, but there is a general structure to all index entry data structures, which I will describe in this section.

The standard fields for an index entry are given in Table 13.15.

The first eight bytes are used to store data that is specific to the index entry. Bytes 8 to 9 define how big the index entry is, and 10 to 11 give the length of the index entry content, which starts in byte 16. The content can be any data. The flags field has the values given in Table 13.16.

When an index entry has a child node, the 0x01 flag will be set, and the VCN address of the child node will be found in the last eight bytes of the index entry. Recall that each index record has a VCN. The 0x02 flag is set when this is the final entry in the list.

Directory Index Entry Data Structure

A directory index, which is used for file names, has a specific index entry data structure. It uses the basic template, as outlined in the previous section, and includes a file reference address and a $FILE_NAME attribute. Each index entry has the fields given in Table 13.17.

The file reference value points to the MFT entry to which this index entry corresponds. The two flag values apply to this entry, which is 0x01 if there is a child node and 0x02 if this is the last entry in the list.

Now let us look at the rest of the $INDEX_ROOT and $INDEX_ALLOCATION attributes that we have already partially dissected. The contents of the $INDEX_ROOT attribute are shown here:

# icat -f ntfs ntfs1.dd 7774-144 | xxd 0000000: 3000 0000 0100 0000 0010 0000 0400 0000 0............... 0000016: 1000 0000 a000 0000 a000 0000 0100 0000 ................ 0000032: c51e 0000 0000 0500 7800 5a00 0100 0000 ........x.Z..... 0000048: 5e1e 0000 0000 0300 e03d ca37 5029 c401 ^........=.7P).. 0000064: 004c c506 0202 c401 e09a 2a36 5029 c401 .L........*6P).. 0000080: d0e4 22b5 096a c401 0004 0000 0000 0000 .."..j.......... 0000096: 7003 0000 0000 0000 2120 0000 0000 0000 p.......! ...... 0000112: 0c02 4d00 4100 5300 5400 4500 5200 7e00 ..M.A.S.T.E.R.~. 0000128: 3100 2e00 5400 5800 5400 0000 0000 0300 1...T.X.T....... 0000144: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 0000160: 1800 0000 0300 0000 0400 0000 0000 0000 ................ [REMOVED]

We already processed the first 32 bytes because the first 16 bytes were the $INDEX_ROOT header, and the second 16 bytes were the node header. Bytes 32 to 37 show that this entry is for MFT entry 7,877 (0x1ec5). Bytes 40 to 45 show that the size of the index entry is 120 bytes (0x78), so it will end in byte 152 in our output. Bytes 26 to 27 show that the size of the attribute is 90 bytes (0x5a). The flag at byte 28 shows that there is a child node whose address will be given in the final eight bytes of the entry, which we expected because the flag in the node header showed that there was a child.

The $FILE_NAME attribute is located in bytes 48 to 137 and bytes 144 to 151 are the final bytes in the index entry and contain the VCN of the child node, which is cluster 0. We can see the name "MASTER~1.TXT" as the name of the file. Bytes 152 to 175 contain an empty index entry and the flag at byte 164 is 3, which shows that it is the end of the list and that it contains a child. Bytes 168 to 175 contain the address of the child node, which is VCN 4. These are the two index records we saw in the $INDEX_ALLOCATION attribute. Figure 13.7 shows the graphical layout of this attribute.

Figure 13.7. Layout of the $INDEX_ROOT attribute in our example directory.

The same process can be repeated for each of the index records in the $INDEX_ALLOCATION attribute. Instead, we will look at some interesting data that occurs well after the node header. We previously saw that the index entries in index record 0 ended at offset 2,296, but that there were another 1,776 bytes allocated to the node. Therefore, there could be deleted file name information. We can seek through the unused area and look for valid index entries. Byte offset 2,400 has the following:

0002400: be1e 0000 0000 0600 6800 5400 0000 0000 ........h.T..... 0002416: 5e1e 0000 0000 0300 908b bf37 5029 c401 ^..........7P).. 0002432: 004c c506 0202 c401 e09a 2a36 5029 c401 .L........*6P).. 0002448: 30a7 6410 9c4a c401 003c 0000 0000 0000 0.d..J...<...... 0002464: 003a 0000 0000 0000 2120 0000 0000 0000 .:......! ...... 0002480: 0903 7000 7300 6100 7000 6900 2e00 6400 ..p.s.a.p.i...d. 0002496: 6c00 6c00 6500 0000 2513 0000 0000 0b00 l.l.e...%.......

This is an index entry for the file in MFT entry 7,870 (0x1ebe), and the name of the file is psapi.dll. Due to the nature of how indexes are re-sorted, we cannot tell if this file was deleted or if was moved to a different entry location because another file was added or deleted. We can tell only after looking at all the other index entries. TSK displays all entries and leaves it up to the user to identify why it is unallocated. Autopsy will filter the TSK output, though, and show only unique names.

Figure 13.8 shows the relationship between the index entries in $INDEX_ROOT and the index records in $INDEX_ALLOCATION. We can see that the root node of the index had two entries. Any file with a name less than MASTER~1.TXT could be found in the index record at VCN 0, and any with a name greater than it could be found in the index record at VCN 4. The index record at VCN 0 had unallocated space at the end of it, and we were able to find the data for the file psapi.dll. Notice that this name is greater than MASTER~1.TXT, so when it was saved to this node, there was likely a different entry in the root node.

Figure 13.8. Layout of the index entries in the dissection examples.