基于差分隐私的连续位置隐私保护机制

李洪涛，任晓宇，王洁，马建峰

（1.山西师范大学数学与计算机科学学院，山西 临汾 041099；2.西安电子科技大学计算机科学与技术学院，陕西 西安 710071）

1 引言

移动智能设备和定位技术的快速发展给移动用户带来了各种类型的基于位置的应用，为人们的生活带来诸多便捷。然而，由于移动用户在享受便捷服务的时候需要向基于位置的服务（LBS，location based service）提供他们的位置信息，使大量用户位置信息被不可信的第三方获取，可能使用户遭受严重的位置隐私泄露问题，危害用户的隐私安全。针对位置隐私保护技术，相关学者进行了大量研究。目前，多数位置隐私保护技术以k-匿名或l-多样性为基础，此类技术是将用户的真实位置泛化成一个区域，实现位置信息的隐私保护。其中，文献[1]基于用户的单一敏感属性设计了个性化k-匿名模型与KAUP（k-anonymity algorithm for personalized quasi-identifier attributes），提高了数据发布过程中的隐私保护程度。文献[2]提出一种基于l-多样性大数据隐私保护方法，采用NER（named entity recognition）方法将数据表示为结构化形式，进而对数据进行匿名化，实现对隐私数据的保护。抑制和扰乱技术也是近些年使用较多的保护方法。抑制技术的主要思想是不发布用户的敏感位置信息。文献[3]提出了一种基于信息熵的轨迹抑制隐私保护算法，通过函数计算抑制敏感位置点的最低代价，选择合理的抑制方式对原始数据集中包含敏感点的序列进行抑制。扰乱技术是将真实位置通过一定的变换生成假位置，达到保护真实位置的目的。文献[4]基于假位置隐私方法，提出了一种最大最小假位置选择（MMDS,maximum and minimum dummy selection）方案，使攻击者很难结合边信息过滤一些假位置，对位置信息进行隐私保护。以上几种隐私保护技术都有一定的局限性和缺点，攻击者可以通过长期的观察、挖掘和分析等方法获取用户的位置隐私信息[5-7]，因此这些技术无法抵抗相关攻击背景知识攻击。

Dwork 等[8]于2006 年提出了差分隐私保护模型，其因良好的隐私保护强度成为一种主流的技术，通过对原始查询结果添加随机噪声，使在数据集中添加或删除某一条数据对查询结果不产生影响，从而让攻击者很难通过多次查询反推某条真实数据，实现隐私保护。Chen 等[9]将差分隐私保护机制应用于位置数据保护，通过对位置数据加入Laplace 噪声，实现对位置数据的隐私保护。霍峥等[10]对自由空间和路网空间分别构造了噪声四分树和噪声R-树，通过添加Laplace 噪声保护位置数据，但没有考虑2 个连续时刻位置数据间的相互影响。吴云乘等[11]采用差分隐私位置保护模型，把已知生成位置时真实位置的后验概率与真实位置概率的比值作为满足差分隐私的条件提出了DPLRM（differential privacy location release mechanism）。Xiao 等[12]将地图转换为带权无向图，给位置区域分配隐私级别，在文献[11]的基础上，用马尔可夫链表示2 个连续位置的关系，提出基于差分隐私的位置保护方案。然而，现有的差分隐私解决方法多数没有考虑位置间的关联，即使对用户所有位置进行保护，攻击者也会根据地理拓扑、时序关系等方法获取用户隐私信息。

针对以上问题，本文提出了一种差分隐私位置保护机制（DPLPM,differential privacy location protect mechanism），该机制能有效保护位置隐私和最大化数据可用性。本文主要贡献如下。

1) 根据路网的拓扑关系，对敏感位置周围路段进行隐私级别划分，提出道路隐私级别（RPL,road privacy level）划分算法（本文简称为RPL 算法）。

2) 提出DPLPM，构建位置树结构并给位置信息分配隐私预算，为敏感路段添加符合差分隐私机制的Laplace 噪声，实现位置信息的隐私保护。

3) 理论分析和实验结果证明，所提机制能够较好地保护位置隐私和最大化数据可用性。

2 相关定义及其概念

2.1 差分隐私的相关定义

定义1邻近数据集。设数据集有相同的属性结构，两者仅相差一条记录，即，则称D和D' 为邻近数据集。

定义2差分隐私。给定邻近数据集D和D'，并已知某查询算法A，若算法A在数据集D和D'的任意输出结果O满足不等式(1)，则称算法A满足ε-差分隐私。

