無線網絡中基于貝葉斯博弈模型的入侵檢測算法研究

陳行，陶軍

(1.東南大學 計算機網絡和信息集成教育部重點實驗室，江蘇 南京 210096；2.東南大學 計算機科學與工程學院，江蘇 南京 210096)

1 引言

近年來無線通信技術在全世界范圍內得到了飛速的發展，由于能夠方便地支持用戶的移動性，無線網絡成為 Internet的重要發展方向之一。無線網絡節點的計算、存儲、能量資源往往非常有限，無線信道帶寬往往十分有限而且很不穩定。無線節點的移動性、無線信道的開放性更使得無線網絡的安全性變得非常脆弱[1]，網絡使用者本能的自私行為很難受到遏制，無線節點之間的行為往往相互影響并難于集中管理，而博弈理論正是研究無線網絡安全問題的有力工具[2]。

入侵檢測技術可以發現網絡中的異常現象，目前已有數種無線網絡的入侵檢測部署方案[3～5]。基于網絡的入侵檢測系統通過檢測網絡中的報文，觀察網絡中發生的異常行為。網絡攻擊存在一定的模式，通過分析異常行為發生的頻率、種類和順序等要素，提取特征值，創建攻擊知識庫，可以判斷網絡是否遭到攻擊和遭到何種攻擊。然而網絡攻擊往往會發生一定的變化，采用固定不變的入侵檢測參數無法把發生變化的攻擊檢測出來，必須根據網絡受攻擊的狀況不斷對入侵檢測參數進行調整[6]。本文將貝葉斯博弈理論運用到無線網絡中的入侵檢測研究中，對入侵檢測參數調整問題展開討論。

2 入侵檢測參數調整問題描述

由于無線節點資源的有限性，應當采用算法復雜度較低的檢測算法。本文采用誤用檢測的思路[6]：每種網絡攻擊都由一系列相互關聯的異常行為組成，當這一系列異常行為連續以高于正常頻率出現的時候，才判斷系統遭到攻擊并發出警報。無線網絡的特點決定網絡中可能存在著諸如網絡信道帶寬的無故變化，網絡連接無故中斷然后又突然恢復，網絡節點無規律的離開網絡然后又無規律的重新加入網絡等情況[7]。所以即使網絡沒有遭到攻擊，異常行為也會以一定的概率發生。因此這里提出“閾值”[8]的概念，只有當閾值被超過的時候，才認為發生了攻擊行為。針對不同種類的攻擊，對閾值的定義是不相同的。它可能與異常行為的數量相關，可能與異常行為的頻率相關，可能與異常行為的種類相關，也可能與異常行為的發生順序相關，還可以是多種因素組成的復合向量。構成攻擊行為的一系列惡意異常行為應當分布在一定的時間間隔內，否則會失去攻擊效果，所以入侵檢測系統對于攻擊行為的檢測也應當被約束在一定的時間間隔之內。只要攻擊行為以一定的頻率反復發生，便一定會有機會完整地分布在入侵檢測的時間間隔之內。

定義 1 在正常情況下異常行為發生的頻率被稱為正常頻率PN，將入侵檢測的時間間隔稱為TI，將入侵檢測算法調整的時間間隔稱為T。由攻擊行為引發的異常行為被稱為惡意異常行為。

每一種攻擊都有一組相關的異常行為以及與之對應的閾值和時間間隔TI。當攻擊行為發生變化，惡意異常行為在時間間隔TI內可能沒有越過閾值，攻擊沒有被檢測出來，但是攻擊行為確確實實發生了。為了能更精確地檢測出攻擊行為，需要對檢測參數進行調整，增大檢測攻擊的時間間隔TI，即每隔時間T逐步增大時間間隔TI，T＞TI。這使得入侵檢測系統有機會檢測出那些在閾值之下的攻擊活動。當入侵檢測系統檢測到攻擊的時候，系統可以對入侵行為進行分析，提取其中異常行為的信息，對閾值和時間間隔進行修正。這使得入侵檢測系統能夠跟蹤攻擊的變化情況，調整閾值。

