一种位置服务中基于虚假位置的隐私保护方法

摘要

本发明提供了一种位置服务中基于虚假位置的隐私保护方法，属于信息安全技术领域。本发明基于DLS算法，采用熵来衡定匿名化程度，并综合考量了用户端的计算复杂度和用户隐私要求之间的均衡。由于在选择假位置时考虑了可能被攻击者利用的边信息，所以本发明能够有效的实现K匿名，使用户能够获得足够大的熵值，降低用户真实位置暴露的概率；且本发明针对不同位置的不同用户作出了不同的方式选择假位置，因此在任何情况下用户采用本发明选择的假位置都能很好的保护用户的位置隐私。

说明书

技术领域

本发明属于信息安全技术领域，具体涉及一种位置服务中基于虚假位置的隐私保护方法。

背景技术

随着移动设备和社交网络的迅速发展，基于位置的服务(LBS，Location-Based Service) 应用越来越广泛。当移动用户需要使用某种位置服务时，移动用户首先使用定位装置(比如 内置GPS的智能手机)获得自己的位置信息，然后将查询请求(可能包含用户的身份、兴趣 爱好、位置信息)发送给LBS服务器，经过LBS服务器处理服务请求信息，最后从LBS服 务器获得自己感兴趣的信息。当用户享受位置服务和定位技术带来的便利和娱乐时，也承担 着敏感信息泄露的风险。根据某个用户的位置服务查询请求，攻击者不仅可以将位置信息和 兴趣爱好与用户的身份关联起来，还可以推测出用户更多的隐私信息。因此，基于位置服务 中的隐私保护研究受到了学术界的广泛关注。

K匿名技术作为解决当前位置服务中位置隐私保护问题的技术手段，近年来受到了国内 外未来LBS领域研究的广泛关注。K匿名技术的目的就是确保用户不被攻击者识别出真实位 置的概率至少是1/K。基于K匿名方法的部分现有研究在选择假位置的时候考虑了可能被攻 击者利用的边信息，边信息是指位置地图上每个位置用户发送位置服务请求的历史概率。

Niu等人提出的DLS算法就是一种考虑边信息而选择假位置方法(Niu,B.et al..Achieving  k-anonymity in privacy-aware location-based services[C].IEEE INFOCOM,2014,754–762.)。 DLS算法用熵来衡定用户的隐私级别，熵值越大表明用户的隐私级别越高。DLS方法将其所 服务的区域划分成n×n＝N个大小相同的位置单元，每个位置单元都对应一个历史查询概率 (query probability based on the previous query history)，具体定义如下：

(1≤i≤N),且$\underset{i=1}{\overset{N}{\Sigma }}{p}_i=1$

其中，p_i为所划分区域中第i个位置单元的历史查询概率，N代表LBS服务器服务范围内的 位置单元总数。

在基于DLS算法的LBS系统中，LBS服务器需要统计出服务区域每个位置单元内用户发送 位置服务请求的历史概率，然后发布这份概率信息，这样每个用户都可以得到位置请求历史 概率。当用户需要某种位置服务时，用户首先利用GPS等定位装置获得自己的准确位置，根 据位置请求历史概率获得当前所处位置发送位置服务请求的历史概率，然后根据用户的匿名 度要求K，从位置地图中寻找出2K个与当前位置发送请求历史概率接近的候选位置，最后计 算从该2K个候选位置中选择的所有可能K-1个位置和用户真实位置构成的K个位置的熵值，选 择使熵值最大的K个位置作为用户向LBS服务器发送的位置信息。

虽然DLS算法能够实现K匿名，保护用户的位置隐私，但该方法适用于服务区域中有很 多位置与用户真实位置发送请求的历史概率相同的状况。当位置地图没有位置与用户真实位 置发送请求的历史概率相同时，该方法并不能很好的保护用户的位置隐私，并且可能有很高 的概率能被攻击者识别出用户的真实位置。同时，该方法在选择K-1个假位置时采用了枚举 的方法，虽然保证了选择的K个位置熵值是最大的，但是算法复杂度较高、收敛速度太慢， 尤其不能适用于匿名度要求很高的用户。

发明内容

本发明要解决的技术问题是，为保护位置服务中用户的位置隐私提出一种假位置选择方 法。本发明提供的方法基于DLS算法，综合考虑了选择假位置时的关键问题：不仅考虑可能 被攻击者掌握的边信息之外，并综合考量用户端的计算复杂度和用户隐私要求之间的均衡。

本发明采用如下技术方案：

一种位置服务中基于虚假位置的隐私保护方法，其流程如图1所示，具体包括以下步骤：

步骤1.当用户端需要某种位置服务时，用户根据自身隐私要求设定合适的匿名度K，执 行步骤2；

