萬盛，李鳳華,，牛犇，孫哲，李暉

(1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2.中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室，北京 100195)

位置隱私保護(hù)技術(shù)研究進(jìn)展

萬盛1，李鳳華1,2，牛犇2，孫哲2，李暉1

(1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2.中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室，北京 100195)

日趨流行的基于位置服務(wù)(LBS,location-based service)在為人們?nèi)粘Ｉ顜肀憷耐瑫r也嚴(yán)重威脅到用戶隱私。位置隱私保護(hù)技術(shù)逐漸成為研究熱點(diǎn)，并涌現(xiàn)出大批研究成果。首先介紹位置隱私保護(hù)背景知識，包括位置服務(wù)應(yīng)用場景、位置服務(wù)體系框架、隱私保護(hù)目標(biāo)和系統(tǒng)構(gòu)架；接著討論LBS中的攻擊者模型和隱私保護(hù)度量指標(biāo)；然后對4種基于泛化和模糊的LBS隱私保護(hù)技術(shù)進(jìn)行深入分析和總結(jié)；最后給出了未來LBS隱私保護(hù)技術(shù)潛在的研究方向。

位置服務(wù)；隱私保護(hù)；位置隱私；隱私度量；攻擊者模型

1 引言

隨著移動設(shè)備的普及和定位技術(shù)的發(fā)展，多樣化的基于位置服務(wù)應(yīng)用給人們的日常生活提供了便利，如尋找附近的餐廳或者銀行、搜索從住所到公司的最短路線等。然而，LBS為用戶提供便利的同時也帶來了隱私泄露的威脅[1]。通過收集用戶發(fā)送的服務(wù)請求中的敏感信息，如位置或者興趣點(diǎn)(POI,point of interest)等，服務(wù)提供商能夠獲取并推斷出用戶的更多隱私信息：1) 通過獲取用戶持續(xù)更新的位置信息，可分析其出行規(guī)律[2]，預(yù)測未來所處位置；2) 利用某些時間段內(nèi)用戶位置信息的統(tǒng)計(jì)數(shù)據(jù)，可推斷出用戶家庭地址和單位[3]；3) 結(jié)合地圖等背景知識，可推斷出用戶的健康狀況、生活習(xí)慣及宗教信仰等[4]。這些隱私信息的泄露可能對用戶造成難以估計(jì)的損失。因此，如何保證用戶隱私信息已成為此類服務(wù)中亟待解決的問題。

由于隱私信息能夠帶來巨大的商業(yè)價值，現(xiàn)有研究普遍認(rèn)為服務(wù)提供商不可信或?yàn)閻阂夤粽遊5]，隱私泄露威脅主要源于服務(wù)提供商或其工作人員。即使服務(wù)提供商可信，惡意第三方也可以通過各種手段獲取服務(wù)器所掌握的部分甚至全部用戶信息，如竊聽無線信道或攻破并控制服務(wù)器。相對而言，用戶設(shè)備端在不考慮病毒或木馬入侵的情況下可信。LBS隱私泄露問題大致分為2類：位置隱私(location privacy)泄露和查詢隱私(query privacy)泄露。位置隱私指與用戶位置信息相關(guān)的敏感信息，包括實(shí)時位置，可以幫助攻擊者準(zhǔn)確定位用戶；用戶訪問過的位置，統(tǒng)計(jì)這些位置可以幫助攻擊者了解該用戶的基本信息（家庭地址和工作單位）；由位置信息推斷出的其他敏感信息。查詢隱私指與查詢內(nèi)容相關(guān)的敏感信息，查詢內(nèi)容包括用戶愛好和需求等信息。

針對上述2類隱私泄露問題，近年來，學(xué)者們提出了大量解決方案，取得了一定進(jìn)展。例如，通過加密技術(shù)保護(hù)隱私信息、使用假名代替真實(shí)用戶名、在位置信息中加入噪聲，以及發(fā)布模糊區(qū)域信息取代具體位置坐標(biāo)等，這些技術(shù)在一定程度上降低了攻擊者識別用戶隱私信息的能力，但仍不同程度地存在不足。

本文關(guān)注LBS隱私保護(hù)最常用的4類技術(shù)，分別對每一類進(jìn)行深入分析。首先介紹LBS隱私保護(hù)背景知識，包括位置服務(wù)應(yīng)用場景、體系框架、隱私保護(hù)目標(biāo)和系統(tǒng)構(gòu)架，接著闡述攻擊者模型和隱私保護(hù)度量指標(biāo)，然后深入討論和分析空間隱匿(spatial cloaking)技術(shù)、位置偏移和模糊(perturbation and obfuscation)技術(shù)、偽造虛假位置(dummy)技術(shù)和群組協(xié)作(collaborative group)技術(shù)，最后總結(jié)現(xiàn)有技術(shù)并展望未來發(fā)展。

2 LBS隱私保護(hù)背景知識

2.1 位置服務(wù)應(yīng)用場景

目前，位置服務(wù)在人們的日常生活中已經(jīng)得到了廣泛的應(yīng)用，本文關(guān)注常用的5類應(yīng)用場景：基于位置的POI檢索服務(wù)、基于位置的精確導(dǎo)航服務(wù)、基于位置的社交網(wǎng)絡(luò)服務(wù)、基于位置的運(yùn)動檢測服務(wù)和基于位置的廣告推送服務(wù)。

1) 基于位置的POI檢索服務(wù)

Yelp、大眾點(diǎn)評和百度糯米等都提供基于位置的POI檢索服務(wù)，用戶使用該類軟件可搜索任何感興趣的位置信息，如附近的餐廳、酒店、醫(yī)院和銀行等公共基礎(chǔ)設(shè)施，除了具體的地理位置之外，該類軟件還會向用戶簡要介紹POI的其他信息，如網(wǎng)友點(diǎn)評等，以提升用戶體驗(yàn)。在這類服務(wù)場景中，由于用戶只是偶爾地提出位置服務(wù)請求，這導(dǎo)致服務(wù)提供商獲取的信息通常是單個孤立的請求。目前，大量的LBS隱私保護(hù)方案都是基于這類場景。

2) 基于位置的精確導(dǎo)航服務(wù)

Autonavi Navigation、百度地圖和滴滴出行等都提供基于位置的精確導(dǎo)航服務(wù)，用戶使用這類軟件時，持續(xù)地發(fā)送實(shí)時位置信息，服務(wù)提供商通過計(jì)算，向用戶返回實(shí)時路況信息，并推薦最佳路線完成導(dǎo)航。在這類服務(wù)場景中，服務(wù)提供商獲取的信息是用戶的精確位置和運(yùn)動軌跡。

3) 基于位置的社交網(wǎng)絡(luò)服務(wù)

Foursquare、Facebook和微信等都提供基于位置的社交服務(wù)，包括近鄰檢測服務(wù)和簽到(check-in)服務(wù)。近鄰檢測服務(wù)是指用戶向服務(wù)提供商上傳位置信息，服務(wù)提供商根據(jù)2個用戶的物理位置判斷是否為近鄰，這樣便于用戶發(fā)現(xiàn)新的朋友，與附近的朋友見面。簽到服務(wù)是指用戶在某個語意(semantic)位置簽到，服務(wù)提供商返回該位置附近的信息，并將該位置信息通知其朋友。通過該類軟件，用戶可了解朋友在做什么，從中發(fā)現(xiàn)共同愛好。在這類服務(wù)場景中，服務(wù)提供商和朋友獲取的信息是單個孤立位置點(diǎn)。

4) 基于位置的運(yùn)動檢測服務(wù)

UltimatePedometer、Nike+和咕咚運(yùn)動等都提供基于位置的運(yùn)動檢測服務(wù)，用戶使用該類軟件(同時佩戴智能手環(huán))可統(tǒng)計(jì)其每天運(yùn)動的步數(shù)、距離和路徑等信息，為分析用戶的運(yùn)動情況提供依據(jù)，引導(dǎo)用戶健康生活。在這類服務(wù)場景中，服務(wù)提供商獲取的信息是用戶的運(yùn)動軌跡。

5) 基于位置的廣告推送服務(wù)

ShopAlerts和Getyowza等都提供基于位置的廣告推送服務(wù)，當(dāng)用戶位于某些商店附近時，該類軟件向用戶推送商店的廣告信息，并贈送折扣券。這樣既能幫助商店推銷商品，又方便用戶選擇合適的商品。在這類服務(wù)場景中，服務(wù)提供商獲取的信息是單個孤立的位置點(diǎn)。

上述5類基于位置服務(wù)的應(yīng)用場景已經(jīng)得到了全面的應(yīng)用和推廣，為用戶日常生活帶來了極大便利。除此以外，還有一些位置服務(wù)應(yīng)用場景，如歷史位置驗(yàn)證[6,7]、基于位置的游戲[8]等。

2.2 位置服務(wù)體系框架

位置服務(wù)相關(guān)的應(yīng)用場景大都對應(yīng)如圖1所示的體系框架，該體系框架包括4個主要實(shí)體：移動設(shè)備、定位系統(tǒng)、通信網(wǎng)絡(luò)和服務(wù)提供商。移動設(shè)備指的是人們常用的智能手機(jī)或者平板筆記本；定位系統(tǒng)可以使用GPS定位、Wi-Fi接入點(diǎn)定位或基站定位[9]；通信網(wǎng)絡(luò)可以是3G或4G網(wǎng)絡(luò)。其服務(wù)過程如下：首先，用戶利用移動設(shè)備向服務(wù)提供商提出服務(wù)請求，請求中包含的位置信息由定位系統(tǒng)提供；然后，服務(wù)請求通過通信網(wǎng)絡(luò)發(fā)送到服務(wù)提供商；最后，服務(wù)提供商根據(jù)用戶的位置和請求內(nèi)容進(jìn)行相應(yīng)的處理，并將結(jié)果通過通信網(wǎng)絡(luò)返回用戶設(shè)備。

圖1 位置服務(wù)體系框架

2.3 隱私保護(hù)目標(biāo)

現(xiàn)有基于位置的隱私保護(hù)方案所保護(hù)的用戶屬性主要包括：用戶ID、位置信息、時間信息以及POI，用四元組表示為〈用戶ID，位置信息，時間信息，POI〉。在設(shè)計(jì)方案之初，需明確隱私保護(hù)目標(biāo)，通常為4個屬性的任意組合。

1) 用戶ID

用戶ID是指用戶姓名、身份證號或其他能夠唯一確定用戶的屬性組。如在導(dǎo)航應(yīng)用中，用戶提供實(shí)時位置信息的同時可使用假名以隱藏用戶ID，但保護(hù)效果有限，原因在于用戶會周期性往返于住所和公司，通過這2個信息，可推測出用戶ID[10]的概率較大。

2) 位置信息

位置信息指用戶所處的位置坐標(biāo)，通常不同應(yīng)用對位置信息有不同精確度需求。例如導(dǎo)航應(yīng)用需要用戶相對精確的位置，而天氣預(yù)報應(yīng)用只需要用戶所在的城市即可。

3) 時間信息

時間信息是指用戶處于某個位置時所對應(yīng)的時刻或時間范圍。用戶在某些時間段內(nèi)很可能處于同一位置，比如夜晚一般位于家中，此類時間段可輔助攻擊者推斷用戶家庭地址相關(guān)的隱私信息。此外，用戶使用導(dǎo)航應(yīng)用時，若能夠獲取時間信息，則可計(jì)算出用戶的行駛速度，從而推測用戶的出行工具等。

4) POI

POI指用戶查詢的服務(wù)內(nèi)容，包括查詢附近餐廳、酒店、購物中心、醫(yī)院和銀行等。POI的暴露很可能導(dǎo)致用戶隱私泄露。例如，某用戶經(jīng)常查詢附近的酒吧，則可推斷出其可能有酗酒習(xí)慣；某用戶經(jīng)常查詢周圍的醫(yī)院，則可推斷出其可能患有某種慢性疾病。

2.4 隱私保護(hù)系統(tǒng)構(gòu)架

