移动Ad hoc网络中黑洞问题的研究

沈明玉, 刘俊龙

(合肥工业大学计算机与信息学院,安徽合肥 230009)

移动Ad hoc网络中黑洞问题的研究

沈明玉, 刘俊龙

(合肥工业大学计算机与信息学院,安徽合肥 230009)

移动Ad hoc网络在民用设施和国防事业方面得到广泛应用,动态变化的拓扑结构是Ad hoc网络的一大特征,也正是这种动态性使得Ad hoc网络特别容易受到安全方面的攻击。文章剖析了AODV路由协议的工作过程,针对协议中存在的黑洞问题,提出了一种新的解决方案,该方案不仅有效地解决了黑洞问题而且可以消除一些现有解决方案所存在的缺陷。

Ad hoc网络;路由安全;AODV;黑洞

移动Ad hoc网络是一种具有高度动态拓扑结构、节点可自由移动的自组织网络[1]。Ad hoc网络中的每个节点,既是网络数据终端,又是路由器。作为需转发数据包的路由器,路由协议是其最重要的部分。其中,AODV路由协议是Ad hoc网络中一种常用的按需路由协议。它在控制开销、节点储存开销和算法复杂度等大部分性能指标方面都优于其它协议,被认为是最有实用前景的Ad hoc网络路由协议之一[2]。

Ad hoc网络的路由协议极易受到攻击,如果路由协议一旦遭受到恶意攻击,整个网络将无法正常工作,并有可能陷入瘫痪,因此路由的安全是整个网络安全的重要部分。本文重点分析了AODV协议的安全隐患,针对协议中最常见的黑洞问题提出了一种新的解决方案,并通过NS-2进行仿真实验。实验结果表明,该解决方案能够有效地阻止黑洞攻击,并且可以消除部分现有方案所存在的缺陷。

1 研究背景

1.1 AODV路由协议

AODV[3]协议是路由协议DSR和DSDV的结合,它借用了DSR的路由发现策略以及DSDV的逐跳路由、序列号和定期广播机制,是一种按需路由协议。在AODV路由协议中,当源节点想要找到一条到达目的节点的路由,而在路由表中又没有有效的路由存在时,它就向所有邻居节点广播一个路由请求分组(RREQ),当中间节点收到RREQ,就在路由表中建立一条指向源节点的反向路由,然后再向周围节点广播这个 RREQ,若中间节点有RREQ所查找的到目的节点的有效路由,则它向上一跳节点回发路由应答消息(RREP),并经若干中间节点向源节点回发RREP。如果目的节点收到RREQ,它就沿着反向路由向源节点回复路由应答分组(RREP),当RREP到达源节点,则建立了一条从源节点到目的节点的有效路由。如果源节点收到了多个RREP,它会根据目标节点序列号和跳数来决定是否更新自己的路由表信息。

1.2 AODV路由协议中的黑洞问题

在最初的AODV协议的应答机制中,允许中间节点对路由请求进行回复,即只要该中间节点有一条到目的节点的可用路由,它就可以响应RREQ消息。这种机制的目的是减小寻路时延和开销。但是,恶意节点利用AODV协议的广播机制,捕获经过自己的RREQ消息,并宣称自己有到达目的节点的最佳路由(通过伪造跳数或者伪造目的节点序列号),从而使源节点采用此虚假路由。恶意节点可以轻易拦截所有数据包而形成一个吸收数据包的“黑洞”。这样使得恶意节点从源节点骗得大量的网络信息和重要的数据,而真正的目的节点接收不到来自源节点的数据,这就是所谓的黑洞问题[4]。通过这个途径恶意节点可以很容易地引导许多网络流量到其自身,以非常低的代价使网络的安全性受到很大的威胁。

1.3 黑洞问题的研究现状

防范黑洞攻击的最简单有效的方法就是禁止中间节点对RREQ进行回复,而仅允许目的节点回复[5]。这在一定程度上避免了黑洞问题,提高了AODV协议的安全性,但也增加了路由建立的延时,当网络的规模比较大时,其效率就会受到严重影响。此外,当恶意节点假冒目的节点向源节点回复虚假RREP时,源节点也无法识别这个RREP是来自目的节点还是恶意节点的。

