Information Technology Reference
In-Depth Information
There have been studies on modeling normal behavior using finite state automata
[8, 12, 16]. The sequences recognized by the finite automaton are considered normal
behavior, and those rejected are considered abnormal. The advantages of finite auto-
mata over the sequences of fixed length are that they can recognize infinitely many
sequences and that they can learn to recognize new patterns through training. How-
ever, the procedure of constructing finite automata has been done manually. In this
paper, we present algorithms to automatically construct finite automata recognizing
normal behavior, and show the performance and efficiency of the system through
experiments and analysis.
2
Related Works
Forrest et al. introduced the use of system call sequences to model program behaviors
[4, 6, 17]. They extract the short sequences of fixed length from the long sequence of
system calls generated by processes, called N-grams, and maintain the database of
such sequences. When a program is monitored, the N-grams are extracted and
matched against the ones in the database of normal sequences. If the miss ratio ex-
ceeds the given threshold, a warning is issued. The use of system call sequences has
been proven to be a very effective way to intrusion detection. However, since short
sequences of fixed length are used, the intruder can dodge detection by carefully in-
serting spurious system calls within the fixed window size in order not to exceed the
threshold.
Wagner et al. use finite automata to represent the result of profiling normal behav-
ior of programs using static analysis of programs [16]. Since this approach analyzes
the source code of the program, it has difficulty in modeling various processes gener-
ated at runtime.
Sekar et al. examine the program counters where the system calls are made [12].
States and edges of finite automata are labeled by program counters and system calls,
respectively. This approach facilitates the construction of finite automata, but has
difficulty in stack traversal and dealing with fork/exec to trace program counters.
Kosoresow et al. substitute macros for frequently occurring substrings of the sys-
tem call sequence, and then construct finite automata recognizing the system call
sequences generated by processes [8]. By introducing macros the system call se-
quences become shorter, and consequently the resulting automaton becomes smaller.
This approach has neither the weakness of the N-gram method nor the difficulty of
tracing program counters. However, the procedure of selecting macros and construct-
ing finite automata are carried out manually using human insight and intuition. In this
paper, we present our study on how to automatically select macros and construct
automata.
3
Automatic Generation of Finite Automata
We construct finite automata that model normal behavior of programs. In the profiling
stage, the sequences of system calls made by the processes are collected. Then a finite
automaton recognizing these sequences is constructed. Once the finite automaton is
constructed, it is used to monitor the executions of the program. If the sequences of
the system calls made by the processes are accepted by the finite automaton, then the
