Research On Regular Expression Grouping Algorithm Based On Particle Swarm Optimization

Along with the development of information technology, network application is in-depth used. At the same time, a large amount of different harmful information also pulls into the network. Hence, the more complex network security detection technology is required. Now,the regular expression has become generally preferred in deep packet detection rules for its substantial capacity and flexibility. In order to improve the matching efficiency, the regular expression is usually converted into the form of DFA. The phenomenon of state explosion,however, easily appears when multiple regular expressions generate a DFA, which would result in huge space consumption. Effective and efficient grouping of regular expressions is one of the solution to the problem. However, the existing grouping schemes are either brute force or just considering one index after grouping, which cannot get optimal grouping results.The research background and significance of the regular expressions grouping problem are firstly introduced. The status of grouping regular expressions strategy research at home and abroad is put forward.Secondly, the basic ideas and mechanism of particle swarm optimization algorithm are described in detail. Then, the grouping regular expressions with particle swarm optimization(GRE-PSO) algorithm is proposed which is based on particle swarm optimization, combining the Becchi algorithm. The algorithm defines a concept called index particle. When the index particle finishes updating, the relevant particle is to be updated. An innovative influence strategy of elimination mechanism of local optimal particle is come up with, When the algorithm is into local optimum. For testing the algorithm, the regular expressions test set is selected randomly in the Snort and L7-filter, of which is used by the Becchi open source of regular expression match engine tool to generate the corresponding DFA that is experimental data. The experimental results show that the GRE-PSO could effectively reduce the number of DFA states compared with non-intelligent grouping algorithm like Becchi algorithm.Compared with intelligent grouping algorithm like GRE-ACO(grouping regular expressions with ant colony optimization) algorithm, it overcomes the shortcoming of GRE-ACO that the number of groups is too large which leads to the low efficiency in matching. All in all, notonly does GRE-PSO algorithm optimize the number of DFA states, but it takes the number of optimal groups into consideration. Thus it reduces the regular expression matching complexity.Finally, the paper tries to deal with the grouping regular expressions problem, combining the PSO(particle swarm optimization) and ACO(ant colony optimization). Then a algorithm called GRE-PSO-ACO(grouping regular expressions with PSO and ACO) algorithm is presented. The experimental results demonstrate that the algorithm can overcome the defect of single algorithm and the global optimization is available, especially in the optimization of total DFA states.