張磊，馬春光，楊松濤，鄭曉東,3

(1.哈爾濱工程大學 計算機科學與技術(shù)學院,黑龍江 哈爾濱 150001； 2.佳木斯大學 信息電子技術(shù)學院,黑龍江 佳木斯 154007； 3.齊齊哈爾大學 應用技術(shù)學院,黑龍江 齊齊哈爾 1610061)

抗軌跡差異識別攻擊的相似軌跡實時生成方法

張磊1,2，馬春光1，楊松濤1,2，鄭曉東1,3

(1.哈爾濱工程大學 計算機科學與技術(shù)學院,黑龍江 哈爾濱 150001； 2.佳木斯大學 信息電子技術(shù)學院,黑龍江 佳木斯 154007； 3.齊齊哈爾大學 應用技術(shù)學院,黑龍江 齊齊哈爾 1610061)

用戶使用基于位置服務進行連續(xù)查詢產(chǎn)生的移動軌跡可能會遭受軌跡差異識別攻擊，進而造成用戶個人隱私的泄露問題，本文依據(jù)軌跡r-匿名的思想，提出了一種相似軌跡實時生成方法用來保護用戶的個人位置隱私。該方法通過匿名服務器對用戶提交進行需要匿名的真實位置計算，實時生成、篩選建立虛假位置集合，利用虛假位置形成的位置軌跡與真實軌跡之間的相似性模糊了真實軌跡，降低了生成的虛假軌跡被攻擊者識別的概率，實現(xiàn)了連續(xù)位置查詢中的實時軌跡匿名。通過性能分析和模擬對比實驗驗證，進一步說明了本文所提出算法的隱私保護效力和算法執(zhí)行效率。

基于位置服務；連續(xù)查詢；隱私保護；虛假位置；實時軌跡匿名；相似軌跡

隨著移動通信和定位技術(shù)的不斷發(fā)展，基于位置服務(location based services, LBSs)逐漸深入到人們的日常生活。然而人們在享受這種服務帶來便利的同時，又不可避免地要面對隱私泄露問題。針對這一問題，研究者提出了以k-匿名[1]、l-多樣性[2]、用戶協(xié)作[3]、錨點[4]和PIR[5]等為主的基于快照服務的隱私保護方法。但是這些方法均不能有效地保護連續(xù)位置服務中的軌跡隱私。針對這一情況，研究者分別從單元泛化[6]、軌跡聚類[7]和全局軌跡相似[8]等方面提出軌跡隱私保護方法。Gao等詳細分析并總結(jié)了這些方法，發(fā)現(xiàn)它們更適合對已生成的軌跡加以保護，并不能有效的保護實時連續(xù)位置服務中的用戶隱私[7]。學者又陸續(xù)提出了基于匿名[9-13]和mix-zone[14-16]的隱私保護方法。盡管這些實時的隱私保護方法能夠有效保護用戶的位置，但是在掌握用戶移動方式的情況下，攻擊者還是能夠通過產(chǎn)生的軌跡差異識別出用戶的真實軌跡，進而獲得用戶隱私。因此，本文基于軌跡匿名和實時連續(xù)位置服務隱私保護的特點，提出了一種相似軌跡實時生成方法，通過實時生成相似軌跡完成軌跡匿名，彌補軌跡隱私保護方法無法適應實時服務，以及實時連續(xù)服務隱私保護方法無法保障軌跡匿名的不足。

1 隱私保護系統(tǒng)架構(gòu)

由于移動通信設備計算能力有限，本文采用三層中心服務器架構(gòu)。如圖1所示，該架構(gòu)包含3個實體：移動用戶(mobile user, U)，匿名服務器(anonymous servers, AS)，服務提供商(location service provider, LSP)。U攜帶定位設備(例如：智能手機、GPS定位模塊)，能夠精確定位自身位置并與LSP交互，進而享受位置依賴服務。但是，U的通信和計算能力有限。AS負責計算相似軌跡位置，具有較強的計算和數(shù)據(jù)處理能力。LSP能夠為User或AS提供服務，具有極強的數(shù)據(jù)分析和處理能力。本文假設U和AS是可信的，而LSP是半可信的，即LSP在嚴格執(zhí)行協(xié)議和算法的前提下，同時使用收集到的位置信息和背景知識推斷U的敏感信息，甚至LSP可能將U的敏感信息出賣給不友好的第三方。

