基于博弈論的移動(dòng)Ad hoc網(wǎng)絡(luò)入侵檢測(cè)模型

李奕男 錢志鴻 劉 影 張 旭

(吉林大學(xué)通信工程學(xué)院 長(zhǎng)春 130025)

1 引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的不斷深入發(fā)展，移動(dòng)計(jì)算設(shè)備和移動(dòng)通信設(shè)備的廣泛應(yīng)用，給人們?cè)谛畔①Y源的利用和共享帶來了巨大的便利。移動(dòng)Ad hoc網(wǎng)絡(luò)(MANET)是由一組帶有無線收發(fā)裝置的移動(dòng)終端組成的多跳、臨時(shí)性自治系統(tǒng)，通過傳輸范圍有限的移動(dòng)節(jié)點(diǎn)間的互相協(xié)作和自我組織保持網(wǎng)絡(luò)的互聯(lián)和數(shù)據(jù)傳輸。Ad hoc網(wǎng)絡(luò)具有無中心控制的分布性、動(dòng)態(tài)變化的拓?fù)浣Y(jié)構(gòu)和多跳的路由結(jié)構(gòu)等特性，已經(jīng)廣泛的應(yīng)用于軍事通信、災(zāi)難救助和臨時(shí)應(yīng)急會(huì)議通信等應(yīng)用環(huán)境[1]。

Ad hoc網(wǎng)絡(luò)技術(shù)擁有廣闊的應(yīng)用前景，但是由于它的無線通信信道的完全開放性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變化缺乏穩(wěn)定性，使得Ad hoc網(wǎng)絡(luò)更容易受到從被動(dòng)監(jiān)聽到主動(dòng)扮演、消息重放、篡改報(bào)文和拒絕服務(wù)等各種安全威脅和攻擊[2]，因此移動(dòng)Ad hoc網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)(IDS)就成為網(wǎng)絡(luò)安全方案的第二道防火墻。

移動(dòng)Ad hoc網(wǎng)絡(luò)與現(xiàn)有的固定網(wǎng)絡(luò)相比有很大的差異，因此那些在傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)中已經(jīng)廣泛應(yīng)用的安全機(jī)制不再適用于移動(dòng)Ad hoc網(wǎng)絡(luò)。入侵檢測(cè)系統(tǒng)的主要作用就是對(duì)整體網(wǎng)絡(luò)進(jìn)行全面監(jiān)控，實(shí)時(shí)檢測(cè)是否發(fā)生了入侵事件，并根據(jù)已有的安全策略對(duì)入侵事件進(jìn)行判斷和響應(yīng)。但是現(xiàn)有的入侵檢測(cè)手段還很有限，當(dāng)攻擊者改變攻擊策略時(shí)，入侵檢測(cè)系統(tǒng)反應(yīng)明顯滯后。同時(shí)，入侵檢測(cè)系統(tǒng)本身報(bào)警數(shù)量大、誤報(bào)率高的問題也很突出，使得檢測(cè)結(jié)果并不完全可信。本文將博弈理論引入到移動(dòng)Ad hoc網(wǎng)絡(luò)的入侵檢測(cè)系統(tǒng)中，針對(duì)多攻擊節(jié)點(diǎn)和不同強(qiáng)度的攻擊源，建立一個(gè)非協(xié)作博弈入侵檢測(cè)模型。通過引入博弈論模型，建立攻防雙方博弈模型，本文論證了該博弈存在一個(gè)納什均衡，能夠?qū)崿F(xiàn)網(wǎng)絡(luò)整體安全性的定量分析。仿真實(shí)驗(yàn)表明該模型通過較小的代價(jià)換取整體網(wǎng)絡(luò)的安全運(yùn)行，具有良好的性能指標(biāo)，證明了該方法的正確性和可行性。