根據(jù)隱私保護(hù)機(jī)制(LPPM,location privacy protection mechanism)主體的不同，隱私保護(hù)系統(tǒng)構(gòu)架可以分為2類。第一類依賴可信第三方(TTP,trusted third party)的系統(tǒng)構(gòu)架，如圖2所示，由可信匿名服務(wù)器(trusted anonymity server)獲取所有用戶的位置信息，并負(fù)責(zé)執(zhí)行LPPM。第二類不依賴可信第三方的系統(tǒng)構(gòu)架，如圖3所示，由用戶移動設(shè)備執(zhí)行LPPM，直接發(fā)送服務(wù)請求并接收查詢結(jié)果。這2類系統(tǒng)構(gòu)架各有特點(diǎn)，前者的優(yōu)勢在于TTP能夠獲取海量用戶的位置信息，并且輔助用戶過濾服務(wù)數(shù)據(jù)，其缺點(diǎn)在于TTP可能成為攻擊者的目標(biāo)，在實(shí)際使用中它的可信性難以保障。后者的優(yōu)勢在于其部署LPPM的簡易性，方便用戶根據(jù)其隱私保護(hù)需求調(diào)整隱私保護(hù)粒度，其缺點(diǎn)為LPPM的實(shí)現(xiàn)受移動設(shè)備性能的限制，且無法獲取全局用戶位置信息。

圖2 依賴可信第三方的系統(tǒng)構(gòu)架

圖3 不依賴可信第三方的系統(tǒng)構(gòu)架

3 攻擊者模型

從時間維度上，攻擊者模型可分為2類，一類攻擊者能獲取某一時刻用戶的單次服務(wù)請求，稱為單點(diǎn)攻擊模型；另一類攻擊者可獲得用戶在一段時間內(nèi)的服務(wù)請求，甚至是整個運(yùn)動過程中所有服務(wù)請求，稱為多點(diǎn)攻擊模型。從背景知識維度上，攻擊者模型也分為2類，其中一類模型不考慮或假設(shè)攻擊者不掌握任何背景知識（電話簿、統(tǒng)計(jì)數(shù)據(jù)等），只依靠單次或幾次服務(wù)請求中的信息推斷用戶的隱私信息，稱為無背景知識模型；另一類假設(shè)攻擊者長期收集和利用各類相關(guān)的背景知識，稱為背景知識模型。

3.1 無背景知識模型

在無背景知識模型下，攻擊者的攻擊方式主要包括位置同質(zhì)攻擊、區(qū)域中心攻擊和位置分布攻擊。

位置同質(zhì)攻擊[11]是指攻擊者分析用戶提交的隱匿區(qū)域內(nèi)的多個位置，若距離非常接近，如位于同一個建筑內(nèi)，雖然達(dá)到k-匿名的要求，但由于隱匿空間太小，用戶的位置隱私仍然無法得到很好的保護(hù)。

區(qū)域中心攻擊[12]是指部分空間隱匿算法可能造成用戶的真實(shí)位置以相對較高的概率出現(xiàn)在隱匿區(qū)域中心。如在某些群組協(xié)作隱私保護(hù)方案中，如圖4所示，發(fā)起者向周圍的協(xié)助用戶發(fā)送請求，不斷擴(kuò)張其匿名集合，從而滿足隱私保護(hù)要求。這種方式往往導(dǎo)致發(fā)起者位于隱匿區(qū)域的中心，攻擊者可極大地縮小用戶所在范圍。

圖4 區(qū)域中心攻擊

位置分布式攻擊[13]主要利用用戶發(fā)送位置分布不均勻的信息推測用戶真實(shí)位置。例如，若攻擊者觀察到隱匿區(qū)域中只有一個用戶位于人口稀少區(qū)域，而其他k?1個用戶位于人口密集區(qū)域，那么位于人口稀少區(qū)域的用戶很可能是該服務(wù)請求的發(fā)送者。如圖5所示，用戶A位于人口稀少區(qū)域，用戶B、C、D和E位于人口密集區(qū)域，假設(shè)k=4。當(dāng)用戶A發(fā)送查詢請求時，由于其位于人口稀少區(qū)域，為了達(dá)到k=4的要求，其隱匿區(qū)域R1必須擴(kuò)展到人口密集區(qū)域，而其他4個用戶無需擴(kuò)大隱匿區(qū)域。由此，攻擊者推斷出用戶A發(fā)送隱匿區(qū)域R1的概率極高。

圖5 位置分布式攻擊

3.2 背景知識模型

在背景知識模型下，攻擊者的攻擊方式主要包括同源攻擊、概率分布攻擊和位置相似性攻擊。

同源攻擊[14]是指攻擊者了解用戶會在同一位置多次發(fā)送服務(wù)請求并收集該信息，結(jié)合LPPM，攻擊者可計(jì)算出最有可能產(chǎn)生這一系列請求的用戶位置。如圖6所示，攻擊者了解到用戶在某家咖啡店，該用戶使用空間隱匿作為LPPM。經(jīng)過一段時間，攻擊者收集到該用戶發(fā)送的隱匿區(qū)域R1、R2和R3，求出3個隱匿區(qū)域的交集，即可將用戶真實(shí)位置限定在極小的范圍內(nèi)。

圖6 同源攻擊

概率分布攻擊[15]是指攻擊者能夠收集到用戶的服務(wù)請求歷史記錄，由此計(jì)算出其查詢概率分布。當(dāng)用戶發(fā)送查詢請求時，若隱匿區(qū)域內(nèi)概率分布不均勻，則攻擊者可以推斷出用戶很可能位于概率較高的位置。

位置相似性攻擊[16]是指攻擊者分析隱匿區(qū)域內(nèi)的語義信息，若該區(qū)域僅包含一種語義信息，比如醫(yī)院或?qū)W校等，則攻擊者可推斷出用戶的行為。如圖7所示，X表示用戶A的真實(shí)位置，其隱私保護(hù)要求為k≥5，S1、S2和S3分別表示醫(yī)院、學(xué)校和銀行3個區(qū)域。若隱匿空間R僅包含S1，雖然可以達(dá)到隱私保護(hù)要求，但攻擊者可以推斷出用戶患有某種疾病，正在進(jìn)行治療。因此，用戶應(yīng)當(dāng)將隱匿區(qū)域擴(kuò)展到包含S2和S3，以抵御該類攻擊。

圖7 位置相似性攻擊

3.3 多點(diǎn)攻擊模型

在多點(diǎn)攻擊模型下，攻擊者的攻擊方式主要包括位置依賴攻擊、連續(xù)位置攻擊和位置追蹤攻擊。

位置依賴攻擊[17]主要根據(jù)用戶2次連續(xù)提交的隱匿區(qū)域在時間上的相關(guān)性，結(jié)合前一隱匿區(qū)域和用戶最大運(yùn)動速度計(jì)算出最大移動邊界(MMB,maximum movement boundary)，將該邊界區(qū)域與后一隱匿區(qū)域求交集，可縮小隱匿區(qū)域大小，甚至直接定位用戶位置。如圖8所示，在t1時刻，用戶A需要查詢附近的醫(yī)院，于是向服務(wù)提供商發(fā)送包含A、B和C的隱匿區(qū)域R1。經(jīng)過一段時間，在t2時刻，用戶A需要查詢附近的加油站，于是向服務(wù)提供商發(fā)送包含A、D和E的隱匿區(qū)域R2。若攻擊者能夠獲取隱匿區(qū)域R1和用戶A的最大運(yùn)動速度，通過計(jì)算可獲得用戶A從t1時刻到t2時刻的最大移動邊界。將最大移動邊界與R2求交集，可定位A的真實(shí)位置。

圖8 位置依賴攻擊

連續(xù)位置攻擊[18,19]是指運(yùn)動中的用戶連續(xù)發(fā)送自己的位置給服務(wù)提供商，即使位置信息是一個隱匿區(qū)域，攻擊者可將連續(xù)的隱匿區(qū)域鏈接在一起，從而識別出查詢發(fā)起者。如圖9所示，假設(shè)存在11個用戶A～K，用戶A的隱私保護(hù)要求為k=5。在t1時刻，用戶A提出查詢請求，空間隱匿算法產(chǎn)生一個包含A、B、C、D和E的隱匿區(qū)域，攻擊者有的概率猜測出查詢發(fā)送者。在t2時刻，各用戶的位置信息發(fā)生變化，攻擊者觀察到的隱匿區(qū)域包含A、B、F、G和H，通過聯(lián)系t1時刻和t2時刻的隱匿區(qū)域，攻擊者可推斷出只有A和B可能是該查詢的發(fā)送者。類似地，攻擊者再聯(lián)系t3時刻的隱匿區(qū)域，可以推測出用戶A為該連續(xù)LBS查詢的發(fā)送者。

圖9 連續(xù)位置攻擊

位置追蹤攻擊[20]主要利用用戶使用導(dǎo)航應(yīng)用時，實(shí)時更新其精確位置信息。通過收集和分析這些信息，攻擊者可以獲取用戶的運(yùn)動規(guī)律和行為習(xí)慣。若用戶只采用隨機(jī)變換假名的方法，沒有合理使用混淆區(qū)(mix zone)等技術(shù)，則無法抵御這類攻擊。

4 隱私保護(hù)度量指標(biāo)

k-匿名和位置熵是目前被廣泛使用的隱私保護(hù)度量指標(biāo)，除此以外，一些學(xué)者結(jié)合各類應(yīng)用場景提出了很多度量指標(biāo)。

4.1 k-匿名

隱私保護(hù)度量指標(biāo)中最為經(jīng)典的是k-匿名，它首先出現(xiàn)在數(shù)據(jù)庫方向[21]，被定義為：對于準(zhǔn)標(biāo)識符屬性，任意一條記錄無法與其他至少k?1條記錄區(qū)分，準(zhǔn)標(biāo)識符屬性是指家庭地址、生日和郵政編碼等可以相結(jié)合以唯一確定某人身份的屬性。在位置服務(wù)中，該度量指標(biāo)可以總結(jié)為“向服務(wù)提供商發(fā)布的區(qū)域中，至少包含其他k?1個不可區(qū)分的用戶信息[22]”。

目前，多數(shù)隱私保護(hù)方案采用k-匿名作為隱私保護(hù)度量指標(biāo)。如部分基于匿名服務(wù)器的方案[20,22～26]由匿名服務(wù)器產(chǎn)生一個隱匿區(qū)域，包含查詢用戶與其他至少k?1個用戶，攻擊者從這k個用戶中識別出查詢者的概率為；部分不依賴可信第三方的方案[27～31]，由移動設(shè)備產(chǎn)生至少k?1個虛假位置，將用戶真實(shí)位置混入其中一并發(fā)送給服務(wù)提供商，攻擊者從中識別出真實(shí)位置的概率為。由于k-匿名沒有考慮隱匿區(qū)域內(nèi)建筑的語義信息，若隱匿區(qū)域正處于某醫(yī)院范圍內(nèi)，攻擊者可推測出用戶患有某種疾病。l-多樣性[32,33]作為k-匿名的一種擴(kuò)展，要求隱匿區(qū)域內(nèi)至少包含l種不同語義類型的小區(qū)域，可有效避免上述問題。另一種擴(kuò)展是強(qiáng)k-匿名[34]，要求用戶在連續(xù)的查詢請求中，組成隱匿區(qū)域的k個用戶盡可能不變，可防止攻擊者通過計(jì)算多個隱匿區(qū)域的交集來定位用戶位置。

4.2 位置熵

k-匿名得到了廣泛應(yīng)用，但也存在明顯缺陷。比如當(dāng)隱匿區(qū)域中用戶出現(xiàn)的概率不相等時，k-匿名不能準(zhǔn)確反映隱私保護(hù)水平。因此，很多學(xué)者提出了位置熵的概念。位置熵起源于香農(nóng)熵[35]，是一種度量不確定性的方法。目前，很多方案[35～40]基于位置熵設(shè)計(jì)隱私保護(hù)度量指標(biāo)。Palanisamy等[39]針對基于混淆區(qū)的方案提出成對熵(pairwise entropy)的概念。理想情況下，用戶進(jìn)入混淆區(qū)后會停留任意隨機(jī)時間，且從任何一個出口離開的概率是相同的。若用戶i離開混淆區(qū)時的假名為i′，則用戶i′的位置熵為

