石月樓 楊旦杰 馮宇 李永強(qiáng)

(浙江工業(yè)大學(xué)信息工程學(xué)院 杭州 310023)

近年來(lái),隨著計(jì)算機(jī)網(wǎng)絡(luò)和信息技術(shù)的不斷發(fā)展,“黑客攻擊”已成為威脅互聯(lián)網(wǎng)安全的主要因素之一,如何有效地防御惡意入侵、保證網(wǎng)絡(luò)安全受到了廣泛的研究[1-3]。

入侵檢測(cè)系統(tǒng)(intrusion detection system,IDS)是一種動(dòng)態(tài)檢測(cè)網(wǎng)絡(luò)的安全防御機(jī)制,可以通過(guò)運(yùn)行入侵檢測(cè)算法來(lái)識(shí)別網(wǎng)絡(luò)中的攻擊,有效彌補(bǔ)安全防護(hù)技術(shù)中的不足[4]。常用的入侵檢測(cè)算法有異常檢測(cè)算法[5]、誤用檢測(cè)算法[6]和人工智能算法[7]。然而單一算法無(wú)法捕獲所有的攻擊,且由于能量的限制,單個(gè)入侵檢測(cè)系統(tǒng)無(wú)法同時(shí)運(yùn)行所有的算法,因此大量的研究工作投入到了入侵檢測(cè)系統(tǒng)的檢測(cè)庫(kù)配置問(wèn)題上。其中,博弈論[8-9]是分析該問(wèn)題的有效工具。文獻(xiàn)[10]將入侵檢測(cè)系統(tǒng)與攻擊者的交互過(guò)程建模為一個(gè)兩人非零和隨機(jī)博弈,通過(guò)求解效用最優(yōu)化方程得到攻防雙方的最優(yōu)策略。文獻(xiàn)[11]也用相同的博弈框架研究了類(lèi)似的問(wèn)題,并通過(guò)強(qiáng)化學(xué)習(xí)算法求得攻擊者和入侵檢測(cè)系統(tǒng)的最優(yōu)策略。文獻(xiàn)[12]通過(guò)兩人零和隨機(jī)博弈框架研究了入侵檢測(cè)系統(tǒng)檢測(cè)庫(kù)配置的問(wèn)題,提出一種基于強(qiáng)化學(xué)習(xí)的算法來(lái)得到最優(yōu)檢測(cè)庫(kù)配置策略。在文獻(xiàn)[13]中,作者使用零和貝葉斯信號(hào)博弈研究了入侵檢測(cè)系統(tǒng)與未知類(lèi)型的攻擊者的交互過(guò)程,并證明博弈的納什均衡策略就是一組最優(yōu)攻防策略。為了可以運(yùn)行更多的算法提升檢測(cè)性能,越來(lái)越多的研究提出在多個(gè)入侵檢測(cè)系統(tǒng)中引入?yún)f(xié)作機(jī)制。文獻(xiàn)[14]驗(yàn)證了協(xié)作式入侵檢測(cè)系統(tǒng)可以顯著提升整體的檢測(cè)性能,并提出分布式激勵(lì)分配方法來(lái)解決檢測(cè)庫(kù)分配的矛盾。文獻(xiàn)[15]也研究了類(lèi)似的問(wèn)題,并且還考慮了傳輸延遲和資源有限對(duì)檢測(cè)庫(kù)分配的影響。文獻(xiàn)[16]在文獻(xiàn)[15]的基礎(chǔ)上還考慮了攻擊者之間的協(xié)作性,提出了一種基于演化博弈的入侵檢測(cè)系統(tǒng)檢測(cè)資源分配模型。求解博弈均衡的方法有Sarsa 算法[17]、Q-learning 算法[18]、Monte Carlo 算法[19]等,這些都屬于強(qiáng)化學(xué)習(xí)范疇[20]。強(qiáng)化學(xué)習(xí)的應(yīng)用場(chǎng)景非常廣泛,尤其適用于環(huán)境動(dòng)力學(xué)無(wú)法建模的場(chǎng)景,智能體通過(guò)與環(huán)境的交互,將得到的獎(jiǎng)勵(lì)值作為反饋信號(hào)進(jìn)行訓(xùn)練[21],且泛化性好,不需要進(jìn)行大量調(diào)參。但傳統(tǒng)的強(qiáng)化學(xué)習(xí)算法只能處理離散狀態(tài),而本文中的信念狀態(tài)是連續(xù)的,因此本文提出后向遞歸算法來(lái)求解博弈問(wèn)題。

