基于位置混淆的轨迹隐私保护方法

2018-08-03张少波刘琴王国军

通信学报 2018年7期

张少波，刘琴，王国军

基于位置混淆的轨迹隐私保护方法

张少波1，刘琴2，王国军3

（1. 湖南科技大学计算机科学与工程学院，湖南湘潭 411201；2. 湖南大学信息科学与工程学院，湖南长沙 410082；3. 广州大学计算机科学与教育软件学院，广东广州 510006）

在用户连续查询过程中，针对第三方匿名器结构中匿名难以保证用户隐私的问题，提出一种基于位置混淆的轨迹隐私保护方法。首先通过位置预测机制和假位置选择机制获得(−1)个查询混淆位置，然后将其与用户真实查询位置一起发送到不同匿名器形成匿名域后，再发送到LBS服务器进行查询，最后将获得的查询结果经不同匿名器返回给用户。该方法通过位置混淆来混淆用户的真实查询位置，使攻击者从单匿名器和LBS服务器不能推断出用户的真实轨迹，加强了对用户轨迹的隐私保护，也解决了单匿名器的性能瓶颈问题。安全分析表明了该方法的安全性，实验结果表明，该方法能减少用户与LBS服务器的交互次数以及单匿名器的开销。

轨迹隐私；位置混淆；位置预测；假位置；匿名器

1 引言

近年来，随着无线通信技术、移动互联网和定位技术的迅速发展，基于位置服务（LBS, location based service）已受到人们的广泛关注[1-2]。用户使用智能手机或掌上电脑，可以从应用商店下载基于位置服务的软件，如Twitter、Foursquare和Gowalla等。通过使用这些LBS应用软件发送查询到LBS服务器，可以获得用户需要的兴趣点（POI, point of interest），如交通导航信息、基于位置的广告、最近提供用户最喜欢的菜肴的餐厅等[3-4]。然而，用户在享受LBS带来极大生活便利和娱乐的同时，他们需要将这些查询请求提交给不可信的位置服务提供商（LSP, location service provider）。在连续LBS查询中，LSP根据收集的用户查询数据可以直接追踪到用户或推断出一些敏感的用户个人信息，如日常行为、家庭地址和社会关系等，这将严重导致用户个人隐私的泄露[5]。

为减少LBS中轨迹隐私泄露，国内外学者已提出一些轨迹隐私保护方法，它们主要采用2种基本结构[6]：基于点对点结构[7]和基于可信第三方（TTP, trusted third party）中心服务器结构[8]。在基于点对点结构中，Chow等[9]首次提出用户协作的点对点匿名方法，但该方法在寻找用户的过程中会产生较大开销。为减少开销，Shokri等[10]提出一种基于缓存的用户合作隐私保护方法，移动用户先在合作用户缓存中查找查询内容，当寻找失败时才通过协作的方式向LSP发出查询。Peng等[11]也提出了一种基于用户合作的轨迹隐私保护方法，通过向周围多跳邻居搜寻有价值的信息构造匿名区域，并发布假查询阻止攻击者重构用户轨迹。总体而言，该结构中移动用户发送查询前需进行一定的匿名或变换处理，这将会对移动终端产生较大的计算开销，同时也不能避免恶意用户的攻击。

然而基于TTP结构的方法也存在2个问题[17]：1)匿名器知道所有用户的精确位置和查询信息，如果它被攻破，这将会带来严重的安全威胁；2) 用户的查询请求和结果返回都必须经过匿名器，它承担着匿名、求精等繁重的计算任务，容易成为该结构中的性能瓶颈，同时也存在着中心点失效的风险。同时，在连续LBS查询过程中，基于TTP结构的匿名技术也很难保证用户的轨迹隐私。当用户发出连续LBS查询时，匿名器将每个查询点都模糊成满足用户需求的匿名域，然而攻击者可根据匿名域顺序重构用户的轨迹，并且攻击者将这些匿名域包含的用户进行对比，也能识别出真实用户。

2) 提出一种基于位置预测和假位置选择机制的混淆位置选择方法，通过位置预测机制，减少用户信息暴露给LBS服务器的风险，同时使用假位置选择机制增加对用户真实位置的混淆度，以提高用户隐私。

3) 提出一种基于多匿名器进行位置匿名的框架，用户查询请求和结果信息通过多个匿名器进行处理和转发，能有效解决TTP结构中单匿名器单点失效风险和性能瓶颈问题。

2 系统模型和相关定义

2.1 系统模型

图1 TPLO模型

