基于遺傳算法的正則表達(dá)式規(guī)則分組優(yōu)化

蔡良偉，程 璐，李 軍，李 霞

1) 深圳大學(xué)信息工程學(xué)院，深圳 518060；2)清華大學(xué)信息技術(shù)研究院，北京 100084

【電子與信息科學(xué) / Electronics and Information Science】

基于遺傳算法的正則表達(dá)式規(guī)則分組優(yōu)化

蔡良偉1，程 璐1，李 軍2，李 霞1

1) 深圳大學(xué)信息工程學(xué)院，深圳 518060；2)清華大學(xué)信息技術(shù)研究院，北京 100084

為解決正則表達(dá)式匹配問題，提出一種基于正態(tài)自適應(yīng)遺傳優(yōu)化的改進(jìn)正則表達(dá)式分組算法．根據(jù)迭代次數(shù)的變化，利用正態(tài)函數(shù)自適應(yīng)改變交叉概率Pc和變異概率Pm， 采取最優(yōu)保存策略保證最優(yōu)個體不被數(shù)值大的Pc和Pm破壞．結(jié)合Becchi算法和局部尋優(yōu)算法進(jìn)一步優(yōu)化．仿真結(jié)果表明，該算法能在全局范圍內(nèi)搜索到更好的解，能有效減少狀態(tài)總數(shù)，降低正則表達(dá)式匹配的空間復(fù)雜度．

人工智能；正態(tài)自適應(yīng)遺傳算法；深度包檢測；正則表達(dá)式；分組算法；網(wǎng)絡(luò)安全

隨著計算機與互聯(lián)網(wǎng)的迅速發(fā)展，網(wǎng)絡(luò)安全問題日益嚴(yán)峻．深度包檢測(deep packet inspection，DPI)技術(shù)已被廣泛用于各種網(wǎng)絡(luò)安全系統(tǒng)中，如防火墻、入侵檢測系統(tǒng)和防病毒網(wǎng)關(guān)等．傳統(tǒng)的DPI技術(shù)采用精確字符串進(jìn)行模式匹配，如AC(Aho-Corasick)[1]、Wu-Manber[2]和Sbom(set backward oracle matching)算法[3]等．但是，隨著網(wǎng)絡(luò)的不斷發(fā)展，入侵特征日益復(fù)雜，傳統(tǒng)的精確字符串已經(jīng)很難滿足要求，正逐漸被靈活且表達(dá)能力更強的正則表達(dá)式(regular expression, RE)所取代．RE正迅速成為描述新一代規(guī)則的主要工具，在DPI中獲得了廣泛應(yīng)用．

