Information Technology Reference
In-Depth Information
behavior of the program is considered to be normal. If some of the sequences are
rejected by the automaton, then the program is believed to behave abnormally and an
intrusion is suspected.
We construct the finite automata through three stages. Firstly, frequently occurring
substrings of system call sequences are selected and replaced by macros. This proce-
dure is to shorten the lengths of the sequences and consequently to reduce the size of
the resulting finite automata. Another positive effect of designating macros is that any
intrusion resulting in alteration of the substring corresponding to a macro will be
detected. Secondly, the sequences are aligned in such a way that the substrings occur-
ring commonly across several sequences are positioned at the same columns. Thirdly,
a finite automaton recognizing these aligned sequences is constructed.
3.1
Macro Selection
To select macros we used an algorithm for finding the substrings that occur more than
given number of times in the string [15]. This algorithm makes use of the data struc-
ture called
suffix trie
. Suffix tries are slightly different from suffix trees in that each
edge is labeled by only one symbol [5].
A suffix trie of a string is constructed after the special symbol $ is attached to the
end of the string. In a suffix trie, the labels along the path from the root to a leaf node
represent a suffix of the string. Hence a path from the root to an internal node
N
represents a substring
w
, and the number of leaf nodes in the subtree whose root is
N
is equal to the number of occurrences of
w
in the string. For example, in figure 1, the
suffix trie tells that the substring
ca
occurs twice in the string
acabca
. Note that the
path from the root to node
N
is labeled
ca
, and the subtree with root
N
has two leaf
nodes.
By making use of the fact just mentioned above, we can compute the frequency of
every substring. Then we compute the amount of reduction that can be obtained by
replacing every occurrence of the given substring by a macro. We select the one that
brings the most reduction on the sequence length to be a macro and replace every
occurrence of the substring by the macro. This procedure is repeated until there is no
more reduction of sequence length.
Fig. 1.
Suffix trie of
acabca
