Research On Regular Expression Grouping Based On Artificial Fish School Algorithm

In the face of increasingly complex network attacks,traditionally matching based on precise string is not suitable for the complex and changeable high-speed network environment.Regular expressions which have the characteristics of flexiblity,efficiency and strong expressive ability are quickly becoming the description language widely used in matching engine to describe network protocol,virus characteristic and so on.Deep Packet Inspection technology adopts regular expression to describe network protocol.Regular expressions have the advantage of flexibility,efficiency and strong expression ability,besides,multiple regular expressions can be merged to generate a single DFA engine which can match all regular expressions by scanning input character at one times.A phenomenon that,however,“state explosion” when regular expressions are complied into a single DFA engine.In the theoretical worst case,the number of DFA states shows exponential growth,resulting a huge memory space requirements.General personal computer hardware platforms is not competent for pattern matching which based on regular expressions.A reasonable grouping of regular expression is an important way to solve the state inflation because of the shortage of storage space.It is an excellent way to group regular expressions into differfent groups through a reasonable combination and separation,however,the existing grouping algorithms are not good enough.In other words,the existing grouping did not find an appropriate compromise between the number of groups and the total number of DFA states,futher more,the existing algorithms fails to achieve optimization not only the number of groupings but also total number of DFA states.Firstly,we analyze the overseas and domestic research status of grouping regular expressions and its insufficient.Secondly,in order to improve the shortcoming of the current grouping algorithm,the minimal collision rate algorithm and minimum new conflict algorithm are proposed.In the minimum conflict grouping algorithm,we redefine the merger and separation strategy,and the experiment shows that the minimum conflict grouping algorithm have better grouping results than the Becchi algorithm.Finally,in order to improve time cost of algorithm execution,minimum new conflict algorithm is innovatively proposed.In this grouping algorithm,we assume that the conflicts beween each regular expression is independent.And the simulation experiments show that this grouping algorithm can greatly compress algorithm execution time under the condition that without sacrificing well grouping results.In Chapter 3,we take advantage of the swarm intelligent algorithm to solve the regular expression grouping problem.The grouping regular expression algorithm based on artificial fish school algorithm is proposed(GRE-AFSA).By take full advantage of the global optimization ability of artificial fish school algorithm and the optimal grouping characteristics of the minimum new conflict algorithm,the distance of artificial fish is redefined and the foraging behavior of artificial fish was improved.Compared with GRE-ACO,GRE-PSO and GRE-SFLA,the GRE-AFSA can search a better grouping results that fewer total DFA states and fewer grouping numbers than GRE-ACO,GRE-PSO and GRE-SFLA.In chapter 4,we try some of improvements that related to artificial fish school algorithm.A regular expression grouping algorithm based on artificial fish swarm algorithm and ant colony algorithm(GRE-ACO-AFSA)is creatively proposed.In GRE-ACO-AFSA,An ant colony algorithm is used to decode the artificial fish code,and the minimum new conflict grouping strategy is adopted in the grouping strategy.It can be seen from the simulational experimental results that the GRE-ACO-AFSA algorithm can optimize the algorithm execution time while ensuring better grouping results.Finally,we tried to use the characteristics of high convergence accuracy and the ability of stable convergence of multi-population artificial fish swarm algorithm,becchi function was adopted to evaluate the food concentration of artificial fish.the experimental results show that,compared with the traditional Becchi grouping algorithm,there are large optimizations in grouping results.