正則表達(dá)式匹配通常是將其轉(zhuǎn)換為等價的非確定型有限自動機(non-deterministic finite machine， NFA)或確定型有限自動機(deterministic finite machine， DFA)進(jìn)行模式匹配．但考慮到匹配效率和準(zhǔn)確率的問題，大部分應(yīng)用都采用基于DFA的匹配技術(shù)來完成實時的深度包檢測．然而，DFA存在著狀態(tài)膨脹的問題(某些情況下，DFA狀態(tài)數(shù)目甚至呈指數(shù)增長)，導(dǎo)致消耗巨大的存儲空間，甚至無法生成．因此，如何減少DFA的存儲空間消耗，是實現(xiàn)高性能正則表達(dá)式匹配的重要問題．通過對正則表達(dá)式集合進(jìn)行分組是解決這一問題的重要方法．目前，已有不少學(xué)者對此進(jìn)行了研究并提出了解決方案．如Yu等[4]指出正則表達(dá)式集合的分組問題，并提出一種啟發(fā)式的分組算法——Fang Yu算法．在計算正則表達(dá)式兩兩之間的沖突后，不斷地將與當(dāng)前分組中沖突作用最少的未分組的正則表達(dá)式加入到當(dāng)前分組，直到該分組的DFA狀態(tài)數(shù)目超過給定的某個閾值，就將其加入到下一分組，最終，得到整個正則表達(dá)式集合的分組情況．徐乾等[5]提出了一種基于正則表達(dá)式的壓縮算法．Becchi等[6-8]提出一種對模式集進(jìn)行自動分組的策略，適用于合并后的DFA狀態(tài)數(shù)過大的情況，該策略是指循環(huán)二分模式集，直到每個分組的DFA狀態(tài)數(shù)都小于預(yù)設(shè)的閾值σ． 肖武德[9]通過計算正則表達(dá)式兩兩之間的沖突比率，將低于某個數(shù)值的表達(dá)式提取出來，對剩下的表達(dá)式分組，然后將事先提取出來的表達(dá)式合理地加進(jìn)去．張樹壯等[10]提出基于猜測-驗證的匹配方法．羅青林等[11]通過采集網(wǎng)絡(luò)數(shù)據(jù)流，對流量進(jìn)行統(tǒng)計分析，根據(jù)計算出來的概率進(jìn)行分組．文獻(xiàn)[12]提出DFA構(gòu)造中基于正則表達(dá)式相似性的分組算法．通過定義正則表達(dá)式相似性的概念和公式，避免了DFA狀態(tài)劇烈地膨脹，從而有效地生成DFA．文獻(xiàn)[13]提出一種基于劃分算法的正則表達(dá)式分組算法．該算法能夠減少DFA狀態(tài)總數(shù)并提高正則表達(dá)式匹配性能，從而適于多核處理器．魏強等[14]在Fang Yu算法的基礎(chǔ)上，提出基于圖劃分的正則表達(dá)式分組算法．柳廳文等[15]證明了當(dāng)沖突非負(fù)和沖突獨立時，正則表達(dá)式集合的最優(yōu)k分組問題是NP-Hard的，且基于局部搜索思想，提出GRELS(grouping regular expression with local searching)分組算法．蔡良偉等[16]提出基于蟻群優(yōu)化的改進(jìn)正則表達(dá)式分組算法(grouping regular expression with ant colony optimization，GRE-ACO)．該算法根據(jù)正則表達(dá)式分組特點，構(gòu)建新的信息素更新策略，有效減少了DFA狀態(tài)總數(shù)．付哲等[17]提出一種深度包檢測中基于正則表達(dá)式的智能分組算法，該算法是遺傳算法(genetic algorithm，GA)和蟻群算法相混合的新的分組算法，能有效解決狀態(tài)爆炸問題，并在內(nèi)存消耗和組數(shù)之間取得全局最優(yōu)折衷．然而，現(xiàn)有的分組方法效果并不理想，仍有待進(jìn)一步提升．如Fang Yu算法分組思想簡單，易于實現(xiàn)，但搜索范圍有限，容易陷入局部解；Becchi算法每次都是按序?qū)φ齽t表達(dá)式進(jìn)行循環(huán)二分組，無法在全局范圍內(nèi)得到最優(yōu)解，有一定的局限性；GRELS分組算法在解決思路上與Fang Yu算法類似，但充分利用了沖突信息并采取了更有效的策略，分組效果相對較好．

本研究提出基于自適應(yīng)遺傳優(yōu)化的改進(jìn)正則表達(dá)式分組算法(regular expression grouping based on normal adaptive genetic algorithm，REG-NAGA)，采用固定分組數(shù)目，利用正態(tài)函數(shù)自適應(yīng)地改變整個種群的交叉概率Pc和變異概率Pm，并且融合了Becchi算法和局部尋優(yōu)策略的思想，在全局范圍內(nèi)搜索正則表達(dá)式模式集規(guī)則分組的最優(yōu)解．

1 正則表達(dá)式分組與GRELS算法

1.1 正則表達(dá)式分組

1.1.1 狀態(tài)膨脹

狀態(tài)膨脹是指將2條或2條以上的正則表達(dá)式合并生成的DFA狀態(tài)總數(shù)，大于其各自單獨生成DFA的狀態(tài)數(shù)目之和．假設(shè)有2條表達(dá)式R1和R2， 它們各自生成的DFA狀態(tài)數(shù)目分別記作size(R1)和size(R2)， 合并后的表達(dá)式為R12， 生成的合并DFA狀態(tài)數(shù)目記作size(R12)，若滿足

size(R1)+size(R2)

(1)

即為狀態(tài)膨脹．

有些正則表達(dá)式生成合并DFA時會急劇膨脹，最壞情況下，甚至可能呈指數(shù)增長．如正則表達(dá)式r1=(.*ab .*cd)和r2=(.*ef .*gh)，它們各自的DFA狀態(tài)數(shù)均為5，如圖1[4]，將這2條正則表達(dá)式生成合并DFA時，狀態(tài)數(shù)膨脹到16，如圖2[4]．因此，研究正則表達(dá)式分組問題的目標(biāo)是盡量減少DFA的狀態(tài)數(shù)目，即各分組的DFA狀態(tài)數(shù)目總和盡可能多地小于不分組時的DFA狀態(tài)數(shù)目．

圖1 正則表達(dá)式r1和r2對應(yīng)的DFA[4]Fig.1 DFA of r1 and DFA of r2[4]

圖2 正則表達(dá)式對應(yīng)的DFA[4]Fig.

1.1.2 評價指標(biāo)

評價正則表達(dá)式集合分組效果的指標(biāo)通常包括DFA的狀態(tài)總數(shù)和分組數(shù)目．

1) DFA狀態(tài)總數(shù)主要考慮DFA的內(nèi)存空間消耗，它主要取決于DFA的狀態(tài)總數(shù)，因此，減少DFA狀態(tài)總數(shù)，就能達(dá)到減小DFA所占存儲空間的目的，為生成和使用DFA提供便利．

