基于位置服務(wù)隱私自關(guān)聯(lián)的隱私保護(hù)方案

李維皓，曹進(jìn)，李暉

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

1 引言

隨著移動(dòng)智能終端的普遍應(yīng)用，社交網(wǎng)絡(luò)已經(jīng)成為了人們生活中必不可少的一部分，其中基于位置服務(wù)（LBS, location-based service）的使用最為頻繁。如今，智能終端可以下載多樣化的應(yīng)用程序，增添多樣化的服務(wù)和個(gè)性化的操作。然而，這種便利也帶來(lái)了安全隱患?；谖恢梅?wù)中，用戶的位置信息被用戶視為一項(xiàng)“無(wú)關(guān)緊要”的信息無(wú)償?shù)匕l(fā)送給了服務(wù)提供商來(lái)?yè)Q取相關(guān)的服務(wù)。然而這些信息一旦被惡意用戶或是具有強(qiáng)大計(jì)算能力的服務(wù)提供商獲取，那么用戶的個(gè)人信息安全就會(huì)受到威脅。位置信息能夠泄露用戶的諸多敏感信息，因此保護(hù)用戶的位置信息隱私也成為了必不可少的研究課題。

在基于位置服務(wù)中，用戶的位置信息分為2種，即單點(diǎn)的位置信息和連續(xù)的位置信息。其中，單點(diǎn)的位置信息為在某個(gè)時(shí)間點(diǎn)發(fā)起的基于位置的請(qǐng)求，例如，尋找附近的商家、查詢某個(gè)城市的天氣等。連續(xù)的位置信息則為在某個(gè)時(shí)間段內(nèi)多次的位置信息的記錄，例如，路線導(dǎo)航、查詢交通擁堵情況等。無(wú)論是單點(diǎn)的位置信息還是連續(xù)的位置信息，都存在很多隱私保護(hù)方案[1-4]，在保證用戶的位置隱私不被泄露的同時(shí)，也使用戶能夠享受相應(yīng)的基于位置的服務(wù)。背景信息的存在提高了攻擊者實(shí)現(xiàn)攻擊的精準(zhǔn)度，因此，在設(shè)計(jì)隱私保護(hù)方案時(shí)，背景信息是必須考慮的因素?，F(xiàn)有的隱私保護(hù)方案中，背景信息是指地圖中位置點(diǎn)的歷史查詢概率[5-7]。根據(jù)歷史查詢概率的大小，攻擊者可以將低概率的位置過濾掉。隨著移動(dòng)智能終端的不斷升級(jí)，存儲(chǔ)成本已經(jīng)大幅降低，用戶在享用基于位置服務(wù)的同時(shí)，移動(dòng)終端也存儲(chǔ)了短時(shí)間內(nèi)的查詢記錄，同樣，服務(wù)提供商也有相關(guān)的信息存儲(chǔ)，可以通過分析用戶的查詢記錄獲取用戶位置信息，因此用戶自身信息也成為了隱私保護(hù)方案設(shè)計(jì)中不可忽略的一項(xiàng)。

本文方案的創(chuàng)新點(diǎn)包括以下3個(gè)方面。

1) 現(xiàn)有的隱私保護(hù)方案大多基于歷史的背景信息，通過普遍存在性來(lái)實(shí)現(xiàn)隱私保護(hù)方案，然而針對(duì)個(gè)體差異性的考慮并不充分。本文方案從歷史信息的關(guān)聯(lián)性和用戶自身信息的關(guān)聯(lián)性2個(gè)方面設(shè)計(jì)來(lái)保護(hù)用戶的隱私，提出了一個(gè)簡(jiǎn)易隱私自關(guān)聯(lián)的隱私保護(hù)算法（Ba-2PS, basic privacy self- correlation privacy- preserving scheme）實(shí)現(xiàn)對(duì)用戶的隱私保護(hù)。

2) 在考慮歷史信息的關(guān)聯(lián)性和用戶自身信息的關(guān)聯(lián)性的同時(shí)，從時(shí)間的維度和查詢范圍的維度擴(kuò)展了簡(jiǎn)易隱私自關(guān)聯(lián)的隱私保護(hù)算法，提出了擴(kuò)展隱私自關(guān)聯(lián)的隱私保護(hù)算法（En-2PS, enhanced privacy self-correlation privacy-preserving scheme）。本文提出的隱私保護(hù)方案基于匿名技術(shù)，由于發(fā)送給服務(wù)提供商的請(qǐng)求信息中包含了用戶的真實(shí)請(qǐng)求，并將真實(shí)信息隱藏在匿名信息中，因此不影響用戶所享有的服務(wù)質(zhì)量。

3) 不同于現(xiàn)有隱私保護(hù)方案的單一保護(hù)用戶的位置隱私或者查詢隱私，本文方案在考慮到背景信息存在的前提下，同時(shí)個(gè)性化地保護(hù)用戶的位置隱私和查詢隱私。

