Carving AVI files
Here I'm going to discuss the AVI file format and carving algorithms,
as implemented in Klennet Carver as of September 2021.
AVI File Format
The full specification of the format (from Microsoft) is available
here.
I will paraphrase the significant bits now:
- The file consists of chunks.
Each chunk starts with the four-byte signature,
followed by the four-byte data size field, then by the data itself.
- Chunks are aligned at the two-byte boundary.
If the data size is odd, there is a padding byte before the next chunk.
- The frames (data chunks) have a signature made from the frame type and the stream number,
NNxx, where xx identifies the frame type and NN identifies the stream.
For example, the first video stream will use 00dc as a signature for its frames.
- The overall structure of the file starts with headers,
followed by video and audio frames, followed by frame indexes.
Carving
Gathering data
The first step is to scan the entire media and identify all the AVI chunks by their signatures.
Headers and indexes are trivial to find.
Frames are a little bit difficult because only two bytes are available for the signature.
Additionally, while we can validate headers and indexes, there is no generalized validation technique for the frames.
Frames are, for all practical purposes, opaque.
As a result, there will be a non-trivial amount of false-positive frame detections.
There is a simple method of cleaning up false positives, though.
For each frame candidate, check if it is adjacent to another AVI chunk on either side.
If there is no chunk on either side, you are looking at a false positive.
While this method will remove a small number of actual frames, especially under extreme fragmentation,
it is still better than dealing with the typical false positives.
Reassembling the files
After the scan completes, we found three sets of objects:
- Headers
- Indexes
- Frames
The first step is to process the frames.
The frames on the media form relatively long sequences until there is damage or fragmentation.
At this point, the sequence breaks and continues somewhere else, with some frames possibly missing due to damage.
For each of these sequences, we construct a sequence of frame sizes corresponding to the frames on the media.
Because frame sizes are random (in fact, they are not, but they are random enough), the sequences of frame sizes are unique.
The second step is to process the indexes.
Indexes list the frames in order, providing size and offset in the file for each frame.
These we also convert to the sequences of frame sizes.
The problem then becomes a straightforward one of matching the sequences of frames on the media with the
sequences derived from indexes.
Some of the frame sequences will have the headers at the beginning, which are also collected.
The final step is to collect any remaining sequences of frames that cannot be associated with any indexes.
Remnants of old, partly overwritten, and damaged files typically fall into this category.
To produce usable files, we need to reconstruct the indexes and headers.
Indexes are easy to build, but headers need to be stolen from some previously reconstructed files.
There is some chance that headers will not match the frames, for example, if the frames and the header
source use different decoders.
These three steps cover most of the recovery process for the AVI files, as I use in Klennet Carver.
Filed under: File carving.
Created Friday, September 3, 2021