王永程,孟艳红

(1.盲信号处理国家重点实验室,四川成都 610041; 2.西安电子科技大学通信工程学院,陕西西安 710071)



针对有向社交网络的Sy bil检测方法

王永程1,孟艳红2

(1.盲信号处理国家重点实验室,四川成都 610041; 2.西安电子科技大学通信工程学院,陕西西安 710071)

摘要:提出了一种针对有向社交网络的Sybil检测方法——SybilGrid法.该方法采用针对有向社交网络拓扑的随机游走策略来检测Sybil节点.通过采集新浪微博上的真实社交网络拓扑数据,对算法的性能进行了评估,证明了算法的有效性.与现有的SybilDefender方法进行了对比分析,对于同样数量的攻击边,SybilDefender法的虚警率为SybilGrid法的1.6倍左右;同时,为了达到相同的虚警率,SybilGrid法所需要的游走路径长度更短,即SybilGrid法的检测效率更高.

关键词:Sybil攻击;社交网络;随机游走

近年来,社交网络越来越受到大众欢迎,如Twitter[1]、新浪微博[2]等.社交网络给人们带来便利的同时,也带来了诸多困扰,例如隐私安全、虚假信息传播、Sybil攻击等.其中,Sybil攻击指恶意用户伪造多个虚拟身份,并利用这些虚拟节点进行恶意言论传播、网络传销等活动,给正常的网络信息传输带来极大危害,这些虚拟节点称为Sybil节点.笔者拟针对Sybil攻击现象,提出一种Sybil节点的检测方法.

在社交网络研究领域,Sybil检测一直是研究热点,许多Sybil检测策略被提出[3-7].然而,大多数研究是针对无向社交网络拓扑开展的,如Facebook这样的社交网络.文献[6-7]提出了非中心化检测方法——SybilGuard法和Sybil Limit法.这两种方法假设社交网络能够快速收敛且Sybil攻击边数有限,通过随机游走策略,确定节点是否为Sybil节点,其缺陷在于漏警率比较高.Sybil Limit法为SybilGuard法的升级版本,但漏警率依然较高,难以达到实用效果.Gate Keeper法[4]为另一个非中心化检测方法,文献[8]指出,该方法难以在真实社交网络上检测到Sybil节点.文献[3]于2009年提出了一项中心化检测方法——SybilInfer 法,利用贝叶斯不确定推理理论,计算节点为Sybil的置信度.该方法能够取得较低的漏警率,但计算复杂度高.SybilDefender法[8]为近年来性能最优的Sybil检测方法,采用了中心化随机游走策略,算法精度和速度较之其他方法都有很大的提升.上述方法都将社交网络建模为无向网络拓扑,文献[9]提出了针对有向社交网络拓扑的Sybil检测方法.笔者受此启发,并利用SybilDefender的随机游走测策略,提出了一种新的有向社交网络Sybil检测方法——SybilGrid.与Sybil Defender方法相比,SybilGrid方法在相同的攻击边数量下,虚警率更低,同时所需的游走路径更短,进一步提升了算法效率.

1 问题描述与研究动机

图1 针对有向社交网络的Sybil攻击模型

文中涉及的概念如下:利用图G建模社交网络拓扑,V、E表示顶点集和边集.社交网络的正常用户称为Honest节点,由Honest节点形成的网络拓扑用H_Region表示.同样,由Sybil节点形成的网络拓扑用S_ Region表示.每个正常用户拥有一个账号,而一个恶意用户,如网络传销者,拥有多个Sybil账号,对应多个Sybil节点,且这些节点间紧密联系.账号间的“关注”关系形成有向边,如新浪微博的“关注”关系.由Sybil节点关注Honest节点形成的有向边称为攻击边;反之,称为妥协边.模型如图1所示.

SybilGrid方法基于如下假设:

(2)至少一个Honest节点是已知的.与文献[3,6-8]相同,假设至少一个Honest节点已知,该节点作为后续Sybil检测的基础.

(3)攻击边数量有限,妥协边为攻击边的一部分,且由honest节点指向sybil节点.H_Region的规模远大于S_Region,同时攻击边数量远小于S_Region或H_Region内部的边数量.与文献[9]相同,不妨设定妥协边数量占攻击边数量的1/10.

