Recovering Deleted JPEGs from a FAT File System - Part 9

Part 9 in a series of posts on recovering deleted JPEG files from a FAT file system.

A month ago (!), in part 8, we looked at the JPEG file format specification to determine if there was sufficient determinism in the on-disk layout to allow the recovery of deleted files through analyzing the residual data in the file system. The answer was mixed:

1. GOOD: Uniquely valued markers, discoverable through data inspection, identify the beginning and type of the segments that constitute a JPEG file.
2. GOOD: the metadata segments have a pre-defined size
3. BAD: the length of the entropy encoded image data is, to the best of my knowledge, unspecified in the START-OF-SCAN segment header. Instead, an END-OF-IMAGE marker is used to identify the end of the entropy encoded data. The theory is that this is done to allow JPEG files to be written as the image is processed.

Essentially, this means that there is no way to determine through data inspection the length or location of the clusters containing the encoded image data. The only clue available is the END-OF-IMAGE marker at the end of the entropy encoded data.

One option is to discover and analyze latent directory entries in the data area - doing so could provide valuable clues to the start and length of erased JPEG files. The downsides to this approach are added complexity (recovering deleted directory entries) and incompleteness (directory entries for deleted JPEG files may not exist due to reuse).

A simpler approach is to inspect each cluster in the data area to see if it begins with a START-OF-IMAGE marker or contains an END-OF-IMAGE marker. Any extent of clusters bounded by START-OF-IMAGE and END-OF-IMAGE markers stands a good chance of being the data for a contiguous JPEG file - the very kind of file we've been trying to recover in this series. In this post, I'll implement this simple method and test the results. Follow the "Read more" think for the rest of the post.

Recovering Deleted JPEGs from a FAT File System - Part 8

Part 8 in a series of posts on recovering deleted JPEG files from a FAT file system.

In part 7, I demonstrated recovering deleted JPEG files through knowing their pre-deletion location in a FAT file system. In the real use-case of recovering accidentally deleted files, the locations are unknown making this approach impossible.

Recovering deleted files without knowing their location requires a method to find them within the unerased data. In this post, I'll show how the structure of a JPEG file can be used to do just that. Follow the read more link for the full discussion.

Recovering Deleted JPEGs from a FAT File System - Part 7

Part 7 in a series of posts on recovering deleted JPEG files from a FAT file system.

After a hiatus due to the holidays, personal matters, and work-stuff I'm ready to continue the FAT Recover project. In this post I'll

• finally demonstrate the two principal assumptions that this project is based on.
• actually recover deleted files using a manual approach.

Follow the "read more" link for the detailed discussion.

But first a mea culpa - I've discovered that the code for long file name support in post 5 is utterly broken. The code works for files that only use a single long file name entry but does not correctly process file names spanning multiple entries. For now, I'll side-step the issue and post a fix at a later time. I'll also update post 5 to warn future readers. Apologies for the error - that's the danger of hacking in the wee hours and minimal unit testing.

Recovering Deleted JPEGs from a FAT File System - Part 6

Part 6 in a series of posts on recovering deleted JPEG files from a FAT file system.

In this post we'll tackle the last major FAT file system data structure - the file allocation table. Compared to the previous post on the root directory, this post is much less complex. Follow the "read more" link for an overview of the file allocation table and the code required to process it.

Recovering Deleted JPEGs from a FAT File System - Part 5

Part 5 in a series of posts on recovering deleted JPEG files from a FAT file system.

UPDATE: 2010/1/28: it's come to my attention that the long file name support code described in this post is broken - it only works for files that utilize a single LFN entry. For the time being I plan to work around this bug for the FATRecover series but I do intend to post a fix eventually. I'll be sure to add another update with a link to the fix when it is available.

The topic of this installment is the root directory and the code required to process it. Although strictly speaking the file allocation table is the next major on-disk area, I think covering the root directory first will make the overall discussion clearer.

Note that this is a watershed post as the "hack" level of the example code increases dramatically. This was unfortunate but necessary to accommodate certain FAT functionality while limiting the discussion's length. That said, readers with sufficient skill should be able to use the example code to create more robust implementations.

Follow the "read more" link for a detailed description of how to read and interpret the root directory.

Recovering Deleted JPEGs from a FAT File System - Part 4

Part 4 in a series of posts on recovering deleted JPEG files from a FAT file system.

