鄭德強

（佳木斯大學(xué) 信息電子技術(shù)學(xué)院，黑龍江 佳木斯154000 ）

0 引言

5G 商用時代的全面到來意味著互聯(lián)網(wǎng)信息數(shù)量將迎來指數(shù)型爆炸，互聯(lián)網(wǎng)安全隨即變得更加重要。入侵檢測系統(tǒng)（Intrusion Detection System，IDS）作為一種主動防御的網(wǎng)絡(luò)安全技術(shù)，長期以來一直將其視作防火墻之后的第二道防線。通常情況下，入侵檢測是通過對網(wǎng)絡(luò)流量以及計算機系統(tǒng)日志等進行掃描，發(fā)現(xiàn)危險信息及漏洞。常見的入侵檢測技術(shù)有基于人工免疫、統(tǒng)計分析以及神經(jīng)網(wǎng)絡(luò)［1］等技術(shù)的檢測方法。其中，基于人工免疫的入侵檢測作為一種受生物免疫系統(tǒng)啟發(fā)而提出的入侵檢測技術(shù)，受到了國內(nèi)外學(xué)者的廣泛關(guān)注。

作為人工免疫入侵檢測技術(shù)的核心算法，否定選擇算法（Negative Selection Algorithm，NSA）具有無須先驗知識，只用少量正常樣本便能檢測無限數(shù)據(jù)的特點［2］。由于現(xiàn)代網(wǎng)絡(luò)信息數(shù)據(jù)流的特點，否定選擇算法已經(jīng)從二進制否定選擇算法發(fā)展為現(xiàn)在的實值否定選擇算法（Real-value Negative Selection Algorithm，RNSA）。由于否定選擇機制的特殊性，算法生成的檢測器會存在檢測黑洞或者冗余現(xiàn)象。針對這一特點，Zhou 等人［3］提出了V-detector 算法。

V-detector 算法應(yīng)對檢測冗余現(xiàn)象優(yōu)先生成半徑較大的超球體檢測器，針對覆蓋黑洞問題生成半徑較小的檢測器，這樣有利于控制檢測器的規(guī)模，提高了RNS 的精確性和時效性［4］。但是由于檢測器分布的隨機性和半徑的不確定性也導(dǎo)致了檢測器的高重疊問題，同時V-detector 算法不可避免地沿襲了否定選擇算法存在的檢測黑洞問題。

針對V-detector 存在的問題，文獻［4］利用異常檢測中容易被忽略的非自體元素，將非自體元素進行非自體區(qū)域的檢測以及用來生成檢測器。這樣保證了新生成的檢測器落入檢測黑洞的概率大大減小，提高了檢測黑洞的覆蓋率以及檢測器的質(zhì)量。文獻［5］通過修改檢測器的生成規(guī)則以及對檢測器進行優(yōu)化，同時采用記憶檢測器和成熟檢測器兩種組合，減少了計算量和存儲空間的大小，提高了檢測率，改進了無線傳感器網(wǎng)絡(luò)入侵檢測模型。文獻［6］通過與克隆選擇算法（Clonal Selection Algorithm，CSA）的結(jié)合，引入定距變異的思想。提升了檢測率和覆蓋率，但是由于自體集的龐大，導(dǎo)致算法較為耗時。文獻［7］受容差粗糙集啟發(fā)，提出了一種新的檢測器構(gòu)造方法，將其運用到Vdetector 算法中，提高了檢測效率。

鑒于此，本文引入灰狼優(yōu)化（Grey Wolf Optimizer，GWO），將其運用到檢測器的生成中，并對檢測器的分布進行優(yōu)化，提高檢測器的覆蓋率?；舅枷霝椋和ㄟ^GWO 算法對隨機生成的檢測器分布位置進行優(yōu)化，優(yōu)先生成較大半徑檢測器，同時標(biāo)記出新的檢測器，保證覆蓋率。達到理想覆蓋率后合理調(diào)整適應(yīng)值，進行檢測黑洞的覆蓋。實驗結(jié)果表明，該算法能顯著提高檢測器的分布覆蓋率和減少檢測黑洞，同時運行時間也較為理想。