2) 分組數(shù)目主要考慮DFA的匹配速度．由于分組數(shù)決定了處理1個字符時的狀態(tài)轉(zhuǎn)移表的訪問次數(shù)，因此，它成為影響DFA匹配速度的關(guān)鍵因素．分組數(shù)目越少，DFA的匹配效率就越高，反之，就越低．

顯然，DFA的狀態(tài)總數(shù)和分組數(shù)目這2個指標(biāo)是互相矛盾的．通常分組數(shù)目越多，則DFA狀態(tài)總數(shù)就越少；反之，DFA狀態(tài)總數(shù)就越多．

1.2 GRELS算法

1.2.1 分組思想

GRELS算法的分組策略是：將n條正則表達(dá)式隨機分為k組，對于當(dāng)前的分組結(jié)果，根據(jù)式(2)[15]，計算每個分組中的沖突狀態(tài)數(shù)F(m,i)(1≤m≤k)， 依次判斷每個分組中是否存在1條表達(dá)式，把它從當(dāng)前分組中加入到另一分組中會減少沖突狀態(tài)數(shù)目，如果存在，就將它移動到減少沖突數(shù)目最多的分組中，然后進(jìn)行下一次判斷；如果不存在，就不移動并進(jìn)行下一次判斷．假設(shè)ri和rj分別表示第i和j條表達(dá)式，則

(2)

其中，Rm表示第m組正則表達(dá)式集合；Mij表示ri和rj合并后的沖突狀態(tài)數(shù)目，滿足式(3)[15]

Mij=Sij-Si-Sj

(3)

其中，Si、Sj和Sij分別表示ri、rj和ri與rj合并后的DFA狀態(tài)數(shù)目．

1.2.2 分組步驟

假設(shè)正則表達(dá)式集合的規(guī)模為n， 固定分組數(shù)目為k， 設(shè)置1個布爾型變量nochange，并初始化為true．

1)計算正則表達(dá)式兩兩之間的沖突狀態(tài)數(shù)目Mij(1≤i，j≤n)， 得到n階沖突矩陣M， 將n條正則表達(dá)式隨機不重復(fù)地分配到k個分組中，記為{R1，R2，…，Rm，…，Rk}， 其中，Rm(1≤m≤k)表示第m個分組的正則表達(dá)式集合．

2)在1個while無限循環(huán)中，將nochange賦值為true．

3)按序依次將每1條正則表達(dá)式ri嘗試加入到k個分組中，根據(jù)式(2)和式(3)，分別計算F(m,i)(1≤m≤k)， 求出使得數(shù)組F中元素最小的下標(biāo)t， 判斷ri是否在分組Rt中，若不在，則將ri從原分組中移動到Rt中，并令nochange=false；否則，不移動，然后進(jìn)行下一次嘗試．

4)若i>n且nochange=true，則跳出while循環(huán)； 否則， 返回步驟2)，并繼續(xù)下一次while循環(huán)．

2 基于遺傳算法的正則表達(dá)式規(guī)則分組優(yōu)化

2.1 遺傳算法

1975年，Holland[18]提出的遺傳算法(genetic algorithm，GA)是模擬自然界中生物遺傳進(jìn)化過程的一種全局優(yōu)化算法．GA通常指簡單遺傳算法(simple genetic algorithm，SGA)．SGA因其具有原理簡單、易于實現(xiàn)且應(yīng)用效果明顯等優(yōu)點被廣泛用于函數(shù)優(yōu)化、組合優(yōu)化、自動控制及人工生命等領(lǐng)域．但是，SGA并不能保證全局最優(yōu)收斂，在求解大規(guī)模復(fù)雜的實際問題時常出現(xiàn)早熟收斂現(xiàn)象，因此，避免早熟收斂現(xiàn)象是遺傳算法研究的主要課題之一．

2.2 自適應(yīng)遺傳算法

基于SGA，Srinivas等[19]提出一種根據(jù)適應(yīng)度動態(tài)改變交叉概率Pc和變異概率Pm的自適應(yīng)遺傳算法(adaptive genetic algorithm，AGA)．在AGA中，Pc和Pm隨個體適應(yīng)度在種群平均適應(yīng)度和最大適應(yīng)度之間進(jìn)行線性調(diào)整．當(dāng)適應(yīng)度越接近最大適應(yīng)度時，Pc和Pm越??；反之，Pc和Pm越大；當(dāng)適應(yīng)度值等于最大適應(yīng)度時，Pc=Pm=0．

然而，在AGA中，當(dāng)適應(yīng)度等于最大適應(yīng)度時，Pc=Pm=0，容易產(chǎn)生局部最優(yōu)解．因此，需對AGA進(jìn)一步改進(jìn)[20-26]．

