1st International ICST Workshop on Computational Forensics

Research Article

Improving the Efficiency of Digital Forensic Search by Means of the Constrained Edit Distance

  • @INPROCEEDINGS{10.1109/IAS.2007.38,
        author={Slobodan Petrovic and Katrin Franke},
        title={Improving the Efficiency of Digital Forensic Search by Means of the Constrained Edit Distance},
        proceedings={1st International ICST Workshop on Computational Forensics},
        publisher={IEEE},
        proceedings_a={IWCF},
        year={2007},
        month={9},
        keywords={Bioinformatics  Codes  Computer science  Computer security  Digital forensics  Educational institutions  Information security  Inspection  Space technology  Testing},
        doi={10.1109/IAS.2007.38}
    }
    
  • Slobodan Petrovic
    Katrin Franke
    Year: 2007
    Improving the Efficiency of Digital Forensic Search by Means of the Constrained Edit Distance
    IWCF
    IEEE
    DOI: 10.1109/IAS.2007.38
Slobodan Petrovic1,*, Katrin Franke1,*
  • 1: NISlab, Department of Computer Science and Media Technology, Gjøvik University College, P.O. box 191, 2802 Gjøvik, Norway
*Contact email: slobodanp@hig.no, katrin.franke@hig.no

Abstract

A new search procedure is presented that makes use of the constrained edit distance in the preselection of the areas of the digital forensic search space that are interesting for the investigation. The constraints regard the maximum numbers of consecutive deletions and insertions. The original algorithm for computing the constrained edit distance is modified in order to be used in forensic search. The modification removes the constraints before the first substitution and after the last substitution. The advantage of the new method over the use of the unconstrained edit distance in the same procedure lies in the possibility of eliminating the need for finer exhaustive search in the fragments of the search space, in which the detected subsequence is too distorted. It also enables better control over the search process in the case of deliberate distortion of the evidence strings. Experimental results show that the proposed method offers data set reduction in the typical cases of as much as 80% compared to the method that uses unconstrained edit distance.