Solving the metamorphic puzzle

Metamorphic viruses have posed a challenge for the anti-virus industry for quite some time. There are several different techniques that can be used by metamorphic viruses to obfuscate their code – from simple register swapping to the more complex heavy code mutation. This article focuses on a number of metamorphic techniques used by 32-bit viruses under the Windows environment and highlights different methods for detecting them.

Over the years, viruses have demonstrated a number of obfuscation techniques to escape detection by anti-virus scanners.

Encryption is the simplest form of code obfuscation. In this technique, a constant key is used to decrypt the encrypted virus body. The virus uses the same key to encrypt all the files that it infects. The decryptor is placed at the start of the virus code and the encrypted data follows. However, since the decryption code is constant, it can be used to recognise the virus, making detection relatively easy.

Oligomorphic viruses differ from simple encrypted viruses because they have a varying, but finite number of decryptors in every infection generation. The method used for detecting simple encrypted viruses cannot be applied to this type of virus because the decryptor is not constant. Instead, the virus can be decrypted on-the-fly. This is achieved by capturing modifications made in consecutive memory locations – a characteristic of viruses that decrypt their virus body.

Polymorphic viruses produce a nearly infinite number of new decryptors with a variety of encryption methods to encrypt the constant virus code for every infection. Since the virus code remains constant after decryption, the detection solution used for oligomorphic viruses can be applied.

However, a more sophisticated method for detecting these viruses is through the use of a 32-bit emulator, which allows virus codes to execute in a controlled environment. The virus codes are then monitored and examined periodically, especially when certain instructions modify portions of the code. However, emulation uses a lot of memory operations and CPU resources. Another technique, called x-raying, allows us to see through the layers of encryption. Using this method, one can acquire the decryption key and decrypt the virus part that needs to be matched. This is applicable if the encryption algorithms are finite or have certain weaknesses.

Of all the code obfuscation methods that exist today, metamorphism is the most difficult to deal with. A good description of metamorphic viruses is given in [1]. Metamorphic viruses have neither a decryptor, nor a constant virus body. However, they are able to create new generations that look different. They do not use a constant data area filled with string constants but have a single code body that carries data as code.

The evolution of metamorphic viruses in the Win32 environment makes the life of the anti-virus researcher a little more challenging. Some metamorphic viruses avoid storing strings in their normal form to prevent easy detection. In this scenario, scan string and range scanning are no use as detection techniques. Instead, techniques such as file structure analysis, code analysis, and behaviour analysis must be used.

As mentioned in [1], in order to detect a metamorphic virus perfectly, a detection routine must be capable of regenerating the essential instruction set of the virus body from the actual instance of the infection. [1] also introduces some of the techniques used to detect metamorphic viruses. In this article, we will enumerate and discuss in detail how each detection technique works and elaborate on their corresponding advantages and disadvantages.

File structure analysis, also known as geometric scanning, involves detecting the modifications that are made by the virus in the structure of the victim file. Some anti-virus experts also call this method 'shape heuristics', owing to the fact that it does not ensure an exact detection and is prone to false alarms.

Win32 binary viruses commonly rely on infection markers to flag files that have already been infected, thus avoiding multiple infections. For example, in the case of Bistro.B, an infected file has a high-byte value 0x51 at the minor linker version field. Such infection markers can also be very useful from the point of view of detection, since they can be used as initial filter signatures, narrowing down the number of files to be scanned.

However, a filter signature alone is not sufficient to ensure error-free virus detection. A better approach is to combine geometric scanning with other detection techniques.

Wildcards and the half-byte detection technique can be used to detect simple metamorphic techniques such as register swapping and op-code changing. Let's look at an example.

Figure 1 shows a code fragment of a Regswap infection.

BE04000000      mov   esi,000000004 ;” ?”
8BDD            mov   ebx,ebp
B90C000000      mov   ecx,00000000C ;” ?”
81C088000000    add   eax,000000088 ;” ê”
8B38            mov   edi,[eax]
89BC8B18110000  mov   [ebx][ecx]*4[00001118],edi
2BC6            sub   eax,esi
49              dec   ecx

