張學(xué)軍,桂小林,蔣精華,4

(1.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安;2.蘭州交通大學(xué)電子與信息工程學(xué)院,730070,蘭州;3.蘭州交通大學(xué)光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室,730070,蘭州;4.香港城市大學(xué)計(jì)算機(jī)系,999077,香港)

?

用戶為中心的差分?jǐn)_動(dòng)位置隱私保護(hù)方法

張學(xué)軍1,2,3,桂小林1,蔣精華1,4

(1.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安;2.蘭州交通大學(xué)電子與信息工程學(xué)院,730070,蘭州;3.蘭州交通大學(xué)光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室,730070,蘭州;4.香港城市大學(xué)計(jì)算機(jī)系,999077,香港)

基于隱形區(qū)的位置混淆技術(shù)是實(shí)現(xiàn)位置隱私廣泛研究的技術(shù),但該技術(shù)需要可信第三方且無(wú)法防止基于背景信息的推理攻擊,容易泄露位置隱私。針對(duì)這一難題,提出了以用戶為中心的差分?jǐn)_動(dòng)位置隱私保護(hù)方法,不需要可信第三方,同時(shí)增強(qiáng)了用戶位置隱私。該方法采用修改的Hilbert曲線映射技術(shù)將地圖中用戶的每個(gè)位置投影到一維空間,通過(guò)組合k匿名和差分隱私技術(shù)隨機(jī)產(chǎn)生擾動(dòng),并將擾動(dòng)位置作為用戶真實(shí)位置提交給服務(wù)商。為了解決移動(dòng)設(shè)備資源受限問(wèn)題,采用基于四分樹(shù)的方法將用戶的上下文存儲(chǔ)和轉(zhuǎn)換為比特流,由此獲得了有效的時(shí)空復(fù)雜度和很高的檢索準(zhǔn)確率。安全分析表明,該方法能有效保護(hù)用戶位置隱私;實(shí)驗(yàn)評(píng)估表明,與采用標(biāo)準(zhǔn)Hilbert曲線映射的方法相比檢索準(zhǔn)確率平均提高了15.4%。所提方法在隱私保護(hù)和服務(wù)精度之間取得了較好的權(quán)衡,對(duì)隱私保護(hù)系統(tǒng)設(shè)計(jì)具有一定的理論和實(shí)際意義。

位置服務(wù);差分隱私;隱私保護(hù);背景信息;位置穩(wěn)私

隨著智能移動(dòng)設(shè)備和無(wú)線通信技術(shù)的快速發(fā)展,位置服務(wù)(location-based service,LBS)給社會(huì)和個(gè)人提供了巨大的便利,但也引發(fā)了嚴(yán)重的隱私關(guān)注。為了讓用戶放心使用LBS,需要實(shí)施隱私保護(hù),防止用戶隱私泄露,然而實(shí)施隱私保護(hù)必然會(huì)降低服務(wù)質(zhì)量。因此,如何保護(hù)用戶隱私而又不妨礙服務(wù)的可用性是一個(gè)重要的挑戰(zhàn)[1-2]。為了面對(duì)這個(gè)挑戰(zhàn),該領(lǐng)域的研究者提出了眾多解決方案,其中基于隱形區(qū)的位置混淆方法[3]是研究最廣泛的技術(shù),它使用k匿名指標(biāo)并依賴可信第三方(trusted thirty part,TTP)。為了實(shí)現(xiàn)k匿名,位置混淆方法將包含用戶真實(shí)位置的查詢通過(guò)TTP提交給位置服務(wù)商(location-based service provider,LSP),TTP將用戶真實(shí)位置擴(kuò)大為地理上包含其他至少k-1個(gè)用戶的隱形區(qū)。因此,不可信的LSP很難把用戶的真實(shí)位置和其他k-1個(gè)用戶的位置區(qū)分開(kāi)。雖然使用k匿名方法可以增強(qiáng)用戶的位置隱私,但仍存在一些缺點(diǎn)。首先,該方法嚴(yán)重依賴TTP,TTP容易成為系統(tǒng)瓶頸,而且TTP知道所有用戶LBS查詢的全部知識(shí),易遭受單點(diǎn)故障。如果攻擊者俘獲了TTP,則所有用戶的隱私都將泄露。新近的研究[4]試圖通過(guò)使用網(wǎng)格標(biāo)識(shí)匹配和保序?qū)ΨQ加密技術(shù)解決這一問(wèn)題,但是需要改變客戶端、TTP和服務(wù)端的系統(tǒng)模型且客戶端計(jì)算開(kāi)銷很大。其次,大部分已有的方法[3-4]都假定攻擊者沒(méi)有關(guān)于用戶的背景信息,如近似位置知識(shí)、與位置相關(guān)的查詢頻率、用戶屬性等。實(shí)際中,因?yàn)橐恍┕粽呖赡軗碛羞@樣的一些背景信息,所以這些方法不能很好地保護(hù)位置隱私。例如,圖1a中擁有近似位置知識(shí)的攻擊者利用隱形區(qū)提高了多個(gè)關(guān)于用戶近似位置的精確度。因此,隱形區(qū)能給攻擊者提供額外知識(shí),會(huì)導(dǎo)致位置隱私泄露。理想情況下,如圖1b所示,僅當(dāng)隱形區(qū)能確保包含每個(gè)用戶對(duì)應(yīng)的近似位置時(shí),由隱形區(qū)造成的隱私泄露問(wèn)題才能被消除。不幸的是,很難判斷攻擊者擁有知識(shí)的范圍和程度。最后,用戶分布稀疏時(shí),很難在一個(gè)合理的隱形區(qū)中發(fā)現(xiàn)足夠的用戶。為此,隱形區(qū)會(huì)出現(xiàn)不必要的擴(kuò)大,最壞情況下用戶的服務(wù)將會(huì)被拒絕。為了避免TTP,一些基于移動(dòng)設(shè)備的隱私保護(hù)方法,如CloakP2P[5]、MobileHide[6]等,被引入到LBS隱私保護(hù)系統(tǒng)中,但是它們?nèi)孕枋褂秒[形區(qū),且要求用戶相互通信以獲取額外信息。

(a)隱私攻擊結(jié)果 (b)隱私理想保護(hù)結(jié)果圖1 使用隱形區(qū)的位置隱私攻擊與理想保護(hù)結(jié)果

啞元技術(shù)[7]不使用隱形區(qū),但當(dāng)攻擊者具有背景信息時(shí),它不能保證位置隱私。啞位置選擇算法[8]和緩存感知的啞位置選擇算法[9]利用虛假信息和緩存等技術(shù)來(lái)存儲(chǔ)歷史查詢信息,以便重復(fù)利用,提高了隱私保護(hù)強(qiáng)度,然而它們會(huì)帶來(lái)很高的計(jì)算和通信開(kāi)銷。上下文感知位置隱私保護(hù)方法[10]在解決時(shí)空復(fù)雜度上非常有效,但是當(dāng)攻擊者知道擾動(dòng)算法和一些背景信息(如包含用戶真實(shí)位置的位置點(diǎn)集合)時(shí),它就不能很好地保護(hù)位置隱私。局部差分?jǐn)_動(dòng)技術(shù)[11]可以抵御背景信息攻擊,但仍需要TTP。差分隱私技術(shù)[12]不使用TTP且無(wú)需考慮攻擊者的背景信息,能針對(duì)攻擊者的先驗(yàn)知識(shí)進(jìn)行有效保護(hù)。目前,大部分差分隱私技術(shù)主要應(yīng)用于離線數(shù)據(jù)的隱私保護(hù),針對(duì)LBS場(chǎng)景的隱私保護(hù)方法較少見(jiàn)且面臨許多新的挑戰(zhàn),需要繼續(xù)研究和完善。因此,如何設(shè)計(jì)一個(gè)適合移動(dòng)設(shè)備、魯棒性很強(qiáng)的LBS隱私保護(hù)系統(tǒng)仍然是一個(gè)很大的挑戰(zhàn)性問(wèn)題。