與現(xiàn)有的大多數(shù)研究完全信息下單個(gè)入侵檢測(cè)系統(tǒng)配置不同,本文考慮了一個(gè)非完全信息下協(xié)作式入侵檢測(cè)系統(tǒng)檢測(cè)庫(kù)配置的問(wèn)題。入侵檢測(cè)系統(tǒng)可以監(jiān)測(cè)到系統(tǒng)的狀態(tài),而攻擊者無(wú)法獲知,只能通過(guò)信念估計(jì),因此通過(guò)非完全信息博弈模擬各入侵檢測(cè)系統(tǒng)和對(duì)應(yīng)攻擊者的交互過(guò)程符合該情況。并且由于多個(gè)入侵檢測(cè)系統(tǒng)共用一套檢測(cè)庫(kù),因此在得到最優(yōu)檢測(cè)庫(kù)配置方案后還要考慮同一檢測(cè)庫(kù)被重復(fù)加載的矛盾。本文主要工作總結(jié)如下:首先,為了解決信息不對(duì)稱(chēng)的情況,攻擊者通過(guò)假想一個(gè)入侵檢測(cè)系統(tǒng)建立基于信念的隨機(jī)博弈框架來(lái)制定策略,通過(guò)后向遞歸算法求解,并證明了有限時(shí)間非完全信息博弈中穩(wěn)態(tài)納什均衡(stationary Nash equilibrium,SNE)的存在;然后,由于入侵檢測(cè)系統(tǒng)可以觀察到攻擊者的策略,因此最優(yōu)檢測(cè)庫(kù)配置方案可以通過(guò)求解一個(gè)混合Markov 決策過(guò)程得到;最后,提出了一種基于策略共享的集中式分配方法解決檢測(cè)庫(kù)被重復(fù)加載的矛盾。

1 問(wèn)題定義

如圖1 所示,入侵檢測(cè)網(wǎng)絡(luò)(intrusion detection network,IDN)由N個(gè)相互連接的入侵檢測(cè)系統(tǒng)IDSi(i∈{1,2,…,N}) 組成,對(duì)應(yīng)的攻擊者用γi(i∈{1,2,…,N}) 表示。每個(gè)子系統(tǒng)的狀態(tài)集合都是S={S1,…,Sq,…,SK},其中,Sq表示某種特定運(yùn)行狀態(tài);例如,S1表示運(yùn)行正常,S2表示正遭受惡意攻擊,S3表示運(yùn)行異常。每個(gè)攻擊者的純動(dòng)作集合都是Aγ={1,…,h,…,H},攻擊者γi發(fā)動(dòng)h類(lèi)型的攻擊的能耗為cγi(h)＞0。

圖1 協(xié)作式入侵檢測(cè)系統(tǒng)模型圖

協(xié)作式入侵檢測(cè)系統(tǒng)共用的檢測(cè)庫(kù)集合為L(zhǎng)={l1,…,lm,…,lH},檢測(cè)庫(kù)lm成功檢測(cè)到h類(lèi)型的攻擊的概率是plm,h。當(dāng)加載的檢測(cè)庫(kù)與攻擊類(lèi)型相匹配時(shí),成功檢測(cè)到的概率會(huì)大幅提升。入侵檢測(cè)系統(tǒng)可以通過(guò)加載多個(gè)檢測(cè)庫(kù)來(lái)優(yōu)化檢測(cè)性能,但是相應(yīng)的檢測(cè)能耗也會(huì)變高,因此要考慮檢測(cè)準(zhǔn)確率和能耗之間的一個(gè)平衡。每個(gè)入侵檢測(cè)系統(tǒng)每次可以同時(shí)加載n(n∈{1,2,…,H}) 個(gè)檢測(cè)庫(kù),則檢測(cè)庫(kù)L的可能組合類(lèi)型共有M=種,表示從H個(gè)檢測(cè)庫(kù)中挑出n個(gè)檢測(cè)庫(kù)的所有可能組合數(shù),用Fj(j∈{1,2,…,M}) 表示,因此,各入侵檢測(cè)系統(tǒng)的純動(dòng)作(檢測(cè)庫(kù)配置方案)集合都可以用AIDS={F1,F2,…,FM} 表示。令入侵檢測(cè)系統(tǒng)IDSi加載檢測(cè)庫(kù)lm的能耗為＞0,則入侵檢測(cè)系統(tǒng)IDSi選擇配置方案aIDSi∈AIDS的總能耗是

接下來(lái),定義入侵檢測(cè)系統(tǒng)IDSi選擇動(dòng)作aIDSi成功檢測(cè)到攻擊aγi的概率為

當(dāng)子系統(tǒng)i狀態(tài)為Sk時(shí),如果攻擊aγi沒(méi)有被成功檢測(cè)到,其損失為D(Sk,aγi),則部署在該子系統(tǒng)上的入侵檢測(cè)系統(tǒng)IDSi的損失為

其中,δIDSi＞0 表示與IDSi檢測(cè)能耗相關(guān)的權(quán)重參數(shù),δγi＞0 表示與攻擊能耗相關(guān)的權(quán)重參數(shù)。最后,定義每個(gè)子系統(tǒng)狀態(tài)轉(zhuǎn)移矩陣為

其中,TSe,Sf(aIDSi,aγi)(e,f∈{1,2,…,K}) 表示子系統(tǒng)i在聯(lián)合純動(dòng)作{aIDSi,aγi} 下從當(dāng)前狀態(tài)Se轉(zhuǎn)移到下一狀態(tài)Sf的概率。

