分級結構Adaboost算法在無線傳感器網絡入侵檢測中的應用研究*

楊曉元 ，胡志鵬，魏立線

(1.武警工程學院電子技術系網絡與信息安全武警部隊重點實驗室，西安710086;2.西安電子科技大學網絡信息安全教育部重點實驗室，西安710071)

無線傳感器網絡部署區域的開放特性和無線通信的廣播特性導致網絡極易受到外界的各種攻擊，嚴重威脅著整個網絡信息安全與正常使用[1－2]。解決這個問題的辦法就是開發無線傳感器網絡入侵檢測系統，以保證網絡的正常運行。

對傳統網絡中的入侵檢測技術的研究已經較為成熟。Denning[3]提出了5種統計分析方法，其中常用的有操作模型和馬爾科夫模型。Wenke Lee研究組和 Stephanie Forrest研究組[4－5]主要使用數據挖掘的方法，采用人工智能、機器學習等技術自動分析原有的數據，從中挖掘出潛在的模式，并預測出入侵行為。除了以上檢測方法外，還有利用神經網絡、優先狀態自動機、計算機免疫系統和基于代理等技術進行網絡的入侵檢測[6]。

由于無線傳感器節點資源嚴重受限導致傳統網絡中的各種入侵檢測技術無法運用其中。其主要原因有兩個:(1)傳統網絡中的入侵檢測算法大多計算量巨大，單個節點的計算能力不足以完成整個檢測過程;(2)傳統網絡中的入侵檢測算法沒有考慮數據交互而引起的能量消耗，對于采用無線通信的傳感器節點來說，大量的數據交互將迅速耗盡節點的能量，最終導致整個網絡的壽命大大減少。所以迫切需要研究新的檢測方法，在檢測精度上、計算復雜度上、能量消耗都能很好地適用于無線傳感器網絡。

現有的無線傳感器網絡入侵檢測方法很多，卻沒有一個統一的標準對檢測算法的性能做出合理的評估，導致有些算法一味追求高檢測率而沒有兼顧能量消耗及時間復雜度等問題。為了統一業內的評價標準，在 Porras和 Debar[7]等人提出的傳統網絡入侵檢測算法性能的評價標準的基礎上，針對無線傳感器網絡資源受限的特點，對其入侵檢測系統的評價標準進行了探討，提出了無線傳感器網絡入侵檢測算法性能的評價標準。

提出了一種改進的Adaboost無線傳感器網絡入侵檢測算法，通過增大權重變化量，減輕下一級訓練的負擔，從而有效地強化對小類錯分樣本的學習，然后對比傳感器節點數據和已建立的入侵行為特征來判斷是否存在入侵行為。采用了分級結構提高了檢測算法的實時性，采用了二叉樹的方法解決了入侵檢測的多分類問題，提出了入侵檢測系統數據采集傳輸協議解決因分級結構帶來的通信開銷增大的問題。

實驗結果表明:本算法的準確性、及時性得到了較大提高，同時具有低能耗性。將數據采集傳輸協議運用在其它檢測算法中，得到了較好的效果。

1 無線傳感器網絡入侵檢測系統的評價標準

無線傳感器網絡是近年來才發展起來的新興技術，面臨的攻擊的威脅很多。盡管人們對無線傳感器網絡入侵檢測系統有了初步的研究，但卻沒有一個明確的標準來評價其性能。傳統網絡中對于入侵檢測算法的評價標準對如何評價無線傳感器網絡入侵檢測算法的性能有重要的借鑒意義。目前，對于傳統網絡入侵檢測系統的評估是根據Porras等給出的3個評價因素和后來Debar等在此基礎上又增加的兩個性能評價測度:

準確性 指IDS從各種行為中正確地識別入侵的能力。

處理性 指一個IDS處理數據源數據的速度。

完備性 指IDS能夠檢測出所有攻擊行為的能力。

容錯性 由于IDS是檢測入侵的重要手段，所以它也就成為很多入侵者攻擊的首選目標，IDS自身必須能夠抵御對它自身的攻擊。

及時性 及時性要求IDS必須盡快地分析數據并把分析結果傳播出去，以使系統安全管理者能夠在入侵攻擊尚未造成更大危害以前做出反應。

如果評價無線傳感器網絡入侵檢測系統套用以上幾個指標是不夠的，因為無線傳感器網絡相對于傳統網絡在能量、計量能力上有很大的差別，所以評價無線傳感器網絡入侵檢測系統必須加上低能耗性。下面對這評價指標進行闡述。