其中，A為混淆區(qū)內(nèi)所有用戶的集合，pi′→j為i′映射到用戶j的概率，理想情況下，i′映射為A中任意用戶的概率相等。在實(shí)際中，混淆區(qū)一般設(shè)置在交叉路口，很多因素會影響其效果：1) 時間因素，先進(jìn)入混淆區(qū)的用戶先離開的概率大于后進(jìn)入混淆區(qū)的用戶；2) 路網(wǎng)環(huán)境，用戶直行、拐彎和調(diào)頭的概率各不相同；3) 道路狀況，比如某個出口堵車，會提高攻擊者推斷出用戶從某些出口駛出的概率。因此，實(shí)際使用時i′映射為A中任意用戶的概率不相同。若少量映射關(guān)系發(fā)生的概率很高，而大部分映射關(guān)系發(fā)生的概率很低，那么即使位置熵很高，攻擊者也能以較高概率推測出映射關(guān)系。為了解決該問題，在成對熵的概念中，假設(shè)混淆區(qū)只有2個用戶i和j，離開混淆區(qū)時的假名為i′和j′，則成對熵Hpair(i,j)可以表示為

若i′映射到用戶i和j的概率pi′→i和pi′→j相等，則Hpair(i,j)等于1，攻擊者能夠聯(lián)系前后假名的可能性最低。但是應(yīng)當(dāng)同時考慮成對熵Hpair(j,i)，若j′映射到用戶i和j的概率pj′→i和pj′→j有較大差距，攻擊者聯(lián)系前后假名的可能性依然很高。因此，用戶i和j的成對熵應(yīng)當(dāng)是Hpair(i,j)和Hpair(j,i)中的較小者，有效的混淆區(qū)應(yīng)當(dāng)滿足任意2對用戶的成對熵都接近1。針對群組協(xié)作的隱私保護(hù)方案，Niu等[37]提出了單個用戶和全局隱私度量標(biāo)準(zhǔn)。當(dāng)用戶直接向服務(wù)器提出服務(wù)請求時，隱私保護(hù)水平通過單個用戶隱私度量標(biāo)準(zhǔn)來衡量。文獻(xiàn)[37]中采用了偽造虛假位置的方法，地圖被分為N×N個單元，從中選擇k個位置，根據(jù)背景知識確定k個位置的查詢概率qi，然后計(jì)算出每個位置成為真實(shí)位置的概率

最后，計(jì)算出位置熵，即攻擊者推斷出真實(shí)位置的不確定性，位置熵越大，隱私保護(hù)水平越高。當(dāng)所有pi相等時，位置熵最大，即lbk。同時該文獻(xiàn)中群組組員緩存并共享數(shù)據(jù)，減少了向服務(wù)提供商提出請求的次數(shù)，提高了整體隱私保護(hù)水平，從而提出了全局隱私度量標(biāo)準(zhǔn)。對于由緩存應(yīng)答的服務(wù)請求，服務(wù)器無法獲得任何信息，因此，攻擊者推斷出真實(shí)位置的不確定性為lbN2。全局隱私度量標(biāo)準(zhǔn)可表示為

其中，Qcache表示由緩存提供的服務(wù)次數(shù)，Qserver表示由服務(wù)器提供的服務(wù)次數(shù)，Hq表示位置熵。可以看出，應(yīng)當(dāng)從兩方面提高整體隱私保護(hù)水平，一方面提高每一次查詢的位置熵，另一方面提升緩存的命中率，使更多請求通過緩存應(yīng)答。

4.3 其他度量方法

除了k-匿名和位置熵，學(xué)者們也提出了許多新的度量方法，扭曲度和差分隱私是其中較為典型的2種度量方法。

4.3.1 扭曲度

Shokri等[41]提出隱私保護(hù)度量指標(biāo)應(yīng)當(dāng)滿足3點(diǎn)要求：1) 從攻擊者角度，考慮攻擊者利用背景知識最小化出錯概率；2) 考慮真實(shí)位置與攻擊者推斷位置間的差異性，多數(shù)情況下該差異性可表示為真實(shí)位置與推斷位置間的距離；3) 適用于各類隱私保護(hù)技術(shù)。文獻(xiàn)[41]中提出一種位置隱私度量框架，包括用戶、軌跡、攻擊者及LPPM。由于攻擊者的目的是將經(jīng)過LPPM變換后的用戶位置重新轉(zhuǎn)化為用戶的真實(shí)軌跡，因此，各類LBS隱私保護(hù)技術(shù)所提供的隱私保護(hù)水平取決于用戶真實(shí)的軌跡與攻擊者推斷的軌跡之間的差異，即扭曲度，扭曲度越大，隱私保護(hù)水平越高。對于用戶u，在時刻t，扭曲度可以表示為

其中，whereis(u,t)表示u在t時刻的真實(shí)位置，Y表示u在一段時間內(nèi)可能發(fā)生的某條軌跡，loc(tail(Y))表示軌跡Y在t時刻對應(yīng)的位置。由于函數(shù)π(·)表示攻擊者通過背景知識推斷出的u按照某條軌跡運(yùn)動的概率，D(·)表示2個位置的差異，且各類LBS隱私保護(hù)技術(shù)都適用，因此滿足上述3點(diǎn)要求。Shokri等[15]細(xì)化了文獻(xiàn)[41]中的位置隱私度量框架：用戶將真實(shí)位置通過LPPM進(jìn)行調(diào)整和扭曲，變成某種形式的假位置，并將用戶名換成假名。同時攻擊者可以獲取三方面的信息：1) LPPM；2) 服務(wù)提供商所獲取的信息；3) 背景知識，如用戶查詢歷史記錄等?；诖耍粽咴O(shè)法推斷用戶的真實(shí)位置。此外，文獻(xiàn)[15]從攻擊者的角度確切地闡述了準(zhǔn)確性(accuracy)、確定性(certainty)及正確性(correctness)這3個指標(biāo)，其中，確定性對應(yīng)位置熵，正確性對應(yīng)扭曲度。準(zhǔn)確性：由于攻擊者不可能了解用戶的所有相關(guān)信息，故其推斷出的用戶位置分布律(Pr(x|o)，x為用戶位置的可能值，o為提交的虛假位置)與理想情況下?lián)碛兴行畔r推斷出的分布律是有差距的，差距越小，準(zhǔn)確性越高。確定性：利用攻擊者推斷出的用戶位置分布律，計(jì)算出位置熵來度量確定性，即

位置熵越高，確定性越低，攻擊者就越不容易確定出用戶真實(shí)位置。正確性：即使攻擊者收集到足夠多的背景知識、推斷出的用戶位置分布律很準(zhǔn)確、而且從用戶位置分布律中很容易確定出用戶位置，即確定性很高，但正確性未必很高，如在某次查詢中，用戶真實(shí)位置在以往數(shù)據(jù)中從未出現(xiàn)過。通過計(jì)算用戶真實(shí)位置xc與攻擊者猜測的所有可能值的期望距離來度量正確性，即

用戶最關(guān)心的是攻擊者能否推斷出正確位置，以及攻擊者推斷結(jié)果與真實(shí)位置有多大差距，因此，正確性是度量隱私保護(hù)水平最重要的指標(biāo)。

4.3.2 差分隱私

以上度量方式均存在一個明顯缺陷，即在度量隱私保護(hù)水平時需要假設(shè)攻擊者掌握的背景知識，而差分隱私的提出能很好地解決該問題。差分隱私[42](differential privacy)首先出現(xiàn)在數(shù)據(jù)發(fā)布隱私保護(hù)領(lǐng)域，其不考慮攻擊者擁有多少背景知識，通過向查詢或者在分析結(jié)果中添加適當(dāng)噪音的方式來達(dá)到一定的隱私保護(hù)效果。近幾年來，差分隱私也被引入到位置隱私保護(hù)領(lǐng)域，取得了一定進(jìn)展。若按照嚴(yán)格的差分隱私要求，要求位置上的任何移動對于LPPM處理后的結(jié)果都沒有影響，或者影響極小。然而，嚴(yán)格的差分隱私要求使服務(wù)提供商無法提供精準(zhǔn)的服務(wù)信息。因此，Andres等[43]借鑒差分隱私思想，提出通過位置不可分辨性(geo-indistinguish ability)來表示用戶的位置隱私保護(hù)需求。文獻(xiàn)[43]指出向服務(wù)提供商發(fā)送隱匿區(qū)域的方法使攻擊者能夠準(zhǔn)確地獲取用戶所處區(qū)域，因此，并未達(dá)到理想的隱私保護(hù)水平。用戶期望隱私保護(hù)水平應(yīng)當(dāng)與距離相關(guān)，例如，攻擊者從用戶提供的位置信息中推斷出用戶位于半徑為1 km的某區(qū)域的概率極低，而隨著半徑的擴(kuò)大，概率也隨之提高，如攻擊者推斷出用戶位于某城市的概率幾乎是百分之百。根據(jù)上述思想，文獻(xiàn)[43]中給出了不可分辨性的3種形式化定義，第3種定義為

其中，r表示x和x′所處區(qū)域半徑，函數(shù)d(·)表示2個位置的距離，該定義表明2個位置的距離越近，LPPM產(chǎn)生相同結(jié)果S的概率應(yīng)當(dāng)接近，反之，LPPM產(chǎn)生相同結(jié)果的概率相差可較大。不同于文獻(xiàn)[38]要求一個圓形區(qū)域內(nèi)的所有位置都滿足位置不可分辨性，Xiao等[44]定義了基于δ-位置集的差分隱私，δ-位置集Xt選取用戶出現(xiàn)概率較高的位置，在這些位置上應(yīng)當(dāng)滿足差分隱私，使任意t時刻，攻擊者不能根據(jù)用戶所發(fā)送的位置Zt區(qū)分出Xt中的任意2個位置，具體定義如下

其中，A(·)表示LPPM，使用δ-位置集的好處在于對于掌握道路環(huán)境和用戶運(yùn)動模型等精確背景知識的攻擊者而言，將真實(shí)位置偏移到概率較低的位置意義不大，故基于δ-位置集的差分隱私更符合實(shí)際要求。

5 LBS隱私保護(hù)技術(shù)

常用LBS隱私保護(hù)方法主要包括基于策略的方法、基于密碼學(xué)的方法和基于泛化和模糊的方法。

基于策略的方案[45,46]主要通過制定隱私保護(hù)規(guī)則、標(biāo)準(zhǔn)和詳細(xì)規(guī)范來約束服務(wù)提供商，禁止位置信息被不正當(dāng)?shù)氖褂谩ｋm然此類方案能夠同時保護(hù)位置隱私和查詢隱私，但缺陷明顯：1) 服務(wù)提供商能否有效執(zhí)行相關(guān)策略往往依賴于法律制度和社會輿論的壓力；2) 沒有度量隱私保護(hù)水平的標(biāo)準(zhǔn)。

基于密碼學(xué)的方案[47～49]主要通過相關(guān)密碼技術(shù)處理向服務(wù)提供商發(fā)送的請求并獲取服務(wù)數(shù)據(jù)以保護(hù)用戶隱私信息。此類方案無需匿名服務(wù)器，位置信息加密后發(fā)送給服務(wù)提供商，后者解密后執(zhí)行相應(yīng)查詢，并將結(jié)果加密后返回，因此安全性很高，但有著較明顯的缺陷：1) 服務(wù)器端需大量的代碼修改以實(shí)現(xiàn)相關(guān)功能，且計(jì)算開銷較大；2) 對于服務(wù)提供商而言，隱私信息可產(chǎn)生巨大的經(jīng)濟(jì)價值，故沒有足夠動機(jī)用高昂成本來保護(hù)用戶隱私信息，因此，此類方案可行性較差。

以下主要介紹并詳細(xì)分析基于泛化和模糊的LBS隱私保護(hù)技術(shù)，包括常用的4種技術(shù)：空間隱匿、位置偏移和模糊、偽造虛假位置和群組協(xié)作。

5.1 空間隱匿

空間隱匿技術(shù)通過為每個查詢用戶形成一個包含k個真實(shí)用戶的隱匿區(qū)域，使服務(wù)提供商難以從該隱匿區(qū)域中確定用戶的真實(shí)身份和準(zhǔn)確位置。

