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

（信息工程大學，河南 鄭州450004）

0 引 言

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

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

從充分反應匹配程度角度進行的r連續(xù)位匹配算法研究較少?；诖耍疚奶岢鲆环N改進型r連續(xù)位匹配算法，即基于權重的基因塊匹配算法，并通過仿真實驗驗證了算法的有效性。

1 理論基礎

1.1 人工免疫基礎

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

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

1.2 陰性選擇算法基礎

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

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

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

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

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

（1）以位為匹配單位，沒有反應匹配程度［11］

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

（2）沒有考慮實際應用中的權重問題［12］

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

3 基于權重的基因塊匹配算法

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

3.1 相關定義

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

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

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

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

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

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

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

3.2 匹配算法規(guī)則

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

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

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

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

3.3 匹配算法檢測流程

檢測流程如圖3所示。

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

4 仿真分析

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

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

采用Matlab2010b仿真平臺進行仿真，實驗數(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ù)不同實驗目的相互組合。

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

4.2 仿真結果分析

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

4.2.1 匹配閾值與相關檢測性能仿真分析

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

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

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

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

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

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

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

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

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

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

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

4.3 改進算法效率分析

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

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

5 結束語

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

r連續(xù)位匹配算法是目前研究的熱點，還有許多問題需要解決。本文未考慮雙層匹配算法中基因塊權重對基因塊內匹配閾值的影響，這是下一步研究的方向［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］.智能計算機與應用，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］.通信學報，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］.四川大學學報 （工程科學版），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匹配算法 ［J］.計算機應用研究，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)絡入侵檢測中的r連續(xù)位匹配算法研究 ［J］.軟件導刊，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］.通信學報，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)絡入侵檢測系統(tǒng) ［D］.重慶：重慶理工大學，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］.計算機科學，2011，38 （10）：181－184.］