針對(duì)這一挑戰(zhàn),本文提出了一個(gè)能抵御背景信息攻擊且無(wú)需任何TTP的差分?jǐn)_動(dòng)位置隱私保護(hù)方法(Ulp2mDP)。Ulp2mDP方法僅運(yùn)行在移動(dòng)設(shè)備上,能夠防止具有背景信息的攻擊者獲取用戶的位置隱私。Ulp2mDP方法首先使用修改的Hilbert曲線(modified hilbert curve,MHC)將地圖中用戶的每個(gè)二維地理位置投影到一維空間,然后利用空間k匿名互惠框架[13]選擇k個(gè)位置,接著按期望的隱私水平通過(guò)向k個(gè)位置中添加可控的拉普拉斯噪聲隨機(jī)產(chǎn)生擾動(dòng),并用擾動(dòng)位置代替用戶的真實(shí)位置來(lái)請(qǐng)求LBS。

Ulp2mDP方法旨在確保隱私保護(hù)和LBS精度,由于其采用用戶為中心的模式,所以面臨移動(dòng)設(shè)備資源受限的挑戰(zhàn)。為解決這一問(wèn)題,使用基于四分樹(shù)的模式將用戶位置的上下文轉(zhuǎn)換和存儲(chǔ)為比特流,由此可獲得高壓縮率、支持有效檢索。由于MHC映射基于真實(shí)地圖離線計(jì)算,僅需很小的存儲(chǔ)空間和檢索成本,在解決時(shí)間和空間復(fù)雜度上很有效[10]。

1 Ulp2mDP方法的設(shè)計(jì)思想

1.1 系統(tǒng)模型與背景信息

Ulp2mDP方法的系統(tǒng)模型主要由LBS用戶和LSP兩部分構(gòu)成,如圖2所示。LBS用戶擁有位置感知無(wú)線設(shè)備,能通過(guò)WiFi、GPRS或3G等無(wú)線協(xié)議連接移動(dòng)互聯(lián)網(wǎng)。LBS用戶將使用位置擾動(dòng)算法生成的擾動(dòng)查詢提交給LSP。LSP不可信,假定為攻擊者,它會(huì)響應(yīng)用戶的擾動(dòng)查詢并返回查詢結(jié)果。LSP通過(guò)觀察接收的擾動(dòng)查詢,獲取關(guān)于用戶的所有背景信息。此外,攻擊者還知道擾動(dòng)算法和系統(tǒng)使用的噪聲分布?；谶@些背景信息,LSP通過(guò)執(zhí)行推理攻擊盡力推斷用戶的真實(shí)位置。

圖2 Ulp2mDP方法的系統(tǒng)模型

本文將攻擊者的背景信息限定為關(guān)于用戶的近似位置知識(shí)(一些包含用戶真實(shí)位置的位置點(diǎn)集合),它能夠通過(guò)多種方式獲得,例如使用蜂窩塔的設(shè)備通信日志、違規(guī)停車的公共記錄、隨意談話中的社會(huì)工程方法等。除非有法律規(guī)定,否則近似位置知識(shí)能夠很容易地從蜂窩塔和無(wú)線訪問(wèn)點(diǎn)的廣播信息中直接推算出來(lái)[11]。

