沈明玉, 劉俊龍

(合肥工業(yè)大學計算機與信息學院,安徽合肥 230009)

移動Ad hoc網(wǎng)絡中黑洞問題的研究

沈明玉, 劉俊龍

(合肥工業(yè)大學計算機與信息學院,安徽合肥 230009)

移動Ad hoc網(wǎng)絡在民用設施和國防事業(yè)方面得到廣泛應用,動態(tài)變化的拓撲結構是Ad hoc網(wǎng)絡的一大特征,也正是這種動態(tài)性使得Ad hoc網(wǎng)絡特別容易受到安全方面的攻擊。文章剖析了AODV路由協(xié)議的工作過程,針對協(xié)議中存在的黑洞問題,提出了一種新的解決方案,該方案不僅有效地解決了黑洞問題而且可以消除一些現(xiàn)有解決方案所存在的缺陷。

Ad hoc網(wǎng)絡;路由安全;AODV;黑洞

移動Ad hoc網(wǎng)絡是一種具有高度動態(tài)拓撲結構、節(jié)點可自由移動的自組織網(wǎng)絡[1]。Ad hoc網(wǎng)絡中的每個節(jié)點,既是網(wǎng)絡數(shù)據(jù)終端,又是路由器。作為需轉發(fā)數(shù)據(jù)包的路由器,路由協(xié)議是其最重要的部分。其中,AODV路由協(xié)議是Ad hoc網(wǎng)絡中一種常用的按需路由協(xié)議。它在控制開銷、節(jié)點儲存開銷和算法復雜度等大部分性能指標方面都優(yōu)于其它協(xié)議,被認為是最有實用前景的Ad hoc網(wǎng)絡路由協(xié)議之一[2]。

Ad hoc網(wǎng)絡的路由協(xié)議極易受到攻擊,如果路由協(xié)議一旦遭受到惡意攻擊,整個網(wǎng)絡將無法正常工作,并有可能陷入癱瘓,因此路由的安全是整個網(wǎng)絡安全的重要部分。本文重點分析了AODV協(xié)議的安全隱患,針對協(xié)議中最常見的黑洞問題提出了一種新的解決方案,并通過NS-2進行仿真實驗。實驗結果表明,該解決方案能夠有效地阻止黑洞攻擊,并且可以消除部分現(xiàn)有方案所存在的缺陷。

1 研究背景

1.1 AODV路由協(xié)議

AODV[3]協(xié)議是路由協(xié)議DSR和DSDV的結合,它借用了DSR的路由發(fā)現(xiàn)策略以及DSDV的逐跳路由、序列號和定期廣播機制,是一種按需路由協(xié)議。在AODV路由協(xié)議中,當源節(jié)點想要找到一條到達目的節(jié)點的路由,而在路由表中又沒有有效的路由存在時,它就向所有鄰居節(jié)點廣播一個路由請求分組(RREQ),當中間節(jié)點收到RREQ,就在路由表中建立一條指向源節(jié)點的反向路由,然后再向周圍節(jié)點廣播這個 RREQ,若中間節(jié)點有RREQ所查找的到目的節(jié)點的有效路由,則它向上一跳節(jié)點回發(fā)路由應答消息(RREP),并經(jīng)若干中間節(jié)點向源節(jié)點回發(fā)RREP。如果目的節(jié)點收到RREQ,它就沿著反向路由向源節(jié)點回復路由應答分組(RREP),當RREP到達源節(jié)點,則建立了一條從源節(jié)點到目的節(jié)點的有效路由。如果源節(jié)點收到了多個RREP,它會根據(jù)目標節(jié)點序列號和跳數(shù)來決定是否更新自己的路由表信息。

1.2 AODV路由協(xié)議中的黑洞問題

在最初的AODV協(xié)議的應答機制中,允許中間節(jié)點對路由請求進行回復,即只要該中間節(jié)點有一條到目的節(jié)點的可用路由,它就可以響應RREQ消息。這種機制的目的是減小尋路時延和開銷。但是,惡意節(jié)點利用AODV協(xié)議的廣播機制,捕獲經(jīng)過自己的RREQ消息,并宣稱自己有到達目的節(jié)點的最佳路由(通過偽造跳數(shù)或者偽造目的節(jié)點序列號),從而使源節(jié)點采用此虛假路由。惡意節(jié)點可以輕易攔截所有數(shù)據(jù)包而形成一個吸收數(shù)據(jù)包的“黑洞”。這樣使得惡意節(jié)點從源節(jié)點騙得大量的網(wǎng)絡信息和重要的數(shù)據(jù),而真正的目的節(jié)點接收不到來自源節(jié)點的數(shù)據(jù),這就是所謂的黑洞問題[4]。通過這個途徑惡意節(jié)點可以很容易地引導許多網(wǎng)絡流量到其自身,以非常低的代價使網(wǎng)絡的安全性受到很大的威脅。