低能耗性 由于無線傳感器網絡中的節點受到能量的限制，所以要求入侵檢測系統必須滿足低能量耗的特點，降低能耗可以從兩個方面著手，一是降低計算復雜度;二是減少通信開銷。

2 無線傳感器網絡入侵檢測算法

2.1 改進的Adaboost算法及其理論分析

Adaboost算法是在每一訓練樣本都賦予一個權重，代表它被某個分量分類器選入訓練集的概率。如果某個樣本點已經被準確地分類，那么在構造下一個訓練集中，它被選中的概率就低;相反，如果某個樣本點沒有被正確分類，那么它的權重就提高，在構造下一個訓練集中，它就會被優先選中。通過這樣的方式，AdaBoost算法能夠針對性地處理那些較困難樣本[8－9]。

在具體實現上，最初令每個樣本的權重都相等。對于第k次迭代操作，就根據這些權重來選取樣本點，進而訓練分類器Ck。然后就根據這個分類器，來提高被它錯分的那些樣本點的權重，并降低可以被正確分類的樣本點的權重。然后，更新過權重的樣本集用來訓練下一個分類器Ck+1。整個訓練過程如此進行下去。由于Adaboost算法簡單高效，所以在模式識別方面得到了廣泛的應用。本文對傳統的Adaboost算法作了改進，通過增大權重變化量、尋找最優分類器等方法，大大減輕下一級的負擔，從而提高了檢測的準確性與及時性。

改進的Adaboost算法的具體步驟如下;

(1)選取訓練樣本{(x1，y1)，……，(xn，yn)}，其中xi表示每個入侵檢測數據的特征向量，yi為類別標識，yi={0，1，2，3，4}分別代表正常樣本和 4 種不同的入侵樣本;

(2)初始化權值，每個訓練樣本具有初始權值wo(i)=1/n，即每個樣本的初始權值相同;

(3)for t=1……t;

(a)對于樣本向量中的每一種的特征j，采用排列組合的方法，從中任意選取m個特征，訓練弱分類器 hj，其分類誤差為，(M是被錯分的樣本的數量);

(b)選擇其中具有最小誤差的分類器hj;作為ht，并記錄其特征;

(d)t++;

(4)最終找到了k個最優分類器，h1……hk。每個分類器的權值為，最后的強分類器的判決函數為:，其中sgn為符號函數;根據H(x)的值可以對樣本進行分類。θ為判決閾值，初始值設定為所有弱分類器權值的平均值，即。

2.2 分級分類器的設計

無線傳感器節點計算能力有限，如果構造一個強分類器進行檢測，勢必需要大量的計算時間，而入侵檢測又對時實性的要求較高，在滿足檢測精度的同時又要符合實時性的要求是困難的。為了解決這個問題，采用了分級式的分類器[10]。

首先，每個檢測節點廣播自己的能量;然后，按照能量的多少對檢測節點分級，能量較多的劃分為第1級檢測節點，次之的劃分為第2級檢測節點，以此類推，分級數量直到滿足所需的檢測精度為止。其次，上一檢測級內的所有檢測節點都對該節點進行檢測，將檢測結果發送到匯總節點，在匯總節點投票判決該節點是否受到攻擊，如果可以確定該節點的數據類型，便直接將其排除或做出相應的入侵響應。如果不能確定，便將其送入第2檢測級進行處理。以此類推，至到最后一級。如果最后一級仍無法做出判斷，可以簡單的認為該節點為異常節點，并做出相應的入侵響應。

靠近前面各級的分類器，只使用小部分重要特征進行判斷，結構簡單，卻對大部分的樣本做出了檢測;靠近后面各級的分類器，雖然采用大量的特征用來檢測，但是由于需要處理的樣本數目很少，對于整體運算時間的耗費很小。分級結構的入侵檢測系統如圖1所示。

圖1 分級結構的入侵檢測系統框圖

2.3 基于二叉樹的多分類方法

由于文中所使用的弱分類器h是針對二分類的情況，對于多分類的情況，可以將多類問題分解為多個二分類問題，本文使用二叉樹方法，每個分類器可以將一類數據的樣本分開。具體的說，就是在一個k類分類問題中，先將k類問題進行排序，將第1類與第2……k類樣本進行訓練，作為第1個分類器，然后將第2類與第3……k類樣本進行訓練，作為第2個分類器，最后直到把k類數據分開。以4類分類問題為例，多類分類的二叉樹結構如圖2所示[11]。

圖2 四分類二叉樹結構

3 數據采集傳輸協議

由于采用了檢測算法是分級結構，級與級之間的通信是必不可少的，所以不得不考慮級與級之間數據傳輸所消耗的時間與能量。

