Sybil攻击防范算法研究＊

詹 杰，刘宏立，刘述钢

（湖南大学电气与信息工程学院，湖南长沙 410082）

Sybil攻击防范算法研究＊

詹 杰†，刘宏立，刘述钢

（湖南大学电气与信息工程学院，湖南长沙 410082）

针对无线传感器网络Sybil攻击的安全性威胁问题，分析了其攻击原理和现有的防范算法.提出了一种分散式防范算法，分别采用测量一致性、测量与计算一致性2种方法对攻击节点进行检测.该算法改变了传统集中式防范算法的思路，并能滤除攻击生成的虚节点.仿真和实验结果表明，该算法对Sybil攻击有很强的针对性，能达到99%的虚节点滤除率，并且有很好的鲁棒性.

Sybil攻击；无线传感器网络；攻击防范；测距

无线传感节点的资源受限和网络通常部署在无人维护、不可控制的环境中，使得无线传感器网络的安全问题变得非常重要.Sybil是存在于WSN或自组网中一种恶性病毒，是无线传感器网络中非常有害的攻击方式中的一种，它表现为在网络层使一个攻击节点非法地以多种身份出现，从而对网络的定位、路由等一些协议和应用产生破坏［1］.Sybil有多种攻击形式和手段［2］，可以总结为：一个身份多个地理位置、多个身份一个地理位置和多个身份多个地理位置［3］.

近年来，如何防范与检测Sybil攻击受到越来越多学者的关注.目前国内外研究的防御和检测措施主要有4种［4－6］：第1种是基于地理定位的检测方法［7－8］，这种方法通过准确的地理定位来检测攻击，但需要全局坐标.第2种是基于密钥系统进行身份验证的方法，如Boneh等［9］提出基于身份的加密方法，Zhang等［10］提出的节点对间的互相认证协议等，这类算法的计算量都较大，不太适合能量有限的无线传感器网络.第3种是通过检测节点各种资源来检测攻击的方法，如Newsome等［11］提出的分配信道射频测试，但如果攻击者资源更强，方法将失效.第4种是基于可靠的验证中心对节点身份进行验证，如果验证中心被攻破，整个网络将失去防护.本文针对Sybil攻击的特点提出了一种新的分散式防范算法，将网络中的正常节点都参与到算法验证中来，能高效地检测到Sybil攻击，并能滤除Sybil攻击生成的虚节点，保证网络安全.

1 Sybil攻击防范算法

1.1 预备知识

假定网络中所有正常节点的通信都是双向的，采用全向天线，网络密度一般（通信范围内10个以上节点），节点分布在二维平面内，采用基于RSSI测距的定位协议，算法符号定义如下：

V为发起测距的节点；Nbr（v）为由v的邻居节点组成的集合；Pk为节点k在实平面上的位置；N为邻居节点的数目；M为交互进行RSSI测量的节点数目；Dij为节点i和j的实际距离；dij为节点i和j的测量距离；Cij为节点i和j的计算距离.

定义1 若节点仅知道它与邻居节点的距离，而不知道邻居节点的位置，则节点无法确定自己的位置.

证明略.

Sybil攻击将产生不存在的虚节点，攻击能否生效，取决于正常节点是否确认这些不存在的虚节点.算法将从节点是否拥有合法位置来判断是否为虚节点.图1为算法表述示意图，由图1可知，在二维坐标中，将相邻的邻居节点之间的距离作为输入，节点的位置作为输出，如果攻击生成Sybil节点，通过我们的算法，在二维平面上很难生成合适的Sybil节点的位置信息，测距数据的输入只会导致更高维的位置信息输出，则这样的节点是Sybil节点，可以滤除.

图1 算法表述示意图Fig.1 Schematic representation of the algorithm

1.2 Sybil攻击防范算法

