張少波，劉琴，王國軍

?

基于位置混淆的軌跡隱私保護方法

張少波1，劉琴2，王國軍3

（1. 湖南科技大學計算機科學與工程學院，湖南 湘潭 411201；2. 湖南大學信息科學與工程學院，湖南 長沙 410082；3. 廣州大學計算機科學與教育軟件學院，廣東 廣州 510006）

在用戶連續(xù)查詢過程中，針對第三方匿名器結(jié)構中匿名難以保證用戶隱私的問題，提出一種基于位置混淆的軌跡隱私保護方法。首先通過位置預測機制和假位置選擇機制獲得(?1)個查詢混淆位置，然后將其與用戶真實查詢位置一起發(fā)送到不同匿名器形成匿名域后，再發(fā)送到LBS服務器進行查詢，最后將獲得的查詢結(jié)果經(jīng)不同匿名器返回給用戶。該方法通過位置混淆來混淆用戶的真實查詢位置，使攻擊者從單匿名器和LBS服務器不能推斷出用戶的真實軌跡，加強了對用戶軌跡的隱私保護，也解決了單匿名器的性能瓶頸問題。安全分析表明了該方法的安全性，實驗結(jié)果表明，該方法能減少用戶與LBS服務器的交互次數(shù)以及單匿名器的開銷。

軌跡隱私；位置混淆；位置預測；假位置；匿名器

1 引言

近年來，隨著無線通信技術、移動互聯(lián)網(wǎng)和定位技術的迅速發(fā)展，基于位置服務（LBS, location based service）已受到人們的廣泛關注[1-2]。用戶使用智能手機或掌上電腦，可以從應用商店下載基于位置服務的軟件，如Twitter、Foursquare和Gowalla等。通過使用這些LBS應用軟件發(fā)送查詢到LBS服務器，可以獲得用戶需要的興趣點（POI, point of interest），如交通導航信息、基于位置的廣告、最近提供用戶最喜歡的菜肴的餐廳等[3-4]。然而，用戶在享受LBS帶來極大生活便利和娛樂的同時，他們需要將這些查詢請求提交給不可信的位置服務提供商（LSP, location service provider）。在連續(xù)LBS查詢中，LSP根據(jù)收集的用戶查詢數(shù)據(jù)可以直接追蹤到用戶或推斷出一些敏感的用戶個人信息，如日常行為、家庭地址和社會關系等，這將嚴重導致用戶個人隱私的泄露[5]。

為減少LBS中軌跡隱私泄露，國內(nèi)外學者已提出一些軌跡隱私保護方法，它們主要采用2種基本結(jié)構[6]：基于點對點結(jié)構[7]和基于可信第三方（TTP, trusted third party）中心服務器結(jié)構[8]。在基于點對點結(jié)構中，Chow等[9]首次提出用戶協(xié)作的點對點匿名方法，但該方法在尋找用戶的過程中會產(chǎn)生較大開銷。為減少開銷，Shokri等[10]提出一種基于緩存的用戶合作隱私保護方法，移動用戶先在合作用戶緩存中查找查詢內(nèi)容，當尋找失敗時才通過協(xié)作的方式向LSP發(fā)出查詢。Peng等[11]也提出了一種基于用戶合作的軌跡隱私保護方法，通過向周圍多跳鄰居搜尋有價值的信息構造匿名區(qū)域，并發(fā)布假查詢阻止攻擊者重構用戶軌跡?？傮w而言，該結(jié)構中移動用戶發(fā)送查詢前需進行一定的匿名或變換處理，這將會對移動終端產(chǎn)生較大的計算開銷，同時也不能避免惡意用戶的攻擊。

