Using Markov Chains to Filter Machine-morphed
Variants of Malicious Programs
Mohamed R. Chouchane, Andrew Walenstein, and Arun Lakhotia
Center for Advanced Computer Studies
University of Louisiana at Lafayette
[e-mail], [e-mail], [e-mail]
Abstract morphism [20], and within self-replicating malware it-
self, which are commonly called  metamorphic mal-
Of the enormous quantity of malicious programs seen ware [22]. Considering the problems that variants can
in the wild, most are variations of previously seen pro- cause, the use of automated morphing is likely to remain
grams. Automated program transformation tools i.e., desirable on the part of malware authors [19].
code morphers are one of the ways of making such
Both dynamic and static methods have been pro-
variants in volume. This paper proposes a Markov
posed for aiding detection of morphed variants of exist-
chain-based framework for fast, approximate detection
ing programs. For example, normalization has been pro-
of variants of known morphers wherein every morphing
posed to remove obfuscating program variations [7, 16],
operation independently and predictably alters quickly-
and for  reversing the effects of known morphers [25].
checked global program properties. Specifically, iden-
Even if these are effective, it can be expensive to ap-
tities from Markov chain theory are applied to approx-
ply powerful variation-detection methods, particularly
imately determine whether a given program may be a
on suspect programs for which they are not necessary. It
variant created from some given previous program, or
would be beneficial to have a fast filter that can quickly
whether it definitely is not. The framework is used
determine whether a given input program need not be
to define a method for finding telltale signs of the use
considered for more involved processing [4].
of closed-world, instruction-substituting transformers
One idea for building such fast filters is to consider
within the frequencies of instruction forms found in a
the morphers as  authors and recognize their author-
program. This decision method may yield a fast tech-
ship [3]. This idea is to take advantage of cases where
nique to aid malware detection.
the morphing engines have idiosyncratic output due to
their recognizable repertoire of morphing techniques.
However even if the morphing engine is not particularly
1. Introduction
idiosyncratic, it may still be predictable. An interesting
question, then, is if the predictability of a given morpher
can be used to generate a fast filter that can quickly dis-
The number of malicious programs found in circula-
card programs that are definitely not a variant produced
tion has been growing at a tremendous rate [21]. This
by it. It has been suggested that Markov chain theory,
growth is causing many troubles, not only because of
for example, might be used to define a framework for
sheer volume [23], but because it is difficult to produce
doing such detections [5].
a defensive response that is both rapid enough and com-
prehensive enough to catch all the new threats. This paper shows for certain classes of program mor-
The fact is, though, that the vast majority of the new phers, Markov chain theory can be used to formalize
malicious programs are not wholly novel programs: they an approach for recognizing whether a given program
are variants of previously seen programs. The vari- may be a morphed variant, or is not. In particular, the
ants can be created via a number of methods, includ- approach applies to morphers that satisfy specific prop-
ing: hand modification, using kits or frameworks, us- erties including: independence of morphing operations,
ing packers or encryptors, or using automated program and the predictable alteration of a rapidly-checkable pro-
transformers, i.e., using morphers. These morphers can gram property that drives further morphing. A key to
be utilized on the malware writer s desktop, on distribu- the framework is that the program property must make
tion servers implementing so-called  server-side poly- it possible to predict the effects of morphing actions on
that property. Filtering is done by encoding the property may even be possible to generate the normalizers au-
changes as a transition matrix and then using Markov tomatically from a model of the morpher [25]. If the
identities to test, to some fixed generation, whether or morpher is not known, it may be possible to use general
not a given program is a descendant of some known an- transformations that try to remove added variations [7]
cestor. Because of the Markov properties, the approach and impose order on unconstrained variations [16].
produces no false negatives. However, in some cases an
A third approach is to recognize the output of the
exact solution is expected to be too expensive to com- morpher by its properties [3]. This is akin to author-
pute exactly, and well-known approximation algorithms
ship analysis for text [14] or programs [15], only instead
can be used instead. We introduce the framework us- of a human author one is considering that the morpher
ing a particular example of its definition for detecting
is a type of author modifying an original text. The cen-
signs of closed-world, instruction-substituting morphers
tral idea for authorship recognition is the detection of
within the frequencies of instructions within programs.
the idiosyncrasies of the author; in morphing terms, this
Section 2 motivates the solution and reviews pre- amounts to searching for unique or limited repertoire of
vious attempts to use global properties of instruction
the morpher [4].
frequencies for fast filtering. Section 3 introduces the
As pointed out by Chouchane et. al [4], no matter
Markov-based decision framework; it is elaborated in
the efficacy of the detector for morphed variants, it may
Section 3.2 it by way of the specific example of an in-
be too computationally inefficient to use on every sus-
struction frequency-based filtering approach. Section 4
pect program. For example, a semantics-based approach
introduces generalizations of the framework and dis-
such as that of Christodorescu et. al [6] involves heavy-
cusses methods for reducing the space needed for the
weight program analysis. But in many cases such deep
transition tables.
analysis is unnecessary, as many of the samples under
consideration (in a system scan or within network traf-
fic) are not, in fact, going to be malicious morphed vari-
2. Fast filtering of morphed variants
ants that require the heavyweight detection. An approx-
imate but fast filter may therefore be extremely useful so
It is known that the problem of recognizing families
that the more resource-hungry approaches are used only
of related programs created by a grammar-based gen-
infrequently ideally, only when needed.
erator can be modeled formally as a language recogni-
Chouchane et. al [4] proposed a heuristic method for
tion problem [10, 12]. A morpher, upon input of a spe-
such a filter for metamorphic programs. It is based on
cific ancestor program, generates a language or  viral
measuring statistical properties of the instruction forms
set [8] consisting of all the different variants it can pro-
of the program. Specifically, the filtering was based on
duce. Depending upon the morpher s qualities, as Filiol
the instruction form frequencies. The different genera-
showed [10], the recognition problem can be classified
tions of a metamorphic program were characterized (ap-
into one of several categories based on Chomsky s lan-
proximately) by averaging the frequencies of their in-
guage hierarchy. Even if the morpher is relatively simple
struction forms. A suspect program is then heuristi-
linguistically, however, it is an important practical prob-
cally filtered if the difference between its instruction fre-
lem of knowing how to create an efficient recognizer.
quency vector (IFV) and all averaged vectors is higher
One approach for recognizing the viral set is to recog-
than some threshold.
nize commonalities in either form, behaviour, or seman-
tics. This approach relies upon the morpher not mod- A problem with such past approaches is that, even
if they are fast, they are heuristic in the sense that they
ifying the commonalities being sought. For example,
one might look for common patterns of byte or opera- could guarantee neither false positive nor false negative
rates. A key reason is the heuristic nature of the test.
tion sequences (e.g., Karim et. al [13]), or of calls or
control flow (e.g., Zhang et. al [26]), or of semantic pat- But a secondary reason is that it relies on finding the
idiosyncrasies of the morphing engine. While the data
terns (e.g., Christodorescu et. al [6]). A limitation of
all such approaches is that the morpher may serve to re- from Chouchane et. al [4] suggests that instruction form
frequencies may indeed be more indicative of the mor-
move those commonalities that are being sought, a goal
pher than simple instructions [2] or bytes [1], it still may
known to morpher authors [9]. Another way of saying
this is that the viral set may not uniformly contain a pat- be the case that the morpher is altered so that it is not
easy to statistically distinguish it from other legitimate
tern of commonality of the type being considered.
constructors.
A second general approach to such recognition is to
normalize the input programs with the aim of making For a fast filter, false positives are perfectly accept-
the modifications introduced by the morpher transpar- able if the false positive rate is reasonable even a 20%
ent and moot. If the specific morphing engine is known, false positive rate means that 80% the time no costly
then precise normalization engine may be possible it analysis is wasted on irrelevant suspect programs. How-
ever it is particularly important to have an extremely Given a positive integer n and a sequence =
x
low false negative rate guaranteed no false negatives, (x1, x2, ..., xn) " Nn, we define the norms || =
x||1
n
if possible. In particular, it would be helpful to have a |xi| and ||x||" = max(|x1|, |x2|, ..., |xn|). I =
i=1
general mathematical framework within which one can {I1, I2, ..., Im} denotes the instruction set of a target
prove the false negative rates are desirably low. computing platform. OCC denotes the function from
(I+, I) to N mapping each (P, Ii) pair to the frequency
of instruction Ii in code segment P . Z denotes the func-
3. Fast recognition using Markov models
tion from R to {0, 1} which returns 1 if and only if its ar-
j
gument is 0. T = {li {(Prj, ri ) : 1 d" j d" imax)}}
i
A framework is proposed for using Markov theory
denotes the set of n productions used by the morph-
to define fast filters based on detecting telltale signs of
ing engine to transform its input. It is assumed that
the morphing within program properties that are quickly
li " I, rj " I+, exactly one rj is identical to li, and
i
checkable. Using Markov chain theory it is possible to
i i
max
Prj = 1, for all 1 d" i d" n. Prj denotes the
show that false negatives will not occur up to some gen- j=1 i i
eration of morphing. The model is defined on morphing probability of use of right hand side element rj (i.e., the
i
processes that: (1) satisfy the Markov property, and (2)
probability that rj is chosen to replace an instance of li).
i
are such that each morphing operations alters a rapidly-
For instructions Ii and Ik, Fi,k(²) returns the probabil-
checkable program property in predictable ways, and
ity that, on input one instance of Ii, the engine generates
such that this property is a determinant of the frequen- ² instances of Ik.
cies of morphing actions in subsequent iterations.
The probabilities of use are assumed to be fixed for
The framework is introduced by way of an example
each production and extractable interactively from the
filter model for probabilistic, closed-world, instruction-
morphing engine. Furthermore, if the engine is not
substitution engines. The example uses IFVs as the
available, these probabilities may also be estimated from
comparison property. After describing the specific ex-
large corpora of programs, where each corpus contains
ample, its generalization is described. Introducing the
members of some specific generation of descendants of
framework using this example helps in exposition, but it
some Eve. Probabilities of use may for example be
also demonstrates that the framework can be applied to
implemented (as in theW32.EvolandW32.Simile
an interesting class of morphers, since such instruction-
metamorphic viruses) using a random number generat-
substitution engines are known. Background notation is
ing procedure that is part of the engine and that makes
briefly introduced, a model of the morpher is introduced,
its choices at run time by reading arbitrary memory lo-
and the Markov-based filter is described. The Markov-
cations. If the latter is the case then we assume that the
based analysis is then generalized to a framework.
1
choices are uniform; Prj = for each rj. Whenever
i i
imax
the morphing engine visits an instruction that is also the
3.1. Morpher modeling
left hand side li of some production, with probability
Prj the engine substitutes li for rj. A sample set of this
i i
In this section, a formal model of a target morphing
type of rule appears in Figure 1.
engine M is presented. It is based on the model from
Let P denote some program and n the number of dis-
Chouchane et. al [4]. We target the class of closed-
tinct instructions occurring in P . The instruction fre-
world morphing malware that uses a morphing engine
quency vector of P , denoted IFV (P ), is the n-tuple
that applies a fixed, finite set of transformation rules,
each of whose components represents exactly one op-
each rule mapping an instruction (the left hand side) to
code mnemonic and holds the frequency (or count) of
a sequence of multiple instructions (the right hand side).
that mnemonic in P . No two components may represent
These rules are used by the engine to probabilistically
the same mnemonic. For instructions Ii and Ik, Ä… " N,
substitute, in the variant being transformed, occurrences
and ² " N, Gi,k(Ä…, ²) returns the probability that, on
of the left hand sides of the rules with one of their cor-
input Ä… instances of Ii, the engine generates ² instances
responding right hand sides. These probabilities are as-
of Ik. It returns 0 if Ä… =0. For 1 d" i d" k d" m, Ä…i,k de-

