趙大鵬，宋光旋，靳遠遠，王曉玲

(華東師范大學 上海市高可信計算重點實驗室,上海 200062)

(*通信作者電子郵箱xlwang@sei.ecnu.edu.cn)

基于查詢概率的位置隱私保護方法

趙大鵬，宋光旋，靳遠遠，王曉玲*

(華東師范大學 上海市高可信計算重點實驗室,上海 200062)

(*通信作者電子郵箱xlwang@sei.ecnu.edu.cn)

現(xiàn)有的隱私保護技術(shù)較少考慮到查詢概率、map數(shù)據(jù)、信息點(POI)語義等邊信息，攻擊者可以將邊信息與位置數(shù)據(jù)相結(jié)合推斷出用戶的隱私信息，為此提出一種新的方法ARB來保護用戶的位置隱私。該方法首先把空間劃分為網(wǎng)格，根據(jù)歷史查詢數(shù)據(jù)計算出處于不同網(wǎng)格區(qū)域的用戶提交查詢的概率；然后結(jié)合相應單元格的查詢概率來生成用戶匿名區(qū)域，從而保護用戶的位置隱私信息；最后采用位置信息熵作為隱私保護性能的度量指標。在真實數(shù)據(jù)集上與已有的兩種方法進行對比來驗證隱私保護方法的性能，結(jié)果顯示該方法具體有較好的隱私保護效果和較低的時間復雜度。

基于位置的服務；位置隱私；邊信息；查詢概率；匿名

0 引言

隨著全球定位系統(tǒng)(Global Positioning System, GPS)、蜂窩網(wǎng)等定位技術(shù)的快速發(fā)展，基于位置的服務(Location-Based Service, LBS)已經(jīng)無處不在，例如，位置查詢(查找距離某用戶一定范圍內(nèi)的餐廳)、電子營銷(發(fā)電子優(yōu)惠券給附近的顧客)、社交網(wǎng)絡(朋友間共享各自的地理位置信息)、交通狀況監(jiān)控(根據(jù)一段時間內(nèi)車輛的位置和速度來推測交通擁堵狀況)、路線查找應用(查找兩地之間的最短路徑)等。雖然LBS給用戶提供了許多有價值的服務，同時也給人們帶來了位置隱私泄露的問題。如果用戶的隱私得不到妥善的保護，將會使用戶的權(quán)益、安全面臨嚴重的威脅。因此能否很好地解決隱私保護問題可以看作是公眾可否放心地使用LBS 服務的前提。

現(xiàn)有的許多位置隱私保護文章[1-3]僅通過用戶的位置信息來保護用戶位置隱私，沒能將位置信息與邊信息相結(jié)合來保護用戶信息，這樣的隱私保護方法較容易受到攻擊者的攻擊，不能達到預期的隱私保護目的，而將邊信息與位置信息相結(jié)合的隱私保護方法才能更好地保護用戶的隱私。例如，某個匿名區(qū)域中大部分被湖泊所覆蓋，攻擊者就可以以很大的概率將湖泊所覆蓋的區(qū)域排除，認為用戶在剩余的區(qū)域內(nèi)，從而縮小用戶匿名區(qū)域的面積。

另外，很多現(xiàn)有的位置隱私保護工作[4-5]基于可信第三方服務器結(jié)構(gòu)保護用戶隱私?？尚诺谌椒掌鹘Y(jié)構(gòu)[6]中，用戶完全信任可信第三方服務器，將準確位置信息告訴可信第三方服務器。但是，現(xiàn)實生活中完全可信的第三方服務器是不存在的，任何人或機構(gòu)都有可能成為攻擊者。即使數(shù)據(jù)擁有者不會成為攻擊者，但他們的系統(tǒng)也會存在被攻擊的可能，攻擊者一旦攻破可信第三方服務器的數(shù)據(jù)庫，用戶的所有信息將完全暴露給攻擊者。

為了解決上述討論的問題，本文結(jié)合邊信息(查詢概率)保護用戶位置的位置隱私,提出ARB(Anonymouse Region Building)算法。首先根據(jù)歷史查詢數(shù)據(jù)計算出每個網(wǎng)格提交查詢的概率，然后根據(jù)查詢概率選擇滿足用戶要求的候選匿名區(qū)域集合，最后通過最大化熵選擇最終的匿名區(qū)域。本文假設(shè)歷史查詢數(shù)據(jù)中查詢點較少的網(wǎng)格用戶提交查詢的概率較小，即歷史查詢點較少的網(wǎng)格是用戶真實位置的概率較小。所以，對于一個匿名區(qū)域，匿名區(qū)域中網(wǎng)格內(nèi)查詢點數(shù)量占匿名區(qū)域查詢點數(shù)量比例越大，該網(wǎng)格查詢概率越大。另外，在系統(tǒng)中采用半可信第三方服務器結(jié)構(gòu)，用戶提交給半可信第三方服務器的查詢中不是準確位置坐標，僅需要根據(jù)自己的隱私偏好提交所在單元格坐標給半可信第三方服務器，即使攻擊者從半可信第三方服務器中獲得位置數(shù)據(jù)或者數(shù)據(jù)被數(shù)據(jù)擁有者公布，用戶的位置隱私也不會完全暴露。并且，該系統(tǒng)中的用戶端不需要大量計算，用戶設(shè)備僅需要根據(jù)用戶的隱私偏好和所在位置坐標計算出用戶所在的網(wǎng)格坐標。將ARB算法在真實數(shù)據(jù)集上進行實驗分析，與已有的兩種方法對比，實驗結(jié)果展示了ARB算法的性能。

