社交网络中的位置隐私保护研究

刘佳　方贤进　康佳

摘要：随着智能终端设备和社交网络服务的广泛使用，移动互联网发展的一个重要趋势是社交、位置和移动相融合，在这些应用中，位置是一项非常重要的信息。该文从位置隐私泄露的风险出发，介绍了几种位置隐私保护技术，比较它们的优劣，提出了移动感知的匿位区域生成方法，通过信息熵理论将用户位置的不可推测性最大化，实现了社交网络中个人隐私保护。

关键词：社交网络；个人位置；隐私保护；匿名模型

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）28-6616-04

随着智能终端设备（如手机、平板电脑等）和社交网络服务（SNS）的广泛使用，移动互联网发展的一个重要趋势是社交、位置和移动相融合[1]。不仅社交网站如FaceBook、Twitter、新浪微博等都扩展了位置服务（Location-base Service）功能，传统的位置服务如周边信息搜索（如微信/QQ）也加入了社交化元素，形成了全新的移动社交网络。在这些应用中，位置是一项非常重要的信息。按用途来分，位置数据可分为三类：第一类是作为服务的输入信息，比如要查找周边的事物如餐馆、银行，需要用户提供当前的位置；第二类是用户主动分享的数据，比如位置签到；第三类是作为服务的使用代价，现在有不少应用提供免费使用，但会要求访问用户位置等个人信息。

位置也是一项非常敏感的信 息，除了位置信息本身涉及个人隐私，通过位置信息还可以推测出用户的其它信息。根据爱伦·威斯汀 （Alan Westin） 在《Privacy and Freedom》一书 [2]中的定义，隐私是指个人或团体决定何时、在何种程度下、以何种方式把关于自己的信息传达给他人的权利。换句话说，隐私是指用户不想泄露的个人信息。因此，位置隐私保护主要针对上述第一类位置信息，使用时做到既能保护位置信息，又不影響正常的位置服务。

位置信息的不当使用或外泄可能会造成各种各样的风险。比如，通过统计用户常去的地方，攻击者可推测用户的私人信息，如兴趣爱好、生活习惯、健康状况等等。又如，知道了用户晚上经常待的地方，攻击者可以推断用户的家庭住址，进而估计用户的收入水平等。另外，如果广告商获知了用户的当前位置，就可以向用户推送与位置相关的广告，可能对用户造成不必要的骚扰。随着大数据（big data）时代的到来，位置信息外泄的风险变得更大了，原因在于攻击者从各种渠道可获取的数据更多更广，运用多数据源的交叉比对、协同分析等手段可对个人隐私信息进行更精准细致的推测[3]。

目前，工业界对位置隐私保护通常采用的方法是基于规则协议的策略，在访问用户位置前需取得用户的授权。比较好的方法是遵循“最小特权原则”，即服务提供商只会在必要的情况下存取用户的位置信息，并且不会长期保存用户数据而用于其它非授权的用途。但这种方法的前提是对服务提供商有足够的信任度，同时也对服务提供商的系统可靠性提出了非常高的要求。不幸的是，即使是完全遵从安全规范的服务提供商，也无法避免系统性的安全漏洞，用户的个人信息依有可能外泄。另一种做法是移除用户的ID标识信息，对位置数据进行匿名化处理。最近美国麻省理工学院的研究人员通过对150多万移动用户长达15个月的轨迹数据分析发现，人们的移动模式是非常独特的，只要给出4个独立的位置点，就能识别出95%以上的用户[4]。换言之，对位置数据进行简单的匿名化处理（如去掉ID标识）不足以保护用户的位置隐私。

因此，学术界近年来致力于研究更可靠的位置隐私保护技术，希望最大限度地保护用户位置等个人信息。该项研究主要面临以下挑战：首先，位置隐私保护是个性化的需求。不同的用户有不同的隐私保护要求。即使是同一用户，在不同的时间、地点对隐私保护的要求也可能不同。其次，位置隐私保护与位置信息可用性是一对矛盾体。服务提供商需要获得用户的位置信息来处理与位置相关的服务请求，而这又恰恰是用户希望保护的个人隐私信息。因此，位置隐私保护技术需要在隐私保护与信息可用性之间取得一个很好的平衡。

