Learning to detect malicious executables in the wild

ABSTRACT

In this paper, we describe the development of a fielded application for detecting malicious executables in the wild. We gathered 1971 benign and 1651 malicious executables and encoded each as a training example using n-grams of byte codes as features. Such processing resulted in more than 255 million distinct n-grams. After selecting the most relevant n-grams for prediction, we evaluated a variety of inductive methods, including naive Bayes, decision trees, support vector machines, and boosting. Ultimately, boosted decision trees outperformed other methods with an area under the roc curve of 0.996. Results also suggest that our methodology will scale to larger collections of executables. To the best of our knowledge, ours is the only fielded application for this task developed using techniques from machine learning and data mining.

REFERENCES

• 1: David W. Aha , Dennis Kibler , Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [doi>10.1023/A:1022689900470]
• 2: A. Aiken. MOSS: A system for detecting software plagiarism. Software, Department of Computer Science, University of California, Berkeley, http://www.cs.berkeley.edu/~aiken/moss.html, 1994.
• 3: Anonymous , Shipley, Maximum Security, Sams, Indianapolis, IN, 2000
• 4: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 5: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 6: L. Breiman. Arcing classifiers. The Annals of Statistics, 26:801--849, 1998.
• 7: M. Christodorescu and S. Jha. Static analysis of executables to detect malicious patterns. In Proceedings of the Twelfth USENIX Security Symposium, Berkeley, CA, 2003. Advanced Computing Systems Association.
• 8: W. Cohen. Fast effective rule induction. In Proceedings of the Twelfth International Conference on Machine Learning, pages 115--123, San Francisco, CA, 1995. Morgan Kaufmann.
• 9: Thomas G. Dietterich, An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization, Machine Learning, v.40 n.2, p.139-157, Aug. 2000 [doi>10.1023/A:1007607513941]
• 10: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 11: Chris Drummond , Robert C. Holte, Explicitly representing expected cost: an alternative to ROC representation, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.198-207, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347126]
• 12: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 13: E. Durning-Lawrence. Bacon is Shake-speare. The John McBride Company, New York, NY, 1910.
• 14: Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In Proceedings of the Thirteenth International Conference on Machine Learning, pages 148--156, San Francisco, CA, 1996. Morgan Kaufmann.
• 15: A. Gray, P. Sallis, and S. MacDonell. Software forensics: Extending authorship analysis techniques to computer programs. In Proceedings of the Third Biannual Conference of the International Association of Forensic Linguists, pages 1--8, Birmingham, UK, 1997. International Association of Forensic Linguists.
• 16: David A. Grossman , Ophir Frieder, Information Retrieval: Algorithms and Heuristics, Kluwer Academic Publishers, Norwell, MA, 1998
• 17: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 18: Anil K. Jain , Robert P. W. Duin , Jianchang Mao, Statistical Pattern Recognition: A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.1, p.4-37, January 2000 [doi>10.1109/34.824819]
• 19: H. T. Jankowitz, Detecting plagiarism in student Pascal programs, The Computer Journal, v.31 n.1, p.1-8, Feb., 1988 [doi>10.1093/comjnl/31.1.1]
• 20: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 21: J. Kephart, G. Sorkin, W. Arnold, D. Chess, G. Tesauro, and S. White. Biologically inspired defenses against computer viruses. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pages 985--996, San Francisco, CA, 1995. Morgan Kaufmann.
• 22: Bradley Kjell , W. Addison Woods , Ophir Frieder, Discrimination of authorship using visualization, Information Processing and Management: an International Journal, v.30 n.1, p.141-150, Jan.-Feb. 1994 [doi>10.1016/0306-4573(94)90029-9]
• 23: I. Krsul. Authorship analysis: Identifying the author of a program. Master's thesis, Purdue University, West Lafayette, IN, 1994.
• 24: I. Krsul and E. Spafford. Authorship analysis: Identifying the authors of a program. In Proceedings of the Eighteenth National Information Systems Security Conference, pages 514--524, Gaithersburg, MD, 1995. National Institute of Standards and Technology.
• 25: R. Lo, K. Levitt, and R. Olsson. MCF: A malicious code filter. Computers & Security, 14:541--566, 1995.
• 26: M. E. Maron , J. L. Kuhns, On Relevance, Probabilistic Indexing and Information Retrieval, Journal of the ACM (JACM), v.7 n.3, p.216-244, July 1960 [doi>10.1145/321033.321035]
• 27: Gary McGraw , Greg Morrisett, Attacking Malicious Code: A Report to the Infosec Research Council, IEEE Software, v.17 n.5, p.33-41, September 2000 [doi>10.1109/52.877857]
• 28: C. Metz, Y. Jiang, H. MacMahon, R. Nishikawa, and X. Pan. ROC software. Web page, Kurt Rossmann Laboratories for Radiologic Image Research, University of Chicago, Chicago, IL, 2003.
• 29: P. Miller. hexdump 1.4. Software, http://gd.tuwien.ac.at/softeng/Aegis/hexdump.html, 1999.
• 30: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 31: D. Opitz and R. Maclin. Popular ensemble methods: An empirical study. Journal of Artificial Intelligence Research, 11:169--198, 1999.
• 32: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 33: J. Platt. Probabilities for SV machines. In P. Bartlett, B. Schölkopf, D. Schuurmans, and A. Smola, editors, Advances in Large-Margin Classifiers, pages 61--74. MIT Press, Cambridge, MA, 2000.
• 34: Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001 [doi>10.1023/A:1007601015854]
• 35: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 36: M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz. A Bayesian approach to filtering junk e-mail. In Learning for Text Categorization: Papers from the 1998 AAAI Workshop, Menlo Park, CA, 1998. AAAI Press. Technical Report WS-98-05.
• 37: Matthew G. Schultz , Eleazar Eskin , Erez Zadok , Salvatore J. Stolfo, Data Mining Methods for Detection of New Malicious Executables, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.38, May 14-16, 2001
• 38: S. Soman, C. Krintz, and G. Vigna. Detecting malicious Java code using virtual machine auditing. In Proceedings of the Twelfth USENIX Security Symposium, Berkeley, CA, 2003. Advanced Computing Systems Association.
• 39: Eugene H. Spafford , Stephen A. Weeber, Software forensics: can we track code to its authors?, Computers and Security, v.12 n.6, p.585-595, Oct. 1993 [doi>10.1016/0167-4048(93)90055-A]
• 40: J. Swets and R. Pickett. Evaluation of diagnostic systems: Methods from signal detection theory. Academic Press, New York, NY, 1982.
• 41: G. Tesauro, J. Kephart, and G. Sorkin. Neural networks for computer virus recognition. IEEE Expert, 11:5--6, August 1996.
• 42: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 43: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

General Terms:
Algorithms, Experimentation, Security

Keywords:
concept learning, data mining, malicious software, security