Data recovery concepts

Defining clusters chain for the deleted entry

To reconstruct a file from a set of clusters, we need to define a chain of clusters. Here are the steps:

1. Scan the drive, going through all file clusters (NTFS) or free clusters (FAT) that we presume belongs to the file.
2. Continue chaining the clusters until the size of the cumulative total of clusters approximately equals the total size of the deleted file. If the file is fragmented, the chain of clusters will be composed of several extents (NTFS), or select probable contiguous clusters and bypass occupied clusters that appear to have random data (FAT).

The location of these clusters can vary depending on file system. For example, a file deleted in a FAT volume has its first cluster in the Root entry; the other clusters can be found in File Allocation Table. On NTFS each file has _DATA_ attribute that describes "data runs". Disassembling data runs reveals extents. For each extent there is a start cluster offset and a number of clusters in extent. By enumerating the extents, the file's cluster chain can be assembled.

The clusters chain can be assembled manually, using low-level disk editors, however it is much simpler using a data recovery utility, like Active@ UNERASER.

Defining a Cluster Chain in FAT16

In the previous topic, we were examining a sample set of data with a deleted file named MyFile.txt. This example will continue with the same theme. The folder we scanned before contains a record for this file:

0003EE60   E5 4D 00 79 00 46 00 69  00 6C 00 0F 00 BA 65 00   aM.y.F.i.l...?e.
0003EE70   2E 00 74 00 78 00 74 00  00 00 00 00 FF FF FF FF   ..t.x.t.....yyyy
0003EE80   E5 59 46 49 4C 45 20 20  54 58 54 20 00 C3 D6 93   aYFILE  TXT .AO"
0003EE90   56 2B 56 2B 00 00 EE 93  56 2B 03 00  33 B7 01 00 V+V+..i"V+ ..3·..  

We can calculate size of the deleted file based on root entry structure. Last four bytes are 33 B7 01 00 and converting them to decimal value (changing bytes order), we get 112435 bytes. Previous 2 bytes (03 00) are the number of the first cluster of the deleted file. Repeating for them the conversion operation, we get number 03 - this is the start cluster of the file.

Here's what is in the File Allocation Table at this moment

Offset      0  1  2  3  4  5  6  7   8  9  A  B  C  D  E  F

00000200   F8 FF FF FF FF FF 00 00  00 00 00 00 00 00 08 00   oyyyyy..........
00000210   09 00 0A 00 0B 00 0C 00  0D 00 FF FF 00 00 00 00   ..........yy....
00000220   00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00   ................

Zeros! And it is good news in our case - it means that these clusters are not occupied, i.e. most likely our file has not been overwritten by another file's data. Now we have chain of clusters 03, 04, 05, 06 and we are ready to recover it.

Some explanations:

• We started looking from offset 6 because each cluster entry in FAT16 takes 2 bytes, our file starts from 3rd cluster, i.e. 3*2=6.
• We considered 4 clusters because cluster size on our drive is 32 Kb, our file size is 112, 435 bytes, i.e. 3clusters*32Kb = 96Kb plus a little bit more.
• We assumed that this file was not fragmented, i.e. all clusters were located consequently. We need 4 clusters; we found 4 free consecutive clusters so this assumption sounds reasonable, although in real life it might not be true.

In many cases data cannot be successfully recovered, because the cluster chain cannot be defined. This will occur when another file or folder is written on the same drive as the one where the deleted file is located. Warning messages about this fact will be displayed while recovering data using Active@ UNDELETE.

Defining a Cluster Chain in NTFS

When recovering on NTFS a part of the DATA attribute called Data Runs give us the location of file clusters. In most cases DATA attributes are stored inside the MFT record, so if we find the MFT record for the deleted file, most likely we'll be able to determine cluster's chain.

In example below DATA attribute is marked with a green color. Data Runs inside, marked as Bold.

Offset      0  1  2  3  4  5  6  7   8  9  A  B  C  D  E  F

00012580   2E 00 70 00 70 00 74 00  80 00 00 00 48 00 00 00   ..p.p.t.Ђ...H...
00012590   01 00 00 00 00 00 04 00  00 00 00 00 00 00 00 00   ................
000125A0   6D 00 00 00 00 00 00 00  40 00 00 00 00 00 00 00   m.......@.......
000125B0   00 DC 00 00 00 00 00 00  00 DC 00 00 00 00 00 00   .U.......U......
000125C0   00 DC 00 00 00 00 00 00  31 6E EB C4 04 00 00 00   .U......1neA....
000125D0   FF FF FF FF 82 79 47 11  00 00 00 00 00 00 00 00   yyyy‚yG.........

Decrypting Data Runs

Decrypting data runs can be accomplished using the following steps:

1. First byte (0x31) shows how many bytes are allocated for the length of the run (0x1 in the example case) and for the first cluster offset (0x3 in our case).
2. Take one byte (0x6E) that points to the length of the run.
3. Pick up 3 bytes pointing to the start cluster offset (0xEBC404).
4. Changing bytes order we get first cluster of the file 312555 (equals 0x04C4EB).
5. Starting from this cluster we need to pick up 110 clusters (equals 0x6E).
6. Next byte (0x00) tells us that no more data runs exist.
7. Our file is not fragmented, so we have the only one data run.
8. Lastly, check to see if there is enough information (size of the file). Cluster size is 512 bytes. There are 110 clusters, 110*512 = 56,320 bytes. Our file size was defined as 56,320 bytes, so we have enough information now to recover the file clusters.

Check to see if there is enough information about the file data?
Cluster size is 512 bytes.
We have 110 clusters, 110*512 = 56320 bytes
Our file size was defined as 56320 bytes, so we have enough information now to recover the file clusters.