Similarity Digest Search: A Survey and Comparative Analysis of Strategies to Perform Known File Filtering Using Approximate Matching

Abstract EN

Digital forensics is a branch of Computer Science aiming at investigating and analyzing electronic devices in the search for crime evidence.

There are several ways to perform this search.

Known File Filter (KFF) is one of them, where a list of interest objects is used to reduce/separate data for analysis.

Holding a database of hashes of such objects, the examiner performs lookups for matches against the target device.

However, due to limitations over hash functions (inability to detect similar objects), new methods have been designed, called approximate matching.

This sort of function has interesting characteristics for KFF investigations but suffers mainly from high costs when dealing with huge data sets, as the search is usually done by brute force.

To mitigate this problem, strategies have been developed to better perform lookups.

In this paper, we present the state of the art of similarity digest search strategies, along with a detailed comparison involving several aspects, as time complexity, memory requirement, and search precision.

Our results show that none of the approaches address at least these main aspects.

Finally, we discuss future directions and present requirements for a new strategy aiming to fulfill current limitations.