Node Clone Attacks Detection Based on Distributed Random Verification in Wireless Sensor Networks*

ZHOU Yuping，HUANG Zhengjie，WANG Juan，CHEN Dong

(1.College of Computer Science，Minnan Normal University，Zhangzhou Fujian 363000，China; 2.China Telecom Corporation Ltd.Zhangzhou Branch，Zhangzhou Fujian 363000，China)

Node Clone Attacks Detection Based on Distributed Random Verification in Wireless Sensor Networks*

ZHOU Yuping1*，HUANG Zhengjie1，WANG Juan1，CHEN Dong2

(1.College of Computer Science，Minnan Normal University，Zhangzhou Fujian 363000，China; 2.China Telecom Corporation Ltd.Zhangzhou Branch，Zhangzhou Fujian 363000，China)

It is easy for adversary to capture and compromise sensor nodes unattended nature in wireless sensor networks.In node replication attack，an adversary can take advantage of the credentials of the compromised node to surreptitious introduce replicas of the node into the network and launch many attacks.A novel distributed detection protocol of node replication attacks is presented.Randomly selected cells to which location claims are mapped and randomly linear-selected node verification in cell are combined in our method.Simulation results show that random verification is designed to balance the energy consumption and the lifespan of the networks is prolonged.High detection rate of node replication attacks and lower communication overhead are achieved.

network security;Wireless Sensor Networks;node replication attack;multi-cell;random verification

无线传感网络在国际上被认为是继互联网之后的第二大网络［1］，其安全问题越来越受到研究者们关注。由于无线传感器网络部署在无人值守，甚至敌对的环境中，传感器节点会暴露在攻击者的视线范围内，攻击者可通过俘虏网络中一个或多个节点，提取出节点中的私密信息如节点ID、用于与其他节点建立安全信道的密钥等，利用这些信息复制出无限数量的具有相同ID和合法私密信息的节点，并把这些复制节点投放到网络中。这些复制节点具有合法的身份ID和正确的密钥等信息，就能通过各种认证机制，并与其他节点建立信任管理，从而可以监听网络流量、窃取敏感信息、实施虚假信息网络注入攻击，甚至破坏无线传感网络中各种应用及协议，是网络安全的巨大隐患［2］。

2005年，Parno［3］首次提出节点复制攻击问题，随后研究人员提出了各种的节点复制攻击检测方案。一般检测方案中，每个节点都要产生一个位置申明信息，该信息主要包含节点位置信息以及该节点的数字签名，当发现同一个节点ID存在多个不同的位置申明时，则表示网络中存在节点复制攻击。检测出是否存在冲突的位置申明信息是静态传感网络中节点复制攻击检测的基本思路［4］。现有的节点复制攻击检测方案主要有两类:集中式检测方案和分布式检测方案。集中式的检测方案依赖于一个控制中心，用于执行检测协议中的一些重要步骤，因此容易遭受单点失效故障或攻击［5］，同时控制节点周围将承受较大的网络通信量，节点负载不均衡，极大影响网络的使用寿命。分布式检测方案则不需要控制中心，Parno等［3］提出的分布式检测协议及Conti等［6］提出的RED(Randomized，Efficient and Distri-buted)协议论证了分布式机制的必要性［2］。根据验证节点是否可以预测，检测方案可以分为确定性检测和随机性检测。随机性检测方案使攻击者无法预测验证节点位置，不能实施智能攻击。Parno等提出的随机性验证协议RM(Randomized Multicast)协议产生O (n2)的通信开销，不适应无线传感网络能量受限的特点［3］。Zhu［7］等提出的所谓随机性多区域概率映射方案实际只是确定性验证方案的变形。徐军［2］提出基于随机种子的线选多播检测方案虽然能实现随机验证，但是种子池的生成和管理对系统造成较大的负担，种子池本身也容易成为智能攻击的目标。Zeng等［8］提出的RAWL(RAndom WaLk)协议和TRAWLK (Table-Assisted RAndom WaLk)协议扩展了Parno等提出的LSM(Line-Selected Multicast)协议［3］，虽然获得比LSM高的检测率，但需要高出近2倍的通信开销。Ho［9］等人提出的基于SPRT(Sequential Probability Ratio Test)的随机检测和Lou［10］等提出的基于SHP(Single HoP detection)的随机检测主要应用于移动无线传感网络中。本文提出一类新的分布式随机验证节点复制攻击检测协议RMC(Randomized parallel Multiple Cells)协议，协议根据生日悖论原理，采用随机局部区域映射，使冲突节点映射到同一区域产生碰撞，再在区域内随机线性选取验证节点进行检测。RMC协议实现随机性验证能有效防止攻击者预测并虏获验证节点破坏检测协议，并使网络能量均匀消耗，延长网络的生存周期。同时域内线性检测使协议的通信和储存开销较低，适合大规模无线传感网络，能获得较高的检测率。

