Name
Abstract | ||
|---|---|---|
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 symbolic representation of NFAs that retains their space-efficiency while 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 remaining as compact as NFAs. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-15512-3_4 | RAID |
Keywords | Field | DocType |
extensive use,deterministic automaton,symbolic representation,nfa-obdd-based representation,finite automaton,binary decision diagram,attack signature,improving nfa-based signature,well-known time-space tradeoff,regular expression,traditional nfas,space tradeoff,finite automata | File Transfer Protocol,Network intrusion detection,Regular expression,Computer science,Automaton,Algorithm,Binary decision diagram,Theoretical computer science,Finite-state machine | Conference |
Volume | ISSN | ISBN |
6307 | 0302-9743 | 3-642-15511-1 |
Citations | PageRank | References |
10 | 0.63 | 39 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liu Yang | 1 | 10 | 0.63 |
| Rezwana Karim | 2 | 65 | 4.68 |
| Vinod Ganapathy | 3 | 713 | 42.69 |
| Randy Smith | 4 | 10 | 0.63 |