1 相關(guān)工作

1.1 V-detector 算法

由于檢測器的半徑就是匹配的閾值，所以檢測器的半徑可以作為人工控制的因素來進行調(diào)配。V-detector算法針對實值否定選擇算法存在的檢測器數(shù)量龐大的問題，優(yōu)先使用半徑較大的檢測器先覆蓋非自體區(qū)域；針對檢測漏洞問題，提出使用半徑小的檢測器去覆蓋檢測黑洞。這樣大大提高了檢測器的質(zhì)量，但是檢測器的分布位置仍是隨機產(chǎn)生的，依然有優(yōu)化的空間。因此，可以使用灰狼優(yōu)化算法對檢測器的落點位置進行優(yōu)化，使檢測器分布更加合理。

1.2 灰狼優(yōu)化算法

研究可知，灰狼優(yōu)化算法就是從灰狼群體捕食行為啟發(fā)得到的［8］。灰狼群體有一個非常嚴格的社會統(tǒng)治階層?；依欠N群的等級如圖1 所示。

由圖1 可知，領(lǐng)導(dǎo)層通常是一雄一雌，叫做α，對應(yīng)到算法，α即為算法中的最優(yōu)解。處于第二層的是β狼，β狼屬于從屬狼，也是算法中的次優(yōu)解。第三層的δ狼、也即算法中的第三優(yōu)解。處于最底層的是ω狼，ω為剩余的所有解。

圖1 灰狼種群的等級制度Fig.1 Gray wolf population hierarchy

灰狼算法的數(shù)學(xué)模型可描述為：

灰狼群體的狩獵過程通常由α狼指揮，β狼和δ狼偶爾也會參與狩獵指揮。由于在實際函數(shù)優(yōu)化過程中，問題最優(yōu)解（獵物位置）往往是不可知的，為了模擬灰狼的捕獵過程，規(guī)定α、β和δ對獵物的潛在位置有更好的了解。每次迭代都會得到當(dāng)前最優(yōu)的3 個解的同時，強制其他灰狼個體（包括ω）根據(jù)最優(yōu)位置來更新自己的位置。此處需要用到的數(shù)學(xué)公式可寫為：

2 本文算法

2.1 改進灰狼優(yōu)化算法

針對灰狼算法的改進有很多，例如種群初始化方式、修改位置更新方程、重新設(shè)定距離控制參數(shù)及收斂因子等，為了應(yīng)對形態(tài)空間的復(fù)雜性，本文引入混沌初始化和萊維飛行來增強灰狼優(yōu)化算法的尋優(yōu)能力。

2.1.1 混沌初始化

灰狼種群的初始化十分重要，初始灰狼優(yōu)化算法的迭代種群都是隨機產(chǎn)生，隨機產(chǎn)生的種群容易陷入局部最優(yōu)［9］。對應(yīng)到檢測器生成過程，局部最優(yōu)會導(dǎo)致達到理想檢測率所需檢測器數(shù)量增加，增加運算資源的消耗。因此本次研究中引入混沌機制，用于群體的初始化。

混沌現(xiàn)象是一種非常普遍的非線性行為，表現(xiàn)出運動隨機的同時也存在著一定的內(nèi)在規(guī)律性，因此也被稱為貌似隨機的不規(guī)則運動?；煦鐧C制具有非線性、非周期性、遍歷性等特點，這些特點正有利于克服群體智能算法初始解的盲目性。實驗證明［10］，使用混沌機制進行種群初始化會有利于優(yōu)化算法進行更有效的全局搜索。

混沌機制有很多映射模型，常見的有Logistic 映射、PWLCM 映射、Singer 映射等，本文選取Logistic映射模型［11］進行種群初始化。其數(shù)學(xué)模型如下：

其中，μ可稱為分支參數(shù)，通常取值為4；zk為混沌變量。