3 基于貝葉斯博弈的入侵檢測博弈模型及其完美均衡

根據無線節點的能源、無線連接數量、所轉發的報文數量等要素可以判斷這個無線節點在網絡中的重要性。將無線節點的價值設置為ω，惡意節點的攻擊獲得成功的收益也為 ω，無線節點進行入侵檢測的代價為Cd，攻擊者發動攻擊的代價為Ca。當惡意節點進行攻擊時，入侵檢測系統能夠以 α的概率發出正確的警報，當網絡沒有受到攻擊時入侵檢測系統以β的概率發出誤警，誤警會給系統帶來的損失為r。博弈雙方的收益函數可以用表1來描述。

表1 博弈收益表

假設入侵檢測系統以 p的概率對網絡進行檢測，惡意節點以q的概率對網絡進行攻擊，網絡中存在惡意節點的概率為 μ。得到入侵檢測系統的收益期望為公式 Ed=p[ q(μ a ω+μβr )-βr-Cd]+ω-qμω，惡意節點的收益期望為公式Ea=q(-paω+ω-Ca)。用取導數的方法可以得到，當入侵檢測系統以的概率進行網絡檢測，惡意節點以的概率進行網絡攻擊時，網絡安全博弈取得平衡[9]。

將時間間隔TI理解成一個博弈周期，在每一個博弈周期中，根據上一周期的檢測結果運用貝葉斯法則對惡意節點存在概率μ進行修正。如果入侵檢測系統發出警報，用式來對信念進行修正。如果入侵檢測系統沒有發出警報，那就用式進行修正。然后重新計算每一個博弈周期中合理的p*和 q*。

命題 1 在基于貝葉斯博弈的入侵檢測博弈模型中存在完美均衡。

證明 這里根據文獻[9]中的條件5來依次證明完美均衡的存在性。

這里的入侵檢測博弈是一個雙人博弈，只有 2個局中人，網絡用戶和網絡安全系統。局中人只有一個博弈對手，所以局中人對博弈對手類型的信念必然是相互獨立的，而且其他局中人對他的信念也是一致的，所以條件1和條件4必然符合。通過觀察信念概率迭代式(1)和式(2)，可以發現對惡意節點存在概率的信念μ的修正結果僅僅取決上一周期的信念本身和網絡用戶在本周期的行動，因此條件3也成立。在每個回合對博弈對手的信念進行修正時引入誤報概率α、β，所以條件2必然符合。考慮到網絡安全系統只有一個類型，所以博弈策略集中不需要對網絡安全系統的類型進行判斷，因此條件5也滿足。從上面的證明可以知道，基于貝葉斯博弈的入侵檢測博弈模型的階段均衡策略同時滿足文獻[9]中的條件5，所以它就是此博弈的完美博弈均衡點。

4 基于貝葉斯博弈的入侵檢測調整

4.1 入侵檢測時間間隔調整算法

入侵檢測系統并不確切知道網絡中是否真的存在惡意節點，它不斷搜集無線網絡中的報文信息，檢測網絡中存在的異常行為。為了檢測出可能發生一定變化的攻擊，需要對入侵檢測算法進行一定的調整，不完全信息動態博弈理論為這種調整提供了理論基礎。

在博弈周期內惡意節點的攻擊概率為q*，其攻擊行為引起的惡意異常行為在時間間隔 TI內超越閾值的概率也為q*。如果在博弈周期中沒有檢測出攻擊行為，可能是因為沒有惡意節點發起攻擊，也可能是因為攻擊引起的惡意異常行為沒有越過閾值。為了檢測出可能存在的攻擊，這里假設網絡中必然存在進行攻擊的惡意節點，因為攻擊行為發生了一定的變化，使得惡意異常行為的時間分布跨度超過了TI，所以入侵檢測系統不能正確地檢測出攻擊行為。于是入侵檢測系統將受到攻擊時正確發出警報的概率α取為0。將α=0代入式(2)，得到