傳輸的數據包有2種方法:第1種方法是本級檢測節點只收集本級所要用到的特征數據進行檢測，傳輸給下一檢測級的信息是“那些節點為不可確定節點”，處于后一級的節點收到消息后，需要重新收集數據，再做入侵檢測，至到最后一級;第2種方法是將采集信息的任務全都交給第一檢測級，第一檢測級收集各級所需要的所有特征，檢測時從中選取本級所需特征，如果本級對某一節點的檢測結果為不確定節點，本級節點就將所有特征數據全部傳給下一檢測級，下一檢測級直接從接收到的數據中提取所需特征進行檢測，無需重新收集所需數據。

理論分析上述2種方法，采用第1種方法，通信數據量較小，但是實時性不高，需要對數據進行多次收集。采用第2種方法，雖然時效性可能有所提高但是通信量會增大。

為了解決時效性與通信能耗之間的矛盾，提出了數據采集傳輸協議。協議的具體辦法是加入數據采集傳輸節點，這種節點負責采集檢測所需要用到的特征信息，給檢測節點發送采集信息，還要與匯總節點通信。

第1步，各檢測級中的n個檢測節點接收Sink節點上訓練好的分類器，作為自身的檢測算法。第2步，數據采集傳輸節點采集檢測所需數據，將采集到的按照相應檢測級傳輸給的檢測節點。第3步，檢測節點對從數據傳輸節點接收到的數據進行處理;而后將檢測結果發送給匯總節點。第4步，匯總結點對各檢測節點的檢測結果匯總，如果本級的n個檢測節點中有r個檢測節點都認為該節點未受到攻擊或可確定所受到攻擊的類型，便直接將其排除或做出相應的入侵響應;如果該節點檢測結果經匯總后，各類所得的票數都小r，那么就認為該節點為不可確定節點。此時匯總節點通知數據采集傳輸節點，向下一檢測級的檢測節點傳輸檢測所需用到的數據，下一檢測級按照上述的方法處理信息，直到最后一級。如果最后一級仍無法確定該節點的狀況，那么可以簡單的認為該節點為異常節點，并對其做出入侵響應。具體過程如圖3所示。

圖3 入侵檢測示意圖

4 分級結構的無線傳感器網絡入侵檢測模型

為了實現分級結構，首先必須建立合適的網絡入侵檢測模型。

假設無線傳感器網絡模型是一個隨即部署在某區域的無線傳感器網絡。這個網絡可以劃分為若干個簇。每個簇內的節點可以劃分為簇頭節點、普通節點、檢測節點和數據采集傳輸節點，簇頭節點負責協調和控制簇內節點及其數據的融合，同時還要負責和Sink節點的通信;檢測節點負責檢測入侵行為;數據采集傳輸節點是用來采集傳輸檢測所需數據。

其中Sink節點不受電量、存儲空間和計算能力等的限制，可以單獨運行一套復雜的入侵檢測算法。所以訓練分類器、通知各檢測節點調整參數都由Sink節點負責。

分級結構中每一個檢測級中有n個檢測節點和一個匯總節點。檢測節點的作用是數據分類;匯總節點的作用是將本級各個檢測節點的處理的結果匯總，得到各級最終的檢測結果，然后再將不可確定節點的信息傳送給數據采集處理節點。

數據采集處理節點的作用是收集各級檢測所需用到的數據;將各檢測級所需用到的特征從收集到的數據中提取出來后，發送給各個檢測級用來檢測。

網絡的具體結構如圖4所示。

圖4 網絡結構

5 仿真實驗

使用MATLAB2010B和NS2作為實驗平臺，實驗用數據由Naval Research實驗室提供的無線傳感器網絡數據集[12－13]，包含了正常流量集{NS1，NS2}和攻擊數據集{AS1，AS2，AS3，AS4}。其中 AS1、AS2、AS3、AS4模擬實現了 Passive Sinkhole Attacks(PSA)、Periodic Route Error Attacks(PREA)、Active Sinkhole Attacks(ASA)，DOS等四個攻擊場景，其中還包括了大量的正常數據信息。這4大類攻擊目前是無線傳感器網入侵方式，因此可以使用這5類數據進行實驗[13－14]。

5.1 準確性評估

首先隨機選取訓練用和測試用樣本各3000條，其中正常數據占60%，DOS攻擊樣本點15%，Passive Sinkhole Attacks攻擊樣本占10%，Periodic Route Error Attacks攻擊占10%，Active Sinkhole Attacks攻擊占5%。使用這些訓練數據訓練分類器，隨后用測試樣本進行性能測試，文中改進的Adaboost算法使用了三級分類器，表1是每一級處理所用特征個數以及經各級測試后可確定樣本數的比例。

