基于蚁群优化的正则表达式分组算法

蔡良伟，刘思麒，李 霞，李 军

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

基于蚁群优化的正则表达式分组算法

蔡良伟1，刘思麒1，李 霞1，李 军2

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

依据Becchi算法的思想基础，提出基于蚁群优化的改进正则表达式分组算法.根据正则表达式间分组的特点，定义正负影响关系的冲突信息和启发函数，构建信息素更新策略.实验结果表明，该算法较Becchi算法能更加客观合理地反映模式集中正则表达式间的优化合并信息，能有效减少状态数量，达到总状态数最优解，降低正则表达式匹配的复杂度.

人工智能;蚁群优化算法;深度包检测;正则表达式;分组算法;冲突信息;信息素;网络安全

随着网络资源共享日趋多样性，网络安全问题日益突出.深度包检测 (deep packet inspection，DPI)已被广泛用于网络入侵检测、网络监控和防火墙等网络安全服务中.现有的DPI技术采用精确字符串进行模式匹配，如AC(Aho-Corasick)算法［1］、Wu_Manber算法［2］等.但随着网络的快速发展，网络攻击和恶意代码也日益复杂，精确字符串已很难准确地描述这些入侵特征.因正则表达式(regular expression，RE)具有灵活且表达力强的特点，用正则表达式代替字符串，作为DPI中检测数据包的匹配语言［3］，成为DPI的主要手段.

在要求匹配效率与准确率都较高的情况下，正则表达式常使用确定型有限自动机 (deterministic finite automaton，DFA)来实现.但当多条正则表达式转换为DFA时，会带来状态空间膨胀问题 (某种情况下，DFA的状态数量甚至呈指数增长)，从而消耗巨大的存储空间，甚至使DFA无法生成［4］.因此，如何解决因DFA状态膨胀导致的巨大空间消耗，是实现正则表达式高性能匹配的重要问题.对正则表达式规则进行分组，是解决该问题的重要途径.目前，已有学者对此做了一些研究.如Yu等［4］针对正则表达式集合的分组问题，提出一种启发式分组算法—Yu算法.在计算正则表达式两两之间的冲突作用时，将f条正则表达式分为g组(g≫f)，在不超出内存限制的前提下，将相互冲突作用较小的未分组的正则表达式加入当前分组，若当前组的状态数目已超过所设定的阈值，就进行下一组的归并，最终得到整个正则表达式的分组情况.Becchi等［5-7］提出一种适于合并后DFA状态数量过大时的自动分组策略.肖武德［8］通过计算正则表达式两两之间的冲突比率，并据此参数进行分组.魏强等［9］在 Yu算法的基础上，结合图划分，提出MaxG-MinR算法，通过改进启发搜索方法，减少DFA的状态数和分组数.柳厅文等［10］指出，正则表达式集合的最优K分组问题是NP-hard的，并基于局部搜索的思想，提出GRELs(grouping regular expression with local searching)分组算法.但现有的分组算法分组效果有待提升.如Yu算法，虽分组策略简单，且组数固定，但适用性有限;Becchi算法每次都需按正则表达式的顺序进行循环二分，限制了优化分组范围的扩大.

本研究根据Becchi算法原理，提出基于蚁群优化的改进正则表达式分组 (grouping regular expression with ant colony optimization，GRE-ACO)算法，利用正则表达式之间的冲突信息，构建新的启发函数和信息素更新策略，搜索正则表达式模式集分组的最优解.

1 正则表达式分组与Becchi算法

1.1 正则表达式分组

1.1.1 分组问题

在正则表达式中，有些表达式生成的DFA的状态数量会膨胀，如两条正则表达式(.*ab.*cd)和(.*ef.*gh)，单独转换为 DFA 的状态数量各为 5，如图1［4］;若将这两条正则表达式合并成一个DFA时，就膨胀到16个状态，如图2［4］.在最坏的情况下，合并后的DFA状态数量呈指数增长.对正则表达式集合进行分组的目标是减少DFA的状态数量，即各分组的DFA状态数量总和应小于不分组时合并的DFA状态数量.

图1 (.*ab.*cd)和(.*ef.*gh)单独转换对应的DFA［4］Fig.1 DFA of(.*ab.*cd)and DFA of(.*ef.*gh)［4］

图2 (.*ab.*cd)和(.*ef.*gh)合并转换对应的DFA［4］Fig.2 DFA of(.*ab.*cd)|(.*ef.*gh)［4］

1.1.2 评价指标

