PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalpel3: A High-Performance Data Carving Architecture for Recovery of Fragmented Files

Karley Waguespack, Samuel Goodwin, George Hendrick, Samuel Hildebrand, Thomas Landaiche, Mingyang Li, Joshua McCain, Tyler Saizan, Jacob Tucker, James M. Ghawaly, Golden G. Richard

arXiv:2608.20363v2cs.DCcs.CR

TL;DR

File carving lacks a publicly available, format-agnostic, high-performance framework for developing fragmented recovery strategies. Scalpel3 supplies massively threaded infrastructure around file-specific validation and reassembly, and experiments show fast contiguous recovery plus earlier validated fragmented results with greater parallelism. The framework therefore provides a practical foundation for fragmented recovery strategies at scale, although effectiveness depends on format-specific internal structure and research.

  • Problem

    Existing tools recover contiguous files effectively, but no publicly available, format-agnostic, high-performance framework supports developing and deploying new fragmented recovery strategies.

  • Method

    Scalpel3 separates massively threaded backend infrastructure from file-type-specific validators and reassembly functions, with APIs, ONNX support, checkpointing, I/O, and operational tooling.

  • Results

    Scalpel3 achieves high contiguous-recovery throughput and makes validated fragmented results available substantially earlier with higher thread counts.

  • Takeaways & Limitations

    Scalpel3 provides an open-source shared platform intended to lower experimentation barriers and translate file-carving research into practical tools.

  • Takeaways & Limitations

    Fragmented recovery accuracy depends on internal format structure, while supporting each file type remains a separate research effort whose results may not transfer across formats.

Abstract

from arXiv · show

File carving recovers files from raw storage without filesystem metadata, a key capability in digital forensics, data recovery, and digital exploration. Existing tools recover contiguous files effectively, but, to our knowledge, no publicly available, format-agnostic, high-performance framework exists in which researchers can develop and deploy new fragmented recovery strategies. Scalpel3 fills this gap with a massively threaded architecture for contiguous and fragmented recovery. Researchers need only write single-threaded validation and reassembly code for a new file type; Scalpel3 supplies worker scheduling, synchronization, checkpointing, and I/O. This separation allows new recovery methods to be added without modifying the backend infrastructure. The architecture also integrates the ONNX Runtime, allowing learned models to be used within validators and recovery strategies. Operational features include interactive human-in-the-loop control, block deduplication, persistent restart checkpoints, incremental output, and a FUSE filesystem for hybrid workflows. We evaluate Scalpel3 on a mixed corpus of more than 80,000 files under contiguous recovery and three controlled fragmentation scenarios: gaps, out-of-order block placement, and both together. Results show fast and accurate contiguous recovery and demonstrate that Scalpel3's massively threaded architecture makes validated fragmented results available substantially earlier than single-threaded execution. Furthermore, strategies tailored to individual file types maintain high overall accuracy across increasingly difficult layouts. Together, these results demonstrate that Scalpel3 provides a practical foundation for developing and deploying fragmented recovery strategies at scale.

1. Introduction

File carving recovers files without filesystem metadata, but fragmentation and disordered surviving blocks make reconstruction difficult. Scalpel3 addresses this gap with an extensible, massively parallel framework and supporting toolchain for practical recovery research.

  • File carving recovers files from raw media without relying on filesystem metadata, supporting recovery after deletion, reformatting, damage, or unknown storage contents.
  • Fragmentation separates file data into noncontiguous regions, while disordered or partial fragments create infeasible combinatorial reconstruction searches.
  • Scalpel3 provides a massively parallel architecture for contiguous and fragmented carving, with researchers implementing file-type-specific validation and reassembly logic.
  • Scalpel3 combines general-purpose extensibility, contiguous and fragmented recovery, massively parallel execution, open-source release, and operational support for deployment at scale.
  • Researchers add new file types through public validator, state, and reassembly APIs without modifying backend infrastructure, including ONNX support for learned models.
  • The toolchain supports reproducible controlled-fragmentation experiments and hybrid workflows through synthetic image generation, blockmaps, and a FUSE filesystem.

2. Related Work

