许志凯　张宏莉　余翔湛

摘 要： 随着智能终端的普及和无线通信技术的发展，基于位置的服务已渗入到人们的日常生活当中这些服务在给人们的日常生活带来便利的同时，也带来隐私泄漏的风险。针对轨迹数据的推理攻击不仅可得出用户可分析出目标用户的家庭住址、工作地点等敏感位置信息，甚至可推测出用户的生活习惯、健康状态、宗教信仰等隐私信息。轨迹隐私能否得到妥善保护已成为制约移动互联网发展的瓶颈问题。本文对已有的轨迹隐私保护方法进行了分类描述，并分析已有工作的优缺点，最后指明未来的研究方向。

关键词：轨迹隐私；隐私保护，位置隐私，网络安全

中图分类号：TP391.41 文献标识号：A

0 引言

随着智能终端的普及和无线通讯技术的发展，基于位置的服务（Location-based Service，LBS）已渗入到人们的日常生活当中。然而，许多基于位置的服务，如电子地图、运动计步、移动广告，需用户实时提交自己的位置信息。这些服务可为人们的生活带来巨大的便利。以电子地图服务提供商Google地图、百度地图为例，这些应用不仅可为用户提供实时交通导航，还可为用户提供实时路况信息，并规划最优线路。然而，这些服务也带来隐私泄漏的风险，在使用这类服务时，LBS用户需实时地将自己的位置信息提交给LBS服务器，但这些轨迹数据往往含有丰富的时空信息。针对轨迹数据的推理攻击不仅可得出用户在什么时间去过什么位置，还可分析出目标用户的家庭住址、工作地点等敏感位置信息，甚至可推测出用户的生活习惯、健康状态、宗教信仰等隐私信息。因此，轨迹隐私保护受到用户及研究者的广泛关注。

针对上述问题，本文介绍基于位置的服务，在此基础上分别综述位置隐私保护技术的主要研究现状及存在的问题，同时，根据目前研究的不足指出未来可能的研究方向。

1 基于位置的服务

图1表示了基于位置服务的一般架构，该架构包含3个实体；

1）为LBS用户提供定位服务的导航定位基础设施，主要包括GPS卫星、无线网络基站、WIFI等。

2）持有移动智能终端的LBS用户（本文的研究中将LBS用户与移动智能终端可视为同一主体）。移动智能终端可通过硬件（如GPS芯片）和软件（如基站信号定位、WIFI指纹定位）技术确定该LBS用户所在地理位置，并通过无线信号与LBS服务器进行通信。

3）为LBS用户指定基于位置服务的服务提供商，如百度地图、Google地图、大众点评等。

连续型LBS服务指的是用户需实时提交的自己的位置信息才能获取到相应服务的LBS服务，这类服务主要包括智能导航服务、无人驾驶汽车、基于位置的新闻（广告）推送、运动计步及某些社交类APP（如定位附近与我兴趣相同的人）等。 以智能导航服务为例，一次典型的连续型LBS服务如图1所示。具体可做如下阐释：

1）用户通过定位服务如GPS等获取自身位置；

2）用户将自身位置及所需的服务请求发送给LBS服务提供商；

3）LBS服务提供商根據用户当前的位置及道路拥塞情况为用户规划行驶线路，并提供导航服务；

4）重复过程（1）至（3）直到满足用户的服务要求，如完成一次从地点A到地点B的导航服务。

2 威胁模型

在轨迹隐私保护的研究中，研究者一般认为GPS等定位设备是可信的，即用户可获取其位置坐标的过程是安全的，而LBS服务提供商是不可信的， 即LBS服务提供商可能会利用用户的轨迹信息挖掘用户的隐私信息。这是因为用户在将位置数据提交给LBS提供商后没有能力验证服务提供商是否可信，其次可信的服务提供商也可能会被恶意第三方攻击，导致用户位置隐私的泄漏。

3 轨迹隐私保护技术

