A Data Carving Algorithm for Digital Forensics

File carving is the recovery of data by searching raw content for file beginnings, endings, and format-specific structures without relying on file-system records. Even when a deleted file's directory entry, inode record, or cluster chain has been damaged, it may be possible to reconstruct the file if its content remains on the disk. NIST likewise classifies file carving as searching for and reconstructing files from content rather than file-system metadata.

I developed the core code I shared entirely myself. My objective was not merely to write a utility that searched for a few known file headers. I built an independent recovery layer that could use the same scanning engine on byte arrays, seekable streams, and raw disk images acquired with tools such as dd, while allowing me to add specialized signatures for new file types.

I used this core on real data in institutional and academic digital-forensics work. Custom-signature support was particularly effective in recovering many files that were no longer accessible through the file system. For institution-specific formats unknown to existing tools, or immutable byte sequences produced by a particular application, I could examine the actual format structure and define more selective start and end patterns.

From file recovery to file carving

Traditional deleted-file recovery usually proceeds through metadata left by the file system. If the filename, first cluster, length, or cluster chain remains intact, recovering the content is relatively straightforward. File carving is used when these records are absent, damaged, or not considered trustworthy.

The file-carving approach became widespread in the early 2000s through tools such as Foremost and later Scalpel. Foremost was developed to operate directly on drives or images created by dd, using beginning and ending values together with internal file structures. Pal and Memon's work on the development of file-carving techniques also classified the field as an area of research progressing from metadata-based recovery toward reconstruction based on content and file structure.

The fundamental operating space of the core I developed is likewise raw byte space. Input is treated not as a file-system object, but as an ordered byte sequence:

\[ D = \{d_0,d_1,\ldots,d_{N-1}\} \]

For the algorithm, whether this sequence comes from an in-memory byte array, a MemoryStream, a large file, or a bit-level copy of physical media does not change the fundamental logic. The input only provides a readable stream and position information.

A raw disk image is especially valuable for this use. NIST defines a disk image as a bit-level copy of the original medium, including unallocated and slack space. SWGDE likewise recommends that physical acquisition produce a bitstream copy, that the source medium not be written to, and that a write blocker be used where possible.

There is an important boundary here. The file-carving core is not an acquisition tool. It does not copy evidence, act as a write blocker, or establish chain of custody by itself. In proper use, the core is an analysis layer operating on a working copy of a verified raw image.

Customizable signature model

A substantial number of file formats begin with distinctive constants. JPEG start markers, the PNG signature, a PDF header, an ELF identifier, or a ZIP local-file record are examples. Some formats also have identifiable endings. JPEG terminators, the PNG IEND structure, and the PDF end marker can be used in this approach.

In the model I developed, each file type is conceptually represented by four pieces of information:

Field Function

Extension Type of the recovered file Start signature Byte sequence identifying a candidate file beginning End signature Optional pattern identifying the file end End offset Number of bytes to include after the end signature

The end offset is small but important. In some structures, the detected marker is not itself the final byte of the file. Fixed fields or structural information can follow it. Cutting only at the end of the signature can produce a file that appears to have been found but is structurally incomplete.

The source code contains signatures for different families including images, documents, archives, executables, audio, video, network packet captures, and virtual disks. The ability to define multiple start variants for the same extension is important for handling real-world encoder differences. JPEG is a clear example. Files share a common start marker, but subsequent application markers can differ.

Adding custom signatures became more valuable in institutional use than relying only on a predefined type list. When I identified a fixed structure occurring only in files produced by a particular application, I could define a longer pattern instead of using a very general and short signature. This reduced false positives while allowing me to recover content that general-purpose tools did not recognize.

PhotoRec also permits the definition of an extension, signature offset, and magic value for unknown formats. It specifically notes that more reliable recovery at developer level requires format-specific mechanisms such as content validation, length checks, and footer detection. The customization approach in my core rests on the same fundamental fact: a good signature is not merely a few arbitrary bytes, but structural knowledge of the file format.

