一种基于结构及节点特征相似度的社交网络图数据去匿名方法

2018-03-14 10:21:14王照永陈勤朱宏林冯世杰
现代计算机 2018年4期
关键词:结构特征先验攻击者

王照永,陈勤,朱宏林,冯世杰

(杭州电子科技大学信息安全部级重点实验室,杭州 310018)

0 引言

如今,社会网络在人们的日常生活、工作中扮演着不可或缺的角色。例如像微博、Facebook、Twitter等社会网络已成为人们获取信息、分享信息和营销推广等的重要途径。由于其自身的透明性和匿名性,这将导致既不易追踪网络中虚假谣言的发布者,又不易追查相关违法犯罪活动的参与者。若攻击者对用户位置数据集进行去匿名化可获得用户的个人位置信息,则可对其进行监视、跟踪,这将有助于案件的侦破。若深入分析用户的位置和运动轨迹等信息,则可能挖掘推断出用户的行为模式、兴趣爱好,甚至健康和政治倾向等个人隐私信息。因此,无论对分析研究还是案件侦破,社交网络中匿名数据的再识别都具有重要的经济和社会价值。例如,大型电商网站通过对网站用户数据分析,可以推测分析用户的生活习惯和购物倾向。显然,用户的私人的信息将会遭到泄露从而引起安全问题。

近年来,社会网络数据的隐私安全问题得到了大量关注[1-3]。例如基于k匿名技术的隐私保护[4-5]和基于图映射的去匿名技术[6-8]研究。然而,先前的去匿名研究仍然存在局限性:(1)先前的大多数攻击只关注去匿名,即实现匿名用户集与辅助数据集的映射。而在去匿名后,攻击者是如何获取和推断用户的隐私信息的却很少被讨论。(2)有些攻击者通常不考虑图节点的属性特征。实际上,攻击者不仅可以直接从发布的数据中获取用户的属性,还可以根据其他属性推断出一些用户的敏感属性。以薪资为例,虽与包括教育和职业在内的多种属性密切相关,但可推测作为程序员或医生明显意味着高薪。为了解决这些限制问题,本文构建了去匿名攻击的图模型,并使用该模型来描述一些敏感隐私信息的推断过程。通过去匿名攻击的图模型来实现两个数据集图节点间的映射。本文提出了一种基于用户社会网络图结构及节点间的特征的去匿名方法,通过对两个数据集图的结构特征及节点特征的分析研究,提出了基于节点间相似度的去匿名方法。本文的去匿名的方法,假设攻击者已获得了其攻击对象部分或全部的一些具体的详细信息(即作为攻击辅助信息),分别对匿名数据集与辅助数据集的图的结构及节点间进行相似度特征的匹配,进而尽可能多地成功实现两个数据集节点间的映射,最终确认匿名对象的所有相关信息。此外,在更新的先验攻击图上进行用户敏感属性或行为倾向的推测,以此挖掘出用户的隐私信息。在两个真实社会网络数据集上进行了大量实验,实验结果证明,提出的去匿名方法在匿名的准确率及运行时间上效率提高。

1 相关工作

近年来,社会网络中数据的去匿名研究受到了学术界、工业界的广泛关注。去匿名研究关注点包括社会网络用户的兴趣、位置和社交关系等方面。例如:基于位置的社交网络服务(LBSNS)已经变得流行起来,此服务正在收集大量的地理社交网络位置数据,从而引发了记录移动记录的个人隐私风险的问题。Gam等人[9]提出了一种基于移动马尔可夫链(MMC)的移动性模型来实现这种攻击。Wei等人[10]提出了一种基于位置的兴趣点标识方法,通过提取访问兴趣点的用户团体的特征描述用户个体兴趣点的特征,将获得标识的兴趣点推荐给有相同兴趣的用户。Davis Jr.等人[11]通过Twitter用户粉丝中可定位的用户,运用多数投票方法来推断其他用户发布博文的地理位置。