sumed to be fixed, or exactly learnable from the descrip-
notes the segment (subvector) of a program s IFV which
tion of the engine, for each rule of the transformation
starts at instruction Ii and ends at instruction Ik. For
system. In order to reduce the very large number of pos-
² " N, 1 d" i d" j d" m, and 1 d" k d" m, Hk( ²)
Ä…i,j,
sible assembly language instructions which are identical
returns the probability that ² instances of instruction Ik
except for the register names or variable values that they
are generated by the engine on input a program with IFV
use, the model may abstract an instruction to just its op-
Ä…1,m, where all of Ä…1,m s components are 0 except, per-

code mnemonic. In the sequel we will loosely use the

phrase  code segment to refer to the abstraction of the haps, for subvector Ä…i,j. Finally, T ( ²1,m) returns
Ä…1,m,
actual code segment. the probability that, on input a program with IFV Ä…1,m,

i i i
li {ri1 ri2 ri3 }
1 mov [reg1+imm], reg2 push reg push reg
mov reg, imm mov reg, reg1
mov [reg1+reg], reg2 add reg,imm1
pop reg mov [reg+imm2], reg2
pop reg
2 mov reg, imm mov reg, imm1 mov reg, imm1 mov reg, imm1
add reg, imm2 sub reg, imm2 xor reg, imm2
3 push reg push reg
mov reg, imm
4 sub reg reg xor reg, reg
Figure 1. Example rule set.
the probabilistic instruction substituting engine gener- be modeled as a Markov chain.

