王永程,孟艷紅

(1.盲信號處理國家重點(diǎn)實(shí)驗(yàn)室,四川成都 610041; 2.西安電子科技大學(xué)通信工程學(xué)院,陜西西安 710071)

?

針對有向社交網(wǎng)絡(luò)的Sy bil檢測方法

王永程1,孟艷紅2

(1.盲信號處理國家重點(diǎn)實(shí)驗(yàn)室,四川成都 610041; 2.西安電子科技大學(xué)通信工程學(xué)院,陜西西安 710071)

摘要:提出了一種針對有向社交網(wǎng)絡(luò)的Sybil檢測方法——SybilGrid法.該方法采用針對有向社交網(wǎng)絡(luò)拓?fù)涞碾S機(jī)游走策略來檢測Sybil節(jié)點(diǎn).通過采集新浪微博上的真實(shí)社交網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù),對算法的性能進(jìn)行了評估,證明了算法的有效性.與現(xiàn)有的SybilDefender方法進(jìn)行了對比分析,對于同樣數(shù)量的攻擊邊,SybilDefender法的虛警率為SybilGrid法的1.6倍左右;同時,為了達(dá)到相同的虛警率,SybilGrid法所需要的游走路徑長度更短,即SybilGrid法的檢測效率更高.

關(guān)鍵詞:Sybil攻擊;社交網(wǎng)絡(luò);隨機(jī)游走

近年來,社交網(wǎng)絡(luò)越來越受到大眾歡迎,如Twitter[1]、新浪微博[2]等.社交網(wǎng)絡(luò)給人們帶來便利的同時,也帶來了諸多困擾,例如隱私安全、虛假信息傳播、Sybil攻擊等.其中,Sybil攻擊指惡意用戶偽造多個虛擬身份,并利用這些虛擬節(jié)點(diǎn)進(jìn)行惡意言論傳播、網(wǎng)絡(luò)傳銷等活動,給正常的網(wǎng)絡(luò)信息傳輸帶來極大危害,這些虛擬節(jié)點(diǎn)稱為Sybil節(jié)點(diǎn).筆者擬針對Sybil攻擊現(xiàn)象,提出一種Sybil節(jié)點(diǎn)的檢測方法.

在社交網(wǎng)絡(luò)研究領(lǐng)域,Sybil檢測一直是研究熱點(diǎn),許多Sybil檢測策略被提出[3-7].然而,大多數(shù)研究是針對無向社交網(wǎng)絡(luò)拓?fù)溟_展的,如Facebook這樣的社交網(wǎng)絡(luò).文獻(xiàn)[6-7]提出了非中心化檢測方法——SybilGuard法和Sybil Limit法.這兩種方法假設(shè)社交網(wǎng)絡(luò)能夠快速收斂且Sybil攻擊邊數(shù)有限,通過隨機(jī)游走策略,確定節(jié)點(diǎn)是否為Sybil節(jié)點(diǎn),其缺陷在于漏警率比較高.Sybil Limit法為SybilGuard法的升級版本,但漏警率依然較高,難以達(dá)到實(shí)用效果.Gate Keeper法[4]為另一個非中心化檢測方法,文獻(xiàn)[8]指出,該方法難以在真實(shí)社交網(wǎng)絡(luò)上檢測到Sybil節(jié)點(diǎn).文獻(xiàn)[3]于2009年提出了一項中心化檢測方法——SybilInfer 法,利用貝葉斯不確定推理理論,計算節(jié)點(diǎn)為Sybil的置信度.該方法能夠取得較低的漏警率,但計算復(fù)雜度高.SybilDefender法[8]為近年來性能最優(yōu)的Sybil檢測方法,采用了中心化隨機(jī)游走策略,算法精度和速度較之其他方法都有很大的提升.上述方法都將社交網(wǎng)絡(luò)建模為無向網(wǎng)絡(luò)拓?fù)?文獻(xiàn)[9]提出了針對有向社交網(wǎng)絡(luò)拓?fù)涞腟ybil檢測方法.筆者受此啟發(fā),并利用SybilDefender的隨機(jī)游走測策略,提出了一種新的有向社交網(wǎng)絡(luò)Sybil檢測方法——SybilGrid.與Sybil Defender方法相比,SybilGrid方法在相同的攻擊邊數(shù)量下,虛警率更低,同時所需的游走路徑更短,進(jìn)一步提升了算法效率.

