File carving
Encyclopedia
File carving is the process of reassembling computer files from fragments in the absence of
filesystem metadata. The carving process makes use of knowledge of common file structures, information contained in files, and heuristics regarding how filesystems fragment
data. Fusing these three sources of information, a file carving system infers which fragments belong together.
File carving is a highly complex task, with a potentially huge number of permutations to try.
To make this task tractable
, carving software typically makes extensive use of models and heuristics.
This is necessary not only from a standpoint of execution time, but also for the accuracy of the
results. State of the art file carving algorithms use statistical techniques like
sequential hypothesis testing
for determining the fragmentation point.
Garfinkel
reported fragmentation statistics collected from over 350 disks containing FAT, NTFS and UFS file systems.
He showed that while fragmentation in a typical disk is low, the fragmentation rate of forensically important files such as email, JPEG and MS-Word are relatively high. The fragmentation rate of JPEG files was found to be 16%, MS-Word documents had 17% fragmentation, AVI (movie format) had a 22% fragmentation rate and
PST files (MS-Outlook) had a 58% fragmentation rate. Pal, Shanmugasundaram, and Memon
presented an efficient algorithm based on a greedy heuristic and
alpha-beta pruning
for reassembling fragmented images.
Pal, Sencar, and Memon introduced sequential hypothesis testing as an effective mechanism for detecting fragmentation point.
Richard and Roussev
presented Scalpel, an open-source file carving tool.
been split into two pieces. This technique is referred to as Bifragment Gap Carving (BGC).
A set of starting fragments and a set of finishing fragments are identified. The fragments
are reassembled if together they form a valid object.
as SmartCarving, makes use of heuristics regarding the fragmentation behavior of known filesystems.
The algorithm has three phases: preprocessing, collation, and reassembly. In the preprocessing
phase, blocks are decompressed and/or decrypted if necessary. In the collation phase, blocks are
sorted according to their file type. In the reassembly phase, the blocks are placed in sequence
to reproduce the deleted files. The SmartCarving algorithm is the basis for the Adroit Photo Forensics
and Adroit Photo Recovery applications from Digital Assembly.
filesystem metadata. The carving process makes use of knowledge of common file structures, information contained in files, and heuristics regarding how filesystems fragment
File system fragmentation
In computing, file system fragmentation, sometimes called file system aging, is the inability of a file system to lay out related data sequentially , an inherent phenomenon in storage-backed file systems that allow in-place modification of their contents. It is a special case of data fragmentation...
data. Fusing these three sources of information, a file carving system infers which fragments belong together.
File carving is a highly complex task, with a potentially huge number of permutations to try.
To make this task tractable
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, carving software typically makes extensive use of models and heuristics.
This is necessary not only from a standpoint of execution time, but also for the accuracy of the
results. State of the art file carving algorithms use statistical techniques like
sequential hypothesis testing
Sequential analysis
In statistics, sequential analysis or sequential hypothesis testing is statistical analysis where the sample size is not fixed in advance. Instead data are evaluated as they are collected, and further sampling is stopped in accordance with a pre-defined stopping rule as soon as significant results...
for determining the fragmentation point.
Garfinkel
reported fragmentation statistics collected from over 350 disks containing FAT, NTFS and UFS file systems.
He showed that while fragmentation in a typical disk is low, the fragmentation rate of forensically important files such as email, JPEG and MS-Word are relatively high. The fragmentation rate of JPEG files was found to be 16%, MS-Word documents had 17% fragmentation, AVI (movie format) had a 22% fragmentation rate and
PST files (MS-Outlook) had a 58% fragmentation rate. Pal, Shanmugasundaram, and Memon
presented an efficient algorithm based on a greedy heuristic and
alpha-beta pruning
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
for reassembling fragmented images.
Pal, Sencar, and Memon introduced sequential hypothesis testing as an effective mechanism for detecting fragmentation point.
Richard and Roussev
presented Scalpel, an open-source file carving tool.
Bifragment gap carving
Garfinkel introduced the use of fast object validation for reassembling files that havebeen split into two pieces. This technique is referred to as Bifragment Gap Carving (BGC).
A set of starting fragments and a set of finishing fragments are identified. The fragments
are reassembled if together they form a valid object.
SmartCarving
Pal developed a carving scheme that is not limited to bifragmented files. The technique, knownas SmartCarving, makes use of heuristics regarding the fragmentation behavior of known filesystems.
The algorithm has three phases: preprocessing, collation, and reassembly. In the preprocessing
phase, blocks are decompressed and/or decrypted if necessary. In the collation phase, blocks are
sorted according to their file type. In the reassembly phase, the blocks are placed in sequence
to reproduce the deleted files. The SmartCarving algorithm is the basis for the Adroit Photo Forensics
and Adroit Photo Recovery applications from Digital Assembly.
See also
- PhotoRecPhotoRecPhotoRec is a file carver data recovery software tool designed to recover lost files from digital camera memory , hard disks and CD-ROMs...
, a popular open-source file carver. - Scalpel (software), an open-source file carver.