由于協(xié)作式入侵檢測(cè)系統(tǒng)共用一套檢測(cè)庫(kù),因此,任一檢測(cè)庫(kù)在每一時(shí)刻只能被分配給一個(gè)入侵檢測(cè)系統(tǒng),即各入侵檢測(cè)系統(tǒng)的檢測(cè)庫(kù)配置方案{aIDS1,aIDS2,…,aIDSN} 需滿(mǎn)足:

2 非完全信息入侵檢測(cè)系統(tǒng)檢測(cè)庫(kù)配置

本文聚焦非完全信息下協(xié)作式入侵檢測(cè)系統(tǒng)的檢測(cè)庫(kù)配置,接下來(lái)將分3 步研究這個(gè)問(wèn)題。首先,構(gòu)建一個(gè)基于信念的隨機(jī)博弈來(lái)研究攻擊者的策略制定問(wèn)題;然后,通過(guò)混合Markov 決策過(guò)程得到入侵檢測(cè)系統(tǒng)的檢測(cè)庫(kù)配置策略;最后,基于策略共享的檢測(cè)庫(kù)分配方法來(lái)解決加載檢測(cè)庫(kù)的矛盾。

2.1 攻擊策略

每個(gè)入侵檢測(cè)系統(tǒng)和對(duì)應(yīng)攻擊者的交互過(guò)程都可以描述為一個(gè)兩人零和隨機(jī)博弈,動(dòng)作集、回報(bào)函數(shù)、子系統(tǒng)的狀態(tài)集合以及狀態(tài)轉(zhuǎn)移概率都是相同的,因此在以下建立的基于信念的隨機(jī)博弈框架中,只考慮其中一個(gè)入侵檢測(cè)系統(tǒng)和其對(duì)應(yīng)攻擊者之間的交互,其余N-1 對(duì)的交互過(guò)程也是完全一樣的。攻擊者γi無(wú)法獲得子系統(tǒng)的真實(shí)狀態(tài),通過(guò)信念估計(jì),并假想一個(gè)同樣使用信念的入侵檢測(cè)系統(tǒng)來(lái)制定策略,建立一個(gè)由五元組＜I,A,B,T,R＞組成的基于信念的隨機(jī)博弈框架。

(2)動(dòng)作:令A(yù)=Δ(AIDS) ×Δ(Aγ) 表示純動(dòng)作集合AIDS×Aγ上的聯(lián)合概率分布集合。

(3)信念:令B=Δ(S) 表示信念集合,Δ(S)表示在狀態(tài)集S上的概率分布。記Bt(k) 表示t時(shí)刻子系統(tǒng)i狀態(tài)為Sk(k∈{1,2,…,K}) 的概率。在t時(shí)刻末,攻擊者γi根據(jù)觀察到的動(dòng)作用下式更新t+1 時(shí)刻的信念:

(4)信念轉(zhuǎn)移概率:令t時(shí)刻信念為b∈B,聯(lián)合概率動(dòng)作為,則t+1 時(shí)刻信念轉(zhuǎn)移到b′∈B的概率可以表示為T(mén)(b′|b,β)=Pr(Bt+1=b′ |Bt=b,At=β)。根據(jù)信念更新式(6),當(dāng)時(shí),有T(b′|b,β)=;否則,T(b′|b,β)=0。于是可以得到:

(5)收益:令rγi(Bt=b,At=β) 表示t時(shí)刻攻擊者γi的收益,是根據(jù)信念b對(duì)所有狀態(tài)下收益的加權(quán)和,具體表達(dá)式為

本文研究的是穩(wěn)態(tài)策略,記為從信念空間B到動(dòng)作空間A的映射,即πN:B→A。在給定信念b∈B,穩(wěn)態(tài)策略是定義在純動(dòng)作集合AIDS×Aγ上的一個(gè)概率分布。因此,加權(quán)入侵檢測(cè)系統(tǒng)和對(duì)應(yīng)攻擊者γi的累計(jì)收益函數(shù)分別為

其中,b0是初始信念。下面給出有限時(shí)間非完全信息博弈問(wèn)題的定義。

問(wèn)題1令GN:=(I,A,B,T,R) 表示一個(gè)有限時(shí)間非完全信息博弈,求解該博弈問(wèn)題就等價(jià)于求解穩(wěn)態(tài)納什均衡策略滿(mǎn)足:

2.2 入侵檢測(cè)系統(tǒng)的檢測(cè)庫(kù)配置方案

由于真正的入侵檢測(cè)系統(tǒng)在信息方面具有優(yōu)勢(shì),因此在博弈的每個(gè)階段,攻擊者的策略制定過(guò)程對(duì)入侵檢測(cè)系統(tǒng)而言是公開(kāi)的,這使得入侵檢測(cè)系統(tǒng)能夠根據(jù)攻擊者的策略來(lái)制定自己的策略。將該過(guò)程建立為一個(gè)混合Markov 決策過(guò)程,并用一個(gè)四元組來(lái)描述。

(2)狀態(tài):令U=S×B為混合狀態(tài)空間,其中,S是子系統(tǒng)的狀態(tài)空間,B是在基于信念的隨機(jī)博弈中定義的信念空間。

