@inproceedings{65c680b13c2446a8992c75834c6638b1,
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.",
keywords = "ordered binary decision diagram (OBDD), pattern matching, regular expression, submatch, tagged-nfa",
author = "Liu Yang and Pratyusa Manadhata and William Horne and Prasad Rao and Vinod Ganapathy",
year = "2012",
doi = "10.1145/2396556.2396594",
language = "American English",
isbn = "9781450316859",
series = "ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems",
pages = "163--173",
booktitle = "ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems",
note = "8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2012 ; Conference date: 29-10-2012 Through 30-10-2012",
}