Olli Huang作者Synced Global制作Geek AI编译Qintong Wu编辑

你的隐私还安全吗?社交网络中浏览历史的去匿名化

论文链接:http://randomwalker.info/publications/browsing-history-deanonymization.pdf

关于作者

前三位作者都来自斯坦福大学,第四位作者 Arvind Narayanan(现为普林斯顿大学助理教授),是该研究的绝对核心。虽然 Narayanan 当时仍然在德克萨斯大学奥斯汀分校攻读博士学位,但是他和他的导师 Vitaly Shimatikov(现康奈尔大学科技校区教授)在Netflix 举办的「Netflix 大奖赛」中(该比赛旨在寻找更好的协同过滤算法 [1]),证明了对 Netflix 提供的匿名用户信息进行「去匿名化」的可能性。因此,毫无意外地,热衷于去匿名化技术的 Narayanan 博士,这一次又准备好展示是否可能对 web 浏览数据和社交文件的链接进行去匿名化处理。

论文亮点

1. 研究问题陈述

在本文中,作者提出了一个问题:是否可能对社交网络中的浏览历史进行去匿名化呢?

令人生畏的是,答案是肯定的!而且「去识别化」之后的浏览数据仍然能够反推出产生浏览历史的原始文件。他们的研究还提出了应用层的匿名化之所以是 Tor(洋葱路由)的阿基琉斯之踵(即要害)的另一个原因,这些现有的匿名系统本应该保护用户的身份不被泄露。

他们的去匿名化方法基于以下的观察:我们通常只在社交网络中关注一组与众不同的用户/账号,并且 web 浏览历史包含我们点击过的链接和访问过的页面。通常情况下,我们更有可能点击被我们所关注的用户/账号所分享的页面。

我们点击过的链接、关注的用户/账号会泄露我们的身份。

本文作者通过创建一个用户浏览行为模型将这个去匿名化的问题形式化,接着推导出对于社交网络中个人资料的最大似然估计

2. 本文贡献

作者声明他们已经做出了以下三个主要的贡献:

2.1 去匿名化策略

在三个假设条件下,建立一个 web 浏览的程式化模型:

(1)一个用户的 web 浏览历史由一个独立同分布的 URL 序列组成,我们将其表示为 H1, ... , Hn,其中 Ht 代表用户 i 访问的第 t 个 URL。

(2)每个用户 i 有一组个性化的推荐链接 Ri,即在 feed 流中出现的链接的推荐集合,它是由用户 i 已关注的人发布的。

(3)如果一个链接在用户的推荐集合中出现,那么该用户就更有可能访问它。并且一个对于用户 i 来说特定的乘法因子 ri 描述了对于这个推荐集合的响应能力。

因此,用户 i 的浏览行为由这个推荐集合 Ri(一组在用户的 feed 中存在的链接)和推荐因子 ri 控制。

定理 1 :以下是一个用户浏览行为模型的形式化定义。

给定一个匿名浏览历史 Ht,以及一组带有推荐集合 C = {R1, ... , Rk} 的候选用户,由此推导出最大似然估计 R^ 和 r^。并且 R^ 是最有可能生成给定的浏览历史的候选者。

两个可选的候选者排序策略

为了提供关于提出的最大似然估计策略(该策略试图将给定的浏览历史和候选用户中最有可能的推荐集合关联起来)的直观思路,他们比较了最大似然估计和另外两种可选方案,即文中所说的:交集大小方法(Intersection Size method)和 Jaccard 方法。

(1)交集大小方法

交集大小方法将一个给定的浏览历史 H 赋给推荐集合 R,该集合包含了给定浏览历史中最多的 URL。然而,这种方法可能偏向于选择较大的推荐集合,即推荐集越大的话,它越有可能拥有给定浏览历史汇总最多的链接。

找到使得下式最大的候选者集合

(2)Jaccard 方法

为了调整推荐集合的大小,Jaccard 方法将一个给定的浏览历史 H 和一个推荐集合 R 相关联,这个推荐集合 R 和浏览历史 H 有最大的 Jaccard 相似度,记作:

正如我们在很多情况下所看到的那样,这个推荐集合 R 往往比浏览历史 H 规模大,换句话说,在用户的 feed 中的链接通常都比用户实际上点击过的浏览历史中的链接多。

因此,最大化 Jaccard 相似度就约等于找到了能够最大化下式的候选者集合:

图 3 说明了在给定浏览历史中的 URL 的数量超过 10 的时候,我们将三种策略的准确率进行对比,发现定理 1 的最大似然估计策略的性能优于交集大小方法和 Jaccard 方法。

图 3: 三种候选者排序方法在合成的浏览历史上的去匿名化准确率:定理 1 的最大似然估计、在候选者的 feed 中出现的历史链接数(交集大小方法)、Jaccard 相似度方法。

而图 4 则描绘了当浏览历史充满噪声最大似然估计准确率,即浏览历史中混入了一个确定比例的形如「朋友的朋友」的链接。在这种设定下,我们提出的最大似然估计方法的准确率仍然较高。

图 4: 在不同的噪声水平下,我们在合成的浏览历史上获得的去匿名化准确率


2.2 去匿名化系统设计

实时去匿名化系统

图2描绘了我们提出的这个系统的架构。首先,该系统从 Twitter 上接受一个匿名浏览历史,然后搜索包含接收到的历史中任意链接的所有 tweet(用户的帖子)。搜索结果会被发送给负责寻找搜索结果中所找到博主的所有粉丝的爬虫。然后,我们会使用去匿名化策略计算每一个粉丝产生接收到的浏览历史的最大似然。

