Demystifying File Similarity for Malware Detection

Demystifying File Similarity for Malware Detection

Speakers: Udbhav Prasad, Distributed Systems Engineer, DataBricks

Conference: BSides SF

YouTube: https://www.youtube.com/watch?v=V0g4c__cBkw

Overview

In an era where malware sophistication is rapidly escalating and adversaries can generate myriad polymorphic variants with ease, the ability to accurately and efficiently identify similar files is paramount for robust cybersecurity defenses. Udbhav Prasad's talk, "Demystifying File Similarity for Malware Detection," delves into the intricate world of file similarity algorithms, tracing their evolution from rudimentary bitwise comparisons to advanced machine learning approaches. The presentation meticulously dissects the challenges inherent in detecting subtly modified malware, especially given the immense scale of modern enterprise networks that can host billions of unique files.

Prasad, drawing on his extensive experience building large-scale distributed systems at companies like Rubrik, Stairwell, and DataBricks, provides a comprehensive overview of both feature-based and learning-based similarity techniques. He emphasizes that while traditional cryptographic hashes excel at identifying exact file matches, they are rendered useless by even a single byte change. This talk explores how various similarity algorithms — including fuzzy hashing techniques like SSDeep, SDHash, and TLSH, as well as machine learning models such as XGBoost and Deep Neural Networks — attempt to overcome this limitation by providing a measure of "degree of similarity" even when files are not identical. The discussion culminates in a comparative analysis of these methods, highlighting their strengths, weaknesses, and the critical need for hybrid detection strategies in today's dynamic threat landscape.

Background

▶ Watch: Introduction and agenda for file similarity talk (0:00)

The foundation of file identification in cybersecurity has long rested on cryptographic hashes like MD5 and SHA256. These algorithms produce a unique fixed-size string (a hash) for any given file. If two files produce the same hash, they are guaranteed to be identical. This property makes cryptographic hashes excellent for verifying file integrity and identifying known malware samples. However, their deterministic nature is also their Achilles' heel in the face of evolving threats. Even a single byte modification to a file will result in a completely different cryptographic hash, rendering it undetectable by simple hash lookups.

The problem is compounded by the ease with which attackers can generate polymorphic malware. Tools like Cobalt Strike and even basic reverse engineering software allow for trivial modifications to binaries, creating functionally identical but cryptographically unique variants. With the advent of large language models, this process is becoming even more automated, enabling attackers to rapidly generate vast numbers of subtly altered malicious payloads. This challenge extends beyond deliberate evasion; modern software development, characterized by continuous integration/continuous deployment (CI/CD) pipelines, generates hundreds of versions of legitimate software daily, making it difficult to distinguish benign updates from malicious insertions in supply chains.

Traditional signature-based detection, exemplified by basic hash databases or static/dynamic analysis systems like those used by VirusTotal or Intezer, struggles at scale. While Yara rules offer more sophisticated byte pattern matching, they are computationally expensive for large enterprises, difficult to author, and require constant maintenance as threats evolve. Applying generic Yara rule sets often leads to high noise (false positives) in specific environments. Furthermore, modern malware analysis extends beyond simple binary classification ("malware or not?") to family attribution, which helps in understanding attacker behaviors, threat hunting, and campaign tracking. This requires a nuanced understanding of file relationships, pushing the need for robust file similarity algorithms beyond simple exact matches. The scale of the problem is immense: large enterprises can monitor tens of thousands of endpoints, processing billions of unique files, turning similarity detection into a daunting "needle in a haystack" challenge.

Key Findings

▶ Watch: The scale of the malware detection challenge (4:30)

The experimental results presented in the talk highlight a significant performance gap between traditional fuzzy hashing techniques and modern machine learning approaches for both malware classification and similarity detection.

