一種新型的否定選擇算法生成檢測器的研究

張清華 ， 趙紅霞 ，2， 朱月君 ，3， 楊暉澤 ，3

（1.茂名學(xué)院 計(jì)算機(jī)與電子信息學(xué)院自動(dòng)化系，廣東 茂名 525000；2.太原理工大學(xué) 計(jì)算機(jī)與軟件學(xué)院，山西 太原 030024；3.太原理工大學(xué) 信息工程學(xué)院，山西 太原 030024）

否定選擇算法主要應(yīng)用于檢測器的生成。傳統(tǒng)的否定選擇算法存在的問題主要有：問題空間過大時(shí)算法時(shí)空復(fù)雜度成指數(shù)級遞增，可行性不高[1]；檢測效率較低，容易產(chǎn)生漏洞；冗余檢測器較多，導(dǎo)致檢測效率的下降[2]；用二進(jìn)制字符串描述抗原和檢測器不利于管理并且此種形式難以表示某些領(lǐng)域的信息；目前自適應(yīng)性對于人工免疫系統(tǒng)仍是復(fù)雜的、函待解決的問題；大部分否定選擇算法中檢測器的管理方式較為簡單[3]；尋找相應(yīng)的檢測器花費(fèi)時(shí)間較長等等。本文根據(jù)否定選擇算法所存在的問題，提出一種新型的否定選擇算法生成檢測器算法，并證實(shí)算法原理和仿真模擬來體現(xiàn)此種方法的優(yōu)越性，最后通過實(shí)驗(yàn)來確認(rèn)此算法，最后進(jìn)行總結(jié)。

1 改進(jìn)的算法

1.1 算法的原理

1.1.1 檢測器問題定義

自體集S，非自體集T和全集U是用0，1二進(jìn)制代碼串表示其特征，U=[0，1]n，S?U，T?U。自體集 S 與非自體集 T 交集為空，自體集S與非自體集T構(gòu)成全集U，如式（1）。

定義 1：待測檢測器 d與檢測器集 x匹配，匹配值 r為：d match x=xj=djfor j=i，…，i+r-1。表示當(dāng)檢測器 d與抗原 x的從第i位開始存在不少于r個(gè)連續(xù)相同的對應(yīng)位時(shí)，二者匹配；r（1〈r≤l）為靜態(tài)匹配閾值。

自體集 S，非自體集 T和全集 U是 n維空間 （ndimensions），其中 S={X1，…，Xn，f}，T={X1，…，Xn，f}，f表示檢測器狀態(tài)，如式（2）。 設(shè)有 2 個(gè)閾值 R，r（R＞r），R 表示最高匹配閾值，表示初始匹配閾值，根據(jù)匹配閾值大小可直接判斷其檢測器狀態(tài)，檢測器存在3種狀態(tài)：自體 （self），非自體（nonself）和不確定檢測器（uncertain）。

定義 2：待 測檢 測 器（Detector），D={X1，…，Xn，f}與檢測集匹配，當(dāng)匹配值 r〈match（x，d）〈R，即 uncertain 狀態(tài)，設(shè)定遞增匹配閾值 r′（r〈r′〈R）來判斷檢測器是否是新增的自體集（或非自體集），如式（3）：

1.1.2 self定義

定義自體集 S={X1，…，Xn，1}，其中 X1，…，Xn代表自體集的特征碼，f=1代表此檢測器狀態(tài)為正常。網(wǎng)絡(luò)是個(gè)動(dòng)態(tài)環(huán)境，隨著時(shí)間T的推移，自體檢測器也在變化，方程（4）所表示是 t時(shí)刻所存在的自體集，S（t）是由 S（t-1）演變而來的，包含一次響應(yīng)保留下來的 Sretain（t-1）（方程（5））和需要進(jìn)行變異的 Supdate（t-1）（方程（6）），還有 t時(shí)刻由待測檢測器檢測轉(zhuǎn)變的和新增的Snew（t）（方程 （7））， 其中待測檢測器轉(zhuǎn)變包含uncertain，通過改變r(jià)可將其歸為 S′。

1.1.3 nonself定義

定義非自體集：T={X1，…，Xn，0}，其中 X1，…，Xn代表檢測器的特征碼，f=0代表此檢測器狀態(tài)為異常。網(wǎng)絡(luò)是個(gè)動(dòng)態(tài)環(huán)境，隨著時(shí)間T的推移，非自體也在變化，方程（8）所表示是t時(shí)刻所存在的非自體類別，T（t）是由 T（t-1）演變而來的，包含一次響應(yīng)保留下來的 Tretain（t-1）（方程（9））和需要進(jìn)行變異的 Tupdate（t-1）（方程（10）），為了防止檢測器冗余，提高檢測器的有效率，對非自體集進(jìn)行耐受以排除相似或相近的檢測器Tdetection（t）（方程（11））。 t時(shí)刻由待測檢測器檢測轉(zhuǎn)變的與新增加的Tnew（t），其中待測檢測器轉(zhuǎn)變包含 uncertain，通過改變 r可將其歸為 T′（方程（12））。

