基于緩存的位置隱私保護(hù)方法研究

馮亞平， 康海燕

(北京信息科技大學(xué) 信息管理學(xué)院 北京 100192)

0 引言

隨著“互聯(lián)網(wǎng)+”時(shí)代的發(fā)展，智能手機(jī)和其他電子移動(dòng)設(shè)備已成為人們?nèi)粘Ｉ钪胁豢苫蛉钡囊徊糠?，基于位置的服?wù)也得到了廣泛的應(yīng)用.用戶在享受位置服務(wù)所帶來便利的同時(shí)，也承擔(dān)著位置隱私或軌跡隱私泄露的風(fēng)險(xiǎn).例如，人們可以使用基于位置的服務(wù)搜索附近的商場、醫(yī)院、銀行、餐廳以及酒店等，攻擊者有可能根據(jù)用戶在服務(wù)請(qǐng)求中的地理位置和請(qǐng)求內(nèi)容推斷出用戶的工作地址、生活習(xí)慣等.現(xiàn)有的隱私保護(hù)技術(shù)[1-4]主要依賴獨(dú)立式結(jié)構(gòu)、集中式可信第三方結(jié)構(gòu)和分布式點(diǎn)對(duì)點(diǎn)結(jié)構(gòu).在基于可信第三方結(jié)構(gòu)的位置隱私保護(hù)技術(shù)中，文獻(xiàn)[5]首次引入匿名服務(wù)器，將數(shù)據(jù)庫中k-匿名隱私保護(hù)模型應(yīng)用到位置服務(wù)隱私保護(hù)中,但是要使個(gè)人用戶保持匿名，位置匿名服務(wù)器必須在地理區(qū)域擁有足夠多的用戶，否則無法匿名.為了滿足用戶的不同隱私需求，文獻(xiàn)[6]提出了一種私有k-匿名模型，該模型使每個(gè)用戶可以設(shè)置自己的隱私需求匿名度，并且每個(gè)用戶的隱私需求匿名度可以不同，通過形成匿名區(qū)來實(shí)現(xiàn)位置隱私保護(hù)，但是有時(shí)在某種程度上也會(huì)暴露該用戶所在的區(qū)域.

文獻(xiàn)[7-11]均采用第三方服務(wù)器進(jìn)行匿名的TTP框架，負(fù)責(zé)對(duì)用戶的查詢進(jìn)行泛化處理，形成包含k個(gè)用戶的匿名區(qū)域，從而實(shí)現(xiàn)對(duì)用戶位置的隱私保護(hù).在這些基于TTP 框架的位置隱私研究方法中，一方面，不同的用戶請(qǐng)求服務(wù)均需要在中心服務(wù)器中進(jìn)行匿名,進(jìn)而得到反饋結(jié)果，容易成為性能的瓶頸和集中攻擊點(diǎn)；另一方面，用戶每一次請(qǐng)求查詢結(jié)束后往往將匿名候選結(jié)果集丟棄，當(dāng)用戶在連續(xù)的 LBS 范圍請(qǐng)求查詢時(shí)，相鄰查詢點(diǎn)的范圍總存在一定的相交區(qū)域，如果這些相交區(qū)域在后續(xù)查詢點(diǎn)又進(jìn)行請(qǐng)求查詢，這將會(huì)增加 LBS 服務(wù)器的開銷，也會(huì)加大用戶信息暴露給LBS服務(wù)器的風(fēng)險(xiǎn)，從而降低了對(duì)用戶隱私的保護(hù)度.文獻(xiàn)[12]提出了一種簡單分布式的軌跡隱藏策略，該策略不依賴可信的第三方，采用虛擬路徑規(guī)劃方法，為了保證用戶發(fā)送的連續(xù)位置服務(wù)請(qǐng)求包括足夠多的真實(shí)可信的軌跡,還需要發(fā)送其他假的位置服務(wù)請(qǐng)求，從而使位置服務(wù)請(qǐng)求打破時(shí)間與空間的關(guān)聯(lián)性，不足之處是發(fā)送大量假的服務(wù)請(qǐng)求增大了通信開銷以及LBS服務(wù)器的計(jì)算開銷.文獻(xiàn)[13]為用戶設(shè)計(jì)了一種基于假位置和用戶協(xié)作的隱私保護(hù)方案，該方案采用熵來衡量匿名化程度，并且在選擇假位置的時(shí)候考慮了攻擊者可能利用的邊信息，使所選擇的假位置與用戶的真實(shí)位置具有相近的歷史查詢概率，然而該方案的通信開銷和存儲(chǔ)開銷均較高.文獻(xiàn)[14]提出一種移動(dòng)軌跡的位置隱私保護(hù)方法DUMMY-T, 旨在保護(hù)用戶隱私免遭背景攻擊, 首先通過DLG算法生成假位置, 然后通過DPC算法生成虛假路徑, 保證了移動(dòng)位置隱私安全，不足之處是假位置和虛擬路徑的生成效率不高.文獻(xiàn)[15]提出一種基于近似匹配的假位置k-匿名位置隱私保護(hù)方法DBAM，該方法采用獨(dú)立式結(jié)構(gòu)，保證了假位置之間物理分散性和語義多樣化,雖然假位置的生成效率在一定程度上優(yōu)于DUMMY-T方法，但效率還有待提高.文獻(xiàn)[16]提出一種基于緩存的時(shí)空擾動(dòng)位置隱私保護(hù)方法，該方法采用中心匿名服務(wù)器結(jié)構(gòu)，不僅保護(hù)用戶位置點(diǎn)的隱私，還保護(hù)其時(shí)間相關(guān)性的移動(dòng)軌跡隱私，但該方法需要找到一種更優(yōu)的數(shù)據(jù)匹配規(guī)則，否則會(huì)出現(xiàn)性能瓶頸問題.