圖1 三層系統(tǒng)架構(gòu)示意圖Fig.1 The system architecture of three layers

定義1 連續(xù)位置服務是指User向LSP發(fā)起多次請求，并獲得連續(xù)服務反饋的過程。這些請求可表示為Q=(ID,Li,I,P)。其中：ID表示用戶的身份標識；Li=(xi，yi)表示查詢設備所處位置；I表示時間間隔；P表示查詢興趣點，如：餐廳、醫(yī)院等。

定義2 軌跡差異識別攻擊是指攻擊者通過獲取用戶的移動速度、移動方向等移動信息，比較識別出移動用戶產(chǎn)生軌跡的攻擊方法。其攻擊成功概率可表示為

式中：tm為攻擊者根據(jù)移動信息建立的軌跡，sim表示軌跡相似性。

2 相似軌跡實時生成方法

相似軌跡實時生成方法的基本原理就是通過實時產(chǎn)生相似的虛假軌跡完成軌跡匿名。為實現(xiàn)相似軌跡匿名，需要經(jīng)過初始匿名位置選擇、相似軌跡位置計算和生成位置篩選等3個步驟。其中初始匿名需選擇分布在多個興趣點區(qū)域中的位置，以降低產(chǎn)生伴隨軌跡的概率。

定義3 軌跡r-匿名是指LSP同時獲得包括真實軌跡t在內(nèi)的至少r條相似軌跡，這些軌跡使得LSP無法通過軌跡長度和軌跡方向之間的差異，識別出t的隱私保護過程。

定義4 伴隨軌跡是指用戶行進過程中經(jīng)過共同的興趣點，這些興趣點可被校正整合為同一軌跡的r條相似軌跡。

定義5 相似軌跡位置區(qū)域是一個相似位置集合，是在方向偏差和相似度閾值內(nèi)，以二元二次方程4個根為頂點建立的區(qū)域。連接前次匿名位置與該區(qū)域內(nèi)任一位置可建立相似軌跡。

定義6 不可到達位置是指生成的虛假位置l′?T，其中T表示LSP獲得的所有歷史軌跡集合。

2.1 相似軌跡位置計算

通過計算相似軌跡位置，獲得滿足生成相似軌跡的位置集合，并經(jīng)過位置篩選建立相似軌跡。關(guān)于相似軌跡位置計算，本文借鑒Gao等關(guān)于相似軌跡區(qū)段計算的基本思想[7]，利用平行距離量化軌跡長度，夾角距離量化方向，使用兩者之和來量化相似程度。在生成位置的過程中，根據(jù)初始匿名位置，計算至少r-1個虛假軌跡來完成軌跡匿名。以兩條軌跡為例闡述相似軌跡生成方法。

假設用戶A和虛假用戶B分別以pa和pb為初始位置建立匿名組，若要計算B的虛假位置pb+1，且連接用戶A、B的相鄰查詢位置能夠產(chǎn)生相似軌跡，需要通過pa、pb和A的后續(xù)查詢位置pa+1使用平行距離和夾角距離建立方程，進而計算得出pb+1的位置。令La和Lb是分別以pa、pa+1和pb、pb+1為兩端位置的軌跡長度，θ表示用戶制定的兩條軌跡之間存在的夾角閾值。由于pa+1已知，通過式(1)、(2)聯(lián)立建立關(guān)于pb+1的二元二次方程，從而計算獲得pb+1。獲取相似軌跡位置區(qū)域計算所需要的平行距離和夾角距離公式可分別表示為

(1)

(2)

式中：A,B表示用戶A、B的移動向量；ω‖、ωθ分別代表平行距離和夾角距離的權(quán)重，由于兩個距離公式均對軌跡相似程度產(chǎn)生影響，因此ω‖,、ωθ的默認值設定為1。其中兩條軌跡之間的相似程度可表示為

(3)

兩個軌跡區(qū)段之間的軌跡距離可表示為

(4)

2.2 篩選生成位置

為降低攻擊者識別虛假位置的概率，需對生成的軌跡相似位置加以篩選。本文主要針對生成位置的實際可到達性加以描述。如圖2所示的虛假用戶U，經(jīng)過計算后可獲得由A、B、C3個位置組成的相似軌跡位置區(qū)域。由于U與A之間存在建筑物阻擋，U與C之間存在河流阻擋。根據(jù)可到達情況，AS只能選擇B作為匿名位置，建立匿名組。