2 相關(guān)工作

基于位置服務(wù)中，用戶的隱私信息包含位置隱私[8-10]和查詢隱私[11-13]，現(xiàn)有的隱私保護(hù)方案主要分為基于密碼學(xué)的隱私保護(hù)方案[14-15]、基于模糊的隱私保護(hù)方案[16-17]、基于差分的隱私保護(hù)方案[3,10]、基于匿名的隱私保護(hù)方案[18-19]。其中，基于匿名的隱私保護(hù)方案分為基于匿名中心的隱私保護(hù)方案[14-15]和基于移動(dòng)終端的隱私保護(hù)方案[7-8,16]。在基于匿名中心的隱私保護(hù)方案中，匿名中心位于用戶終端和服務(wù)提供商之間，承擔(dān)了性能和安全的責(zé)任，對(duì)用戶的信息進(jìn)行處理，經(jīng)過匿名化操作的請(qǐng)求信息由匿名中心發(fā)送至服務(wù)提供商，降低了用戶的計(jì)算、存儲(chǔ)開銷。然而，匿名中心成為了性能和安全的瓶頸，大量的隱私請(qǐng)求由匿名中心來(lái)處理，執(zhí)行效率會(huì)大幅降低，同時(shí)一旦匿名中心被攻破，那么所有的隱私信息將會(huì)泄露。目前，移動(dòng)網(wǎng)絡(luò)不斷發(fā)展，智能終端不斷智能化，存儲(chǔ)能力不斷增加，計(jì)算處理能力不斷加強(qiáng)，為了避免匿名中心的單點(diǎn)泄露問題，基于移動(dòng)終端的隱私保護(hù)方案也不斷涌現(xiàn)。Niu等[5]設(shè)計(jì)實(shí)現(xiàn)了基于匿名的隱私保護(hù)方案，考慮到背景信息中每一個(gè)位置的歷史查詢概率，同時(shí)為了避免所選的匿名位置位于相同的建筑之內(nèi)降低隱私保護(hù)效果，通過計(jì)算匿名位置之間的距離，確保所選取的匿名位置單元兩兩之間的距離盡可能遠(yuǎn)?；诨旌蠀^(qū)域（Mixzone）的隱私保護(hù)方案中，Palanisamy等[20]通過更換用戶離開Mixzone時(shí)的假名，使攻擊者不能夠通過分析進(jìn)入Mixzone和離開該區(qū)域的關(guān)聯(lián)性來(lái)獲取用戶的真實(shí)信息，以保護(hù)用戶的位置隱私。CacheCloak方案[21]利用緩存用戶請(qǐng)求的服務(wù)信息來(lái)避免和服務(wù)提供商的多次交互，通過減少交互次數(shù)保護(hù)用戶的隱私信息。Xu等[18]提出了一種基于感知的隱私保護(hù)模型，利用信息熵來(lái)衡量位置區(qū)域的受歡迎程度，并且利用四叉樹來(lái)分離請(qǐng)求信息和特定用戶，針對(duì)不同的分類提供個(gè)性化的隱私保護(hù)。

在保護(hù)用戶位置隱私的同時(shí)，用戶請(qǐng)求中的查詢內(nèi)容同樣包含了用戶的隱私，根據(jù)基于匿名的隱私保護(hù)算法演變出了l-多樣性方案[23-25]和t-接近性方案[26-28]。其中，l-多樣性方案在基于k匿名方法的基礎(chǔ)上，保證了每個(gè)等價(jià)類中敏感屬性達(dá)到閾值，避免了敏感屬性的泄露。k匿名技術(shù)是一種利用混淆的方法使觀測(cè)者無(wú)法辨別出真實(shí)信息的技術(shù)，例如，將用戶的真實(shí)信息和k-1個(gè)匿名信息一起發(fā)送給服務(wù)提供商，服務(wù)提供商不能夠分辨出接收到的k個(gè)請(qǐng)求中哪一個(gè)是真實(shí)的請(qǐng)求信息。He等[25]提出了空間多樣性，結(jié)合用戶的路徑和隨機(jī)模型，分析得到用戶的空間差異度，提出了一個(gè)優(yōu)化停頓的隱私訪問方案，實(shí)現(xiàn)了較高的隱私保護(hù)效果。Li等[28]分析了l-多樣性的隱私保護(hù)算法的局限性，設(shè)定在等價(jià)類中敏感屬性的分布距離不大于預(yù)設(shè)的閾值，實(shí)現(xiàn)對(duì)敏感屬性的保護(hù)。

現(xiàn)有的隱私保護(hù)方案為保護(hù)用戶的位置隱私和查詢隱私奠定了深厚的基礎(chǔ)。本文根據(jù)現(xiàn)有的隱私保護(hù)方案，考慮了用戶自身信息之間的關(guān)聯(lián)，在保證位置信息不被泄露的同時(shí)，從時(shí)間的維度和查詢范圍的維度保護(hù)了用戶的查詢隱私。

