基于邊聚類的電力通信網Sybil攻擊檢測算法

黨曉婧， 張 林， 呂啟深， 彭 浩， 張柏松

(1. 中國南方電網有限公司 深圳供電局電力科學研究院， 廣東 深圳 518000； 2. 深圳康托普信息技術有限公司 業務研究中心， 廣東 深圳 518034)

為了保障電力系統安全、穩定運行，電力通信網需要制定一系列的安全措施，防止來自電力系統外部與內部的攻擊.電力系統遭受的攻擊行為不但包含專門針對電力控制系統的攻擊行為，也包含一些適用于互聯網與社交網絡的通用攻擊方法.在這些通用的攻擊方法中，Sybil攻擊是一種廣泛應用的攻擊算法，Sybil攻擊又稱為女巫攻擊，其基本思想是利用網絡中少數的通信節點控制數量較大的虛假身份，再使用大量的虛假身份對其他正常的通信節點發起攻擊.該攻擊最早起源于點對點的通信網絡攻擊，廣泛應用于社交網絡和互聯網等攻擊方法中.針對Sybil攻擊的檢測與預防，國內外的學者做出了大量的研究，其中，Yu等[1]提出了SybilGuard算法，檢測可疑節點是否為攻擊源頭；隨后，其又提出了分散式SybilLimit算法[2]，利用隨機路徑末尾區分合法節點與可疑節點，從而減少了假陰性檢測結果的數量.眾多學者在此基礎上，做出了較多具有標志性的科研成果，然而，這些檢測算法均存在檢測精度較低或計算復雜度較高等缺點，不適用于大規模網絡中Sybil攻擊的檢測.

針對這一關鍵問題，本文在詳細分析Sybil攻擊方法的基礎上，通過引入邊介數和K-means邊聚類算法，提高Sybil攻擊的檢測效率，從而分離邊介數較高的攻擊邊.在此基礎上，利用標簽權值檢測得到Sybil攻擊的發起節點，最終完成Sybil攻擊的檢測.

1 邊介數計算

一般而言，邊介數定義為當前邊的最短路徑與網絡圖中所有最短路徑的數量比值.目前，經典算法計算介數的時間較長，難以應用于大規模網絡[3-5].本文提出了一種邊介數的計算算法，網絡中有一個節點a，不妨設起始節點為s，目標節點為t，則其介數中心性的定義如下：

1) 對于一個網絡G(V，E)，文中統一使用G表示網絡圖，V和E分別表示網絡的頂點集和邊集.節點a∈V的介數中心性CB(a)的計算公式為

(1)

2) 對于網絡G(V，E)，邊l的邊介數中心性WB(l)的計算公式為

(2)

3) 設ρ為從節點s到節點v的路徑，R(ui)是ui的鄰居節點集合，P[ρs，v]是從節點s把節點v作為下一個節點的概率，則頂點h的k路徑邊介數中心性Wk(h)的計算公式為

(3)

(4)

(5)

在大規模網絡中，為了充分利用邊介數的性質，本文引入隨機游走策略，提出恰當的邊介數計算算法，其流程描述為：

1) 輸入為網絡G(V，E)，迭代輪數T，隨機路徑長度L，邊的權值系數β，輸出邊介數參數S；

2) 初始化邊介數參數S=0，計算所有節點權值分配值，所有邊權值分配值；

3) 若i≤T，步長計數器N=0，選取起始節點；

4) 若步長計數器N≤L，且其鄰接邊集合元素數量大于標記值，則重復執行這些程序；

5) 將所有邊的標記值置為0；

6) 對于所有的邊，設定邊介數參數分配值，同時，返回其邊介數參數值.

2 邊聚類算法

利用邊介數算法能夠實現真實邊與可疑邊的初步分離[6].為了進一步鑒別可疑邊中的真實用戶，同時克服傳統K-means算法易受干擾的缺點，基于隨機游走邊介數的特征[7-8]，本文使用優化初始化中心和存儲的方法，對傳統K-means聚類算法進行必要的改進，從而更加精確地檢測攻擊邊.

2.1 算法改進

在介紹算法改進策略前，需要引進邊聚類系數的概念.邊聚類系數衡量了網絡中任意兩個節點之間的緊密關系程度[9-10].對于一個網絡G(V，E)，邊e∈E，邊的頂點為q和h，則e的邊聚類系數C(e)的計算表達式為

(6)

式中，C(q)與C(h)分別為頂點q和h的聚類系數值.

在傳統K-means算法中，初始中心點對聚類結果的影響較大[11]，因此，如何選擇更恰當的初始中心點，盡量將初始中心點分布于不同的類簇中是優化K-means算法的重要策略.本文對于初始中心點的選取步驟如下：

