位置隱私保護技術研究進展

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

(1.西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071；2.中國科學院信息工程研究所信息安全國家重點實驗室，北京 100195)

位置隱私保護技術研究進展

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

(1.西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071；2.中國科學院信息工程研究所信息安全國家重點實驗室，北京 100195)

日趨流行的基于位置服務(LBS,location-based service)在為人們日常生活帶來便利的同時也嚴重威脅到用戶隱私。位置隱私保護技術逐漸成為研究熱點，并涌現出大批研究成果。首先介紹位置隱私保護背景知識，包括位置服務應用場景、位置服務體系框架、隱私保護目標和系統構架；接著討論LBS中的攻擊者模型和隱私保護度量指標；然后對4種基于泛化和模糊的LBS隱私保護技術進行深入分析和總結；最后給出了未來LBS隱私保護技術潛在的研究方向。

位置服務；隱私保護；位置隱私；隱私度量；攻擊者模型

1 引言

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

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

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

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

2 LBS隱私保護背景知識

2.1 位置服務應用場景

目前，位置服務在人們的日常生活中已經得到了廣泛的應用，本文關注常用的5類應用場景：基于位置的POI檢索服務、基于位置的精確導航服務、基于位置的社交網絡服務、基于位置的運動檢測服務和基于位置的廣告推送服務。

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

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

2) 基于位置的精確導航服務

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

3) 基于位置的社交網絡服務

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

4) 基于位置的運動檢測服務

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

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

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

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

2.2 位置服務體系框架

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

圖1 位置服務體系框架

2.3 隱私保護目標

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

1) 用戶ID

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

2) 位置信息

位置信息指用戶所處的位置坐標，通常不同應用對位置信息有不同精確度需求。例如導航應用需要用戶相對精確的位置，而天氣預報應用只需要用戶所在的城市即可。

3) 時間信息

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

4) POI

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

2.4 隱私保護系統構架

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

圖2 依賴可信第三方的系統構架

圖3 不依賴可信第三方的系統構架

3 攻擊者模型

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

3.1 無背景知識模型

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

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

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

圖4 區域中心攻擊

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

圖5 位置分布式攻擊

3.2 背景知識模型

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

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

圖6 同源攻擊

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

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

圖7 位置相似性攻擊

3.3 多點攻擊模型

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

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

圖8 位置依賴攻擊

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

圖9 連續位置攻擊

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

4 隱私保護度量指標

k-匿名和位置熵是目前被廣泛使用的隱私保護度量指標，除此以外，一些學者結合各類應用場景提出了很多度量指標。

4.1 k-匿名

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

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

4.2 位置熵

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

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

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

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

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

4.3 其他度量方法

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

4.3.1 扭曲度

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

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

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

用戶最關心的是攻擊者能否推斷出正確位置，以及攻擊者推斷結果與真實位置有多大差距，因此，正確性是度量隱私保護水平最重要的指標。

4.3.2 差分隱私

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

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

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

5 LBS隱私保護技術

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

基于策略的方案[45,46]主要通過制定隱私保護規則、標準和詳細規范來約束服務提供商，禁止位置信息被不正當的使用。雖然此類方案能夠同時保護位置隱私和查詢隱私，但缺陷明顯：1) 服務提供商能否有效執行相關策略往往依賴于法律制度和社會輿論的壓力；2) 沒有度量隱私保護水平的標準。

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

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

5.1 空間隱匿

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

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

圖10 希爾伯特曲線變換

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

圖11 混淆區

5.2 位置偏移和模糊

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

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

5.3 偽造虛假位置

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

圖12 查詢處理過程示例

圖13 時間相關性引起的隱私泄露

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

圖14 偽造虛假位置示例

圖15 虛假位置篩選示例

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

圖16 DUMMY-Q處理過程示例

5.4 群組協作

群組協作技術[27,30,31,38,64～66]通過用戶自組織的P2P網絡能夠獲取附近用戶的位置信息。該技術可分為2類：陌生人之間的協作和基于信任關系的協作。

5.4.1 陌生人之間的協作

陌生人之間的協作通常使用藍牙通信技術，用戶之間的信息交互發生在10 m之內。

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

5.4.2 基于信任關系的協作

基于信任關系的協作通常使用藍牙或ad hoc網絡建立協作組，協作組成員之間相互信任，用以分享位置或其他信息。

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

