LBS下的位置隐私保护【摘要】随着移动网络平台的发展，基于位置的服务（LBS）也成为人们生活中不可或缺的一部分，而用户在获取LBS的同时也想服务提供商提供了自己的位置信息。

这个信息有可能被攻击者获取继而得知用户的隐私。

位置隐私保护是现阶段信息安全领域的热门研究方向，并且已经取得了一定的研究成功，然而存在的问题也是对未来研究不小的挑战。

本文简要对包括k-匿名技术在内的，现阶段不同原理和应用背景下的位置隐私保护方案和算法进行了介绍。

最后，总结了位置隐私保护技术当前存在的问题及未来的发展方向。

【关键词】基于位置的服务位置隐私保护k-匿名方法轨迹隐私保护1.引言随着智能手机和平板电脑的移动设备的普及，随着物联网及其相关技术的飞速发展，基于位置的服务LBS(Location based service)越来越流行，也逐渐成为人们生活中不可或缺的一部分。

LBS是指使用某种定位技术（如全球卫星定位系统、手机定位和通过Wi-Fi接入点的定位），为移动用户提供与当前的位置有关的个性化服务。

[1]位置服务系统结合完备的地理信息数据和信息搜索引擎, 可以提供给用户丰富的位置信息服务。

具体有以下应用：(1) 人身安全和紧急救助；(2) 机动车反劫防盗；(3) 集团车队、人员和租凭设备的调度管理；(4) 与位置相关的信息服务；(5) 物流管理；(6) 广告；(7) 友情、娱乐性服务等。

[12]如今，我们已经可以随处可见基于位置的服务，搜寻Google Map，找寻附近的酒店、餐馆、娱乐场所，道路导航，这些无不是LBS的典型应用。

而类似微信这种社交平台提供的就近交友服务，同样是LBS的功劳。

图表1 LBS的典型构成注：图表1来源于百度百科移动终端用户以WAP协议通过WAP网关向WEB服务器发出请求，包括用户代码、密码和电话号码。

WEB服务器将这些信息送到定位服务器，如果是合法用户，则接受请求并记录用户当前位置送回到WEB服务器。

WEB服务器通知用户已经成功登陆并允许用户进一步提出想要查找的内容。

Web服务器根据位置信息和用户的选择形成LDAP服务请求并发送LDAP服务器，LDAP服务器在数据库中搜寻满足用户请求的信息，并通过Web服务器将相关信息发送给用户。

如果LDAP服务器在用户所在蜂窝范围内没找到满足条件的内容，则搜索相邻的蜂窝，如果仍未找到，就向用户回复相关信息。

如图1所示，为基本的LBS构成。

随着LBS占据移动市场越来越重的份额，一方面可以预见LBS将更为深刻地影响人们生活和出行的方式，与此同时，这种趋势也对LBS提出了更高的要求。

移动用户所携带的移动终端获取用户当前的位置信息，用户想服务器提出服务请求，继而获取与当前位置相关的服务。

由于服务器是根据用户的位置信息来处理服务请求，那么用户的位置信息则存在被泄露或者被非法使用的风险。

随着LBS的发展，由此带来的位置隐私保护也越来越受到人们的重视。

某些不法分子可以通过获取特定用户的位置信息，推测出用户的生活轨迹和习惯，从而得知用户的其他私密信息，这将极大危害到用户的隐私和利益。

如何保护用户位置隐私成为近年来亟待解决的问题，也是近几年信息安全领域的一大研究热点。

目前，已有很多针对LBS环境下的位置隐私保护研究，也有一些相对而言简单有效的技术提出。

位置隐私保护是阻止其他个体或团体知道某个用户当前或过去的位置的能力。

由于位置信息服务需借助用户位置信息，因此用户信息越准确，服务器返回给用户的服务信息的正确性、可靠性、准确性也会越高，用户信息的精确度决定了LBS的质量。

