一种基于停顿和映射的隐私轨迹混淆策略

唐 禹 吴正华

(电子科技大学信息与软件工程学院 成都 611731)

近年来，基于位置的服务(LBS)变得越来越普遍，LBS提供商基于用户的位置提供例如定位、导航、路线规划、兴趣点(POI)搜索、定制化广告等服务.其可以通过用户移动设备的GPS定位、蜂窝移动网络信息、WiFi信息等来获取用户定位.一方面，丰富的LBS便利了用户的生活，但是另一方面，LBS也窃取了用户的隐私，Fechner的报告[1]显示攻击者可能会因为牟利的目的进行一些骚扰行为.根据Busic和Filjar的调查[2]，大多数商业LBS要求我们每隔几分钟更新一次定位.当用户连续使用LBS时情况会愈发严重，如果用户的轨迹被恶意使用，通过数据挖掘[3-5]可以获取用户的更多隐私，包括家庭住址、爱好、生活情况、健康状况、亲密关系等.因此轨迹信息的保护得到了广泛的应用研究，受到国内外学者的关注.

为了保护用户的位置隐私，目前国内外已有很多研究.Kato等人[6]认为，一个能够保证用户位置隐私的系统应该满足以下2个条件：1)它应该是一个封闭的系统，即能够在用户的移动设备上部署，并且不会向外部泄露用户的位置隐私；2)它不应破坏用户或LBS提供商的利益.第2个要求对于使整个生态系统受益至关重要.否则，没有用户或LBS会使用该系统来保护隐私.但是，前人的研究基本上是基于K-匿名算法，在真实使用中，使用者往往不具备专业知识背景，他们无法为每个LBS构建请求，通常是LBS应用直接向移动设备请求位置信息，这种请求的结果是固定的，即某一个经纬度标识的点，也就无法通过返回给应用多个定位数据，以实现K-匿名算法.

应用在LBS中的位置隐私保护系统架构主要有3类[7]：集中式模型、分布式模型和独立式模型.其中集中式模型需要有可信的第三方服务器，分布式模型需要用户进行分布式组网，都需要外部服务或设备的帮助，而独立式模型的隐私保护皆由用户设备完成，不干涉外部网络与服务，也与本文的研究方向最为贴切.

在独立式模型中的轨迹隐私保护算法主要分为3种：K-匿名轨迹算法、轨迹抑制算法和虚拟轨迹算法.

轨迹抑制算法是选择性地抑制敏感位置的发布[14]，轨迹抑制法虽然实现简单，但是却容易导致数据丢失，降低数据可用性.Weng等人[15]提出一种基于扰动的轨迹数据隐藏发布方法，找到出现频率低的位置节点来替换出现频率高或有隐私泄露风险的节点.

虚拟轨迹算法是通过对真实轨迹的处理，得到1条虚拟轨迹，此轨迹在LBS等位置服务和用户轨迹隐私中取得折中.Duckham等人[16]提出了一种通过混淆的方式在LBS与位置隐私中取得一定平衡的框架.Ardagna提出了3种混淆策略[17]：1)通过扩大其半径来降低定位区域精准度；2)通过移动其中心来降低定位区域精准度；3)通过减小半径来降低定位区域精准度.

本文致力于在无第三方可信服务器的情况下独立保护用户的位置隐私，同时为使用者提供可用的LBS.本文的方法着重于维护可用LBS和用户位置隐私之间的平衡，通过一定的混淆策略降低用户的位置信息质量，以达到保护用户位置隐私的目的.同时考虑到真实轨迹中存在的停顿现象及工作、住宅等地的固定点存在，在普通混淆策略的基础上增加了停顿处理和固定点映射策略，使得本文的方法在拟真方面更加优秀.在降低定位精度方面，本文创新性地提出了通过时延来获取混淆区域中心，在降低定位精准度的同时保证了轨迹的拟真性.

1 本文的隐私保护模型

1.1 条件假设

1.2 度量标准

为了明确在使用混淆算法前后用户获得的LBS差异，本文提出通过命中率AR来度量模型对于用户获取LBS的影响.命中率AR表示为

(1)

