一种基于位置模糊化的假名动态生成方法

摘要

本发明提出了一种基于位置模糊化的假名动态生成方法，针对基于位置服务中移动用户发起连续查询请求不能很好的保护用户的位置隐私。在移动通信中，用户在享受基于位置的服务LBS带来的方便与快捷同时，容易遭受到攻击者实施的连续查询攻击：匿名区域交叉攻击和匿名区域收缩攻击，最终会导致用户的位置信息暴露。因此本发明针对匿名区域交叉攻击提出一种方法，在匿名服务器生成匿名区域的过程中给查询发起者动态生成必要的假名，使得攻击者不能通过对比历史匿名区域以及当前的匿名区域挖掘出用户的真实身份，从而攻击者不能把截取到的位置信息与真实用户的身份一一对应起来，实现了用户的位置隐私安全。

说明书

技术领域

本发明涉及移动通信中基于位置服务的隐私保护技术领域，具体是面向连 续查询中匿名区域交叉攻击下的用户位置隐私安全保护。

背景技术

基于位置服务(Location-BasedServices，LBS)随着移动定位技术以及无 线通信技术的快速发展，已经成为人们生活中不可或缺的一部分。人们可以通 过任何的移动设备，如手机、PDA等，查询到各种所需要的信息，例如离我最 近的电影院等。在基于位置服务能给人们带来方便快捷与高效服务的同时，它 也给那些不法之徒带来了有机可乘的机会，随之而来的就是位置隐私遭到泄露。 由于用户发起基于位置服务请求的时候，需要提交想要查询的内容以及自己的 精确位置信息给服务提供商，攻击者就可以截取到用户的位置信息，从而可能 造成用户的位置隐私泄露。因此，为了能够有效地保护用户的位置隐私，提出 了位置信息模糊化的概念。位置信息模糊化又可以细分为用户的身份模糊以及 用户的位置模糊。身份模糊常用的方法可以是身份匿名或者说假名策略，就是 说在发送的请求中将用户的身份直接删除或者说利用某种机制生成一个假的ID 代替用户的真实身份发送给位置服务提供商。位置模糊常用的方法是位置K匿 名，将K-1个其他和真实用户不可区分的用户位置信息和查询发起者的位置信 息一起形成的匿名区域发送给位置服务提供商，这样攻击者即使能截取到该匿 名区域也无法将K个位置与用户的身份一一对应起来。在基于位置服务的应用 中，攻击者能力有限的情况下，以上两种方法可以有效保护用户的位置隐私安 全。

随着移动设备的普及，基于位置服务(LBS)的流行，位置隐私的安全在 该领域是一个巨大的挑战。现有的K-匿名模型主要针对的是快照查询，所谓快 照查询即是说用户前后发起的查询请求无关联。但是在现实生活中人们发起的 主要是连续查询，即是说用户在查询某具体的地点的时候，会连续发起多次查 询请求来确定自己的前进路线是否正确。例如车载导航系统，会连续发送同一 地点的查询请求以确保路线正确。如果将快照查询的位置隐私保护技术直接应 用到连续查询中，攻击者可以通过收集不同时刻的匿名空间区域实施区域交叉 攻击很容易的就能推测出查询发起者的实际位置或者行动路线。因此，连续查 询作为位置隐私保护的热点问题之一，如何在用户的连续查询过程中去保护用 户的位置隐私是非常有必要的。

目前，已提出了一种针对连续查询的位置隐私保护方法，提出在初始时刻 生成的匿名空间区域内的移动用户，在整个查询生命周期内都有效，即不改变 匿名空间区域中的移动用户，而只是根据匿名空间区域中移动用户的移动距离 来改变匿名空间区域的大小。虽然在特定的情况下该方法有效，但是随着移动 用户的移动，匿名空间区域会随着变大或者变小甚至重合，导致的后果就是位 置服务质量下降或者用户的位置隐私需求得不到满足。

发明内容

为了克服上述现有技术中存在的缺陷，本发明的目的是提供一种根据用户 的隐私需求来生成相应匿名空间区域大小的方法。该方法通过在可信第三方的 匿名服务器中嵌入一个动态假名生成模块，根据用户的查询请求以及历史匿名 空间区域来为真实查询发起者生成合适的假名，从而抵制攻击者通过历史匿名 空间区域来实施区域交叉攻击，迷惑攻击者不能推测或挖掘出真实用户的位置 信息。

