基于微分博弈的無線傳感器網絡惡意程序傳播模型*

周海平,沈士根,馮 晟,黃龍軍,彭 華

(紹興文理學院計算機科學與工程系,紹興 312000)

無線傳感器網絡WSNs(Wireless Sensor Networks)是由大量具有無線通信和感知能力的傳感器節(jié)點組成的分布式通信系統。由于WSNs集感知、計算、通信等功能于一體,且價格便宜、部署方便,目前已經在農業(yè)、軍事、工業(yè)制造等眾多領域中得到了應用[1-4]。然而,由于WSNs中的傳感器節(jié)點采用無線方式通信,且攜帶的電池能量有限,很容易受到惡意攻擊[5-7],常見的攻擊方式有信道干擾[8]、拒絕式服務DoS(Denial of Service)攻擊[9]、身份欺騙[10]、惡意程序傳播[11]等多種形式。相比其他攻擊方式,惡意程序傳播是一種影響范圍更大、破壞力更強的攻擊方式,因為傳感器節(jié)點一旦被惡意程序感染,又會向其他節(jié)點傳播惡意程序,導致整個網絡迅速癱瘓[12-14]。

至今為止,人們已經對WSNs的入侵檢測問題[15-16]和計算機網絡中的病毒傳播問題[17-18]做了大量研究,并取得了豐碩的成果,然而,對WSNs中惡意程序傳播問題的研究目前仍處于初級階段。與本文相關的研究成果包括:王小明等人利用元胞自動機方法對移動無線傳感器網絡中的惡意數據包傳播行為進行模擬[19],揭示了不確定環(huán)境下惡意數據包傳播的時空特征。文獻[20]將傳統的傳染病傳播理論應用于WSNs中的惡意程序傳播過程,作者將惡意程序和入侵檢測系統IDS(Intrusion Detection System)當做兩種相互對抗的智能體,建立了二者之間的微分博弈模型,通過對博弈模型的分析和求解,得到了二者之間的均衡策略,該策略可以在抑制惡意程序的傳播的同時降低檢測代價。曹玉林等人將傳染病模型應用于WSNs的病毒傳播研究[21],他們將易感節(jié)點的免疫比例和感染節(jié)點的恢復比例做為最優(yōu)控制變量,實現了最小成本開銷下最大程度遏制病毒傳播的目標。文獻[22]對WSNs中的移動代理被攻擊時病毒的傳播行為進行了研究,發(fā)現在移動代理被攻擊的情況下病毒更容易擴散。文獻[23]提出了一個WSNs的蠕蟲病毒傳播模型,作者研究了通信半徑和節(jié)點分布密度對病毒傳播效果的影響。

盡管人們已經分別對WSNs中的攻防博弈模型以及惡意程序傳播模型做過大量研究,但是目前這兩方面的工作大多是獨立開展的,而實際上,這兩個領域的研究問題是緊密聯系的。一方面,攻防雙方所采取的博弈策略會影響惡意程序的傳播結果。因為當惡意節(jié)點對合法節(jié)點發(fā)起攻擊時,合法節(jié)點通常會采取一定的防御措施,這會影響惡意節(jié)點的攻擊成功率,從而影響惡意程序的傳播結果。另一方面,傳播結果也會反過來改變攻防雙方的博弈策略,這是因為博弈雙方會根據網絡中感染節(jié)點的比例來調整自己的策略。文獻[24]用博弈論的方法分析了攻防雙方的博弈策略,并依據博弈策略確定惡意程序的傳播概率,從而建立了WSNs的惡意程序傳播模型。然而,該文建立的博弈模型假定攻防雙方都知道對方的節(jié)點類型,且攻防雙方不會根據傳播結果動態(tài)更新自己的策略,這顯然與真實情況存在差異。實際情況中,惡意節(jié)點會偽裝成合法節(jié)點,因此攻防雙方不會知道對方的節(jié)點類型,此外,在惡意程序的傳播過程中,兩種節(jié)點的比例會發(fā)生變化,這會促使攻防雙方及時調整自己的策略,因此,需要用微分博弈的理論來描述動態(tài)變化的博弈策略?；谝陨戏治?本文從攻防過程出發(fā),建立了基于不完全信息的微分博弈模型,并將其與惡意程序傳播模型耦合起來,從而探討博弈策略對惡意程序傳播結果的影響,并進一步揭示博弈參數與傳播結果之間的關系,使人們有望通過控制博弈參數來抑制惡意程序的傳播。