为了收集网络数据,即粉丝列表,我们采取了一种贪婪的缓存策略:后台监听器监听推文(tweet)的数据流,并选择那些拥有 1 万到 10 万粉丝的用户。接着,将这些用户添加到网络缓存中,并且通过实时去匿名化过程爬取数据。因此,我们提出的去匿名化策略同时依赖于缓存的(或预取的)网络数据和实时信息。

                           图 2:web 浏览历史的实时去匿名化系统架构图。
2.3 仿真和实验

作者在仿真的浏览历史数据上评估去匿名化策略,并且证明了给定一个由超过 30 个 Twitter 链接组成的浏览历史,我们可能在超过 50%的情况下推断出相应的用户画像。

除了仿真之外,他们还对大约 400 位用户贡献的真实世界浏览数据进行了实验,其中超过 70% 的用户都被准确识别。作者进一步指出,许多网站都嵌入了在线追踪器,旨在识别具有特定浏览历史的用户,一边进行去匿名化攻击,这使用户的隐私受到威胁。

作者指出,他们提出的去匿名化策略可用于「任意类型的事务性数据,并且对带噪声的观测值有很强的鲁棒性,可以推广到大范围的早期去匿名化攻击」。此外,他们成功地从超过 3 亿候选者中识别出正确的 Twitter 信息。据作者所知,这是目前最大规模的去匿名化挖掘案例。

图 5 展示了作者进行的在线去匿名化实验的三张截图。用户可以上传他/她的浏览历史进行去匿名化,并且作者所提出的最大似然估计系统会返回浏览历史中有匹配的链接的候选用户的测试结果。

图 5:在线实验的截图。


相关工作

在去匿名化领域有大量的文献,作者发现了「连锁攻击」,即根据用户行为证明其独特性/特异性,和他们的研究最为相似。

许多类型的数据容易受到电影评论历史的事物记录 [2]、位置轨迹 [3,4]、信用卡元数据 [5],以及写作风格 [6] 等的连琐攻击。

作者发现,之前唯一研究浏览历史独特性的研究是 Olenjnik 等人 [7] 所做的,这项研究被记录在《Why Johnny can’t browse in peace: On the uniqueness of web browsing history patterns》一文中。当只有 50 个链接时,他们可以在拥有约 370,000 名用户的数据集中识别出 42%的用户身份/指纹,并且这种用户的「行为指纹」在一段时间内是稳定的。

评论

作者十分慷慨地提醒我们:「只要每个用户的订阅列表可以被推断、内容是公开的、并且用户访问的(web)站点上的链接足够多,任何社交媒体网站可以被用于这样的(去匿名化)攻击。」

对于我们来说,事先知道我们在社交网络上分享的哪些内容是可以推断或者去匿名化的是十分困难的。而且在当下的信息时代,仅仅因为潜在的攻击而不去点击链接也是不可能的......但是有一件事,也可能是我们唯一能做的一件保护我们的隐私免于侵害的事,就是通过编辑我们的社交网络隐私设置保持私人生活「隐私化」:在向公众发布个人信息之前三思,以防被躲在暗处的恶意攻击者识别出身份。你给出的每一个赞,每条你留下的评论,甚至是你在社交网络上的关注列表,都可能揭示出你的身份。

保持低调可能是一种美德,在虚拟世界中更是如此,这全是为了安全!


参考文献

[1] https://en.wikipedia.org/wiki/Arvind_Narayanan

[2] A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages 111–125. IEEE, 2008.

[3] Y.-A. De Montjoye, C. A. Hidalgo, M. Verleysen, and V. D. Blondel. Unique in the crowd: The privacybounds of human mobility. Scientific reports, 3, 2013

[4] C. Y. Ma, D. K. Yau, N. K. Yip, and N. S. Rao. Privacy vulnerability of published anonymous mobility traces. IEEE/ACM Transactions on Networking, 21(3):720–733, 2013.

[5] Y.-A. De Montjoye, L. Radaelli, V. K. Singh, et al. Unique in the shopping mall: On the reidentifiability of credit card metadata. Science, 347(6221),2015

[6] A. Narayanan, H. Paskov, N. Z. Gong, J. Bethencourt, E. Stefanov, E. C. R. Shin, and D. Song. On the feasibility of internet-scale author identification. In IEEE Symposium on Security and Privacy ,2012

[7] L. Olejnik, C. Castelluccia, and A. Janc. Why Johnny can’t browse in peace: On the uniqueness of web browsing history patterns. In 5th Workshop on Hot Topics in Privacy Enhancing Technologies, 2012.

理论
1
相关数据
协同过滤技术

协同过滤(英语:Collaborative Filtering),简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要。协同过滤又可分为评比(rating)或者群体过滤(social filtering)。其后成为电子商务当中很重要的一环,即根据某顾客以往的购买行为以及从具有相似购买行为的顾客群的购买行为去推荐这个顾客其“可能喜欢的品项”,也就是借由社区的喜好提供个人化的信息、商品等的推荐服务。除了推荐之外,近年来也发展出数学运算让系统自动计算喜好的强弱进而去芜存菁使得过滤的内容更有依据,也许不是百分之百完全准确,但由于加入了强弱的评比让这个概念的应用更为广泛,除了电子商务之外尚有信息检索领域、网络个人影音柜、个人书架等的应用等。

最大似然估计技术

极大似然估计是统计学中用来估计概率模型参数的一种方法

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

暂无评论
暂无评论~