為克服SGA的早熟收斂和AGA易陷入局部最優(yōu)解的缺點，本研究提出一種改進(jìn)的自適應(yīng)遺傳算法——REG-NAGA．該算法綜合考慮了快速收斂和全局收斂這2個要求，采取最優(yōu)保存策略保證最優(yōu)個體不被大的Pc和Pm破壞，根據(jù)正態(tài)函數(shù)構(gòu)造新的Pc和Pm計算公式，并對它們進(jìn)行優(yōu)化．

2.2.1 遺傳操作的改進(jìn)

適應(yīng)度函數(shù)是用來判斷群體中個體好壞程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估的．通常，適應(yīng)度函數(shù)就等于目標(biāo)函數(shù)．本研究中的目標(biāo)函數(shù)是各分組的DFA狀態(tài)數(shù)目之和．假設(shè)正則表達(dá)式集合R的k個分組為{R1，R2，…，Rk}， 適應(yīng)度函數(shù)為

(4)

其中，f為適應(yīng)度； size(Ri)為第i個分組的正則表達(dá)式集合的DFA狀態(tài)數(shù)目．

本研究的目標(biāo)是盡量減少DFA狀態(tài)總數(shù)，即使目標(biāo)函數(shù)(各分組的DFA狀態(tài)數(shù)目之和)越小越好，亦即適應(yīng)度越小越好．這里，與通常情況有所不同， 適應(yīng)度值越小， 種群中的個體就越適應(yīng)環(huán)境．

編碼采用序號編碼，即自然數(shù)編碼．每個個體用由自然數(shù)組成的位串來表示，假設(shè)有8條正則表達(dá)式， 個體編碼對應(yīng)序號1～8的全排列， 如圖3．

圖3 染色體序號編碼表示Fig.3 Representation of a chromosome number coding

遺傳操作主要包括選擇、交叉和變異．

1) 選擇．該操作符合優(yōu)勝劣汰原則，即把好的個體直接遺傳到下一代或通過交叉和變異產(chǎn)生新個體再遺傳到下一代．采用輪盤賭選擇算子，根據(jù)式(5)和式(6)，每個個體被選擇的概率與其適應(yīng)度值呈負(fù)相關(guān)．

(5)

(6)

其中，Pi為第i個個體被選擇的概率；fi為第i個個體的適應(yīng)度；fi′為中間變量；n為群體規(guī)模．顯然，個體適應(yīng)度越小，其被選擇的概率越大；反之亦然．

2) 交叉．它是遺傳算法的核心操作，即根據(jù)交叉概率將2個父代個體的部分基因進(jìn)行替換重組生成新個體的操作．通過交叉，可使遺傳算法的搜索能力得到相當(dāng)大的提高．本研究采用多點交叉，如圖4，其中，帶陰影的數(shù)字代表交叉點．

圖4 多點交叉Fig.4 Multi-point crossover

3)變異．它遺傳算法中的輔助操作，是指根據(jù)變異概率對群體中的父代個體的某些基因進(jìn)行變動而生成新個體的操作．引入變異操作的原因是：①使遺傳算法具有局部的隨機搜索能力，當(dāng)遺傳算法通過交叉已接近最優(yōu)解鄰域時，利用變異可以加速向最優(yōu)解收斂，此時，變異概率應(yīng)取較小值；②使遺傳算法能維持群體多樣性．防止出現(xiàn)早熟收斂現(xiàn)象，此時，變異概率應(yīng)取較大值．通常有互換變異和逆序變異2種方式，如圖5和圖6，其中，帶陰影的數(shù)字代表變異點．

圖5 互換變異Fig.5 Swap mutation

圖6 逆序變異Fig.6 Reverse mutation

選擇采取最優(yōu)保存策略，即每一代的最優(yōu)個體被選擇下來進(jìn)行交叉和變異，如果交叉、變異之后的結(jié)果比之前的結(jié)果好，就保留之后的結(jié)果；否則，就保留之前的結(jié)果．這里，主要研究對交叉和變異操作的改進(jìn)，即對交叉概率Pc和變異概率Pm計算公式的改進(jìn)．

改進(jìn)方案如下：

根據(jù)式(7)和式(8)，Pc和Pm隨著迭代次數(shù)進(jìn)行動態(tài)非線性自適應(yīng)調(diào)整．整體呈遞減的趨勢，即迭代次數(shù)越大，Pc和Pm越小．令閾值σ=T/3， 則

0≤t≤T(7)

0≤t≤T(8)

其中，t為迭代次數(shù)；T為最大的進(jìn)化代數(shù)；Pc、Pcmax和Pcmin分別表示交叉概率、交叉概率最大值和交叉概率最小值；Pm、Pmmax和Pmmin分別表示變異概率、變異概率最大值和變異概率最小值．

