基于博弈策略的動態(tài)網(wǎng)絡病毒傳播模型和控制

王俊嶺,羅智榮,郭翠芳,劉 娟

(江西理工大學信息工程學院,江西 贛州341000)

1 引言

隨著信息技術(shù)的迅速發(fā)展,計算機網(wǎng)絡已深入到社會生產(chǎn)、生活的方方面面,基于網(wǎng)絡的應用程序也越來越多。計算機連接到網(wǎng)絡中越頻繁,病毒入侵的可能性就越大,計算機病毒也以種類更多、隱蔽性更強、更加智能化和傳播途徑多元化的方式不斷進化。計算機病毒的破壞性不容小覷,它們不僅給人類帶來巨大的經(jīng)濟損失,甚至威脅到社會的安全穩(wěn)定。計算機病毒傳播能力強、數(shù)量多且危害大,儼然成為了當今信息社會的重要威脅之一,如何控制計算機病毒的傳播已成為一項重要課題[1]。

由于網(wǎng)絡結(jié)構(gòu)決定了節(jié)點之間的連通性,因此網(wǎng)絡結(jié)構(gòu)在促進或抑制病毒擴散方面起著重要作用。Ren等[2]建立了一種基于殺傷信號的計算機病毒傳播模型(SEIR-KS),從理論上分析了該模型的全部動力學模型,獲得一個流行閾值,并通過應用Routh-Hurwitz準則和Lyapunov泛函方法,證明無病平衡和病毒平衡在局部和全局的漸進穩(wěn)定。Yang等[3]研究了在可移動存儲介質(zhì)中網(wǎng)絡拓撲對計算機病毒傳播的影響,文中提出了一種新穎的基于網(wǎng)絡的計算機病毒傳播模型,并得出較小的最大節(jié)點度或較大的冪律指數(shù)都有利于遏制病毒的傳播。蔡秀梅[4]致力于分析計算機病毒傳播的內(nèi)在特性,分別考慮計算機網(wǎng)絡中的內(nèi)部和外部因素對病毒傳播的影響,從不同角度建立兩種能反映計算機病毒傳播規(guī)律的動力學模型,并通過理論推導和數(shù)值仿真對模型進行分析。

Peng等[5]在SIS模型中提出,只有當相應的參數(shù)化鄰域(PAM)的光譜半徑小于1時,該流行病會消失,并基于此結(jié)果,評估免疫策略的效率。Ahn和Hassibi等[6]研究了離散時間和連續(xù)時間的SIS模型在復雜網(wǎng)絡上的傳播動態(tài),同時考慮了多個模型的無病平衡狀態(tài)(DFE)和非疾病自由平衡(NDFE),并確定了NDFE的存在性,唯一性和穩(wěn)定性條件。Fall等[7]在連續(xù)時間的SIS模型上,對確定性分區(qū)流行病學模型的整體穩(wěn)定性結(jié)果進行了調(diào)查,并對無病平衡(DFE)和非疾病自由平衡(NDFE)導出了充分的全局漸進穩(wěn)定性條件。Reciado等[8]針對連續(xù)時間的SIS模型,提出了凸框架,來滿足不同級別疫苗接種資源的最優(yōu)分配,并將其應用于真實的在線社交網(wǎng)絡。

上述研究都在靜態(tài)結(jié)構(gòu)基礎(chǔ)上研究病毒傳播,但是無法捕獲病毒在網(wǎng)絡中的動態(tài)特性,因此有必要研究隨時間變化的網(wǎng)絡中的病毒動態(tài)。Prakash等人[9]將離散時間的SIS模型擴展為具有時變結(jié)構(gòu)的模型,通過非線性動力學系統(tǒng)(NLDS)對其進行近似求解,在一定條件下得出時變圖的流行閾值,并通過展示有效的啟發(fā)式方法來展示閾值有效性。Bokharaie等人[10]考慮了非均質(zhì)情況下的SIS模型,并且使用矩陣族的聯(lián)合光譜半徑的概念,提供了病毒徹底消除的條件。但現(xiàn)有動態(tài)結(jié)構(gòu)模型研究中均未考慮計算機病毒的隔離與傳統(tǒng)病毒隔離的重要差異。

