FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2009, VOLUME 15, NUMBER 5, PAGES 181-198

**Using algebraic models of programs for detecting metamorphic malwares**

R. I. Podlovchenko

N. N. Kuzyurin

V. S. Shcherbina

V. A. Zakharov

Abstract

View as HTML
View as gif image

Polymorphic and metamorphic viruses are the most sophisticated
malicious programs that give a lot of trouble to virus scanners.
Each time when these viruses infect new executables or replicate
themselves, they completely modify (obfuscate) their signature to
avoid being detected.
This contrivance poses a serious threat to antivirus software
which relies on classical virus-detection techniques: such viruses do
not have any stable specific sequence of instructions to be looked
for.
In the ultimate case, the only characteristic which remains invariable
for all generations of the same virus is their functionality
(semantics).
To all appearance, the only way to detect for sure a metamorphic
malicious code is to look for a pattern which has the same
semantics as (i.e., equivalent to) some representative sample of the
virus.
Thus, metamorphic virus detection is closely related to the
equivalence-checking problem for programs.
In this paper, we outline some new automata-theoretic framework for
the designing of virus detectors.
Our approach is based on the equivalence-checking techniques in
algebraic models of sequential programs.
An algebraic model of programs is an abstract model of computation,
where programs are viewed as finite automata operating on Kripke
structures.
Models of this kind make it possible to focus on those properties of
program instructions that are widely used in obfuscating
transformations.
We give a survey (including the latest results) on the complexity
of equivalence-checking problem in various algebraic models of
programs and estimate thus a resilience of some obfuscating
transformation commonly employed by metamorphic viruses.

Location: http://mech.math.msu.su/~fpm/eng/k09/k095/k09509h.htm

Last modified: October 8, 2010