近些年轨迹隐私保护受到研究者的广泛关注。根据用户的查询请求在到达LBS服务器之前变换方式的不同，当前的轨迹隐私保护方法可分为以下3类：

1）基于k匿名泛化的方法；

2）基于噪声数据的方法；

3）基于动态假名的方法。

3.1 基于k匿名泛化的轨迹隐私保护技术

K匿名泛化法[1]是一种经典的位置隐私保护技术。其基本思想是：在发送服务请求时，以一块空间区域代替用户的精准位置，即通过降低用户位置的精度的方式满足用户的隐私需求。部分研究者[2-3]将k匿名泛化应用到轨迹隐私保护中。一个直观的思路是将连续的2次查询视为2个独立的LBS服务请求，即分别为这2次查询构建匿名空间。但这种方法易受基于用户移动速度的推理攻击。针对上述问题，文献[2]基于用户移动速度构建匿名区域，以保证2个连续提交的匿名区域在速度上可达。然而，这一方法并不能充分保证用户的位置隐私。如图2所示，设A正在沿道路行驶，并在实时地查询周边的东北菜馆。图（a）是用户A在时刻ti生成的匿名空间，图（b）是用户A在时刻ti+1生成的匿名空间。 由于用户的移动方向与速度并不会完全相同，2块匿名空间中只包含用户A这一共同用户，即使两块匿名空间在速度上是完全可达的，攻击者也可通过比对2块匿名空间中的用户轻易地推测出用户A正在查询东北菜馆的信息。

综上问题论述开展研究，文献[3]认为在连续查询中，用户所提交的匿名区域应包含k个相同的用户。基于上述思想，有针对性地提出一种基于贪心的匿名区域构建算法，但通过该方法构造的匿名空间的面积会随着查询次数的上升而带来线性增加，从而形成严重的通信和计算开销。轨迹隐私保护需建立用户服务可用性的基础上， 如何在保护用户轨迹隐私的同时，尽可能的减小匿名空间的面积，提高基于服务的可用性，是该类方法未来的研究重点。

3.2 基于噪声数据的轨迹隐私保护方法

基于噪声数据的轨迹隐私保护方法[4-5]的实现思想是：在将用户的真实位置发送给LBS提供商的同时，以一定的策略生成若干虚假位置（dummy）并发送给LBS服务提供商作为用户真实位置的“掩护”，使攻击者无法分辨出用户真实位置。文献[6-8]针对连续查询查中的噪声数据添加机制进行了研究。文献[6]根据上一时刻的位置，按随机的速度和方向进行移动，并将获得的随机的位置点作为虚假位（dummy）进行发布，但这种方法生成的虚假位置点往往与用户真实的移动特征不符，且这些虚假位置点本身可能是一些实际上不可能到达的位置。针对这一问题，文献[7]在生成虚假位置点时加入了移动速度、路网等约束条件。文献[8]认为移动用户不会始终连续性移动，因此其在生成噪声数据点时会让移动对象根据周边的环境随机地产生一些停顿，以防止攻击者识别出噪声数据。然而，现实社会中，用户的行驶过程易遇到各种意外事件，如何处理这些意外事件，以生成更“真实”的噪声轨迹数据仍是一个巨大的挑战。此外，上述方法对攻击者的背景知识假设较为保守，当攻击者获得了从用户的日常行为中提取的背景知识时，即使用户的生成的噪声轨迹无法模拟出真实用户的移动轨迹，攻击者也可辨别出用户的真实轨迹。

3.3基于动态假名的方法的轨迹隐私保护方法。

基于假名的轨迹隐私保护方法的基本思想为：用户在发送基于位置的服务请求是以一个假名（pseudonym）来代替用户的真实身份。然而，研究者发现长时间使用同一假名并不能有效地保护用户的隐私，这是因为在路网中移动用户是公开可见的，一次偶然的隐私的泄漏就可能会导致用户整个移动轨迹的泄漏。因此，研究者[9]提出基于mix-zone的动态假名技术。

