張明清，程 建，孔紅山，劉小虎

（信息工程大學(xué)，河南 鄭州450004）

0 引 言

當(dāng)前研究人員模仿生物免疫系統(tǒng)相關(guān)特性，建立人工免疫系統(tǒng) （artificial immune system，AIS），用以保護(hù)主機(jī)或網(wǎng)絡(luò)，檢測入侵行為［1－3］。陰性選擇算法是人工免疫系統(tǒng)中常用的免疫算法，而匹配算法是陰性選擇算法的重要組成部分［4］，目前主要采用的是r連續(xù)位匹配算法［5］。

唐俊等［6］對r值不變進(jìn)行了改進(jìn)，提出了一種動(dòng)態(tài)r連續(xù)位匹配算法，增強(qiáng)了算法的適用性，但r值的變動(dòng)會對入侵檢測系統(tǒng)造成較大影響；韓亮等［7］對r連續(xù)位匹配算法中匹配閾值取值與檢測效率的關(guān)系進(jìn)行了研究，指出了相應(yīng)問題，但并未對算法進(jìn)行改進(jìn)；蘆天亮等［8］對陰性選擇算法中的黑洞問題進(jìn)行了研究，提出了一種采用雙重檢測器的陰性選擇算法，該算法能夠提高黑洞覆蓋率，但只在檢測器生成方面做了改進(jìn)，未涉及匹配算法；陳園園［9］對傳統(tǒng)r連續(xù)位匹配算法進(jìn)行了改進(jìn)，提出了基于基因塊的匹配，但匹配閾值仍采用傳統(tǒng)取值，降低了算法適用性。

從充分反應(yīng)匹配程度角度進(jìn)行的r連續(xù)位匹配算法研究較少。基于此，本文提出一種改進(jìn)型r連續(xù)位匹配算法，即基于權(quán)重的基因塊匹配算法，并通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 理論基礎(chǔ)

1.1 人工免疫基礎(chǔ)

生物免疫系統(tǒng)是一個(gè)十分精密的，集入侵檢測、防御于一體的系統(tǒng)。其將自身物質(zhì)視為自體，外界入侵視為非自體。生物體主要通過抗體細(xì)胞來識別和防御非自體物質(zhì)，抗體細(xì)胞需要通過自身耐受的檢驗(yàn)才能生成，如果其與任一自體細(xì)胞相匹配則將其殺死，通過自身耐受后才能成為真正起作用的抗體?？贵w與抗原 （即非自體）進(jìn)行作用，如果匹配則將該抗原殺死。人工免疫系統(tǒng)借鑒生物免疫系統(tǒng)的相關(guān)特性來解決工程實(shí)踐中遇到的一些現(xiàn)實(shí)問題，其廣泛應(yīng)用于入侵檢測等應(yīng)用領(lǐng)域。人工免疫系統(tǒng)與入侵檢測系統(tǒng)概念對比見表1。

表1 人工免疫與入侵檢測系統(tǒng)概念對比

1.2 陰性選擇算法基礎(chǔ)

陰性選擇算法是一種異常檢測算法，其基本思想是將所有非正常行為視為異常。因此檢測器的生成與生物免疫系統(tǒng)中抗體生成相似，需要經(jīng)過自體耐受訓(xùn)練，也即需要確保生成的檢測器不與正常行為匹配。通過自體耐受訓(xùn)練的檢測器對網(wǎng)絡(luò)行為進(jìn)行檢測，如果匹配則認(rèn)為其是入侵。

2 傳統(tǒng)r連續(xù)位匹配算法分析

傳統(tǒng)r連續(xù)位匹配算法指2個(gè)字符串X和Y相對應(yīng)的位置上如果有r個(gè)及以上連續(xù)字符相同，則稱兩字符串匹配，其中r為匹配閾值。給出傳統(tǒng)匹配算法數(shù)學(xué)定義如下［10］。

定義 如果字符串X和Y從P1位開始有連續(xù)K1位相同；從P2位開始有連續(xù)K2位相同，以此類推，從Pn位開始有連續(xù)的Kn位相同。則取Kmax＝max｛k1，k2，…，kn｝，Kmax即為字符串X和Y的匹配位數(shù)，Kmax≥r則匹配，否則不匹配。舉例如圖1所示。

該匹配算法簡單、易用，但也存在以下缺點(diǎn)：

