位置轨迹相关性差分隐私保护技术研究与进展*

秦呈旖, 吴 磊,2,3, 魏晓超,3, 王 皓,3

1.山东师范大学 信息科学与工程学院, 济南250307

2.河南省网络密码技术重点实验室, 郑州450001

3.山东省分布式计算机软件新技术重点实验室, 济南250307

1 引言

在大数据时代, 随着移动终端设备和GPS 定位技术的广泛应用与发展, 基于位置的服务(location based service, LBS) 比如兴趣点查询、交通路径规划导航、社交网络位置共享等成为日常生活中不可或缺的一部分, 给我们带来诸多便利.基于地理位置的网络空间以时间序列、行为轨迹以及地理上不可知信息标记相结合的方式, 帮助用户同外部世界建立更广泛、更紧密的连接, 增强网络空间同地理位置之间的关联性.同时, 位置服务提供商(location based service provider, LBSP) 也获取和收集了海量用户的位置[1]、轨迹信息以及其他相关时空信息, 以提高位置服务的精度和效率.然而, 由于其自身特性, 人们在享受这些便捷的同时也面临着很多问题.其中最突出的就是隐私泄露问题.LBSP 是诚实且好奇的, 其可能是一个潜在的敌手.为了进一步获取更有价值的用户个人信息和商业信息以谋求利益, LBSP 会挖掘一些关于用户的敏感信息、同一用户在相似时刻和不同时刻的轨迹相关性, 以及多用户之间的轨迹相关性.因此, 如何利用隐私保护技术对轨迹相关性进行保护成为一个亟待解决的难题.

基于时空的两条相关行动轨迹可以体现或泄露单用户的个人信息或两个用户之间的某些社会关系信息[2], 可以用来对用户信息进行链接预测和评级预测.虽然用户多轨迹的相关性可以对LBS 服务质量进行提升, 但也导致了严重的隐私问题.生活中存在大量的隐私泄露风险案例, 例如, 2016 年Uber 的隐私风波, LBSP 在乘客不使用App 时后台持续搜索并记录位置信息, 有员工利用权限追踪歌手碧昂丝等名人的乘车信息, 并在乘客不知情的情况下搜集其个人信息.2017 年, GPS 追踪公司Strava 基于用户健身追踪器(GPS) 位置信息绘制出一张全球范围内用户运动轨迹热照片, 一位澳大利亚留学生从照片中发现这张轨迹图曝光了美军官兵在此活动的一些痕迹, 同时也找到了一些敏感的军事基地轮廓.2020 年成都新冠确诊女孩因其活动轨迹暴露, 这位女孩的个人信息被搜索出来发布到了网上, 并且遭到了网络暴力.一个典型的示例如图1 所示, 一个大型的追踪新冠阳性患者应用程序, 假设敌手事先知道用户A 和用户B 的背景, 其中用户A 是阳性确认病例, 用户B 是其某个密切接触者, 潜在敌手根据应用程序发布的轨迹可知他们经常在同一时间出现在同一地点, 敌手可推断用户A 和用户B 是关系密切的, 可以根据相关的先验知识来进一步确认他们的社会关系.综上所述, 在基于位置的服务中不仅要保护用户的基本位置信息, 还必须防止或限制用户位置轨迹相关性的泄露, 以保护用户之间的社会关系隐私, 从而达到完备的LBS 隐私保护.

图1 通过位置轨迹相互性进行社会关系推理的示例Figure 1 Example of social relationship reasoning through location trajectory correlation

目前, 泛化(generalization)[3,4]、混合区(mix zones)[5]、抑制(inhibition) 以及扰乱(disturbance)是四类最常用的位置轨迹隐私保护方式.泛化和混合区均可用来保护用户的轨迹隐私安全, 但其效果并不理想; 抑制与扰乱虽然能很好地保护用户的轨迹数据隐私, 但是存在着一定的安全隐患.泛化是把轨迹中各时刻位置泛化为区域; 混合区更适用于车联网, 利用路口转换假名保护车辆信息; 抑制是依据用户实际位置所处敏感区域大小抑制分发位置; 扰乱是给各时刻位置加上噪声产生干扰位置分发.但是, 如果需保护的位置在敏感区域内, 在使用以上方法进行轨迹保护后, 敌手仍然可通过组合攻击和背景知识攻击[6]等多种类型的隐私攻击方法获得个人隐私信息.差分隐私(differential privacy, DP)[7]因其严格的数学定义以及量化标准可以弥补以上保护技术的缺陷.同时, 差分隐私技术不依赖于攻击者所掌握的背景知识,敌手无法区分个人记录是否包含在数据库中.因此, 将其作为主要方法应用于用户轨迹相关性隐私保护中[8,9]已成为当前隐私保护领域内一个重点研究方向.

近年来, 差分隐私保护技术与位置轨迹相关性隐私保护相结合的研究逐渐成熟[10], 其中, 大多相关研究工作涉及到单个用户轨迹的位置以及运动模式等隐私泄露问题.根据用户轨迹之间是否具有相关性, 现有的轨迹隐私保护方法可归纳为四类: 单条轨迹内无相关性隐私保护方法、单条轨迹内相关性隐私保护方法、两条不同轨迹之间相关性隐私保护方法以及多条不同轨迹之间相关性隐私保护方法.其中, 现有研究位置轨迹相关性体现在时间上、位置上以及时空上隐私保护, 现举例说明轨迹时间相关性、位置相关性以及时空相关性[11]存在的隐私泄露问题:

(1) 轨迹在连续时刻间可能存在某种相关性, 即使均在每个时刻对相应位置进行保护, 连续的轨迹仍然具有较大可能暴露用户的真实位置.如图2(a) 所示, 用户在不同时刻的敏感位置均利用泛化技术进行扩大, 攻击者亦根据用户的移动模式、行为习惯等其它信息, 很大程度猜测出用户此时此刻所处的位置(如晚上7:00 吃完晚饭, 通过这条轨迹的大约90% 的用户会选择去公园散步), 进而造成用户隐私的泄露.

图2 轨迹相关性示例Figure 2 Examples of trajectory correlation

