Constructing malware normalizers using term rewriting
Tóm tắt
A malware mutation engine is able to transform a malicious program to create a different version of the program. Such mutation engines are used at distribution sites or in self-propagating malware in order to create variation in the distributed programs. Program normalization is a way to remove variety introduced by mutation engines, and can thus simplify the problem of detecting variant strains. This paper introduces the “normalizer construction problem” (NCP), and formalizes a restricted form of the problem called “NCP=”, which assumes a model of the engine is already known in the form of a term rewriting system. It is shown that even this restricted version of the problem is undecidable. A procedure is provided that can, in certain cases, automatically solve NCP= from the model of the engine. This procedure is analyzed in conjunction with term rewriting theory to create a list of distinct classes of normalizer construction problems. These classes yield a list of possible attack vectors. Three strategies are defined for approximate solutions of NCP=, and an analysis is provided of the risks they entail. A case study using the
$${\tt W32.Evol}$$
virus suggests the approximations may be effective in practice for countering mutated malware.
Tài liệu tham khảo
VX heavens. (http://vx.netlux.org)
Aho, A., Sethi, R., Ullman, J.: Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading (1986)
Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, London (1998)
Baxter, I.D., Yahin, A., Moura, L.M.D., Sant’Anna, M., Bier, L.: Clone detection using abstract syntax trees. In: Proceedings of the 1998 International Conference on Software Maintenance (CSM ’98), pp. 368–377 (1998)
Benny. Benny’s metamorphic engine for Win32. (http://vx.netlux.org/29a/29a-6/29a-6.316)
Bruschi, D., Martignoni, L., Monga, M.: Using code normalization for fighting self-mutating malware. In: Proceedings of International Symposium on Secure Software Engineering. IEEE, Washington, DC (2006)
Chess, D., White, S.: An undetectable computer virus. In: Proceedings of Virus Bulletin Conference, Sept 2000
Christodorescu, M., Jha, S., Seshia, S.A., Song, D., Bryant, R.E.: Semantics-aware malware detection. In: 2005 IEEE Symposium on Security and Privacy, pp. 32– 46 (2005)
Christodorescu, M., Kinder, J., Jha, S., Katzenbeisser, S., Veith, H.: Malware normalization. Technical Report 1539. University of Wisconsin, Madison, Nov. 2005
Cohen, F.: Computational aspects of computer viruses. Comput. Secur. 8(4), 325–344 (1989)
Collberg, C.S., Thomborson, C.: Watermarking, tamper-proofing, and obfuscation tools for software protection. IEEE Trans. Softw. Eng. 28(8), 735–746 (2002)
Cordy, J.R.: TXL—a language for programming language tools and applications. In: ACM 4th International Workshop on LTDA. Electronic Notes in Theoretical Computer Science, vol. 110, pp. 3–31. Springer, Heidelberg (2004)
Dave, M.A.: Compiler verification: a bibliography. SIGSOFT Softw. Eng. Notes 28(6), 2 (2003)
Filiol, É.: Metamorphism, formal grammars, and undecidable code mutation. Int. J. Comput. Sci. 2(1), Nov 2007
Hong Zuo, Z., xin Zhu, Q., tian Zhou, M.: On the time complexity of computer viruses. IEEE Trans. Inf. Theory 51(8), Aug 2005
Kamiya, T., Kusumoto, S., Inoue, K.: A multilinguistic token-based code clone detection system for large scale source code. Trans. Softw. Eng. 8(7), 654–670 (2002)
Kinder, J., Katzenbeisser, S., Schallhart, C., Veith, H.: Detecting malicious code by model checking. In: Julisch, K., Kruegel, C. (eds.) Intrusion and Malware Detection and Vulnerability Assessment: Second International Conference (DIMVA 2005). Lecture Notes in Computer Science, pp. 174. Springer, Heidelberg (2005)
Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebras. In: Automation of Reasoning 2: Classical Papers on Computational Logic 1967–1970, pp. 342–376. Springer, Heidelberg (1983)
Kruegel, C., Kirda, E., Mutz, D., Robertson, W., Vigna, G.: Polymorphic worm detection using structural information of executables. In: Valdes, A., Zamboni, D. (eds.) Recent Advances in Intrusion Detection: 8th International Symposium (RAID 2005). Lecture Notes in Computer Science, vol. 3858, pp. 206–226. Springer, Heidelberg (2006)
Lakhotia, A., Kapoor, A., Kumar, E.U.: Are metamorphic viruses really invincible?—Part II. Virus Bull. pp. 9–12, Jan 2005
Lakhotia, A., Mohammed, M.: Imposing order on program statements and its implications to AV scanners. In: Proceedings of the 11th IEEE Working Conference on Reverse Engineering, pp. 161–171, Nov 2004
Landi, W.: Undecidability of static analysis. ACM Lett. Program. Lang. Syst. 1(4), 323–337 (1992)
Mathur, R.: Normalizing metamorphic malware using term-rewriting. Master’s Thesis, Center for Advanced Computer Studies, University of Louisiana at Lafayette, Dec 2006
Müller, A.J., Shinohara, T.: On approximate matching of programs for protecting libre software. In: CASCON ’06: Proceedings of the 2006 conference of the Center for Advanced Studies on Collaborative Research, pp. 21–36. ACM Press, New York (2006)
Nachenberg, C.: Computer virus-antivirus coevolution. Commun. ACM 40(1), 47–51 (1997)
Singh, P.K., Moinuddin, M., Lakhotia, A.: Using static analysis and verification for analyzing virus and worm programs. In: Proceedings of the 2nd European Conference on Information Warfare and Security, pp. 281–292 (2003)
Skoudis, E.: Malware: Fighting Malicious Code. Prentice-Hall, Englewood Cliffs (2004)
Symantec: W32.Evol security response writeup. http://www.symantec.com/security_response/writeup.jsp?docid=2000-122010-0045-99, checked 15 Aug 2007
Ször, P.: The Art of Computer Virus Research and Defense. Symantec Press, Austin (2005)
Ször, P., Ferrie, P.: Hunting for metamorphic. In: 11th International Virus Bulletin Conference (2001)
The Mental Driller. Metamorphism in practice. (http://vx.netlux.org/29a/29a-6/29a-6.205)
Visser, E.: A survey of rewriting strategies in program transformation systems. In: Workshop on Reduction Strategies in Rewriting and Programming (WRS’01). Electronic Notes in Theoretical Computer Science, vol. 57 (2001)
Walenstein, A., Mathur, R., Chouchane, M.R., Lakhotia, A.: The design space of metamorphic malware. In: Proceedings of the 2nd International Conference on Information Warfare, Monterey, Mar 2007
Z0mbie: Automated reverse engineering: Mistfall engine. (http://vx.netlux.org/lib/vzo21.html)
Z0mbie: Some ideas about metamorphism. (http://vx.netlux.org/lib/vzo20.html)