1 問題描述與研究動機(jī)

圖1 針對有向社交網(wǎng)絡(luò)的Sybil攻擊模型

文中涉及的概念如下:利用圖G建模社交網(wǎng)絡(luò)拓?fù)?V、E表示頂點(diǎn)集和邊集.社交網(wǎng)絡(luò)的正常用戶稱為Honest節(jié)點(diǎn),由Honest節(jié)點(diǎn)形成的網(wǎng)絡(luò)拓?fù)溆肏_Region表示.同樣,由Sybil節(jié)點(diǎn)形成的網(wǎng)絡(luò)拓?fù)溆肧_ Region表示.每個正常用戶擁有一個賬號,而一個惡意用戶,如網(wǎng)絡(luò)傳銷者,擁有多個Sybil賬號,對應(yīng)多個Sybil節(jié)點(diǎn),且這些節(jié)點(diǎn)間緊密聯(lián)系.賬號間的“關(guān)注”關(guān)系形成有向邊,如新浪微博的“關(guān)注”關(guān)系.由Sybil節(jié)點(diǎn)關(guān)注Honest節(jié)點(diǎn)形成的有向邊稱為攻擊邊;反之,稱為妥協(xié)邊.模型如圖1所示.

SybilGrid方法基于如下假設(shè):

(2)至少一個Honest節(jié)點(diǎn)是已知的.與文獻(xiàn)[3,6-8]相同,假設(shè)至少一個Honest節(jié)點(diǎn)已知,該節(jié)點(diǎn)作為后續(xù)Sybil檢測的基礎(chǔ).

(3)攻擊邊數(shù)量有限,妥協(xié)邊為攻擊邊的一部分,且由honest節(jié)點(diǎn)指向sybil節(jié)點(diǎn).H_Region的規(guī)模遠(yuǎn)大于S_Region,同時攻擊邊數(shù)量遠(yuǎn)小于S_Region或H_Region內(nèi)部的邊數(shù)量.與文獻(xiàn)[9]相同,不妨設(shè)定妥協(xié)邊數(shù)量占攻擊邊數(shù)量的1/10.

針對有向網(wǎng)絡(luò)拓?fù)涞腟ybil檢測與針對無向網(wǎng)絡(luò)拓?fù)涞腟ybil檢測的相同之處是假設(shè)(1)和假設(shè)(2),不同之處在于假設(shè)(3)中關(guān)于妥協(xié)邊的假設(shè),即有向圖中考慮了從H_Region到S_Region的反向關(guān)注.

2 針對有向社交網(wǎng)絡(luò)的Sybil檢測方法

SybilGrid方法的設(shè)計思想體現(xiàn)在兩方面,一方面由于H_Region和S_Region之間的攻擊邊數(shù)量有限,從網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的角度看,兩者分別為兩個社區(qū),攻擊邊為社區(qū)之間的圖割,所以,一次分別始于不同社區(qū)的隨機(jī)游走應(yīng)以較大的可能性遍歷本社區(qū)節(jié)點(diǎn).H_Region的節(jié)點(diǎn)規(guī)模遠(yuǎn)大于S_Region,因此,只要隨機(jī)游走的路徑足夠長,始于不同社區(qū)的隨機(jī)游走所遍歷的節(jié)點(diǎn)數(shù)量就會呈現(xiàn)出較大差異.SybilGrid的預(yù)處理環(huán)節(jié)通過執(zhí)行多次隨機(jī)游走,得到從Honest節(jié)點(diǎn)出發(fā)遍歷的節(jié)點(diǎn)數(shù)量的統(tǒng)計值,SybilGrid利用這些統(tǒng)計值來區(qū)分Honest節(jié)點(diǎn)和Sybil節(jié)點(diǎn);另一方面,對于有向圖而言,由于有向圖中“環(huán)路”的數(shù)量遠(yuǎn)小于無向圖中“環(huán)路”的數(shù)量,有向圖中的隨機(jī)游走會較快地遍歷更多的節(jié)點(diǎn),故針對有向圖的隨機(jī)游走效率更高.同時,由于SybilGrid假設(shè)了妥協(xié)邊,導(dǎo)致從H_Region游走到S_Region的概率降低,從而使得虛警率會一定程度降低.