(2) 现有隐私保护机制仅考虑单个位置的隐私泄露问题, 忽略地理空间上不同位置之间存在的相关性也会对个人隐私造成一定程度的影响.如图2(b) 所示, 用户所处的当前位置为A, 假设位置L 为敏感位置, 利用泛化技术将位置L 扩大到圆形区域内(敏感区域), 用户从位置A 按照箭头的方向出发, 由于位置A 不敏感, 因此会如实上报该位置, 经过一段时间, 用户移动到位置B, 即使敏感位置所处的区域不会上报用户的位置, 攻击者根据位置A 以及敏感位置L 之间存在的拓扑关系, 较容易猜出用户途经或停留在位置L 处, 从而泄露了用户的位置轨迹隐私.

(3) 在连续查询场景下, 用户相邻时刻的查询请求具有时空相关性.为了保护相关性, 用户需要在请求时间内到达下一个位置点.如图2(c) 所示, 用户在ti时刻所处的位置为M, 其所在的泛化区域还存在其它位置点M1,M2,M3,M4,而用户在ti+1时刻所处的位置为N,其所在的泛化区域存在位置点N1,N2,N3,N4.M−→N 为用户真实移动轨迹.攻击者根据用户的查询间隔ti+1−ti和移动速度可推测出M4−→N2为假移动轨迹, 进而增加攻击者猜测真实轨迹成功的概率.

在早期关于轨迹相关性隐私保护的工作[12–14]中, 研究学者基于树重构的方式进行轨迹相关性隐私保护, 采用马尔可夫模型[15], 在单个轨迹内实现差分隐私相关保护.此外, 利用地理和语义关联[16]来合成轨迹, 实现轨迹隐私性和可用性的平衡.但是, 它们均不涉及用户之间的轨迹相关性以及可推出的用户之间社会关系的隐私保护需求.现有的方法和解决方案大多集中在单个用户的位置轨迹隐私上, 极少考虑到多用户地理空间以及时间上的轨迹相关性.

本文第2 节介绍了位置轨迹相关性隐私保护技术的基本概念.第3 节系统地分析了基于差分隐私的位置轨迹相关性的隐私保护方法, 对不同方案中的隐私保护方法进行分析比较.第4 节总结并展望基于差分隐私的位置轨迹相关性隐私保护技术研究中亟待解决问题和研究发展方向.最后第5 节总结全文.

2 相关概念

2.1 差分隐私基本定义

差分隐私是Dwork 等人于2006 年提出的一项隐私保护技术[7], 它将随机干扰噪音加入到数据集中的查询结果中, 在数据集中增加或删除一条记录时, 不会对查询结果产生任何影响, 从而确保了数据的隐私性.中心化差分隐私的详细定义如下所示.

定义1 (ε-差分隐私) 假设M是一个随机算法,D1和D2是一组只有一条记录不相同的相邻数据集,对于算法M在相邻数据集上的任意输出O满足不等式:

则随机算法M则满足ε-差分隐私.其中,ε表示隐私预算, 其值通常在ε ∈[0,1].ε越小, 表示随机噪声作用在相邻数据集上得到相同结果的概率越高, 其隐私保护程度越高, 使得结果不可区分以此达到隐私保护的目的, 反之亦然.

2.2 全局敏感度

添加噪声量大小影响保护数据的隐私性和可用性, 全局敏感度决定噪声量的大小[17].

定义2 (全局敏感度) 假设有函数F:D −→Rm, 输入一个数据集D1, 输出m维实数向量, 对于任意相邻数据集D1和D2的全局敏感度为:

其中,‖▪‖1称为一阶范数距离;F为在数据集D上执行的查询函数.全局敏感度由查询函数F作用在相邻数据集D1和D2执行查询操作的最大差异, 仅与查询函数F本身有关, 与数据集D无关, 直接影响噪声添加的多少.

2.3 噪声机制

差分隐私中最常用的噪声机制为Laplace 机制和指数机制.其中Laplace 机制通过Laplace 分布产生扰动噪声添加到返回结果中, 使攻击者无法分辨真实值和扰动值, 使结果满足ε-差分隐私; 指数机制通过采用满足一定分布的随机抽样来控制各种选项的输出值来满足ε-差分隐私, 其关键在于设置打分函数.然而, Laplace 机制适用于数值型数据, 具有一定的局限性, 而指数机制适用于离散型数据, 拓宽了差分隐私的应用范围.

定义3 (Laplace 机制)[18]对于任意函数F:D −→Rm, 其全局敏感度为ΔF, 若随机算法M输出的结果满足

则算法M满足ε-差分隐私.其中, Lap(ΔF/ε) 为服从Laplace 分布的Laplace 噪声, 其大小与全局敏感度ΔF成正比, 与隐私预算ε成反比.

定义4 (指数机制)[19]给定数据库D的一个效用估值打分函数u:(D,O)→R,r ∈O, 若随机算法M满足

则算法M满足ε-差分隐私.其中, Δu为打分函数u: (D,r) 的全局敏感度, 打分函数越大, 表示被选择输出值r的概率越高.

2.4 组合性质

对于一个复杂的问题, 可以通过多个步骤来实现, 并且在满足差分隐私的前提下, 每一个组元步骤都可以设置一个合理的隐私预算.差分隐私具有序列组合性和并行组合性两种基本的结合特性.

定义5 (序列组合性)[20]给定数据集D, 存在n个随机算法{M1,M2,···,Mn}, 每个算法Mi均满足εi-差分隐私, 则Mi在数据集D上的顺序操作满足-差分隐私.序列组合性说明当有一个算法序列同时作用在一个数据集上时, 最终的差分隐私预算等价于算法序列中所有算法的预算的和.

定义6 (并行组合性)[21]给定一个数据集D, 将其分成n份互不相交的集合{D1,D2,···,Dn}, 每个集合分别对应于一个随机算法{M1,M2,···,Mn}, 且每个算法Mi均满足εi-差分隐私, 则Mi作用在数据集D上的并行操作满足maxεi-差分隐私.

并行组合性说明如果所有算法处理的数据集彼此不相交, 那么该算法序列构成的组合算法提供的隐私保护水平取决于算法序列中的保护水平最差者(隐私预算最大者).

3 主要研究方向

在差分隐私模型下所保护的位置轨迹相关性的形式复杂多样.其中, 依据相关性将位置轨迹相关性隐私保护分为三类: 单条轨迹内相关性保护、两条不同轨迹之间相关性保护、多条不同轨迹之间相关性保护.除了严格的差分隐私模型外, 相对更为宽松的隐私保护需求如PufferFish 隐私[22,23]等也被采用以保护位置轨迹相关性, 以提升用户高质量网络服务的使用体验.

