基于噪声匿名组的LBS位置隐私保护算法

高喜龙，袁 健，许能闯

(上海理工大学 光电信息与计算机工程学院，上海 200093)

0 引言

移动应用技术发展给人们带来了众多便利，基于位置的服务(location based service,LBS)[1]日益受到欢迎。但由于请求LBS时，用户位置等敏感信息需要向服务商提交，若被不法分子获取，则可利用成熟的数据处理技术获得用户住址、兴趣爱好等信息，对LBS用户造成不可估计的损失[2]。因此，最大限度保护LBS用户个人信息一直是隐私保护领域的重点研究内容。

为解决LBS的位置隐私问题，产生了以k-匿名[3]为代表的传统算法模型，然而大量研究证明该类算法无法有效估计攻击者所拥有的背景知识，因而无法设计出适用于各种场景下的位置隐私保护模型[1]。较新的差分隐私保护[4]无视背景知识，很好地弥补了K匿名在该方向上的缺陷。然而差分隐私在该领域应用较少。文献[5]以差分隐私为基础提出的Geo-Indistinguishability算法，是差分隐私在该领域较新的尝试 ，但其存在对隐私预算[4]过度依赖的问题。针对现有算法无法有效抵抗背景知识攻击和过度依赖隐私预算现状，本文提出基于差分隐私的匿名组LBS位置隐私保护算法MBG(MobiHide Based on Geo-Indistinguishability,MBG)。该算法在形成匿名组时，首先经过差分隐私的噪声过滤，只有满足差分隐私的用户才能进入匿名组提交，从而提高了用户隐私保护效果。

1 相关工作

当前LBS位置隐私保护策略分为基于政策法的位置隐私保护技术、基于加密法的LBS隐私保护技术和基于扭曲法的LBS位置隐私保护技术。

基于政策法的LBS位置隐私保护技术，通过制定一些常用的隐私管理规则和可信任的隐私协定，约束服务提供商公平、安全地使用用户LBS查询中的位置信息，如IETF的GeoPriv[6]和W3C的P3P[7]。基于加密法的LBS位置隐私保护技术，通过使用加密技术使用户查询信息中的位置信息对LBS服务器不可见，从而达到位置隐私保护目的。如基于隐私信息检索的LBS隐私保护技术[8]，其实现方法依赖于特定的用户数据以及复杂的算法及硬件支持；全同态加密技术[9]可在不揭密用户查询的前提下返回正确的查询结果，但其效率很低。因而如何平衡隐私保护与隐私保护实现所需代价间的关系，成为该类算法需要考虑的重点。

基于扭曲法的LBS位置隐私保护技术指在LBS查询暴露给LBS服务器之前，事先对查询中的时空信息进行适当的修改或扭曲，使LBS服务器无法获得精确的位置信息。这类技术的实现往往依赖于攻击者的先验知识，易遭受具有数据分布特征等背景知识的攻击。差分隐私[4]对背景知识不够敏感，可设计出能够抵御具有任意背景知识攻击的隐私保护框架[5,10]。基于扭曲法的LBS位置隐私保护技术与差分隐私概念相结合成为研究热点。

文献[11]提出的MobiHide模型以K匿名为基础，同时为了加快请求服务时的处理速度，参照一种基于希尔伯特曲线[12]的用户划分空间[13]，使用户自组织形成一个基于Chord[14]的自组织网络，其匿名组的形成仍参照传统K匿名思想。为提高隐私保护效果，引入差分隐私概念，在形成匿名组时由用户指定的距离参数过滤用户组，仅允许符合要求的用户进入最终的匿名查询组，从而提升用户隐私保护效果。

2 MBG算法

为修正传统以K匿名为基础的LBS位置隐私保护算法的不足，提出基于差分隐私的用户位置特性[15]的MBG算法。该算法以传统的K匿名算法为核心，在形成匿名组时先由用户指定的隐私保护参数ξ过滤，ξ为差分隐私相关的位置隐私参数。MBG算法流程如图1所示。

图1 MBG算法流程

(1)在当前LBS服务器负责区域内，按照Hibert-Curve将当前区域内所有用户排序形成Hibert空间，所有用户获得唯一标识符。

(2)根据用户标识符形成基于Chord的用户自组织网络。

(3)LBS用户发起LBS请求，若查询用户为新用户，返回步骤(1)；否则，按照K匿名要求形成匿名组。

(4)根据用户指定的距离参数ξ过滤匿名组内用户，不符合要求的用户将被排除，直至达到K个用户形成匿名组，提交以获取服务。

用户指定的距离参数ξ应满足Geo-Indistinguishability：

