Information Technology Reference
In-Depth Information
5
Conclusions
Although finite automata have many advantages in modeling normal behavior of
programs using system call sequences, they have not been used widely, mostly be-
cause they could not be constructed automatically. In this paper we presented algo-
rithms for automatically constructing finite automata through substituting macros for
frequently occurring substrings and aligning multiple sequences. We also imple-
mented our algorithms and experimented using well-known data sets of system call
sequences. The results of experiments showed the perfect detection rate, low false
positive rate, and a better performance than the N-gram approach.
Since our techniques do not require any other information except the system call
sequences from the system, they do not impose much load to the system. Furthermore
finite automata can be constructed in polynomial time, and normality of a given se-
quence can be tested by the automaton in linear time.
Suppose that the number of sequences is
k
, the length of the longest sequence is
m
, and the sum of the lengths of all the sequences is
n
. The time taken to construct
the suffix trie of the sequences is
2
nO
[15]. Since computing the frequency of
every substring takes time proportional to the size of the trie, macro selection takes
)
(
)
2
nO
time. The time complexity of center star method of multiple sequence align-
ment is
(
2
2
O
(
km
+
k
l
)
, where
l
is the length of the aligned sequences [13]. Hence
2
2
2
the total time is
.
We have plans to apply other known automata learning algorithms or devise new
domain-specific automata learning algorithms. We also plan to do elaborate perform-
ance analysis using various data sets of system call sequences.
We have presented algorithms to automatically construct finite automata modeling
normal behaviors of programs using system call sequences. Our algorithms are effi-
cient, and the resulting finite automata are effective in recognizing normal behaviors
and detecting abnormal behaviors. As far as we know, ours is the first study on auto-
matically constructing finite automata for intrusion detection.
O
(
n
+
km
+
k
l
)
References
1. Cormen, T., Leiserson, C., Rivest, R., and Stein, C.:
Introduction to Algorithms
, second ed.,
MIT Press (2001) 350-355
2. Debar, H., Becker, M., and Siboni, D.: A Neural Network Component for an Intrusion De-
tection System. Proceedings of the IEEE Symposium on Security and Privacy (1992) 240-
250
3. Denning, D.: An Intrusion Detection Model. Proceedings of the IEEE Symposium on Secu-
rity and Privacy (May 1986) 119-131
4. Forrest, S., Hofmeyr, S., Somayaji, A., and Longstaff, T.: A Sense of Self for Unix Proc-
esses. IEEE Symposium on Security and Privacy (1996) 120-128
5. Gusfield, D.:
Algorithms on Strings, Trees, and Sequences
, Cambridge University Press,
(1997) 332-350
6. Hofmeyr, S., Forrest, S.: Intrusion Detection using Sequence of System Calls. Journal of
Computer Security, Vol. 6 (1998) 151-180