随着位置轨迹差分隐私保护技术的不断发展, 位置轨迹差分隐私保护方案按照不同分类标准有着不同的分类方法, 如图3 所示.

图3 位置轨迹相关性差分隐私保护分类Figure 3 Classification of location trajectory correlation differential privacy preservation techniques

3.1 差分隐私模型下单条轨迹内相关性保护

在位置轨迹隐私保护工作方面, 由于轨迹中存在着不利于用户隐私的时空相关性, 攻击者能根据其因素进行挖掘, 推测出轨迹中存在的隐私信息以谋求利益, 但现有的隐私保护工作极少数涉及到轨迹在空间以及时间上的相关性, 故造成严重的隐私泄露的问题.在差分隐私模型下, 单条轨迹内相关性保护的目标是如何对轨迹在时间上、空间上以及时空结合的相关性进行净化处理, 保证相邻轨迹数据集的不可区分性,确保轨迹相关性隐私不被泄露.目前已有基于时间相关性、空间相关性以及时空相关性的轨迹相关性隐私保护方案.尽管它们仍对轨迹相关性的隐私保护具有较多的限制, 但是这些方法可以最大程度地提高轨迹的隐私性和可用性.

3.1.1 基于差分隐私的单条轨迹内时间相关性保护

针对差分隐私的单条轨迹内时间相关性保护方法可以分为建立相关模型和进行序列转换两种解决方式.第一种是通过建立相关模型来表示轨迹序列的时间相关性, 比如基于树重构、基于马尔可夫链等.第二种是序列转换, 将位置轨迹相关性通过滤波转换为特别的形式, 基于转换的思想方案主要包括卡尔曼滤波、高斯白噪声.

(一) 相关模型

建立相关模型的基本思想是通过建立相关模型来表示轨迹的时间相关性, 比如, 位置轨迹发布过程中转移概率分布的马尔可夫模型, 或能够反映位置轨迹数据之间相关性的稀疏矩阵等, 在建立模型后, 这些均作为差分隐私敏感度函数的权重值, 以此来决定轨迹序列中添加噪声的大小.

(1) 基于树重构保护模型

一条轨迹可以抽象为按时间顺序组成的位置序列, 如表1 所示.利用基于树重构的保护模型来净化表示轨迹的时间相关性, 顾名思义, 将轨迹数据集用“树” 的形式表示轨迹的时序性, 再利用差分隐私保护模型对“树” 的分支节点进行净化调整, 以最大化提高轨迹的可用性, 最后得到重构后的轨迹数据集.其中,基于树的保护模型包括搜索树、前缀树和预测后缀树等.

表1 轨迹序列表Table 1 Trajectory sequence table

首先, 我们考虑最为普遍的、查询效率高的前缀树, 利用此方式来对轨迹的时间相关性进行保护.如图4 所示, 依据表1 中的轨迹序列, Chen 等人[12,13]提出了一种基于前缀树的数据依赖方式.如其名称所示, 首先利用前缀树的形式表示位置轨迹数据库中要发布的位置轨迹数据, 以此来表示轨迹中的时间相关性, 利用差分隐私技术对轨迹数据进行修改和修正, 并根据重建的轨迹树产生轨迹数据集, 进一步安全发布轨迹数据.

图4 轨迹序列用前缀树表示Figure 4 Sequence of trajectories is represented by a prefix tree

在基于前缀树的轨迹相关差分隐私保护中, 采用了两个阶段来实现位置轨迹相关性的保护: (1) 构造噪声前缀树(保证了轨迹的时序特性); (2) 修正噪声前缀树(提高了轨迹的可用性).具体来说: 为了满足差分隐私, 该方案需要保证从位置集合中形成的每条轨迹都有一定的概率出现在净化的数据集中, 因此,原始轨迹数据集中的敏感信息可以被覆盖.为了提高构建前缀树PT 的存储效率, 该方案采用了均分制的隐私预算划分方法, 假设树的高度为h, 故每个节点的隐私预算为¯ε=ε/h, 并以一种有噪声的方式迭代地构造PT 的每个级别.对于所有的位置集合, 该方案提供了一个有效的方法: 分别处理前缀树及轨迹中空节点和非空节点相关联的孩子节点.对于非空节点, 如果噪声计数≥θ, 则该节点属于非空节点, 则保留该节点继续扩展子节点.对于空节点, 为了提高算法的效率, 该方案设计了一个拉普拉斯机制的统计过程,遵循二项分布[24]B(m,pθ) 选取一个k值, 其中m为空节点的总数,pθ表示每个空节点随机化后取值大于θ的概率.选取k个均匀随机的空节点, 使得其计数值大于等于θ, 并服从以下分布:

然而, 由于差分隐私对轨迹进行保护时需要添加噪声, 因此在轨迹发布之前, 还需对节点计数的一致性进行处理, 以此来消除由于噪声的添加导致孩子节点的计数值之和大于父节点的计数值的情况.如果对不一致的情况未得到相应的解决, 由此产生的发布轨迹可能是无意义的, 也因此提供了较差的轨迹可用性.一致性的约束严格规定父节点的计数大于等于其孩子节点的计数总和.对修正后的前缀树进行后序遍历来生成私有轨迹发布.

以上的方案提出了一种数据依赖的解决方案, 基于现有轨迹数据递归来构造一个噪声前缀树.由于噪声前缀树的高度是由待发布的轨迹数据集中最长的轨迹长度所决定的, 但是随着前缀树的增长, 方案的数据效用变得很差.因此我们需要限定轨迹数据集中轨迹的最大长度, 对过长轨迹进行截断处理, 这就使得有些轨迹的子片段被抛弃.因此, 为了提高轨迹数据可用性, Chen 等人[25]在2012 年首次引入n-gram模型(又称搜索树模型, 如图5 所示) 作为在序列数据中实现差分隐私的有效方法, 用发布计数大于一个阈值和模型大小小于nmax的可变长度的n-gram 来对底层数据库信息和添加拉普拉斯噪声大小之间进行平衡.该方案开发了一系列计数来保证变长n-gram 模型下良好的效用, 包括自适应隐私预算分配方案, 阈值的正式选择和一致性约束的执行.这些技术利用了n-gram 模型中固有的马尔科夫假设允许减少注入的噪声, 从而进一步提高了数据的可用性.具体来说, 在自适应隐私预算分配阶段, 根据已知的噪声计数自适应地预测一条路径的长度hv, 在此之前, 需要依据马尔科夫假设计算出Pmax的大小(其表示节点v向所有子节点转移的概率最大估计值), 其定义如下:

依据公式c(v)·(Pmax)hv=θ得出剩余路径的最大长度:

因此, 该节点v的隐私预算计算方式为:εv=ε/hv(ε为剩余的隐私预算).

由于搜索树可能存在子节点噪声计数总和不等于其父节点的噪声计数, 并且一些子节点噪声计数缺失.该方案提出一种一致性约束来解决此问题, 利用马尔可夫假设来近似缺失的计数, 然后根据其父节点计数将子节点的计数标准化.因此n-gram 模型解决了轨迹数据应用差分隐私在其固有的序列性和高维性的问题, 提高了数据的可用性.

(2) 基于马尔可夫链保护模型

人们的行为轨迹可以用一个简单的马尔科夫链很好地建模.马尔科夫链是一种随机过程, 描述了在状态空间中从一个状态转换到另一个状态的过程, 由一个有限数量的状态组成.该过程具备下一状态的概率分布只能由当前状态决定的性质, 由于人类活动轨迹具有时序性, 下一位置仅与当前位置有关, 故利用马尔科夫链来建模轨迹之间的时间相关性.

定义7 (α-DPT(differential privacy under temporal correlations)) 如果一个差分隐私机制的TPL小于或等于α, 我们认为该机制在时间相关下满足α-差分隐私, 即α-DPT.

DPT是时间序列数据差分隐私的增强版本.这意味着时间隐私泄露在内是有界的.对于后向隐私泄露(BPL) 和前向隐私泄露(FPL), 设计一个多项式算法来计算.在不同的时间点上运行以进行连续的数据发布时, 在每个时间点都有一个恒定的Pi和不同的α作为输入.最后, 设计一种有效的针对TPL 的数据发布机制, 在每个时间点仔细校对传统差分隐私机制的隐私预算, 并提出一种新的隐私预算分配方式,在时间点1 和T分配更大的隐私预算, 在时间[2,T] 分配常量值, 以确保时间点[1,T −1] 的BPL 是相同的, 用αBt表示, 在时间[2,T] 的FPL 相同, 用αFt表示, 使其满足α-DPT.

由于以上方法具有差分隐私只保护用户级别隐私的缺陷, Xiao 等人[29]提出了基于δ-位置集的差分隐私法来保护时间相关性下用户在每个时间戳上的真实位置, 对单个用户强制执行保护, 且合并用户之间的时间相关性.两个连续时间戳之间的位置变化是由通过马尔可夫链建模的时间相关性决定的.因此, 为了保护真实的位置, 使用“δ-位置集” 来包括所有可能的位置(用户可能出现的位置), 使其“隐藏” 在δ-位置集中.δ-位置集是一个包含先验概率和不小于1-δ的最小位置数量的集合:

基于δ-位置集来定义差分隐私, 在任意时间戳t, 随机机制A满足δ-位置集ΔXt上的任意位置x1和x2,以下条件成立:

发布的位置zt在时间戳t上是差分隐私的, 保证了真实的位置总是在每个时间戳的δ-位置集中受到保护, 以便在时间相关性下进行持续的位置共享.

在差分隐私灵敏度的计算中, 由于l1-范数灵敏度不能捕获多维空间中的几何灵敏度, 提出了一种灵敏度壳的定义:

定义8 (灵敏度壳(sensitivity hull)) 查询函数f的灵敏度壳Δf是凸包, 其中Δf是对于δ-位置集ΔX中的任意一对x1和x2的f(x1)−f(x2) 的集合,

因此, 基于δ-位置集的差分隐私框架以显著的高效率和高效用发布不同的私有位置.

(二) 序列转换

序列转换方法背后的基本思想是在保持相关序列的同时将其转化为独立的形式, 同时保持其主要特征.例如, 可以根据人类活动轨迹中不同时刻位置的相互依赖关系, 通过构造相关函数和频率序列来表示这些过程的特定相关性形式.这样, 就能够将它们转化为特殊形式的相关性序列.该方法能提高轨迹数据的可用性.

由于轨迹在时间戳之间的相关性, 基于差分隐私发布具有序列性的轨迹数据会导致较高的扰动误差,轨迹数据稀疏性给隐私性和可用性也带来一定的挑战[30].Fan 等人[31]提出了一种保护用户不同隐私的实时框架和两种估计算法(时间估计和空间估计).在每个时间戳中, 输入的多维数据都受到拉普拉斯扰动机制的扰动, 以保证差分隐私.然后, 对于数据的可用性, 估计模块对扰动数据进行后处理, 以产生更准确的版本.

具体来说, 对于时间估计, 其关键思想是利用频率序列的内部时间序列模型函数, 并利用拉普拉斯噪声扰动值估计真实的聚合值.根据道路网络连接关系将每个单元划分为稀疏或密集, 并为每个类别内的单元假设相同的内部模型, 对于每个单元c, 其频率序列Xc可以用以下过程模型函数表示:

ωc被称为过程噪声, 它服从正态分布[32].Qc值表示相邻时间戳之间的变化程度.

由拉普拉斯扰动机制得到的噪声观测结果可以建模如下:

每个单元计数的差分隐私预算是α/T, 因为总体隐私预算α被统一分配给每个时间戳.这里我们对每个单元采用v ∼N(0,R) 高斯逼近, 并使用基于卡尔曼滤波的滤波技术, 对每个单元进行转换, 之后进行后验估计.综上所述, 对于每个时间戳k和每个单元格c, 用预测程序推导出一个预测频率.在接收到噪声观测后, 可以通过预测和观测的线性组合, 用正确的程序得到一个后验估计, 转换为相关的轨迹序列, 极大地提高了每个时间戳发布数据的准确性.

对于空间估计, 依赖于简单和实用的假设.为了应对由于数据稀疏下进行扰动导致的高相对误差的情况, 根据空间邻近区域将相似的单元格聚合成分区, 并在每个分区内执行估计, 假设分区内的对象均匀分布.由于四叉树更适合于多维时间序列场景, 提出了一种基于四叉树的自顶而下的空间划分方法.总体来说, 假设每个分区内的单元具有相似的密度, 对于每个时间戳k, 从每个分区的单元格中聚合一个分区计数, 然后使用拉普拉斯噪声计数来估计分区内每个单元的频率.因此, 通过将噪声计数均匀地分布到每个单元中, 降低了每个单元的扰动误差.