隐私预算ε用来控制算法A在2 个邻近数据集输出相同结果的概率比例，它表明隐私保护的程度，即ε越小，隐私保护程度越高，当ε=0 时，隐私保护程度达到最高。

定义3全局敏感度。设函数f:D→Rd，输入一个数据集，输出d维实数向量，对于任意临近数据集D和D'，称GFf为函数f的全局敏感度。

2.2 Laplace 机制

Laplace 机制通过向确切的查询结果中加入服从Laplace 分布的随机噪声来实现ε-差分隐私，主要面向数值型查询结果。记初始位置下尺度参数为b的Laplace 分布为Lap(b)，其概率密度函数为

定义4Laplace 机制。给定数据集D，设有函数f:D→ed，其敏感度为Δf，那么随机算法A(D)=f(D)=Y提供ε差分隐私，其中Y～Lap(Δf/ε)为随机噪声，服从尺度参数为 Δf/ε的Laplace 分布。

2.3 数据可用性

本文采用文献[12]的定义来测量本文数据可用性。假设t时刻发布位置是Ot，其真实位置是Zt，本文采用Ot和Zt之间的欧氏距离作为误差评价，即

特别地，对于长度为|W|的轨迹，本文同样以距离误差为基础衡量数据可用性，如式(5)所示。RMSE等于位置上处于敏感区域的真实位置与其发布位置之间的均方根误差和。RMSE 越大，表示数据可用性越差。

其中，∏Zt为指示函数，当Zt为敏感位置时，指示函数∏Zt的值等于1，否则该值等于0。

3 系统结构和威胁模型

3.1 系统结构

本文的系统结构如图1 所示，主要包括三部分：客户端、隐私保护处理器和位置服务处理器。客户端主要通过GPS 定位模块获取用户位置，并将位置存储至数据库中；隐私保护处理器分为数据划分模块、连续位置数据保护模块和数据库，数据划分模块将连续位置划分隐私级别，并将经过隐私级别划分的数据存储至数据库，连续位置数据保护模块对数据库中的位置提供差分隐私保护；位置服务处理器根据连续位置保护模块提出的查询请求，获得位置信息查询反馈，并将查询结果存储至数据库中。

图1 系统结构

针对用户位置隐私泄露问题，本文提出一种基于差分隐私的连续位置保护机制。在客户端，GPS定位模块获取用户位置数据，并将其上传至数据库，数据划分模块用RPL 算法对位置数据划分隐私级别；假设隐私保护处理器是可信任的第三方，连续位置数据保护模块从数据库中获取经过隐私级别划分的数据，通过DPLPM 添加基于差分隐私的Laplace 噪声，并生成位置集合；位置服务处理器向连续位置数据保护模块提出查询请求，连续位置数据保护模块将查询结果反馈至位置服务提供商；位置服务提供商在提供服务之后，将数据存储至数据库。

3.2 威胁模型

本文假设攻击者会不定时攻击用户的位置数据。很多位置服务提供商都有不同程度的安全保障，但当其服务器或数据库受到攻击时，用户的位置数据等隐私信息就可能被泄露。基于这个假设，本文提出的隐私威胁模型如图2 所示。智能手机、便携电脑和近场通信（NFC,near field communication）等便携设备获取用户位置数据，并将连续位置数据传送至服务器端进行处理，进而从位置服务提供商处获取服务。攻击者可以通过攻击服务器端或直接攻击位置服务提供商，获取用户隐私信息。

图2 隐私威胁模型

4 本文机制描述

本文常用符号如表1 所示。

表1 常用符号

4.1 RPL 算法

在数据划分模块，改进道路隐私级别划分算法，结合岔路口位置提出RPL 算法。图3(a)为真实区域的路网示意，○表示路口i，表示真实位置，表示用户当前所处位置，2 个路口间的虚线表示路口可直达。假设用户会选择最短路径到达目的位置。图3(b)统计了到达不同的目的位置最少需要经过路口的个数。其中，用户自定义初始敏感位置集合为SLinitial={sl1,sl2,…,slsl}，对应的隐私级别集合为PLinitial={pl1,pl2,…,plpl}。PLinitial中元素的取值范围为[0,1]，值越大表示敏感位置隐私级别越高。

图3 路网示意及到达不同的目的位置需要经过路口的个数

假设v为初始敏感位置，其隐私级别为v.pl，v的邻接位置集合为neighborSet，g是neighborSet 中的一个位置，v与g的距离为g.dis，则g的隐私级别为

