A file system is used to index and organize files on the disk. Records in the file system point to exact location(s) on the disk containing information that belongs to a certain file. Different file systems organize files differently. This article discusses the recovery of FAT (File Allocation Table) file systems, which includes the original FAT, FAT16 and FAT32.
File System Analysis
A modern data recovery tool applies several different methods in order to determine the exact location of a deleted (or missing) file. It will attempt to analyze the file system first, if available, as a record in the file allocation table contains the most comprehensive information about the location of the file, its name and attributes. If any part of the file system is still available, the tool will be able to enumerate records in the file system, determine the record belonging to a particular file, and find out about which sectors on the disk belong to the file, and in what order. This may be essential for the correct recovery of a file, as the file may be stored on the disk in the form of several segments (fragments) instead of a single continuous record due to disk fragmentation.
Fragmented files are extremely difficult (and not always possible) to recover without a valid file system reference.
Locating Files in the File Allocation Table (FAT)
In the FAT file system, all files are assigned an individual record. These records contain information about the file, including all data clusters occupied by the file. FAT structures are used to identify subsequent clusters in the files, as well as to determine the current state of the clusters (e.g. they may be available if the file is deleted, still belong to the file, or already taken by a different file).
As you can see, fragmented files will occupy more than one cluster, and will therefore have an interlinked chain of FAT structures recorded in the file system. Locating the very first record and following (enumerating) the links is essential when locating all the records.
File system analysis is all that happens if the recovery tool is operating in its Quick Scan mode. But what if the file system is empty (e.g. after a disk format operation), damaged, or completely missing? In that case, a comprehensive analysis of the entire disk surface must be performed, engaging a signature-search method of locating certain types of files.
Extended Analysis and Signature Search
Signature search allows data recovery tools to successfully identify, locate and recover files that are not indexed in the file system. Signature search can detect files having persistent signatures (e.g. “JFIF” in JPEG files) or containing a limited character sub-set (e.g. text files). Sometimes, files with certain cyclic or recurrent structures can be detected and recovered. By detecting the presence of a file and analyzing its header, a signature-search algorithm can calculate clusters occupied by that file on the disk, and successfully recover the file. More details about signature search will be published in a follow-up article.