Algorithms to accelerate multiple regular expressions matching for deep packet inspection

By S. Sushanth Kumar, Sarang Dharmapurikar, Fang Yu, P. Crowley, Jonathan S. Turner. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2006

569 citations recorded by the source corpus.

There is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement simple string matching algorithms to match packets against a large, but finite set of strings. owever, there is growing interest in the use of regular expression-based pattern matching, since regular expressions offer superior expressive power and flexibility. Deterministic finite automata (DFA) representations are typically used to implement regular expressions. However, DFA representations of regular expression sets arising in network applications require large amounts of memory, limiting their practical application.In this paper, we introduce a new representation for regular expressions, called the Delayed Input DFA (D2FA), which substantially reduces space equirements as compared to a DFA. A D2FA is constructed by transforming a DFA via incrementally replacing several transitions of the automaton with a single default transition. Our approach dramatically reduces the number of distinct transitions between states. For a collection of regular expressions drawn from current commercial and academic systems, a D2FA representation reduces transitions by more than 95%. Given the substantially reduced space equirements, we describe an efficient architecture that can perform deep packet inspection at multi-gigabit rates. Our architecture uses multiple on-chip memories in such a way that each remains uniformly occupied and accessed over a short duration, thus effectively distributing the load and enabling high throughput. Our architecture can provide ostffective packet content scanning at OC-192 rates with memory requirements that are consistent with current ASIC technology.

Subfields: Artificial Intelligence, Hardware and Architecture, Organic Chemistry

View Paper: https://www.semanticscholar.org/paper/3474677009bdbaeca42b5aaf0e666b1c9cb7bc86

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Muhammad Yasin
2. Jeyavijayan Rajendran
3. Ozgur Sinanoglu

In Hardware and Architecture

1. Muhammad Yasin
2. Ozgur Sinanoglu
3. Jeyavijayan Rajendran
4. M. Ashraf
5. M. Nabeel
6. A. Sengupta

Citations in the corpus

• Provably-Secure Logic Locking: From Theory To Practice (2017, background): “Examples include processors with to-be-protected address spaces, for which access is granted only to restricted entities [8]; network-on-chip (NoC) routers where certain IP address ranges may carry particular semantics [12]; intrusion detection systems that rely on paŠern matching [24]; and digital ”