为了实现本发明的上述目的，本发明提供了一种基于位置模糊化的假名动 态生成方法，包括如下步骤：

步骤一：用户发送K匿名查询请求P(ID,L,Q,T_q)，其中，ID为用户的身 份标识；L为用户的位置信息，Q为请求查询的内容，T_q为请求发起的时间； 匿名服务器根据用户的隐私需求K生成匿名空间区域CR_i，然后判断该用户是 否为首次发起匿名查询请求，如果是，则直接将匿名空间区域CR_i以及查询内容 Q发送给位置服务提供商；否则，进入下一步。

步骤二：匿名服务器判断当前时刻用户的匿名空间区域的匿名集S_i是否与 历史匿名集S_k,k＝1,2,...,i-1相同，如果相同，则将历史匿名区域CR_k发送给位 置服务提供商；否则，进入下一步。

步骤三：匿名服务器针对发起查询的用户，根据系统时间的唯一性，动态 生成与历史假名不重复的4位数的用户假名newID。具体地，所述匿名服务器 生成用户假名newID时，采用假名生成函数P(ST)，该函数根据用户上一时刻的 用户名生成一个唯一的假名。

步骤四：将假名newID与用户的真实身份标识oldID比较，如果不相同，就 进入下一步；否则，回到步骤三。

步骤五：将步骤三生成的用户假名newID与当前时刻用户的匿名空间区域 的匿名集S_i中其他用户身份标识otherID进行比较；如果不同，则生成新的匿名 空间区域newCR_i，并将新的匿名空间区域newCR_i和查询内容Q一起发送给位置 服务提供商；否则，回到步骤三。

在以上基础上，本发明还包括位置服务提供商搜索出候选结果集，然后返 回给匿名服务器，匿名服务器根据匿名集对返回的候选结果集进行筛选；最后 再返回给用户，用户根据自己的实际位置在筛选后的结果集中查找自己所需的 服务信息。

本发明提出了一种基于位置模糊化的假名动态生成方法，在生成的匿名空 间区域不满足隐私需求的情况下，启动假名动态生成算法:使用假名生成函数 P(ST)，将生成的假名与真实用户的身份标识信息以及当前时刻的其他K-1个 用户的身份标识信息进行比较，如果和其中的任何一个身份标识信息相同，则 重新运行假名生成函数，最终要使得生成假名过后的匿名空间区域满足用户的 隐私需求，从而攻击者不能通过用户的历史空间匿名区域去进行数据挖掘或者 实施空间区域交叉攻击来得到用户的真实位置信息，以此来保证用户的位置隐 私安全。

本发明通过基于位置模糊化的假名动态生成方法来为用户在需要的时刻生 成假名，形成一个可安全发布的匿名空间区域，从而达到有效抵抗匿名空间区 域交叉攻击。同时，新生成的匿名空间区域不会因为用户太分散而变得很大， 因此降低了位置服务提供商在检索目标查询内容时所花的开销，提高了用户获 得的服务质量；由于基于位置模糊化的假名动态生成策略每次都要判断用户生 成的匿名空间区域的有效性，为不能安全发布的匿名空间区域重新生成新的匿 名集，从而大大的提高了用户位置的匿名成功率。

附图说明

本发明的上述和/或附加的方面和优点，结合下面附图对实施例的描述中将 变得明显和容易理解，其中：

图1是本发明的原理图；

图2是本发明的利用动态假名生成匿名空间区域流程图；

图3是本发明的系统架构图；

图4是本发明的连续查询匿名空间区域交叉攻击示意图；

图5是本发明的匿名服务器内部结构模型图。

具体实施方式

下面结合附图对本发明的具体实施作进一步的详细阐明。