Multi-pattern search engine

Scanning a large disk image from beginning to end separately for every signature is inefficient. For P different signatures and a source of N bytes, independent scans have approximate cost:

\[ O(PN) \]

In the core I developed, all start and end signatures are combined in a shared byte-trie structure. Signatures beginning with the same byte prefix share transitions. Definitions with similar starts, such as JPEG variants or ZIP-based formats, do not compare the same bytes repeatedly.

The structure resembles the shared-prefix idea of the Aho-Corasick algorithm, but it is not a complete Aho-Corasick automaton. Instead of constructing failure links, scanning begins at the trie root at every possible start position and stops at the first mismatch. With L denoting the longest signature, the theoretical upper bound is:

\[ O(NL) \]

When signatures are short and L is fixed, execution behaves linearly in practice:

\[ O(N) \]

This choice aims not at the theoretically optimal solution to the general text-search problem, but at a small and predictable hot path for binary signatures of bounded length. Transitions are stored in tables indexed directly by byte value, so each step requires neither a hash calculation nor a chain of character comparisons.

The automaton is prepared only on first use. Hexadecimal signatures are converted into byte arrays, processed by length, and merged into the shared transition table. The same structure can be reused in subsequent disk scans. In institutional work where many images are examined within the same application process, this startup cost becomes negligible.

Streaming design for large data

Loading an entire disk image into RAM is unnecessary and often impossible. The core therefore operates with large fixed-size blocks. The file is read into the main scanning buffer through smaller consecutive reads, and signature search is performed over that buffer.

The most important source of error in block-based scanning is boundary crossing. The first bytes of a signature can occur in one block and the remaining bytes in the next. If blocks are searched independently, the signature is missed.

I solved this by using overlap equal to the length of the longest signature. The final part of the previous block is copied to the beginning of the next. Every signature divided across two blocks is thereby present in full in at least one scan window.

When L is the longest signature and B is block length, the amount of data reexamined at each boundary is only on the order of L bytes:

\[ \text{additional scan ratio} \approx \frac{L}{B} \]

For large blocks, this ratio is negligible. It nevertheless guarantees that data is not lost at block boundaries.

The file stream is opened with a sequential-scan option. This tells the operating system that the read pattern moves forward. Large sequential reads rather than backward random access reduce seek cost on rotating disks and can also benefit from read-ahead behavior on SSD and network storage.

For a byte array, the same engine can operate over a memory stream. Using a general Stream prevents the core from being tied to a file system or a specific image format. As long as the source can be resolved into a seekable byte stream, the search logic remains unchanged.

Matching beginnings and endings

The scanning stage records every pattern found with its type identifier and absolute position. Matches are then ordered by position. When a start marker is encountered, a suitable end marker for the same file type is searched for in the forward direction.

The search is not unbounded. A configured maximum size prevents a start marker from being paired with an unrelated footer much later on the disk. The upper bound also reduces unnecessary searching in corrupted or incomplete files.

A file range is obtained as:

\[ R=[p_h,\ p_f+l_f+o_f) \]

Where:

p_h is the position of the start signature.

p_f is the position of the end signature.

l_f is the length of the end signature.

o_f is the format-specific end offset.

Instead of copying the entire resulting file into memory, it is represented by its start and end positions. This range in the source can be read through a bounded substream. Recovering a file of hundreds of megabytes therefore does not require another byte array of the same size.

This design separates recovery from export. Scanning first produces the source path, start position, end position, and type for each candidate. Only selected candidates can later be written into separate files, hashed, or sent to format validators.

Algorithmic cost

Let N be source length, L the longest signature, M the number of pattern matches, and K the number of candidate files produced.

The upper bound of trie-based scanning is:

\[ O(NL) \]

Because signature lengths are fixed and small, actual behavior is approximately O(N).

Sorting matches costs:

\[ O(M\log M) \]

Because scanning proceeds forward, records are produced in largely sorted order. Final sorting nevertheless gives deterministic output in the presence of block overlaps and multiple signatures at the same position.