(1)

其中，S为攻击者拥有的背景知识，x为真实用户，x′为距真实用户距离不超过ξ的匿名组用户。公式(1)表达的实际内容为：假定攻击者可获得ξ范围外的当前用户的所有背景知识，其获知背景知识前后推断出用户真实身份的概率相差值应在与ξ相关的参数因子范围内。

3 实验分析

从服务质量与隐私保护度对比MobiHide与MBG对用户位置隐私的保护效果。实验数据来源于旧金山港湾区，由基于网络的移动对象生成器构成[9]。本实验单机环境为Inter(R) Core(TM) i7 CPU 3.4GHz，8GB内存，Window10操作系统。

3.1 实验评价指标

3.1.1 服务质量

隐私保护服务质量由响应时间、查询结果的准确性衡量。在相同隐私保护度下，移动对象获得的服务质量越高,说明隐私保护技术越好。

(1)响应时间。响应时间指从用户发出LBS请求至用户获取服务的时间，任意选取n位用户，记用户Ui的响应时间为ti，对任意算法模型的平均响应时间MT(Mean Time,简称MT)，应有：

(2)

(2)查询结果的准确性。用fi表示用户的查询结果，若符合预期标准，即返回的查询结果与用户所期望的兴趣点一致，记fi=true；否则fi=false；以resulti作为当前用户查询结果的统计量，以CROUQ(Coincident Result Of User Query，简称CROUQ)表示满足用户查询的兴趣点结果，即：

(3)

以APOUQ(Actual Point of User Query,简称APOUQ)表示实际用户请求的兴趣点，即实际查询用户数目n：

APOUQ=n

(4)

以符合率CP(Coincident Probability，简称CP)描述每种算法的最终结果，则：

(5)

3.1.2 隐私保护度

隐私保护度反应LBS隐私保护技术披露隐私多寡的程度，披露风险越小，隐私保护度越高。披露风险与隐私保护算法和攻击者掌握的背景知识相关。假设攻击者可以获得除查询用户外的所有信息，以Ui表示用户查询结束后攻击者是否推断为实际查询用户，若攻击者推断出用户真实身份，则Ui=true；否则Ui=false。以Ti作为查询结果统计量，设每组样本实际查询用户数为n，对于N组样本，披露风险DR(Disclosure Risk)计算如下：

(6)

3.2 实验结果分析

表1为3种隐私保护模型的服务质量与隐私保护效果所使用的系统参数：MobiHide[19]是基于k-匿名的位置隐私保护算法的一种，对于地理位置信息上的隐私保护范围没有明显界限。MBG算法参照K匿名思想与由差分隐私扩展而来的Geo-indistinguishability,故额外制定隐私保护距离ξ。此外，为了保证算法的适用性，分别指定k=21,22,…,30，对不同K值的实验结果采用均值比较。

表1 算法模型实验对比使用参数

3.2.1 服务质量

(1)响应时间。实验采用系统参数如表1所示，在不同K值下取10 000位用户的LBS请求时间统计，按照公式(2)计算两种位置隐私保护模型的MT，如图2所示。

图2 平均服务响应时间对比

(2)查询结果的准确性。根据公式(5)计算两种模型的LBS用户查询结果，准确性如图3所示。

图3 查询结果与用户兴趣点吻合程度

图2和图3结果表明，在不同K值下用户的服务质量，新提出的MBG算法与原有的MobiHide算法相比，基本满足用户的服务需求。

3.2.2 隐私保护度

图4为根据公式(6)，按照表1给定的实验参数，MobiHide与MBG对用户发起LBS查询时用户隐私的披露统计情况。

图4 隐私披露情况统计

从图4可以看出，在不同K值下，引入了差分隐私的基于MobiHide的MBG算法对于用户隐私的披露风险，明显小于使用传统K匿名思想的匿名组方法。

综合以上结果，MBG算法在LBS位置隐私保护方面，在保证用户服务质量的前提下，相较于传统的K匿名方法，对用户的位置隐私保护程度明显提升。

4 结语

本文立足于具有明显定位优势的K匿名隐私保护系统，结合差分隐私的相关做法，提出了以克服K匿名无法有效估计攻击者背景知识缺陷为目的的MBG算法模型。该算法吸取了差分隐私无视攻击者背景知识的特点，通过设置距离参数以过滤匿名组中不符合该特性的用户，从而提升隐私保护效果。MBG算法是结合差分隐私在LBS位置隐私保护领域较新的尝试，但差分隐私在该领域的应用较少，更为完善有效的隐私保护模型尚待研究。