Prior carving research developed signature-based, fragmented-recovery, and classification methods, but existing systems remained specialized, limited, or lacked a usable general implementation. Scalpel3 combines format-aware recovery with parallel execution and broader integration.

  • File carving research spans signature-based contiguous recovery, fragmented recovery, and statistical or machine-learning fragment classification.
  • Traditional header–footer carvers are effective for contiguous files but can produce false positives when signatures lack strong format validation.
  • Scalpel3 parallelizes header/footer detection, block validation, reassembly, file validation, and I/O rather than only selected pipeline phases.
  • Prior fragmented-carving systems include gap models, image and executable strategies, and multimedia prototypes, but many were unavailable, single-format, or limited.
  • Format-aware validators use structures such as offsets, lengths, checksums, coding constraints, and cross-field consistency to prune fragmented reconstruction searches.
  • Fragment classification can guide candidate search, yet existing integrations were generally evaluated in isolation or tied to particular file formats.

3. Scalpel3: Architectural Overview

Scalpel3 coordinates contiguous and fragmented carving through modular components, dedicated thread pools, shared queues, and a virtualized image view. Its phased workflow progressively escalates recovery while supporting checkpointing and operator control.

  • Architecture: Scalpel3 coordinates high-performance fragmented recovery through a carver, file mirror, validators, blockvectors, blockmaps, and a promising queue.The architecture supports format-specific identification, reconstruction, and validation.
  • Recovery phases: The carver performs block validation and boundary discovery once, then iterates through contiguous recovery, promising-fragment reassembly, and speculative candidate creation.These phases are designated C, F1, and F2.
  • Recovery phases: Validated files are removed from the search space, while repeated contiguous passes can expose logical contiguity created by newly covered blocks.Fragmented recovery periodically pauses for contiguous-recovery retries as coverage changes.
  • Parallel execution: Dedicated thread pools and shared candidate queues distribute boundary scanning, validation, and reassembly work across the recovery pipeline.The header/footer search uses SIMD operations where available.
  • Operational control: Checkpointing flushes state to disk and lets operators halt, inspect, resume, or abandon candidates during long-running carving jobs.The scalpel3-ctl utility provides checkpoint, status, and candidate-abandonment commands.

3.2. A Running Example

The running example shows how Scalpel3 combines deduplication, candidate scheduling, blockvectors, format-specific validation, and backtracking to reconstruct fragmented files. Coverage and structural constraints progressively simplify and constrain the search.

  • Example layout: The fourteen-block example contains a contiguous JPEG, two fragmented PNGs, duplicated filler content, unrelated compressed data, and unrelated boundary blocks.PNG-1 is split around the JPEG, while PNG-2 is separated by filler and unrelated data.
  • Initialization: Duplicate detection makes block 8 the exemplar and block 12 a duplicate that fragmented recovery does not independently inspect.Duplicate blocks inherit classifier scores from their exemplar.
  • Candidate scheduling: The promising queue schedules partially validated candidates using accumulated service time, preventing expensive candidates from monopolizing reassembly.This policy surfaces early partial results across many files rather than completing only a few.
  • Blockvectors: Blockvectors record each candidate’s ordered block references and maintain validity, apparent and actual positions, and tried alternatives for backtracking.The API supports logical ordering and locality-sensitive placement.
  • Shared blocks: A candidate’s block may overlap with candidates from other file types because blocks remain available until a file validates fully and becomes covered.This permits parallel exploration of overlapping reconstructions.
  • Format-specific reassembly: For PNG-2, chunk length and CRC constraints exclude filler and unrelated blocks before validation, yielding the fully validated sequence ⟨6, 7, 10, 11⟩.Formats lacking deterministic constraints use incremental validation and backtracking instead.

3.5. The File Mirror