Gruteser等[20]將k-匿名的概念引入到位置隱私領(lǐng)域，并首次提出了一種簡單而有效的空間隱匿方案，其基本思想為：從一個足夠大的區(qū)域開始，將該區(qū)域分割成4個小區(qū)域，計(jì)算真實(shí)用戶所在區(qū)域的用戶數(shù)，若用戶數(shù)大于k則繼續(xù)分割，直到用戶數(shù)小于k為止。倒數(shù)第2次分割形成的區(qū)域就是隱匿區(qū)域?？紤]到當(dāng)用戶處在人口密度較小地區(qū)時只有增大隱匿區(qū)域才可能覆蓋k個用戶，服務(wù)質(zhì)量會明顯降低。因此，文獻(xiàn)[20]提出了改進(jìn)方案，其基本思想為：用戶設(shè)置隱匿區(qū)域面積，經(jīng)若干次分割后，隱匿區(qū)域縮小到用戶的設(shè)定值，觀察該隱匿區(qū)域內(nèi)出現(xiàn)的用戶數(shù)量，當(dāng)有k?1個用戶訪問過該區(qū)域時，將此隱匿區(qū)域和這段時間間隔發(fā)送給服務(wù)提供商。該方案主要問題是用戶無法根據(jù)需求設(shè)置不同的k和隱匿區(qū)域。Chow等[22]提出個性化k-匿名方案，將整個區(qū)域?qū)蛹墑澐?，劃分方法為每層對上層的每個單元進(jìn)行四等分，從而形成自頂向下的金字塔型數(shù)據(jù)結(jié)構(gòu)，金字塔中的每個單元都記錄該區(qū)域的用戶數(shù)量。同時，在一張散列表中記錄每個用戶所在的底層單元和隱私需求，用戶可設(shè)置不同的k和隱匿區(qū)域大小。由于用戶位置的持續(xù)變化，金字塔形數(shù)據(jù)結(jié)構(gòu)和散列表均需實(shí)時更新。當(dāng)用戶需要位置服務(wù)時，從用戶散列表?xiàng)l目中獲取隱私需求和用戶所在單元，若用戶所在單元的用戶數(shù)和區(qū)域面積都超過隱私要求，則將該單元發(fā)送給服務(wù)提供商，否則考察該單元水平方向的鄰居單元和豎直方向的鄰居單元，若用戶所在單元與其中一個鄰居單元合并后滿足用戶隱私要求，則將合并后的區(qū)域發(fā)送給服務(wù)提供商，否則返回到該單元的父單元，并重復(fù)執(zhí)行上述過程直到找到滿足條件的區(qū)域。然而，上述2種空間隱匿方案均不能抵抗位置推斷攻擊，為此文獻(xiàn)[50]提出利用希爾伯特曲線(Hilbert curve)構(gòu)造隱匿區(qū)域。根據(jù)希爾伯特曲線對用戶進(jìn)行排序，若采用k-匿名，則將連續(xù)k個用戶分為一組，最后一組不超過2k?1個用戶，由于同一組用戶形成相同的隱匿區(qū)域，因此，該方案能夠抵御位置推斷攻擊。Ngo等[51]指出，由于空間維度的降低，該方案[50]容易產(chǎn)生較大的隱匿區(qū)域，由此給服務(wù)提供商帶來大量的計(jì)算開銷和網(wǎng)絡(luò)通信開銷。如圖10所示，假設(shè)有8個用戶，隱私保護(hù)需求為3-匿名，由此將用戶分為2組。圖10(a)中2個隱匿區(qū)域大小分別是16個單元和49個單元，平均值為32.5個單元。通過對希爾伯特曲線的翻轉(zhuǎn)或旋轉(zhuǎn)操作，可減少大部分用戶的隱匿區(qū)域，例如圖10(b)中2個隱匿區(qū)域大小的平均值為13個單元。由此，若對所有可能的希爾伯特曲線進(jìn)行篩選，可為每個用戶找到其最小的隱匿區(qū)域，但該方式又不能抵御推斷攻擊。為了同時解決這2個問題，文獻(xiàn)[51]提出了一種基于差分隱私的隱匿區(qū)域擾動方案，將隱匿區(qū)域最小的希爾伯特曲線版本擾動到所有可能的希爾伯特曲線版本。根據(jù)差分隱私的性質(zhì)，相鄰用戶一般會得到較為接近的擾動結(jié)果以抵御推斷攻擊。另一方面，其噪聲函數(shù)保證隱匿區(qū)域越小的希爾伯特曲線版本有較高概率作為擾動結(jié)果。

圖10 希爾伯特曲線變換

以上空間隱匿方案均采用了k-匿名的度量標(biāo)準(zhǔn)。除了k-匿名，位置熵的度量標(biāo)準(zhǔn)也被廣泛應(yīng)用于該類方案。Beresford等[35]提出基于混淆區(qū)(mix zone)的隱私保護(hù)方案。該方案將區(qū)域分為2類：混淆區(qū)和應(yīng)用區(qū)。當(dāng)用戶位于應(yīng)用區(qū)時，匿名服務(wù)器可向服務(wù)提供商發(fā)布位置信息。而當(dāng)用戶進(jìn)入混淆區(qū)時，不允許匿名服務(wù)器發(fā)布信息。首先所有用戶都被賦予假名，當(dāng)用戶離開混淆區(qū)時更換新假名。如圖11所示，假設(shè)某時刻假名為A和B的用戶進(jìn)入混淆區(qū)，此時立即停止向服務(wù)提供商發(fā)布位置信息。當(dāng)2名用戶離開時，匿名服務(wù)器為他們分配新的假名X和Y。由于服務(wù)提供商無法找出前后2個假名間的聯(lián)系，則可認(rèn)為達(dá)到2-匿名的效果。然而，若考慮用戶的運(yùn)動模式，比如用戶直行的概率遠(yuǎn)大于折返的概率，那么這種情況很難達(dá)到2-匿名的效果。因此，該場景中使用位置熵的度量方法衡量隱私保護(hù)水平更為準(zhǔn)確。Palanisamy等[39]將混淆區(qū)應(yīng)用到路網(wǎng)環(huán)境下的車輛位置隱私保護(hù)，為了保證混淆區(qū)有較大的成對熵，必須使同時進(jìn)入混淆區(qū)的用戶在混淆區(qū)內(nèi)停留的時間盡可能相同。由此，文獻(xiàn)[39]提出了3種改進(jìn)方案。方案1在普通混淆區(qū)基礎(chǔ)上加入時間窗口，需要變換假名的車輛需滿足進(jìn)入混淆區(qū)的時間相近，從而提高成對熵，后2種改進(jìn)都包含時間窗口功能。方案2考慮了道路狀況，如堵車，攻擊者通過觀察車輛駛出時間，可推斷出車輛從各個出口駛出的概率。針對該問題，方案2提出根據(jù)實(shí)際情況適當(dāng)偏移矩形混淆區(qū)，保證從每個入口到達(dá)交叉路口中心的時間相同。方案3考慮用戶速度偏離平均速度，其從各個出口駛出的概率不同。針對該問題，方案3采用非矩形混淆區(qū)，即混淆區(qū)只包含交叉路口中心區(qū)和出口路段，使用戶在混合區(qū)中停留的時間盡可能相同。Xu等[23]擴(kuò)展了位置熵的概念，提出利用區(qū)域人口密度來體現(xiàn)隱私保護(hù)需求。文獻(xiàn)[23]指出隱私是用戶的一種主觀概念，用戶無法判斷其隱私保護(hù)需求應(yīng)當(dāng)對應(yīng)多大的k值，因此，利用k值反映用戶的隱私保護(hù)要求是不準(zhǔn)確的。由此，文獻(xiàn)[23]中提出由用戶確定某個示例區(qū)域，該區(qū)域能夠滿足其隱私保護(hù)需求，由匿名服務(wù)器計(jì)算該區(qū)域的人口密度，并作為用戶的隱私保護(hù)需求。在計(jì)算區(qū)域人口密度時，不能簡單地統(tǒng)計(jì)該區(qū)域中的用戶數(shù)，因?yàn)槟承┯脩粼谠搮^(qū)域出現(xiàn)的次數(shù)要遠(yuǎn)高于其他用戶，如用戶A的工作單位位于該區(qū)域，則用戶A提出服務(wù)請求的概率較大，因此，利用位置熵定義區(qū)域人口密度更為準(zhǔn)確。匿名服務(wù)器通過收集歷史數(shù)據(jù)計(jì)算出位置熵，包括經(jīng)過該區(qū)域的用戶數(shù)和每個用戶出現(xiàn)的次數(shù)等，從而得到該區(qū)域人口密度?？臻g隱匿技術(shù)也存在缺點(diǎn)，如在人口稀少區(qū)域，為了達(dá)到隱私保護(hù)需求，服務(wù)質(zhì)量將受到較大影響。此外，雖然依賴可信第三方的系統(tǒng)構(gòu)架能夠獲取海量的用戶位置信息，為實(shí)現(xiàn)空間隱匿技術(shù)提供保障。但是此類系統(tǒng)構(gòu)架缺陷明顯：1) 隨著用戶規(guī)模和應(yīng)用軟件的劇增，匿名服務(wù)器的負(fù)載較大，將成為位置服務(wù)生態(tài)系統(tǒng)的性能瓶頸；2) 單點(diǎn)失效問題嚴(yán)重，將極大地影響用戶體驗(yàn)；3) 若TTP被攻擊者控制，用戶的位置信息和服務(wù)請求歷史記錄都會被泄露。不依賴可信第三方的系統(tǒng)構(gòu)架可以避免上述問題，以下3類技術(shù)均針對不依賴可信第三方的系統(tǒng)構(gòu)架。

圖11 混淆區(qū)

5.2 位置偏移和模糊

位置偏移和模糊技術(shù)[43,52～57]通過加入噪音降低位置精確度，如真實(shí)位置的小范圍移動或者以某個區(qū)域代替真實(shí)位置，來達(dá)到保護(hù)用戶隱私的效果。