Now that we've created a test data set and covered the high-level structure of a FAT file system, it's time to get our hands dirty with some code. Enough talk, more action!!!

Follow the "read more" link for a detailed description of how to read and interpret a FAT file system boot sector.

Recovering Deleted JPEGs from a FAT File System - Part 3

Part 3 in a series of posts on recovering deleted JPEG files from a FAT file system.

The FAT file system was invented in 1980 by Tim Paterson while developing 86-DOS, the precursor of MS-DOS. Since its creation, FAT has gone through a number of evolutions to accommodate growing disk sizes, and provide more capabilities. Although FAT is nearly 30 years old, it remains in common use due to its ubiquitous OS support and simplicity - both important factors for embedded consumer devices like digital cameras.

FAT's history is complex, a retelling could consume an entire series of posts itself. For this project, it is sufficient to know that there are three main variants - FAT12, FAT16, and FAT32 - each successively supporting larger maximum disk sizes. Generally speaking, the on-disk format of all three variants is very similar, so much so that code developed to grok one format can, with reasonable effort, be hacked to grok another¹. In this project, we'll be working with a FAT16 file system which hdiutil can be explicitly requested to create by using the argument -fs "MS-DOS FAT16"².

The following diagram depicts the high-level, on-disk structure of a FAT16 file system (not drawn to scale).

+---------+-------+--------+-------+---------------------+
|   BOOT  | RESV  |   FAT  | ROOT  |  DATA ............. |
|  SECTOR | (OPT) |        | DIR   |  AREA ............. |
+---------+-------+--------+-------+---------------------+
0                                                        N

In computer storage, capacity is divided into fixed sized units called sectors - typically 512 bytes long³. The sector is the fundamental unit for addressing storage and smallest amount of data that can be transferred to/from a disk drive. While older disk drives used an awkward addressing scheme based on physical geometry, newer drives use a linear series of sector addresses.

The first sector (offset 0) of a FAT16 file system contains the BOOT SECTOR which provides critical information about the file system's organization. Optionally, a number of sectors may be reserved after the boot sector (RESV).

The next major data structure is the File Allocation Table (FAT) from which the file system gets its name. The FAT is essentially an array of 16bit elements ⁴ each representing a fixed size portion of the DATA AREA. To minimize the FAT's relative size, each element represents a cluster⁵, a power-of-two multiple number of sectors. In addition to tracking the allocation status of each DATA AREA cluster, FAT elements are also used to store pointers forming linked-lists describing the on-disk location of files and sub-directories spanning multiple clusters.

After the FAT comes the root directory area (ROOT DIR) used to hold the information describing the files and sub-directories at the top of the file system namespace tree. In FAT12 and FAT16, the root directory area is a fixed size which limits the numbers of files and sub-directories that can be stored in it.

The remainder of the disk capacity (DATA AREA) is essentially a heap allocated as needed to store file and sub-directory data. As mentioned previously, use of the DATA AREA is managed by the FAT.

In the next few posts, I'll describe each of these major areas in greater detail and present the code needed to interpret them. By the end, we should essentially have a read-only FAT file system implementation that will serve as the basis for the remainder of the project.

Footnotes:

¹ Here I am ignoring many, many subtle differences and complications. A thorough discussion of the technical details for all of FAT's variants is outside the scope of this series. The curious reader is recommended to read the bountiful information available via a Google search. Brian Carrier's book, File System Forensic Analysis, is another valuable resource (which sadly wasn't available when I first did this project in 2004).

² Note that FAT16 file systems have a minimum supported size - usually 16MB but some tools may allow smaller sizes.

³ Some enterprise level disk drives use a 520 byte sector - the additional 8 bytes are often used to store error checking and recovery information for RAID systems.

⁴ The size of the FAT elements is one of the principal differences between the file system variants. FAT12 uses 12bit entries while FAT32 uses 32bit entries. The FAT element size is one of the factors that determines each variant's maximum supported disk size.

⁵ Other file systems may use the term block instead of cluster.

Recovering Deleted JPEGs from a FAT File System - Part 2

Part 2 in a series of posts on recovering deleted JPEG files from a FAT file system.

Whenever I develop an analysis program I first create a dataset to test and experiment against. In part 1, I mentioned that I used my digital camera to create a test data set for the original project in 2004. For this series of posts, I thought it would be better to use a data set reproducible by others. Two things are required to accomplish this goal:

• A collection of commonly available test images
• A repeatable method for creating disk images of FAT file systems

A Google search for test images led me to this wikipedia page from which I selected the University of Southern California Signal & Image Processing Institute's data set - specifically the miscellaneous corpus. This collection consists of 44 TIFF images of various resolutions ranging in size from 64KB to 1MB (17MB in total). Since JPEG images are needed for this project, I used the following ImageMagick command to do the conversion.

mogrify -format jpg -quality 90 *.tiff

After the conversion, the file sizes ranged from 4.8KB to 350KB (3.4MB in total) - a conveniently sized collection for this project.

In the 2004 project, I used the UNIX dd command to make a disk image of my camera's memory card. However for this project, I wanted a way to create disk images without requiring a physical device. One option considered was to use Linux loop devices but I wanted to use my machine-of-choice, an Apple MacBookPro, for this project - an artificial but important constraint since this is for fun.

After some research, I discovered that Apple's hdiutil utility can create a suitable image using the following command:

hdiutil create \
        -fs "MS-DOS" \
        -megabytes <SIZE> \
        -layout NONE \
        -volname <VOLNAME> <IMAGENAME>

Executing this command creates the file <IMAGENAME>.dmg that is an image of a FAT file system called <VOLNAME> with a total capacity of <SIZE> megabytes. The remaining argument, -layout NONE, prevents a partition table from being added to the image - an unnecessary complication for this project.

The following example illustrates the OS X terminal commands needed to create a 16MB disk image with a single JPEG file on it¹

$ hdiutil create \
          -fs "MS-DOS" \
          -megabytes 16 \
          -layout NONE \
          -volname FRTEST1 frtest1
..................................................
created: /<PATH>/frtest1.dmg

$ hdiutil attach frtest1.dmg 
/dev/disk1             /Volumes/FRTEST1

$ cp images/4.2.04.jpg //Volumes/FRTEST1//

$ hdiutil detach //Volumes/FRTEST1//

Using the selected image corpus and above hdituil terminal commands, a wide variety of test disk images can be created programmatically via shell scripts - just what is needed for this project.

In the next post, we'll start down the path of grokking a FAT file system layout.

Footnotes:

¹ Minor changes were made to the example output to remove machine specific information (i.e. paths) and fit it within the limited size of the post area.

Recovering Deleted JPEGs from a FAT File System - Part 1

Part 1 in a series of posts on recovering deleted JPEG files from a FAT file system.

In 2004, my in-laws returned from a vacation and had all of the pictures accidentally deleted from their digital camera. When I heard the news my first thought was that the data may still be there!

Often, deleting a file only erases its associated file system metadata (i.e. name, owner, etc) - the file's data is left unchanged. As a result, a deleted file can sometimes be recovered by finding the unchanged data fragments and recombining them in the correct order. I reasoned that if their camera took this metadata-only approach then there was a good chance that some of the pictures could be recovered.

Unfortunately, my in-laws lived in another state so I couldn't examine their camera's memory card right away. I suggested that they remove the card from the camera and bring it with them on their next visit so that I could analyze it then.

My initial plan was to try one of the many file recovery tools that already existed. However, I soon began to wonder how hard it would be to write a program to recover the pictures myself. Finding the challenge exciting, I immediately began spending all of my spare time coding up a recovery program.

After one week, and a lot of caffeine, I had a C program capable of recovering deleted JPEG files from a FAT file system - the typical file system used by digital cameras. Using my own camera as a test bed, the program could reliably recover pictures after performing an "erase all" operation. Cool!

Unfortunately, the story didn't end as well for my in-laws. When I finally received their memory card I found that all of the file system data blocks had the value 0xFF - a clear sign that the entire FLASH memory had been erased¹. The data was gone.

Despite the unfortunate ending, this project was one of my favorite spare-time hacks. So much so in fact that I thought it would be fun to recreate it as a series of blog posts. Over the next few weeks I plan to write a series of posts under the label "FATrecover" describing how to develop such a program. By the end of the series, hopefully anyone with sufficient coding experience will be able to write their own FAT file system recovery program.

Footnotes:

¹ FLASH memory, being a form of EEPROM, cannot be re-written directly. Instead, the FLASH memory cells must first be returned to an unwritten state - an operation typically called an "erase". After being erased, the affected memory cells have a value of 0xFF.