1 协议环境

1.1 协议需求

无线传感器网络容易遭受物理攻击，节点复制攻击是常见攻击之一。无线传感器网络自身固有的缺陷，如存储空间不足、电能容量小、缺乏物理防护设备、无人守护等，使集中式检测存在诸多问题，分布式检测成为协议设计的需要。为防止攻击者预测验证节点，在协议运行前颠覆验证节点，采用随机性验证是提高协议自身安全性的关键。

当变节节点和它的复制节点被检测出来时，需要有相应的撤销机制在全网广播废除它们，使正常节点停止与其通信。协议设计应尽量减少通信量和计算量以适应无线传感器网络存储、电能等有限资源的限制，以延长无线传感器网络的生存期。同时要实现高的节点复制攻击检测率来保证系统的安全性。

1.2 网络模型

无线传感器网络由成千上万、均匀规则地分布在广大区域的低能量的小节点组成。整个网络由互不相交的区域单元(Cell)构成物理网格，最终形成二层式拓扑结构，每个区域单元即为一个簇并产生一个簇首节点。无线传感器网络采用多跳通信传输模式，每个普通节点的通信能力和能量相同，并以非监督方式工作。网络可以动态添加新的节点和摘除能量耗尽或意外损坏的坏死节点。假设网络基站是安全可信任的，基站可不经过簇首直接向网络内所有的节点直接发送指令控制信息。

在系统布置之前完成大部分的安全设置，本系统使用基于身份公钥加密系统［11］，通过TA(Trusted Authority)的主密钥对系统的公钥签名得到系统的私钥。当被虏获节点数量超过安全门限时，密钥预分配方法可以保证整个网络被攻破的概率很低。事实上，使用这样的安全模型，敌手没有TA的帮助是无法获得密钥，没有合法密钥就无法生成一个新的ID(Identity)。敌手只能捕获并克隆合法的节点，并暗中把这些克隆节点部署到网络中具有战略地位的特定区域进行有目的的攻击破坏。

1.3 攻击模型

攻击者的主要目标是秘密俘获若干固定数目的合法的传感器节点，并能把被俘虏的节点秘密安插到网络中实施攻击行为，完成节点复制攻击并防止已经被俘虏的节点暴露。这些节点可以正常方式同网络中其他节点通信和合作。攻击者通过被动攻击和主动攻击来实现这个目标。通过秘密监听网络数据和收集有关信息来评估实施诸如重放、修改网络数据等主动攻击的收益，攻击者实施节点复制攻击时可能的隐含利益及被检测到的概率。同时，攻击者具有记忆功能，对被俘虏的节点不会重复攻击，而是选择那些对攻击威胁最大的节点进行破坏。

2 协议框架

假设网络的部署规模为n个传感器，这些节点的ID唯一，在一轮检测周期内相对静止。网络节点在检测间隔中可动态添加或删除，并可通过GPS或定位算法确定自己的地理位置，生成一个二维的坐标(x，y)。协议运行由3步骤组成:

(1)区域单元物理网格的建立阶段