TPLO方法的优点是攻击者不能从单个匿名器获得用户的真实轨迹，即使多个匿名器共谋，由于假位置混淆了用户的真实位置，攻击者也很难获得用户的轨迹。同时，通过混淆的用户位置并结合形成的匿名域发送到LBS服务器查询，LBS服务器不能获得用户的真实轨迹。LBS服务器查询的结果也同样经不同匿名器返回给用户。该方法中单个匿名器的失效并不影响系统的运行，能有效解决基于TTP结构中的单匿名器单点失效风险和性能瓶颈问题。根据系统中不同的角色和功能，系统主要由3类实体组成：用户、多匿名器和LBS服务器。

用户：携带具有全球定位、计算存储和无线通信功能智能终端的用户，他们可以通过多种方式（Wi-Fi或3G/4G移动通信网络）接入移动网络，并将不同时刻的请求信息连续发送到LBS服务器进行查询，以获得预期的服务。本方案中用户能根据自身位置预测后续的几个查询位置，并能在其周围找到一些合适的假位置。

LBS服务器：它是一个服务提供者，拥有大量与位置服务相关的服务和信息资源，能为用户提供各种数据服务。当LBS服务器收到用户发出的查询请求后，它在数据库搜索用户指定的POI，并将满足用户需求的查询结果返回给用户。

2.2 位置预测

2.3 安全模型

目前，在位置隐私保护的研究方面，比较典型的攻击模型主要有2种[18]：强攻击者攻击模型和弱攻击者攻击模型。

1) 强攻击者攻击模型

在强攻击者攻击模型中，攻击者能监视整个系统中特定用户的行为记录。攻击者通常不破坏协议流程，但它试图从自己获取的信息中分析得到用户的其他信息。TPLO方法中的匿名器和LSP可能成为潜在的强攻击者。匿名器在用户和LBS服务器之间进行匿名和转发信息，可能会对用户行为进行分析而造成用户信息泄露。LSP管理所有用户的LBS查询数据，且可能会因利益关系泄露LBS服务器中的敏感信息给第三方。

2) 弱攻击者攻击模型

在弱攻击者攻击模型中，攻击者具有很少的关于用户的背景知识，攻击者可以通过使用背景知识或其他一些攻击手段进行攻击，试图知道其他用户的更多个人敏感信息。通常攻击者通过侦听不安全的无线信道，试图窃听信息并推断出一些用户的敏感信息，如用户的敏感位置、真实身份和兴趣爱好等。TPLO方法中，攻击者通过试图窃听用户与LBS服务器之间的通信信道，并分析传输过程中的数据进行攻击。

3 TPLO方法实现

实现TPLO方法的过程主要分为5个步骤：用户查询请求、匿名器匿名、服务器查询、匿名器转发与用户求精结果，本节将分别对其进行介绍。TPLO方法中的符号定义及描述如表1所示。

3.1 用户查询请求

3.1.1 混淆位置选择

表1 TPLO方法中的符号定义及描述

1) 位置预测机制

算法1 用户查询预测位置算法

6) else

9) 跳转到第2)步；

10) else

11) 调用运动函数；

12) end if

13) end if

2) 假位置选择机制

假如用户的真实位置、预测位置和选择的假位置都非常靠近且都位于医院、学校等特定的场所，就容易暴露用户的隐私，同时假位置不能选择在海洋、湖泊等一些不可能的区域，因此如何选择合适的假位置至关重要[20]。在TPLO方法中，首先根据用户的真实位置和预测位置，在其附近生成一些均匀分散的临时位置，然后在这些临时位置附近的实际路网上最终确定其假位置，以避免假位置生成在一些不可能的区域。

图2 假位置选择

3.1.2 匿名器选择机制

在以上过程中，如果存在不同位置都映射到编号相同的匿名器，就会产生冲突。为解决该问题，本文方案采用二次探测再散列的方法进行处理，对有冲突的匿名器编号，再通过式(6)进行计算。

3.1.3 用户发起查询

最后，用户根据映射表，将各查询位置分别形成查询请求信息，发送到不同的匿名器进行匿名。

3.2 匿名器匿名

3.3 服务器查询

3.4 匿名器转发与用户求精结果

4 安全性分析

本节主要分析TPLO方法分别抵制强攻击者和弱攻击者的攻击，并将匿名器和LSP当作强攻击者，窃听者当作弱攻击者。具体分析如下。

4.1 抵制单匿名器的攻击

挑战。多个匿名器在用户和LBS服务器之间负责对用户位置进行匿名，并对查询请求、查询结果等信息进行转发。单匿名器作为强攻击者试图从用户这些数据中推断出一些敏感信息，从而揭露用户的运动轨迹。如果单匿名器可以确定地知道用户所对应的轨迹，那么单匿名器将赢得这个游戏。

定理1 TPLO方法能抵制单匿名器的推断攻击。

从以上分析可知，单匿名器无法推断出用户的真实轨迹。

4.2 抵制LSP的攻击

挑战。LSP管理所有用户的查询数据，LSP作为强攻击者试图从用户这些查询数据中推断出一些关于用户的敏感信息，从而揭露用户的精确位置。如果LSP可以成功地猜测出指定用户的查询内容或所对应用户的精确位置，那么LSP将赢得这个游戏。