針對(duì)攻防雙方不對(duì)稱的網(wǎng)絡(luò)安全問題，Musman和Ding Yong[3,4]等人提出了靜態(tài)映射型入侵響應(yīng)模型。該模型是指按一定的原則對(duì)攻擊進(jìn)行分類，并用人工的方式將每一次報(bào)警映射到一個(gè)預(yù)先定義好的相應(yīng)措施上。靜態(tài)映射型入侵響應(yīng)很大程度上解決了人工響應(yīng)長(zhǎng)、負(fù)擔(dān)大的問題，但是當(dāng)系統(tǒng)狀態(tài)發(fā)生變化，如網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)負(fù)載發(fā)生變化時(shí)，原有的響應(yīng)措施將不再適應(yīng)。在此基礎(chǔ)上，Carver和Ragsdale[5,6]等人在2000年提出了通過考慮IDS自身的誤報(bào)警率和以往響應(yīng)方式的成功率來自動(dòng)調(diào)整響應(yīng)映射。這種動(dòng)態(tài)自適應(yīng)方法部分解決了響應(yīng)措施的適應(yīng)性問題，但是因?yàn)闆]有考慮響應(yīng)的代價(jià)，使得有時(shí)響應(yīng)會(huì)得不償失。2002年Lee和Fan[7]等人提出了基于系統(tǒng)收益的入侵檢測(cè)響應(yīng)模型，在綜合計(jì)算操作代價(jià)、響應(yīng)代價(jià)和損失代價(jià)的基礎(chǔ)上選擇適當(dāng)?shù)膽?yīng)對(duì)策略。這種收益模型未能將不同系統(tǒng)遭受同一攻擊的損失不同區(qū)別開來，收益考慮的不全面。Foo和Wu[8]提出了根據(jù)IGraph圖法的基于系統(tǒng)收益的入侵響應(yīng)和容忍模型，對(duì)系統(tǒng)可能的入侵路徑進(jìn)行描述，然后根據(jù)入侵可能造成的系統(tǒng)損失和響應(yīng)代價(jià)選擇響應(yīng)措施。這種方法非常復(fù)雜不易實(shí)現(xiàn)，實(shí)用性不高。Lye和Wing[9]使用統(tǒng)一和隨機(jī)博弈對(duì)系統(tǒng)中的攻防雙方關(guān)系進(jìn)行了描述和推理，證明了博弈理論對(duì)入侵檢測(cè)和響應(yīng)的適用性。Xu[10]等人通過博弈理論框架來對(duì)他們提出的DDOS防御系統(tǒng)的性能進(jìn)行分析，引導(dǎo)防御系統(tǒng)的調(diào)整。

2 移動(dòng)Ad hoc網(wǎng)絡(luò)入侵檢測(cè)博弈模型

2.1 博弈論與網(wǎng)絡(luò)入侵和響應(yīng)

對(duì)于分布式網(wǎng)絡(luò)的入侵響應(yīng)而言，響應(yīng)者所期望的結(jié)果或者所采取的行動(dòng)，不只取決于其自身的行為(策略)，還應(yīng)取決于入侵者和檢測(cè)系統(tǒng)的行為(策略)，而博弈論正是研究這種策略互相依存的理論。博弈論是研究競(jìng)爭(zhēng)條件決策分析的科學(xué)，它研究的典型問題是若干個(gè)利益沖突者在同一環(huán)境中進(jìn)行決策以求自己的利益得到滿足[11]。在網(wǎng)絡(luò)入侵和響應(yīng)的過程中，入侵者的目的就是對(duì)網(wǎng)絡(luò)發(fā)起進(jìn)攻，非法獲得網(wǎng)絡(luò)信息，影響正常的網(wǎng)絡(luò)服務(wù)；防御響應(yīng)一方就是要通過實(shí)施安全策略保證網(wǎng)絡(luò)的正常服務(wù)。因此，入侵者和響應(yīng)者之間的博弈是利益沖突的博弈，雙方都希望能夠最大化自己的利益，攻防雙方之間強(qiáng)調(diào)個(gè)人的理性。因此，入侵者和響應(yīng)者之間的利益是完全對(duì)立的，網(wǎng)絡(luò)入侵和響應(yīng)的過程是一個(gè)非合作、完全信息、有限次重復(fù)的對(duì)抗性博弈。

