The Design And Implementation Of Regular Expression Engines Based On Deterministic Finite Automata

With the development of network security auditing techniques, the phenomenon ofattacks against the application layer becoming more and more. As the flexiblevariability of the regular expression, this audit technology based on it has the ability ofstrong-expression and flexible-scalability, which that based on the string matching doesnot have. A growing number of network audit technology has been using it to describeand support. Traditional reguar expression matching engine is divied in to NFA-basedand DFA-based regular expression matching engine. Because DFA has a widelyapplication in some areas such as network monitoring, its focus position in the lexicalanalysis is more and more prominent. Based on the research and analysis of existingDFA construct engine optimization technology, this paper has studied the optimizationtechnology and implementation program of the DFA engine from two aspects: Firstly,construction and optimization based on a single DFA engine; Secondly, constructionand optimization based on the grouping-algorithm DFAconstruct engine.For the first, we study the regular expressions match ASCII characters in thespecial conditions. In the study of using a subset of the construction method constructsDFA engine process, a subset of the original construction process is optimized, so thatthe generation of a single DFA engine efficiency is greatly improved, and on this basisto achieve a single DFA regular expression matching engine; for the second, DFAregular expressions or similar relationship between the structure, during the study ofusing the grouping method of the process of DFA engine construction, we collected alarge number of test data, proposed the concept of similarity of regular expressions andformulas, and on this basis to achieve a grouping regular expression matching enginebased on grouping method.For the two regular expression engine which have achieved to develop a detailedtest plan, from the time consumption and space occupied, the two engines were madefor targeted performance test, the results show that, both in terms of time consumption,or in the space occupancy, optimized DFA engine is better than no optimizationalgorithm introduced DFAengine.