1.2 設(shè)計(jì)思想與動(dòng)機(jī)

Ulp2mD方法的設(shè)計(jì)源于下面的觀察及其可能的影響。具體地,攜帶智能手機(jī)的用戶在某個(gè)地理區(qū)域移動(dòng)時(shí)查詢LBS,以定位他們感興趣的周圍興趣點(diǎn)(例如飯店或地鐵站等)。假定LSP誠(chéng)實(shí)且好奇,即它能準(zhǔn)確回答用戶的查詢,但希望通過(guò)分析用戶訪問(wèn)的位置收集用戶的隱私信息。

在LBS應(yīng)用(例如Foursquare、WeChat等)中,用戶總是傾向于從對(duì)他們有意義的地方(例如家、辦公室等)提交查詢。在這些地方,用戶通常更有可能執(zhí)行某些活動(dòng)而沒(méi)有太多的運(yùn)動(dòng)[14]。我們稱這些地方為用戶的興趣點(diǎn),并定義其為地理空間中的真實(shí)興趣點(diǎn),假定用戶從他們的興趣點(diǎn)請(qǐng)求LBS。本文主要關(guān)注保護(hù)用戶請(qǐng)求LBS的興趣點(diǎn)。事實(shí)上,對(duì)興趣點(diǎn)的推理會(huì)造成非常嚴(yán)重的位置隱私侵害[15]。例如,推理興趣點(diǎn)可能會(huì)讓好奇的LSP發(fā)現(xiàn)用戶的家庭住址和工作地點(diǎn),甚至推斷出用戶的宗教和政治傾向。假定每個(gè)興趣點(diǎn)ψi都近似的表示為(xi,yi,ζi),其中(xi,yi)表示興趣點(diǎn)的位置坐標(biāo),ζi代表興趣點(diǎn)位置坐標(biāo)(xi,yi)的語(yǔ)義屬性,例如它的語(yǔ)義位置。

有效保護(hù)位置隱私的一種簡(jiǎn)單方法是基于經(jīng)緯度上預(yù)先確定的噪聲分布來(lái)隨機(jī)擾動(dòng)用戶位置。但是,這種方法對(duì)LBS不充分,因?yàn)橛辛祟A(yù)先確定的噪聲分布,隱私保護(hù)水平和LBS精度很大程度上依賴用戶所在位置的上下文。例如,直覺(jué)上,為獲得同樣的隱私水平和LBS精度,在郊區(qū)擾動(dòng)位置偏離用戶的位置要比在市區(qū)更遠(yuǎn),因?yàn)槭袇^(qū)的路網(wǎng)和興趣點(diǎn)密度分布要比郊區(qū)密集很多。

位置隱私保護(hù)的一個(gè)關(guān)鍵挑戰(zhàn)是如何實(shí)現(xiàn)上下文感知的隱私保護(hù)。已有的k匿名技術(shù)通過(guò)TTP上用戶分布的全局知識(shí)實(shí)現(xiàn)上下文感知,例如隱形區(qū)在人口稀少的郊區(qū)會(huì)自動(dòng)變得更大。沒(méi)有了TTP,就必須從其他來(lái)源獲得上下文。為此,本文設(shè)計(jì)了基于興趣點(diǎn)密度分布的MHC映射技術(shù)來(lái)獲得上下文。MHC將地理區(qū)域中的每個(gè)二維興趣點(diǎn)投影到一維空間,使一維空間的每個(gè)數(shù)據(jù)點(diǎn)都有同質(zhì)的上下文(如相同的密度),而且原來(lái)相鄰的興趣點(diǎn)在投影后仍然保持鄰近。圖3a為基于興趣點(diǎn)密度分布的MHC映射技術(shù)對(duì)地理區(qū)域進(jìn)行分割的一個(gè)實(shí)例,圖中的圓點(diǎn)Pi(i=1,…,15)為興趣點(diǎn),每個(gè)原子單元中的數(shù)字代表該原子單元的Hilbert值。通常,興趣點(diǎn)密集的區(qū)域會(huì)導(dǎo)致更細(xì)的粒度劃分,這樣一維空間中的每個(gè)數(shù)據(jù)點(diǎn)都有相同的密度。相應(yīng)地,圖3b為使用標(biāo)準(zhǔn)Hilbert曲線(standard hilbert curve,SHC)映射技術(shù)對(duì)空間進(jìn)行分割的一個(gè)實(shí)例,由于SHC使用了相同的粒度分割區(qū)域,所以它不能反映興趣點(diǎn)密度分布特點(diǎn)。

Hilbert曲線的最優(yōu)數(shù)據(jù)聚類和距離保持特性使得一維空間中相鄰的兩個(gè)點(diǎn)更有可能在原來(lái)空間也相鄰。因此,給定一個(gè)特定的點(diǎn),能很容易地發(fā)現(xiàn)其周圍鄰近的點(diǎn)。根據(jù)這一屬性,用戶請(qǐng)求LBS時(shí),首先使用MHC投影其興趣點(diǎn)到一維空間,然后利用k匿名互惠框架[13]選擇包含自己興趣點(diǎn)在內(nèi)的k個(gè)興趣點(diǎn),并向k個(gè)興趣點(diǎn)中添加仔細(xì)選擇的拉普拉斯噪聲產(chǎn)生擾動(dòng),保證由k個(gè)興趣點(diǎn)分別計(jì)算得到同樣擾動(dòng)的概率相似(達(dá)到eε)。這樣,具有近似位置知識(shí)的攻擊者很難推斷出用戶的真實(shí)興趣點(diǎn)。