BB04000000      mov   ebx,000000004 ;” ?”
8BCD            mov   ecx,ebp
BF0C000000      mov   edi,00000000C ;” ?”
81C088000000    add   eax,000000088 ;” ê”
8B30            mov   esi,[eax]
89B4B920110000  mov   [ecx][edi]*4[00001120],esi
2BC3            sub   eax,ebx
4F              dec   edi

Figure 1: Regswap infection code fragment.

The parts shown in bold are the common virus codes for every generation. These are good candidates for a detection pattern. Half-byte detection would be appropriate for this type of infection if the scanning engine supports it.

A new metamorphic technique emerged when variants of the Zmorph virus appeared. In this case, a piece of polymorphic code is positioned at the entry point of the infected file. This decrypts the virus one instruction at a time and rebuilds it by pushing the result into the stack memory. After the last instruction has been decrypted, control is transferred to the start of the virus body, which is also located in the stack memory.

In order to detect this type of metamorphism, emulators must be able to detect stack decryption. The emulator must monitor the memory that is accessed by the virus. Once control is transferred to the stack memory, the emulator detects it and dumps the whole decrypted virus code for identification.

Note that monitoring the memory locations accessed by the virus while emulating has a significant impact on performance and thus filter checking should be applied first.

Another level of metamorphism was introduced when Win32 viruses such as Ghost and Zperm were released. Here, the virus code may be constant but metamorphosis is achieved by dividing the code into frames and infections – these frames are positioned randomly and connected by branch instructions to maintain the process flow. The diagram shown in Figure 2 illustrates this.

Figure 2: Subroutine depermutation.

The branch instructions could be a simple relative jump (0xe9, 0xea, 0xeb) or a complex transfer of control (i.e. push val32; ret). As shown in Figure 2, the control flow remains the same for the two infections. The level of permutation varies depending on the number of subroutines that constitute the whole virus. For instance, the code of a virus that has eight subroutines can mutate by eight or 40,320 ways. The level of permutation can be computed as n (where n refers to the number of subroutines/frames). To make detection more difficult, most viruses insert garbage instructions between frames.

The Zperm virus employs a Real Permutating Engine (RPME) to accomplish its sophisticated levels of metamorphism. To counter this method, we need to perform partial emulation (emulation of branch instructions only) to reconstruct the virus code in its form prior to permutation. Figure 3 shows the process of rebuilding the permutated virus code:

Permutated code   Decoding procedure

    aaa1          1.   decode aaa1

    aaa2          2.   decode aaa2

    aaa3          3.   decode aaa3

    jmp @A        4.   change IP to @A

    bbb1          5.   decode aaa7

    bbb2          6.   decode aaa8

@B: aaa4          7.   decode aaa9

    aaa5          8.   change IP to @B

    aaa6          9.   decode aaa4

    jmp @C        10.  decode aaa5

    bbb3          11.  decode aaa6

    bbb4          12.  change IP to @C

@A: aaa7          13.  decode aaa10

    aaa8          14.  decode aaa11

    aaa9          15.  decode aaa12

    jmp @B        16.  decode ret

@D: aaa13

     aaa14

     ret

     bbb5

@C:  aaa10

     aaa11

     aaa12

     ret

Figure 3: Permutated virus rebuilding process.

The challenge here lies in deciding when to stop decoding and in ensuring that the virus codes are thoroughly exhausted. With the help of the decode table and IP address table, this can be done easily. This technique can be very effective for rebuilding the code as well as removing garbage.

An 'improved' version of Bistro was released some time after the original. In addition to an RPME engine, it has another anti-emulation technique: the random code insertion technique (aka macho engine). It inserts do-nothing instructions and dummy loops randomly before the decryptor codes. As a consequence, some emulators fail to rebuild the real virus codes, instead emulating millions of do-nothing instructions.

To avoid this problem, an emulator must have a means of identifying do-nothing instructions and dummy loops and must be able to skip them as encountered.

In the case of Bistro, the macho engine can be detected by monitoring the movement of IP and checking the 'WRITE' operations. Generic detection of all Win32 viruses that utilize macho engines is possible using this method. However, a drawback of the method is that it is also susceptible to false positives.

