Abstract
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. Therefore, recent research has focused on devising new techniques to detect and contain network worms without the need of human supervision. In particular, a number of approaches have been proposed to automatically derive signatures to detect network worms by analyzing a number of worm-related network streams. Most of these techniques, however, 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. To detect these types of worms, it is necessary to devise new techniques that are able to identify similarities between different mutations of a worm.
This paper presents a novel technique based on the structural analysis of binary code that allows one to identify structural similarities between different worm mutations. The approach is based on the analysis of a worm’s control flow graph and introduces an original graph coloring technique that supports a more precise characterization of the worm’s structure. The technique has been used as a basis to implement a worm detection system that is resilient to many of the mechanisms used to evade approaches based on instruction sequences only.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Babai, L., Luks, E.: Canonical Labeling of Graphs. In: 15th ACM Symposium on Theory of Computing (1983)
Bailey, M., Cooke, E., Jahanian, F., Nazario, J., Watson, D.: The Internet Motion Sensor: A Distributed Blackhole Monitoring System. In: Network and Distributed Systems Symposium, NDSS (2005)
Berk, V., Gray, R., Bakos, G.: Using Sensor Networks and Data Fusion for Early Detection. In: SPIE Aerosense Conference (2003)
Dagon, D., Qin, X., Gu, G., Lee, W., Grizzard, J., Levin, J.: HoneyStat: Local Worm Detection Using Honeypots. In: Jonsson, E., Valdes, A., Almgren, M. (eds.) RAID 2004. LNCS, vol. 3224, pp. 39–58. Springer, Heidelberg (2004)
DeTristan, T., Ulenspiegel, T., Malcom, Y., von Underduk, M.: Polymorphic Shellcode Engine Using Spectrum Analysis, http://www.phrack.org/show.php?p=61&a=9
Kim, H.-A., Karp, B.: Autograph: Toward Automated, Distributed Worm Signature Detection. In: 13th Usenix Security Symposium (2004)
Kolesnikov, O., Lee, W.: Advanced Polymorphic Worms: Evading IDS by Blending in with Normal Traffic. Technical report, Georgia Tech. (2004)
Kreibich, C., Crowcroft, J.: Honeycomb - Creating Intrusion Detection Signatures Using Honeypots. In: 2nd Workshop on Hot Topics in Networks (2003)
Kruegel, C., Valeur, F., Robertson, W., Vigna, G.: Static Analysis of Obfuscated Binaries. In: 13th Usenix Security Symposium (2004)
Linn, C., Debray, S.: Obfuscation of Executable Code to Improve Resistance to Static Disassembly. In: ACM Conference on Computer and Communications Security, CCS (2003)
Macaulay, S.: ADMmutate: Polymorphic Shellcode Engine, http://www.ktwo.ca/ttsecurity.html
McKay, B.: Nauty: No AUTomorphisms, Yes?, http://cs.anu.edu.au/~bdm/nauty/
McKay, B.: Practical graph isomorphism. Congressus Numerantium 30 (1981)
Moore, D., Shannon, C., Voelker, G., Savage, S.: Internet Quarantine: Requirements for Containing Self-Propagating Code. In: IEEE Infocom Conference (2003)
Newsome, J., Karp, B., Song, D.: Polygraph: Automatically Generating Signatures for Polymorphic Worms. In: IEEE Symposium on Security and Privacy (2005)
Paxson, V.: Bro: A System for Detecting Network Intruders in Real-Time. In: 7th Usenix Security Symposium (1998)
Rabin, M.O.: Fingerprinting by Random Polynomials. Technical report, Center for Research in Computing Techonology, Harvard University (1981)
Roesch, M.: Snort - Lightweight Intrusion Detection for Networks. In: Usenix LISA Conference (1999)
Singh, S., Estan, C., Varghese, G., Savage, S.: Automated Worm Fingerprinting. In: 6th Symposium on Operating System Design and Implementation, OSDI (2004)
Skiena, S.: Graph Isomorphism. In: Implementing Discrete Mathematics: Combinatorics and Graph Theory. Addison-Wesley, Reading (1990)
Sophos. War of the Worms: Top 10 list of worst virus outbreaks in 2004 (2004), http://www.sophos.com/pressoffice/pressrel/uk/20041208yeartopten.html
Staniford, S., Moore, D., Paxson, V., Weaver, N.: The Top Speed of Flash Worms. In: 2nd ACM Workshop on Rapid Malcode, WORM (2004)
Staniford, S., Paxson, V., Weaver, N.: How to 0wn the Internet in Your Spare Time. In: 11th Usenix Security Symposium (2002)
Venkataraman, S., Song, D., Gibbons, P., Blum, A.: New Streaming Algorithms for Fast Detection of Superspreaders. In: Network and Distributed Systems Symposium, NDSS (2005)
Weaver, N., Paxson, V., Staniford, S., Cunningham, R.: A Taxonomy of Computer Worms. In: ACM Workshop on Rapid Malcode (October 2003)
Weaver, N., Staniford, S., Paxson, V.: Very Fast Containment of Scanning Worms. In: 13th Usenix Security Symposium (2004)
Whyte, D., Kranakis, E., van Oorschot, P.: DNS-based Detection of Scanning Worms in an Enterprise Network. In: Network and Distributed Systems Symposium, NDSS (2005)
Williamson, M.: Throttling Viruses: Restricting Propagation to Defeat Malicious Mobile Code. In: 18th Annual Computer Security Applications Conference, ACSAC (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kruegel, C., Kirda, E., Mutz, D., Robertson, W., Vigna, G. (2006). Polymorphic Worm Detection Using Structural Information of Executables. In: Valdes, A., Zamboni, D. (eds) Recent Advances in Intrusion Detection. RAID 2005. Lecture Notes in Computer Science, vol 3858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11663812_11
Download citation
DOI: https://doi.org/10.1007/11663812_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31778-4
Online ISBN: 978-3-540-31779-1
eBook Packages: Computer ScienceComputer Science (R0)