(a)MHC劃分 (b)SHC劃分

(c)MHC劃分區(qū)域(d)四分樹(shù)的序列化存儲(chǔ) 的四分樹(shù)表示圖3 MHC和SHC映射技術(shù)

1.3 添加拉普拉斯噪聲擾動(dòng)

形式上讓l1,…,lk表示k個(gè)興趣點(diǎn)(k為興趣點(diǎn)數(shù)),其中的一個(gè)是用戶的真實(shí)興趣點(diǎn)lr=(xr,yr)。lp=(xp,yp)是lr對(duì)應(yīng)的擾動(dòng)興趣點(diǎn)。對(duì)于這k個(gè)興趣點(diǎn)中的任意兩個(gè)興趣點(diǎn)li和lj,它們生成擾動(dòng)興趣點(diǎn)lp=(xp,yp)的概率應(yīng)滿足下式

P(xp|xi)≤eεP(xp|xj)

(1)

P(yp|yi)≤eεP(yp|yj)

(2)

式中:ε≥0;i,j∈{1,…,k};P(xp|xi)為xi對(duì)應(yīng)xp的概率;P(yp|yi)為yi對(duì)應(yīng)yp的概率。這一屬性可以通過(guò)使用拉普拉斯噪聲擾動(dòng)lr=(xr,yr)獲得。研究表明,分別向每個(gè)坐標(biāo)點(diǎn)添加噪聲提供的隱私保護(hù)比分別向每個(gè)位置點(diǎn)添加噪聲更強(qiáng)[16]。因此,采用分別向每個(gè)坐標(biāo)添加尺度參數(shù)為b的拉普拉斯分布,使得獨(dú)立擾動(dòng)li=(xi,yi)的坐標(biāo)xi和yi滿足

(3)

(4)

每個(gè)坐標(biāo)添加的噪聲數(shù)量為-bsign(rnd)ln(1-2|rnd|),rnd是[-1/2,1/2]中的一個(gè)均勻隨機(jī)值?；谙旅娴挠^察,將b設(shè)為(maxnxn-minnxn)/ε產(chǎn)生xp、(maxnyn-minnyn)/ε產(chǎn)生yp,其中maxnxn表示x1,…,xn中的最大值;minnxn表示x1,…,xn中的最小值。由此,可獲得擾動(dòng)興趣點(diǎn)lp=(xp,yp)。

不失一般性,對(duì)于興趣點(diǎn)li、lj、lp,由三角不等式可得

(5)

將式(5)重新整理,兩邊除以b并將其提升為底數(shù)為e的冪指數(shù),然后再在兩邊乘以1/2b可得

(6)

由式(3)和式(4),可將式(6)修改為

(7)

對(duì)每個(gè)坐標(biāo)xi和yi,式(7)相應(yīng)地可表示為

(8)

(9)

分別設(shè)定式(8)和式(9)的指數(shù)邊界,可得

(10)

(11)

因此,只要將b設(shè)為k個(gè)興趣點(diǎn)中任意兩個(gè)興趣點(diǎn)各自坐標(biāo)分量的最大距離,則這k個(gè)興趣點(diǎn)集合中任意兩個(gè)興趣點(diǎn)產(chǎn)生特定擾動(dòng)的概率總是被限定在常數(shù)因子eε內(nèi),即任意兩個(gè)興趣點(diǎn)產(chǎn)生擾動(dòng)的概率相似。

2 Ulp2mDP實(shí)現(xiàn)方法

2.1 基于興趣點(diǎn)密度分布的MHC映射方法

MHC映射方法的實(shí)現(xiàn)需要參考上下文信息,如興趣點(diǎn)或路網(wǎng)密度。一般而言,路網(wǎng)密度和興趣點(diǎn)密度強(qiáng)相關(guān),路網(wǎng)密度越大的區(qū)域興趣點(diǎn)密度也越大。因此,MHC映射技術(shù)可以很容易地適應(yīng)于路網(wǎng)密度。下面給出MHC映射技術(shù)的構(gòu)建方法。