One of the most efficient ways to deal with different types of obfuscation is the use of disassembly code to match the pattern (regular expression) using Deterministic Finite Automata, or DFA.

In its simplest terms, a regular expression is a formula for matching strings that follow a pattern. It provides a mechanism for selecting specific strings from a set of character strings. DFA is a transition table containing states and their corresponding next states.

Before digging into the details, we must define some terminologies:

As an overview, this detection method simply treats the virus file as a series of disassembly codes (alphabets) that can be matched against a database of existing virus disassembly codes.

In this technique, the scanning of a file is terminated automatically when the current disassembly code does not match any of the disassembly codes in the database or when the disassembly code does not belong to the acceptable list of instructions for a certain virus. Thus, this solution is relatively fast compared to others.

Two main components are involved in this solution: the builder and the simulator. The builder creates the automaton of the virus using the grammar pattern, while the simulator performs the automaton matching and conditional test using RegEx operators during file scanning.

The grammar pattern contains information on normalization (a set of garbage or negative filters) as well as information on how to detect the malicious file (Grammar and Accepted instructions). It uses regular expression where each item represents an assembly instruction.

An opcode can be any Intel IA-32 assembly instruction and an operand can be any of the following:

In wildcard instructions, the opcode and the operand vary. Possible values for the register operand are REG, REG8, REG16 and REG32, while the possible values for the immediate operand are IMM, IMM16 and IMM32. For memory operands, MEM, MEM16 and MEM32 are the possible values. Assembly instructions are associated through operators such as start (*), plus (+), qmark (?), or (|) and explicit dot (.).

As shown in Figure 4, the pattern source format is processed by the DFA builder to produce automatons. Each assembly instruction is assigned a unique ID for easy matching and added to the corresponding garbage, accept and grammar list. Since our pattern is composed of operators, it has to deal with precedence. For easy processing, the pattern can be converted from infix expression to postfix expression before creating the DFA patterns.

Figure 4: The DFA building process.

The simulator is responsible for scanning files for malicious content. It has four sub-components: a disassembler, depermutator, normalizer and DFA simulator. The input data is pre-processed by the first three sub-components before they are passed to the DFA simulator.

Figure 5 shows the simulator component.

Figure 5: The DFA simulation process.

The disassembler part performs the conversion from binary code to assembly code, while the depermutator component connects the subroutines of the permutated virus. The normalizer explicitly disregards garbage instructions using the data (Garbage section) from the pattern.

DFA simulation is the final step of the process. Using the input symbol derived from the file being scanned and the automaton created in the building process, the DFA simulator scans the file for malicious content.

For every input symbol, the simulator checks for the matching states and updates them accordingly. Wildcards and conflicts in pattern are resolved by having a set of transition states. When an input symbol is rejected, the DFA simulator checks the entries in the Accept section. If there is a match, the state is toggled back as if it were not rejected. It then reads the next input and continues the simulation. Once the final and accepting state is reached, the file is tagged as a virus.

This particular detection solution covers almost all of the code obfuscation techniques discussed above. Encrypted viruses can be detected by creating a virus signature based on the decryptor's disassembly code. Oligomorphic and polymorphic viruses can be addressed by creating an automaton based on the virus' alphabets or the possible set of instructions that it can produce during infection.

Although polymorphic viruses are capable of producing an almost infinite number of decryptors for each infection, these decryptors can still be subdivided into manageable parts, which enable the creation of a set of automatons. On most occasions, these viruses can be detected generically through detection of the polymorphic engine.

Conveniently, this method also covers the detection of permutating viruses through the depermutator component, which connects the subroutines of the permutated virus. Unlike emulators, which are known to be slow and cannot handle viruses that generate do-nothing loops, this technique simply treats the virus as a series of disassembly codes that can be matched with a database of existing virus disassembly codes. For more sophisticated viruses, like Zmist and Etap, this detection method works best if coupled with a smart emulator.

Code transformation is a method of converting mutated instructions to the simplest form where common codes exhibited by the virus can be captured. The combinations of instructions are transformed to an equivalent but simple form.