綜上所述，現(xiàn)有方案的TTP框架存在局限性，服務(wù)質(zhì)量較低，通信開銷大.本文提出了一種不依賴可信第三方的基于緩存的中國剩余定理(caching-based Chinese remainder theorem,CCRT)位置隱私保護(hù)方法；在客戶端加入了緩存機(jī)制，減少了用戶與LBS服務(wù)器之間的交互；根據(jù)用戶不同等級(jí)的隱私需求，采用中國剩余定理算法計(jì)算真實(shí)地理位置等價(jià)集，滿足了用戶的個(gè)性化隱私需求，同時(shí)也降低了用戶信息暴露給LBS服務(wù)器的風(fēng)險(xiǎn).

1 基于緩存的中國剩余定理算法

1.1 理論分析

在基于位置服務(wù)的隱私保護(hù)研究中，主要存在以下3個(gè)問題.

1) 在采用集中式結(jié)構(gòu)的位置服務(wù)隱私保護(hù)方法中，每次的服務(wù)請(qǐng)求都需要通過一個(gè)位置匿名服務(wù)器轉(zhuǎn)發(fā)后再送到LBS服務(wù)器，這種方法非常依賴于位置匿名服務(wù)器，一旦位置匿名服務(wù)器被攻擊者入侵，所有用戶的隱私安全將會(huì)受到威脅. 此外，所有用戶的請(qǐng)求查詢都要通過匿名服務(wù)器的轉(zhuǎn)發(fā)，使得位置匿名服務(wù)器成為系統(tǒng)性能的瓶頸.例如，在基于k-匿名方案中，基本方法是將用戶的真實(shí)位置數(shù)據(jù)隱藏在用戶和至少k-1個(gè)其他鄰居訪問點(diǎn)組成的位置集合中，但這種傳統(tǒng)的方法往往由于無法找到k-1個(gè)同時(shí)存在的鄰居訪問點(diǎn)而無法順利獲取位置服務(wù)，并且會(huì)在某種程度上暴露該用戶所在區(qū)域，無法保證高級(jí)別的位置隱私保護(hù)請(qǐng)求，從而影響服務(wù)質(zhì)量.

2) 在位置服務(wù)中，由于用戶有不同級(jí)別的位置隱私保護(hù)請(qǐng)求，因此在提供服務(wù)時(shí)，要依據(jù)用戶的不同隱私需求對(duì)位置進(jìn)行隱私保護(hù).

3) 許多移動(dòng)用戶向LBS服務(wù)器查詢相似的服務(wù)請(qǐng)求，服務(wù)器重復(fù)地對(duì)相似的請(qǐng)求進(jìn)行查詢并返回結(jié)果，從而加大了整個(gè)系統(tǒng)的通信開銷.從這個(gè)角度來說，對(duì)服務(wù)數(shù)據(jù)進(jìn)行緩存是可行的.