The file mirror gives Scalpel3 a shifting logical image while preserving physical block references. It manages coverage and duplicates and provides shared, optimized I/O for recovery threads.

  • Logical and physical views: The file mirror maintains actual and apparent images, removing covered data from the logical view while preserving physical block locations.This lets later passes discover contiguity without losing references to the evidence image.
  • Coverage and duplicates: Coverage and duplication metadata exclude covered blocks, coalesce fragmented duplicate choices through exemplars, and retain uncovered physical copies for contiguous recovery.The two recovery modes therefore use duplicate information differently.
  • I/O: The mirror mediates uniform reads and writes, using sequential readahead, asynchronous vector writes, memory mappings, or contiguous buffers as needed.A shared read-only memory mapping allows all threads to access the evidence image.
  • Integration: Blockvectors depend on the mirror to translate apparent and actual block numbers, fetch data, and update coverage during reconstruction.The two structures jointly maintain candidate state and image state.
  • Coverage feedback: When JPEG blocks are covered, previously separated PNG blocks become consecutive in the apparent image and recover through a second contiguous pass.This provides a cheap path for mild fragmentation without invoking fragmented reassembly.

3.6. Blockmaps

Scalpel3’s blockmap tracks coverage, duplication, exemplars, reference counts, and reservations to support efficient fragmented recovery. Primary and shadow maps batch concurrent coverage updates while apparent-image mappings expose newly contiguous data.

  • Blockmap metadata: The blockmap tracks coverage, duplication, exemplar status, zero blocks, reference counts, and reservations for each image block.These fields support coverage control, duplicate handling, and reservation-based scheduling.
  • Apparent image: When validated blocks are covered, the apparent image can make remaining fragments appear contiguous and enable a fast contiguous recovery pass.This interaction supports mild-fragmentation recovery without invoking fragmented reassembly.
  • Deduplication and reservations: Duplicate blocks remain visible at their physical positions during contiguous recovery, while fragmented recovery considers only each duplicate group’s exemplar.This preserves physical layout for contiguous carving while reducing equivalent fragmented-search candidates.
  • Deduplication and reservations: Reference counts keep exemplars available until every occurrence in their duplicate group is covered.For exemplars, the count records uncovered instances; covering a block sets its reference count to zero when applicable.
  • Deduplication and reservations: Reservations count in-progress candidates holding an exemplar or duplicate and let strategies prefer blocks with fewer competing claims.The default strategy uses this mechanism to reduce fruitless validator calls.
  • Blockmap updates: Coverage updates accumulate in a shadow blockmap and periodically replace the primary map after reassembly threads become quiescent.Batching avoids a global blockmap lock while rebuilding apparent-to-actual mappings for recovery threads.

3.7. Validators

Scalpel3 combines block-level and file-level validation with learned inference, checkpointing, and operator control. Validators prioritize avoiding false negatives, while ONNX-based confidence scores guide—but do not exclude—candidate blocks.

  • Validator roles: Block validators assess whether blocks may belong to a file type, while file validators test structural integrity of assembled fragments.File validation occurs on complete contiguous candidates or incrementally during left-to-right reassembly.
  • Validator roles: Block validators minimize false negatives by accepting ambiguous blocks for later disambiguation by file validators or reassembly logic.The same block may therefore be accepted for multiple file types.
  • Machine learning: ONNX-integrated learned models can supply per-block confidence scores that influence candidate ordering without removing blocks from the search space.MoDiCo runs before block validators, and validators may retain or change its scores.
  • Operational control: Scalpel3 uses periodic, progress, and restart checkpoints to update coverage, expose active work, and serialize restartable state.Restart checkpoints are scheduled every 5m by default and include candidate queues, blockvectors, and blockmap metadata.
  • Operational control: Interactive controls let operators inspect jobs, monitor coverage and statistics, and terminate unpromising reassembly work during large-image processing.Jobs are tracked by UUID for reliable cancellation.
  • Incremental output: Validated files are written incrementally, while partial fragments can optionally be emitted under status-specific output directories.This supports inspection before the entire carving operation completes.

4. Adding New File Types

New file types are added through small, format-specific interfaces while Scalpel3 supplies scheduling and backend execution. Developers can choose optional validators, state hooks, and custom reassembly strategies, with left-to-right reassembly as the fallback.

  • Validation interface: File validators report whether a fragment is promising, the last consistent byte offset, and whether the fragment fully validates.These outputs control truncation, queueing, completion, or discard decisions.
  • Custom reassembly: Custom reassembly functions control initialization, block selection, validation, backtracking, checkpoint handling, and final candidate output.They use Scalpel3’s core structures and backend APIs to implement format-specific recovery logic.
  • Default strategy: Galloping mode tentatively places exponentially larger runs of sequential blocks, then trims back to the last verified state after failure.The default strategy uses this to exploit long contiguous runs within fragmented files.
  • Default strategy: The default left-to-right strategy appends blocks at a candidate’s tail and invokes the file validator after each extension.It serves as the baseline when no format-specific reassembly function is provided.
  • Custom reassembly: Format-specific reassembly can use locality, duplication status, validator results, probabilistic search, or learned guidance without changing the backend.The interface supports adding new strategies through developer-supplied functions.
  • Required and optional components: Adding a new format requires a file validator and configuration registration; block validators and custom reassembly functions are optional.State hooks are required when format-specific block or candidate state is used.

