A Non-context-free Metamorphic Virus

Last wednesday’s session was an enlightening view of the dark and mysterious world of computer viruses. Mistral was our guide, delivering a detailed and intriguing talk on the metamorphic virus he has been developing for his Part II Project

Given the wide misuse of the term by the media, it is worth clarifying what is actually meant by a virus, in the technical sense.

Virus (pl. viruses) is a program that can ‘infect’ other programs by modifying them to include a possibly evolved copy of itself.

– Fred Cohen

With this definition in mind, we can move onto metamorphic viruses, which are viruses which mutate their code in some way upon each infection.

To wet out appetite, Mistral conjured up screenshots of historic viruses (pictured), giving a brief history of computer viruses. The earliest viruses were mainly for the purposes of a joke and it was typically the intention of the creator to make it obvious to the user that their machine had been compromised. This usually took the form of displaying messages or images to the user. Indeed, mistral gave a demo of a DOS virus which he had written (!) which informed users that their PC had taken a ‘holiday’ and would then proceed to lock the PC for the entire day!


Mistral went on to describe various techniques deployed by anti-virus engines which attempt to detect infected processes and files on the system. He covered a range of topics, covering simple techniques such as simply hashing the whole (or parts of) the file to far more advanced techniques, including the use of finite automata to model and detect infections.

He explained the principle components of a metamorphic virus and how his virus has been designed. This list of components included a disassembler, assembler and linker as well as the analysis engine and transformation system.

The first step in the infection process if to generate the first patient, which is taken by infecting the first process with your virus, which would have been compiled into an executable. This form of the virus is the one which is transmitted and will evolve continually on each new infection. The virus will need to disassemble itself at each step, into some internal representation, analyse and transform this representation before lining and assembling the result into the new infected process. This is a huge topic but Mistral delivered detailed examples including instruction permutation and constant folding/unfolding.

The final part of Mistral’s talk involved a discussion of formal languages and automata and how viruses can be classified:

  • Language: Virus family
  • Word: Virus Instance
  • Grammar: Metamorphic engine
  • Automata: metamorphic virus detector

It turns out that there is a weakness in the design of such detection schemes and Mistral presented some of his ideas about how this can be overcome.

Overall, a thoroughly enjoyable talk, with some extremely interesting food for thought!