由式(7)和式(8)可得Pc和Pm隨迭代次數(shù)t的變化情況，如圖7．

圖7 交叉概率和變異概率的自適應(yīng)調(diào)整曲線Fig.7 Adaptive adjustment figure of crossover probability and mutation probability

2.3 Becchi算法

2.3.1 分組思想

Becchi算法的分組策略是：通過設(shè)置閾值σ， 然后不斷循環(huán)二分模式集，直到每個分組的DFA狀態(tài)數(shù)目都小于閾值σ． 即滿足

size(group_current)<σ

(9)

其中， size()為正則表達(dá)式規(guī)則集的DFA狀態(tài)數(shù)；group_current表示下一條正則表達(dá)式加入當(dāng)前組后，當(dāng)前組中的正則表達(dá)式集合；閾值σ滿足

σ=η{size(group_curr_before)+size(rj)}

(10)

這里，η為閾值系數(shù)；rj為插入當(dāng)前組中的下1條表達(dá)式；group_curr_before為在表達(dá)式rj插入當(dāng)前組前，當(dāng)前組中的正則表達(dá)式集合．

2.3.2 分組步驟

將正則表達(dá)式集合按順序排成一列，作為第1個未分組的集合．

1) 取未分組的正則表達(dá)式集合中的第1條，作為當(dāng)前組中的第1條．

2) 按序依次遍歷未分組集合中的每一條未被訪問過的正則表達(dá)式，嘗試加入到當(dāng)前組中，如果滿足式(9)，就加入；否則，就把該條表達(dá)式放入下一未分組正則表達(dá)式集合中．

3)判斷未分組的正則表達(dá)式集合是否為空，如果為空，就輸出分組結(jié)果，否則，就返回步驟1)，繼續(xù)進(jìn)行分組．

2.4 局部優(yōu)化

由于遺傳算法局部搜索能力不強，雖然能較快到達(dá)最優(yōu)解附近，但要取到最優(yōu)解需要花費很長的時間甚至無法取到，因此，要加入局部優(yōu)化算法，來增強局部搜索能力．優(yōu)化思想是：嘗試對已分好組的正則表達(dá)式集合進(jìn)一步優(yōu)化，依次取各個分組中的每一條表達(dá)式，嘗試加入到另一個分組，判斷DFA狀態(tài)總數(shù)是否減少，如果減少，就把該條正則表達(dá)式加入到使DFA狀態(tài)總數(shù)減少最多的分組中；否則，就取下一條正則表達(dá)式進(jìn)行判斷．

2.5 REG-NAGA算法框架

REG-NAGA算法流程圖如圖8．

圖8 REG-NAGA算法流程Fig.8 REG-NAGA algorithm

REG-NAGA算法實現(xiàn)的具體步驟為：

① 輸入．設(shè)n為正則表達(dá)式條數(shù)，最大進(jìn)化代數(shù)為T， 種群規(guī)模為N， 交叉概率的最小值為Pcmin、最大值為Pcmax，變異概率的最小值為Pmmin、最大值為Pmmax，閾值系數(shù)為η，多點交叉的交叉點數(shù)為pot，最大分組數(shù)為k.

② 初始化種群．對代數(shù)計數(shù)器進(jìn)行初始化，即設(shè)t=0． 隨機生成N個個體作為初始種群P(0)；相應(yīng)地隨機生成N個個體的分組情況作為初始分組G(0)． 計算沖突矩陣Mn×n(第i行第j列元素Mij根據(jù)式(3)得到)．

③ 個體評價．計算種群P(t)中每個個體的適應(yīng)度fi．將最小適應(yīng)度fmin所對應(yīng)的個體及分組情況保留下來．

④ 輪盤賭選擇．當(dāng)前群體中適應(yīng)度較小的個體更有機會遺傳到下一代．個體i被選擇的概率為pi，累積概率為qj， 循環(huán)N次，每次隨機生成一個[0，1]區(qū)間的隨機數(shù)，記第i個隨機數(shù)為numi， 判斷numi≤q1， 若成立，則選擇第1個個體參與下面的操作；否則，繼續(xù)判斷qj1， 若成立，則選擇第j+1個個體參與下面的操作．循環(huán)結(jié)束后，得到N個個體．判斷最優(yōu)個體是否入選，若未被選擇，則用選擇前的最優(yōu)個體取代選擇后的最差個體，并更新最優(yōu)個體序號的值．

⑤ 自適應(yīng)交叉．循環(huán)N次，每次隨機生成一個[0，1]內(nèi)的隨機數(shù)，記第i個隨機數(shù)為numi，根據(jù)交叉概率Pc的公式， 判斷numi

⑥ 自適應(yīng)變異．循環(huán)N次，每次隨機生成一個[0，1]內(nèi)的隨機數(shù)，記第i個隨機數(shù)為numi，根據(jù)變異概率Pm的公式，判斷numi