（1）以位為匹配單位，沒有反應(yīng)匹配程度［11］

某一網(wǎng)絡(luò)訪問由2種屬性a、b構(gòu)成，a采用3位編碼，b采用2位編碼，自體集為 ｛10001，11011｝，設(shè)a、b這2種屬性均只有一種取值代表入侵行為，入侵行為記為a：001，b：10，當(dāng)且僅當(dāng)a，b中有一種為入侵屬性時(shí)，該網(wǎng)絡(luò)行為被認(rèn)定為入侵行為。當(dāng)r＝2時(shí)，根據(jù)陰性選擇算法規(guī)則，01100是合格檢測器，則采用未經(jīng)改進(jìn)的r連續(xù)位匹配規(guī)則，行為A＝10101被認(rèn)定為入侵行為，然而實(shí)際情況則是A為正常訪問行為，因?yàn)槠?個(gè)子屬性101與01均不是入侵屬性。造成此類錯(cuò)誤的原因在于傳統(tǒng)匹配以位為單位，該網(wǎng)絡(luò)行為由2個(gè)子屬性組成，而10101與01100的匹配位則是10，即2個(gè)子行為連接部分，因此并未真正體現(xiàn)子行為的匹配程度。錯(cuò)誤匹配如圖2所示。

（2）沒有考慮實(shí)際應(yīng)用中的權(quán)重問題［12］

攻擊檢測需要監(jiān)視多種參數(shù)，各個(gè)參數(shù)在表征攻擊程度方面并不相同。在實(shí)際的網(wǎng)絡(luò)入侵檢測中相關(guān)參數(shù)可能有端口、源IP、目的IP、網(wǎng)絡(luò)類型等等，而各種參數(shù)之間的重要性并不完全相同。例如源IP地址沒有在服務(wù)器記錄的IP地址范圍內(nèi)，該訪問很有可能是入侵行為，則參數(shù)源IP權(quán)重應(yīng)相對大些，這些在傳統(tǒng)的匹配算法中并沒有很好的體現(xiàn)。

3 基于權(quán)重的基因塊匹配算法

針對傳統(tǒng)算法的不足，本節(jié)提出了基于權(quán)重的基因塊匹配算法。

3.1 相關(guān)定義

（1）檢測器集合DET：通過自體集耐受的字符串集合；

（2）字符串S：由二進(jìn)制字符組成的基因塊構(gòu)成，其包括基因塊數(shù)目為N，字符總長度為n；

（3）基因GEN：生物學(xué)中，基因是指攜帶有遺傳信息的DNA或RNA序列，是控制生物性狀的基本遺傳單位。陰性選擇算法中指能夠表示某類信息的字符串，對于入侵檢測系統(tǒng)而言基因?qū)?yīng)最基本的匹配單位，不同的基因代表不同的特征屬性。字符串S＝ ｛gen1，gen2，…，genn｝，genn所代表的性狀種類數(shù)為i，則其所需編碼位數(shù)為l，其中l(wèi)＝示不超過，l為整數(shù)），字符串S表示為

（4）權(quán)重wi：基因塊i對應(yīng)的權(quán)重為wi，其滿足w1＋w2＋…＋wn＝1。每個(gè)基因的權(quán)重wi由基因所代表不同特征對入侵檢測的重要性決定；權(quán)重越大，表示該基因相對越重要；

（5）基因塊匹配閾值ri：基因塊之間是否匹配的臨界值。匹配程度大于等于ri時(shí)，基因塊匹配，匹配算法采用傳統(tǒng)的r連續(xù)位匹配；

（6）親和度AD：字符串之間的匹配程度；

（7）字符串匹配閾值R：判斷字符串之間是否匹配的臨界值，當(dāng)親和度AD大于等于R時(shí)匹配，小于則不匹配。在該改進(jìn)匹配算法中匹配基因不需要連續(xù)。根據(jù)親和度AD的定義，計(jì)算得出AD，與R比較即可得出是否匹配。

3.2 匹配算法規(guī)則