Yiu等[52]提出SpaceTwist方案，主要解決k近鄰(knearest neighbor)查找問題。首先，在真實(shí)位置附近挑選一個位置設(shè)為錨點(diǎn)(anchor)，然后以其為位置信息連續(xù)向服務(wù)器發(fā)送查詢請求，查詢范圍不斷擴(kuò)大，最后計(jì)算返回結(jié)果與真實(shí)位置之間的距離，挑選k個最為鄰近的結(jié)果。如圖12所示，q為用戶真實(shí)位置，g為錨點(diǎn)，算法以錨點(diǎn)為中心逐次找到滿足服務(wù)請求的近鄰a、b、c，同時更新m和n(m為g到最新發(fā)現(xiàn)的近鄰的距離，n為q與最近近鄰的距離，m逐漸增大，n逐漸減小)，直到滿足m＞n+distance( q,g)時算法結(jié)束。錨點(diǎn)離真實(shí)位置越遠(yuǎn)，隱私保護(hù)水平越高，但相應(yīng)的計(jì)算開銷也越大。Ardagna等[54]提出位置模糊可通過幾種基本操作及其組合來完成。該方案考慮到現(xiàn)有定位技術(shù)存在一定誤差，用戶只能確定其真實(shí)位置的所在區(qū)域，該區(qū)域大小表示某種定位技術(shù)的最高精確度。由此引出相關(guān)性(relevance)的概念，即相對于某種定位技術(shù)最高精確度的損失，它可同時度量精確性和隱私保護(hù)水平，通常情況下，LPPM產(chǎn)生的精確度損失越大，相關(guān)性就越低，同時隱私保護(hù)水平就越高，用戶可以通過相關(guān)性準(zhǔn)確描述其隱私保護(hù)需求。為達(dá)到用戶指定的相關(guān)性要求，文獻(xiàn)[54]提出3種位置模糊基本操作：擴(kuò)大半徑、縮小半徑以及圓心偏移。通過以上3種操作的組合，能夠以多種方式實(shí)現(xiàn)用戶的相關(guān)性要求，靈活完成位置模糊處理。Perazzo等[53]指出已有的位置偏移和模糊方案存在缺陷[43,54,55]，此類方案僅簡單地偏移位置并擴(kuò)大隱匿區(qū)域，沒有考慮到攻擊者可能了解偏移算法，或者統(tǒng)計(jì)大量數(shù)據(jù)得出偏移向量概率分布等信息。通過此類信息，攻擊者可計(jì)算出用戶在隱匿區(qū)域內(nèi)分布的概率密度，若不為常數(shù)，即非均勻分布，則攻擊者可推斷出用戶在隱匿區(qū)域的某一范圍內(nèi)出現(xiàn)概率較大，導(dǎo)致隱私保護(hù)水平下降。由此，文獻(xiàn)[53]提出了一種偏移向量的概率分布函數(shù)，使用戶在隱匿區(qū)域內(nèi)分布的概率密度為常數(shù)，從而達(dá)到均勻分布的效果。Andres等[43]借鑒差分隱私的思想，提出通過位置不可分辨性表示用戶的隱私保護(hù)需求，并設(shè)計(jì)了一種滿足該特性的噪音生成機(jī)制。由于拉普拉斯分布(Laplace distribution)能夠滿足位置不可分辨性，方案中將二維拉普拉斯分布轉(zhuǎn)化為極坐標(biāo)形式作為噪聲函數(shù)，其中，夾角滿足均勻分布，半徑滿足伽瑪分布(Gamma distribution)。此外，由于坐標(biāo)精度有限，需將該噪聲函數(shù)產(chǎn)生的結(jié)果離散化，從而得到理想的位置偏移。文獻(xiàn)[43]沒有考慮位置偏移對于服務(wù)質(zhì)量的影響，不能很好地滿足實(shí)用性要求。Shokri等[58]提出基于零和貝葉斯博弈(zero sum Bayesian game)的策略，在最優(yōu)化隱私保護(hù)水平的同時確保服務(wù)質(zhì)量損失小于給定閾值。該策略假設(shè)攻擊者已獲取先驗(yàn)知識，用戶和攻擊者輪流進(jìn)行博弈，從而最優(yōu)化各自利益。其中，用戶在確保服務(wù)質(zhì)量損失小于給定閾值的情況下最大化隱私保護(hù)水平，而攻擊者根據(jù)先驗(yàn)知識和虛假位置力求最小化隱私保護(hù)水平，形成博弈雙方。但該方案也存在不足，當(dāng)攻擊者掌握細(xì)粒度先驗(yàn)知識時，比如在時間維度上，某用戶早晨和晚上有完全不同的習(xí)慣，攻擊者則可在這2個時段使用不同的先驗(yàn)知識來降低隱私保護(hù)水平。由于位置不可分辨性基于差分隱私，因此，位置不可分辨性具有不基于先驗(yàn)知識的特性，可彌補(bǔ)文獻(xiàn)[58]中方案的不足。Bordenabe等[59]結(jié)合文獻(xiàn)[43]和文獻(xiàn)[58]方案的優(yōu)勢，構(gòu)建一種最優(yōu)化服務(wù)質(zhì)量機(jī)制，在滿足位置不可分辨性的前提下，最小化服務(wù)質(zhì)量損失。Xiao等[44]關(guān)注用戶位置的時間相關(guān)性，充分考慮動態(tài)場景下的隱私保護(hù)。如圖13所示，用戶從學(xué)校到咖啡館的過程中，利用位置偏移技術(shù)，向服務(wù)提供商發(fā)送了3次位置信息。雖然3個時刻的位置信息都得到了很好的保護(hù)，但攻擊者仍然可利用道路環(huán)境和用戶運(yùn)動模型，推斷出用戶位于咖啡館。該方案中時間相關(guān)性可用馬爾可夫鏈描述，其馬爾可夫轉(zhuǎn)換矩陣為

5.3 偽造虛假位置

由于位置偏移和模糊技術(shù)降低了位置精確度[60]，因此，返回的服務(wù)數(shù)據(jù)可能不準(zhǔn)確。而偽造虛假位置技術(shù)[28,29,36,61]則不存在該問題，但通信開銷相對較高。

圖12 查詢處理過程示例

圖13 時間相關(guān)性引起的隱私泄露

Kido等[28]通過產(chǎn)生多個虛假位置(dummy)，將用戶真實(shí)位置混入其中，一起發(fā)送給服務(wù)提供商以實(shí)現(xiàn)隱私保護(hù)。服務(wù)提供商由于無法區(qū)分真實(shí)位置和dummy，只能對每個所提交的位置提供所需服務(wù)。該方案中dummy的產(chǎn)生基于隨機(jī)運(yùn)動模型，沒有考慮dummy的選取質(zhì)量問題，而是把重點(diǎn)放在如何降低通信消耗上。應(yīng)當(dāng)如何選取dummy才能接近真實(shí)用戶的運(yùn)動模型是這類技術(shù)一直努力解決的問題。Lu等[29]提出2種偽造虛假位置方案，稱為CirDummy和GridDummy。如圖14所示，CirDummy方案基于包含用戶真實(shí)位置的虛擬圓產(chǎn)生dummy，GirdDummy方案基于包含用戶真實(shí)位置的虛擬方格產(chǎn)生dummy。該方案主要考慮兩方面問題，一方面dummy分布不均勻時，零散的dummy很容易被攻擊者排除掉，故該方案采用均勻產(chǎn)生dummy的方法(圖14(a)中所有的夾角θ都相同，圖14(b)中任意相鄰dummy的間距相同)；另一方面考慮了dummy所形成的隱私保護(hù)區(qū)域應(yīng)當(dāng)超過某個閾值，以防止隱私保護(hù)區(qū)域太小直接泄露用戶位置。這2種方案都沒有考慮背景知識[62,63]，如部分dummy位于湖泊、海洋、高山和沼澤等區(qū)域時，攻擊者可以輕易地排除這部分dummy。Niu等[36]提出DLS方案，以每個位置的查詢概率(在歷史查詢記錄中，所有用戶在該位置上的查詢次數(shù)除以整張地圖總的查詢次數(shù))來表示背景知識，通過位置熵來度量隱私保護(hù)水平。

圖14 偽造虛假位置示例

圖15 虛假位置篩選示例

如圖15所示，用戶隨機(jī)產(chǎn)生9個dummy，并與真實(shí)位置一起發(fā)送給服務(wù)提供商，理論上達(dá)到了10-匿名的效果。然而，若服務(wù)提供商利用背景知識排除掉一部分dummy，則實(shí)際上達(dá)不到10-匿名的效果。因此，該場景中使用位置熵的度量方法衡量隱私保護(hù)水平更為準(zhǔn)確，如圖15中位置1、2、3的查詢概率高于其他7個位置，則這次查詢的位置熵為lb3，而不是lb10。理想情況下，當(dāng)所有dummy的查詢概率與真實(shí)位置相同時，熵值最大，隱私保護(hù)水平最高。為了獲得較大的位置熵，文獻(xiàn)[36]首先選取與真實(shí)位置查詢概率最接近的4k個備選dummy，并隨機(jī)挑選m組，每組包含真實(shí)位置和2k?1個備選dummy，然后通過計(jì)算每組的位置熵，找到熵值最大的一組，最后從熵值最大的組中選出k?1個dummy，選擇的標(biāo)準(zhǔn)是盡可能形成較大的隱匿區(qū)域。在具體實(shí)現(xiàn)過程中，該方案采用了一種探索式的方法：定義輸出集和備選集2個集合，輸出集在初始時只包含真實(shí)位置，備選集包含2k?1個備選dummy。每輪從備選集中選出一個dummy移除，并將其加入到輸出集，在k?1輪后得到輸出結(jié)果。每輪選擇時，計(jì)算備選集中每一個dummy被選中的概率與它的權(quán)重(該dummy與輸出集中所有位置的距離之積)成正比。通過該方法不僅達(dá)到了較高的熵值，還使dummy分布在較大的空間中。Pingley等[61]提出如圖16所示DUMMY-Q方案，通過偽造多個POI的方式保護(hù)查詢隱私。具體地，首先根據(jù)歷史查詢次數(shù)，對空間進(jìn)行四叉樹形式的劃分，保證劃分后的每一個區(qū)域有大致相同的歷史查詢次數(shù)。然后根據(jù)用戶的運(yùn)動模型和當(dāng)前位置預(yù)測出用戶可能經(jīng)過的區(qū)域集合，并根據(jù)規(guī)則建立POI池。最后基于POI池相應(yīng)地偽造請求與真實(shí)請求一起發(fā)送給服務(wù)提供商，使攻擊者難以分辨。Fawaz等[4]提出一種位置隱私保護(hù)框架LP-Guardian，該框架利用偽造虛假位置技術(shù)，在不修改位置服務(wù)APP的前提下，滿足不同類型位置服務(wù)APP的隱私保護(hù)需求。對于用戶正在使用的APP根據(jù)其制定的規(guī)則進(jìn)行處理，結(jié)果分為3種情況：直接發(fā)送、不發(fā)送和隱匿處理后發(fā)送。若需隱匿處理，則根據(jù)APP類型選擇不同的隱匿處理方式，從而滿足不同的隱私保護(hù)需求：對于持續(xù)收集用戶位置的APP(如健康監(jiān)測軟件)，通過偽造某運(yùn)動過程的起點(diǎn)和終點(diǎn)來達(dá)到隱私保護(hù)的目的，同時保持距離和速度與實(shí)際情況相一致；對于需要偶爾提供精確位置的APP，該框架考慮到攻擊者持續(xù)收集用戶信息，并計(jì)算每個用戶的運(yùn)動模型。若某用戶的運(yùn)動模型與所有其他用戶差別較大，則攻擊者可識別該用戶的身份。因此，當(dāng)某用戶的運(yùn)動模型與理論模型偏離較大時，通過發(fā)送虛假位置來矯正該用戶的運(yùn)動模型；對于需要提供城市級別位置的APP和后臺運(yùn)行的APP，只提供用戶所在城市。LP-Guardian權(quán)衡了隱私保護(hù)粒度、APP可用性和服務(wù)質(zhì)量，在實(shí)際應(yīng)用中取得了較好的效果。Niu等[37]提出群組協(xié)作方案中，當(dāng)需要向服務(wù)提供商發(fā)送請求時，可利用偽造虛假位置技術(shù)來提高緩存(cache)命中率。服務(wù)提供商對每一個dummy都會提供位置服務(wù)，因此，將協(xié)作組中沒有緩存記錄的位置作為dummy，可以達(dá)到提高緩存命中率的效果。文獻(xiàn)[37]在保證隱私保護(hù)水平的同時考慮了影響緩存命中率的多個因素：1) 緩存位置的查詢概率，應(yīng)當(dāng)盡量緩存查詢概率高的位置；2) 緩存位置與用戶真實(shí)位置的距離，應(yīng)當(dāng)盡量緩存真實(shí)位置的近鄰位置；3) 緩存位置的新鮮度，應(yīng)當(dāng)盡量緩存接近緩存期限的位置。綜合上述3個因素，可定量計(jì)算每組dummy對緩存做出的貢獻(xiàn)。為了保證隱私保護(hù)水平，該方案首先挑選與真實(shí)位置查詢概率最接近的4k個dummy以確保較大的位置熵，然后從其中隨機(jī)選取2k個作為備選，最后選出k?1個對緩存貢獻(xiàn)最大的dummy。

圖16 DUMMY-Q處理過程示例

5.4 群組協(xié)作

群組協(xié)作技術(shù)[27,30,31,38,64～66]通過用戶自組織的P2P網(wǎng)絡(luò)能夠獲取附近用戶的位置信息。該技術(shù)可分為2類：陌生人之間的協(xié)作和基于信任關(guān)系的協(xié)作。

5.4.1 陌生人之間的協(xié)作

陌生人之間的協(xié)作通常使用藍(lán)牙通信技術(shù)，用戶之間的信息交互發(fā)生在10 m之內(nèi)。

