1. 引言
随着智能手机和无线网络的广泛应用，移动应用近年来呈现出爆炸式的增长。据统计2014年全球移动应用的使用量增长了76% [1] 。至2014年底，谷歌Play拥有143万款应用，Apple Store拥有121万款应用 [2] ，其中基于位置的服务(Location-based Service, LBS)备受用户青睐。以百度地图为例，从2012年成立至今，用户数从最初7000万增长到超2亿活跃用户 [3] ，它提供的定位、导航、查询等位置信息服务为现代生活带来了极大的便利。然而，用户提交的位置服务请求和自己的位置信息在一定程度上会对个人的隐私造成泄露风险 [4] [5] 。一方面，对某些用户而言，其位置信息本身就是隐私数据；另一方面，攻击者可以根据位置信息来推测用户的个人身份、工作性质、健康状况或者兴趣爱好等隐私信息 [6] - [9] 。
近年来，学术界对位置隐私保护问题进行了广泛的研究，并提出了一系列保护方法。从已有的位置隐私保护技术来看，可以将其分为四类，即空间模糊化、虚拟对象、隐私信息检索(Privacy Information Retrieval, PIR)和差分隐私保护。其中，空间模糊化技术是将用户的真实位置模糊成一个满足用户个性隐私需求的空间，并用模糊后的空间代替精确位置提交给位置信息服务器处理；虚拟对象技术将虚拟的对象与真实对象混合在一起作为位置服务请求发送者，使攻击者无法实现位置与用户的准确映射，这种方法的研究重点在于如何合理的选择虚拟对象；PIR技术是基于不可信数据库提出的隐私保护技术，它能实现用户访问服务器的同时阻止服务器获知用户访问内容，提供了高水平的隐私保护，该技术最大的挑战在于设计一个好的检索算法来加快检索效率和降低存储空间；差分隐私是近年来提出的一种新的隐私保护定义，由于其独立于攻击者的背景知识，并提供了严格的、可证明的隐私保护，成为目前隐私保护领域的一个研究热点。
本文首先分析LBS系统所面临的隐私泄露风险，然后对以上四类隐私保护技术的基本原理和实现方法进行综述，通过对已有研究成果的梳理，详细分析和比较这些技术的优缺点，最后探讨位置隐私保护技术在未来的研究方向。
2. LBS的基本结构与威胁分析
2.1. LBS的基本结构
LBS的基本结构(如图1)通常由4个部分构成：移动终端、定位系统、传输网络和位置信息服务器 [10] 。用户利用移动终端向LBS服务器发送位置服务请求(如“离我最近的加油站”)，服务请求则通过传输网络到达LBS服务器，LBS服务器查询存储的位置信息，再将查询结果通过传输网络发送给用户的移动终
Figure 1. Basic framework of LBS system
图1. LBS系统的基本结构
端。用户及查询结果的位置信息由定位系统提供。可见，位置信息是LBS网络中传输的最核心数据，也是位置隐私保护的对象。
2.2. LBS面临的隐私泄露威胁
在LBS体系结构中，传输网络和LBS服务器被认为是存在安全威胁的不受信任方。用户的请求信息有可能在传输网络中被截获和分析，也有可能在服务器端被非授权的泄露，从而对用户隐私造成威胁。位置隐私威胁并不仅仅指位置信息的泄露，更重要的在位置信息暴露后受到的与时间和空间相关的推理攻击 [11] ：攻击者可以根据用户的位置信息推断出用户的个人隐私信息。因此，根据隐私泄露程度不同，位置隐私面临威胁可分为以下三种 [12] ：
(1) 物理威胁：攻击者直接攻击传输网络或者服务器等物理设备获取用户最原始的位置信息；
(2) 推理威胁：攻击者在获得用户的位置信息后，利用观察、推理、挖掘等技术推断出关于用户的隐私信息 [13] ；
(3) 联合攻击：攻击者在获得用户位置信息后联合用户使用的其他移动应用等外部资源，对用户隐私进行更深度的挖掘。例如，攻击者可以联合用户的社交网络信息来挖掘用户朋友的隐私信息 [14] 。
显然，物理威胁只涉及到用户的物理位置信息，推理威胁会危及到用户的个人身份信息，联合攻击则影响到了用户的整个生活环境。位置隐私的泄露是导致以上威胁的根本原因。
3. 位置隐私保护技术
近年来，学术界对位置隐私保护的研究取得了丰富的成果，各种隐私保护理论与模型在位置隐私保护中得到应用。本节对已有的位置隐私保护技术进行梳理和比较。
3.1. 空间模糊化
空间模糊化技术 [15] - [17] 是指用户在进行位置信息请求时，提交给服务器的并不是用户的精确位置，而是一个空间范围，使得攻击者不能分辨用户的具体位置。k-anonymity是空间模糊技术应用的最主要的隐私保护模型 [18] 。该模型要求数据集的任一记录都至少和其它k − 1个记录不可区分 [18] [19] 。Marco Grureser [20] 最先将k-anonymity的概念运用到位置隐私保护中，要求每个用户在某个时间和空间范围内与其它至少k − 1个用户不可区分，使攻击者不能从至少k个用户中识别攻击目标进而推断出其准确位置。k-anonymity的缺点在于模型参数过于单一，仅通过k来确定隐私水平，在某些情况下会使隐私保护失效。例如在用户密集处，满足k-anonymity的狭小区域能够在一定程度上泄露用户的准确位置；而在用户稀疏处，则有可能用户数量达不到k的要求而匿名失败。
之后的研究对k-anonymity模型进行了改进以克服这些缺点。文献 [21] 提出的Casper模型在k-anonymity基础上引入了新的隐私参数Amin，表示最小模糊区域。如图2所示，Casper模型用金字塔的数据结构来进行位置信息存储，金字塔的每一层覆盖了同样的区域，并将这些区域划分为网格形式，每个网格记录着当前存在的用户数。当进行空间模糊时，利用网格的融合和分裂来满足匿名区域k和Amin的隐私水平。Casper模型将空间模糊化的过程全部交给客户端和LBS服务器之间的可信任第三方(位置匿名器)来完成。用户将位置服务请求和自己的位置信息发送给位置匿名器，匿名器进行空间模糊化后发送给LBS服务器，服务器根据匿名后的请求查询候选结果，并返还给匿名器，匿名器进行结果筛选后将精确结果返回给用户。Casper方案的缺点在于空间模糊化的过程比较复杂，因此对匿名器的性能要求较高。同时，匿名器作为一个必不可少的可信任第三方会带来一定的风险。另外，Casper以真实活动的对象作为匿名参与者，在人员密度稀疏的地区就有可能导致模糊区域过大的问题，导致查询结果的可用性降低。
Casper模型主要解决了查询快照中的位置隐私保护问题，但用户是不断运动的，连续位置之间的相关性往往可以被攻击者利用并进行相关位置攻击。相关位置攻击指攻击者利用用户运动位置之间的相关性推理用户精确位置的攻击方式。如图3(a)所示，
表示对象A在ti时刻的模糊空间，
表示对象A在ti+1时刻的模糊空间，假设攻击者已知A的最大运动速度，则可以推断A在ti+1时刻可能达到的范围为
，进而可以推理出A在ti+1时刻的精确位置处在
和
相交部分。同样地，如图3(b)所示，攻击者可以根据A在ti+1时刻的模糊空间
和A的最大运动速度推断出ti时刻A可能的位置集合
，进而推理A在ti时刻的精确位置处在
和
的相交部分。因此攻击者可以利用相关位置攻击缩减攻击对象的模糊空间，降低隐私保护水平。
对此，文献 [22] 提出了iCliqueCloak模型解决相关位置攻击问题。如图4所示，对象A在ti+1时刻生成模糊空间时要满足以下2个条件：(1)模糊空间
必须包含在ti+1时刻A可能到达的范围
内；(2)以
为基础推断出的ti时刻A可能的位置集合
必须包含ti时刻A的模糊空间
。iCliqueCloak模型能够有效地防止攻击者利用相关位置攻击来缩减模糊空间，从而保持原有的隐私水平。
从实际应用效果来看，空间匿名技术能够为位置隐私保护提供了一个个性化的解决方案，但其缺点在于对区域的人口密度比较敏感。另外，匿名器的处理性能及其自身的安全性都会影响到空间匿名技术的应用效果。
Figure 2. Data structure of Casper model
图2. Casper模型的数据结构
(a) (b)
Figure 3. Relative location attack. (a) Forward deducing; (b) Backward deducing
图3. 相关位置攻击。(a)位置的正向推导；(b)位置的逆向推导
Figure 4. Requirements of iCliqueCloak
图4. iCliqueCloak模型的要求
3.2. 虚拟对象(Dummy)
Dummy [23] - [26] 的保护方式简单来说就是用户在提交位置服务请求时，将自己的真实位置和几个虚假位置一起提交给LBS服务器，LBS服务器针对所有提交的位置分别进行查询处理，将所有结果返还给用户，用户再根据自己的真实位置进行筛选。在Dummy的方法中，如何选择虚拟对象的位置是一个关键问题。对此，文献 [24] 提出了虚拟对象在分布上的一般性要求，包括分散性、稠密性和均匀性。
文献 [26] 提出了满足k-anonymity和最大模糊区域为s的两种虚拟位置的生成算法(Privacy-Area Aware Dummy GenerationAlgorithms, PAD)：基于圆和网格的Dummy生成方案。如图5所示，基于圆的Dummy生成方案是将用户真实位置pos绕着圆心O依次旋转 角而成，每旋转一次生成一个Dummy，并且满足：(1)
；(2)
。基于网格的Dummy生成方案如图6所示，将用户真实位置沿着网格移动生成Dummy，每个网格的边长
。
Dummy的生成方式解决了Casper模型过于依赖区域人口密度的缺点，但其自身的缺点也不可忽视，PAD算法中取得虚拟位置的方法过于规则化，而忽略了实际的地理特征。例如，按照这种规则化的方式选取的虚拟位置可能在现实环境中根本不可能有活动对象出现，那么这个虚拟位置就失去了混淆攻击者的功能。类似的，如果攻击者预先掌握了一些背景知识，例如地理环境、区域人口密度、运动最大速度等，即可实施背景知识攻击 [27] [28] ，将这些背景知识与获取的用户位置信息结合来推断用户的位置隐私和其他隐私信息。因此，为了阻止背景知识攻击，在选取虚拟位置时要使虚拟位置更接近真实对象的运动特点和规律。
文献 [29] 基于“越热门的地点越可能存在活动对象”的假设，应用熵理论建立了DLS (Dummy-Location Selection) 模型来进行虚拟位置的选择。假设用pi表示某个位置i被访问的概率，pi越大说明这个位置越热门，利用熵 [30] [31] 来衡量匿名程度:
(1)
H值越大说明匿名效果越好。由式(1)可知，当所有参与匿名的k个位置的热门程度相同，即pi为1/k时，H值达到最大。如图7所示，DLS模型选取的虚拟位置分布在与真实位置热门程度接近的区域中。
使用Dummy的位置隐私保护机制的优点在于能够摆脱对现实环境的过度依赖，无论在人口密集区
还是稀疏区都能较好地满足用户的隐私需求，提高了匿名化的成功率。但这些方法共同的不足在于，攻击者所掌握的背景知识是难以量化和准确建模的，因此在选取虚拟对象时往往忽略了对背景知识的考虑或者仅仅根据特定的背景知识假设提出针对性的解决方案，这样的保护机制无法应对基于新的背景知识的攻击。
3.3. 隐私信息检索
隐私信息检索(private information retrieval, PIR)是一种客户与服务器通信的安全协议，能够保证服务器无法识别客户在查询数据库时具体的查询对象，从而防止服务器端根据客户的查询对象来确定客户的兴趣点进而推断客户的隐私信息，因其能够提供了高水平的隐私保护，成为位置隐私保护的主要技术之一 [32] - [35] 。举例来说，PIR要实现这样的功能：假设Bob拥有一个不可信任的数据库DB，数据库包含n个记录，Alice想要获取DB[i]中的内容，PIR协议能保证Alice不但能访问DB[i]中的内容，而且不让Bob知道i的值 [32] 。PIR主要分为2种实现形式即基于计算的PIR [36] 和基于硬件的PIR [37] [38] 。基于计算的PIR依赖广为人知的数学计算难题来保证检索的隐秘性，需要付出较高的计算代价，除此之外，基于计算的PIR在处理每个查询请求时都要线性浏览整个数据库，产生了高昂的处理成本。基于硬件的PIR技术目前已经在现实中开始采用(例如IBM4758安全协作器) [39] ，具有很强的现实意义。基于硬件的 PIR将一个受用户信赖的处理器内嵌入LBS服务器中，接受用户的访问请求，检索服务器中相应的数据库，并将结果加密，返还给用户。在整个检索过程中能防止服务器获知访问了哪些数据，并且用户的访问请求和检索结果被加密，能够防止信息在传输过程中被泄露。在位置隐私保护应用中，基于硬件的PIR系统结构如图8所示。
在服务器中储存了整个地区的地图和兴趣点(points of interest, POIs)信息，LBS根据索引结构将DB划分为几个子数据库DB1, DB2, …, PIR处理器根据用户的请求对DB1, DB2, …进行查询，并将结果返还给用户。在信息查询过程中，PIR处理器就像一个黑盒子自动完成查询而不让服务器知道它访问了哪些子数据库。因此，这类方法的研究重点在于如何设计索引结构和访问顺序从而减少执行的检索复杂度和储存空间。文献 [34] 利用Hilbert空间曲线将POI的二维存储方式转化为H值的一维存储方式，减少了存储空间，并将POI根据H值的大小按照B+-tree的结构来组织，以便简化检索次数。文献 [33] 则将存储区
Figure 8. LBS with hardware-based PIR
图8. 基于硬件PIR的LBS系统结构
域用网格表示，并用Hilbert值表示每个网格单元，同时建立了3个数据库DB1, DB2, DB3来分别存储POI的不同信息。DB1按照H值的顺序存储每个网格单元中POI的数量信息，DB2按照H值存储每个POI的ID、坐标和指向DB3的指针，DB3存储了每个POI的其他详细信息。这样的存储结构能够在不遍历整个数据库的前提下高效地进行kNN (k Nearest Neighbor)查询。首先根据用户的位置信息在DB1中查找kNN，然后在DB2中确定kNN的ID和坐标，并根据指针在DB3中获取kNN的详细信息。除此之外，还为每个查询建立了查询计划，保证每个查询都按照同样的顺序和次数进行检索，以避免外部的模式攻击。
PIR协议能够对用户请求、信息检索及结果返回等整个通信过程都提供可靠的保密性，因此受到越来越多的关注。PIR除运用在查询快照的位置隐私保护中，还被广泛应用在近邻查询和最短路径查询中 [40] 。PIR有待继续研究的问题主要有两点：其一，PIR的存储代价和计算代价较高，如何设计合理的检索计划和索引结构是应用PIR的主要挑战；其二，由于LBS服务器必须要存储整个区域的POI和地图信息，存储空间和检索效率的限制使得PIR目前只能用于区域范围较小的场合。
3.4. 差分隐私
差分隐私是由Dwork在2006年提出的一种新的隐私安全定义 [41] 。它能够保证数据集的查询结果对某个具体记录的变化不敏感，因此，一个记录存在于一个数据集里，就像它不存在于数据集里一样安全，攻击者无法通过观察和计算查询结果来推测用户的隐私信息 [42] 。差分隐私的定义 [43] 为：设随机算法M，Range(M)为M所有可能的输出集合，对于任何两个邻近数据集D1和D2，以及Range(M)的子集
，若算法M满足：
则称算法M提供ε-差分隐私保护，其中ε称为隐私保护预算。从原理上看， 隐私实质上是将数据集的精确查询结果转化为一个分布，使得对两个邻近数据集进行查询得到相同结果的概率几乎相同。Laplace机制 [44] 和指数机制 [45] 是两种最基本的差分隐私实现机制。其中，Laplace机制用于查询结果为数值型的情况，指数机制则用于保护非数值型查询结果。
由于差分隐私无需考虑攻击者掌握的任何背景知识，并能提供严格可证明的隐私保护，因此在隐私保护数据发布 [46] - [49] 和隐私保护数据挖掘 [50] - [54] 等方面得到广泛的研究和应用。显然，差分隐私更适用于保护多用户的聚合信息，在只涉及单个用户的位置隐私保护问题上并不合适。根据差分隐私的定义，用户位置的变化对查询结果的影响须微乎其微，这使得查询变得毫无意义。为解决这一问题，文献 [55] 将差分隐私与k-anonymity结合起来，提出了一种混合模型，对于由k个位置构成的匿名集合，在提交位置时要求以相近的概率（小于
）输出k个位置中的任意一个。该模型的主要问题在于，匿名集合的选取对最终的隐私保护结果影响过大。
为此，文献 [56] 利用差分隐私的定义，提出了一种地域不可区分模型(Geo-Indistinguishability)。该模型基于位置隐私保护的现实，认为用户位置的微小变化应该对查询结果影响很小，但当用户位置变化较大时，查询结果可以有较大的变化，因此可以根据用户位置的变化程度来设定相应的隐私保护水平。Geo-Indistinguishability的定义为：设X表示用户可能的位置集合，Z表示可能发布的位置集合，d(·,·)表示欧氏距离，对于任意两个位置
和
并且
，若算法K满足：
则称K在半径r内满足ε-地域不可分，其中ε表示每单位距离的隐私保护水平。这一定义表明，对于两个非常接近的真实位置x1和x2，它们产生相同新位置z的概率分布也越接近；反之，随着x1和x2距离增大，产生相同新位置z的概率分布则可以相差较大，两个概率分布之间的差异由隐私保护水平
来控制。如图9所示，用户A在以半径为r的圆形区域内能享受
的隐私保护水平，r越小则隐私保护水平越高，反之则隐私保护水平越低。Geo-Indistinguishability可以通过向用户的真实位置添加二维Laplace噪声来实现。地域不可区分模型为差分隐私在位置隐私保护中的应用提出了一个切实可行的机制，成为一些后续研究的基础。
如何降低噪声量是差分隐私在应用中无法回避的问题。文献 [57] 认为，Geo-Indistinguishability模型在保护单个位置(用户只进行一次查询)时是有效的，但一个用户往往会进行多次查询，连续的位置变化会形成轨迹，如果将Geo-Indistinguishability独立地应用到每个位置上，所产生的噪声量将是不可接受的。根据差分隐私中位数机制(median mechanism) [58] 的基本思想，充分利用查询之间的关联关系，可以有效提高隐私保护预算的利用效率，因此，文中提出了一种针对位置保护的可预测差分隐私机制。该机制由预测函数、加噪机制和测试机制构成。预测函数根据先前提交的位置来预测当前须提交的新位置
，然后由测试机制来测试
与用户当前位置的距离是否在某个阈值之内，如果是，则直接提交
，否则才调用加噪机制来产生新的位置。由于仅在调用加噪机制时才消耗隐私保护预算，所以可极大地提高预算利用率，降低噪声。另外，文献 [59] 针对降噪问题提出了一种面向位置数据发布的差分隐私保护算法
Figure 9. Privacy level varies with r
图9. 隐私保护水平随r发生变化
(PriLocation)。位置数据发布的内容通常包括用户到过的位置集及其统计频次，如果直接应用差分隐私来保护发布的内容，将会因为位置频次的稀疏性导致噪声量过大。PriLocation算法由位置聚类、权重干扰、位置选择等三个操作构成，首先根据距离将所有位置划分到k个簇中，每个位置则泛化为其所在的簇；然后将每个用户的位置统计频次转化为簇的频次统计，并用Laplace噪声进行干扰；最后利用指数机制从涉及的簇中选择位置作为用户到过的位置。由于簇的数量要远小于位置的数量，使得加入噪声的次数急剧减少，从而降低了噪声量。
差分隐私的主要优点在于它对攻击者所掌握的背景知识完全免疫，能够为用户提供强健的隐私保护。但从其在位置隐私保护中的应用效果来看，在有些方面还有待继续深入的研究，包括：(1)在处理高敏感度查询时，添加的噪声过大，会极大地降低数据的可用性；(2)给定的隐私预保护算会限制数据查询次数；(3)计算复杂度普遍较高。
3.5. 小结
由于无线通信技术和LBS服务模式的不断创新，位置隐私保护技术目前以及未来的一段时期仍将处于研究的高峰期。本节对现有的实现技术进行了分类梳理，将这些技术分为了四类，包括空间模糊化、虚拟对象、PIR和差分隐私，并分别对其中的代表性成果进行了介绍和分析。每一类的技术都有其各自的优缺点和适用范围，它们在隐私保护水平、运行开销以及主要优缺点等方面的比较如表1所示。
总的来看，空间模糊化和虚拟对象技术相对成熟，能够较好地达到数据安全性和可用性的平衡，在目前来说，实用性相对较好；PIR技术由于基于密码学基础，能够提供高水平的隐私保护，但计算代价高是其主要劣势，因此主要更适合于安全级别要求较高的场合；差分隐私能够提供可控的和可证明的隐私保护，但噪声大进而影响到数据可用性是有待继续研究的问题。
4. 未来的研究方向
位置隐私保护是一个相对年轻的研究领域，从目前的研究现状来看，在理论基础和实现技术等许多方面尚有待深入研究。同时，随着移动通信业务的不断推陈出新，位置隐私保护也必将面临更多的挑战，其未来的研究方向主要包括以下几个方面：
(1) 隐私保护参数的设置与优化
位置隐私保护技术在理论上都是基于一些隐私保护模型，例如k-anonymity [19] 、l-diversity [60] 、t-closeness [27] 、m-invariance [61] 、p-confidentiality [62] 、ε-DP [43] 等，其隐私保护水平都是由相应的隐私保护参数来调节的。如何通过对这些参数的设置来达到隐私保护水平和服务水平的最佳平衡，即如何寻求隐私保护参数的最优解，是一个需要继续研究的问题，它可能涉及到对用户的调查、对行为和心理的评估，以及对现实环境的分析等。
Table 1. Comparison between location privacy preserving techniques
表1. 位置隐私保护技术比较
(2) 个性化的位置隐私保护方案
在现实当中，对隐私保护的需求往往因用户或地域的不同而有很大的区别。但目前的位置隐私保护方案大多并没有考虑这些多样化的需求，隐私保护系统往往工作在某种统一的设置下。虽然有些研究已经意识到这个问题并提出了相应的解决方法 [63] [64] ，但这些方法大多工作在特定的环境下，还不具备一般通用性。设计细粒度的、支持不同层次的隐私水平的个性化隐私保护方案是未来的一个研究方向 [65] 。
(3) 社交网络中的位置隐私保护
社交网络的风靡对隐私保护提出了新的挑战 [66] 。在移动互联网中，位置数据与图片、文字、音频数据结合在一起，一般的结构化数据转变为非结构化数据，同时，采用实名认证的移动社交网络将个人身份信息与位置信息进行了绑定，社交网络中与用户之间的互动则导致隐私暴露的范围扩大。传统的隐私保护方法并不能适应这些新的变化，研究社交网络的位置隐私保护方法是未来的一个重要的研究方向。
5. 结束语
随着LBS的广泛应用，位置隐私保护问题受到了学术界、政府部门、消费者和产业界的多方关注。本文对LBS的一般体系结构和存在的位置隐私威胁进行阐述和分析，介绍了目前主要的位置隐私保护技术，并对各自的适用范围及优缺点进行了详细的分析和对比。最后，结合位置隐私保护的研究现状，指出了该领域在未来的研究方向。
基金项目
国家自然科学基金项目(61304067)；湖北省自然科学基金项目(2014CFB354)；中央高校基本科研业务费专项资金(31541511301)。