Home
News
People
Projects
Publications
Workshops
Seminar
Software
Conferences
Funding
Collaborations
Resources
Directions

 

Webmaster

Signature Matching using Ordered Binary Decision Diagrams

Description

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.

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

[Top]

Publications

[Top]

People
Faculty

Vinod Ganapathy

Graduate Students

Liu Yang
Rezwana Karim

[Top]

--------------
Last modified: July 2010.