本方案中的核心理論是中國剩余定理算法，利用該算法的等價(jià)集思想，將等價(jià)集的概念與地理坐標(biāo)相結(jié)合獲取虛擬點(diǎn)位置，得到用戶真實(shí)位置等價(jià)集，并且獲取的位置點(diǎn)之間的關(guān)聯(lián)能夠應(yīng)對(duì)路徑分析的攻擊，從而對(duì)真實(shí)位置進(jìn)行保護(hù).利用該算法改變等價(jià)集中虛擬位置的個(gè)數(shù)，從而保證用戶在順利獲取位置服務(wù)時(shí)能滿足用戶不同的隱私需求.

1.2 解決方案

本文提出了一種不依賴可信第三方的基于緩存的中國剩余定理位置隱私保護(hù)方法，其基本模型如圖1所示.該模型不依賴可信的第三方服務(wù)器，模型架構(gòu)主要包括移動(dòng)客戶端和LBS服務(wù)器兩部分.客戶端新增了后臺(tái)處理模塊，包括處理區(qū)、計(jì)算區(qū)和緩存區(qū).處理區(qū)主要是對(duì)服務(wù)請(qǐng)求以及請(qǐng)求結(jié)果進(jìn)行處理；計(jì)算區(qū)主要是計(jì)算真實(shí)位置的等價(jià)集；緩存區(qū)主要是存儲(chǔ)用戶一定時(shí)間內(nèi)請(qǐng)求的服務(wù)數(shù)據(jù).用戶在使用基于位置的服務(wù)時(shí)，位置隱私保護(hù)工作(例如預(yù)處理、等價(jià)集的生成、篩選請(qǐng)求服務(wù)的返回結(jié)果等)都是由客戶端獨(dú)立完成的.

圖1 基于緩存的中國剩余定理位置隱私保護(hù)模型Fig.1 Caching-based Chinese remainder theorem model for location privacy protection

整個(gè)服務(wù)的基本處理流程如下：若用戶U1第一次在所在位置請(qǐng)求服務(wù)時(shí)，首先為了滿足用戶不同等級(jí)的隱私需求，用戶自定義隱私需求并請(qǐng)求服務(wù)，后臺(tái)處理模塊中的計(jì)算區(qū)通過中國剩余定理算法對(duì)獲取的真實(shí)位置的經(jīng)緯度進(jìn)行計(jì)算，得到一個(gè)關(guān)于經(jīng)緯度的等價(jià)集,其中用戶自定義的隱私需求包括等價(jià)集中虛擬位置點(diǎn)的個(gè)數(shù)以及以真實(shí)位置為圓心獲取虛擬點(diǎn)的范圍；而后客戶端將包含真實(shí)位置與等價(jià)集的服務(wù)請(qǐng)求發(fā)送給LBS服務(wù)器進(jìn)行查詢，從而達(dá)到多個(gè)位置同時(shí)請(qǐng)求服務(wù)的效果；最后LBS服務(wù)器返回所有位置的請(qǐng)求結(jié)果，再經(jīng)過客戶端處理將真實(shí)位置的請(qǐng)求結(jié)果發(fā)送給用戶并存儲(chǔ)于緩存區(qū).

若用戶U1在某位置點(diǎn)請(qǐng)求服務(wù)時(shí)，如果之前一段時(shí)間內(nèi)，用戶可能在該點(diǎn)或相近或等價(jià)的位置請(qǐng)求過相同或相似的服務(wù)，那么此服務(wù)已存儲(chǔ)于緩存區(qū)，緩存區(qū)查詢到此服務(wù)后會(huì)將結(jié)果直接反饋給用戶，無須再進(jìn)行等價(jià)集計(jì)算和請(qǐng)求LBS服務(wù)器，這樣減少了用戶與服務(wù)器之間的交互，破壞了用戶U1在時(shí)間與空間上的相關(guān)性，從而對(duì)用戶的軌跡隱私起到了一定的保護(hù)作用.中國剩余定理算法也具有一定的自我處理能力，一定時(shí)間后會(huì)自動(dòng)刪除緩存區(qū)中一些經(jīng)常訪問不到的服務(wù)請(qǐng)求數(shù)據(jù)，以存儲(chǔ)更多的其他請(qǐng)求數(shù)據(jù).