然而基于TTP結(jié)構的方法也存在2個問題[17]：1)匿名器知道所有用戶的精確位置和查詢信息，如果它被攻破，這將會帶來嚴重的安全威脅；2) 用戶的查詢請求和結(jié)果返回都必須經(jīng)過匿名器，它承擔著匿名、求精等繁重的計算任務，容易成為該結(jié)構中的性能瓶頸，同時也存在著中心點失效的風險。同時，在連續(xù)LBS查詢過程中，基于TTP結(jié)構的匿名技術也很難保證用戶的軌跡隱私。當用戶發(fā)出連續(xù)LBS查詢時，匿名器將每個查詢點都模糊成滿足用戶需求的匿名域，然而攻擊者可根據(jù)匿名域順序重構用戶的軌跡，并且攻擊者將這些匿名域包含的用戶進行對比，也能識別出真實用戶。

2) 提出一種基于位置預測和假位置選擇機制的混淆位置選擇方法，通過位置預測機制，減少用戶信息暴露給LBS服務器的風險，同時使用假位置選擇機制增加對用戶真實位置的混淆度，以提高用戶隱私。

3) 提出一種基于多匿名器進行位置匿名的框架，用戶查詢請求和結(jié)果信息通過多個匿名器進行處理和轉(zhuǎn)發(fā)，能有效解決TTP結(jié)構中單匿名器單點失效風險和性能瓶頸問題。

2 系統(tǒng)模型和相關定義

2.1 系統(tǒng)模型

圖1 TPLO模型

TPLO方法的優(yōu)點是攻擊者不能從單個匿名器獲得用戶的真實軌跡，即使多個匿名器共謀，由于假位置混淆了用戶的真實位置，攻擊者也很難獲得用戶的軌跡。同時，通過混淆的用戶位置并結(jié)合形成的匿名域發(fā)送到LBS服務器查詢，LBS服務器不能獲得用戶的真實軌跡。LBS服務器查詢的結(jié)果也同樣經(jīng)不同匿名器返回給用戶。該方法中單個匿名器的失效并不影響系統(tǒng)的運行，能有效解決基于TTP結(jié)構中的單匿名器單點失效風險和性能瓶頸問題。根據(jù)系統(tǒng)中不同的角色和功能，系統(tǒng)主要由3類實體組成：用戶、多匿名器和LBS服務器。

用戶：攜帶具有全球定位、計算存儲和無線通信功能智能終端的用戶，他們可以通過多種方式（Wi-Fi或3G/4G移動通信網(wǎng)絡）接入移動網(wǎng)絡，并將不同時刻的請求信息連續(xù)發(fā)送到LBS服務器進行查詢，以獲得預期的服務。本方案中用戶能根據(jù)自身位置預測后續(xù)的幾個查詢位置，并能在其周圍找到一些合適的假位置。

LBS服務器：它是一個服務提供者，擁有大量與位置服務相關的服務和信息資源，能為用戶提供各種數(shù)據(jù)服務。當LBS服務器收到用戶發(fā)出的查詢請求后，它在數(shù)據(jù)庫搜索用戶指定的POI，并將滿足用戶需求的查詢結(jié)果返回給用戶。

2.2 位置預測

2.3 安全模型

目前，在位置隱私保護的研究方面，比較典型的攻擊模型主要有2種[18]：強攻擊者攻擊模型和弱攻擊者攻擊模型。

1) 強攻擊者攻擊模型

在強攻擊者攻擊模型中，攻擊者能監(jiān)視整個系統(tǒng)中特定用戶的行為記錄。攻擊者通常不破壞協(xié)議流程，但它試圖從自己獲取的信息中分析得到用戶的其他信息。TPLO方法中的匿名器和LSP可能成為潛在的強攻擊者。匿名器在用戶和LBS服務器之間進行匿名和轉(zhuǎn)發(fā)信息，可能會對用戶行為進行分析而造成用戶信息泄露。LSP管理所有用戶的LBS查詢數(shù)據(jù)，且可能會因利益關系泄露LBS服務器中的敏感信息給第三方。

2) 弱攻擊者攻擊模型