1 相關(guān)工作

很多工作采用了匿名技術(shù)，Gruteser等[3]提出了位置k匿名的概念，最先把k匿名從關(guān)系數(shù)據(jù)庫領(lǐng)域引入LBS隱私保護領(lǐng)域。位置k匿名要求當一個用戶請求獲得LBS服務時，用一個包含自己當前位置的匿名區(qū)域代替自己的準確位置上傳給LBS服務器，并且匿名區(qū)域中必須包含該查詢用戶與其他至少k-1個用戶。Mokbel等[4]最先提出的IntervalCloak的隱私保護方法，通過遞歸地劃分整個系統(tǒng)空間，直到查詢用戶所在的最小矩形中用戶數(shù)目小于k，將該區(qū)域的上一層矩形區(qū)域作為匿名區(qū)域傳給LBS服務器。Pan等[5]將移動速度應用到隱私k匿名中，從而可以抵抗位置依賴攻擊。Chen等[6]通過分析簡單位置k匿名的缺點，然后提出了滿足用戶隱私偏好的度量指標，并根據(jù)該度量指標提出相應的隱私保護算法。Zhou等[7]在k匿名的基礎(chǔ)上加入了多樣性，使得每個匿名集合滿足敏感性、多樣性的要求，從而能更好地保護用戶的位置隱私。

假位置技術(shù)是很多研究者所使用的隱私保護技術(shù)，如：Palanisamy等[8]將假名技術(shù)應用于路網(wǎng)中，提出Mix-zone的方法來保護用戶的位置隱私；Guo[9]將動態(tài)假名轉(zhuǎn)換機制與用戶的個性化特征相結(jié)合來保護用戶的位置隱私；Niu等[10]通過最大化熵和隱藏區(qū)域面積來選擇假位置，達到保護用戶隱私的目的。

加密技術(shù)也是常用的位置隱私保護方法，如：Ghinita等[11]借助隱私信息檢索的方法隱私信息檢索(PrivateInformationRetrieval,PIR)來保護用戶的查詢隱私，查詢用戶不需要將查詢的具體信息發(fā)送給服務提供商，但用戶需要根據(jù)當前位置推測出需要訪問數(shù)據(jù)的位置，然后服務端將信息返回給用戶；Papadopoulos等[12]對PIR方法作了進一步優(yōu)化，提出了cPIR，使得計算開銷大幅度下降；Schlegel等[13]通過引入半可信第三方服務器和加密技術(shù)保護用戶查詢隱私，系統(tǒng)中的半可信第三方服務器不知道用戶的任何時空信息，僅用于驗證查詢結(jié)果；Khoshgozaran等[14]提出了基于Hilbert曲線的加密方法，將用戶的位置與用戶興趣點從二維坐標轉(zhuǎn)移到一維加密空間，通過兩條不同參數(shù)的Hilbert曲線轉(zhuǎn)化而來的一維加密空間仍然保持了二維空間中的鄰近性，因此在一維加密空間中同樣可以進行k鄰近查詢與范圍查詢；Lu等[15]提出PLAM隱私保護框架，通過使用同態(tài)加密技術(shù)保護用戶隱私，但時間開銷相對較大；Paulet等[16]通過PIR加密技術(shù)保護用戶位置數(shù)據(jù)，從而達到保護用戶隱私的目的，同時對數(shù)據(jù)進行加密使得用戶不能訪問未授予訪問權(quán)限的數(shù)據(jù)。

2 技術(shù)準備