⑦ Becchi算法．對選擇、交叉和變異后得到的種群中的每個個體使用固定分組的Becchi算法．通過設(shè)置閾值σ，不斷的循環(huán)二分模式集，得到k個分組情況．另外，設(shè)置禁忌數(shù)組tabu[n]，記錄每次添加到當(dāng)前分組的正則表達(dá)式序號，判斷tabu.size()

⑧ 局部優(yōu)化．對已分好組的正則表達(dá)式集合，進(jìn)行進(jìn)一步優(yōu)化．針對Becchi優(yōu)化后得到的種群中的每個個體的k個分組進(jìn)行局部優(yōu)化，即依次將每個分組中的每條正則表達(dá)式嘗試加入到另一個分組中，判斷DFA狀態(tài)總數(shù)是否減少，若減少，則將該條正則表達(dá)式加入到使DFA狀態(tài)總數(shù)減少最多的分組中；否則，進(jìn)行下一次嘗試．然后判斷最優(yōu)個體是否進(jìn)一步優(yōu)化，若已優(yōu)化，則更新最優(yōu)個體為相應(yīng)的值；否則，保持原值不變．由于局部優(yōu)化是以犧牲時間復(fù)雜度為代價來換取DFA狀態(tài)總數(shù)的減少，因此，如果對效率要求較高，就可以只對最優(yōu)個體進(jìn)行局部優(yōu)化．

⑨ 終止條件判斷．循環(huán)代數(shù)t′=t+1， 其中t為上一輪循環(huán)代數(shù)，t′為當(dāng)前循環(huán)代數(shù)．判斷t′

3 結(jié)果與分析

為驗證REG-NAGA的有效性，本實驗分別從snort和L7-filte兩個開源系統(tǒng)中抽取若干條正則表達(dá)式作為測試集．以Becchi開源正則表達(dá)式匹配引擎(Becchi Michela．Regular expression processor．http: //regex.wustl.edu/)為工具生成DFA．實驗環(huán)境為Intel Pentium(R)Dual-Core cpu E5800 @3.20 GHz，2 GB內(nèi)存，操作系統(tǒng)為ubuntu10.04．設(shè)置交叉概率的最小值Pcmin=0.65， 最大值Pcmax=0.90； 設(shè)置變異概率的最小值pmmin=0.1，最大值pmmax=0.3；設(shè)置閾值系數(shù)η=1.0．對每個規(guī)則集的各種算法都進(jìn)行5次實驗，得到最優(yōu)解和平均解．

表1為分別從snort和L7-filter測試集中抽取若干條規(guī)則的不同實驗的數(shù)據(jù)匯總，包括不分組時的DFA狀態(tài)總數(shù)，采用Becchi算法、GRELS算法、GRE-ACO算法和REG-NAGA各自進(jìn)行5次實驗得到的最優(yōu)解和平均解．

表1 實驗結(jié)果比較Table 1 Comparison of experimental results for several algorithms

由表1可知：

1)Becchi算法分組結(jié)果固定，但分組效果并不理想；GRELS算法通過對已隨機分為k組的正則表達(dá)式集合進(jìn)行局部搜索，因此，得到的分組結(jié)果是局部最優(yōu)的，無法收斂到全局最優(yōu)解．另外，在一定程度上，它的解依賴于初始分組數(shù)k及初始分組結(jié)果；GRE-ACO算法是基于蟻群優(yōu)化的分組算法，每次均能收斂到一個比較穩(wěn)定的值．

2)REG-NAGA是一種基于遺傳算法的規(guī)則分組優(yōu)化算法，該算法通過自適應(yīng)調(diào)整交叉、變異概率，充分利用遺傳算法的全局收斂性，并融合局部尋優(yōu)的思想，使每次實驗均能收斂到一個相當(dāng)穩(wěn)定的全局較優(yōu)解．對于中小規(guī)模的測試集snort，采用REG-NAGA所得到的DFA狀態(tài)總數(shù)都比采用其他3種算法(Becchi算法、GRELS算法以及GRE-ACO算法)的更優(yōu)．當(dāng)規(guī)則集數(shù)目較小時，差別為0；隨著規(guī)則集數(shù)目的增多，差別越來越明顯；而對于大規(guī)模的測試集L7-filter，REG-NAGA所獲得的DFA狀態(tài)總數(shù)要明顯優(yōu)于其他3種算法．

