基于差分隐私模型的位置轨迹发布技术研究

奥鹏网院作业

基于差分隐私模型的位置轨迹发布技术研究
冯登国*①② 张 敏①② 叶宇桐①
①(中国科学院软件研究所可信计算与保障实验室 北京 100190)
②(中国科学院软件研究所计算机科学国家重点实验室 北京 100190)
摘 要：位置轨迹大数据的安全分享、发布需求离不开位置轨迹隐私保护技术支持。在差分隐私出现之前，K-匿名及其衍生模型为位置轨迹隐私保护提供了一种量化评估的手段，但其安全性严重依赖于攻击者所掌握的背景知识，当有新的攻击出现时模型无法提供完善的隐私保护。差分隐私技术的出现有效地弥补了上述问题，越来越多地应用于轨迹数据隐私发布领域中。该文对基于差分隐私理论的轨迹隐私保护技术进行了研究与分析，重点介绍了差分隐私模型下位置直方图、轨迹直方图等空间统计数据发布方法，差分隐私模型下轨迹数据集发布方法，以及连续轨迹实时发布隐私保护模型。与此同时，在对现有方法对比分析的基础上，提出了未来的重点发展方向。
关键词：隐私保护；差分隐私；位置大数据；轨迹大数据；数据发布
1 引言
移动互联网的快速发展将人类带入位置大数据时代。越来越多基于位置的服务(Location Based Services, LBS)融入人们的日常生活，提供诸如兴趣点查询、社交网络实时位置共享、路线规划与导航等服务，为人们提供了极大的便利。与此同时，各类LBS服务汇聚了数以亿计的位置信息，为企业挖掘有价值的商业信息提供了基础数据。通过位置轨迹大数据分析，企业与政府部门能更准确地预测城市交通动态、预先采取措施缓解交通拥堵压力、进行道路规划[1]；也可以为用户构建画像并提供更为精准的个性化服务[2]。
但是，如果缺乏足够的位置轨迹隐私保护，那么数据发布必然导致大量用户隐私泄露。例如，2014年数据科学家Tocher[3]曾根据公开数据以及乘坐出租车的公开新闻照片识别出了纽约名人搭乘出租车的起点、目的地与乘车费用等；2017年风靡欧美的运动Strava[4]发布了世界用户活动“热图”，被网友挖掘出军事基地的位置、训练时间以及个人用户家庭住址和真实身份等。目前轨迹发布面临最为突出的风险是轨迹去匿名化，即匿名轨迹属主的身份被重新识别出来。在个体位置被持续记录的场景下，轨迹如同指纹一般可以唯一标识出用户。不仅轨迹中特征位置容易暴露匿名轨迹用户身份，而且轨迹中的时序特征、位置分布特征都隐藏着轨迹与现实用户之间的关联。例如，目前基于HMM模型的轨迹去匿名化方法可以识别出Gowalla数据集中近90%的匿名用户[5]。除可能暴露用户身份隐私以外，轨迹还可能泄露大量用户敏感信息。例如，观察到用户出现在医院可以推测出其本人或家庭成员的健康状况；根据用户对某类兴趣点的访问频率，可以推测出用户偏好及经济水平；结合轨迹的产生时段以及起始、结束地点信息，容易推测出用户家庭住址，等等。因此，如何实现位置轨迹数据的安全分享与发布，保护用户身份隐私、敏感属性隐私不被泄露，已成为当前IT产业界与学术界共同关注的重要问题。
在差分隐私出现之前，轨迹匿名与隐私保护大多采用以K-匿名为代表的基于等价类的方法。K-匿名理论假设攻击者能力有限，仅能将攻击目标缩小到一定的等价类范围内，无法唯一地准确识别攻击目标。研究者通过轨迹分割、子轨迹聚类、泛化与扰动等处理，实现至少K个用户轨迹之间不可区分。经典的代表是Abul等人[6]提出的(K,δ)匿名模型，基于欧氏距离对轨迹进行聚类，组内轨迹数目至少为K，组内轨迹间距离小于阈值δ，发布内容为组内均值轨迹，或真实位置点重构轨迹。此后，研究者提出了基于轨迹分割[7]、基于位置点扰动[8]等方法进一步减少位置轨迹片段中的用户特征序列，以满足K-匿名模型或改进的L-diversity模型要求。此外，也有研究者提出了基于路网Mix-zone的假名轨迹集分割、基于伪随机加密的可逆位置泛化等多种改进方法[9]，降低匿名轨迹的重识别风险，增强数据可用性。K-匿名理论面临的最大问题是，一旦攻击者能力超过了预先的假设，就能够进一步区分等价类内的不同记录，实现去匿名化。例如攻击者可通过链接攻击、位置同质性攻击、位置关联依赖攻击等破坏位置或轨迹的K-匿名安全性。总体来说，虽然K-匿名模型及其衍生模型提供了一种量化评估的手段，使得不同类型的方案之间具有可比性，但无法提供严格数学证明，安全性依赖于攻击者所掌握的背景知识。当有新的攻击出现时，原有保护机制可能完全或部分失效，模型无法提供完善的隐私保护。
差分隐私技术的出现有效地弥补了上述问题。一方面，差分隐私模型对攻击者的能力做了最大假定，并不依赖于攻击者所掌握的背景知识；另一方面，差分隐私模型建立于坚实的数学基础之上，对隐私保护进行了严格定义，并提供了量化评估方法，使得不同方法提供的隐私保护水平具有可比性。正因为如此，差分隐私[10]自2006年被提出以来，就受到众多隐私保护领域研究者的关注，广泛应用于支持隐私保护的数据挖掘与数据发布领域[11]。近年来，差分隐私理论与轨迹隐私保护融合研究方面涌现出了一批新成果，本文重点来综述和分析这方面的最新研究成果，并在对比分析的基础上提出未来的重点发展方向。
2 差分隐私模型
2.1 基本定义
差分隐私[10]是基于数据失真的隐私保护技术，通过注入噪声，使得增加或删除一条数据记录的操作对输出的影响不可区分，保证数据集中个体的隐私。其基本概念和定义如下。
定义1(ε-差分隐私，简称ε-DP)[10] 对于一个支持随机机制的查询算法f:D→Rd，其输入为一个数据集，输出为d维实数向量。若对任意数据集D及其相邻数据集 D′ ，算法f对任意输出S ⊆Range(f)都满足下列式(1)，则称算法f满足ε-差分隐私。