然而, 以上方法使用的拉普拉斯噪声具有独立且同分布的缺点, 敌手可以通过滤波等细化方法去除相关时间序列中的独立噪声, 使有效性以及隐私程度低于预期.Wang 等人[33]提出了一种有效的相关时间序列数据发布解决方案(correlated time-series data publication solution via differential privacy, CTSDP),通过差分隐私,使用序列-不可区分性和相关的拉普拉斯机制(correlated Laplace mechanism,CLM)来解决上述挑战, 并发布相关的时间序列数据.该方案定制了一种个人隐私泄露风险, 在相关时间序列中,利用差分隐私发布序列的挑战是使得个人隐私泄露风险满足差分隐私, 同时保持高可用性.如下所示:

如果满足上述条件, 则认为CTS-DP 已经达到了ε-差分隐私.

CTS-DP 包括以下两个阶段: (1) 定义序列-不可区分性.然后, 导出满足序列-不可区分性的噪声序列的自相关函数.(2) CL 根据噪声序列的自相关函数产生一个相关的拉普拉斯噪声序列.CLM 通过一个特定的滤波器将四个高斯白噪声序列进行转换, 并输出一个相关的高斯序列.序列-不可区分性的定义如下:如果噪声和原始序列的归一化自相关函数,RZ(τ) 和RXX(τ) 满足RZ(τ) =RXX(τ), 敌手既无法区分噪声和原始序列, 且不能利用原始序列的相关性知识来进行挖掘隐私信息以谋求利益.CLM 具体过程为:首先生成四个IID 高斯白噪声[32,34]序列, 其参数由灵敏度函数和保护强度决定.将白噪声级数通过一个特定的滤波器(即一个典型的线性系统), 得到了相关的高斯序列.最后, 根据从高斯级数生成拉普拉斯序列的原理, 转换得到了一个相关的拉普拉斯序列.由于高斯白噪声序列易于生成, CLM 可以在计算能力有限的设备上实现.

3.1.2 基于差分隐私的单条轨迹内位置相关性保护

对于单条轨迹内位置相关性保护, 我们将通过相关网络数据的发布[35,36]来代替轨迹数据的发布进行描述.

由于网络数据之间具有较高的相关性, 并且传统的数据准备工作采取随机采样会导致较低准确性, 在保证高可用性和隐私性的前提下高效地发布网络数据, 该研究尚未成熟.Zhang 等人[35]针对高维数据(轨迹数据) 的发布提出了一种基于差分隐私的隐私数据发布机制(PrivBayes), 该机制改变了传统的采样方式, 利用贝叶斯网络建模的方式表示数据之间的相关性.PrivBayes 分为贝叶斯网络N的构造、噪声版本的条件分布Pr∗[Xi|∏i] 以及合成发布数据集D∗三个阶段.k度贝叶斯网络N的构造被建模为一个优化问题, 为输入数据库D中的属性集A中每个属性Xi选择一个父集∏i, 最大化∑d i=1H(Xi)−H(A),

其中, 定义一个打分函数F(灵敏度很小), 将每个AP 对(X,∏)∈Ω 映射到一个分数:

F(X,∏)的值往往与相互信息I(X,∏)呈正相关,考虑相邻分布之间的L1距离,其灵敏度为S(F)=1/n.受到隐私预算ε、数据库元组总数n和噪声边际分布的有用性θ三个因素的影响,k的选择应该平衡贝叶斯网络的信息量和边际分布的鲁棒性.对于任何i ∈[k+1,d], 首先计算联合分布Pr[Xi,∏i], 然后注入拉普拉斯噪声(其尺度为2(d −k)/nε2) 生成噪声分布Pr∗[Xi|∏i], 确保该过程满足(ε2/(d −k))-差分隐私.最后, 利用贝叶斯网络N提供的采样方法, 在不考虑其他隐私的情况下从条件分布Pr∗[Xi| ∏i]中采样每个Xi, 生成任意数量的元组来构建一个合成数据库D∗.从以上过程可以看出, 以贝叶斯网络发布高维网络数据是高效准确的, 这将为未来探索新的方向: 某些问题是否可以直接从物化模型及其参数中得到回答, 而不是通过随机抽样.

数据相关性的存在导致敌手区分两个数据库的能力有所增强.差分隐私在应用大数据相关性方面时,很容易受到数据之间相关性的影响, 进而影响差分隐私的效果.Chen 等人[36]针对数据相关性隐私保护的问题, 通过引入一个相关性参数k并结合差分隐私技术, 提出了一种相关性下的差分隐私保护机制(ε-differential privacy under correlation).给定一个隐私参数ε、一个相关参数k, 设置相关性差分隐私.

定义9 (ε-differential privacy under correlation) 如果对于具有相关参数k的任意两个数据库D1和D2,|D1ΔD2|=1 以及任何可能的输出o ∈Range(A), 则机制A满足:

由于数据之间存在相关性, 函数的输出不仅影响单个记录, 还影响其他所有相关的记录, 利用group差分隐私, 在任何ε/k-差分隐私下, 也保证了k个记录不同数据库的ε-差分隐私.为了防止相关性带来的隐私风险, 利用相关参数k来校准噪声, 有以下结论:

因此, 方案在具有相关参数k的数据库上满足ε-差分隐私.在此基础上, 提出了一个实用的非交互式的网络数据发布解决方案, 可以防止对手学习到任何两个个体之间存在的直接联系.

3.1.3 基于差分隐私的单条轨迹内时空相关性保护

在单条轨迹内时空相关性隐私保护中, 由于轨迹在时间上、空间上存在隐私泄露的风险, 故需要对轨迹的时空相关性进行保护.关于基于差分隐私的单条轨迹内时空相关性的采样方法除3.1.1 节中的以外,还存在基于参考系统采样、基于自适应采样机制等方法.

(一) 基于参考系统采样

基于参考系统采样的主要思想是依据人类的运动速度、运动模式、轨迹特征以及密度等因素建立一种参考系统, 对轨迹进行不同程度地映射, 形成高效用的校正轨迹, 从而实现了保护轨迹时空相关性的目的.