1.3 黑洞問題的研究現(xiàn)狀

防范黑洞攻擊的最簡單有效的方法就是禁止中間節(jié)點對RREQ進行回復,而僅允許目的節(jié)點回復[5]。這在一定程度上避免了黑洞問題,提高了AODV協(xié)議的安全性,但也增加了路由建立的延時,當網(wǎng)絡的規(guī)模比較大時,其效率就會受到嚴重影響。此外,當惡意節(jié)點假冒目的節(jié)點向源節(jié)點回復虛假RREP時,源節(jié)點也無法識別這個RREP是來自目的節(jié)點還是惡意節(jié)點的。

文獻[6,7]提出的SAODV和路由協(xié)議安全擴展等解決方案是基于加密算法的安全策略,這些安全策略可以提供較完善的路由安全保障,包括黑洞問題的解決。但密碼體制的引入增加了源節(jié)點和目的節(jié)點的運算量,對節(jié)點的運算能力、能耗等方面有了更高的要求。因此,雖然可以有比較高的安全性,但是由于每個節(jié)點都要進行加密和驗證,因此其對移動終端的計算能力和電源有較高的要求,而且還會增加大量的時延。

文獻[8]提出,當中間節(jié)點應答(設為節(jié)點B)時,必須把它的下一跳節(jié)點(設為節(jié)點C)的信息附加在RREP中發(fā)給源節(jié)點。源節(jié)點根據(jù)該信息從其它路由給C發(fā)驗證包,以查詢C是否真有到目的節(jié)點和到該中間應答節(jié)點的可用路由。若C確實存在到目的節(jié)點和應答節(jié)點的可用路由,則信任該應答節(jié)點并開始發(fā)送數(shù)據(jù)。若C沒有到目的節(jié)點或到應答節(jié)點的路由則忽略該應答,同時向全網(wǎng)發(fā)送警告信息孤立該應答節(jié)點。該方案在一定程度上解決了黑洞問題,但仍存在以下缺陷:①唯一路徑問題。若應答節(jié)點B是正常節(jié)點,但源節(jié)點和目的節(jié)點間僅存在經(jīng)由B的唯一路由,則源節(jié)點由于無法從另外的路由對節(jié)點C進行驗證,從而誤認為B是惡意節(jié)點。②惡意節(jié)點團隊破壞。如果惡意節(jié)點B和C組成團隊進行破壞,則源節(jié)點收到的查詢結果也是虛假的。

2 基于ECC的AODV解決方案

數(shù)字簽名是一種有效的認證手段,與RSA相比,橢圓曲線密碼在同等安全強度下可大大減少計算量,本文分析了以上幾種現(xiàn)有解決方案的缺陷,針對協(xié)議中存在的黑洞問題,提出了一種基于橢圓曲線加密法路由安全協(xié)議。

2.1 橢圓曲線加密法

橢圓曲線加密法(Elliptic Curve Cryptography,簡稱ECC)是當今眾多研究者最關注的公鑰加密技術之一[9],以橢圓曲線理論為基礎,建立基于橢圓曲線的對應密碼體制。設素數(shù)域橢圓曲線方程為:E:y2=(x3+ax+b)mod p,曲線參數(shù)為E:{a,b,G,N,P},G是橢圓曲線E/F(p)的基點,用G=(xG,yG)來表示,N是基點G的階。假定私鑰sk為整數(shù)r,則對應的公鑰為橢圓曲線E上的一個點rG,用(xr,yr)標記。用SSK表示私鑰種子矩陣,由整數(shù)矢量(r ij)組成,P SK表示公鑰種子矩陣,由對應的點rijG=(xij,rij)組成。

由S SK計算用戶A私鑰的步驟為:

(1)假定有h個映射F1,F2,…,Fh,這些映射將A的身份信息(可以是ID等)映射為h個映射值,將h個映射值記為m1,m2,…,mh。

(2)用m1,m2,…,mh作為行號從S SK的h列取出相應的矢量為rm1,rm2,…,rmh,按(3)式計算用戶A的私鑰。

A的公鑰不需要通過證書傳遞,由通信對方D計算得到,步驟為:

(1)D由A的身份信息用相同的映射算法計算出行映射值 m1,m2,…,mh,從公鑰種子矩陣PSK中取出相應的矢量,如((xm11,ym1),(xm22,ym22),…,(xmhh,ymhh))。