其中，参数ε被称为隐私预算。定义1表明，ε越小，则差分隐私算法作用在一对相邻数据集上所产生查询结果的概率分布越相似，攻击者更难以判断某元素是否存在于数据集中，因而隐私保护程度更高。
定义2 (全局敏感度)[12] 对于函数f: D→Rd，定义 ∆f =maxD,D′||f(D)−f(D′)||1，称为函数f的全局敏感度。
全局敏感度是特定查询函数f在所有可能的相邻数据集D和 D′上查询时输出值变化的最大范围，其度量值为两者之间的L1距离。它与数据集D无关，由查询函数f自身决定。全局敏感度直接影响添加噪声的多少。f的全局敏感度越大，则在ε相同条件下需要注入的噪声越多。在特殊场景下被较小的局部敏感度取代。



戴笠搜查黄炎培住宅，事先未报告蒋介石，是他自作主张。蒋介石听了邵力子的报告后，觉得此事也损害了他的威信和形象。他立即将戴笠叫来问是怎么回事。
3.1.1 位置直方图隐私发布
在差分隐私模型下，一种直观的噪音注入方式是对构成空间直方图的每个单元网格添加独立同分布的拉普拉斯噪声[19]，但在大多数实际应用中，网格粒度的选择面临两难困境：若网格粒度过大，则查询结果精确度难以满足应用需求；而网格粒度过细时，会带来两个严重问题：其一是大多数网格的数据稀疏，其二是误差累加效应明显，覆盖面积较大的查询结果精度急剧降低，且该问题在高维直方图发布中表现尤为突出。以我国地图为例，若采用10 m×10 m的精度表示，则由近 1011个网格构成。一个包含千万级位置信息的数据集分散在该地图上时，绝大多数网格被命中的次数为0或者非常小的数值。此时，若为了满足查询ε-差分隐私要求而采用Laplace机制注入噪声干扰，在每个网格单元上应添加Lap(1/ε)噪声，方差为σ2。当查询Q覆盖相当于北京市面积的数据时，查询带来噪声叠加效应将包含 108个区域的误差，查询结果的方差可达108σ2。即查询范围愈大，结果失真愈严重。虽然文献[20]中分别给出了一种统一规划的UG方案，以及一种适应性调整AG方案，通过网格粒度优化机制部分改善了该问题，但无法从根本上解决该矛盾。
为了对任何范围查询都提供高精度查询结果，更为普遍的做法是借鉴空间索引的设计思想，实现支持空间计数查询的层次化直方图结构[21,22]。采用不同层次节点表示不同面积的网格，取代统一粒度的网格对外提供直方图查询服务。最常见的是基于四叉树结构的发布方法。
四叉树(QuadTree，又称四分树或四元树)是一种经典空间网格划分方法，可以为划分后的网格提供空间索引服务。当树中每个节点中记录该节点区域所包含的位置点个数时，四叉树可用于响应针对任意区域内所包含位置点的计数查询。由于四叉树结构与数据的相关度较小，因而其所对应的差分隐私保护方法较其他索引更为简单，应用更为广泛。早期的方法采用完全四叉树[21]，树结构本身是完全公开的，只有每个节点所代表的本区域范围位置数目涉及用户隐私，因此其噪声注入方法比较简单，仅涉及对节点计数添加拉普拉斯噪声。因为增加或者删除某个位置，将改变由该位置所在的叶子节点到根节点路径上所有中间节点的计数，所以按照差分隐私的序列组合性(定义3)，总体隐私预算为路径上各个节点的隐私预算之和，且与树的高度密切相关。假定四叉树高度为h，则第i层的树节点的计数注入数量为Lap(1/εi)的Laplace噪音，当对于各层的隐私预算配额采用平均分配策略时，各层的隐私预算相同，均为ε i =ε/h。其和满足总体隐私预算：
由于各个节点所添加的随机噪声规模相同，因此父节点计数所含噪声期望小于所有子节点随机噪声期望值之和。在响应用户的计数查询时，应采用类似索引树的查询模式，自上而下在四叉树中搜索匹配该查询的节点或节点集合，并根据节点加噪计数进行回答，以最小化结果误差。此外，上述方案还可以从多个角度进行优化：
(1) 各层的隐私预算配额改用几何分配策略，降低总体节点方差；
(2) 可以采用最小二乘法对所有节点的加噪计数进行后置处理，当父子节点之间计数满足一致性约束时，可得到无偏最佳估计值。该处理步骤需要完成自上而下、自下而上、再自上而下的3次树遍历，以提高处理复杂度为代价提升查询结果准确度。
文献[22]提出一种基于不完全四叉树的位置发布方法PrivTree，如图1所示，对高维空间位置数据进行更为合理的划分，摆脱了对树高h的参数依赖，并采用局部敏感度和引入近似误差δ降低噪声误差。较文献[21]方法在Gowalla数据集上的准确率提升近20%。
虽然完全四叉树易于实现差分隐私分析，但它同时也带来很大弊端。尤其是当位置点数据分布极端不均衡时，基于完全四叉树的方法将增加树的高度并形成大量空节点，导致总体注入过多噪声。此时若能采用某种形式的平衡树，更为均衡地实现空间划分，则可以有效降低层次树的高度。单维直方图数据发布中的经典方法之一是为数据集构建K叉平均树[23]，划分使得直方图各个区间数目较为均衡，再通过最优线性无偏估计对其进行一致性修正，降低中间节点所代表的区间查询噪声误差。类似地，在2维及多维直方图数据发布时，可以采用KD-树索引，每次选择一个中位数所代表的超平面对空间进行均衡划分。由于KD树索引中位置点分布影响树结构，所以隐私预算不仅包括为节点计数注入噪声的配额，还包括用于树结构的随机化的配额。总体隐私预算为：
节点计数可以直接添加拉普拉斯噪音，此处不再赘述。而树结构的随机化主要是指中位数选取的随机化。文献[21]给出了多种中位数噪声方法。例如：
(1)添加拉普拉斯噪声方法：计算出每个区间的敏感度 σs(median)，并在区间中位数基础上添加Lap(2σs(median)/ε)噪声。为提高可用性，采用基于局部敏感度包络的平滑敏感度(smooth-sensitivity)替代全局敏感度，使之满足( ε,δ)−近似差分隐私；
(2)采用指数机制加噪。设置rank(·)函数返回所有数据排序后的序号。越接近中位数的点其打分函数分值越高，被选择的概率也越大。由于排序函数的敏感度为1，所以某个位置x被选中作为加噪中位数的概率可表示为