ates a program with IFV ²1,m.
State Transition Matrix. Given a (finite) set of states
Note that, in general, a morpher may iteratively apply
of size k, the k by k transition matrix is the matrix con-
the morphing rules in order to create a variant. A server- structed where row i and column j entry is the state tran-
side morpher may, for example, start with the same orig- sition probability between state i and state j.
inal program and create variants by multiple application
of the substitution rules. In such cases, we still say that
1. mov eax,10
1. mov eax,16
2. add eax,6
the morphing engine produces variants of different  gen-
3. push eax
2. push eax
erations , where a generation is an iteration through the 4. mov eax, 9
5. mov eax, 32
3. mov eax, 32
substitution rules. 6. mov ecx, 1024
4. mov ecx, 1024
Substitute
7. mov edx, 47
5. mov edx, 32
8. sub edx, 15
9. push eax
6. push eax
3.2. Detection using a Malware s IFV 10. sub eax, eax
7. mov eax, 0
11. push eax
8. mov [ecx+4], ebx
12. mov eax, ecx
13. add eax, 2
Initial State
14. mov [eax+2], ebx
Given the preceding model of the instruction-
instruction freq.
15. pop eax
substituting morpher, a property is selected that is pre- mov %r,#i 5
Final State
push %r 2
dictably altered by the morpher and such that this prop-
instruction freq.
mov [%r+#i],#i 1
erty dictates iterated morphing properties. We expand on mov %r,#i 5
push %r 3
the suggestion of Chouchane et. al [5] by elaborating the
mov [%r+#i],#i 1
formal Markov model for the detection or filtering; gen-
add %r,#i 2
sub %r,#i 1
eralization of the model to a framework is performed in
sub %r,%r 1
State Transition
the subsequent section. The trick to mapping the prob-
mov %r,%r 1
pop %r 1
lem to a Markov chain problem is to treat that property
as a  state , and then map state transition changes as
predictable changes to that property.
State and State Transition. To be consistent with the
Figure 2. Simple state transition.
terminology used in Markov chain theory, we will use
the term  state (normally called abstraction) to refer to
The Existing work on Markov chains [18] has identi-
a program s IFV. Figure 2 illustrates a simple example
fied certain interesting classes of chains and ways of us-
of a state transition induced on a code fragment by some
ing a chain s transition matrix to infer useful information
probabilistic instruction substituting engine. Note that a
about the process it represents. In particular, successive
state transition is a vector (IFV) transformation.
powers of the transition matrix can be used for predict-
State Transition Probability. Given two program
ing the distribution of instruction forms. Specifically,

states Ä…1,m and ²1,m, the transition probability from

a Markov chain T is typically started in a state chosen

Ä…1,m to ²1,m is the probability that, on input a pro-

by a probability distribution on the set of states, called
gram whose state is Ä…1,m, the morphing engine produces

a probability vector. Let denote a probability vector
u

a program whose state is ²1,m. This probability will which holds the initial probabilities of a malware s state.
depend upon the instruction frequencies, the transition The powers of T are known to give interesting informa-
rules that can morph those instructions, and the prob- tion about the evolution of these distributions from one
abilities of those rules. Since the transition probabili- malware generation to the next: For any positive integer
n n
ties do not depend upon the history of transitions, such n, the ijth entry (T )ij of T gives the probability that
a morphing process obeys the Markov property and can the chain, starting in state si, will be in state sj after n
n
steps. More generally, if we let un = uT , then the NP-complete. In practice, one may then want to choose
probability that an nth-generation malware descendant to use a polynomial-time approximation scheme [11] for
is in some state si after n transitions is the ith compo- computing each of the Gi,k(Ä…, ²).
nent of un.
Hk( ²) can be recursively computed by observ-
Ä…1,m,
²
This result can be used as the basis for filtering. As-
ing that for 1 Ä…i,m,
´=0
sume that a known existing malicious program is sus-
Hk( ²-´). The recursion stops when i+1 = m,
Ä…i+1,m,
pected to have given rise to variants through application
that, is when we ask for the value of Hk( ² - ´).
Ä…m,m,
of the morpher. The original malicious program eve can
This value is computed by observing that Hk( ²-
Ä…m,m,
be considered the initial probabilities, that is, will have
u
´) =Gm,k(|| ² - ´).
Ä…m,m||1,
0 for all states except for IFV (eve), the IFV of eve.
The IFV transition probabilities are finally computed
Given a suspect program q, it will have a particular IFV,
by observing that
n
IFV (q). The matrix entry of T IFV (eve), IFV(q)
m
will record the probability that q is a nth generation vari-

T ( ²1,m) = H( ||²i,i||1).
Ä…1,m, Ä…1,m,
ant of eve. Significantly, if that entry is 0, then it is
i=1
impossible that q could have been generated by the mor-
pher in n generations. If the entry is non-zero, it the
3.4. Matrix optimization
probability that the morpher would have created q from
the eve. Given a constant number of generations, k, the
transition matrices up to k define the possibility that q
In theory, the set of all possible IFVs is infinite, since
could have been generated by M in up to k generations;
infinite growth in size is a theoretical option for morph-
the probabilities can also be examined to determine if it
ing malware. It is hence necessary in practice to at least
is likely that q is a given generation descendant of eve.
impose an upper bound on the size of this set while lim-
This basic results provides the mathematical basis for a
iting, as much as possible, the deterioration of the pre-
filter based on the predictable morphing actions of M.
dictive and classification power of the transition matrix.
Possible heuristics for doing so include, but may not
3.3. Computing transition probabilities be limited to, (1) reducing the size of the instruction
set by abstracting an assembly language instruction to

its opcode mnemonic or by ignoring register names and
The state transition probability, T ( ²1,m), is
Ä…1,m,
computed using the probabilities Fi,k, Gi,k, and Hk de- variable values, (2) imposing an upper bound on the pos-
sible frequency of each individual instruction, (3) im-
fined above. Fi,k can be computed by observing that,
posing an upper bound on an IFV s norm ||.|| , and (4)
for all ², "
abstracting each component of an IFV to one of two val-
imax

ues ( low or  high ), depending on whether that com-
j
Fi,k(²) = Z(² - OCC(ri , Ik)) × Prj.
i
ponent is less than or greater than some threshold.
j=0
We view the probabilistic instruction substitution pro- 4. Generalization
cess of Ä… instances of instruction Ii as Ä… independent
events (individual substitutions of each of the Ä… in-
The IFV-based model described above can be gener-
stances of instruction Ii). The outcome of each of these
alized to expand the set of morphers that the model can
events may yield zero or more occurrences of instruc-
apply to. Furthermore, the basic Markov-based frame-
tion Ik. Let S = {´ : Fi,k(´) = 0} denote the set of

work can be divorced from the specifics of the IFV so
all possible counts of instruction Ik that can be gener-
that it can be applied to the larger class of morphers that
ated by the engine on input an instance of instruction Ii.
need not be instruction-substituting; indeed, the same
Ä…

Let S² denote the set of Ä…-tuples ´ =(´1, ´2, ..., ´Ä…) of
basic Markov framework can apply to any morphing
elements of S such that || ||1 = ². Gi,k(Ä…, ²) is given
´
process that fits certain Markov process properties.
by
Ä…

4.1. Generalization of mutation model
Gi,k(Ä…, ²) = Fi,k(´j).
Ä… j=1
´"S²
In addition to allowing garbage inserting transforma-

Unfortunately, the problem of finding a ´ " SÄ… such tions which are modelable as fixed transformation rules
that || ||1 is equal to ² is an NP-complete one. In fact, (i.e., which map an instruction to a code segment of fi-
´
computing any Ä…-tuple x whose ||.||1 equals a fixed ² is nite, fixed size), we allow the following relaxations to
an instance of the SUBSET SUM problem and is hence the target probabilistic instruction-substituting engine.
1. The engine may not perform any condition check- probabilistic instruction-substituting malware, is to as-
ing. The engine is free to rewrite any or all of the sign low rule application probabilities to rules that in-
left hand side instances without the need to perform crease the size of the variant being transformed. Higher
condition checking. Rule 3 of Figure 1 is garbage- rule application probabilities would be assigned to rules
inserting rule and is a good example of the engine transforming a single instruction into another single in-
simply making the assumption that the condition struction. TheIA-32instruction set is rich enough to
 immediately after eachpush eaxinstruction, allow for a large number of rules (such as the fourth rule
the contents of registereaxmay be safely altered in Figure 1) mapping an instruction to an equivalent but
isTRUE. This relaxation is based on the observa- syntactically different instruction.
tion that condition checking may not be an optimal
design choice of morphing malware since it typ-
1. mov eax,10
1. mov eax,16
2. add eax,6
ically increases the engine s transformation time;
3. push eax
2. push eax
it may require the engine to statically solve po-
4. mov eax, 9
5. mov eax, 32
tentially costly (and sometimes unsolvable) prob- 3. mov eax, 32
6. mov ecx, 1024
4. mov ecx, 1024
Substitute
lems. Allowing this relaxation adds non-condition-
7. mov edx, 47
5. mov edx, 32
8. sub edx, 15
checking malware to our targeted class of malware.
9. push eax
6. push eax
10. sub eax, eax
See Walenstein et al. [24] for more on the design
7. mov eax, 0
11. push eax
8. mov [ecx+4], ebx
choices of morphing malware.
12. mov eax, ecx
13. add eax, 2
14. mov [eax+2], ebx
2. The engine may perform additional transforma-
15. pop eax
tions as long as they are not IFV-altering. The en-
Rename
gine may perform extra transformations to the vari-
ant being transformed as long as they do not change
1. mov eax,10
the IFV of that variant. Such transformations in-
1. mov eax,10
2. add eax,6
2. add eax,6
clude register renaming and instruction reordering.
3. push eax
3. push eax
4. mov eax, 9
Examples are shown in Figure 3. These transfor- 4. mov eax, 9 Reorder
5. mov ebx, 1024
5. mov eax, 32
mations (except perhaps for the instruction reorder-
6. mov eax, 32
6. mov ebx, 1024
7. mov edx, 47
ing transformation) are often used by malware writ- 7. mov edx, 47
8. sub edx, 15
8. sub edx, 15
ers since they are relatively easy to implement and 9. push eax
9. push eax
10. sub eax, eax
10. sub eax, eax
contribute to changing the code of the variant being
11. push eax
11. push eax
12. mov eax, ecx
transformed. Allowing this relaxation adds non- 12. mov eax, ebx
13. add eax, 2
13. add eax, 2
IFV-altering malware to our targeted class of mal-
14. mov [eax+2], ebx
14. mov [eax+2], ecx
15. pop eax
15. pop eax
ware.
The first relaxation is reasonable because the mal-
Figure 3. Morphing transformations.
ware signature prediction and detection procedure pro-
posed in this paper is independent of the semantics of
the malware.
4.2. Generalization to Markov framework
The second relaxation is reasonable because this pro-
cedure is specifically designed to detect the effects of the
The example used in the previous section is that of
instruction substitution transformation and assumes that
an instruction-substituting morphing engine. It is pos-
only instruction substitution affects the IFV of the mal-
sible to generalize the entire work by carefully noting
ware code, i.e., any other subsequent transformations
how the formalization to use Markov chain theory was
performed by the engine do not affect the IFV of the
accomplished:
malware code.
Since we are dealing with engines which substitute
" Markov property The morphing engine obeyed
an instruction by code segments of size greater than or
the Markov property in that the probability of the
equal to one, the size of a descendant of a given variant
rules firing did not depend upon the history of fir-
may be greater than that of the variant. It is clearly a
ing.
plausible requirement of good design practices of mor-
phing malware to prevent a malware variant size from " State and state transition mapping The state in
 growing too fast as its code gets morphed. A number our model was the IFV of the program. This is
of methods can be used to have some control over the a quickly calculable abstraction of the program it-
increase in the sizes of the successive descendants for a self. Morphing actions (state transitions) could be
given variant. One way of doing this, in the context of mapped to state transitions.
" Morphing dependence on property Note that for References
the transition mappings to be possible, the morph-
ing actions must depend upon the abstracted state.
[1] D. Bilar. Statistical structures: Fingerprinting malware
In the case of the instruction-substituting engines, it
for classification and analysis. In Proceedings of Black
is clear that the substitutions that may be performed Hat Federal 2006. Black Hat, 2006.
[2] D. Bilar. Opcodes as predictor for malware. Int.
depend wholly upon the frequencies of the instruc-
J. Electronic Security and Digital Forensics, 1(2):156
tions present.
168, 2007.
Thus, while the proposed IFV method of fast fil- [3] M. R. Chouchane and A. Lakhotia. Using engine signa-
ture to detect metamorphic malware. In 4th Workshop
tering itself may be useful (for instruction substitut-
on Recurring Malcode (WORM), 2006.
ing morphers), a more general result is the Markov-
[4] M. R. Chouchane, A. Walenstein, and A. Lakhotia.
based framework. It can be noted that many other
Statistical signatures for fast filtering of instruction-
morphing processes including ones that are not fully
substituting metamorphic malware. In 5th Workshop on
automatic may be approximated as a Markov process.
Recurring Malcode (WORM), 2007.
If there is a controlling property of the morphing, and
[5] M. R. Chouchane, A. Walenstein, and A. Lakho-
this property is quickly checkable, then a fast filter may
tia. Metamorphic authorship recognition using Markov
be defined.
models. Virus Bulletin, May 2008.
[6] M. Christodorescu, S. Jha, S. A. Seshia, D. Song, and
R. E. Bryant. Semantics-aware malware detection. In
5. Conclusions
Proceedings of the 2005 IEEE Symposium on Security
and Privacy (S&P 05), pages 32 46, 2005.
The IFV-based detection model proposed in the pa- [7] M. Christodorescu, J. Kinder, S. Jha, S. Katzenbeisser,
per circumvents the inherent limitations of many static and H. Veith. Malware normalization. Technical re-
port, Department of Computer Science, The University
and dynamic malicious program detection approaches.
of Wisconsin, 2005.
It is a semantics-independent solution to the problem of
[8] F. Cohen. Computational aspects of computer viruses.
detecting morphed malware variants that overcomes the
Computers and Security, 8(4):325, June 1989.
limitations of having to exactly solve unsolvable prob-
[9] M. Driller. Metamorphism in practice, 2004. http:
lems or efficiently solve provably intractable problems.
//vx.netlux.org/29a/29a-6/29a-6.205.
Furthermore, the individual limitations of existing tech-
[10] E. Filiol. Metamorphism, formal grammars and unde-
nology and research on malware detection, and the fact
cidable code mutation. International Journal of Com-
that morphing engines are difficult to write and tend to
puter Science, 2(1):70 75, Apr. 2007.
be reused, typically by writing a new malicious program
[11] M. R. Garey and D. S. Johnson. Computers and In-
to be morphed by an existing engine, suggest the useful-
tractability: A Guide to the Theory of NP-Completeness.
ness of the proposed method, since it uses information W. H. Freeman & Co., 1979.
about a morphing malware s engine (transformation pro- [12] Z. hong Zuo, Q. xin Zhu, and M. tian Zhou. On the time
complexity of computer viruses. IEEE Transactions on
cess) to detect variants of the malware by approximately
Information Theory, 51(8), Aug. 2005.
deciding membership in the set of programs that can be
[13] M. E. Karim, A. Walenstein, A. Lakhotia, and L. Parida.
generated by the engine.
Malware phylogeny generation using permutations of
It is perhaps intuitively expected that a predictable
code. Journal in Computer Virology, 1(1-2):13 23,
morphing engine will have an exploitable weakness sim-
November 2005.
ply by virtue of the predictable nature of the morphing
[14] D. V. Khmelev and F. J. Tweedie. Using markov chains
actions. The proposed framework defines cases where
for identification of writers. Literary and Linguistic
fast filtering is possible; specifically the framework pro-
Computing, 16(4):299 307, 2001.
vides the mathematical basis for defining accurate fil- [15] I. Krsul and E. Spafford. Authorship analysis: Identify-
ing the author of a program. Computers and Security,
ters (no false positives) for variants of known programs
16(3):233 257, 1997.
built from known morphing engines that obey specific
[16] A. Lakhotia and M. Mohammed. Imposing order on pro-
Markov properties. This can raise the bar for malware
gram statements to assist anti-virus scanners. In Pro-
production by easing the detection of the potentially
ceedings of the 11th Working Conferenceon Reverse En-
large volumes of variations that could be generated us-
gineering, 2004.
ing simple morphers. While important implementation
[17] H. Martin, editor. Proceedings of Virus Bulletin Confer-
and optimization issues are outside the scope of this pa-
ence 2007, Vienna, Austria, 2007. Virus Bulletin Inc.
per, the key step for defining a fast filter is taken by the
[18] S. Meyn and R. Tweedie. Markov Chains and Stochastic
framework in the use of a quickly computable property
Stability. Springer-Verlag, London, 1993.
of a program that can be used to look up probabilities of
[19] M. Schipka. A road to big money: evolution of automa-
being constructed by the Markov generation process. tion methods in malware development. In Martin [17].
[20] R. Sherstobitoff. Server-side polymorphism: Crime-
ware as a service model (CaaS). ISSA Journal, page 46,
May 2008.
[21] Symantec. Symantec global internet security threat re-
port volume XIII: Trends for july december 07, Apr.
2008.
[22] P. Ször. The Art of Computer Virus Research and De-
fense. Symantec Press. Addison Wesley Professional,
1st edition, 2005.
[23] J. Telafici and D. Gryzanov. What a waste  the AV
community DoS-ing itself. In Martin [17].
[24] A. Walenstein, R. Mathur, M. R. Chouchane, and
A. Lakhotia. The design space of metamorphic malware.
In 2nd International Conference on i-Warfare and Secu-
rity (ICIW), 2007.
[25] A. Walenstein, R. Mathur, M. R. Chouchane, and
A. Lakhotia. Constructing malware normalizers using
term rewriting. Journal in Computer Virology, January
2008 2008. doi:10.1007/s11416-008-0081-5.
[26] Q. Zhang and D. S. Reeves. MetaAware: Identifying
metamorphic malware. In Proceedings of the 23rd An-
nual Computer Security Applications Conference (AC-
SAC 07), pages 411 420, 2007.