Manweiler等[64]提出陌生人之間的協(xié)作方案：首先用戶在相遇時產(chǎn)生隨機(jī)對稱密鑰，此密鑰作為此次相遇的憑證，并將密鑰的散列值前綴發(fā)送給服務(wù)器。然后當(dāng)用戶需要發(fā)送消息時，用該密鑰對消息加密，并將密鑰的散列值前綴和密文一并發(fā)送給服務(wù)器。最后服務(wù)器通過匹配散列值前綴的方式，找到擁有相同前綴的用戶，將密文發(fā)送給他們。該方案用k-匿名來度量和設(shè)置用戶的隱私保護(hù)水平，如果用戶將密鑰的散列值前綴長度縮短，那么服務(wù)器需要將消息發(fā)送給更多的用戶(k就越大)，隱私保護(hù)水平也就相應(yīng)提高，但系統(tǒng)開銷也隨之增長。為了更好地降低系統(tǒng)開銷，且便于用戶對系統(tǒng)開銷進(jìn)行細(xì)粒度的控制，Niu等[27]提出細(xì)粒度的隱私保護(hù)方案。首先，每個用戶在本地緩沖寄存器中周期性地記錄其歷史位置，當(dāng)與其他用戶相遇時，隨機(jī)分享部分歷史數(shù)據(jù)。為了便于用戶控制通信消耗，用戶設(shè)置一個交換時間比，每隔一段時間開啟位置數(shù)據(jù)交換模塊，工作一定時間后關(guān)閉。接著，用希爾伯特曲線按照查詢次數(shù)分布將地圖劃分為多個單元，查詢概率越高的區(qū)域劃分粒度越細(xì)，每個單元按順序被賦予希爾伯特值，該過程可以離線執(zhí)行。然后將所有單元(cell)劃分為k段，若真實(shí)位置位于某一段的第i個單元，則選出其他段的第i個單元作為備選。最后，對于每一個備選單元，在本地緩沖寄存器中找到與其距離最近的位置，若距離足夠近(在單元內(nèi)部)，則用此位置替換備選位置，否則將備選位置做小范圍的偏移。該方案利用希爾波特曲線降低了空間維度，從而減小了系統(tǒng)開銷。此外，結(jié)合陌生人之間的協(xié)作技術(shù)能夠收集真實(shí)用戶位置信息的特點(diǎn)和偽造虛假位置技術(shù)計(jì)算和通信開銷較小的特點(diǎn)，實(shí)現(xiàn)用戶對系統(tǒng)開銷的細(xì)粒度控制。

5.4.2 基于信任關(guān)系的協(xié)作

基于信任關(guān)系的協(xié)作通常使用藍(lán)牙或ad hoc網(wǎng)絡(luò)建立協(xié)作組，協(xié)作組成員之間相互信任，用以分享位置或其他信息。

Chow等[31]提出P2Pcloaking方案，可同時滿足k-匿名和隱匿區(qū)域要求。如圖17所示，用戶向距離為1的鄰近組員廣播請求，每個鄰近組員返回其ID和位置信息，若返回結(jié)果少于k個，則將距離設(shè)為2重新發(fā)送請求。當(dāng)組員發(fā)現(xiàn)請求中的距離大于1時，不僅返回自身ID和位置信息，還需向其相鄰組員廣播請求，該請求中的距離是其收到請求中的距離減1。當(dāng)距離等于1時，組員只需返回自身ID和位置信息。用戶通過不斷增加距離，使返回信息的組員數(shù)量至少為k?1。例如，圖17(a)中m8為需要位置服務(wù)的用戶，設(shè)k等于5，先向距離為1的鄰近組員廣播請求，發(fā)現(xiàn)組員m5、m7和m9。由于沒有達(dá)到5-匿名的要求，因此將距離設(shè)為2重新發(fā)送請求，m5、m7和m9收到請求后，發(fā)現(xiàn)距離大于1，則返回自身ID和位置信息的同時向其相鄰組員廣播請求，請求中的距離等于1。如圖17(b)所示，組員m4、m6、m10和m15收到請求，由于距離等于1，故只返回自身ID和位置信息。此時m8收到了7個組員的應(yīng)答，滿足5-匿名要求。接著用戶從這些返回信息的組員中，挑選k?1個最近組員形成匿名集。如圖17(c)所示，用戶選擇m4、m5、m7和m9形成匿名集。最后若匿名集形成的隱匿區(qū)域小于用戶的最小隱匿區(qū)域要求，則向外擴(kuò)張使其符合要求，如圖17(d)所示，擴(kuò)大隱匿區(qū)域的邊長。Niu等[30]指出文獻(xiàn)[31]存在的問題：1) 由于ad hoc網(wǎng)絡(luò)是一種短距離通信方式，且具有廣播特性，因此，該方案挑選的k?1個組員都在真實(shí)用戶周圍，真實(shí)用戶位于隱匿區(qū)域中心的概率極高；2) 由于該方案采用逐跳挑選組員的方式，相對遠(yuǎn)離用戶的組員很難被選中，因此方案所形成的隱匿區(qū)域較小。雖然Chow等在文獻(xiàn)[12]中對算法進(jìn)行了改進(jìn)，首先調(diào)整了隱匿區(qū)域的中心，以用戶位置和任意相鄰組員的中點(diǎn)作為中心，其次根據(jù)用戶要求適當(dāng)擴(kuò)大隱匿區(qū)域，但通過實(shí)驗(yàn)證明該修改方案仍然不能抵御文獻(xiàn)[30]中提出的基于方差的攻擊。針對上述問題，文獻(xiàn)[30]中提出了如下解決方案：首先Alice向距離一跳的鄰近組員廣播請求，收到應(yīng)答后隨機(jī)選擇f(1≤f≤k)個組員，并將這些組員和用戶一并作為備選集。接著，從備選集中隨機(jī)選出一個組員Bob，將備選集發(fā)送給Bob，由Bob再次廣播請求，收到應(yīng)答后同樣隨機(jī)選擇f個組員，并將這些組員加入到備選集中。重復(fù)上一步操作，直到備選集中組員的數(shù)量大于或等于k。最后一個廣播請求的組員Frank將備選集發(fā)送給Alice，由Alice構(gòu)建包含備選集中所有組員的隱匿區(qū)域。該方案中，f是一個重要參數(shù)，首先對于Bob而言，Alice的真實(shí)位置隱匿在f個位置中。其次，f可以用來調(diào)節(jié)隱私保護(hù)水平和系統(tǒng)開銷。若f取最大值k，則該方案與文獻(xiàn)[27]相同，可能只需一跳就能完成，系統(tǒng)開銷很小，但無法抵御相關(guān)攻擊。若f取最小值1，則可能需要多跳完成該算法，這樣便可形成較大的隱匿區(qū)域，但系統(tǒng)開銷較大。目前，大量基于群組協(xié)作的位置隱私保護(hù)方案提出了緩存的思想[37,38,65]。用戶將服務(wù)信息緩存一段時間，并向其他需要該信息的組員轉(zhuǎn)發(fā)，從而減少用戶向服務(wù)提供商提出請求的次數(shù)，以降低用戶隱私泄露的可能性。Shokri等[65]提出MobiCrowd方案，此方案對于服務(wù)器而言，需要做的改進(jìn)是對每條服務(wù)信息進(jìn)行數(shù)字簽名，用戶則可使用服務(wù)提供商的公鑰來驗(yàn)證位置服務(wù)信息，以防止篡改位置服務(wù)信息或傳播過期位置服務(wù)信息的行為。每個用戶設(shè)備都維持一個緩沖寄存器，用以存儲其獲得的其他組員或者服務(wù)提供商發(fā)送的服務(wù)信息。每條服務(wù)信息中包含到期時間，在過期前數(shù)據(jù)一直存儲在緩沖寄存器中。當(dāng)用戶在緩沖寄存器中沒有找到滿足服務(wù)請求的信息時，服務(wù)請求將通過ad hoc網(wǎng)絡(luò)發(fā)送給其他組員，若某些組員緩存了該服務(wù)請求所對應(yīng)的服務(wù)信息，則向該用戶發(fā)送應(yīng)答。一般會設(shè)置一個服務(wù)周期以降低每個用戶的通信開銷。當(dāng)用戶沒有收到任何應(yīng)答時，才向服務(wù)提供商提出服務(wù)請求。MobiCrowd方案沒有考慮當(dāng)緩存數(shù)據(jù)無法滿足用戶需求時如何保護(hù)隱私。Niu等[38]提出EPclock方案以解決上述問題。當(dāng)用戶需要位置服務(wù)時，先執(zhí)行“本地搜索算法”，通過ad hoc網(wǎng)絡(luò)從其他組員獲得服務(wù)數(shù)據(jù)，若服務(wù)覆蓋率超過閾值，則用戶需求得到滿足。否則，執(zhí)行空間隱匿算法，逐跳將服務(wù)請求發(fā)送給某個組員，即虛擬請求者。虛擬請求者將其用戶名加入服務(wù)請求后，繼續(xù)轉(zhuǎn)發(fā)服務(wù)請求給另一個組員，即發(fā)送者，由發(fā)送者向服務(wù)提供商發(fā)送該請求，請求范圍覆蓋用戶所需區(qū)域，并將應(yīng)答返回給用戶。由于服務(wù)請求中，用戶ID來源于虛擬請求者，POI來源于用戶，位置來源于發(fā)送者，因此攻擊者難以獲得任何參與者的隱私信息。

圖17 P2P空間隱匿算法示例

6 現(xiàn)有技術(shù)對比分析

6.1 4類技術(shù)優(yōu)缺點(diǎn)分析

本文綜述了位置服務(wù)中2種隱私保護(hù)系統(tǒng)構(gòu)架下基于泛化和模糊的4類LBS隱私保護(hù)技術(shù)。

依賴可信第三方系統(tǒng)構(gòu)架中，現(xiàn)有方案一般采用空間隱匿技術(shù)將真實(shí)位置隱藏在包含其他k?1個真實(shí)用戶的隱匿區(qū)域中。該技術(shù)既能保護(hù)位置隱私，又能保護(hù)查詢隱私，一般使用k-匿名和位置熵作為隱私保護(hù)度量標(biāo)準(zhǔn)。其優(yōu)勢在于：1) 能夠同時滿足用戶的k-匿名和隱匿區(qū)域要求；2) TTP能夠獲取海量用戶的位置信息；3) TTP能夠輔助用戶過濾服務(wù)數(shù)據(jù)，降低用戶端的計(jì)算和存儲開銷。缺點(diǎn)在于：1) 在人口稀少地區(qū)，該技術(shù)容易導(dǎo)致隱匿區(qū)域過大或服務(wù)延遲過高；2) 隱匿區(qū)域較大時，服務(wù)器端需消耗大量計(jì)算資源處理查詢請求；3) 系統(tǒng)負(fù)載的增加和單點(diǎn)失效的發(fā)生，使TTP成為系統(tǒng)瓶頸。

不依賴可信第三方的系統(tǒng)構(gòu)架中，現(xiàn)有方案主要集中于3類技術(shù)：位置偏移和模糊技術(shù)、偽造虛假位置技術(shù)和群組協(xié)作技術(shù)。

位置偏移和模糊技術(shù)在真實(shí)位置中加入噪聲以降低位置精確度。該技術(shù)主要用于保護(hù)位置隱私，使用相關(guān)性和位置不可分辨性作為隱私保護(hù)度量標(biāo)準(zhǔn)。其優(yōu)勢在于：1) 計(jì)算和存儲開銷較?。?)通過調(diào)整噪聲函數(shù)的相關(guān)參數(shù)，可達(dá)到較高的隱私保護(hù)水平；3) 根據(jù)不同應(yīng)用需求，用戶可調(diào)節(jié)位置精確度損失。其缺點(diǎn)在于：1) 降低了位置精確度，可能難以滿足用戶服務(wù)需求；2) 在人口稀少地區(qū)，難以達(dá)到應(yīng)有的隱私保護(hù)水平；3) 該技術(shù)主要針對位置隱私，不能保護(hù)查詢隱私。

偽造虛假位置技術(shù)將真實(shí)位置和多個虛假位置一并發(fā)送給服務(wù)提供商。該技術(shù)既能保護(hù)位置隱私，又能保護(hù)查詢隱私，一般使用k-匿名和位置熵作為隱私保護(hù)度量標(biāo)準(zhǔn)。其優(yōu)勢在于：1) 不受人口密度限制，無論用戶處于何位置都能滿足用戶的隱私保護(hù)要求；2) 由于向服務(wù)提供商發(fā)送的信息中包含真實(shí)位置，因此返回的服務(wù)數(shù)據(jù)較為精確；3) 便于用戶隨時調(diào)整隱私保護(hù)策略。其缺點(diǎn)在于：1) LPPM的實(shí)現(xiàn)受移動設(shè)備性能的限制；2) 由于無法收集和利用真實(shí)的用戶位置，攻擊者可以通過各種背景知識排除虛假位置；3) 虛假位置會帶來額外的通信消耗。