首轮成簇时，因为所有节点能量相等，采用LEACH路由算法选择簇首节点［12］，簇首节点之间采用单跳通信。首轮之后，网络采用基于剩余能量多者优先原则确定簇首，节点根据自身当前能量和簇内节点平均能量的比例来竞争簇首。节点当选簇首后广播其簇首信息，普通节点在接收到多个不同簇首广播信息后，根据自身与不同簇首的不同通信成本取最小通信成本原则，选择加入某个簇，并向簇首发出加入申请。同时记录其他簇首信息。簇首收到节点申请加入簇后将节点加入自己的路由表。在传感网络二层结构建立后，根据物理网格生成算法对每个簇进行编号。将整个无线传感器网络分成m=u×v个区域单元cell，表示传感网络分为u行和v列，某个区域ID为w(w=(u'－1)*v+v'，其中u'∈{1，2，…，u}，v'∈{1，2，…，v})表示该区域在第u'行第v'列。算法如表1所示。

表1 建立区域单元(cell)算法

(2)区域单元映射阶段

每轮检测协议开始之初，每个节点都产生一个节点位置申明{IDL，lL，SIGSKL(H(IDL‖lL))}，其中IDL为节点L的身份标识;lL为节点L的位置坐标，记作二维＜xL，yL＞;SIGSKL(H(IDL‖lL))表示节点L身份标识拼接位置坐标后取哈希值，并使用节点密钥对该哈希值签名。节点复制攻击检测时，节点L从网络范围内随机选择q个区域单元，并把自己的位置申明发给所选的区域单元C={C1，C2，…，Cq}。根据生日悖论定理，在由m个区域单元组成的网络中，每个节点位置申明映射到个区域单元进行验证，则至少一个冲突产生的概率很高，使q取 O()个区域单元。区域单元中的节点对收到的位置申明使用与该节点对应的密钥解密签名进行认证，并根据自身的大致传输辐射半径判断其合理性。对不能通过检查的节点位置申明信息给予丢弃，能通过检查的节点位置申明信息，在区域单元中进行进一步的线选验证节点多播验证。算法如表2所示。

表2 区域单元映射算法

(3)域内线选多播验证阶段

节点L将节点位置申明映射到某区域单元，假设节点a为该区域单元中第一个收到位置申明信息的节点，其位置坐标为(xa，ya)。首先，节点a在对位置申明验证通过后，将该位置申明数据包的生存周期时间TTL设成，节点a存储节点L的位置申明，承担验证节点工作，将节点L的位置申明与其已存储其他节点的位置申明相比较，如发现存在具有相同ID不同地理位置的情况，说明出现克隆攻击，则节点a直接向基站报告克隆节点的ID，由基站向全网广播节点L失效的公告。如果验证节点a上没有检测出克隆节点，则验证节点a向自己的相邻节点转发节点L的位置申明，每个邻居节点记录该位置申明，成为一个辅助验证节点，进行同样验证。然后使用地理路由［13］沿xa轴水平方向和ya轴垂直方向同时播送，并使TTL减去1。播送过程中位置声明总选择最靠近xa轴或ya轴的邻居节点转发，直到检测出冲突或到达区域单元的边界，数据包被丢弃。在区域单元验证转发过程中，所有验证节点要么在同一水平x坐标轴上，要么在同一垂直Y坐标轴上，而且验证节点占据一个面，该面是以坐标轴上验证节点为中心，和作为辅助验证节点的一跳距离邻居构成的一个区域，因此当二个冲突向量在同一区域单元内沿着各自x坐标轴或Y坐标轴转发时，必定会在交叉点形成的验证面中相遇，并被检测出来。

我们以图1实例说明，假设节点L'是节点L的克隆节点，它们同时映射到同一区域单元内。节点L映射到验证节点a，坐标(xa，ya)。点L'映射到验证节点g，坐标(xg，yg)。则节点a沿着xa轴方向和ya轴方向同时转发，而节点g沿着xg轴方向和yg轴方向同时转发。转发过程中，坐标轴上的验证节点一边储存位置申明，一边向一跳邻居节点广播形成验证面。最终在xa轴和yg轴(ya轴和xg轴)相交处形成的验证面上验证节点m(验证节点t)上检测出冲突。算法如表3所示。

图1 协议示意图

表3 线选多播验证算法

3 协议分析

3.1 协议安全

假设克隆节点L'被布置在L={L1，L2，…，Ll}的l个位置上，根据生日悖论定理，在由m个区域单元组成的网络中，每个节点位置申明映射到■个区域单元进行验证，则至少一个冲突产生的概率很高。分析具有相同ID不同位置的克隆节点被映射到同一区域单元的碰撞概率。

假设传感网络由m个区域单元组成，对于每个节点，随机选择并映射到q个验证区域，根据生日悖论标准推导，l1位置上的位置申明选择的q个映射区域没有收到l2位置申明的q个信息复制的概率Pnc1为:

同样，l3位置上的位置申明选择的q个映射区域没有收到l2位置申明和l1位置申明的2q个信息复制的概率Pnc2

因此，所有位置申明都没有映射到同一区域产生碰撞的概率Pnc为

其中l为克隆节点L'被布置的位置数量，使x=－(i·q/m)，将标准近似式(1+x)≤ex代人式(3)可得:

则位置申明映射过程中产生碰撞的概率pc为:

将式(6)代入式(7)，可得:

3.2 协议性能

协议的性能通常从通信开销Ccom和储存开销Cmem二方面评测。通信开销是指执行一次检测协议时每个节点平均发送和接收的数据包数量，在我们的协议中通信开销为:

其中Cf为节点位置申明映射到区域单元的通信开销，Cs为节点位置申明在区域单元中沿着水平和垂直方向传播检测的通信开销。无线传感器网络内任意二个节点间的通信开销平均为O/2)［3］，因此每轮检测中Cf为O(q·■n/2)，而Cs为O(q·2·)，其中为区域单元水平轴(垂直轴)的平均长度距离，q为随机映射的区域单元数量，则通信开销根据式(9)即Ccom=O·/2)。