从式(6)可知，g.dis 越大，g.pl 就越小，即距离敏感位置越远的点隐私级别越小。若g.dis=0，即g与初始敏感位置v重合，则取其本身的隐私级别和分配的隐私级别中较大者作为新的隐私级别；若g.dis≠0，即g为初始非敏感位置，则其隐私级别为g.pl。

已知用户初始敏感位置，根据图3(a)计算该位置的隐私级别，步骤如下。确定初始集合SLinitial中的位置v至路口i的路段上是否存在用户的第二个敏感位置，若不存在，则计算位置v与i之间的距离dis(v,i)=R，当R<η时，输出位置v与i的路段v→i；当R≥η时，输出距离为η的路段。若位置v至路口i的路段上存在用户的第二个敏感位置g，则先根据式(6)计算位置g的隐私级别，并与g的初始隐私级别进行比较，取其中较大者作为位置g的最终隐私级别，此时，输出的敏感路段为两段，即v至g的路段v→g，以及g至路口i的路段g→i。用户道路隐私级别划分算法如算法1 所示。

算法1RPL 算法

输入路网G=，路网的区域划分M={SLinitial,NSLinitial}，初始敏感位置集合SLinitial，每个敏感位置对应的隐私级别集合PLinitial，距离阈值η

输出敏感路段及其隐私级别

如果在初始敏感位置v到路口的路段上出现用户自定义的另一个一级初始隐私位置，则直接输出位置v到路口的全部路段。

4.2 差分隐私位置保护机制

在位置数据保护模块，采用位置树结构，基于差分隐私保护模型提出DPLPM。本文构建位置树反映路网实际情况。v表示初始敏感位置，i表示路口。路网结构转换为位置树如图4 所示。

1) 如图4(a)所示，敏感位置周围有2 条路通往路口i，转换为树结构后，包含一个根节点、2 个叶子节点。

2) 如图4(b)所示，敏感位置周围有3 条路通往路口i，转换为树结构后，包含一个根节点、3 个叶子节点。

3) 如图4(c)所示，在敏感位置周围的路段上，有一个敏感位置g，转换为树结构后，深度为2，包含一个根节点、一个子节点、2 个叶子节点。

图4 路网结构转换为位置树

依次类推，将路网转换为位置树。

根据差分隐私定义可知，隐私预算越小，对数据的隐私保护程度越大，以位置树的高度为基础，对隐私预算进行分配。

其中，q为2 个敏感位置间隐私级别比值，即其应分配隐私预算的比值。位置v为隐私级别最高的敏感位置，相应地，v.pl 最大，即g.pl

下面，根据路网示意构建位置树结构，根据树的高度分配隐私预算，添加Laplace 噪声，实现对用户位置数据的保护。首先，以位置v为根节点构建位置树，若构建树的高度为1，则将隐私预算ε平均分配至用户的t个敏感位置；若树的高度大于1，则按照式(7)分配隐私预算，并根据隐私预算为每个位置加入符合差分隐私机制的Laplace 噪声Laplace Noisy(εt)。差分隐私位置保护机制如算法2所示。

算法2DPLPM

输入路网G=，隐私预算ε={ε1,ε2,…,εh}，噪声树的高度h，噪声值N={N1,N2,…,Nh}，初始敏感位置v，真实位置Zt，敏感路段上敏感位置数t

输出位置集合W

5 差分隐私证明和算法分析

5.1 差分隐私证明

给定隐私预算ε，本节证明RPL 算法和DPLPM均满足ε-差分隐私。

RPL 算法不能以差分隐私机制中数据集的概念来定义，因为对于位置和位置隐私来说，用户的每个位置都是需要被保护的，本文假设已知某时刻的发布位置Ot，根据已发布的位置判断真实位置的后验概率为Pr(Zt|Ot)，即

由差分隐私定义可知，RPL 算法满足ε-差分隐私。

在DPLPM 中，加入Laplace 噪声，即符合ε-差分隐私，证明过程如下。

证明已知Laplace 机制的概率密度函数为，设px表示Al(x,f,ε)的概率密度函数，py表示Al(y,f,ε)的概率密度函数，则对于某个输出值Z，有

可知，RPL 算法和DPLPM 均满足ε-差分隐私。证毕。

5.2 算法分析