然而網絡攻擊者并不清楚入侵檢測系統的調整情況，所以它將正確報警概率α設置為初始值，運用式來計算周期t中發動攻擊的概率qt。

這里設計基于貝葉斯博弈的入侵檢測時間間隔調整算法（TSMA-BG,time span modify algorithm based on Bayes game）。

在時間間隔T內存在n個TI時間的博弈周期，n=T/TI，周期編號為k,k+1,…,k+n-1。運用迭代式(3)和式(4)，計算各博弈周期中惡意節點的攻擊概率qt，然后求和，得到時間間隔T內攻擊行為發生次數的期望值，即攻擊的次數期望約為將時間間隔T除以攻擊次數期望，就得到了時間間隔TI的修正值

觀察式(3)，易證得μt+1＞μt，所以得到經過這種方法修正的 TI必然比前一個時間間隔T內的TI值要大。

4.2 對入侵檢測參數的修正算法

針對無線網絡的攻擊多種多樣，可以抽象成多種多樣的特征。為簡單起見，這里將網絡攻擊抽象成異常行為種類 VoM、異常行為頻率 FoM、時間分布跨度SoA這3個要素。只有當檢測到的異常行為包括了足夠的種類，每種異常行為的頻率足夠高，并且在這2個條件能在一定的時間內同時被滿足，才認為網絡遭到攻擊，并發出警報。一旦網絡攻擊被發現，網絡安全系統行動起來對網絡進行全面的分析。分析攻擊源頭，判斷其行為模式，將惡意異常行為的VoM、FoM和SoA整理出來，用得到的新數據對攻擊閾值和入侵檢測時間間隔進行修正。

這里設計入侵檢測參數修正算法(DPMA,detection parameter modify algorithm)，算法如下。

惡意異常行為的種類：VoM={p,q,r,s},保持不變。攻擊時間分布跨度：

惡意異常行為的頻率：

在式(5)、式(6)中，VoM表示攻擊與異常行為p、q、r、s相關聯，這不會隨著入侵檢測參數的調整而改變。表示在博弈周期t內，攻擊相關的異常行為分布的時間跨度，α、β表示修正參數。表示在博弈周期t中異常行為r的頻率閾值，PNr表示正常情況下異常行為 r的發生頻率。表示在剛檢測到的攻擊行為中時間跨度和異常行為 r的頻率。這里應該特別指出，每一種攻擊行為都有與之相關的 VoM和 SoA，與攻擊行為相關的每一個異常行為都有各自的FoM。

4.3 針對多個異常行為進行的檢測時間間隔調整

經過實驗發現，當一種攻擊行為包含有多種惡意異常行為的時候，對閾值的調整需要變得非常謹慎。入侵檢測系統可以精確地檢測出惡意異常行為的發生概率并進行入侵檢測參數修正。當攻擊只有一種惡意異常行為的時候，閾值和檢測時間間隔TI可以很快調整至穩定狀態，此時入侵檢測系統能以很高的概率檢測出攻擊行為。而當攻擊包含多種異常行為的時候，則必須要求每種異常行為都達到相應的閾值。如果一種異常行為到達閾值的概率為a，a＜1，那么n種異常行為同時到達閾值的概率則為an，an會隨著n值的增大而迅速變小。實驗證明，當n≥3的時候，根據攻擊行為信息進行參數調整，閾值和入侵檢測時間間隔TI無法穩定下來，在出現TI值大幅上升后緩緩下降，再大幅上升，反復震蕩的現象。這是因為對入侵檢測參數的修正使TI下降到一定程度時，入侵檢測系統無法檢測到發生的攻擊，于是在時間間隔T后，又進行入侵檢測時間間隔調整。當檢測到攻擊行為后，又根據檢測到的信息進行入侵檢測參數修正，反復進行。