SybilGrid包含兩個環(huán)節(jié),第1為預(yù)處理環(huán)節(jié),輸入為G(V,E)和h,輸出不同路徑長度對應(yīng)的遍歷節(jié)點(diǎn)數(shù)量的統(tǒng)計量,這些統(tǒng)計量作為第2環(huán)節(jié)判斷節(jié)點(diǎn)性質(zhì)的輸入.第2個環(huán)節(jié)為Sybil檢測環(huán)節(jié),輸入為可疑節(jié)點(diǎn)u以及第1環(huán)節(jié)輸出的統(tǒng)計量,輸出為u是否為Sybil節(jié)點(diǎn).第1環(huán)節(jié)的算法流程如下:

其次,SybilGrid基于不同的路徑長度,從lmin到lmax,分別從各Judge節(jié)點(diǎn)出發(fā),執(zhí)行R次隨機(jī)游走,然后計算訪問頻率大于閾值t的節(jié)點(diǎn)數(shù)量n.對每個路徑長度l而言,存在f+1個統(tǒng)計值{ni:1≤i≤f+1},再進(jìn)一步計算f+1個值的均值和方差,輸出三元組〈l,ˉm,δ〉.SybilGrid與SybilDefender的不同在于各參數(shù)的取值,這里取lmin=20,lmax=100,Δl=20,t=5,這些取值遠(yuǎn)小于Sybil Defender取值,原因在于有向圖上環(huán)路數(shù)量較少,隨機(jī)游走的節(jié)點(diǎn)覆蓋率更高.

SybilGrid第二環(huán)節(jié)的算法流程如下:

Algorithm 2——Sybil檢測

正如Algorithm 2所示,為了確定可疑節(jié)點(diǎn)u的性質(zhì),從u出發(fā)執(zhí)行R次路徑長度為l0(l0≥lmin)的隨機(jī)游走,并統(tǒng)計訪問次數(shù)F[i]＞t的節(jié)點(diǎn)的個數(shù)m,基于Algorithm 1輸出的三元組〈l,δ〉,計算-m,如果-m＞δα,則u是Sybil節(jié)點(diǎn);否則,路徑長度增加Δl,重復(fù)上述流程,直到-m＞δα.如果路徑長度增大至lmax,該公式一直得不到滿足,則認(rèn)為u是Honest節(jié)點(diǎn).

在Algorithm 2執(zhí)行過程中,有兩個參數(shù)比較重要,分別是α和lmax,lmax取較大的值時,能提高Sybil檢測的準(zhǔn)確率,但運(yùn)行時間會增加,效率降低.同樣,隨著α取值增大,虛警率會降低,但漏警率會升高.在實(shí)驗(yàn)部分,會對α和lmax的取值進(jìn)行分析.

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用的數(shù)據(jù)集來源于新浪微博的真實(shí)社交網(wǎng)絡(luò),按粉絲數(shù)抓取了排名前10 000的用戶的關(guān)注信息,形成了699 236條有向邊.這些用戶被認(rèn)為是正常用戶,形成H_Region社區(qū).對S_Region社區(qū)采用Erd¨os-R˙enyi(ER)模型[10]生成,其中包含1 000個Sybil節(jié)點(diǎn),同時令S_Region節(jié)點(diǎn)平均度等于H_Region節(jié)點(diǎn)平均度.攻擊邊的數(shù)量為自定義參數(shù),不同的攻擊邊數(shù)量對應(yīng)不同的Sybil攻擊圖,妥協(xié)邊數(shù)量按攻擊邊數(shù)量的10%處理.定義Ph2s為虛警率,即Honest節(jié)點(diǎn)被檢測為Sybil節(jié)點(diǎn)的概率值,Ps2h為漏警率,即Sybil節(jié)點(diǎn)被檢測為Honest節(jié)點(diǎn)的概率.

3.1 Sybil檢測性能分析

