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

（1.茂名學院 計算機與電子信息學院自動化系，廣東 茂名 525000；2.太原理工大學 計算機與軟件學院，山西 太原 030024；3.太原理工大學 信息工程學院，山西 太原 030024）

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

1 改進的算法

1.1 算法的原理

1.1.1 檢測器問題定義

自體集S，非自體集T和全集U是用0，1二進制代碼串表示其特征，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與抗原 x的從第i位開始存在不少于r個連續(xù)相同的對應位時，二者匹配；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 個閾值 R，r（R＞r），R 表示最高匹配閾值，表示初始匹配閾值，根據(jù)匹配閾值大小可直接判斷其檢測器狀態(tài)，檢測器存在3種狀態(tài)：自體 （self），非自體（nonself）和不確定檢測器（uncertain）。

定義 2：待 測檢 測 器（Detector），D={X1，…，Xn，f}與檢測集匹配，當匹配值 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ò)是個動態(tài)環(huán)境，隨著時間T的推移，自體檢測器也在變化，方程（4）所表示是 t時刻所存在的自體集，S（t）是由 S（t-1）演變而來的，包含一次響應保留下來的 Sretain（t-1）（方程（5））和需要進行變異的 Supdate（t-1）（方程（6）），還有 t時刻由待測檢測器檢測轉(zhuǎn)變的和新增的Snew（t）（方程 （7））， 其中待測檢測器轉(zhuǎn)變包含uncertain，通過改變r可將其歸為 S′。

1.1.3 nonself定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

該算法步驟如下：

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

Step2：當 match（d，m）≥R 時，且 m 屬于自體集 S，進行CNSA算法；

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

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

Step5：當 match（d，s）〈R 時，且 m 屬于 T，match（d，m）〈r，則 d屬于Snew；

Step6：當 match（d，s）〈R 時，且 m 屬于 S，進行 CNSA 算法。

2 仿真和實驗

2.1 仿真

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

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

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

2.2 實驗

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

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

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

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

3 結(jié) 論

本文提出一種新的否定選擇算法生成檢測器的方法，該算法通過自體耐受生成檢測器防止漏洞產(chǎn)生，能有效提高病毒的檢測率；通過遞增改變閾值減少黑洞產(chǎn)生，有效阻止誤報率產(chǎn)生；通過對檢測器集自體耐受防止檢測集產(chǎ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.