为了方便简单地捕获轨迹中时空相关性,He 等人[37,38]不再直接使用马尔可夫模型,而是建立差分隐私轨迹(differentially private trajectories,DPT),以此建立一种新的层次参考系统(hierarchical reference systems, HRS) 模型, 该模型可以捕获原始轨迹中不同速度范围内的运动, 将原始轨迹按照不同速度划分成多个轨迹片段(离散化), 较长的步长(慢速度运动) 映射到划分更粗糙的层次参考系统, 反之较短的步长(快速度运动) 映射到划分更精细的参考系统中.接下来, 构造前缀树集合HRS→{T1,T2,···,TM}.前缀树被实例化为参考系统, 每个前缀树仅记录某一层次系统下的轨迹段集合.为了保证差分隐私, 前缀树节点计数中添加拉普拉斯噪声进行扰动, 并对前缀树进行剪枝以进一步提高轨迹数据的可用性.以上不免会造成大量误差:

前者为前缀树噪声计数误差, 后者为前缀树剪枝造成的误差.整体隐私预算分为ε=εs+εr, 前者为选择树添加的随机噪声分配的隐私预算, 后者为前缀树计数添加噪声所分配的隐私预算.因此, 为了降低误差大小, DPT 使用一种新的模型选择算法来设置前缀树的高度k来提高轨迹的可用性.该算法目标是找到高度为k的最优模型F+∗, 使得模型满足以下条件:

除此之外, 为了最大程度保留轨迹的方向性, 提出了一种新的后处理策略, 该策略引入一种新的方向加权采样方案, 该方案对相邻的单元格进行编码, 并采样轨迹, 首先为轨迹的每个方向dir 设置相等的权重wdir(x) =αc(dir,x)(权重随着采样过程而更新), 其中,x为轨迹前缀,α是一个大于1 的权重因子.当轨迹的长度较长时, 对应窗口大小为w, 利用wdir(x)=αc(dir,x|w|)来计算方向权重.

由于He 等人[37,38]对原始轨迹采样存在效率低的缺陷, 而且隐私评估方法仅处理较短的轨迹(位置少), 因此, Wang 等人[14]提出一种基于差分隐私的轨迹校准和发布系统(private trajectory calibration and publication system, PTCP).首先, 在考虑轨迹的特征和密度的情况下, 建立一种基于聚类的方法来提取轨迹数据库中的特征点, 以此作为锚点, 并使用具有σ ＞0 尺度的拉普拉斯噪声来扰动位置, 以此来建立基于泛化的锚点参考系统(reference system, RS) RSA= [a1,a2,···,am].接下来, 为了降低校准计算成本, 对每条轨迹进行R-tree 索引, 基于几何图形的校准方法将其位置点映射为锚点, 形成校正轨迹.为了保护不同隐私需求的轨迹, 提高实用性和效率, 提出了一种轨迹发布机制, 建立噪声增强前缀树, 利用马尔科夫假设将噪声增强扩展到足够的长度.对于非叶子节点, 使用估计高度函数来估计该节点子树hs的高度, 估计噪声计数的大小为c′(currentnode)∗Phstmm ≤θ,Xmax为前缀树中从根节点到一个叶子节点的最大程度,hs应该限制在Xmax−i中, 因此子树的高度为:

(二) 基于自适应采样

基于自适应的采样机制方法, 其基本思想是在差分隐私的保护模型下依据轨迹数据的动态变化进行动态调整隐私预算, 降低扰动误差, 从而对轨迹数据更为准确地采样.

现有方法大多集中在静态数据的一次性发布, 而对于数据流来说, 其需要进行实时的收集和发布[39,40], Wang 等人[41]研究具有时空相关性的众包数据发布问题, 提出了一种在无限流上的在线聚合监控方案RescueDP.其中, 设计了一种自适应采样机制, 依据数据动态变化以及剩余隐私预算来调整采样率, 为了减小误差, 定义一种采样间隔确定}, 使用PID 误差δj的相对值和拉普拉斯噪声λr= 1/εr的尺度来决定是增加还是减少采样间隔.为了有效地分配隐私预算, 提出一种自适应隐私预算分配方式, 考虑分区p和采样间隔I之间的关系(随着I增大, 分区比例会缓慢增加), 让p= Φlin(I+1) 来避免给下一个采样点留下太少的预算, 因此, 当前时间戳所分配的隐私预算为εi= min(p·εr,εmax), 其中εmax用来限制当前时间戳分配隐私预算的最大值.为了降低较小统计量所造成的扰动误差, 提出一种动态分组机制, 利用已经发布采样点的统计数据来预测当前采样点统计数据的值,利用皮尔逊相关系数[42]来度量统计学变化趋势的相似性, 将较小统计量的区域变化趋势的相似性归为一组.接下来, 对每一组添加拉普拉斯噪声对统计值进行以下扰动:

然后对每个区域的扰动统计量取平均数M(g[j]) =M(g)/φ,∀j= 1,2,···,φ.由于时间序列具有丰富的时空相关性, 最终使用过滤机制(卡尔曼滤波[43]) 来提高已发布数据的准确性.RescueDP 较现有的方法, 提高了数据的准确性和可用性.

(三) 基于马尔可夫链采样

由于马尔科夫链表示状态空间中, 依据状态转移概率矩阵, 从当前时刻状态到下一时刻状态转换的随机过程, 利用马尔科夫链对运动轨迹进行采样, 既能模拟轨迹内的时间相关性, 也能模拟用户真实位置轨迹内的时空相关性.

为了进一步提高轨迹数据扰动之后的可用性以及轨迹相关性保护的计算效率, Gursoy 等人[47]提出了一个具有不同隐私和攻击弹性的可扩展的轨迹合成器(AdaTrace), 通过研究用户的真实轨迹, 来提取四个空间和统计特征: 密度感知网格、马尔可夫链迁移率模型、出行分布以及路线长度分布.为了考虑到不同隐私和攻击弹性的因素, 可以对四个特征使用不同的噪声机制进行特征提取和扰动.首先对旅行长度分布进行研究, 来确定轨迹合成的长度, 对于密度感知网格, 网格存在过于粗糙和细致的问题, 提出了一个具有密度自适应网格力度的网络, 对于密度高的区域, 划分更细致; 反之亦然.为了提高轨迹的可用性, 需要模拟轨迹的移动性, 采用马尔科夫链进行移动建模.为了保存轨迹起始点和结束点之间的相关性, 需要对轨迹的行程分布进行计算, 其过程如下:

