Internet worms have become a widespread threat to system and network operations. In order to fight them more efficiently, it is necessary to analyze newly discovered worms and attack patterns. This paper shows how techniques based on Kolmogorov Complexity can help in the analysis of internet worms and network traffic. Using compression, different species of worms can be clustered by type. This allows us to determine whether an unknown worm binary could in fact be a later version of an existing worm in an extremely simple, automated, manner. This may become a useful tool in the initial analysis of malicious binaries. Furthermore, compression can also be useful to distinguish different types of network traffic and can thus help to detect traffic anomalies: Certain anomalies may be detected by looking at the compressibility of a network session alone. We furthermore show how to use compression to detect malicious network sessions that are very similar to known intrusion attempts. This technique could become a useful tool to detect new variations of an attack and thus help to prevent IDS evasion. We provide two new plugins for Snort which demonstrate both approaches.
The problem of network security is approached from the point of view of Kolmogorov complexity (see Evans. S, et al, Proc. DARPA Inf. Survivability Conf. & Exposition II, vol 2. p.322-33, 2001). The principle of conservation of complexity is utilized to identify healthy complexity norms objectively and detect attacks via deviation of these norms under TCP IP. Observed complexity changes that fall within expected hounds are indicators of system health, while complexity changes outside the expected bounds for normal protocol and application use are indicators of system fault or attack. Experimental results using FTP normal and attack sessions are presented.