在這樣的情況下，原有的辦法無法完全解決問題，此時應當對參數修正的目標進行調整，即入侵檢測系統首先根據檢測到的攻擊行為信息進行參數修正，隨著參數修正的不斷進行，入侵檢測系統開始無法有效地檢測到攻擊行為。此時應當將最近一次檢測到攻擊行為的入侵檢測參數作為修正目標，而不是直接將檢測到的攻擊行為參數作為修正目標。即在DPMA算法中，用最后一次檢測成功的參數來取代這種機制被稱為基于回退機制的入侵檢測參數修正算法(DPMA-DB,detection parameter modify algorithm based on drawback mechanism)。

5 入侵檢測算法的數據結構和實現

本節為入侵檢測參數調整設計數據結構和基本算法。首先是攻擊知識庫，它由一個二維數組和2個一維數組組成。二維數組 FoM[voa][vom]表示攻擊行為相關的異常行為頻率閾值，橫坐標vom表示異常行為的種類，縱坐標voa表示網絡攻擊的種類，節點FoM[i][j]表示在網絡攻擊 i中異常行為 j的頻率閾值。一維數組SoA[voa]表示每種網絡攻擊的時間分布跨度，一維數組TSA[voa]表示每種網絡攻擊的算法調整時間間隔T。

設置2個時鐘數組clockI[voa]、clockT[voa]，針對每種網絡攻擊分別在2個數組中各保存一個時鐘，分別為入侵檢測時間間隔和算法調整時間間隔計時。當時鐘值到達時間間隔時將時鐘清零，重新開始計時。clockI[voa]對應時間間隔 SoA[voa]，clockT[voa]則對應入侵檢測算法調整時間間隔T。

設置二維數組 counter[voa][vom]來保存異常行為計數器，節點counter[i][j]保存了網絡攻擊i中異常行為j的發生數量。每當異常行為k被發現一次，數組的第k列節點值都增加1。當時鐘clockI[l]清零時，要將數組的第l行節點清零，重新開始計算異常行為的數量。當第l行的每一個節點counter[l][j]的值都滿足 counter[l][j]≥SoA[l]×FoM[l][j]，認為網絡遭到了攻擊，發出警報。此時也要將數組的第 l行節點清零，重新開始計數，同時將時鐘 clockI[l]和clockT[l]清零，重新開始計時。網絡診斷模塊也同時啟動，對網絡攻擊進行全面分析，收集網絡攻擊的詳細信息，阻止網絡攻擊的繼續，并運用式(5)、式(6)對入侵檢測參數進行調整，將調整結果分別保存到數組 FoM[voa][vom]、SoA[voa]中去。當時鐘clockT[l]清零的時候，運用 4.1節中的 TSMA-BG算法對入侵檢測時間間隔進行調整。

6 模擬實驗及實驗結果

這里用網絡模擬軟件 NS2[10]來對算法進行仿真，模擬惡意節點對多跳無線網絡進行攻擊的情景及網絡安全系統的反應。

實驗1 對灰洞攻擊的檢測和分析

惡意節點以一定的概率丟棄應當轉發的報文，阻礙多跳無線網絡中的報文傳輸，這被稱為灰洞攻擊。由于無線通信的特征，正常的無線信道本身也存在著一定的報文傳輸失敗概率。入侵檢測系統通過統計無線鏈路中報文傳輸失敗的概率來發現灰洞攻擊行為，當傳輸失敗概率超過閾值的時候，入侵檢測系統發出警報。入侵檢測節點觀察鄰居節點收到報文和轉發報文的數量[5]，可以精確地找到惡意節點及其行為特征。這為惡意節點行為特征的修正提供了必要的信息。

