免疫入侵檢測多目標優化克隆選擇算法研究

張鳳斌，范學林，席 亮

(哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080)

1 引言

在有線和無線網絡中，免疫入侵檢測系統憑借其自適應性和穩定的檢測率得到廣泛應用，其中檢測器的迭代進化過程極為關鍵。克隆選擇算法是訓練成熟檢測器的一種有效方法，其原理是類比父代和子代的累計親和力選取優勢樣本[1]，但這會致使迭代后的成熟檢測器高度重疊，影響進化效率。其主因在于，大量受交叉變異操作的檢測器能檢測出當代種群無法檢測的抗原，卻因為沒有達到設定的累計匹配親和力閾值，在迭代中被丟棄。顯然，提高種群個體的累計親和力平均值會提升種群檢測范圍，但該策略缺乏對檢測器個體與所有抗原檢測結果的統計和記錄，使得大量篩選的優勢個體存在檢測半徑相互包含冗余的問題，不利于訓練的高效性。

隨著對入侵檢測理論的不斷研究，機器學習和統計學習相關模型在該領域得到了良好的應用，Altwaijry[2]在一般的網絡嗅探器基礎上，引入了多個異常檢測的貝葉斯分類器，用于計算TCP連接正常與攻擊的概率，該算法判斷同類型攻擊較為精確，對多種類型的攻擊則需多種分類器協作識別。Tian等人[3]通過統計操作系統中每個進程的系統調用次數和執行的概率構建了一種用于在線檢測的馬爾科夫入侵檢測模型。在大數據量檢測時，該模型具有較高的速度，然而對一些與正常行為相似度極高的行為易引發誤報。文獻[4]提出了擁有雙分界面的一種新型支持向量機算法，在訓練耗時方面只有標準支持向量機的四分之一，但需要對訓練樣本進行降噪處理。Elhag等人[5]將一類二值技術用于模糊遺傳系統，通過得分矩陣實現FRBCSs檢測器對抗原的識別，但檢測結果一定程度上依賴規則集的設定。

上述檢測方法經實驗證實都具有較好的檢測率，然而監測模型對抗原的判別嚴重依賴原始訓練集的訓練結果，面對檢測數據中自體與非自體標準的不斷更迭，和已出現誤報的攻擊行為，系統的自適應能力很差，造成系統檢測率的魯棒性較低，自我更新與糾錯能力較弱。

免疫入侵檢測模型屬集合范疇，集合中個體具有較高的獨立性，可及時根據網絡中的自體與非自體規則對模型中的檢測器和自體集進行更新。當前網絡中的非自體被檢測器判定是自體時，刪除該檢測器以及系統中與該非自體在空間上高重疊的自體樣本；如識別當前網絡中的自體為非自體時，移除該檢測器，并把該自體納入自體集中。定時在自體集中耐受生成新的成熟檢測器，置換超過生命周期的成熟檢測器和耐受失敗的記憶檢測器，使得系統具有良好的動態自適應性。然而進化過程中的檢測器高重疊現象卻因累計親和力函數值策略不能得到很好的解決。本文將檢測器的克隆進化過程抽象為求解多目標優化問題，優化了檢測器種群迭代效率，提升了系統的檢測率，當規則集發生變化時具有良好的動態自適應性。

2 相關工作

基于遺傳理論的迭代算法具有良好的全局性和收斂性,Barani等人[6]通過融合小生境技術的蜂群算法訓練經自體耐受的成熟檢測器，使用蒙特卡羅積分法預測非自體被檢測器覆蓋的總量，根據該值確定檢測器迭代次數。該免疫入侵檢測模型很好地平衡了檢測率和誤報率之間的關系，但缺乏魯棒性。多目標優化遺傳算法大量應用于高維多目標函數極值最優解的搜索[7,8]。文獻[9]提出將非線性數據線性化，并對數據進行特征選擇，以構建多目標優化模型，實現對數據的線性分析，高速判斷網絡行為。Yu等人[10]提出了結合多目標優化理論的遺傳算法，實現了對抗原的特征提取，在保持一定檢測率的前提下，具有較高的檢測效率。