针对有向网络拓扑的Sybil检测与针对无向网络拓扑的Sybil检测的相同之处是假设(1)和假设(2),不同之处在于假设(3)中关于妥协边的假设,即有向图中考虑了从H_Region到S_Region的反向关注.

2 针对有向社交网络的Sybil检测方法

SybilGrid方法的设计思想体现在两方面,一方面由于H_Region和S_Region之间的攻击边数量有限,从网络社区结构的角度看,两者分别为两个社区,攻击边为社区之间的图割,所以,一次分别始于不同社区的随机游走应以较大的可能性遍历本社区节点.H_Region的节点规模远大于S_Region,因此,只要随机游走的路径足够长,始于不同社区的随机游走所遍历的节点数量就会呈现出较大差异.SybilGrid的预处理环节通过执行多次随机游走,得到从Honest节点出发遍历的节点数量的统计值,SybilGrid利用这些统计值来区分Honest节点和Sybil节点;另一方面,对于有向图而言,由于有向图中“环路”的数量远小于无向图中“环路”的数量,有向图中的随机游走会较快地遍历更多的节点,故针对有向图的随机游走效率更高.同时,由于SybilGrid假设了妥协边,导致从H_Region游走到S_Region的概率降低,从而使得虚警率会一定程度降低.

SybilGrid包含两个环节,第1为预处理环节,输入为G(V,E)和h,输出不同路径长度对应的遍历节点数量的统计量,这些统计量作为第2环节判断节点性质的输入.第2个环节为Sybil检测环节,输入为可疑节点u以及第1环节输出的统计量,输出为u是否为Sybil节点.第1环节的算法流程如下:

其次,SybilGrid基于不同的路径长度,从lmin到lmax,分别从各Judge节点出发,执行R次随机游走,然后计算访问频率大于阈值t的节点数量n.对每个路径长度l而言,存在f+1个统计值{ni:1≤i≤f+1},再进一步计算f+1个值的均值和方差,输出三元组〈l,¯m,δ〉.SybilGrid与SybilDefender的不同在于各参数的取值,这里取lmin=20,lmax=100,Δl=20,t=5,这些取值远小于Sybil Defender取值,原因在于有向图上环路数量较少,随机游走的节点覆盖率更高.

SybilGrid第二环节的算法流程如下:

Algorithm 2——Sybil检测

正如Algorithm 2所示,为了确定可疑节点u的性质,从u出发执行R次路径长度为l0(l0≥lmin)的随机游走,并统计访问次数F[i]＞t的节点的个数m,基于Algorithm 1输出的三元组〈l,δ〉,计算-m,如果-m＞δα,则u是Sybil节点;否则,路径长度增加Δl,重复上述流程,直到-m＞δα.如果路径长度增大至lmax,该公式一直得不到满足,则认为u是Honest节点.

在Algorithm 2执行过程中,有两个参数比较重要,分别是α和lmax,lmax取较大的值时,能提高Sybil检测的准确率,但运行时间会增加,效率降低.同样,随着α取值增大,虚警率会降低,但漏警率会升高.在实验部分,会对α和lmax的取值进行分析.

3 实验分析

实验采用的数据集来源于新浪微博的真实社交网络,按粉丝数抓取了排名前10 000的用户的关注信息,形成了699 236条有向边.这些用户被认为是正常用户,形成H_Region社区.对S_Region社区采用Erd¨os-R˙enyi(ER)模型[10]生成,其中包含1 000个Sybil节点,同时令S_Region节点平均度等于H_Region节点平均度.攻击边的数量为自定义参数,不同的攻击边数量对应不同的Sybil攻击图,妥协边数量按攻击边数量的10%处理.定义Ph2s为虚警率,即Honest节点被检测为Sybil节点的概率值,Ps2h为漏警率,即Sybil节点被检测为Honest节点的概率.

3.1 Sybil检测性能分析

