Recursive FAT FS

Apr 7, 2022 |


The File Allocation Table (FAT) file system is a specific type of computer file system architecture. The FAT file system was originally designed in 1977 for floppy disks and has been adopted over the years because of its simple and robust properties. We have recently encountered a problem with a recursive FAT file system listing using The Sleuth Kits fls tool. When run with the -r (recursive) option, fls will create a top-level virtual directory called $OrphanFiles. These are files that at one time resided on the file system but have since been deleted. It is important to note that there may still be metadata on the drive from an orphan file that someone may find helpful, even if the original file itself does not exist. You can find more information from the TSK page here.

Solving the Problem

We face a problem when you run fls with the -r switch on the top level of a FAT file system. When fls reaches the virtual directory $OrphanFiles, it will begin a bin walk through the virtual memory space. This can take a long time, especially if the drive is large or slow.

 It is worth noting that the tool fatcat seems to work well with FAT file systems. While using fatcat, it read our test directories recursively and quickly without a binwalk. The only problem was that we wanted the inode for each file and directory.

 To solve this problem, we decided to write a script to automate multiple runs of fls and combine the results back into a full fls listing without running a recursive check against the $OrphanFiles. The process goes like this:

  1. Run fls without the recursive switch and save the results.
  2. Build a list of inodes and names for the resultant directories.
  3. Grab the inode and directory name as separate variables.
  4. Loop through the inode list for the directories and run fls with the recursive -r switch.
  5. Insert the parent directory name into the output.
  6. Combine the subdirectory output with the top-level output.


The test drive is a good ol' Memorex 16 Gb FAT32 drive, as noted in the photo below in the fsstat.


To show what's sitting at the drive's root level, we'll run fls without the -r. We can see below that the ‘*’ symbol annotates a few deleted files. As a quick refresh, the r/r means it's a regular file on the file system, the d/d means it's a directory, and the v/v indicates a virtual file/directory created by fls. The number to the left of the ‘:’ is the inode for any particular file.

 We can see that there are some .gx files from a slicer for a 3D printer and a directory called oscars at inode 124. Notice the $OrphanFiles line at the end of the listing.


When run recursively, fls will begin parsing into the $OrphanFiles directory and running a binwalk that can take a prohibitive amount of time—for example, in the image below.


To solve this, you first create a top-level listing without the recursive switch. I'm also going to remove the virtual files to prevent them from causing me a problem in the future.

fls /dev/sda1 -p | grep -iv v\/v > top_level_listing_file_and_dir

 Next, you create a list containing the inode and name of each (non-deleted) directory.

 cat top_level_listing_file_and_dir | grep -v \* | cut -f 1,2 | grep d\/d | cut -f 1,2,3 > top_level_dir_inode_list

The new list looks like this:


Finally, you are going to create a loop that:

  1. Creates a variable for the inode
  2. Creates a variable for the name of the directory
  3. Runs fls with the recursive -r option against that directory inode
  4. Pipe the fls output into awk and insert the name of the parent directory before saving it to a subdirectory list.
  5. Finally, combine the subdirectory list with the parent directory listing.

while read line; do

echo "line - $line"

FAT_DIR_INODE=$(echo $line | cut -d " " -f 2 | cut -d ":" -f 1)


FAT_DIR_NAME=$(echo $line | cut -d " " -f 3-100)


fls -r -p -l /dev/sda1 "$FAT_DIR_INODE" | awk -F '\t' -v TLDIR="$FAT_DIR_NAME" '{print $1"\t"TLDIR"/"$2"\t"$3"\t"$4"\t"$5"\t"$6"\t"$7"\t"$8"\t"$9"\t"$10"\t"$11}' > sub_directory_listings

done < top_level_dir_inode_list

cat sub_directory_listings >> top_level_listing_file_and_dir

With the awk scripting language, you need to insert the directory name in front of the second column. We used the field -F switch and \t to indicate, awk, to use tabbed columns and then used the variable -v switch to provide a variable name and the bash variable. To maintain a consistent output with fls, we used the "\t" to tell awk to output with tabs.

Now we can run this script on any FAT FS and get a recursive listing without waiting for the orphan file binwalk. Our final output now contains a full recursive listing.


The total line count from the script compared to the total line count from manually running fls comes out to be the same when subtracting the 4 virtual files that were removed from the listing.

The time to run this recursive script on this drive was 3.5 seconds compared to 16 minutes with the orphan file listing.

Below is an example of the orphan files that are presented if you do indeed decide to wait. We can see that this drive appears to have been used to boot or install kali.


And if we take a look at one of the orphan inodes using istat, we can see that there is metadata associated with it.



As you can see, there is certainly value in the orphan files, and it's not something to dismiss, but for this situation, we needed to grab a recursive deleted and over file listing as fast as possible. Using this script, we were able to grab what we needed in a fraction of the time it originally took.