為了選取合適的α值,首先考察不同的α對Sybil檢測性能的影響.實(shí)驗(yàn)參數(shù)如下:lmin=20,lmax=100,l0=20,t=5,f=100,R∈{1 000,2 000,3 000}.這里需要說明的是,該組參數(shù)為經(jīng)驗(yàn)值,在實(shí)際應(yīng)用中,需要根據(jù)訓(xùn)練數(shù)據(jù)來選用合適的參數(shù).圖2為實(shí)驗(yàn)結(jié)果.可以看出,當(dāng)α＞4時,Ps2h=1,即漏警率為100%,算法失效.隨著α取值增大,虛警率逐漸降低.同時可以看出,R越大,虛警率越小.由于不同的R值對應(yīng)的虛警率差別不大,這里選取α=4,R=2 000為后續(xù)實(shí)驗(yàn)參數(shù).

圖2 α對Sybil檢測性能的影響分析　

圖3 σ對Sybil檢測性能的影響分析

攻擊邊數(shù)量有限是SybilGrid方法的假設(shè)之一,這里將分析不同的攻擊邊數(shù)量對算法性能的影響.為使實(shí)驗(yàn)結(jié)果更具普適性,取攻擊邊數(shù)量與Sybil節(jié)點(diǎn)數(shù)量的比值作為自變量,定義為σ,其物理意義為平均每個Sybil節(jié)點(diǎn)實(shí)施的攻擊數(shù)量,圖3為實(shí)驗(yàn)結(jié)果.可以看出,當(dāng)σ≥0.8(攻擊邊數(shù)量大于等于800)時,漏警率為100%,SybilGrid算法失效,當(dāng)σ≤0.5(攻擊邊數(shù)量小于等于500)時,漏警率為0,且虛警率維持在3×10-3左右.從0.02≤σ≤0.5區(qū)間內(nèi)性能曲線的放大圖可以看到,隨著σ的增大,虛警概率呈上升趨勢,即S_ Region和H_Region之間的邊越多,檢測準(zhǔn)確率越低,虛警率越高.原因在于隨著攻擊邊的增多,S_Region中節(jié)點(diǎn)與H_Region節(jié)點(diǎn)聯(lián)系越來越緊密,分辨性逐漸變差.

3.2 與SybilDefender的性能比較

與無向圖模型相比,有向圖模型假設(shè)攻擊邊具有方向性,這使得隨機(jī)游走從H_Region游走到S_Region的可能性進(jìn)一步降低.故理論上攻擊邊數(shù)量相同的情況下,SybilGrid的虛警率應(yīng)比SybilDefender更低.從圖4的實(shí)驗(yàn)結(jié)果來看,上述構(gòu)想可以得到驗(yàn)證.從0.02≤σ≤0.5區(qū)間內(nèi)性能曲線的放大圖可以清楚看到針對無向圖的SybilDefender的虛警率高于針對有向圖的SybilGrid,前者約為后者的1.6倍左右.當(dāng)σ=0.5 時,錯誤率稍微下降.理論上σ越大,意味著Sybil節(jié)點(diǎn)越來越像Honest節(jié)點(diǎn),此時兩種類型節(jié)點(diǎn)的可分辨性變差,虛警率升高,實(shí)驗(yàn)結(jié)果與理論分析存在矛盾.原因是本實(shí)驗(yàn)采取隨機(jī)游走策略,每次游走都存在不確定性,可能影響到最終的虛警概率.但從整體來看,虛警概率仍隨σ的增大而升高.

另外,由于有向圖中“環(huán)路”的數(shù)量遠(yuǎn)小于無向圖中“環(huán)路”的數(shù)量,有向圖中的隨機(jī)游走會較快地遍歷更多的節(jié)點(diǎn),故針對有向圖的隨機(jī)游走效率更高.可以推測,為了達(dá)到相同的虛警率,SybilGrid所需要的最大路徑長度應(yīng)小于SybilDefender的最大路徑長度,也可以理解為在相同的路徑長度下,前者的虛警率更低.為此,表1考察了不同的lmax值對應(yīng)的兩種算法的檢測結(jié)果.可以看出,當(dāng)lmax=20時,兩者的漏警率為100%,即路徑長度太短,無法識別Sybil節(jié)點(diǎn),算法失效.當(dāng)lmax≥20時,兩種算法都能有效識別Sybil節(jié)點(diǎn),但虛警率方面,SybilDefender的虛警率更高,約為SybilGrid方法的1.5倍左右.

圖4 SybilGrid與SybilDefender檢測性能的對比分析(σ)

表1 SybilGrid與SybilDefender檢測性能的對比分析(lmax)