3 準(zhǔn)備工作

3.1 基本概念

1) POI

POI（point of interest）是指在某一個(gè)位置點(diǎn)區(qū)別于坐標(biāo)信息來(lái)辨別該位置的性質(zhì)。例如，Alice在某商場(chǎng)請(qǐng)求周圍公交車站，那么此商場(chǎng)就是該位置的POI，而該位置的坐標(biāo)則是位置信息，公交車站是查詢內(nèi)容。

在某種程度上，POI和查詢內(nèi)容在語(yǔ)義上具有重合性。例如，在上述的例子中，商場(chǎng)是該位置的POI，公交車站是查詢內(nèi)容，然而從公交車站的位置坐標(biāo)來(lái)說，公交車站是該位置的POI。綜上所述，POI是位置坐標(biāo)上基礎(chǔ)建設(shè)（或者其他能夠區(qū)別辨識(shí)的設(shè)施）的語(yǔ)義內(nèi)容，能夠作為用戶進(jìn)行查詢的關(guān)鍵字成為查詢內(nèi)容。

2) 背景信息

隨著科技的發(fā)展和信息的海量增加，任何一個(gè)具有計(jì)算、處理和存儲(chǔ)功能的個(gè)體都能夠獲取地圖中用戶所處區(qū)域的歷史查詢數(shù)據(jù)，其中包含了某個(gè)地點(diǎn)曾經(jīng)發(fā)生和當(dāng)前發(fā)生的請(qǐng)求記錄、該地的查詢概率以及該地所處的商圈和POI。現(xiàn)有的隱私保護(hù)方案單一地考慮了背景信息中歷史數(shù)據(jù)的集合，而未關(guān)注某個(gè)特定時(shí)間點(diǎn)的查詢概率以及相鄰時(shí)間點(diǎn)的查詢概率。本文所指背景信息不僅包含了查詢概率，同時(shí)包含了區(qū)別位置的興趣點(diǎn)POI。本文中的背景信息是通過Google地圖的API（application programming interface）來(lái)獲取區(qū)域內(nèi)每個(gè)位置的查詢概率，并將背景信息存儲(chǔ)于智能終端中。

3.2 LBS基本框架結(jié)構(gòu)

基于位置服務(wù)的基本架構(gòu)主要由 4個(gè)部分組成：GPS衛(wèi)星、移動(dòng)終端、通信基站和服務(wù)提供商，如圖1所示。

圖1 LBS基本框架結(jié)構(gòu)

用戶通過移動(dòng)終端獲取其所處的位置信息，然后通過移動(dòng)蜂窩網(wǎng)絡(luò)或者Wi-Fi將服務(wù)請(qǐng)求發(fā)送至服務(wù)提供商的服務(wù)器。服務(wù)提供商在接收到由通信基站轉(zhuǎn)發(fā)來(lái)的請(qǐng)求后，將用戶所需的服務(wù)信息作為響應(yīng)發(fā)送給用戶的移動(dòng)終端，從而完成一個(gè)完整的請(qǐng)求服務(wù)和響應(yīng)服務(wù)的過程。

1) GPS衛(wèi)星為移動(dòng)終端提供當(dāng)前的地理位置信息?；谖恢梅?wù)的隱私保護(hù)算法對(duì)此過程中的信息不進(jìn)行考慮，默認(rèn)在位置獲取的過程是安全的。

2) 用戶通過移動(dòng)終端對(duì)請(qǐng)求信息進(jìn)行隱私保護(hù)，將保護(hù)后的信息發(fā)送至通信基站，在該過程中，用戶的請(qǐng)求信息已經(jīng)過隱私保護(hù)處理。

3) 通信基站將接收到的信息發(fā)送至相應(yīng)的LBS提供商的服務(wù)器，通信基站只對(duì)用戶的請(qǐng)求和收到的響應(yīng)進(jìn)行轉(zhuǎn)發(fā)，不對(duì)請(qǐng)求信息進(jìn)行修改。同樣，通信基站在收到服務(wù)器的響應(yīng)后將其轉(zhuǎn)發(fā)至移動(dòng)終端，不對(duì)響應(yīng)信息進(jìn)行修改。

3.3 研究動(dòng)機(jī)

在設(shè)計(jì)基于位置服務(wù)的隱私保護(hù)方案時(shí)，背景信息的存在為攻擊者提供了線索來(lái)分析推測(cè)出用戶的真實(shí)信息。本節(jié)通過一個(gè)例子來(lái)解釋本文的研究動(dòng)機(jī)。如圖2所示，將地圖等分為6×6的位置單元，根據(jù)背景信息中的歷史查詢概率，每一個(gè)位置單元用不同的灰度來(lái)表示該位置單元?dú)v史查詢概率的不同，灰度越高表示在該位置單元的歷史查詢概率越高，灰度越低表示該位置單元的歷史查詢概率越低。