在弱攻擊者攻擊模型中，攻擊者具有很少的關于用戶的背景知識，攻擊者可以通過使用背景知識或其他一些攻擊手段進行攻擊，試圖知道其他用戶的更多個人敏感信息。通常攻擊者通過偵聽不安全的無線信道，試圖竊聽信息并推斷出一些用戶的敏感信息，如用戶的敏感位置、真實身份和興趣愛好等。TPLO方法中，攻擊者通過試圖竊聽用戶與LBS服務器之間的通信信道，并分析傳輸過程中的數(shù)據(jù)進行攻擊。

3 TPLO方法實現(xiàn)

實現(xiàn)TPLO方法的過程主要分為5個步驟：用戶查詢請求、匿名器匿名、服務器查詢、匿名器轉(zhuǎn)發(fā)與用戶求精結(jié)果，本節(jié)將分別對其進行介紹。TPLO方法中的符號定義及描述如表1所示。

3.1 用戶查詢請求

3.1.1 混淆位置選擇

表1 TPLO方法中的符號定義及描述

1) 位置預測機制

算法1 用戶查詢預測位置算法

6) else

9) 跳轉(zhuǎn)到第2)步；

10) else

11) 調(diào)用運動函數(shù)；

12) end if

13) end if

2) 假位置選擇機制

假如用戶的真實位置、預測位置和選擇的假位置都非?？拷叶嘉挥卺t(yī)院、學校等特定的場所，就容易暴露用戶的隱私，同時假位置不能選擇在海洋、湖泊等一些不可能的區(qū)域，因此如何選擇合適的假位置至關重要[20]。在TPLO方法中，首先根據(jù)用戶的真實位置和預測位置，在其附近生成一些均勻分散的臨時位置，然后在這些臨時位置附近的實際路網(wǎng)上最終確定其假位置，以避免假位置生成在一些不可能的區(qū)域。

圖2 假位置選擇

3.1.2 匿名器選擇機制

在以上過程中，如果存在不同位置都映射到編號相同的匿名器，就會產(chǎn)生沖突。為解決該問題，本文方案采用二次探測再散列的方法進行處理，對有沖突的匿名器編號，再通過式(6)進行計算。

3.1.3 用戶發(fā)起查詢

最后，用戶根據(jù)映射表，將各查詢位置分別形成查詢請求信息，發(fā)送到不同的匿名器進行匿名。

3.2 匿名器匿名

3.3 服務器查詢

3.4 匿名器轉(zhuǎn)發(fā)與用戶求精結(jié)果

4 安全性分析

本節(jié)主要分析TPLO方法分別抵制強攻擊者和弱攻擊者的攻擊，并將匿名器和LSP當作強攻擊者，竊聽者當作弱攻擊者。具體分析如下。

4.1 抵制單匿名器的攻擊

挑戰(zhàn)。多個匿名器在用戶和LBS服務器之間負責對用戶位置進行匿名，并對查詢請求、查詢結(jié)果等信息進行轉(zhuǎn)發(fā)。單匿名器作為強攻擊者試圖從用戶這些數(shù)據(jù)中推斷出一些敏感信息，從而揭露用戶的運動軌跡。如果單匿名器可以確定地知道用戶所對應的軌跡，那么單匿名器將贏得這個游戲。

定理1 TPLO方法能抵制單匿名器的推斷攻擊。

從以上分析可知，單匿名器無法推斷出用戶的真實軌跡。

4.2 抵制LSP的攻擊

挑戰(zhàn)。LSP管理所有用戶的查詢數(shù)據(jù)，LSP作為強攻擊者試圖從用戶這些查詢數(shù)據(jù)中推斷出一些關于用戶的敏感信息，從而揭露用戶的精確位置。如果LSP可以成功地猜測出指定用戶的查詢內(nèi)容或所對應用戶的精確位置，那么LSP將贏得這個游戲。

定理2 TPLO方法能抵制LSP的推斷攻擊。

