Hi there! I’m Dávid Maliga, a PhD student in the CrySyS lab, under the supervision of Prof. Levente Buttyán, and I have recently presented our extended abstract at this year’s CSCS conference (15th Conference of PhD Students in Computer Science) in the wonderful city of Szeged. This work was part of an R&D project that focused on designing efficient differential storage schemes for large malware repositories (e.g., VirusTotal, MalwareBazaar, or Kaibou Repo). Our project partner was Ukatemi Technologies, and the project was funded by the National Research, Development and Innovation Office of Hungary under grant number 2023-1.1.1PIACI_FÓKUSZ-2024-00030.
The main idea of our work stems from the observation that many malware samples are not entirely new, but rather minor modifications of existing members of a malware family. Thus, if we organize similar samples into groups (clusters), it suffices to store one “complete” sample per group – a representative sample for the whole cluster – with the rest stored as differences with respect to the completely stored sample; this is known as differential storage.
The best way to think of this is as video compression. Imagine you have to store the frames of a movie. You don’t store each one completely separately because consecutive frames are very similar. Instead, there is a “full” keyframe (called an I-frame), and for the other frames, you only store what has changed compared to the previous ones (these are the P-frames).
Exactly the same idea can be used to store malware samples efficiently: a representative sample of the cluster is like the key frame, it is stored in its entirety. All other malware samples in the cluster are stored as differences relative to the representative sample. So instead of storing 1,000 similar malware samples in their entirety, you store the “reference” only once and the differences for the rest.
But how can we measure similarities between malware samples? For this, we use a so-called locality-sensitive hash algorithm called TLSH. Traditional cryptographic hash functions (such as SHA-256 or MD5) are designed in such a way that if a single bit in the input is changed, the output hash value changes completely and unpredictably (this is called the avalanche effect). TLSH (and locality-sensitive hashes in general), on the other hand, is based on the exact opposite property: it returns similar hashes for similar inputs. If a large portion of two malware samples match – say, one is just a modified version of the other, then their TLSH hashes will also be close to each other. TLSH also provides a specific numerical value indicating how (dis)similar the two samples are. The smaller this dissimilarity score is, the more similar the two samples are.
This makes it possible to construct a similarity graph of malware samples, where each node represents a malware sample, and an edge is added between two nodes if their dissimilarity score is below a certain threshold (in the paper, this threshold was 40 and 86). And once such a graph is available, we can identify clusters of similar malware samples by using graph clustering algorithms. The identified clusters can then be the basis for differentially storing the samples, as we desribed above.
A main challenge is that, in practice, malware repositories are continuously growing with new samples arriving each and every day from different malware feeds, so the malware similarity graph representing the samples in the repository is also constantly changing. It would be a naive approach to re-run a graph clustering algorithm on the entire similarity graph each time new samples are added to it and then re-organize differntial storage based on the potentially changing clusters. Instead, we propose a better solution to this problem in our paper.
More specifically, we propose novel incremental clustering algorithms that handle dynamic graph changes in a more efficient manner. We call these clustering algorithms as follows: Incremental Join Closest Cluster Head (I-JCCH) and its variants, Incremental Join Closest Cluster Head w/ Maximum Cluster Size n (I-JCCH-n), and Incremental Join Closest Neighbor (I-JCN).
The first algorithm, I-JCCH, always compares new samples only to the representative samples (so called cluster heads) of existing clusters, and it adds a new sample to the cluster with the most similar cluster head without recalculating the clustering for the entire graph.
The I-JCCH algorithm has one theoretical weakness: large number of similar samples may all be added to the same cluster, making that cluster to grow too large in size. Why is this a problem? Because the larger a cluster is, the slower it can become to retrieve a specific sample from it. This is because, due to differential storage, the sample being retrieved often has to be “reconstructed” in multiple steps.
For this reason, we introduce an upper bound, n, on the size of clusters in the I-JCCH-n algorithm. Here, when a new sample arrives, the algorithm searches for the most similar cluster head. If that cluster has already reached its maximum size, the sample cannot be placed there. Instead, the algorithm tries the next most sismilar cluster head, and so on. If the sample cannot fit into any of the existing clusters, it forms its own new cluster.
Using an incremental approach speeds up clustering but may overlook better matches, because a sample within a given cluster might be more similar to a new sample than the cluster head of that cluster. Because of this, we examined the correlation between TLSH difference and compression gain from delta storage, finding that smaller TLSH dissimilarity scores yield greater storage efficiency. Therefore, in the I-JCN clustering algorithm, we compare each new malware sample against all samples in the repository, not just to the cluster heads, to store them more efficiently.
According to an evaluation on a dataset of 100,000 samples totaling more than 116 GB, this approach achieves nearly 50% storage savings. Furthermore, in case of I-JCCH-n with small cluster-size constraints, sample retrieval becomes faster, clearly demonstrating the trade-off between storage efficiency and retrieval speed. Although I-JCN achieved the best storage efficiency, we were only able to achieve a 0.5% gain in exchange for greater complexity. This suggests that I-JCCH offers a better trade-off.
The abstract submitted to the conference is available here. This paper could be cited as follows: Dávid Maliga and Levente Buttyán, Design and analysis of incremental clustering algorithms for large dynamic similarity graphs, 15th Conference of PhD Students in Computer Science (CSCS), 2026.