其中，Lr表示真实定位，Lf表示此真实定位对应的虚拟定位，POI(L)表示在定位L处所获得的LBS兴趣点集合，故AR可以用通过虚假轨迹获取到的兴趣点集合中命中真实定位获取到的兴趣点集合的数量与真实定位获取到的兴趣点数量的比值来表示.

为表示所生成轨迹的真实性，本文提出通过判正率CR来度量生成的假轨迹被判断为真实轨迹的概率.即所有生成轨迹中，被定性判断为真实轨迹的轨迹条数占生成的所有轨迹条数的比例.

1.3 轨迹生成策略

本文提出的虚拟轨迹生成策略通过延迟使用，暂停处理和固定点映射的方法达到保护用户轨迹隐私的目的.当用户使用提供LBS服务的应用时，应用将会通过系统API调用获取当前的定位，本策略在这一环节通过修改系统API返回的数据，以达到返回虚假定位、保护用户隐私的目的，并使得此算法具有普适性，可以为无相关背景知识的用户所使用.

1.4 延迟使用

常规的虚拟轨迹生成策略通过当前位置生成虚拟节点“哑元”(dummies)，由哑元生成半径r控制定位精准度，r越大则定位精准度越低，用户隐私保护程度越高.然而一方面单一的增减r会使得轨迹无序性随r增大而增大，即生成的虚假轨迹更容易被识别；另一方面此策略在某些情况下极易暴露用户真实位置，如高速路出口处等位置，此时即使哑元并不在出口处，但是攻击者也可以轻易结合时间信息推断被攻击者的位置.故本文的生成策略考虑到Ardagna等人[17]的研究，通过移动区域中心的方法，降低定位精准度的同时更大程度地保护用户位置隐私.为了使虚假轨迹更加拟真(如图1所示)，生成虚假定位的区域中心选择一定延迟时间D之前的真实定位.

图1 控制生成定位精准度的方式

1.5 停顿处理

用户并非一直在行走，如果用户在某个地方停下来如观看风景或短暂休息，此时在以往的匿名轨迹生成算法中将会继续在当前节点周围生成哑元，然而停留时间越长，生成的哑越有可能暴露真实定位所在.如图2所示，在同一真实定位附近，分别生成5，20，100个虚拟定位，真实定位越来越接近所有定位的中心.故本策略拥有停顿处理功能，当使用者停顿后，其相应的哑元也会停顿，避免隐私泄露的风险.

图2 生成不同个数虚假定位时真实定位所在位置

1.6 固定映射

在前人的研究中很少考虑到固定的映射策略，但是固定点映射在反恶意检测中有很大的作用，如果从攻击者的角度出发，大部分使用者都会有常驻点，如家或工作地点等，可以通过判断一段时间内用户有没有常驻点来表明此轨迹是否是虚假轨迹，所以常驻点映射是十分必要的，例如当用户回到家之后，相应的哑元也会最终到达一个固定点停留，防止攻击者的虚假轨迹识别.而从用户的角度出发，一段路径中的某些点可能是必须暴露的，此时固定点映射也可以暴露出用户指定的点，达到定制化的效果.

1.7 算法思路

首先得到真实轨迹集合RT，由于用户设备本身存在定位误差，所以需要先对真实轨迹进行预处理，把误差范围内的定位处理为同一定位，解决用户停顿后因为定位误差带来的前后定位不一致问题.同时为了方便后续依据时延t获取混淆区域半径，在前t个时间内重复第1个定位节点.

随后进行哑元生成，根据处理好的真实轨迹集合中的每一个定位，在混淆半径r内取出1个满足可达性的点.即前一个哑元能够在单位时间内到达此哑元.在此过程中如有遇到在固定点映射集合M中的点，则哑元不必自己生成，而是从M中取得.

最后将所有哑元合并就得到了用户的虚假轨迹，使用者可以根据需求从中提取数据.

1.8 轨迹预处理

为了使延迟使用和暂停处理的算法策略更好地发挥作用，需要对用户真实轨迹RT进行处理，将相似定位处理为同一定位，解决移动设备本身定位精度问题带来的误差，同时依据时延时间t在真实轨迹开始处不断填充相同的起始节点.

算法1.真实轨迹预处理算法.

步骤1.将PRT置为空集；

步骤2.重复t次；

