Constructing malware normalizers using term rewriting

A malware mutation engine is able to transform a malicious program to create a different version of the program. Such mutation engines are used at distribution sites or in self-propagating malware in order to create variation in the distributed programs. Program normalization is a way to remove vari...

Full description

Saved in:
Bibliographic Details
Published in:Journal in computer virology 2008-11, Vol.4 (4), p.307-322
Main Authors: Walenstein, Andrew, Mathur, Rachit, Chouchane, Mohamed R., Lakhotia, Arun
Format: Article
Language:English
Subjects:
Applied sciences
Computer Science
Computer science
control theory
systems
Exact sciences and technology
Language theory and syntactical analysis
Memory and file management (including protection and security)
Memory organisation. Data processing
Original Paper
Programming languages
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A malware mutation engine is able to transform a malicious program to create a different version of the program. Such mutation engines are used at distribution sites or in self-propagating malware in order to create variation in the distributed programs. Program normalization is a way to remove variety introduced by mutation engines, and can thus simplify the problem of detecting variant strains. This paper introduces the “normalizer construction problem” (NCP), and formalizes a restricted form of the problem called “NCP=”, which assumes a model of the engine is already known in the form of a term rewriting system. It is shown that even this restricted version of the problem is undecidable. A procedure is provided that can, in certain cases, automatically solve NCP= from the model of the engine. This procedure is analyzed in conjunction with term rewriting theory to create a list of distinct classes of normalizer construction problems. These classes yield a list of possible attack vectors. Three strategies are defined for approximate solutions of NCP=, and an analysis is provided of the risks they entail. A case study using the virus suggests the approximations may be effective in practice for countering mutated malware.
ISSN:1772-9890
1772-9904
DOI:10.1007/s11416-008-0081-5