1.2 切割否定選擇算法[3]

根據(jù)故障診斷檢測中所采用在自己空間變異搜索來訓(xùn)練檢測器的陰性選擇算法，采用非己空間變異搜索的故障檢測算法[4-7]，采用空間切割否定選擇算法。如圖1所示，檢測器的生成有固定檢測器，變長檢測器，和基于切割的檢測器，固定檢測器由于檢測器檢測范圍的不可變性，容易引起漏洞的產(chǎn)生，造成系統(tǒng)檢測率和檢測效率均不高。可變檢測器算法中候補(bǔ)檢測器的空間生成位置存在不確定性，相同檢測器可檢測出部分相同的異常數(shù)據(jù)，動(dòng)態(tài)調(diào)節(jié)檢測器的大小同樣會使得某些檢測器成為冗余檢測器。因?yàn)樾璨捎靡环N自適應(yīng)的成熟檢測器生成算法，在動(dòng)態(tài)調(diào)整檢測器檢測范圍的同時(shí)防止冗余的產(chǎn)生。

圖1 檢測器的生成方式Fig.1 Generation mode of detector

切割檢測器可以有效防止漏洞產(chǎn)生，同時(shí)與固定和變長的檢測器相比較，可以用較少的成熟檢測器檢測同樣區(qū)域的抗原，并且有效防止檢測器生成冗余。

本文所涉及的是對于二進(jìn)制代碼串，進(jìn)行匹配閾值為固定r，可變閾值 r，矩形切割（方程 13），此方程主要是對自體在耐受中，匹配值達(dá)到R時(shí)，進(jìn)行相同部分取反。中所引用的CNSA算法如圖2所示。

圖2 CNSA算法流程圖Fig.2 Flow chart of CNSA algorithm

檢測器生成算法步驟如下：

Step1：匹配待測檢測器 D（x）與自體集 S，觀察 match（s，d）的匹配值；

Step2： 當(dāng) match（d，s）≥R 時(shí)，將相同的特征碼取反變成新的檢測器 D′（x）；

Step3：將D′（x）與 S匹配看是否小于 r，滿足時(shí)變成非自體集 Tnew，否則r自增，返回Step2；

Step4：當(dāng) match（d，s）時(shí)〈R，看是否 match（d，s）〈r，滿足時(shí)檢測器為Tnew，否則r自增，直到不發(fā)生匹配，則為Snew。

檢測器檢測階段原理如圖3所示。

圖3 檢測器檢測階段的流程圖Fig.3 Flow chart of detector phase

該算法步驟如下：

Step1：待測檢測器d與檢測器集m相匹配，觀察匹配值；

Step2：當(dāng) match（d，m）≥R 時(shí)，且 m 屬于自體集 S，進(jìn)行CNSA算法；

Step3：當(dāng) match（d，m）≥R 時(shí)，且 m 屬于非自體集 T，刪除該檢測器（防止產(chǎn)生冗余）；

Step4：當(dāng) match（d，s）〈R 時(shí)，且 m 屬于 T，直到其匹配值不等于 r，則 d屬于 Tnew；

Step5：當(dāng) match（d，s）〈R 時(shí)，且 m 屬于 T，match（d，m）〈r，則 d屬于Snew；

Step6：當(dāng) match（d，s）〈R 時(shí)，且 m 屬于 S，進(jìn)行 CNSA 算法。

2 仿真和實(shí)驗(yàn)

2.1 仿真

在自體集有限的條件下，比較RV，RVVD和CNSA算法的檢測效率（圖4，圖5），RV算法中檢測閾值 r固定，因此檢測率上升趨勢平穩(wěn)且相對較低。又因r相對自體長度較大容易造成漏洞產(chǎn)生，導(dǎo)致檢測率低下，候選檢測器產(chǎn)生的隨機(jī)性也使得檢測率難以提高。參與耐受自體數(shù)量為10時(shí)，算法最高檢測率只能達(dá)到90.62%，如圖4；自體數(shù)量為40時(shí)候，最高檢測率只有78%，如圖5。RVVD算法動(dòng)態(tài)改變檢測器識別范圍r，使用識別范圍較小的檢測器以彌補(bǔ)漏洞的產(chǎn)生，并通過消除大量冗余提高檢測效率，圖中其檢測率上升幅度相對RV算法較大，但當(dāng)且僅當(dāng)參與檢測的成熟檢測器數(shù)增加到一定范圍內(nèi)，才一可提高其檢測率到較高水平。CNSA算法只需較少成熟檢測器即可識別較大范圍的非自體抗原，保證較高檢測率，當(dāng)參與檢測的成熟檢測器數(shù)量一定時(shí)，其檢測率明顯具有優(yōu)勢；進(jìn)一步也可以看出，本算法成功的減少了漏洞的產(chǎn)生，只需相對較少的成熟檢測器即可使得檢測率維持在90%以上，有效地保證了人工免疫系統(tǒng)的安全性。