Zhang[15]等人主要研究了最優(yōu)動態(tài)對策和網(wǎng)絡拓撲結(jié)構(gòu)對病毒擴散和最佳動態(tài)對策的綜合影響,提出了一種新型的異構(gòu)傳播模型及最優(yōu)控制問題。祝清意[16]為了研究脈沖控制對病毒傳播的影響,在前人模型的基礎(chǔ)上提出了一個帶脈沖控制的時滯SIR模型,求得了該模型的無毒周期解,給出了無毒周期解的全局吸引性條件和該系統(tǒng)的一致持久性條件,對于確立合理的計算機殺毒軟件更新時間具有重要意義。楊櫓星[17]研究表明可以根據(jù)節(jié)點的個性化特點,最合算的分配補丁,在病毒控制策略方面以更小的代價,盡量減小網(wǎng)絡病毒所造成的損失。Wan等[13]研究了通過利用拓撲結(jié)構(gòu)在網(wǎng)絡中分配有限的控制資源,并使用特征值敏感度思想以及采用拉格朗日乘子的約束優(yōu)化方法,最大程度的抑制病毒的傳播。Enns等[14]研究了在網(wǎng)絡圖結(jié)構(gòu)中刪除相關(guān)聯(lián)系,并對移動連接的數(shù)量加以限制,從而使節(jié)點感染病毒的數(shù)量最小化。這種方法取得了較好的結(jié)果,有效的抑制了病毒的傳播。

本文主要研究在無標度動態(tài)網(wǎng)絡中,根據(jù)病毒的特殊屬性以及影響計算機病毒傳播的關(guān)鍵因素,結(jié)合博弈論從宏觀層面建立刻畫病毒傳播行為的動力系統(tǒng)模型,分析病毒的傳播規(guī)律,制定有效的策略抑制病毒傳播。

2 基于動態(tài)網(wǎng)絡的病毒模型

2.1 傳統(tǒng)SEIR病毒模型

傳統(tǒng)的SEIR模型在SIR模型的基礎(chǔ)上增加了具有潛伏狀態(tài)的倉室,該模型包括易感者(S)、潛伏者(E)、感染者(I)、恢復者(R)。潛伏者是指計算機已經(jīng)被侵入了病毒代碼,一開始處于潛伏狀態(tài),并沒有表現(xiàn)出病毒特征,也不具有傳播性,并不會對其它節(jié)點造成破壞,但一旦爆發(fā)將產(chǎn)生巨大破壞。傳統(tǒng)SEIR模型的數(shù)學描述如下

(1)

式(1)中,單位時間內(nèi)易感者接觸感染者后以概率轉(zhuǎn)化為潛伏者,易感者轉(zhuǎn)化為潛伏者的數(shù)量為。處于潛伏期的病毒爆發(fā)后以概率轉(zhuǎn)化為感染者,潛伏者轉(zhuǎn)化為感染者的數(shù)量為。當采用某種方式清除了潛伏者中的病毒后以概率轉(zhuǎn)化為易感者,潛伏者轉(zhuǎn)化為易感者的數(shù)量為。感染者采取某種措施清除病毒并獲得永久免疫后以概率轉(zhuǎn)化為恢復者,感染者轉(zhuǎn)化為恢復者的數(shù)量為。本模型不考慮外部因素對于計算機病毒傳播的影響。SEIR模型變化如圖1所示。

圖1 SEIR模型

2.2 動態(tài)網(wǎng)絡SEIR模型建立

本文研究了處于發(fā)展階段的網(wǎng)絡系統(tǒng)中,計算機的數(shù)量隨時間呈動態(tài)變化。采用計算機動力學倉室建模的方法,在傳統(tǒng)模型的基礎(chǔ)上建立了SEIR計算機病毒傳播模型,研究計算機病毒傳播的過程。

