|
|
||
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. |
