Similarity Digest Schemes are used in various applications (e.g. digital forensics, spam filtering, malware detection and malware clustering), which require them to be resistant against attacks aiming at generating (A) semantically similar inputs with very different similarity digest values, or (B) completely different inputs with very similar digest values. We show that TLSH, a widely used similarity digest function, is not robust enough against either kinds of attacks. More specifically, we propose automated methods to modify executable software binaries in a way that the modified binary has the exact same functionality as the original one, yet (A) its TLSH difference score from the original version becomes high, or (B) its TLSH digest becomes very similar to another arbitrary TLSH digest up to a complete digest collision. We evaluate our methods on a large data set containing malware binaries, and we also show that they can be used effectively to generate adversarial samples that evade detection by SIMBIoTA, a recently proposed similarity-based malware detection approach.

In this paper, we present a pipeline that we designed for cleaning and processing large datasets of potentially malicious binaries using access to a rate-limited cloud-based malware analysis platform. Our goal is to efficiently filter out and discard benign files, to extract metadata from the remaining, likely-to-be-malware samples, and to create graph-based databases containing only metadata of verified malware. The main issue that we have to solve is the limited quota for accessing online malware analysis platforms that can be used for deciding about the maliciousness of a binary and obtaining metadata from static and dynamic analysis of samples. Our pipeline solves the problem by reaching a state where every sample in the database is either confirmed malware (based on its VirusTotal report) or similar to a confirmed malware with a minimal amount of requests made to the online platform. A database in such a state is already usable in practice, while confirming the malicious nature of and extracting metadata for all the samples in it can be continued in the background.

Similarity digest schemes are used in various applications (e.g., digital forensics, spam filtering, malware clustering, and malware detection), which require them to be resistant to attacks aiming at generating semantically similar inputs that have very different similarity digest values. In this paper, we show that TLSH, a widely used similarity digest function, is not sufficiently robust against such attacks. More specifically, we propose an automated method for modifying executable files (binaries), such that the modified binary has the exact same functionality as the original one, it also remains syntactically similar to the original one, yet, the TLSH difference score between the original and the modified binaries becomes high. We evaluate our method on a large data set containing malware binaries, and we also show that it can be used effectively to generate adversarial samples that evade detection by SIMBIoTA, a recently proposed similarity-based malware detection approach.