SEIR系統(tǒng)中各個節(jié)點與自身狀態(tài)、鄰居節(jié)點、網(wǎng)絡環(huán)境有一定的聯(lián)系。結(jié)合動態(tài)網(wǎng)絡的特點,加入動態(tài)變化的接入移除概率。單位時間內(nèi),進入系統(tǒng)的任何計算機都是易感節(jié)點,進入系統(tǒng)的速率設為A;系統(tǒng)中,各個節(jié)點因計算機損壞、用戶下線等原因移除網(wǎng)絡的速率為d,感染狀態(tài)的計算機移出系統(tǒng)速率b,因此,感染狀態(tài)計算機移出網(wǎng)絡的速率為b+d;由于安裝殺毒軟件等原因,易感者以速率轉(zhuǎn)化為具有免疫能力的恢復者,潛伏者和感染者轉(zhuǎn)化為移出者的概率分別為和;計算機病毒觸發(fā)后,潛伏者以概率轉(zhuǎn)化為感染者。

模型中,S(t)表示t時刻,系統(tǒng)中易感染狀態(tài)的計算機數(shù)量;E(t)表示t時刻,系統(tǒng)中潛伏狀態(tài)的計算機數(shù)量;I(t)表示t時刻,系統(tǒng)中感染狀態(tài)的計算機數(shù)量;R(t)表示t時刻,系統(tǒng)中恢復狀態(tài)的計算機數(shù)量;N(t)表示t時刻,系統(tǒng)中所有狀態(tài)計算機數(shù)量的總和。用公式描述為

S(t)+E(t)+I(t)+R(t)=N(t)

(2)

其中,模型用微分方程描述如下

(3)

因為R(t)=N(t)-S(t)-E(t)-I(t),式(3)可以簡化為如下微分方程:

(4)

其中,系統(tǒng)(3)的方程組的初始條件為S(0)≥0,E(0)≥0,I(0)≥0,R(0)≥0,則系統(tǒng)的可行域為Ω={(S,E,I):0≤S,E,I≤A/d,S+E+I≤A/d}。

2.3 病毒模型分析

SEIR模型中具有n個節(jié)點,即有n臺計算機處于互聯(lián)狀態(tài)。假設病毒在計算機網(wǎng)絡中傳播,其中任意一臺計算機的感染率i的變化速率如下

(5)

(6)

其中,B=diag(βi,…,βn),符號diag(·,…,·)為創(chuàng)建一個矩陣,其中所有參數(shù)都位于對角線上。A是網(wǎng)絡圖結(jié)構(gòu)的鄰接矩陣,p(t)=diag(p1(t),…,pn(t)),D=diag(δ1,…,δn)。將式(6)中的模型的時變擴展,即

(7)

其中,A(t)是時間函數(shù)。

2.4 病毒模型的無病平衡狀態(tài)

定理1:設?iβi=β,BA(t)-D的最大特征值始終小于0,即supt≥0λ1(BA(t)-D)<0,且A(t)在t上是分段連續(xù)且有界的,則無病平衡總在全局范圍內(nèi)呈指數(shù)穩(wěn)定。

≤pT(BA(t)-D)p

≤λ1(BA(t)-D)‖p‖2

≤(supt≥0λ1(BA(t)-D))‖p‖2≤0

(8)

由于每個pi(t)是一個概率,構(gòu)造(p(t)BA(t))ij≥0,?i,j,因此第一個不等式成立。第二個不等式由Rayleigh-Ritz定理成立,因為當?iβi=β時,BA(t)-D是對稱陣。第三個不等式根據(jù)最大值來定義。因此,由于系統(tǒng)在t中是分段連續(xù)的,而局部Lipschitz條件在?tp(t),p≥0中是連續(xù)的,所以由文獻[11]中的定理2,該系統(tǒng)快速收斂到原點。

定理2:若BA(t)-D的最大特征值始終小于0,即supt≥0λ1(BA(t)-D)<0,且A(t)是連續(xù)可微并且有界的,則無病平衡呈全局漸進穩(wěn)定。