(3)混合狀態(tài)轉(zhuǎn)移概率:令t時(shí)刻混合狀態(tài)為u∈U,聯(lián)合概率動(dòng)作為則t+1時(shí)刻混合狀態(tài)轉(zhuǎn)移到u′∈U的概率為

(4)收益:入侵檢測(cè)系統(tǒng)IDSi的收益函數(shù)為

其中,ω(s,aIDSi,aγi) 已在式(2)定義。

入侵檢測(cè)系統(tǒng)IDSi的穩(wěn)態(tài)策略用表示,是混合狀態(tài)空間U到動(dòng)作空間Δ(AIDS) 的映射,即:U→Δ(AIDS)。入侵檢測(cè)系統(tǒng)IDSi的累計(jì)收益函數(shù)為

其中,u0是初始混合狀態(tài),是攻擊者γi的穩(wěn)態(tài)策略。在獲知攻擊者γi的穩(wěn)態(tài)納什均衡策略之后,入侵檢測(cè)系統(tǒng)IDSi的目標(biāo)是最大化累計(jì)收益函數(shù),因此,入侵檢測(cè)系統(tǒng)的最優(yōu)配置策略可以通過(guò)求解以下最優(yōu)問(wèn)題來(lái)得到:

2.3 檢測(cè)庫(kù)分配

在檢測(cè)庫(kù)分配過(guò)程中,會(huì)有一個(gè)入侵檢測(cè)系統(tǒng)充當(dāng)中心管理者調(diào)度所有入侵檢測(cè)系統(tǒng)加載檢測(cè)庫(kù)。在得到各入侵檢測(cè)系統(tǒng)的最優(yōu)配置策略以及對(duì)應(yīng)攻擊者的穩(wěn)態(tài)納什均衡策略后,將該信息報(bào)告給入侵檢測(cè)網(wǎng)絡(luò)管理者,管理者通過(guò)基于策略共享的檢測(cè)庫(kù)分配方法得到協(xié)作式入侵檢測(cè)系統(tǒng)實(shí)際的檢測(cè)庫(kù)配置方案為{aIDS1,aIDS2,…,aIDSN},該分配方法將在下一節(jié)中詳細(xì)介紹。此時(shí)入侵檢測(cè)系統(tǒng)IDSi的期望收益為

其中,u={s,b} 表示當(dāng)前時(shí)刻子系統(tǒng)i的狀態(tài)以及攻擊者γi的信念,是攻擊者γi的穩(wěn)態(tài)納什均衡策略,ω(s,aIDSi,aγi) 已在式(2)定義。

此外,本文考慮的是入侵檢測(cè)網(wǎng)絡(luò)的收益,即所有入侵檢測(cè)系統(tǒng)的收益之和,入侵檢測(cè)網(wǎng)絡(luò)的收益為

因此,中心管理者求得的檢測(cè)庫(kù)配置方案需滿(mǎn)足:

3 入侵檢測(cè)系統(tǒng)檢測(cè)庫(kù)配置方案計(jì)算

本節(jié)將給出具體求解基于信念的隨機(jī)博弈、混合Markov 決策過(guò)程以及檢測(cè)庫(kù)分配的方法。

3.1 攻擊策略

為了解決有限時(shí)間非完全信息博弈問(wèn)題1,本文提出后向遞歸算法來(lái)構(gòu)建攻擊者γi的最優(yōu)穩(wěn)態(tài)策略。在該算法中,假定加權(quán)入侵檢測(cè)系統(tǒng)已經(jīng)使用穩(wěn)態(tài)納什均衡策略;并且證明該算法的解就是有限時(shí)間非完全信息博弈問(wèn)題GN的穩(wěn)態(tài)納什均衡策略。

令GN中的SNE 策略為具體可以表示為根據(jù)式(10),在穩(wěn)態(tài)納什均衡策略下,攻擊者γi從t時(shí)刻到N時(shí)刻的累計(jì)收益函數(shù)為

下面給出后向遞歸算法的具體步驟。

(1)初始化:對(duì)所有的信念b∈B,令t=N+1時(shí)攻擊者γi的收益函數(shù)為

則t=N時(shí)刻攻擊者γi的最優(yōu)穩(wěn)態(tài)策略為

相應(yīng)地,t=N時(shí)攻擊者γi的收益函數(shù)為

(2)遞歸:對(duì)于任意t=N-1,N-2,…,0;?bt∈B,攻擊者γi的最優(yōu)穩(wěn)態(tài)策略為

則相應(yīng)地,攻擊者γi的收益函數(shù)為

(3)構(gòu)造攻擊者γi的一個(gè)最優(yōu)穩(wěn)態(tài)策略為

在上述的后向遞歸算法中,理論上需要先將一方參與者的穩(wěn)態(tài)納什均衡策略固定下來(lái),再求解另一方參與者的穩(wěn)態(tài)納什均衡策略,但是在實(shí)際的仿真案例中,由于GN是零和博弈,因此在求得收益矩陣以后可以通過(guò)效用等值[22]方法同時(shí)求解出雙方的穩(wěn)態(tài)納什均衡策略。下面的定理1 給出了上述后向遞歸算法與有限時(shí)間非完全信息博弈GN中穩(wěn)態(tài)納什均衡存在的關(guān)系。