令R是用戶移動(dòng)的地理區(qū)域的邊界,Ψ是R中所有可能的興趣點(diǎn)的集合。不失一般性,認(rèn)為用戶移動(dòng)區(qū)域R是一個(gè)矩形區(qū)域。當(dāng)且僅當(dāng)原區(qū)域中的興趣點(diǎn)數(shù)大于預(yù)定義的閾值σ時(shí),可將原區(qū)域遞歸地劃分為4個(gè)相等大小的子區(qū)域。圖3a是這種劃分的一個(gè)例子,它根據(jù)給定的閾值σ=1對(duì)區(qū)域進(jìn)行遞歸劃分,直到區(qū)域中的興趣點(diǎn)數(shù)不超過(guò)給定的閾值σ為止。從圖中可以看到,MHC劃分覆蓋了具有細(xì)粒度的高密度興趣點(diǎn)區(qū)域,每個(gè)原子單元,即不能進(jìn)一步劃分的單元,包含大約σ或更少的興趣點(diǎn)。如圖3c所示,這種劃分很容易表示為一棵四分樹(shù)。特別地,樹(shù)中的每個(gè)節(jié)點(diǎn)僅有兩種可能:葉子節(jié)點(diǎn)或包含4個(gè)孩子的節(jié)點(diǎn)。為了有效地存儲(chǔ)樹(shù),可以構(gòu)建一棵廣度優(yōu)先搜索樹(shù),并為每個(gè)節(jié)點(diǎn)存儲(chǔ)1 bit的信息,表明該節(jié)點(diǎn)是否為葉子節(jié)點(diǎn),按此可以將用戶移動(dòng)空間轉(zhuǎn)化為序列化的地圖存儲(chǔ)文件。圖3d給出了圖3c中四分樹(shù)表示地圖的序列化存儲(chǔ)的一個(gè)例子。假定興趣點(diǎn)集合的規(guī)模為n,則生成葉子節(jié)點(diǎn)的個(gè)數(shù)為n/σ。一棵具有n/σ個(gè)葉子節(jié)點(diǎn)的四分樹(shù)最多只有4n/3σ個(gè)節(jié)點(diǎn),那么序列化文件需要的空間最多是4n/3σ個(gè)bit,因此文件的存儲(chǔ)開(kāi)銷是O(n)。由于某個(gè)地理區(qū)域內(nèi)的興趣點(diǎn)數(shù)在一定時(shí)期內(nèi)不會(huì)發(fā)生太大變化,所以MHC的構(gòu)建可以通過(guò)離線方式實(shí)現(xiàn)。為了給每個(gè)原子單元分配一維空間中的Hilbert值,需要對(duì)四分樹(shù)進(jìn)行深度優(yōu)先遍歷,按照每個(gè)葉子節(jié)點(diǎn)的遍歷先后次序分配一維空間中興趣點(diǎn)的Hilbert值。如圖3c所示,葉子節(jié)點(diǎn)下面的數(shù)字代表每個(gè)葉子節(jié)點(diǎn)被訪問(wèn)的先后次序,即為該葉子節(jié)點(diǎn)對(duì)應(yīng)原子單元的Hilbert值,也是該原子單元中興趣點(diǎn)的Hilbert值。例如,在圖3a中,包含興趣點(diǎn)p3、p4的原子單元的Hilbert值為33和14,相應(yīng)的興趣點(diǎn)p3、p4的Hilbert值也為33和14。計(jì)算各個(gè)興趣點(diǎn)Hilbert值的時(shí)間復(fù)雜度是O(n)。

2.2 位置差分?jǐn)_動(dòng)

由1.3節(jié)分析可知,位置差分?jǐn)_動(dòng)算法的思想為:首先在MHC映射的基礎(chǔ)上使用空間k匿名互惠框架[13]生成k個(gè)興趣點(diǎn),然后使用差分隱私技術(shù)向這k個(gè)興趣點(diǎn)中添加拉普拉斯噪聲,以確保這k個(gè)興趣點(diǎn)中任意兩個(gè)興趣點(diǎn)產(chǎn)生同一擾動(dòng)的概率總是被限定在常數(shù)因子eε內(nèi),從而使得具有近似位置知識(shí)的攻擊者很難推理出用戶的真實(shí)興趣點(diǎn)。顯然,k個(gè)興趣點(diǎn)中任何一個(gè)興趣點(diǎn)都可用于產(chǎn)生擾動(dòng),本文選擇所有其他k-1個(gè)興趣點(diǎn)平均距離最小的興趣點(diǎn)作為用戶的擾動(dòng)。產(chǎn)生擾動(dòng)興趣點(diǎn)的時(shí)間復(fù)雜度是O(log4n)。

3 Ulp2mDP安全性分析

有兩種類型的攻擊者:主動(dòng)攻擊者和被動(dòng)攻擊者。被動(dòng)攻擊者經(jīng)?；讷@取的偵聽(tīng)信息進(jìn)行修改、重放或注入攻擊。實(shí)際中,這種類型的攻擊可以通過(guò)使用一些成熟的加密工具加以避免,如公鑰基礎(chǔ)設(shè)施。因此,我們主要關(guān)注如何避免來(lái)自主動(dòng)攻擊者的共謀攻擊和推理攻擊,這兩種攻擊會(huì)引發(fā)嚴(yán)重的隱私泄密問(wèn)題。主動(dòng)攻擊者能俘獲LSP,而且能獲得移動(dòng)用戶的所有信息,通過(guò)執(zhí)行共謀攻擊和推理攻擊獲得特定用戶的敏感信息。

定理1 Ulp2mDP方法是抗共謀攻擊的。

證明 共謀攻擊經(jīng)常發(fā)生在一組用戶之間。然而,在Ulp2mDP方法中因?yàn)椴淮嬖诤腿魏纹渌脩舻慕换?所以與用戶共謀對(duì)其他用戶沒(méi)有任何影響。因此,Ulp2mDP方法是抗共謀攻擊的。這種類型攻擊者的最好情況是能通過(guò)俘獲LSP得到所有信息,這時(shí)他就變成了一個(gè)主動(dòng)攻擊者執(zhí)行推理攻擊。

定理2 Ulp2mDP方法是抗推理攻擊的。