2 基于緩存的中國剩余定理位置隱私保護(hù)算法

2.1 相關(guān)定義

定義1服務(wù)請(qǐng)求的數(shù)據(jù)格式.用戶提交服務(wù)請(qǐng)求的數(shù)據(jù)格式為Q={(x,y),t,r}，客戶端發(fā)送給LBS服務(wù)器的服務(wù)請(qǐng)求數(shù)據(jù)格式為Q′={(x,y),G,t,r}，其中：(x,y)表示用戶地理位置的經(jīng)緯度；t表示請(qǐng)求服務(wù)的時(shí)間；r表示請(qǐng)求服務(wù)的內(nèi)容；G表示地理位置的等價(jià)集.

定義2隱私級(jí)別.用戶在提交服務(wù)請(qǐng)求時(shí)，可根據(jù)不同的需求對(duì)位置設(shè)置不同的隱私等級(jí)，從而滿足用戶的個(gè)性化隱私需求.隱私級(jí)別由 (n,f)共同決定，其中：n表示等價(jià)集中虛擬位置點(diǎn)的個(gè)數(shù)；f表示以真實(shí)位置為圓心獲取虛擬點(diǎn)的范圍.n、f越大，該位置的隱私級(jí)別越高.

定義3等價(jià)集.由真實(shí)地理位置產(chǎn)生的等價(jià)位置的集合，用符號(hào)G來表示.若等價(jià)集G中有3個(gè)位置，則G={G1,G2,G3}.

定義4中國剩余定理(CRT).中國剩余定理一般是指孫子定理，即求解一元線性同余方程組問題.其表示式為

(1)

利用中國剩余定理的原理將式(1)用于位置隱私保護(hù)，根據(jù)式(1)對(duì)真實(shí)地理位置進(jìn)行計(jì)算，產(chǎn)生真實(shí)位置的等價(jià)集.客戶端將服務(wù)請(qǐng)求Q′發(fā)送給LBS服務(wù)器請(qǐng)求服務(wù)，此時(shí)真實(shí)位置隱藏在等價(jià)集中，成功保護(hù)了用戶的位置信息.假設(shè)n=3，其真實(shí)地理位置坐標(biāo)(x,y)=(116.231 7°, 39.542 7°),(m1,m2,m3)=(13, 17, 113), (n1,n2,n3)=(13, 45, 92)，具體計(jì)算過程如下.

(i) (x,y)=(116.231 7°, 39.542 7°)，整數(shù)化為(X,Y)=(1 162 317°, 395 427°).

(ii) 中國剩余定理同余方程組為

求解得

由此，通過中國剩余定理能夠得到互相不可區(qū)分的位置等價(jià)集.

定義5緩存命中率.緩存命中率表示由緩存機(jī)制為用戶提供服務(wù)請(qǐng)求的概率.其表示式為

(2)

式中：QC表示緩存提供服務(wù)請(qǐng)求的次數(shù)；QS表示LBS服務(wù)器提供服務(wù)請(qǐng)求的次數(shù).緩存命中率越高，用戶與LBS服務(wù)器的交互次數(shù)越少，位置隱私保護(hù)效果越好.

2.2 處理流程

該算法的處理步驟主要集中在客戶端的后臺(tái)處理模塊中，緩存區(qū)存儲(chǔ)一定時(shí)間內(nèi)的服務(wù)請(qǐng)求數(shù)據(jù)，與請(qǐng)求服務(wù)的時(shí)間無關(guān)，不受時(shí)間因素的影響.基于緩存的中國剩余定理算法的隱私保護(hù)流程如圖2所示.

圖2 基于緩存的中國剩余定理算法的隱私保護(hù)流程Fig.2 Privacy protection flowchart by caching-based Chinese remainder theorem

基于緩存的中國剩余定理位置隱私保護(hù)算法的具體步驟如下.

Step 1： 用戶提交LBS服務(wù)請(qǐng)求Q，并自定義用戶的隱私級(jí)別.

Step 2： 查詢緩存區(qū)是否存在該服務(wù)請(qǐng)求Q，若存在，跳轉(zhuǎn)Step 3；否則，跳轉(zhuǎn)Step 4.

Step 3： 緩存區(qū)將查詢結(jié)果直接反饋給用戶，請(qǐng)求完成.

