用戶為中心的差分擾動位置隱私保護方法

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

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

?

用戶為中心的差分擾動位置隱私保護方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 設(shè)計思想與動機

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

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

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

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

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

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

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

1.3 添加拉普拉斯噪聲擾動

形式上讓l1,…,lk表示k個興趣點(k為興趣點數(shù)),其中的一個是用戶的真實興趣點lr=(xr,yr)。lp=(xp,yp)是lr對應(yīng)的擾動興趣點。對于這k個興趣點中的任意兩個興趣點li和lj,它們生成擾動興趣點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對應(yīng)xp的概率;P(yp|yi)為yi對應(yīng)yp的概率。這一屬性可以通過使用拉普拉斯噪聲擾動lr=(xr,yr)獲得。研究表明,分別向每個坐標點添加噪聲提供的隱私保護比分別向每個位置點添加噪聲更強[16]。因此,采用分別向每個坐標添加尺度參數(shù)為b的拉普拉斯分布,使得獨立擾動li=(xi,yi)的坐標xi和yi滿足

(3)

(4)

每個坐標添加的噪聲數(shù)量為-bsign(rnd)ln(1-2|rnd|),rnd是[-1/2,1/2]中的一個均勻隨機值。基于下面的觀察,將b設(shè)為(maxnxn-minnxn)/ε產(chǎn)生xp、(maxnyn-minnyn)/ε產(chǎn)生yp,其中maxnxn表示x1,…,xn中的最大值;minnxn表示x1,…,xn中的最小值。由此,可獲得擾動興趣點lp=(xp,yp)。

不失一般性,對于興趣點li、lj、lp,由三角不等式可得

(5)

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

(6)

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

(7)

對每個坐標xi和yi,式(7)相應(yīng)地可表示為

(8)

(9)

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

(10)

(11)

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

2 Ulp2mDP實現(xiàn)方法

2.1 基于興趣點密度分布的MHC映射方法

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

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

2.2 位置差分擾動

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

3 Ulp2mDP安全性分析

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

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

證明 共謀攻擊經(jīng)常發(fā)生在一組用戶之間。然而,在Ulp2mDP方法中因為不存在和任何其他用戶的交互,所以與用戶共謀對其他用戶沒有任何影響。因此,Ulp2mDP方法是抗共謀攻擊的。這種類型攻擊者的最好情況是能通過俘獲LSP得到所有信息,這時他就變成了一個主動攻擊者執(zhí)行推理攻擊。

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

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

4 實驗評測與結(jié)果分析

4.1 實驗環(huán)境與方法

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

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

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

(12)

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

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

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

4.3 k匿名集生成效率評價

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

圖4 k匿名集的生成時間的比較

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

4.4 位置擾動性能評價

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

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

(1)接近度。接近度指標表示擾動接近于真實位置的比率。

(13)

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

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

(14)

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

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

表2 擾動位置鄰近用戶真實位置的接近度

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

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

圖6 近似KNN檢索的偏移度

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

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

5 結(jié) 論

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

[1] 張學(xué)軍, 桂小林, 伍忠東. 位置服務(wù)隱私保護研究綜述 [J]. 軟件學(xué)報, 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é)報, 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。 作者簡介:張學(xué)軍(1977—),男,博士生;桂小林(通信作者),男,教授,博士生導(dǎo)師。 基金項目:國家自然科學(xué)基金資助項目(61472316);陜西省科技計劃資助項目(2016ZDJC-05,2013SZS16-Z01);蘭州交通大學(xué)光電技術(shù)與智能控制教育部重點實驗室開放課題資助項目(KFKT2016 -7);甘肅省自然科學(xué)基金資助項目(2016GS07203)。

時間: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