CrySyS Blog

This post summarizes the work we presented at the 15th Conference of PhD Students in Computer Science (CSCS), 2026 in Szeged. My name is Jószef Sándor, I’m a PhD student in the CrySyS Lab, mentored by Prof. Levente Buttyán. A BSc student, Bence Kovács, was also involved in this project, mostly working on the implementation of our ideas.

Imagine a lightweight malware detector running on a small IoT device. It’s fast, compact, and accurate on test data. Now imagine an attacker who tweaks a malware file just enough to fool the detector – while the malware still works exactly as intended. This is a rational move for the attacker: building a whole new malware is difficult and expensive, so reusing existing malware – even at the binary level – while evading detection is a much cheaper path to success.

To defend against this, we first need to know what kinds of changes are likely to succeed. We could hand-craft a few evasive variants ourselves, but that approach is slow and covers only a handful of evasion strategies. Instead, we adapt how evolution works: similar to natural selection shaping organisms over generations to better fit their environment, we let a genetic algorithm shape malware modification strategies, automatically discovering the most effective method to construct evasive samples from a given input malware binary.

Figure 1. The genetic algorithm loop in one picture: keep what works best, change what does not, and repeat.

Our framework GAME (Genetic Algorithm for Malware Evasion) does exactly this: it starts with many random modification strategies, tests them, keeps the better ones, and creates new variants through mutation and crossover. Instead of evolving raw files directly, it evolves strategies for changing ELF malware binaries in format-preserving ways, such as appending data to, overwriting unused paddings, or injecting a new segment in the ELF file. A strategy’s goodness is measured not only by whether it evades detection, but also by how well it keeps the attacker’s practical goals in mind, such as minimal file size growth. GAME was validated on SIMBIoTA-ML, a lightweight IoT malware detector that uses TLSH-based features with a machine learning (ML) classifier. GAME does not need internal details of the ML model used by the detector. It only needs the final prediction label, so it works in a black-box setting.

Figure 2. GAME framework overview: original malware is transformed into evasive variants guided by a genetic algorithm that can bypass detection.

In the reported setup, we trained SIMBIoTA-ML (used with a Random Forest classifier) on ARM malware and benign binaries, then ran GAME against malware samples. The pattern was clear: strategies improved quickly already in early generations, and by around generation 32, well performing strategies evolved that produced samples that evaded detection. Strategies using padding overwrite and segment injection were often the strongest, since they produce evading malware samples with hard to detect structural anomalies.

The real power of our approach for generating adversarial malware samples is that it tries to minimize the amount of explicit assumptions made about the attacker. Instead of making arbitrary assumptions about what adversarial strategies are actually used to generate evading samples, we only make reasonable assumptions about the set of modification primitives available to the attacker and model preferences of the attacker implicitly in the fitness function used to evaluate the performance of the evolving populations of strategies; the rest is solved by evolution.

GAME is not just an attacker’s story – its main value is defensive. It can generate diverse and realistic evasive samples that can later be used for making SIMBIoTA-ML more robust using adversarial training methods.

For further details, you can check our paper here.

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.