Robust and Scalable String Pattern Matching for Deep Packet Inspection on Multicore Processors

Yi-Hua E. Yang, Viktor K. Prasanna

Abstract

Conventionally, dictionary-based string pattern matching (SPM) has been implemented as Aho-Corasick deterministic finite automaton (AC-DFA). Due to its large memory footprint, a large-dictionary AC-DFA can experience poor cache performance when matching against inputs with high match ratio on multicore processors. We propose a head-body finite automaton (HBFA), which implements SPM in two parts: a head DFA (H-DFA) and a body NFA (B-NFA). The H-DFA matches the dictionary up to a predefined prefix length in the same way as AC-DFA, but with a much smaller memory footprint. The B-NFA extends the matching to full dictionary lengths in a compact variable-stride branch data structure, accelerated by single-instruction multiple-data (SIMD) operations. A branch grafting mechanism is proposed to opportunistically advance the state of the H-DFA with the matching progress in the B-NFA. Compared with a fully populated AC-DFA, our HBFA prototype has $({<} 1/5)$ construction time, requires $({<} 1/20)$ runtime memory, and achieves 3x to 8x throughput when matching real-life large dictionaries against inputs with high match ratios. The throughput scales up 27x to over 34 Gbps on a 32-core Intel Manycore Testing Lab machine based on the Intel Xeon X7560 processors.
BibTeX
@article{yang2013robust,
  author = {Yi-Hua E. Yang and Viktor K. Prasanna},
  title = {{Robust and Scalable String Pattern Matching for Deep Packet Inspection on Multicore Processors}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2013},
  url = {https://openreview.net/forum?id=zcBtKod44x},
}

Loading related content...

Figure