步骤2.用户端首先利用定位装置如GPS获取其自身的准确位置L_real，然后根据从LBS 服务器获得的每个位置单元的历史查询概率及相应坐标的表项集合P确定用户当前位置的历 史查询概率p_L；接着，用户端挑选出集合P中与概率值p_L不等的概率值并汇于概率集合中， 集合P中与概率值p_L相等的概率值汇于集合S中，用表示集合S的大小；设定阈 值K'，K/5<K'<K，并优先选择使K/K'为偶数时的K'，用户端根据K'、K及之间的大小关 系选取剩余K-1个假位置：若则执行步骤2-1，若则执行步骤2-2，若 则执行步骤2-3；

步骤2-1.若用户端直接从概率集合S中随机选择非真实用户所在位置的K-1个 概率值，并将这K-1个概率值对应的坐标作为假位置，连同用户端真实位置一同发送给LBS 服务器，完成用户端位置服务请求的发送；

步骤2-2.若用户端从概率集合中选择与用户端真实位置的历史查询概率 值p_L大小最接近的个概率值，并组成集合C，执行步骤2-2-1；

步骤2-2-1.令p_max和p_min分别为概率集合S中的最大值和最小值，定义p_max-min为集合C 中不小于p_max的最小值，p_min-max为集合C中不大于p_min的最大值，比较概率集合[S∪p_max-min] 和概率集合[S∪p_min-max]的熵值，并将集合S更新为熵值较大的那个概率集合；若集合S更新 为集合[S∪p_max-min]，则将集合C更新为剔除p_max-min后的概率集合；若集合S更新为集合[S ∪p_min-max]，则将集合C更新为剔除p_min-max后的概率集合；执行步骤2-2-2；

步骤2-2-2.重复步骤2-2-1直到集合S的元素个数为K时止，把集合S中包含有用户端 真实位置的这K个概率值对应的坐标发送至LBS服务器，完成用户端位置服务请求的发送；

