基于二次否定剪切選擇的入侵檢測方法*

劉會會，牛 玲，孔韋韋

（1.周口師范學(xué)院，河南 周口 466001；2.西安郵電大學(xué)，西安 710121）

0 引言

計算機(jī)技術(shù)的迅猛發(fā)展極大地改變了人類的生產(chǎn)、生活模式，但隨之而來的計算機(jī)安全問題也深深地困擾著廣大用戶。在此背景下，計算機(jī)信息安全已經(jīng)成為國內(nèi)外相關(guān)領(lǐng)域的研究熱點(diǎn)，并產(chǎn)生了一系列技術(shù)模型和方法[1-3]。受生物免疫系統(tǒng)模型的啟發(fā)，人工免疫系統(tǒng)模型得到了建立和發(fā)展，誕生了諸如克隆選擇[4]、危險理論[5]、否定選擇算法（Negative Selection Algorithm，NSA）[6-15]以及免疫網(wǎng)絡(luò)[16]等多種模型，并被廣泛用于計算機(jī)入侵檢測領(lǐng)域。其中，NSA由于具有優(yōu)良的自適應(yīng)保護(hù)機(jī)制，被認(rèn)為是目前解決入侵檢測問題的重要方法。

NSA通過模擬T細(xì)胞成熟過程中的耐受機(jī)制，清除不能通過自體耐受的候選檢測器，從而實(shí)現(xiàn)對非自體集合的識別以抵御計算機(jī)網(wǎng)絡(luò)中的入侵行為。因此，理想的成熟檢測器應(yīng)該滿足以下幾點(diǎn)要求：1）能夠盡可能地識別非自體集合；2）不能識別任何自體集合。

傳統(tǒng)的NSA采用字符串形式對自體和檢測器進(jìn)行編碼，雖然實(shí)現(xiàn)起來較為簡單，但系統(tǒng)的整體檢測率較低。Gonzalez[17]提出的實(shí)值否定選擇算法（Real-valued NSA，RNSA）對傳統(tǒng)NSA進(jìn)行了較大改進(jìn)，但由于檢測器半徑是固定值，因此，檢測效率提升有限。為此，Zhou等提出一種新型否定選擇算法（V-detector）[18-19]，該算法中的檢測器半徑可以根據(jù)自身與自體集間的距離自適應(yīng)地進(jìn)行調(diào)整，一定程度上提升了檢測效率。文獻(xiàn)[12]也對否定選擇算法進(jìn)行了較為全面的總結(jié)和闡述。不同于以往提出的否定選擇算法，文獻(xiàn)[13]首次提出了針對候選檢測器進(jìn)行兩次否定選擇過程，從而有效提升檢測器生成效率，并盡可能減少了成熟檢測器中的個體數(shù)量。然而，過分苛刻的耐受過程容易造成大量檢測器被刪除，從而在一定程度上將不可避免地對檢測效率構(gòu)成影響。

因此，本文將結(jié)合二次否定選擇算法和文獻(xiàn)[20]中的切割機(jī)制，提出一種基于二次否性剪切選擇的入侵檢測方法。該方法首先將新生成的檢測器與成熟檢測器集合作比對，清除能夠被成熟檢測器完全覆蓋的個體以提升每個檢測器的耐受性能；然后，將通過耐受性檢測的檢測器與訓(xùn)練自體集作比對，如果出現(xiàn)覆蓋則對檢測器進(jìn)行剪切，并將剪切后的個體置入成熟檢測器集合；最后，對成熟檢測器集合進(jìn)行優(yōu)化，使用數(shù)量盡可能少、半徑盡可能大的檢測器覆蓋盡可能大區(qū)域的非自體集合以提升整個入侵檢測系統(tǒng)的綜合性能。

1 經(jīng)典實(shí)值否定選擇算法

經(jīng)典的RNSA模型主要分為半徑固定型和半徑可變型算法兩大類。其中，前者通常以檢測器的數(shù)量作為整個算法的最終迭代終止條件，假設(shè)隨機(jī)生成一個候選檢測器H，然后計算H與每一個自體訓(xùn)練集間的最小距離dis，如果dis＞dS+dH，則H可以作為成熟檢測器集合中的元素。其中，dS和dH分別表示自體集合半徑和候選檢測器的半徑。

在半徑可變型算法中，常以非自體集合覆蓋率作為整個算法的最終迭代終止條件，假設(shè)隨機(jī)生成一個候選檢測器H，然后計算H與每一個自體訓(xùn)練集間的最小距離dis，如果dis＞dS，則H可以作為成熟檢測器集合中的元素，且其半徑值為dis-dS。圖1給出了兩種類型算法的示意圖。

圖1 半徑固定型和半徑可變型RNSA

