基于遗传算法的正则表达式规则分组优化

1)深圳大学信息工程学院,深圳 518060; 2)清华大学信息技术研究院,北京 100084

人工智能; 正态自适应遗传算法; 深度包检测; 正则表达式; 分组算法; 网络安全

Regular expression grouping optimization based on genetic algorithm
Cai Liangwei1, Cheng Lu1, Li Jun2, and Li Xia1

Cai Liangwei1, Cheng Lu1, Li Jun2, and Li Xia11)College of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China2)Research Institute of Information Technology, Tsinghua University, Beijing 100084, P.R.China

artificial intelligence; normal adaptive genetic algorithm; deep packet inspection; regular expression; grouping algorithm; network security

DOI: 10.3724/SP.J.1249.2015.03281

备注

为解决正则表达式匹配问题,提出一种基于正态自适应遗传优化的改进正则表达式分组算法.根据迭代次数的变化,利用正态函数自适应改变交叉概率Pc和变异概率Pm, 采取最优保存策略保证最优个体不被数值大的Pc和Pm破坏.结合Becchi算法和局部寻优算法进一步优化.仿真结果表明,该算法能在全局范围内搜索到更好的解,能有效减少状态总数,降低正则表达式匹配的空间复杂度.

An improved optimization method based on normal adaptive genetic algorithm(NAGA)is proposed to solve the matching problem of regular expression grouping(REG), in which the crossover probability and the mutation probability are adaptively changed by a normal function according to the number of iterations. And the optimal preservation strategy is used in REG-NAGA to ensure that the best individual is not destroyed by large Pc and Pm. Additionally, Becchi algorithm and the local optimization algorithm are integrated into REG-NAGA for further optimization. Simulation results show that REG-NAGA can search a better solution in the global scope and reduce the total number of states and the space complexity of regular expression matching effectively.

·