圖2 研究動(dòng)機(jī)

現(xiàn)有的隱私保護(hù)方案為了達(dá)到最佳的隱私保護(hù)效果，所選取匿名位置的歷史查詢概率和用戶（Alice）真實(shí)位置的歷史查詢概率相同，從而使隱私度量值最高。在t時(shí)刻，Alice位于位置區(qū)域C1中，該地圖中和 Alice所處位置區(qū)域C1具有相同的歷史查詢概率的位置區(qū)域?yàn)镃2、C3、C4，即

其中，P(Ci)表示位置區(qū)域Ci的歷史查詢概率，如圖2(a)所示。假設(shè)在該例子中，選取的k匿名算法中的k=3，則需要選擇k-1=2個(gè)匿名位置區(qū)域，則從3個(gè)具有相同歷史查詢概率的位置區(qū)域中選出2個(gè)，即C2、C3，如圖2(b)所示的虛線區(qū)域R1。

然而，有很多APP對(duì)用戶的歷史查詢信息進(jìn)行存儲(chǔ)。例如，在t-1時(shí)刻，Alice曾在位置區(qū)域C3發(fā)起過對(duì)于que1的查詢請(qǐng)求，由于2個(gè)時(shí)間點(diǎn)之間的時(shí)間差值足夠小，即Δt=ε，εN+∈，那么攻擊者則會(huì)認(rèn)為Alice在短期內(nèi)搜索過該位置的服務(wù)，且服務(wù)內(nèi)容相同，則該位置區(qū)域C3為匿名位置，從而用戶的泄露概率由增加為，增加了隱私泄露的風(fēng)險(xiǎn)。

因此，單一地考慮地圖中位置的歷史信息無(wú)法抵御攻擊者從用戶自身信息的關(guān)聯(lián)性來(lái)推斷出用戶真實(shí)信息的攻擊。本文從歷史信息和用戶自身信息2個(gè)方面同時(shí)考慮，提出了2個(gè)隱私保護(hù)算法：簡(jiǎn)易隱私自關(guān)聯(lián)的隱私保護(hù)算法（Ba-2PS）和擴(kuò)展隱私自關(guān)聯(lián)的隱私保護(hù)算法（En-2PS）。其中，Ba-2PS考慮到用戶自身關(guān)聯(lián)的隱私信息，在選取匿名位置區(qū)域時(shí)，將區(qū)域C3過濾，從而選取區(qū)域位置C4為匿名區(qū)域，如圖2(b)中的虛線區(qū)域R2所示。

3.4 隱私度量

在基于k匿名的隱私保護(hù)方案中，用戶發(fā)送給服務(wù)提供商的請(qǐng)求包含了用戶的身份、發(fā)送請(qǐng)求的時(shí)間戳、用戶的當(dāng)前位置、查詢內(nèi)容和查詢范圍。本文為了衡量隱私保護(hù)的程度，采用k匿名概率和信息熵來(lái)衡量隱私信息被推測(cè)的不確定性[28]。其中，k匿名概率表示用戶隱私信息的泄露概率，泄露概率越大則表示隱私保護(hù)的程度越低。在基于信息熵的隱私度量中，信息熵值越大，說明計(jì)算的信息的不確定性越高，則隱私保護(hù)的程度就越高。信息熵的具體定義如下。

定義1基于k匿名概率的隱私度量。已知所選取的匿名位置構(gòu)成區(qū)域?yàn)镽，，即|R|=r，則基于k匿名概率中k的取值為該區(qū)域中位置單元的個(gè)數(shù)，即k=|R|，則泄露概率為

定義 2基于信息熵的隱私度量。已知用戶真實(shí)的位置區(qū)域?yàn)閖，經(jīng)過k匿名算法得到k-1個(gè)匿名位置區(qū)域，則信息熵為

其中，Pri表示根據(jù)用戶的真實(shí)位置區(qū)域j選取的匿名區(qū)域i的概率。信息熵具有極值性，即事件的發(fā)生概率相同，信息熵值達(dá)到最大值，概率事件的不確定性最高，在隱私保護(hù)算法中則說明用戶的隱私保護(hù)程度最高。

4 簡(jiǎn)易隱私自關(guān)聯(lián)的隱私保護(hù)算法

Ba-2PS算法由地圖預(yù)處理算法和雙篩選算法組成。其中，地圖預(yù)處理算法實(shí)現(xiàn)了對(duì)地圖的初始化分割，根據(jù)歷史背景信息初始化位置單元的歷史查詢概率，進(jìn)而通過雙篩選算法選取匿名位置發(fā)送給服務(wù)提供商來(lái)?yè)Q取相應(yīng)的服務(wù)。

