# A Data Carving Algorithm for Digital Forensics

> File carving recovers candidate files without filesystem metadata by combining signatures with structural validation; header matching alone produces weak boundaries and false positives.

- Author: Muhammet Ali Köker
- Language: en
- Canonical: https://alikoker.com.tr/en/data-carving-algorithm-for-digital-forensics
- Translation: https://alikoker.com.tr/adli-bilisimde-veri-kazima-algoritmasi
- Published: 2021-04-15T12:00:00+03:00
- Modified: 2026-09-01T10:55:42+03:00
- Verified: 2026-08-27T10:36:29+03:00
- Type: article

## File Carving Is More Than Signature Scanning

Finding a file header only identifies a candidate start offset. The harder forensic problem is determining where the object ends, whether its internal structure is coherent, and whether the byte sequence is genuinely an instance of the target format. A `magic byte` search alone can generate many false positives on large raw images.

A stronger workflow locates the signature, evaluates format-specific length or terminator information, parses internal structure when possible, and records the recovered object together with its source offset and context. Fragmented files require additional caution because contiguous-sector assumptions may fail. Data recovered from [unallocated space](/en/wiki/unallocated-space) has less filesystem context than an allocated file record, so the recovered artefact and the evidential claim should remain distinct.

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 this core independently. 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 specialised signatures to be added for new file types.

In real data sets, custom signatures are particularly useful for organisation-specific formats and formats not recognised by general-purpose tools. Selective start and end patterns derived from the actual format structure produce fewer false candidates than short generic magic-value searches.

## 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:

```text
D = {d_0,d_1...,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:

- `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:

```text
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:

```text
O(NL)
```

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

```text
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 ≈ (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:

```text
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:

```text
O(NL)
```

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

Sorting matches costs:

```text
O(Mlog 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:

```text
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

2. Plausible file length

3. Format-specific structural parsing

4. Validation of internal length, [CRC](/en/wiki/crc), or checksum fields

5. Ability to open with a standard decoder

6. 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

Successful data carving does not result from a short list of magic values alone. It requires understanding the file format of the examined system, selecting a discriminative signature, avoiding unnecessarily short patterns and validating 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. A robust carving workflow combines file-system-independent search, format-specific knowledge, controlled range extraction and a separate validation stage.

## Open-Source Implementation

I published the implementation of the signature scanning and carving flow so the algorithm can also be followed directly in code:

**Source code:** [forensic-file-carver-csharp](https://github.com/alikoker/forensic-file-carver-csharp)

## Software Record

**GitHub:** [forensic-file-carver-csharp](https://github.com/alikoker/forensic-file-carver-csharp)

**Archived software release (Zenodo DOI):** [10.5281/zenodo.22117441](https://doi.org/10.5281/zenodo.22117441)

---

**Research software project:** [Forensic File Carver](/en/forensic-file-carver-csharp)

## From Extracted Artifact to Security Context

An artifact recovered from a file or raw byte stream does not explain the incident by itself. Signature and pattern matches must be related to incident context, attacker behavior and deceptive or hostile data formats.

These concepts help connect a forensic artifact to its security context.

The core runtime concepts include [Indicator of Compromise](/en/wiki/indicator-of-compromise), [Steganography](/en/wiki/steganography), [Tactics Techniques and Procedures](/en/wiki/tactics-techniques-and-procedures) and [YARA](/en/wiki/yara).

For operation and diagnosis, [Meltdown](/en/wiki/meltdown) and [Zip Bomb](/en/wiki/zip-bomb).

## From Raw Media to Recoverable File Artifacts

Data carving attempts to recover evidence from raw byte streams when filesystem metadata cannot be trusted. Acquisition method, signature validation, unallocated regions and file remnants therefore affect the reliability of the algorithm directly.

The following forensic concepts define the main boundaries of a carving workflow.

The core runtime concepts include [Binary Entropy](/en/wiki/binary-entropy), [Disk Image](/en/wiki/disk-image), [E01](/en/wiki/e01) and [File Carving](/en/wiki/file-carving).

For operation and diagnosis, [Magic Number](/en/wiki/magic-number), [Slack Space](/en/wiki/slack-space), [Unallocated Space](/en/wiki/unallocated-space) and [Write Blocker](/en/wiki/write-blocker).

## References

- Brian Carrier. (2005). File System Forensic Analysis. Addison-Wesley Professional.

- Simson L. Garfinkel. (2007). Carving Contiguous and Fragmented Files with Fast Object Validation. Digital Investigation, 4(Suppl.), 2-12. [doi:10.1016/j.diin.2007.06.017](https://doi.org/10.1016/j.diin.2007.06.017)

## Cite This Work

Köker, M. A. (2021). A Data Carving Algorithm for Digital Forensics. alikoker.com.tr. https://alikoker.com.tr/en/data-carving-algorithm-for-digital-forensics

- BibTeX: https://alikoker.com.tr/en/data-carving-algorithm-for-digital-forensics.bib
- RIS: https://alikoker.com.tr/en/data-carving-algorithm-for-digital-forensics.ris
- CSL-JSON: https://alikoker.com.tr/en/data-carving-algorithm-for-digital-forensics.csl.json