MtE (Mutation Engine) Review

Mutation Engine was the first polymorphic generator, written by the Dark Avenger. MtE was put into circulation in 1991. It is the most widespread polymorphic generator, and has been incorporated to 33 different viruses.

Though revolutionary in its time, Mutation Engine is currently somewhat outdated. Practically all anti-virus products can detect MtE-hidden viruses. Nevertheless, MtE continues to be a source of inspiration for people aspiring to write polymorphic generators - for example, almost all generators written after MtE mimic the documentation provided with MtE.

MtE v0.91's size is 2048 bytes.

The following is a 1992 report on MtE:

    Mutation Engine Report
    prepared by
    Tarkan Yetiser

    TABLE of CONTENTS

I. Mutation Engine and Viruses. . . . . . . . . . . . . . . . . . .

II. How to Catch Viruses and MtE-based Viruses . . . . . . . . . . .

III. Mutation Types and Detection Algorithms. . . . . . . . . . . . .

IV. Live Tests and Results . . . . . . . . . . . . . . . . . . . . .
A. Comments on Test Results . . . . . . . . . . . . . . . .

V. A Simple Message . . . . . . . . . . . . . . . . . . . . . . . .

I. Mutation Engine and Viruses

We have analyzed the so-called MtE (Mutation Engine by a "Dark Avenger" from Bulgaria), and sample viruses based on it; namely, Pogue and Dedicated. We have also conducted tests to examine what kind of a potential this miscreant has, and collected empirical data on how popular scanners deal with the MtE. We have also implemented a little program (CatchMtE) that can recognize MtE-based code using an algorithmic technique. The program in executable form is available free of charge as a service to the public. Due to possible misuse, the source code and a more detailed (at the opcode and bit-mask level) analysis with decryptor samples and algorithms necessary to detect MtE will be made available in a limited fashion. Under no circumstances, actual virus samples will be provided; except the missed samples can be sent to known anti-viral product developers who wish to enhance their programs.

For those who are not familiar with the MtE, some preliminary info will be presented first:

MtE is NOT a virus per se, but an object module that can be linked into a virus to give it polymorphic capabilities. MtE expects to be called as a routine that can encrypt a certain portion of code and can generate a suitable decryption routine. It uses a random number generator to vary each mutation so that it will not be possible to recognize the new variant by using simple scanning techniques. The random number generator is not part of the MtE object module. A sample pseudo-random number generator is included with the archive Dark Avenger distributes. A virus writer could also supply his own random number generator.

Part 2.

Though all this may sound ordinary, MtE got so much attention not because it is just another encryptive virus but because it can provide even simple viruses with a feature that makes it difficult to scan for them. MtE is just like a library routine that you link into your virus and call when needed. It is a little over 2K in an object module named MtE.OBJ. A person who calls himself "Dark Avenger" claims to have developed MtE, and distributes it by uploading to BBSes in Bulgaria. The archive contains a fairly detailed documentation on how to use MtE, and even includes a demonstration virus, a non-resident COM infector known as "Dedicated". Shortly after MtE made its appearance, a modified copy of this virus called "Fear" is also seen. Why this person is engaged in such potentially harmful activity, or how he/she gets away with it is not something we know about. Curious individuals who would like to learn more about the history of virus production in Bulgaria and other social as well as technical issues are invited to read an excellent paper written by anti-virus researcher Mr. Vesselin Bontchev of Virus Testing Center, University of Hamburg. The paper is titled "Bulgarian Virus Factory", and it is available via anonymous FTP. It provides insight into some of the cultural aspects of the virus underground in Bulgaria. Mr. Bontchev's contribution to anti-virus research is much appreciated; otherwise, we probably would have never known what goes on inside the Bulgarian virus factories.

II. How to Catch Viruses and MtE-based Viruses