关于储存开销Cmem，因为平均每个节点映射到q个区域单元，在区域单元中位置申明沿着水平、垂直两个方向转发存储，而且以轴上节点为中心，向相邻节点转发形成验证面，为保证碰撞率高于63%，使q为O(■m)，因此，对于一个节点ID其平均的存储开销为O(q·(·d+)·2)即O(d·■n)，其中d为区域单元中每个节点的邻居节点数。对于协议的安全性，每次协议运行都随机选择并映射到多个区域单元，在区域单元中采用最新收到信息的节点沿水平和垂直轴转发验证，目标区域单元确定的随机多样性，验证区域确定后验证节点的随机线性选择使得协议能避免单点失效或局部区域能量消耗过大过早消亡的现象，有效地防御复制节点的智能攻击，提高网络的生存周期，并有较高节点复制攻击检测率。

针对几种随机性验证协议，表4对Parno提出的LSM和RM协议［3］﹑Zhu等提出的P-MPC协议［7］及本文提出的RMC协议的通信开销和储存开销进行比较，其中n为无线传感网络的规模即包含的传感节点数量;d为节点的平均邻居数目;g为一个邻居节点转发位置申明到目标位置数量;pf为邻居节点决定转发位置申明的概率;w为验证节点的数量;m为区域单元的数量。

表4 通信开销和存储开销比较表

4 仿真实验

仿真实验使用Omnet++仿真器，该仿真器能够支持较大规模的网络仿真，协议仿真中，传感器节点随机均匀地部署在500 m×500 m的监控区域，节点通信遵循UDG(Unit Disk Graph)双向通信模型。传感器节点数量从1 000增加到10 000，每次增加1 000，调整节点的通信范围使节点的平均邻居数目为d=40。采用贪婪转发机制的地理路由协议进行数据包转发［14］，在仿真实验中仅仅考虑两个克隆节点存在的情况，两个克隆节点随机部署在网络监控区域之中，对每组参数，仿真实验运行100次，并将实验结果的平均值作为最终结果。

