Automated reassembly of file fragmented images using greedy algorithms

Nasir Memon, Anandabrata Pal

Research output: Contribution to journalArticle

Abstract

The problem of restoring deleted files from a scattered set of fragments arises often in digital forensics. File fragmentation is a regular occurrence in hard disks, memory cards, and other storage media. As a result, a forensic analyst examining a disk may encounter many fragments of deleted digital files, but is unable to determine the proper sequence of fragments to rebuild the files. In this paper, we investigate the specific case where digital images are heavily fragmented and there is no file table information by which a forensic analyst can ascertain the correct fragment order to reconstruct each image. The image reassembly problem is formulated as a κ-vertex disjoint graph problem and reassembly is then done by finding an optimal ordering of fragments. We provide techniques for comparing fragments and describe several algorithms for image reconstruction based on greedy heuristics. Finally, we provide experimental results showing that images can be reconstructed with high accuracy even when there are thousands of fragments and multiple images involved.

Original languageEnglish (US)
Pages (from-to)385-393
Number of pages9
JournalIEEE Transactions on Image Processing
Volume15
Issue number2
DOIs
StatePublished - Feb 2006

Keywords

  • File fragmentation
  • Forensics
  • Greedy algorithms
  • Reassembly

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Automated reassembly of file fragmented images using greedy algorithms'. Together they form a unique fingerprint.

  • Cite this