定理1由后向遞歸算法構(gòu)造出的解是有限時(shí)間非完全信息博弈GN的一個(gè)穩(wěn)態(tài)納什均衡策略。

證明要證明是有限時(shí)間非完全信息博弈GN的一個(gè)穩(wěn)態(tài)納什均衡策略,根據(jù)問(wèn)題1 中對(duì)穩(wěn)態(tài)納什均衡的定義,即等價(jià)于證明成立。由于在后向遞歸算法中假定加權(quán)入侵檢測(cè)系統(tǒng)使用穩(wěn)態(tài)納什均衡策略顯然是成立的。因此,下面只需要證明成立。

值得注意的是,在定義有限時(shí)間非完全信息博弈的收益函數(shù)時(shí)沒(méi)有用到折扣因子(或者,等價(jià)于折扣因子ρ=1),如果在定義有限時(shí)間非完全信息博弈的收益函數(shù)時(shí)加上折扣因子,定理1 也依然適用于證明該博弈存在一個(gè)穩(wěn)態(tài)納什均衡,詳見(jiàn)下面的推論1。

推論1當(dāng)有限時(shí)間非完全信息博弈GN的收益函數(shù)定義為

其中,0＜ρ＜1 是折扣因子。在這樣的情況下,GN依然存在一個(gè)穩(wěn)態(tài)納什均衡。

證明在定義式(19)中加入折扣因子ρ,后續(xù)證明過(guò)程和定理1 的證明過(guò)程相同。

3.2 檢測(cè)庫(kù)配置方案

在這一小節(jié)給出求解混合Markov 決策過(guò)程的方法。定理2 給出了入侵檢測(cè)系統(tǒng)IDSi的最優(yōu)純動(dòng)作貝爾曼方程。

定理2入侵檢測(cè)系統(tǒng)IDSi的最優(yōu)純動(dòng)作貝爾曼方程為

證明根據(jù)基于信念的隨機(jī)博弈中求得的穩(wěn)態(tài)納什均衡策略∈B,入侵檢測(cè)系統(tǒng)IDSi的累計(jì)收益函數(shù)滿(mǎn)足最優(yōu)貝爾曼方程[23]:

其中,第2 個(gè)等號(hào)成立的條件是因?yàn)闋顟B(tài)s的轉(zhuǎn)移與信念b的轉(zhuǎn)移都是相互獨(dú)立的;第3 個(gè)等號(hào)成立的條件是因?yàn)楣粽擀胕無(wú)法獲知入侵檢測(cè)系統(tǒng)IDSi的策略βIDSi,所以只能根據(jù)加權(quán)入侵檢測(cè)系統(tǒng)的穩(wěn)態(tài)納什均衡策略來(lái)更新信念。因此,式(30)可以改寫(xiě)為

將式(31)中的概率動(dòng)作換成純動(dòng)作,可得入侵檢測(cè)系統(tǒng)IDSi的最優(yōu)純動(dòng)作狀態(tài)值函數(shù)為

其中,a={aIDSi,aγi}。

綜上所述,入侵檢測(cè)系統(tǒng)IDSi的最優(yōu)純動(dòng)作貝爾曼方程式(27)和(28)得證。

通過(guò)最優(yōu)純動(dòng)作貝爾曼方程式(27)和(28),入侵檢測(cè)系統(tǒng)IDSi可以算得任意狀態(tài)下所有聯(lián)合動(dòng)作即狀態(tài)純動(dòng)作值表。又因?yàn)槿肭謾z測(cè)系統(tǒng)在信息方面有優(yōu)勢(shì),可以看到攻擊者的策略制定過(guò)程,即在博弈的每一階段,入侵檢測(cè)系統(tǒng)都能獲得攻擊者的穩(wěn)態(tài)納什均衡策略。因此,入侵檢測(cè)系統(tǒng)IDSi可以通過(guò)算法1求得最優(yōu)檢測(cè)庫(kù)配置方案。

算法1 的步驟4 表示遍歷入侵檢測(cè)系統(tǒng)IDSi的檢測(cè)庫(kù)配置方案AIDS;步驟5 表示入侵檢測(cè)系統(tǒng)IDSi每一個(gè)檢測(cè)庫(kù)配置方案對(duì)應(yīng)的期望收益,表示攻擊者選擇z類(lèi)型的攻擊的概率;步驟7表示選出能使期望收益最大的檢測(cè)庫(kù)配置方案。

由該算法流程可以看出,入侵檢測(cè)系統(tǒng)IDSi的最優(yōu)檢測(cè)庫(kù)配置方案是在獲得防守者γi的穩(wěn)態(tài)納什均衡策略以后,計(jì)算每一種檢測(cè)庫(kù)配置方案對(duì)應(yīng)的期望收益,通過(guò)比較期望收益的大小,選擇最大值對(duì)應(yīng)的配置方案。因此,入侵檢測(cè)系統(tǒng)IDSi的最優(yōu)檢測(cè)庫(kù)配置方案實(shí)質(zhì)上是一個(gè)純策略。