其中，圖中深灰色區(qū)域表示自體集合，淡灰色區(qū)域表示成熟檢測器，自體集合之外的區(qū)域?yàn)榉亲泽w集合。在左圖中采用了半徑固定型檢測器對非自體集合進(jìn)行檢測，而右圖則采用了半徑可變型的檢測器對非自體集合進(jìn)行檢測。顯然，半徑可變型算法結(jié)果具有數(shù)量更少的成熟檢測器以及檢測率更高的檢測效果。然而，這兩種類型的算法均沒有考慮候選檢測器可能與成熟檢測器之間的重疊覆蓋。文獻(xiàn)[13]針對此問題提出了二次否定選擇算法，在原有RNSA基礎(chǔ)上，添加了將候選檢測器進(jìn)行成熟檢測器集合中元素耐受訓(xùn)練的過程，在一定程度上提升了檢測器生成效率，但單純一味地將與自體集合有重疊的候選檢測器完全刪除，容易造成檢測效率的下降。

2 本文提出方法

本文結(jié)合二次否定選擇算法和切割機(jī)制，提出一種基于二次否性剪切選擇的入侵檢測方法，該方法主要分為3個部分：成熟檢測器耐受訓(xùn)練過程、訓(xùn)練自體集耐受訓(xùn)練過程、成熟檢測器集合優(yōu)化過程。

2.1 成熟檢測器耐受訓(xùn)練過程

經(jīng)典RNSA模型沒有考慮候選檢測器可能與成熟檢測器之間的重疊覆蓋可能。顯然，一旦出現(xiàn)這種情況，將意味著新產(chǎn)生的候選檢測器與現(xiàn)有的某個成熟檢測器具有相似或者完全相同的覆蓋范圍和檢測能力，因此，針對候選檢測器進(jìn)行成熟檢測器集合的耐受訓(xùn)練是完全有必要的，有利于提高候選檢測器的生成效率。

耐受訓(xùn)練過程具體步驟如下：

1）隨機(jī)生成一個候選檢測器H；

2）計算候選檢測器H與成熟檢測器中每一個個體之間的歐氏距離dis；

3）如果滿足式（1），則候選檢測器H通過了耐受訓(xùn)練；否則，返回步驟（a）；

其中dnew與di分別表示候選檢測器與成熟檢測器中第i個個體，rdi為成熟檢測器di的半徑，Nd為成熟檢測器集合中的個體數(shù)量。

圖2給出了候選檢測器與成熟檢測器間可能存在的3種位置關(guān)系示意圖。

圖2 候選檢測器與成熟檢測器間可能存在的3種位置關(guān)系

顯然，當(dāng)式（1）滿足時，候選檢測器與成熟檢測器之間沒有任何重復(fù)覆蓋區(qū)域，因此，該候選檢測器是必要的，并且不能被現(xiàn)有成熟檢測器個體所取代；反之，如果式（1）得不到滿足，則二者必然存在“部分相交”或“完全包含”位置關(guān)系，候選檢測器的檢測效能也將受到部分削弱或是完全覆蓋。因此，任何一個合格的候選檢測器必須滿足式（1）。

2.2 訓(xùn)練自體集耐受訓(xùn)練過程

任何成熟檢測器個體必須滿足兩個要素，即只能識別非自體集合且不能覆蓋任何自體集合。因此，對任何候選檢測器都有必要進(jìn)行訓(xùn)練自體集的耐受訓(xùn)練過程?，F(xiàn)有的絕大多數(shù)NSA模型對任何與自體集“相交”的候選檢測器均采取“清除”策略，該策略實(shí)施簡單，但容易造成大量候選檢測器被刪除從而影響檢測效率。事實(shí)上，將這些檢測器進(jìn)行徹底“清除”是完全沒有必要的，這些“瑕疵”檢測器可以為我們提供自體集合與非自體集合間尤其是關(guān)于二者邊界更多的位置信息，

本文借鑒文獻(xiàn)[20]提出的剪切機(jī)制，對一些在訓(xùn)練自體集耐受訓(xùn)練過程中不合格的檢測器進(jìn)行切割，使之能夠順利通過耐受檢驗(yàn)。

假設(shè)檢測器類型為超立方體結(jié)構(gòu)，訓(xùn)練自體集耐受訓(xùn)練過程具體步驟如下：

1）將通過檢測器耐受過程的候選檢測器H與訓(xùn)練自體集中的某個元素Straining作比對；

2）如果H與Straining有重疊區(qū)域，按照尺寸從大到小的順序?qū)進(jìn)行切割，生成4個新的檢測器H1-H4，并將其列入候選檢測器集合；否則，保持候選檢測器H不變；

3）如果候選檢測器與自體集合中所有元素均完成了耐受訓(xùn)練過程，算法結(jié)束，否則，返回步驟1）。