Step 4： 通過中國剩余定理對(duì)獲取的真實(shí)位置的經(jīng)緯度進(jìn)行計(jì)算，得到一個(gè)關(guān)于真實(shí)位置經(jīng)緯度的等價(jià)集G.

Step 5： 將包括真實(shí)位置及其等價(jià)集G的服務(wù)請(qǐng)求Q′發(fā)送給 LBS服務(wù)器進(jìn)行查詢.

Step 6： LBS服務(wù)器進(jìn)行查詢后返回請(qǐng)求結(jié)果給客戶端.

Step 7： 客戶端對(duì)返回的結(jié)果進(jìn)行篩選并反饋給用戶，同時(shí)更新緩存區(qū)的數(shù)據(jù)，請(qǐng)求完成.

2.3 安全性分析

本方案中攻擊者主要依靠2種途徑竊取用戶的位置信息：一是攻擊者通過竊聽或監(jiān)控客戶端與服務(wù)器之間的通信獲取位置信息；二是攻擊者通過入侵LBS服務(wù)器從而監(jiān)控整個(gè)系統(tǒng)，侵犯用戶的隱私.本文所提出的基于緩存的中國剩余定理算法，在緩存機(jī)制下，使得用戶每一次發(fā)出的服務(wù)請(qǐng)求并非與LBS服務(wù)器都產(chǎn)生交互，當(dāng)用戶的服務(wù)請(qǐng)求無法在本地得到滿足時(shí)，就會(huì)向LBS服務(wù)器發(fā)送請(qǐng)求來得到服務(wù)數(shù)據(jù).由于等價(jià)集中真實(shí)位置與虛擬位置的識(shí)別度較低，即使攻擊者竊聽到某條記錄，也很難從位置等價(jià)集中分析出用戶的真實(shí)位置.LBS服務(wù)器雖然收集了一定量的用戶服務(wù)數(shù)據(jù)，但位置數(shù)據(jù)在空間和時(shí)間上并不是連續(xù)的，在最壞情況下，LBS服務(wù)器也只能等概率地猜測其中某個(gè)位置為用戶的真實(shí)位置，很難推測出位置軌跡.攻擊者的目標(biāo)是獲得用戶的位置信息，從而得到用戶的其他敏感信息.本方案中由于緩存機(jī)制在用戶的客戶端中，故假定由緩存機(jī)制提供位置服務(wù)的過程是安全的.

針對(duì)不可信位置服務(wù)提供商，從概率分布攻擊、同源攻擊和位置相似性攻擊這3種主要攻擊方式進(jìn)行安全性分析.

1) 針對(duì)概率分布攻擊，用戶利用中國剩余定理算法產(chǎn)生虛擬位置，將位置等價(jià)集G={G1,G2, …,Gn}作為匿名位置集合，并向服務(wù)提供商發(fā)送服務(wù)查詢請(qǐng)求.在這個(gè)過程中，不可信的位置服務(wù)提供商根據(jù)背景信息從匿名位置集合中獲得各位置單元的查詢概率，由于用戶每次的隱私需求不同，位置集合中位置個(gè)數(shù)不同，虛擬位置的產(chǎn)生范圍不同，位置服務(wù)提供商很難推斷出用戶真實(shí)位置的概率.

2) 針對(duì)同源攻擊，本方案利用緩存機(jī)制，用戶每次請(qǐng)求服務(wù)均將位置等價(jià)集中的n個(gè)應(yīng)答結(jié)果存儲(chǔ)在緩存中.當(dāng)用戶在同一位置且較短時(shí)間內(nèi)連續(xù)發(fā)送多個(gè)位置查詢請(qǐng)求時(shí)，由于緩存區(qū)已存儲(chǔ)該服務(wù)數(shù)據(jù)，在一定的時(shí)間間隔內(nèi)，任意查詢請(qǐng)求均可由緩存中的記錄作為應(yīng)答結(jié)果，有效減少用戶與不可信的LBS服務(wù)器的交互次數(shù)，降低了隱私泄露風(fēng)險(xiǎn).

