Computer Engineering Commons^™

On The Database Lookup Problem Of Approximate Matching, Frank Breitinger, Harald Baier, Douglas White

Electrical & Computer Engineering and Computer Science Faculty Publications

Investigating seized devices within digital forensics gets more and more difficult due to the increasing amount of data. Hence, a common procedure uses automated file identification which reduces the amount of data an investigator has to look at by hand. Besides identifying exact duplicates, which is mostly solved using cryptographic hash functions, it is also helpful to detect similar data by applying approximate matching.

Let x denote the number of digests in a database, then the lookup for a single similarity digest has the complexity of O(x). In other words, the digest has to be compared against …

File Detection On Network Traffic Using Approximate Matching, Frank Breitinger, Ibrahim Baggili

Journal of Digital Forensics, Security and Law

In recent years, Internet technologies changed enormously and allow faster Internet connections, higher data rates and mobile usage. Hence, it is possible to send huge amounts of data / files easily which is often used by insiders or attackers to steal intellectual property. As a consequence, data leakage prevention systems (DLPS) have been developed which analyze network traffic and alert in case of a data leak. Although the overall concepts of the detection techniques are known, the systems are mostly closed and commercial. Within this paper we present a new technique for network traffic analysis based on approximate matching (a.k.a …

An Efficient Similarity Digests Database Lookup – A Logarithmic Divide & Conquer Approach, Frank Breitinger, Christian Rathgeb, Harald Baier

Journal of Digital Forensics, Security and Law

Investigating seized devices within digital forensics represents a challenging task due to the increasing amount of data. Common procedures utilize automated file identification, which reduces the amount of data an investigator has to examine manually. In the past years the research field of approximate matching arises to detect similar data. However, if n denotes the number of similarity digests in a database, then the lookup for a single similarity digest is of complexity of O(n). This paper presents a concept to extend existing approximate matching algorithms, which reduces the lookup complexity from O(n) to O(log(n)). Our proposed approach is based …

An Efficient Similarity Digests Database Lookup -- A Logarithmic Divide And Conquer Approach, Frank Breitinger, Christian Rathgeb, Harald Baier

Electrical & Computer Engineering and Computer Science Faculty Publications

Investigating seized devices within digital forensics represents a challenging task due to the increasing amount of data. Common procedures utilize automated file identification, which reduces the amount of data an investigator has to examine manually. In the past years the research field of approximate matching arises to detect similar data. However, if n denotes the number of similarity digests in a database, then the lookup for a single similarity digest is of complexity of O(n). This paper presents a concept to extend existing approximate matching algorithms, which reduces the lookup complexity from O(n) to O(log(n)). Our proposed approach is based …