而用户却需要在不暴露隐私信息的前提下获得高质量的服务。

因此，平衡位置隐私保护和服务质量之间的矛盾是基于位置服务中位置隐私保护的核心问题。

[2]另外，在不同的移动网络中，也有许多具体的问题需要解决，而不同的隐私保护方案诸如服务器负担加重等问题，使得目前为止，仍没有一个最优的方案来解决位置隐私保护的问题。

但是前人的研究却给后来者提供了很多启发。

接下来的篇幅将简要介绍几种典型的方案与算法并分析各自的利弊。

最后，讨论目前位置隐私保护方法中存在的问题以及未来的研究方向。

2.位置隐私保护位置隐私信息由标识信息和位置信息组成[3]。

标识信息表示用户的静态属性或特征，用来唯一标识一个用户。

位置信息则描述某个个体或团体的行踪。

传统的位置隐私保护的方法主要是根据组成位置隐私信息的两类信息来进行分类[2]。

一类方法是向服务器提供准确的用户位置信息，以便得到高质量的服务信息，而将用户的标识信息（例如匿名、假名等）进行隐藏；另一类方法是将用户的标识信息完全暴露给服务器，而将用户位置信息进行隐藏，即将用户的位置信息模糊化（泛化）后提供给服务器，以达到位置隐私保护的目的；再者是将上两类方法的结合方案。

2.1 身份保护方法2.1.1 k-匿名位置隐私技术Sweeney[4]在2002年最先提出的k-匿名方法是一种广泛应用于数据发布中的数据隐私保护的技术。

该方法对每条记录的非敏感属性进行泛化，使得发布后的数据中的每条记录都至少不能和其他k-1条记录区别开来。

该方法的思想被一些研究者移植到位置隐私保护中，是最早提出的位置隐私保护方法，并成为了目前使用最普遍的方法。

其中，“匿名”的思想，属于身份保护，即用户的ID不能跟其他k-1个用户的ID区分开来，这样，即使某个用户的位置信息被攻击者截获，攻击者也无法得知究竟是哪个用户像服务器发送了请求。

k-匿名技术被证明能够防止用户位置信息泄露，并从根本上防止用户的身份信息泄露。

k-匿名保护需要引入一个集中式的第三方平台即匿名器。

当用户向服务器发送LBS 服务请求时，先把位置信息发送给匿名器。

匿名器将用户的位置坐标泛化成一个具有k-匿名性质的区域即匿名区ASR( anonymous spatial region) ，并且该区域在面积上不小于一定的值，且区域内至少有k个用户，用户的身份在该区域内被识别出来的概率为1 /k。

采用该方案时，LBS服务器需要添加一个查询处理器，专门用来快速地处理空间区域的查询，找出所有的候选结果即候选集( candidate set，CS) ，并返回给用户，让用户从中选择一个最优的。

虽然该方案考虑周全，能够在很大程度上解决位置隐私保护存在的问题，但是增加了服务器的运算资源，并且加重了网络的负载。

目前，k-匿名方法是普遍使用的位置隐私保护方法。

文献[1]总结了几种常见的匿名算法。

其中，间隔匿名(interval cloak)算法和Casper匿名(Casper cloak)算法，也称作小集团算法(clique cloak)算法的基本思路都是由匿名服务器构建一个四叉树数据结构，将平面控件递归地用十字分成四个面积相等的正方形区间，直到所得到的最小的正方形区间的面积为系统要求的允许用户所采用的最小匿名面积位置为之，每个正方形区间对应于四叉树中的一个节点，系统中的用户每隔一定的时间将自己的位置坐标上报给匿名服务器，匿名服务器更新并统计每个节点对应区间内的用户数量。

当用户进行匿名查询时，匿名器通过检索四叉树为用户U 生成一个匿名区ASR，间隔匿名算法从包含用户U 的四叉树的叶子节点开始向四叉树根的方向搜索，直到找到包含不低于k 个用户的节点( 包括用户U在内) ，并把该节点所对应的区域作为用户U的一个匿名区ASR。