区域单元规模s设定为一个节点广播所能播送的绝大部分范围，设m表示区域单元的数量，为体现实验公平性，m取值与文献［7］一致.

其中l为表示无线传感网络的边长度;R为节点通信范围;round()是四舍五入取整数函数;对区域单元中广播覆盖不到的区域采用单点播送，d为节点的平均邻居数目;n为无线传感网络的规模即包含的传感节点数量。

设lcell为区域单元的边长度，则节点申明映射到区域单元后，数据包沿着水平和垂直两个方向同时储存转发的最大距离不超过lcell跳，将映射到区域单元的数据包生命周期设为TTL=lcell=时，区域内冲突节点位置申明产生碰撞的概率为100%。

图2 区域映射冲突概率图

仿真实验也实现了LSM协议和P-MPC协议，协议的参数设置与Parno［3］和Zhu［7］论文中的设置一样。LSM协议平均每个节点有40个邻居节点，邻居节点的独立转发概率P为6/d。P-MPC协议的ps= 0.2、pf=3/d、v=3，即区域单元内的每个节点储存位置申明的概率为0.2，邻居节点转发概率为3/d。

节点复制检测率是指在复制节点存在的情况下，检测到复制节点的概率，是协议评估主要指标。图3显示了LSM协议、RMC协议和P-MPC协议在不同网络规模下对节点复制检测率的比较情况，RMC协议节点复制平均检测率比LSM协议高24.4%。主要原因在于LSM实现的是线相交的检测机制，当出现两线相交点刚好没有传感器节点的情况时则检测失效，而RMC采用面相交检测机制，一个面以水平或垂直轴上检测节点为中心，和一跳邻居节点构成检测面，使检测100%成功。同时RMC协议节点复制平均检测率比P-MPC协议略高5.1%。

图3 复制节点检测率比较图

通信开销是运行一轮协议平均每个节点发送和接受数据包的总数量。如图4所示，相对于同样实现随机检测的RM协议，RMC的通信开销显著减少。与其他二个协议相比较，RMC协议的通信开销初始时低于SLM协议和P-MPC协议，在网络2000节点规模时逐渐大于SLM协议和P-MPC协议，随着网络规模的增大通信开销的差距越来越大。主要原因是RMC采用随机验证机制，为保证较高检测率，映射区域数量保持在O()个，网络规模越大映射区域数量越多，而P-MPC是确定性验证方案的变形，其区域映射是在保持固定数量的确定区域内再进行随机选择映射，映射区域数量不会随网络规模增大而增多。

耗尽能量节点百分比是能量耗尽节点占全部节点的比值，耗尽能量节点百分比随协议运行轮数变化而变化的情况如图5所示，其中RMC协议的耗尽能量节点百分比明显比P-MPC和LSM协议的耗尽能量节点百分比低，在协议运行300轮后，RMC协议的节点存活率为54%，LSM协议的节点存活率为46%，P-MPC协议的节点存活率为22%。主要原因是RMC协议的验证节点随机选择，其能量消耗均衡，避免局部流量集中使局部节点过早消亡从而延长网络的生命期。

图4 通信开销比较图

图5 网络中耗尽能量节点百分比随轮数变化图

5 结束语

本文在节点复制检测RMC协议中将随机区域单元选择映射和局部区域单元内随机线选验证节点相结合，实现能防御节点复制智能攻击的随机验证机制，增强协议的安全性。与SLM协议和P-MPC协议比较有较高节点复制攻击检测率。仿真实验设置为均匀规则的拓扑环境，在今后的工作中，将进一步模拟不规则非均匀节点分布的网络拓扑，使协议更接近真实应用。

［1］朱世才，王海涛，陈磊，等.战场环境中基于簇的WSN生存性路由协议［J］.传感技术学报，2013(10):1426－1431.