4.1 地圖預(yù)處理算法

在地圖預(yù)處理算法中，獲取地圖，將地圖等分為m個(gè)位置單元，每個(gè)位置單元作為后續(xù)進(jìn)行位置選取的最小位置單元。其中，m的數(shù)值決定了地圖劃分的粒度，loci表示第i個(gè)位置單元，且+i,m∈N 。

在t時(shí)刻，用戶Alice位于位置單元locu中，請(qǐng)求附近的POI的信息，其中請(qǐng)求范圍記作radu，所查詢的內(nèi)容記作queu。用戶Alice的真實(shí)請(qǐng)求向量為。根據(jù)背景信息獲取位置單元locu的查詢概率Pr(locu)，遍歷地圖中的位置單元，選擇和Alice當(dāng)前位置單元具有相近查詢概率的位置單元，即其中γ≥0，將滿足條件的位置單元存儲(chǔ)在集合η中，并將集合η作為雙篩選算法的一個(gè)輸入，則loci∈η。具體如算法1所示。

算法1地圖預(yù)處理算法

輸入地圖，用戶當(dāng)前位置信息

輸出集合η

1) 等分地圖為m個(gè)位置單元；

3) 存儲(chǔ)于集合η中；

4) 輸入集合η。

4.2 雙篩選算法

根據(jù)地圖預(yù)處理算法得到一個(gè)位置單元的集合η，在該集合中每個(gè)位置單元的歷史查詢概率和用戶當(dāng)前所處位置單元具有相同的歷史查詢概率。在雙篩選算法中，假設(shè)用戶的移動(dòng)終端中緩存了用戶在T時(shí)間段內(nèi)的查詢記錄，該時(shí)間段的查詢記錄存儲(chǔ)于集合ζ中，其中用戶u在T時(shí)間內(nèi)的查詢記錄為，其中l(wèi)ocali∈ζ，

根據(jù)已知位置單元集合η和查詢記錄集合ζ，對(duì)位置單元集合η和查詢記錄集合ζ中的向量求交集，如果集合η中的位置單元存在于集合ζ中，則將該位置單元從集合η中刪除。經(jīng)過第一次篩選，集合η中的位置單元個(gè)數(shù)小于或等于最初從地圖預(yù)處理算法中得到的位置單元個(gè)數(shù)。此次篩選得到的位置單元避免了因用戶自身信息關(guān)聯(lián)而降低隱私強(qiáng)度的問題。

然而，此時(shí)集合η中的位置單元不能滿足距離用戶的位置盡可能遠(yuǎn)，而一旦選取的匿名位置單元和用戶的真實(shí)位置十分接近時(shí)，無(wú)法避免兩者位于同一座建筑內(nèi)，從而失去進(jìn)行匿名保護(hù)的意義。第二次篩選操作的目的則是盡可能地選取距離較遠(yuǎn)的位置單元，保證匿名位置單元盡可能分散。

為了方便第二次的篩選操作，本文采用四叉樹地圖進(jìn)行存儲(chǔ)，根據(jù)背景信息迭代劃分地圖，每次四等分，如圖3所示。查詢概率高的區(qū)域位置單元的密度較高，查詢概率低的區(qū)域位置單元的密度較低，因此，在中，設(shè)置。根據(jù)迭代劃分，對(duì)應(yīng)由四叉樹來(lái)進(jìn)行存儲(chǔ)，為了保證所選的匿名位置盡可能分散，則所選的匿名位置單元中不存在任意2個(gè)位置單元屬于同一個(gè)父節(jié)點(diǎn)，且深度檢索該位置單元所屬分支的深度滿足的節(jié)點(diǎn)不存在相同的父節(jié)點(diǎn)。

圖3 迭代四等分劃分

最后將得到的k-1個(gè)位置單元作為匿名位置單元構(gòu)成匿名查詢請(qǐng)求和用戶的真實(shí)位置一起發(fā)送給服務(wù)提供。具體如算法2所示。

算法2雙篩選算法

輸入集合η、ζ，k值

輸出集合η′

5 擴(kuò)展隱私自關(guān)聯(lián)的隱私保護(hù)算法

En-2PS算法是Ba-2PS的擴(kuò)展方案，在考慮到歷史背景信息和用戶自身信息的同時(shí)，分析位置單元、查詢內(nèi)容、查詢半徑之間的關(guān)聯(lián)關(guān)系，設(shè)計(jì)匿名查詢內(nèi)容生成算法和請(qǐng)求生成算法。

5.1 匿名查詢內(nèi)容生成算法

在匿名查詢內(nèi)容生成算法中，從時(shí)間的維度分析位置單元和查詢內(nèi)容的關(guān)系，從而確定匿名查詢內(nèi)容。時(shí)間維度的不同，所查詢的POI的種類也不相同。用戶請(qǐng)求服務(wù)的時(shí)間為t，根據(jù)Ba-2PS選取的k-1個(gè)匿名位置單元滿足以下3個(gè)要求。