1)隨機選擇網絡G(V，E)中的一個邊，將這個邊的數據點設定為中心點；

2) 對于已知的數據點，計算和存儲該點與其鄰近中心點的最小距離di，把這些距離相加可得D；

3) 選取某個點的中隨機值r∈[0，D]，重復將中隨機值r累加到最小距離di中，直至r>D，此時，該點即為下一個中心點；

4) 反復執行步驟2)～3)，直至中心點的個數達到聚類數.

選取初始中心點的算法需要頻繁存儲與查詢最小距離數據，這也是傳統K-means算法待優化之處.為了解決這一問題，本文使用鍵值的形式，存儲邊到邊索引信息與中心點之間的距離信息.

通常每個中心點需要存儲邊索引、邊介數和邊聚類系數等信息[12].其中，中心點之間的距離可以用邊介數與邊聚類系數計算獲取，因此，本文使用拉鏈法存儲邊到邊索引和距離信息.例如，中心點0～1之間的邊為0，這兩點之間的距離為0.23，則存儲為(“0～1”，0.23).

若需要增加一個存儲元素，則使用鍵值信息生成散列碼，獲取數組的索引.若產生沖突，則令新元素的引用指向與其沖突的元素，使用單鏈表的形式處理沖突；若需要查詢某一個鍵值信息，則使用該存儲結構快速查找到某個中心點的信息，從而提高存儲與查詢的效率.

2.2 算法步驟

利用優化初始中心點的選取策略與中心點距離的存儲方法[12-13]，本文提出了基于K-means的邊聚類算法，其具體執行步驟為：

1) 選取K個初始中心點；

2) 按照K個初始中心點，將所有網絡節點劃分到距離其最近的中心點所屬類別中；

3) 對于所有類別，計算其數據平均值，生成新的中心點；

4) 使用新的中心點，繼續對所有的數據點進行劃分；

5) 反復執行步驟3)～4)，直至劃分結果收斂，同時返回最后的聚類結果.需要說明的是，該聚類算法需要頻繁地計算某個網絡節點(x，y)到中心點(x0，y0)的距離.

3 團體檢測算法

利用邊介數和邊聚類的計算算法可以檢測得到所有的可疑邊.為了進一步精確地檢測攻擊邊，文中提出了一種基于標簽權值的團體檢測算法.該算法以網絡圖G(V，E)和可疑邊集合為輸入，輸出只包含實施Sybil攻擊的節點集合.基于標簽權值的檢測算法基本思想為：通過更新種子集節點的標簽，令所有節點的標簽傳播值達到最大.

與傳統的標簽傳播算法相比[14]，本文使用異步的方式更新標簽，設迭代輪數為i，起始節點是s，其鄰近節點主要有(sj1，…，sjm，sj(m+1)，…，sjk)，則其標簽選擇函數Zs(i)表達式為

Zs(i)=f(Zsj1(i)，…，Zsjm(i)，

Zsj(m+1)(i)，…，Zsjk(i))

(7)

由式(7)可知，第i輪的迭代標簽由第i-1輪、鄰近節點(sj1，sj2，…，sjm)第i輪和鄰近節點(sj(m+1)，sj(m+2)，…，sjk)第i-1輪的標簽狀態決定，而函數f的功能是選擇影響力最大的標簽.在將節點變化的擴散過程中，本文需要頻繁地更新網絡中的頂點標簽.起始節點為s，其鄰近節點標簽為m的標簽傳播值為mp(m)，則其標簽更新表達式為

(8)

式中：C(mi)為鄰近節點標簽為m的邊聚類系數；N(m)為標簽為m的節點個數；∑deg(mi)為標簽m的頂點度數之和.基于標簽更新的表達式，s的標簽選擇函數M(s)為

M(s)=arg maxmp(m)=

(9)

團體檢測算法的具體步驟為：

1) 利用邊聚類結果，構造種子集；

2) 根據節點度的大小，對所有節點進行從大到小的排序；

3) 按照步驟2)的順序結果，使用式(8)更新所有節點的標簽；

4) 測試所有節點的標簽傳播值是否最大，若是，則算法終結，返回結果；否則，反復執行步驟3)～4).

4 仿真驗證與分析

為了驗證攻擊檢測算法的有效性，本文利用不同規模的數據集，分別對攻擊檢測算法與SybilLimit算法進行仿真.此外，文中還詳細地對比分析了這兩種算法的仿真結果.

4.1 仿真數據與環境

本文選用來自Amazon的通信網絡數據集，Amazon數據集擁有335 874個通信節點和924 589條邊.對該通信網絡的數據集進行一定的擴展和操作，即可得到本文的實驗數據集.其具體的過程描述為：從真實數據集中，隨機選取被攻擊節點，與Sybil節點共同構成攻擊邊，然后利用PA(preferential attachment)模型構造實驗所需的拓撲結構.