评价正则表达式集合分组效果的常用指标是DFA的状态总数和分组数量.

1)考虑DFA的状态总数主要是为减少DFA存储空间.DFA的状态数量对生成和使用DFA时需要占用的存储空间起关键因素，DFA的状态数量越小，它所占用的存储空间就越少.

2)分组数目决定了处理每个字符时状态转移表的访问次数，进而影响正则表达式的匹配速度.

显然，这两个指标之间是相互冲突的.一般情况下，分组数量越大，DFA的状态总数越小;分组数量越小，DFA的状态总数越大.

1.2 Becchi分组算法

设置阈值为

其中，size()为合并规则后生成的状态数;group_before为在下一条正则表达式加入当前组之前，当前组中正则表达式的集合;Rj为下一条正则表达式;α为阈值参数.

在正则表达式模式集中，按照其内正则表达式的排列顺序循环地对模式集进行二分，直至每组的状态数都小于阈值σ，即

其中，group_local表示下一条正则表达式加入到当前组后，当前组中正则表达式的集合.

Becchi算法具体步骤为:

1)以未分组的正则表达式集的第1条表达式，作为当前组的第1条规则;

2)依次尝试将下一条正则表达式加入当前组，若满足size(group_local)＜σ，则该表达式放入当前组.如此循环，直到历遍正则表达式模式集中所有表达式.余下的未被选入当前组的正则表达式，按其在原集合中的顺序排序后分为一组，作为下一未分组的正则表达式集合;

3)判断未分组中的正则表达式集合中表达式是否为0，若是，则输出分组结果;否则，返回1)并继续开始分组.

2 基于蚁群优化的正则表达式分组算法

2.1 蚁群算法

蚁群优化 (ant colony optimization，ACO)算法是人们受蚂蚁觅食行为启发，提出的一种元启发式算法，能解决许多组合优化问题［11-19］.蚂蚁在觅食过程中，通过在经过的路径中释放信息素来标示路径，蚂蚁间则通过交换信息素来寻找最优路径.

蚂蚁k(k=1，2，…，m)在运动过程中，根据各条路径上的信息量决定其转移方向.在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率.在t时刻，蚂蚁k由正则表达式i到正则表达式j的状态转移概率为

其中，s⊂allowedk为蚂蚁k下一步允许的路径，即剩余未被分组的正则表达式集合;τij(t)为t时刻路径(i，j)上的信息素浓度;α为信息启发因子，体现轨迹的相对重要性，反映蚂蚁在运动过程中积累信息的能力，α值越大表示蚂蚁探索能力越强，越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强;β为期望启发因子，体现能见度的相对重要性，反映蚂蚁在运动过程中，启发信息在它选择路径时的受重视程度，β值越大，蚂蚁的开发能力越强，该状态转移概率越接近于贪心规则.

为将蚁群算法应用于正则表达式分组问题，本研究根据正则表达式规则集的特点，重新定义冲突信息、启发函数及信息素更新策略，使蚂蚁的信息素在表达式分组的组内进行分布、累积及更新.

2.1.1 冲突信息

设正则表达式集合R中含n条表达式，任意两条正则表达式Ri和Rj转换后产生的DFA状态数量分别记为size(Ri)和 size(Rj)，而合并后产生的DFA状态数量为Sij.若Sij≥size(Ri)+size(Rj)，则称这两条正则表达式存在正冲突影响;否则，称这两条正则表达式存在负冲突影响.本研究将这种正则表达式之间的冲突影响称为冲突信息.显然，在正则表达式分组过程中，冲突呈负冲突影响的越多越好，因为，只有在负冲突影响下，正则表达式集合合并时，DFA的总状态数量才会减小.

GRE-ACO算法以DFA总状态数最小为最优目标.分组数目越小，越能客观地反映正则表达式规则集内正则表达式的冲突信息以及合并合适程度.可见，分组数目越小越好.

2.1.2 新的启发函数

ηij(t)为t时刻路径(i，j)上的启发函数信息.借鉴冲突信息，以正则表达式分组后总状态数量最小为目标函数的正则表达式集合分组，其表达式为

式(3)表明，若正则表达式Ri和Rj之间冲突信息负相关系数越大，则Ri和Rj越适合并在同一组.启发函数的值越大，蚂蚁从Ri转移到Rj的期望程度就越高.Sij相当于解决旅行商问题 (travelling salesman problem，TSP问题)中的两城之间的距离.

2.1.3 更新信息素策略