5. Scalpel3 Toolchain

The Scalpel3 toolchain supports reproducible fragmentation experiments, persistent blockmap management, and hybrid workflows with other recovery tools. Utilities compare, edit, mount, and reuse coverage and deduplication information across runs.

  • Controlled experiments: fragmentator generates synthetic disk images with controlled fragmentation and emits ground-truth layouts for byte-for-byte recovery comparisons.A seed parameter makes randomized placement reproducible.
  • Blockmap utilities: The toolchain’s blockmap utilities record coverage, duplication relationships, and reservation metadata for reuse across runs.The blockmap is a per-block index maintained for carving operations.
  • Blockmap utilities: crblockmap detects all-zero blocks and performs SHA-256-based block deduplication, confirming candidate duplicates through direct comparison.The resulting metadata is stored in the blockmap.
  • Hybrid workflows: modblockmap supports manual coverage edits and imports external-tool logs, allowing third-party recoveries to be marked before Scalpel3 searches residual space.This enables hybrid workflows involving tools such as PhotoRec.
  • Blockmap utilities: cmpblockmaps compares two blockmaps to highlight coverage changes and quantify progress between runs.Its primary use is measuring differences before and after Scalpel3 processing.
  • Hybrid workflows: blockmapfs exposes an uncovered-only FUSE view so downstream scanners avoid data already validated by Scalpel3 or other tools.Combined with coverage editing, the view supports sequential processing by multiple carving tools.

6. Format-Specific Carving

Scalpel3 uses format-specific validators and reassembly strategies because file formats expose different structural evidence. The section develops strategies for PNG, JPEG, GIF, ELF, and related formats, including learned block classification for ELF.

  • Format-specific validators are necessary because headers, framing, alignment, compression, and checksums differ across file formats.
  • The format-specific case studies show how checksums, chunk structure, decodable streams, and internal metadata become validation and reassembly signals.These signals guide strategies for the fragmented image formats and metadata-driven ELF recovery.
  • 6.1. PNG File Carving: PNG recovery combines chunk parsing, CRC checks, zlib inflation, and CRC-constrained block selection for fragmented files.The strategy uses inverse CRC reasoning and structured searches before final structural and stream validation.
  • 6.2. JPEG File Carving: JPEG validation parses markers and Huffman-decodes entropy-coded scans, while reassembly ranks continuations using structure and decoded image continuity.JPEG lacks per-chunk checksums, so incorrect continuations may decode for many bytes before failing.
  • 6.3. GIF File Carving: GIF recovery validates LZW-decoded sub-block chains and prioritizes continuation blocks using sub-block phase and continuity checks.GIF has no per-chunk checksum, so decoding is supplemented by statistical detectors and alignment information.
  • 6.4. ELF File Carving: ELF carving estimates file length from internal header, program-table, section-table, and segment metadata because ELF has no footer.When the optional section header table is absent, Scalpel3 uses the highest occupied extent among other metadata and segments.
  • 6.4. ELF File Carving: Fragmented ELF recovery uses an ONNX Runtime learned model to classify candidate blocks when rule-based block evidence is weak.The bulk of ELF files has little per-block structure that can be checked cheaply.

7. Performance

