Fast submatch extraction using OBDDs

Yang Liu, Pratyusa K. Manadhata, William Horne, Prasad Rao, Vinod Ganapathy2012 · DOI

TL;DR

This paper introduces Submatch-OBDD, a novel approach for efficiently extracting sub-strings (submatches) from network traffic and log data using regular expressions. By leveraging Ordered Binary Decision Diagrams (OBDDs) to represent pattern matching, Submatch-OBDD significantly outperforms existing methods like RE2 and PCRE, especially when multiple patterns are processed together.

What Problem Does This Paper Address?

Network Intrusion Detection Systems (NIDS) and Security Information and Event Management (SIEM) systems heavily rely on pattern matching using regular expressions to analyze vast amounts of data. A crucial feature in these patterns is the "submatch construct," which allows for the extraction of specific parts of a matched string. Existing methods for submatch extraction, primarily based on Non-deterministic Finite Automata (NFAs) or recursive backtracking, suffer from significant performance issues. NFA-based approaches are slow, while backtracking methods are vulnerable to "algorithmic complexity attacks," where specially crafted inputs can cause them to grind to a halt. This leaves a critical gap in efficiently and reliably extracting valuable submatch information from high-speed network traffic and massive log files.

Methods

The core innovation of this paper is the Submatch-OBDD approach. It builds upon prior work on using OBDDs for NFA-based pattern matching but extends it to handle submatch extraction. The key steps are:

  1. Tagging Regular Expressions: The authors introduce a method to annotate capturing groups within regular expressions with unique tags. This is done by extending Thompson's NFA construction algorithm to create "tagged NFAs," where transitions can be associated with these tags.
  2. Boolean Function Representation: These tagged NFAs are then converted into symbolic Boolean functions. This representation captures the state transitions and tag associations in a mathematical form.
  3. OBDD Manipulation: Ordered Binary Decision Diagrams (OBDDs) are used to efficiently represent and manipulate these Boolean functions. OBDDs are a powerful data structure for compactly representing complex Boolean functions and performing operations like conjunction and existential quantification.
  4. Submatch Extraction Algorithm: The paper details how to use these OBDD representations to perform both match testing (determining if a string matches a pattern) and submatch extraction. The extraction process involves a backward traversal on the OBDD representation to identify the specific substrings associated with each tag.

This approach aims to overcome the limitations of NFAs (time inefficiency) and backtracking (vulnerability to attacks) by leveraging the compact representation and efficient operations of OBDDs.

Datasets

The authors evaluated their Submatch-OBDD approach using three sets of patterns and corresponding data:

  • Snort-2009: 115 patterns extracted from the PCRE fields of the Snort 2009 HTTP rule set. These patterns were matched against two web traces (1.2GB and 1.3GB) and one synthetic trace designed to exploit backtracking vulnerabilities.
  • Snort-2012: 403 patterns extracted from the PCRE fields of the Snort 2012 HTTP rule set. These were evaluated on the same web traces as Snort-2009 and a new 1MB synthetic trace.
  • Firewall-504: 504 patterns from a commercial SIEM system used for normalizing firewall logs. These were tested against 87MB of enterprise firewall logs.

Key Insights and Ideas

  • OBDDs for Submatch Extraction: The paper demonstrates that OBDDs, typically used for formal verification and digital logic, can be effectively adapted for efficient submatch extraction in regular expressions. This opens up new avenues for applying these powerful symbolic methods to network security and data analysis.
  • The Power of Combination: The most significant performance gains for Submatch-OBDD were observed when multiple patterns were combined into a single OBDD representation. This highlights the potential for significant speedups in scenarios where a large set of rules needs to be applied simultaneously, such as in SIEM systems.
  • Robustness Against Attacks: By using an NFA-based approach represented by OBDDs, Submatch-OBDD is inherently resistant to the backtracking algorithmic complexity attacks that plague engines like PCRE. This is a critical advantage for security applications where attackers might try to evade detection.
  • Trade-offs in Pattern Matching: The evaluation reveals nuanced performance differences. While Submatch-OBDD excels with combined patterns, individual pattern matching might be slower than highly optimized engines like RE2 in certain simple cases due to the overhead of OBDD operations.

Key Results

  • Significant Speedup: In the best-case scenario (combined patterns), Submatch-OBDD was one to two orders of magnitude faster than RE2 and PCRE.
  • Performance on Real-World Data:
    • For the Snort-2009 dataset, Submatch-OBDD in combined mode was an order of magnitude faster than the best performance of RE2 and PCRE in sequential mode.
  • For the Snort-2012 dataset, Submatch-OBDD was faster than RE2 and PCRE on the synthetic trace, but slightly slower than PCRE on web traces. However, the authors emphasize PCRE's vulnerability to attacks.
  • For the Firewall-504 dataset, Submatch-OBDD was the fastest, with combined mode being orders of magnitude faster than RE2 and PCRE.
  • Resistance to Attacks: PCRE's performance degraded by two to three orders of magnitude on synthetic traces designed to exploit backtracking, while Submatch-OBDD and RE2 showed no such degradation.
  • Memory Efficiency: Submatch-OBDD's memory usage was comparable to RE2, and generally reasonable, though PCRE was often the most memory-efficient.

Limitations and Future Work

  • POSIX Compliance: The paper notes that the submatch assignment produced by Submatch-OBDD is not necessarily the leftmost or longest match required by POSIX standards. However, they argue that POSIX's limitations with greedy/reluctant closures make it incomplete, and many real-world tools deviate from strict POSIX compliance.
  • Optimization Potential: The authors acknowledge that their implementation of Submatch-OBDD is not heavily optimized and believe further improvements are possible.
  • Backreferences: Similar to RE2, Submatch-OBDD does not support backreferences, which are a non-regular construct used in some advanced pattern matching scenarios.
  • Future Work: The paper suggests that further optimization of the OBDD operations and exploring more advanced OBDD manipulation techniques could lead to even greater performance gains. Investigating support for backreferences would also be a valuable extension.

Summary updated

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.
BibTeX
@misc{liu2012fast,
  author = {Yang Liu and Pratyusa K. Manadhata and William Horne and Prasad Rao and Vinod Ganapathy},
  title = {{Fast submatch extraction using OBDDs}},
  year = {2012},
  doi = {10.1145/2396556.2396594},
}
Figure