2.1.2 萊維飛行

由于自體形態(tài)空間的復(fù)雜性，實際搜索中難免出現(xiàn)尋優(yōu)漏洞，導(dǎo)致檢測黑洞的產(chǎn)生。為了更好地進行全局尋優(yōu)，本文算法引入萊維飛行［12］來改進灰狼算法的尋優(yōu)過程。

萊維飛行得名于其搜索的運動軌跡，即在隨機行走的過程中會有一定的概率實現(xiàn)大跨步，將其與步長分布沒有重尾的隨機行走相比，該運動軌跡像飛行一樣。

簡而言之，萊維飛行是一種以短距離隨機搜索為主，一定概率長距離搜索為輔的搜索行走方式。這種搜索方式可以使得算法在復(fù)雜的自體空間搜索變得更加全面，減少檢測黑洞的產(chǎn)生和避免尋優(yōu)算法陷入局部最優(yōu)。

萊維飛行位置更新公式［13］為：

由于萊維飛行的實現(xiàn)至今未有一個統(tǒng)一的形式，所以本文采用Mantegna 算法模擬，Mantegna 算法數(shù)學(xué)表述如下。

步長s計算公式為：

其中，μ、ν為正態(tài)分布，即：

具體地：

其中，α通常取值為常數(shù)1.5。

2.2 IGV-detector 算法

人工免疫入侵檢測算法的目標(biāo)是生成的檢測器擁有盡可能大的覆蓋率和盡可能小的重疊率，很明顯優(yōu)先使用較大半徑的檢測器有利于得到更大的覆蓋率。

對于檢測器j，假設(shè)pk是離其最近的檢測器的中心點，于是就有：

本文自體和檢測器以及檢測器和檢測器之間的親和力計算仍然采用歐氏距離，即｜ Pk -pj ｜和｜Pi -pj ｜的計算公式見如下：

如果此時存在檢測器i使得｜Pi -pj ｜≤Ri，即該檢測器落在了自體區(qū)域，則該檢測器視為無效檢測器。此時得到檢測器j的半徑：

式（16）保證了每次生成的檢測器都有盡可能大的半徑，同時和自體不會有重疊。通過公式（15）和公式（16）得到檢測器的半徑rj依賴于檢測器的落點pj。由于落點位置的無導(dǎo)數(shù)性質(zhì)，可以使用灰狼算法來優(yōu)化檢測器的pj，同時適應(yīng)值被定義為檢測器的rj大小。對應(yīng)于灰狼算法也就是半徑較大的候選檢測器個體等級更高，每次迭代完成后頭狼α的位置即為相對最優(yōu)檢測器的位置，α值即為該檢測器的半徑大小。

至此，研究給出了IGV-detector 算法流程如圖2所示。改進灰狼算法優(yōu)化后的IGV-detector 算法步驟詳見如下。

圖2 IGV-detector 算法流程Fig.2 IGV-detector algorithm flow chart

Step 1設(shè)定生成成熟檢測器閾值以及自體集自體半徑、灰狼算法迭代次數(shù)等參數(shù)。

Step 2混沌初始化灰狼種群和設(shè)定算法參數(shù)a，A和C。

Step 3初始化前3 只狼的位置并計算每只灰狼個體的適應(yīng)值。

Step 4記適應(yīng)值最好的個體為Xα，適應(yīng)值次之個體為Xβ，適應(yīng)值再次之個體為Xδ。

Step 5在不與自體元素和已有成熟檢測器發(fā)生免疫親和的前提下結(jié)合萊維飛行策略搜索自體空間，通過公式（7）更新每個個體的位置。

Step 6更新灰狼算法參數(shù)a，A和C。

Step 7計算每只灰狼個體的適應(yīng)值，并更新α，β，δ。

Step 8灰狼算法迭代次數(shù)加1，并判斷算法迭代次數(shù)是否到達閾值。如果未到達、轉(zhuǎn)到Step5。反之，繼續(xù)執(zhí)行算法。