將網絡系統的價值ω設置為500，網絡安全系統進行入侵檢測的代價Cd設置為100（在移動的無線節點中進行入侵檢測通常要付出很高的代價），惡意節點發動攻擊的代價Ca為50，誤警損失r設置為100，正確發出警報的概率α為0.9，誤警的概率為 0.2。報文傳輸失敗的攻擊閾值取為 0.95，分別將惡意異常行為的發生概率取為0.6和0.3。入侵檢測算法調整的時間間隔T被設置為50個博弈周期，檢測攻擊的時間間隔TI的初始值被設置為5個時間單位。時間間隔TI和攻擊閾值的修正參數α和β都被設置為 0.5。觀察入侵檢測時間間隔 TI的調整過程和攻擊閾值的調整過程。

在圖1中，橫坐標表示博弈周期，縱坐標表示入侵檢測時間間隔TI。這里不進行閾值的修正而只進行時間間隔TI的調整。圖中的實線表示惡意異常行為概率為0.3時入侵檢測時間間隔的變化情況，觀察圖1可以知道，在第50個博弈周期，也就是第一個時入侵檢測算法調整的時間間隔T結束的時候，進行了第一次入侵檢測時間間隔調整，TI由 5上升為12。在第100個博弈周期即第2個時間間隔T時進行了第二次入侵檢測時間間隔調整，TI被調整為22。在第112個博弈周期時，入侵檢測系統檢測到了攻擊行為，隨即根據檢測到的信息對TI進行修正。每檢測出一次攻擊就進行一次修正，使得TI不斷下降，逐步穩定在 17個時間單位。圖中的虛線表明惡意異常行為概率為0.6時，在第一個時間間隔T中就檢測出了攻擊行為，根據檢測出的攻擊信息進行的調整結果反而使得時間間隔 TI逐步上升，最終穩定在7個周期的時間內。

圖1 單獨進行入侵檢測時間間隔調整

這里研究同時進行參數修正和入侵檢測時間間隔調整的情況下，閾值和時間間隔 TI的變化情況。圖2和圖3中的2條曲線表示惡意異常行為的發生概率分別為0.6和0.3時，TI和閾值的變化情況。當第一個時間間隔T結束的時候，TI開始第一次調整，從第二個時間間隔T開始檢測到攻擊行為，開始根據檢測到的信息進行參數修正。閾值經修正不斷減小，分別穩定為0.6和0.3，這和惡意異常行為的發生概率相符合。當發生概率為0.3時，TI首先上升，然后逐步下降為至 5。而發生概率為 0.6時，TI直接下降直到5。這是因為TI在調整的同時，閾值也在不斷下降。隨著閾值的穩定，時間間隔回歸到了初始的時間間隔 5，此時入侵檢測系統可以正常的檢測出變化過的攻擊行為。

圖2 時間間隔的變化情況

圖3 攻擊閾值的變化情況

實驗2 針對隧道攻擊的檢測和分析

這里模擬惡意節點進行隧道攻擊的情景，選取3種異常行為進行判斷：修改路由控制報文序列號使之失效、發送錯誤的路由控制報文使報文向惡意節點匯聚、將收集的報文向特定節點轉發。將其閾值設置為{0.95,0.95,0.95}，惡意異常行為的發生概率為{0.6,0.65,0.7}。其他參數設置與實驗1中設置的相同。

圖4中實線表示對包含3種異常行為的隧道攻擊進行入侵檢測時TI的變化情況，虛線表示對只有一種異常行為的灰洞攻擊進行入侵檢測時TI的變化情況。這里直接使用了DPMA算法。如圖中所示，當只有一種異常行為時，對檢測時間間隔TI的調整取得了很好的效果，當TI穩定的時候，入侵檢測系統可以以很高的概率檢測出潛在的攻擊行為。而當有 3種異常行為時，TI值出現大幅度的波動，此時入侵檢測系統對攻擊行為的檢測概率也很低，往往低于50%。具體原因參見4.3節的分析。

