(*) Both authors contributed equally
Proceedings of the 13th International Symposium on Recent Advances in Intrusion Detection (RAID 2010). Published as Volume 6307 of Lecture Notes in Computer Science (LNCS), pages 58-78; Ottawa, Canada; September 15-17, 2010.
Network intrusion detection systems (NIDS) make extensive use of regular expressions as attack signatures. Internally, NIDS represent and operate these signatures using finite automata. Existing representations of finite automata present a well-known time-space tradeoff: Deterministic automata (DFAs) provide fast matching but are memory intensive, while non-deterministic automata (NFAs) are space-efficient but are several orders of magnitude slower than DFAs. This time/space tradeoff has motivated much recent research, primarily with a focus on improving the space-efficiency of DFAs, often at the cost of reducing their performance.
This paper presents NFA-OBDDs, a new representation of regular expressions that uses ordered binary decision diagrams (OBDDs) to retain the space-efficiency of NFAs while drastically improving their time-efficiency. Experiments using Snort HTTP and FTP signature sets show that an NFA-OBDD-based representation of regular expressions can outperform traditional NFAs by up to three orders of magnitude and is competitive with a variant of DFAs, while still retaining the space-efficiency of NFAs.
Paper:
[
PDF
]
(© Springer)
Slides:
[
Powerpoint
|
PDF
]
Code and Data:
[
Here
]
DOI:
[
10.1007/978-3-642-15512-3_4
]
Several captions in images, especially those that depict experimental results
and examples of OBDDs, were corrupted by the software that Springer used to
generate the PDF posted on their Web page and therefore do not appear in that
PDF file. Please use the version of the paper posted above instead.
Journal version: This paper is superseded by its journal version, Fast, Memory-efficient Regular Expression Matching with NFA-OBDDs, which appears in Computer Networks. The journal version contains several additional details over the conference version, including experimental results with more traces and an evaluation of the impact of OBDD variable ordering. Please read the journal version instead.