A semantics-based approach to malware detection

ABSTRACT

Malware detection is a crucial aspect of software security. Current malware detectors work by checking for "signatures," which attempt to capture (syntactic) characteristics of the machine-level byte sequence of the malware. This reliance on a syntactic approach makes such detectors vulnerable to code obfuscations, increasingly used by malware writers, that alter syntactic properties of the malware byte sequence without significantly affecting their execution behavior.This paper takes the position that the key to malware identification lies in their semantics. It proposes a semantics-based framework for reasoning about malware detectors and proving properties such as soundness and completeness of these detectors. Our approach uses a trace semantics to characterize the behaviors of malware as well as the program being checked for infection, and uses abstract interpretation to "hide" irrelevant aspects of these behaviors. As a concrete application of our approach, we show that the semantics-aware malware detector proposed by Christodorescu et al. is complete with respect to a number of common obfuscations used by malware writers.

REFERENCES

• 1: Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
• 2: D. Chess and S. White. An undetectable computer virus. In Proceedings of the 2000 Virus Bulletin Conference (VB2000), Orlando, FL, USA, Sept. 27--29, 2000. Virus Bulletin.
• 3: Stanley Chow , Yuan Gu , Harold Johnson , Vladimir A. Zakharov, An Approach to the Obfuscation of Control-Flow of Sequential Computer Programs, Proceedings of the 4th International Conference on Information Security, p.144-155, October 01-03, 2001
• 4: Mihai Christodorescu , Somesh Jha , Sanjit A. Seshia , Dawn Song , Randal E. Bryant, Semantics-Aware Malware Detection, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.32-46, May 08-11, 2005 [doi>10.1109/SP.2005.20]
• 5: F. Cohen, Computer viruses: theory and experiments, Computers and Security, v.6 n.1, p.22-35, Feb. 1987 [doi>10.1016/0167-4048(87)90122-2]
• 6: C. Collberg, C. Thomborson, and D. Low. A taxonomy of obfuscating transformations. Technical Report 148, Department of Computer Sciences, The University of Auckland, July 1997.
• 7: Christian Collberg , Clark Thomborson , Douglas Low, Manufacturing cheap, resilient, and stealthy opaque constructs, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268962]
• 8: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 9: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• 10: Patrick Cousot , Radhia Cousot, Systematic design of program transformation frameworks by abstract interpretation, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.178-190, January 16-18, 2002, Portland, Oregon
• 11: Mila Dalla Preda , Roberto Giacobazzi, Control Code Obfuscation by Abstract Interpretation, Proceedings of the Third IEEE International Conference on Software Engineering and Formal Methods, p.301-310, September 07-09, 2005 [doi>10.1109/SEFM.2005.13]
• 12: M. Dalla Preda and R. Giacobazzi. Semantic-based code obfuscation by abstract interpretation. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), volume 3580 of Lecture Notes in Computer Science, pages 1325--1336, Lisboa, Portugal, July 11--15, 2005. Springer Berlin/Heidelberg.
• 13: T. Detristan, T. Ulenspiegel, Y. Malcom, and M. S. von Underduk. Polymorphic shellcode engine using spectrum analysis. Phrack, 11(61):published online at http://www.phrack.org (last accessed on Jan. 16, 2004), Aug. 2003.
• 14: Shafi Goldwasser , Yael Tauman Kalai, On the Impossibility of Obfuscation with Auxiliary Input, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.553-562, October 23-25, 2005 [doi>10.1109/SFCS.2005.60]
• 15: A. Gupta and R. Sekar. An approach for detecting self-propagating email using anomaly detection. In G. Vigna, E. Jonsson, and C. Kruegel, editors, Proceedings of the 6th International Symposium on Recent Advances in Intrusion Detection (RAID'03), volume 2820 of Lecture Notes in Computer Science, pages 55--72, Pittsburgh, PA, USA, Sept. 8--10, 2003. Springer Berlin/Heidelberg.
• 16: Intel Corporation. IA-32 Intel Architecture Software Developer's Manual.
• 17: M. Jordan. Dealing with metamorphism. Virus Bulletin, pages 4--6, Oct. 2002.
• 18: J. Kinder, S. Katzenbeisser, C. Schallhart, and H. Veith. Detecting malicious code by model checking. In K. Julisch and C. Krügel, editors, Proceedings of the 2nd International Conference on Intrusion and Malware Detection and Vulnerability Assessment (DIMVA'05), volume 3548 of Lecture Notes in Computer Science, pages 174--187, Vienna, Austria, July 7--8, 2005. Springer Berlin/Heidelberg.
• 19: Jeremy Z. Kolter , Marcus A. Maloof, Learning to detect malicious executables in the wild, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014105]
• 20: W.-J. Li, K. Wang, S. J. Stolfo, and B. Herzog. Fileprints: Identifying file types by n-gram analysis. In Proceedings of the 6th Annual IEEE Systems, Man, and Cybernetics (SMC) Workshop on Information Assurance (IAW'05), pages 64--71, West Point, NY, June 15--17, 2005. United States Military Academy.
• 21: Cullen Linn , Saumya Debray, Obfuscation of executable code to improve resistance to static disassembly, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948149]
• 22: P. Morley. Processing virus collections. In Proceedings of the 2001 Virus Bulletin Conference (VB2001), pages 129--134, Prague, Czech Republic, Sept. 27--28, 2001. Virus Bulletin.
• 23: Carey Nachenberg, Computer virus-antivirus coevolution, Communications of the ACM, v.40 n.1, p.46-51, Jan. 1997 [doi>10.1145/242857.242869]
• 24: Rajaat. Polymorphism. 29A Magazine, 1(3), 1999.
• 25: Symantec Corporation. Symantec Internet Security Threat Report: Trends for January 06--June 06, volume X. Symantec Corporation, Sept. 25, 2006.
• 26: Peter Szor, The Art of Computer Virus Research and Defense, Addison-Wesley Professional, 2005
• 27: P. Ször and P. Ferrie. Hunting for metamorphic. In Proceedings of the 2001 Virus Bulletin Conference (VB2001), pages 123--144, Prague, Czech Republic, Sept. 27--28, 2001. Virus Bulletin.
• 28: Hoeteck Wee, On obfuscating point functions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060669]
• 29: z0mbie. Automated reverse engineering: Mistfall engine. Published online at http://www.madchat.org//vxdevl/papers/vxers/Z0mbie/autorev.txt (last accessed on Sep. 29, 2006).
• 30: z0mbie. Real permutating engine. Published online at http://vx.netlux.org/vx.php?id=er05 (last accessed on Sep. 29, 2006).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Mechanical verification

General Terms:
Languages, Security, Theory, Verification

Keywords:
abstract interpretation, malware detection, obfuscation, trace semantics