該算法進(jìn)行雙層匹配。第一層是基因塊間的匹配，首先對二進(jìn)制字符串A、B對應(yīng)的基因塊進(jìn)行匹配，采用傳統(tǒng)的r連續(xù)位匹配規(guī)則，當(dāng)匹配位數(shù)大于等于ri（ri為基因塊Ai與Bi匹配閾值）時(shí)，基因塊Ai與Bi匹配，由于各基因所代表的行為不同，其位數(shù)長短也不盡相同，不同基因的匹配閾值應(yīng)根據(jù)相應(yīng)基因長度確定。記基因塊i長度為lengthi，結(jié)合傳統(tǒng)的匹配方法得基因塊匹配中閾值ri的確定函數(shù)為

式中：r——傳統(tǒng)連續(xù)位匹配閾值，則基因塊匹配函數(shù)表示如下

第二層為字符串的匹配，根據(jù)第一層匹配得出的f（Ai，Bi），即各基因塊間的匹配程度，根據(jù)基因塊的各權(quán)重，計(jì)算得出字符串A與B的親和度

若AD≥R匹配，否則不匹配。

3.3 匹配算法檢測流程

檢測流程如圖3所示。

根據(jù)陰性選擇原理，首先需要生成足夠的檢測器，然后檢測器開始檢測。定義自體集集合SELF，非自體集NONSELF，根據(jù)實(shí)際應(yīng)用確定字符串S由幾種基因組成，并確定基因權(quán)重及閾值R，r；隨機(jī)生成檢測器并根據(jù)改進(jìn)匹配算法規(guī)則進(jìn)行耐受訓(xùn)練；如果AD≥R則刪除字符串，否則將a加入檢測器集合DET；循環(huán)上述過程直至生成實(shí)驗(yàn)所需數(shù)量檢測器；檢測器對網(wǎng)絡(luò)行為進(jìn)行檢測，如果全部檢測器均沒有與之發(fā)生匹配，則判斷網(wǎng)絡(luò)行為正常，否則判斷其為入侵。

4 仿真分析

針對上節(jié)改進(jìn)的匹配算法，本節(jié)進(jìn)行仿真分析，從檢測率、誤檢率2個(gè)方面驗(yàn)證算法的正確性和有效性，并對改進(jìn)算法的效率進(jìn)行理論分析。

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

采用Matlab2010b仿真平臺進(jìn)行仿真，實(shí)驗(yàn)數(shù)據(jù)選擇R.A.Fisher Iris plants dataset經(jīng)典數(shù)據(jù)集［13］。Iris數(shù)據(jù)集包含3類數(shù)據(jù)：setosa，versicolour，virginica，分別記為data1，data2，data3。每類50組數(shù)據(jù)，每組數(shù)據(jù)4種特征?？梢詫?類數(shù)據(jù)分別視為自體集與非自體集，根據(jù)不同實(shí)驗(yàn)?zāi)康南嗷ソM合。

（1）權(quán)重：實(shí)際應(yīng)用中應(yīng)根據(jù)先驗(yàn)知識或相應(yīng)專家意見來判斷特征的權(quán)重。由于本實(shí)驗(yàn)數(shù)據(jù)均已知，因此當(dāng)某一類數(shù)據(jù)確定為自體集后，可以采用非自體集與自體集之差的大小來確定相應(yīng)基因權(quán)重；

4.2 仿真結(jié)果分析

檢測器相關(guān)檢測性能不僅由匹配算法決定，而且與檢測器數(shù)量密切相關(guān)。在相同匹配算法條件下，檢測器數(shù)量越多，檢測率越高。在相同檢測器數(shù)量條件下，匹配閾值r的取值對相關(guān)檢測性能也具有很大影響。因此本節(jié)從檢測器數(shù)量與匹配閾值2個(gè)方面對2種算法綜合比較。

4.2.1 匹配閾值與相關(guān)檢測性能仿真分析

實(shí)驗(yàn)1：對上述data1、data2、data3設(shè)定3種組合情況：①data1為自體集，data2為非自體集；②data2為自體集，data3為非自體集；③data3為自體集，data1為非自體集。根據(jù)經(jīng)驗(yàn)值確定檢測器數(shù)量為100，對3種組合情況分別進(jìn)行仿真，對3組仿真結(jié)果取平均值。圖4是通過仿真得出的2種算法的r值與檢測率的關(guān)系。