圖17 P2P空間隱匿算法示例

6 現有技術對比分析

6.1 4類技術優缺點分析

本文綜述了位置服務中2種隱私保護系統構架下基于泛化和模糊的4類LBS隱私保護技術。

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

不依賴可信第三方的系統構架中，現有方案主要集中于3類技術：位置偏移和模糊技術、偽造虛假位置技術和群組協作技術。

位置偏移和模糊技術在真實位置中加入噪聲以降低位置精確度。該技術主要用于保護位置隱私，使用相關性和位置不可分辨性作為隱私保護度量標準。其優勢在于：1) 計算和存儲開銷較小；2)通過調整噪聲函數的相關參數，可達到較高的隱私保護水平；3) 根據不同應用需求，用戶可調節位置精確度損失。其缺點在于：1) 降低了位置精確度，可能難以滿足用戶服務需求；2) 在人口稀少地區，難以達到應有的隱私保護水平；3) 該技術主要針對位置隱私，不能保護查詢隱私。

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

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

6.2 現有方案存在問題

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

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

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

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

4) 現有研究大多針對如何設計和改進隱私保護方案，專門針對隱私保護度量指標的研究尚不完善，由此導致對于不同隱私保護方案的評判沒有一個統一的標準。因此，應當研究如何制定統一的隱私度量指標使各類方案都能得到合理的評估。

表1 現有位置隱私保護技術的目標

表2 現有位置隱私保護技術的系統開銷

7 結束語

LBS已成為人們日常生活中不可或缺的一種信息服務方式，因此，如何在使用LBS過程中有效地防止隱私泄露成為隱私保護領域的研究熱點。本文全面介紹了LBS隱私保護背景知識，討論了現有攻擊者模型和隱私度量指標，并深入分析和對比了4類基于泛化和模糊的隱私保護技術，指出了現有方案的優點和不足。未來面對云計算、大數據等新技術帶來的機遇，現有的隱私保護技術面臨著各種新的挑戰，研究者適時提出隱私計算理論體系[67]。在未來位置隱私保護方面，亟待從以下幾方面為用戶隱私數據全生命周期保護提供理論與技術支撐。

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

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

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

[1]王璐,孟小峰.位置大數據隱私保護研究綜述[J].軟件學報,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]周傲英,楊彬,金澈清,等.基于位置的服務:架構與進展[J].計算機學報,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]劉海,李興華,王二蒙,等.連續服務請求下基于假位置的用戶隱私增強方法[J].通信學報,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]潘曉,郝興,孟小峰.基于位置服務中的連續查詢隱私保護研究[J].計算機研究與發展,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]倪巍偉,馬中希,陳蕭.面向路網隱私保護連續近鄰查詢的安全區域構建[J].計算機學報,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]彭長根,丁紅發,朱義杰,等.隱私保護的信息熵模型及其度量方法[J].軟件學報,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 位置隱私保護方法研究[J].通信學報,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]倪巍偉,陳蕭,馬中希.支持偏好調控的路網隱私保護k近鄰查詢方法[J].計算機學報,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:一種用戶協作無匿名區域的位置隱私保護方法[J].計算機學報,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].通信學報,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-），男，江蘇南通人，西安電子科技大學博士生，主要研究方向為網絡安全與隱私保護。

李鳳華（1966-），男，湖北浠水人，博士，中國科學院信息工程研究所副總工程師、研究員、博士生導師，主要研究方向為網絡與系統安全、隱私計算、可信計算。

牛犇（1984-），男，陜西西安人，博士，中國科學院信息工程研究所助理研究員，主要研究方向為網絡安全、隱私計算。

孫哲（1987-），男，安徽安慶人，中國科學院信息工程研究所博士生，主要研究方向為信息安全、隱私保護。

李暉（1968-），男，河南靈寶人，博士，西安電子科技大學教授、博士生導師，主要研究方向為密碼學、無線網絡安全、云計算安全、信息論與編碼理論。

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

—廣東聯合基金資助項目(No.U1401251)；國家高技術研究發展計劃（“863”計劃）基金資助項目(No.2015AA016007)；國家自然科學基金—青年科學基金資助項目(No.61502489)；國家“核高基”科技重大專項基金資助項目（No.2015ZX01029101）