For binary classification (identifying a file as malware or benign) and multi-class classification (attributing a file to a specific malware family), XGBoost emerged as the superior model. In binary classification, XGBoost consistently outperformed Deep Neural Networks (DNNs) across metrics like accuracy, precision, and recall, albeit by a small percentage (around 1%). This seemingly small difference translates to substantial improvements when dealing with billions of files. For the more complex multi-class problem of classifying files into one of 20 malware families, XGBoost achieved an impressive 90% accuracy, a significant leap from a random guess (5% accuracy). DNNs performed considerably worse in this multi-class scenario.

However, the roles reversed when evaluating file similarity. Using a metric-agnostic approach called label homogeneity (measuring how many of a file's k-nearest neighbors share the same label), Deep Neural Networks demonstrated exceptional performance. For 100 nearest neighbors, DNNs achieved a label homogeneity score of 94-95%, meaning nearly all similar files identified by the DNN belonged to the same malware family. XGBoost, while significantly better than fuzzy hashing, reached only 75% homogeneity. In stark contrast, the fuzzy hashing algorithm SSDeep performed poorly, with only about 20% of its 100 nearest neighbors sharing the same label, indicating its limited ability to capture true semantic similarity.

These findings lead to a critical conclusion: model-task alignment is essential. There is no single "best" algorithm for all aspects of malware detection. XGBoost is highly effective for classification tasks, particularly when dealing with tabular features extracted from files. Deep Neural Networks, on the other hand, excel at capturing complex, non-linear relationships necessary for semantic similarity and generating robust embeddings. Fuzzy hashes, despite their limitations in overall similarity scoring, still offer value in terms of explainability and locality awareness, providing insights into which specific parts of files are similar. Therefore, the talk strongly advocates for hybrid detection systems that leverage the complementary strengths of these diverse tools for comprehensive and adaptable malware defense.

Technical Deep Dive

▶ Watch: Limitations of signature-based detection and Yara rules (5:50)

The journey into file similarity begins with fundamental concepts before advancing to more sophisticated methods.

The most basic approach is Hamming distance, which measures the number of positions at which two bit or byte streams differ. While simple, its direct application to entire files is impractical; a single offset can make two highly similar files appear entirely different. However, Hamming distance finds utility later in more advanced systems, comparing processed feature vectors rather than raw files.

A more refined approach is Edit distance, also known as Levenshtein distance. This metric quantifies the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one sequence into another. It intelligently handles minor shifts, as demonstrated by DNA sequence comparisons where a single offset yields a high Hamming distance but a low Levenshtein distance. Despite its intelligence, Levenshtein distance scales poorly; its dynamic programming algorithm is linear in the input size, making it computationally prohibitive for comparing a new file against billions of existing ones.

To overcome the scaling limitations of byte-by-byte comparisons, feature-based similarity emerged. Instead of raw bytes, files are pre-processed into "bags of tokens" – collections of extracted features like n-grams or imports. Jaccard similarity is a straightforward way to compare two such bags, calculated as the size of their intersection divided by the size of their union. This significantly reduces the search space, as comparisons are made on features rather than entire files. MinHash extends Jaccard similarity by providing an approximate, faster method for calculating it, particularly useful for very large datasets. However, even Jaccard similarity can scale poorly if the number of features is proportional to file size, and these methods lack inherent clustering capabilities. They are also sensitive to reordering of features, which is a common obfuscation technique.

This leads to the concept of fuzzy hashing, designed to produce hashes that are "similar" for files that are "similar," where small changes in the file result in small changes in the hash. The general workflow for fuzzy hashing involves:

1. Chunking: Breaking a file into segments.
2. Hashing: Applying a hash function to each segment.
3. Concatenation/Aggregation: Combining these segment hashes into a final fuzzy hash or digest.

Three prominent fuzzy hashing algorithms are discussed:

1. SSDeep (SSD): This algorithm uses a sliding window over the byte sequence and applies a rolling hash. It employs a sophisticated mechanism to decide where to break the rolling hash, generating a sequence of hashes. The final fuzzy hash is constructed by concatenating the last six lowest bits of these hashes. Similarity is then determined by calculating the Levenshtein distance between two SSDeep hashes, yielding a score from 0 (no match) to 100 (very similar). A key limitation is its sensitivity to reordering, compression, padding, or encoding changes, as it maintains an ordered concatenation of chunk hashes.

1. SDHash: Improving upon SSDeep's limitations, SDHash uses a fixed-size sliding window (64 bytes). Instead of taking all chunk hashes, it computes the Shannon entropy of the hashes within the window, selecting only the "most interesting" ones (those with lowest entropy). These selected hashes are then inserted into a Bloom filter, which acts as a set-based representation. Similarity between two SDHash digests is determined by the Hamming distance between their respective Bloom filters. SDHash offers better resilience to reordering due to its set-based nature. However, its digest size can become proportional to the input file size if the Bloom filter fills up, leading to higher storage costs and slower clustering. It remains sensitive to large-scale structural changes.

1. TLSH (Trend Micro Locality Sensitive Hash): This is considered one of the most robust fuzzy hashing techniques today. TLSH aims to overcome the reordering sensitivity and unpredictable digest sizes of its predecessors. It extracts n-grams from a sliding window and generates a histogram of 256 buckets based on these n-grams. Each n-gram is hashed and placed into its corresponding histogram bucket, with the count in the bucket incremented. This histogram is then used to generate a compact, fixed-size hash. TLSH is generally more robust to changes than SSDeep or SDHash, though SDHash might be better for specific containment detection tasks. Crucially, TLSH emits a true metric-based distance, satisfying properties like non-negativity, zero distance if and only if objects are equal, and the triangle inequality. This metric property is vital because it allows TLSH hashes to be used with vector databases and modern infrastructure designed for efficient vector search and clustering, opening avenues for scalable similarity comparisons.

Despite their advancements, fuzzy hashing techniques still face limitations. They are sensitive to large structural changes, rely on manual feature selection (algorithms are "handwritten"), and struggle to capture semantic similarity – the actual meaning or function of a file. They primarily focus on structural or syntactic similarity.

This brings us to learning-based similarity, which aims to learn complex patterns automatically from raw features, making them adaptable to evolving malware and temporal changes. The core workflow for machine learning-based similarity involves:

1. Classification Model Training: A model (e.g., XGBoost, DNN) is trained to classify files (e.g., malware/benign, or into malware families).
2. Embedding Generation: The trained classification model is then used to derive an embedding model. This model produces a vector representation (an "embedding") of the input file. These embeddings are latent or semantic representations of the file's features, mapped into an n-dimensional space.
3. Similarity Comparison: Files that are "close" to each other in this n-dimensional embedding space are considered similar. Distance metrics like Euclidean distance are commonly used here.

Two key machine learning models are explored:

1. XGBoost (Extreme Gradient Boosting): An ensemble learning method that sequentially builds a multitude of decision trees. It's renowned for its speed in training and inference, and its effectiveness with tabular features (e.g., static or dynamic analysis features extracted from malware). To generate an embedding from an XGBoost model, the input file is passed through all the trained trees. Each tree routes the file to a specific leaf node. An embedding is then constructed as a bit vector where each bit corresponds to a leaf node across all trees, indicating which leaf node the file reached in each tree. Similarity between two such embeddings is typically calculated using Hamming distance. This works because files classified similarly by the trees are likely to end up in the same or similar leaf nodes.

1. Deep Neural Networks (DNNs): These multi-layer networks are adept at capturing non-linear, complex, hierarchical representations of features from various inputs, including raw binary data or extracted features. For malware detection, DNNs are highly effective. To generate an embedding from a trained DNN, the "head" (the final classification layer) of the network is typically "chopped off." The output of the last hidden layer then serves as the file's vector representation or embedding. Similarity between these DNN embeddings is commonly measured using Euclidean distance. This approach is particularly powerful for capturing semantic relationships that might be missed by purely structural methods.

Demo / Proof of Concept

▶ Watch: Introduction to Hamming distance for bitstream comparison (6:30)

While the talk did not feature a live, interactive demonstration, Udbhav Prasad presented the results of extensive experimental work conducted with a colleague as a passion project, serving as a comprehensive proof of concept for the discussed methodologies. The experiments aimed to compare the effectiveness of fuzzy hashing and machine learning models for malware classification and similarity detection.

The core dataset for these experiments was the Ember dataset, an invaluable open collection of features from one million Portable Executable (PE) files. This dataset includes static analysis metadata such as byte statistics, header information, strings, imports, and crucially, SSDeep hashes. For the experiments, 800,000 labeled files (400,000 malware and 400,000 benign) were utilized. A significant enhancement to this dataset came from Crowdstrike, who augmented it with similarity information by processing the files through VirusTotal and tagging malware with AVclass labels, which essentially denote the malware family. It's important to note that the experiments could not include TLSH comparisons due to the dataset lacking raw file access, which is required to compute TLSH hashes. This remains a scope for future work.

The evaluation of classification models (XGBoost and DNNs) involved standard metrics:

• Accuracy: The proportion of correctly labeled samples.
• Precision: Of all samples labeled as positive, how many were actually positive (analogized to a metal detector finding gold).
• Recall: Of all actual positive samples, how many were correctly identified (analogized to finding all gold on the beach).
• F1 Score and AUC (Area Under the Curve): Composite metrics that balance precision and recall.

For the binary classification problem (malware vs. benign), XGBoost showed slightly better performance than Deep Learning, with higher accuracy, precision, and recall scores. While the difference might seem small (around 1%), it becomes significant at scale. For the multi-class classification problem (assigning files to one of 20 malware families), XGBoost demonstrated a clear advantage, achieving approximately 90% accuracy, vastly superior to a random guess (5%). Deep Learning models performed considerably worse in this specific multi-class task.

To compare the similarity models (SSDeep, XGBoost embeddings, DNN embeddings), which use different distance metrics (Levenshtein, Hamming, Euclidean, respectively), a metric-agnostic approach called label homogeneity was employed. This metric assesses a model's effectiveness in clustering similar items by asking: "For each file, how many of its k nearest neighbors share the same label?" A higher homogeneity score indicates a better similarity model.

The results for label homogeneity were striking:

• SSDeep: Showed poor performance, with only about 20% of its 100 nearest neighbors sharing the same label.
• XGBoost embeddings: Performed significantly better than SSDeep, with approximately 75% of its 100 nearest neighbors having the same label.
• Deep Neural Network embeddings: Demonstrated exceptional performance, achieving 94-95% label homogeneity among its 100 nearest neighbors.

These experimental findings clearly illustrate that while XGBoost excels at classification, Deep Neural Networks are superior for capturing the nuanced relationships required for robust file similarity. The results underscore the necessity of a multifaceted approach, leveraging different models for different tasks.

Defensive Implications

▶ Watch: Understanding Edit (Levenshtein) distance for file similarity (7:20)

The insights from this talk carry significant implications for cybersecurity defenders seeking to build more resilient and effective malware detection systems. The foremost takeaway is the critical need for hybrid detection systems. Relying on a single type of algorithm, whether traditional fuzzy hashing or a specific machine learning model, is insufficient against sophisticated and evolving threats.

Here's how defenders can apply this information:

1. Task-Specific Model Deployment:

• For malware classification (binary: malware/benign, or multi-class: family attribution), XGBoost should be prioritized. Its superior accuracy and speed with tabular features extracted from static or dynamic analysis make it an ideal choice for initial triage and categorization.
• For file similarity detection and clustering, especially for identifying polymorphic variants or tracking campaigns, Deep Neural Networks (DNNs) are demonstrably superior. Their ability to generate robust, semantically rich embeddings allows for more accurate identification of functionally similar but structurally diverse malware. This is crucial for threat hunting and understanding adversary tactics.

1. Leveraging Fuzzy Hashes for Explainability and Locality: While outperformed by ML models in overall similarity scoring, fuzzy hashing algorithms like TLSH (and to a lesser extent SSDeep/SDHash) retain value. They offer explainability by indicating which specific blocks or regions of files are similar, a property known as locality awareness. This can be invaluable for reverse engineers and analysts who need to pinpoint the exact changes between malware variants or understand how obfuscation techniques are applied. Integrating fuzzy hash comparisons alongside ML embeddings can provide a richer, more actionable context for alerts.

1. Continuous Model Fine-Tuning: The concept of temporal changes in malware is critical. A model trained on older malware data (e.g., 2014-2018 in the Ember dataset) may not perform well against contemporary threats. Defenders must implement processes for continuous retraining and fine-tuning of their machine learning models with fresh, in-the-wild malware samples to maintain detection efficacy.

1. Feature Engineering and Data Quality: The performance of ML models heavily depends on the quality and richness of input features. Investing in robust static and dynamic analysis pipelines to extract comprehensive features (byte statistics, headers, imports, exports, strings, etc.) is crucial. The talk highlighted that string-based features (imports, exports) were particularly important for XGBoost's performance.

1. Addressing Obfuscation: While the speaker acknowledged limitations in directly addressing VM-based obfuscation (e.g., VMProtect), the community response emphasized that even packed or obfuscated files can still reveal clustering patterns. Future work for defenders should involve researching and integrating techniques to unpack or de-obfuscate files before or during feature extraction, or to develop models specifically robust to obfuscated inputs (e.g., using AST-based embeddings as suggested in the Q&A).

1. Balancing Precision and Recall: Defenders must explicitly consider the trade-off between false positives (precision) and false negatives (recall). In high-risk environments (e.g., critical infrastructure), high recall (finding all threats, even if it means some benign files are flagged) might be prioritized. In other contexts, high precision (minimizing false alarms) might be more desirable. Machine learning models can be tuned to favor one over the other based on organizational risk appetite.

1. Comprehensive Tool Evaluation: When evaluating security products (like EDRs, sandboxes, or threat intelligence platforms), organizations should inquire about the range of file similarity and classification algorithms they employ. A vendor leveraging a diverse set of tools (fuzzy hashes, XGBoost, DNNs) is likely to offer a more robust and adaptable solution.

In essence, the future of malware detection lies in a sophisticated, multi-layered approach that intelligently combines the strengths of various algorithms, continuously adapts to new threats, and provides both high-level classification and granular, explainable similarity insights.

Key Takeaways

• No Single Solution: There is no universal "best" algorithm for all malware detection tasks; hybrid systems are essential.
• XGBoost for Classification: XGBoost excels at binary and multi-class malware classification, particularly with rich, tabular features derived from static/dynamic analysis.
• Deep Neural Networks for Similarity: Deep Learning models, through their ability to generate powerful semantic embeddings, are superior for detecting file similarity and clustering related malware variants.
• Fuzzy Hashes for Explainability: Techniques like TLSH still hold value for providing locality awareness and explainability, indicating which parts of files are similar.
• Model-Task Alignment is Crucial: The choice of algorithm must align with the specific security task (e.g., classification vs. similarity, initial detection vs. threat hunting).
• Continuous Adaptation: Malware detection models require continuous fine-tuning with new threat intelligence to remain effective against evolving temporal changes in attack patterns and obfuscation techniques.

About the Speaker(s)

Udbhav Prasad is a seasoned engineer with a passion for building large-scale distributed systems. His professional journey has seen him contribute to prominent technology companies, including Rubrik, where he focused on data resilience and security, and Stairwell, a security startup that operates similarly to VirusTotal but with extensive file storage capabilities. Currently, Udbhav is a Distributed Systems Engineer at DataBricks, a company that is increasingly investing in security product development. His interest in security stems from the intersection of large-scale systems and data, a domain where he believes significant advancements in detection and defense can be made. Udbhav's expertise lies in designing and implementing scalable software architectures, and he actively explores how these principles can be applied to complex cybersecurity challenges like malware detection and analysis.