Thus, the traditional approach appears wasteful; the automaton
unnecessarily bloats up in size as it attempts to represent the entire
signature even though the tail portions are rarely visited. Rather,
the tail portions can be isolated from the automaton, and put to
sleep during normal traffic conditions and woken up only when
they are needed. Since the traditional approach is unable to
perform such selective sleeping and keeps the automaton awake
for the entire signature, we call this deficiency insomnia.
In other words, insomnia can be viewed as the inability of the
traditional pattern matchers to isolate frequently visited portions
of a signature from the infrequent ones. Insomnia is dangerous
due to two reasons i) the infrequently visited tail portions of the
reg-exes are generally complex (contains closures, unions, and
length restrictions) and long (more than 80% of the signature),
and ii) the size of fast representations of reg-exes (e.g. DFA)
usually increases exponentially with the length and complexity of
an expression. Thus, without a cure from insomnia, a DFA of
hundreds of reg-exes may become infeasible or will require
enormous amounts of memory.
An obvious cure to insomnia will essentially require an isolation
of the frequently visited portions of the signatures from the
infrequent ones. Clearly, frequently visited portions must be
implemented with a fast representation like a DFA and stored in a
fast memory in order to maintain high parsing rates. Moreover,
since fast memories are less dense and limited in size, and fast
representations like DFA usually suffer from state blowup, it is
vital to keep such fast representations compact and simple.
Fortunately, practical signatures can be cleanly split into simple
prefixes and suffixes, such that the prefixes comprise of the entire
frequently visited portions of the signature. Therefore, with such a
clean separation in place, only the automaton representing the
prefixes need to remain active at all times; thereby, curing the
traditional approach from insomnia by keeping the suffix
automaton in a sleep state most of the times.
There is an important tradeoff involved in such a prefix and suffix
based pattern matching architecture. The general objective is to
keep the prefixes small, so that the automaton which is awake all
the time remains compact and fast. At the same time, if the
prefixes are too small then normal data streams will match them
very often, thereby waking up the suffixes more frequently than
desired. Notice that, during anomalous conditions the automaton
representing the suffixes will be triggered more often; however,
we discuss such scenarios later. Under normal conditions, the
architecture must therefore balance the tradeoff between the
simplicity of the fast automaton and the dormancy of the slow
automaton.
We refer to the automaton which represents the prefixes as the
fast path and the other automata as the slow path. Fast path
remains awake all the time and parses the entire input data stream,
and activates the slow path once it finds a matching prefix. There
are two expectations. First, the slow path should be triggered
rarely. Second, the slow path should process a small fraction of
the input data; hence it can use a slow memory technology and a
compact representation like a NFA, even if it is relatively slow. In
order to meet these expectations, we must ensure that the normal
data streams either do not match the prefixes of the signatures or
match them rarely. Additionally, even after a prefix match, the
slow path processing should not continue for a long time. The
likelihood that these two expectations will be met during normal
traffic conditions will depend directly upon the signatures and the
positions where they are split into prefixes and suffixes. Thus, it is
critically important to decide these split positions and we describe
our procedure to compute these in the next section.
4.1 Splitting the regular expressions
The dual objectives of the splitting procedure are that the prefixes
remain as small as possible, and at the same time, the likelihood
that normal data matches these prefixes is low. The probability of
matching a prefix depends upon its length and the distribution of
various symbols in the input data. In this context, it may not be
acceptable to assume a uniform random distribution of the input
symbols (i.e. every symbol appears with a probability of 1/256)
because some words appear much more often than the others (e.g.
“HELO” in an ICMP packet). Therefore, one needs to consider a
trace driven probability distribution of various input symbols [6].
With these traces, one can compute the matching probability of
prefixes of different lengths under normal and attack or
anomalous traffic. This probability will establish the rate at which
slow path will be triggered.
In addition to the “matching probabilities”, it is important to
consider the probabilities of making transitions between any two
states of the automaton. This probability will determine how long
the slow path will continue processing once it is triggered. These
transition probabilities are likely to be dependent upon the
previous stream of input symbols, because there is a strong
correlation between the occurrences of various symbols, i.e. when
and where they occur with respect to each other. The transition
probabilities as well as the matching probabilities can be assigned
by constructing an NFA of the regular expressions signatures and
parsing the same against normal and anomalous traffic.
More systematically, given the NFA of each regular expression,
we determine the probability with which each state of the NFA
becomes active and the probability that the NFA takes its different
transitions. Once these probabilities are computed, we determine a
cut in the NFA graph, so that i) there are as few nodes as possible
on the left hand side of the cut, and ii) the probability that states
on the right hand side of the cut is active is sufficiently small. This
will ensure that the fast path remains compact and the slow path is
triggered only occasionally. While determining the cut, we also
need to ensure that the probability of those transitions which
leaves some NFA node on the right hand side and enters some
other node on the same side of the cut remains small. This will
ensure that, once the slow path is triggered, it will stop after
processing a few input symbols. Clearly, the cut computed from
the normal traffic traces and from the attack traffic are likely to be
different, thus the corresponding prefixes will also be different.
We adopt the policy of taking the longer prefix. Below, we
formalize the procedure to determine cuts in the NFA graphs.
Let p
s
: Q → [0, 1] denote the probability with which the NFA
states are active. Let the cut divides the NFA states into a fast and
a slow region. Initially, we keep all states in the slow region; thus
the slow path probability p is
s
p
. Afterwards, we begin
moving states from the slow region to the fast region. The
movements are performed in a breadth first order beginning at the
start state of the NFA, and those states are moved first, whose
probabilities of being active are higher. After a state s is moved to
the fast region, p
s
[s] is reduced from the slow path probability p.
We continue these movements, until the slow path probability, p