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