Scalable lookahead regular expression detection system for deep packet inspection

Masanori Bando, N. Sertac Artan, H. Jonathan Chao

Research output: Contribution to journalArticle

Abstract

Regular expressions (RegExes) are widely used, yet their inherent complexity often limits the total number of RegExes that can be detected using a single chip for a reasonable throughput. This limit on the number of RegExes impairs the scalability of today's RegEx detection systems. The scalability of existing schemes is generally limited by the traditional detection paradigm based on per-character-state processing and state transition detection. The main focus of existing schemes is on optimizing the number of states and the required transitions, but not on optimizing the suboptimal character-based detection method. Furthermore, the potential benefits of allowing out-of-sequence detection, instead of detecting components of a RegEx in the order of appearance, have not been explored. Lastly, the existing schemes do not provide ways to adapt to the evolving RegExes. In this paper, we propose Lookahead Finite Automata (LaFA) to perform scalable RegEx detection. LaFA requires less memory due to these three contributions: 1) providing specialized and optimized detection modules to increase resource utilization; 2) systematically reordering the RegEx detection sequence to reduce the number of concurrent operations; 3) sharing states among automata for different RegExes to reduce resource requirements. Here, we demonstrate that LaFA requires an order of magnitude less memory compared to today's state-of-the-art RegEx detection systems. Using LaFA, a single-commodity field programmable gate array (FPGA) chip can accommodate up to 25000 (25 k) RegExes. Based on the throughput of our LaFA prototype on FPGA, we estimate that a 34-Gb/s throughput can be achieved.

Original languageEnglish (US)
Article number6216497
Pages (from-to)699-714
Number of pages16
JournalIEEE/ACM Transactions on Networking
Volume20
Issue number3
DOIs
StatePublished - Jun 2012

Keywords

  • DPI
  • Deep packet inspection
  • LaFA
  • Lookahead Finite Automata
  • NIDPS
  • network intrusion detection and prevention system
  • regular expressions

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Scalable lookahead regular expression detection system for deep packet inspection'. Together they form a unique fingerprint.

  • Cite this