DocumentCode :
239823
Title :
A novel regular expression matching algorithm based on multi-dimensional finite automata
Author :
Yangyang Gong ; Qinrang Liu ; Xiangyu Shao ; Cong Pan ; Huijuan Jiao
Author_Institution :
SoC Lab., NDSC, Zhengzhou, China
fYear :
2014
fDate :
1-4 July 2014
Firstpage :
90
Lastpage :
97
Abstract :
Regular expression matching plays an important role in network security. Regular expression matching is achieved by NFA and DFA. DFA is suitable for high-speed IDS due to its efficiency. However, the combined compilation of multiple rules containing “.*” may blow up in state and storage space. In this paper, we give an explanation to this problem from the prospective of information theory, and propose a multidimensional mathematical model focusing on the most serious state explosion. We divide redundant states into zero-dimensional ones and one-dimensional ones. The former are compressed by dimension, and the later are dynamically built. Theory proof illustrates that the space complexity of the model reaches the theoretical lower bound. Then we propose the multi-dimensional finite automata (MFA) based on the model. Experimental results show that, MFA reduces greatly the construction time, memory and matching time, compared with several typical state-of-the-arts DFA improved algorithms.
Keywords :
computational complexity; computer network security; finite automata; pattern matching; DFA; MFA; NFA; high-speed IDS; information theory; lower bound; multidimensional finite automata; multidimensional mathematical model; network security; one-dimensional state explosion; regular expression matching algorithm; space complexity; state space; storage space; zero-dimensional state explosion; Algorithm design and analysis; Automata; Complexity theory; Explosions; Mathematical model; Redundancy; Security; DFA DPI; IDS; regular expression; state explosion;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High Performance Switching and Routing (HPSR), 2014 IEEE 15th International Conference on
Conference_Location :
Vancouver, BC
Type :
conf
DOI :
10.1109/HPSR.2014.6900887
Filename :
6900887
Link To Document :
بازگشت