本文根據抗原與抗體一對多的映射關系，提出了用于迭代訓練檢測器的多目標優化克隆選擇算法MCSA (Multi-objective optimization-Clonal Selection Algorithm)。將種群的克隆進化過程轉化為特殊的多目標優化模型。MCSA算法中，經克隆、交叉、變異、耐受后的種群中的每個成員將和所有抗原進行匹配，并以向量的方式記錄檢測器和所有抗原的檢測結果。通過計算向量間的支配關系來得到非支配向量，非支配向量對應的成熟檢測器將進入子代的記憶檢測器集合。同時，受支配檢測器經變異、耐受后，部分進入子代。最后，在子代中加入耐受成功的新的成熟檢測器，以固定一定的種群規模。實驗表明，迭代次數相同的情況下，相比傳統克隆選擇算法，MCSA使得種群擁有更大的檢測范圍和更低的誤報率，加快了檢測器的進化效率，提高了系統的檢測率。

2.1 多目標優化理論基本概念

在實數集R中,n維決策向量X=(x1,x2,…,xn)T?Rn，m維目標向量Y={y1,y2,…,ym}?Rn。多目標函數如下：

Max(Y)=G(X)=(f1(X),f2(X),…fm(X))T,

(1)

G(X)為從目標到決策向量的轉換函數。

定義1可行解：?X∧∈X，且滿足上述約束條件，則X∧為可行解。

定義2可行解集合：所有可行解的集合記做可行解集，用XP表示。

定義3pareto支配：{?x,y∈Xp|fk(x)≥fk(y),k=1,2,…,m}∧{?l∈{1,2,…,m}|fl(x)>fl(y)}，則x對于多個目標而言支配y，記做xy。

定義4pareto最優解:{?X,X*∈XP|?XX*}，則X*為pareto最優解，也被稱作非支配解。

定義5pareto最優解集:S*={X*|?X,X*∈XP;?XX*}。

2.2 構建檢測器抗原多目標優化模型

檢測器和抗原通過實值編碼,由l個特征表示。其中檢測器X=〈x1,x2,x3,…,xl〉,抗原Y=〈y1,y2,y3,…,yl〉。把特征轉化至[0,1]空間，則任意特征f∈[a,b]，f=(f-a)/(b-a)。耐受過程，候選檢測器與自體抗原的歐氏距離大于匹配閾值Dd時，成功耐受，否則刪除該檢測器；檢測階段，如公式(1)所示，fk(X,Y)=1，則X判斷Y為攻擊行為。圖1為m個非自體抗原與n個檢測器的檢測結果。將檢測器X1、X2和所有非自體抗原的檢測結果分別映射成向量α、β，當X1、α、X2、β滿足定義3的條件時，即X1X2。那么，所有滿足定義4條件的檢測器，就形成了非支配的成熟檢測器集合，該集合的檢測范圍可覆蓋這n個檢測器的檢測范圍。

Figure 1 Relationship of detector antigen matching

圖1 檢測器抗原匹配關系

2.3 MCSA中的交叉變異策略

相同特征之間的互換交叉以及單點特征的高頻變異，使得種群在進化過程中的多樣性不斷提高。然而，在多目標問題中引用傳統變異的方式，會引發解空間的最優解過于稠密，不利于種群多樣性。為解決這一問題，文獻[11]對變異算子加入了特殊的越界處理方法，用于最優解的迭代，相比在多目標問題中得到廣泛應用的多項式變異[12]收斂性更優。因此，本文利用柯西變異結合越界處理策略對檢測器進行變異。Ti為檢測器Xi中的某一特征，公式(2)為柯西分布，公式(3)為參數σ的柯西變異過程。φ(0,σ)為以0為對稱軸，參數為σ的柯西分布的隨機數。公式(4)為越界處理過程，其中χ為離散型隨機變量：

fc(x,σ)=σ/[π(σ2+x2)],-∞

(2)