3) 針對(duì)位置相似性攻擊，本方案在隱私級(jí)別中利用f表示以真實(shí)位置為圓心獲取虛擬點(diǎn)的范圍，通過用戶自定義f，可使用戶的真實(shí)位置與產(chǎn)生的虛假位置有一定的差距，從而保證虛假位置集合所形成的匿名區(qū)域中包含多種語義信息，即使不可信服務(wù)提供商根據(jù)查詢請(qǐng)求獲取到等價(jià)集中所有位置的相關(guān)信息，也無法根據(jù)語義特征推斷出用戶的軌跡信息.

因此，本文方案能夠有效地抵御擁有背景信息的攻擊者的概率分布攻擊、同源攻擊和位置相似性攻擊.

2.4 算法復(fù)雜度分析

時(shí)間復(fù)雜度方面: 基于緩存的中國剩余定理算法在用戶提出請(qǐng)求服務(wù)后，均需要先在緩存區(qū)進(jìn)行查找，并需要對(duì)緩存中位置集合的查詢概率進(jìn)行計(jì)算并排序.位置集合的大小為s，若在位置集合中查找到用戶請(qǐng)求服務(wù)的地理位置，則位置集合的查詢概率計(jì)算和排序的時(shí)間復(fù)雜度為O(1)；若沒有查找到，則還需要根據(jù)用戶的隱私級(jí)別(n,f)計(jì)算真實(shí)位置的等價(jià)集，計(jì)算等價(jià)集的時(shí)間復(fù)雜度為O(1).隨著請(qǐng)求次數(shù)的增多，緩存區(qū)存儲(chǔ)的數(shù)據(jù)會(huì)越多，位置集合的查詢概率計(jì)算和排序的復(fù)雜度將會(huì)增加O(s)，則總的算法時(shí)間復(fù)雜度為O(s).

空間復(fù)雜度方面:算法在處理過程中只是需要存儲(chǔ)臨時(shí)的變量，所需的內(nèi)存空間極少，總的算法空間復(fù)雜度為O(1).

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)和環(huán)境

收集了同一城市的100個(gè)用戶在3個(gè)月內(nèi)的請(qǐng)求服務(wù)數(shù)據(jù)，主要包含用戶的服務(wù)提交時(shí)間、經(jīng)緯度、請(qǐng)求內(nèi)容等信息.實(shí)驗(yàn)采用處理之后的數(shù)據(jù)，用戶的請(qǐng)求服務(wù)用Q={(x,y),t,r}來表示.本實(shí)驗(yàn)硬件環(huán)境為Intel(R) Core(TM)i5-5200U CPU，內(nèi)存4 GB，操作系統(tǒng)為Windows 10(×64)，實(shí)驗(yàn)開發(fā)環(huán)境為 Eclipse(Java)+MySQL.

3.2 實(shí)驗(yàn)過程與結(jié)果分析

3.2.1虛擬位置點(diǎn)測試 隨機(jī)選取了較活躍的3個(gè)用戶在某一天5時(shí)—21時(shí)的軌跡進(jìn)行測試，默認(rèn)用戶對(duì)請(qǐng)求位置的隱私級(jí)別均相等，其中n=3,f=20 km，即產(chǎn)生3個(gè)虛擬位置點(diǎn)且產(chǎn)生虛擬位置點(diǎn)的取值范圍半徑為20 km.隨著時(shí)間的變化，LBS服務(wù)器得到的用戶請(qǐng)求位置中，虛擬位置與真實(shí)位置的距離偏差如圖3所示.可以看出，虛擬位置點(diǎn)對(duì)應(yīng)的時(shí)間就是不同用戶請(qǐng)求服務(wù)的時(shí)間, 當(dāng)用戶在不同或相同的時(shí)間點(diǎn)請(qǐng)求服務(wù)時(shí)，都會(huì)產(chǎn)生3個(gè)不同的虛擬位置點(diǎn)；各個(gè)虛擬位置點(diǎn)與真實(shí)位置點(diǎn)的距離偏差均為0～20 km，這主要是由于實(shí)驗(yàn)假設(shè)每個(gè)用戶的隱私級(jí)別都相等.圖3中顯示的虛擬位置也正是LBS服務(wù)器中接收到的所有位置中的一部分.因?yàn)橛脩舨⒎莾H僅在圖中所標(biāo)識(shí)的時(shí)間點(diǎn)上發(fā)出服務(wù)請(qǐng)求，用戶的請(qǐng)求一旦在緩存區(qū)有記錄，緩存區(qū)會(huì)直接反饋給用戶，并不需要再產(chǎn)生虛擬位置坐標(biāo)，這樣就擾亂了LBS服務(wù)器接收到的請(qǐng)求在時(shí)間和空間上的連貫性.因此，攻擊者無法區(qū)別用戶的真實(shí)位置和分析用戶的軌跡，從而保護(hù)了用戶軌跡數(shù)據(jù).