正则表达式分组后，表达式之间的信息素都按式(4)进行挥发，以免信息素无限累积，让ACO算法“忘记”蚂蚁走过的较差路径［11］.更新后的信息素表达式为

其中，ρ为信息素挥发系数.

正则表达式集合被分组完成后，组内表达式的顺序与最终状态数量无关.因此，在GRE-ACO算法中，信息素更新策略是对每个正则表达式分组中的规则集进行信息素累积，而各分组间不进行信息素累积，即对于有n条正则表达式的规则集，蚂蚁完成1次循环后，对任意分组(r1，r2，…，rm)，按照式(5)增强边(ri，rj)(其中，m ＜ n;i≠j;i，j∈1，2，…，m.)上的信息素.

例如，一个有6条正则表达式的规则集 (1，2，3，4，5，6)，采用GRE-ACO算法分组为 (1，3，5)和 (2，4，6).以第1组为例，两两正则表达式之间 (1，3)、 (3，1)、 (1，5)、 (5，1)、(3，5)和 (5，3)的信息素按式(5)进行增强.

其中，Q为信息素强度，可影响算法的收敛速度;Stotal-k为k只蚂蚁在本次循环中分组后所得的总状态数量.蚂蚁所构造出的正则表达式分组总状态数越小，各组所含的边上积累的信息素越多，且这些边在以后的迭代过程中，被蚂蚁选中的概率就越大，这有利于GRE-ACO算法收敛至全局最优.

2.2 GRE-ACO算法框架

基于蚁群优化的改进正则表达式分组算法流程为:

Step1初始化参数.令时间t=0，循环次数Nc=0，并预设最大循环次数Ncmax.将m只蚂蚁置于n条正则表达式上，令正则表达式Ri和Rj上的初始化信息量τij(0)为常数，初始时刻令Δτij(0)=0.

Step3蚂蚁的禁忌表索引号k=1.

Step4蚂蚁数目k'=k+1，k为上一轮禁忌表索引号，k'为当前禁忌表索引号.

Step5蚂蚁个体根据式(2)计算的概率选择下一条正则表达式进行合并，并判断将要合并后的当前组是否满足式(1).若是，则把所选择的正则表达式归入已分组，记录信息并修改禁忌表，蚂蚁继续前进;否则，把选择的正则表达式归入未分组，并跳到Step7.

Step6判断所有的蚂蚁是否已到达终点，即是否已遍历所有正则表达式.若是，则选择所有蚂蚁中分组后DFA的总状态数目最小的情况作为最优解，并按照式(5)更新信息素;否则，跳至Step4.

Step7判断该蚂蚁是否已访问所有的正则表达式.若是，跳到Step8;否则，跳到Step5.

Step8判断该蚂蚁是否已达终点，即分组是否已结束.若是，跳到Step6;否则，跳到Step4，对剩下的未分组中的所有正则表达式进行下一轮新一组的归并.

Step9若Nc'≥Ncmax，则循环结束并输出正则表达式分组结果;否则，清空禁忌表并跳转到Step2.

GRE-ACO算法的基本流程图如图3.

3 实验结果与分析

为检验GRE-ACO算法求解正则表达式分组问题的有效性，本研究从Snort中抽取正则表达式测试集，通过Becchi开源正则表达式匹配引擎(Michela Becchi.Regular expression processor.http://regex.wustl.edu/)工具生成相应的DFA作为实验数据.仿真所用计算机配置为Intel Core i3 CPU M330@2.13 GHz，2 Gbit内存，操作系统为 ubuntu12.04.设置信息启发因子α =1，期望启发因子β=5，信息素挥发率ρ=0.1，蚂蚁数量为3.每个规则集每种算法进行5次实验，求出最优解和平均解.

图3GRE-ACO算法流程Fig.3 GRE-ACO algorithm

图4(a)为对正则表达式测试集ruleset04.sig中的4条规则单独生成的DFA状态数量以及两两规则合并后生成的DFA状态数列成矩阵.图4(b)为按式(3)计得的对应新启发函数矩阵图.由图可见，第1条规则跟第2、3和4条规则的启发函数信息η1j(j=2，3，4)分别为0.562 5、0.789 5 和0.761 9，说明第1 条规则与其余3条规则间的冲突信息都为正冲突影响，正冲突影响越大，越不适于合并.第1条规则跟第2条规则，η12=0.562 5，合并后的DFA状态数为32;第3条规则跟第4条规则的启发函数信息η34=1.083 3，表明它们之间存在负冲突影响.冲突信息越是负相关，正则表达式越适于合并.可见，第3条规则单独生成DFA状态数为6，第4条规则单独生成的DFA状态数为7，size(R3)+size(R4)=13，它们合并后DFA的状态数为12，少于各自单独生成的状态数，所以适合合并.

表1为对从snort规则集随机抽取的规则数进行不同实验的数据汇总，包括不同规则集不分组时总的状态数量，以及GRE-ACO算法与Becchi算法进行5次实验得出的最优解和5次解的平均解.图5为GRE-ACO算法和Becchi算法实验结果柱状图.

图4 对ruleset04.sig中4条规则进行DFA生成以及新启发函数计算Fig.4 DFA for regular expression in ruleset04.sig and new heuristic function

表1 实验数据汇总Table 1 Statistics of experiments

图5 Becchi算法跟GRE-ACO算法实验结果比较Fig.5 Comparison of experiment results of Becchi algorithm and GRE-ACO algorithm

由表1及图5可知:

1)Becchi算法通过循环地采用二分法对正则表达式集合来分组，分组结果固定，但依赖于模式集中的表达式输入顺序，不一定能精确反映模式集中正则表达式之间的最优分组信息;

