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

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

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

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

1 改進的算法

1.1 算法的原理

1.1.1 檢測器問題定義

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

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

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

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

1.1.2 self定義

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

1.1.3 nonself定義

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

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

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

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

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

本文所涉及的是對于二進制代碼串，進行匹配閾值為固定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自增，直到不發生匹配，則為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，刪除該檢測器（防止產生冗余）；

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

圖4 自體集數目為10

圖5 自體集數目為40

2.2 實驗

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

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

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

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

3 結 論

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

[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，FU Dong-mei.An improved artificial immune network optimization algorithm and its performance analysis[J].2009，19（4）：434-445.

[5] WANG Qian，FENG 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.