算法分为2阶段：安全测距阶段和滤除Sybil节点阶段.在第1阶段，每个节点使用安全测距算法测量它和邻居节点的距离.在第2阶段，创建平面，经过安全测距后，每个节点都将和邻居节点中测距一致性的节点连接成簇，在该集合中选择包含节点最多的簇，这个簇所在的平面即为排除了Sybil攻击的簇平面.

1.2.1 安全测距算法

安全测距算法可以运用多种测距技术，这里我们采用RSSI测距.

第1步 RSSI强度信号加密发送.簇头节点首先以全功率发送射频信号给所有邻居节点u∈Nbr（v），通知发起测距操作，然后邻居节点相互之间开始测距操作，节点v以一个随机的RSSI强度ptx发送测距包给节点u，接收节点u记录接收到的功率值puv.

在预定时间内或者是收集了Nbr（v）中每个节点的射频强度信号后，采用对称加密协议，用随机的密钥k加密ptx，对每个u∈Nbr（v）的节点，u广播这个加密包给邻居节点，直到u∈Nbr（v）中所有节点都相互进行了测距包的加密接收操作，邻居节点中有些非法节点不能对加密的测量数据包作回复，将会排除出u∈Nbr（v）集合.

第2步 RSSI解密测量.Nbr（v）中的节点在预定时间内或者是收集了邻居节点加密的信息后，解密k.收到Nbr（v）中每个节点的密钥k后，可分别解密出邻居节点的ptx，在一个簇内，节点相互之间结合测距公式计算出与邻居节点的距离dij.收集了邻居节点的距离信息以后，Nbr（v）中节点比较收集到的数据，在误差范围内有｛dij｜dij＝dji，i，j∈Nbr（v），i≠j｝，则保留节点i，j以及这两个节点之间的测量数据.

安全测距算法阻止了部分Sybil节点计算与邻居节点的距离，若只知道自已的puv值，而不知道ptx值，则无法计算距离.而知道ptx值则需要解密算法和密钥k，故一部分Sybil节点将无法完成测距操作.

1.2.2 Sybil节点滤除算法

安全测距算法并不能很好地滤除Sybil节点，这只是算法的第一道屏障.它只对两个点之间作了测距处理，而RSSI测距有较大的误差，一些Sybil节点完全可能生成误差范围以内测距数据.在定义1的基础上，我们提出Sybil节点滤除算法.

经过安全测距算法后，节点v随机选取两个邻居节点i和j确定一个平面（这里的邻居节点是指能通过安全测距算法的节点），由这3个节点、3个边建立本地的坐标系统L，在节点v的坐标系统中，我们用G（V，E）来构建集合，V表示节点v和它的邻居节点集合，E表示集合内任意两个节点之间测量距离和计算距离一致的节点的集合.最初，G为空集，G更新过程为：对每个邻居节点k∈Nbr（t），计算节点的k位置Pk（邻居节点k的位置通过v，i，j3个节点用三边测量法确定，采用坐标系统L中的测量距离dkv，dki，dkj）.

对任意节点i，j∈Nbr（t），找出i，j之间的测量距离dij，并根据它们在该坐标系的坐标，求出两点间的计算距离，如果，则可将这两个点的链路边e（i，j）加入E中.

由这3个发起定位节点所形成的G（V，E）集合用簇C来表示，此时的V是测量与计算一致性的邻居节点的集合，E为测量与计算一致性的节点链路的集合.

对V中每个邻居节点都重复进行该算法，将形成多个簇C的集合，找出其中最大的簇C，此时簇C就为滤除了Sybil节点的簇.

1.2.3 算法证明

定义2 在集合G（V，E）中，如果随机选择创建簇的顶点都是实节点，那么经过算法处理后所选择的簇C中不会有Sybil节点.

证 图2为滤除Sybil节点示意图.由图2（a）可知，节点v在位置P1，选择了两个在P2，P3位置的实节点，以v为簇头组建簇C.经过安全测距算法后，E中将包含符合条件的邻居节点之间的链路.因为事先攻击节点并不知道3个创建簇顶点的坐标位置，根据定义1，它无法生成与这3个节点达成测量一致性的Sybil节点位置，生成的位置只有可能是原攻击节点位置或不在该平面上的位置，这样的Sybil节点将无法进入簇内，它只会出现在平面P，上，不会到簇C中来，所以由正常节点组成的簇平面C中不会有Sybil节点.