2)GRE-ACO算法是基于蚁群优化的分组算法，该算法充分利用信息素的正反馈特征，每次均能收敛到一个比较稳定的值.在不同的模式集测试当中，采用GRE-ACO算法所得DFA状态数量都能比采用Becchi算法所得状态数量更优，且规则集数目的越多，效果越明显.

图6为GRE-ACO算法对23条规则进行5 000次迭代实验后所得的总状态数收敛曲线图.由图6可见，GRE-ACO分组算法在实验ruleset23.sig规模集迭代5 000次实验中，在2 000次迭代左右能寻到较优解，使总状态数达到632，说明该算法具有较强的全局搜索能力，接近最优解.

图6 总状态数曲线收敛图Fig.6 Convergence figure of total number of states

结 语

在Becchi算法的基础上，提出基于蚁群优化的改进正则表达式分组的新算法，并根据正则表达式间冲突信息的特点，重新定义启发式函数和信息素更新策略.实验结果表明，该算法能客观反映模式集中正则表达式间的优化合并信息，有效减少状态数量，降低正则表达式匹配的复杂度.

/References:

［1］Aho A V，Corasick M J.Efficient string matching:an aid to bibliographic search ［J］.Communications of the ACM，1975，18(6):333-340.

［2］Wu S，Manber U.A fast algorithm for multi-pattern searching［R］.TR-94-17.Tucson(USA):University of Arizona，1994.

［3］Sommer R，Paxson V.Enhancing byte-level network intrusion detection signatures with context signatures with context［C］//Proceedings of the 10th ACM Conference on Computer and Communications Security.New York(USA):ACM，2003:262-271.

［4］Yu F，Chen Z F，Diao Y，et al.Fast and memory-efficient regular expression matching for deep packet inspection［C］//Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems.New York(USA):ACM，2006:93-102.

［5］Becchi M，Crowley P.A hybrid finite automaton for practical deep packet inspection［C］//Proceedings of the ACM CoNEXT Conference.New York(USA):ACM，2007，1:1-12.

［6］Becchi M，Cadambi S.Memory-efficient regular expression search using state merging［C］//The 26th IEEE International Conference on Computer Communications.Anchorage(USA):IEEE Press，2007:1064-1072.

［7］Becchi M，Franklin M，Crowley P.A workload for evaluating deep packet inspection architectures［C］//IEEE International Symposium on Workload Characterization.Seattle(USA):IEEE Press，2008:79-89.

［8］Xiao Wude.An efficient regular expression grouping algorithm ［J］.Network and Computer Security，2010(4):57-59.(in Chinese)

肖武德.一种正则表达式的高效分组算法［J］.计算机安全，2010(4):57-59.

［9］Wei Qiang，Li Yunzhao，Chu Yanjie.Regular expression grouping algorithm based on graph partitioning ［J］.Computer Engineering，2012，38(18):137-139.(in Chinese)

魏 强，李云照，褚衍杰.基于图划分的正则表达式分组算法 ［J］.计算机工程，2012，38(18):137-139.

［10］ Liu Tingwen，Sun Yong，Bu Dongbo，et al.1/(1-1/k):optimal algorithm for regular expression grouping［J］.Journal of Software，2012，23(9):2261-2272.(in Chinese)