The cost of matching starts and ends depends on data distribution. Each start performs a forward search within a configured distance. In real disks with low signature density, this stage remains limited. Cost can increase in maliciously constructed data or data containing the same pattern very frequently.

The main scanning buffer has fixed size. Pattern matches, however, remain in memory until examination completes, so auxiliary space is:

\[ O(M) \]

For very large images, the determining factor is signature-match density rather than image size itself. This approach is balanced for general datasets. In specialized environments that produce extremely many matches, memory use can be further bounded by ordered matching and incremental result output.

Validating the recovered file

Finding a header and footer does not prove that the byte sequence between them is certainly a valid file. The same pattern can occur in another file's body, compressed data, or arbitrary bytes. Signatures of embedded files can also appear inside an archive.

A carving result is therefore a candidate. Confidence should be increased in stages:

1. Start and end signature consistency

1. Plausible file length

1. Format-specific structural parsing

1. Validation of internal length, CRC, or checksum fields

1. Ability to open with a standard decoder

1. Recording of source position and hash value

Garfinkel proposed treating fast and accurate carving as a multilayer decision problem that validates or rejects candidate byte sequences early. Fast object validators for formats such as JPEG, OLE, and ZIP are an important part of this approach.

NIST likewise notes that deleted-file recovery results can contain irrelevant or additional content and that the examiner must understand the limitations of the tool used. The reason a standard terminology has been proposed for classifying and validating recovery results is to avoid conflating candidates, validated files, and erroneous recoveries.

In institutional use, I did not consider successful opening of the file sufficient. The source image, absolute byte range, file type, and hash value where necessary must be evaluated together. The evidential value of recovered content does not come merely from the algorithm finding the file, but from the reproducibility and auditability of the complete process.

Contiguous files and the fragmentation boundary

This core primarily recovers contiguously stored files. It assumes that the byte range between the beginning and ending markers belongs to the same file. If a file is fragmented, another file or unallocated region can occur between its fragments. A header-footer method can then join incorrect content or fail to locate the valid footer.

NIST emphasizes that carving is straightforward for files with easily identifiable start and end structures that are stored contiguously, while fragmentation makes the problem substantially harder. Academic work on fragmented files has developed more complex methods using format validation, cluster similarity, possible fragment ordering, and decoder feedback.

This limitation does not contradict the practical success of the algorithm. In real cases, many deleted files remain in contiguous clusters. Signature-based contiguous carving can be highly effective, particularly for small and medium-sized images, documents, archives, and application outputs.

Another factor increasing success is the use of custom signatures. In many institutional incidents, locating specific contiguous records produced by the system under examination with high selectivity can be more effective than attempting to reconstruct fragmented examples of a broad general file type.

The technical meaning of the experience

When developing this core, I did not treat file carving only as a list of file headers. The resulting structure combines several engineering decisions:

An input-source-independent stream model

Fixed-size block scanning for large files

Overlap preventing signature loss at block boundaries

A multi-pattern automaton merging shared prefixes

Detection of beginning and ending markers in one scan

Format-specific footer offsets

A search bound preventing unbounded false matching

A substream exposing the recovered range without copying it

Signature definitions extensible to new and institution-specific formats

My ability to recover many files in institutional and academic digital-forensics work did not result from a short list of magic values alone. Successful results required understanding the file format of the examined system, selecting the correct signature, avoiding unnecessarily short patterns, and validating the resulting candidates structurally.

The core I developed is not a general-purpose file-system recovery package or an intelligent carver that automatically joins fragmented files. Its more accurate technical position is a high-capacity, stream-based carving engine focused on contiguous-file recovery with customizable signatures.

Defining these boundaries clearly is important in digital forensics. What a tool does not do must be known as well as what it does successfully. The effective results in my own work were based on the same approach: file-system-independent search, institution-specific format knowledge, controlled range extraction, and a separate validation stage for the result.