Etap (aka Simile) is the first metamorphic virus where this type of scanning technology is applicable. Let’s have a quick look at how Etap achieves metamorphism through heavy code transformation.

Etap, like Zmist, implements a combination of metamorphic techniques – entry point obfuscation, permutation, and heavy code mutation via shrinking and expanding techniques. The shrinking and expanding of virus codes is also known as the 'accordion model'. To accomplish such code mutation, this virus had gone through several steps as illustrated below:

Disassembler -> Shrinker -> Permutator -> Expander -> Assembler

The virus uses pseudo-assembler techniques to decode each instruction in a form that it can manipulate easily. It extracts the instructions, instruction length, registers and other pertinent information. The shrinker then compresses the disassembled codes produced from the previous generation to prevent the virus code from growing continuously. At this point, garbage codes and do-nothing instructions are also eliminated. Figure 6 shows sample Win32 instructions that Etap has compressed/transformed.

XOR Reg,-1       —> NOT Reg

SUB Mem,Imm      —> ADD Mem,-Imm

XOR Reg,0        —> MOV Reg,0

ADD Reg,0        —> NOP

AND Mem,0        —> MOV Mem,0

XOR Reg,Reg      —> MOV Reg,0

SUB Reg,Reg      —> MOV Reg,0

AND Reg,Reg      —> CMP Reg,0

TEST Reg,Reg     —> CMP Reg,0

LEA Reg,[Imm]    —> MOV Reg,Imm

MOV Mem,Mem      —> NOP

Figure 6: One-to-one instruction transformation.

PUSH Imm / POP Reg                 —> MOV Reg,Imm

MOV Mem,Reg/PUSH Me                —> PUSH Reg

MOV Mem,Reg / MOV Reg2,Mem         —> MOV Reg2,Reg

ADD Reg,Imm / ADD Reg,Reg2         —> LEA Reg,[Reg+Reg2+Imm]

OP Reg,Imm / OP Reg,Imm2           —> OP Reg,(Imm OP Imm2)

LEA Reg,[Reg2+Imm] / ADD Reg,Reg3  —> LEA Reg,[Reg2+Reg3+Imm]

POP Mem / PUSH Mem                 —> NOP

MOV Mem2,Mem / MOV Mem3,Mem2       —> MOV Mem3,Mem

OP Reg,xxx / MOV Reg,yyy           —> MOV Reg,yyy

NOT Reg / NEG Reg                  —> ADD Reg,1

NEG Reg / ADD Reg,-1               —> NOT Reg

Figure 7: Two-to-one instruction transformation.

MOV Mem,Reg
OP Mem,Reg2
MOV Reg,Mem            —> OP Reg,Reg2

MOV Mem,Imm
OP Mem,Reg
MOV Reg,Mem           —> OP Reg,Imm (it can’t be SUB)

MOV Mem2,Mem
OP Mem2,Imm
MOV Mem,Mem2         —> OP Mem,Imm

CMP Reg,Reg
JNO/JAE/JZ/JBE/JNS/JP/JGE/JLE @xxx
!= Jcc              —> JMP @xxx

MOV Mem,Imm
CMP/TEST Reg,Mem
Jcc @xxx           —> CMP/TEST Reg,Imm
                       Jcc @xxx
                       Jcc @xxx

MOV Mem,Reg
AND/TEST Mem,Reg2
Jcc @xxx          —> TEST Reg,Reg2
                      Jcc @xxx

MOV Mem2,Mem
SUB/CMP Mem2,Reg
Jcc @xxx          —> CMP Mem,Reg
                      Jcc @xxx

MOV Mem2,Mem
AND/TEST Mem2,Imm
Jcc @xxx          —> TEST Mem,Imm
                      Jcc @xxx

MOV Mem2,Mem
SUB/CMP Mem2,Imm
Jcc @xxx          —> CMP Mem,Imm
                      Jcc @xxx

PUSH EAX
PUSH ECX
PUSH EDX         —> APICALL_BEGIN

Figure 8: Three-to-one/two/three instruction transformation.

