模糊推理結合Michigan型遺傳算法的網絡入侵檢測方案

馬勇（四川工程職業技術學院 電氣信息工程系，四川　德陽　618000）

模糊推理結合Michigan型遺傳算法的網絡入侵檢測方案

馬勇
（四川工程職業技術學院 電氣信息工程系，四川德陽618000）

針對計算機網絡中安全性問題，提出一種融合模糊推理和Michigan型遺傳算法的網絡入侵檢測方案。首先，通過一種啟發式過程來確定每個模糊if-then規則后件類和確定性分數。然后，利用Michigan型遺傳算法，通過交叉和變異操作來進化模糊系統的規則，產生高分類率的模糊規則。最后，通過協同進化后的模糊系統實現入侵檢測。在DARPA數據集上進行實驗，結果表明該方案能夠精確的檢測U2R、R2L、DoS和PRB類網絡攻擊，具有很高的安全性。

網絡入侵檢測；模糊推理；Michigan型遺傳算法；規則進化

當前計算機網絡盡管具有多重安全策略，譬如，訪問控制、加密以及防火墻的應用，然而，網絡安全的漏洞還是與日俱增。因此，迫切需要智能的入侵檢測系統（Intrusion Detection System，IDS）來自動地檢測新型的入侵行為［1］。

目前，主要有兩種入侵檢測方法：誤用檢測和異常檢測［2］。誤用檢測的檢測速度快、誤報警率低，但其只能檢測出數據中已知的入侵模式，無法檢測新出現的入侵行為，且需要實時的更新數據庫［3］。異常檢測系統能夠檢測出新的入侵行為，但通常具有較高的誤報警率［4］。為此，學者們提出了多種混合IDS，例如，文獻［5］提出一種基于增量式神經網絡的入侵檢測系統，解決了神經網絡離線訓練所帶來的問題，對在線檢測過程中新出現的攻擊類型進行增量式學習，實現對入侵檢測模型的動態擴展。文獻［6］提出了一種非監督異常檢測框架，其利用集群估算、K-鄰近和支持向量機（SVM）進行入侵檢測。然而，該系統所需的特征維數很高，計算效率低。

基于模糊if-then規則［7］的模糊推理系統在很多應用領域已得到成功應用。一般情況下，若模糊模型的精確性較高，其解釋性相對較差。而具備較高解釋性的模糊模型，其精確性又較低。精確性與解釋性較好折衷的模糊模型，具有簡單的結構和較少的參數，運算量低，泛化能力強。由于模糊邏輯的知識表達能力與進化計算的全局自學習能力可以互補［8］。所以，可引用進化計算來改進模糊系統。其中，遺傳算法是進化計算理論體系中最具代表性的算法，因此可形成一種有效的遺傳模糊推理系統。文中基于遺傳模糊推理系統的思想，提出一種融合模糊推理和Michigan型遺傳算法的網絡入侵檢測系統。首先，通過一種啟發式過程來確定每個模糊if-then規則后件類和確定性分數。然后，利用Michigan型遺傳算法進化模糊系統的規則，進行協同進化，最終通過獲得的最優模糊規則實現入侵檢測。實驗結果表明，文中方案能夠精確的檢測網絡攻擊。

1　基于模糊規則的模式分類

1.1模糊規則分類

本文假設模式分類問題為具有連續屬性的n-維模式空間中的c-類問題。同時還假設給定m個實向量xp=（xp1，xp2，…，xpn），p=1，2，…，m，并將其作為來自c個類的訓練模式c≤m。

由于模式空間為［0，1］n，所以每種模式的屬性值為xpi∈［0，1］，p=1，2，…，m；i=1，2，…，n。在本文中，將每個數據集的屬性值規范化到單位區間［0，1］。

文中提出的模糊分類器系統中，使用如下形式的if-then規則。

規則Rj：If x1為Aj1…，xn為Ajn，Then類Cj滿足CF=CFj。

其中，Rj為第j個if-then規則的標簽，Aj1…，Ajn為單位區間［0，1］上的前件模糊集，Cj為后件類（即給定C類中的一類），CFj為模糊if-then規則Rj的確定性分數。本文將一組典型的語言值用作圖1中的前件模糊集，并通過把每種屬性域劃分為對稱的三角模糊集，明確圖1中每個語言值的隸屬函數。值得注意的是，對于特定模式分類問題，文中在模糊分類系統中可以使用任何定制的隸屬度函數。

圖1　五個語言值的隸屬度函數（S：小，MS：中小，M：中，ML：中大，L：大）

在n維模式分類問題中，模糊if-then規則的總數為5n。當屬性的數量（即n）很大時（如n=41的入侵檢測問題），有可能在單模糊規則庫中使用所有5n個模糊if-then規則。

