Research On Efficient Pattern Matching Technologies For Network Security

Pattern matching is an important basic research field in computer science.It has beenwidely used in network intrusion detection/prevention systems, virus-anti devices andAnti-Spam applications because of its high accuracy and efficiency. However, as thetype and complexity of attacks on network increase, the pattern sets used in securitysystem become bigger and each pattern becomes more complex. The pattern matching fornetwork security has become a essential research filed. This paper focuses on the efficientpattern matching techniques for the network application and has proposed a number ofalgorithms. The main contributions of this paper includes:(1) A matching model based on data cognition. Many classical matching algorithms'time complexities are near to,or even achieve the best theoretical bound. However, theirperformance may degrade in some cases. Our method considers the statistical featuresof input data as well as the traditional factors when we select matching algorithms forspecific applications. This model processes input data using a set of algorithms instead ofonly one. It analyzes the inputs while processing them, and dynamically selects the bestalgorithm based on the analyzing result and the characteristics of each algorithm. We alsoproposed a selecting method based on statistics of traveling depth and optimized it usingsequential probability ratio test. The proposed method selects algorithm dynamically andhas a better performance than using any one of the algorithms only.(2) A novel method to drastically reduce the memory requirements of DFAs whilestill maintains the high matching speed and provides worst-case guarantees. DFA is oneof the most effective method of regular expression matching. However, its efficiencyis based on using huge memory space to describe every"possibility". We removed theduplicate transitions between states by dividing all the DFA states into a number of groupsand making each group of states share a merged transition table. We also proposed anefficient algorithm for transition sharing between states. The high efficiency in time andspace makes our approach adaptive to frequently updated DFAs.(3) A matching algorithm based on guessing and verification. DFA memory com-paction can save more than 90% memory of original DFA, however, DFA memory re-quirements increase exponentially but DFA memory reduction efficiency is linear. Our method first searches special sub patterns of each rule by DFA, and checks the resultby NFA once the previous guessing is successful. This algorithm takes advantage of thehigh processing efficiency of DFA and compact representation of NFA. It can improve thematching efficiency by reducing the frequency of calling the slower verification behaviors.This method can provide a high throughout as well as a moderate memory requirement.(4) A string expression and its matching method. String expression describes thelogical and position relation of a number of strings. The proposed matching methoduses a two-level matching structure. First, it checks the occurrences of each string usingclassical string matching algorithms, then drives the extended finite automaton using theprevious checking results. Its time and space complexities are near to the classical stringmatching algorithm. It resolves the complex rules matching problem on the large scalebetter.