Research On Multi-dimensional Regular Expression Matching Algorithm For Network Security

Network security has been a major threat to people?s livelihood and country?s base recent years. With the line-speed increase of network bandwidth and the diversification of intrusion patterns, regular expression matching, the most widely used DPI algorithm, has been facing with performance challenges of matching and storage efficiency. DFA based regular expression algorithm is matching efficient, however, the combined compilation of multiple rules containing “.*” may blow up in state and storage space. The issue has been ever difficult and hot in the aspect of regular expression algorithm. Researchers have proposed many DFA improved algorithms to solve this issue, while there are several problems yet: 1) they lack theoretical innovation and thus lack complete compressing of state space; 2) most of them achieve the compressing of state space at cost of un-constant level time complexity, which decreases the matching efficiency and thus cannot be easily applied to IDS. The paper carried on theoretical studied on DFA state explosion from model innovation to algorithm proposing, then algorithm appliance. In this paper, we proposed high-speed and low-storage regular expression model and algorithms. Its main contributions are outlined as follows:1) Multi-dimensional Cube State Transition Diagram(M-D-Cube-STD) is proposed. Firstly, the mess 2-D STD is expanded in the multi-dimensional space and then redundancy states are divided into zero-dimensional ones and one-dimensional ones. At last the former are compressed by dimension, and the later are dynamically built. Theory and experiments show that, focusing on the ideal rules containing “.*”s, state space complexity of this approach reaches the theoretical lower bound, and thus solves the explosion problem caused by the interaction of “.*”s.2) Multi-dimensional Cube DFA(M-D-Cube-DFA) is proposed based on M-D-Cube-STD. Firstly, design ideas are put forwards through the contrast of M-D-Cube-STD and traditional STD. And then the algorithm obtains the information of active state through the springboard of one-dimensional surface, and implements equivalent state transition through the transit of zero-dimensional surface. Theory and experiments results prove that M-D-Cube-DFA reaches the theoretical lower bound of finite automata in matching time and storage space. Experiments results show that M-D-Cube-DFA achieves a logarithmic compression to the exponential increase of state and storage space of DFA at the price of 3~4 times of matching time. Therefore, for the ideal rules containing “.*” in theory, M-D-Cube-DFA solves the state and storage explosion caused by the interaction of “.*”s.3) A regular expression algorithm based on Multi-dimensional Finite Automata(MFA) is proposed. Firstly, the input direction theory of finite automata is proposed concluding that sole DFA improved algorithms cannot fully solve state space compression focusing on the whole rule set. And then rule templates are expanded in the principle in bringing in text-directed feature to decrease signature-directed feature. At last, MFA covers 68.9% of Snort signatures. Theory and experiments results show that, the construction time, storage space and matching time complexity of MFA have a great improvement. Experiments applied MFA to secure rules. Experiments show that, MFA achieves a magnitude compression of the construction time, storage and matching time, compared with several classic DFA improved algorithms.Multi-dimensional regular expression algorithm is efficient in matching and space. It can be a coprocessor of regular expression matching engine in software design and a IP core in the hardware design to address the combined compilation of security signatures containing “.*”s, and thus conquering the DFA state explosion by the interaction of “.*” in regular expressions.