圖4 中可以看出，匹配閾值在1到7時(shí)二者檢測率均達(dá)到100%，這是因?yàn)槠ヅ溟撝递^低，每個(gè)檢測器的檢測范圍很大，而入侵?jǐn)?shù)據(jù)數(shù)量較少。匹配閾值進(jìn)一步增加，可以看出改進(jìn)算法優(yōu)于傳統(tǒng)算法。當(dāng)匹配閾值過大時(shí)由于檢測器數(shù)量有限，將導(dǎo)致檢測率迅速降低，直至為0。

實(shí)驗(yàn)2：對data1、data2、data3，分別取各自的前25組為自體集，后25組為 “非自體集”。對3種組合情況分別進(jìn)行仿真，對3組仿真結(jié)果取平均值。得傳統(tǒng)算法與改進(jìn)算法誤檢率比較如圖5所示。

圖5 中可以看出，匹配閾值在1到5時(shí)二者誤檢率均達(dá)到100%，這是由匹配閾值過低導(dǎo)致的。匹配閾值進(jìn)一步增加，可以看出改進(jìn)算法誤檢率明顯低于傳統(tǒng)算法，由于檢測器數(shù)量有限當(dāng)匹配閾值過大時(shí)誤檢率迅速降低，直至為0。

4.2.2 檢測器數(shù)量與相關(guān)檢測性能仿真分析

綜合4.2.1小節(jié)中誤檢率與檢測率取值，可得匹配閾值的合理取值范圍為9～13。匹配閾值為9時(shí)，檢測器數(shù)量與檢測率與誤檢率的關(guān)系分析如下。

實(shí)驗(yàn)3：data1、data2、data3的設(shè)定與實(shí)驗(yàn)1相同。分別進(jìn)行仿真，取平均值。傳統(tǒng)算法與改進(jìn)算法檢測率比較如圖6所示。

圖6 中可以看出，隨著檢測器數(shù)量的增多，檢測率也隨之提高，整體上改進(jìn)算法檢測率高于傳統(tǒng)算法，從曲線的波動(dòng)性可以看出傳統(tǒng)算法波動(dòng)性較大，改進(jìn)算法則相對平緩。

實(shí)驗(yàn)4：data1、data2、data3的設(shè)定與實(shí)驗(yàn)2相同。分別進(jìn)行仿真，取平均值。傳統(tǒng)算法與改進(jìn)算法誤檢率比較如圖7所示。

圖7 中可以看出，隨著檢測器數(shù)量的增多，誤檢率隨之上升，整體上改進(jìn)算法誤檢率低于傳統(tǒng)算法，且改進(jìn)算法曲線較為平緩，傳統(tǒng)算法曲線波動(dòng)較大。二者誤檢率較高的原因在于自體集數(shù)量較少，但不影響二者的比較。

綜合上述仿真結(jié)果可以得出改進(jìn)算法在相關(guān)檢測性能方面均優(yōu)于傳統(tǒng)算法。

4.3 改進(jìn)算法效率分析

對改進(jìn)算法與傳統(tǒng)算法的復(fù)雜度進(jìn)行分析比較，以明確改進(jìn)算法是否實(shí)用。

設(shè)字符串S其包括基因塊數(shù)目為N，每塊長度為ij（1≤j≤N）字符串總長度為n，匹配閾值為R。設(shè)傳統(tǒng)算法時(shí)間復(fù)雜度為o（n）。在此不考慮傳統(tǒng)算法計(jì)算最長匹配字符數(shù)的具體算法，但顯然可知該算法時(shí)間復(fù)雜度至少與字符串總長度線性相關(guān)，即o（n）＝k＊n。則根據(jù)改進(jìn)算法規(guī)則，第1層匹配算法的復(fù)雜度為而根據(jù)式 （3）改進(jìn)算法第2層只是進(jìn)行了線性相加，因此從總體上看改進(jìn)算法的復(fù)雜度幾乎沒有增加。

5 結(jié)束語

本文針對陰性選擇算法中廣泛使用的r連續(xù)位匹配算法存在的問題，對其進(jìn)行了深入分析，提出了基于權(quán)重的基因塊匹配算法，采用雙層匹配，能夠充分反應(yīng)匹配程度。采用matlab進(jìn)行了仿真實(shí)現(xiàn)，從3個(gè)方面對改進(jìn)算法進(jìn)行了分析。分析結(jié)果表明所提出的改進(jìn)算法明顯降低了誤檢率，提高了檢測率，且并未增加算法復(fù)雜度。