群組協(xié)作技術(shù)通過組員間分享位置信息，相互協(xié)作完成隱私保護(hù)工作。該技術(shù)既能保護(hù)位置隱私，又能保護(hù)查詢隱私，一般使用k-匿名和位置熵作為隱私保護(hù)度量標(biāo)準(zhǔn)。其優(yōu)勢在于：1) 可獲取周圍用戶的真實(shí)位置，能夠抵御基于背景知識的攻擊；2) 通過緩存和共享服務(wù)信息減少查詢次數(shù)，提高整個群組的隱私保護(hù)水平；3) 可結(jié)合其他幾種技術(shù)提高隱私保護(hù)水平或者緩存命中率。其缺點(diǎn)在于：1) ad hoc網(wǎng)絡(luò)通信距離較短，無法形成較大隱匿區(qū)域；2) 若用戶處于人口稀少區(qū)域，該方法可行性較差；3) 組員間分享和緩存相關(guān)信息增加了額外的通信和存儲開銷。

6.2 現(xiàn)有方案存在問題

通過分析現(xiàn)有工作，不難看出LBS隱私保護(hù)方案有以下幾方面問題亟需解決。

1) 如表1所示，現(xiàn)有方案主要針對位置信息和用戶ID這2個目標(biāo)，將POI和時間信息作為保護(hù)目標(biāo)的相對較少，尤其是對時間信息的保護(hù)尚未得到足夠重視。對于掌握細(xì)粒度背景知識的攻擊者，可利用多個位置的時間相關(guān)性來推測用戶真實(shí)位置，對于時間信息的保護(hù)能夠抵抗此類攻擊。所以，在很多應(yīng)用場景中，單一的隱私保護(hù)目標(biāo)不能達(dá)到很好的隱私保護(hù)效果，只有綜合考慮多個隱私保護(hù)目標(biāo)才能設(shè)計(jì)出更有效的方案。

2) 現(xiàn)有方案大都沒有定量權(quán)衡隱私保護(hù)水平和位置精確度。為提高隱私保護(hù)水平，很多技術(shù)犧牲了一定的位置精確度，如使用隱匿區(qū)域代替真實(shí)位置、在真實(shí)位置中加入噪聲等。然而，若位置精確度太低，會導(dǎo)致服務(wù)數(shù)據(jù)不能滿足用戶需求，影響可用性，隱私保護(hù)失去意義。此外，不同應(yīng)用對位置精確度的要求各異，如對于POI搜索應(yīng)用，真實(shí)位置和虛假位置的距離應(yīng)有嚴(yán)格限制；對于天氣預(yù)報應(yīng)用，真實(shí)位置和虛假位置的距離要求較低。因此，設(shè)計(jì)方案時應(yīng)對隱私保護(hù)水平和位置精確度進(jìn)行均衡分析。

3) 如表2所示，現(xiàn)有研究大多數(shù)都是從提高隱私保護(hù)水平角度出發(fā)，很少考慮系統(tǒng)開銷問題。然而，由于用戶設(shè)備端的系統(tǒng)資源有限，精度損失、通信開銷、存儲開銷和計(jì)算開銷等都會影響用戶體驗(yàn)。如大量計(jì)算開銷使移動設(shè)備的處理速度變慢，大量通信開銷使用戶額外費(fèi)用增加，大量電量開銷影響移動設(shè)備在戶外的使用，最終阻礙位置服務(wù)的發(fā)展。因此，設(shè)計(jì)方案時應(yīng)當(dāng)充分考慮降低系統(tǒng)開銷。

4) 現(xiàn)有研究大多針對如何設(shè)計(jì)和改進(jìn)隱私保護(hù)方案，專門針對隱私保護(hù)度量指標(biāo)的研究尚不完善，由此導(dǎo)致對于不同隱私保護(hù)方案的評判沒有一個統(tǒng)一的標(biāo)準(zhǔn)。因此，應(yīng)當(dāng)研究如何制定統(tǒng)一的隱私度量指標(biāo)使各類方案都能得到合理的評估。

表1 現(xiàn)有位置隱私保護(hù)技術(shù)的目標(biāo)

表2 現(xiàn)有位置隱私保護(hù)技術(shù)的系統(tǒng)開銷

7 結(jié)束語

LBS已成為人們?nèi)粘Ｉ钪胁豢苫蛉钡囊环N信息服務(wù)方式，因此，如何在使用LBS過程中有效地防止隱私泄露成為隱私保護(hù)領(lǐng)域的研究熱點(diǎn)。本文全面介紹了LBS隱私保護(hù)背景知識，討論了現(xiàn)有攻擊者模型和隱私度量指標(biāo)，并深入分析和對比了4類基于泛化和模糊的隱私保護(hù)技術(shù)，指出了現(xiàn)有方案的優(yōu)點(diǎn)和不足。未來面對云計(jì)算、大數(shù)據(jù)等新技術(shù)帶來的機(jī)遇，現(xiàn)有的隱私保護(hù)技術(shù)面臨著各種新的挑戰(zhàn)，研究者適時提出隱私計(jì)算理論體系[67]。在未來位置隱私保護(hù)方面，亟待從以下幾方面為用戶隱私數(shù)據(jù)全生命周期保護(hù)提供理論與技術(shù)支撐。

1) 擴(kuò)展背景知識，建立更為可靠的LBS隱私保護(hù)機(jī)制。通過挖掘和利用背景知識，攻擊者可發(fā)動更為有效的攻擊?，F(xiàn)有方案缺乏對時間、用戶運(yùn)動和行為模型等背景知識的充分考慮，而攻擊者可能會收集此類信息。因此，對背景知識的擴(kuò)展研究，并將其應(yīng)用到具體方案中是一個重要的研究方向。

2) 設(shè)計(jì)合適的LBS隱私保護(hù)度量標(biāo)準(zhǔn)。k-匿名和位置熵是最為廣泛的LBS隱私保護(hù)度量標(biāo)準(zhǔn)，但很難準(zhǔn)確表達(dá)用戶多樣化的隱私保護(hù)要求。差分隱私作為一種嚴(yán)格的、可證明的度量標(biāo)準(zhǔn)，在數(shù)據(jù)庫隱私保護(hù)方向已經(jīng)取得了很多成果，如拉普拉斯機(jī)制和指數(shù)機(jī)制。將差分隱私和相應(yīng)隱私保護(hù)機(jī)制引入到位置隱私保護(hù)領(lǐng)域是一個重要的研究方向。

3) 平衡隱私保護(hù)和服務(wù)質(zhì)量。很多方案提高隱私保護(hù)水平需以犧牲服務(wù)質(zhì)量為代價。博弈論的方法能夠較好地解決雙方或多方的利益均衡問題，如零和貝葉斯博弈、納什均衡等。因此，將博弈論的方法引入到LBS隱私保護(hù)技術(shù)中是一個重要的研究方向。

[1]王璐,孟小峰.位置大數(shù)據(jù)隱私保護(hù)研究綜述[J].軟件學(xué)報,2014,25(4):693-712.WANG L,MENG X F.Location privacy preservation in big data era:a survey[J].Journal of Software,2014,25(4):693-712.

[2]HOH B,GRUTESER M.Protecting location privacy through path confusion[C]//1st IEEE International Conference on Security and Privacy for Emerging Areas in Communications Networks (Secure-Comm’05).Athens,Greece,2005:194-205.

[3]KRUMM J.Inference attacks on location tracks[C]//5th Springer International Conference on Pervasive Computing(PERVASIVE’07).Toronto,Canada,2007:127-143.

[4]FAWAZ K,SHIN K G.Location privacy protection for smartphone users[C]//21st ACM Conference on Computer and Communications Security(CCS’14).Scottsdale,United States,2014:239-250.

[5]SHIN K G,JU X,CHEN Z,et al.Privacy protection for users of location-based services[J].IEEE Wireless Communications,2012,19(1):30-39.

[6]ZHANG Y,TAN C C,XU F,et al.VProof:lightweight privacy-preserving vehicle location proofs[J].IEEE Transactions on Vehicular Technology,2015,64(1):378-385.

[7]WANG X,PANDE A,ZHU J,et al.STAMP:enabling privacy-preserving location proofs for mobile users[J].IEEE Transactions on Networking,2016,PP(99):1-14.

[8]DICKINSON A,LOCHRIE M,EGGLESTONE P.UKKO:enriching persuasive location based games with environmental sensor data[C]// 2th ACM Annual Symposium on Computer-Human Interaction in Play(CHI Play’15).London,United Kingdom,2015:493-498.

[9]周傲英,楊彬,金澈清,等.基于位置的服務(wù):架構(gòu)與進(jìn)展[J].計(jì)算機(jī)學(xué)報,2011,34(7):1155-1171.ZHOU A Y,YANG B,JIN C Q,et al.Location-based services:architecture and progress[J].Journal of Software,2011,34(7):1155-1171.

[10]WERNKE M,SKVORTSOV P,DüRR F,et al.A classification of location privacy attacks and approaches[J].Personal and Ubiquitous Computing,2014,18(1):163-175.

[11]MACHANAVAJJHALA A,KIFER D,GEHRKE J,et al.L-diversity:privacy beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):3.

[12]CHOW C Y,MOKBEL M F,LIU X.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica,2011,15(2):351-380.

[13]MOKBEL M F.Privacy in location-based services:state-of the-art and research directions[C]//8th IEEE International Conference on Mobile Data Management (MDM’07).Mannheim,Germany,2007:228-228.

[14]THEODORAKOPOULOS G.The same-origin attack against location privacy[C]//14th ACM Workshop on Privacy in the Electronic Soci-ety(WPES’15).Denver,United States,2015:49-53.

[15]SHOKRI R,THEODORAKOPOULOS G,BOUDEC J Y LE,et al.Quantifying location privacy[C]//32nd IEEE Symposium on Security and Privacy(S&P’11).Berkeley,United States,2011:247-262.

[16]LEE B,OH J,YU H,et al.Protecting location privacy using location semantics[C]//17th ACM international conference on Knowledge discovery and data mining(SIGKDD’11).San Diego,United States,2011:1289-1297.

[17]PAN X,XU J,MENG X.Protecting location privacy against location-dependent attacks in mobile services[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(8):1506-1519.

[18]劉海,李興華,王二蒙,等.連續(xù)服務(wù)請求下基于假位置的用戶隱私增強(qiáng)方法[J].通信學(xué)報,2016,37(7):140-150.LIU H,LI X H,WANG E M,et al.Privacy enhancing method for dummy based privacy protection with continuous location-based service queries[J].Journal on Communications,2016,37(7):140-150.

[19]潘曉,郝興,孟小峰.基于位置服務(wù)中的連續(xù)查詢隱私保護(hù)研究[J].計(jì)算機(jī)研究與發(fā)展,2010,47(1):121-129.PAN X,HAO X,MENG X F.Primacy prospering towards continuous query in location-based services[J].Journal of Computer Research and Development,2010,47(1):121-129.

[20]GRUTESER M,GRUNWALD D.Anonymous usage of location-based services through spatial and temporal cloaking[C]//1st ACM International Conference on Mobile Systems,Applications,and Services(MobiSys’03).San Francisco,United States,2003:31-42.

[21]SWEENEY L.k-anonymity:a model for protecting privacy[J].International Journal on Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5):557-570.

[22]CHOW C Y,MOKBEL M F,AREF W G.Casper*:query processing for location services without compromising privacy[J].ACM Transactions on Database Systems,2009,34(4):1-48.

[23]XU T,CAI Y.Feeling-based location privacy protection for location-based services[C]//16th ACM Conference on Computer and Communications Security(CCS’09).Chicago,United States,2009:348-357.