当前大部分研究工作围绕如何构建单个mix-zone区域展开。 文献[10]提出的MobiMix即是其中的代表性方法，对应基本思想为针对现实中可能被攻击者利用的背景知识，如移动速度，转移概率等，利用不规则的多边形及其组合建立混淆区域，使其适应当前场景，提高隐私保护程度。然而，在现实中只有同时部署多个混淆区域才能有效地保护用户的轨迹隐私，但在mix-zone内用户必须停止使用基于位置的服务，部署过多的mix-zone可能会严重影响服务质量。在此问题基础上，文献[11]提出一种基于组合优化的混淆区域部署方案。文献[12]进一步地考虑路网和交通流量的限制，提出一种基于整数规划的混淆区域部署方案，可在部署有限个混淆的区域的同时，尽可能提高用户的隐私保护水平。 单个mix-zone的设计目前已经有较为成熟的方案，如何在城市环境下协调部署多个mix-zone则是该方向未来的研究重点。

4 结束语

随着移动互联网的发展，轨迹隐私保护受到研究者的广泛关注。本文对近些年来该方向已有的研究成果进行了回顾，对比和分析了已有的方法和技术，并指出仍然存在的问题和可能的研究方向。整体来说，目前轨迹隐私保护的研究仍然处于起步阶段，仍有许多关键性问题尚未解决。

参考文献：

[1] SWEENEY L. k-anonymity： a model for protecting privacy[J]. International Journal on Uncertainty， Fuzziness and Knowledge-based Systems， 2002， 10（5）： 557-570.

[2] GHINITA G， DAMIANI M L， SILVESTRI C， et al. Preventing velocity-based linkage attacks in location-aware applications[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Washington： ACM ，2009： 246-255.

[3] WANG Y， XU D， HE X， et al. L2P2： Location-aware location privacy protection for location-based services[C]//Proceedings of IEEE INFOCOM. Orlando， Florida： IEEE， 2012：1996-2004.

[4] NIU B， LI Q， ZHU X， et al. Achieving k-anonymity in privacy-aware location-based services[C]//Proc. of IEEE INFOCOM. Toronto： IEEE， 2014：754-762.

[5] NIU B， LI Q， ZHU X， et al. Enhancing privacy through caching in location-based services[C]//Proc. of IEEE INFOCOM. Hong Kong： IEEE， 2015：1017-1025.

[6] KIDO H， YANAGISAWA Y， SATOH T. Protection of location privacy using dummies for location-based services[C]//Proc. of the 21st Intl Conf. on Data Engineering. Tokyo： IEEE， 2005： 1248?1248.

[7] SUZUKI A， IWATA M， ARASE Y， et al. A user location anonymization method for location based services in a real environment[C]//Proc. of the 18th ACM SIGSPATIAL Intl Symp. on Advances in Geographic Information Systems. Sana Jose：ACM， 2010： 398?401.

[8] KATO R， IWATA M， HARA T， et al. A dummy-based anonymization method based on user trajectory with pauses[C]//Proc. of the 20th ACM SIGSPATIAL Intl Conf. on Advances in Geographic Information Systems. Redondo：ACM， 2012： 249?258.

[9] FREUDIGER J， RAYA M， FLEGYHAZI M， et al. Mix-zones for location privacy in vehicular networks[C]//WiN-ITS. Vancouver， British Columbia， Canada：ACM， 2007：1-7.

[10] ALANISAMY B， LIU L. Attack-resilient mix-zones over road networks： architecture and algorithms[J]. IEEE Transactions on Mobile Computing， 2015， 14（3）： 495-508.

[11] FREUDIGER J， SHOKRI R， HUBAUX J P. On the optimal placement of mix zones[C]//Proc. of the 9th International Symposium on Privacy Enhancing Technologies （PETS09）. Seattle：IEEE， 2009：216–234.

[12] LIU X， ZHAO H， PAN M， et al. Traffic-aware multiple mix zone placement for protecting location privacy. In： Proceedings of the IEEE INFOCOM 2012. Orlando， Florida： IEEE， 2012： 972-980.