本文采用四叉樹[4]的數(shù)據(jù)結(jié)構(gòu)，將空間自頂向下逐層劃分，直到網(wǎng)格邊長小于閾值L(單位：m)，本文實驗中閾值的設(shè)置為25m。閾值根據(jù)位置隱私保護的需要進行選取，閾值越大表示用戶隱私等級越高，本文則取一個人們覺得不是特別大的值，對實驗對影響不大。四叉樹最頂層為第0層，最底層為第H層，第i層的網(wǎng)格數(shù)為4i，例如，第H層的網(wǎng)格個數(shù)為4H。然后在第H層對每個網(wǎng)格內(nèi)的歷史查詢進行統(tǒng)計，得到最底層網(wǎng)格內(nèi)數(shù)據(jù)點個數(shù)，即四叉樹葉節(jié)點的值，任一非葉節(jié)點的值等于其四個子節(jié)點值之和。

2.1 基本定義

本文系統(tǒng)中主要有兩種服務請求：用戶向半可信第三方服務器提交的查詢請求QU和半可信第三方服務器向服務提供商提交的服務請求QS。

定義1 用戶提交給半可信第三方服務器的服務請求QU(UID,h,(R，C),k,Con)，其中:UID為用戶身份標識；h為用戶所在匿名層次，由于用戶不完全信任半可信第三方服務器，不希望將自己的準確位置告訴它，h的值決定了用戶向半可信第三方服務器暴露的位置信息量的多少，h越大，用戶位置信息越具體，真實位置的隱藏粒度越小，反之亦然；(R,C)為用戶所在行列坐標，R為行坐標，C為列坐標；k為用戶的隱私保護程度，是位置k匿名的閾值(k為大于等于2的偶數(shù))；Con為查詢內(nèi)容，不是本文重點研究的內(nèi)容。例如，某用戶提交查詢QU為(2，6，(4,5)，4，con),表示用戶2向半可信第三方服務器提交了一個匿名層次為第6層并且匿名區(qū)域大小為4的服務請求，用戶2所在位置的網(wǎng)格編號為(4,5)，查詢內(nèi)容為con。

定義2 半可信第三方服務器向服務提供商SP提交的服務請求QS((L,U),(R,B),h,Con))，其中:(L,U)為用戶匿名區(qū)域的左上單元格行列坐標；(R,B)為用戶匿名區(qū)域右下單元格行列坐標；h為用戶所在四叉樹的匿名層次；Con為查詢內(nèi)容。

定義3 存儲相應網(wǎng)格區(qū)域內(nèi)的歷史查詢點數(shù)目的四叉樹稱為歷史查詢點分布樹。歷史查詢點分布樹每層都存儲著一個如圖1的歷史查詢點統(tǒng)計分布矩陣，每個單元格中的整數(shù)表示歷史查詢點落在該單元格中的次數(shù)。例如，圖1中灰網(wǎng)格(4,2)中整數(shù)是35，表示歷史查詢點落在網(wǎng)格(4,2)內(nèi)的統(tǒng)計次數(shù)為35。

圖1 歷史查詢點分布情況

定義4 逆向攻擊是指攻擊者不僅知道用戶當前的匿名區(qū)域，而且知道歷史查詢點數(shù)據(jù)分布情況和隱私保護機制，從而根據(jù)用戶的匿名區(qū)域推測出用戶真實位置的攻擊方法。

如圖1所示的歷史查詢點分布情況，匿名機制是opt算法，計算出所有包含用戶位置的大小為k的矩形區(qū)域的熵，將熵最大的矩形區(qū)域作為用戶的匿名區(qū)域。當某用戶U的隱私偏好為k=2，建立匿名區(qū)域為{(4,1),(4,2)}時，攻擊者可以推測出用戶的位置在(4,2)網(wǎng)格中。因為存在大小為2的匿名區(qū)域{(3,1),(4,1)}的位置熵值大小為1.0，用戶的匿名區(qū)域的位置熵值小于1.0，若用戶位置是在查詢數(shù)量為40的網(wǎng)格內(nèi)，則根據(jù)匿名機制將選擇{(3,1),(4,1)}區(qū)域作為用戶匿名區(qū)域，所以用戶的位置不在歷史查詢點數(shù)目為40的網(wǎng)格中，而是在歷史查詢點數(shù)目為35的網(wǎng)格中。

定義5 矩形區(qū)域的寬度是指矩形區(qū)域的行數(shù)。例如，圖1中陰影矩形區(qū)域的寬度為2。本文中的匿名區(qū)域不考慮不規(guī)則區(qū)域情況，所以生成的匿名區(qū)域均為矩形區(qū)域。

2.2 系統(tǒng)結(jié)構(gòu)

在半可信第三方服務器結(jié)構(gòu)中，用戶僅有所保留地信任半可信第三方服務器，與傳統(tǒng)的可信第三方服務器結(jié)構(gòu)相比，本文中的用戶不需要將自己的準確信息發(fā)送給半可信第三方，僅需要將匿名的單元格發(fā)送給半可信第三方服務器。并且，本文系統(tǒng)中的用戶具有較高的自主選擇權(quán)利。若用戶需要隱私級別較高，用戶可以選擇較高的四叉樹層次作為自己的匿名層次，使得半可信第三方服務器也無法確定用戶的準確位置；相反，如果用戶對當前位置不敏感，用戶可以選擇較低的四叉樹層次作為自己的匿名層次。