以上生成一个具有较高数据可用性以及较低计算量的合成轨迹, 并有效地抵抗不同推理攻击[48], 以此来保护轨迹中的敏感信息.

为了进一步最大化高效地保留轨迹中的空间和时间信息, 提高隐私保护的实用性和效率, 降低所需的计算量,Ghane 等人[49]提出了一种基于差分隐私保护时空相关性的轨迹生成机制(trajectory generative mechanism, TGM), 该机制分为编码和轨迹生成阶段, 编码阶段提出一个概率图形生成模型以精确地对轨迹中的位置进行编码, 利用空间和时间聚合函数将轨迹T转换为聚合域, 并拟合马尔可夫过程来估计轨迹中下一个位置的状态(停留、移动、终止), 其中, 转移概率利用g(m,v,Ti) 的图计数查询来计算,

上式中c(v,Ti) 表示在一个特定节点v上带有前缀Ti的轨迹数量, 其中m= 1 表示移动事件的统计, 以此来生成图形模型G.对于轨迹生成阶段, 提出一种自适应添加噪声的算法, 该算法能够保持任意长度的轨迹运动模式, 最大化保留轨迹的时空信息.转移概率的计算过程中, 利用节点效用来选择起点的位置:

3.2 差分隐私模型下两条不同轨迹之间相关性保护

3.1 节讲述了各类单条轨迹内相关性在差分隐私保护模型下的隐私保护方法, 但这些方法仅考虑干扰一个用户的位置轨迹, 而没有考虑多个用户之间的位置轨迹相关性, 相关轨迹的发布可能会泄露敏感的社会关系.因此, 这些技术不能很好地抵御各种攻击.目前, 差分隐私应用轨迹间相关性隐私保护存在以下挑战: 保护个人轨迹的隐私保护; 保护不同用户之间的位置轨迹相关性隐私保护.

为了在严格的差分隐私模型下保护不同用户之间的位置相关性, Ou 等人[50]提出了一种基于隐马尔可夫模型(hidden Markov models, HMMs) 的私有轨迹发布机制.该机制首先构造相邻轨迹数据库, 使用HMM 生成一个可能的轨迹集(probable trajectories sets, PTSs), 并利用HMM 相似性来衡量两个用户中间可能轨迹集合中的相关性并定义一个位置相关性系数Sij= ∑(∑Slij/t)/n, 当Sij ≥λ, 表示相关性较大; 反之亦然.选取用户Ui和Uj中位置相关系数Sij ＜λ内的所有可能的位置轨迹, 并结合用户的真实轨迹RTi, 一起构造私有候选集合(private candidate sets, PCS):Ct=ct ∈(TUi −RTi),TUi表示用户Ui在HMM 运动下的所有可能位置轨迹集合, 以此来构造相邻数据集.在此基础上, 提出了一种位置相关性保护机制, 在时间段t内, 一个随机机制R基于PTS 满足ε-差分隐私, 对于任何zt(要发布的位置轨迹) 都有:, 确保了两个个体之间的位置相关性在时间t内得到了差分隐私保护.对于敏感度Sf的计算相当于一个人的位置轨迹数据可以改变查询函数f的最大变化, 分析传统差分隐私敏感度的计算可以得出敏感度与查询数量ρ有关, 即Sf=ρ.最后, 提出一种轨迹发布机制, 该机制输入用户的真实位置轨迹RT, 输出从私有候选集合Ct中随机选择的发布位置轨迹zt, 其目的是保护个体之间的位置相关性.

在净化轨迹发布之后, 如果不对其进行处理, 则用户将会享受较低的网络服务质量.高效用意味着原始轨迹不会被扭曲太大.针对此问题, Ou 等人[51]在2018 年研究社会关系与轨迹相关性之间的关系, 提出了一种基于差分隐私的发布相关轨迹隐私保护机制.该机制通过严格的数学模型来建立一个基于轨迹距离的分数测量方法S=S(x)S(y), 以此来量化两个用户之间的社会关系,S越大, 说明社会关系越强, 反之亦然.针对社会关系, 依据最大不同的相邻轨迹距离和敏感度, 提出一个n-体拉普拉斯框架D′(a,b) =D(a,b)+δ, 以此来保护社会关系免受各种攻击.为了提高发布轨迹的可用性, 基于精确位置的服务以及基于双用户位置相关性的服务, 提出了两种基于拉格朗日乘子的差分隐私方法, 即UD-LMDP和UC-LMDP, 并提出了位置相关性系数来衡量不同轨迹之间的相关性强弱, 即:

通过LM (Lagrange multiplier) 方法分别得到最优的拉普拉斯噪声尺度参数集bud和buc, 以实现给定效用ud下的最大隐私性minε|Ud=ud以及给定位置相关效用uc的最大隐私性minε|Uc=uc.最后, 依据拉普拉斯噪声参数集合安全地发布净化轨迹.

以上方案均对两条不同轨迹之间的位置相关性进行保护, 但是均未考虑时间因素, 现如今保护不同用户之间的时空相关性研究尚未成熟.因此, 保护轨迹中时空相关性是一个亟待解决的问题.

3.3 差分隐私模型下多条不同轨迹之间相关性保护

3.1 与3.2 节所陈述的方案仅仅适用于小于等于两个用户的情况, 均未考虑多个用户不同位置轨迹之间相关性.即使轨迹受到现有方法的扰动, 由轨迹相关性引起的隐私泄露仍然存在.

为了解决发布大量轨迹时, 由于轨迹相关性而导致的隐私泄露问题, Yu 等人[52]提出了一种基于差分隐私的相关轨迹发布方法(correlated trajectory publication with differential privacy, CTP).首先, 该方法分离用户真实轨迹, 并通过拉普拉斯机制自适应网格划分方法将地理区域离散化为网格G, 并计算每个单元格中轨迹的单元格访问的归一化次数, 其计算方法如下所示:

由于q(Ci) 是归一化的, 所以q的敏感度为1, 添加拉普拉斯噪声以确保轨迹单元的隐私性, 并得到轨迹单元访问概率向量.