图2 滤除Sybil节点示意图Fig.2 Schematic of filtering the Sybil nodes

定义3 如果发起平面定位所选的顶点至少有一个虚节点，那么经过算法后所形成的簇平面C中所含节点的数比全由实节点发起所形成的簇平面C所含的节点数要少.

证 由图2（b）可知，节点v在位置P1和其他两个位于P2，P3的节点创建了平面P，，其中至少有一个是Sybil节点，假设P2是Sybil节点，在平面P，上形成簇C，.由于P2是Sybil节点，那么很多实节点和P2将有不一致的测量距离，将会被排除出簇C，，C，中只会存在和P2共谋的Sybil节点以及误差范围内的实节点.一般情况下，网络中实节点数要大于虚节点数，在实平面P上的簇中所包含的实节点都能满足算法一致性的要求，所以C中所含的节点数将大于簇C，中所包含的节点数.

如果在平面P，上Sybil节点数大于合法节点数，而且攻击节点产生的Sybil节点能达成测量一致性，那么在平面P，上，簇C，中的节点数大于实平面C中的节点数，但出现这种情况的概率很小，因为发起定位的节点v，P2，P3是随机选择的，攻击节点生成的Sybil节点不一定都会在某一个平面P，上，并且满足相互之间的测距一致性要求.因此，在簇C，中所含节点数小于簇C所含节点数的概率很高.

1.2.4 算法特例说明

我们提出的Sybil防范算法由正常节点发起操作.但如果由Sybil节点发起操作，并且建立一个簇平面，如图2（b）所示的P，平面，而且Sybil节点数足够多，那么该平面可经过防范算法保留下来，在该平面上的正常节点将被欺骗，但是，这种欺骗的影响只会发生在实平面和虚平面的交线上，因为实节点总会在自己的实平面上.同理，还有一些实节点也可能被另外的虚平面欺骗，同样处于两个平面的交线上.这个情况说明，即使Sybil攻击得逞，它也仅仅能损害分布在两个面相交线上的节点.假定有n个实节点在实平面P，没有3个节点是共线的，Sybil要能生效，虚节点的数量至少要超过3C2n个，这将比实节点的数量大得多，代价将会很大.这说明了该算法在大量Sybil节点存在的情况下也能工作.

2 算法仿真与实验

图3为算法效果仿真示意图.我们设计了15个随机分布的节点仿真（见图3（a）），其中大圆形点为恶意节点，攻击生成了10个不存在的Sybil节点（见图3（b）），这些Sybil节点由一个攻击节点生成，相互之间可以合谋攻击而组成簇平面，实节点可通过算法创建簇平面，组成的2个平面如图3（c）所示，两平面经过算法后合并.由于Sybil节点和实节点除攻击点之外，节点之间不会有正确的测距信息，所以两个簇将进行节点数量的比较，最终生成的簇平面如图3（d）所示，除了攻击节点外，Sybil节点都被滤除，Sybil攻击不会产生后果.

图3 算法效果仿真示意图Fig.3 Sketch of simulation effect of the algorithm

2.1 实验验证

在100 m×100 m的区域内（见图3（a）），随机分布15个节点.我们设计如下实验：采用CC2430射频模块，通过RF寄存器TXCTRLL中PA-LEVEL控制0xF7，0xFB，0xFF三级输出功率，对应的通信变化为55～80 m.恶意节点生成了10个Sybil节点，随机分布在这个区域内（用随机函数生成坐标，然后根据坐标布置节点），每个Sybil节点都有自己的位置，但是发布RSSI信息的只有一个攻击节点.一共设计了10组实验（采集了1.6万个RSSI信号），每一组实验保持普通节点的位置不变，但产生的Sybil节点位置变化，重复10次，得到如图4所示的实验结果（这里设计的误差门限值ε为10 m）.

