FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA
(FUNDAMENTAL AND APPLIED MATHEMATICS)
2009, VOLUME 15, NUMBER 5, PAGES 181-198
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.
| Main page | Contents of the journal | News | Search |
Location: http://mech.math.msu.su/~fpm/eng/k09/k095/k09509h.htm
Last modified: October 8, 2010