1) 根據(jù)背景信息所選取的位置單元和用戶所處的位置單元有相近的查詢概率。

2) 不存在用戶在T時(shí)段內(nèi)的查詢記錄中。

3) 所選取的位置單元分散在地圖中且互不相鄰。

為了保護(hù)用戶的查詢隱私，在發(fā)送給服務(wù)提供商的請(qǐng)求信息中的查詢內(nèi)容不能和用戶真實(shí)的查詢內(nèi)容相同，同時(shí)避免在特定時(shí)間點(diǎn)發(fā)送不可能的請(qǐng)求信息（例如，在清晨時(shí)間查詢酒吧）。已知用戶Alice在位置單元請(qǐng)求的查詢內(nèi)容queu，集合'η中的匿名位置單元loci，根據(jù)背景信息，在t時(shí)刻，匿名位置單元曾查詢的POI中選取查詢概率較高的POI作為查詢請(qǐng)求中匿名位置單元loci的查詢內(nèi)容quei，則該查詢內(nèi)容的查詢概率滿足其中0＜θ＜1。具體如算法3所示。

算法3匿名查詢內(nèi)容生成算法

輸入集合'η，背景信息

輸出集合δ

5.2 請(qǐng)求生成算法

在請(qǐng)求生成算法中，從查詢范圍的維度重新選擇每一個(gè)匿名請(qǐng)求對(duì)應(yīng)的查詢半徑，從而避免攻擊者利用背景信息推測(cè)匿名位置單元的查詢半徑過大或者過小，進(jìn)而降低匿名位置單元的個(gè)數(shù)，提高用戶隱私的泄露概率。例如，位置單元的查詢半徑過大，包含了不可能的地方（例如河、湖），從而攻擊者推測(cè)此位置為匿名位置單元。

已知 Ba-2PS中對(duì)地圖利用四叉樹進(jìn)行存儲(chǔ)，假設(shè)k=3，選取的 2個(gè)匿名位置單元分別為loc1和loc2，如圖4所示。根據(jù)深度優(yōu)先搜索四叉樹，得到位置單元的深度分別為Dep(loc1)、Dep(loc2)和Dep(locu)。如果所選的位置單元的深度滿足Dep(loci)＞θ，則說明該位置單元所處區(qū)域密度較高，進(jìn)而相應(yīng)的查詢半徑為radi=radi+β，其中β＜0，如果Dep(loc1)≤θ，則查詢半徑為，其中β＞0。

圖4 四叉樹

最后，得到查詢半徑和相應(yīng)的位置單元、查詢內(nèi)容，重新構(gòu)成匿名請(qǐng)求和用戶的真實(shí)請(qǐng)求一起發(fā)送給服務(wù)提供商。具體如算法4所示。

算法4請(qǐng)求生成算法

輸入集合'η，集合δ

輸出真實(shí)請(qǐng)求和匿名請(qǐng)求

6 隱私性分析和實(shí)驗(yàn)驗(yàn)證

本節(jié)分別從隱私性分析、性能分析以及隱私性驗(yàn)證對(duì)Ba-2PS和En-2PS方案的性能和隱私性進(jìn)行測(cè)試和驗(yàn)證。通過分析證明 En-2PS方案能夠抵御的攻擊類型，同時(shí)通過隱私度量對(duì)保護(hù)隱私的保護(hù)程度證明了方案的隱私性。

本文實(shí)驗(yàn)采用Matlab軟件在PC機(jī)（2.9 GHz Intel i7 CPU, 16 GB 內(nèi)存）上進(jìn)行模擬仿真，并對(duì)方案的性能進(jìn)行驗(yàn)證。

選取了某城市內(nèi)8 km×8 km的地圖，劃分為160×160個(gè)位置單元，每個(gè)位置單元為50 m×50 m的矩形。實(shí)驗(yàn)中參數(shù)k是指k-匿名中發(fā)送給服務(wù)提供商的請(qǐng)求數(shù)量，選取范圍為[5,50]。

6.1 隱私性分析

本節(jié)分別從共謀攻擊和推斷攻擊2個(gè)方面分析了 En-2PS方案的安全性。在基于位置服務(wù)中，用戶利用無(wú)線信道和基于位置的服務(wù)提供商進(jìn)行交互。無(wú)線信道是開放的，基于密碼學(xué)的隱私保護(hù)算法可以避免惡意用戶竊取無(wú)線信道中的隱私信息，然而基于密碼學(xué)的隱私保護(hù)算法（例如，AES、3DES、RSA等）計(jì)算和處理開銷較大。