如图2所示，如果用户u1发起k = 2 的匿名查询，间隔匿名算法将首先搜索到象限区间［( 0，0) ，( 1，1) ］，其中包含不少于2 个用户。

接下来，间隔匿名算法将就向根的方向上升一级搜索象限区间［( 0，0) ，( 2，2) ］，该象限区间包含3 个用户，大于要求的2个，算法停止搜索，并将该区间作为用户u1的匿名区ASR。

而Casper cloak 的做法是依次检查它的两个相邻的兄弟节点和它所组合起来的区间中所包含的用户数量是否大于等于k，如果满足则直接将组合区间作为用户的匿名区，否则再对其父节点进行搜索。

文献[1]还介绍了Hilbert匿名( Hilbert cloak) 算法，也称做小集团算法(clique cloak)，以及匿名区分割算法，这里就不再赘述了。

图表2 匿名实例注：图表2来自文献[1]2.1.2 k-匿名位置隐私技术的优化与改进在位置隐私保护中，不同的用户有不同的位置K-匿名需求，针对K-匿名法的局限性，由Gedik and Liu[6]首先提出了个性化K－匿名法。

个性化K-匿名法是改进的K-匿名法，在这种方法中，每位用户可以自行定义其所需的匿名等级，根据匿名等级设置相应的位置隐私策略，并通过分类树的节点来定义隐私保护程度，此时有着相同K 值的移动用户信息可能被一起匿名化。

这种方法的缺点在于当K 值增高时，模糊的信息量就会减少，匿名化信息的比例会逐渐下降。

文献[8]提供了一种个性k-匿名算法，在普通匿名算法中增加匿名群记忆模块，从而加快匿名算法的匿名速度。

仿真结果表明当用户对安全要求较高的情况下，新匿名算法与普通算法相比具有更快的匿名速度，同时匿名成功率也得到了提升;但在用户对安全要求低的情况下，新算法在匿名速度方面要慢于普通算法，成功率方面的优势也不明显。

由于发送给LBS提供方的用户信息被第三方平台匿名器模糊化，进而对服务器查询优化，以及查询安全的要求进一步提高。

同时，文献[10]提出仅仅保护用户身份的匿名性是是不够的，为了防止攻击者非法攻击服务器，再通过高级数据挖掘技术，进而获得用户的隐私，文献进行了服务器端查询结果完整性和数据保密性的研究，引入了基于锚点的增量查询的方法，提出了一个改进的保证空间数据保密性和查询结果完整性的隐私保护方案。

即便在同一地点进行多次查询，变换每次查询、验证过程的锚点信息，使得每次查询时两轮交互所基于的希尔伯特值都与之前不一样，这样攻击者就无法区分第一轮和第二轮的查询，找不到两者的对应关系，进而抵抗了用户在同一地点发起重复请求时容易遭受的攻击[10]。

2.1.3 假名技术假名是匿名的一种特殊类型，每个用户使用一个假名来达到隐藏真实ID的目的。

恶意的攻击者虽然可能从服务器端得到用户的准确位置信息，但不能准确地将位置信息与用户的真实信息联系起来，增加了定位某个具体用户的难度，从而达到用户位置隐私保护的目的。

[2] Beresford和Stajano提出了一种重要的身份保护方法——混合区域(mix zone)。

该方法定义了两种类型的区域：应用区域和混合区域。

这两种类型的区域都是一个空间区域。

在应用区域中，用户可以提出服务请求和接收服务信息；但在混合区域中，用户没有任何通信。

这种方法的有效性在于用户使用假名。

为了更好地保护用户的位置隐私，用户使用同一个假名不能超过一定的时间。

例如用户在进入混合区域之前使用某一个假名，出混合区域时使用另一个不同的假名。