Malware Detection based on Dependency Graph using Hybrid Genetic Algorithm

[minakshi bhoi]

Malware Detection based on Dependency Graph using Hybrid Genetic Algorithm
B.Tech Seminar report
by
Jishnu V
Department of Computer Science And Engineering
Government Engineering College, Thrissur
December 2010

[attachment=7712]

Abstract
Computer malwares are becoming a serious threat to our data and information stored
in our computers. Among them, scripted malwares are gaining popularity since script-
ing is supported by a wide range of programs. So their detection and prevention is very
important. Most malware detection tools follow signature based detection mechanism.
But by the introduction of polymorphic variants of malwares, signature based detec-
tion has become ine cient. This paper proposes a mechanism based on dependency
graphs for detecting script malwares. All malwares are represented by dependency
graphs and the detection is done by nding the maximum subgraph isomorphism with
the dependency graph of the target le. Since the problem of nding maxumum sub-
graph isomorphism is a NP hard problem, a genetic algorithm is more appropriate.
A heuristic approach is also presented to improve accuracy and reduce computational
cost of our genetic algorithm.

Chapter 1
Introduction
Malicious softwares or malwares are a broad class of softwares that are threats to
computer systems. They damages the computer systems, destroys or steals data, or
allows unauthorized access. According to thier behaviour malwares can be grouped
as viruses, spywares, adwares or trojan horses.
Scripted malwares are those that written in script languages like VBscript,
javascript etc.. These are spread in the form of sources embedded in emails or docu-
ments.
Signature based detection is the most common method followed for malware
detection. The malware detection tools have the siganture of most malwares in their
database. Signature can be considered to be a piece of code that uniquely identi es
that malware. The suspicious le is searched for a known signature. If the signature
matches with one in the database the le is declared as malware, else benign.
Malware polymorphism is the main threat to the signature based detection
technique. But it only changes the appearance of the malware. The dependencies
among statements will be still valid. The structure of the dependency graph of the
code will remain same even after alteration of statements. So our problem reduces to
nding the maximum subgraph isomorphism between the graphs. A genetic algorithm
with heuristics is used since nding maximum subgraph isomorphism is a NP hard
problem.

Chapter 2
Malware Polymorphism
Many techniques have evolved over time to avoid detection of anti-virus softwares.
The most prominent among them is malware polymorphism. This method is the main
threat to the signature based detection.
Polymorphic viruses confuse the virus detectors by changing their appearance.
Even if they change their appearance, their function will not change. The algorithm
of the original code remains intact. Commonly, 7 well-known techniques are used for
creating polymorphic variants. Even with these 7 techniques only, it is possible to
create a large number of variants of a single virus. Some even have a mutation engine
which creates a random variant each time it infects a new program.
2.1 7 well-known Polymorphic Techniques
The di erent polymorphic variants of the code shown in Figure 2.1(a) are shown
in Figure 2.1(b)-2.1(h). The di erent techniques are described below:
2.1.1 Variable Renaming
Identi er names are changed by keeping the correctness of the program. It is the
weakest form of polymorphism.