文中模糊分類系統搜索相對數量較小的具有高分類能力的模糊if-then規則（如100個規則）。由于每個模糊if-then規則的后件類和確定性分數可以通過簡單的啟發式過程從訓練模式中確定，所以本文模糊分類系統的任務是，為一個模糊if-then規則集生成前件模糊集的組合。然而，該任務對于高維模式分類器問題來說是很難的，因為搜尋空間涉及5n個組合（如在n=13時，多于1 000萬個）。

為此，在本文模糊分類器系統中，通過利用啟發式過程來確定每個模糊if-then后件類Ci和確定性分數CFj。步驟如下描述。

1.2Ci和CFj的確定

步驟1：通過下式運算，計算具有模糊if-then規則Rj的每個訓練模式的兼容性。

上式中，μji（xpi）為第p個模式中第i個屬性的隸屬度函數。

步驟2：對于每個類，計算具有模糊if-then規則Rj的訓練模式的兼容性分數：

上式中，βClass（Rj）為類h中具有模糊if-then規則Rj的訓練模式的兼容性分數總和。NClass為對應類為h的訓練模式的數量。

步驟3：找出具有最大βClass h（Rj）值的類h?j。

如果兩個或更多的類具有最大值，則不能確定唯一模糊if-then規則的后件類Cj。在這種情況下，令Cj為φ。如果沒有與模糊if-then規則Rj相配的訓練模式（即，對于h=1，2，…c，βClass h（Rj）=0）則還將后件類Cj指定為φ。

步驟4：如果后件類Cj為φ，則令模糊if-then規則Rj的確定性分數CFj=0。否則，用以下公式計算確定性分數CFj。

通過本文提出的啟發式過程，可以指定任意前件模糊集組合的后件類和確定性分數。

本文模糊分類器系統的任務是生成前件模糊集的組合，用以生成具有高分類能力的規則集S。然后，通過S中的單優先規則Rj來分類xp=（xp1，xp2，…，xpn），其確定如下：

也就是說，優先原則選出具有最大兼容性和確定性分數CFj。如果不存在與輸入的模式xp一致的模糊規則（即，對于?Rj∈S，μj（xp）=0），則拒絕分類。

文中，將每個模糊if-then規則編碼為字符串。利用下面的符號來表示五個語言值：1：小；2：中小；3：中；4：中大，5：大。例如，若模糊if-then規則被編碼為“1342”，即x1為小，x2為中，x3為中大，x4為中小，則cj類滿足CF=CFj。

入侵檢測是一個高維度的分類問題，在該問題中，將41維的特征向量作為輸入，將5個類作為其輸出。所以在本文中，種群中和每個規則集中的所有規則的類標簽都相同。因此，在分類問題中，對于每個類重復遺傳模糊規則生成算法。

文中目標分類器由個分類器組成。每個分類器獨立發展，將獲得的模糊規則集組合用于最終分類器系統的結構中。圖2為目標分類器的結構。

圖2　本文目標分類器結構

2　融合Michigan遺傳算法的模糊系統

Michigan型遺傳算法［9］中，每一條染色體代表單條模糊規則，因為模糊模型的規則庫是由多條模糊規則組成，所以多條模糊規則在遺傳優化過程中需要相互競爭與合作以形成性能較好的模糊模型，模糊規則之間的這種競爭與合作的關系，使得模糊模型難以從整體上確定單條規則的優劣性，因此Michigan型遺傳算法需要較好的權值分配策略以確定每一條染色體的適應度值［10］。

文中提出一種融合Michigan型遺傳算法和模糊系統的入侵檢測方案，其算法的執行步驟如下：

步驟1（初始化）：初始化生成模糊if-then規則的原始種群。

步驟2（遺傳操作）：通過遺傳操作生成新的模糊if-then規則。

步驟3（替換）：利用新生成的規則替換一部分當前種群。

步驟4（重新初始化）：通過重新初始化種群，提高if-then規則的性能。

步驟5（停止）：如果滿足停止條件（最大遺傳代數），則終止該算法，否則，回到步驟2。

該模糊分類器系統的每個步驟詳細描述如下：

1）步驟1：初始化

文中用表示種群中模糊if-then規則數。為了產生初始種群，根據訓練數據集中的隨機模式生成Npop個模糊if-then規則。對于分類問題的每一個類，分別執行遺傳模糊系統。因此，根據訓練數據集的模式，提取隨機模式。這里，訓練數據集的后件類與算法運行的類相同。接著，對于這個隨機模式，本文僅使用5個語言值來確定前件模糊集的最合適組合。

利用方程（2）測試具有隨機模式的前件模糊集的兼容性。在生成每個模糊if-then規則之后，根據模糊系統確定這個規則的后件類。只有它的后件類與其相應的隨機模式類相同時，才接受生成的模糊規則。否則，拒絕該生成的模糊規則，并重復規則生成過程［11，12］。