3.3 檢測(cè)庫(kù)分配

由于協(xié)作式入侵檢測(cè)系統(tǒng)共用一套檢測(cè)庫(kù),因此可能會(huì)出現(xiàn)同一時(shí)刻多個(gè)入侵檢測(cè)系統(tǒng)加載同一檢測(cè)庫(kù)的矛盾,本小節(jié)將介紹如何用基于策略共享的集中式分配方法解決該矛盾。

每一時(shí)刻,入侵檢測(cè)系統(tǒng)通過(guò)與攻擊者的交互得到最優(yōu)檢測(cè)庫(kù)配置方案。由算法1 的分析可知,該最優(yōu)檢測(cè)庫(kù)配置方案是純策略,表示為{aIDS1,…,aIDSi,…,aIDSN},其中,aIDSi∈AIDS,i∈{1,2,…,N}。將該最優(yōu)檢測(cè)庫(kù)配置方案報(bào)告給中心管理者,若滿(mǎn)足式(4)和(5),則說(shuō)明各入侵檢測(cè)系統(tǒng)的檢測(cè)庫(kù)配置方案沒(méi)有任何矛盾,即沒(méi)有2 個(gè)或2 個(gè)以上的入侵檢測(cè)系統(tǒng)同時(shí)加載同一個(gè)檢測(cè)庫(kù),則中心管理者按該方案分配檢測(cè)庫(kù)。若不滿(mǎn)足上述條件則說(shuō)明有檢測(cè)庫(kù)被重復(fù)加載,則此時(shí)中心管理者先將沒(méi)有矛盾的檢測(cè)庫(kù)分配掉;然后再通過(guò)一個(gè)優(yōu)化機(jī)制將矛盾的檢測(cè)庫(kù)分配給合適的入侵檢測(cè)系統(tǒng)。該優(yōu)化機(jī)制具體描述如下。

(1)對(duì)任意入侵檢測(cè)系統(tǒng)IDSi(i∈{1,2,…,N}),找出其與剩余所有入侵檢測(cè)系統(tǒng)加載有矛盾的檢測(cè)庫(kù)的集合,表示為uij=aIDSi∩aIDSj(j={1,2,…i-1,i+1,…,N})。

(2)對(duì)?lm∈uij,利用式(18)計(jì)算入侵檢測(cè)系統(tǒng)IDSi加載lm、IDSj不加載lm后入侵檢測(cè)網(wǎng)絡(luò)的期望收益。注意,當(dāng)從入侵檢測(cè)系統(tǒng)IDSj的配置方案中去掉檢測(cè)庫(kù)lm以后,中心管理者會(huì)再?gòu)氖Ｓ嗟臋z測(cè)庫(kù)中挑選滿(mǎn)足以下條件的檢測(cè)庫(kù)分配給IDSj。

再用相同的方法計(jì)算入侵檢測(cè)系統(tǒng)IDSj加載lm、IDSi不加載lm后入侵檢測(cè)網(wǎng)絡(luò)的期望收益

4 仿真分析

如圖2 所示,考慮一個(gè)由2 個(gè)入侵檢測(cè)系統(tǒng)相互連接的入侵檢測(cè)網(wǎng)絡(luò)展開(kāi)有限次博弈,每個(gè)子系統(tǒng)i(i∈{1,2}) 都有3 個(gè)狀態(tài){S1,S2,S3}。攻擊者的純動(dòng)作集合為Aγ={1,2},且不同類(lèi)型的攻擊的能耗分別為cγi(1)=0.8 和cγi(2)=1.2(i∈{1,2})。不同狀態(tài)下各類(lèi)型的攻擊對(duì)子系統(tǒng)i造成的損失如表1 所示。

表1 不同狀態(tài)下攻擊對(duì)系統(tǒng)造成的損失

圖2 二對(duì)二攻防博弈模型圖

協(xié)作式入侵檢測(cè)系統(tǒng)共用的檢測(cè)庫(kù)集合為L(zhǎng)={l1,l2},每個(gè)入侵檢測(cè)系統(tǒng)任意時(shí)刻只能加載一個(gè)檢測(cè)庫(kù),則入侵檢測(cè)系統(tǒng)的純動(dòng)作(檢測(cè)庫(kù)配置方案)集合為AIDS={{l1},{l2}},每個(gè)檢測(cè)庫(kù)被加載的能耗分別為IDSi(l1)=0.6,IDSi(l2)=1.0,i∈{1,2}。各檢測(cè)庫(kù)成功檢測(cè)到攻擊的概率分別為pl1,1=0.80,pl1,2=0.20,pl2,1=0.15,pl2,2=0.90。式(2)中的權(quán)重參數(shù)δIDSi=0.5 和δγi=0.4,i∈{1,2}。狀態(tài)轉(zhuǎn)移矩陣T(aIDSi,aγi) 可以按以下方式計(jì)算得到。假設(shè)當(dāng)前子系統(tǒng)i的狀態(tài)為S2,攻擊者γi發(fā)動(dòng)類(lèi)型為1 的攻擊,對(duì)應(yīng)的IDSi加載檢測(cè)庫(kù){l1},則相關(guān)的狀態(tài)轉(zhuǎn)移概率分別為