此外文献[24]中提出的启发式KD树划分方法可供参考。需要指出的是，由于KD索引树是二叉树，其扇出小于四叉树中节点扇出(fanout为4)，导致树高相差近1倍。所以，若不做特殊处理则其误差反而会大于四叉树。只有通过扁平化处理，提升KD树中索引节点的扇出，才能真正达到其设计目的。
3.1.2 轨迹直方图隐私发布
一个朴素的空间轨迹直方图把底层的空间分解成网格单元，每个单元记录轨迹片段数量，可以提供单元级别的空间轨迹查询。但由于各单元之间彼此独立无关，轨迹在多个单元中的子轨迹会被重复计数，导致大范围轨迹聚集查询误差较大。因而EH(Euler Histograms)模型及其变种DEH(Distributed Euler Histogram)模型[25]，以及层次化改进模型EHT(Euler Histograms Tree)模型[26]等作为其改进模型，都可以在某种程度上降低子轨迹重复技术带来的误差，更好地支持矩形空间聚集查询。以EH模型为例，每个单元内的子轨迹数量被记录为面计数(称为Face或F)，同时，穿过单元4个边界的轨迹数目被记录为边记录(称为Edge或E)。当需要准确计算出指定区域内的轨迹数目时，将其拆分为针对面计数F和边计数E的两个子查询，然后计算两者返回值之间的差值，即：q (H)=qF(F)−qE(E)。
一个朴素的空间直方图把底层的空间分解成网格单元，每个单元记录位置或轨迹片段数量，可以提供单元级别的空间信息查询。由于经典的空间位置大多为2维数据，所以空间位置发布多为2维直方图。空间数据频度直方图可用于空间信息聚集查询，如查询某个区域的用户或者轨迹数量，统计通过一个路段的所有车辆总数，或者一个城市中任意街区的智能手机的使用者数量等。典型的空间直方图包括空间位置直方图与轨迹直方图，分别用于支持空间位置计数查询与空间轨迹计数查询。

图 1 基于四叉树的差分隐私位置计数查询方法

图 2 EH模型功能示意图