Step 9得到Xα即為合格檢測器的中心，α為合格檢測器的半徑。將合格檢測器納入成熟檢測器集。

Step 10判斷成熟檢測器個數(shù)是否到達閾值要求，沒有即轉(zhuǎn)Step 2，達到要求則輸出成熟檢測器集并終止算法。

上文所述的算法保證了每次生成的成熟檢測器盡可能擁有最大的半徑以及最優(yōu)的位置，但是由于迭代過程中迭代方向的不確定，使得落點在每次更換位置時要進行自體和檢測器的免疫耐受，這使得在達到較高的覆蓋率C1時迭代生成一個成熟檢測器所需時間大大增加，延遲到達理想的覆蓋率C2的時間。此時將優(yōu)化算法的適應(yīng)值由候選檢測器半徑改為檢測器覆蓋率，同時候選落點的親和力計算只與自體元素進行。盡管這樣會導(dǎo)致檢測器重疊率增加，但是這樣的重疊會更好地彌補檢測黑洞的產(chǎn)生。

2.3 IGV-detector 算法收斂性分析

全局搜索算法的判斂準(zhǔn)則及相關(guān)定義［15-16］如下。

定義1給定一個目標(biāo)函數(shù)f，函數(shù)的解空間是從Rn到R，S是Rn的一個子集。在S中尋找一個點z，能夠使得函數(shù)f的值最小化或者至少能夠生成一個函數(shù)f在S上的可接受的下確界。

假設(shè)1f（H（z，ξ））≤f（z），如果ξ∈S，則f（H（z，ξ））≤f（ξ）。其中，H是指可以在待求解問題空間產(chǎn)生解的函數(shù)。假設(shè)1 要求H函數(shù)產(chǎn)生的新解優(yōu)于當(dāng)前解。z是存在于解的子集S中的某個最小值，ξ是根據(jù)相應(yīng)算法在子集S中所得到的一系列的可行解。

定義2在Lebesgue 測度空間中，定義搜索的下界為：

其中，v［A］是在集合A上的Lebesgue 測度。

引理1IGV-detector 算法滿足假設(shè)1。

證明由于算法的迭代方向是單調(diào)的，即檢測器的半徑或者整體覆蓋率都是逐漸變大的，所以本文算法明顯滿足假設(shè)1。

引理2IGV-detector 算法滿足Condition 2。

證明假設(shè)2 是指對于位置測度為v的任意一個A的子集，如果采用隨機抽樣的方法，那么重復(fù)錯過集合A的概率必定為零。由于算法的ε可接受區(qū)域Rε?S（Rε＝｛z∈S∣f（z）＜φ+ε｝，ε ＞0），所有在可接受區(qū)域取得點的概率肯定是非零值。文獻［17］已經(jīng)證明了原始灰狼算法的灰狼群狀態(tài)空間的一般狀態(tài)轉(zhuǎn)移至最優(yōu)狀態(tài)的轉(zhuǎn)移概率為1，即：

研究中證明了原始灰狼算法是全局收斂的，即滿足上述條件。IGV-detector 算法是在GWO 算法的基礎(chǔ)上運用混沌初始化和萊維飛行策略更新灰狼種群的位置。因此，對于原始灰狼算法種群，設(shè)其支撐集的并集為α；對運用混沌初始化以及萊維飛行作用的灰狼種群，設(shè)其支撐集的并集為β。由于2種改進策略的隨機性，必然存在整數(shù)t1，使得當(dāng)t ＞t1時，β?S。因此，對于IGV-detector 算法，存在整數(shù)t2，使得當(dāng)t ＞t2時，α∪β?S。定義S的任意Borel 子集A＝Mi，t，則有v（A）＞0，μt［A］＝所以，IGVdetector 算法滿足假設(shè)2。

定理2GWO 算法收斂到全局最優(yōu)，即

證明由于IGV-detector 算法滿足Condition 1和Condition 2，算法滿足定理1 的條件，所以IGVdetector 算法是一個全局收斂算法，也即算法以概率1 全局收斂。