(2)按照(4)式計算公鑰,PkA和skA構成一對橢圓曲線密碼公、私鑰對。

2.2 E-AOD V路由安全協(xié)議

本文針對現(xiàn)有安全協(xié)議的缺陷,提出了一種新的基于橢圓曲線加密法路由安全協(xié)議(EAODV)。在方案中,當中間節(jié)點B對源節(jié)點A進行路由應答時,源節(jié)點A需對該中間節(jié)點B進行驗證,測試所應答路由的正確性之后才能建立路由連接。具體過程如下:

(1)當A發(fā)起路由建立時,生成新的隨機數(shù)Fa,計算Ra=FaG,其中G為橢圓曲線基點,加入RREQ中進行路由查找。

(2)如圖1所示,中間節(jié)點B對源節(jié)點A進行RREP回復,同時向目的節(jié)點D發(fā)送一個“中間回復許可請求”(approbate-request),該請求報文為:B→D:Na‖Ra。

(3)源節(jié)點A將該路由存入緩沖區(qū),再根據(jù)中間節(jié)點B提供的路由的跳數(shù)等待一個相應的時間T。

(4)如圖2所示,目的節(jié)點D收到中間回復許可請求后,由Na按照上述方法計算出節(jié)點A的公鑰Ka;并生成一定長度的秘密隨機數(shù)Fd,計算Rb=Fd G,并計算Fa Rd的2個坐標之一中導出會話密鑰K,用私鑰K-1b生成中間回復許可應答(app robate-reply),將其用K加密后發(fā)送給源節(jié)點A。該應答報文為:D→A:Nd‖Rd E(K:sign(K-1d:Rd‖Ra‖Na))。

(5)源節(jié)點 A若在時間T內(nèi)收到中間節(jié)點B發(fā)來的“中間回復許可應答”,計算FaRd,用與第(4)步相同的方法得到K,解密后驗證D的簽名,若驗證成功,取出緩沖區(qū)中的路由,建立路由連接。否則,源節(jié)點 A從緩沖區(qū)中刪除該路由,并重啟路由發(fā)現(xiàn)過程。源節(jié)點 A將該中間節(jié)點B列入黑名單,并向網(wǎng)絡發(fā)出警告,隔離該節(jié)點。

圖1 中間回復許可請求過程

圖2 中間回復許可應答過程

路由測試消息和測試應答消息僅在網(wǎng)絡中單播而不需要做任何耗時的處理工作(如查表、比較等),路由測試的速度遠遠大于重新觸發(fā)RREQ的速度,因此,若中間節(jié)點B確實存在到目的節(jié)點的路由,則整個測試過程的時間要遠小于重新建立一個到目的節(jié)點路由過程的時間。

3 實驗與分析

為了驗證本文提出的針對黑洞攻擊的安全策略的可行性,選取NS-2網(wǎng)絡仿真軟件,網(wǎng)絡拓撲結構是一個包含50個移動節(jié)點的網(wǎng)絡模型,各節(jié)點隨機分布在1 000 m×1 000 m的平面矩陣區(qū)域內(nèi),鏈路層采用IEEE 802.11協(xié)議,仿真時間為500 s。發(fā)起路由請求的源節(jié)點和目的節(jié)點隨機產(chǎn)生,節(jié)點的最大連接數(shù)為30,最大移動速度為20m/s,停頓時間為50 s。信源采用隨機生成的CBR(恒定比特流),每個包的長度為512 B。

E-AODV與SAODV的比較如圖3所示,從圖3可以看出,E-AODV協(xié)議比SAODV協(xié)議的平均端到端延時更小。這是因為基于橢圓曲線加密法的數(shù)字簽名與SAODV協(xié)議相比,在同等安全強度下極大地降低了計算量。此外,本方案僅當中間節(jié)點回復時才采用該加密算法,所以對節(jié)點的計算能力和能量要求更低,并且路由建立的時延更短。

圖3 E-AODV與SAODV的比較

攻擊節(jié)點丟包率為被攻擊節(jié)點截獲并丟棄的數(shù)據(jù)分組總數(shù)與所有源節(jié)點發(fā)送的數(shù)據(jù)分組總數(shù)之比。在該仿真實驗中,設置一惡意節(jié)點在收到鄰居節(jié)點廣播的RREQ后立刻進行黑洞攻擊,EAODV與ADOV的比較如圖4所示。

圖4 E-AODV與ADOV的比較

