Information Technology Reference
In-Depth Information
Automatic Generation of Finite State Automata
for Detecting Intrusions Using System Call Sequences
*
Kyubum Wee
1
and Byungeun Moon
2
1
Ajou University, Suwon, S. Korea 442-749
kbwee@ajou.ac.kr
2
SitecSoft, Seoul, S. Korea 135-090
lovtea@sitecsoft.com
Abstract.
Analysis of system call sequences generated by privileged programs
has been proven to be an effective way of detecting intrusions. There are many
approaches of analyzing system call sequences including N-grams, rule induc-
tion, finite automata, and Hidden Markov Models. Among these techniques use
of finite automata has the advantage of analyzing whole sequences without im-
posing heavy load to the system. There have been various studies on how to
construct finite automata modeling normal behavior of privileged programs.
However, previous studies had disadvantages of either constructing finite auto-
mata manually or requiring system information other than system calls. In this
paper we present fully automatized algorithms to construct finite automata rec-
ognizing sequences of normal behaviors and rejecting those of abnormal behav-
iors without requiring system information other than system calls. We imple-
mented our algorithms and experimented with well-known data sets of system
call sequences. The results of the experiments show the efficiency and effec-
tiveness of our system.
1
Introduction
Intrusion detection techniques can be broadly classified into two classes: misuse de-
tection and anomaly detection. Misuse detection tries to find signatures of intrusion
by looking up the known patterns of attack. Anomaly detection maintains normal
patterns of behavior and issues an alarm when the system being monitored shows
abnormal behavior. Anomaly detection techniques are studied actively, because they
have the advantage of being able to detect previously unknown patterns of intrusions.
One of the most important factors of anomaly detection is how to profile normal
behaviors. In particular, it should be able to accommodate normal behaviors that are
not directly observed while the patterns of normal behavior are collected.
There are many techniques of profiling normal behavior including statistical ap-
proach [3, 7, 9, 10, 14], neural networks [2], and Hidden Markov Models (HMM)
[17]. Forrest introduced the technique of analyzing system call sequences [4, 6, 17]. It
maintains the database of normal sequences of fixed length. It gives an alarm if the
difference between the sequence being monitored and the one in the database exceeds
the given threshold.
*
This work was supported partly by the Brain Korea 21 Project and partly by the Institute of
Information Technology Assessment research project C1-2002-088-0-3.