社会网络数据包含了大量用户的个人信息。虽国内外对社交网络数据的隐私保护研究已经取得了不少成果,但仍存在一些局限。如在非交互式社交网络中,现有的研究工作大多只考虑了单次发布的社交网络数据。然而对于连续发布的社交网络数据集,一方面,现有的匿名化方法无法很好地保护用户隐私,也不能满足对匿名数据进行演化分析的需要;另一方面,现有的去匿名化方法中固有的不确定性被放大了,因此仍存在较大的改进空间。因此,需对基于社会网络数据的图的结构特征进行进一步的研究。

目前,在基于社会网络数据图的结构特征的去匿名化攻击中,假设攻击者获取了用户的详细信息(即辅助信息),如通过网络爬虫等方法获取不同社交网络中用户及用户间的关系等信息。去匿名化攻击分为主动攻击和被动攻击。主动攻击是在数据发布之前,攻击者已创建一定数量的账号并使他们各自成为固定的关系,这样就形成了一种极易分辨出来的图结构,在数据匿名发布后,首先找到这些节点的映射,然后以此为中心对其他节点进行去匿名化操作变的相对容易些。但其显然不太适用于大数据集,且需要创建大量的伪节点比较麻烦。被动攻击则是需要获取其他的相关信息,例如其他一些热门社会网络的用户数据集,以此作为攻击辅助数据集,无需创建大量伪节点,可通过特征相识度匹配,实现数据集的用户间的映射以实现社交网络匿名数据的去匿名化。

此外,已经提出了各种基于图的结构的方法来对社交网络数据进行去匿名化[12-14]。给定匿名的社会网络图结构和真实信息的辅助用户图结构,基于图的结构的去匿名方法是通过检查这两个社会网络中节点间的相似性来实现节点之间的映射,最终再识别匿名用户。Narayanan等人[15]提出了完全基于网络的拓扑结构的去匿名化方法,虽然开始需要对少量节点进行匹配,但并没有像主动攻击那样,通过创建大量用户伪节点来实现去匿名化。根据少量的辅助数据,寻找相似结构特征完成了种子节点的映射,然后通过不断扩散进而找出新的节点映射关系,以较小的出错率成功地识别出1/3的同时拥有Twitter和Flicker的用户数据。Aston等人[12]提出了一种基于图节点相似度测量的算法,同时也评估了几种轻匿名算法的隐私风险。Ji S[8]等人研究了结构化数据去匿名的量化、实践和意义。文献[16]利用朋友关系的网络图将跨多个不同社会网络的账号映射数学建模,来识别属于同一个用户的所有账户。

然而,综上文献在基于社会网络图结构的去匿名方法仍存在局限性,本文提出了一种基于社交网络数据图的结构及节点特征相似度的去匿名方法,该方法利用社交网络图的结构特征与节点属性的特征之间的相似性差异实现节点间的映射,去匿名正确率会高一些。

2 去匿名模型

针对数据集的匿名隐私保护,在数据发布之前,通常先对用户的数据集进行匿名化技术处理(如Name&ID的删除并替换、添加或删除节点间的链接等),然后再发布其匿名后的数据集。对于去匿名化,攻击者需构建先验攻击图Gu和匿名图Ga,然后利用去匿名和隐私推理技术来识别匿名用户并推断出用户的一些敏感属性。

2.1 数据模型

社会网络数据图的建模时,通过对其图的结构的研究,发现由同一组用户产生的社交网络数据集图的结构有很强的相似性。假设:(1)攻击者不知道攻击目标用户的真实身份及两个数据集节点间的映射关系。攻击者试图去匿名某一特定目标或一组用户集,甚至所有匿名用户。此外,攻击者也可能获取各种背景知识作为攻击的先验知识。(2)数据发布者是信任的,无论是数据集的发布前后。