为了选取合适的α值,首先考察不同的α对Sybil检测性能的影响.实验参数如下:lmin=20,lmax=100,l0=20,t=5,f=100,R∈{1 000,2 000,3 000}.这里需要说明的是,该组参数为经验值,在实际应用中,需要根据训练数据来选用合适的参数.图2为实验结果.可以看出,当α＞4时,Ps2h=1,即漏警率为100%,算法失效.随着α取值增大,虚警率逐渐降低.同时可以看出,R越大,虚警率越小.由于不同的R值对应的虚警率差别不大,这里选取α=4,R=2 000为后续实验参数.

图2 α对Sybil检测性能的影响分析　

图3 σ对Sybil检测性能的影响分析

攻击边数量有限是SybilGrid方法的假设之一,这里将分析不同的攻击边数量对算法性能的影响.为使实验结果更具普适性,取攻击边数量与Sybil节点数量的比值作为自变量,定义为σ,其物理意义为平均每个Sybil节点实施的攻击数量,图3为实验结果.可以看出,当σ≥0.8(攻击边数量大于等于800)时,漏警率为100%,SybilGrid算法失效,当σ≤0.5(攻击边数量小于等于500)时,漏警率为0,且虚警率维持在3×10-3左右.从0.02≤σ≤0.5区间内性能曲线的放大图可以看到,随着σ的增大,虚警概率呈上升趋势,即S_ Region和H_Region之间的边越多,检测准确率越低,虚警率越高.原因在于随着攻击边的增多,S_Region中节点与H_Region节点联系越来越紧密,分辨性逐渐变差.

3.2 与SybilDefender的性能比较

与无向图模型相比,有向图模型假设攻击边具有方向性,这使得随机游走从H_Region游走到S_Region的可能性进一步降低.故理论上攻击边数量相同的情况下,SybilGrid的虚警率应比SybilDefender更低.从图4的实验结果来看,上述构想可以得到验证.从0.02≤σ≤0.5区间内性能曲线的放大图可以清楚看到针对无向图的SybilDefender的虚警率高于针对有向图的SybilGrid,前者约为后者的1.6倍左右.当σ=0.5 时,错误率稍微下降.理论上σ越大,意味着Sybil节点越来越像Honest节点,此时两种类型节点的可分辨性变差,虚警率升高,实验结果与理论分析存在矛盾.原因是本实验采取随机游走策略,每次游走都存在不确定性,可能影响到最终的虚警概率.但从整体来看,虚警概率仍随σ的增大而升高.

另外,由于有向图中“环路”的数量远小于无向图中“环路”的数量,有向图中的随机游走会较快地遍历更多的节点,故针对有向图的随机游走效率更高.可以推测,为了达到相同的虚警率,SybilGrid所需要的最大路径长度应小于SybilDefender的最大路径长度,也可以理解为在相同的路径长度下,前者的虚警率更低.为此,表1考察了不同的lmax值对应的两种算法的检测结果.可以看出,当lmax=20时,两者的漏警率为100%,即路径长度太短,无法识别Sybil节点,算法失效.当lmax≥20时,两种算法都能有效识别Sybil节点,但虚警率方面,SybilDefender的虚警率更高,约为SybilGrid方法的1.5倍左右.

图4 SybilGrid与SybilDefender检测性能的对比分析(σ)

表1 SybilGrid与SybilDefender检测性能的对比分析(lmax)

4 结 论

笔者提出了针对有向社交网络的Sybil检测方法——SybilGrid法.通过真实社交网络数据的实验验证分析,证明了方法的有效性.同时,与现有检测方法SybilDefender法进行了对比分析,发现在相同的攻击边数量下,Sybil Grid法的虚警率更低,且为达到相同的虚警概率,SybilGrid法所需要的随机游走路径长度更短,即运算效率更高.

参考文献:

[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.

基金项目:国家自然科学基金资助项目(61372076,61301171);高等学校学科创新引智计划资助项目(B08038);中央高校基本科研业务费专项资金资助项目(K5051301059,K5051201021)

收稿日期:2015-09-03

doi:10.3969/j.issn.1001-2400.2016.02.034

中图分类号:TP309.5

文献标识码:A

文章编号:1001-2400(2016)02-0199-06

SybilGrid:Sybil detection method based on directed social networks