圖4 調整比較

這里針對隧道攻擊進行入侵檢測時采用的不同入侵檢測參數修正算法進行研究。圖5中的虛線表示采用DPMA算法進行參數修正，而實線則表示采用DPMA-DB算法進行參數修正。觀察發現，當采用DPMA算法的時候，TI出現了較大的波動，而且這種波動沒有趨向穩定的趨勢，會一直持續下去。采用DPMA-DB算法時，TI值最低為5，然后逐漸回升，并最終穩定在8。這表明DPMA-DB算法可以使TI達到合適的穩定值，實驗結果同時還表明，此算法可以使入侵檢測系統能以大約85%的概率檢測出攻擊行為。

圖5 入侵檢測方式比較

圖6展示了采用DPMA-DP調整算法后，攻擊閾值的變化情況，3條曲線分別表示3種異常行為的攻擊閾值。實驗結果表明，算法可以對攻擊閾值進行有效的調整，最終得到穩定的結果。

圖6 攻擊閾值的調整情況

7 結束語

本文將貝葉斯博弈理論引入到無線網絡中的入侵檢測研究中，運用不完全信息動態博弈中的完美均衡計算多個博弈周期中網絡攻擊者發動攻擊的期望，設計入侵檢測時間間隔調整算法TSMA-BG，使得入侵檢測系統能夠有效地檢測出發生變化的攻擊行為。根據檢測出的攻擊行為特征，對入侵檢測參數進行修正，并設計入侵檢測參數修正算法DPMA。實驗發現，當攻擊行為有多個異常行為的時候，單純使用DPMA算法無法使入侵檢測系統達到穩定的狀態。這里設計基于回退機制的入侵檢測參數修正算法DPMA-DB，實驗證明，在入侵檢測系統中使用 TSMA-BG算法和DPMA-DB算法可以對發生變化的攻擊行為進行有效的檢測。

[1] ZHANG Y,LEE W.Intrusion detection in wireless ad hoc networks[A].Proc MobiCom 2000[C].2000.275-283.

[2] JOHARI R,TSITSIKLIS J N.Routing and peering in a competitive Internet[A].Conference on Decision and Control[C].2004.

[3] HIJAZI A,NASSER N.Using mobile agents for intrusion detection in wireless ad-hoc networks[A].Proc of Second IFIP International Conference on Wireless and Optical Communications Networks(WOCN 2005)[C].2005.362-366.

[4] HASSWA A,ZULKERNINE M,HASSANEIN H.Routeguard: an intrusion detection and response system for mobile ad-hoc networks[A].Proc of IEEE International Conference on Wireless and Mobile Computing,Networking and Communications(WiMob’2005)vol 3[C].2005.336-343.

[5] JIANHUA S,FAN H,YAJUN G.A distributed monitoring mechanism for mobile ad-hoc networks[A].Proc of the 8th International Symposium on Parallel Architectures,Algorithms and Networks(ISPAN'05)[C].2005.236-240.

[6] KETAN N,AMITABH M.A novel intrusion detection approach for wireless ad hoc networks[A].Wireless Communications and Networking Conference[C].2004.831-836.

[7] HUBAUX P,GROSS T,LE Y,et al.Towards self-organizing mobile ad-hoc networks: the Terminodes project[J].IEEE Communication Magazine,2001,39(1): 118-124.

[8] MISHRA A,NADKARNI K,PATCHA A.Intrusion detection in wireless ad hoc networks[A].Proc of IEEE Wireless Communications[C].2004.48-60.

[9] 施錫銓.博弈論[M].上海:上海財經大學出版社,2000.SHI Y Q.Game Theory[M].Shanghai: Shanghai University of Finance and Economics Press,2000.

[10] The network simulator ns-2[EB/OL].http://www.isi.edu/nsnam/ns/.2009.