圖2 生成位置篩選示意圖Fig.2 The refine of dummy locations

綜合初始匿名、相似軌跡位置計算和篩選生成位置的思想，設計了相似軌跡生成算法。

算法1 相似軌跡生成算法

輸入：用戶當前查詢位置pi+1與前次位置pi以及虛假前次位置pj

輸出：pj+1位置集合，該集合中位置滿足軌跡匿名

1) Procedure:AS收到請求Q;

2) 隨機選擇2r-1個位于不同興趣點的匿名位置構(gòu)成集合B；

3) hreshold_sim=min_sim(A,B);thresholdθ=Max_θ; //設置相似性和夾角閾值；

4) Ps=null; //目標位置集為空；

5)foreveryB //對于每個虛假位置；

6)Dist(A,B)=(1-threshold_sim)/threshold_sim;

7)A·B=dot(‖pi+1-pi‖,‖pj+1-pjV);

8)dθ=thresholdθ=

9)d‖=Dist(A,B)-thresholdθ=‖pi+1-pi‖-‖pj+1-pj‖;//平行距離；

10) pj+1=solve(d‖,dθ));//解關(guān)于pj+1二元二次方程；

11) 使用pj+1建立位置相似區(qū)域；

12)if當前區(qū)域可從pj到達；

13) 隨機選擇任一位置作為 pc;

14) S=S+ pc;

15)else

16)break; //匿名失敗

17)endif

18)End

19)EndProcedure

算法1根據(jù)每一個參與前次匿名的位置，計算所得虛假位置保存在S中，在連續(xù)匿名過程中重復3)～19)，計算獲得能夠產(chǎn)生相似軌跡的位置，連接后獲得相似的匿名軌跡，最終實現(xiàn)軌跡r-匿名。

3 性能分析與實驗驗證

3.1 性能分析

(5)

由此可得ui=uj，即用戶ui和uj無法區(qū)分，進而可知攻擊者通過軌跡差異識別攻擊無法在r條相似軌跡中準確識別出待攻擊用戶。

為實現(xiàn)軌跡r-匿名，需要在每個連續(xù)查詢間隔內(nèi)生成r條相似軌跡。在最好的情況下，其時間復雜度為O(r-1)。若每個生成位置均不可到達則需調(diào)整相似參數(shù)，此時算法的執(zhí)行時間復雜度為2O(r-1)。由此，可得出算法1的時間復雜度為O(sum)=O(r-1)+2O(r-1)=O(r-1)。綜上，可以認為該算法的時間復雜度取決于用戶設定的軌跡匿名閾值和后續(xù)相似位置的可到達性。由于相似軌跡實時生成方法是基于歐氏空間提出，可認為在多數(shù)情況下能夠找到可達的相似軌跡位置。因此，在一般情況下，該算法的時間復雜度為O(r)。

3.2 環(huán)境配置

本實驗中所涉及方法是在Windows 7系統(tǒng)上使用Matlab 7來進行模擬的，運行環(huán)境為1.70GHz Intel Core i5，內(nèi)存4 GB。實驗數(shù)據(jù)采用BerlinMOD Data Set提供的真實位置數(shù)據(jù)，并隨機選擇城市中心位置進行實驗驗證。同時，本文加入以下方法進行對比：LTPPM[10]、EGCA[11]和CLAPPINQ[13]，其中LTPPM主要針對軌跡差異識別攻擊。表1為實驗中采用的相關(guān)參數(shù)閾值。

表1 實驗參數(shù)閾值設定表

3.3 結(jié)果比較

如圖3所示，本文提出方法所產(chǎn)生的軌跡與基軌跡之間極為相似，可以實現(xiàn)軌跡匿名。

圖3 軌跡相似性對比Fig.3 The comparison of trajectories

通常，在軌跡隱私保護中需降低伴隨軌跡產(chǎn)生率，以防止攻擊者通過共同的興趣點識別出真實軌跡。從圖4中可以看到，隨著匿名值增大，各算法產(chǎn)生伴隨軌跡的概率逐漸增加。但本文所提出的方法由于對初始位置加以限制，其伴隨軌跡產(chǎn)生率要遠低于其他算法。其他算法中LTPPM相對較好，這是由于部分相距較遠的協(xié)作用戶降低了伴隨軌跡的產(chǎn)生概率。最后，CLAPPINQ和EGCA由于隨機選擇匿名用戶，使得伴隨軌跡的產(chǎn)生率明顯高于另2種算法。

