Paper Info
Title
Design and optimizations for efficient regular expression matching in DPI systems
Abstract
Efficient techniques for pattern matching are essential in a number of networked systems and services, such as intrusion detection systems, application identification and classification services, and traffic management. Most pattern matching applications describe patterns using regular expression and the support engine is Deterministic Finite Automaton (FA). Previous research studies address either performance or space requirements issues. From the original DFA formalism we design and evaluate optimizations to its representation and operation to meet Deep Packet Inspection (DPI) systems' requirements for commodity platforms, such as (i) decreasing the original DFA memory consumption (high compression ratio) and (ii) performing pattern matching as fast as the original DFA. Our approach spans from designing the DFA to developing memory layouts to get the most of the underlying architecture. The contributions of this work are threefold: (i) a new and improved finite automaton model, called Ranged Compressed DFA (RCDFA), (ii) three RCDFA optimizations for achieving more compression and matching speed, and (iii) three advanced layouts for implementing the compressed automaton without memory and performance penalties. The experimental evaluation shows that RCDFA compresses DFA up to 99% without imposing additional memory lookups. The proposed advanced layouts reach memory compression of around 97%. RCDFA together with the advanced layouts outperforms the standard DFA by up to 32 times in terms of processing speed.
Year
DOI
Venue
2015
10.1016/j.comcom.2014.12.011
Computer Communications
Keywords
Field
DocType
DFA optimization,Deep Packet Inspection,Performance evaluation,Computer network
Deep packet inspection,Regular expression,Deterministic finite automaton,Computer science,Automaton,Finite-state machine,Real-time computing,Compression ratio,Pattern matching,Intrusion detection system
Journal
Volume
Issue
ISSN
61
C
0140-3664
Citations 
PageRank 
References 
4
0.39
17
Authors
5
Name
Order
Citations
PageRank
Rafael Antonello1343.33
Stenio F. L. Fernandes2707.42
Djamel Sadok337157.81
Judith Kelner428831.23
Géza Szabó5958.87