由图4（a）可知，算法的效率很高，一组10次实验，Sybil攻击共产生100个Sybil节点，绝大多数Sybil节点都能被滤除，最多的一组也只留下8个Sybil节点（如果门限值设置小一点，效果会更好，当然，也会有一部分正常节点会由于测距误差被误滤除）.

由Sybil滤除算法可知，Sybil攻击要影响正常节点必须一次有3个以上的虚节点组成一个虚平面，上述实验中，其攻击生效的结果如图4（b）所示.在100次实验中，只有一次影响了18%的实节点的位置，从而产生攻击后果.

3 算法性能分析

3.1 滤除算法重复次数讨论

图4 针对Sybil攻击实验结果比较图Fig.4 Algorithm results against the Sybil attack

若所选择三边定位的顶点都是实节点，则只要运行一次就能滤除Sybil节点；若所选的顶点中有Sybil节点，则需要重复多次进行比较，找出最大的簇，这样才能滤除虚节点.即算法的重复次数i和实虚节点的比例相关.

假定q是t的邻居节点，而且是Sybil节点的概率，那么至少一个顶点是虚节点的概率是1－（1－q）2，在运算过程中，选择的顶点都是实节点的概率为1－（1－（1－q）2）i.图5为Sybil节点的比例、迭代次数以及滤除成功率的关系图，图6为特定滤除成功率下迭代次数和Sybil节点比例的关系图.由图5和图6可知，当Sybil节点数量占的比例较小时，重复算法很少次就能达到很高的滤除率；当Sybil节点数量占的比例较大时，则需增加反复运行的次数.由图6可知，即使50%的节点是Sybil节点，重复的次数也只需要16次就能达到99%的虚节点滤除率.

图5 Sybil节点比例、迭代次数以及滤除成功率关系图Fig.5 The relation of repetition times，proportion of Sybil nodes and filtration ratio

3.2 门限值讨论

对Sybil节点的滤除主要通过测距一致性来实现，设定的门限值对算法的影响很大.若取的门限值小，则Sybil节点的滤除率高，但同时，一部分正常节点也将被滤除.因此，必须综合考虑测距误差门限值的影响.

图6 特定滤除成功率下Sybil节点比例和迭代次数关系图Fig.6 The relation of proportion of virtual node vs the number of iterations under special filtering ratio

对本次实验1.6万个数据的误差范围的分布情况做了统计，得到了实节点和Sybil节点在同样环境下测距误差值的分布情况，如图7所示，正常节点的测距误差变化比较平缓，门限值的选取对其影响不大，即使门限值设定为射频通信距离的30%，被算法误滤除的正常节点比例为0.05～0.22，而此时Sybil节点的滤除率为0.2～0.98，门限值的设定范围能完全满足实用要求.

图7 测距误差分布图Fig.7 Ranging error distribution

4 结 论

本文提出的Sybil安全算法有别于现有的集中式验证方式，该算法采用无中心节点的分散验证方式，实验结果证明该算法的效果很好，虽然出现了一次影响18%正常节点的定位，但这并不意味Sybil攻击就会得逞，因为Sybil节点簇不一定是节点数最多的簇.在没有中心节点的情况下，算法本身的安全性也能得到保证，算法过程简单，部分算法（点对点部分）在CC2430芯片上已经实现.

当然算法还存在一定的局限性，可调的RSSI测距会造成邻居节点数和安全算法的邻居节点数目不一致，会漏掉对部分实节点的保护.虽然可采用TDOA等另外的测距方法来解决该问题，但同时也会引入成本过高，超声信号区分难等问题.实际中WSN还要面对更多的恶意攻击，但提出的分散验证的方法将是无线传感器网络安全的一种新的思路，在今后的工作中，将对其做进一步完善.

［1］ MAINWARING A，POLASTRE J，SZEWCZYK R，etal.Wireless sensor networks for habitat monitoring［C］／／Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.Atlanta：University of Southern California，2002：88－97.

