Evasion techniques
The most widespread technique used by commercial anti-malware systems in
order to detect viruses is based on malware signatures [
21
]. They are invariant
patterns, usually taken from the program's code or raw le content, used to
uniquely identify the given malware. To evade signature based scanners many
today viruses (called metamorphic) are able to transform themselves during
the propagation phase, without losing their capabilities [
47
]. To achieve this
goal several metamorphic transformation are used, including code permutation,
garbage code insertion, code shrinking and expansion, register renaming,
encryption [
2, 3, 15
]. The result of these transformations is a brand new virus that,
while keeping the functionality of its predecessor, present a di erent structure
and then a di erent signature, thus evading detection [
47
]. As explained in [
4
],
we de ne M P to be the set of malicious programs, where P is the set of
all programs and S to be the set of signatures. A detector is then a function
D : P M ! f0; 1g. A program p is detected if there is a signature m 2 S such
that D(p; m) = 1. In the case of malwares D(p; m) = 1 () m is a pattern
derived from p.
Using signature for malware detection is e cient only if it is applied to known
malware. This technique, compared to dynamic analysis techniques, has less
scanning time, lower false-positive ratio and doesn't su er of the risks of system
infection due to the execution of the malware. The use of code obfuscation
techniques allows to easily generate variants of known malware resulting in new
malware that cannot be detected by signature based scanners and are harder to
comprehend for an human analyst. As stated in [
31
] more than 80% of malware
is packed, in accordance to [
41
] almost 50% of new malware in 2006 were existing
malware obfuscated with packing techniques. The same trend is linked to the use
of other obfuscation approaches. There exist many examples of code obfuscation
designed to avoid AV scanners detection [
17, 23, 32, 34
] and all of them are able
to easily evade signature based malware detectors.
As described in [
47
] except for packing, the rst obfuscation technique
historically used is encryption [
36, 37, 45
]. The executable body is crypted and the
malware adds to it a decryptor that provides decryption of the body at program
runtime. Since at every infection the cryptographic keys used are di erent the
crypted virus body will be always di erent. One of the rst viruses that
developed this strategy is Cascade, followed by Win95/Mad and Win95 Zombie [
42
].
Some of this kind of viruses use also multiple layers of encryption (Win32/Coke).
The major limitation of this approach is that in most cases the decryption is in
clear text and, since it is always the same, it can be used in order to generate
a signature. To overcome this limitation malware writers created new malware
able to change also decryptor code. This led to the birth of polymorphic
malware [
34
], that, using many di erent techniques [
11, 26, 45
] are able to generate
always di erent decryptors, without invariant patterns that could be used as
signatures. The rst viruses that used a real 32-bit polymorphic engine were
Win95/Marburg and Win95/HPS. They have been developed and spreaded
online many polymorphic engines, among these we can cite \The Mutation Engine"
(MtE ) [
36
] that is able to easily convert non obfuscated code into polymorphic
malware. Altough polymorphic malware are e ective against signature based
detection, they can be detected using more re ned techniques. After the decryption
phase, in fact, the body of the virus will be always the same. Using
sandboxing techniques [
36, 37
] the detectors are able to emulate malware in a controlled
environment, allowing the decryptor to decrypt malware body in memory. At
this point it is still possible to use signature based techniques on the decrypted
body. To prevent malware emulation several armoring techniques have been
proposed [
36
] but the improvements in sandboxing mechanisms brought many of
them to be ine ective. To overcome all these limitations malware writers brought
obfuscation to a new level: metamorphic malware [
17, 23
] [
11, 26, 37, 45
]. They
are malware able to transform their own body during infection phase. At each
iteration metamorphic malware is rewritten so that each succeeding version of
the code is di erent from the preceding one.
There are numerous techniques used by this kind of malware (and often by
polymorphic malware too):
{ Register swapping : is a technique used, for example, by Vecna's Win95/Regswap
virus [
45
]. It consists in changing registers used in various instructions during
the evolution from generation to generation. Wildcard searching makes this
technique ine ective.
{ Instruction substitution : it is based on substituting single, or groups, of
instructions with other instructions (or groups of them). The new instructions
will be equivalent to the previous ones in functionalities but syntactically
di erent [
26
].
{ Garbage instructions insertion : is a technique based on the insertion of
garbage instructions, that are useless for the execution of the program. Their
only goal is to vary malware body [
1, 26, 45
]. They can be single instructions
or sequences that perform useless operations leaving unaltered the state of
the program or even instructions located in areas of the program that will
never be executed. In this case we are talking about dead-code.
{ Transposition: this name is used to de ne many instruction reordering
techniques that leave unaltered the ow of the program [
11
]. One of these
technique consist in randomly reordering some instructions then using
unconditional jumps to reconstruct the original ow. In a more elegant way it is
possible to isolate independent groups of instructions then modify their
order. In this case, since the sequences are independent, there is no need to
make use of unconditional jumps. Finding independent groups of instructions
is not an easy task to perform, so, often developers use easier techniques,
which can be considered a variant of the rst one. It is based on the
reordering of the various subroutines that are present inside the malware [
11
].
One of the malware that used this approach is Win32/Ghost. If we have n
subroutines we are able to generate up to n! di erent variants.
{ Code integration: is the most sophisticated technique used to obfuscate code.
It has been introduced by the virus writer Zombie in Win95/Zmist (Zombie
Mistfall). It consists in decompiling the program to infect in distinct parts
and then inserting malware code between them. At the end the original
program and the malware are reassembled in a single executable.
Although several theoretical studies [
10, 14
] have proved that an algorithm able
to detect all types of malware can not exist, a lot of e ort has been put to
improve detection mechanisms. Several methods have been proposed, varying
from support vector machine (SVM) [
7
], to decision trees [
25,33
], to Naive Bayes
Method [
38
]. There are two di erent approaches in malware detection: static and
dynamic analysis. The rst analyzes a binary without executing it. Since this
technique is safer, faster and easier to implement than dynamic analysis, it is
the most widespread approach, even if it is more limited than the latter. Some
examples of operations that are performed by static analysis are nding patterns
on executables and code ow analysis. In addition to be fast and safe, static
analysis has the advantage of reaching complete application code coverage, thus
reducing the number of false positives in malware detection. The main problem
in using static analysis is that it is very di cult to detect unknown malware.
Dynamic analysis, instead, runs malware in a sandbox simulating the behaviour
of a real environment, monitoring all system calls. It is clear that the speed of
performing this kind of analysis is much slower than static analysis techniques. In
addition to that, several techniques have been proposed from malware writers in
order to check if the infected executable is running inside a virtual machine, and,
in that case, changing its own behaviour in a non o ensive one. To overcome
the limitation of static analysis they have been introduced many techniques
based on the concept of code normalization. These techniques try to reduce
obfuscated code to a base form that is the same for all obfuscated variants of the
same executable. Many di erent approaches to code normalization have been
proposed. Among them we can cite Christodorescu et al. [
12
], Walenstein et
al. [
44
] and Lakhotia et al. [
28
]. In the latter the base form is called \zero form"
and the process to reduce an executable to that form is called \zeroing". As
herm1t states in [
20
] if this kind of approach was perfect a tool that could perform
zeroing reducing all possible variants of a virus into a single \normalized" form
(not necessarily optimal), could then use this strategy with every algorithm thus
proving or refuting their identity. That's known to be indecidable. The e ort of
the creators of detectors is then focused on capturing semantic pattern inside
an executable rather than invariant synctactic features. These techniques vary
from API call analysis [
35
] to Control Flow Graph analysis.
As explained in [
40
] a Control Flow Graph (CFG ) is a graph in which the
nodes are basic blocks of execution and the edges are possible control ow
transfers between them. They are used both for malware detection and
vulnerability discovery. CFG recovery is a widely discussed topic in literature, we can
cite [
13, 24, 27, 39, 43, 46
].
Many CFG recovery algorithms deal with the problem of indirect jumps.
An indirect jump occurs when the control ow is transferred to a target
represented by a value in a register or to a memory location. This makes ow analysis
much harder because the destination of the jump is not easily resolvable. This
is because it could depend from computations speci ed in code, from the
application context or even from function pointers used in object oriented languages
to implement object polymorphism [
40
].
Control Flow Graph based malware detection As previously stated, due to the
di culty on isolating invariant synctactic features of a self-mutating malware,
the e ort of the creators of detectors is focused on capturing semantic patterns.
CFG are widely used to nd similiarities among executables [
18
] and, more in
detail, among malwares [4{6,8,9,19,22,30]. The techniques proposed in literature
are based on generating the CFG of a program P to analyze. The generated CFG
is the compared to a set of CFGs of known viruses in order to nd isomorphic
components. Usually ( [
6
]) before extracting the CFG from a program P a set
of normalization operations [
28
] are performed on the binary. This step aims to
reduce the e ects of mutation techniques. The normalized binary is then used to
extract the CFG which is then compared to CFG extracted by normalized known
malware. If the CFG of the normalized program contain a subgraph isomorphic
to the CFG of a malware, then the executable is marked as malicious.
4
Using compilers to evade detection
The advances in malware detection and the plethora of di erent devices and
operating systems in use nowadays, pose new intriguing challenges to malware
writers. The use of assembly language is becoming more and more painful,
because of the di culties involved to write portable and easy-to-support code. In
the forward-looking article \Recompiling the metamorphism" [
20
], the author,
herm1t, suggests to make use of high level languages in order to overcome the
di culties involved in developing malware in pure assembly. He outlines how
using a high level language gives to the developer the opportunity to easily extract
additional information from the code, rather than builtin support for features
like hashes, iterators or objects. The idea of "recompiling the metamorphism"
is without any doubt interesting and introduces many advantages to the virus
writer, however, not all the bene ts of using compilers have been considered in
detail. In order to evade new anti-malware techniques based on the extraction
of semantic patterns from executables, compilers could play an important role.
They, in fact, are able to generate executables characterized by very di erent
structures and could be used in order to defeat detection mechanisms. In this
respect we take into accounts the bene ts introduced by using exotic compilers,
like the M/o/Vfuscator2 3 in order to obtain di erent CFGs, thus fooling the
CFG based detection.
Single instruction compilers as an evasion technique In [
16
], Dolan demonstrates
the Turing-completeness of the x86 instruction mov. After the publication of the
article many people started to implement, most of the time for fun, single
instruction compilers, capable to compile arbitrary programs into lists of only mov
instructions. Several di erent instruction turned out to be Turing-complete, so
many di erent single instruction compilers arose 4. Even if at rst sight it may
seem just like a funny fact, the use of single instruction compilers has very
interesting consequences. Since in single instruction compiled programs comparisons,
jumps, function calls are all implemented with a single instruction, the resulting
CFG is a single (usually long) basic block. This result is very interesting, because
having a CFG composed by a single basic block make ine ective all detection
mechanisms based on CFG isomorphism detection. Using a single instruction
3 https://github.com/xoreaxeaxeax/movfuscator
4 https://github.com/xoreaxeaxeax/movfuscator/tree/master/post
compiler, however, has its drawbacks. First of all a program compiled with a
single instruction compiler could be considered suspicious, thus marked as
malicious. In addition to that, the size of a program compiled with a single instruction
compiler, is, most of the time, much bigger than the size of the same program
compiled using the entire set of instructions. This introduces some problems to
virus writers that in many cases have a limited space in the binary they are going
to infect, so they should keep the malicious code as small as possible. Sometimes
even the performances of the malicious code is important and programs
compiled with a single instruction compiler usually are slower than traditional ones
in terms of execution speed. These problems lead to rethink the way single
instruction compilers are used for evasion purposes. A simple but e ective solution
could be splitting the source code at compilation time. In our implementation we
mark with source code annotation the functions that we want to compile with
a single instruction compiler, then at compilation time, making use of the tools
provided by LLVM [
29
] we are able to build an executable that uses the full set
of instructions for the code that cannot be used to determine its malicious
behaviour and a single instruction for the malware routines. In this way we are able
to build a much smaller executable that is still able to fool CFG based malware
detection. It is important to underline that the single block of single instruction
compiled code can be furtherly modi ed using the metamorphic techniques
described in section 2. This single block can be also manipulated in order to obtain
di erent CFGs, this can be easily done by inserting jumps or comparisons, thus
creating branches in the graph. To further variate the result of the obfuscation,
several di erent single instruction compilers can be adopted, resulting in a great
variety of CFGs, making very hard for the detectors to extract signatures, both
syntactically, due to metamorphic transformation, and semantically, thanks to
the always changing CFG.
5