證明 在Ulp2mDP方法中,為了享受LBS,用戶需要向攻擊者提交LBS查詢。理想情況下,由于擾動(dòng),攻擊者不能識(shí)別擾動(dòng)位置和用戶之間的任何直接連接。然而,攻擊者知道整個(gè)地圖上的興趣點(diǎn)密度、關(guān)于用戶的近似位置知識(shí)以及噪聲分布?；谶@些信息,攻擊者能夠執(zhí)行推理性攻擊來(lái)獲得查詢用戶的真實(shí)位置。具體來(lái)講,攻擊者知道所有的興趣點(diǎn)集合Ψ等可能的位置點(diǎn)集合l1,…,lr,…,lk,位置擾動(dòng)算法以及噪聲分布P(li)。因?yàn)樵谥涝肼暦植嫉那闆r下,攻擊者近似知識(shí)中的某些位置是極不可能產(chǎn)生擾動(dòng)的,所以攻擊者就要利用新了解的信息分布來(lái)提高從這些可能的位置點(diǎn)集合l1,…,lr,…,lk中成功猜測(cè)真實(shí)位置lr的概率。在本文算法中,推理攻擊可以通過(guò)使用拉普拉斯分布來(lái)避免。由于使用了尺度參數(shù)b≥0的拉普拉斯分布,從位置點(diǎn)集合l1,…,lr,…,lk中計(jì)算出同樣擾動(dòng)位置lp的概率被限定在一個(gè)很小的常數(shù)因子eε范圍內(nèi)。添加到某個(gè)位置點(diǎn)上的拉普拉斯噪聲的數(shù)量取決于這k個(gè)位置點(diǎn)中任意兩個(gè)位置的各自坐標(biāo)分量的最大距離,只要尺度參數(shù)b使用了這個(gè)最大距離,擾動(dòng)lp=(xp,yp)就會(huì)滿足概率比eε,而且被選中的k個(gè)位置保持了互惠性。不管哪一個(gè)興趣點(diǎn)是查詢點(diǎn),通過(guò)擾動(dòng)算法都會(huì)得到同樣的匿名集。因此,給定擾動(dòng)lp=(xp,yp),不管哪個(gè)興趣點(diǎn)被用于執(zhí)行擾動(dòng),k個(gè)興趣點(diǎn)產(chǎn)生擾動(dòng)的概率都是相同的(在常數(shù)因子eε內(nèi)),也就是說(shuō)攻擊者不能使用這些信息提高他成功猜測(cè)用戶真實(shí)位置的概率。

4 實(shí)驗(yàn)評(píng)測(cè)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境與方法

算法使用Java語(yǔ)言實(shí)現(xiàn),并在Intel Core i7-4790 3.6 GHz處理器、4 GB內(nèi)存、Windows OS計(jì)算機(jī)上完成,實(shí)驗(yàn)結(jié)果為執(zhí)行100次相應(yīng)算法的平均值。實(shí)驗(yàn)中的興趣點(diǎn)集合Ψ取自相應(yīng)的北美道路網(wǎng)絡(luò)興趣點(diǎn)集合數(shù)據(jù)集NA(http: ∥www.cs. utah.edu/～lifeifei/SpatialDataset.htm)。

4.2 MHC和SHC映射技術(shù)的參數(shù)選擇

MHC映射技術(shù)會(huì)依據(jù)曲線的遍歷順序給每個(gè)原子單元分配唯一的Hilbert值,包含在原子單元內(nèi)的興趣點(diǎn)的索引就是該原子單元的Hilbert值。如果原子單元內(nèi)包含多個(gè)興趣點(diǎn),則其索引值都相同。使用重疊因子λ量化興趣點(diǎn)索引值相同的情況

(12)

式中:M為包含興趣點(diǎn)的原子單元的數(shù)量;H為填充曲線索引值的上限;ni是索引值等于i的興趣點(diǎn)數(shù)量。當(dāng)設(shè)置相同的λ值時(shí),MHC和SHC映射技術(shù)采用的σ、曲線階數(shù)D及生成興趣點(diǎn)索引的時(shí)間見(jiàn)表1。

表1 參數(shù)選擇與索引生成時(shí)間

由表1中可以看出,在相同λ下,MHC映射技術(shù)生成索引的效率大大高于SHC,而且隨著λ的增大,MHC的效果更明顯。因?yàn)镸HC考慮了興趣點(diǎn)的密度分布,對(duì)不同密度的區(qū)域采用不同的曲線階數(shù),使得對(duì)密度較低區(qū)域的劃分不使用過(guò)高的曲線階數(shù),從而提高了索引的計(jì)算效率。下面的實(shí)驗(yàn)取參數(shù)λ=4.9、σ=10、D=9進(jìn)行。

4.3 k匿名集生成效率評(píng)價(jià)

圖4給出了采用MHC和SHC映射技術(shù)的k匿名集生成時(shí)間t的比較。

圖4 k匿名集的生成時(shí)間的比較

從圖4中可以看出,隨著k值的增加,使用MHC和SHC映射技術(shù)生成k匿名集的時(shí)間沒(méi)有顯著地變化。這是因?yàn)樵跀_動(dòng)算法中,選擇滿足互惠性的k個(gè)興趣點(diǎn)僅需遍歷四分樹(shù)中很小的局部子樹(shù),而且由于四分樹(shù)中間節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中包含其子樹(shù)中所有興趣點(diǎn)的數(shù)目,所以不需要再遍歷其子樹(shù)來(lái)得到這些信息。在相同k值的情況下,SHC生成匿名集的時(shí)間遠(yuǎn)多于MHC,平均多出了約66%,這是因?yàn)镾HC映射對(duì)所有區(qū)域都采用統(tǒng)一的粒度進(jìn)行劃分,沒(méi)有考慮用戶的上下文信息。在生成匿名集時(shí),相同情況下MHC要比SHC遍歷更少的子樹(shù),從而匿名集的生成時(shí)間有了較大幅度的降低。

4.4 位置擾動(dòng)性能評(píng)價(jià)

閾值σ決定了四分樹(shù)的大小,也決定了序列化地圖存儲(chǔ)文件的大小。隨著σ的增大,生成的序列化地圖文件僅需很小的存儲(chǔ)空間。σ=10時(shí),MHC生成擾動(dòng)的時(shí)間小于1 ms,檢索時(shí)間不超過(guò)2 s。

