Research On Storage Oriented Regular Expression Matching Algorithms

As the key technology of network security applications, regular expression matching provides significant effect. This thesis researches on the storage oriented regular expression matching algorithms based on deterministic finite automata, in order to meet the requirement of deep packet inspection.The main contents of the thesis include:1. The traditional regular expression matching algorithms are analyzed and compared. By presenting the advantages of algorithm designs based on storage oriented architecture, the storage oriented regular expression matching algorithms are studied, which provide a full range of researches for algorithm designs.2. The regular expression syntax is researched in rule sets, the principles of regular expression matching and their influence on algorithms are analyzed, and the problems of state explosion are discussed, which provide theoretical foundation for algorithm designs.3. A compressed algorithm of state transition table based on sparse matrix is proposed. And based on the algorithm, an optimization strategy is presented by combining the alphabet compressed algorithm. The results show that the compression ratio is generally more than 90% under the Linux L7-filter and Bro rule sets.4. A delayed input deterministic finite automata optimization algorithm of bounding default path is proposed based on weight first policy and node first policy. The results show that when the diameter is bounded small, the memory space could be compressed to some extent.5. A bitmap shift finite automata applied to matching a single counting constraint pattern is proposed aimed at the state explosion caused by a single counting constraint pattern. On the foundation of researches of combining multiple counting constraint patterns, exterior state explosion problem is introduced, and aimed at the problem a high efficient papilionaceous finite automata applied to multiple counting constraint patterns is presented.