表1 分級結構各級所用特特征數和可確定樣本數

改進的Adaboost的檢測率與誤檢測率如表2所示。

表2 分級結構各級測試結果

為了對改進的Adaboost算法的性能作出準確的評價，將其檢測結果與Adaboost算法、與BP網絡、SVM、核Fisher線性判別等強分類算法進行比較。其結果如表3和表4所示。

表3 兩種Adaboost算法測試結果

表4 各種強分類器測試結果

通過實驗數據對比，本文所提出的算法在檢測精度上只是略高于Adaboost、SVM、BP網絡等算法，這是因為文中只用到了三級分類器，這樣的檢測率對一般的網絡是足夠的。如果某網絡對檢測率要求效高，可以通過增加分級級數來達到目的，但同時也會帶來能耗增大的問題。

5.2 能耗評估

當檢測節點運行入侵檢測系統時，通信增加的能耗要遠大于計算增加的能耗，節點傳輸一個比特數據所耗費的能量要比計算一個比特所耗費的能量高約3個數量級。因此本文討論能耗問題時只考慮檢測過程中的通信能耗[14]。

Chndrakasan[15]提出了一種能量消耗模型:傳感器節點發送k比特數據所消耗的能量為

傳感器節點接收k比特數據所消耗的能量為

其中εamp是信號放大器的放大倍數，Esend和Erev是發送電路和接收電路的能耗，d是信號的發送距離。

分別對加入和未加入數據采集傳輸協議的檢測系統的能耗情況進行仿真實驗。為了能夠更客觀地評價改進的Adaboost算法的低能耗性，還仿真了采用核Fisher線性判算法的檢測節點能耗情況。能耗如圖5所示。

圖5 兩種分類算法的能耗

通過圖5可以看出，未加入數據采集傳輸協議時，采用兩種檢測算法的檢測節點能耗都非常高。加入數據采集傳輸協議后，節點的能耗都有了明顯的降低。雖然改進Adaboost的算法的能耗略高于核Fisher線性判別的能耗。但對其評估時，考慮到及時性、準確，能耗的略高可以忽略。

對檢測節點內的能耗的分析，可反映出檢測系統可工作的時間。對于整體網絡來說，還要對加入檢測系統前后網絡的生存周期進行比較。

網絡生存周期的定義目前主要有2種:第1，當網絡中有一個節點能量耗盡，就認為此時就是網絡的生存周期;第2，網絡中有些存點死亡，但是整個網絡還是能繼續工作，這樣我們也可以認為網絡是存在的，此時就是網絡的生存周期。文中網絡是部署在野外工作環境中的大型網絡，所以采用第2種說法更為合適。加入檢測系統前后網絡的生存周期如圖6所示。

圖6

從圖6中可以看出，加入了檢測系統在有入侵情況下，大大提高了網絡的生存周期;即便在沒有入侵的情況下，也不會對網絡的生存周期影響太大。這是因為加入的檢測系統自成一體，其中的各個節點所需要的能量來自于自身，不會給網絡帶來額外能耗。整體網絡能耗的略微增加，主要是由入侵響應時刪除入侵節點導致的拓撲變化和收接轉發檢測結果所產生的。

5.3 及時性評估

評價入侵檢測算法的性能，僅僅對比檢測率與誤檢率是不科學的，還需要考慮到時間因素。好的檢測算法即要滿足高的檢測率還要滿足低的時間消耗。

由于本文中的檢測算法是分級結構，所以在時間的計算上，考慮檢測用時的同時還需考慮兩級之間數據傳輸所消耗的時間。表5是分級結構各級測試所用時間。

表5 分級結構各級測試所用時間

定義1設分級結構分類器共有n級，各級所用的時間為t1……tn，經各級測試后所能確定數據類型的樣本占總數的比例為ω1……ωn，那么分級結構分類器檢測所用的加權平均時間為

定義2假設測試樣本有m條，分級結構分類器共有n級，經過各級測試后所能確定數據類型的樣本占總數的比例為ω1……ωn，那么需要傳給下一級檢測的樣本的數量為，那么分類器檢測時的加權平均傳輸量為，l為一個數據包的包長。

根據IEEE802.15.4中MAC層的數據幀格式，可以將數據包需要分為3類，第1類為檢測節向匯總節點發送檢測結果，它的包長l可以認為是8個字節，包括2個字節的幀控制域;1個字節的幀序號;2個字節的地址消息;1個字節的MAC層有效數據(檢測結果);2個字節的幀檢驗序列;第2類為匯總節點向數據采集傳輸節點傳送不可確定節點信息，它的包長l可以認為是9個字節，MAC層有效數據為2字節;第3類為數據采集節點向檢測節點發送檢測用數據，它的包長l需要根據傳輸的特征向量的大小來確定，一般每一個特征向量的數據大小為1字節。