相应地，对该节点的隐私因子的估计值为：εv = /hv。 其中为当前剩余隐私因子。由于降低了注入噪声规模，N-gram方案消除了对轨迹长度的限制，可以支持长达14,795个状态的轨迹[31]，top-K频繁子轨迹发现召回率(TPR)提升效果也非常显著。但其所能支持的数据状态空间仍然十分有限。
为了解决实际应用中位置网格粒度选择的困境，以及轨迹分布不均衡问题，文献[32,33]提出了一种折中性的多层次前缀树的方法(Differentially Private Trajectory, DPT)，采用不同层次代表不同粒度的地理网格结构。通过层次参考系统映射(hierarchical reference systems mapping)，将轨迹按照速度特性分解表示为多个轨迹片段，分别被映射到不同层次的参考系统中，从而兼顾了不同类型轨迹的粒度需求。例如，当运动轨迹呈现出运动速度快，轨迹较为平缓特点时，采用高层的参考系统，节点精度较低；反之则映射于底层参考系统中，节点精度高。通过在不同层次上的分解与映射，极大地降低了描述一条轨迹所需的坐标点数目。相应地，DPT方法为轨迹数据集构造了一个前缀树集合，HRS→ {T1,T2,···,TM}。其中的每个前缀树只负责记录某一个层次下的子轨迹序列集。树中每个节点都有两种类型子节点；一类是在同一层次系统下的9个子节点，分别代表下一步可能的9个移动方位；另一类是M个子节点，代表下一步可能移动到的其他参考系统。假定某条轨迹被分为如下3个片段，分别记录于RS2, RS3和RS2参考系统对应的前缀树中。图5表示了该轨迹片段在RS2前缀树中的存储方式。
(1) (4, 1)2, (5, 1)2, (2, 0)3；
(2) (2, 0)3, (3, 0)3, (4, 0)3, (5, 0)3, (6, 1)3, (6,1)3, (6, 1)3, (13, 3)2；
(3) (13, 3)2, (13, 4)2, (13, 5)2, (14, 6)2。
在图5中root被视为第0层。坐标点(4, 1)2令位于第1层的节点“(4, 1)”计数加1操作；类似地，二元序列“(4, 1)2(5, 1)2”令第2 层的节点“(4, 1)(5, 1)”的计数加1；三元序列“(4, 1)2(5,1)2(2, 0)3”比较特殊：因为坐标(2, 0)3属于RS3，所以该序列最终令第3层节点“(4, 1)(5, 1)RS3”的计数加1。按照上述规则可以将整条轨迹中相应部分添加到RS2前缀树中。

图 4 基于N-gram的搜索树方法

图 5 轨迹片段在RS2前缀树中的表达示例
前缀树节点添加噪音以及剪枝等步骤与前面类似，不再赘述。值得一提的是，为了降低总体误差，DPT方案不仅为节点添加随机噪声，还选择随机丢弃部分前缀树，因此方案误差由两部分构成：。前者为每个前缀树节点添加拉普拉斯噪声引入的误差，后者是随机丢弃一部分前缀树造成的误差。相应地，整体隐私预算分配为两部分，ε=εs+εr，其中εs是用于为选择树添加随机噪声，εr用于对前缀树节点计数添加Laplace噪声。为了实现误差Error最小化，即通过搜索算法对参数F+(前缀树集合)与k(前缀树高度)的选择优化，得到参数F+和k的最优解或近似最优解。DPT方案较早期方法[30,31]显著提升了轨迹直径分布的准确度、起终点匹配度以及F1-score等指标，在相同的隐私预算下提高了轨迹数据的可用性。
3.2.2 基于聚类的差分隐私轨迹发布
差分轨迹隐私发布中另一类重要方法基于位置聚类的思想。在位置精度高、候选位置集合规模巨大，且每个位置数据相对稀疏的场景下，该类方法较树重构方法更为通用。考虑的问题为：若每条轨迹可被抽象表示为一个由位置与时间构成的二元组序列， Ti =(l1,t1)→(l2,t2)→···→(ln,tn)，如何对轨迹集合T进行净化处理，使其成为满足差分隐私要求的可发布的数据集 T′？
基于聚类的轨迹发布仍然采用了分阶段处理的思想[34]，按照时间将长度为|T|的轨迹集处理分为|T|个阶段，在每个阶段对所有位置进行聚类分组，用每个聚类中心点替代该聚类中所有真实位置点，产生扰动后的轨迹数据集。正由于采用计算生成的聚类中心点取代了前缀树方法中的真实位置，降低了候选位置数目，所以基于聚类的轨迹发布可以在支持更高精度的位置表示的同时，避免状态爆炸问题。
可以看出，有两项处理需要引入随机化噪声，分别是：(1)聚类中心点的随机化；(2)对轨迹计数的随机化。相应的隐私预算包括两部分ε =ε1+ε2。后者噪声注入方法是拉普拉斯机制并进行一致性修订，不再赘述。下面介绍聚类分组随机化处理方法。
采用经典聚类算法如k-means算法可以实现位置点聚类。若给定了分组数量参数g，根据其聚类分配策略p，可不断迭代计算每个位置点与各聚类分组的距离，修订其所属分组，最终得到稳定的g个聚类分组。在聚类中心点的随机化时，不再采用上述经典聚类分配策略，可以随机分组，采用指数机制在所有可能分配策略中选择分配策略p˜。
若定义在某个随机分配策略下，每个位置点到其所属聚类分组的距离均值为 MeanDist(p˜)，则根据k-means原理显然有M eanDist(p˜)≥MeanDist(p)。可以将打分函数定义为式(11)的形式，采用指数机制选择聚类分组策略。与经典分配策略接近的策略更大概率会被选中，也可以理解为距离接近的点更高概率会被聚类在一组

