Fast Submatch Extraction using OBDDs
Yang, Liu; Manadhata, Pratyusa K.; Horne, William G.; Rao, Prasad; Ganapathy, Vinod
Keyword(s): Regular expression; pattern matching; submatch; tagged-NFA; Ordered Binary Decision Diagram (OBDD)
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.
Additional Publication Information: To be published in the ANCS'12: Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems Austin, Texas, USA, October 2012.
External Posting Date: October 6, 2012 [Fulltext]. Approved for External Publication
Internal Posting Date: October 6, 2012 [Fulltext]