本文的研究框架如下:首先,建立WSNs中惡意節(jié)點與合法節(jié)點之間的攻防博弈模型,并對博弈策略進行分析與求解。其次,基于攻防雙方的博弈策略建立WSNs的惡意程序傳播模型,通過求解傳播模型得到系統的實時感染比例與博弈參數之間的關系。再次,用數值模擬方法及元胞自動機模型對WSNs中的惡意程序傳播過程進行模擬及仿真。最后,對數值模擬結果和元胞自動機仿真結果進行分析、比較及討論。

1 WSNs中的不完全信息攻防博弈模型

在WSNs中,合法節(jié)點為了防御惡意節(jié)點的攻擊,會啟動入侵檢測系統IDS(Intrusion Detection System)對收到的信息進行檢測,但檢測過程需要消耗一定的能量,由于無線傳感器節(jié)點攜帶的電池能量十分有限,若每次收到信息時都進行檢測,則很快會因能量耗盡而無法工作?？紤]到其大多數情況下收到的都是正常信息,合法節(jié)點只需以一定的概率隨機抽查一部分信息進行檢測。同時,對惡意節(jié)點來說,若其頻繁地發(fā)起攻擊,則很容易被合法節(jié)點發(fā)現,為了掩飾自己的身份,惡意節(jié)點會經常發(fā)送正常信息(不攻擊)。由此可見,惡意節(jié)點和合法節(jié)點在攻防博弈過程中會根據其所處的局勢采取對自己最有利的策略。在博弈過程中信息發(fā)送方和信息接收方互不知道對方的身份,但是知道對方為合法節(jié)點及惡意節(jié)點的概率,因為在現實環(huán)境中,IDS會將每個時刻的檢測情況上報給管理中心,然后管理中心會以廣播的形式實時發(fā)布毒情報告(報告網絡的感染節(jié)點比例),基于以上特點,本文采用不完全信息博弈模型對雙方的攻防策略進行分析。

定義1WSNs中惡意節(jié)點與合法節(jié)點之間的不完全信息博弈模型可以表示為一個五元組Ξ=〈N,{Tj},p,{Sj},{uj}〉,其中:

①N為博弈參與者集合,對于本文來說,博弈在兩個參與者之間進行,其中參與者1為信息發(fā)送者,參與者2為信息接收者,因此,N={信息發(fā)送者,信息接收者}。

②Tj為參與者j所屬的類型空間,在WSNs中,傳感器節(jié)點含有惡意節(jié)點和合法節(jié)點兩種類型,因此,Tj={惡意節(jié)點,合法節(jié)點},j∈N。

③p為博弈參與者在類型空間上的概率分布,本文指惡意節(jié)點與合法節(jié)點所占的比例,該參數對所有參與者都是公開的。

④Sj為參與者j可采取的行動集合,該行動集合與參與者類型有關。本文中,當參與者為信息發(fā)送方且為惡意節(jié)點時,有“攻擊”和“不攻擊”兩種行動,記為S發(fā)送者,惡意節(jié)點={攻擊,不攻擊};當參與者為信息接收方且為合法節(jié)點時,有“檢測”和“不檢測”兩種行動,記為S接收者,合法節(jié)點={檢測,不檢測};當參與者為信息發(fā)送方且為合法節(jié)點時,只有“不攻擊”一種行動,記為S發(fā)送者,合法節(jié)點={不攻擊};當參與者為信息接收方且為惡意節(jié)點時,只有“不檢測”一種行動,記為S接收者,惡意節(jié)點={不檢測}。需要特別指出的是,其中的“不攻擊”行動不是指節(jié)點不發(fā)送信息,而是指其發(fā)送的是正常信息。