隱形區(qū)可以確保查詢結(jié)果中包含對(duì)應(yīng)用戶真實(shí)位置的檢索結(jié)果,而由擾動(dòng)位置查詢的結(jié)果則不一定包含對(duì)應(yīng)用戶真實(shí)位置的檢索結(jié)果,這種檢索結(jié)果的差異是否存在取決于擾動(dòng)位置和真實(shí)位置間的距離。本文采用以下3個(gè)指標(biāo)評(píng)價(jià)算法的有效性。

(1)接近度。接近度指標(biāo)表示擾動(dòng)接近于真實(shí)位置的比率。

(13)

式中:|o|是真實(shí)結(jié)果集o中的查詢對(duì)象的數(shù)量,|o∩o′|是o和o′間共同對(duì)象的數(shù)量。

(3)偏移度。偏移度μ度量K最近鄰檢索的實(shí)際檢索結(jié)果和真實(shí)檢索結(jié)果在距離方面的差異,定義如下式

(14)

式中:q為查詢用戶的真實(shí)查詢興趣點(diǎn),dist(·)為歐式距離函數(shù)。

對(duì)于接近度,記擾動(dòng)位置鄰近真實(shí)位置的距離為d,計(jì)算ε為不同值時(shí)d小于等于1 000 m、500 m、100 m的平均擾動(dòng)百分比,結(jié)果見(jiàn)表2。ε=0.01說(shuō)明2個(gè)用戶產(chǎn)生擾動(dòng)的概率相同(e0.01=1.01),但這對(duì)大多數(shù)k值來(lái)說(shuō)很難實(shí)現(xiàn)。當(dāng)ε為0.5(e0.5=1.65)時(shí),超過(guò)90%的擾動(dòng)點(diǎn)在真實(shí)位置1 000 m以內(nèi),超過(guò)60%的擾動(dòng)點(diǎn)在真實(shí)位置500 m以內(nèi)。擾動(dòng)點(diǎn)的數(shù)量隨著ε的增加而增加,但是較高的ε值會(huì)降低方法的實(shí)際意義。例如,當(dāng)ε=2.0,意味著必須接受7倍概率(e2.0=7.39)差異的結(jié)果。然而,具有較小ε值的高接近度也是可能的。

表2 擾動(dòng)位置鄰近用戶真實(shí)位置的接近度

對(duì)K最近鄰檢索,取ε=0.5產(chǎn)生擾動(dòng),圖5、圖6分別給出了對(duì)應(yīng)不同K值的平均相似度和偏移度的實(shí)驗(yàn)結(jié)果。

圖5 近似KNN檢索的平均相似度

圖6 近似KNN檢索的偏移度

由圖5可以看出,增加K,便提高了檢索結(jié)果對(duì)象的相似度,隨著K的增加,K最近鄰檢索的相似度由約60%增加到接近90%。因?yàn)楦鄶?shù)量的檢索對(duì)象可以看作擴(kuò)大了搜索半徑,在這種情況下,一個(gè)對(duì)象就變得更有可能在更多數(shù)量查詢的K最近鄰對(duì)象集中。例如,從一個(gè)城市的兩個(gè)不同地方查找最近的電影院,我們期望這兩個(gè)位置在它們最近的10個(gè)電影院查詢結(jié)果列表中有更高的重疊。重疊的程度依賴這兩個(gè)位置彼此鄰近的程度。在這方面,添加到位置上的噪聲至關(guān)重要。由MHC產(chǎn)生擾動(dòng)的K最近鄰檢索結(jié)果的相似度比由SHC產(chǎn)生擾動(dòng)的K最近鄰檢索結(jié)果的相似度平均提高了15.4%,這是因?yàn)镸HC考慮了興趣點(diǎn)的密度分布,在稠密區(qū)域僅需添加較小的擾動(dòng)就可以獲得較高的隱私保護(hù)度。

偏移度指標(biāo)表示相對(duì)于真實(shí)位置的K最近鄰查詢的檢索對(duì)象與相對(duì)于擾動(dòng)位置的K最近鄰查詢的檢索對(duì)象的距離差異,其可以更有效地度量檢索結(jié)果的質(zhì)量。由圖6可以看出,由MHC產(chǎn)生擾動(dòng)的K最近鄰查詢的偏移度要比由SHC產(chǎn)生擾動(dòng)的K最近鄰查詢的偏移度小,這是因?yàn)镸HC考慮了上下文信息,產(chǎn)生的擾動(dòng)要比SHC小。

5 結(jié) 論

本文提出了一種以用戶為中心的差分?jǐn)_動(dòng)位置隱私保護(hù)方法(Ulp2mDP)。Ulp2mDP方法不依賴任何TTP,在產(chǎn)生擾動(dòng)時(shí)考慮了用戶所在位置的上下文,能夠有效阻止背景信息攻擊。通過(guò)安全性分析和實(shí)驗(yàn)評(píng)估,可以發(fā)現(xiàn)Ulp2mDP方法能夠抵御近似位置知識(shí)的攻擊,使用擾動(dòng)位置不會(huì)顯著提高攻擊者關(guān)于用戶位置的先驗(yàn)知識(shí),具有很強(qiáng)的隱私保護(hù)強(qiáng)度。但是,一些不合理擾動(dòng)的識(shí)別仍然是一個(gè)問(wèn)題,后續(xù)工作中,將考慮放棄k匿名集來(lái)解決這一問(wèn)題。

[1] 張學(xué)軍, 桂小林, 伍忠東. 位置服務(wù)隱私保護(hù)研究綜述 [J]. 軟件學(xué)報(bào), 2015, 26(9): 2373-2395. ZHANG Xuejun, GUI Xiaolin, WU Zhongdong. Privacy preservation for location-based service: a survey [J]. Journal of Software, 2015, 26(9): 2373-2395.

