灰洞检测:基于链路质量估计的看门狗算法

蒋 锟，汪 芸

(东南大学计算机科学与工程学院，江苏 南京 211189)

0 引言

近年来，无线传感器网络(Wireless Sensor Network)成为重要的研究热点。无线传感器网络是由大量部署在监测区域内具有感知、计算、存储和无线通信能力的微型节点组成的自组织分布式网络。这些节点协作地采集被感知对象的相关信息，并通过短距离多跳的无线通信方式将采集的数据传输到基站做进一步的分析和处理。无线传感器网络被设计成为可以大范围、长期对监测区域进行全面感知和精确控制的特殊自组织网络。

无线传感器网络中的安全问题日渐被研究者关注。灰洞攻击是最具网络性能破坏力的威胁之一。无线传感器网络的报文依靠网络中的节点彼此多跳接力传输，通常报文传输包括路由发现、路由回复和数据报文传输3个阶段。传感器网络的自组织性允许节点的自由加入和退出，因此难以控制网络中节点的可信程度。此外传感器网络中的节点通常部署在恶劣的区域，这使得传感器网络的节点易于被俘获从而成为恶意节点。当恶意节点成为通信路径上的中间节点后，在数据报文传输过程中，恶意节点通过故意丢弃报文对网络通信实施攻击，该攻击又分为黑洞(Black Hole)和灰洞(Gray Hole)两种攻击类型。黑洞攻击指网络中的恶意节点在数据报文传输过程中，丢弃所有收到的数据报文。而灰洞攻击选择性丢弃数据报文，因此灰洞比黑洞更加隐蔽，更难以检测。灰洞攻击通常会导致网络报文吞吐量下降、报文重传率高，甚至造成网络报文传输无法进行。

现有的检测算法主要依靠统计节点的接收转发行为来检测灰洞。传感器网络本身的链路质量比一般网络差，因此现有方法会产生较大的误差，尤其当传感器网络处于恶劣条件下，链路质量问题会导致很高的误报漏报率。本文的核心思路就是通过估计链路质量来修正统计结果以提高检测正确率。

1 相关工作

1.1 链路质量估计

传感器网络与传统网络的一个显著区别是网络的动态链路质量特性。链路质量表现在通信双方的范围不规则不对称，通信强度随时间变化等方面。在质量差的通信链路上会有较高的自然丢包概率，选择差链路质量的路由路径会导致网络吞吐量下降200%甚至更多［1］。准确的链路质量估计能够帮助传感器网络节点选择正确的路由，从而大幅优化网络性能。

链路质量可以通过多个度量进行估计，如接收信号强度(RSS)、发送延时、数据包接收率(PRR)等。期望发送数指标(ETX)是最常用的链路质量指标，它衡量成功转发一个报文所需的期望报文数，它的倒数为链路转发成功率。此外还有其他一些指标:链路的不对称指标(ETF)［2］;ETOP［3］考虑节点位置对链路质量的影响;Competence［4］、L-NT［5］、ENT［6］、端到端成功率［7］、数据包所需数［8］、EDR［9］等。

本文提出的检测算法需要链路间的转发成功率，也就是ETX指标的倒数，所以本文采用广为使用的4-bits协议。4-bits协议［10］使用4 bits来综合考虑物理层、链路层、网络层的信息估计链路质量。该方法使用物理信号强度和网络层拥塞程度信息做链路过滤，再根据链路层信标报文的收发统计数据来估计ETX指标。

1.2 灰洞攻击检测

Watchdog［11］是最早的检测灰洞攻击的方法，该方法中，数据传输的上游和下游节点的共同一跳邻居充当看门狗节点，该节点使用混杂模式监听介质来统计下游转发上游节点报文的行为。如果发现下游的丢包率高于某阈值则断定下游为恶意节点从而采取其他措施将其排除出路由。

此后有许多改进型的看门狗算法用来提高检测准确率。文献［12］通过选择多个看门狗共同协作来检测黑洞攻击。文献［13］提出将网络分段，看门狗节点的检测结果只在分段网络中有效，这样有效降低错误检测结果在全网内的扩散。文献［14］在路由路径旁边构造一条由看门狗组成的旁信道，旁信道作为主路由的参照，能够比较出主路由中哪个节点处发生了丢包从而检测出恶意节点。

上述看门狗算法都需要监听上下游节点的转发行为，根据监听到的统计结果进行判断。事实上，在传感器网络中，突发的碰撞等原因会导致链路质量急剧下降而使得上下游之间以及看门狗与上下游之间的转发、监听行为无法完成，这些自然丢包使得检测误报、漏报率显著增加。

