Research Of Large-Scale Pattern Matching Algorithm Based On Network Security System

Pattern matching as one of the core module of network security system, its efficiency will directly affect the overall performance of the system, so the pattern matching algorithm has been the hot issue to the academia. With the development of big data and cloud computing era, the amount of data on the network is more and more big, network security system needs to be guarantee high-speed running in the case of high throughput. As the expanding of the patterns on the network security system, the big challenge of the research on the pattern matching algorithm is to deal with the increasingly large number of patterns. Therefore, the research of the pattern matching algorithm has very important significance to adapt to the development of network.Firstly, this thesis introduces the background of the research, and the problems of pattern matching algorithms are analyzed in the grim situation of network security. The principles and the complexities of the classic multi-pattern matching algorithms are introduced. Then, the experimental results of the classic AC algorithm, WM algorithm and SBOM algorithm are summarized and analyzed by setting different conditions in the experiments in this thesis. At the same time, the advantages, disadvantages and the suitable conditions of the classic algorithms are summarized in this thesis.Secondly, in view of the defects of the classic AC algorithm, an improved algorithm for AC algorithm which can greatly reduce the memory space of system is proposed in this thesis. At the same time, according to the characteristics of the widely used patterns in the network security system, three improved methods for the classic WM algorithm are proposed:the optimization of storage structure, the optimization of hash functions and the optimization of patterns. The experimental results show that the improved algorithm has significantly increased performance. With the popularity of multi-core processors, a parallel algorithm based on the automata is proposed. This method can run algorithms separately in each core. The experimental results show: whether shooting is high or low, the algorithm is faster.Finally, according to the analysis to the characteristics of the patterns and texts in the network security system, a matching algorithm based on classification is proposed in this thesis. It combines the optimized AC algorithm and the optimized WM algorithm, respectively, to deal with a subset of the patterns of different lengths. The algorithm avoids the defects of the two kinds of classic algorithms, and it has improved the performance of the system obviously. In the condition of large-scale patterns, the testing results show that the algorithm has obvious advantages.