⑤uj為參與者j在博弈過程中獲得的收益,uj的值由所有博弈參與者的類型及策略組合決定。

表1給出了本文用到的一些符號的定義,表2給出了博弈雙方的收益矩陣。

表1 符號定義

表2 合法節(jié)點與惡意節(jié)點的博弈收益函數表

在博弈模型中,信息發(fā)送方和信息接收方都含有惡意節(jié)點和合法節(jié)點,不論哪種節(jié)點,在發(fā)送信息(惡意程序或正常信息)時都需要消耗代價為eM的能量。合法節(jié)點對收到的信息進行檢測需要消耗代價為eD的能量,當惡意節(jié)點向合法節(jié)點發(fā)起攻擊,合法節(jié)點又正好進行檢測時,合法節(jié)點會因成功檢測出惡意程序而獲得價值為a的收益,惡意節(jié)點則會因暴露身份而被修復,從而造成代價為a的損失。當惡意節(jié)點發(fā)起攻擊,而合法節(jié)點不進行檢測時,惡意節(jié)點會因成功傳播惡意程序獲得價值為b的收益,而合法節(jié)點則會因感染惡意程序造成代價為b的損失。另外,為了使博弈有意義,模型須滿足a≥eD及b≥eM這兩個條件。

另外值得指出的是,信息在WSNs的傳遞過程中可能需要經過多跳才能到達目的節(jié)點,但中間節(jié)點并不會參與博弈過程,因為中間節(jié)點為了節(jié)約能量一般只參與對數據的轉發(fā),而不會對轉發(fā)的數據進行檢測,數據轉發(fā)之后會立即被中間節(jié)點刪除,因此惡意程序也不會對中間節(jié)點造成影響,所以博弈只在信息的發(fā)起節(jié)點和目的節(jié)點之間進行。

由表2可知,作為信息發(fā)送方的合法節(jié)點和信息接收方的惡意節(jié)點都只有一種行動,不需要對它們的策略進行分析,因此本文只需要對信息發(fā)送方的惡意節(jié)點和信息接收方的合法節(jié)點的策略進行分析。合法節(jié)點在對收到的信息做出行動時,既要考慮對方的節(jié)點類型,也要考慮對方會采取哪種策略,若對方是惡意節(jié)點且發(fā)起攻擊,則合法節(jié)點就應該進行檢測,反之,就不應該檢測;同理,若惡意節(jié)點面對的是合法節(jié)點,當對方開啟檢測,就不應該進行攻擊,反之,就應該發(fā)起攻擊。由此可見,惡意節(jié)點和合法節(jié)點之間的攻防博弈模型不存在純策略納什均衡解,下面從混合均衡策略的角度分析博弈雙方的攻防行為。

定理1WSNs中惡意節(jié)點與合法節(jié)點之間的不完全信息博弈模型存在混合納什均衡策略。

證明假設WSNs中合法節(jié)點的比例為s,惡意節(jié)點的比例為i,且兩種節(jié)點發(fā)送信息的頻率相同。另外,假設惡意節(jié)點以概率x進行攻擊(傳播惡意程序),以概率1-x不進行攻擊(傳播正常信息),合法節(jié)點以概率y進行檢測,以概率1-y不進行檢測,則根據收益矩陣,作為防御方的合法節(jié)點的期望收益Eus為:

EuS=ixy(a-eD)+i(1-x)y(-eD)+ix(1-y)(-b)+i(1-x)(1-y)·0+sy(-eD)+s(1-y)·0

(1)

作為攻擊方的惡意節(jié)點的期望收益EuI為:

EuI=sxy(-a-eM)+s(1-x)y(-eM)+sx(1-y)(b-eM)+s(1-x)(1-y)(-eM)+ix(-eM)+i(1-x)(-eM)

(2)

ix(a-eD)+i(1-x)(-eD)-ix(-b)+s(-eD)=0