4 結(jié) 論

筆者提出了針對有向社交網(wǎng)絡(luò)的Sybil檢測方法——SybilGrid法.通過真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)的實(shí)驗(yàn)驗(yàn)證分析,證明了方法的有效性.同時,與現(xiàn)有檢測方法SybilDefender法進(jìn)行了對比分析,發(fā)現(xiàn)在相同的攻擊邊數(shù)量下,Sybil Grid法的虛警率更低,且為達(dá)到相同的虛警概率,SybilGrid法所需要的隨機(jī)游走路徑長度更短,即運(yùn)算效率更高.

參考文獻(xiàn):

[1]YU Y,WANG X.World Cup 2014 in the Twitter World:A Big Data Analysis of Sentiments in U.S.Sports Fans’Tweets[J].Computers in Human Behavior,2015,48:392-400.

[2]ZHANG L,PENG T Q.Breadth,Depth and Speed:Diffusion of Advertising Messages on Microblogging Sites[J].Internet Research Electronic Networking Applications& Policy,2015,25:453-470.

[3]DANEZIS G,MITTAL P.Sybilinfer:Detecting Sybil Nodes Using Social Networks[C]//16th Annual Network & Distributed System Security Symposium.Reston:Internet Society,2009:39-53.

[4]TRAN N,LI J,SUBRAMANIAN L,et al.Optimal Sybil-resilient Node Admission Control[C]//Proceedings of the IEEE International Conference on Computer Communications.Piscataway:IEEE,2011:3218-3226.

[5]NOH G,KANG Y M,OH H,et al.Robust Sybil Attack Defense with Information Level in Online RecommenderSystems[J].Expert Systems with Applications,2014,41(4):1781-1791.

[6]YU H F,GIBBONS P B,KAMINSKY M,et al.Sybil Limit:a Near-optimal Social Network Defense Against Sybil Attacks[J].IEEE/ACM Transactions on Networking,2010,18(3):885-898.

[7]YU H F,KAMINSKY M,GIBBONS P B,et al.SybilGuard:Defending Against Sybil Attacks via Social Networks[J].IEEE/ACM Transactions on Networking,2008,16(3):576-589.

[8]WEI W,XU F,TAN C C,et al.SybilDefender:a Defense Mechanism for Sybil Attacks in Large Social Networks[J].IEEE Transactions on Parallel& Distributed Systems,2013,24(12):2492-2502.

[9]LIU P F,WANG X H,CHE X Q,et al.Defense Against Sybil Attacks in Directed Social Networks[C]//Proceedings of the 19th International Conference on Digital Signal Processing.Piscataway:IEEE,2014:239-243.

[10]ERD″OS P,R’ENYI A.On Random Graphs[J].Publicationes Mathematicae Debrecen,1959,6:290-297.

(編輯:李恩科)

WANG Yongcheng1,MENG Yanhong2
(1.National Key Lab.of Science and Technology on Blind Signal Processing,Chengdu 610041,China; 2.School of Telecommunication Engineering,Xidian Univ.,Xi’an 710071,China)

Abstract:A Sybil detection method based on the random walk strategy is proposed to detect the Sybil nodes in the directed social network.The performance of the algorithm is evaluated by collecting the real social network topological data on Sina Weibo,and the effectiveness of the algorithm is proved.In addition,compared with the existing SybilDefender method,it is found that the false alarm rate of SybilDefender is about 1.6 times as great as SybilGrid.Meanwhile,to achive the same false alarm probability,the random walk length required by SybilGrid is much shorter,meaning that the detection efficiency of SybilGrid is higher.

Key Words:Sybil attack;social networks;random walk

作者簡介:王永程(1987-),男,博士,E-mail:407541127@qq.com.

基金項目:國家自然科學(xué)基金資助項目(61372076,61301171);高等學(xué)校學(xué)科創(chuàng)新引智計劃資助項目(B08038);中央高校基本科研業(yè)務(wù)費(fèi)專項資金資助項目(K5051301059,K5051201021)

收稿日期:2015-09-03

doi:10.3969/j.issn.1001-2400.2016.02.034

中圖分類號:TP309.5

文獻(xiàn)標(biāo)識碼:A

文章編號:1001-2400(2016)02-0199-06

SybilGrid:Sybil detection method based on directed social networks