用相同的方法可以得到不同狀態(tài)所有聯(lián)合動(dòng)作下的狀態(tài)轉(zhuǎn)移概率。令I(lǐng)DSi在狀態(tài)Sk(k=1,2,3) 下的收益矩陣為ω(k,·,·),則ω(1,·,·)=

通過(guò)后向遞歸算法和算法1 可以求解有限時(shí)間非完全信息博弈的穩(wěn)態(tài)納什均衡策略和最優(yōu)檢測(cè)庫(kù)配置策略。將博弈的長(zhǎng)度設(shè)置為N=3。當(dāng)t=3時(shí),信念可以表示為b3=(b3(1),b3(2),b3(3)),b3(1) +b3(2) +b3(3)=1,且b3(1)＞0,b3(2)＞0,b3(3)＞0。令分別表示博弈第3 階段攻擊者γi和加權(quán)入侵檢測(cè)系統(tǒng)IDSi的穩(wěn)態(tài)納什均衡策略,aIDSi,3表示博弈第3 階段入侵檢測(cè)系統(tǒng)IDSi的最優(yōu)檢測(cè)庫(kù)配置方案。根據(jù)后向遞歸算法,首先對(duì)?b∈B,設(shè)置然后根據(jù)式(21)可以算得為

其中,∈=q1-q2-q3+q4,且qm(m∈{1,…,4})是第3 階段博弈矩陣的元素,其具體表達(dá)式為

當(dāng)η＞0 時(shí),入侵檢測(cè)系統(tǒng)IDSi加載檢測(cè)庫(kù)l1;當(dāng)η＜0 時(shí),入侵檢測(cè)系統(tǒng)IDSi加載檢測(cè)庫(kù)l2;當(dāng)η=0 時(shí),任意加載檢測(cè)庫(kù)l1或者檢測(cè)庫(kù)l2。在得到最優(yōu)檢測(cè)庫(kù)配置方案{aIDS1,aIDS2} 后,如果滿(mǎn)足式(4)和(5),則直接為IDS1和IDS2分配檢測(cè)庫(kù);否則按3.3 節(jié)中的分配方法為IDS1和IDS2分配檢測(cè)庫(kù)。

在博弈的t=2、1、0 階段,信念bt可以用信念更新式(6)得到,真實(shí)狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移矩陣得到,攻擊者的穩(wěn)態(tài)納什均衡策略和入侵檢測(cè)系統(tǒng)的最優(yōu)配置方案可通過(guò)上述相同的步驟算得。

在這個(gè)仿真案例中,給定攻擊者γ1的信念為b3=(0.5,0.3,0.2),子系統(tǒng)1 的真實(shí)狀態(tài)為1;攻擊者γ2的信念為b3=(0.4,0.4,0.2),子系統(tǒng)2 的真實(shí)狀態(tài)為2,按上述步驟,攻擊者γ1從博弈的第3 階段到第0 階段的穩(wěn)態(tài)納什均衡策略分別為

相對(duì)應(yīng)地,入侵檢測(cè)系統(tǒng)IDS1從博弈的第3 階段到第0 階段的最優(yōu)檢測(cè)庫(kù)配置方案為aIDS1,3={l1},aIDS1,2={l2},aIDS1,1={l2} 和aIDS1,0={l2}。

用同樣的方法可以得到攻擊者γ2從第3 階段到第0 階段的穩(wěn)態(tài)納什均衡策略分別為

相對(duì)應(yīng)地,入侵檢測(cè)系統(tǒng)IDS2從博弈的第3 階段到第0 階段的最優(yōu)檢測(cè)庫(kù)配置方案aIDS2,3={l1},aIDS2,2={l1},aIDS2,1={l2} 和aIDS2,0={l2}。

注意到在博弈的第3 階段,入侵檢測(cè)系統(tǒng)IDS1和IDS2都要加載檢測(cè)庫(kù)l1。當(dāng)入侵檢測(cè)系統(tǒng)IDS1加載檢測(cè)庫(kù)l1而IDS2加載檢測(cè)庫(kù)l2,入侵檢測(cè)網(wǎng)絡(luò)的收益;當(dāng)入侵檢測(cè)系統(tǒng)IDS2加載檢測(cè)庫(kù)l1而IDS1加載檢測(cè)庫(kù)l2,入侵檢測(cè)網(wǎng)絡(luò)的收益,因此把檢測(cè)庫(kù)l1分配給入侵檢測(cè)系統(tǒng)IDS1。類(lèi)似地在博弈的第1 階段,入侵檢測(cè)系統(tǒng)IDS1和IDS2都要加載檢測(cè)庫(kù)l2。當(dāng)入侵檢測(cè)系統(tǒng)IDS1加載檢測(cè)庫(kù)l2而IDS2加載檢測(cè)庫(kù)l1,入侵檢測(cè)網(wǎng)絡(luò)的收益r1IDN=0.740;當(dāng)入侵檢測(cè)系統(tǒng)IDS2加載檢測(cè)庫(kù)l2而IDS1加載檢測(cè)庫(kù)l1,入侵檢測(cè)網(wǎng)絡(luò)的收益,由于因此檢測(cè)庫(kù)l2可以分配給入侵檢測(cè)系統(tǒng)IDS1或者IDS2。在博弈的第0 階段,入侵檢測(cè)系統(tǒng)IDS1和IDS2都要加載檢測(cè)庫(kù)l2。當(dāng)入侵檢測(cè)系統(tǒng)IDS1加載檢測(cè)庫(kù)l2而IDS2加載檢測(cè)庫(kù)l1,入侵檢測(cè)網(wǎng)絡(luò)的收益;當(dāng)入侵檢測(cè)系統(tǒng)IDS2加載檢測(cè)庫(kù)l2而IDS1加載檢測(cè)庫(kù)l1,入侵檢測(cè)網(wǎng)絡(luò)的收益=0.800,由于因此檢測(cè)庫(kù)l2被分配給入侵檢測(cè)系統(tǒng)IDS1。