證明:當(p(t)BA(t))ij≥0?i,j,通過構(gòu)造:

(9)

3 病毒傳播模型的模擬

3.1 病毒模型分析

對于仿真,節(jié)點的位置和速度都是隨機的初始條件。初始感染率p(0)的設置通過隨機選擇媒介的一個子集并完全感染它們實現(xiàn),即設置pi(0)=1,?i∈I,其余節(jié)點是完全健康狀態(tài),即pj(0)=0,?j?I.鄰接矩陣A(t)根據(jù)節(jié)點相對位置構(gòu)成,半徑為r。節(jié)點被限制在一個固定的區(qū)域,并遵循不同的速度更新。

在本節(jié)中,建立一個具有100個節(jié)點的網(wǎng)絡系統(tǒng),每個節(jié)點與網(wǎng)絡圖中的任意若干節(jié)點相連。在系統(tǒng)中隨機選擇4個節(jié)點,使其感染病毒,并且網(wǎng)絡圖中每個節(jié)點都具有一定的治愈率和感染率。在一定的時間步數(shù)內(nèi),系統(tǒng)中的節(jié)點最終都被治愈。參見圖2。

圖2 動態(tài)網(wǎng)絡節(jié)點變化圖

圖2截取了網(wǎng)絡系統(tǒng)中節(jié)點被感染和治愈的過程中的四個階段,(a)為初始階段,(b)(c)為中間階段,(d)為最終階段。分別展示了四個階段中易感節(jié)點和感染節(jié)點的情況。

圖3給出了網(wǎng)絡系統(tǒng)中易感者和感染者隨時間變化的數(shù)量曲線圖,其中(a)(b)(c)(d)分別對應圖3中網(wǎng)絡結(jié)構(gòu)圖。粗線曲線代表易感節(jié)點,細線曲線代表感染節(jié)點。從細線曲線看可以看出,在系統(tǒng)4個節(jié)點被感染并以一定的感染率感染附近節(jié)點的情況下,初始階段被感染節(jié)點呈上升趨勢,易感節(jié)點成下降趨勢,但在一定的治愈率的條件下,最終感染節(jié)點都被治愈,系統(tǒng)最終進入穩(wěn)定狀態(tài)。

圖3 系統(tǒng)中易感與感染節(jié)點變化曲線

3.2 恒定漂移理論

通過考慮不同的動力學模型可以得出定理1的若干推論。對于仿真,鄰接矩陣A(t)取決于節(jié)點的位置,即時間函數(shù)。使用Horn等的定義,對于某個半徑r,可以通過以下方式設置aij(t)

(10)

其中,x(t)∈Rd。

其中φ是常數(shù)向量,求解這個微分方程并將其帶入(10),矩陣A(t)變?yōu)?/p>

(11)

若這些節(jié)點具有恒定的漂移,則它們最終將浮動的足夠遠。假設系統(tǒng)中的節(jié)點具有非零的治愈率,那么,最終系統(tǒng)中的病毒將被徹底清除。

推論1:給定固定的T,如果supt≥0λ1(BA(t)-D)<0,?t>T(B=βI)則無病平衡呈全局指數(shù)漸進穩(wěn)定狀態(tài)。

該系統(tǒng)的線性離散時間公式為

pk+1=(I-D+BAK)pk

(12)

命題1:考慮式(12)中的模型。如果Ak是獨立且均勻分布的隨機變量,并且supkE[ln(σ1(I-D+BAk))]<0,則無病平衡點可確定為全局漸進穩(wěn)定狀態(tài)。

證明:由于supkE[ln(σ1(I-D+BAk))]<0并且Ai為i.i.d,根據(jù)強大數(shù)定律,存在c<0,使得

(13)

(14)

因此對于任意p0,

(15)

4 基于博弈策略的SIQR病毒隔離控制