To increase the level of metamorphism, the virus codes are processed first by the permutator. The expander simply undoes what the shrinker did. It replaces the single instructions with corresponding singles, pairs or triplet instructions.

The expander is also responsible for register translation and variable re-selection. Instructions are selected by the expander in a random manner. In the final step, the assembler's task is to convert the pseudo-assembly code into the real Intel IA-32 assembly instructions.

The disassembled code fragments shown in Figure 9 and Figure 10 are two different generations of Etap. At first glance, it seems that the two code fragments are different because the instruction constructs used are far from each other. But detailed analysis shows that they both assemble the string 'kernel32.dll' in the stack, then call the GetModuleHandle API.

mov   eax,06E72656B ;”nrek”

mov   [edx],eax

mov   eax,032336C65 ;”23le”

mov   [edx][04],eax

mov   eax,06C6C642E ;”lld.”

mov   [edx][08],eax

xor   eax,eax

mov   edx][0C],eax

call  .00040299D

Figure 9: First generation of Etap.

push 6c6c442e                     ; mov ebp, “lld.”
pop ebp

mov edx,73b36c67                  ; mov edx, “23le” —> encrypted
and edx,3e7fdedd

push 4e72454b                     ; mov esi, “nrek”
pop esi

push ebp                          ; mov ecx, ebp
pop ecx

mov dword ptr ds:[42268c],ecx     ; mov mem+8, ecx
lea ebx,dword ptr ds:[esi]        ; mov ebx, esi
mov dword ptr ds:[422684],ebx     ; mov mem, ebx
mov dword ptr ds:[422688],edx     ; mov mem+4, edx

push 0                            ; xor reg2, reg2 or mov reg2, 0
pop edx

mov dword ptr ds:[422690],edx     ; mov [mem+c], edx
mov ecx,infect1.00422684          ; mov ecx, mem
push ecx                          ; push ecx

push <&kernel32.getmodulehandlea> ; mov edi, offset getmodulehandle
pop edi

call dword ptr ds:[edi]           ; call getmodulehandle via edi

Figure 10: Second generation of Etap.

The solution for Etap is divided into three methods – simple string search, behaviour checking, and code transformation. The first and second method do not guarantee perfect detection and are prone to false positives. The latter is the perfect solution for this type of metamorphism, but is also very hard to implement.

Most anti-virus engines already support string search so it will not be discussed here.

The second method requires an emulator to follow the virus code and trigger several flags when a behaviour that pertains to the virus is encountered.

However, this technique does not guarantee perfect detection because there are some samples wherein the API names cannot be resolved properly. In addition, an emulator is required to intercept the RDTSC instruction and make sure that correct values are specified so that the virus continues with the process. Otherwise, the virus simply exits and the scanner fails to notice the virus behaviour, resulting in a missed detection. Another drawback of this method is that it is slow – because it requires the emulation of every Intel IA-32 instruction.

The last method, which is also the most complex to implement, is code transformation. This method involves transforming the virus code back to its form prior to the expander stage. This form is similar to the first generation as mentioned above.

In this method, we transform the virus code into its simplest form, where common instructions for virus detection are applicable. Three instructions are transformed to two or one instruction(s); two instructions are transformed to one instruction.

The code transformation module must be heavily optimized and flexible to be able to guarantee perfect detection without compromising scanning performance. For speed concerns, the virus location can be transformed from where the scan pattern is taken so as not to cause a significant impact on the performance of the scan engine. Checking filters via geometric techniques like file structure analysis is also advisable, whenever possible.

Zmist uses techniques that are similar to those used by Etap. More details on this virus and its infection techniques can be found in [1].

Devising a perfect solution for detection of metamorphic viruses is one of the enduring goals of most anti-virus vendors. Several techniques are known to exist but some are simple workaround solutions while others are shortcuts.

It is important to consider three factors when designing a solution for metamorphic viruses: detection rate, speed and false positives. To achieve perfect detection, a re-write of the scan engine is appropriate to make it interactive, flexible, and optimized to handle such kinds of virus. It is also worth mentioning that creating an automated replication system to produce several different generations of infected samples would be necessary to guarantee a 100% detection rate.