從圖5中可以看到各算法隨匿名值增大，匿名用戶被攻擊者識別的概率逐漸增加。本文所提出的算法由于對生成的虛假位置進行篩選，降低了攻擊者成功剔除匿名位置的概率，因而與其他算法相比具有較低的識別率，進一步保護了用戶的位置軌跡隱私。EGCA由于隨機選擇匿名用戶，使得其匿名用戶識別率最高。CLAPPINQ和LTPPM由于匿名用戶變更以及真實軌跡被匿名軌跡所圍繞，使得其識別率要高于本文算法。

圖4 產(chǎn)生伴隨軌跡概率Fig.4 The probability of concomitant trajectories

圖5 匿名用戶識別率Fig.5 The probability of identification

在執(zhí)行效率的對比實驗中，根據(jù)匿名值變化，查看各算法在執(zhí)行時間上的差異。同時，查看在連續(xù)多次執(zhí)行過程中，相同匿名值限定下的連續(xù)執(zhí)行時間。最后比較各算法的匿名成功率。下面以3次連續(xù)查詢?yōu)槔?，查看各算法隨匿名值增大導致的執(zhí)行時間變化。

從圖6中可以看出，直接選擇用戶匿名的CLAPPINQ和EGCA方法其執(zhí)行時間較短，且CLAPPINQ由于采用預計算的方式，其執(zhí)行時間最短，但這兩種方法均無法有效抵抗軌跡差異識別攻擊。LTPPM通過用戶協(xié)作建立相似軌跡來抵抗軌跡差異識別攻擊，該方法既涉及到尋找協(xié)作用戶，又需對匿名軌跡進行篩選，因此其時間效率受匿名值變化影響最大。本文方法僅處理相似軌跡位置，無需尋找協(xié)作用戶，與LTPPM相比具有更好的執(zhí)行效率。

在圖7中可以看到，相同參數(shù)連續(xù)運行過程中各算法的執(zhí)行時間。在這些算法中，本文所提出的算法在計算出匿名位置之后，需進行相似軌跡位置篩選，其執(zhí)行時間要高于直接選擇用戶進行匿名的CLAPPINQ和EGCA，但低于查找協(xié)作用戶建立相似軌跡的隱私保護算法LTPPM。

圖6 隨匿名值變化的執(zhí)行時間Fig.6 The performance with r

圖7 隨重復次數(shù)變化的執(zhí)行時間Fig.7 The performance with running times

從圖8中可以看到各算法的匿名成功率。EGCA由于使用單匿名框，其匿名成功率受匿名次數(shù)影響較小。LTPPM因需要連續(xù)尋找能夠參與匿名的協(xié)作用戶，其匿名成功率急速降低。本文算法同樣因為生成位置篩選，使得隨連續(xù)匿名申請次數(shù)增加導致成功率逐漸下降。CLAPPINQ方法由于采用預計算，其成功率要好于LTPPM與本文方法。

圖8 匿名成功率Fig.8 The success ratio of anonymity

綜上，從兩組實驗的對比中可以看出，本文所提出的相似軌跡實時生成方法盡管在執(zhí)行效率上優(yōu)勢并不明顯(如圖6～8)，但與同類方法相對比該方法能夠更好地抵抗軌跡差異識別攻擊(如圖4、5)。

4 結(jié)論

1)本文分析了攻擊者通過軌跡差異獲取用戶隱私的攻擊行為，利用攻擊成功率量化了這種攻擊行為。

2)針對這種攻擊行為基于軌跡相似性計算的思想，提出了相似軌跡實時生成方法，利用軌跡方向、軌跡長度的量化以及位置篩選實現(xiàn)了連續(xù)位置服務過程中的位置隱私保護。

3)本文通過性能分析和實驗結(jié)果比較進一步證明該方法在增強用戶位置軌跡隱私的同時具有較好的執(zhí)行效率。今后的工作將在如何降低AS對執(zhí)行效率的影響以及提高匿名成功率等方面展開。

[1]GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]// International Conference on Mobile Systems, Applications, and Services. San Francisco, USA, 2003:31-42.

[2]BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid[C]// International Conference on World Wide Web. Beijing, China, 2008:237-246.

[3]REBOLLO-MONEDERO D, FORNé J, SOLANAS A, et al. Private location-based information retrieval through user collaboration[J]. Computer communications, 2010, 33(6): 762-774.

