评估位置邻近服务的隐私保证及攻击防御策略—研究与实践调查(CCS概念)

+Ⓧ评估位置邻近服务的隐私保证乔治·阿杰罗斯，泰奥菲洛斯·佩齐奥斯，苏芬尼·西瓦科恩，和Angelos D. KEROMYTIS，网络安全实验室，哥伦比亚大学JASON POLAKIS，伊利诺伊大学芝加哥分校计算机科学系基于位置的服务已经成为日常生活中不可或缺的一部分。为了解决从位置信息的使用和共享中出现的隐私问题，社交网络和智能电话应用已经采用位置邻近方案作为平衡用户隐私与效用的手段不幸的是，尽管有大量关于这个主题的学术文献，但大型服务提供商采用的方案并不总是正确设计或实现的，使用户容易受到位置泄露攻击。这种攻击最近受到广泛宣传，因为在某些情况下，它们甚至使压迫政权的公民面临生命危险。在本文中，我们系统地评估了流行的基于位置的服务和移动应用程序部署的防御措施，我们提供的理论基础，目前采用的邻近模型的隐私保证，设计实际的攻击，为每种情况下，并证明严格的界限进行成功的攻击在实践中所需的查询数量。为了评估我们方法的完整性，我们对流行的服务进行了广泛的实验，包括Facebook，Foursquare和Grindr。我们的研究结果表明，即使上述服务实现了各种隐私保护技术来保护他们的用户，他们仍然容易受到攻击。特别是，我们能够精确定位Facebook用户在其确切位置的5米范围内。对于Foursquare和Grindr，即使启用了最严格的隐私设置，在90%的情况下，用户的位置也在15米范围我们的攻击非常高效，在几秒钟内完成。Facebook和Foursquare承认了我们调查结果的严重性，这两家公司都遵循了我们的建议，并在其生产系统中采用了我们设计的安全接近方案。随着提供定位功能的移动应用程序数量的不断增加，服务提供商和软件开发人员必须能够评估其服务提供的隐私保证为此，我们讨论了目前所有主要服务都可以采用的可行防御措施，并提供了一个开源测试框架，供希望评估提供邻近功能的应用程序的隐私保护特性的研究人员和服务提供商使用。CCS概念：信息系统→基于位置的服务;社交网络;。安全和隐私→社交网络安全和隐私;隐私保护;附加关键词和短语：基于位置的服务、位置隐私、位置邻近、用户分布攻击、空间伪装这项工作得到了国家科学基金会的支持，资助号为CNS-13-18415。作者地址：G. Argyros，T. Petsios，S. Sivakorn和A. D. Keromytis，Computer Science Department，Columbia University in the City of New York，1214 Amsterdam Avenue，New York，NY 10027;电子邮件：{argyros，theofilos，suphannee，angelos}@cs.columbia.edu; J.伊利诺伊大学芝加哥分校计算机科学系摩根街MC 152，芝加哥，IL 60607;电子邮件：polakis@uic.edu。允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，不收取任何费用，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页或显示器的初始屏幕上显示此通知以及完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要复制，再版，张贴在服务器上，再分发到列表，或在其他作品中使用本作品的任何组成部分，需要事先特定的许可和/或费用。可向出版部索取，ACM，Inc.2 Penn Plaza ， Suite 701 ， New York ， NY 10121-0701 USA ， 传 真 ： 1 （ 212 ） 869-0481 ， 或permissions@acm.org。c 2017 ACM 2471-2566/2017/02-ART12 $15.00DOI：http://dx.doi.org/10.1145/3007209ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月12十二G. Argyros等人ACM参考格式：放大图片作者：George Argyros，Theofilos Petsios，Suphannee Sivakorn，Angelos D. Keromytis和JasonPolakis。2017.评估位置邻近服务的隐私保证。ACM Trans. Priv. Secur. 19，4，第12条（2017年2月），31页。DOI：http://dx.doi.org/10.1145/30072091. 介绍在移动设备的使用已经成为日常生活的组成部分的时代，社交网络和移动应用正在为用户提供越来越丰富的基于位置的特征集合然而，除了它提供的好处之外，这种功能还使用户面临各种各样的威胁，从推断敏感数据[Minami和Borisov2010]（例如，医疗问题，政治倾向和宗教信仰），身体风险，如跟踪[Scheck 2010]。此外，最近的文章揭示了位置隐私的威胁形势非常复杂：政府机构一直在使用PRISM等程序大规模监视社交网络用户[Greenwald and MacAskill 2013]，执法机构一直在针对使用虚假社交网络帐户的用户，以便通过监控他们的签到行为来访问他们的个人数据并跟踪他们的行踪[Larwald 2010;Police Forum 2013]。泄露用户的位置是一个重大的2013];因此，服务正在采用位置邻近度的更面向隐私的方法：通知用户谁在附近，以及在什么距离，而不透露实际位置。然而，当服务暴露了到用户的确切距离时，三边测量攻击就变得可行了。最近媒体上出现了太多这样的例子，最值得注意的是埃及政府使用三边测量来定位和监禁同性恋约会应用程序的用户[Paton2014;Noack 2014]。很明显，保护用户的位置隐私是一个紧迫的问题;在某些情况下，它甚至可能是一个生死攸关的问题。这种令人震惊的事件引起了流行服务的注意，反过来，这些服务已经部署了防御机制来防止本地化攻击。 尽管学术界已经做出了广泛的努力来解决位置隐私的问题[Zhong等人，2007;S. 2009;Shokrietal. 2011;Narayananetal. 2011]，提供基于位置的功能的服务在采用所提出的解决方案方面进展缓慢。在本文中，我们将探讨10种流行的社交网络和基于位置的服务（LBS）的隐私保障。我们审计这些服务，并确定他们部署的防御机制，以保护其用户的位置隐私为了评估已被业界采用的各种防御措施，我们将定位用户的问题形式化为离散欧氏平面中的搜索问题据我们所知，这是LBS中用户发现攻击的第一次正式处理。我们证明了严格的界限上的查询的数量需要在不同的邻近模型攻击服务，并设计最佳的算法，实现这些攻击。我们的技术的查询复杂性的下限提供了有用的洞察力，对本地化攻击的常见缓解措施的有效性，如速率限制用户可以发出的查询的数量。我们评估了我们对四个审计服务的攻击，这些服务采用了不同的对策：Facebook，Grindr，Skout和Foursquare我们表明，用户发现攻击接近服务可能需要复杂的技术，我们的攻击包括几何算法，逐渐减少候选边界区域的用户居住，雇用串通帐户获得侧信道信息的用户之间的距离，并利用统计算法处理随机化服务作为一种防御机制。我们的研究结果表明，尽管防御机制已经到位，但攻击仍然是可能的，并且可以在大规模和连续的基础上（实时跟踪）使用。ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月评估位置邻近服务的隐私保证十二特别是，假设攻击者和受害者在社交网络中有联系，我们在3秒内确定了Facebook用户的实际位置在5米以内，在7秒内确定了90%的Swarm用户的实际位置在15米以内，每个服务都有最严格的隐私设置。我们甚至对我们的攻击进行了压力测试，并展示了实时跟踪移动目标的可行性。由于最近涉及Grindr的事件[Noack2014]，该服务隐藏了压迫政权公民的距离信息。即使没有任何距离信息，我们也能够通过推断到目标的距离来进行成功的攻击使用一对合谋的账户，以及Grindr基于距离的用户排序，我们确定了67%的用户在其确切位置的10米范围内，98%在19米范围内。同样，即使Skout实现了复杂的随机化防御，我们也能够精确定位其平均37.4米范围内的用户我们的研究结果表明，没有行业标准来确保用户的位置隐私;目前的大多数防御都是基于临时的方法，这些方法往往缺乏对本地化攻击技术复杂性的理解尽管我们积极努力防止此类威胁，但我们审计的每项服务都容易受到至少一种攻击。为了提供一个强大的解决方案，我们重新审视了文献中的混淆机制，空间伪装[Gruteser和Grunwald2003]，并将其应用到基于距离的邻近服务领域。通过量化平面并将用户映射到网格上的点，该服务可以防止对手以比网格单元更精细的精度精确定位用户为了激励服务采用这种防御，我们提供了对所获得的隐私（在某些假设下）以及隐私和可用性之间的权衡的精确描述 在我们的调查结果披露后，Facebook和Foursquare承认了我们攻击的严重性，并按照我们的指导方针，采用了空间伪装来保护他们的用户。本文的主要贡献如下：- 我们提出了一个正式的处理用户发现攻击的邻近服务。我们模型的问题，证明了查询复杂性的下限，并设计算法，匹配相应的下限。通过大量的实验，我们评估了流行的邻近服务的隐私性我们向服务披露的发现导致Facebook和Foursquare采用了空间隐身。此外，我们还评估了在采用空间隐身后，我们在Facebook和Foursquare上攻击的准确性我们分析攻击的实际方面，并确定影响其性能和准确性的关键特征。我们提供指导方针，以削弱攻击，并确保最低水平的隐私，而不会导致服务质量的显着恶化。我们发布了一个开源审计框架，用于帮助开发人员和研究人员评估邻近服务的隐私。我们的框架已经被Facebook用于评估他们新采用的空间隐身机制。1.1. 负责任的披露披露针对服务的攻击会引发道德问题，因为有人可能会说，广告商以前可能缺乏进行此类攻击的专业知识。然而，最近的事件表明，对手已经瞄准了用户。虽然在野外看到的攻击是直接的，并且可以通过某些现有的防御来预防，但评估流行服务的隐私保证并防止未来的攻击至关重要由于对所提供的隐私的误解[Constine2014 a，2014 b; Frizell2014]和有缺陷的建议（例如，四舍五入距离[Wardle2014]），使用户面临危及生命的情况。我们联系了我们评估过的服务，ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月12：4G。Argyros等人详细分析我们的攻击，我们的指导方针，防止他们，并分析我们的空间隐身方法的隐私/可用性权衡。由于我们的披露，Foursquare和Facebook已经采用了空间隐身。此外，Facebook安全团队使用我们的测试框架来评估他们的隐形机制。文档结构：文章的其余部分组织如下。第2节介绍了威胁模型和位置邻近度的相关信息。第3节提供了用户发现问题的正式处理第4节描述了攻击的实际方面，第5节概述了流行的邻近服务及其各自的特点。我们在第6节中针对实际服务对我们的算法进行了实验评估。在第7节中，我们设置了实现邻近功能的指导方针，在第8节中，我们描述了我们的开源审计框架。相关工作在第9节中讨论，我们在第10节中提出我们的结论。2. 背景和威胁模型接近披露。两个用户之间的距离可以以各种形式公开。为了简单起见，我们将对手称为Mallory，将目标称为Bob。精确距离：这是最容易攻击的情况，因为三边测量算法可以以非常高的精度识别Bob的确切位置。这样的算法已经被广泛地探索（例如，Thomas和Ros[2005]）。位置磁盘：服务返回距离的上限，创建一个以Mallory为中心的磁盘，该磁盘包含Bob（例如，位置环：服务返回一个范围作为距离信息，以马洛里为中心的环（两个同心圆），鲍勃位于两个圆之间。这可以是简单舍入函数的结果（例如，51米和99米之间的距离四舍五入为100米）。量化距离：平面被量化为网格，创建隐藏区域，混淆用户的位置。接近度可以以两种形式公开：（i）将用户映射到网格点，并且从他们的网格点计算距离;或者(ii)接近度是布尔值，表示同一小区内的协同定位威胁模型。对手可以是对确定用户位置感兴趣的任何实体保险公司），或者恶意的个人（例如，[Scheck 2010]. 为了突出现有设计和对策的低效率，我们采用了弱对抗模型;对手只使用系统显示的距离信息。我们的攻击不需要事先知道用户在第6节中，我们证明了我们可以识别用户3. 模拟发现攻击在本节中，我们提供了用户发现攻击的理论模型。我们制定我们的问题作为一个搜索问题的离散欧几里德平面。这是因为服务和协议（例如，GPS）不能提供任意的精度。通过将其建模为离散问题，我们可以调整输入的大小对于以下内容，我们将遵循标准算法教科书中的符号[Cormen et al.2001年]。此外，我们使用术语k-近似的优化问题，以表示一个算法，输出的解决方案的大小最多k倍的最佳解决方案的大小。ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月·、·0否则。评估位置邻近服务的隐私保证12：5我们考虑目标用户u驻留在离散欧几里得平面的点pu处。攻击者可以请求关于用户u的位置的接近度信息。这是通过一个预言机获得的，我们称之为邻近预言机P。由于攻击者可以伪造自己的位置，她可以从欧几里得平面内的任何点查询邻近预言因此，接近度预言器接受点p并且返回点p和目标用户的位置pu的接近度信息我们用Pu（）表示邻近预言机，对于点p的输入，输出p的某个函数pu。另外，我们定义dist（p1，p2）为两点p1，p2之间的欧几里得距离。我们继续定义用户发现问题，我们的主要算法问题，在位置邻近服务的背景下。定义3.1（用户发现问题（UDP））。设pu是离散欧氏平面上的一点，A是包含pu的区域。在UDP中，目标是识别点pu，给定区域A作为输入，并且黑盒访问邻近性预言Pu。在下面的部分中，我们将描述捕获真实服务所使用的协议的接近预言机的三种不同实现。对于这些预言机中的每一个，我们描述了如何解决UDP访问相应的预言机。3.1. 磁盘用户发现问题我们首先给出第一个神谕的定义定义3.2（磁盘邻近Oracle）。半 径 为 r 的圆盘邻近预言机Pr，u（p）接受离散欧几里德平面中的点p作为输入，并且被定义为Pru（p）=. 1 ifdist（p，pu）≤r此模型捕获通知用户另一个用户是否在其当前位置的特定距离内的服务和协议在附近，没有提供进一步的信息。我们定义的磁盘用户发现问题（DUDP）是UDP给定的黑盒访问磁盘接近Oracle。我们通过将问题划分为两个子问题来解决DUDP，这需要不同的方法来解决。首先，我们希望将用户限制在半径为r的单个圆盘内，其次，在该圆盘上搜索目标点pu。在前一个子问题中，用户被给予一个可能很大的区域A，她希望用半径为r的圆盘覆盖该区域，以便将搜索区域限制在单个圆盘内。我们把这个问题称为磁盘覆盖问题。为了实现有效的攻击，我们希望用最少数量的磁盘覆盖该区域。定义3.3. 在圆盘覆盖问题中，输入是离散欧几里得平面中的面积A和数r>0。目标是用最少数量的半径为r的圆盘覆盖区域A。本质上，在LBS的上下文中，并且知道目标用户如果用户位于A内，则她的位置被限制在半径为r的特定磁盘内，并且必须使用接近度预言来进一步将用户的位置细化我们称这个子问题为磁盘搜索问题。定义3.4. 在圆盘搜索问题中，输入是半径为r以及邻近预言机Pr，u（）。我们的目标是在输入盘内唯一地精确定位点puACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月十二G. Argyros等人| |∈ ∈≤=⊆ ∈ ∈∈=| |请注意，当输入区域被限制在半径为r的磁盘上时，磁盘搜索问题正是DUDP。由于这两种情况的处理方式不同接下来，我们检查每个子问题，并描述解决它们的算法。解决磁盘覆盖问题。为了推广我们的攻击，我们假设攻击者拥有的唯一信息是目标用户位置的非常粗粒度的近似值给定用户可能居住的总区域，我们的第一个目标是精确定位半径为r的磁盘内的用户，如由邻近预言机提供的。一个问题，正是对应于磁盘覆盖问题是最小支配集（MDS）的问题，在一类特殊的图称为单位磁盘图（UDG）。在MDS问题中，给定一个图G（V，E）作为输入，目标是找到一个集合D V，使得对于每个vV，存在一个u D，使得（u，v）E。UDG是一类特殊的几何图;尽管存在许多等价的定义，我们将使用被称为邻近模型的定义[Clark et al.1990]：定义3.5（UDG的邻近模型）。 考虑平面上的n个点的集合P。P中的点的UDG是无向图G（P，E），其中P是n个点的集合，对于每个u，vP，我们有（u，v）E当且仅当dist（u，v）k，对于某个预定义的k>0。UDG中的MDS问题已经被广泛研究。虽然它仍然是NP难的[Masuyama et al.1981年]找到一个精确的解决方案，已经实现的近似比是更好的比一般的MDS问题，其中它是NP-难找到一个解决方案小于O（logn）倍的最佳解决方案。具体来说，存在多项式时间近似方案（PTAS）[Nieberg and Hurink2006]，其复杂性对于我们旨在解决的问题实例来说是不切实际的，以及线性时间的5-近似[Marriott et al.1995]和时间的3-近似O（n18）[Deet al. 2011年]。请注意，需要覆盖的区域可能遍布整个城市甚至更大的区域。因此，相应的图可以包含数百万个节点。在这种规模下，即使是具有二次复杂度的算法也可能导致非常大的运行时。幸运的是，对于MDS问题，存在一种算法，其运行时间与输入集的大小成线性关系，并且计算最优解的5-近似该算法的工作原理是从图中取一个任意节点，将其添加到支配集，删除所有已被所选节点覆盖的相邻节点算法的时间复杂度为O（V）。如果图是UDG，则算法提供的覆盖的大小最多为最小覆盖的5倍[Marriott et al. 1995]。由于这是一个非常一般的结构，有许多方法可以选择点集，同时满足算法的要求。虽然这些不同的构造将提供相同的最差情况近似比，但它们在实践中的表现可能非常不同在我们的算法中，我们通过用六边形平铺二维平面来创建集合的点，这是一种确保在Cellular网络中以最小数量的位置覆盖[Wang etal.2005年]。 Eac h六边形边缘等于3r，其中r是查找粒度的半径。注意现在，由于我们的集合中没有两个点的距离小于r，我们的算法创建了最小覆盖的5-近似，并且选择点平均需要O（V）解决磁盘搜索。 在用户被限制在半径为r的圆盘上之后，目标是将位置细化到单个点。我们提出了一个算法，解决了磁盘ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月评估位置邻近服务的隐私保证十二≤=−·==\||=∈∩|∩|||表I.用于搜索（·）算法的符号S将点集输入到搜索引擎Search（·）R（S）集合SKR（S）的短边长度DR（S）的长边长度IR（S） R（S）内的点集Cr（p）以点p为圆心半径为rpmR（S）短边中点Lm与R（S）的长边平行且与pmS1SCr（p）S2S\S1使用O（logr）查询的搜索问题我们可以很容易地证明结果是最优的。我们的算法工作起来像一个二分搜索算法，使用预言机削减候选点，用户居住在每个查询的一半。请注意，我们可能并不总是能够在每个切割中将候选点分成两个相等的集合;然而，正如我们将展示的那样，所需的查询总数仍然是O（logr）。我们首先提供一些定义，这些定义将在整个算法的描述中使用：对于欧几里得空间中的给定点集S，我们用R（S）表示包含这些点的外接矩形，用IR（S）表示矩形R（S）中的点R（S）的两条边对于点p，我们用Cr（p）圆盘中以p为中心，半径为r的点。我们说该算法在集合S上执行切割，导致两个子集S1，S2，当在点p和S1上查询邻近预言Pr，uSC r（p），S2S S1.我们用Pm表示R（S）短边的中点.最后，设lm是一条平行于R（S）的长边通过pm的直线。表I提供了我们的符号的简单参考。算法RISSEARCH（S）递归地进行(1) 对于集合S的输入，如果S1，返回p S.(2) 对于lm中的每个点pi，从距离R（S）的距离r开始，向R（S）移动，检查集合SCr（pi）的大小。如果对于点pi，SCr（pi）>S/2成立，则设p pi1。(3) 调用点p上的邻近oracle：- 如果Pr，u（p）=1，则在S1上递归。- 如果Pr，u（p）=0，则在S2上递归。一旦我们限制了算法进行递归调用的次数，算法的正确性就很明显了。对于运行时分析，我们假设对Pr，u（·）的调用需要恒定的时间。我们证明了下面的定理。3.6. history 该算法的时间复杂度为O（r log r），并且将对邻近预言机Pr，u（·）进行最多O（log r）次查询。此外，我们证明了以下定理显示我们的算法的最优性3.7.第三章 设Pr，u（）是半径为r的邻近预言机，A是离散欧氏平面上的点集. 用OPTMDS表示从A中的点产生的UDG的控制集的最小大小然后，在最坏的情况下，求解集合A中的DUDP的任何确定性算法将不得不对磁盘邻近oracle Pr，u（·）进行▲（OPT MDS + log r）查询。在LBS的上下文中，A表示可以向服务执行查询的所有合法坐标。在没有施加限制的情况下，ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月十二G. Argyros等人|=≤「·联系我们|··]「服务和任何一对坐标被接受，可以选择任意精度量化，直到服务支持的十进制精度。3.2. 舍入用户发现问题现在，我们转向一个不同的Oracle实现。这种邻近预言模型计算p和pu之间的距离，但将所得值舍入到某个预定义的精度。为了在这个模型中正确定义oracle，我们定义了舍入类的概念第三章. 8（舍入类）。 对于整数Ik=（a，b）<$R+，定义舍入类Rk为元组（Ik，δk），其中δk∈ R+为舍入值.一些服务（例如，Facebook）根据两个用户之间的距离应用不同的舍入。这激发了舍入类族的概念，我们稍后定义它来捕获这种行为。定义3.9（舍入类族）。 我们定义一个舍入类族S={（I1，δ1）， . ，（In，δn）}，以获得舍入类，其具有以下保持：(1) 因此，I={I1， . . . ，In}形成R+的一个分割。(2) 对于i，j，我们有ij<$δi<δj。<(3) 当k>1时，δk≤infIk成立.第一个条件意味着，对于每一个可能的距离，都有一个相应的舍入值。第二个条件断言舍入值随着距离的减小而单调减小。第三个条件直观地表明，与实际距离相比，所添加的舍入很小。条件2和3不是我们的攻击工作所必需的;然而，它们是我们在所有服务中发现的自然约束，并且简化了我们算法的描述和分析。接下来，我们定义算子xδ，它将x四舍五入到最接近的数xrx，使得δxr1。注意，可以类似地定义运算符δ和δ。在攻击实际服务时，我们考虑舍入也使用这些操作符的类然而，算法本身不会以任何方式改变。为了简单起见，我们将在整个演示和分析中使用δ定义3.10. 由舍入类S的族索引的舍入邻近性OraclePS，u（p）被定义为：设（Ik，δk）∈S是一个舍入类，使得dist（p，pu）∈Ik.那么，PS，u（p）=「我们将舍入用户发现问题（RUDP）定义为UDP访问舍入邻近Oracle。我们的问题定义也涵盖了其他模型。例如，输出精确距离的预言机是具有舍入类族S（R，δ），δ0的舍入邻近预言机。解决RUDP。 直觉上，如果我们有到目标用户的确切距离，一个简单的三边测量将给我们他的位置。然而，在我们的例子中，应用了舍入操作，这给结果增加了噪声因此，应用一个在四舍五入的距离上进行三边测量是为了减小用户所在的区域接下来，我们利用这样的事实，对于每个舍入类Rk（Ik，δk），我们有δkinfIk。在减小的区域内重新应用三边测量算法将导致获得更小的舍入误差，从而进一步减小搜索区域。重复此过程，直到我们达到R1=（I1，δ1），在这种情况下，我们使用舍入值[1]由于δ可能不是整数，我们在这里滥用符号δx来表示x是δ的整数倍。ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月评估位置邻近服务的隐私保证十二·=·1··=·≤||+的· ||+的、·0否则pu=Search（Areak，Pr，u（·））;Pr，u=SimulateProximityOracle（PS，u（·））;面积i=三边（面积i−1，PS，u（·））;i=i+1;虽然<我|区域i|> 1个端i=1;n =1;L= |S|;输入：舍入接近度OraclePS，u（·），区域A;输出：目标用户在欧几里德平面中的位置;面积0=A;算法1：RUDP算法来定义一个磁盘邻近oracle并执行我们提出的RISsearch（）算法。具体地，我们将半径r δ1的盘邻近度oraclePr，u（）定义如下：Pru（p）=. 1如果PS，u（p）≤δ1注意，在最后一次三边测量之后，要搜索的剩余点位于大小为δ2的区域中。因此，一个半径为δ1的圆盘足够大，可以运行RISK Search（）算法。算法1显示了攻击的实现我们定义了一个过程B Trilaterate（A，PS，u（）），它接受一个区域A和一个舍入邻近预言作为输入，通过查询PS，u（），执行一个三边测量，以减少用户居住的可能区域B。三边测量算法的细节是已知的[Huang and Narayanan 2014]，因此被省略;最后，过程SimulateProximityOracle创建了一个磁盘邻近oracle，如前所述。分析. 三边测量的迭代应用保证了减少搜索因为我们知道，对于一个舍入类Rk，我知道了。虽然这是自然的，但这种限制是不必要的;如果在任何时候，算法都不能保证三边测量将提供减小的搜索区域，那么我们可以类似于我们定义的方式来定义邻近预言。它的前面，然后执行搜索搜索（）算法。该算法对oracle的查询次数为3SO（log δ1），其中δ1是舍入值较小的舍入类R1。此外，三边测量过程所需的时间也是常数;因此，总运行时间为O（S δ1logδ1）。我们证明了以下定理，建立了一个匹配的下界的com-确定性算法的RUDP问题的复杂性第3.11章. 任何求解RUDP的确定性算法都可以访问由一系列舍入类S =（（I1，δ1），.， （I n，δn））要求▲（|S| + log δ1）在最坏的情况下对P S，u的查询。3.3. 随机用户发现问题在该模型下，点的邻近性预言查询结果遵循概率分布，而不是距离的确定性函数我们使用以下定义来捕捉定义3.12. 由概率分布D索引的随机邻近预言PD，u（p）定义如下：PD，u（p）<$D（p u，p）.ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月十二G. Argyros等人DDDDD{}联系我们∈N+|、u、、换句话说，向oracle查询的每个点将从基于查询的点和目标用户的位置的概率分布中获得其值。我们将随机用户发现（RANDUDP）定义为UDP访问随机邻近Oracle。我们还假设分布是已知的。虽然在实践中，服务不太可能发布所使用的分布，但攻击者可以部署具有已知位置的假受害者用户，并从分布中收集大量样本，以创建近似值。请注意，RANDUDP的定义方式，存在某些概率分布，对于这些概率分布，不可能定位目标用户。例如，在0， 1上的均匀分布的情况下，查询oracle将不会提供任何关于用户位置的信息然而，这样的发行版也无法为服务的用户提供任何真正的功能;因此，它们在实践中不会遇到。通常，或值P，u将以一定概率返回正确的邻近信息，否则返回不正确的值。对于以下内容，我们考虑一个直观的随机化模型，我们表示为与高斯噪声的圆盘搜索一样。在此模型下，定义了以下随机邻近预言。定义3.13. 具有半径r和标准偏差σ的随机化盘邻近预言机定义如下：Pr，σ，u（p）=（1−zpu（p））Pr，u（p）+zpu（p）（1−Pr，u（p）），其中Pr，u是半径为r的磁盘邻近预言机，zpu（p）0， 1是误差函数，满足Pr[z（p）1个区（pp）[a b]]bf（x r一）dx其中a，bR和f（x，r，σ）是（r，σ）的PDF，平均值为r和标准差σ。直观地说，在这个模型下，当攻击者试图检测到距离用户r的点以执行切割时，增加了大量的噪声，迫使攻击者使用搜索算法执行错误的切割，从而停止攻击。此外，当我们远离“危险区域”时，噪音会降低在我们在研究中遇到的所有不同防御中，这个模型是最难破解的，因为它需要比以前的模型更多的查询。后来，我们提出了一个算法，以解决搜索问题与高斯噪声，并减少表明，区分正态分布与不同的平均值的问题减少到这个问题。用高斯噪声解决磁盘搜索。在这里，我们推导出一个算法来解决高斯噪声的搜索问题。我们的算法是最大似然估计（MLE）原理的应用，该原理广泛应用于统计和机器学习。具体地，该算法如下进行：(1) 给定一个面积A作为输入，设rr是包围面积A的最小圆的半径。然后，对于给定的输入数k，在距离A的质心d∈[r−rr，r+rr]处随机采样k个点。令S={（p1，l1=Pr，σ，u（p1）），...，（pk，lk=Pr，σ，u（pk））}。ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月pu=∈=，σ、评估位置邻近服务的隐私保证十二.(2) 计算A中候选点上的MLE为Kpu=argmax log Pr[Pr，σ，u（pi）=li]，p<$u∈conv（A）i=1其中conv（A）表示区域A的凸包。分析. 有关MLE算法的更多信息，请读者参阅Hastie等人[2001]。然而，我们注意到，选择A的凸包内的点的原因是，由于高斯分布的概率密度函数是对数凹的，前面提出的问题可以写成凸优化问题，如果我们从A的凸包内选择点，那么可以利用有效的凸优化算法[Boyd和Vandenberghe2004]来找到具有最大似然的点。4. UDP的实际尺寸在这里，我们描述了对实际服务进行攻击的实际方面和挑战。搜索空间。根据对手Chaabane等人[2012]发现，29%的用户公开透露他们目前的城市，而48%的人透露给他们的联系人。这些信息也可能通过地理推断攻击获得[Jia et al.2014]。虽然我们的攻击非常有效，但附带信息可以减少搜索空间的大小接近Oracle查询。由于攻击需要与服务交互，因此以下实际方面变得相关，因为它们会影响攻击。连接. 服务可能会限制哪些用户可以获得邻近信息。约会应用程序将这些信息披露给未连接的用户（即，陌生人）。社交网络具有更多面向隐私的默认设置，并且仅向用户的联系人披露虽然这看起来像是一个障碍，但对手可以使用虚假帐户来与用户交朋友。以前的工作（例如，Bilge等人[2009]）已经广泛地探讨了这个主题，并证明了用户非常有可能接受来自未知帐户的请求。对于本文的其余部分，我们假设，如果需要的话，对手在服务中与用户连接尽管如此，我们还是尽量减少了攻击者的数量;当需要社交联系时，我们只使用一个帐户。侦查由于发送虚假坐标是微不足道的，因此服务部署了检测这种情况的机制。为了确定机制及其阈值，我们可以遵循Polakis等人的方法。[2013年]。 通过知道确切的阈值，我们可以最小化攻击的持续时间，同时避免检测。攻击精度。准确性必然取决于用户设备的GPS精度。在我们的实验中，距离是根据报告给服务的坐标计算的。因此，我们测量我们的攻击的准确性。实际上，准确度可能受到设备GPS误差的影响然而，智能手机正变得越来越精确，GPS精度在10米以内，研究人员证明了30%的改进[Yang et al.2014年]。此外，我们的攻击的准确性是这样的，GPS错误不会减轻目标用户面临的威胁。投影误差。没有地图投影能完美地表示所有区域，并且给定的投影被构造为仅保留少数属性（例如，形状）的真实地理区域。虽然攻击不依赖于投影坐标，但搜索区域的坐标应使用最适合该区域的投影进行变换，以最小化引入的误差我们使用适当的等距ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月十二G. Argyros等人表II.受欢迎的服务与位置接近#DSTGPS网格查询速度兰德Facebook1-5B◎✗✗✗✓✗群5-10MⓍ✓✗✗✓✓Grindr5-10MⓈ|∅✗✗✓✗✗Skout10- 50米◎✗✗✓✓✓MeetMe10- 50米Ⓧ|◎✗✓✗✓✗洛沃10- 50米◎✗✗✗✗✗Tinder10- 50米◎✗✗✗✓✗SayHi10- 50米Ⓢ✓✗✗✗✗豪莫5-10M◎✓✗✗✗✗HelloWorld1K-5K◎✗✗✗✗✗距离：-精确的圆-圆环-圆盘-无圆我们正在搜索的大陆的圆锥投影，以我们感兴趣的区域为中心。5. 位置邻近性：一个案例研究在本节中，我们分析了一系列提供邻近功能的流行服务，以验证我们的攻击的适用性和现实性。我们的分析表明，我们的理论公式的发现问题和相应的接近预言机的建设可以成功地模拟现有服务的接近功能表二详细列出了每一应用程序的邻近度模型。表格的第一列（#）表示Google Play商店报告的每个应用的下载次数-Dst（距离信息） ：服务可以以各种形式显示距离（例如，盘、环等）。-GPS（GPS坐标） ：用户的GPS坐标可以与其他用户共享;这可以显式地完成（例如，示出了精确位置）或隐式地（应用程序接收用于计算距离的联系人的坐标）。-网格 ：服务可以在计算距离时使用网格在Swarm中，虽然使用了网格，但它不会影响计算。在MeetMe中，距离是从对手的网格点到受害者的实际位置计算的因此，两者都不执行可以防止攻击的空间隐身。-查询（查询限制） ：服务可以强制执行查询速率限制，禁止直接执行攻击。除非强制执行非常严格的限制，否则可以简单地增加查询之间的等待时间。-速度（速度限制） ：服务可能会对用户在位置之间旅行的速度进行限制。-Rand ：该服务在邻近预言机返回的距离中添加随机噪声。在执行此初始分析后，我们针对遇到的所有可能的位置披露模型评估了我们的为此，我们选择了四个应用程序-Facebook，Swarm，Grindr和Skout-来检查我们的攻击如何针对使用环，磁盘或确切位置显示距离的服务执行，以及在服务执行伪装或向其报告的距离添加随机噪声的情况下。其余服务的邻近模型属于其中一类;因此，省略了相应的分析在第6节中展示我们的实验结果之前，我们首先详细说明我们选择的应用程序集的特性。ACM Transactions on Privacy and Security，卷。19，不。4、第12条，公布日期：2017年2月评估位置邻近服务的隐私保证十二∗Swarm由Foursquare部署，并围绕位置接近度构建：朋友被分配到六个大小的位置盘：（i）300米，（ii）1.5公里，（iii）15公里，（iv）30公里，（五）64公里;（六）超过64公里的Swarm使用的API尚未公开;因此，我们对客户端应用程序和服务的服务器之间的通信协议进行了反向工程。我们的实验表明，Swarm采用静态网格，用户被分配到最近的网格点。 网格单元的尺寸为252米274米。有两个相关的API调用：UpdateLocation更新位置Activities_Recent在与应用交互时发送，包