圖3給出了二維空間情況下的候選檢測器切割示意圖。

圖3 二維空間下候選檢測器切割示意圖

在圖3中，正方形區(qū)域表示候選檢測器D1，中間圓形區(qū)域?yàn)橛?xùn)練自體集區(qū)域Self。顯然，D1完全覆蓋了Self，因此，必須對D1進(jìn)行切割。從4個方向分別對D1到Self的空間位置進(jìn)行測量，得出測量距離線長度為a＞b＞c＞d，對應(yīng)的4條切割線均與這4條距離線垂直，分別為 L1，L2，L3，L4。為了盡可能保證大尺寸檢測器形態(tài)的完整性，切割過程依次按照測量距離線由大至小的順序進(jìn)行。

Step 1中，沿切割線L1對原候選檢測器D1進(jìn)行切割，得到新生成熟檢測器D1和右側(cè)的“不合格”候選檢測器D2；

Step 2中，沿切割線L2對原候選檢測器D2進(jìn)行切割，得到新生成熟檢測器D2和下側(cè)的“不合格”候選檢測器D3；

Step 3中，沿切割線L3對原候選檢測器D3進(jìn)行切割，得到新生成熟檢測器D3和左側(cè)的“不合格”候選檢測器D4；

Step 4中，沿切割線L4對原候選檢測器D4進(jìn)行切割，得到新生成熟檢測器D4。

需要指出的是，雖然在圖3中新生成的4個檢測器在圖3的示例中已經(jīng)完全符合要求，但并不代表它們已成為成熟檢測器，還需要與訓(xùn)練自體集中的其他元素分別進(jìn)行比對完成耐受訓(xùn)練。

2.3 成熟檢測器集合優(yōu)化過程

經(jīng)過成熟檢測器耐受訓(xùn)練和訓(xùn)練自體集耐受訓(xùn)練后的檢測器均為合格的檢測器個體，理論上將全部歸入成熟檢測器集合，但由于不同成熟檢測器間可能存在多種復(fù)雜的位置關(guān)系，如“包含”、“部分相交”等，因此，有必要對最終的成熟檢測器集合進(jìn)行優(yōu)化，以期提高檢測器的檢測性能。圖4為成熟檢測器集合中檢測器間可能存在的多種位置關(guān)系。

圖4 成熟檢測器間可能存在的位置關(guān)系

成熟檢測器集合優(yōu)化過程的具體步驟如下：

1）選取成熟檢測器集合中的檢測器Di作為基準(zhǔn)檢測器；

2）計算檢測器Di與成熟檢測器集合中其他檢測器Dj（j≠i）間的距離dis（Di，Dj）；

3）若dis（Di，Dj）≤|RDi-RDj|，則檢測器間存在“包含”情況，圖5為檢測器間存在“包含”情況的示意圖，此時從成熟檢測器集合中刪除半徑較小的檢測器個體；否則，轉(zhuǎn)向4）；其中，RDi與RDj分別表示基準(zhǔn)檢測器Di與其他檢測器Dj的半徑。

圖5 成熟檢測器間的“包含”關(guān)系

圖6 成熟檢測器間的“分離”關(guān)系

4）若dis（Di，Dj）＞|RDi-RDj|，則檢測器間存在“分離”情況。圖6為檢測器間存在“分離”情況的示意圖，以基準(zhǔn)檢測器Di與其他檢測器Dj中心位置連線的中點(diǎn)作為圓心，以dis（Di，Dj）-（RDi+RDj）作為半徑構(gòu)建新檢測器 D（new）k，刪除檢測器 Dj；特殊地，若dis（Di，Dj）-（RDi+RDj）＜rs[j]，則不構(gòu)建新檢測器 D（new）k，并保持檢測器 Di，Dj不變；否則，轉(zhuǎn)向 5）；

5）若|RDi-RDj|≤dis（Di，Dj）≤RDi+RDj，則檢測器間存在“部分相交”情況，圖7為檢測器間存在“部分相交”情況的示意圖；

圖7 成熟檢測器間的“部分相交”關(guān)系

定義參數(shù)β，γ分別為圖7中RDi與dis（Di，Dj）、RDj與dis（Di，Dj）間的夾角，即：

若 max（β，γ）≥π/3 且 β≥γ，則刪除檢測器 Di；若 max（β，γ）≥π/3 且 β＜γ，則刪除檢測器 Dj；否則，保持檢測器 Di，Dj不變；

6）若成熟檢測器中所有檢測器均參與了討論，算法結(jié)束；否則轉(zhuǎn)向2）。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)描述

