💻 computer science

MalTree: Tracing Malware Evolution from Embeddings at Scale

The paper introduces MalTree, a scalable framework that adapts bioinformatics phylogenetic techniques to automatically model malware evolution using structural, behavioral, and image-based features, achieving 87% temporal consistency and enabling proactive, lineage-aware defense strategies.

Original authors: Akash Amalan, Georgios Smaragdakis, Tom J. Viering

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Akash Amalan, Georgios Smaragdakis, Tom J. Viering

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the world of computer viruses (malware) not as a chaotic pile of random bad code, but as a giant, evolving family tree, much like the history of humans or the spread of a flu virus.

For a long time, security experts have played a game of "whack-a-mole." They wait for a new virus to appear, study it, and then build a shield to stop it. But by the time they build the shield, the virus has already changed its face, slipped through, and created a new version. This paper, MalTree, proposes a way to stop playing whack-a-mole and start understanding the family history instead.

Here is the breakdown of how they did it, using simple analogies:

1. The Problem: The "Reactive" Game

Think of malware detection like a bouncer at a club. The bouncer has a list of known bad guys (signatures). If someone looks like a bad guy on the list, they get kicked out. But the bad guys are smart; they wear disguises (encryption) or change their clothes (polymorphism) to look different. By the time the bouncer updates the list, the bad guy has already changed again.

The authors argue that instead of just looking at individual "bad guys," we should look at their family tree. If we know that "Virus A" is the parent of "Virus B," and "Virus B" is the parent of "Virus C," we can predict what "Virus D" might look like before it even shows up.

2. The Solution: MalTree (The Digital Genealogist)

The researchers built a tool called MalTree. Instead of reading the code line-by-line (which is like trying to read a book written in a language you don't speak), they used a method borrowed from biology called Phylogenetics.

The DNA of Malware: In biology, scientists compare DNA to see how related two animals are. MalTree does the same thing with malware. It takes a virus and turns it into a "fingerprint" (called an embedding).
Three Types of Fingerprints: To get a complete picture, they didn't just look at one thing. They looked at three different "angles":
1. The Skeleton (Static): What the code looks like when it's frozen (like looking at a car's engine block).
2. The Behavior (Dynamic): What the virus does when it runs (like watching a car drive to see if it speeds or swerves).
3. The Visual (Image): They turned the code into a picture (like a barcode) and used AI to "see" patterns, similar to how a human recognizes a face.

They combined these three views into a single, super-detailed fingerprint for each virus.

3. Building the Tree

Once they had the fingerprints, they used math (specifically algorithms named UPGMA and Neighbor-Joining) to calculate how "different" each virus is from every other virus.

If two viruses have very similar fingerprints, they are placed close together on the tree (siblings).
If they are very different, they are placed far apart (distant cousins).

They did this for 103,883 different malware samples. That's a massive family reunion!

4. The "Time Machine" Check

A big question is: Is this tree actually real, or did the computer just guess?

To prove it works, the researchers used VirusTotal timestamps (the date a virus was first reported to the internet).

The Logic: In a real family tree, the "parent" must exist before the "child."
The Test: They checked if the viruses that appeared earlier in time were actually placed higher up on the tree (closer to the root) than the ones that appeared later.
The Result: It worked 87% of the time. This means the tree they built matches the real history of how these viruses evolved.

5. What They Found (The "Aha!" Moments)

The paper highlights a few key discoveries using this tree:

Different Speeds: Just like some families have kids every year and others wait a decade, some malware families evolve very slowly, while others mutate incredibly fast. One family (Bashlite) changed more than 10 times faster than others. This suggests security teams can't use a "one-size-fits-all" defense; they need to tailor their speed to the specific virus family.
The Mirai Botnet: They traced the famous Mirai virus (which caused a huge internet blackout in 2016). The tree correctly identified its "children," including Bashlite, Okiru, and Gafgyt. This matched what human experts already knew from years of manual investigation, proving the computer can do in hours what usually takes humans months.
The "Hub" Problem: They found that some viruses act like "delivery trucks" (loaders) that carry many different types of bad payloads. The tree showed these connections, but also warned that sometimes viruses look related just because they use the same tools, not because they are actually family.

The Bottom Line

MalTree is a tool that turns the chaotic mess of computer viruses into an organized family tree. By understanding the family history, security experts can stop just reacting to the latest disguise and start anticipating how the virus family will evolve next.

It's like moving from trying to catch a single thief in the dark to having a map of the entire criminal underworld, knowing exactly who is related to whom and where they are likely to strike next.

Technical Summary: MalTree – Tracing Malware Evolution from Embeddings at Scale

1. Problem Statement

Current malware detection paradigms are fundamentally reactive. Machine learning models trained on known samples degrade as threats evolve through polymorphism, metamorphism, and obfuscation. While understanding evolutionary relationships among malware families could inform proactive defense, traditional reverse engineering to uncover lineage is slow, often taking months to years. Furthermore, existing phylogenetic approaches in malware analysis are limited by small sample sizes, single feature modalities, or a lack of temporal validation to confirm whether inferred trees reflect actual emergence timelines. There is a critical gap in scaling evolutionary analysis to large datasets while validating that structural similarities correspond to genuine historical lineages.

2. Methodology

The authors propose MalTree, a framework that applies bioinformatics-inspired phylogenetic techniques to malware samples at an unprecedented scale. The pipeline consists of four main stages:

2.1. Multi-Modal Embedding Extraction

Rather than analyzing raw binaries (which are often packed), MalTree analyzes memory dumps extracted from controlled sandbox executions to reveal decrypted code and runtime states. It extracts three complementary embeddings:

Pseudo-static ( $e_s$ ): Derived from executable sections (headers, imports, exports, opcodes) using the LIEF library, encoded via a text-embedding model (OpenAI text-embedding-3-large) to 3,000 dimensions, concatenated with byte histograms.
Dynamic ( $e_d$ ): Captures behavioral traces (file, process, registry, network, mutex activity) from sandbox execution, encoded to 1,000 dimensions.
Image ( $e_i$ ): Memory dumps converted to RGB images (bin2png) and processed through a ResNet-50 architecture pre-trained on malware image benchmarks and fine-tuned on the dataset, yielding 2,048-dimensional vectors.

These embeddings are fused via concatenation and a two-layer neural network, reducing the combined 6,560 dimensions to a 1,000-dimensional representation for tree construction.

2.2. Tree Construction

The framework constructs phylogenetic trees from pairwise distances in the embedding space using two distance-based algorithms:

UPGMA (Unweighted Pair Group Method with Arithmetic Mean): Assumes a constant evolutionary rate (molecular clock).
Neighbor-Joining (NJ): Accommodates rate heterogeneity, allowing lineages to evolve at different speeds.
The authors utilize RapidNJ to achieve near- $O(n^2)$ scaling, enabling the processing of over 100,000 samples.

2.3. Temporal Validation

Since malware lacks genetic sequences and known divergence dates, MalTree introduces a novel validation method using VirusTotal first-submission timestamps as proxies for emergence time.

Rooting: Trees are rooted using the sample with the earliest timestamp (outgroup rooting) or via midpoint rooting.
Consistency Metric: The framework validates the tree by comparing the inferred divergence order against timestamps. For sibling pairs sharing a Most Recent Common Ancestor (MRCA), the sample with the shorter path length (branch distance) to the MRCA is inferred to have emerged earlier. A "temporal consistency score" is calculated as the proportion of sibling pairs where the tree-inferred order matches the timestamp order.

2.4. Inter-Family Analysis

To infer relationships between families, the framework aggregates samples by family (determined by VirusTotal consensus labels). It calculates the median path distance from each family's leaves to their shared MRCA. Directed edges are created from the family with the shorter median distance (earlier diverging) to the family with the longer distance, with edge weights representing the source family's median distance.

3. Key Contributions

Large-Scale Phylogenetic Analysis: The authors constructed validated phylogenetic trees from 103,883 malware samples spanning 538 families. This analysis was completed in approximately 11 hours (UPGMA) or 3 days (NJ) on a 20-core cluster, representing the largest such analysis to date.
Temporal Validation Framework: The paper introduces a method to validate evolutionary directionality using VirusTotal timestamps, addressing a gap in prior work where inferred trees were not verified against real-world emergence timelines.
Interpretable Evolutionary Insights: The framework includes methods for tree simplification and inter-family analysis that reveal relationships consistent with public cybersecurity intelligence (e.g., the Mirai botnet lineage).
Open Release: The code and embeddings are released to the community to facilitate further research.

4. Experimental Results

Embedding Quality: Combined multi-modal embeddings achieved a family classification accuracy of 93.69% using a linear probe, outperforming individual modalities. Image embeddings alone achieved 94.91%, suggesting visual structure strongly discriminates families.
Temporal Consistency: The Neighbor-Joining algorithm with outgroup rooting achieved a temporal consistency score of 87.1%. This indicates that the inferred evolutionary relationships closely align with real-world emergence timelines. In contrast, UPGMA performed well (86.0%) in its nominal configuration but degraded significantly when forced into alternative rooting schemes, suggesting malware evolution often violates the constant-rate assumption.
Evolutionary Rates: Analysis of embedding drift revealed that mutation rates are non-uniform across families. Some families (e.g., Bashlite, Syslogk) exhibit over 10 times higher drift than others, violating the molecular clock assumption required by UPGMA and favoring Neighbor-Joining.
Case Studies:
- Mirai Botnet: The inferred tree correctly identified five known Mirai descendants (Bashlite, Okiru, MooBot, Gafgyt, Rapperbot) with edge weights consistent with documented code lineage and threat intelligence. Static analysis of import/export symbols confirmed high code reuse (e.g., 82% overlap between Mirai and Okiru).
- SmokeLoader: The framework identified delivery chain associations (e.g., with Amadey, RedLine) rather than code inheritance, demonstrating its ability to capture operational proximity.
- Limitations Observed: The framework captured functional similarities rather than organizational ones. For instance, the Conti ecosystem (Wizard Spider group) did not cluster together because the tools (banking trojans, loaders, ransomware) occupied different regions of the feature space despite shared authorship.

5. Significance and Claims

The paper claims that MalTree provides a foundation for shifting malware analysis from sample-by-sample classification toward lineage-aware evolutionary modeling. By demonstrating that phylogenetic methods can capture meaningful evolutionary structure at scale, the work suggests that detection strategies should be tailored to the specific evolutionary tempos of malware families.

The authors emphasize that their approach complements existing workflows by producing evolutionary insights in weeks rather than the months required for manual reverse engineering. However, they remain modest about the scope, noting that:

The framework captures functional relationships (code reuse, shared toolkits) rather than organizational ones (threat actor attribution).
It cannot automatically distinguish between code evolution, delivery chain associations, and incidental feature-space proximity.
The validity of the inferred trees relies on the assumption that shorter branch lengths within sibling pairs correspond to earlier emergence, a "local clock" assumption that holds empirically for shallow divergences but requires further validation for highly irregular evolution.

Ultimately, MalTree offers a scalable, automated method to visualize and validate the co-evolving digital ecosystem of malware, providing security practitioners with hypotheses for investigation and a deeper understanding of how malware families evolve over time.