定理2 TPLO方法能抵制LSP的推断攻击。

证明在TPLO方法中，当用户在查询预测位置发出查询请求时，用户可直接从缓存获取查询结果。在该过程中，用户与LSP没有进行交互，LSP就无法获取用户的任何信息。

从上述分析可知，LSP无法准确地确定用户的位置，也不能从LBS服务器中的用户查询数据正确地猜测出与查询内容对应的用户。

4.3 抵制窃听者的攻击

挑战。弱攻击者通过侦听不安全的无线信道，试图从这些数据中能推断出一些用户的敏感信息，从而揭露出指定用户的轨迹或查询内容。如果弱攻击者可以成功地猜测出指定用户的查询内容或所对应的用户轨迹，那么弱攻击者将赢得这个游戏。

定理3 TPLO方法能抵制侦听者的攻击。

从以上分析可知，窃听者不能猜测出指定用户的查询内容或所对应的用户轨迹。

5 实验及结果分析

本节主要通过实验验证用户连续查询时与LBS服务器的交互情况、在相关参数变化下对TPLO方法性能的影响及在匿名器的开销上与TTP结构的Gedik方法[13]和Hwang方法[14]进行仿真实验对比。

实验采用Brinkhoff移动对象生成器[21]，输入德国奥尔登堡市交通网络图并生成10 000个移动对象。德国奥尔登堡市交通网络图上生成的移动用户分布如图3所示。图3(b)和图3(c)是在图3(a)基础上分别放大4倍和8倍后的移动用户分布。移动用户集数据随机分布，实验随机选取移动对象Tom的移动轨迹作为实验对象。移动对象Tom的运动轨迹如图4所示。实验参数设置如表2所示。实验的硬件环境为：Intel(R) Core(TM) i5-4590 CPU @3.30 GHz，4.00 GB内存，操作系统为Microsoft Windows 7，采用MyEclipse 开发平台，以Java编程语言实现。

图3 德国奥尔登堡市交通网络图上生成的移动用户分布

图4 移动对象Tom的运动轨迹

表2 实验参数

5.1 用户与LBS服务器的交互情况

5.2 参数变化对TPLO性能的影响

表3 用户与LBS服务器交互次数对比

图5 查询位置数目及匿名度变化对性能的影响

图6 及匿名度变化对性能的影响

5.3 匿名器性能对比

图7 查询半径及匿名度变化对性能的影响

图8 匿名器的性能对比

6 结束语

[1] YI X, PAULET R, BERTINO E, et al. Practical approximatenearest neighbor queries with location and query privacy[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(6): 1546-1559.

[2] PRIMAULT V, BOUTET A, MOKHTAR S B, et al. Adaptive location privacy with ALP[C]//The 35th Symposium on Reliable Distributed Systems (SRDS). 2016: 269-278.

[3] 雷凯跃, 李兴华, 刘海,等. 轨迹发布中基于时空关联性的假轨迹隐私保护方案[J]. 通信学报, 2016, 37(12):156-164.

LEI K Y, LI X H, LIU H, et al. Dummy trajectory privacy protection scheme for trajectory publishing based on the spatiotemporal correlation[J]. Journal on Communications, 2016, 37(12): 156-164.

[4] GRISSA M, YAVUZ A, HAMDAOUI B. Preserving the location privacy of secondary users in cooperative spectrum sensing[J]. IEEE Transactions on Information Forensics & Security, 2017, 12(2): 418-431.

[5] 张学军, 桂小林, 伍忠东. 位置服务隐私保护研究综述[J]. 软件学报, 2015, 26(9): 2373-2395.

ZHANG X J, GUI X L, WU Z D. Privacy preservation for location-based services: a survey[J]. Journal of Software, 2015, 26(9): 2373-2395.

[6] 万盛, 李凤华, 牛犇, 等. 位置隐私保护技术研究进展[J]. 通信学报, 2016, 37(12): 1-18.

WAN S, LI F H, NIU B, et al. Research progress on location privacy-preserving techniques[J]. Journal on Communications, 2016, 37(12): 1-18.

[7] ARDAGNA C A, CREMONINI M, VIMERCATI S D C D, et al. An obfuscation-based approach for protecting location privacy[J]. IEEE Transactions on Dependable & Secure Computing, 2010, 8(1):13-27.

[8] 霍峥, 孟小峰, 黄毅. PrivateChechIn:一种移动社交网络中的轨迹隐私保护方法与进展[J]. 计算机学报, 2013, 36(4): 716-726.

HUO Z, MENG X F, HUANG Y. PrivateChechIn: trajectory privacy-preserving for chech-in services in MSNS[J]. Chinese Journal of Computers, 2013, 36(4): 716-726.

[9] CHOW C Y, MOKBEL M F, LIU X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C] //The 14th annual ACM International Symposium on Advances in Geographic Information Systems. 2006:171-178.