證明 在TPLO方法中，當用戶在查詢預測位置發(fā)出查詢請求時，用戶可直接從緩存獲取查詢結(jié)果。在該過程中，用戶與LSP沒有進行交互，LSP就無法獲取用戶的任何信息。

從上述分析可知，LSP無法準確地確定用戶的位置，也不能從LBS服務器中的用戶查詢數(shù)據(jù)正確地猜測出與查詢內(nèi)容對應的用戶。

4.3 抵制竊聽者的攻擊

挑戰(zhàn)。弱攻擊者通過偵聽不安全的無線信道，試圖從這些數(shù)據(jù)中能推斷出一些用戶的敏感信息，從而揭露出指定用戶的軌跡或查詢內(nèi)容。如果弱攻擊者可以成功地猜測出指定用戶的查詢內(nèi)容或所對應的用戶軌跡，那么弱攻擊者將贏得這個游戲。

定理3 TPLO方法能抵制偵聽者的攻擊。

從以上分析可知，竊聽者不能猜測出指定用戶的查詢內(nèi)容或所對應的用戶軌跡。

5 實驗及結(jié)果分析

本節(jié)主要通過實驗驗證用戶連續(xù)查詢時與LBS服務器的交互情況、在相關參數(shù)變化下對TPLO方法性能的影響及在匿名器的開銷上與TTP結(jié)構的Gedik方法[13]和Hwang方法[14]進行仿真實驗對比。

實驗采用Brinkhoff移動對象生成器[21]，輸入德國奧爾登堡市交通網(wǎng)絡圖并生成10 000個移動對象。德國奧爾登堡市交通網(wǎng)絡圖上生成的移動用戶分布如圖3所示。圖3(b)和圖3(c)是在圖3(a)基礎上分別放大4倍和8倍后的移動用戶分布。移動用戶集數(shù)據(jù)隨機分布，實驗隨機選取移動對象Tom的移動軌跡作為實驗對象。移動對象Tom的運動軌跡如圖4所示。實驗參數(shù)設置如表2所示。實驗的硬件環(huán)境為：Intel(R) Core(TM) i5-4590 CPU @3.30 GHz，4.00 GB內(nèi)存，操作系統(tǒng)為Microsoft Windows 7，采用MyEclipse 開發(fā)平臺，以Java編程語言實現(xiàn)。

圖3 德國奧爾登堡市交通網(wǎng)絡圖上生成的移動用戶分布

圖4 移動對象Tom的運動軌跡

表2 實驗參數(shù)

5.1 用戶與LBS服務器的交互情況

5.2 參數(shù)變化對TPLO性能的影響

表3 用戶與LBS服務器交互次數(shù)對比

圖5 查詢位置數(shù)目及匿名度變化對性能的影響

圖6 及匿名度變化對性能的影響

5.3 匿名器性能對比

圖7 查詢半徑及匿名度變化對性能的影響

圖8 匿名器的性能對比

6 結(jié)束語

[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] 雷凱躍, 李興華, 劉海,等. 軌跡發(fā)布中基于時空關聯(lián)性的假軌跡隱私保護方案[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:一種移動社交網(wǎng)絡中的軌跡隱私保護方法與進展[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] 周長利, 馬春光, 楊松濤. 路網(wǎng)環(huán)境下保護LBS位置隱私的連續(xù)KNN查詢方法[J].計算機研究與發(fā)展, 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

A

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?），男，湖南邵東人，博士，湖南科技大學講師，主要研究方向為移動社交網(wǎng)絡、隱私保護、云計算安全、大數(shù)據(jù)安全和隱私等。

劉琴（1982?），女，湖南長沙人，博士，湖南大學副教授，主要研究方向為云計算安全、大數(shù)據(jù)安全與隱私保護等。

王國軍（1970?），男，湖南長沙人，廣州大學博士生導師、廣東省珠江學者特聘教授，主要研究方向為信息安全、可信計算、大數(shù)據(jù)安全和隱私保護等。