表6 各級傳輸所用時間

根據定義1和定義2可以計算出改進的Adaboost算法所用的總時間為T=t1+t2

另外，還將文中算法用時與其它幾種算法的用時進行了對比，表7是各種分類器所用時間。

表7 各分類器檢測用時間

從表7可以看出改進的Adaboost算法在時間的消耗上遠遠小于其它各種分類器，從而可以更好的滿足無線傳感器網絡入侵檢測對實時性的要求。

6 結論

本文對如何評價無線傳感器網絡入侵檢測系統的性能做出評價標準。提出了一種改進的Adaboost的無線傳感器網絡入侵檢測算法，該算法對比傳感器節點數據和已建立的入侵行為特征來判斷是否存在入侵行為。雖然本算法具有高效的檢測率和高效的實時性，但同時卻帶來了高能耗的問題，為了解決高能耗，提出了數據采集傳輸協議。通過理論分析和仿真實驗，使用文中提出的評價指標對其性能進行估價。綜合準確性、低能耗性、及時性考慮，改進的Adaboost算法的性能要高于其它的檢測算法。

另外，為了測評數據采集傳輸協議的效果，還將其運用在核Fisher線性判別檢測算法中，使用本協議后，該算法性能有明顯提高，足以證明本協議適用于各種入侵檢測算法。

但是，對于評價標準中的處理性、完備性、容錯性未能做出定性定量的評價。如何定性定量的評價一個無線傳感器網絡入侵檢測系統的這幾個性質是下一步工作的重點。

[1]Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Network:A Survey on Sensor Network[J].IEEE Communications Magazine，2002，40(8):102－114.

[2]Perrig A，Stankovic J，Wagner D.Security in Wireless Sensor Networks[J].Communications of the ACM，2004，47(6):53－57.

[3]Denning D E.An Intrusion Detection Model[J].IEEE Transactions on Software Engineering，1987，13(2):222－232.

[4]Lee W，Stolfo S J，Mok K W.A Data Mining Framework for Building Intrusion Detection Models[C]//Proceedings of IEEE Symposium on Security and Privacy，Oakland，1999.110－116.

[5]Lee W，Stolfo S J，Mok K W.Adaptive Intrusion Detection:A Data Mining Approach[C]//Artificial Intelligence Review.2002，14:533－567.3989.Berlin:Springer-Verlag，2006:293－308.

[6]Rajasegarar S，Leckie C，Palaniswami M，et al.Distributed Anomaly Detection in Wireless Sensor Networks[C]//Proceedings of the 10th IEEE Singapore International Conference on Communication System(ICCS 2006).

[7]王白亮，羅守山，楊義先.入侵檢測系統的測試與評估[EB/OL].http://www.netmaker.com/art_8032.html.

[8]張重慶，李明祿，伍民友.數據收集傳感器網絡的負載平衡網絡構建方法[J].軟件學報，2007，18(5):1110－1121.

[9]Richard O，DudaPeterE，HartDavid G Stort.Pattern Classification second Edition[M].機械工業出版社，2005.

[10]王勇，陶曉玲.分級結構的AdaBoost入侵檢測方法研究[J].西安電子科技大學學報(自然科學版)，2008:263－268.

[11]Perrig A，Szewczyk R，Tygar J D，et al.SPINS:Security Protocols for Sensor Networks[J].Wireless Networks，2002，8(5):521－534.

[12]杜曉通.無線傳感器網絡絡技術與工程應用[M].機械工業出版社，2010.

[13]Downard I.Simulating Sensor Networks in NS-2.Technical Report[R].NRL/FR/5522－04－10073，Naval Research Laboratory，Washington，D.C.，U.S.A.，May 2004.

[14]Yan K Q，Wang S C，Liu C W.A Hybrid Intrusion Detection System of Cluster-Based Wireless Sensor Networks[C]//Proceedings of the International Multi Conference of Engineers and Computer Scientists 2009Ⅰ.

[15]Heinzelman W B，Chndrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[D].IEEE Transaction on Wireless Communications，2002，1(4):660－670.

[16]Onat I，Miri A.An Intrusion Detection System for Wireless Sensor Networks[C]//Proceedings of the IEEE International Conference on Wireless and Mobile Computing，Networking and Communications(WiMOB 2005).