在上述步骤中参数g(聚类分组数目)的选择是一个关键因素。一般来说，g取值增大，则分组中的位置更趋紧密，聚类中心与位置的距离更小，因而数据可用性更好。但同时应该注意，随着g取值增大，不同轨迹合并的几率下降，每条轨迹的计数相应减少了。因而，g取值过大时反而会在添加Laplace噪音后降低数据可用性。因而g的取值应在一定合理区间，并与轨迹长度|T|及轨迹集大小n相关。
由于采用高斯机制对所有的分配策略打分的过程时间复杂度是O(|T|mgng)，其中n为所有用户轨迹总数，m为维度，分配策略数量为n g种，在实现中耗时过高。可以通过选择指数机制中权值较高者作为候选项，减少分配策略的候选空间来降低复杂度，提高算法效率[35]。
图6描述了该方案1次执行过程。首先将集合D根据时间点分为|T |个子集L i,(1 ≤i ≤|T|)；然后设置聚类的分组数目参数g，并基于k-means算法依次对每个子集L i 采用聚类分配策略p˜，将其分为g个分组。最后，用聚类后的中心点代替原始轨迹数据集D的轨迹点，从而得到扰动后的轨迹集S。在图6中，g=2, |T|=4。
轨迹聚类方法满足ε-差分隐私。即使攻击者掌握了D的相邻数据集 D′ ( D′包含除轨迹T以外的其他所有轨迹),也无法通过发布的数据集D得知轨迹T的信息。
3.3 连续轨迹发布隐私保护模型

图 6 轨迹聚类方法过程示意图
3.2节所述各类轨迹隐私保护方法在ε-DP模型框架下，将轨迹发布视为一系列连续位置的发布，在每个步骤添加适当的噪声(相当于每个轨迹点注入Lap(|L|/ε)的噪声，|L|为轨迹长度)，利用的组合特性确保总体满足隐私预算为ε的差分隐私要求。为了保持发布数据的可用性，要求轨迹集中任何轨迹满足最大长度约束，这极大地限定了发布数据的使用范围。而连续发布的轨迹数据之间存在的高度关联性使得该问题变得更加困难。本小节介绍适用于理论上无限长用户连续轨迹数据发布方法，旨在解决如下连续数据动态发布问题：如果从t1,t2，至ti–1时刻的所有已发布位置数据(已注入噪音)均满足隐私保护模型要求，那么如何对ti时刻的位置信息添加随机化噪声，使得该时刻发布的数据也同时满足隐私保护模型要求？
3.3.1 本地化差分隐私模型下的轨迹隐私保护
本地化差分隐私(LDP)的目标在于解决服务器不可信场景下数据安全采集与分析问题。与经典集中式差分隐私模式不同，在LDP模式下，用户提交数据之前先于本地进行随机化加噪处理，然后于服务器端进行统计与分析。目前LDP被广泛应用于热门网址发现[36]、常用表情图标筛选、热点频率统计[37]等场景，以实现用户隐私保护的数据采集与分析。
同理，若用户在位置轨迹信息采集时将地理位置交与不可信服务器，则等同于已经失去位置隐私，后续保护机制也失去了意义。但是技术实现上并不能直接应用已有的Rappor[36], SH[37]等经典LDP算法，原因在于，连续提交的多个数据之间显然存在某种程度的关联，用户不可能产生随机移动。例如，受到移动速度与路网结构等因素影响，在已知用户在ti–1时刻位置的前提下，用户在ti时刻可能出现的位置范围就十分有限。一方面，如果添加噪声时未考虑这些因素，则攻击者可以利用掌握的用户历史位置信息及位置转移概率来推测当前准确位置，使得原有ε-DP机制失效。另一方面，若考虑所有位置之间的迁移可能性，容易导致噪音添加过度，降低数据可用性。
针对上述问题，文献[38]在对攻击者能力进行合理假设基础上提出了一种LDP轨迹隐私保护方法，对攻击者能力予以最大假定。假设攻击者有能力掌握(1)用户轨迹的1阶马尔科夫模型矩阵M; (2)用户在ti–1时刻以及之前的所有真实地理位置。
当攻击者看到用户ti时刻发布的加噪位置yi时，存在P r[xi|M,yi,xi−1]的概率可以推测出用户的真实地理位置xi。在此假定下用户的隐私保护需求为：在ti时刻发布的用户地理位置yi对于任意一组可能的候选地理位置xi与，都满足式(12)约束

若无特殊限定，要求在所有用户可能位置集合上，且对于任意一组位置xi与都严格满足上述差分隐私约束，那么为了满足ε-DP所添加的噪声，将导致地理位置坐标随机偏移过大而不可用。因为一旦ti时刻发布的加噪地理位置yi(yi =Noise(xi,xi−1,xi−2,···))与ti–1时刻的真实位置xi-1在语义和位置连续性等方面存在巨大偏差，位置yi就失去了价值，与之相关的LBS服务也将失效。
为了解决上述问题，文献[38,39]从以下几方面着手改进，提高了发布数据可用性。
(1) 提出了δ-位置集合(δ-Location Set)概念限定了xi与的取值范围。具体来说，根据用户在任意时刻ti的真实地理位置，为其产生相对应的δ-位置集合，它既是用户在该时刻最可能处于的位置集合，也是攻击者可用于推测地理位置的选择范围。在该集合中随机选择某位置替换真实的地理位置进行发布。定义如下。
定义8(δ-位置集合 δ-location set) 令Pr[xi|M,xi−1]表示t时刻用户处于位置xi的先验概率，若该值不小于1–δ，则将其添加到t时刻的δ-位置集合 ∆Xt中。用公式表示为


表 2 基于差分隐私保护的轨迹信息发布方法比较

