Metamorphism: A mathematical challenge for antivirus software

Metamorphic viruses, currently the most advanced computer viruses in the wild, have the unique ability of mutating their own code virtually into infinitely many highly dissimilar copies of themselves that nevertheless have the same functionality. This ability—metamorphism—together with other advanced obfuscation techniques makes these computer viruses virtually undetectable by the antivirus software available in the market today. In this paper, we show that viral metamorphism is fully attainable by the employment of van Wijngaarden grammars. The challenge then for an antivirus software is to embed the Turing machine that decides the language generated by the grammar.