3 實驗及結(jié)果分析

為了更直觀地表示檢測器分布情況，本文算法在二維數(shù)據(jù)集和公共數(shù)據(jù)集NSL-KDD 下進行了驗證。實驗在Matlab R2018b 軟件下進行，其中主機配備16 GB 內(nèi)存、Intel（R）Core（TM）i5-1035G1 CPU、Windows 10 操作系統(tǒng)。實驗統(tǒng)計工具采用Matlab 自帶的探查器工具。

3.1 算法在二維數(shù)據(jù)集下的驗證

二維數(shù)據(jù)集選取的是Zhou［3］二維人造數(shù)據(jù)集。該數(shù)據(jù)集有環(huán)形及五角星等自體分布形態(tài)，每種形態(tài)有1 000 條自體數(shù)據(jù)，皆被歸一化到［0，1］之間。本實驗對比了V-detector 算法、粒子群優(yōu)化［18］的PV-detector 算法、灰狼算法優(yōu)化的GV-detector 算法以及改進灰狼算法優(yōu)化的IGV-detector 算法，對比達到相同覆蓋率所需檢測器個數(shù)及時間、以及生成固定檢測器個數(shù)所達到的覆蓋率。

覆蓋率的計算采取文獻［3］中的方法，即在檢測空間內(nèi)隨機采樣m個點，如果有n個點未被覆蓋到，則估計的覆蓋范圍為1-n／m。當(dāng)期望的覆蓋率為α＝1-n／m時，至少迭代的次數(shù)應(yīng)為：

實驗選取五角星二維空間和環(huán)形二維空間進行測試。設(shè)置PV-detector 算法、GV-detector 算法、IGV-detector 算法的尋優(yōu)迭代次數(shù)為100，當(dāng)本文算法生成檢測器覆蓋率在五角星二維空間下達到95%時，各算法生成檢測器的分布覆蓋情況如圖3所示。

圖3 4 種算法生成相同檢測器的覆蓋情況Fig.3 The coverage for the same detector generated by four algorithms

由圖3 可知，由于V-detector 算法檢測落點都是未加干預(yù)地隨機產(chǎn)生，所以其重疊率較高，覆蓋率較低；由于檢測器的分布有了指導(dǎo)方向，所以其余3種算法的檢測器分布更加合理，優(yōu)先在目標(biāo)空間邊緣生成大半徑檢測器，有效避免了邊緣檢測黑洞的產(chǎn)生，覆蓋率更高。同時由于粒子群算法陷入“早熟”現(xiàn)象，灰狼優(yōu)化算法擁有比粒子群算法更好的尋優(yōu)和避免陷入局部最優(yōu)的能力［8］，所以GVdetector 算法、IGV-detector 算法的覆蓋率比PVdetector 算法的覆蓋率更高。同樣地，由于引入了萊維飛行，使得算法在尋優(yōu)過程中實現(xiàn)了對自體區(qū)域的跨越，覆蓋效果更好。

為了驗證改進算法的魯棒性和穩(wěn)定性，本文在相同條件下重復(fù)試驗了20次，測試在五角星和環(huán)形二維數(shù)據(jù)集下進行，當(dāng)達到相同覆蓋率4 種算法所用時間和檢測器個數(shù)詳見表1、表2。

表1 達到95%覆蓋率所用時間對比Tab.1 Comparison of the time to reach 95%coverage

表2 達到95%覆蓋率所用檢測器個數(shù)對比Tab.2 Comparison of the number of detectors to achieve 95%coverage

3.2 算法在公共數(shù)據(jù)集下的驗證