参见图1，一种基于位置模糊化的假名动态生成方法包括：在生成匿名区域 (CloakingRegion,CR)的过程中，匿名服务器(AnonymousServer,AS)根据 用户的位置隐私需求K以及匿名集是否变化来为查询发起者动态生成假名，以 生成适合要求的匿名区域。也就是说，当查询发起者是首次发起匿名请求 P(ID,L,Q,T_q)，其中，ID为用户的身份标识；L为用户的位置信息，一般用坐 标表示；Q为请求查询的内容；T_q为请求发起的时间；用户身份标识信息未曾 暴露，则可以直接由匿名服务器AS发送给位置服务提供商LSP，纵然攻击者有 能力截取到相关信息，但是信息量不够根本不能推测出请求发起者是谁。其次， 当查询发起者非首次发起匿名请求，那么匿名服务器AS就要判断其匿名集S_i是 否与历史匿名集S_k(k＝1,2,...,i-1)相同，i表示当前时刻，如果相同，则直接将 历史匿名集S_k发送给位置服务提供商LSP，因为攻击者无法通过比较相同的匿 名集去发动匿名区域交叉攻击，否则，匿名服务器启动假名动态生成算法为请 求发起者生成一个和以往ID不同的假名，从而达到迷惑攻击者的目的。这样， 即使攻击者截取到足够多的历史匿名区域，他也无法分辨出谁是请求发起者。

匿名服务器AS根据请求发起者的位置隐私需求K生成对应匿名空间区域， 然后将它发送给位置服务提供商LSP。同时匿名服务器AS存储匿名空间区域， 形如：([x₁,y₁],[x₂,y₂],[t₁,t₂])，表示移动用户在([t₁,t₂])这个时间段内的某一时 刻在二维空间([x₁,y₁],[x₂,y₂])内，以及其中所有用户的身份标识ID。在匿名服 务器AS接收到用户的K匿名请求后，根据存储的历史记录来判定用户是否是首 次发起请求以及根据当前时刻t_i所能生成的匿名集S_i与t_k(k＝1,2,...,i-1)时刻的 匿名集S_k相比较，若S_i∩S_k≥2,那么匿名服务器AS可以直接将首次匿名空间区 域CR₁或者历史匿名空间区域CR_k发送给位置服务提供商LSP。

匿名服务器AS内嵌入一个假名动态生成算法，对需要假名变换的匿名区域 进行假名生成。假设一个用户发起一个3-匿名请求(即K的大小为3)，则匿名 服务器在确定该用户是非首次发起匿名请求以及此时生成的匿名区域的匿名集 中除了用户发起者与过去某个时刻的匿名集不相同，即是说 S_i∩S_k<2(k＝1,2,...,i-1)，则启动假名动态生成算法。如匿名集中有3个用户分别 是：A、B和C，并假设用户A为这个匿名请求的发起者。由于B和C发生变化， 与历史匿名集中除查询发起者不同，如果查询发起者A依然采用首次使用的真 实ID或者使用上一时刻的假名，那么攻击者就可以根据匿名区域交叉攻击去推 测出真实的用户发起者。因此，对A启动假名生成函数P(ST)。此时，A不同于 以往任何时刻的ID，攻击者无法凭借他的知识推测出查询发起者到底是谁。

当针对查询发起者启动假名动态生函数P(ST)后，匿名服务器AS利用系统 时间的唯一性，动态生成与历史假名不重复的4位数的ID。再进行如下操作： 将生成的假名newID与用户的真实身份oldID比较，如果相同则重新运行假名生 成函数P(ST)。反之，再循环比较生成的假名newID与匿名集S_i中的其他用户 的身份标识符otherID，如果不同，则发送修改后的匿名空间区域给位置服务提 供商LSP，否则再次回到假名动态生成步骤。

匿名服务器为查询发起者生成假名过后，在一个3-匿名的匿名集中有3个 不同ID的用户，由于真实用户的ID是严格按照和以往ID不重复的要求，那么 其余两个ID都有可能出现在其他的任何一个或几个匿名区域中，那么攻击者通 过区域交叉攻击很有可能会认为其余的ID为查询发起者，这样就更加迷惑了敌 人将矛头指向其他非真实用户，从而达到更好的位置隐私保护效果。

位置服务提供商将搜索出的候选结果集返回给匿名服务器，然后匿名服务 器根据匿名集对返回的结果进行更精确的筛选。最后再返回去用户，用户根据 自己的实际位置在精确的候选结果集中查找自己所需的服务信息。