3.2.2虛擬位置點(diǎn)的生成效率 測試了不同隱私等級(jí)下虛擬位置點(diǎn)的生成效率.圖4 為本文方法(CCRT)與DUMMY-T方法[14]、DBAM方法[15]虛擬位置平均生成時(shí)間的對(duì)比.可以看出，隨著隱私等級(jí)的增加，DUMMY-T方法、DBAM方法和本文方法的虛擬位置平均生成時(shí)間都在增加，DUMMY-T方法與DBAM方法的增加幅度明顯較大，其中DUMMY-T方法花費(fèi)的時(shí)間最多.而本文方法的增加幅度較小，花費(fèi)的時(shí)間相比其他兩種方法也較少.因此，本文方法具有明顯的時(shí)間效率優(yōu)勢.

3.2.3緩存平均命中率測試 抽樣選取了20個(gè)用戶240 h內(nèi)的軌跡進(jìn)行測試，緩存平均命中率隨時(shí)間的變化結(jié)果如圖5所示.可以看出，隨著時(shí)間的增加，緩存平均命中率增大.這主要是由于隨著時(shí)間的增加，用戶請(qǐng)求服務(wù)不斷增多，緩存區(qū)中存儲(chǔ)的請(qǐng)求結(jié)果數(shù)據(jù)也逐漸增多，故緩存平均命中率逐漸增大.240 h內(nèi)緩存平均命中率最高接近0.5，相比無緩存機(jī)制的框架，大大減少了用戶與LBS服務(wù)器的交互，從而使攻擊者難以從LBS服務(wù)器接收到的服務(wù)請(qǐng)求中推斷出用戶的軌跡.

3.2.4通信開銷測試 本文方法主要分析客戶端與LBS服務(wù)器之間的通信開銷.通信開銷主要是由客戶端向LBS服務(wù)器請(qǐng)求查詢的服務(wù)數(shù)據(jù)大小和次數(shù)決定的，假設(shè)查詢的服務(wù)數(shù)據(jù)大小相同，則通信開銷主要由移動(dòng)客戶端向LBS服務(wù)器發(fā)送請(qǐng)求的次數(shù)決定.隨著時(shí)間的增加，移動(dòng)客戶端向LBS服務(wù)器發(fā)送請(qǐng)求的次數(shù)隨時(shí)間的變化結(jié)果如圖6所示.可以看出，隨著時(shí)間的增加，請(qǐng)求次數(shù)逐漸減小.這主要是由于隨著時(shí)間的增加，緩存中存儲(chǔ)的服務(wù)數(shù)據(jù)會(huì)越多，當(dāng)用戶發(fā)出服務(wù)請(qǐng)求時(shí)，緩存中的數(shù)據(jù)提供服務(wù)的概率增大，故發(fā)送給LBS服務(wù)器的請(qǐng)求次數(shù)逐漸減小，降低了通信開銷.

圖3 虛擬位置與真實(shí)位置的距離偏差Fig.3 Distance deviation between virtual location and real location

圖4 虛擬位置平均生成時(shí)間的對(duì)比Fig.4 Comparison on average generation time of virtual location

圖5 緩存平均命中率隨時(shí)間的變化Fig.5 Average hit ratio of cache changing with time

圖6 請(qǐng)求次數(shù)隨時(shí)間的變化Fig.6 The number of requests changing with time

4 結(jié)束語

本文提出了一種采用緩存區(qū)機(jī)制與中國剩余定理算法相結(jié)合來實(shí)現(xiàn)位置隱私保護(hù)的方案，該方案對(duì)數(shù)據(jù)的處理主要由客戶端完成，不依賴可信的第三方服務(wù)器，減少了用戶與 LBS服務(wù)器之間的交互，保證了用戶的不同隱私保護(hù)需求，從而保護(hù)用戶的位置隱私不被泄露.通過虛擬位置點(diǎn)的生成效率、緩存平均命中率以及通信開銷的實(shí)驗(yàn)，證明了該方案的可行性和高效性.