圖4 自體集數(shù)目為10

圖5 自體集數(shù)目為40

2.2 實(shí)驗(yàn)

在計(jì)算機(jī)病毒檢測中，利用特征碼檢測器可以檢測未知病毒，提高計(jì)算機(jī)主動(dòng)防御病毒的安全性。采取KDDcup99[8]數(shù)據(jù)，從數(shù)據(jù)篩選分析數(shù)據(jù)來源3種協(xié)議不同的數(shù)據(jù)包分別是TCP，UDP和ICMP 3種類型。從大量的數(shù)據(jù)集中TCP所占的79.21%，所以為了便于對TCP連接記錄進(jìn)行分析，觀察41個(gè)屬性特征信息選用具有代表性能體現(xiàn)出狀態(tài)變化的8個(gè)數(shù) 據(jù) 是 連 續(xù) 的 特 征 ：src_bytes、dst_bytes、count、srv_count、srror_rate、srv_serror_rate、same_srv_rate、diff_srv_rate。 對樣本數(shù)據(jù)進(jìn)行預(yù)處理，得到長度為32位的二進(jìn)制字符串，匹配長度R取值15，匹配r取值9。

由于數(shù)據(jù)量龐大，選取部分?jǐn)?shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)。本文選擇抽樣每個(gè)選取8000條數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，其中正常數(shù)據(jù)5000條，異常數(shù)據(jù)3000條。抽取正常數(shù)據(jù)作為自體集，訓(xùn)練集中的入侵?jǐn)?shù)據(jù)包括DoS攻擊和R2L攻擊。正常數(shù)據(jù)3000條，入侵?jǐn)?shù)據(jù)2000條。其中入侵?jǐn)?shù)據(jù)包括已知入侵和未知入侵。

實(shí)驗(yàn)采用測試數(shù)據(jù)進(jìn)行測試，在入侵?jǐn)?shù)據(jù)大于自體集數(shù)據(jù)的情況下，自體集是隨機(jī)抽樣，為使檢測器的檢測率達(dá)到99%，隨著自體數(shù)的增加迭代次數(shù)T在減少，需要的實(shí)驗(yàn)結(jié)果如表1所示。試驗(yàn)結(jié)果表明在確保檢測率達(dá)到99%，檢測等量入侵檢測器，在隨著自體集數(shù)目遞增的情況下，需要迭代的次數(shù)在遞減，說明隨著自體集的逐步完善，檢測率會逐步提高，所用的時(shí)間會減少。自體集不同分布情況影響檢測器生成的迭代次數(shù)。

表1 自體集的個(gè)數(shù)與入侵檢測器個(gè)數(shù)之間的關(guān)系Tab.1 The relationship between number of selfset and number of non-selfset

3 結(jié) 論

本文提出一種新的否定選擇算法生成檢測器的方法，該算法通過自體耐受生成檢測器防止漏洞產(chǎn)生，能有效提高病毒的檢測率；通過遞增改變閾值減少黑洞產(chǎn)生，有效阻止誤報(bào)率產(chǎn)生；通過對檢測器集自體耐受防止檢測集產(chǎn)生冗余。此外，該算法的不足之處，隨著自體集的擴(kuò)增，生成龐大的檢測器，計(jì)算復(fù)雜度和搜索時(shí)間相應(yīng)增大，在這一方面改進(jìn)，還需進(jìn)一步研究。

[1] ZHAO Bing-je， SUN Fu-xiong， XIE Wei.The research of generation algorithm of detectors in immune-based detection model [C]// International Symposium on Knowledge Acquisition and Modeling， 2008：693-697.

[2] QIN Ren-chao， LI Tao， ZHANG Yu.An immunity based computer virus detection method with GA-RVNS[C]//Second International Symposium on Intelligent Information Technology Application，2008：864-868.

[3] ZENG Jin-quan， LI Tao， LIU Xiao-jie.A feedback negative selection algorithm to anomaly detection [C]//Third International Conference on Natural Computation（ICNC 2007），2007：575-579.

[4] ZHAO Yu-feng，F(xiàn)U Dong-mei.An improved artificial immune network optimization algorithm and its performance analysis[J].2009，19（4）：434-445.

[5] WANG Qian，F(xiàn)ENG Xiao-kai.A detector generation algorithm based on negative selection [C]//Fourth International Conference on National Computation，2008：605-611.

[6] ZHANG Qing-hua， SHAO Long-qiu， ZHANG Ya-she.Design of unit fault diagnosis system software based on artificial immune system [C]//2008 International Conference on Computer Science and Software Engineering， 2008：431-435.

[7] ZHANG Qing-hua，QIAN Yu，XU Bu-hong， et al.Application study of non-dimension-parameter to fault diagnosis technology in artificial immune system [J].Noise and Vibration Control，2008（1）：89-92.

[8] ZHANG Qing-hua，QIAN Yu，XU Bu-gong， et al.Negative selection algorithm of the method of mutation search in self space to train detector[J].Computer Application，2007（3）：627-629.