一些跨层的检测算法考虑到了链路质量问题引起的误报、漏报问题。文献［15］使用有限状态自动机对丢包原因进行建模，该模型中主要考虑RTS/CTS模型的冲撞概率以及链路错误概率来推导出恶意丢包概率。文献［16］通过使用上下两节点共同监督中间节点的模式，能够有效降低数据包在节点间链路自然丢失引起的误报率。上述2种方法都是使用排除法来推导出恶意节点的丢包概率，但是丢包原因可能有更多可能性，难以用排除法来穷尽。

本文通过使用链路质量估计协议估计链路转发成功率，这比排除法更加通用，并且由于不用计算每种丢包原因的概率而使得健壮性更好。

2 检测算法

2.1 模型假设

本文假设网络中的节点没有能量限制，每个节点都分配了公私密钥对，并且知道其它所有节点的公钥。这些公钥用来保证网络中的包不被篡改。路由的源节点和目的节点都是可靠节点。恶意节点的选择性丢包概率与信道的自然丢包率是独立的。信道的自然丢包率服从高斯分布。恶意节点之间相互独立，没有合谋攻击。

2.2 路由选择

源节点需要将数据发给目的节点时，会先建立一条路由。本文使用4-bits链路质量估计协议获得一条从源节点到目的节点的最佳链路质量的路由。该协议要求节点定期与周边邻居交换信标报文来估计链路质量指标ETX。路由生成时期，每个节点估计自己到目的节点的总ETX，每个节点选择下一跳节点中到目的节点ETX最小的节点作为转发节点。路由选择阶段估计出的链路质量是该链路的自然链路质量，因为此阶段恶意节点不会主动丢包以确保自己尽可能被选为路由节点。

路由路径上的每个节点都成为其下游的主看门狗，此外根据需要还可以为其下游选择k个辅看门狗，辅看门狗是主看门狗与其下游的公共一跳邻居，将公共一跳邻居按照链路质量排序后选择前k个。对于每个路由节点(除源节点和目的节点外)，它至少有一个主看门狗，至多有k个辅看门狗。

2.3 检测算法设计

为方便表达，首先介绍下文将要使用的符号。recva，b指节点 a 从节点 b 接收到的报文数。senda，b指节点a发送给节点b的报文数。链路质量lqa，b表示节点a发报文给节点b，节点b能正确接收到的概率。图1给出一个典型的看门狗应用场景，节点a通过节点b给节点c发报文，看门狗节点w是节点a与节点b的共同一跳邻居，能够监听到节点a发报文给节点b和节点b发报文给节点c。对于看门狗w，节点a称为上游节点，节点b称为下游节点。

图1 看门狗应用场景

经典的看门狗算法中，每个看门狗节点通过比较下游节点的丢包率和设定的阈值来判定下游节点是否是恶意丢包节点。下游节点的丢包率按如下公式计算:

式(1)中，nu为下游节点正确收到上游节点发的报文数，nd为下游节点转发的报文数。看门狗将自己从上游节点收到的报文数recvw，a近似为下游正确接收的报文数nu，而将从下游节点收到的报文数recvw，b近似为下游转发的报文数nd，据此来近似计算下游节点的丢包率。

不难看出，在上述近似计算中，经典看门狗算法依赖的两个观察值都可能由于链路质量而导致误报、漏报。如图1中，上游a确实发了一个报文给下游b，而此时链路(a，w)突然出现碰撞等链路问题导致w没有监听到该动作，此时nu的估计值变小，导致计算出的Pd变小，使得漏报率上升。反之，下游b确实如实地转发了上游的报文，而w因为链路(b，w)的链路质量问题没有监听到该动作，这将导致nd的估计值变小，导致计算出的Pd变大，使得误报率上升。另外，即使看门狗对上下游的监测信息是正确的，但是由于链路(a，b)的链路质量导致下游没有正确接收到上游的报文，这会导致误报率上升。

本文的基本思想是通过链路质量估计协议估计出每条链路的链路质量，再用链路质量去修正统计观察值，以更加准确地估计下游丢包率。修正方法如下:

看门狗节点自身记录了它与邻居间链路质量，但是没有上下游之间的链路质量lqa，b，在4-bits链路质量估计协议中，a发给b的每个报文中的ETX字段记录了两者之间的链路质量，那么看门狗监听到上游发给下游的报文，即可根据 ETX字段值计算出 lqa，b。判断下游是否为恶意节点的依据是:

源节点每发送N个报文启动一次检查过程。在此过程中，源节点发送原始的检测报文，每个收到该报文的节点将其判断结果追加到原始报文后面，追加格式为［id，wid，，MACid］，id 为自身 id，wid 为被其监测的下游节点id是对wid监测的判断结果，MACid是用于防止报文被修改的数字签名。辅看门狗从主看门狗处接收检测报文，将其对下游的判断追加之后再返回给主看门狗。主看门狗依次将检测报文发给辅看门狗，等辅看门狗全部追加判断后再追加其判断，最后将此报文发给下一跳节点。以图1中的节点a为例，a从上游收到检测报文M后的动作:

最终路径中所有节点的判断结果会汇总到目的节点，目的节点首先验证信息摘要以确保报文没有被篡改，然后计算最终的判决，如果节点被不少于一半的看门狗怀疑，那么这个节点被最终判为恶意节点。目的节点将判为恶意节点的id组装成预警报文，再反向发往源节点，收到预警报文的节点发现其邻居id在预警报文中，就将该邻居从路由表中剔除。

2.4 参数优化

本小节主要关注阈值τ的优化，使得检测的误报率和漏报率最低。

在路由选择阶段，看门狗估计其监测节点的自然丢包率X1，其概率分布为 X1～N(μ1，)。该阶段恶意节点为了能够被选择加入路由，不会主动丢包，因此此时估计出的是检测节点的自然丢包率的概率分布。数据发送阶段，看门狗估计其监测对象的总丢包率的概率分布X2～N(μ2，)。

假设该检测对象是恶意节点，其恶意丢包率为mdr，由于自然丢包和恶意丢包是独立事件，那么恶意节点的总丢包率为X2=1-(1-mdr)(1-X1)=X1+mdr(1-X1)。如图2所示，此时X2＞X1，并且恶意节点的丢包率mdr越大，总丢包率X2与自然丢包率X1之间的差距越大。

图2 最优阈值理论推导

检测的误报率是由自然丢包率X1超过阈值τ而引起的，即图2中的斜线阴影区域面积。同理，检测的漏报率是由总丢包率X2低于阈值τ而引起的，即图2中的竖线阴影区域面积。当阈值增大时，斜线阴影区域面积减小而竖线阴影区域面积增大，即检测误报率降低而漏报率增大，反之亦然。最优阈值τ*应该使得检测的误报、漏报率之和最小。因此最佳阈值计算方法如下:

其中 fX1和 fX2分别为 X1和 X2的概率密度函数，Pfalsenegative和Pfalsepositive分别是检测误报率和漏报率。

路由选择阶段后，系统只知道自然丢包率X1的分布，此时将阈值设置为τ1使得误报率低于概率Pinit，即 τ1=minτ［Pfalsenegative(τ)≤Pinit］，此后当网络检测出恶意节点后，获得恶意节点的丢包概率分布X2，即可计算出当前最优阈值，经过迭代逼近τ*。

3 性能评估

本文的检测算法在TinyOS中实现，并且在Tiny-OS自带的TOS仿真平台进行仿真实验。本文的实验拓扑如图3所示，节点6和节点1分别为源、目的节点。实验场景分为以下3种:场景1是单恶意节点场景，节点3为恶意节点;场景2为间隔多恶意节点场景，节点3和节点5为恶意节点;场景3为连续多恶意节点场景，节点3和节点4为恶意节点。恶意节点丢包率mdr为33%。经典看门狗算法的判断阈值为20%。

图3 实验拓扑

本文主要和经典看门狗算法做性能比较，因为本文主要改进经典看门狗算法的最基础的链路部分，其他基于看门狗的改进算法主要是对看门狗个数、拓扑等方面改进，这些改进方法都可以使用本文提出的方法，因此本文直接和经典看门狗算法做比较。本文的评价标准是算法的正确率(Correctness Ratio)、误报率(False Negative Ratio)、漏报率(False Positive Ratio)和准确率(Accuracy Ratio)。正确率指算法正确判断节点是恶意节点或正常节点的概率，误报率指算法将正常节点判为恶意节点的概率，漏报率指算法将恶意节点判为正常节点的概率，准确率指算法将恶意节点判为恶意节点的概率。实验的每个数据都是重复运行100次得到的均值。

图4(a)是单恶意节点场景下的算法性能比较。随着自然丢包率X1的增加，因为=mdr(1-X1)，所以自然丢包率X1和恶意节点总丢包率X2之间的距离减小，这使得分辨出两者的难度增大，因此图4(a)中算法的正确率都呈现下降趋势，但是基于链路质量的看门狗算法下降趋势较为缓慢;其次由于X2=mdr+X1(1-mdr)，随着自然丢包率X1的增加，恶意节点总丢包率X2会增大，而经典看门狗算法的阈值固定，基于链路质量的看门狗算法迭代更新阈值较慢，根据公式(7)可以推出算法的漏报率会降低，所以图4(a)中算法的准确率会随着自然丢包率的增大而提高，但是根据公式(6)可以推出算法的误报率会增加，图4(a)显示出经典看门狗算法会牺牲大量的误报率来提高准确率，而本文的算法则通过牺牲一点准确率来保证算法的总正确率。图4(b)是间隔多恶意节点场景下的性能比较。该场景下的性能趋势与图4(a)基本一致，但是多恶意节点会导致算法正确率随着自然丢包率的增长而恶化得比单恶意节点快，说明多恶意节点之间的丢包模型会相互影响，不是完全独立的。图4(c)是连续多恶意节点场景下的性能比较，可以看到该场景下的性能与间隔多恶意节点场景下的性能趋势基本一致，主要原因是恶意节点之间是独立的，恶意节点之间没有合谋攻击，恶意节点只是如实地反应自己的监测结果。