在生成Npop個模糊if-then規則之后，使用當前種群中模糊if-then規則集，通過分類所有給出的訓練模式來評估每個規則的適應值。利用如下方程來評估模糊if-then規則的適應值：

上式中，NCP（Rj）為被Rj正確分類的訓練模式的數量。

2）步驟2：遺傳操作生成新種群

為了生成下個種群的新模糊if-then規則，需要先從當前種群中選擇一對模糊if-then規則。本文通過下式的選擇概率來選擇當前種群中的每個模糊if-then規則。

上式中，fitnessmin（S）為種群中模糊if-then規則的最小適應值。迭代該過程，直到選擇到預設對數的模糊if-then規則。

將交叉操作應用到隨機選擇的具有預設交叉概率Pc的模糊if-then規則對上。需注意，為交叉操作所選的兩個個體應不同，另外，本文使用單點交叉［13］。在執行完交叉操作之后，確定生成個體的后件類。如果這些類與它們的父代的類相同，則接受生成的個體；否則，重復交叉操作。

預先確定變異概率Pm，在交叉操作之后，利用不同的前件模糊集替換模糊if-then規則中的每個前件模糊集。在執行完變異操作之后，確定變異個體的后件類。如果該后件類與變異操作之前的個體的類相同，則接受變異個體；否則，重復變異操作直到預設的迭代數Mrepeat。在執行完選擇、交叉和變異步驟之后，根據方程（7）評估每個生成個體的適應度值。

3）步驟3：替換

利用新生成的規則替換當前種群中預設數目的模糊if-then規則。在本文模糊分類器系統中，從當前種群中移除百分之PrepR具有最小適應度值的較差規則。并添加具有百分之（100-PrepR）新生成的模糊if-then規則（PrepR為替換百分比）。

在執行完上面的替換程序之后，根據方程（7）評估每個個體的適應度值。

4）步驟4：重新初始化

為了提高當前種群的分類率，文中利用拒絕訓練模式生成的新模糊if-then規則，并替換當前種群中的一些較弱的模糊if-then規則。替換的新規則數取決于當前種群中較弱個體的數目［14］。較弱個體的適應度閾值定義如下：

上式中，Pweak為閾值的百分比；Fmax是一個數，表示輸入個體的最大可能適應度值。通過降低Pweak，可以使更多的個體執行重初始化操作。

在執行完重新初始化步驟之后，根據方程（7）評估每個個體的適應度值。

3　實驗及分析

3.1實驗環境

文中利用國際標準入侵檢測評估數據集DARPA［15］上進行實驗。數據庫由正常和惡意通訊相關的大量網絡連接組成，每條連接用41維的特征向量表示，并將連接標記屬于五類中的哪一類。這些類中的一個子類為正常類，其余為4個為不同的入侵類。4種入侵類分別為：探測（PRB）攻擊、拒絕服務（DoS）攻擊、非法遠程闖（R2L）攻擊和非法提升權限（U2R）攻擊。這些入侵類中包含了計算機網絡中22種不同的攻擊，4個入侵類的樣本數如表1所示。

文中從這些數據集中選擇650個樣本作為訓練集，選擇6 500個樣本作為測試集，訓練和測試集樣本數量如表2所示。

在提出的基于遺傳模糊系統的IDS中，設定遺傳算法所使用的參數如下：種群大小為20；交叉概率（Pc）為0.9；變異概率（Pm）為0.1；變異迭代數（Mrepeat）為20；替代率（PrepR）為20；最大遺傳代數為20。

3.2性能分析

首先，對文中IDS系統進行入侵檢測性能分析實驗，表3為文中遺傳模糊系統分類網絡的混淆矩陣。可以看出，文中系統對于正常類、U2R、R2L、DoS和PRB類的分類準確率分別為99.2％、78％、79.4％、92.9％和88.2％，整體平均準確識別率達到了87.54％。這說明，文中IDS具有較高的正確檢測率。

表1　4種不同入侵類中的攻擊

表2　訓練和測試集樣本數量

表3　本文IDS分類檢測的混淆矩陣

然后，將文中系統與現有入侵檢測方案：文獻［5］和文獻［6］方案進行比較。表4列出了各種IDS的性能比較，可以看出，文中IDS的在正常類和PRB類的分類率明顯高于其他方案，整體準確分類率也遠遠高于其它方案，分別比文獻［5］和文獻［6］方案性能提高了10.24％和6.68％。這是因為本文使用的基于遺傳模糊推理系統的IDS比其他方法更可靠［16-17］。

表4　各種IDS的入侵檢測分類準確率比較

4　結論