文献[6,7]提出的SAODV和路由协议安全扩展等解决方案是基于加密算法的安全策略,这些安全策略可以提供较完善的路由安全保障,包括黑洞问题的解决。但密码体制的引入增加了源节点和目的节点的运算量,对节点的运算能力、能耗等方面有了更高的要求。因此,虽然可以有比较高的安全性,但是由于每个节点都要进行加密和验证,因此其对移动终端的计算能力和电源有较高的要求,而且还会增加大量的时延。

文献[8]提出,当中间节点应答(设为节点B)时,必须把它的下一跳节点(设为节点C)的信息附加在RREP中发给源节点。源节点根据该信息从其它路由给C发验证包,以查询C是否真有到目的节点和到该中间应答节点的可用路由。若C确实存在到目的节点和应答节点的可用路由,则信任该应答节点并开始发送数据。若C没有到目的节点或到应答节点的路由则忽略该应答,同时向全网发送警告信息孤立该应答节点。该方案在一定程度上解决了黑洞问题,但仍存在以下缺陷:①唯一路径问题。若应答节点B是正常节点,但源节点和目的节点间仅存在经由B的唯一路由,则源节点由于无法从另外的路由对节点C进行验证,从而误认为B是恶意节点。②恶意节点团队破坏。如果恶意节点B和C组成团队进行破坏,则源节点收到的查询结果也是虚假的。

2 基于ECC的AODV解决方案

数字签名是一种有效的认证手段,与RSA相比,椭圆曲线密码在同等安全强度下可大大减少计算量,本文分析了以上几种现有解决方案的缺陷,针对协议中存在的黑洞问题,提出了一种基于椭圆曲线加密法路由安全协议。

2.1 椭圆曲线加密法