本節(jié)將對文中所提方法的有效性進(jìn)行仿真驗(yàn)證，仿真實(shí)驗(yàn)平臺是一臺PC，配置為2.3 GHz處理器、4 G內(nèi)存以及VC++程序語言。簡單起見，選取圓環(huán)形數(shù)據(jù)集作為訓(xùn)練自體集，且設(shè)定自體集半徑為 0.05，各維特征均歸一化至[0，1]n區(qū)間內(nèi)，實(shí)驗(yàn)選取Iris標(biāo)準(zhǔn)數(shù)據(jù)作為測試對象。

為了進(jìn)行比較，選取了經(jīng)典RNSA、V-detector以及DNSA 3種方法與本文方法進(jìn)行比較。其中，RNSA方法采用固定半徑型檢測器模型，這里設(shè)定為0.10，而另兩種方法均采取可變半徑型檢測器模型，可以根據(jù)檢測器中心與自體集中心間的距離自適應(yīng)設(shè)定。本節(jié)將針對包括本文方法在內(nèi)的4種方法進(jìn)行3組仿真實(shí)驗(yàn)。

3.2 成熟檢測器數(shù)量比較實(shí)驗(yàn)

在保證一定覆蓋率的前提下，成熟檢測器數(shù)量在一定程度上是衡量一種方法優(yōu)劣的重要指標(biāo)。方法所需的成熟檢測器數(shù)量越少，方法的性能就越優(yōu)越，表1給出了4種方法在成熟檢測器數(shù)量指標(biāo)上的比較結(jié)果。

表1 4種方法的成熟檢測器數(shù)量比較

顯然，隨著覆蓋率水平的提高，4種方法對應(yīng)的成熟檢測器數(shù)量均出現(xiàn)了相應(yīng)的增加；然而，同其他兩種方法相比，DNSA與本文方法的增長幅度明顯緩慢，體現(xiàn)出這兩種方法良好的魯棒性和優(yōu)越的檢測性能，尤其是在覆蓋率達(dá)到99%時，經(jīng)典RNSA對應(yīng)的成熟檢測器達(dá)到10 124，V-detector指標(biāo)為381，而DNSA和本文方法的對應(yīng)指標(biāo)值僅為17和14。

3.3 檢測率與誤報率比較實(shí)驗(yàn)

在估計覆蓋率一定的前提下，檢測率的高低也是一項(xiàng)重要指標(biāo)。表2、表3分別給出了估計覆蓋率在90%～100%范圍內(nèi)時包括本文方法在內(nèi)的4種方法對應(yīng)的檢測率結(jié)果和誤報率結(jié)果。

表2 4種方法的對應(yīng)檢測率比較結(jié)果

表3 4種方法的對應(yīng)誤報率比較結(jié)果

顯然，隨著估計覆蓋率水平的提高，4種方法對應(yīng)的檢測率與誤報率均相應(yīng)增加。當(dāng)估計覆蓋率超過95%時，4種方法的檢測率均超過了99%，獲得了較為理想的檢測結(jié)果，然而，4種方法對應(yīng)的誤報率表現(xiàn)卻大相徑庭，例如當(dāng)估計覆蓋率達(dá)到99%時，4種方法的誤報率分別為55.92%，45.59%，22.12%和16.24%。顯然，本文方法在保證較高檢測器的同時具有最佳的誤報率水平。

3.4 運(yùn)行時間比較實(shí)驗(yàn)

表4給出了4種方法在估計覆蓋率為95%前提下各自的平均運(yùn)行時間，每組數(shù)據(jù)均進(jìn)行3次仿真并取平均值。

表4 4種方法的平均運(yùn)行時間比較

4種方法中，RNSA最為耗時，V-detector方法次之，DNSA方法運(yùn)行時間最短，而本文方法為次優(yōu)，主要原因在于本文方法不同于DNSA方法對未通過訓(xùn)練自體集耐受訓(xùn)練候選檢測器的處理方案，引入了“剪切”機(jī)制對“有瑕疵”的候選檢測器進(jìn)行了切割，最終對成熟檢測器集合還進(jìn)行了優(yōu)化處理，因此，在運(yùn)行時間上要略長于DNSA方法。

4 結(jié)論

本文提出了一種基于二次否性剪切選擇的入侵檢測方法。該方法包含了成熟檢測器耐受訓(xùn)練過程、訓(xùn)練自體集耐受訓(xùn)練過程以及成熟檢測器集合優(yōu)化過程3個重要環(huán)節(jié)，力求使用數(shù)量盡可能少、半徑盡可能大的檢測器覆蓋盡可能大區(qū)域的非自體集合以提升整個入侵檢測系統(tǒng)的綜合性能。理論分析和仿真實(shí)驗(yàn)結(jié)果表明，同現(xiàn)有的幾種經(jīng)典方法相比，本文提出的方法具有更高的檢測率、更低的誤報率以及更少的檢測器數(shù)量。