移动轨迹和社交网数据的强大去匿名化方法及实验结果

+Ⓧ通用图数据去AnAnonymization：从移动轨迹到社交网络吉寿玲，李卫，佐治亚理工学院，美国IBM T.J. Watson研究中心JING SELENA HE，Kennesaw State University佐治亚理工学院当人们使用社交应用程序和服务时，他们的隐私受到潜在的严重威胁。在这篇文章中，我们提出了一种新的，强大的，有效的去匿名化攻击移动跟踪数据和社交数据。首先，我们设计了一个统一的相似性（US）的测量，它考虑到本地和全球的数据结构特征，从辅助数据中获得的信息，以及从正在进行的去匿名化结果继承的知识。通过分析真实数据集上的测量结果，我们发现一些数据可以精确地去匿名化，而另一些数据可以在粗粒度下去匿名化。利用这一特性，我们提出了一个基于美国的去匿名化（DA）框架，它迭代地去匿名化数据的准确性保证。然后，为了在不知道匿名数据和辅助数据之间的重叠大小的情况下对大规模数据进行去匿名化，我们将DA推广到自适应去匿名化（ADA）框架。通过巧妙地处理两个核心匹配子图，ADA实现了高的去匿名准确性并降低了计算开销。最后，我们研究了三个著名的移动轨迹：圣安德鲁斯，Infocom06和Smallblue，以及三个社交数据集：ArnetMiner，Google+和Facebook的去匿名化攻击。实验结果表明，所提出的去匿名框架是非常有效的和鲁棒的噪声。源代码和使用的数据集现已在SecGraph [2015]上公开。CCS概念： 安全和隐私→假名、匿名和不可追踪; 安全和隐私→数据匿名化和清理附加关键词和短语：图去匿名化，社交网络，移动性痕迹这项工作得到了国家科技支撑计划（2014BAH24F01）的部分支持。Mudhakar Srivatsa本文件中包含的观点和结论是作者的观点和结论，不应被解释为代表美国陆军研究实验室（美国政府、英国国防部或英国政府。美国和英国政府被授权为政府目的复制和分发重印本，尽管此处有任何版权注释。Jing S.他作者地址：S。季昕是浙江大学计算机科学与技术学院的一名教授，美国乔治亚理工学院电气与计算机工程学院，亚特兰大，GA 30332，电子邮件：sji@gatech.edu; W.李先生就职于佐治亚理工学院电气与计算机工程学院，地址：美国佐治亚州亚特兰大市，邮编：30332; wli64@gatech.edu Srivatsa是IBM的Thomas J.Watson研究中心，Yorktown Heights，NY 10598，USA;电子邮件：msrivats@us.ibm.com; J. S.他在美国佐治亚州玛丽埃塔市肯索州立大学计算机科学系工作; jhe4@kennesaw.edu贝亚是电气和计算机工程学院，佐治亚理工学院，亚特兰大，GA 30332，美国;电子邮件：rbeyah@ece.gatech.edu。允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，不收取任何费用，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页或显示器的初始屏幕上显示此通知以及完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要复制，再版，张贴在服务器上，再分发到列表，或在其他作品中使用本作品的任何组成部分，需要事先特定的许可和/或费用。可向出版部索取，ACM，Inc.2 Penn Plaza ， Suite 701 ， New York ， NY 10121-0701 USA ， 传 真 ： 1 （ 212 ） 869-0481 ， 或permissions@acm.org。c 2016 ACM 1094-9224/2016/04-ART12 $15.00DOI：http://dx.doi.org/10.1145/2894760ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月12十二S. Ji等人ACM参考格式：纪守陵，李维清，穆达卡·斯利瓦查，何晶，拉希姆·贝亚。2016年。通用图形数据去匿名化：从移动轨迹到社交网络。ACM传输信息系统安全18，4，第12条（2016年4月），29页。DOI：http://dx.doi.org/10.1145/28947601. 介绍如今，社交网络服务是一项快速增长的业务智能电话技术的发展进一步促进了社交应用和服务的扩散，诸如即时消息（例如，IRC、AIM、MSN、Jabber、Skype）、共享站点（例如，Flickr、Picassa、YouTube、Plaxo）、博客（例如，Blogger、WordPress、LiveJournal）、wiki（例如，Wikipedia、PBWiki、Wolfram MathWorld）、微博（ 例 如 ， Twitter 、 Jaiku ） 、 社 交 网 站 （ 例 如 ， Facebook 、 MySpace 、 Ning 、Google+）和协作网络（例如，DBLP，ArnetMiner）。 由于对企业的巨大商业价值和对社会的巨大影响，社交网络和数据分析吸引了越来越多的研究兴趣[Backstrom et al. 2007;Narayanan and Shmatikov 2009; Srivatsa and Hicks 2012; Ji et al. 2014，2015 a，2015 b]。当用户参与在线社交网络活动（例如，创建个人端口并连接到社交朋友）或利用社交网络功能（例如，发布当前位置或与虚拟社交好友共享信息），人们 另一方面，为了将大量的用户数据用于商业或学术目的，社交网络所有者通常会发布社交数据用于研究（数据挖掘）或将数据传输给商业合作伙伴用于目标广告[Narayanan and Shmatikov 2009]。此外，移动计算和通信技术的巨大进步使得智能手机等移动设备能够收集有关用户的大量信息[Srivatsa and Hicks 2012]。例如，用户可以通过智能手机上的Twitter/Facebook轻松地更新他们的位置位置或显示他们的共享/关注信息。为了保护用户的隐私，社交网络所有者和服务提供商通常在向公众公布数据之前通过删除“个人身份信息（PII）”来匿名化数据。然而，在现实中，这种数据匿名化容易受到一种新的基于社会辅助信息的数据去匿名化攻击[Backstrom et al.2007; Narayanan和Shmatikov2009; Srivatsa和Hicks 2012]。实用性和有效性来自两个基本事实。首先，当网络所有者和服务提供商发布数据时，仅应用朴素的匿名化技术来删除基本的PII。例如，即使对于经过仔细处理（通过未知的采样技术）和匿名化（包含数据扰动）的Netflix Prize数据集，其包含Netflix的500，000个订阅者的匿名电影评级，并出于研究竞赛的目的发布，其结构本身也携带了足够的信息来有效地侵犯隐私[Narayanan and Shmatikov 2008]。此外，现有的匿名化技术（例如，Campan和Truta[2008]， Hay等人 [2008]，Liu和Terzi[2008]，以及Zheleva和Getoor [2007]）有几个限制，例如对对手的社交数据或知识做出不切实际的假设，不可扩展等（详细的限制分析在相关工作部分中显示），这阻止了它 们 在 现 实 中 的 可 行 性 [Backstrom et al. 2007; Narayanan 和 Shmatikov2009;Srivatsa和Hicks 2012]。第二个事实是社会辅助信息的广泛和普遍可用性[Backstrom et al. 2007;Narayanan和Shmatikov 2009;Srivatsa和Hicks 2012]。 正如Narayanan和Shmatikov [2009]以及Srivatsa和Hicks [2012]所指出的那样，对手可以通过多种渠道轻松获得社交辅助信息，例如，学术和政府数据挖掘，广告，第三方应用程序，数据聚合和推断，隐私攻击和获取以及智能传感和收集。即使不太可能获得大规模的辅助信息ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月通用图数据去AnAnonymization：从移动轨迹到社交网络十二少量的辅助知识通常足以成功地破坏隐私。一 些 去 匿 名 化 攻 击 是 针 对 社 交 数 据 [Backstrom et al. 2007; Narayanan andShmatikov 2009]或移动跟踪数据[Srivatsa and Hicks 2012]设计的。然而，现有的工作是有限的，由于一个或几个原因，例如，可扩展性，通用性和鲁棒性。我们的工作在以下部分或全部方面改进了现有的工作首先，我们提出了一种新的基于核心匹配子图（CMS）的自适应去匿名策略，显著提高了去匿名的其次，除了利用节点的局部属性，我们将节点的全局属性纳入去匿名化，而不会产生高的计算复杂度。此外，我们还定义和应用两个新的相似性度量建议去匿名化技术。最后，在这项工作中提出的去匿名化算法是一个更一般的攻击框架。它可以应用于移动跟踪数据和社交数据，有向和无向数据图，以及加权和非加权数据集。我们在相关工作部分（第二节）给出了详细的分析和评论。总之，我们在这篇文章中的主要贡献如下：(1) 我们分析了三个去匿名化指标，即结构相似性，相对距离相似性和继承相似性。通过结构相似性，我们综合考虑了节点的局部和全局拓扑特征，并根据节点的结构特性来量化两个节点之间的相似性。1通过相对距离相似度，从辅助种子信息的角度度量两个节点的相似程度。通过继承相似性，我们量化了两个节点之间的相似性的知识，已经被去匿名化的节点。我们还研究了这三种测量在真实数据集上的作用。通过实验，我们发现，一些匿名的节点是显着区分相对于一些指标，这表明这些节点是潜在的容易去匿名。另一方面，对于具有不明显特征的其他节点，它们也可以被去匿名化，但是具有更粗的粒度。(2) 为了有效地去匿名化，我们综合考虑定义的结构相似性、相对距离相似性和继承相似性，定义了一种统一相似性随后，我们提出了一个基于US的去匿名化（DA）框架，通过该框架，我们迭代地对匿名数据进行去匿名化，并通过去匿名化阈值和映射控制因子提供准确性保证。(3) 为了在不知道匿名数据和辅助数据之间的重叠大小的情况下对大规模数据进行去匿名化，我们将DA概括为Adap，主动去焦虑化（ADA）框架。ADA自适应地从两个核心匹配子图开始进行数据去匿名化，这两个核心匹配子图被定义为估计匿名化数据与辅助数据之间的重叠大小通过巧妙地处理CMS，ADA中的去匿名化被限制在两个相对较小的子图中，具有更多的信息置信度，从而提高了此外，我们还将DA/ADA扩展到匿名数据或辅助数据无法用连通图建模的场景(4) 我们将所提出的去匿名化框架应用于三个著名的移动轨迹：圣安德鲁斯[Bigwood etal.2011]，Infocom06 [Scott et al.2009]和Small- blue [Smallblue 2009]。实验结果表明，该去匿名攻击是非常有效和强大的。只知道1在本文中，我们使用拓扑特征和结构/结构特征可并行性。ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月12：4 S. Ji等人一个种子映射，57. 7%，93. 2%，78。圣安德鲁斯、Infocom06和Smallblue中分别有3%的数据可以成功地去匿名化此外，即使将20%的噪声添加到匿名数据中，80. 8%，50%。7%，60。圣安德鲁斯、Infocom06和Smallblue中仍有8%的数据可以分别成功地去匿名化（使用五个种子映射）。(5) 我们还研究了对社交数据集的去匿名化攻击：Arnet-Miner（一个加权的合著者数据集，由1，127位作者和6，690个合著者关系组成）Google+（两个数据集，一个由5，200个用户和7，062个连接组成，另一个由5，200个用户和7，813个连接组成）和Facebook（63，731个用户和1，269，502个再次，实验结果表明，所提出的去匿名化框架的有效性和鲁棒性。仅基于对五个种子映射的了解，ArnetMiner中96%的用户（具有4%的噪声）和Google+中58%的用户可以成功地去匿名化。更重要和令人惊讶的是，即使是匿名数据和辅助数据之间的重叠，在Facebook中也只有20%，而在Facebook中只有90%。8%的普通用户也可以成功地去匿名化，假阳性错误率为8。6%，根据20个种子映射。此外，我们还分析了叶用户（一个连接的用户）对去匿名性能的影响，根据实际数据的实验。本文的其余部分组织如下。在第2节中，我们调查了最相关的工作。在第三节中，我们给出了数据模型和考虑的数据模型。在第4节中，介绍了去匿名化框架。在第5节中，改进了所提出的去匿名化框架，并将其扩展到一般的大规模社交数据集。我们在第6节中说明并讨论了在真实社交和移动数据集上进行的大量实验的结果。最后，我们在第7节结束本文。2. 相关工作在本节中，我们将介绍相关的工作。我们首先回顾了网络科学的指标，我们利用来衡量匿名用户和辅助用户之间的相似性，特别是结构相似性然后，我们调查了针对社交和移动数据集的特定匿名化技术和去匿名化攻击。最后，我们讨论了区别于现有的去匿名化攻击建议的去匿名化攻击的差异。2.1. 相似性和相似性在我们的去匿名化攻击的设计中，一个关键步骤是测量匿名用户和辅助用户（可以被认为是已知用户，在第3节中正式定义）之间的结构相似性在测量两个节点（用户）之间的结构相似性时，我们使用了网络科学中的几个指标。我们在本小节中简要介绍这些指标。在图论和网络科学中，中心性测量被广泛用于测量图/网络中节点的重要性[Centrality2015;Newman 2010]。在这篇文章中，我们使用度中心性、接近中心性和介数中心性，以及它们的加权版本来度量图中节点的结构属性（正式定义在第4节中给出）。度中心性度量连接到节点的边的数量，它显示了图中节点的局部结构特征（重要性）[Freeeman1978;Newman 2010]。接近中心性度量图中节点到其他节点的平均距离（断开图中的组件 ） ， 这 是 节 点 的 一 个 广 泛 使 用 的 全 局 结 构 特 征 [Newman 2010] 。 它 首 先 由Bavelas[1950]（以远度的倒数的名义）引入。后 来 ，它被F r e e m a n 重新措辞[1978]。ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月通用图形数据去Anatomization：从移动轨迹到社交网络12：5[Rochat2009]将 紧 密 中心 性 扩 展 到 断开 连 接 的 图 的 场景 在 另 一 个 独立 的 工 作 中 ，Opsahl[2010]还将紧密中心性的概念扩展到不连通图。介数中心性度量节点位于其他节点之间的最短路径上的程度，这是节点的另一个广泛使用的全局结构特征[Freeeman 1978;Newman 2010]。它的形式化通常归因于Freeman在Freeman [1978]中。最近，Opsahl等人[2010]将度中心性，贴近中心性和介数中心性的定义推广到加权图。Newman [2010]详细介绍了这三个中心性度量以及其他节点中心性度量，例如Katz中心性，PageRank，Hubs和Authorities。Garg [2009]以及Boldi和Vigna [2014]进行了其他关于图的中心性度量的公理化工作。许多现实世界的图应用程序和挖掘任务利用网络/图相似性，这通常使用网络科学中的三种基本方法进行测量：结构等价，自守等价和正则等价[Similarity 2015;Newman2010]。 在这三种方法中，结构对等是最强的相似形式。在许多实际应用中，它通常被放松到某种弱形式的相似性[Similarity 2015;Hanneman and Riddle 2005]。 沿着这条线并利用图中节点的不同结构特征，已经在各种应用中开发了几种结构相似性度量[Basak etal. 1988; Brandes and Lerner 2004; Zhou et al. 2009; Narayanan and Shmatikov2009;Nilizadeh et al. 2014年 ] 。 例如， Basak et al. [1988] 研 究 使 用 图 论 指 数 确 定Brandes和Lerner[2004]通过放宽公平划分引入了结构相似性，并将概念应用于角色分配（角色提取）。Zhou等人[2009]定义了基于邻域随机游走距离的结构相似性，并将其应用于图聚类。在安全和隐私领域中，结构相似性也被广泛用于测量两个用户关于不同的图论度量（例如，度中心性）[Narayanan and Shmatikov2009; Nilizadeh et al.2014年]。2.2. 分析社交和移动数据社交和移动性跟踪数据现在可以通过多个渠道容易地获得和可用，例如学术和政府数据挖掘 、 广 告 、 第 三 方 应 用 、 数 据 聚 合 和 推 断 以 及 隐 私 攻 击 和 获 取 [Backstrom etal.2007;Narayanan和Shmatikov 2009;Srivatsa和Hicks 2012]。 为了保护公开发布的数据的隐私，常见的方法是通过移除PII（例如，姓名、年龄、社会安全号码）。然而，这种幼稚的数据匿名化通常容易受到去匿名化攻击[Cam- pan and Truta 2008; Hay et al.2008; Liu and Terzi 2008]。因此，提出了几种进一步的策略，其主要思想是通过增加数据本身的自同构来扰动原始数据，这可以使发布的数据不可区分，从而抵御去匿名化（重新识别）攻击。为了保护图数据中敏感关系的隐私，Zheleva和Getoor[2007]根据删除的数据量和保留的隐私量设计了五种不同的隐私保护策略然而，在设计的策略中没有考虑辅助信息对对手的共同可用性Hay等人[2008]将k-匿名引入到社会数据匿名化中。对对手信息的一种然而，在现实中，对手有更多的辅助信息可以轻松获得或只需很小的努力（例如，通过学术和政府ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月||||=||=||12：6 S. Ji等人数据挖掘、广告、第三方应用程序）。另一方面，所设计的k-匿名方案适用于低平均度社交 图[Narayanan and Shmatikov 2009] 。然 而， 事实 是， 社交 图2012年 b]。例如，Google+的连接组件中的节点和边的数量分别为69，501和9，168，660，这意味着平均度为263.8。Campan和Truta[2008]扩展了Hay等人的k-匿名方案[2008]通过定义量化由于边缘泛化而导致的结构信息损失Liu和Terzi[2008]也将类似的k-匿名方法应用于图上的ID匿名化，其中假设对手的先验正如我们之前所指出的，对手可以轻松地或只需很小的努力就可以获得更丰富的辅助信息。更重要的是，正如Narayanan和Shmatikov[2009]所指出的，k-匿名的基石是基于数据2.3. 消除社交和移动数据的与本文最密切相关的作品是Backstrom等人[2007]，Narayanan和Shmatikov[2009]，Srivatsa和Hicks[2012]以及Ji等人。 [2014年]。 Backstrom等人[2007]引入了主动攻击和被动攻击来去匿名化社交数据。对于主动攻击，攻击者应该在数据发布之前创建多个Sybil节点，并在Sybil节点和目标节点之间建立关系（实际上和直观上，要知道何时以及社交数据的哪一部分将被发布，以及何时植入Sybil节点并不简单正如随后的工作[Narayanan and Shmatikov2009]中所分析的那样，许多原因限制了主动攻击的实用性。一个直接的局限性是，主动攻击不可扩展且难以控制，因为社交数据量持续增加[McAuleyand Leskovec 2012; Gong et al. 2012 b]。为了执行主动攻击，需要创建许多Sybil节点和关系/纽带，这是不切实际的。此外，Sybil防御方案[Alvisi et al.2013; Yu et al.2008 a，2008 b，2009]使这一点变得更加困难。另一方面，在真实的在线社交网络中，目标节点没有理由响应来自陌生Sybil节点的连接请求。对于Backstrom等人[ 2007]中的被动攻击，攻击者可以侵犯与他们链接的用户的隐私，这同样适用于小型社交网络，难以扩展到大规模社交数据。Narayanan和Shmatikov[2009]将去匿名化攻击扩展到大规模有向社交网络数据;即，社交数据携带方向信息，其可以用作辅助知识。所设计的去匿名算法包括两个阶段：种子识别和传播。在种子识别阶段，在匿名化图和辅助图之间识别种子映射的集合。在传播过程中，通过采用若干启发式度量，包括偏心率、边方向性、节点度、重访节点和反向匹配，将已识别的种子映射传播到匿名图和辅助图之间的一般映射.Narayanan和Shmatikov[2009]中传播阶段的时间复杂度为O（（E1E2）d1d2）O（n4），其中E1和d1（分别为E2和d2）分别是匿名图（分别为辅助图）的边集基数和度界，n是匿名图或辅助图中的节点数（从顺序角度来看相同）。Srivatsa和Hicks[2012]提出了第一个针对移动性的去匿名化攻击同时使用社交网络作为侧通道。去匿名化过程也包括两个阶段：地标（种子）选择和映射传播。在地标选择阶段，将选择介数得分最高的k个地标。ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月通用图形数据去Anatomization：从移动轨迹到社交网络12：7分别在匿名图和辅助图中作为种子。在传播过程中，三个方案的图匹配（去匿名化），即距离向量，随机生成树，递归子图匹配。为了给出高的图匹配（去匿名化）准确性，将针对所有k！匿名图和辅助图之间的可能界标映射，这是非常耗时的（例如，为了对Smallblue数据集进行去匿名化，该数据集具有125个节点[Smallblue2009]和5个地标，设计的映射传播方案分别需要6.7小时、6.2小时和0.5小时）。因此，可扩展性可能是Srivatsa和Hicks [2012]工作的一个重要限制。Ji等人[2014]研究了图形数据的去匿名性具体来说，他们量化了完全或部分去匿名化匿名图的结构条件此外，根据量化，他们提出了一种无种子的去匿名化攻击，适用于密集和大规模的图。随后，Ji et al. [2015 a]进一步从理论上研究了具有种子知识的社交网络的去匿名性。它们还为使用种子知识完全或部分地去匿名化社交网络提供了条件最近，Ji等人开发了SecGraph，这是一种用于图形数据匿名化和去匿名化的统一开源平台[Ji等人，2015 b; SecGraph 2015]。在SecGraph中，他们实现并评估了11种图匿名化方案、12种图效用度量、7种应用效用度量和15种现代图去匿名化攻击（包括本文中提出的两种攻击他们发现，现有的匿名化方案仍然容易受到一种或多种去匿名化攻击。每个匿名化方案的可验证性程度取决于它保留多少数据以及保留哪些数据实用程序。Nilizadeh等人[2014]研究了如何使用图社区信息来增强现有的基于种子的去匿名攻击（例如，Narayanan和Shmatikov [2009]以及Srivatsa和Hicks [2012]）。他们提出了一个基于社区的去匿名化框架，该框架首先在社区级别，然后在用户级别对图进行去匿名化。2.4. 话以下一些或所有方面将这项工作与现有技术区分开来。首先，在对大型数据集进行去匿名化时，我们根据种子信息在匿名图和辅助图中定义CMS。基于CMS，我们提出了一种新的自适应去匿名策略，非常适合大规模数据的去匿名。遵循这种策略，我们首先对CMS中的节点进行去匿名化，然后通过自适应地跨越两个图中的CMS来传播去匿名化通过这种方式，我们可以显着提高去匿名化的准确性，并降低计算复杂度。其次，度中心度只能表示图中节点的局部性质。在一些匿名数据中，存在具有相似度的许多节点的事实模糊了使用度来匹配/区分节点的有效性或甚至无效。因此，我们包括指示图中节点的全局属性的度量（例如，接近中心性、中间中心性）。此外，除了利用结构知识，我们还定义和应用两个相似性度量，即相对距离相似性和继承相似性，在建议的去匿名化技术。 这提高了去匿名化的效率和准确性。更重要的是，通过在大规模数据集中基于CMS的自适应去匿名化，可以克服包括新的全局度量所引起第三，Narayanan和Shmatikov[2009]中提出的去匿名化策略适用于可以通过有向图建模的社交数据，其中方向信息被假设为对手的免费在这项工作中，我们考虑一个更一般的情况下，ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月十二S. Ji等人i、j--|∈}--|}=i、ji、ji、ji、j=--||∀∈∈}∈ ={}i、ji、ji、jIJ我通过消除方向限制。 我们的去匿名化算法适用于不相关图以及有向图，方法是结合Narayanan和Shmatikov [2009]中的方向启发式。最后，我们还考虑了匿名图的边的潜在权重（关系强度）信息。因此，我们的去匿名化算法在加权图上也是有效的。总之，本工作中提出的去匿名化攻击适用于大规模社交网络数据、移动性跟踪数据、有向/无向数据图和加权/未加权数据图，并且比以前的工作更一般。3. 序言和系统模型3.1. 分析和辅助数据模型3.1.1. 分析数据图。在这篇文章中，我们考虑了可以用无向图来建模的匿名数据，2由G a表示（Va，Ea，Wa），其中Vai iisa节点是节点集（例如，匿名Google+图中的用户），Ea la i，j Va，i和j之间存在联系，是所有链接的集合- 存在于Va中的任何两个节点之间（链接可以是诸如在Google+中的朋友关系或诸如在移动性跟踪St Andrew中的联系人关系），以及W a={Wa|i，j ∈ V a，l a∈ E a，wa是实数}是可能权重的集合asso-与Ea中的链接相关联（例如，在合著者图中，合著者关系的权重如果Ga是一个无权图，我们只需定义对于每个链路la∈Ea，wa=1。对于n_i ∈ V_a，我们定义它的邻集为Na（i）={j ∈V_a|l a∈ E a}。那么，|N a（i）|表示Ga中i的邻居数。 设p a（i，j）是Ga中从i到j的最短路，|p a（i，j）|是p a（i，j）上的链接数（从i到j通过pa（i，j）的链接）。然后，我们定义Pa= {pa（i，j）}为i和j之间的所有最短路径此外，我们定义Ga的直径为D a= max {|p a（i，j）|<$i，j ∈ V a，p a（i，j）∈ Pa}，即最长最短的长度路在G。3.1.2. 辅助数据图。与Narayanan和Shmatikov [2009]以及Srivatsa和Hicks [2012]一样，我们假设辅助数据是在当前在线社交网络中抓取的信息，例如，Twitter上的“关注”关系[Narayanan和Shmatikov 2009]，Flickr上的“联系人”关系，Facebook上的“朋友”关系，以及Google+上的“圈子”关系。此外，类似于匿名化数据，辅助数据也可以被建模为无向图Gu（Vu，Eu，Wu），其中Vu是节点集合，Eu是Vu中的节点之间的所有链接（关系）的集合，并且Wu是与Eu中的链接相关联的可能权重的集合。关于匿名图Ga的定义，我们可以定义iVu的邻域为Nu（i），iVu和jVu之间的最短路集为Pu（i，j）pu（i，j），G u的直径为Dumaxp u（i，j）i，jV u，p u（i，j）Pu（i，j）.另外，我们假设Ga和Gu是连通的。请注意，这不是限制我们的计划。所设计的去匿名算法也适用于Ga和Gu不连通的情况我们将在第5节讨论这一点。3.2. 攻击模型我们的去匿名化目标是尽可能准确地将匿名图Ga中的节点映射到辅助图Gu然后，对手可以依靠2注意，本文中设计的去匿名化算法也可以直接应用于有向图，方法是忽略边上的方向信息，或者结合Narayanan和Shmatikov [2009]中基于边方向的去匿名化启发式。ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月通用图数据去AnAnonymization：从移动轨迹到社交网络十二.（1）.联系我们| |=.=∈.联系我们|∈=/} {}∈表I.圣安德鲁斯、Infocom06、Smallblue和相关社交网络概述圣安德鲁斯Infocom06小蓝通信网络类型通信节点数持续时间（天）粒度（秒）联系人号码WiFi273030018,241蓝牙784120182,951IM12530300240,665社交网络类型社交节点没有。Facebook27DBLP616Facebook400辅助数据，如用户在在线社交网络中创建的投资组合，以侵犯用户形式上，设γ（v）是物理世界中v∈Ga的客观实在然后，理想的去匿名化可以由映射n：Ga→Gu表示，使得对于v∈Ga，（v）=vr，ifvr≠（v）Vu;如果n（v）∈/Vu，其中，a是不存在的特殊指标。现在让M={（v1，v1r），（v2，v2r）， . ，（vn，vnr）}是去匿名化攻击的结果，使得viV a，viV a，n V a，i1，2，. ，n;vir = n（vi），vir ∈ V un {n}， i= 1，2，.，n.然后，如果满足以下条件，则认为vi上的去匿名化是成功的：当γ（vi）Vu时，则有n（vi）γ（vi）;如果γ（vi）∈/Vu，（二）（三）或失败，如果如果γ（vi）Vu，则有n（vi）uuVu，uγ（vi）;当γ（vi）∈/Vu时，则γ（v i）/= γ.（四）在这篇文章中，我们的目标是设计一个去匿名化框架，具有高成功率（准确率）和低失败率。此外，所设计的去匿名化算法有望对噪声具有鲁棒性，并可扩展到大规模数据集。3.3. 数据集在这篇文章中，我们采用了六个著名的数据集来检查设计的去匿名化框架的有效性：圣安德鲁斯/Facebook [Bigwood et al.2011; Srivatsa and Hicks2012]， Infocom 06/DBLP[Scott et al.2009; Srivatsa and Hicks2012] ， Smallbule/Facebook [Smallblue2009;Srivatsa and Hicks2012]， ArnetMiner [Tang et al.2008]、Google+[Gong et al.2012 b]和Facebook [Viswanath et al.2009年]。St Andrews、Infocom06和Smallbule是三个流动性跟踪数据集。圣安德鲁斯数据集包含了在圣安德鲁斯大学部署的27个T-mote用户在30天内的WiFi记录的移动跟踪数据Infocom06跟踪包括在迈阿密君悦酒店举行的IEEEINFOCOM 2005中，78名用户携带iMotes进行了4天的蓝牙目击Smallbule数据集由企业网络上的125个即时通讯用户之间的联系人组成三种迁移率曲线的概述见表I。我们采用与以前的工作完全相同的技术[Sri- vatsa和Hicks2012]来预处理三个流动性跟踪数据集，以获得三个通用图数据去AnAnonymization：从移动轨迹到社交网络十二ACM Transactions on Information and System Security，卷。号184、第12条，公布日期：2016年4月十二S. Ji等人匿名数据图表。为了去匿名化上述三个匿名化的移动性数据轨迹，我们采用与这三个移动性轨迹相关联的三个辅助社交网络数据集[Srivatsa和Hicks2012]。对于圣安德鲁斯数据集，我们有一个Facebook数据集，指示跟踪中T-mote用户之间的“朋友”关系。对于Infocom06数据集，我们使用了一个由DBLP获得的616位作者组成的合著者数据集，这表明了INFOCOM 2005所有与会者之间的“合著者”关系。对于Smallblue数据集，我们有一个Facebook数据集，表示来自与 Smallblue 相同企业的 400名员工之间的请注意 ，Infocom06和Smallblue对应的社交网络数据集是它们的超集。我们还将所提出的去匿名化攻击应用于社交数据集：ArnetMiner [Tang et al.2008]、Google+[Gong et al.2012 a]和Facebook [Viswanath et al.2009年]。ArnetMiner是一个在线学术社交网络。在本文中，所使用的数据是从ArnetMiner在2011年的主题“数据库系统/XML数据”中提取的对于每一个合著者关系，都有一个与之相关的权重，表示两个作者合著的论文数量。因此，ArnetMiner数据可以通过以下方式建模：加权图此外，我们知道ArnetMiner数据的真实情况。当使用它来检查所呈现的去匿名化攻击时，我们将首先通过添加不同级别的噪声来对其进行匿名化作为一个新的社交网络，Google+于2011年7月初推出我们使用两个Google+数据集，分别创建于2011年7月 19日和8月6日[Gong etal.2012a]，分别表示为JUL和AUG。JUL和AUG都有5,200名用户及其个人资料。此外，7月有7,062个连接，8月有7,813个连接通过洞察力分析[Gong et al.2012年a]，在八月出现的一些连接可能不会出现在七月，反之亦然。这是因为用户可以添加新连接或禁用现有连接。此外，这两个数据集被预处理为无向图。由于我们知道JUL和AUG的手工标记的基础事实，我们将通过使用AUG作为辅助数据对JUL进行去匿名化，然后使用JUL作为辅助数据对AUG进行去匿名化来检查所提出的去匿名化框架Facebook数据集由63，731名用户和1，269，502个“朋友”关系（链接）组成。为了使用这个数据集来检查所呈现的去匿名化攻击，我们将基于已知的手工标记的地面事实对其进行预处理。对于更详细的实验设置和数据处理，我们将在实验部分（第6节）中进行描述4. 解除匿名从宏观上看，所设计的去匿名化攻击框架包括两个阶段：种子选择和映射传播。在种子选择阶段，我们识别从匿名化图Ga到辅助图Gu的少量种子映射，这些种子映射用作地标以引导去匿名化。在映射传播阶段，我们通过综合利用多个相似性度量来去匿名化Ga由于种子选择可以通过许多现有的策略来实现，并且不会是我们的主要技术贡献，因此我们将简要讨论它，并重点讨论如何设计有效的映射传播方案。4.1. 种子选择和映射生成在我们的去匿名化框架（以及其他去匿名化攻击）中，种子选择的合理性和可行性在于三个现实。首先是大量社交数据的共同可用性，这是获得少量种子的开放而丰富的来源。例如，（1）对于学术和政府数据挖掘发布的数据，可以在ACM Transactions on Information and System Security