针对这些挑战，现有的位置隐私保护技术大致分为两类：1）时空匿位（cloaking）技术[5-12]：降低位置信息的时空粒度，根据易受到基于背景知识的攻击，用一个时空区域来表示用户的大概位置。2）零隐私泄露技术[13-18]：采用计算密码学的方法，对位置数据进行加密处理，进而在密文空间内进行相关信息搜索服务的计算。时空匿位技术对位置隐私的保护力度有限，容易受到基于背景知识的攻击，但其计算代价比较低。而零隐私泄露技术的计算代价比较高，但可以做到对位置隐私的完全保护，但降低了位置信息的可用性。

1 时空匿位保护技术

1.1 基于粒度的空间匿位

时空匿位技术允许用户定义可暴露的位置粒度。文献[5～6]着重考虑如何在满足用户隐私保护要求的前提下将匿位区域最小化，并没有考虑服务请求的内容。以最近邻查询为例，假设用户想搜索最近的餐馆，但只允许在面积为T的范围内暴露位置。一个简单直接的做法是根据用户当前的位置随机生成一个面积为T并且包含该用户的区域（如图1（a）中黄色框所示）作为匿位区域向服务器发出查询请求。服务器返回该匿位区域内所有可能点的最近邻（g， g1， g2） 给用户，然后用户根据自己的精确位置提炼出真正的结果（g）。

这种方法有两个不足：一是服务器查询处理时间较长，因为需要处理匿位区域内所有可能点的最近邻查询；二是查询结果返回时间较长，因为没有考虑服务请求而随机生成的匿位区域可能导致太多的最近邻结果需要返回，增加了数据传输量。

为了克服这些不足，文献[7]提出利用沃罗诺伊元（Voronoi cell）的概念来生成匿位区域。一个对象的沃罗诺伊元定义为一个多边形区域，在此区域内所有查询点的最近邻都是该对象（如图1（b）所示）。因此，一个匿位区域的最近邻结果就是它们的沃罗诺伊元与该匿位区域相交的对象。这样，对于给定的一个匿位面积T，为了将返回结果的数目最小化，最优的匿位区域应该选取和最少个数沃罗诺伊元相交的区域，比如图1（b）中的匿位区域。另外，既然沃罗诺伊元是潜在的查询点集合，一个更优的方法是直接请求返回对象，比如图1（c）中的g。这意味着用户可能的位置是在g的沃罗诺伊元内，所以g的沃罗诺伊元可以理解为该用户的匿位区域。如果g的沃罗诺伊元面积没有达到匿位面积T，就可以要求返回邻近的更多对象，直到它们的沃罗诺伊元面积之和超过T。为了实现此方法，该文设计了新型的沃罗诺伊元索引，以便用户可以快速有效地选取需要返回的结果，同时又满足空间匿位的粒度要求。此外，对于连续查询中基于用户移动模式的攻击，该文提出移动感知的匿位区域生成方法[8]，通过信息熵理论将用户位置的不可推测性最大化。

1.2 位置K匿名

基于粒度的空间匿位技术比较直观，但有可能导致查询隐私的泄漏。假设图2中用户从绿色的匿位区域发出一个内容敏感的匿名查询请求。如果攻击者从其它数据源得知当时只有用户A在该匿位区域内，那么就可以把用户A和该敏感查询关联起来。为了解决此问题，文献[9]最早把K匿名的概念应用到位置隐私保护上，提出了位置K匿名，即一个用户的匿位区域应覆盖至少K-1个其它用户，以至于这K个用户是不可分辨的。在图2中，设K为3，那么用户A的匿位区域可以为红色框包围的区域。这样，即使攻击者知道用户的位置，也无法和匿位区域内3个用户中的某一个关联起来，从而降低了隐私泄漏的风险。不过，在用户密集的地点单独使用位置K匿名生成的匿位区域面积较小（如图2中蓝色的匿位区域）。为了兼顾位置隐私及查询隐私保护，一般要求空间的匿位粒度也要达到一定的阈值。