3)Becchi算法的魯棒性最強．REG-NAGA的魯棒性優(yōu)于GRELS算法，在處理snort測試集時，兩者的魯棒性均很強，每次均能收斂到一個相當(dāng)穩(wěn)定的全局較優(yōu)解；但在處理大規(guī)模的L7-filter測試集時，REG-NAGA要優(yōu)于GRELS算法．此時，GRELS算法每次求得的解幾乎都不同，魯棒性較差；REG-NAGA的魯棒性也優(yōu)于GRE-ACO算法，在處理snort測試集時，當(dāng)規(guī)則集數(shù)目較小時，兩者的魯棒性均很強，但隨著規(guī)則集數(shù)目的增多，GRE-ACO的穩(wěn)定性越來越差；然而對于大規(guī)模的測試集L7-filter，GRE-ACO算法相對較穩(wěn)定，略差于REG-NAGA．

圖9為23條snort測試集的DFA狀態(tài)總數(shù)收斂曲線圖．由圖9可知，隨著迭代次數(shù)的遞增，DFA狀態(tài)總數(shù)呈遞減趨勢，當(dāng)?shù)螖?shù)為3時，DFA狀態(tài)總數(shù)為628，此后維持該值不變．即經(jīng)過3代運行基本能收斂到問題的解．由此說明，REG-NAGA能較快的收斂到全局較優(yōu)解．

圖9 DFA狀態(tài)總數(shù)收斂曲線圖Fig.9 Convergent graph of the total number of DFA states

結(jié) 語

為解決多正則表達(dá)式生成合并DFA的狀態(tài)膨脹問題，提出一種新算法——基于正態(tài)自適應(yīng)遺傳優(yōu)化的改進(jìn)正則表達(dá)式分組算法．該算法通過自適應(yīng)的改變種群的交叉和變異概率，采用最優(yōu)保存策略，并融合Becchi算法及局部優(yōu)化算法來進(jìn)一步優(yōu)化．實驗結(jié)果表明，該算法充分利用遺傳算法的全局收斂性，能有效減少狀態(tài)總數(shù)，降低正則表達(dá)式匹配的空間復(fù)雜度，在處理大規(guī)模測試集時，能快速收斂到全局最優(yōu)解，具有很強的魯棒性．

/ 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] Allauzen C，Crochemore M，Raffinot M. Factor oracle: a new structure for pattern matching[C]// SOFSEM’99: Theory and Practice of Informatics．Berlin: Springer，1999: 295-310．