社会网络数据大多都有结构化的图结构,因此要把匿名数据集结构化,表示为Ga=(Va,Ea),Va={i│i是一匿名用户}即为一匿名用户集,Ea={e(i,j)│用户间的关系,i,j∈Va}用户关系集。实际上,社会网络数据集往往是有向图或无向图的结合。然而,为了图的构造简单和不失一般性,假设Ga是一无向图。注意,本文设计的算法可直接衍生到适用于有向图场景中。

同样,辅助数据用于构建攻击者的先验攻击图Gu。去匿名时两个数据集通常都会有一些重叠用户,这有助于匿名用户的去匿名化。此外,获取辅助数据方式有很多种,例如数据聚合、在线爬虫、第三方的应用收集等。辅助数据集可表示为图Gu=(Vu,Eu),Vu={i|i是一已知的用户}和Eu={e(i,j)│用户间的关系,i,j∈Vu}。

2.2 去匿名概述

在去匿名化过程中,攻击者试图尽可能多地将先验攻击图Gu中的节点映射到匿名图Ga上的节点,本文是基于社会网络图结构及节点属性特征的相似度差异实现节点间的映射。在完成某一映射方案之后,可将匿名节点相关联的属性也链接到先验攻击图节点上,实现了先验攻击图的更新。重要的是,还可根据新获取的属性信息进行用户隐私信息的推测。过程如图1。

图1一去匿名的例子。假设Bill同时存在于匿名数据集和先验数据集。原始数据集图1(a)通过匿名处理后,再发布图1(b)。攻击者构建先验攻击图1(c)。攻击者知道用户Bill有四条链接和年龄超过50等特征。攻击者尝试将先验攻击图中的Bill节点映射到匿名图中的一个节点。通过节点间相似度测量,发现节点有B和D与Bill都有很高的相似度,因此B和D都被添加到候选映射集合中。显然,攻击者从节点的属性特征发现用户B的年龄60而用户D的年龄40,最后把Bill映射到节点B而不是D。接下来,图Ga中与节点B链接的属性同样也与图Gu的Bill相关联,在这种情况下,若攻击者确认Bill是程序员,则该属性被添加到更新的图1(d)中。攻击者可推断出私人的一些属性或关系。就像图1(b)描述的那样,攻击者知道程序员有超过5万美元的薪水,因此攻击者可以推断出Bill的薪资等敏感信息状况。

图1 去匿名的过程

3 去匿名攻击

基于两个数据集的图Ga和Gu,任意一个DA去匿名攻击方案都被定义为映射的实现过程即σ:Va→Vu。基于用户图的结构及节点特征上的相似差异性尽可能多的实现用户间的映射。

3.1 结构特征

本节先定义一些结构特征,对于任一数据集节点i∈Va或Vu,定义如下:

度:对于 i∈ Va(Vu),其节点度表示为 d(i),即 d(i)=|其中是节点i领域的基数。

领域:对于 i∈Va(Vu),其领域特征 n(i)表示为一β维向量,β是一用户定义的参数(非负的整数)并表示i用户领域内第k大度节点(1≤k≤β)。

考虑到用户的全局结构特征,定义了K距离(Top-K reference distance)和抽样近似距离(sampling close⁃ness centrality),从不同的角度来分析用户图的结构特征,进而有效的区分节点之间的差异性。定义如下:

Top-K 距离:对于 i∈Va(Vu),Top-K 距离 lK(i)表示一个K维向量,其表示节点i与其领域内的第k大度节点间的最短路径的长度(1≤λ≤K)。注意,可能出现这种情况:若图的结构中(Ga或Gu)中不存在边关系,则=∞。

抽样近似中心:对于 i∈Va(Vu),定义 C(i)来描述其全局拓扑结构特征,但并未导致多大的计算开销。实际上,先随机的从Va节点数据集中抽取 某 一 子集Sa⊆Va(Su⊆Vu)。然后其中 h(i,j)是用户 i与 j之间的距离。