4 未来研究挑战
虽然目前差分隐私在地理位置、轨迹等空间数据发布上已获取了很大进展，但随着应用场景的不断变化，以及AI领域新技术的不断涌现，未来仍然有许多关键性研究问题有待进一步解决。下面列举几个可深入研究的方向供研究人员参考：
(1) 连续发布轨迹数据差分隐私保护
在差分隐私框架下实现轨迹连续发布往往导致隐私预算快速耗尽。随着发布次数的增长，累积噪声迅速增大，发布结果的可用性急剧下降。现有的替代性的方法包括采用动态的局部敏感度、平滑敏感度取代全局敏感度[29]，采用流数据滑动窗口进行截断分析处理[44]等。此外，连续轨迹数据之间的关联性也往往需要添加额外噪声，进一步降低数据可用性。近年来在差分隐私领域，以PufferFish隐私为代表的通用模型受到越来越多的关注，取代经典差分隐私模型用于关联数据、局部敏感数据的差分隐私保护。但是满足PufferFish隐私的轨迹数据发布方法，以及高效的噪声生成机制仍十分有限，有待深入研究。
(2) 深度学习与轨迹差分隐私保护框架
基于神经网络的机器学习技术在图像、自然语言处理等领域的成功极大地推动了该学科技术的发展，对隐私保护技术领域也产生了重要影响。Abadi等人[45]在Tenserflow框架下实现了支持差分隐私的随机梯度下降(SGD)算法，显示个体数据差分隐私保护并不会过多影响学习效率与效果。此外，研究者提出了一系列基于循环神经网络(Recurrent Neural Network, RNN)的轨迹重识别方法，基于轨迹-用户交叉熵损失函数[46]、双目标神经网络[47]、注意力机制[48]、seq2seq模型[49]等训练RNN编码器，得到了具有良好抗噪能力的轨迹表示。记录层级差分隐私保护并不足以实现轨迹身份匿名。深入理解深度学习与差分隐私技术的相互作用，构建新型差分隐私保护框架，是未来值得探究的重要方向之一。
(3) 支持自主定义隐私预算的轨迹数据发布
在差分隐私轨迹数据发布中，隐私预算ε的设置与选取既与数据质量密切相关，也与用户对个人隐私信息的重视程度息息相关。如何平衡服务质量与公开隐私数据之间的博弈关系，属于用户个性化选择范畴。目前已有若干个性化差分隐私保护方法，实现了中心模型下的交互式均值等统计信息发布[50,51]，以及本地模型下的离散分布估计[52]与热门地理位置挖掘[53]等。但是如何在个人轨迹采集与发布中实现对多隐私因子支持，在允许用户自主控制其位置数据采样频率与质量的同时保证服务质量，则有待未来结合应用进一步分析与研究。
5 结束语
差分隐私保护技术采用了攻击者能力最大化假定、安全性强，不受新型攻击出现的影响，近年来被越来越多地应用于位置、轨迹数据安全发布，取得了丰富的成果。从实际应用角度看，差分隐私轨迹发布算法的设计重点在于，如何在保护隐私的同时兼顾可用性，合理设计隐私预算因子，降低实现机制算法复杂度，生成高质量的净化数据集。本文对基于差分隐私理论的轨迹隐私保护技术进行了总结，讨论了轨迹数据持续发布、本地化隐私保护、深度学习等因素带来的问题与挑战，希望能对本领域的研究者有所帮助。
参 考 文 献
[1]BAO Jie, HE Tianfu, RUAN Sijie, et al. Planning bike lanes based on sharing-bikes’ trajectories[C]. The 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, Canada, 2017: 1377–1386.
[2]YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al. Tdrive: Driving directions based on taxi trajectories[C]. The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, San Jose, USA, 2010:99–108.
[3]TOCKAR A. Riding with the stars: Passenger privacy in the NYC Taxicab dataset[EB/OL]. https://research.neustar.biz/author/atockar/, 2018.
[4]W-Pwn. 健身APP泄露军事机密, 包括中国南海[EB/OL]. https://zhuanlan.zhihu.com/p/33405626, 2018.
[5]CHEN Zhenyu, FU Yanyan, ZHANG Min, et al. The deanonymization method based on user spatio-temporal mobility trace[C]. The 19th International Conference on Information and Communications Security, Beijing, China,2017: 459–471.
[6]ABUL O, BONCHI F, and NANNI M. Never walk alone:Uncertainty for anonymity in moving objects databases[C].The 24th IEEE International Conference on Data Engineering, Cancun, Mexico, 2008: 376–385.
[7]TERROVITIS M, POULIS G, MAMOULIS N, et al. Local suppression and splitting techniques for privacy preserving publication of trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(7): 1466–1479.doi: 10.1109/TKDE.2017.2675420.
[8]YAO Lin, WANG Xinyu, WANG Xin, et al. Publishing sensitive trajectory data under enhanced l-diversity model[C]. The 20th IEEE International Conference on Mobile Data Management, Hong Kong, China, 2019:160–169.
[9]冯登国. 大数据安全与隐私保护[M]. 北京: 清华大学出版社,2018: 194–219.
[10]DWORK C. Differential privacy[C]. The 33rd International Colloquium on Automata, Languages and Programming,Venice, Italy, 2006: 1–12. doi: 10.1007/11787006_1.
[11]ZHU Tianqing, LI Gang, ZHOU Wanlei, et al. Differentially private data publishing and analysis: A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2017,29(8): 1619–1638. doi: 10.1109/TKDE.2017.2697856.
[12]MCSHERRY F and TALWAR K. Mechanism design via differential privacy[C]. The 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, USA,2007: 94–103.
[13]MCSHERRY F D. Privacy integrated queries: An extensible platform for privacy-preserving data analysis[C]. The 2009 ACM SIGMOD International Conference on Management of Data, Rhode Island, USA, 2009: 19–30.
[14]DWORK C, KENTHAPADI K, MCSHERRY F, et al. Our data, ourselves: Privacy via distributed noise generation[C].The 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Peterbury,Russia, 2006: 486–503.
[15]KIFER D and MACHANAVAJJHALA A. No free lunch in data privacy[C]. The 2011 ACM SIGMOD International Conference on Management of Data, Athens, Greece, 2011:193–204.
[16]GEHRKE J, LUI E, and PASS R. Towards privacy for social networks: A zero-knowledge based definition of privacy[C]. The 8th Conference on Theory of Cryptography,Providence, USA, 2011: 432–449.
[17]KIFER D and MACHANAVAJJHALA A. Pufferfish: A framework for mathematical privacy definitions[J]. ACM Transactions on Database Systems, 2014, 39(1): Article No.3. doi: 10.1145/2514689.
[18]DWORK C. A firm foundation for private data analysis[J].Communications of the ACM, 2011, 54(1): 86–95. doi:10.1145/1866739.1866758.
[19]DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]. The 3rd Theory of Cryptography Conference, New York, USA, 2006:265–284.
[20]QARDAJI W, YANG Weining, and LI Ninghui.Differentially private grids for geospatial data[C]. The 29th IEEE International Conference on Data Engineering,Brisbane, Australia, 2013: 757–768.
[21]CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al.Differentially private spatial decompositions[C]. The 28th IEEE International Conference on Data Engineering,Washington, USA, 2012: 20–31.
[22]ZHANG Jun, XIAO Xiaokui, and XIE Xing. PrivTree: A differentially private algorithm for hierarchical decompositions[C]. The 2016 International Conference on Management of Data, San Francisco, USA, 2016: 155–170.
[23]HAY M, RASTOGI V, MIKLAU G, et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2010,3(1/2): 1021–1032.
[24]XIAO Yonghui, XIONG Li, and YUAN Chun. Differentially private data release through multidimensional partitioning[C]. The 7th Workshop on Secure Data Management, Singapore, 2010: 150–168.
[25]XIE Hairuo, TANIN E, and KULIK L. Distributed histograms for processing aggregate data from moving objects[C]. 2007 International Conference on Mobile Data Management, Mannheim, Germany, 2007: 152–157.
[26]XIE Hairuo, TANIN E, KULIK L, et al. Euler histogram tree: A spatial data structure for aggregate range queries on vehicle trajectories[C]. The 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science, Dallas/Fort Worth, USA, 2014: 18–24.
[27]GHANE S, KULIK L, and RAMAMOHANARAO K.Publishing spatial histograms under differential privacy[C].The 30th International Conference on Scientific and Statistical Database Management, Bozen-Bolzano, Italy,2018: Article No.14.
[28]HARDT M, LIGETT K, and MCSHERRY F. A simple and practical algorithm for differentially private data release[C].Advances in Neural Information Processing Systems, Lake Tahoe, USA, 2012: 2339–2347.
[29]TO H, NGUYEN K, and SHAHABI C. Differentially private publication of location entropy[C]. The 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Burlingame, USA, 2016:Article No. 35.
[30]CHEN Rui, FUNG B C M, DESAI B C, et al. Differentially private transit data publication: A case study on the montreal transportation system[C]. The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, 2012: 213–221.
[31]CHEN Rui, ACS G, and CASTELLUCCIA C. Differentially private sequential data publication via variable-length ngrams[C]. The 2012 ACM Conference on Computer and Communications Security, Raleigh, USA, 2012: 638–649.
[32]HE Xi, CORMODE G, MACHANAVAJJHALA A, et al.DPT: Differentially private trajectory synthesis using hierarchical reference systems[J]. The VLDB Endowment,2015, 8(11): 1154–1165. doi: 10.14778/2809974.2809978.
[33]HE Xi, RAVAL N, and MACHANAVAJJHALA A. A demonstration of VisDPT: Visual exploration of differentially private trajectories[J]. The VLDB Endowment,2016, 9(13): 1489–1492. doi: 10.14778/3007263.3007291.
[34]HUA Jingyu, GAO Yue, and ZHONG Sheng. Differentially private publication of general time-serial trajectory data[C].2015 IEEE Conference on Computer Communications, Hong Kong, China, 2015: 549–557. doi: 10.1109/INFOCOM.2015.7218422.
[35]LI Meng, ZHU Liehuang, ZHANG ZIjian, et al. Achieving differential privacy of trajectory data publishing in participatory sensing[J]. Information Sciences, 2017,400/401: 1–13. doi: 10.1016/j.ins.2017.03.015.
[36]ERLINGSSON Ú, PIHUR V, and KOROLOVA A. Rappor:Randomized aggregatable privacy-preserving ordinal response[C]. The 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, USA,2014: 1054–1067.
[37]BASSILY R and SMITH A. Local, private, efficient protocols for succinct histograms[C]. The 47th Annual ACM Symposium on Theory of Computing, Portland, USA, 2015:127–135.
[38]XIAO Yonghui and XIONG Li. Protecting locations with differential privacy under temporal correlations[C]. The 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, USA, 2015: 1298–1309.
[39]WANG Shuo, SINNOTT R, and NEPAL S. Protecting the location privacy of mobile social media users[C]. IEEE International Conference on Big Data, Washington, USA,2016: 1143–1150.
[40]HARDT M and TALWAR K. On the geometry of differential privacy[C]. The 42nd ACM Symposium on Theory of Computing, Cambridge, UK, 2010: 705–714.
[41]SONG Shuang, WANG Yizhen, and CHAUDHURI K.Pufferfish privacy mechanisms for correlated data[C]. The 2017 ACM International Conference on Management of Data, Chicago, USA, 2017: 1291–1306.
[42]OU Lu, QIN Zheng, LIAO Shaolin, et al. An optimal pufferfish privacy mechanism for temporally correlated trajectories[J]. IEEE Access, 2018, 6: 37150–37165. doi:10.1109/ACCESS.2018.2847720.
[43]DWORK C and ROTH A. The algorithmic foundations of differential privacy[J]. Foundations and Trends® in Theoretical Computer Science, 2014, 9(3/4): 211–407. doi:10.1561/0400000042.
[44]KELLARIS G, PAPADOPOULOS S, XIAO Xiaokui, et al.Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014,7(12): 1155–1166. doi: 10.14778/2732977.2732989.
[45]ABADI M, CHU A, GOODFELLOW I, et al. Deep learning with differential privacy[C]. The 2016 ACM SIGSAC Conference on Computer and Communications Security,Vienna, Austria, 2016: 308–318.
[46]GAO Qiang, ZHOU Fan, ZHANG Kunpeng, et al.Identifying human mobility via trajectory embeddings[C].The 26th International Joint Conference on Artificial Intelligence, Macao, China, 2017: 1689–1695.
[47]WANG Guowei, LIAO Dongliang, and LI Jing. Complete user mobility via user and trajectory embeddings[J]. IEEE Access, 2018, 6: 72125–72136. doi: 10.1109/ACCESS.2018.2881457.
[48]ZHOU Fan, GAO Qiang, TRAJCEVSKI G, et al.Trajectory-user linking via variational autoencoder[C]. The 27th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018: 3212–3218.
[49]LI Xiucheng, ZHAO Kaiqi, CONG Gao, et al. Deep representation learning for trajectory similarity computation[C]. The 34th IEEE International Conference on Data Engineering, Paris, France, 2018: 617–628.
[50]JORGENSEN Z, YU Ting, and CORMODE G.Conservative or liberal? Personalized differential privacy[C].The 31st IEEE International Conference on Data Engineering, Seoul, South Korea, 2015: 1023–1034.
[51]LI Haoran, XIONG Li, JI Zhanglong, et al. Partitioningbased mechanisms under personalized differential privacy[C]. The 21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, Jeju, South Korea, 2017:615–627.
[52]YE Yutong, ZHANG Min, FENG Dengguo, et al. Multiple privacy regimes mechanism for local differential privacy[C].The 24th International Conference on Database Systems for Advanced Applications, Chiang Mai, Thailand, 2019:247–263.
[53]CHEN Rui, LI Haoran, QIN A K, et al. Private spatial data aggregation in the local setting[C]. The 32nd IEEE International Conference on Data Engineering, Helsinki,Finland, 2016: 289–300.
Research on Differentially Private Trajectory Data Publishing
FENG Dengguo①② ZHANG Min①② YE Yutong①
①(Trusted Computing and Information Assurance Laboratory, Institute of Software,Chinese Academy of Sciences, Beijing 100190, China)
②(State Key Laboratory of Computer Science, Institute of Software,Chinese Academy of Sciences, Beijing 100190, China)
Abstract: Securely sharing and publishing location trajectory data relies on support of location privacy protection technology. Prior to the advent of differential privacy, K-anonymity and its derived models provide a means of quantitative assessment of location-trajectory privacy protection. However, its security relies heavily on the background knowledge of the attacker, and the model can not provide perfect privacy protection when a new attack occurs. Differential privacy effectively compensates for the above problems, and it proves the level of privacy protection based on rigorous mathematical theory and is increasingly used in the field of trajectory data privacy publishing. Therefore, the trajectory privacy protection technology based on differential privacy theory is studied and analyzed, and the methods of spatial statistical data publishing are introduced such as location histogram and trajectory histogram, the method of trajectory data set publishing and the model of continuous real-time location release privacy protection. At the same time, the existing methods are compared and analyzed, the key development directions are put forward in the future.
Key words: Privacy preserving; Differential privacy; Location big data; Trajectory big data; Data publishing
中图分类号：TN918
文献标识码：A
文章编号：1009-5896(2020)01-0074-15
DOI: 10.11999/JEIT190632
收稿日期：2019-08-26；改回日期：2019-11-30；网络出版：2019-12-05
*通信作者： 冯登国 feng@is.iscas.ac.cn
基金项目：国家自然科学基金(U1636216)
Foundation Item: The National Natural Science Foundation of China (U1636216)
冯登国：男，1965年生，中国科学院院士，研究员，研究方向为网络与信息安全.
张 敏：女，1975年生，研究员，研究方向为数据安全与隐私保护.
叶宇桐：男，1993年生，博士生，研究方向为差分隐私保护技术.