为了实现位置 K 匿名，文献[5，6]需要一个可靠的代理服务器来搜集不同用户 的位置信息，然后进行匿名及匿位化处理。然而在此过程中，代理服务器可能获知用户的精确位置。为了消除由代理服务器泄漏 位置信息带来的风险，文献[10]提出了一个无须用户提供具体位置信息的方案，主要思想是利用用户的邻近信息来生成匿位区域。具体来说，服务器首先获取用户的邻近信息，计算出最优的K用户群组；然后用安全界定的方法 动态地产生能覆盖全部K个用户的匿位区域。此外，针对连续查 询中基于历史K匿名位置的攻击及位置数据发布中敏感事件的K匿名保护，文献[11，12]给出了相应的解决方案。

2 零隐私泄露的位置保护技术

2.1 近邻检测

鉴于地理位置社交网络的日趋活跃，近邻检测（proximity detection）成为一种基础服务。一般而言，近邻检测要求移动用户向服务器上传明文空间中的位置，后者以此检测两个或多个移动用户是否是近邻，即判断距离是否小于某一阈值。文献[13]提出了一种“grid-and-hashing”的方法，将空间用网格整齐划分为均一的单元（cell），然后把用户所在单元的标识符（ID） 进行不可逆哈希转换后发送给服务器，使得服务器仍然可以进行近邻检测，但无法得知每个用户的具体位置。

然而该项技术的问题是，由于网格的划分是预先指定的，因此存在假阴性的检测结果，即虽然两个移动用户距离很近，但由于被划分到不同的单元中，导致他们上传到服务器的哈希值不同。鉴于此，文献[14]提出了“网格覆盖”技术（如图3 所示）：通过应用一系列相互交错的网格，使得每个用户有一个对应的哈希向量，如果两个移动用户在某一向量维度上拥有相同的哈希值，则表明他们是近邻。显然，网格的摆放和布局会对减少假阴率产生很大影响。在文献[14]给出了用户位置随机分布模型下的最优网格覆盖方案。通过实验，发现最优布局比随机布局减少了一半的网格需求，例如16个网格在最优布局下可以达到32个网格在随机布局下同等的10%左右的假阴率。

文献[14]研究了在网格覆盖技术下，用户在移动过程中哈希值的更新上传问题。传统技术要求用户在离开本单元后立即更新，以保证近邻检测结果的准确性。然而考虑到很多情况下用户可能与所有需要进行近邻检测的好友都相距甚远，这样的更新策略费时费力，因此文献[14]提出了基于网格层阶的更新策略，将每个用户在当前位置上无须进行更新的范围最大化，最大程度地降低因用户移动带来的更新代价。实验证明，对于一个数万人的地理位置社交网络，该策略可将每检测点（checkpoint）的用户上传开销控制在数百字节范围内。

2.2 零知识地理信息检索

基于位置的信息检索是移动社交网络中最基础的服务之一。用户通过向网络服务器提交自己的位置，来检索与该位置相关的信息。随着信息产业的发展，这些位置相关的信息已成为服务提供商的无形资产，故而保护它们防止用户恶意攫取也成为重要的问题。一个流行的例子是用于分享各类安全和非安全（例如有钓鱼风险）的Wi-Fi 热点共享数据库。用户可以通过提交自己的位置获取附近的该类Wi-Fi热点信息。可是考虑到上述数据隐私的问题，不能仅仅为了保护用户位置隐私而将整个数据库保存在客户端。

文献[15]集中研究了可以同时保护用户位置隐私和数据库隐私的零知识检索算法，即用户无法获取除查询结果外的任何数据，而服务器亦无法得知用户的查询内容：鉴于过去密码学所提出的技术[16-17]由于代价过高而无法直接应用于海量数据，文献[18]中整合最新的同态加密（homomorphic encryption）和有条件不经意传输（conditional oblivious transfer）并提出了一种基于树形索引的不经意遍历框架，包括索引、剪枝、预计算等，解决了键值存储下海量数据查询中的双向隐私保护问题。实验证明，与直接应用密码学技术相比，该方法将原本线性的时间和传输复杂度压缩到对数级，从而使得在大数据时代下保护双向隐私成为可能。