[24]GEDIK B,LIU L.Protecting location privacy with personalized k-anonymity:architecture and algorithms[J].IEEE Transactions on Mobile Computing,2008,7(1):1-18.

[25]GEDIK B,LIU L.Protecting location privacy with personalized k-anonymity:architecture and algorithms[J].IEEE Transactions on Mobile Computing,2008,7(1):1-18.

[26]倪巍偉,馬中希,陳蕭.面向路網(wǎng)隱私保護(hù)連續(xù)近鄰查詢的安全區(qū)域構(gòu)建[J].計(jì)算機(jī)學(xué)報,2016,39(3):628-642.NI W W,MA Z X,CHEN X.Safe region scheme for privacy-preserving continuous recent neighbor query on road networks[J].Journal of Computers,2016,39(3):628-642.

[27]NIU B,LI Q H,ZHU X Y,et al.A fine-grained spatial cloaking scheme for privacy-aware users in location-based services[C]//23rd IEEE International Conference on Computer Communication and Networks (ICCCN’14).Shanghai,China,2014:1-8.

[28]KIDO H,YANGISAWA Y,SATOH T.An anonymous communication technique using dummies for location-based services[C]//2nd IEEE International Conference on Pervasive Services(ICPS'05).Santorini,Greece,2005:88-97.

[29]LU H,JENSEN C S,YIU M L.Pad:privacy-area aware,dummy-based location privacy in mobile services[C]//7th ACM International Workshop on Data Engineering for Wireless and Mobile Access( MobiDE’08).Vancouver,Canada,2008:16-23.

[30]NIU B,ZHU X Y,LI Q H,et al.A novel attack to spatial cloaking schemes in location-based services[J].Future Generation Computer Systems,2015,49(1):125-132.

[31]CHOW C Y,MOKBEL M F,LIU X.A peer-to-peer spatial cloaking algorithm for anonymous location-based services[C]//14th ACM International Symposium on Advances in Geographic information Systems(ACM-GIS’06).Arlington,USA,2006:171-178.

[32]CICEK A E,NERGIZ M E,SAYGIN Y.Ensuring location diversity in privacy-preserving spatio-temporal data publishing[J].The VLDB Journal,2014,23(4):609-625.

[33]ZHANG X,XIA Y,BAE H Y.A novel location privacy preservation method for moving object[J].International Journal of Security and Its Applications,2015,9(2):1-12.

[34]ZHANG C,HUANG Y.Cloaking locations for anonymous location based services:a hybrid approach[J].GeoInformatica,2009,13(2):159-182.

[35]BERESFORD A,STAJANO F.Location privacy in pervasive computing[J].IEEE Pervasive Computing,2003,2(1):46-55.

[36]NIU B,LI Q H,ZHU X Y,et al.Achieving k-anonymity in privacy-aware location-based services[C]//33th IEEE International Conference on Computer Communications(INFOCOM’14).Toronto,Canada,2014:754-762.

[37]NIU B,LI Q H,ZHU X Y,et al.Enhancing privacy through caching in location-based services[C]//34th IEEE International Conference on Computer Communications(INFOCOM’15).Hong Kong,China,2015:1017-1025.

[38]NIU B,ZHU X Y,LI W H,et al.EPcloak:an efficient and privacy-preserving spatial cloaking scheme for LBSs[C]//11th IEEE International Conference on Mobile Ad Hoc and Sensor Systems(MASS’14).Philadelphia,United States,2014:398-406.

[39] PALANISAMY B,LIU L.Attack-resilient mix-zones over road networks:architecture and algorithms[J].IEEE Transactions on Mobile Computing,2015,14(3):495-508.

[40]彭長根,丁紅發(fā),朱義杰,等.隱私保護(hù)的信息熵模型及其度量方法[J].軟件學(xué)報,2016,27(8):1891-1903.PENG C G,DING H F,ZHU Y J,et al.Information entropy models and privacy metrics methods for privacy protection[J].Journal of Software,2016,27(8):1891-1903.

[41]SHOKRI R,FREUDIGER J,JADLIWALA M,et al.A distortion-based metric for location privacy[C]//8th ACM Workshop on Privacy in the Electronic Society(WPES’09).Chicago,United States,2009:21-30.

[42]DWORK C,LEI J.Differential privacy and robust statistics[C]//41st Annual ACM Symposium on Theory of Computing(STOC’09).Bethesda,United States,2009:371-380.

[43]ANDRES M E,BORDENABE N E,CHATZIKOKOLAKIS K,et al.Geo-indistinguishability:differential privacy for location-based systems[C]//20th ACM Conference on Computer and Communications Security(CCS’13).Berlin,Germany,2013:901-914.

[44]XIAO Y,XIONG L.Protecting locations with differential privacy under temporal correlations[C]//22nd ACM Conference on Computer and Communications Security(CCS’15).Denver,United States,2015:1298-1309.

[45]IETF.Geographic location/privacy (geopriv) [EB/OL].http://datatracker.ietf.org/wg/geopriv/charter/

[46]World Wide Web Consortium(W3C).Platform for privacy preferences(P3P) project.[EB/OL].http://www.w3.org/P3P

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

[48]GHINITA G,KALNIS P,KHOSHGOZARAN A,et al.Private queries in location based services:anonymizers are not necessary[C]//27th ACM Conference on Management of Data(SIGMOD’08).Vancouver,Canada,2008:121-132.

[49]YI X,PAULET R,BERTINO E,et al.Practical approximate k nearest neighbor queries with location and query privacy[J].IEEE Transactions on Knowledge and Data Engineering,2016,PP(99):1-14.

[50]KALNIS P,GHINITA G,MOURATIDIS K,et al.Preventing location-based identity inference in anonymous spatial queries[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(12):1719-1733.

[51]NGO H,KIM J.Location privacy via differential private perturbation of cloaking area[C]//28th IEEE Computer Security Foundations Symposium(CSF’15).Verona,Italy,2015:63-74.

[52]YIU M L,JENSEN C S,M?LLER J,et al.Design and analysis of a ranking approach to private location-based services[J].ACM Transactions on Database Systems,2011,36(2):1-42.

[53]PERAZZO P,DINI G.A uniformity-based approach to location privacy[J].Computer Communications,2015,64(1):21-32.

[54]ARDAGNA C A,CREMONINI M,DE CAPITANI DI VIMERCATI S,et al.An obfuscation-based approach for protecting location privacy[J].IEEE Transactions on Dependable and Secure Computing,2011,8(1):13-27.

[55]DüRR F,SKVORTSOV P,ROTHERMEL K.Position sharing for location privacy in non-trusted systems[C]//9th IEEE International Conference on Pervasive Computing and Communications(PerCom’11).Seattle,United States,2011:189-196.

[56]PINGLEY A,YU W,ZHANG N,et al.Cap:a context-aware privacy protection system for location-based services[C]//29th IEEE International Conference on Distributed Computing Systems(ICDCS’09).Montreal,Canada,2009:49-57.

[57]周長利,馬春光,楊松濤.基于敏感位置多樣性的 LBS 位置隱私保護(hù)方法研究[J].通信學(xué)報,2015,36(4):14-25.ZHOU C L,MA C G,YANG S T.Research of LBS privacy preserving based on sensitive location diversity[J].Journal on Communications,2015,36(4):14-25.

[58]SHOKRI R,THEODORAKOPOULOS G,TRONCOSO C,et al.Protecting location privacy:optimal strategy against localization attacks[C]//19th ACM Conference on Computer and Communications Security(CCS’12).Raleigh,United States,2012:617-627.

[59]BORDENABE N E,CHATZIKOKOLAKIS K,PALAMIDESSI C.Optimal geo-indistinguishable mechanisms for location privacy[C]// 21st ACM Conference on Computer and Communications Security(CCS’14).Scottsdale,United States,2014:251-262.

[60]倪巍偉,陳蕭,馬中希.支持偏好調(diào)控的路網(wǎng)隱私保護(hù)k近鄰查詢方法[J].計(jì)算機(jī)學(xué)報,2015,38(4):884-896.NI W W,CHENG X,MA Z X.Location privacy preserving k-nearest neighbor query method on road network in presence of user’s preference[J].Chinese Journal of Computers,2015,38(4):884-896.

[61]PINGLEY A,ZHANG N,FU X,et al.Protection of query privacy for continuous location based services[C]//30th IEEE International Conference on Computer Communications (INFOCOM’11).Shanghai,China,2011:1710-1718.

[62]MA C Y T,YAU D K Y,YIP N K,et al.Privacy vulnerability of published anonymous mobility traces[J].IEEE Transactions on Networking,2013,21(3):720-733.

[63]LIU X,LIU K,GUO L,et al.A game-theoretic approach for achieving k-anonymity in location based services[C]//32nd IEEE International Conference on Computer Communications(INFOCOM’13).Turin,Italy,2013:2985-2993.

[64]MANWEILER J,SCUDELLARI R,COX L P.Smile:encounter-based trust for mobile social services[C]//16th ACM Conference on Computer and Communications Security(CCS’09).Chicago,United States,2009:246-255.

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

[66]黃毅,霍崢,孟小峰.CoPrivacy:一種用戶協(xié)作無匿名區(qū)域的位置隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報,2011,34(10):1976-1985.HUANG Y,HUO Z,MENG X F.CoPrivacy:a collaborative cocation privacy-preserving method without clocking region[J].Chinese Journal of Computers,2011,34(10):1976-1985.

[67]李鳳華,李暉,賈焰,等.隱私計(jì)算研究范疇及發(fā)展趨勢[J].通信學(xué)報,2016,37(4):1-11.LI F H,LI H,JIA Y,et al.Privacy computing:concept,connotation and its research trend[J].Journal on Communications,2016,37(4):1-11.

萬盛（1987-），男，江蘇南通人，西安電子科技大學(xué)博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)安全與隱私保護(hù)。

李鳳華（1966-），男，湖北浠水人，博士，中國科學(xué)院信息工程研究所副總工程師、研究員、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與系統(tǒng)安全、隱私計(jì)算、可信計(jì)算。

牛犇（1984-），男，陜西西安人，博士，中國科學(xué)院信息工程研究所助理研究員，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、隱私計(jì)算。

孫哲（1987-），男，安徽安慶人，中國科學(xué)院信息工程研究所博士生，主要研究方向?yàn)樾畔踩?、隱私保護(hù)。

李暉（1968-），男，河南靈寶人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、無線網(wǎng)絡(luò)安全、云計(jì)算安全、信息論與編碼理論。

Research progress on location privacy-preserving techniques

WAN Sheng1,LI Feng-hua1,2,NIU Ben2,SUN Zhe2,LI Hui1
(1.State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China;2.State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100195,China)

While providing plenty of convenience for users in daily life,the increasingly popular location-based service(LBS) posed a serious threat to users’ privacy.The research about privacy-preserving techniques for LBS is becoming a hot spot,and there are a large number of research results.First,background information of privacy protection for LBS was introduced,including application scenarios of LBS,the LBS framework,objects of privacy protection and system architectures of privacy protection.Second,adversary models and metrics for privacy protection in LBS was discussed.Third,four types of privacy-preserving techniques based on generalization and obfuscation for LBS were analyzed and summarized thoroughly.Finally,the potential research directions for privacy-preserving techniques for LBS in the future were shown.

location-based service,privacy protection,location privacy,privacy metrics,adversary model

s:The National Natural Science Foundation of China—Guangdong Provincial People’s Government of the Joint Natural Science Fund Projects (No.U1401251),The National High Technology Research and Development Program of China (863 Program)(No.2015AA016007),The National Natural Science Youth Science Foundation of China (No.61502489),The National Science and Technology Major Project of China (No.2015ZX01029101)

TN929

A

10.11959/j.issn.1000-436x.2016279

2016-08-12；

2016-10-10

牛犇，niuben@iie.ac.cn

—廣東聯(lián)合基金資助項(xiàng)目(No.U1401251)；國家高技術(shù)研究發(fā)展計(jì)劃（“863”計(jì)劃）基金資助項(xiàng)目(No.2015AA016007)；國家自然科學(xué)基金—青年科學(xué)基金資助項(xiàng)目(No.61502489)；國家“核高基”科技重大專項(xiàng)基金資助項(xiàng)目（No.2015ZX01029101）