(3)

將s+i=1代入方程(3),整理得:

(4)

sy(-a-eM)-sy(-eM)+s(1-y)(b-eM)-s(1-y)(-eM)=0

(5)

整理上式得:

(6)

2 微分博弈驅動下的WSNs惡意程序傳播模型

在WSNs中,當惡意節(jié)點向合法節(jié)點傳播惡意程序時,若合法節(jié)點不進行檢測,則會被惡意程序感染,感染后的節(jié)點變?yōu)閻阂夤?jié)點,并能進一步向其他節(jié)點傳播惡意程序。反之,如果合法節(jié)點在遭受攻擊時開啟檢測,則能阻止惡意程序的入侵并能清除惡意節(jié)點中的惡意程序,從而使惡意節(jié)點恢復為合法節(jié)點。假設WSNs中總共有N個節(jié)點,其中惡意節(jié)點個數為NI,占總節(jié)點數的比例為i,合法節(jié)點個數為NS,占總節(jié)點數的比例為s。每個惡意節(jié)點會在單位時間內隨機選擇一個其他節(jié)點發(fā)送信息,其中發(fā)送惡意程序的概率為x,發(fā)送正常信息的概率為1-x,合法節(jié)點會以概率y對收到的信息進行檢測。根據上一節(jié)的分析,惡意節(jié)點與合法節(jié)點作為理性的智能體,會采用混合納什均衡策略作為各自的攻防策略,即x=x*,y=y*,因此,單位時間內一個惡意節(jié)點成功感染一個合法節(jié)點的概率為x*(1-y*)s,而一個惡意節(jié)點被修復為合法節(jié)點的概率為x*y*s。于是單位時間內整個網絡新增的惡意節(jié)點數為x*(1-y*)sNI,新增的合法節(jié)點數為x*y*sNI。WSNs中兩種節(jié)點隨時間的演化過程可以用微分方程組(7)表示:

(7)

方程組(7)兩邊同時除以N得:

(8)

于是有:

(9)

(10)

整理得:

(11)

令t0=0,并假設初始時刻的感染比例為i0,對方程(11)兩邊進行積分得:

(12)

即

(13)

整理得:

(14)

由式(14)可知,網絡中惡意節(jié)點的感染比例與博弈模型中的收益參數有關,博弈參數決定了系統隨時間的演化結果。

3 數值模擬與仿真

3.1 攻防策略與收益之間的關系數值模擬

圖1 博弈雙方策略的變化對合法節(jié)點期望收益的影響

圖2 博弈雙方策略的變化對惡意節(jié)點期望收益的影響

3.2 惡意程序傳播數值模擬

微分方程組(8)描述了WSNs惡意程序傳播過程中網絡節(jié)點狀態(tài)隨時間的演化行為,式(14)給出了該系統的解析解,對式(14)進行數值模擬,可得到網絡中感染節(jié)點比例隨時間的變化趨勢,模擬結果如圖3至圖5所示,每張圖中的四條曲線分別刻畫了eD取不同值時系統的演化過程,從中可以看出博弈參數對傳播結果的影響。

圖3顯示,當a>b時,隨著時間的推移,網絡中的節(jié)點感染比例逐漸達到1,最終所有節(jié)點都處于感染狀態(tài)。此外,當eD增大時能加速惡意程序的傳播,即合法節(jié)點的檢測能耗越大,惡意程序的傳播速度越快。解釋如下:①當a>b時,x*(1-y*)si>x*y*si,即單位時間內新感染的節(jié)點多于恢復正常狀態(tài)的節(jié)點,因此網絡中的感染節(jié)點比例會不斷增加,直至所有節(jié)點都被感染。②當檢測能耗eD增大時,由混合納什均衡策略可知,合法節(jié)點保持檢測概率不變,而惡意節(jié)點提高了攻擊概率,從而使惡意程序的傳播速度變快。

圖3 a>b時感染節(jié)點比例演化趨勢(a=3.0,b=2.0)

