XFAs: Fast and Compact Signature Matching
Randy Smith, Cristian Estan, Somesh Jha
UW CS technical report 1610, August 2007
Deep packet inspection required by network devices, such as
intrusion detection systems, is becoming a performance bottleneck.
Deterministic finite automata (DFAs) are a popular
solution to this problem because they are fast and because it
is possible to combine the DFAs corresponding to multiple
signatures into a single DFA. But combining DFAs recognizing
complex signatures leads to an explosive increase in
memory usage. To counter this effect current systems use
multiple DFAs each recognizing a subset of the signatures
and each is matched separately against the traffic.
In this paper, we present extended finite automata (XFAs),
an alternative to DFAs that avoids state-space explosion problems.
XFAs extend DFAs with a few bytes of "scratch memory"
used to store bits and counters which record progress.
Simple programs associated with automaton states manipulate
this scratch memory. XFAs are deterministic in their
operation, are equivalent to DFAs in expressiveness, and require
no custom hardware support. Measurements of our
fully functional prototype XFA implementation show that
for most signature sets XFAs are at least tens of thousands of
times smaller than the DFA matching all signatures. Compared
to various configurations using multiple DFAs, the
XFA is 10 times smaller and 5 times faster or 5 times smaller
and 20 times faster.
This work is currently under submission. Please email us if you want a copy of the full paper.