di≤Ti≤hi,σ=1

(3)

(4)

3 算法與分析

3.1 MCSA迭代訓練算法

輸入：檢測器種群規模N,父代種群Pt,子代種群Qt,訓練數據集Strain(Snoself,Sself)，迭代次數t，迭代最大次數tmax。成熟檢測器集Dma，候選檢測器Dim，記憶檢測器集Dmc，變異概率Pv，交叉概率Pc，檢測器和所有非自體匹配后的記錄向量Vectorset，受支配檢測器集，數組p[],q[]。

輸出:訓練t代的檢測種群Pt。

begin

Pt=?，Qt=?，t=1,Ddominated=?;//初始化數據

produceDimtoleranceSself→Dma(|Dma|==N);/*耐受生成成熟檢測器集合直至規模達到N*/

While(t≤tmax)

Pt=Dma;

if(|Pt|

do

Produce newDim;

newDimtoleranceSself→newDma;/*耐受生成成熟檢測器*/

Pt=Pt+newDma;

While(|Pt|<=N) /*加入新耐受成功的成熟檢測器直至達到種群規模*/

p[]=?,q[]=?;

p[]=Pt;//將Pt放入數組p[]中

q[]=Pt;//將Pt放入數組q[]中

for (i=1;i≤N;i++)

p[i].(Vectorset)=p[i] matchSnoself;/*存儲匹配結果到對應檢測器的Vectorset*/

for (i=1;i≤N;i++)

if(p[i]==?)

continue;

for(j=1;j≤N;j++)

if(j==i||q[j]=?)

continue;

if(p[i].(Vectorset)q[j].(Vectorset))/*判別檢測器之間的支配關系*/

Ddominated=Ddominated∪q[j];

q[j]=?;//將q[]中受支配檢測器置空

p[j]=?;//將p[]中受支配檢測器置空

else if(!(p[i].(Vectorset)q[j].(Vectorset)))

continue;

if(t≠tmax)

Dmc=Pt-Ddominated;

Ddominated=clone(Ddominated);

newDdominated=variaion and cross (Ddominated);

[(newDdominated] toleranceSself→Dma;/*將交叉變異后的受支配檢測器重新耐受*/

Dma=Dmc+Dma/*新耐受成功的檢測器和記憶檢測器一起作為下一代的成熟檢測器*/

remove(Dma);//刪除重復的檢測器

t=t+1;

end;

3.2 算法分析

由MCSA算法的迭代流程可知，抗體的交叉變異操作，會使得抗體在受支配和非支配之間相互轉化，為證明迭代進化具有收斂性，抽象克隆進化過程為馬爾科夫狀態模型，得出迭代穩定的種群存在非支配抗體的概率。以A(k)={A1(k),A2(k),…,An(k)}表示總量為n的第k代抗體集合A。φ(A)表示A中非支配抗體的總量，l為抗體的特征總量，δ()算子用來計算支配和非支配抗體在相同特征上取值不同的特征數量，D表示A(k)中的非支配抗體集。

證明A(k)不存在最優非支配抗體的概率:

根據貝葉斯公式有如下關系：

由克隆選擇的性質知P{φ(A(k+1))=0|φ(A(k))≠0}=0。

所以P{φ(A(k+1))=0|φ(A(k))=0}≤1-ε<1。

經上述分析，MCSA算法迭代至收斂時，種群中存在非支配抗體的概率為1。

□

4 實驗分析

4.1 數據處理及參數設置

Figure 2 Influence of matching threshold on the algorithm圖2 匹配閾值對算法的影響

4.2 算法迭代效率分析

通過對比500個成熟檢測器的迭代耗時、檢測率、誤報率這三個指標，考量了CSA和MCSA兩種算法的特性，結果如表1所示。

鑒于較低的匹配閾值會使耐受生成的成熟檢測器和自體在高維空間過重疊，較高的匹配閾值會使得迭代效果不明顯，因此設定實驗的匹配閾值為0.5。檢測器種群經CSA算法克隆進化至150～190代時，DR穩定在30.1%左右，FR保持在0.60%左右，而經MCSA算法克隆進化至90～190代時，檢測率保持在32.78%左右，誤報率維持在0.50%左右。在一定的檢測器基數和匹配閾值的前提下，由于MCSA算法存在計算非支配向量這一過程，使得其每20次的迭代耗時相比CSA較高，但卻削減了迭代至穩定的總時間，提升了進化效率。

4.3 檢測器匹配閾值分析

圖2為不同閾值下，500個成熟檢測器的檢測率及誤報率的變化過程。Dd以 0.5為起點，0.1為步長。根據表1的實驗結果，分別設定MCSA和CSA的迭代次數為90和150。通過表1和圖2可以發現，偏低的匹配閾值導致了檢測器種群較低的檢測范圍，限制了克隆選擇提高種群檢測器率的作用，但也使得種群誤報率較低。另一方面，數據采集的不確定性造成了訓練集和測試集中的自體差異性較高，當匹配閾值設定較大時，由訓練集自體耐受生成的檢測種群易引發較高的誤報率。所以，匹配閾值的確定對平衡系統檢測率和誤報率的關系極為重要。為計算合適的匹配閾值，轉化不同閾值下的檢測結果為約登指數，約登指數表示為檢測率與誤報率的差，約登指數與分類效果成正比。根據圖2可知，經MCSA訓練的檢測器種群，系統約登指數的最大值為97.35%，DR為98.85%，FR為1.50%，Dd=2.5；經CSA訓練的檢測器種群其最大約登指數為93.71%,DR為97.21%，FR為3.50%，Dd=2.8。自體集的自適應更新策略和檢測器的克隆進化過程以及較低的匹配閾值，使得檢測系統的FR在Dd< 2.0以前，未因匹配閾值的遞增發生較大變化，穩定一個較低的值。系統的FR在Dd≥2.0以后均有較為明顯的變化，相比之下，AMINM的誤報率略低。同等的匹配閾值條件，AMINM相比AINM始終具有較高的DR。當Dd為1.8時，兩系統的FR相差0.06%，DR卻相差0.146；在Dd為3時，DR僅差0.2%，FR卻相差4.6%。其原因在于，CSA算法中,成熟檢測器匹配抗原的累計親和力值可以反映該抗體識別攻擊的數量，但不能完全反映該個體相對所有抗原的檢測能力。同理，根據激活閾值β篩選的記憶檢測器種群也存在這一問題，導致該種群在高維空間依舊高重疊，不能有效保存迭代過程的優化成果，影響克隆選擇的效率，導致AINM相對于AMINM在DR方面提升較為緩慢。檢測過程，在一定檢測器數量和固定的匹配閾值的環境下，相比CSA算法，MCSA算法使得記憶檢測器得到了精簡且檢測面范圍更大，由系統中已識別出的自體耐受的成熟檢測器將更多，這對穩定誤報率在一個較低的水平意義重大。

Figure 3 Effect of detector number on algorithm圖3 抗體規模對算法的影響

4.4 檢測器數量分析

為驗證檢測器數量對系統檢測率的影響，分別選取AINM和AMINM的最佳匹配閾值和迭代次數進行了對比實驗，結果如圖3所示。系統的DR伴隨檢測器數量的增長逐步提高，并最終達到一個穩定的水平,DF并沒有因為系統檢測器基數的變化受到太大的影響，這也說明了匹配閾值對于控制誤報率的重要作用。而在一定匹配閾值的情況下，過度增加系統檢測器的基數，并不能對檢測率和誤報率帶來絕對意義上的優化效果，反而還會降低克隆進化的效率。所以，適當的檢測器數量無論對系統的檢測效率還是迭代效率甚至是檢測精度都具有重要意義。

5 結束語

傳統克隆選擇算法通過累計親和力函數值選取優勢個體，這一策略導致了檢測器的高重疊。為解決這一問題，本文將克隆選擇算法抽象為檢測器與抗原的多目標優化問題，提出了MCSA算法。MCSA以向量的形式記錄檢測結果，根據該向量矩陣映射出Pareto非支配向量，以此得到當代種群中的非支配檢測器，最終實現篩選優勢個體。通過實驗，實現了在不同閾值、不同種群數量的環境下，AMINM和AINM檢測性能的對比。雖然在檢測率和誤報率這一指標上，MCSA的訓練效果要優于CSA算法，但是MCSA每代的訓練耗時依舊高于CSA。減小非支配檢測器求解的時間復雜度，加大實驗數據的規模，是未來需要進一步改善的工作。

[1] Yin Chun-yong,Ma Lu-yu,Feng Lu.Towards accurate intrusion detection based on improved clonal selection algorithm[J].Multimedia Tools & Applications,2015:1-14.

[2] Altwaijry H.Bayesian based intrusion detection system[J].Journal of King Saud University-Science,2012,24(1):1-6.

[3] Tian P R, Duan M, Sun C, et al.Intrusion detection based on system calls and homogeneous Markov chains[J].Journal of Systems Engineering and Electronics,2008,19(3):598-605.

[4] He Jun,Zheng Shi-hui.Intrusion detection model with twin support vector machines[J].Journal of Shanghai Jiaotong University (Science),2014,19(4): 448-454.

[5] Elhag S,Fernández A,Bawakid A,et al.On the combination of genetic fuzzy systems and pairwise learning for improving detection rates on intrusion detection systems[J].Expert Systems with Applications,2015,42(1):193-202.

[6] Barani F,Abadi M.BeeID: Intrusion detection in aodv-based manets using artificial bee colony and negative selection algorithms[J].The ISC International Journal of Information Security,2012,4(1):25-39.

[7] Liu Min, Zeng Wen-hua.Memory enhanced dynamic multi-objective evolutionary algorithm based on decomposition[J].Journal of Software,2013,24(7):1571-1588.(in Chinese)

[8] Wang Bo,Nie Xiao-wei.Multi-criteria mathematical programming based on network instrusion detection[J].Computer Research and Development,2015,52 (10): 2239-2246.(in Chinese)

[9] Badran K,Rockett P.Multi-class pattern classification using single,multi-dimensional feature-space feature extraction evolved by multi-objective genetic programming and its application to network intrusion detection[J].Genetic Programming and Evolvable Machines,2012,13(1): 33-63.

[10] Yu Yan, Huang Hao. An ensemble approach to intrusion detection based on improved multi-objective genetic algorithm [J].Journal of Software,2007,18(6):1369-1378.

[11] Wen Shi-hua,Zheng Jin-hua,Li Mi-qing.Comparison and research of mutation operator in multi-objective evolutionary algorithm [J].Computer Engineering and Applications,2009,45 (2): 74-78.(in Chinese)

[12] Deb K,Goyal M.A combined genetic adaptive search (GeneAS) for engineering design[J].Computer Science and Informatics,1996,26(4): 30-45.

[13] Yu Yan, Huang Hao.Feature selection using multi-objective genetic algorithms for intrusion detection [J].Computer Science,2007,34 (3): 197-200.(in Chinese)

[14] Li Tao. An immune based model for network monitoring[J].Chinese Journal of Computers,2006,29(9): 1515-1522.(in Chinese)

附中文參考文獻：

[7] 劉敏,曾文華.記憶增強的動態多目標分解進化算法[J].軟件學報,2013,24(7):1571-1588.

[8] 汪波,聶曉偉.基于多目標數學規劃的網絡入侵檢測方法[J].計算機研究與發展,2015,52(10):2239-2246.

[11] 文詩華,鄭金華,李密青.多目標進化算法中變異算子的比較與研究[J].計算機工程與應用，2009,45(2):74-78.

[13] 俞研,黃皓.面向入侵檢測的基于多目標遺傳算法的特征選擇[J].計算機科學,2007,34(3): 197-200.

[14] 李濤.基于免疫的網絡監控模型[J].計算機學報，2006,29(9):1515-1522.