1) 时间复杂度。假设连续位置数据中共有n个位置，在RPL 算法中，最耗时的部分是遍历所有位置，其时间复杂度为O(n)=n；在DPLPM 中，最耗时的部分是将隐私预算分配给每层树结构，再将每一层的隐私预算分配给敏感路段中的每一个位置，其时间复杂度为O(n)=ht。总体来说，本文所提算法计算消耗较小。

2) 隐私性。根据DPLPM，t时刻发布位置Ot使当前位置Zt满足ε-差分隐私，即轨迹W中，每一个位置都满足ε-差分隐私，可知轨迹W满足ε-差分隐私。

3) 数据安全性。本文经过数据划分模块和连续位置数据保护模块的处理后，将数据上传至位置服务提供商，位置服务提供商不能获得用户原始数据，所以攻击者不能通过位置服务提供商对用户进行攻击；本文采用差分隐私保护模型抵御背景知识攻击，攻击者无法根据用户的行为模式和地理拓扑关系推断出用户的真实位置，并根据用户的隐私级别分配不同的隐私预算，实现对用户位置数据的保护。

4) 数据可用性。本文通过式(5)对数据可用性进行分析。由式(5)可知，影响数据可用性主要有以下3 个因素。①轨迹长度。轨迹长度越长，需要考虑的时刻越多，使发布位置与真实位置之间的距离越大，即数据可用性越差。②敏感位置Zt与发布位置Ot的欧氏距离，距离越大，RMSE 越大，数据可用性越差。③指示函数∏Zt的值，即判断位置Zt是否为敏感位置，若为敏感位置，则∏Zt=1，否则，∏Zt=0，数据可用性最高。本文所提RPL 算法使敏感轨迹长度降到最低，同时由概率比值可得真实位置与发布位置之间的距离为eε，通过控制隐私预算减少两者的距离，由此可知，本文在数据可用性方面是最优的。

6 实验与分析

6.1 实验设置

本节测试本文所提DPLPM 的性能。实验使用Python 实现，在3.60 GHz CPU、8 GB RAM 的Windows 10 平台上运行，实验数据集为真实位置数据集Geolife[13]和Gowalla[14]。将DPLPM 和FPT（final private trajectory）算法[15]、基于频繁驻留点的加噪（NFRP,noisy of frequent resident points）算法[16]进行比较，从隐私保护程度、算法运行时间和数据可用性3 个方面判断本文算法的优劣性。

6.2 实验结果与分析

6.2.1 隐私保护程度

本节实验分析了本文所提DPLPM 的隐私保护程度，通过用户自定义和式(6)计算隐私级别pl、由仿真实验结果选出距离阈值η、初始敏感区域SLinitial大小k和隐私预算ε，比较本文算法和FPT算法、NFRP 算法在Geolife 数据集和Gowalla 数据集上的隐私保护程度。

k=4，pl=0.25 时，距离阈值η对隐私保护程度的影响如图5 所示。

图5 η对3 种算法隐私保护程度的影响

从图5 可知，3 种算法的隐私保护程度都随着η的增大而减小。根据式(5)可知，随着输出路段距离的不断增大，位置的隐私级别不断下降，即隐私保护程度减小。

pl=0.25，η=20 时，初始敏感区域SLinitial大小k对隐私保护程度的影响如图6 所示。

图6 k对3 种算法隐私保护程度的影响

图6 可知，3 种算法的隐私保护程度都随着k的增大而减小。这是因为敏感位置越多，则所需的隐私预算越多，即隐私保护程度越小。

k=4，η=20 时，隐私级别pl 对隐私保护程度的影响如图7 所示。从图7 可知，随着pl 的增加，3 种算法隐私保护程度都在增加。这是因为隐私级别pl 越大，为其分配的隐私预算越小，即隐私保护程度要越大。

图7 pl 对3 种算法隐私保护程度的影响

k=4，η=20，pl=0.25 时，隐私预算ε对隐私保护程度的影响如图8 所示。从图8 可知，随着ε的增加，3 种算法隐私保护程度都在减少，由差分隐私定义可得，隐私预算越大，隐私保护程度越小。

此外，从图5～图8 可以看出，在不同参数下，本文所提算法的隐私保护程度都优于其他2 种算法。

图8 ε对3 种算法隐私保护程度的影响

6.2.2 数据可用性

本文用RMSE 衡量数据可用性。本节实验分别在Geolife 数据集和Gowalla 数据集上运行，对比了本文所提DPLPM、FPT 算法和NFRP 算法的数据可用性。其中，FPT 算法通过构建噪声前缀树实现对位置数据的保护，NFRP 算法根据统计后的流量图中边的流量值添加噪声。