圖4顯示,當a=b時,網絡中感染節(jié)點的比例保持初始值不變。解釋:當a=b時,x*(1-y*)si=x*y*si,即單位時間內新感染的節(jié)點數等于恢復正常狀態(tài)的節(jié)點數,因此網絡中的感染節(jié)點比例會保持不變。

圖4 a=b時感染節(jié)點比例演化趨勢(a=2.0,b=2.0)

圖5顯示,當a1-y*成立,即合法節(jié)點的檢測概率大于不檢測概率,此時惡意節(jié)點攻擊時被發(fā)現且被修復的概率大于不被發(fā)現的概率,當eD增大時,惡意節(jié)點發(fā)起攻擊的概率增大,因此其修復速度也變快了。

圖5 a

圖6 惡意節(jié)點的攻擊策略演化趨勢(eD=0.5)

3.3 惡意程序傳播元胞自動機仿真

前面的理論傳播模型基于一個假設:WSNs中任意兩個節(jié)點之間可以直接通信。然而,在真實情況中,傳感器節(jié)點的發(fā)射功率一般與通信距離的平方成正比,為了節(jié)約能量,每個節(jié)點只能與其附近的節(jié)點進行通信。由于理論模型無法處理這種情況,本文接下來用元胞自動機方法對WSNs中的惡意程序傳播過程進行研究,一方面可以對理論傳播模型的結論進行驗證,另一方面可以考查通信半徑及節(jié)點的移動行為對傳播速度的影響。

3.3.1 仿真算法

步驟1生成一個如圖7所示的規(guī)格為100×100的網格,隨機選擇比例為pw的格子布設傳感器節(jié)點。

步驟2每個傳感器節(jié)點與距離自己半徑不超過r的節(jié)點產生連邊(組網),由此生成傳感器網絡。

步驟3在初始時刻t0=0,隨機選取比例為i0的節(jié)點設置為惡意節(jié)點。

步驟4每個惡意節(jié)點在自己的鄰居節(jié)點(可以與其直接通信的節(jié)點)中隨機選擇一個節(jié)點發(fā)送信息,其中發(fā)送惡意信息的概率為x*,發(fā)送正常信息的概率為1-x*。

步驟5若惡意節(jié)點選中的節(jié)點也是惡意節(jié)點,則信息會被直接丟棄。反之,若惡意節(jié)點選中的是合法節(jié)點,則合法節(jié)點會以概率y*對收到的信息進行檢測,以概率1-y*不對信息進行檢測。當合法節(jié)點接收的是惡意程序信息且正好沒有啟動檢測時則會被感染,感染后的節(jié)點就變成惡意節(jié)點,并能繼續(xù)向其他節(jié)點傳播惡意程序;當惡意節(jié)點向合法節(jié)點發(fā)送惡意程序,而合法節(jié)點又正好對其進行檢測時,惡意節(jié)點就會被識別,被識別的惡意節(jié)點會被修復,從而又轉化為合法節(jié)點。

步驟6若t小于預設的模擬步數,則t的值增加1,并轉入步驟4繼續(xù)執(zhí)行,否則,結束運行。

圖7 無線傳感器節(jié)點分布圖(灰色為正常節(jié)點, 黑色為惡意節(jié)點,pw=0.1,i0=0.05)

3.3.2 仿真結果

設定參數pw=0.1,執(zhí)行上述模擬步驟,考查不同博弈參數下WSNs惡意程序的傳播過程,模擬結果如圖8～圖13所示。

圖8～圖10分別對應的是a>b、a=b及ab時,仿真過程惡意程序的擴散速度要比理論模型慢;②a

圖8 a>b時感染節(jié)點比例演化趨勢 (a=3.0,b=2.0,r=5.0)

圖9 a=b時感染節(jié)點比例演化趨勢 (a=2.0,b=2.0,r=5.0)

圖10 a

圖11 惡意節(jié)點的攻擊策略演化趨勢 (eD=0.5,r=5.0)