步骤4.结束重复；

步骤8.结束遍历；

步骤9.返回PRT.

1.9 生成虚假轨迹

在之前经过预处理的轨迹PRT的基础上，通过混淆策略和固定点映射策略生成虚假轨迹FT.

算法2.虚假轨迹生成算法.

步骤1.将FT置为空集；/*生成与PRT中定位数对应的FT*/

步骤7.结束遍历；

步骤8.返回FT.

2 实验与数据分析

本文使用微软亚洲研究院收集的轨迹数据集Geolife[18-20]，使用了其182个用户在2007-04—2012-08期间记录的24 876 978个点表示的GPS轨迹的数据，本实验代码由Python3.8.3编写，实验环境为macOS 10.15.7操作系统.实验中的POI(L)即定位L处的周围兴趣点通过调用高德地图开放平台接口获取，平均距离s指混淆区域中心与原定位的平均欧氏距离.

2.1 时延t对命中率AR的影响

由于不同用户对于POI(兴趣点)搜索的需求范围不同，我们使用了3种搜索范围，分别是300 m，1 000 m和3 000 m，即在这3种POI搜索范围中探究时延t与命中率AR的关系：命中率1表示在搜索附近300 m时POI的命中率；命中率2表示在搜索附近1 000 m时POI的命中率；命中率3表示在搜索附近3 000 m时POI的命中率.实验表明，当用户对POI搜索距离较大时，延迟对命中率影响较小，在3 000 m时POI搜索范围的情况下，即使时延300 s也可以达到超过94%的命中率.

2.2 混淆区域半径r对命中率AR的影响

在POI查询距离分别为300 m时，时延对命中率的影响如图4所示，当POI的查询范围为3 000 m时，时延对命中率的影响如图5所示，此时时延对命中率的影响非常小，同时从图3可以看出，时延越长，时延后的节点与原节点欧氏距离越远，即混淆效果越好，但当POI范围较近时，时延对命中率的影响较大.

图3 时延t对命中率的影响

图4 POI查询范围为300 m时混淆半径对命中率的影响

图5 POI查询范围为3 000 m时混淆半径对命中率的影响

2.3 与以往方案对比

此次实验位置采样设置为每5秒1次，混淆半径为10 m，分别对比了随机法、轨迹旋转法和本文的方法所生成轨迹的判正率CR和命中率方差ARV.

在以往关于虚拟轨迹算法的研究中，并没有对轨迹的拟真性提出量化标准，本文实验通过判正率这一判断指标对各方法进行定性比较.

由图6可知，随着平均距离的增大，通过随机法生成的轨迹迅速失去真实性，极易被判断为假轨迹，而本文的策略与轨迹旋转法生成的轨迹则基本不受平均距离的影响，具有较高的真实性.

图6 不同方法的判正率

如图7所示，本文的策略在POI命中率的方差上与随机法是一个量级，远低于轨迹旋转法，保证了LBS的稳定可用.

图7 不同方法的命中率方差

3 结束语

目前基于LBS的位置隐私保护主要集中在K-匿名算法等模型上，然而此类模型要求使用者具有相应的背景知识，不适宜作为普适的解决方案，对于没有背景知识的普通使用者来说，在位置隐私保护和LBS中取折中的混淆算法无疑是更佳的选择.本文在以往研究的基础上，采用了延时处理、停顿处理、固定点映射等策略，提出了一种更优的保护使用者位置隐私的混淆策略.相比于以往的混淆策略，通过随机法生成的轨迹随着混淆中心的位移长度增加，轨迹呈现混沌的趋势，与真实轨迹不符，通过轨迹旋转法生成的虚假轨迹虽然具有较高的真实性，但是在POI命中率上容易出现极端情况，本文的策略则表现出了更好的拟真性与稳定性.

下一步的研究工作主要包含：

1)本文所采用的数据集主要分布在北京市，建筑密集，POI集中，而对于人口稀疏、POI较少的地区的处理有待进一步研究；

2)本文主要关注的步行轨迹，针对骑行、公共交通或驾车等速度更快的情况缺乏探讨，基于时延等策略的混淆是否有效还需要验证，适用于这些情况的更好的混淆策略也还需进一步研究.