此外，在仿真實驗中，Sybil攻擊節點的數量分別被設置為10 000、6 000和1 000，攻擊路徑數量分別設定為20～90.使用的軟件開發工具為MyEclipse 9.0，編程語言是Java，硬件配置為Intel Core i7-4790處理器.

4.2 評價指標

為了準確地評價攻擊檢測算法和SybilLimit算法的效果，本文使用假負率和模塊化度量等指標進行評價.設ntp是檢測得到的真實攻擊節點數量，nfn是被檢測為合法節點的攻擊節點數量，則假負率Rfn的計算表達式為

(10)

此外，令x代表已劃分團體，X為總團體的數量，ec為團體x中邊數量，qc為團體x到其他團體的邊數，A為所有邊的數量，則模塊化度量Q的計算表達式為

(11)

4.3 仿真結果與分析

在上述仿真數據集與軟硬件環境下，本文對攻擊檢測算法和SybilLimit算法進行仿真.兩種算法在不同節點下的假負率仿真結果如圖1～3所示.

圖1 10 000個Sybil攻擊節點時假負率仿真圖Fig.1 Simulation of false negative rate with 10 000 Sybil attack nodes

圖2 6 000個Sybil攻擊節點時假負率仿真圖Fig.2 Simulation of false negative rate with 6 000 Sybil attack nodes

圖3 1 000個Sybil攻擊節點時假負率仿真圖Fig.3 Simulation of false negative rate with 1 000 Sybil attack nodes

由圖1～3可知，在算法與模型相同的情況下，隨著攻擊路徑數量增加，假負率Rfn先降低，再逐步提高.其主要原因是在攻擊路徑增加的時候，Sybil攻擊的群體特征逐漸顯現，而當攻擊路徑數量小于40的時候，由于群體特征不夠明顯，所以算法的檢測難度較高，隨著攻擊路徑數量的增加，算法的檢測難度降低，此時假負率Rfn也逐漸減少；當攻擊路徑數量超過40之后，通信網絡將遭受更多攻擊，其攻擊種類也在大量增加，這直接導致算法檢測攻擊的難度增加，同時假負率Rfn也逐漸提高.在路徑數量與模型相同的情況下，本文攻擊檢測算法的假負率Rfn顯著低于經典SybilLimit算法，其主要原因是本文攻擊檢測算法的設計保留了經典SybilLimit算法的優點，同時避免了經典算法存在的缺點；由圖1～3的比較可知，所提攻擊檢測算法和經典SybilLimit算法隨著攻擊節點的增加，其檢測效果也更加優秀.這表明，本文的攻擊檢測算法適用于大規模網絡的攻擊檢測，而且其假負率指標水平低于經典SybilLimit算法.

在10 000個Sybil攻擊節點和PA模式下，本文還統計了SybilLimit算法和攻擊檢測算法的模塊化度量指標，其指標隨路徑數量變化的統計結果如圖4所示.

圖4 模塊化度量仿真結果對比Fig.4 Comparison of simulation results for modularity measurement

一般而言，模塊化度量主要衡量網絡結構強度，該指標越大，表明算法的團體檢測結果更加準確.根據圖4可知，本文攻擊檢測算法和經典SybilLimit算法的模塊化度量指標隨著攻擊路徑的增加而提高，而在各種相同的外部條件和路徑數量下，本文攻擊檢測算法的模塊化度量指標要大于經典SybilLimit算法，這些仿真結果進一步表明，本文提出的算法具有更加優秀的團體檢測結果.

綜合假負率和模塊化度量的對比結果可以看出，文中提出的攻擊檢測算法的表現優于經典SybilLimit算法，這是因為文中提出的攻擊檢測算法使用了更加合理的邊聚類算法和標簽傳播算法，增大了真實節點和Sybil攻擊節點之間的差距，降低了真實節點被誤判為攻擊節點的概率，從而實現了更加精確的團體攻擊檢測.

5 結 論

基于邊介數和邊聚類計算算法，本文提出了適用于電力通信網的Sybil攻擊檢測算法.仿真結果表明，該算法的表現優于經典SybilLimit算法.但是，這種攻擊檢測算法還可能存在一定的缺陷，這是因為文中所有仿真均使用了非常成熟的靜態數據，盡管這些攻擊數據來源于實際網絡狀態的統計，然而現實網絡環境非常復雜，攻擊技術和手段更新周期變化非?？?，所以該算法是否可以動態檢測現實網絡的Sybil攻擊，依然是未知的，需要進一步的研究與改進，下一步將致力于解決該問題.