Worm Detection

Next generation worm detection using structural information of executables


Network worms are malicious programs that spread automatically across networks by exploiting vulnerabilities that affect a large number of hosts. Because of the speed at which worms spread to large computer populations, countermeasures based on human reaction time are not feasible. In order to address the problem, a number of approaches have been proposed to automatically derive signatures to detect network worms by analyzing a number of worm-related network streams. These approaches are known as content sifting, and most of them assume that the worm code does not change during the infection process. Unfortunately, worms can be polymorphic. That is, they can mutate as they spread across the network through self-encryption mechanisms or semantics-preserving code manipulation techniques. In this research we propose a technique that uses the structural properties of a worm's executable to identify different mutations of the same worm. More specifically, we divide a program binary's control flow graph (CFG) into a set of subgraphs. These subgraphs are then "fingerprinted" based on their adjacency matrix and finally their nodes are colored based on the types of instructions they contain. Once this has been completed, CFGs and their subgraphs can be compared with the aim of detecting isomorphisms between subgraphs, thus indicating the mutation of a particular worm. The technique is resilient to code modifications that make existing approaches based on content sifting ineffective. The main contributions of this work are:
  • We propose a novel fingerprinting technique based on control flow information that allows us to detect structural similarities between variations of a polymorphic worm.
  • We introduce an improvement of the fingerprinting technique that is based on a novel coloring scheme of the control flow graph.
  • We present an evaluation of a prototype system to detect polymorphic worms that implements our novel fingerprinting techniques.


Internet Worm
A malicious program that spreads automatically among hosts on a network by exploiting various vulnerabilities present on those hosts.
Polymorphic Worm
A worm that has the ability to mutate via code transformations (e.g., encryption and semantics preserving code transformations) as it spreads.
Content Sifting
A technique to automatically derive worm signatures given various network flows that is based on several currently valid heuristics.
A mapping between graphs or sets that preserves the relations between elements of each set or graph.


We analyzed malicious code that was disguised by ADMmutate, a well-known polymorphic engine. ADMmutate operates by first encrypting the malicious payload, and then prepending a metamorphic decryption routine. To evaluate our system, we used ADMmutate to generate 100 encrypted instances of a worm, which produced a different decryption routine for each run. Then, we used our system to identify common substructures between these instances. Our system could not identify a single fingerprint that was common to all 100 instances. However, there were 66 instances that shared one fingerprint, and 31 instances that shared another fingerprint. Only 3 instances did not share a single common fingerprint at all. We performed a second experiment to analyze the structural similarities between different members of a worm family. Strictly speaking, members of a worm family are not polymorphic per se, but the experiment provides evidence of how much structural similarity is retained between variations of a certain worm. This is important to understand how resilient our system is to a surge of worm variations during an outbreak. For this experiment, the prototype was run against 342 samples of malware variants from 93 distinct families.
Family Variant Tests Matches Match Rate
FIZZER 1 1 100.00%
FRETHEM 1 1 100.00%
KLEZ 6 6 100.00%
KORGO 136 9 6.62%
LOVEGATE 300 300 100.00%
MYWIFE 3 1 33.33%
NIMDA 1 1 100%
OPASERV 171 11 6.43%
All 1,991 338 16.97%


2005 (1 publication)

Polymorphic Worm Detection Using Structural Information of Executables C. Kruegel, E. Kirda, D. Mutz, W. Robertson, G. Vigna Proceedings of the International Symposium on Recent Advances in Intrusion Detection (RAID 2005) BibTeX

Research topics

People involved


PhD Students

Last update
Sept. 26, 2011, 7:47 a.m.