Hybrid Finite Automata-Based Algorithm for Large Scale Regular Expression Matching

Wei He; Yun Fei Guo; Hong Chao Hu

doi:10.4028/www.scientific.net/AMM.263-266.3108

Paper Titles

The Security Risk and Protection of Distribution Automation System
p.3091

A Steganalysis Based on OC-SVM and Two Clustering Methods
p.3096

A Watermarking Scheme Based on NSCT Using Computer-Generated Hologram
p.3100

Blind Detection of Tampered JPEG Image Based on Blocking Artifacts of Double Quantization
p.3104

Hybrid Finite Automata-Based Algorithm for Large Scale Regular Expression Matching
p.3108

Influence of Path Attacks on Security of Six-State Scheme
p.3114

Reconfigurable Aggregated Multicast Scheme Based on QoS Categories and Tree Similarity
p.3120

Research on Micro-Certificate Based Security System for Internet of Things
p.3125

The Security Protection and Technology Analysis of Information System
p.3130

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 263-266Hybrid Finite Automata-Based Algorithm for Large...

Hybrid Finite Automata-Based Algorithm for Large Scale Regular Expression Matching

Abstract:

Fast data transmission put forward high requirements on network content matching (NCM). Due to the high time complexity, Nondeterministic Finite Automata (NFA) was unable to meet the demand of regular expression matching (REM) which was the core of NCM; Transfer NFA to Deterministic Finite Automaton (DFA) could enhance the throughput, but led to state explosion, which increased demand for memory. To balance memory and throughput, state explosion in the transformation from NFA to DFA has been analyzed and a new method DC-DFA is presented for large scale REM. DC-DFA is based on hybrid automata structure which composed of NFA and DFA. DC-DFA introduces GradeOne classification to cut the memory usage and deep classification to improve throughput. The results show that for serious state explosion, DC-DFA could reduce 75% DFA states and improve memory utilization efficiently while maintain high system throughput.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 263-266)

Pages:

3108-3113

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.263-266.3108

Citation:

Cite this paper

Online since:

December 2012

Authors:

Wei He*, Yun Fei Guo, Hong Chao Hu

Keywords:

Deep Classification, Hybrid Structure, Regular Expression, State Explosion

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] A. R. Meyer and M. J. Fischer. Economy of description by automata grammars and formal systems. In Proc. of Sym. on Switching and Automata Theory (SWAT '71), pages 188–191, Washington, DC, USA,1971. IEEE Computer Society.

DOI: 10.1109/swat.1971.11

Google Scholar

[2] Yaxuan Qi, K.W.J.F., FEACAN: Front-End Acceleration for Content-Aware Network Processing, in INFOCOM. 2011.

DOI: 10.1109/infcom.2011.5935021

Google Scholar

[3] Hoang Le, V.K.P., A Memory-Efficient and Modular Approach for Large-Scale String Pattern Matching. 2012.

Google Scholar

[4] Yaxuan Qi, Multifiled Packet Classification Algorithm. 2011. Tsinghua University. Beijing.

Google Scholar

[5] Fang Yu, Zhifeng Chen, Yanlei Diao, T. V. Lakshman, and Randy H.Katz. Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection. In Proc. of Sym. on Archit. for Netw. and Comm. Systems (ANCS), pages 93–102, 2006.

DOI: 10.1145/1185347.1185360

Google Scholar

[6] Michela Becchi and Patrick Crowley. A Hybrid Finite Automaton for Practical Deep Packet Inspection. In ACM CoNEXT, pages 1–12, 2007.

DOI: 10.1145/1364654.1364656

Google Scholar

[7] Yi-Hua E. Yang, V.K.P., Space-Time Tradeoff in Regular Expression Matching with Semi-Deterministic Finite Automata, in IEEE INFOCOM. 2011.

DOI: 10.1109/infcom.2011.5934986

Google Scholar