Scalpel3 is evaluated on a common 80,549-file corpus across contiguous, GAP, out-of-order, and combined fragmentation workloads. It remains competitive and highly accurate for contiguous recovery, while threading advances fragmented results earlier and format-specific evidence determines accuracy.

  • 7.1. Experimental Setup and Methodology: 80,549 files spanning six formats were evaluated with 16 KiB blocks, ground-truth scoring, repeated runs, and measurements through 128 reported threads.The corpus includes PNG, ZIP, JPEG, GIF, ELF, and DOCX files.
  • 7.2. Contiguous Recovery: Scalpel3 recovered 80,524–80,525 files exactly, about 5,000 more than single-threaded PhotoRec, while remaining within PhotoRec’s performance range.PhotoRec is the contiguous-carving baseline because no publicly available tool performs general fragmented reassembly.
  • 7.2. Contiguous Recovery: Random zero padding has little effect on contiguous recovery, whereas random padding adds modest scanning cost.Scalpel3 skips known all-zero blocks but must search random padding for possible signatures.
  • 7.3. Fragmented Recovery: Accuracy tracks available structural evidence: PNG is nearly perfect, GIF remains strong, and JPEG is the limiting format under difficult fragmentation.In the combined scenario, fragmented PNG exact recoveries were 5,217–5,226, GIF exact recoveries were 476–477, and JPEG exact recoveries were 186–192.
  • 7.3.1. Gap Fragmentation: 1,646 s to 104 s: GAP runtime decreases from one to 128 threads, corresponding to a 15.9× speedup with identical final validated counts.The 128-thread GAP run produced 80,525 exact recoveries.
  • 7.3.2. Out-of-Order Fragmentation: 128 threads reaches 79,000 validated files after 806 s in out-of-order recovery, compared with 1,709 s for 64 threads.The 64-, 96-, and 128-thread configurations converge near 79,850 validated files by the fixed budget.
  • 7.3.3. Combined Gap and Out-of-Order Fragmentation: In the combined scenario, 128 threads reaches 78,000 validated files after 1,614 s, compared with 4,545 s for 32 threads.Higher thread counts make most results available earlier even though the top configurations converge near 79,700 validated files.

8. Limitations

Scalpel3’s fragmented reassembly depends on format-specific internal structure and can become computationally unbounded under severe damage or weak validation. Supporting each file type remains a separate research effort whose results may not transfer across formats.

  • Formats lacking checksums, grammars, decodable streams, or offset metadata provide few constraints for fragmented reassembly.Entropy-coded JPEG data supports less accurate reordering than CRC-protected PNG data.
  • Support for each file type requires separate research into cheaply validated structures and search-pruning constraints.The backend supplies infrastructure, but does not replace format analysis.
  • Highly speculative recovery can become computationally expensive or lack a termination guarantee when blocks are missing, fragmentation is pathological, or validators are weak.Stopping criteria, checkpoints, operator control, and phase ordering mitigate these conditions.

9. Future Work

Future work focuses on expanding format coverage, improving generic reassembly strategies, and incorporating filesystem knowledge. These directions aim to provide additional constraints for fragmented recovery while preserving Scalpel3’s raw-block operating model.

  • Broadening fragmented recovery to additional file formats requires identifying format-specific structures, offsets, checksums, and cross-field constraints.Scalpel3’s public validator and custom reassembly interfaces provide a common development platform.
  • Candidate generic strategies include bidirectional assembly, seam-based scoring, beam search, and constraint-based placement.These strategies could be evaluated against the default left-to-right approach under identical conditions.
  • Filesystem-aware carving could sharpen fragmented recovery by exploiting allocator patterns even when filesystem knowledge is incomplete.Scalpel3 currently operates on raw block sequences because filesystem metadata may be absent or untrustworthy.

10. Conclusions

Scalpel3 is an extensible, massively parallel framework for contiguous and fragmented file recovery, separating orchestration, disk I/O, and format-specific recovery logic. Its phased architecture and operational features support practical investigations, while experiments show high contiguous throughput and earlier validated fragmented recovery with more threads.

  • Scalpel3 separates pipeline orchestration, disk I/O and block management, and format-specific validation and reassembly.This separation supports recovery of both contiguous and fragmented files in a publicly available framework.
  • The phased C, F1, F2 recovery model prioritizes easier recoveries before progressively more expensive fragmented reassembly.Blockmap updates and periodic checkpoints reduce the search space for later passes.
  • Higher thread counts recover more validated files earlier from large candidate sets, while contiguous recovery achieves high throughput.The results show substantial acceleration of fragmented reassembly.
Loading 2608.20363v2…