r連續(xù)位匹配算法是目前研究的熱點(diǎn)，還有許多問題需要解決。本文未考慮雙層匹配算法中基因塊權(quán)重對基因塊內(nèi)匹配閾值的影響，這是下一步研究的方向［14］。

［1］Astha Keshariya，Noria Foukia.DDoS defense mechanisms：A new taxonomy ［G］.LNCS 5939：Data Privacy Management and Autonomous Spontaneous Security，2010：222－236.

［2］WU S X，Banzhaf W.The use of computational intelligence in intrusion detection systems：A review ［J］.Applied Soft Computing，2010，10 （1）：1－35.

［3］WU Yuanyuan，ZENG Aiguo.Intrusion detection based on artificial immune classifier ［J］.Intelligent Computer and Applications，2013，3 （1）：75－78 （in Chinese）.［伍媛媛，曾愛國.基于人工免疫分類器的入侵檢測方法 ［J］.智能計(jì)算機(jī)與應(yīng)用，2013，3 （1）：75－78.］

［4］JIN Zhangzan，LIAO Minghong，XIAO Gang.Survey of negative selection algorithms［J］.Journal on Communications，2013，34（1）：159－170 （in Chinese）.［金章贊，廖明宏，肖剛.否定選擇算法綜述 ［J］.通信學(xué)報(bào)，2013，34 （1）：159－170.］

［5］YANG Jin，LIU Xiaojie，LI Tao，et al.Matching algorithm in artificial immune system ［J］.Journal of Sichuan University（Engineering Science Edition），2008，40 （3）：126－131 （in Chinese）.［楊進(jìn)，劉曉潔，李濤，等.人工免疫中匹配算法研究 ［J］.四川大學(xué)學(xué)報(bào) （工程科學(xué)版），2008，40 （3）：126－131.］

［6］TANG Jun，ZHAO Xiaojuan.Rvariable matching algorithm used for IDS ［J］.Application Research of Computers，2010，27 （2）：745－748 （in Chinese）.［唐俊，趙曉娟.一種用于入侵檢測系統(tǒng)的可變r(jià)匹配算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27 （2）：745－748.］

［7］HAN Liang，LI Chengyun.Research on r contiguous bits matching in immunity network intrusion detection ［J］.Software Guide，2012，11 （11）：60－62 （in Chinese）.［韓亮，李成云.免疫網(wǎng)絡(luò)入侵檢測中的r連續(xù)位匹配算法研究 ［J］.軟件導(dǎo)刊，2012，11 （11）：60－62.］

［8］LU Tianliang，ZHENG Kangfeng，F(xiàn)U Rongrong.Anomaly detection system with hole coverage optimization based on negative selection algorithm ［J］.Journal on Communications，2013，34 （1）：128－135 （in Chinese）.［蘆天亮，鄭康鋒，傅蓉蓉，等.基于陰性選擇算法的異常檢測系統(tǒng)黑洞覆蓋優(yōu)化［J］.通信學(xué)報(bào)，2013，34 （1）：128－135.］

［9］CHEN Yuanyuan.Network intrusion detection system based on artificial immune ［D］.Chongqing：Chongqing University of Technology，2011（in Chinese）.［陳園園.基于人工免疫的網(wǎng)絡(luò)入侵檢測系統(tǒng) ［D］.重慶：重慶理工大學(xué)，2011.］

［10］Feng Xiang，Zhao Tianling.Research on intrusion detection system using improved artificial immune algorithm ［C］／／IEEE International Conference on Computer Science and Information Technology，2011：636－640.

［11］Dasgupta D，YU SH，Nino F.Recent advances in artificial immune systems－models and applications ［J］.Applied Soft Computing，2011，11 （2）：1574－1587.

［12］GAO XZ，Chow MY，Pelta D.Theory and applications of artificial immune systems ［J］.Neural Computing and Applications，2010，19 （8）：1101－1102.

［13］Sir Ronald Fidher.iris ［DB／OL］.［2000－07－11／2013／09－27］.http：／／archive.ics.uci.edu／ml／machine－learning－databases／iris／.

［14］YANG Ning，WANG Qian.Negative Selection algorithm based on niche strategy ［J］.Computer Science，2011，38（10）：181－184 （in Chinese）.［楊寧，王茜.一種基于小生境策略的陰性選擇算法 ［J］.計(jì)算機(jī)科學(xué)，2011，38 （10）：181－184.］