張少波,劉 琴,李 雄,王國軍
(1. 湖南科技大學(xué)計算機科學(xué)與工程學(xué)院 湖南 湘潭 411201;2. 湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082;3. 廣州大學(xué)計算機科學(xué)與教育軟件學(xué)院 廣州 510006)
目前,基于位置服務(wù)(location-based service, LBS)已廣泛應(yīng)用于軍事、商業(yè)和民生等領(lǐng)域[1]。用戶通過 LBS可以獲得當(dāng)前位置附近的興趣點(points of interests, POIs),如最近的影院、醫(yī)院和餐館等[2]。根據(jù)用戶連續(xù)的LBS查詢,攻擊者可能分析出特定用戶軌跡的敏感信息,如家庭住址、生活習(xí)慣和健康狀況等行為特征[3]。蘋果手機引發(fā)的“隱私門”風(fēng)波,就是通過LBS泄露用戶的隱私。因此,LBS中的軌跡隱私保護(hù)已成為急需解決的問題。
在連續(xù)LBS查詢中,學(xué)者已提出一些軌跡隱私保護(hù)方法,主要分為兩類結(jié)構(gòu)[4]:點對點和基于可信第三方(trusted third party, TTP)的中心服務(wù)器結(jié)構(gòu)。在點對點結(jié)構(gòu)中,文獻(xiàn)[5]最先提出了用戶協(xié)作的點對點匿名算法。文獻(xiàn)[6]提出了一種通過用戶緩存相互合作的隱私保護(hù)方法。但在這種結(jié)構(gòu)中,用戶發(fā)送的查詢需要進(jìn)行匿名或變換處理,對終端將會產(chǎn)生較大開銷。在基于TTP中心服務(wù)器結(jié)構(gòu)中,引入一個可信匿名器作為移動用戶和位置服務(wù)提供商(location service provider, LSP)之間的中間體,它負(fù)責(zé)對用戶的查詢進(jìn)行泛化處理,形成一個包括k個用戶的匿名域[7]。文獻(xiàn)[8]首次提出在第三方服務(wù)器進(jìn)行匿名的TTP框架。文獻(xiàn)[9]提出了一種社交網(wǎng)絡(luò)中軌跡隱私的保護(hù)方法。文獻(xiàn)[10]基于TTP結(jié)構(gòu)提出一種時間混淆技術(shù),攻擊者很難重構(gòu)用戶的軌跡。文獻(xiàn)[11]基于 TTP結(jié)構(gòu)和假位置思想,提出一種在路網(wǎng)環(huán)境的連續(xù)查詢方法。文獻(xiàn)[12]針對怎樣使用激勵機制而設(shè)計了兩種方案來取得K匿名位置隱私。但在這些基于TTP結(jié)構(gòu)的方法中,用戶每次查詢得到精確結(jié)果后,往往將候選結(jié)果集丟棄。在連續(xù)的LBS范圍查詢中,相鄰查詢點的范圍總存在一定的相交區(qū)域。如果這些相交區(qū)域在后續(xù)查詢點又向LSP查詢,將會加大用戶信息暴露給LSP的風(fēng)險,也會增加LBS服務(wù)器的開銷。
針對基于TTP結(jié)構(gòu)存在的局限性,本文提出一種基于緩存候選結(jié)果集(cache candidate result set,CCRS)的軌跡隱私保護(hù)方法。該方法利用緩存思想,在用戶端和匿名器中緩存用戶每次查詢得到的候選結(jié)果集,供移動軌跡上的后續(xù)查詢點使用,以減少用戶與LBS服務(wù)器之間的交互,降低用戶軌跡信息暴露給LBS服務(wù)器的風(fēng)險。
圖1 基于CCRS的軌跡隱私保護(hù)模型
圖1為基于CCRS的軌跡隱私保護(hù)模型,它主要包括用戶、匿名器和LBS服務(wù)器3類實體,其具體工作過程為:1) 用戶發(fā)送查詢時,先確定查詢范圍內(nèi)包含的各網(wǎng)格單元標(biāo)識,并在用戶端緩存中查找。如果能找到這些網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集,則返回給用戶;否則將未查找到的網(wǎng)格單元標(biāo)識發(fā)送給匿名器。2) 匿名器收到用戶的這些網(wǎng)格單元標(biāo)識后,在其緩存中查找匹配。如果匿名器緩存有這些網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集,則返回查詢結(jié)果;否則基于Markov模型的移動位置預(yù)測方法,在匿名器中形成k-匿名域后再發(fā)送給LSB服務(wù)器查詢。3) LBS服務(wù)器根據(jù)匿名域范圍,查詢各網(wǎng)格單元內(nèi)包含的POIs,并將各網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集返回給匿名器。4) 匿名器將各網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集更新到緩存,并與用戶需要查詢的網(wǎng)格單元標(biāo)識進(jìn)行匹配。如果相等,則將該網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集發(fā)送給用戶。5) 用戶將查詢匹配得到的網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集更新到緩存,并將得到的匹配候選結(jié)果集進(jìn)行過濾求精,最后得到精確結(jié)果。
定義 1 緩存隱私度量:根據(jù)信息熵對用戶位置隱私度的度量,基于緩存的隱私度量可表示為[13-14]:
式中,表示緩存中能找到的網(wǎng)格單元標(biāo)識數(shù);表示需向LBS服務(wù)器查詢的網(wǎng)格單元標(biāo)識數(shù);m2表示網(wǎng)格單元數(shù)目;H(g)表示真實網(wǎng)格單元標(biāo)識在查詢g中的不確定性。在查詢過程中,網(wǎng)格單元標(biāo)識的命中率可表示為:
式(1)可變換為:
可以看出,通過提高緩存命中率可增強用戶的位置隱私度。
用戶的移動軌跡可以是n階的馬爾科夫鏈,可表示為具有時序性的移動軌跡點序列,每個移動軌跡點pi的所處移動位置li只與其前面的n個移動軌跡點{pi-n+1,pi-n+2, … ,pi-1,pi}相關(guān)[15]:
式中,pil=li表示第i次移動軌跡點pi的位置是li。
對于前n個移動軌跡點組成的用戶軌跡,可預(yù)測求解具有最大概率的移動位置:
式中,lp表示用戶移動的預(yù)測位置。當(dāng)有n個候選移動位置時,通過計算所有移動位置lk是目標(biāo)預(yù)測位置的概率,以預(yù)測用戶真實的目標(biāo)位置lp。
圖2所示為基于CCRS的軌跡隱私保護(hù)工作過程,主要分為5個步驟,下面將分別進(jìn)行介紹。
圖2 基于CCRS的軌跡隱私保護(hù)工作過程
用戶先將查詢范圍內(nèi)網(wǎng)格結(jié)構(gòu)定義為:
式中, (x1,y1)、 (x2,y2)表示能確定用戶查詢范圍的兩個位置坐標(biāo);m×m表示劃分的網(wǎng)格數(shù)目。各網(wǎng)格單元都有唯一的標(biāo)識(xi,yj),可表示為:
式中,ci、rj分別為列、行標(biāo)識,1 ≤i,j≤m;(xi,yi)為查詢范圍內(nèi)的任意點。
用戶根據(jù)查詢半徑R,確定需要查詢的網(wǎng)格單元標(biāo)識,并在用戶端緩存中查找。如果能找到所有網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集,則直接對候選結(jié)果集進(jìn)行求精,得到精確結(jié)果,否則將未找到的網(wǎng)格單元標(biāo)識形成標(biāo)識集Ih。
式中,n為移動軌跡上的連續(xù)查詢點次數(shù)。最后用戶將需要查詢的網(wǎng)格單元標(biāo)識集Ih、隨機生成的密鑰Ku、用戶當(dāng)前位置Lh和運動方向Dh、網(wǎng)格結(jié)構(gòu)Grids以及查詢內(nèi)容Content組成用戶的請求消息,并使用匿名器的公鑰PKa對請求消息進(jìn)行非對稱加密形成MSGua發(fā)送給匿名器。
當(dāng)匿名器收到MSGua后,先用自己的私鑰aSK對MSGua解密,獲得標(biāo)識集hI,然后在匿名器緩存中查找。如果能找到網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集,則返回給用戶端。否則匿名器對未查找到的網(wǎng)格單元標(biāo)識進(jìn)行匿名處理。匿名時采用基于Markov模型的移動位置預(yù)測方法,預(yù)測用戶在移動過程中的下一個查詢位置。最后根據(jù)該預(yù)測位置形成匿名域,以提高下次查詢的命中率。
基于Markov模型的移動位置預(yù)測主要從移動用戶歷史軌跡中獲取一些有意義的物理位置,并通過統(tǒng)計概率模型來預(yù)測該用戶的移動位置。本文利用文獻(xiàn)[16]中提出的基于時間距離約束的網(wǎng)格聚類算法,先將用戶的歷史軌跡數(shù)據(jù)映射到定義的網(wǎng)格,獲得所有停留點集合 S P = { s p1, sp2,… ,s pn},并以sp作為輸入,通過聚類方法聚集成停留區(qū)域集合R= {r1,r2,… ,rN},其中ri是一個停留點spi的集合。然后可將用戶移動軌跡表示為連續(xù)的軌跡序列Tra =ri, … ,rj(ri,rj∈R)。因此,通過輸入用戶每條歷史軌跡序列,可獲得移動對象的歷史停留區(qū)域序列 T ra = {r1,r2, … ,rN},它也可表示為狀態(tài)變量序列X= {x1,x2,… ,xN},且每個停留區(qū)域?qū)?yīng)一個狀態(tài)。如果移動對象潛在的停留區(qū)域數(shù)目為m,則它的狀態(tài)空間集合為S=s1,s2,… ,sm。最后用戶根據(jù)這些狀態(tài),建立用戶的狀態(tài)轉(zhuǎn)移矩陣Pr = P r(R[i],R[j])。根據(jù)文獻(xiàn)[17]基于運動趨勢的移動對象預(yù)測算法,對每一個停留區(qū)域計算其移動概率,取其概率值最大的為Rp,并根據(jù)如下公式計算預(yù)測移動位置lp:
當(dāng)獲得移動用戶下一個查詢位置lp后,匿名器根據(jù)用戶需要查詢的網(wǎng)格單元標(biāo)識集hI和網(wǎng)格結(jié)構(gòu)Grids,選擇k個用戶所在的網(wǎng)格單元形成匿名區(qū)域Region。最后匿名器將匿名域Region、網(wǎng)格結(jié)構(gòu)Grids以及查詢內(nèi)容Content組成新的查詢請求消息,并使用LBS服務(wù)器公鑰PKS對它們進(jìn)行非對稱加密形成MSGas,再發(fā)送給LBS服務(wù)器。
LBS服務(wù)器收到請求消息MSGas后,先使用自己的私鑰SKS解密MSGas,獲得Grids、Region和Content。然后LBS服務(wù)器根據(jù)Grids中 (x1,y1)、(x2,y2)和m恢復(fù)用戶指定的網(wǎng)格結(jié)構(gòu),并根據(jù)查詢內(nèi)容Content搜索匿名域Region中網(wǎng)格單元包含的POIs,得到g個POIs。如果第j個POI的位置為(xi,yj) (1 ≤i,j≤g),則可計算它所在的網(wǎng)格單元標(biāo)識,并可獲得每個網(wǎng)格單元標(biāo)識(cz,rt)包含的興趣點集。最后,LBS服務(wù)器將這些查詢到的興趣點網(wǎng)格集φr,形成候選結(jié)果集MSG,用匿名器的公鑰PKa進(jìn)行加密形成消息MSGsa返回給匿名器:
首先,匿名器解密MSGsa,得到匿名域中每個網(wǎng)格單元標(biāo)識對應(yīng)的POIs,并將它更新到匿名器緩存。匿名器更新時,根據(jù)用戶當(dāng)前位置Lh和運動方向hD,需替換與用戶運動方向相反、且距離移動用戶下一個目標(biāo)預(yù)測位置lp最遠(yuǎn)的POIs。然后,匿名器將查詢到的網(wǎng)格單元標(biāo)識集rφ與用戶需要查詢區(qū)域的網(wǎng)格單元標(biāo)識hI進(jìn)行匹配,找到用戶需要查詢的網(wǎng)格單元標(biāo)識及對應(yīng)的POIs。最后,匿名器使用用戶的密鑰uK,對查詢到的網(wǎng)格單元標(biāo)識及包含的POIs進(jìn)行對稱加密,并組成MSGau返回給查詢用戶:
用戶收到MSGau后,首先用密鑰uK解密MSGau獲得所需查詢網(wǎng)格單元中的每個POI的精確位置。然后,用戶將得到的網(wǎng)格單元標(biāo)識及包含的POIs更新到用戶端緩存。最后,用戶計算在自己查詢區(qū)域之內(nèi)的POIs,得到精確查詢結(jié)果。
在用戶初次查詢時,因緩存中沒有候選結(jié)果集,用戶發(fā)送的查詢需經(jīng)過匿名器匿名后,再轉(zhuǎn)發(fā)給LBS服務(wù)器查詢,LBS服務(wù)器收到的查詢請求為MSGas。MSGas中包括匿名域Region、查詢內(nèi)容Content以及網(wǎng)格結(jié)構(gòu)Grids,從這些信息中LBS服務(wù)器不能獲得用戶的真實位置。經(jīng)匿名后的Region中,它至少包含k個用戶,LBS服務(wù)器能成功猜到是指定用戶的概率只有1k。
在用戶移動軌跡上后續(xù)點的查詢過程中,用戶可以通過緩存直接得到部分或全部查詢結(jié)果。如果用戶直接從緩存中取得全部結(jié)果,他將不必與LBS服務(wù)器進(jìn)行交互,因此,LBS服務(wù)器不能獲得用戶的任何信息。否則,在緩存中沒有查找到的網(wǎng)格單元將形成匿名域,再發(fā)送給LBS服務(wù)器查詢,但該匿名域不一定包含用戶的真實位置。所以,LSP通過這些連續(xù)查詢數(shù)據(jù)不能獲得指定的用戶和真實位置,CCRS方法能抵制LSP的連續(xù)查詢推斷攻擊。
當(dāng)用戶發(fā)送請求消息給匿名器時,用匿名器公鑰PKa對MSGua進(jìn)行了非對稱加密,偵聽者沒有匿名器私鑰SKa,不能解密MSGua得到有用信息。當(dāng)匿名器將請求消息轉(zhuǎn)發(fā)給LBS服務(wù)器時,LBS的公鑰PKs對MSGua進(jìn)行了非對稱加密,同樣偵聽者沒有LBS的私鑰SKS,不能解密MSGas得到有用信息。在候選結(jié)果返回用戶的過程中,非對稱加密函數(shù)E(?)和對稱加密函數(shù)En(?)分別對MSGsa、MSGau進(jìn)行了加密,偵聽者沒有匿名器的私鑰SKa和用戶密鑰Ku,不能解密MSGsa和MSGau。因此,偵聽者既不能獲得任何有用的信息,更不能得到用戶的精確位置,CCRS方法能抵制偵聽者的攻擊。
實驗采用Brinkhoff移動對象生成器[18],輸入德國奧爾登堡市交通網(wǎng)絡(luò)圖,并生成10 000個移動對象。實驗隨機選取Bob的移動軌跡作為實驗對象,圖3為移動用戶Bob的運動軌跡,表1為實驗參數(shù)設(shè)置。實驗運行平臺為Windows 7操作系統(tǒng),Intel(R)Core(TM) i5-4590處理器、4 GB內(nèi)存。
圖3 移動用戶Bob的運動軌跡
表1 實驗參數(shù)設(shè)置
當(dāng)n= 3 0時,對比CCRS中使用Markov與No Markov方案對兩級緩存平均命中率的影響。由圖4可知,通過基于Markov模型的移動位置預(yù)測進(jìn)行k-匿名的CCRS比沒有使用Markov模型進(jìn)行k-匿名的緩存命中率要高,同時緩存命中率隨著匿名度k的增大而增大。因為通過基于Markov模型移動位置預(yù)測方法,可以預(yù)測到移動用戶的下一個移動點位置,然后根據(jù)該位置選擇周圍k個用戶所在的網(wǎng)格單元作為匿名域,可以預(yù)先將下一點需要查詢的網(wǎng)格單元提前進(jìn)行查詢,相對于沒有Markov的方法,使用Markov的CCRS方法能提高緩存的命中率。同時匿名度越高,相應(yīng)緩存中的網(wǎng)格單元標(biāo)識及包含的候選結(jié)果集就越多,在緩存中能找到用戶需要查詢的網(wǎng)格單元標(biāo)識的可能性就越大,相應(yīng)的緩存命中率就高。因此,匿名度k越大,緩存命中率就越高。
圖4 緩存平均命中率對比
圖5為LBS服務(wù)器的性能對比圖。當(dāng)k= 3 0時,對比 CCRS與 Gedik[9]、Hwang[10]方案對 LBS服務(wù)器性能的影響。由圖5可知,在LBS服務(wù)器時間開銷和通信開銷上,隨著n的增大,CCRS相對于Gedik、Hwang方案優(yōu)勢越大。因為Gedik、Hwang方案中用戶發(fā)送的查詢經(jīng)匿名器匿名后,都需在LBS服務(wù)器中對整個匿名域進(jìn)行查詢,并將查詢獲得的候選結(jié)果集返回給用戶。在CCRS方案中,用戶端和匿名器使用二級緩存機制,用戶發(fā)送查詢時,首先在二級緩存中查詢,只有在緩存中找不到需要查詢的網(wǎng)格單元標(biāo)識時,再經(jīng)匿名后到LBS服務(wù)器中查詢,這樣有效減少了LBS服務(wù)器查詢的次數(shù)和通信開銷。因此,在LBS服務(wù)器的時間開銷和通信開銷上,CCRS方案相對于Gedik、Hwang方案有較大的優(yōu)勢。
圖5 LBS服務(wù)器的性能對比
本文提出了一種基于緩存候選結(jié)果集的軌跡隱私保護(hù)方法,利用緩存思想和基于Markov移動位置預(yù)測進(jìn)行k-匿名的技術(shù),減少用戶與LBS服務(wù)之間的交互,提高緩存的命中率和用戶的軌跡隱私。安全分析表明該方法能抵制連續(xù)查詢和偵聽者的攻擊。實驗結(jié)果顯示,與 Gedik、Hwang方案比較,CCRS方法能減少LBS服務(wù)器的開銷。但CCRS方法只考慮用網(wǎng)格單元內(nèi)用戶的數(shù)目形成k-匿名域,因此在下一步工作中,將會考慮用戶發(fā)送查詢的概率形成匿名域,以進(jìn)一步提高用戶的位置隱私。
[1]PRIMAULT V, BOUTET A, MOKHTAR S B, et al.Adaptive location privacy with ALP[C]//Proceedings of the 35th Symposium on Reliable Distributed Systems (SRDS).New Jersey, USA: IEEE, 2016: 269-278.
[2]YI X, PAULET R, BERTINO E, et al. Practical approximateknearest neighbor queries with location and query privacy[J]. IEEE Transactions on Knowledge and Data Engineering,2016, 28(6): 1546-1559.
[3]張學(xué)軍, 桂小林, 伍忠東. 位置服務(wù)隱私保護(hù)研究綜述[J].軟件學(xué)報, 2015, 26(9): 2373-2395.ZHANG Xue-jun, GUI Xiao-lin, WU Zhong-dong. Privacy preservation for location-based services: a survey[J]. Journal of Software, 2015, 26(9): 2373-2395.
[4]張少波, 劉琴, 王國軍. 基于網(wǎng)格標(biāo)識匹配的位置隱私保護(hù)方法[J]. 電子與信息學(xué)報, 2016, 38(9): 2173-2179.ZHANG Shao-bo, LIU Qin, WANG Guo-jun. The method of location privacy protection based on grid identifier matching[J]. Journal of Electronics & Information Technology, 2016, 38(9): 2173-2179.
[5]CHOW C Y, MOKBEL M F, LIU Xuan. A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]//Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems. New York, USA: ACM, 2006:171-178.
[6]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.
[7]CORSER G P, FU H R, BANIHANI A. Evaluating location privacy in vehicular communications and applications[J].IEEE Transactions on Intelligent Transportation Systems,2016, 17(9): 2658-2667.
[8]GEDIK B, LIU L. Protecting location privacy with personalizedk-anonymous: Architecture and algorithms[J].IEEE Transaction on Mobile Computing, 2008, 7(1): 1-18.
[9]霍崢, 孟小峰, 黃毅. PrivateChechIn: 一種移動社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法與進(jìn)展[J]. 計算機學(xué)報, 2013,36(4): 716-726.HUO Zheng, MENG Xiao-feng, Huang Yi. PrivateChechIn:Trajectory privacy-preserving for chech-in services in MSNS[J]. Chinese journal of computers, 2013, 36(4):716-726.
[10]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.
[11]周長利, 馬春光, 楊松濤. 路網(wǎng)環(huán)境下保護(hù)LBS位置隱私的連續(xù)KNN查詢方法[J]. 計算機研究與發(fā)展, 2015,52(11): 2628-2644.ZHOU Chang-li, MA Chun-guang, YANG Song-tao.Location privacy-preserving method for LBS continuous KNN query in road networks[J]. Journal of Computer Research and Development, 2015, 52(11): 2628-2644.
[12]ZHANG Y, TONG W, ZHONG S. On designing satisfaction-ratio-aware truthful incentive mechanisms fork-anonymity location privacy[J]. IEEE Transactions on Information Forensics and Security, 2016, 11(11):2528-2541.
[13]NIU B, LI Q, ZHU X, et al. Enhancing privacy through caching in location-based services[C]//Proceeding of the IEEE INFOCOM 2015. New Jersey, USA: IEEE, 2015:1017-1025.
[14]XIAO C, CHEN Z, WANG X, et al. DeCache: a decentralized two-level cache for mobile location privacy protection[C]//Proceedings of the Sixth International Conference on Ubiquitous and Future Networks(ICUFN).New Jersey, USA: IEEE, 2014: 81-86.
[15]CHEN M, LIU Y, YU X. NLPMM: a next location predictor with Markov modeling[C]//Proceeding of the 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining. New York, USA: Springer, 2014:186-197.
[16]ZHENG V, ZHENG Y, XIE X, et al. Collaborative location and activity recommendations with GPS history data[C]//Proceeding of the 19th International Conference on World Wide Web. New York, USA: ACM, 2010: 1029-1038.
[17]李雯, 夏士雄, 劉峰, 等. 基于運動趨勢的移動對象位置預(yù)測[J]. 通信學(xué)報, 2014, 35(2): 46-53.LI Wen, XIA Shi-xiong, LIU Feng, et al. Location prediction algorithm based on movement tendency[J].Journal of Communications, 2014, 35(2): 46-53.
[18]BRINKHOFF T. Generating traffic data[J]. Bulletin of the Technical Committee Data Engineering, 2003, 26(2):19-25.