由于WSNs中惡意程序的傳播過程與通信半徑有關,因此,我們進一步研究了傳感器節(jié)點的通信半徑對惡意程序傳播速度的影響,在模擬過程中通過修改通信半徑的值,得到了不同通信半徑下惡意程序的傳播曲線,從圖12可以看出,在其他參數固定的情況下,惡意程序的傳播速度隨著通信半徑的增加而增大。

在某些實際情況中,有些WSNs中的節(jié)點能夠不斷移動,這會導致網絡結構不斷變化,基于此,我們進一步對節(jié)點移動場景下的惡意傳播過程進行仿真,仿真時只需在步驟5結束之后讓每個節(jié)點隨機選擇一個方向移動一格,仿真結果如圖13所示。從圖中可以看出,節(jié)點移動時惡意程序的傳播速度要高于靜態(tài)網絡。

圖12 通信半徑對惡意程序傳播速度的影響 (eD=2.0,a=3.0,b=2.0)

圖13 節(jié)點游動對惡意程序傳播速度的影響 (a=3.0,b=2.0,r=4.0,eD=0.5)

4 討論

4.1 博弈均衡策略的分析

4.2 理論結果與仿真結果的差異分析

盡管本文的理論模型和元胞自動機仿真所得的研究結論整體上是一致的,但兩者之間仍然存在一些差異,例如:在a>b時,理論模型中惡意程序的傳播速度要大于元胞自動機仿真的傳播速度,這一點可以分別從圖3與圖8的比較中反映出來。導致這種差異的主要原因如下:①理論模型假設網絡中任意兩個節(jié)點都可以直接通信,而在元胞自動機模型中,每個節(jié)點只能與距離它不超過r的節(jié)點通信,傳播范圍的限制降低了惡意程序的傳播速度。②在元胞自動機模型中,由于惡意節(jié)點只能攻擊其附近的節(jié)點,隨著時間的推移,就會導致大量惡意節(jié)點聚集成簇,這種聚集效應使得大量惡意節(jié)點無法有效選擇合法節(jié)點進行攻擊,從而降低了惡意程序的傳播效率。值得一提的是,當網絡中的節(jié)點能夠隨機移動時能降低成簇效應,從而可以提高惡意程序的傳播速度,圖13對節(jié)點移動和靜止時的傳播速度進行了比較,比較結果證實這一點。

4.3 研究結果的應用

基于本文的研究結果,可以制定相關的措施來減緩和抑制WSNs中惡意程序的傳播,具體措施可以如下:①加大對合法節(jié)點感染惡意程序的懲罰(增大b的值),使得b>a,促使其積極應對惡意節(jié)點的攻擊,提高檢測命中率。②當無法改變a>b的關系時,可以通過優(yōu)化入侵檢測算法來降低合法節(jié)點的檢測能耗(減小eD的值),從而降低惡意程序的傳播速度。③適當減小傳感器節(jié)點的通信半徑,這一方面可以降低惡意程序的傳播速度,另一方面也可以節(jié)約傳感器節(jié)點的能耗,延長其使用壽命。

5 結束語

本文從博弈論的角度對WSNs中的惡意程序傳播問題進行了研究,得到了以下結論:①惡意節(jié)點的攻擊策略是一個動態(tài)策略,其值與網絡中節(jié)點的感染比例有關,會隨時間動態(tài)變化。②網絡中惡意程序的最終傳播結果由博弈參數決定,通過設計合適的博弈機制可以抑制WSNs中惡意程序的傳播。③惡意程序的傳播速度與通信半徑及節(jié)點的移動行為有關,通信半徑的增大及節(jié)點的移動都能加快惡意程序的傳播速度。

本文建立的惡意程序傳播模型暫時只考慮了節(jié)點的兩種狀態(tài),在實際場景中,節(jié)點可能還會存在潛伏狀態(tài)、免疫狀態(tài)、死亡狀態(tài)等狀態(tài),甚至不同節(jié)點的攻擊或防御能力會存在差異,這種含多種狀態(tài)的復雜異質網絡中的惡意程序傳播問題是我們未來研究的方向。