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

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

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

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

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

1 邊介數(shù)計(jì)算

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

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

(1)

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

(2)

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

(3)

(4)

(5)

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

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

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

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

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

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

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

2 邊聚類算法

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

2.1 算法改進(jìn)

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

(6)

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

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

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

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

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

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

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

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

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

2.2 算法步驟

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

1) 選取K個(gè)初始中心點(diǎn)；

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

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

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

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

3 團(tuán)體檢測(cè)算法

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

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

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

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

(7)

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

(8)

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

M(s)=arg maxmp(m)=

(9)

團(tuán)體檢測(cè)算法的具體步驟為：

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

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

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

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

4 仿真驗(yàn)證與分析

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

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

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

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

4.2 評(píng)價(jià)指標(biāo)

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

(10)

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

(11)

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

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

圖1 10 000個(gè)Sybil攻擊節(jié)點(diǎn)時(shí)假負(fù)率仿真圖Fig.1 Simulation of false negative rate with 10 000 Sybil attack nodes

圖2 6 000個(gè)Sybil攻擊節(jié)點(diǎn)時(shí)假負(fù)率仿真圖Fig.2 Simulation of false negative rate with 6 000 Sybil attack nodes

圖3 1 000個(gè)Sybil攻擊節(jié)點(diǎn)時(shí)假負(fù)率仿真圖Fig.3 Simulation of false negative rate with 1 000 Sybil attack nodes

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

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

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

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

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

5 結(jié) 論

基于邊介數(shù)和邊聚類計(jì)算算法，本文提出了適用于電力通信網(wǎng)的Sybil攻擊檢測(cè)算法.仿真結(jié)果表明，該算法的表現(xiàn)優(yōu)于經(jīng)典SybilLimit算法.但是，這種攻擊檢測(cè)算法還可能存在一定的缺陷，這是因?yàn)槲闹兴蟹抡婢褂昧朔浅３墒斓撵o態(tài)數(shù)據(jù)，盡管這些攻擊數(shù)據(jù)來源于實(shí)際網(wǎng)絡(luò)狀態(tài)的統(tǒng)計(jì)，然而現(xiàn)實(shí)網(wǎng)絡(luò)環(huán)境非常復(fù)雜，攻擊技術(shù)和手段更新周期變化非?？欤栽撍惴ㄊ欠窨梢詣?dòng)態(tài)檢測(cè)現(xiàn)實(shí)網(wǎng)絡(luò)的Sybil攻擊，依然是未知的，需要進(jìn)一步的研究與改進(jìn)，下一步將致力于解決該問題.