2.2 博弈模型

博弈問題有5個(gè)要素：局中人，策略空間，概率分布，信息集，效用函數(shù)。

定義 假設(shè)Ad hoc網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)(n=1,…,N)，則基于博弈的Ad hoc網(wǎng)絡(luò)入侵檢測(cè)模型如下：

局中人：式(1)中{A, D}表示局中人，A表示網(wǎng)絡(luò)攻擊方，即網(wǎng)絡(luò)入侵者；D表示網(wǎng)絡(luò)防御方，即IDS的響應(yīng)的決策者。

策略空間：式(1)中{SA,SD}表示局中人的策略空間，SA表示攻擊方的策略，SD表示防御方的策略。概率分布：式(1)中{PA, PD}表示探測(cè)器的概率分布矩陣，其中

信息集：式(1)中{IA,ID}表示攻擊方和防御方的信息集，信息集的維數(shù)由攻擊方采用的攻擊方式數(shù)決定。

效用函數(shù)：式(1)中{RA,RD}表示博弈模型的效用函數(shù)，代表階段博弈結(jié)束后，攻防雙方可能得到的收益集合。

2.3 模型存在納什均衡的證明

根據(jù)納什定理[12]：在一個(gè)有n個(gè)博弈方的博弈G={S1, S2,…,Sn;u1, u2,…,un}中，如果n是有限的，且Si是有限集(i=1,2,…,n)，則該博弈至少存在一個(gè)納什均衡。即每一個(gè)有限策略博弈都至少有一個(gè)混合策略納什均衡。

本模型攻防雙方的信息集維數(shù)是有限的，因此對(duì)應(yīng)的策略型博弈也是有限的。根據(jù)納什均衡的存在條件，任意有限策略型博弈至少存在一個(gè)策略納什均衡。博弈中局中人都是理性的，攻防雙方只有在達(dá)到納什均衡的策略下，才能使收益最大化，也即局中人的最佳選擇。

3 仿真結(jié)果與分析

為了驗(yàn)證本論文提出模型的準(zhǔn)確性，選用了NS-2[13]軟件對(duì)模型進(jìn)行仿真。實(shí)驗(yàn)中引入了兩種實(shí)驗(yàn)場(chǎng)景：(1)正常的具有入侵檢測(cè)系統(tǒng)的AODV路由協(xié)議；(2)引入了基于博弈論的入侵檢測(cè)的改進(jìn)AODV路由協(xié)議。通過測(cè)量系統(tǒng)的檢測(cè)率、誤檢測(cè)率、路由包開銷和平均延遲4個(gè)主要參數(shù)指標(biāo)來真實(shí)反映模型系統(tǒng)的安全性和穩(wěn)定性。具體實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。實(shí)驗(yàn)結(jié)果如圖1所示。

從圖1(a)和圖1(b)的仿真結(jié)果可以看出，隨著網(wǎng)絡(luò)中惡意節(jié)點(diǎn)數(shù)目的增加，大規(guī)模入侵事件的發(fā)生，IDS會(huì)產(chǎn)生大量警報(bào)，造成警報(bào)泛洪，從而會(huì)占用大量的通信帶寬，影響正常的網(wǎng)絡(luò)通信，網(wǎng)絡(luò)的整體性能呈現(xiàn)下降趨勢(shì)。本文提出的入侵檢測(cè)模型既可以提高準(zhǔn)確率，又能夠緩解網(wǎng)絡(luò)擁塞的狀況。實(shí)驗(yàn)證明其具有很高的檢測(cè)率，達(dá)到90%以上，誤檢率保持在10%以下，證明了方法的有效性。

表1 NS-2參數(shù)設(shè)置

從圖1(c)的仿真結(jié)果可以看出，本模型計(jì)算量少，給系統(tǒng)帶來的路由開銷小，占用帶寬少，節(jié)省了網(wǎng)絡(luò)資源。從圖1(d)中可以發(fā)現(xiàn)本模型計(jì)算時(shí)間短，檢測(cè)效率高，非常適宜移動(dòng)Ad hoc網(wǎng)絡(luò)。

