摘要
经过对正则表达式合并DFA(确定型有限自动机)状态爆炸问题的分析,采用正则表达式两两合并DFA的状态增加数之和衡量多个正则表达式合并后真实的状态增加情况,将正则表达式最优分组问题归约为带权无向图的k-最大割问题。在此基础上,提出了一种面向高效深度包检测的启发式正则表达式分组算法REGEDPI。采用贪婪策略构造初始解,引入移除参数进行迭代优化。实验表明相比于其他算法,REG-EDPI算法能够在合理的运行时间内,获得更优的分组策略,具有更强的实际应用价值。
After analyzing the state explosion problem of DFA( deterministic finite automaton),a combination of two DFAs state increase was used to measure the actual state increase of combination of multiple regular expressions. Make the issue of regular expression optimal grouping reduced to k-maximum cut of weighted undirected graph. On this basis,this paper proposed a heuristic grouping algorithm of regular expression for efficient deep package inspection. The algorithm constructed initial solution by the greedy strategy,and introduced a removal parameter to optimize the solution. Experimental results show that the proposed algorithm can obtain better grouping strategy in reasonable running time,and has more practical value.
引文
[1]刘兴奎,邵宗有,刘新春,等.面向深度包检测的DFA细粒度并行匹配方法[J].计算机研究与发展,2014,51(5):1061-1070.
[2]Sommer R,Vern P.Enhancing byte-level network intrusion detection signatures with context[C]//Proc of the 10th ACM Conference on Computer and Communications.New York:ACM Press,2003:262-271.
[3]丁麟轩,黄昆,张大方.基于并行字符索引的多步长正则表达式匹配算法[J].计算机研究与发展,2015,52(3):681-690.
[4]Xu Chengcheng,Chen Shuhui,Su Jinshu,et al.A survey on regular expression matching for deep packet inspection:applications,algorithms,and hardware platforms[J].IEEE Communications Surveys&Tutorials,2016,18(4):2991-3029.
[5]邵翔宇,刘勤让,谭力波.基于规则模板的正则表达式分组算法[J].电子学报,2016,44(1):236-240.
[6]Liu Tingwen,Yang Yifu,Liu Yanbing,et al.An efficient regular expressions compression algorithm from a new perspective[C]//Proc of INFOCOM.Piscataway,NJ:IEEE Press,2011:2129-2137.
[7]Liu Cong,Pan Yan,Chen Ai,et al.A DFA with extended character-set for fast deep packet inspection[J].IEEE Trans on Computers,2014,63(8):1527-1937.
[8]宫阳阳,刘勤让,杨镇西,等.基于多维有限自动机的DFA改进算法[J].通信学报,2015,36(5):174-186.
[9]敬茂华,杨义先,汪韬,等.新颖的正则NFA引擎构造方法[J].通信学报,2014,35(10):98-106.
[10]Yu Xiaodong,Feng Wuchun,Yao Danfeng,et al.O3FA:a scalable finite automata-based pattern-matching engine for out-of-order deep packet inspection[C]//Proc of Symposium on Architectures for Networking and Communications Systems.New York:ACM Press,2016:1-11.
[11]Yu Fang,Chen Zhifeng,Diao Yanlei,et al.Fast and memory-efficient regular expression matching for deep packet inspection[C]//Proc of ACM/IEEE Symposium on Architectures for Networking and Communications Systems.New York:ACM Press,2006:93-102.
[12]徐乾,鄂跃鹏,葛敬国,等.深度包检测中一种高效的正则表达式压缩算法[J].软件学报,2009,20(8):2214-2226.
[13]Becchi M,Franklin M,Crowley P.A workload for evaluating deep packet inspection architectures[C]//Proc of IEEE International Symposium on Workload Characterization.Piscataway,NJ:IEEE Press,2008:79-89.
[14]Rohrer J,Atasu K,Van Lunteren J,et al.Memory-efficient distribution of regular expressions for fast deep packet inspection[C]//Proc of the7th IEEE/ACM International Conference on Hardware/Software-CoDesign and System Synthesis.New York:ACM Press,2009:147-154.
[15]柳厅文,孙永,卜东波,等.正则表达式分组的1/(1-1/k)-近似算法[J].软件学报,2012,23(9):2261-2272.
