Abstract
This paper deals with metamorphic viruses. More precisely, it examines the use of advanced code obfuscation techniques with respect to metamorphic viruses. Our objective is to evaluate the difficulty of a reliable static detection of viruses that use such obfuscation techniques. Here we extend Spinellis’ result (IEEE Trans. Inform. Theory, 49(1), 280–284, 2003) on the detection complexity of bounded-length polymorphic viruses to metamorphic viruses. In particular, we prove that reliable static detection of a particular category of metamorphic viruses is an \({\mathcal{NP}}\)-complete problem. Then we empirically illustrate our result by constructing a practical obfuscator which could be used by metamorphic viruses in the future to evade detection.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aho A.V., Sethi R. and Ullman J.D. (1986). Compilers: Principles, Techniques and, Tools. Addison-Wesley, Reading, MA
Beaucamps, P., Filiol, E.: On the possibility of practically obfuscating programs—towards a unifed perspective of code protection. J. Comput. Virol. (WTCV’06 Special Issue, Bonfante, G., Marion, J.-Y. eds), 2(4) (2006)
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Crypto ’01, LNCS No.2139, pp. 1–18 (2001)
Bruschi D., Martignoni L. and Monga M. (2006). Detecting self-mutating malware using control-flow graph matching. In: Büschkes, R. and Laskov, P. (eds) Detection of Intrusions and Malware & Vulnerability Assessment, volume 4064 of LNCS, pp 129–143. Springer, Berlin
Bruschi, D., Martignoni, L., Monga, M.: Using code normalization for fighting self-mutating malware. In: Proceedings of the International Symposium of Secure Software Engineering. IEEE Computer Society, Arlington (2006)
Chow, S., Gu, Y., Johnson, H., Zakharov, V.A.: An approach to the obfuscation of control-flow of sequential computer programs. In: ISC ’01: Proceedings of the 4th International Conference on Information Security, pp. 144–155. Springer, London (2001)
Cifuentes, C.: Reverse Compilation Techniques. Ph.D. thesis, Queensland University of Technology, School of Computing Science (1994)
Christodorescu, M., Jha, S.: Static analysis of executables to detect malicious patterns. In: In Proceedings of the 12th USENIX Security Symposium, pp. 169–186 (2003)
Christodorescu, M., Jha, S.: Testing malware detectors. In ISSTA ’04: Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, pp. 34–44. ACM Press, New York (2004)
Cohen, F.: Computational aspects of computer viruses. Rogue programs: viruses, worms and Trojan horses, pp. 324–355 (1990)
Collberg, C., Thomborson, C., Low, D.: A taxonomy of obfuscating transformations. Technical Report 148, Univerity of Auckland, New Zealand (1997)
Collberg, C., Thomborson, C., Low, D.: Manufacturing cheap, resilient, and stealthy opaque constructs. In: Principles of Programming Languages 1998, POPL’98, pp. 184–196 (1998)
Debray S.K., Evans W., Muth R. and De Sutter B. (2000). Compiler techniques for code compaction. ACM 22(2): 378–415
Filiol E. (2006). Advanced Viral Techniques: Mathematical and Algorithmic Aspects. Springer, Berlin
Filiol, E.: Malware pattern scanning schemes secure against black-box analysis. J. Comput. Virol. (EICAR 2006 Special Issue, Broucek, V., Tuner, P. eds), 2(1) (2006)
Jacob, G., Filiol, E., Le Liard, M.: Evaluation methodology and theoretical model for antiviral behavioural detection strategies. J. Comput. Virol. (TCV 2006 Special Issue, Bonfante, G., Marion, J.-Y. eds), 3(1) (2007)
Landi, W.A.: Interprocedural Aliasing in the Presence of Pointers. Ph.D. thesis, New Brunswick, New Jersey, USA (1992)
Lakhotia, A., Kapoor, A., Kumar, E.U.: Are metamorphic viruses really invincible? Virus Bull. (2004)
Ogiso, T., Sakabe, Y., Soshi, M., Miyaji, A.: Softwate tamper resitance based on the difficulty of interprocdeural analysis. In: The Third International Workshop on Information Security Applications, pp. 437–452 (2002)
Preda, M.D., Christodorescu, M., Jha, S., Debray, S.: A semantics-based approach to malware detection. In: Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’07), pp. 377–388, January 17–19, 2007. ACM Press, New York (2007)
Rice, H.G.: Classes of recurively enumerable sets and their decision problems. Transactions of the American Mathematical Society, pp. 358–366 (1953)
Szor, P., Ferrie, P.: Hunting for metamorphic. In: Virus Bulletin Conférence, September 2001
Spinellis D. (2003). Reliable identification of bounded-length viruses is np-complete. IEEE Trans. Inform. Theory 49(1): 280–284
Sung, A.H., Xu, J., Chavez, P., Mukkamala, S.: Static analyzer of vicious executables(save). In: Proceedings of the 20th Annual Computer Security Applications Conference (ACSAC’04). IEEE (2004)
Szor P. (2005). The Art of Computer Virus Research and Defense. Addison-Wesley, Reading, MA
Wang, C., Hill, J., Knight, J., Davidson, J.: Software tamper resistance: Obstructing static analysis of programs. Technical Report CS-2000-12, University of Virginia (2000)
Walenstein, A., Mathur, R., Chouchane, M.R., Lakhotia, A.: Normalizing metamorphic malware using term rewriting. SCAM 2006: The 6th IEEE Workshop Source Code Analysis and Manipulation, pp. 75–84 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Borello, JM., Mé, L. Code obfuscation techniques for metamorphic viruses. J Comput Virol 4, 211–220 (2008). https://doi.org/10.1007/s11416-008-0084-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11416-008-0084-2