如圖2所示，本文中的半可信第三方服務器結(jié)構(gòu)，不是完全依靠可信第三方匿名服務器完成匿名過程。系統(tǒng)主要由三部分組成：移動端、半可信第三方服務器和服務提供商。其中，用戶端是攜帶移動設(shè)備的用戶，移動設(shè)備配有定位功能，并具有簡單的計算能力(如智能手機)，可以通過用戶的經(jīng)緯度坐標計算出用戶所在匿名層次的網(wǎng)格編號；半可信第三方服務器可根據(jù)用戶提交的查詢信息QU與查詢概率生成用戶的匿名查詢QS， 并將匿名查詢QS發(fā)送給服務提供商(ServiceProvider,SP)；服務提供商SP根據(jù)半可信第三方服務器發(fā)送來的匿名查詢QS查找相應的候選結(jié)果集，并返回給半可信第三方服務器。

圖2 半可信第三方服務器結(jié)構(gòu)

在本文的系統(tǒng)中，用戶可根據(jù)自己的隱私偏好選取匿名層次h以及匿名等級k，所在層次h的網(wǎng)格單元面積為用戶的最小匿名區(qū)域大小即用戶的最大暴露位置粒度，是任何其他實體所知道用戶最詳細的位置信息。所以，即使攻擊者獲得半可信第三方服務器的數(shù)據(jù)，也無法獲得用戶的準確位置信息。用戶服務請求的過程分五步完成：1)用戶首先根據(jù)自己的隱私偏好，選擇在四叉樹中的匿名層次h，然后用戶根據(jù)移動設(shè)備定位功能得到自己當前位置坐標，計算出所在單元格坐標(R,C)，將服務請求QU發(fā)送給半可信第三方服務器； 2)半可信第三方服務器根據(jù)用戶所在的單元格坐標(R,C)和用戶隱私偏好k對用戶進行相應的區(qū)域模糊處理，從而得到用戶的匿名區(qū)域，并將匿名服務請求QS發(fā)送給服務提供商，詳細內(nèi)容將在第2.6節(jié)中介紹；3)服務器根據(jù)用戶請求進行查詢，將得到的候選結(jié)果集返回給半可信第三方服務器，這部分不是本文研究重點；4)半可信第三方服務器根據(jù)用戶所在網(wǎng)格編號對結(jié)果集進行初步篩選，并將篩選之后的結(jié)果集返回給用戶；5)用戶根據(jù)自己的準確位置坐標找到最終的結(jié)果。

2.3 度量指標

