趙大鵬，宋光旋，靳遠(yuǎn)遠(yuǎn)，王曉玲

(華東師范大學(xué) 上海市高可信計(jì)算重點(diǎn)實(shí)驗(yàn)室,上海 200062)

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

基于查詢概率的位置隱私保護(hù)方法

趙大鵬，宋光旋，靳遠(yuǎn)遠(yuǎn)，王曉玲*

(華東師范大學(xué) 上海市高可信計(jì)算重點(diǎn)實(shí)驗(yàn)室,上海 200062)

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

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

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

2 技術(shù)準(zhǔn)備

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

2.1 基本定義

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

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

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

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

圖1 歷史查詢點(diǎn)分布情況

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

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

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

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

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

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

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

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

2.3 度量指標(biāo)

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

(1)

2.4 攻擊模型

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

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

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

2.6 ARB算法

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

(2)

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

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

輸入 歷史查詢點(diǎn)分布數(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)

計(jì)算寬度為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)

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

17)

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

18)

returnCloakRegion

2.7 時(shí)間復(fù)雜度分析

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

k=r1q1r2q2…riqi…rmqm

(3)

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

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

2.8 安全性分析

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

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

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

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

圖3 熵 vs.k

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

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

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

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

表2表示歷史查詢點(diǎn)個(gè)數(shù)為6萬，用戶匿名層次h=6時(shí)，ARB算法生成匿名區(qū)域的時(shí)間隨用戶隱私偏好k值增加的變化情況。可以看出隨著用戶隱私偏好k值的增加，ARB算法生成匿名區(qū)域時(shí)間也增加，ARB算法計(jì)算開銷較小，可以達(dá)到微秒級(jí)，并且當(dāng)k×N(N為k的因數(shù)個(gè)數(shù))相近時(shí)生成匿名區(qū)域時(shí)間也相近，與2.7節(jié)中的時(shí)間復(fù)雜度分析相吻合。

表2 ARB算法運(yùn)行時(shí)間隨k的變化情況

4 結(jié)語

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

)

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

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

1001- 9081(2017)02- 0347- 05

10.11772/j.issn.1001- 9081.2017.02.0347

TP391

A