NDLI: SRD-DFA: Achieving Sub-rule Distinguishing with Extended DFA Structure

Content Provider	IEEE Xplore Digital Library
Author	Gao Xia Xiaofei Wang Bin Liu
Copyright Year	2009
Abstract	Deep Packet Inspection (DPI) relies highly on regular expression due to its power of description, generalization and flexibility. In DPI, packet payload is compared against a large number of rules written in regular expression. To achieve high throughput, multiple regular expressions are combined and compiled into one DFA, which leads to two problems: a) State explosion; b) Sub-rule distinguishing in the combined ruleset. While the first problem has been extensively studied in the recent years, we did not find any literature which formally discusses the second problem in detail. We formulate it and propose Sub-Rule Distinguishable DFA (SRD-DFA), an extended DFA structure, and develop techniques to distinguish sub-rules from multiple regular expressions upon this structure. SRD-DFA can achieve the same throughput as minimized DFA, since it only incurs little extra memory consumption without extra run-time computation. Experimental results under the L7-filter ruleset and a subset of Snort ruleset demonstrate that our approach achieves 8 to 14 times higher throughput than the DFA without rule combination, while only introducing less than 8.4% overhead of state increase compared to the minimized DFA after rule combination. SRD-DFA can be easily used with advanced DFA compression algorithms to achieve much less memory consumption.
Starting Page	723
Ending Page	728
File Size	310686
Page Count	6
File Format	PDF
ISBN	9780769539294
e-ISBN	9781424454211
DOI	10.1109/DASC.2009.71
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-12-12
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Doped fiber amplifiers Inspection Throughput Minimization Explosions Engines Computer science Regular Expression Automata Intrusion detection Pattern matching DFA Power engineering and energy
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

DFA-Based Regular Expression Matching on Compressed Traffic

Pattern-Based DFA for Memory-Efficient and Scalable Multiple Regular Expression Matching

Scalable TCAM-based regular expression matching with compressed finite automata

SRD-DFA: Achieving Sub-Rule Distinguishing with Extended DFA Structure

A Comparative Study on DFA-Based Pattern Matching for Deep Packet Inspection

Fast and memory-efficient regular expression matching for deep packet inspection

Reorganized and Compact DFA for Efficient Regular Expression Matching

An Extended Automata to Efficiently Match Counting Constraints Patterns

A multiple regular expressions matching architecture for network intrusion detection system

SRD-DFA: Achieving Sub-rule Distinguishing with Extended DFA Structure

Similar Documents

DFA-Based Regular Expression Matching on Compressed Traffic

Pattern-Based DFA for Memory-Efficient and Scalable Multiple Regular Expression Matching

Scalable TCAM-based regular expression matching with compressed finite automata

SRD-DFA: Achieving Sub-Rule Distinguishing with Extended DFA Structure

A Comparative Study on DFA-Based Pattern Matching for Deep Packet Inspection

Fast and memory-efficient regular expression matching for deep packet inspection

Reorganized and Compact DFA for Efficient Regular Expression Matching

An Extended Automata to Efficiently Match Counting Constraints Patterns

A multiple regular expressions matching architecture for network intrusion detection system

SRD-DFA: Achieving Sub-rule Distinguishing with Extended DFA Structure