針對網(wǎng)絡中的計算機病毒控制,目前無論是技術(shù)領(lǐng)域還是模型領(lǐng)域,對于一些新型病毒的檢測與防御都存在欠缺。大多數(shù)的網(wǎng)絡中的計算機病毒控制技術(shù),都是以治愈為主,存在嚴重的滯后性。而現(xiàn)在的網(wǎng)絡隔離防止方法對網(wǎng)絡流量造成了嚴重的影響,例如針對不變的網(wǎng)絡地址、維護特別指定的子網(wǎng),都存在很多問題。本文在不隔離全部節(jié)點的基礎(chǔ)上,建立模型倉室,利用博弈策略對計算機中的節(jié)點進行單獨隔離,建立了一種基于博弈策略的SIQR病毒隔離控制模型。這個模型可以有效的解決現(xiàn)有的隔離方法存在的問題。

隔離技術(shù)[13,14]是指對于節(jié)點密集的系統(tǒng),將節(jié)點分成不同的組,在空間上將它們限制在單獨的區(qū)域內(nèi)。由于計算機網(wǎng)絡具有拓撲結(jié)構(gòu),而網(wǎng)絡結(jié)構(gòu)中的計算機病毒傳播也與這種結(jié)構(gòu)密切相關(guān)。同時,網(wǎng)絡結(jié)構(gòu)中的計算機病毒的傳播會對網(wǎng)絡資源的最佳利用產(chǎn)生影響,因此,通過控制病毒的傳播來最大化網(wǎng)絡資源的利用,是本節(jié)研究內(nèi)容的關(guān)鍵。通過建立基于SIQR的病毒隔離模型,將系統(tǒng)建立為五個倉室,將不同的狀態(tài)的節(jié)點隔離在不同的倉室內(nèi),從而達到控制病毒傳播,治愈感染節(jié)點,讓系統(tǒng)處于平衡穩(wěn)定狀態(tài)的目的。

4.1 病毒控制模型

本節(jié)基于SIQR模型,建立了基于博弈策略的病毒控制模型。在SIQR病毒模型中,易感節(jié)點的感染概率為βi,恢復率為γ。節(jié)點可實施隔離(Q)或者保持正常狀態(tài)(N)?；诓┺睦碚搧碚f,隔離節(jié)點可視為合作者,正常狀態(tài)節(jié)點可視為叛逃者,不同狀態(tài)下有不同的感染率βi。假設隔離節(jié)點的感染概率比正常狀態(tài)節(jié)點的感染概率低,即βQ<βN。本節(jié)將SIQR模型擴展為五部分SQ,SN,IQ,IN,R。

本節(jié)病毒控制模型允許交叉交互,并采用感知支付(π)的博弈論概念,將其未來的策略采用基于當前策略的感知風險。合作者預計遭受感知的成本為Ω,這代表所造成的損失,同時降低了感染率,這會給合作者帶來衡定收益,即

πQ=-Ω

(16)

同時,叛逃者由其感染概率乘以可感知的疾病成本參數(shù)δ而具有可感知的風險,即

πN=-δβNI

(17)

按照演化的博弈動力學,給定主體i,j策略的概率與它們的收益πi有關(guān),由Epperlein規(guī)則

(18)

在每個時間間隔(S或I)內(nèi)使用任何類型的合作策略(Q)和叛逃策略(N),并將其乘以策略i或j之間的策略轉(zhuǎn)換概率Θ(πi,πj)。這等效于使用均值逼近的演化博弈動力學的主方程(對于每個隔室),對于策略轉(zhuǎn)化率,定義為

Φs=SQ(SN+IN)Θ(πQ,πN)-SN(SQ+IQ)Θ(πN,πQ)

(19)

ΦI=IQ(SN+IN)Θ(πQ,πN)-IN(SQ+IQ)Θ(πN,πQ)

(20)

其中,φs是SQ節(jié)點轉(zhuǎn)換為SN的速率(對于φI則相反)。從感染動力學來說,假設βa,βN>βa>βQ。其中,βN是叛逃者相互作用的感染率,βQ是合作者相互作用的感染率,合作者與叛逃者之間通過感染率βa相互作用。本節(jié)設置βa=a(βN+βQ)/2,即βQ和βN的平均值,該平均值由外部控制參數(shù)1>a>0加權(quán)。假設所有節(jié)點的恢復率相同,則SIQR模型的動力學方程如下