［2］ LEVNEB N，SHIELDS C，MARHOLINN B.A survey of solutions to the sybil attack［R］.Amherst：University of Massachusetts Amherst，2006.

［3］ 余群，张建明.无线传感器网络中的Sybil攻击检测［J］.计算机应用，2006，26（12）：2897－2899.

YU Qun，ZHANG Jian-ming.Sybil attacks detecting in wireless sensor networks［J］.Computer App Lications，2006，26（12）：2897－2899.（In Chinese）

［4］ KARLOF C，WAGNER D.Secure routing in wireless sensor networks：attacks and counter-measures［C］／／First IEEE Int Workshop on Sensor Network Protocols and Applications（SNPA 2003）.Anchorage，AK，USA：IEEE Computer Society，2003：113－127.

［5］ DOUCEUR J R.The Sybil attack［C］／／First International Workshop on Peer-to-Peer Systems.Cambridge，MA，USA，2002：251－260.

［6］ DEMIRBAS M，SONG Y.An RSSI-based scheme for Sybil attack detection in wireless sensor networks［C］／／Proceedings of the 2006 International Symposium on World of Wireless.Washington DC，USA：Mobile and Multimedia Networks，2006：564－570.

［7］ 张建明，于群，王良民.基于地理信息的传感器网络Sybil攻击检测方法［J］.系统仿真学报，2008，20（1）：259－263.

ZHANG Jian-ming，YU Qun，WANF Liang-min.Geographical location-based scheme for Sybil attacks dectection in wireless sensor networks［J］.Journal of System Simulation，2008，20（1）：259－263.（In Chinese）

［8］ 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2005，16（5）：857－868.

WANG Fu-Bao，SHI Long，REN Feng－yuan.Self-localization systems and algorithms for wireless sensor networks［J］.Journal of Software，2005，16（5）：857－868.（In Chinese）

［9］ BONEH D，LYNN B，SHACHAM H.Short signatures from the weil pairing［C］／／Proceedings of the 6th Inter-national Conference on Theory and Application of Cryptology and Information Security.Kyoto，Japan，2000：514－532.

［10］ZHANG Qing-hua，WANG Pan，REEVES D S，etal.Defending against Sybil attacks in sensor networks［C］／／In Proc of the 25th IEEE International Conference on Distributed Computing Systems Workshops.USA：IEEE Press，2005：185－191.

［11］NEWSOME J，SHI E，SONG D，etal.The Sybil attack in sensor networks：analysis and defenses［C］／／Proc of Third Int Symposium on Information Processing in Sensor Networks（IPSN＇04）.Berkeley，California，USA：ACM Press，2004：259－268.

Study of the Guarding Algorithm against Sybil Attack

ZHAN Jie†，LIU Hong-li，LIU Shu-gang

（College of Electrical and Information Engineering，Hunan Univ，Changsha，Hunan 410082，China）

The increasing application of WSN（Wireless Sensor Network）brings forward higher and higher requirements on the security of the network.The Sybil is one of the multitudinous security attacks that WSN has to face now and is one of the most ruinous.Based on the analysis of its attacking principle，a type of dispersing guarding algorithm linked with network localization was proposed.The algorithm was used for the measurement of the consistency and the calculation of two methods for the detection of attack nodes，which is different from the traditional centralized guarding mode.The emulation of the algorithm and the experiment results indicate that the algorithm has very good pertinence and robustness against Sybil attack.

Sybil attack；wireless sensor networks；attack defense；ranging

TP919.2；TP915

A

1674-2974（2011）06-0079-05＊

2010-09-20

国家自然科学基金资助项目（50807011）；湖南省科技厅计划资助项目（2010FJ4068）；中科院上海技术物理所红外重点实验室项目（201021）

詹 杰（1973－），男，湖南常德人，湖南大学博士研究生

†通讯联系人，E-mail：Jiezhanwl＠163.com