[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 communi-cations systems．New York(USA)：Association for Computing Machinery，2006：93-102．

[5] Xu Qian，E Yuepeng，Ge Jingguo，et al．Efficient regular expression compression algorithm for deep packet inspection[J]．Journal of Software，2009，20(8): 2214-2226．(in Chinese) 徐 乾，鄂躍鵬，葛敬國，等．深度包檢測中一種高效的正則表達(dá)式壓縮算法[J]．軟件學(xué)報，2009，20(8): 2214-2226．

[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, Crowley P. A hybrid finite automaton for practical deep packet inspection[C]// Proceedings of the ACM CoNEXT Conference．New York(USA)：Association for Computing Machinery，2007，1：1-12．

[8] Becchi M, Franklin M, Crowley P. A workload for evalu-ating deep packet inspection architectures[C]// IEEE International Symposium on Workload Characterization. Seattle (USA): IEEE Press , 2008: 79-89．

[9] Xiao Wude．An efficient regular expression grouping algorithm[J]．Network and Computer Security，2010(4)：57-59．(in Chinese) 肖武德．一種正則表達(dá)式的高效分組算法[J]．計算機安全，2010(4)：57-59．

[10] Zhang Shuzhuang，Luo Hao，F(xiàn)ang Binxing，et al．An efficient regular expression matching algorithm for network security inspection[J]．Journal of Computers，2010，10: 1976-1986．(in Chinese) 張樹壯，羅 浩，方濱興，等．一種面向網(wǎng)絡(luò)安全檢測的高性能正則表達(dá)式匹配算法[J]． 計算機學(xué)報，2010，10: 1976-1986．

[11] Luo Qinglin．Algorithms to speeding up multiple regular expressions matching for application traffic classification[D]． Beijing：Capital Normal University，2011．(in Chinese) 羅青林．適合應(yīng)用層協(xié)議分類的多正則表達(dá)式匹配方法研究[D]．北京：首都師范大學(xué)，2011．

[12] Yao Tie，Xu Qiang，He Jin．A grouping algorithm based on regular expression similarity for DFA construction[C]// IEEE 13th International Conference on Communication Technology(ICCT)．Jinan(China)：IEEE Press，2011：671-674．

[13] He Gang， Wang Yang， Wu Xiaochun．A regular expression grouping algorithm based on partitioning method[C]// The 3rd IEEE International Conference on Network Infrastructure and Digital Content (IC-NIDC)．Beijing (China)：IEEE Press，2012：271-274．

[14] Wei Qiang，Li Yunzhao，Chu Yanjie．Regular expression grouping algorithm based on graph partitioning[J]．Computer Engineering，2012，38(18)：137-139．(in Chinese) 魏 強，李云照，褚衍杰．基于圖劃分的正則表達(dá)式分組算法[J]．計算機工程，2012，38(18)：137-139．

[15] 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) 柳廳文，孫 永，卜東波，等．正則表達(dá)式分組的1/(1-1/k)：近似算法[J]．軟件學(xué)報，2012，23(9)：2261-2272．

[16] Cai Liangwei，Liu Siqi，Li Xia．Regular expression grouping algorithm based on ant colony optimization[J]．Journal of Shenzhen University Science and Engineering，2014，31(3)：279-285．(in Chinese) 蔡良偉，劉思麒，李 霞，等．基于蟻群優(yōu)化的正則表達(dá)式分組算法 [J]．深圳大學(xué)學(xué)報理工版，2014，31(3)：279-285．

[17] Fu Zhe， Wang Kai， Cai Liangwei，et al．Intelligent grouping algorithms for regular expressions in deep inspection[C]// The 23rd International Conference on Computer Communication and Networks (ICCCN)．Shanghai (China)：IEEE Press，2014：1-8．

[18] Holland J H．Adaptation in natural and artificial systems：An introductory analysis with applications to biology，control，and artificial intelligence[M]．Ann Arbor(USA)：The University of Michigan Press，1975．

[19] Srinivas M，Patnaik L M．Adaptive probabilities of crossover and mutation in genetic algorithms[J]．IEEE Transactions on Systems，Man and Cybernetics，1994，24(4)：656-667．

[20] Xing Yingjie, Chen Zhentong, Sun Jing，et al．An improved adaptive genetic algorithm for job-shop scheduling problem[C]// The 3rd International Conference on Natural Computation．Haikou(China)：[s.n.]，2007，4：287-291．

[21] Sun Zhongyue,Guan Zhongliang, Wang Qin．An improved adaptive genetic algorithm for vehicle routing problem[C]// International Conference on Logistics Systems and Intelligent Management．Harbin(China)：Springer，2010，1：116-120．

[22] Wang Fujun,Li Junlan,Liu Shiwei,et al．An improved adaptive genetic algorithm for image segmentation and vision alignment used in microelectronic bonding[J]．IEEE/ASME Transactions on Mechatronics，2014，19(3)：916-923．

[23] Hu Baofang，Sun Xiuli， Li Ying， et al．An improved adaptive genetic algorithm in cloud computing[C]// The 13th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)．Beijing：IEEE Press，2012：294-297．

[24] Wang Wanliang，Wu Qidi，Song Yi．Modified adaptive genetic algorithms for solving job-shop scheduling problems[J]．System Engineering Theory and Practice，2004,24(2)：58-62．(in Chinese) 王萬良，吳啟迪，宋 毅．求解作業(yè)車間調(diào)度問題的改進(jìn)自適應(yīng)遺傳算法[J]．系統(tǒng)工程理論與實踐，2004,24(2)：58-62．

[25] Shen Bin，Zhou Yingjun，Wang Jiahai．Research of job-shop scheduling problem based on self-adaptive genetic algorithm[J]．Computer Application，2009，29(z2)：161-164．(in Chinese) 沈 斌，周瑩君，王家海．基于自適應(yīng)遺傳算法的job shop調(diào)度問題研究[J]．計算機應(yīng)用，2009，29(z2)：161-164．

[26] Jin Jing，Su Yong．An improved adaptive genetic algorithm[J]．Computer Engineering and Application，2005,41(18)：64-69．(in Chinese) 金 晶，蘇 勇． 一種改進(jìn)的自適應(yīng)遺傳算法[J]．計算機工程與應(yīng)用，2005,41(18)：64-69．

【中文責(zé)編：英 子；英文責(zé)編：雨 辰】

2014-12-23；Accepted：2015-03-14

Regular expression grouping optimization based on genetic algorithm

Cai Liangwei1?, Cheng Lu1, Li Jun2, and Li Xia1

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

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 largePcandPm. 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.

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

：Cai Liangwei，Cheng Lu，Li Jun，et al．Regular expression grouping optimization based on genetic algorithm[J]. Journal of Shenzhen University Science and Engineering, 2015, 32(3): 281-289.(in Chinese)

TP 391；TP 393

A

10.3724/SP.J.1249.2015.03281

國家自然科學(xué)基金資助項目 (61171124)

蔡良偉(1964—)，男(漢族)，廣東省陽江市人，深圳大學(xué)教授．E-mail：cailw@szu.edu.cn

Foundation：National Natural Science Foundation of China (61171124)

? Corresponding author：Professor Cai Liangwei．E-mail：cailw@szu.edu.cn

引 文：蔡良偉，程 璐，李 軍，等．基于遺傳算法的正則表達(dá)式規(guī)則分組優(yōu)化[J]. 深圳大學(xué)學(xué)報理工版，2015，32(3)：281-289.