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
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;
Conference_Titel :
High Performance Switching and Routing (HPSR), 2014 IEEE 15th International Conference on
Conference_Location :
Vancouver, BC
DOI :
10.1109/HPSR.2014.6900887