k=4，pl=0.25 时，距离阈值η对RMSE 的影响如图9 所示。

图9 η对3 种算法RMSE 的影响

从图9 可知，3 种算法的RMSE 都随着η的增大而增大。NFRP 算法的可用性最差，因为该算法只为某一位置的经纬度添加噪声；FPT 算法的位置数据可用性相对较好，但FTP 算法较多地对空节点添加噪声；DPLPM 考虑了位置连续性之间的影响，数据可用性是最好。

pl=0.25，η=20 时，初始敏感区域SLinitial大小k对DPLPM、FPT 算法和NFRP 算法RMSE 的影响如图10 所示。

图10 k对3 种算法RMSE 的影响

从图10 可知，3 种算法的RMSE 都随着k的增大而增大。这是因为位置个数的增大会导致隐私预算增多，添加的噪声也增加，即数据可用性变差。NFRP 算法的可用性最差，DPLPM 可用性最好，而FPT 算法介于二者之间。

k=4，η=20 时，隐私级别pl 对DPLPM、FTP算法和NFRP 算法RMSE 的影响如图11 所示。

从图11 可知，3 种算法的RMSE 都随着pl 的增大而增大。这是因为随着隐私级别的增大需要添加的噪声增加，数据可用性变差。DPLPM 的可用性最好，FPT 算法次之，NFRP 算法最差。

图11 pl 对3 种算法RMSE 的影响

6.2.3 算法运行时间

本节实验在Geolife数据集和Gowalla数据集上运行DPLPM、FPT 算法和NFRP 算法，对比3 种算法的运行时间。

k=4，pl=0.25 时，距离阈值η对DPLPM、FPT算法和NFRP 算法运行时间的影响如图12 所示。

从图12 可知，随着η的增加，3 种算法的运行时间都随之增加。因为DPLPM 只需要提供加噪，所以DPLPM 运行时间是最少的。

图12 η对3 种算法运行时间的影响

pl=0.25，η=20 时，初始敏感区域SLinitial大小k对DPLPM、FPT 算法和NFRP 算法运行时间的影响如图13 所示。

图13 k对3 种算法运行时间的影响

从图13 可知，随着k的增加3 种算法的运行时间都随之增加。FTP 算法在2 个数据集上的运行时间都是最长的，而NFRP 算法次之，DPLPM 的运行时间是最短的。

k=4，η=20 时，隐私级别pl 对DPLPM、FTP算法和NFRP 算法运行时间的影响如图14 所示。

从图14 可知，随着pl 的增加，3 种算法的运行时间都在增加。FPT 算法在2 个数据集上运行时间都最长，NFRP 算法次之，DPLPM 的运行时间最短。

图14 pl 对3 种算法运行时间的影响

6.3 相关工作比较

本文所提DPLPM 与其他方法的比较如表2 所示。文献[17]提出一种基于隐私拆分的轨迹隐私保护方法，建立单点位置的发布对查询轨迹的前向和后向隐私风险评估机制，通过拆分查询轨迹，消除轨迹中位置间的相关性，但没有控制隐私预算，同时使算法开销增大。文献[12]提出一种差分隐私保护方法，根据时间相关性，使用马尔可夫链预测前一个位置对后一个位置的影响，考虑了路网中的位置连续性，但没有对隐私预算进行合理分配。文献[18]将不规则树引入差分隐私方法中，减少连续查询时噪声叠加带来的查询精度下降问题，但没有考虑位置间的相关性。文献[19]提出AC-TFIDF（adaptive clustering based TFIDF）算法，根据重要位置点在不同时刻的分布状况，选择聚类中心代替原始位置，生成发布位置，但没有考虑路网实际情况。

表2 相关工作比较

7 结束语

本文研究了连续位置隐私保护问题，基于差分隐私机制，提出了一种连续位置隐私保护机制。在位置数据划分模块提出了隐私级别划分算法，根据路网关系计算其相邻位置的隐私级别，使攻击者无法推断出用户隐私位置；在位置数据保护模块提出差分隐私位置保护机制DPLPM，根据道路关系映射位置树，根据树的高度为敏感路段分配隐私预算，并添加符合差分隐私机制的Laplace 噪声，保护了用户的位置信息。理论分析证明，本文算法均满足ε-差分隐私。仿真实验证明，本文所提DPLPM 有较好的隐私保护程度和较高的数据可用性。