Scanning for many known viruses is usually a trivial task. You disassemble a sample, extract a sequence of bytes that would exist in each infected executable object, put it into a pattern matching engine, and then look for that pattern in executable objects that that virus is known to target. This method proved to be quite useful in fighting many viruses seen in the wild. Assuming a carefully chosen scan string, you can find the virus easily without too many false positives. Not so for polymorphic viruses.
These viruses try to defeat common scanning methods. They keep their body encrypted to defy analysis, and encrypt the new copy inserted into an executable object using a different key so that it will "look" as if a different virus infection has occurred. However, even these viruses require a plaintext code that will decrypt the rest of the virus. Scanners can use strings extracted from the plaintext portion of the virus to identify them. It is usually necessary to include wildcard bytes (don't-care bytes) to be able to deal with the varying parts of the decryption routine. Naturally, false alarms are more likely to occur. MtE is more advanced than such viruses seen before.
We would like to emphasize that the contents of each mutation and the corresponding decryption routine MtE generates is far too variable to extract a simple (or even wildcard) scan string. It is necessary to analyze the MtE itself as well as many sample mutations. After that, certain characteristics of the code MtE generates can be used as telltale signs to detect its presence. Avoiding false positives while maintaining 100% detection ratio is quite difficult.
Armed with an 80x86 instruction set guide (we used Turbo Assembler 3.0 Quick Reference Guide), and a good disassembler (we used Mr. Zandt's DIS86 available via anonymous FTP), and a few known viruses based on MtE (Pogue and Dedicated with payload removed), we analyzed the MtE code, and the mutations generated. Tests were conducted on a 40Mhz 386 with a 100 meg HD and MS-DOS 5.0, and a 4.77Mhz IBM/XT with a 30 meg HD and PC-DOS 3.3 installed. A simple program that generated decoys (small, fully functional programs) was used to create a large number of samples. In the case of Pogue, the virus was allowed to remain resident and infect each decoy program as it is created. Since the Dedicated virus is not resident, it was necessary to create decoys first and then infect them by running the virus (infects in the current directory). After the tests, we archived the samples and stored them on floppy diskettes, and removed them from the hard drives of the test machines.
In the Intel 80x86 architecture, it is possible to express a computation in very dissimilar ways. This is possible because certain registers can be substituted in place of another one and still achieve the same result. For example, you can index an array by using SI, DI, BP or BX registers. Or you could XOR a certain value at a given memory location by loading that value in AX, BX, CX or DX first, and performing the XOR on that register, and then putting the result back into memory, etc. Even other possibilities exist. When stepping through elements in an array, you can increment the index register by ADDing to it, INCing it, or ADDing and then SUBtracting from it. It should be clear that such flexibility helps MtE significantly. Of course, variability is something string scanners do not handle too well, since there are many combinations to search for.
MtE goes even further than that. The size of the decryption routine is also variable, making it infeasible to assume certain things that would hold for many polymorphic viruses. It also sets up a lengthy sequence of redundant instructions before the decryptor enters the decryption loop.

Part 3

For over 90% of the mutations, MtE generates a convoluted 16-bit XOR-type encryption; however, in many cases it uses indirect ways to apply the XOR mask to a memory value. For example, it computes the mask, and then gets the value to be decrypted into a register, applies the mask and put the result back into that memory location. Besides, memory access is done using many different instructions such as MOV and XCHG. There are also many redundant instructions peppered freely throughout the decryptor.
In some cases (5.5%), MtE generates a decryptor with a null effect. The decryptor does not actually decrypt anything, and the virus code is in plaintext. The frequency of such cases seems to depend on the random number generator. It is funny to note that some popular scanners misidentify such extreme cases where the virus is not even encrypted. To handle these mutations, it is sufficient to extract a signature from the MtE itself. It is also possible to extract one from known MtE-based viruses and identify the virus directly. At any rate, a scan string from MtE itself should be used in case a future virus creates a plaintext variant.
We must also mention that even these plaintext mutations contained a fully working copy of MtE. They successfully propagated and generated encrypted mutations in future generations. MtE appears to generate correct code in all cases. The deviation between new generations started using plaintext parents and new generations started using encrypted parents was negligible.

III. Mutation Types and Detection Algorithms

MtE generates 4 "types" of mutations. They are as follows:

    1.  Double-reference (detectable using Method-1) (  91.0% )
    2.  SUB-NEG (detectable using Method-2)   (   2.0% )
    3.  Single-reference (detectable using Method-3) (   1.5% )
    4.  Plaintext or no-reference  (   5.5% )

By implementing three algorithms and one scan string for the plain mutations, it is possible to recognize MtE-based viruses while keeping false positives to an acceptable level. We have one such program that achieved 100% hit rate during our tests. Some others also claim 100% hit rate; and we have tested them as well.
A more detailed analysis of mutation types is not made public due to possible misuse of such information.

IV. Live Tests and Results

          Test #1     Base Virus Name: Dedicated

                                 SCAN 91     F-PROT 2.04       CatchMtE 1.0

          by Name (1)             67                69          60
          as MtE  (2)             933               931         940
          misidentified           -0                -0          N/A
          missed                  -0                -0          -0
          Hit Rate                100%              100%        100%

    (1)  SCAN91 --> [Mut],  F-PROT 2.04 --> Dedicated, CatchMtE --> Dedicated
    (2)  SCAN91 --> [DAME], F-PROT 2.04 --> MtE,       CatchMtE --> MtE-based

          Test #2     Base Virus Name: Pogue

                                 SCAN 91     F-PROT 2.04       CatchMtE 1.0

          by Name (1)             0           0                 56
          as MtE  (2)             935         936               944
          misidentified (3)       -65         -61               N/A
          missed                  -0          -3                -0
          Hit Rate                93.5%       93.6%             100%

    (1)  SCAN91 --> N/A,  F-PROT 2.04 --> N/A,    CatchMtE --> Pogue
    (2)  SCAN91 --> [DAME], F-PROT 2.04 --> MtE,  CatchMtE --> MtE-based
    (3)  SCAN91 --> [7S], F-PROT 2.04 --> Gotcha, CatchMtE --> N/A

A. Comments on Test Results

It seems that both F-PROT 2.04 and SCAN 91 misidentify some Pogue mutations that are in plaintext. F-PROT "quickscan" missed ALL mutations. You are advised to use SECURE scan mode of this product. The extra speed comes with 0% hit rate on MtE-based viruses!
F-PROT 2.04 missed three encrypted Pogue mutations. We examined these samples and found them to be of Type-3, and detectable using Method-3. The samples worked as expected. One of those three that were missed was called "suspicious" and guessed to be a variant of the Gotcha virus. We can only speculate that F-PROT lacks Method-3 detection algorithm and uses a heuristic in such cases. Surprisingly, Virx 2.3 missed one of these same mutations. Due to annoying user interface, we were unable to include Virx 2.3 in our full test suite.
It should be noted that misidentification of 6% of Pogue mutations is a little alarming. All these misidentified mutations were found to be working and capable of generating new mutations.

V. A Simple Message

It is dangerous to assume that scanning is adequate since there are some products that can detect MtE-based viruses 100% of the time. We identified at least two ways to make MtE less predictable. Of course, such information will not be disseminated. However, considering the availability of MtE to the hackers all around the world, and the "glory" Dark Avenger will enjoy due to media hype, it's only a matter of time such improvements will be discovered by irresponsible individuals. Besides, this may start a new trend among virus writers to create things like MtE. Keeping up with new virus signatures was hard enough (though manageable), but keeping up with many mutation engines is not going to be trivial. Unfortunately, locking up these "mutant engineers" is not a practical solution, and not even legally possible in many parts of the world.
The message is clear. The first line of defense against viruses is NOT using scanners. Although they proved to be very useful, you are highly encouraged to consider other approaches such as integrity checkers as a first line of defense. Even the less sophisticated integrity checkers have a better chance to catch mutating viruses, long before their developers get a chance to analyze the virus samples. The reason is that viruses have a tendency to modify existing code to propagate in most cases. Their spread can be controlled using a non-virus-specific solution that concentrates on the main characteristic of most viruses. Such an approach is not only more cost-effective but also more secure. If your company still relies on a virus scanner to protect its PC- based computing resources against viruses, you are walking on thin ice.