定義 3已知?i∈C，滿足其中集合C為共謀集合，是攻擊者通過接收到的信息推測(cè)出用戶的位置信息，loci為攻擊者接收到的位置信息，且loci∈O，集合O是攻擊者所觀測(cè)到的位置信息集合，表示攻擊者通過收集到的位置信息推測(cè)出位置信息的概率。

引理1En-2PS可抵御共謀攻擊。

證明攻擊者為了獲取用戶的真實(shí)位置信息，可能聯(lián)合其他用戶甚至服務(wù)提供商實(shí)現(xiàn)共謀攻擊。在本文方案中，無(wú)論多少用戶或者服務(wù)提供商聯(lián)合，通過公布的位置信息推斷出真實(shí)位置信息的概率為一常數(shù)。En-2PS利用了k匿名技術(shù)來(lái)實(shí)現(xiàn)匿名位置單元的選取，則從k個(gè)公布出的位置單元中得出用戶真實(shí)位置單元的概率為

En-2PS是根據(jù)真實(shí)的背景信息來(lái)選取匿名位置單元的，其中背景信息可以被任意用戶或服務(wù)提供商獲取，因此，無(wú)論共謀用戶有多少，用戶的真實(shí)信息始終隱藏在k-1個(gè)匿名位置信息中。綜上所述，En-2PS能夠抵御共謀攻擊。證畢。

定義4已知loci∈O，集合O是攻擊者所觀測(cè)到的位置信息集合，且|O|=k，攻擊者推斷出的位置信息為，如果方案滿足，則表明攻擊者觀測(cè)到的位置單元兩兩相同，因概率相同從而不可分區(qū)；如果滿足，則表明攻擊者觀測(cè)到的位置單元兩兩不同，使攻擊者不能分辨。因此，沒有孤立點(diǎn)和通過背景關(guān)系可分析出的特殊點(diǎn)，說明該方案能夠抵御推斷攻擊。

引理2En-2PS可抵御推斷攻擊。

證明在 LBS中，服務(wù)提供商具有強(qiáng)大的計(jì)算、處理和存儲(chǔ)能力，在推斷攻擊中視服務(wù)提供商為主動(dòng)攻擊者，可以基于背景信息來(lái)分析推斷用戶的隱私。在 En-2PS中，根據(jù)背景信息選取的匿名位置單元滿足，其中γ＞0，攻擊者不能根據(jù)位置單元的查詢概率對(duì)觀測(cè)到的信息進(jìn)行篩選來(lái)分析得出用戶的真實(shí)位置單元。從而，攻擊者推斷用戶的真實(shí)信息滿足。此外，En-2PS中對(duì)用戶的查詢內(nèi)容和查詢范圍進(jìn)行個(gè)性化選擇，成功地避免了攻擊者通過背景信息和事件發(fā)生的可能性來(lái)推斷用戶真實(shí)信息的情況，因此，En-2PS能夠抵御推斷攻擊。證畢。

基于隱私度量的隱私性分析，根據(jù)第3.4節(jié)中提出的隱私度量，利用信息熵計(jì)算隱私保護(hù)方案所實(shí)現(xiàn)的隱私保護(hù)程度。參照3.4節(jié)中用戶真實(shí)的位置區(qū)域?yàn)閖，所對(duì)應(yīng)的熵值如式(1)所示。

在地圖預(yù)處理算法中，所選取位置單元locu的查詢概率為Pr(locu)，遍歷地圖中的位置單元，選擇和當(dāng)前位置單元具有相近查詢概率的位置單元，即，其中γ≥0。根據(jù)信息熵的定義，當(dāng)選擇的位置單元具有相同的查詢概率時(shí)，信息熵值達(dá)到最大。假設(shè)locx和locy滿足，其中0＜p＜1，當(dāng)locx越接近時(shí)，的值越大，求導(dǎo)可得

在地圖預(yù)處理算法中參數(shù)γ≥0，則有當(dāng)γ=0時(shí)，上述式子得到，即當(dāng)所選取的位置單元的查詢概率相同時(shí)取最大值。

6.2 性能驗(yàn)證

1) 執(zhí)行時(shí)間和存儲(chǔ)開銷與參數(shù)k關(guān)系

本節(jié)評(píng)估了Ba-2PS和En-2PS的執(zhí)行時(shí)間和存儲(chǔ)開銷隨k匿名算法中參數(shù)k值變化的情況，如圖5所示。Ba-2PS中沒有參數(shù)γ的參與，故只考慮了En-2PS中γ=0.02和γ=0.12的情況。參數(shù)γ決定了選取匿名位置單元的查詢概率的偏差度，參數(shù)γ越大，則集合η中的元素就越多，從而影響了算法的執(zhí)行時(shí)間。Ba-2PS和En-2PS的計(jì)算和存儲(chǔ)都在用戶的智能移動(dòng)終端中進(jìn)行，終端中存儲(chǔ)的數(shù)據(jù)大小并不會(huì)因?yàn)檫x取的k值大小而改變，故在圖5(b)中算法的存儲(chǔ)開銷保持不變。En-2PS中，參數(shù)γ不影響通信開銷，因此γ=0.2與γ=0.12這2條曲線重合。

