Metamorphism, Formal Grammars and Undecidable Code Mutation

Authors: Eric Filiol

Abstract:

This paper presents a formalisation of the different existing code mutation techniques (polymorphism and metamorphism) by means of formal grammars. While very few theoretical results are known about the detection complexity of viral mutation techniques, we exhaustively address this critical issue by considering the Chomsky classification of formal grammars. This enables us to determine which family of code mutation techniques are likely to be detected or on the contrary are bound to remain undetected. As an illustration we then present, on a formal basis, a proof-of-concept metamorphic mutation engine denoted PB MOT, whose detection has been proven to be undecidable.

Keywords: Polymorphism, Metamorphism, Formal Grammars, Formal Languages, Language Decision, Code Mutation, Word Problem

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329887

References:

[1] Beaucamps P., Filiol E. (2006), On the possibility of practically obfuscating programs - Towards a unified perspective of code protection, Journal in Computer Virology, (2)-4, WTCV-06 Special Issue, G. Bonfante & J.-Y. Marion eds.
[2] Carton O. (2006), Langages formels, calculabilite et complexite, Cours de l- Ecole Normale Sup'erieure. Available on http://www. jussieu.fr/˜carton/Enseignement/Complexite/ENS/ Support/
[3] Chomsky N. (1956), Three models for the description of languages, IRE Transactions on Information Theory, 2, pp. 113-124.
[4] Chomsky N. (1969), On certain formal properties of grammars, Information and Control, 2, pp. 137-167.
[5] Cohen F. (1986), Computer viruses, Ph. D thesis, University of Southern California, January 1986.
[6] Filiol E. (2005), Computer viruses : from theory to applications, IRIS International Series, Springer Verlag France, ISBN 2-287-23939-1.
[7] Filiol E. (2006), Malware Pattern Scanning Schemes Secure Against Black-box Analysis. In: Proceedings of the 15th EICAR Conference. The extended version has been published in Journal in Computer Virology, EICAR 2006 Special Issue, Vol. 2, Nr. 1, pp. 35-50.
[8] Filiol E., Jacob G. et Le Liard M. (2006), Evaluation Methodology and Theoretical Model for Antiviral Behavioural Detection Strategies, Journal in Computer Virology, (3)-1, WTCV-06 Special Issue, G. Bonfante & J.-Y. Marion eds.
[9] Filiol E. (2007), Techniques virales avancees, Collection IRIS, Springer Verlag France. An English translation is pending and will be in print in mid 2007.
[10] Grune D. (1984), How to Produce All Sentences From a Two-level Grammar, Information Processing Letters, 19, pp. 181-185.
[11] Hopcroft J. E., Motwani R. and Ullman J. D. (2006), Introduction to Automata Theory, Languages and Computation, 3rd ed., Addison Wesley.
[12] Jones N. D. (1997), Computability and Complexity, MIT Press.
[13] Lakhotia A., Kapoor A and Kumar E. U. (2004), Are Metamorphic Viruses Really Invicible? Part1, Virus Bulletin, 12, pp. 5-7.
[14] Papadimitriou C. H. (1995), Computational Complexity, Addison Wesley, ISBN 0-201-53082-1.
[15] Post E. (1947), Recursive unsolvability of a problem of Thue, Journal of Symbolic Logic, 12, pp. 1-11.
[16] Qozah (1999), Polymorphism and grammars, 29A E-zine, 4, http: //www.29a.net/.
[17] Spinellis D. (2003), Reliable Identification of Bounded-length Viruses is NP-complete, IEEE Transactions in Information Theory, Vol. 49, No. 1, pp. 280-284.
[18] Tzeitzin G.C (1958), Associative calculus with an unsolvable calculus problem, Tr. Math. Inst. Steklov Akad. Nauk SSSR, 52, pp. 172-189.
[19] van Wijngaarden A., Mailloux B.J., Peck J.E.L., Koster C.H.A., Sintzoff M., Lindsey C.H., Meertens L.G. and Fisker R.G. (1975), Revised Report on the Algoithmic language ALGOL 68, Acta Informatica, 5, pp. 1-236.
[20] Zuo Z. et Zhou M. (2004), Some further theoretical results about computer viruses, The Computer Journal, Vol. 47, No. 6.
[21] Zuo Z, Zhou M. (2005), On the Time Complexity of Computer Viruses, IEEE Transactions in Information Theory, (51), 8. World Academy of Science, Engineering and Technology 2 2007