为了更好地保护轨迹相关性, 利用单元访问概率向量量化轨迹相关性S(Tci,Tcj) = sim(Pci,Pcj), 并对其利用进化算法(evolutionary algorithms, EAs)[53]中的粒子群优化算法(particle swarm optimization,PSO) 约束优化来削弱不同用户之间的相关性, 如公式所示:

3.4 对比分析

基于差分隐私模型的轨迹相关性隐私保护是近年来受到广泛关注的研究内容, 其研究受到差分隐私以及轨迹隐私保护领域的影响.表2 对基于差分隐私保护的轨迹相关性进行了对比与总结.从安全性角度出发, 前述各方案采用Laplace 机制、指数机制或两者兼并进行噪声注入, 均满足隐私保护要求较为严格的ε-DP 模型.需要注意的是, 即使隐私保护程度选择相同的模型, 方案注入的噪声规模也不尽相同, 导致方案可用性存在较大差异.以上方案中, 对于可用性的衡量分别采用平均相对误差、准确率、F1-score、KL散度等指标评估隐私保护结果的可用性.表3 与表4 对现有方案中轨迹相关性主要方法的优缺点进行分析总结.总体来说, 对于单用户轨迹内相关性隐私保护在时间相关性、位置相关性以及时空相关性方面的研究日益成熟, 在差分隐私的保护模型下实现了隐私性以及可用性之间的均衡, 但仅仅局限于单用户的单条轨迹相关性的保护, 未考虑多个用户轨迹之间的相关性, 在使用这些隐私保护方案对单用户轨迹内相关性进行保护时, 敌手仍能依据背景知识进行推理攻击, 造成巨大的隐私泄露风险.此外, 由于很难用严格的数学表达式来量化与两个用户以及多个用户轨迹相关的社会关系, 以及很难为保证隐私保护而提高数据的可用性, 因此双轨迹之间的相关性以及多轨迹之间的相关性研究[50–52]较少.防止通过不同轨迹之间的相关性来推理社会关系是一个具有挑战性的隐私保护问题, 需要对相关工作进行大量研究.

表2 位置轨迹相关性隐私保护主要方法的特点对比Table 2 Features comparison of main approaches to privacy preservation for location trajectory correlation

表3 多用户(≥2) 轨迹内相关性主要方法对比Table 3 Comparison of correlation privacy preservation methods within multi-user (≥2) trajectories

表4 单用户轨迹内相关性主要方法对比Table 4 Comparison of correlation privacy preservation methods within single-user trajectories

4 未来研究挑战

轨迹相关性隐私保护是一个新兴的研究领域, 现有的技术方法面临着各种挑战, 还有很多方面值得研究人员深入研究.下面从三方面简述可深入研究的展望供研究人员参考:

(1) 传统差分隐私保护技术在轨迹相关性中的改进与应用

从当前差分隐私的研究成果来看, 其保护作用在大数据环境下的应用往往是被动执行的, 无法依据查询函数的种类来主动执行, 被动执行保护会造成噪声添加程度不合理.此外, 大多数工作均不考虑用户的个性化保护, 仅考虑单个位置的隐私保护, 噪声过大或过小都会对差分隐私的保护水平和数据可用性造成影响.在差分隐私轨迹相关性隐私保护工作中, 隐私预算ε的设置和分配是一项极其重要的工作.研究者应考虑多因素(用户的时间、速度以及运动模式等) 构造高效的自适应个性化隐私预算模型, 在有效保护隐私的前提下提高数据的可用性, 尽可能在功能和效率之间寻求平衡.因此, 针对不同保护对象的类型和隐私需求, 构造智能化的主动差分隐私保护框架有待深入研究.

(2) 挖掘轨迹相关性中的其他隐私保护模型

将差分隐私框架用于实现轨迹相关性的隐私保护, 往往随着发布轨迹的次数增加而噪声也增加, 导致隐私预算快速耗尽, 造成发布轨迹的可用性较差.针对此问题, 现有的弥补方法有动态的局部敏感度、平滑敏感度以及滑动窗口, 旨在在发布结果的隐私性和可用性之间取得平衡.但是, 针对多个用户之间的位置轨迹的关联性也需要添加额外的噪声进行保护, 在差分隐私领域, 混洗差分隐私(shuffled differential privacy)[54,55]、PufferFish 隐私[22,23]以及ρ-差分可辨性[56]等通用隐私保护模型应用越来越广泛.前者是一种介于差分隐私和本地差分隐私之间的差分隐私模型, 用户不需要像传统本地化差分隐私一样加入大量的噪声也能实现相同水平的隐私保护效果.后者是差分隐私的推广, 旨在解决相关数据的隐私问题.深入研究不同隐私保护模型应用于轨迹相关性隐私保护的优缺点, 选择高效的隐私保护模型是未来轨迹相关性隐私保护领域内值得探究的重要方向之一.

(3) 轨迹相关性建模的合理设计

在基于差分隐私保护位置轨迹相关性的方法中, 单条轨迹内相关性隐私保护研究逐渐成熟, 不同用户(两个或三个以上) 之间的位置轨迹相关性隐私保护研究的相关研究较少, 为了在严格的隐私保证下保护多条轨迹之间相关性, 必须通过安全的个人轨迹发布机制来解决轨迹相关性的公开问题.轨迹在空间和时间特征的影响下, 敌手可以从中挖掘大量的敏感信息以谋求利益, 故多条轨迹之间的轨迹相关性需要进行严格的定义, 并提出合理高效的量化标准.目前已经有隐马尔可夫相似性、余弦相似性、豪斯多夫距离法等若干轨迹相关性量化方法, 但如何在个人轨迹相关性合理建模中实现多隐私因子支持, 并且在轨迹相关性精准度量的基础上, 对轨迹数据进行有针对性的技术处理, 从而实现对多条轨迹之间的位置轨迹相关性的高效隐私保护, 有待未来结合应用进一步分析与研究.

5 总结

差分隐私近年来被广泛应用于位置、轨迹发布以及位置轨迹相关性的研究, 并取得了丰富的研究成果.本文阐述了基于差分隐私保护模型的位置轨迹相关性保护技术的基本方法和研究进展, 同时展望了未来的研究方向.总的来说, 轨迹相关性隐私保护是一个多学科结合的领域, 作为新兴的研究领域现有的技术方法仍然面临着各种挑战, 希望本文能对本领域的研究学者有所帮助.