本文采用的度量指標主要是位置熵。位置熵指標最早由Chen等[6]提出，作用是衡量位置的不確定性，位置熵的值越大，不確定性就越高?；谖恢渺氐奈恢秒[私評價標準的含義是:通過用戶與查詢位置之間的對應關(guān)系的不確定性來度量隱私保護的效果。攻擊者將真實位置與請求者關(guān)聯(lián)起來的概率越小，意味著熵就越大，用戶位置隱私暴露的可能性也就越??；反之，如果攻擊者關(guān)聯(lián)真實位置與請求者之間的概率越大，熵越小，用戶位置隱私暴露的可能性也就越大。若給定一個包含k個網(wǎng)格的匿名區(qū)域區(qū)域，用戶在網(wǎng)格i的概率是pi，可以通過式(1)來計算矩形區(qū)域的熵值：

(1)

2.4 攻擊模型

攻擊者的目標是獲得某用戶的位置隱私，根據(jù)攻擊者知道信息量的多少，將攻擊者分為弱攻擊者和強攻擊者。弱攻擊者是指僅知道用戶匿名區(qū)域信息，希望獲得用戶準確位置信息的攻擊者；強攻擊者是指攻擊者不僅知道用戶當前匿名區(qū)域信息而且知道歷史查詢點分布情況和位置隱私保護機制的攻擊者。目前很多未結(jié)合邊信息的位置隱私保護技術(shù)[2-4]已經(jīng)可以很好地抵制弱攻擊者，因此本文僅考慮強攻擊者，并且將LBS服務商作為強攻擊者，因為LBS服務提供商知道查詢概率和位置隱私保護機制。

2.5 半可信第三方服務器的結(jié)構(gòu)

如圖2所示，半可信第三方服務器包括三個模塊：數(shù)據(jù)庫模塊、匿名模塊和查詢結(jié)果精煉模塊。數(shù)據(jù)庫模塊根據(jù)歷史查詢數(shù)據(jù)中歷史查詢點的分布情況建立歷史查詢點分布樹，并將它存儲在數(shù)據(jù)庫模塊中，當用戶提交所在匿名層次h后，數(shù)據(jù)庫模塊會將相應層次歷史查詢點分布矩陣傳輸給匿名模塊，供匿名模塊構(gòu)建匿名區(qū)域使用；匿名模塊結(jié)合歷史查詢點分布矩陣數(shù)據(jù)與用戶的隱私偏好k值，利用ARB算法生成相應的匿名區(qū)域(2.6節(jié)具體介紹)，從而獲得匿名查詢QS，并將QS發(fā)送給LBS服務提供商；查詢結(jié)果精煉模塊根據(jù)用戶所在單元格位置采用文獻[2]中的基于匿名區(qū)域的最鄰近查找算法對從SP返回的候選結(jié)果進行篩選，刪除部分候選結(jié)果，并將篩選之后的結(jié)果發(fā)送給用戶端。

2.6 ARB算法

對于某用戶U，其真實位置坐標(C,R)，隱私偏好k，所在匿名層次為h，包含用戶真實位置網(wǎng)格的匿名區(qū)域有很多。如圖1所示，灰色陰影網(wǎng)格為用戶的位置，用戶隱私偏好k=4，則滿足此要求的匿名區(qū)域還有很多，將在2.8節(jié)中進行詳細分析，本文提出的ARB算法就是為了解決如何選擇匿名區(qū)域的問題。對于每個包含用戶位置的矩形區(qū)域可以根據(jù)式(2)計算出每個網(wǎng)格i的查詢概率pi。攻擊者可以根據(jù)查詢請求概率推斷出用戶的位置會以較大概率落在概率較大的網(wǎng)格內(nèi)，從而排除查詢概率較小的區(qū)域，減小用戶的匿名區(qū)域網(wǎng)格數(shù)量，使得匿名區(qū)域不能滿足用戶隱私偏好k的要求，所以若圖1中陰影區(qū)域為某用戶的匿名區(qū)域，則攻擊者可以以很大概率推斷用戶在值為15的網(wǎng)格中。在考慮了查詢概率時，不同矩形區(qū)域的熵是不同的，若僅選擇熵最大的區(qū)域作為匿名區(qū)域，就容易受到逆向攻擊，本文采用ARB算法尋找匿名區(qū)域，可以很好地抵抗逆向攻擊。

(2)

對于一個服務請求QU，用戶隱私偏好為k，ARB算法首先計算出所有包含用戶位置并且大小為k的矩形區(qū)域的熵，將熵值最大的k個區(qū)域取出，然后隨機從這k個區(qū)域中選擇一個作為用戶的匿名區(qū)域。算法1為ARB算法的偽代碼，算法的輸入是歷史查詢點分布數(shù)據(jù)、用戶位置(C,R)和用戶的隱私偏好k，輸出為用戶的匿名區(qū)域CloakRegion。第1)行將計數(shù)變量count賦值0，count用于統(tǒng)計k的因數(shù)個數(shù)，包含用戶位置且大小為k的區(qū)域個數(shù)為Count×k；第2)～8)行計算出所有包含用戶位置且大小為k的矩形區(qū)域的熵，其中，第3)、4)行排除區(qū)域?qū)挾炔皇莕(n為k的因數(shù))的情況，第7)、8)行計算區(qū)域?qū)挾葹閚(n為k的因數(shù))的矩形區(qū)域的熵；第9)行將長度為k的數(shù)組Number初始化為0，Number[i]用于記錄熵值第i大的矩形區(qū)域位置；第10)行將Max置0，用于記錄每一輪選擇的最大熵值；第11)～15)行執(zhí)行top-k算法選擇熵值最大的k個矩形區(qū)域；第16)、17)行隨機選擇熵最大的k個矩形區(qū)域中的一個作為用戶的匿名區(qū)域；第18)行返回結(jié)果。

算法1ARB(生成匿名集合)。

輸入 歷史查詢點分布數(shù)據(jù)，用戶所在位置(C,R)，用戶隱私偏好k;

輸出 用戶的匿名區(qū)域CloakRegion。

1)

Count←0

2)

Forifrom1:k

3)

Ifk%i==0then

4)

Continue;

5)

Else

6)

Count++;

7)

Forjfrom1tok

8)

計算寬度為i的包含用戶位置的第Count×k+j區(qū)域的熵Entropy[Count*k+j]

9)

Number[1:k]←0

10)

Max←0

11)

Forifrom1:k

12)

Forjfrom1:Count*k

13)

Ifentropy[j]>Maxthen

14)

Max=entropy[j];

15)

Number[i]=j;

16)

隨機產(chǎn)生一個小于等于k的正整數(shù)n

17)

CloakRegion←第Number[n]個匿名區(qū)域;

18)

returnCloakRegion

