基于邊聚類的電力通信網(wǎng)Sybil攻擊檢測算法

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

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

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

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

1 邊介數(shù)計算

一般而言，邊介數(shù)定義為當(dāng)前邊的最短路徑與網(wǎng)絡(luò)圖中所有最短路徑的數(shù)量比值.目前，經(jīng)典算法計算介數(shù)的時間較長，難以應(yīng)用于大規(guī)模網(wǎng)絡(luò)[3-5].本文提出了一種邊介數(shù)的計算算法，網(wǎng)絡(luò)中有一個節(jié)點a，不妨設(shè)起始節(jié)點為s，目標(biāo)節(jié)點為t，則其介數(shù)中心性的定義如下：

1) 對于一個網(wǎng)絡(luò)G(V，E)，文中統(tǒng)一使用G表示網(wǎng)絡(luò)圖，V和E分別表示網(wǎng)絡(luò)的頂點集和邊集.節(jié)點a∈V的介數(shù)中心性CB(a)的計算公式為

(1)

2) 對于網(wǎng)絡(luò)G(V，E)，邊l的邊介數(shù)中心性WB(l)的計算公式為

(2)

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

(3)

(4)

(5)

在大規(guī)模網(wǎng)絡(luò)中，為了充分利用邊介數(shù)的性質(zhì)，本文引入隨機游走策略，提出恰當(dāng)?shù)倪吔閿?shù)計算算法，其流程描述為：

1) 輸入為網(wǎng)絡(luò)G(V，E)，迭代輪數(shù)T，隨機路徑長度L，邊的權(quán)值系數(shù)β，輸出邊介數(shù)參數(shù)S；

2) 初始化邊介數(shù)參數(shù)S=0，計算所有節(jié)點權(quán)值分配值，所有邊權(quán)值分配值；

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

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

5) 將所有邊的標(biāo)記值置為0；

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

2 邊聚類算法

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

2.1 算法改進

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

(6)

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

在傳統(tǒng)K-means算法中，初始中心點對聚類結(jié)果的影響較大[11]，因此，如何選擇更恰當(dāng)?shù)某跏贾行狞c，盡量將初始中心點分布于不同的類簇中是優(yōu)化K-means算法的重要策略.本文對于初始中心點的選取步驟如下：

1)隨機選擇網(wǎng)絡(luò)G(V，E)中的一個邊，將這個邊的數(shù)據(jù)點設(shè)定為中心點；

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

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

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

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

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

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

2.2 算法步驟

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

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

2) 按照K個初始中心點，將所有網(wǎng)絡(luò)節(jié)點劃分到距離其最近的中心點所屬類別中；

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

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

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

3 團體檢測算法

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

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

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

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

(7)

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

(8)

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

M(s)=arg maxmp(m)=

(9)

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

1) 利用邊聚類結(jié)果，構(gòu)造種子集；

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

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

4) 測試所有節(jié)點的標(biāo)簽傳播值是否最大，若是，則算法終結(jié)，返回結(jié)果；否則，反復(fù)執(zhí)行步驟3)～4).

4 仿真驗證與分析

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

4.1 仿真數(shù)據(jù)與環(huán)境

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

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

4.2 評價指標(biāo)

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

(10)

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

(11)

4.3 仿真結(jié)果與分析

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

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

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

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

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

在10 000個Sybil攻擊節(jié)點和PA模式下，本文還統(tǒng)計了SybilLimit算法和攻擊檢測算法的模塊化度量指標(biāo)，其指標(biāo)隨路徑數(shù)量變化的統(tǒng)計結(jié)果如圖4所示.

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

一般而言，模塊化度量主要衡量網(wǎng)絡(luò)結(jié)構(gòu)強度，該指標(biāo)越大，表明算法的團體檢測結(jié)果更加準(zhǔn)確.根據(jù)圖4可知，本文攻擊檢測算法和經(jīng)典SybilLimit算法的模塊化度量指標(biāo)隨著攻擊路徑的增加而提高，而在各種相同的外部條件和路徑數(shù)量下，本文攻擊檢測算法的模塊化度量指標(biāo)要大于經(jīng)典SybilLimit算法，這些仿真結(jié)果進一步表明，本文提出的算法具有更加優(yōu)秀的團體檢測結(jié)果.

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

5 結(jié) 論

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