圖5 執(zhí)行時(shí)間和存儲(chǔ)開銷與參數(shù)k關(guān)系

2) 執(zhí)行時(shí)間和通信開銷與參數(shù)γ關(guān)系

本節(jié)評(píng)估了執(zhí)行時(shí)間和通信開銷和參數(shù)γ的關(guān)系，如圖6所示。Ba-2PS沒有參數(shù)γ的參與，故只選取了k=20和k=50對(duì)En-2PS進(jìn)行性能評(píng)估。用戶利用移動(dòng)終端將請(qǐng)求信息發(fā)送給服務(wù)提供商來(lái)?yè)Q取服務(wù)，其中請(qǐng)求信息的大小決定了通信開銷的大小，而請(qǐng)求信息的大小取決于匿名算法中參數(shù)k值的大小，而和參數(shù)γ無(wú)關(guān)。然而，參數(shù)γ的大小影響了集合η的大小，參數(shù)γ的值越大，則滿足條件的位置單元就越多，故集合η中元素越多，在進(jìn)行迭代遍歷時(shí)消耗的時(shí)間更多。

圖6 執(zhí)行時(shí)間和通信開銷與參數(shù)γ關(guān)系

6.3 隱私驗(yàn)證

本節(jié)分別從泄露概率、位置隱私和查詢隱私3個(gè)方面對(duì)Ba-2PS和En-2PS的隱私性進(jìn)行評(píng)估，同時(shí)與Spati-PPM算法[6]進(jìn)行比較，驗(yàn)證本文方案的安全性。

實(shí)驗(yàn)比較了理論上的最佳值（optimal）、隨機(jī)值（baseline）和Ba-2PS、En-2PS、Spati-PPM方案隨參數(shù)k變化的泄露概率，如圖7所示，k值越大，發(fā)送給服務(wù)提供商的請(qǐng)求信息就越多，則攻擊者能推測(cè)出真實(shí)信息的概率就越低。

本文采用信息熵作為用戶位置隱私和查詢隱私的度量標(biāo)準(zhǔn)，具體的計(jì)算方式如定義2所示。信息熵，其中熵值越大，對(duì)應(yīng)的位置隱私度量和查詢隱私度量越高。因?yàn)?En-2PS在構(gòu)造請(qǐng)求時(shí)對(duì)用戶的請(qǐng)求范圍進(jìn)行了個(gè)性化選取，減小了攻擊者利用查詢范圍和位置單元的可能性，進(jìn)而實(shí)現(xiàn)推斷攻擊，降低了分析出用戶敏感信息的可能性，提高了位置隱私和查詢隱私的不確定性，如圖8和圖9所示。其中，Spati-PPM算法考慮了時(shí)間和空間之間的關(guān)聯(lián)性，為攻擊者推斷用戶的真實(shí)信息增加了難度，因此圖8中該方案的位置隱私效果優(yōu)于Ba-2PS，但因其未涉及對(duì)查詢隱私的保護(hù)，圖9中該方案的效果最差。En-2PS在考慮請(qǐng)求范圍的同時(shí)，也在選取匿名位置單元時(shí)將時(shí)間因素考慮在內(nèi)，避免了利用時(shí)空關(guān)聯(lián)因素來(lái)推斷出用戶的真實(shí)位置信息和查詢內(nèi)容的可能性。

圖7 參數(shù)k與泄露概率關(guān)系

圖8 參數(shù)k與位置隱私度量關(guān)系

圖9 參數(shù)k與查詢隱私度量關(guān)系

7 結(jié)束語(yǔ)

在基于位置服務(wù)中，用戶和服務(wù)提供商都會(huì)存儲(chǔ)一定時(shí)間內(nèi)的用戶請(qǐng)求信息，因此，攻擊者可以通過對(duì)歷史查詢信息的分析降低匿名效果。本文提出了一種隱私信息自關(guān)聯(lián)的隱私保護(hù)方案，在選取匿名位置單元時(shí)考慮到用戶自身的查詢歷史的自關(guān)聯(lián)關(guān)系，避免了攻擊者利用該信息來(lái)實(shí)現(xiàn)推斷攻擊。本文首先提出了一個(gè)基本的隱私保護(hù)方案Ba-2PS考慮了用戶信息的自關(guān)聯(lián)，進(jìn)而從查詢范圍出發(fā)，提出了En-2PS，實(shí)現(xiàn)了對(duì)用戶位置隱私和查詢隱私的保護(hù)。最后，本文通過詳細(xì)的性能和安全性實(shí)驗(yàn)驗(yàn)證了方案的有效性和安全性。