［2］徐军.无线传感器网络恶意节点攻击若干问题研究［D］.安徽:中国科技技术大学，2012.

［3］Parno B，Perrig B，Gligpr A.Distributed Detection of Node Replication Attacks Sensor Networks［C］//Proceedings of the 2005 IEEE Symposium on Security and Privacy Washington D C.USA［s.n.］.2005:49－63.

［4］Khan W，Aalsalem M.Detection and Mitigation of Node Replica-tion Attacks in Wireless Sensor Networks:A Survey［J］.International JournalofDistributedSensorNetworks，2013，2013: 1－22.

［5］Zhu W T.Detecting Node Replication Attacks in Wireless Sensor Networks:A Survey Review Article［J］.Journal of Network and Computer Applications，2012，35(3):1022－1034.

［6］Conti M，Di Pietro R，Mancini LV，et al.A Randomized，Efficient，Distributed Protocol for the Detection of Node Replication Attacks in Wireless Sensor Network［C］//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc’07);2007:80－89.

［7］Zhu B，Setia S，Jajodia S，et al.Localized Multicast:Efficient and Distributed Replica Detection in Large-Scale Sensor Networks［J］.IEEE Transactions on Mobile Computing，2010，9:913－926.

［8］Zeng Y，Cao J，Zhang S.Random Walk Based Approach to Detect Clone Attacks in Wireless Sensor Networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(5):677－691.

［9］Ho J W，Wright M.Fast Detection of Mobile Replica Node Attacks in Wireless Sensor Networks Using Sequential Hypothesis Testing［J］.IEEE Transactions on Mobile Computing，2011，10(6):767－782.

［10］Lou Y，Zhang Y.Single Hop Detection of Node Clone Attacks in Mobile Wireless Sensor Networks［C］//Proceedings of the International WorkshoponInformationandElectronics Engineering (IWIEE)，Harbin China，10－11 March 2012:2798－2803.

［11］Hess F.Efficient Identity Based Signature Schemes Based on Pairings［C］//Proc Ninth ANN Int’l Workshop Selected Areas in Cryptography(SAC’02).2002:310－324.

［12］章春华，陈宏伟.LEACH协议簇头选择算法的改进与研究［J］.湖北工业大学学报，2012，27(2):19－22.

［13］赵灿.无线传感网络中路由算法的研究及实现［D］.浙江大学，2013.

［14］汪治理，章勇，刘红.一种基于代码克隆检测技术的WSNs重编程方法［J］.传感技术学报，2013(9):1288－1292.

周豫苹(1976－)，女，福建人，闽南师范大学副教授，博士，主要研究方向为计算机网络、信息安全，yp_zhou@mnnu.edu.cn。

一类新的分布式随机验证无线传感网络节点克隆攻击检测*

周豫苹1*，黄振杰1，王娟1，陈东2
(1.闽南师范大学计算机学院，福建漳州363000;2.中国电信股份有限公司漳州分公司，福建漳州363000)

由于无线传感器网络节点的无人值守性，攻击者很容易捕获并复制节点，利用节点的安全证书把复制节点发布到无线传感器网络的各个角落，进而秘密发动各种攻击。提出一类新的分布式节点复制攻击检测协议，协议采用随机区域单元映射和域内随机线选验证相结合的方法进行攻击检测。仿真结果显示，协议的随机验证特性使网络能量消耗均匀，延长网络的生存周期。域内线选验证使协议的通信开销和储存开销较低并具有较高的检测率。

网络安全;无线传感器网络;节点克隆攻击;多区域单元;随机验证

TP393.08

A

1004－1699(2014)04－0544－07

2014－01－01修改日期:2014－04－02

C:7230;6150p

10.3969/j.issn.1004－1699.2014.04.022

项目来源:国家自然科学基金项目(61170246);福建省自然科学基金项目(2012J01295);福建省教育厅科技基金项目(JA11170)