2.7 時間復雜度分析

時間復雜度也是本文用來衡量系統(tǒng)性能的一個重要指標，ARB的算法時間復雜度僅與k值有關(guān)系。任一整數(shù)k可分解為式(3)的形式:

k=r1q1r2q2…riqi…rmqm

(3)

其中：ri是素數(shù)，qi是相應素數(shù)的指數(shù)。則k的因數(shù)個數(shù)N為(q1+1)(q2+1)…(qm+1)(N≤k)，例如，18=2×32,18的因數(shù)個數(shù)為(1+1)(2+1)=6，即1、2、3、6、9、18。

對于任意一個k的因數(shù)n，矩形區(qū)域?qū)挾葹閚的區(qū)域有k個。例如，圖1中包含用戶位置的大小為4，且矩形區(qū)域?qū)挾葹?的區(qū)域數(shù)量為4。所以ARB算法中計算熵的次數(shù)僅與用戶的隱私偏好k值有關(guān)，且為N×k次(N為k的因數(shù)個數(shù))。ARB算法需要從N×k(N為k的因數(shù)個數(shù))個熵中選取熵值最大的k個矩形區(qū)域，時間復雜度為O(N×k2)。由于k的值較小，所以ARB的計算復雜度較低，時間開銷較小。

2.8 安全性分析

本文系統(tǒng)結(jié)構(gòu)是半可信第三方服務器結(jié)構(gòu)，用戶可以根據(jù)自己的隱私偏好選擇自己的匿名層次h，不會將其準確位置坐標發(fā)送給任何其他實體。所以，即使半可信第三方服務器與服務提供商SP串謀，也不能獲得用戶的準確位置。本文中僅考慮攻擊能力較強的強攻擊者，他希望根據(jù)已獲得的查詢概率數(shù)據(jù)推測用戶的真實位置，面對強攻擊者本文方法仍然可以抵抗推理攻擊。

一個隱私保護方法能夠抵抗推理攻擊當且僅當匿名算法生成的匿名區(qū)域中每個網(wǎng)格是用戶真實位置的概率是相同的。pi和pj分別表示ci和cj是用戶真實位置的概率，其中ci和cj表示匿名區(qū)域中任意兩個網(wǎng)格，則本文方案能夠抵抗推理攻擊當且僅當pi=pj。根據(jù)本文方法最大化匿名區(qū)域熵的步驟可知所選擇匿名區(qū)域中每個網(wǎng)格的查詢概率是非常相近的，所以pi=pj。

但當查詢概率的數(shù)據(jù)分布極度不均勻時，本文方法將難以找到合適的匿名區(qū)域，即使給定一個滿足用戶要求的大小為k的區(qū)域，攻擊者也將能夠以大概率推斷出用戶的真實位置。

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

采用真實數(shù)據(jù)來對算法進行評測。該真實數(shù)據(jù)采用合肥市中心5.5km×3.5km范圍內(nèi)的歷史GPS采樣點數(shù)據(jù)，其包含3萬多個人產(chǎn)生的60多萬個采樣點，此處，把采樣點作為查詢點。數(shù)據(jù)包括用戶ID、時間和經(jīng)緯度坐標。為了方便，實驗選取其中3.2km×3.2km的空間進行實驗，邊長閾值為25m將目標空間劃分為128×128的網(wǎng)格空間，空間層次為8層，分別為第0層到第7層。

本文實驗代碼采用Java編寫，運行在配置2.4IntelCoreQuadCPU，4GB內(nèi)存的64位Windows7操作系統(tǒng)中。本文主要使用匿名區(qū)域的位置熵和建立匿名區(qū)域所需時間來評測ARB算法。

3.2 實驗結(jié)果

圖3表示歷史查詢點個數(shù)為6萬，用戶匿名層次h=6時，四種算法生成匿名區(qū)域的平均熵值隨用戶隱私偏好k值增加的變化情況。其中：ARB為本文提出的基于查詢概率構(gòu)建匿名區(qū)域的算法；dummy[17]為不考慮查詢概率，通過隨機游走的方法選擇匿名區(qū)域的算法，是本文的baseline算法；IClique[5]是基于速度信息實現(xiàn)位置隱私保護的方法；opt是理論上熵的最大值?？梢钥闯錾赡涿麉^(qū)域的熵值隨用戶隱私偏好k值增加而增加，從而表明用戶隱私偏好k值越大，熵值越大，用戶真實位置所在網(wǎng)格的不確定性也越大。從實驗結(jié)果可以看出，ARB算法達到的位置隱私保護效果較好。

圖3 熵 vs.k

