Genetic Algorithm Optimization For Regular Expression Grouping

With the rapid development of Internet technology, the new network applications and services appear constantly. Accordingly, the rapid expansion of the network bandwidth,cause the size of the set of rules to be detected more and more huge and complex. So powerful regular expression become a new tool to describe rules, and be successfully used in deep packet inspection technology. However, in some cases, state inflation will appear when multiple regular expression generate merger DFA, lead to huge storage space consumption and even unable to make the DFA. Through the collection of regular expressions grouping is the main way to solve this problem. At present, quite a few researchers have studied the grouping algorithm and put forward solutions, But the grouping result is not ideal, the grouping algorithm can’t effectively solve the problem of excessive DFA space consumption and need to be further optimized.Firstly, this paper introduces the research background and meaning of the regular expression grouping and the research status at home and abroad.Secondly, the nearest neighbor optimization algorithm has been introduced in this paper,by defining the DFA state matrix and sorted according to the nearest neighbor principle, then from front to back local optimization search strategy is used to solve the problem of the regular expression grouping; This paper describes briefly the basic principle of genetic algorithm and its application in various fields. To solve the matching problem of regular expressions grouping(REG), we propose an improved optimization method based on nomal adaptive genetic algorithm(NAGA). According to the different emphasis on two factors which are the number of iterations and the degree of concentration of the fitness, regular expression grouping based on normal adaptive genetic algorithm(REG-NAGA) adaptively changes the crossover probability Pc and the mutation probability Pm by a nomal function, and takes the optimal preservation strategy to ensure that the best individual is not destroyed by large Pc and Pm. In addition, REG-NAGA combines the Becchi algorithm and local optimization algorithm to further optimization.Lastly, several regular expressions randomly selected respectively from the snort and L7-filter are regarded as a test set, and we use the regular expression matching engine tool which is opened source by Becchi to generate the DFA as the experimental data, then simulate the algorithm. Simulation results show that the REG-NAGA can search better solution by a global search, thus reduces the total number of states effectively, and decreases the space complexity of the regular expression matching.