[2] 張學(xué)軍, 桂小林, 馮志超, 等. 位置服務(wù)中的查詢隱私度量框架研究 [J]. 西安交通大學(xué)學(xué)報(bào), 2014, 48(2): 8-13. ZHANG Xuejun, GUI Xiaolin, FENG Zhichao, et al. A quantifying framework of query privacy in location-based service [J]. Journal of Xi’an Jiaotong University, 2014, 48(2): 8-13.

[3] GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking [C]∥Proceedings of the First International Conference on Mobile Systems, Applications, and Services. New York, USA: ACM, 2003: 31-42.

[4] SCHLEGEL R, CHOW C Y, HUANG Q, et al. User-defined privacy grid system for continuous location-based services [J]. IEEE Transactions on Mobile Computing, 2015, 14(10): 2158-2172.

[5] CHOW C Y, MOKBEL M F, LIU X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service [C]∥Proceedings of the 14th ACM International Symposium on Advances in Geographic Information Systems. New York, USA: ACM, 2006: 171-178.

[6] GHINITA G, KALNIS P, SKIADOPPULOS S. MOBIHIDE: a mobile peer-to-peer system for anonymous location-based queries [C]∥Proceedings of the 10th International Symposium on Advances in Spatial and Temporal Databases. Berlin, Germany: Springer-Verlag, 2007: 221-238.

[7] KIDO H, YANAGISAWA Y, SATOH T. An anonymous communication technique using dummies for location-based services [C]∥Proceedings of the Second International Conference on Pervasive Services. Piscataway, NJ, USA: IEEE, 2005: 88-97.

[8] NIU Ben, LI Qinhua, ZHU Xiaoyan, et al. Achievingk-anonymity in privacy-aware location-based services [C]∥Proceedings of the 33th IEEE Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 2014: 754-762.

[9] NIU Ben, LI Qinhua, ZHU Xiaoyan, et al. Enhancing privacy through caching in location-based services [C]∥Proceedings of the 34th IEEE Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 2015: 754-762.

[10]PINGLEY A, YU W, ZHANG N, et al. A context-aware scheme for privacy-preserving location-based services [J]. Computer Networks, 2012, 56(11): 2551-2568.

[11]DEWRI R. Local differential perturbations: location privacy under approximate knowledge attackers [J]. IEEE Transactions on Mobile Computing, 2013, 12(12): 2360-2372.

[12]XIAO Yonghui, LI Xiong. Protecting location with dynamic differential privacy under temporal correlations [C]∥Proceedings of the 22nd ACM Conference on Computer and Communications Security. New York, USA: ACM, 2015: 1298-1309.

[13]GHINITA G, ZHAO Keliang, PAPADIAS D, et al. A reciprocal framework for spatialk-anonymity [J]. Information System, 2010, 35(3): 299-314.

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

[15]GAMBS S, KILLIIJIA MO, CORTEZ M. Show me how you move and I will tell you who you are [J]. Transactions on Data Privacy, 2011, 2(4): 103-126.

[16]JIANG K, SHAO Dongxu, BRESSAN S, et al. Publishing trajectories with differential privacy guarantees [C]∥Proceedings of the 25th International Conference on Scientific and Statistical Database Management. New York, USA: ACM, 2013: 1-12.

(編輯 武紅江)

A User-Centric Location Privacy-Preserving Method with Differential Perturbation for Location-Based Services

ZHANG Xuejun1,2,3,GUI Xiaolin1,JIANG Jinghua1,4

(1. School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China;2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China;3. Key Laboratory of Opto-Technology and Intelligent Control Ministry of Education, Lanzhou Jiaotong University,Lanzhou 730070, China; 4. Department of Computer Science, City University of Hong Kong, Hong Kong 999077, China)

A user-centric location privacy-preserving method with differential perturbations (Ulp2mDP) is proposed to solve the problem that the location obfuscation technique using cloaking region requires a trusted third part (TTP) and cannot sufficiently prevent inference attacks based on background information, and hence is easy to leak location privacy. The method can enhance the user’s location privacy without requiring a TTP. The Ulp2mDP uses a modified Hilbert curve to project each 2-D geographical location of user into a 1-D space, and then randomly generates a reasonable perturbed location by combining thekanonymity with differential privacy technique. The perturbed value is then submitted as the user’s real location to the service provider. In order to address the resource limitation of mobile devices, a quad-tree based scheme is used to transform and to store the user’s context information as bit stream, which are highly efficient with respect to time and space complexities, hence to achieves high precision of retrieval. Security analysis shows that the Ulp2mDP can effectively protect user’s location privacy. Experimental evaluation and a comparison with the approach using standard Hilbert curve show that the average retrieval accuracy of the Ulp2mDP increases by 15.4%. It is concluded that the Ulp2mDP provides a tradeoff between privacy preserving and service accuracy, and has a certain theoretical and practical significance for the design of privacy-preserving systems.

location-based service; differential privacy; privacy preserving; background information; location privacy

2016-08-08。 作者簡(jiǎn)介:張學(xué)軍(1977—),男,博士生;桂小林(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61472316);陜西省科技計(jì)劃資助項(xiàng)目(2016ZDJC-05,2013SZS16-Z01);蘭州交通大學(xué)光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題資助項(xiàng)目(KFKT2016 -7);甘肅省自然科學(xué)基金資助項(xiàng)目(2016GS07203)。

時(shí)間:2016-10-19

10.7652/xjtuxb201612013

TP309

A

0253-987X(2016)12-0079-08

網(wǎng)絡(luò)出版地址:http: ∥www.cnki.net/kcms/detail/61.1069.T.20161019.1622.006.html