分别从图的结构的局部和全局不同的角度分析了图的结构特征。其中度和领域体现了用户图的局部结构特征,而Top-K参考距离和抽样近似距离表现了用户图的全局结构特征。本文放弃使用准确近似中心(accurate closeness centrality)特征而引入了抽样近似距离,也能体现出图节点的全局结构特征,但并未导致太多的计算开销。

3.2 相似度

根据上节的相关定义,考虑图的结构特征,先定义了一个结构相似度如(1):

其中匿名数据集的用户i∈Va和辅助数据集的用户j∈Vu,c1,c2,c3∈[0,1]是带权重的常数值,且c1+c2+c3=1,d,c(i)=(d(i),c(i)),s(·)表示两向量间的余弦相似度。而余弦相似度更多的是从方向上区分向量间的差异,对绝对的数值不敏感。这里,引入了调整余弦相似度,如在所有维度上数值减去节点平均度dˉ。从算法分析上,虽然复杂度增加了,但是相比普通余弦相似度结构相似度区别更容易了,这有助于去匿名化。

除了考虑结构上相似性外,又考虑到节点间的属性相似度§a(i,j)。在图1中,每个用户节点i(∀i∈Va)都有一些链接属性。给定节点i及其出现的属性链接都有置信分cs(假设在Gu中以100%置信分出现该节点属性同样也会在Ga中出现),节点j(j∈Vu)类似于上定义。因此,节点i与j之间的属性相似度如(2)所示:

在图节点映射的实现过程中,为了提高节点间映射的准确率,应分别考虑图节点的结构及节点属性特征。最后,给 §s(i,j),§a(i,j)分配权重,所以节点i和j的相似度表示为 S(i,j):

3.3 去匿名算法

代码如下:

该算法中,首先构建了两个结构化数据集的图:匿名图和先验攻击图(Ga与Gu)。实际上,若图中两个节点通过相似性匹配实现了映射,则它们领域内节点更有可能实现映射。为了减少映射空间和复杂度,选择对图节点进行广度优先遍历(BFS),这将会导致比DFS更少的错误累积。具体地说,第五步:图Gu中每个节点 i∈Vu,通过计算相似性 S(i,j),获取其 k最相似的候选映射集合,其中k和θ是平衡匿名用户去匿名的准确率和复杂度而预先定义的参数。此外,初始节点的选取是至关重要的,因为它对节点映射的实现过程有很大的影响。先随机从图Gu中选取高节点度的节点,并计算它与所有节点 j∈Ga之间的相似性。若相似度范围大于阈值θ(默认设置为0.8),则选择该节点作为初始节点。在这些最可能的候选集c(i)中,移除相似度小于θ的候选节点,通过匹配先验攻击图和匿名图形节点之间的相似度来实现图节点之间的映射。当完成图节点BFS时,就实现了所有节点的映射。

4 实验与评估

本文对两个社会网络数据集进行去匿名攻击实验,且对用户的隐私进行一些隐私推测,从而披露更多的用户隐私数据。然后对两个数据集的去匿名性能进行了评估。

表1 数据集的统计信息

4.1 数据集

本文使用社交网络(Twitter和Google+)的两个真实数据集进行去匿名化实验。对于Twitter,从其网络中获取数据及他们的个人文件,其中包括81306个节点和1768149链接,且具有不完整或无效的错误属性的用户都被删除。同样Google+数据集,包括107614个节点和13673453链接。此外,预处理数据集,包括删除重复的和离散的用户个人文件。表1显示了预处理数据集的统计信息。

在数据集去匿名攻击之前,首先需匿名图G以生成匿名图Ga。给定任意原始数据集,用户的隐私数据通常都包含在节点间链接和节点属性。为了匿名G,链接和节点属性通常受到扰乱等匿名技术处理。具体的来说,匿名图中链接以抽样概率Sa从图G链接中随机抽样,并且图G中用户的姓名和ID都被删除并用假名代替。这里,假设当匿名图Ga生成时,节点的属性保持不变。生成先验攻击图Gu时,抽样的方式略有不同。首先,选取了一些用户作为攻击者的目标用户。注意,图Gu上的链接是以抽样概率Su从与上边这些有关的用户中随机抽取得到的。同样,假设节点的属性保持不变。