步骤2-3.若令集合从概率集合中选择与用户端真实位置的历 史查询概率值p_L大小最接近的K²/K'-ε-ω个概率值，构成侯选假位置概率集合其中有 [K²/(2K')]-ε个概率值小于p_L，剩余[K²/(2K')]-ω个概率值大于p_L，且 ε和ω由用户端自行设定，并优先满足：ω>ε，执行步骤2-3-1；

步骤2-3-1.令：

${\bar{p}}_L=\exp \left(\frac{\underset{s_i\in S}{\Sigma }{s}_i\ln s_i}{\underset{s_i\in S}{\Sigma }{s}_i}\right)$

其中，s_i为集合中第i个元素，并定义为集合中不小于的最小值，为 集合中不大于的最大值，然后比较概率集合和概率集合的熵 值，并将集合更新为熵值较大的那个概率集合；若集合更新为集合则将 集合更新为剔除后的概率集合；若集合更新为集合则将集合更 新为剔除后的概率集合；执行步骤2-3-2；

步骤2-3-2.重复步骤2-3-1直到集合中的元素个数为K时止，把集合中包含有用户 端真实位置的这K个概率值对应的坐标发送给LBS服务器，完成用户端位置服务请求的发送。

本发明的有益效果是：

(1)由于在选择假位置时候考虑了可能被攻击者利用的边信息，所以本发明能够有效的 实现K匿名，使用户能够获得足够大的熵值，降低用户真实位置暴露的概率；

(2)由于本发明针对不同位置的不同用户作出了不同的方式选择假位置，因此在任何情 况下用户采用本发明选择的假位置都能很好的保护用户的位置隐私；

(3)本发明提出的选择假位置的方法能够大大减少用户端的计算开销；因此，发明不仅 适用于隐私要求比较低的用户，隐私要求比较低高的用户。

附图说明

图1为本发明提供的位置服务中基于虚假位置的隐私保护方法的流程示意图。

具体实施方式

本具体实施方式提供一种位置服务中基于虚假位置的隐私保护方法，其流程如图1所示， 具体包括以下步骤：

步骤1.当用户端需要某种位置服务时，用户根据自身隐私要求设定合适的匿名度K，执 行步骤2；

步骤2.用户端首先利用定位装置如GPS获取其自身的准确位置L_real，然后根据从LBS 服务器获得的每个位置单元的历史查询概率及相应坐标的表项集合P确定用户当前位置的历 史查询概率p_L；接着，用户端挑选出集合P中与概率值p_L不等的概率值并汇于概率集合中， 集合P中与概率值p_L相等的概率值汇于集合S中，用表示集合S的大小；设定阈 值K'，K/5<K'<K，并优先选择使K/K'为偶数时的K'，用户端根据K'、K及之间的大小关 系选取剩余K-1个假位置：若则执行步骤2-1，若则执行步骤2-2，若 则执行步骤2-3；

步骤2-1.若用户端直接从概率集合S中随机选择非真实用户所在位置的K-1个 概率值，并将这K-1个概率值对应的坐标作为假位置，连同用户端真实位置一同发送给LBS 服务器，完成用户端位置服务请求的发送；

在从集合P中任意选取K-1个假位置与用户端真实位置对应的历史查询概率组成的概率 集合中，本步骤所选取的K-1个假位置与用户端真实位置对应历史查询概率组成的概率集合 的熵值是最大的；这样选择K-1个假位置能减少用户端的计算开销，因为在这种情况下，不 管怎样选择K-1假位置，要使相应概率集合的熵值最大，假位置对应的查询概率必须从概率 集合S中选择。此时，用户的位置隐私能够很好地被保护，因为所有假位置的历史请求概率 都相同，即使攻击者知道LBS系统中每个位置单元的历史查询概率，也无法得知用户的真实 位置，用户真实位置被猜中的概率至多为1/K；

步骤2-2.若用户端从概率集合中选择与用户端真实位置的历史查询概率 值p_L大小最接近的个概率值，并组成集合C，执行步骤2-2-1；

本步骤所选择的个概率值，一方面可使用户端最终选择的K个位置对应的概率 集合的熵值足够大，且理论上最优的K-1个假位置的概率值组合也是在集合C∪S中产生的； 另一方面将选择假位置的范围大大缩小，由此减少计算复杂度；

步骤2-2-1.令p_max和p_min分别为概率集合S中的最大值和最小值，定义p_max-min为集合C 中不小于p_max的最小值，p_min-max为集合C中不大于p_min的最大值，比较概率集合[S∪p_max-min] 和概率集合[S∪p_min-max]的熵值，并将集合S更新为熵值较大的那个概率集合；若集合S更新 为集合[S∪p_max-min]，则将集合C更新为剔除p_max-min后的概率集合；若集合S更新为集合[S ∪p_min-max]，则将集合C更新为剔除p_min-max后的概率集合；执行步骤2-2-2；概率集合的熵值 H由如下公式确定：

$H=-\underset{i=1}{\overset{m}{\Sigma }}\left[q_i{\log }_2{q}_i\right],q_i=\frac{p_i}{\underset{i=1}{\overset{m}{\Sigma }}{p}_i}---\left(1\right)$

其中，m为概率集合的概率值数量，p_i为概率集合的第i个概率值；

步骤2-2-2.重复步骤2-2-1直到集合S的元素个数为K时止，把集合S中包含有用户端 真实位置的这K个概率值对应的坐标发送至LBS服务器，完成用户端位置服务请求的发送；

本步骤选择出的K个位置对应的概率集合的熵值不仅与理论最大值十分接近，而且还能 减少用户在选择假位置的计算复杂度，在这种情况下，用户的位置隐私能够得到很好的保护， 因为在所有假位置中确保了有足够多的假位置与用户真实位置的查询请求概率相同，即使攻 击者知道LBS系统中每个位置的历史查询概率，并通过某种手段推测出发起服务请求位置点 的概率为p_L，仍然无法获得用户端的真实位置；

步骤2-3.若令集合从概率集合中选择与用户端真实位置的历 史查询概率值p_L大小最接近的K²/K'-ε-ω个概率值，构成侯选假位置概率集合其中有 [K²/(2K')]-ε个概率值小于p_L，剩余[K²/(2K')]-ω个概率值大于p_L，且 ε和ω由用户端自行设定，并优先满足：ω>ε，执行步骤2-3-1；

步骤2-3-1.令：

${\bar{p}}_L=\exp \left(\frac{\underset{s_i\in \bar{S}}{\Sigma }{s}_i\ln s_i}{\underset{s_i\in \bar{S}}{\Sigma }{s}_i}\right)$

其中，s_i为集合中第i个元素，并定义为集合中不小于的最小值，为 集合中不大于的最大值，然后比较概率集合和概率集合的熵 值，并将集合更新为熵值较大的那个概率集合；若集合更新为集合则将 集合更新为剔除后的概率集合；若集合更新为集合则将集合更 新为剔除后的概率集合；执行步骤2-3-2；

步骤2-3-2.重复步骤2-3-1直到集合中的元素个数为K时止，把集合中包含有用户 端真实位置的这K个概率值对应的坐标发送给LBS服务器，完成用户端位置服务请求的发送；

本步骤选择出的K个位置对应的概率集合的熵值不一定是最大的，但确能很好的保护用 户的位置隐私。当采取枚举的方法来选择假位置时，由于假位置中没有与p_L相同的请求概率， 如果攻击者知道LBS系统中每个位置的历史查询概率，并通过某种手段推测出发起服务请求 位置点的概率为p_L，那么用户的真实位置暴露的概率是非常高。在本发明中，在开始选择假 位置的时候，用户随机从集合选择了一个位置作为用户的假位置，这个随机假位置的选取 将决定后面K-2个假位置，因此由于假位置选择的随机性将决定最后K个假位置的随机性。 这样，即使攻击者知道用户选择假位置的机制，由于程序每运行一次产生的K个假位置可能 会不同，并且在不同位置选择的K个位置可能也会相同，因此攻击者就不会知道用户的真实 位置到底是哪一个。在这种情况下，其实用户是牺牲熵值来保护自己的位置隐私，用户选择 的K个位置可能会使的所选位置对应的概率集合的熵值变小，但增大了用户选择的K个位置 的随机性。