在相同模擬場(chǎng)景下比較了本文提出的基于策略共享的集中式分配方法和文獻(xiàn)[14]提出的分布式激勵(lì)分配方法解決檢測(cè)庫(kù)重復(fù)加載的矛盾后,所有入侵檢測(cè)系統(tǒng)的收益總和。前者為10.360,后者為9.235,由此可以看出,本文提出的分配方法比分布式激勵(lì)分配方法在收益值上提升了12.18%。此外,還研究了2 種分配方法完成分配的時(shí)間,基于策略共享的集中式分配方法運(yùn)行時(shí)長(zhǎng)為2.3 ms,分布式激勵(lì)分配方法運(yùn)行時(shí)長(zhǎng)為1.4 ms,后者的運(yùn)行時(shí)長(zhǎng)相對(duì)減少了39.00%。因此當(dāng)分配次數(shù)變多以及檢測(cè)庫(kù)數(shù)量變多后,分布式激勵(lì)分配方法在運(yùn)行時(shí)間上的優(yōu)勢(shì)會(huì)更明顯。這是由于本文提出的分配方法為了能最優(yōu)化整體入侵檢測(cè)網(wǎng)絡(luò)的檢測(cè)性能,考慮了矛盾檢測(cè)庫(kù)分配的所有情況,因此當(dāng)檢測(cè)庫(kù)的數(shù)量較多時(shí)耗時(shí)會(huì)較為嚴(yán)重。而分布式激勵(lì)分配方法是各檢測(cè)系統(tǒng)選擇能使自己檢測(cè)性能最優(yōu)化的檢測(cè)庫(kù),即通過(guò)一系列的局部最優(yōu)來(lái)近似整體最優(yōu),這種分配方法能降低計(jì)算的復(fù)雜度,但是整個(gè)入侵檢測(cè)系統(tǒng)的性能可能不會(huì)達(dá)到最優(yōu)。

5 結(jié)論

本文給出了有限時(shí)間下非完全信息協(xié)作式入侵檢測(cè)系統(tǒng)的最優(yōu)檢測(cè)庫(kù)配置方法,該方法不僅解決了各入侵檢測(cè)系統(tǒng)應(yīng)對(duì)不同類(lèi)型攻擊時(shí)最優(yōu)檢測(cè)庫(kù)的配置,而且解決了共用一套檢測(cè)庫(kù)引發(fā)的加載庫(kù)的矛盾。攻擊者無(wú)法獲知系統(tǒng)狀態(tài)的設(shè)定也更符合實(shí)際,可以通過(guò)構(gòu)建一個(gè)基于信念的隨機(jī)博弈來(lái)解決,并借助后向遞歸算法證明了博弈中SNE 的存在。真正的入侵檢測(cè)系統(tǒng)利用一個(gè)欺騙機(jī)制獲知攻擊者的策略,并基于該策略算得每種檢測(cè)庫(kù)配置方案下的期望收益,通過(guò)比較期望收益的大小得到最優(yōu)檢測(cè)庫(kù)配置方案。解決多個(gè)入侵檢測(cè)系統(tǒng)加載同一檢測(cè)庫(kù)矛盾的分配方法實(shí)質(zhì)上就是在分配完所有檢測(cè)庫(kù)的約束下最大化入侵檢測(cè)網(wǎng)絡(luò)的收益。仿真案例驗(yàn)證了上述方法的有效性,并給出了各入侵檢測(cè)系統(tǒng)的最優(yōu)檢測(cè)庫(kù)配置方案。

本文只考慮了入侵檢測(cè)系統(tǒng)之間的協(xié)作性,而攻擊者是相互獨(dú)立的,不存在任何合作。未來(lái)工作可以考慮更加智能的協(xié)作式攻擊者,能通過(guò)分享信息來(lái)實(shí)時(shí)更新攻擊策略,以及當(dāng)任意一個(gè)攻擊者攻擊失敗時(shí),其余的攻擊者可以協(xié)助攻擊。