4.2 实验结果分析

为了评估去匿名算法的准确性,本文使用用户被正确识别的比例和运行时间作为衡量去匿名算法效用和复杂度的标准指标。由于数据集Google+和Twitter上的实验是相似的,先专注于数据集Google+。默认参数设置为:k=10,θ=0.7,Sa=Su=0.8,WS=0.6。实验运行在Ubuntu14.04操作系统上,Intel Xeon 2.4GHz*4,内存32G。当对数据集Google+进行去匿名化攻击时,每次去匿名实验都会重复多次,实验结果取平均值。

图2显示了参数k和θ是如何影响数据集去匿名化的准确度和时间复杂度。图2(a),当k≤10,匿名数据集去匿名的准确率随着k值的增加而提高。但当k>10时,去匿名准确率具有较小的波动。但随着k值的增加,运行时间不断增加。这是因为进行节点映射时需匹配更多的节点。因此,默认设定参数k=10。据图2(b)显示,相似度阈值θ的变化对去匿名的准确率和运行时间影响有些差异。这些参数的设置与平衡去匿名的准确率和运行时间有很大的相关性。

此外,一些参数的设置对去匿名化准确率和运行时间也有很大的影响。图3(a),当0.5≤Ws≤0.8时,去匿名方法的效果更好一些(注意,权值Ws,1-Ws是分配给图的节点的结构相似性与属性特性相似性的权重)。因此,这表明上述两个特征值在测量节点间的相似性时起着重要的作用。但相比节点属性特征,节点的结构特征对节点的映射的实现影响更重要一些。

图2 去匿名的准确率和运行时间(k&θ)

图3 去匿名的准确率和运行时间(Ws)

除了去匿名的准确度稍低一些,Twitter数据集的相关实验也有类似的结果。本文采用了图的广度优先遍历(BFC)遍历节点和对节点属性进行了k匿名处理,因此仅仅通过节点属性特征的相似性来区分用户是非常困难的。正如所考虑的,若有更多的基于图的结构特征(如抽样近似中心(Sampling closeness centrality)、Top-K 参考距离(Top-K reference distance)、l-hop neighborhood等)纳入到的方法中,这将会提高去匿名的准确率。

5 讨论

通过对实际数据集的实验分析,发现对拥有高节点度或高图密度的用户组更有可能成功地被去匿名化。这是因为节点度高的用户包含了更多的图的结构信息。为了支持本文的想法,对实验结果进行了深入的分析了解,观察到具有较低程度的数据集节点很难被去匿名化。

假设图Gu中每个节点都有相应的匹配节点在图Ga上,即Vu⊆Va,且两个数据集的重叠用户的比例将直接影响去匿名的准确率。当两个数据集的共同的节点数很少时,去匿名的准确率将会很低。此外,可能会出现原始数据集中不存在来自先前攻击图Gu的某一用户,因此绝对不存在于匿名图Ga中。这种情况下,应该稍微做出一些调整,一个用户将被映射到假的节点或被直接忽略,即在图Ga上很可能没有匹配的节点。

6 结语

本文提出了一种基于社会网络数据的图的结构及节点特征相似度测量的去匿名攻击,它综合考虑了社会网络图结构特征和节点属性特征的差异性,进行用户节点间的相似性匹配来实现用户间的映射,有效地推测出一些用户的敏感信息数据。实验结果表明,与现有的大多数去匿名方法相比,该方法提高了去匿名化的效率和准确率。未来将着重于研究以下方面:a)由于现有的多数匿名技术易受到基于图的结构的DA攻击,建议针对这种攻击设计出有效的解决方案。b)如何定量分析社会网络的去匿名风险?还没有任何理论定量地分析匿名技术数据与去匿名攻击的相关性。