[10] SHOKRI R, THEODORAKOPOULOS G, PAPADIMITRATOS P, et al. Hiding in the mobile crowd: location privacy through collaboration[J]. IEEE Transactions on Dependable and Secure Computing, 2014, 11(3): 266-279.

[11] PENG T, LIU Q, MENG D, et al. Collaborative trajectory privacy preserving scheme in location-based services[J]. Information Sciences, 2017, 387:165-179.

[12] ZHANG Y, TONG W, ZHONG S. On designing satisfaction- ratio-aware truthful incentive mechanisms for k-anonymity location privacy[J]. IEEE Transactions on Information Forensics and Security, 2016, 11(11): 2528-2541.

[13] GEDIK B, LIU L. Protecting location privacy with personalized k-anonymous: architectrue and algorithms[J]. IEEE Transaction on Mobile Computing, 2008, 7(1):1-18.

[14] HWANG R H, HSUEH Y L, CHUNG H W. A novel time-obfuscated algorithm for trajectory privacy protection[J]. IEEE Transactions on Services Computing, 2014, 7(2): 126-139.

[15] LIAO D, LI H, SUN G, et al. Protecting user trajectory in location-based services[C]//IEEE Global Communications Conference (GLOBECOM). 2015: 1-6.

[16] 周长利, 马春光, 杨松涛. 路网环境下保护LBS位置隐私的连续KNN查询方法[J].计算机研究与发展, 2015, 52(11): 2628-2644.

ZHOU C L, MA C G, YANG S T. Location privacy-preserving method for LBS continuous KNN query in road networks[J]. Journal of Computer Research and Development, 2015, 52(11): 2628-2644.

[17] PENG T, LIU Q, WANG G J. Enhanced location privacy preserving scheme in location-based services[J]. IEEE Systems Journal, 2017, 11(1): 219-230.

[18] GAO S, MA J F, SHI W S, et al. TrPF: a trajectory privacy-preserving framework for participatory sensing[J]. IEEE Transactions on Information Forensics and Security, 2013, 8(6): 874-887.

[19] JEUNG H Y, SHEN H T, LIU Q, et al. A hybrid prediction model for moving objects[C]//The 24th International Conference on Data Engineering. 2008:70-79.

[20] NIU B, ZHANG Z Y, LI X Q, et al. Privacy-area aware dummy generation algorithms for location-based services[C]//The International Conference on Communications. 2014: 957-962.

[21] BRINKHOFF T. Generating traffic data[J]. Bulletin of the Technical Committee Data Engineering, 2003, 26(2): 19-25.

Trajectory privacy protection method based on location obfuscation

ZHANG Shaobo1, LIU Qin2, WANG Guojun3

1. School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China 2. College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China 3. School of Computer Science and Educational Software, Guangzhou University, Guangzhou 510006, China

In the process of continuous queries, a method of trajectory privacy protection based on location obfuscation was proposed to solve the problem that-anonymity was difficult to guarantee user privacy in third party architectrue. Firstly, the (−1) query obfuscation locations through the location prediction was obtained and the dummy location selection mechanism, and then sent them together with the user’s real query location to different anonymizers to form cloaking regions and sent them to the LBS server for queries, and the query results were returned to the user by different anonymizers. In this method, the user’s real query location was confused by the location obfuscation, and the attacker couldn’t deduce the user’s trajectory from a single anonymizer or the LBS server. The method can enhance the privacy of the user’s trajectory and can effectively solve the performance bottleneck in the single anonymizer structure. Security analysis shows the security of the proposed approach, and experiments show this method can reduce the number of interactions between the user and the LBS server and the overhead of the single anonymizer.

trajectory privacy, location obfuscation, location prediction, dummy location, anonymizer

TP393

10.11959/j.issn.1000−436x.2018119

2017−10−28；

2018−05−11

王国军，csgiwang@gmail.com

国家自然科学基金资助项目（No.61632009, No.61472451, No.61402161, No.61772194）；湖南省自然科学基金资助项目（No.2016JJ3046）；广东省自然科学基金资助项目（No.2017A030308006）；广东省高等教育高层次人才基金资助项目（No.2016ZJ01）

The National Natural Science Foundation of China (No.61632009, No.61472451, No.61402161, No.61772194), The Natural Science Foundation of Hunan Province (No.2016JJ3046), The Natural Science Foundation of Guangdong Province (No.2017A030308006), The High Level Talents Program of Higher Education in Guangdong Province (No.2016ZJ01)

张少波（1979−），男，湖南邵东人，博士，湖南科技大学讲师，主要研究方向为移动社交网络、隐私保护、云计算安全、大数据安全和隐私等。