Paper Info
Title
Fast submatch extraction using OBDDs
Abstract
Network-based intrusion detection systems (NIDS) commonly use pattern languages to identify packets of interest. Similarly, security information and event management (SIEM) systems rely on pattern languages for real-time analysis of security alerts and event logs. Both NIDS and SIEM systems use pattern languages extended from regular expressions. One such extension, the submatch construct, allows the extraction of substrings from a string matching a pattern. Existing solutions for submatch extraction are based on non-deterministic finite automata (NFAs) or recursive backtracking. NFA-based algorithms are time-inefficient. Recursive backtracking algorithms perform poorly on pathological inputs generated by algorithmic complexity attacks. We propose a new approach for submatch extraction that uses ordered binary decision diagrams (OBDDs) to represent and operate pattern matching. Our evaluation using patterns from the Snort HTTP rule set and a commercial SIEM system shows that our approach achieves its ideal performance when patterns are combined. In the best case, our approach is faster than RE2 and PCRE by one to two orders of magnitude.
Year
DOI
Venue
2012
10.1145/2396556.2396594
ANCS
Keywords
Field
DocType
commercial siem system,event log,siem system,recursive backtracking algorithm,submatch extraction,pattern language,pattern matching,event management,new approach,recursive backtracking,regular expression
String searching algorithm,Regular expression,Computer science,Binary decision diagram,Finite-state machine,Theoretical computer science,Security information and event management,Backtracking,Pattern matching,Intrusion detection system
Conference
Citations 
PageRank 
References 
4
0.64
21
Authors
5
Name
Order
Citations
PageRank
Liu Yang1111.16
Pratyusa Manadhata2916.84
William Horne31917.81
Prasad Rao433021.08
Vinod Ganapathy571342.69