[1]冯登国,张敏,李昊.大数据安全与隐私保护.计算机学报,2014,37(1),246-258.

[2]珍富,董晓蕾,周俊等.大数据安全与隐私保护研究进展[J].计算机研究与发展,2016,53(10):2137-2151.

[3]孟小峰,慈祥.大数据管理:概念、技术与挑战[J].计算机研究与发展,2013,50(1):146-169.

[4]Yuan M,Chen L,Yu P S,et al.Protecting Sensitive Labels in Social Network Data Anonymization[J].IEEE Transactions on Knowledge&Data Engineering,2013,25(3):633-647.

[5]Roberto J.Bayardo,Rakesh Agrawal.Data Privacy through Optimal k-Anonymization[C].International Conference on Data Engineering,2005.ICDE 2005.Proceedings.IEEE,2005:217-228.

[6]Ding X,Zhang L,Wan Z,et al.A Brief Survey on De-Anonymization Attacks in Online Social Networks[C].Computational Aspects of Social Networks(CASoN),2010 International Conference on.IEEE,2010:611-615.

[7]Fabiana C,Garetto M,Leonardi E.De-Anonymizing Scale-Free Social Networks by Percolation Graph Matching[C].Computer Communications(INFOCOM),2015 IEEE Conference on.IEEE,2015:1571-1579.

[8]Ji S,Li W,Srivatsa M,et al.Structural Data De-Anonymization:Theory and Practice[J].IEEE/ACM Transactions on Networking,2016,24(6):3523-3536.

[9]Gambs S,Killijian M O,del Prado Cortez M N.De-Anonymization Attack on Geolocated Data[J].Journal of Computer and System Sci-ences,2014,80(8):1597-1614.

[10]Wei L Y,Yeh M Y,Lin G,et al.Discovering Point-of-Interest Signatures Based on Group Features from Geo-Social Networking Data[C].Technologies and Applications of Artificial Intelligence(TAAI),2013 Conference on.IEEE,2013:182-187.

[11]Davis Jr C A,Pappa G L,de Oliveira D R R,et al.Inferring the Location of Twitter Messages Based on User Relationships[J].Transactions in GIS,2011,15(6):735-751.

[12]Fu H,Zhang A,Xie X.Effective Social Graph De-Anonymization Based on Graph Structure and Descriptive Information[J].ACM Transactions on Intelligent Systems and Technology(TIST),2015,6(4):49.

[13]Ji S,Li W,Srivatsa M,et al.Structure Based Data De-Anonymization of Social Networks and Mobility Traces[C].International Conference on Information Security.Springer,Cham,2014:237-254.

[14]Ji S,Li W,Srivatsa M,et al.Structural Data De-Anonymization:Quantification,Practice,and Implications[C].Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.ACM,2014:1040-1053.

[15]Narayanan A,Shmatikov V.De-Anonymizing Social Networks[C].Security and Privacy,2009 30th IEEE Symposium on.IEEE,2009:173-187.

[16]Korula N,Lattanzi S.An Efficient Reconciliation Algorithm for Social Networks[J].Proceedings of the VLDB Endowment,2014,7(5):377-388.

猜你喜欢
结构特征先验攻击者
基于微分博弈的追逃问题最优策略设计
自动化学报(2021年8期)2021-09-28 07:20:18
基于无噪图像块先验的MRI低秩分解去噪算法研究
正面迎接批判
爱你(2018年16期)2018-06-21 03:28:44
基于自适应块组割先验的噪声图像超分辨率重建
自动化学报(2017年5期)2017-05-14 06:20:44
特殊环境下双驼峰的肺组织结构特征
兽医导刊(2016年12期)2016-05-17 03:51:54
基于平滑先验法的被动声信号趋势项消除
2012年冬季南海西北部营养盐分布及结构特征
有限次重复博弈下的网络攻击行为研究
先验的废话与功能的进路
东南法学(2015年2期)2015-06-05 12:21:36
C-PRrpp半群的结构特征