圖4表示用戶隱私偏好k=10，用戶匿名層次h=6時，四種算法生成匿名區(qū)域的平均熵值隨著歷史查詢點數(shù)據(jù)量增加的變化情況?？梢钥闯?，四種算法隨著歷史查詢數(shù)據(jù)量的增加，匿名區(qū)域熵值也隨之增加，并且隨著歷史查詢數(shù)據(jù)量的增加熵的增長速率越來越緩慢，當歷史查詢數(shù)目增加到36萬以上時，熵幾乎不再增長，ARB算法的熵明顯大于IClique和dummy兩種算法。這說明本文設(shè)計的系統(tǒng)隱私保護效果與歷史查詢數(shù)據(jù)量成正比，但是達到一定數(shù)量之后，隱私保護效果幾乎不變，歷史查詢數(shù)據(jù)量的增加反而會帶來系統(tǒng)開銷的增加。

圖4 熵vs.歷史查詢數(shù)據(jù)量

表1表示用戶的隱私偏好k=10，歷史查詢點個數(shù)為6萬時，隨著用戶所在匿名層次h的變化，ARB算法生成的匿名區(qū)域熵的變化情況。從表中可以看出，隨著用戶所在層次的不斷上升(h減小)，用戶的位置熵越大，用戶真實位置不確定性越大，從而攻擊者獲得用戶位置信息難度也增加，這與我們設(shè)立用戶隱私偏好的初衷是一致的。所以，對于隱私要求較高的用戶，可以選擇較高的隱私層次，從而更好地保護用戶的位置隱私。

表1 熵值隨著用戶匿名層次h的變化情況

表2表示歷史查詢點個數(shù)為6萬，用戶匿名層次h=6時，ARB算法生成匿名區(qū)域的時間隨用戶隱私偏好k值增加的變化情況?？梢钥闯鲭S著用戶隱私偏好k值的增加，ARB算法生成匿名區(qū)域時間也增加，ARB算法計算開銷較小，可以達到微秒級，并且當k×N(N為k的因數(shù)個數(shù))相近時生成匿名區(qū)域時間也相近，與2.7節(jié)中的時間復雜度分析相吻合。

表2 ARB算法運行時間隨k的變化情況

4 結(jié)語

本文提出了一種采用半可信第三方服務器結(jié)構(gòu)的隱私保護方法，用戶可以根據(jù)自己的隱私偏好選取空間劃分粒度，從自身需求出發(fā)完成個性化的位置隱私，該方法所產(chǎn)生的用戶匿名區(qū)域難以被攻擊者所縮小。但是，當數(shù)據(jù)分布極不均勻時，會出現(xiàn)ARB算法無法找到熵較大的匿名區(qū)域來完成用戶位置匿名的情況；另外，ARB的主要應用場景是在單次查詢中，在將來的工作中我們將研究連續(xù)查詢的位置隱私保護方法。

)

[1]XUN,ZHUD,LIUH,etal.Combiningspatialcloakinganddummygenerationforlocationprivacypreserving[C]//ADMA2012:Proceedingsofthe8thInternationalConferenceonAdvancedDataMiningandApplications,LNCS7713.Berlin:Springer-Verlag, 2012: 701-712.

[2]ASHOURI-TALOUKIM,BARAANI-DASTJERDIA,SEL?UKAA.Thecloaked-centroidprotocol:locationprivacyprotectionforagroupofusersoflocation-basedservices[J].KnowledgeandInformationSystems, 2015, 45(3): 589-615.

[3]GRUTESERM,GRUNWALDD.Anonymoususageoflocation-basedservicesthroughspatialandtemporalcloaking[C]//MobiSys’03:ProceedingsoftheFirstInternationalConferenceonMobileSystems,Application,andServices.NewYork:ACM, 2003: 31-42.

[4]MOKBELMF,CHOWC-Y,AREFWG.ThenewCasper:queryprocessingforlocationserviceswithoutcompromisingprivacy[C]//ICDE2007:Proceedingsofthe23rdInternationalConferenceonDataEngineering.Washington,DC:IEEEComputerSociety, 2007: 1499-1500.

[5]PANX,XUJ,MENGX.Protectinglocationprivacyagainstlocation-dependentattacksinmobileservices[J].IEEETransactionsonKnowledgeandDataEngineering, 2012, 24(8): 1506-1519.

[6]CHENX,PANGJ.Measuringqueryprivacyinlocation-basedservices[C]//CODASPY’12:ProceedingsoftheSecondACMConferenceonDataandApplicationSecurityandPrivacy.NewYork:ACM, 2012: 49-60.

[7]ZHOUC,MAC,YANGS,etal.AlocationprivacypreservingmethodbasedonsensitivediversityforLBS[C]//NPC2014:Proceedingsofthe11thIFIPWG10.3InternationalConferenceonNetworkandParallelComputing,LNCS8707.Berlin:Springer-Verlag, 2014: 409-422.