图2是本发明的利用动态假名生成匿名空间区域流程图。本发明定义的匿 名空间区域生成模型实际上是在位置模糊化的基础上再对查询发起者的身份标 识信息进行适当的修改以阻止攻击者的区域交叉攻击推测出用户身份与位置信 息的对应关系。图2所述的假名动态生成算法的实时步骤如下：第一步：当用 户发起查询请求，匿名服务器根据位置模糊化技术生成对应的匿名空间区域 CR_i，然后判断其是不是首次发起请求，如果是，则直接将生成的匿名空间区域 CR_i发送给位置服务提供商LSP。第二步:从查询发起者的历史空间区域匿名集 中取一个匿名集S_k(k＝1,2,...,i-1)，然后与当前生成的匿名集S_i比较判断S_i∩S_k是否大于等于2，如果是，则取匿名空间区域CR_k直接发送给位置服务提供商 LSP，反之，判断是否所有的历史匿名集都比较判断过。没有遍历完历史匿名 集的话重复第二步工作。第三步:当用户不是首次发起请求，历史匿名集中也没 有找到合适的空间区域，则运行假名生成函数P(ST)，为用户生成新的身份标识 符newID，然后分别判断其与用户的原始身份标识符oldID是否相同，与当前匿 名集中的用户身份标识符otherID∈S_i是否相同，倘若任何一个相同，则重复第 三步工作。由于我们所提出的假名生成函数P(ST)的唯一性，不需要去比较以 前生成的假身份标识符。最终，将以newID生成的newCR_i发送给位置服务提供商 LSP。

图3是本发明的系统架构图。共分为三部分：移动终端、可信第三方、位 置服务提供商。如图可知，如果某个移动用户需要基于位置的服务，那么先要 把自身的真实位置信息、查询的内容和隐私需求(例如匿名度K和匿名区域的 最小面积S)同时发送给可信第三方(也就是匿名服务器)，当可信第三方接收 到用户的请求，就会利用某一种匿名机制(比如模糊化算法)把用户的实际位 置扩大为一个符合用户隐私需求的匿名空间区域。另外，可信第三方还必须取 消查询内容的标识信息，将生产的匿名空间区域以及查询请求一起发送给位置 服务提供商，并时刻监测位置空间范围中的各个移动用户，周期性的更新生成 的匿名空间区域，位置服务提供商收到用户的请求后，需要对匿名空间区域中 的所有位置进行检索并给出候选结果集，再将全部的结果集反馈给可信第三方， 最后结合移动用户所处的实际位置可信第三方对候选结果集进行求精处理，然 后将最合理准确的结果返回给移动用户。

图4是本发明的连续查询匿名空间区域交叉攻击示意图。当一个用户发起 连续查询请求时，攻击者可以在不知道用户任何背景知识的情况下，通过攻击 位置服务提供商或者利用其他途径获得连续查询用户生成的不同匿名空间区 域，然后简单的将多个连续的匿名空间区域取交集就能知道发送查询的用户的 身份，攻击者再对获取的多个连续匿名空间区域进行挖掘，就能推测出用户的 位置信息。如图所示，黑色圆圈代表移动用户，箭头代表移动方向。图中移动 用户A发起3-匿名查询，在用户发起连续查询的3个不同时刻生成了不同的匿 名空间区域。在t_i时刻，用户A生成的匿名区域中包括移动用户A，D和E，由 于用户一直处于移动状态，当用户A在t_i+1时刻，其生成的匿名空间区域包括 A,B和D，注意此时刻用户E已经不再匿名区域中。在t_i+2时刻，当用户的匿名 空间区域再次重新生成时，此时包括的用户又变为A，F和H。因此，当攻击 者获得这三个匿名空间区域后，只需要对三个匿名空间区域进行简单的取交集 就能发现查询请求的发起者是用户A。

图5是本发明的匿名服务器内部结构模型图。如图所示，用户信息是指用 户个人信息和用户的个性化需求信息等。位置信息包括用户的实时位置信息、 用户的历史位置信息以及生成的历史匿名空间区域等。动态假名生成在用户的 真实身份或者历史假名不符合用户的隐私需求时，生成一个符合匿名空间区域 生成的假名。匿名服务器的假名映射机制保存用户真假名之间的映射关系。最 后位置匿名机制为用户生成匿名的空间区域以模糊化用户的精确位置，从而达 到用户位置隐私保护的目的。