File carving
 | It has been suggested that Optimistic decompression be merged into this article. (Discuss) Proposed since August 2012. |
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.
Simson Garfinkel[1] 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 Word documents are relatively high. The fragmentation rate of JPEG files was found to be 16%, Word documents had 17% fragmentation, AVI had a 22% fragmentation rate and PST files (Microsoft Outlook) had a 58% fragmentation rate (the fraction of files being fragmented into two or more fragments). Pal, Shanmugasundaram, and Memon[2] presented an efficient algorithm based on a greedy heuristic and alpha-beta pruning for reassembling fragmented images. Pal, Sencar, and Memon[3] introduced sequential hypothesis testing as an effective mechanism for detecting fragmentation point. Richard and Roussev[4] presented Scalpel, an open-source file carving tool.
Carving schemes
Bifragment gap carving
Garfinkel introduced the use of fast object validation for reassembling files that have 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.
SmartCarving
Pal developed a carving scheme that is not limited to bifragmented files. The technique, known 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.
Carving memory dumps
Snapshots of computers' volatile memory can be carved. Memory dump carving is routinely used in digital forensics, allowing investigators to access ephemeral evidence. Ephemeral evidence includes recently accessed images and Web pages, documents, chats and communications committed via social networks. If an encrypted volume (TrueCrypt, BitLocker, PGP Disk) was used, binary keys to encrypted containers can be extracted and used to instantly mount such volumes. The content of volatile memory gets fragmented. A proprietary carving algorithm was developed by Belkasoft to enable carving fragmented memory sets (BelkaCarving).
See also
- Adroit (software), a commercial file carver that uses fragment reassembly carving.
- Belkasoft Evidence Center, a commercial computer forensics product implementing file system and smart memory dump carving.
- Defraser (software), an open-source video file carver with fragment repair capabilities.
- Foremost (software), an open-source file carver.
- PhotoRec, a popular open-source file carver.
- MediaCarve (software), a free file carver targeted to media files.
- Recover My Files, proprietary evaluationware, ms-windows
- Scalpel (software), an open-source file carver.
References
- ^ Simson Garfinkel, "Carving Contiguous and Fragmented Files with Fast Object Validation", in Proceedings of the 2007 digital forensics research workshop, DFRWS, Pittsburgh, PA, August 2007
- ^ A. Pal and N. Memon, "Automated reassembly of file fragmented images using greedy algorithms" in IEEE Transactions on Image processing, February 2006, pp 385393
- ^ A. Pal, T. Sencar and N. Memon, "Detecting File Fragmentation Point Using Sequential Hypothesis Testing", Digital Investigations, Fall 2008
- ^ Richard, Golden, Roussev, V., "Scalpel: a frugal, high performance file carver", in Proceedings of the 2005 digital forensics research workshop, DFRWS, August 2005