椭圆曲线加密法(Elliptic Curve Cryptography,简称ECC)是当今众多研究者最关注的公钥加密技术之一[9],以椭圆曲线理论为基础,建立基于椭圆曲线的对应密码体制。设素数域椭圆曲线方程为:E:y2=(x3+ax+b)mod p,曲线参数为E:{a,b,G,N,P},G是椭圆曲线E/F(p)的基点,用G=(xG,yG)来表示,N是基点G的阶。假定私钥sk为整数r,则对应的公钥为椭圆曲线E上的一个点rG,用(xr,yr)标记。用SSK表示私钥种子矩阵,由整数矢量(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路由安全协议

本文针对现有安全协议的缺陷,提出了一种新的基于椭圆曲线加密法路由安全协议(EAODV)。在方案中,当中间节点B对源节点A进行路由应答时,源节点A需对该中间节点B进行验证,测试所应答路由的正确性之后才能建立路由连接。具体过程如下:

(1)当A发起路由建立时,生成新的随机数Fa,计算Ra=FaG,其中G为椭圆曲线基点,加入RREQ中进行路由查找。

(2)如图1所示,中间节点B对源节点A进行RREP回复,同时向目的节点D发送一个“中间回复许可请求”(approbate-request),该请求报文为:B→D:Na‖Ra。

(3)源节点A将该路由存入缓冲区,再根据中间节点B提供的路由的跳数等待一个相应的时间T。

(4)如图2所示,目的节点D收到中间回复许可请求后,由Na按照上述方法计算出节点A的公钥Ka;并生成一定长度的秘密随机数Fd,计算Rb=Fd G,并计算Fa Rd的2个坐标之一中导出会话密钥K,用私钥K-1b生成中间回复许可应答(app robate-reply),将其用K加密后发送给源节点A。该应答报文为:D→A:Nd‖Rd E(K:sign(K-1d:Rd‖Ra‖Na))。

(5)源节点 A若在时间T内收到中间节点B发来的“中间回复许可应答”,计算FaRd,用与第(4)步相同的方法得到K,解密后验证D的签名,若验证成功,取出缓冲区中的路由,建立路由连接。否则,源节点 A从缓冲区中删除该路由,并重启路由发现过程。源节点 A将该中间节点B列入黑名单,并向网络发出警告,隔离该节点。

图1 中间回复许可请求过程

图2 中间回复许可应答过程

路由测试消息和测试应答消息仅在网络中单播而不需要做任何耗时的处理工作(如查表、比较等),路由测试的速度远远大于重新触发RREQ的速度,因此,若中间节点B确实存在到目的节点的路由,则整个测试过程的时间要远小于重新建立一个到目的节点路由过程的时间。

3 实验与分析

为了验证本文提出的针对黑洞攻击的安全策略的可行性,选取NS-2网络仿真软件,网络拓扑结构是一个包含50个移动节点的网络模型,各节点随机分布在1 000 m×1 000 m的平面矩阵区域内,链路层采用IEEE 802.11协议,仿真时间为500 s。发起路由请求的源节点和目的节点随机产生,节点的最大连接数为30,最大移动速度为20m/s,停顿时间为50 s。信源采用随机生成的CBR(恒定比特流),每个包的长度为512 B。

E-AODV与SAODV的比较如图3所示,从图3可以看出,E-AODV协议比SAODV协议的平均端到端延时更小。这是因为基于椭圆曲线加密法的数字签名与SAODV协议相比,在同等安全强度下极大地降低了计算量。此外,本方案仅当中间节点回复时才采用该加密算法,所以对节点的计算能力和能量要求更低,并且路由建立的时延更短。

图3 E-AODV与SAODV的比较

攻击节点丢包率为被攻击节点截获并丢弃的数据分组总数与所有源节点发送的数据分组总数之比。在该仿真实验中,设置一恶意节点在收到邻居节点广播的RREQ后立刻进行黑洞攻击,EAODV与ADOV的比较如图4所示。

图4 E-AODV与ADOV的比较

从图4所示可以看出,在遭到黑洞攻击后,AODV协议攻击节点截获并丢弃数据分组最高可以占总数据分组的56%,这是因为AODV协议未设安全措施的缘故,而采用 E-AODV协议后,攻击节点的丢包率明显下降,恶意节点基本都能被截获,这是因为恶意节点不能通过E-AODV协议的安全验证,是在接收端被丢弃的。

此外,本协议利用中间节点所回复的路由,在等待时间T内对中间节点进行验证,不需要绕过节点B,所以不会发生唯一路径问题。若节点B与节点C都是恶意节点,由于它们不存在到目的节点D的路由,那么节点B从目的节点D获取approbate-rep ly的时延就会大大超过正常路由测试所需时间,从而不能在等待时间 T内发送approbate-reply给源节点 A,节点B所回复的RREP被丢弃。这表明,E-AODV协议降低了路由建立的时延,在有效抵抗黑洞攻击的同时,具有较高的安全性。

4 结束语

由于MANET具有媒体开放、动态拓扑结构及容量有限等特点,使得Ad hoc网络的安全性较难保证。路由的安全是整个网络安全的重要部分,也是一个难以彻底解决的问题。针对路由安全的威胁有许多种,不可能存在一种方案可以有效地防御各种威胁,因为每种威胁都有各自的特点。所以应该根据网络的实际应用环境,针对可能存在的致命威胁和敏感数据设计算法予以解决和保护。

[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路由协议中负载及能量均衡技术[J].合肥工业大学学报:自然科学版,2008,31(11):1798-1800.

[3] 詹鹏飞,陈前斌,李 云.移动 Ad hoc网络AODV路由协议安全性分析和改进[J].计算机应用,2003,23(8):44-47.

[4] 彭志楠,叶丹霞,范明钰.移动Ad hoc网络的黑洞攻击研究[J].计算机应用研究,2009,26(11):4006-4009.

[5] 叶阿勇,许 力.移动Ad hoc网络 AODV路由协议中的黑洞问题[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

合肥工业大学博士专项基金资助项目(GDBJ2009-005)

沈明玉(1962-),男,江苏兴化人,合肥工业大学副教授,硕士生导师.

(责任编辑 张秋娟)