柳厅文，孙 永，卜东波，等.正则表达式分组的1/(1-1/k):近似算法 ［J］.软件学报，2012，23(9):2261-2272.

［11］Dorigo M，Maniezzo V，Colorni A.Ant system:optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，1996，26(1):29-41.

［12］Dorigo M，Stützle T.Ant colony optimization:overview and recent advances［M］//Michel Gendreau，Jean-Yves Potvin.Handbook of Metaheuristics:International Series in Operations Research＆ Management Science.Berlin:Springer，2010:227-263.

［13］Mandala S R，Kumara S R，Rao C R，et al.Clustering social networks using ant colony optimization ［J］.Operational Research，2013，13(1):47-65.

［14］ Putha R，Quadrifoglio L，Zechman E.Comparing ant colony optimization and genetic algorithm approaches for solving traffic signal coordination under oversaturation conditions［J］.Computer-Aided Civil and Infrastructure Engineering，2012，27(1):14-28.

［15］Liao T，Stützle T，Montes De Oca M A，et al.A unified ant colony optimization algorithm for continuous optimization ［J］.European Journal of Operational Research，2014，234(3):597-609.

［16］Lin Y，Zhang J，Chung H，et al.An ant colony optimization approach for maximizing the lifetime of heterogeneous wireless sensor networks［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part C:Applications and Reviews，2012，42(3):408-420.

［17］ Wang Jinfeng，Yin Guofu，Lei Qianzhao，et al.Integrated process planning and scheduling based on an ant colony algorithm ［J］.Journal of Southeast University Natural Science Edition，2012，42(S1):173-177.(in Chinese)

王进峰，阴国富，雷前召，等.蚁群算法在工艺规划与车间调度集成优化中的应用［J］.东南大学学报自然科学版，2012，42(S1):173-177.

［18］Xia Yamei，Cheng Bo，Chen Junliang，et al.Optimizing services composition based on improved ant colony algorithm ［J］.Chinese Journal of Computer，2012，35(2):270-281.(in Chinese)

夏亚梅，程 渤，陈俊亮，等.基于改进蚁群算法的服务组合优化 ［J］.计算机学报，2012，35(2):270-281.

［19］Li Yinghao，Guo Ruipeng.Unit commitment solved by multi colony chaotic ant optimization algorithm ［J］.Power System Protection and Control，2012，40(9):13-17.(in Chinese)

李颖浩，郭瑞鹏.求解机组组合问题的多种群混沌蚁群算法［J］.电力系统保护与控制，2012，40(9):13-17.

2014-01-27;

2014-03-27

Regular expression grouping algorithm based on ant colony optimization

Cai Liangwei1†，Liu Siqi1，Li Xia1，and Li Jun2

1)College of Information Engineering，Shenzhen University，Shenzhen 518060，P.R.China
2)Research Institute of Information Technology，Tsinghua University，Beijing 100084，P.R.China

Following the idea of the Becchi algorithm，an improved regular expressions grouping algorithm based on ant colony optimization(GRE-ACO)was introduced.Taking account of the characteristics of regular expressions grouping，GRE-ACO defined the relationship between positive and negative effects of conflict information，a new heuristic function and pheromone update strategy.Comparison with the Becchi algorithm shows that GRE-ACO can reflect the optimizing merge information of the regular expressions more reasonably，reduce the amount of states effectively，and attain the optimal solution of the total number of state.As a result，the GRE-ACO can reduce the complexity of matching algorithm.

artificial intelligence;ant colony optimization;deep packet detection;regular expression(RE);grouping algorithm;conflict information;pheromone;network security

TP 391;TP 393

A

10.3724/SP.J.1249.2014.03279

Foundation:National Natural Science Foundation of China(61171124)

†

Professor Cai Liangwei.E-mail:cailw@szu.edu.cn

:Cai Liangwei，Liu Siqi，Li Xia，et al.Regular expression grouping algorithm based on ant colony optimization ［J］.Journal of Shenzhen University Science and Engineering，2014，31(3):279-285.(in Chinese)

国家自然科学基金资助项目 (61171124)

蔡良伟 (1964—)，男 (汉族)，广东省阳江市人，深圳大学教授.E-mail:cailw@szu.edu.cn

引 文:蔡良伟，刘思麒，李 霞，等.基于蚁群优化的正则表达式分组算法 ［J］.深圳大学学报理工版，2014，31(3):279-285.

【中文责编:英 子;英文责编:雨 辰】