從圖4所示可以看出,在遭到黑洞攻擊后,AODV協(xié)議攻擊節(jié)點截獲并丟棄數(shù)據(jù)分組最高可以占總數(shù)據(jù)分組的56%,這是因為AODV協(xié)議未設安全措施的緣故,而采用 E-AODV協(xié)議后,攻擊節(jié)點的丟包率明顯下降,惡意節(jié)點基本都能被截獲,這是因為惡意節(jié)點不能通過E-AODV協(xié)議的安全驗證,是在接收端被丟棄的。

此外,本協(xié)議利用中間節(jié)點所回復的路由,在等待時間T內(nèi)對中間節(jié)點進行驗證,不需要繞過節(jié)點B,所以不會發(fā)生唯一路徑問題。若節(jié)點B與節(jié)點C都是惡意節(jié)點,由于它們不存在到目的節(jié)點D的路由,那么節(jié)點B從目的節(jié)點D獲取approbate-rep ly的時延就會大大超過正常路由測試所需時間,從而不能在等待時間 T內(nèi)發(fā)送approbate-reply給源節(jié)點 A,節(jié)點B所回復的RREP被丟棄。這表明,E-AODV協(xié)議降低了路由建立的時延,在有效抵抗黑洞攻擊的同時,具有較高的安全性。

4 結束語

由于MANET具有媒體開放、動態(tài)拓撲結構及容量有限等特點,使得Ad hoc網(wǎng)絡的安全性較難保證。路由的安全是整個網(wǎng)絡安全的重要部分,也是一個難以徹底解決的問題。針對路由安全的威脅有許多種,不可能存在一種方案可以有效地防御各種威脅,因為每種威脅都有各自的特點。所以應該根據(jù)網(wǎng)絡的實際應用環(huán)境,針對可能存在的致命威脅和敏感數(shù)據(jù)設計算法予以解決和保護。

[1] Ramanathan R,Redi J.A brief overview of ad hoc netwo rks:challenges and directions[J].IEEE Communications Magazine,2002,40(5):20-22.

[2] 沈明玉,孫 偉.AODV路由協(xié)議中負載及能量均衡技術[J].合肥工業(yè)大學學報:自然科學版,2008,31(11):1798-1800.

[3] 詹鵬飛,陳前斌,李 云.移動 Ad hoc網(wǎng)絡AODV路由協(xié)議安全性分析和改進[J].計算機應用,2003,23(8):44-47.

[4] 彭志楠,葉丹霞,范明鈺.移動Ad hoc網(wǎng)絡的黑洞攻擊研究[J].計算機應用研究,2009,26(11):4006-4009.

[5] 葉阿勇,許 力.移動Ad hoc網(wǎng)絡 AODV路由協(xié)議中的黑洞問題[J].計算機工程,2005,31(14):125-126.

[6] Zapata M G.Secure ad hoc on demand distance vector(SAODV)routing[J].ACM M obile Compu ting and Communications Review(MC2R),2002,7(6):106-107.

[7] Papadim itratos P,H ass Z J.Secu re rou ting for m obile ad hoc netw orks in SCS communication netw ork s and distributed system s[C]//M odeling and Simulation Conference,San Antonio,TX,2002:27-31.

[8] Deng H ongmei,LiWei.Routing security in w irelessad hoc netw ork s[J].IEEE Communication Magazine,2002,40(10):70-75.

[9] 劉 淳,劉建偉,張其善,等.一種無證書Ad hoc密鑰管理與認證模型[J].西安電子科技大學學報:自然科學版,2007,34(6):974-979.

Research on black hole p roblem in m ob ile ad hoc networks

SHEN M ing-yu, LIU Jun-long

(School of Compu ter and Inform ation,Hefei University of Technology,H efei 230009,China)

Mobile ad hoc netw orks are extensively used inmilitary and civilian application,one typical characteristic o f w hich is the dynamic topo logical structure.This dynam ic nature of topo logy makes the network vulnerable to security attacks.This paper analyzes the operating processand potential insecurity factors of AODV routing protocol,and proposes a new solution for the black hole problem.The solution can not on ly so lve the black hole p rob lem efficiently,but it can also m ake up the deficiencies of some solutions in existence.

ad hoc network;routing security;Ad hoc On-Demand Distance Vector(AODV);b lack hole

TP393

A

1003-5060(2011)01-0087-04

10.3969/j.issn.1003-5060.2011.01.021

2010-01-11

合肥工業(yè)大學博士專項基金資助項目(GDBJ2009-005)

沈明玉(1962-),男,江蘇興化人,合肥工業(yè)大學副教授,碩士生導師.

(責任編輯 張秋娟)