[8]PALANISAMYB,LIUL.Attack-resilientmix-zonesoverroadnetworks:architectureandalgorithms[J].IEEETransactionsonMobileComputing, 2015, 14(3): 495-508.

[9] GUO M, PISSINOU N, IYENGAR S S.Pseudonym-based anonymity zone generation for mobile service with strong adversary model [C]// CCNC 2015: Proceedings of the 2015 12th Annual IEEE Consumer Communications and Networking Conference.Piscataway, NJ: IEEE, 2015: 335-340.

[10] NIU B, LI Q, ZHU X, et al.Achievingk-anonymity in privacy-aware location-based services [C]// Proceedings of the IEEE INFOCOM 2014.Piscataway, NJ: IEEE, 2014: 754-762.

[11] GHINITA G, KALNIS P, KHOSHGOZARAN A, et al.Private queries in location based services: anonymizers are not necessary [C]// SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.New York: ACM, 2008: 121-132.

[12] PAPADOPOULOS S, BAKIRAS S, PAPADIAS D.pCloud: a distributed system for practical PIR [J].IEEE Transactions on Dependable and Secure Computing, 2012, 9(1): 115-127.

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

[14] KHOSHGOZARAN A, SHIRANI-MEHR H, SHAHABI C.Blind evaluation of location based queries using space transformation to preserve location privacy [J].GeoInformatica, 2013, 17(4): 599-634.

[15] LU R, LIN X, SHI Z, et al.PLAM: a privacy-preserving framework for local-area mobile social networks [C]// Proceedings of the IEEE INFOCOM 2014.Piscataway, NJ: IEEE, 2014: 763-771.

[16] PAULET R, KAOSAR M G, YI X, et al.Privacy-preserving and content-protecting location based queries [J].IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5): 1200-1210.

[17] SATOH T, KIDO H, YANAGISAWA Y.An anonymous communication technique using dummies for location-based services [C]// ICPS ’05: Proceedings of the 2005 International Conference on Pervasive Services.Washington, DC: IEEE Computer Society, 2005: 88-97.

This work is partially supported by the National Natural Science Foundation of China (61170085, 61472141), Shanghai Leading Academic Discipline Project (B412), Shanghai Knowledge Service Platform Project (ZF1213).

ZHAO Dapeng, born in 1988, M.S.candidate.Her research interests include location privacy protection, data mining.

SONG Guangxuan, born in 1992, M.S.candidate.Her research interests include distributed data base, query optimization.

JIN Yuanyuan, born in 1995, M.S.candidate.Her research interests include location privacy protection, data mining.

WANG Xiaoling, born in 1975, Ph.D., professor.Her research interests include location privacy protection, data mining.

Query probability-based location privacy protection approach

ZHAO Dapeng, SONG Guangxuan, JIN Yuanyuan, WANG Xiaoling*

(ShanghaiKeyLaboratoryofTrustworthyComputing,EastChinaNormalUniversity,Shanghai200062,China)

The existing privacy protection technologies rarely consider query probability, map data, semantic information of Point of Information (POI) and other side information, so the attacker can deduce the privacy information of the user by combining the side information with the location data.To resolve this problem, a new algorithm was proposed to protect the location privacy of users, namely ARB (Anonymouse Region Building).Firstly, the space was divided into grids, and historical statistics were utilized to obtain the probability of queries for each grid of space.Then, the anonymous region for each user was obtained based on query probability of corresponding grid to protect the user’s location privacy information.Finally, the location information entropy was used as a measure of privacy protection performance, and the performance of the proposed method was verified by comparison with the existing two methods on the real data set.The experimental results show that ARB obtains better privacy protection effect and lower computation complexity.

Location-Based Service (LBS); location privacy; side information; query probability; anonymity

2016- 08- 12;

2016- 09- 30。 基金項目:國家自然科學基金資助項目(61170085，61472141)；上海市重點學科建設(shè)項目(B412)；上海市可信物聯(lián)網(wǎng)軟件協(xié)同創(chuàng)新中心資助項目(ZF1213)。

趙大鵬(1988—)，男，安徽滁州人，碩士研究生，主要研究方向：位置隱私保護、數(shù)據(jù)挖掘； 宋光旋(1992—)，男，山東青島人，碩士研究生，主要研究方向：分布式數(shù)據(jù)庫、查詢優(yōu)化； 靳遠遠(1995—)，女，河南駐馬店人，碩士研究生，主要研究方向：位置隱私保護、數(shù)據(jù)挖掘； 王曉玲(1975—)，女，山東煙臺人，教授，博士，CCF會員，主要研究方向：位置隱私保護、數(shù)據(jù)挖掘。

1001- 9081(2017)02- 0347- 05

10.11772/j.issn.1001- 9081.2017.02.0347

TP391

A