張鳳斌，范學(xué)林，席 亮

(哈爾濱理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080)

1 引言

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

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

上述檢測方法經(jīng)實驗證實都具有較好的檢測率，然而監(jiān)測模型對抗原的判別嚴(yán)重依賴原始訓(xùn)練集的訓(xùn)練結(jié)果，面對檢測數(shù)據(jù)中自體與非自體標(biāo)準(zhǔn)的不斷更迭，和已出現(xiàn)誤報的攻擊行為，系統(tǒng)的自適應(yīng)能力很差，造成系統(tǒng)檢測率的魯棒性較低，自我更新與糾錯能力較弱。

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

2 相關(guān)工作

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

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

2.1 多目標(biāo)優(yōu)化理論基本概念

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

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

(1)

G(X)為從目標(biāo)到?jīng)Q策向量的轉(zhuǎn)換函數(shù)。

定義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對于多個目標(biāo)而言支配y，記做xy。

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

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

2.2 構(gòu)建檢測器抗原多目標(biāo)優(yōu)化模型

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

Figure 1 Relationship of detector antigen matching

圖1 檢測器抗原匹配關(guān)系

2.3 MCSA中的交叉變異策略

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

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

(2)

di≤Ti≤hi,σ=1

(3)

(4)

3 算法與分析

3.1 MCSA迭代訓(xùn)練算法

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

輸出:訓(xùn)練t代的檢測種群Pt。

begin

Pt=?，Qt=?，t=1,Ddominated=?;//初始化數(shù)據(jù)

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

While(t≤tmax)

Pt=Dma;

if(|Pt|

do

Produce newDim;

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

Pt=Pt+newDma;

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

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

p[]=Pt;//將Pt放入數(shù)組p[]中

q[]=Pt;//將Pt放入數(shù)組q[]中

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

p[i].(Vectorset)=p[i] matchSnoself;/*存儲匹配結(jié)果到對應(yīng)檢測器的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))/*判別檢測器之間的支配關(guān)系*/

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);//刪除重復(fù)的檢測器

t=t+1;

end;

3.2 算法分析

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

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

根據(jù)貝葉斯公式有如下關(guān)系：

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

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

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

□

4 實驗分析

4.1 數(shù)據(jù)處理及參數(shù)設(shè)置

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

4.2 算法迭代效率分析

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

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

4.3 檢測器匹配閾值分析

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

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

4.4 檢測器數(shù)量分析

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

5 結(jié)束語

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

[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)

附中文參考文獻(xiàn)：

[7] 劉敏,曾文華.記憶增強(qiáng)的動態(tài)多目標(biāo)分解進(jìn)化算法[J].軟件學(xué)報,2013,24(7):1571-1588.

[8] 汪波,聶曉偉.基于多目標(biāo)數(shù)學(xué)規(guī)劃的網(wǎng)絡(luò)入侵檢測方法[J].計算機(jī)研究與發(fā)展,2015,52(10):2239-2246.

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

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

[14] 李濤.基于免疫的網(wǎng)絡(luò)監(jiān)控模型[J].計算機(jī)學(xué)報，2006,29(9):1515-1522.