4 結(jié)論

本文提出了一種基于博弈論Ad hoc網(wǎng)絡(luò)入侵檢測(cè)模型，將攻防雙方的網(wǎng)絡(luò)入侵和響應(yīng)的過程抽象成一個(gè)非合作、完全信息、有限次重復(fù)的對(duì)抗性博弈。在雙方的博弈過程中，尋求納什均衡，使局中人進(jìn)行最佳選擇。通過實(shí)例分析和實(shí)驗(yàn)可以看出，該模型能夠使IDS在響應(yīng)后的收益得到保證，并且最優(yōu)解穩(wěn)定可靠。

圖1 采用博弈論的入侵檢測(cè)的仿真結(jié)果

[1] 朱建明, Srinivasan Raghunathan. 基于博弈論的信息安全技術(shù)評(píng)價(jià)模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2009, 32(4): 828-834.Zhu Jian-ming and Srinivasan Raghunathan. Evaluation model of information security technologies based on game theoretic[J]. Chinese Journal of Computers, 2009, 32(4):828-834.

[2] Ryu Y U and Rhee H S. Evaluation of intrusion detection systems under a resource constraint. ACM Transactions on Information and Systems Security, 2008, 11(4): 20.1-20.24.

[3] Musman S and Flesher P. System or security managers’adaptive response tool [C]. DARPA Information Survivability Conference and Exposition 2000, Hilton Head, USA, 2000,Vol.2: 1056-1060.

[4] 丁勇, 虞平, 龔儉. 自動(dòng)入侵響應(yīng)系統(tǒng)的研究[J]. 計(jì)算機(jī)科學(xué)，2003, 30(10): 160-166.Ding Yong, Yu Ping, and Gong Jian. A study of automated intrusion response systems [J]. Computer Science, 2003,30(10): 160-166.

[5] Carver C, Hill J M, and Surdu J R. A methodology for using intelligent agents to provide automated intrusion response[C].The IEEE Systems, Man, and Cybernetics Information Assurance and Security Workshop, West Point, NY, 2000:110-116.

[6] Ragsdale D, Carver C, and Humphries J, et al.. Adaptation techniques for intrusion detection and intrusion response system[C]. The IEEE Int’l Conf on Systems, Man, and Cybernetics at Nashville, Tennessee, 2000: 1398-1406.

[7] Lee W, Fan W, and Miller M, et al.. Toward cost-sensitive modeling for intrusion detection and response [J]. Journal of Computer Security, 2002, 10(1/2): 5-22.

[8] Foo B, Wu Y, and Mao Y, et al.. ADEPTS: adaptive intrusion response using attack graphs in an E-commerce environment[C]. Int’l Conf on Dependable Systems and Networks (DSN’05), Washington, 2005: 139-146.

[9] Lye K and Wing J M. Game strategies in network security[C].The 2002 IEEE Computer Security Foundations Workshop,Copenhagan, Denmark, 2002: 71-86.

[10] Xu J and Lee W. Sustaining availability of Web services under distributed denial of service attacks [J]. IEEE Transactions on Computer, 2003, 52(4): 195-208.

[11] [美]艾里克·拉斯繆森. 王暉等譯. 博弈與信息博弈論概論. 北京: 北京大學(xué)出版社, 2003: 385-417.

[12] 董武世, 孫強(qiáng), 柯宗武, 陳年生. 基于博弈論的Ad hoc網(wǎng)絡(luò)功率控制模型[J]. 武漢理工大學(xué)學(xué)報(bào), 2009, 31(17): 114-122.Dong Wu-shi, Sun Qiang, Ke Zong-wu, and Chen Nian-sheng.Power control model based on game theory in Ad hoc networks[J]. Journal of Wuhan University of Technology,2009, 31(17): 114-122.

[13] Ns2 network simulation[OL]http ://www.isi.edu/nsnam/ns ,2009.