Evolvable malware

ABSTRACT

The concept of artificial evolution has been applied to numerous real world applications in different domains. In this paper, we use this concept in the domain of virology to evolve computer viruses. We call this domain as "Evolvable Malware". To this end, we propose an evolutionary framework that consists of three modules: (1) a code analyzer that generates a high-level genotype representation of a virus from its machine code, (2) a genetic algorithm that uses the standard selection, cross-over and mutation operators to evolve viruses, and (3) the code generator converts the genotype of a newly evolved virus to its machinelevel code. In this paper, we validate the notion of evolution in viruses on a well-known virus family, called Bagle. The results of our proof-of-concept study show that we have successfully evolved new viruses-previously unknown and known-variants of Bagle-starting from a random population of individuals. To the best of our knowledge, this is the first empirical work on evolution of computer viruses. In future, we want to improve this proof-of-concept framework into a full-blown virus evolution engine.

REFERENCES

• 1: F-Secure Virus Description Database, available at http://www.f-secure.com/v-descs/.
• 2: The IDA pro disassembler and debugger, available at http://www.hex-rays.com/idapro/.
• 3: Offensive Computing, available at http://www.offensivecomputing.net.
• 4: VX Heavens Virus Collection, VX Heavens website, available at http://hvx.netlux.org.
• 5: Kaspersky Lab, VirusList.Com, available at http://www.viruslist.com/en/viruses/encyclopedia/.
• 6: J.M. Bauer, J.G. Michel and Y. Wu. "ITU Study on the Financial Aspects of Network Security: Malware and Spam", ICT Applications and Cybersecurity Division, International Telecommunication Union, Final Report, July 2008, available at http://www.itu.int/ITU-D/cyb/cybersecurity/docs/itu-study-financial-aspects-of-malware-and-spam.pdf.
• 7: F. Cohen, "Computer Viruses", PhD thesis, University of Southern California, 1985.
• 8: Goldie Gabrani , Preeti Bhargava , Bhawana Bhawana , Gagandeep Singh Gill, Use of genetic algorithms for Indian music mixing, Ubiquity, v.2008 n.March, p.1-10 [doi>10.1145/1361264.1361265]
• 9: John R. Koza , Forrest H. Bennett, III , David Andre , Martin A. Keane, Reuse, Parameterized Reuse, and Hierarchical Reuse of Substructures in Evolving Electrical Circuits Using Genetic Programming, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.312-326, October 07-08, 1996
• 10: J.R. Koza and J.P. Rice, "Automatic Programming of Robots using Genetic Programming" 10th National Conference on Artificial Intelligence, pp. 194--201, Association for the Advancement of Artificial Intelligence (AAAI), 1992.
• 11: M.A. Ludwing, "Computer Viruses, Artificial Life and Evolution", American Eagle Publications, 1993.
• 12: Jeff Gray , Raymond Klefstad, Adaptive and Evolvable Software Systems: Techniques, Tools, and Applications, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences, p.274, January 03-06, 2005 [doi>10.1109/HICSS.2005.68]
• 13: M.H. Marghny and A.F. Ali, "Web Mining based on Genetic Algorithm", IGCST International Journal on Artificial Intelligence and Machine Learning, Special Issue on AI Classification&Analysis Techniques, 2006.
• 14: Hans Jonas Fossum Moen , Stein Kristoffersen, Multi-resistant radar jamming using genetic algorithms, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389398]
• 15: David Montana , Talib Hussain , Tushar Saxena, Adaptive Reconfiguration Of Data Networks Using Genetic Algorithms, Proceedings of the Genetic and Evolutionary Computation Conference, p.1141-1149, July 09-13, 2002
• 16: K. Rozinov, "Reverse code engineering: An In-depth Analysis of the Bagle Virus", 6th Annual IEEE SMC Information Assurance Workshop (IAW), pp. 380--387, IEEE Press, USA, 2005.
• 17: Eugene H. Spafford, Computer viruses as artificial life, Artificial Life, v.1 n.3, p.249-265, Spring 1994
• 18: Gary Stein , Bing Chen , Annie S. Wu , Kien A. Hua, Decision tree classifier for network intrusion detection with GA-based feature selection, Proceedings of the 43rd annual Southeast regional conference, March 18-20, 2005, Kennesaw, Georgia [doi>10.1145/1167253.1167288]
• 19: Omid David-Tabibi , Moshe Koppel , Nathan S. Netanyahu, Genetic algorithms for mentor-assisted evaluation function optimization, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389382]
• 20: Gil Weinberg , Mark Godfrey , Alex Rae , John Rhoads, A Real-Time Genetic Algorithm in Human-Robot Musical Improvisation, Computer Music Modeling and Retrieval. Sense of Sounds: 4th International Symposium, CMMR 2007, Copenhagen, Denmark, August 27-31, 2007. Revised Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-85035-9_24]
• 21: D. Whitley, "An Overview of Evolutionary Algorithms: Practical Issues and Common Pitfalls", Information and Software Technology, 43(14), pp. 817--831, 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

General Terms:
Experimentation, Security

Keywords:
artificial evolution, computer virus, genetic algorithm