公共數(shù)據(jù)集采取NSL-KDD 數(shù)據(jù)集，該數(shù)據(jù)集是KDD CUP99 數(shù)據(jù)集的改進版本，相較于后者，NSL-KDD 去除了大量的冗余信息，訓(xùn)練集和測試集的數(shù)據(jù)規(guī)?？s小后使數(shù)據(jù)集變得更加合理，同時使得實驗有了一致性和可對比性。NSL-KDD 里面訓(xùn)練集包含125 973 條記錄，測試集包含22 544 條記錄，其中數(shù)據(jù)維數(shù)為42 維。本文實驗選取了其中20%的數(shù)據(jù)。

在數(shù)據(jù)預(yù)處理部分，由于原始數(shù)據(jù)的離散性，需要進行連續(xù)化處理。比如協(xié)議類型部分，變換規(guī)則為：TCP →1；UDP →2；ICMP →3 等。同時由于高維數(shù)據(jù)對檢測率的影響［19］，需要對數(shù)據(jù)進行降維處理。數(shù)據(jù)的降維方式有很多，本文選取的是比較成熟的PCA 方法，選擇保留90%的特征降維后數(shù)據(jù)維度為20 維。自體集數(shù)據(jù)的半徑對最終的實驗檢測指標(biāo)的影響是巨大的，本文的自體集數(shù)據(jù)半徑設(shè)為0.01。歸一化方法選擇最大最小歸一化方法，方法公式具體如下：

其中，xmin為樣本中數(shù)據(jù)最小值，xmax為樣本中數(shù)據(jù)最大值。

入侵檢測對應(yīng)于實際應(yīng)用的評價指標(biāo)主要有檢測率、誤報率等，本實驗測試了4 種算法不同的檢測器數(shù)量對應(yīng)的檢測率。結(jié)果如圖4 所示。由圖4 中分析可知，V-detector 由于其生成檢測器分布的不確定性，檢測率呈現(xiàn)緩慢遞增的趨勢。其余3 種優(yōu)化算法在檢測器數(shù)目較少時便能達到較理想的檢測率，這是因為在檢測器生成早期優(yōu)先生成高質(zhì)量的檢測器，在算法后期生成的檢測器多用于彌補檢測黑洞，因此檢測率增長緩慢，但總地來看優(yōu)化后的算法仍能以相對較少的檢測器數(shù)量達到較高的檢測率。

圖4 4 種算法生成相同檢測器數(shù)量與檢測率關(guān)系Fig.4 The relationship between the number of detectors and the detection rate generated by the four algorithms

生成200 個檢測器所需時間對比見表3。由表3 可知，達到相同檢測率優(yōu)化后的算法所需時間更短。

表3 生成200 個檢測器所需時間對比Tab.3 Comparison of the time required to generate 200 detectors

總地來看，IGV-detector 算法能在較短的時間達到更高的檢測率，符合入侵檢測實時性的要求。

4 結(jié)束語

本文通過引入灰狼優(yōu)化算法對經(jīng)典算法Vdetector 檢測器的分布進行了優(yōu)化?；依莾?yōu)化算法等元啟發(fā)式方法由于其無需計算導(dǎo)數(shù)、無需過多先驗知識等優(yōu)點在近些年受到了大量關(guān)注。Vdetector 繼承了否定選擇算法的“基因”，即檢測器都是隨機產(chǎn)生的。在自體空間未知的情況下，隨機似乎更能滿足檢測器分布廣泛的需求。在引入灰狼優(yōu)化算法之后，檢測器的耐受分布便有了指導(dǎo)的方向，同時由于群體尋優(yōu)的機制存在可以更好地應(yīng)對復(fù)雜的自體空間。結(jié)果表明，改進后的V-detector算法提高了檢測器的質(zhì)量，減少了不必要的檢測器重疊以及對檢測黑洞進行了更好的覆蓋。但是由于迭代過程中尋優(yōu)方向的不確定性，導(dǎo)致每次產(chǎn)生的新的候選落點都要與自體和已有成熟檢測器進行免疫耐受，這種不確定性導(dǎo)致了在檢測器生成后期生成一個成熟檢測器的時間有所增加。以后的改進方向應(yīng)是對迭代落點的方向進行引導(dǎo)，避免或者減少這種大量的親和力計算。