文中提出一種融合模糊推理和Michigan型遺傳算法的網絡入侵檢測方案。通過一種啟發式過程來確定每個模糊if-then規則后件類和確定性分數。利用Michigan型遺傳算法協同進化模糊推理系統的規則。實驗表明，本文方法對U2R、R2L、DoS和PRB類攻擊的整體檢測率達到了87.54％，具有很高的性能。

在今后工作中，將考慮使用多目標演化模糊系統來提取一個易于理解的模糊分類器，進一步提高本文IDS性能。

［1］肖寅東，王厚軍，田書林.高速網絡入侵檢測系統中包頭解析方法［J］.儀器儀表學報，2012，33（6）:1414-1419.

［2］高苗粉，秦勇，李勇，等.網絡入侵檢測系統自體集檢測中的概率匹配高效尋優機制［J］.計算機應用，2013，33（1）:156-159.

［3］Elngar A A，El A M D A，Ghaleb F F M.A Real-Time Anomaly Network Intrusion Detection System with High Accuracy［J］.Information Sciences Letters，2013，35（3）:49-56.

［4］Subaira.A S，Anitha.P.A Survey:Network Intrusion Detection System based on Data Mining Techniques［J］.International Journal of Computer Science＆amp;Mobile Computing，2013，2（10）:174-185.

［5］趙建華，李偉華.有監督SOM神經網絡在入侵檢測中的應用［J］.計算機工程，2012，38（12）:110-111.

［6］Hsieh C F，Cheng K F，Huang Y F，et al.An Intrusion Detection System for Ad Hoc Networks with Multi-attacks Based on a Support Vector Machine and Rough Set Theory ［J］.Journal of Convergence Information Technology，2013，26 （5）:269-281.

［7］周豫蘋，方建安.神經模糊理論在入侵檢測系統中的應用研究［J］.微電子學與計算機，2010，27（9）:126-129.

［8］李晶皎，許哲萬，王愛俠，等.基于移動模糊推理的DoS攻擊檢測方法［J］.東北大學學報：自然科學版，2012，33（10）:1394-1398.

［9］Mehta S B，Chaudhury S，Bhattacharyya A，et al.Tissue classification in magnetic resonance images through the hybrid approach of Michigan and Pittsburg genetic algorithm. ［J］.Applied Soft Computing，2011，11（4）:3476-3484.

［10］Li W，Gong Z.Michigan-based variable-length encoding of genetic algorithm for k-anonymization［C］//Information Science and Engineering（ICISE），2010 2nd International Conference on.2010:1295-1298.

［11］馬永杰，云文霞.遺傳算法研究進展［J］.計算機應用研究，2012，29（4）:1201-1206.

［12］Dai F，Zheng K，Binwu，et al.Using Genetic Algorithm for Optimal Security Hardening in Risk Flow Attack Graph［J］. Ksii Transactions on Internet＆amp;Information Systems，2015，9 （4）:3476-3484.

［13］Babbar-Sebens M，Minsker B S.Interactive Genetic Algo-rithm with Mixed Initiative Interaction for multi-criteria ground water monitoring design［J］.Applied Soft Computing，2012，12（1）:182-195.

［14］魯立，劉頌.基于自適應遺傳算法的入侵檢測方法［J］.科學技術與工程，2012，12（33）:9075-9078.

［15］Wanwarang T，Ongtang M.Elitism Enhancements for Genetic Algorithm based Network Intrusion Detection System［J］. Journal of Convergence Information Technology，2013，38（5）: 137-140.

［16］葉勃宏.基于FPGA的SATAⅡ協議物理層實現［J］.電子科技，2014（6）:17-21.

［17］趙旭，江晉.一種面向網絡入侵檢測系統的多媒體鏈表結構［J］.西安工業大學學報，2015（3）:186-191.

A network intrusion detection schemer based on fuzzy inference and Michigan genetic algorithm

MA Yong
（Department of Electrics and Information Engineering，Sichuan Engineering Technical College，Deyang 618000，China）

For the issues that the security problem of computer network，a network intrusion detection schemer base on fuzzy inference and Michigan genetic algorithm is proposed.Firstly，a heuristic procedure is set to determine the consequent class and the certainty score of each fuzzy if-then rule.Then，the rules of fuzzy system are evolved by crossover and mutation operations of the Michigan genetic algorithm，to generate the fuzzy rules of high classification rate.Finally，the intrusion detection is realized by the fuzzy system after cooperative evolved.Experiments on DARPA data sets show that the proposed scheme can accurately detect U2R，R2L，DoS and PRB attacks，and has high security.

network intrusion detection；fuzzy inference；Michigan genetic algorithm；rule evolution

TN918

A

1674－6236（2016）11-0108-04

2016-01-20稿件編號：201601167

國家自然科學基金（40701146）；四川省高校重點實驗室項目（2014WZY05）

馬 勇（1959—），男，四川什邡人，副教授。研究方向：網絡安全、web挖掘等。