3 结束语

如何保护个人位置隐私正受到学术界及工业界越来越多的重视。该文从位置隐私泄露的风险出发，介绍了几种位置隐私保护技术。这些技术在隐私保护力度和计算代价方面各有优劣，采用哪种技术应结合具体的应用场景。展望未来，新的位置隐私技术需要考虑用户社交关系对位置隐私泄漏造成的影响。比如，用户A分享了与用户B在一起的信息，那么这两个用户的位置信息应受到同样的保护，否则任何一方的位置泄漏都会影响到另一方。因此，未来可以研究结合社交關系的新型位置隐私模型及技术，以便能全方位地保护用户的个人隐私信息，让用户可以放心地使用移动社交网络中的各项应用服务。

参考文献：

[1] 李德毅.大数据时代的位置服务[J].第七届中国电子政务高峰论坛主题演讲，2013.

[2] Alan F. Westin. Privacy and freedom， Bodley Head， 1970.

[3] McKinsey Global Institute. Big data： the next frontier for innovation， competition， and productivity，2011.

[4] Y.-A. Montjoye， C. A. Hidalgo， M. Verleysen， and V. D. Blondel. Unique in the crowd： the privacy bounds of human mobility. Scienti?c Reports， 2013.

[5] B. Gedik and L. Liu. Protecting location privacy with personalized k-anonymity： architecture and algorithms. IEEE Transactions on Mobile Computing， 2008； 7（1）： 1-18.

[6] C.-Y. Chow， M. F. Mokbel， and W. G. Aref. Casper： query processing for location services without compromising privacy. ACM Transactions on Database Systems， 2009，34（4）， 24.

[7] H. Hu and J. Xu. 2PASS： Bandwidth-optimized location cloaking for anonymous location-based services. IEEE Transactions on Parallel and Distributed Systems （TPDS）， 2010； 21（10）： 1458-1472.

[8] J. Xu， X. Tang， H. Hu， and J. Du. Privacy-conscious location-based queries in mobile environments. IEEE Transactions on Parallel and Distributed Systems （TPDS）， 2010：21（3）： 313-326.

[9] M. Gruteser and D. Grunwald， Anonymous usage of location-based services through spatial and temporal cloaking. ACM MobiSys， 2003.

[10] H. Hu and J. Xu. Non-exposure location anonymity. IEEE ICDE， 2009.

[11] X. Pan， J. Xu， and X. Meng. Protecting location privacy against location-dependent attacks in mobile services. IEEE Transactions on Knowledge and Data Engineering （TKDE）， 2012； 24（8）： 1506-1519 .

[12] H. Hu， J. Xu， S. T. On， J. Du， and J. K. Ng. Privacy- aware location data publishing. ACM Transactions on Database Systems （TODS）， 35（3）， July 2010.

[13] L. ?ik?nys， J. R. Thomsen， S. ?altenis， M. L. Yiu， and O. Andersen， A Location privacy aware friend locator， Proc. of SSTD， 2009， 405-410.

[14] H. P. Li， H. Hu， and J. Xu. Nearby Friend Alert： Location anonymity in mobile geosocial networks. IEEE Pervasive Computing （PC）， 2013， 12（4）： 62-70.

[15] H. Hu， J. Xu， C. Ren and B. Choi. Processing private queries over untrusted data cloud through privacy homomorphism. IEEE ICDE， 2011.

[16] A. Yao， Protocols for secure computations， Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science， 1982.

[17] I. F. Blake and V. Kolesnikov， Strong conditional oblivious transfer and computing on intervals， Proceedings of ASIACRYPT， 2004.

[18] H. Hu， J. Xu， X. Xu， K. Pei， B. Choi， and S. Zhou. Private search on key-value stores with hierarchical indexes. IEEE ICDE， 2014.