[4]MAN L Y, JENSEN C S, M?LLER J, et al. Design and analysis of a ranking approach to private location-based services[J]. ACM transactions on database systems, 2011, 36(2): 475-486.

[5]GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location based services: anonymizers are not necessary[C]// International Conference on Management of Data. Vancouver, Canada, 2008: 121-132.

[6]AL-HUSSAENI K, FUNG B C M, CHEUNG W K. Privacy-preserving trajectory stream publishing[J]. Data & knowledge engineering, 2014, 94: 89-109.

[7]GAO S, MA J, SUN C, et al. Balancing trajectory privacy and data utility using a personalized anonymization model[J]. Journal of network & computer applications, 2014, 38(1): 125-134.

[8]GURUNG S, LIN D, JIANG W, et al. Traffic information publication with privacy preservation[J]. ACM transactions on intelligent systems & technology, 2014, 5(3): 1-26.

[9]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.

[10]GAO S, MA J F, SHI W S, et al. LTPPM: a location and trajectory privacy protection mechanism in participatory sensing [J]. Wireless communications & mobile computing, 2015, 15(1): 155-169.

[11]WANG E K, YE Y. A new privacy-preserving scheme for continuous query in location-based social networking services [J]. International journal of distributed sensor networks, 2014(1): 836-839.

[12]JIA J, ZHANG F. Nonexposure accurate location k-anonymity algorithm in LBS [J]. Scientific world journal, 2014(1): 149-168.

[13]HASHEM T, KULIK L, ZHANG R. Countering overlapping rectangle privacy attack for moving kNN queries [J]. Information systems, 2013, 38(3): 430-453.

[14]PALANISAMY B, LIU L, LEE K, et al. Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J]. Distributed & parallel databases, 2014, 32(1): 91-118.

[15]PALANISAMY B, LIU L. Attack-resilient mix-zones over road networks: architecture and algorithms[J]. IEEE transactions on mobile computing, 2015, 14(3): 495-508.

[16]SUN Y, ZHANG B, ZHAO B, et al. Mix-zones optimal deployment for protecting location privacy in VANET[J]. Peer-to-Peer networking & applications, 2015, 8(6): 1108-1121.

本文引用格式：

張磊，馬春光，楊松濤，等. 抗軌跡差異識別攻擊的相似軌跡實時生成方法[J]. 哈爾濱工程大學學報， 2017， 38(7): 1173-1178.

ZHANG Lei, MA Chunguang, YANG Songtao, et al. Real-time similar trajectory generation algorithm for resisting trajectory difference identification attack[J]. Journal of Harbin Engineering University， 2017， 38(7): 1173 -1178.

Real-time similar trajectory generation algorithm for resisting trajectory difference identification attack

ZHANG Lei1,2, MA Chunguang1, YANG Songtao1,2, ZHENG Xiaodong1,3

(1.College of Computer Science And Technology, Harbin Engineering University, Harbin 150001, China; 2.College of Information And Electronic Technology, Jiamusi University, Jiamusi 154007, China; 3.College of Applied Technology, Qiqihar University, Qiqihar 161006, China)

To address the problem of a trajectory difference identification attack when a user uses location-based services for continuous queries, this paper provides an algorithm for generating a similar real-time trajectory to protect the user’s personal privacy based on trajectoryr-anonymity. The algorithm utilizes an anonymous server to generate a set of dummy locations in real time with the real location of the user, and these locations are composed of similar trajectories of the real user to make the real trajectory fuzzy. The probability of successful trajectory difference identification attack is then reduced. This algorithm achieves real-time trajectory anonymity in continuous location queries. Performance analysis and simulation with other algorithms further verify the effectiveness of the presented algorithm in protecting a user’s privacy, as well as the efficiency of the algorithm.

location based service; continuous query; privacy preservation; dummy location; real time trajectory anonymity; similar trajectory

2016-05-20.

日期：2017-04-26.

國家自然科學基金項目(61472097);高等學校博士學科點專項科研基金項目(20132304110017);黑龍江省自然科學基金項目(F2015022).

張磊(1982-),男, 講師,博士研究生； 馬春光(1974-),男,教授,博士生導師.

馬春光,E-mail：machunguang@hrbeu.edu.cn.

10.11990/jheu.201605070

TP311

A

1006-7043(2017)07-1173-06

網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170426.1802.082.html