(21)

(22)

(23)

(24)

(25)

其中,τ是與流行病的時間尺度相關(guān)的耦合參數(shù),用于控制節(jié)點轉(zhuǎn)變策略的速度。實驗中,采用策略時間尺度τ=1。如圖4所示,Sd為SQ倉室中,處于易感狀態(tài)的合作節(jié)點的數(shù)量變化曲線;Sc為SN倉室中,處于易感狀態(tài)的叛逃節(jié)點的數(shù)量變化曲線;id為IQ倉室中,處于感染狀態(tài)的合作節(jié)點的數(shù)量變化曲線;ic為IN倉室中,處于感染狀態(tài)的叛逃節(jié)點的數(shù)量變化曲線。系統(tǒng)正設置總共節(jié)點數(shù)為2000,潛伏期設為40,初始感染者設為10,每個倉室可容納的隔離數(shù)為400。

圖4 倉室SQ,SN,IQ,IN,R中數(shù)量隨時間變化情況。

從圖中可以看出,隨著時間的變化,在一定的治愈率的條件下,病毒倉室內(nèi)感染節(jié)點的密度隨時間的增加而減小,網(wǎng)絡結(jié)構(gòu)中的治愈節(jié)點最終都被收斂到R倉室中,說明計算機網(wǎng)絡中的病毒得到了有效的控制,系統(tǒng)趨于平衡穩(wěn)定狀態(tài)。

圖5中展示了SIQR模型中,在不區(qū)分合作節(jié)點與叛逃節(jié)點的情況下,感染節(jié)點、易感染節(jié)點和治愈節(jié)點隨時間的數(shù)量變化曲線。從圖中可以看出,隨著時間的變化,網(wǎng)絡結(jié)構(gòu)中感染節(jié)點在一定治愈率的條件下,被逐漸治愈,系統(tǒng)最終呈現(xiàn)無病平衡的穩(wěn)定狀態(tài)。

圖5 SEIR模型中各倉室節(jié)點數(shù)量隨時間變化

5 總結(jié)

在本文的病毒仿真中,模擬了病毒在人群中傳播的仿真模型。系統(tǒng)中每個節(jié)點分配大小為1的運動范圍參數(shù)。在初始時間內(nèi)隨機感染若干個節(jié)點,節(jié)點在一定范圍內(nèi)運動,當感染節(jié)點或潛伏期節(jié)點與易感節(jié)點距離小到一定的范圍后,易感節(jié)點被感染。易感節(jié)點在經(jīng)過發(fā)病期后被隔離,隔離后系統(tǒng)最終呈現(xiàn)無感染節(jié)點的穩(wěn)定狀態(tài),病毒得到了有效的控制。

在基于博弈策略的SEIR病毒隔離控制模型中,將節(jié)點分成不同的組,并在空間上將它們限制在單獨的區(qū)域內(nèi)。由于計算機網(wǎng)絡中的病毒傳播與網(wǎng)絡拓撲結(jié)構(gòu)密切相關(guān),通過有限的資源隔離來最大程度的控制病毒傳播是關(guān)鍵。實驗中,策略時間尺度τ=1時,病毒倉室內(nèi)隨時間的增加而減小,計算機網(wǎng)絡中的病毒得到了有效的控制,系統(tǒng)趨于穩(wěn)定狀態(tài)。

本文在SEIR病毒模型的基礎(chǔ)上,根據(jù)病毒爆發(fā)時通常采取的隔離措施的實際情況,加入了基于博弈策略的隔離因素,建立了動態(tài)計算機病毒網(wǎng)絡模型。通過進行穩(wěn)定性分析、給出無病平衡條件、仿真,分析了模型中各影響因素在計算機網(wǎng)絡病毒傳播過程中所起到的控制作用,并根據(jù)實驗結(jié)果提出了有效措施,對防控病毒傳播可以起到重大的指導作用。