图4 算法性能比较

图5 不同阈值下的检测结果

图5展现的是不同阈值下的检测结果。在场景1下，自然丢包率为20%。可以看到随着阈值τ的增大，检测误报率 Pfalsenegative(τ)会减小，而漏报率Pfalsepositive(τ)会增大，准确率是先增大后减小的趋势。根据第2.4节参数优化的计算，可以计算出此时的最佳阈值τ*=0.336。实验结果与第2.4节的理论分析基本符合。

4 结束语

本文提出的基于链路质量的看门狗算法通过估计链路质量来修正看门狗的检测结果，能够有效地降低由于链路质量而引起的误报、漏报率，本文提出的最优阈值理论，能够有效地根据网络环境调整参数，最小化误报、漏报概率，提高算法正确率。网络环境越恶劣(网络自然丢包率越高)，本文的算法越有优势。在未来的工作中，将研究看门狗数量、拓扑对检测结果的影响以及多个恶意节点间的合谋攻击的检测。

［1］De Couto D S J，Aguayo D，Bicket J，et al.A high-throughput path metric for multi-hop wireless routing［J］.Wireless Networks，2005，11(4):419-434.

［2］Sang L，Arora A，Zhang H.On exploiting asymmetric wireless links via one-way estimation［C］//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2007:11-21.

［3］Jakllari G，Eidenbenz S，Hengartner N，et al.Link positions matter:A noncommutative routing metric for wireless mesh networks［J］.IEEE Transactions on Mobile Computing，2012，11(1):61-72.

［4］Lin S，Zhou G，Whitehouse K，et al.Towards stable network performance in wireless sensor networks［C］//Proceedings of the 30th IEEE Real-Time Systems Symposium.2009:227-237.

［5］Zhang H，Sang L，Arora A.Comparison of data-driven link estimation methods in low-power wireless networks［J］.IEEE Transactions on Mobile Computing，2010，9(11):1634-1648.

［6］Draves R，Padhye J，Zill B.Comparison of routing metrics for static multi-hop wireless networks［J］.ACM SIGCOMM Computer Communication Review，2004，34(4):133-144.

［7］Gnawali O，Yarvis M，Heidemann J，et al.Interaction of retransmission，blacklisting，and routing metrics for reliability in sensor network routing［C］//Proceedings of the 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks.2004:34-43.

［8］Cerpa A，Wong J L，Potkonjak M，et al.Temporal properties of low power wireless links:Modeling and implications on multi-hop routing［C］//Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2005:414-425.

［9］Gu Y，He T.Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links［C］//Proceedings of the 5th International Conference on Embedded Networked Sensor Systems.2007:321-334.

［10］Fonseca R，Gnawali O，Jamieson K，et al.Four-bit wireless link estimation［C］//Proceedings of the 6th Workshop on Hot Topics in Networks.2007.

［11］Marti S，Giuli T J，Lai K，et al.Mitigating routing misbehavior in mobile ad hoc networks［C］//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking.2000:255-265.

［12］Patcha A，Mishra A.Collaborative security architecture for black hole attack prevention in mobile ad hoc networks［C］//Proceedings of the 2003 IEEE Radio and Wireless Conference.2003:75-78.

［13］Nasser N，Chen Y.Enhanced intrusion detection system for discovering malicious nodes in mobile ad hoc networks［C］//Proceedings of the 2007 IEEE International Conference on Communications.2007:1154-1159.

［14］Li X，Lu R，Liang X，et al.Side channel monitoring:Packet drop attack detection in wireless ad hoc networks［C］//Proceedings of the 2011 IEEE International Conference on Communications.2011.

［15］Hayajneh T，Krishnamurthy P，Tipper D，et al.Detecting malicious packet dropping in the presence of collisions and channel errors in wireless ad hoc networks［C］//Proceedings of the 2009 IEEE International Conference on Communications.2009:1062-1067.

［16］Shila D M，Cheng Y，Anjali T.Channel-aware detection of gray hole attacks in wireless mesh networks［C］//Proceedings of the 28th IEEE Conference on Global Telecommunications.2009:3998-4003.