李維皓，曹進(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ù)中，用戶(hù)的位置信息被用戶(hù)視為一項(xiàng)“無(wú)關(guān)緊要”的信息無(wú)償?shù)匕l(fā)送給了服務(wù)提供商來(lái)?yè)Q取相關(guān)的服務(wù)。然而這些信息一旦被惡意用戶(hù)或是具有強(qiáng)大計(jì)算能力的服務(wù)提供商獲取，那么用戶(hù)的個(gè)人信息安全就會(huì)受到威脅。位置信息能夠泄露用戶(hù)的諸多敏感信息，因此保護(hù)用戶(hù)的位置信息隱私也成為了必不可少的研究課題。

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

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

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

2) 在考慮歷史信息的關(guān)聯(lián)性和用戶(hù)自身信息的關(guān)聯(lián)性的同時(shí)，從時(shí)間的維度和查詢(xún)范圍的維度擴(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)求信息中包含了用戶(hù)的真實(shí)請(qǐng)求，并將真實(shí)信息隱藏在匿名信息中，因此不影響用戶(hù)所享有的服務(wù)質(zhì)量。

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

2 相關(guān)工作

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

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

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

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ē)卉?chē)站，那么此商場(chǎng)就是該位置的POI，而該位置的坐標(biāo)則是位置信息，公交車(chē)站是查詢(xún)內(nèi)容。

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

2) 背景信息

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

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

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

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

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

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

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

3) 通信基站將接收到的信息發(fā)送至相應(yīng)的LBS提供商的服務(wù)器，通信基站只對(duì)用戶(hù)的請(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í)，背景信息的存在為攻擊者提供了線(xiàn)索來(lái)分析推測(cè)出用戶(hù)的真實(shí)信息。本節(jié)通過(guò)一個(gè)例子來(lái)解釋本文的研究動(dòng)機(jī)。如圖2所示，將地圖等分為6×6的位置單元，根據(jù)背景信息中的歷史查詢(xún)概率，每一個(gè)位置單元用不同的灰度來(lái)表示該位置單元?dú)v史查詢(xún)概率的不同，灰度越高表示在該位置單元的歷史查詢(xún)概率越高，灰度越低表示該位置單元的歷史查詢(xún)概率越低。

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

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

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

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

因此，單一地考慮地圖中位置的歷史信息無(wú)法抵御攻擊者從用戶(hù)自身信息的關(guān)聯(lián)性來(lái)推斷出用戶(hù)真實(shí)信息的攻擊。本文從歷史信息和用戶(hù)自身信息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考慮到用戶(hù)自身關(guān)聯(lián)的隱私信息，在選取匿名位置區(qū)域時(shí)，將區(qū)域C3過(guò)濾，從而選取區(qū)域位置C4為匿名區(qū)域，如圖2(b)中的虛線(xiàn)區(qū)域R2所示。

3.4 隱私度量

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

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

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

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

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

Ba-2PS算法由地圖預(yù)處理算法和雙篩選算法組成。其中，地圖預(yù)處理算法實(shí)現(xiàn)了對(duì)地圖的初始化分割，根據(jù)歷史背景信息初始化位置單元的歷史查詢(xún)概率，進(jìn)而通過(guò)雙篩選算法選取匿名位置發(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í)刻，用戶(hù)Alice位于位置單元locu中，請(qǐng)求附近的POI的信息，其中請(qǐng)求范圍記作radu，所查詢(xún)的內(nèi)容記作queu。用戶(hù)Alice的真實(shí)請(qǐng)求向量為。根據(jù)背景信息獲取位置單元locu的查詢(xún)概率Pr(locu)，遍歷地圖中的位置單元，選擇和Alice當(dāng)前位置單元具有相近查詢(xún)概率的位置單元，即其中γ≥0，將滿(mǎn)足條件的位置單元存儲(chǔ)在集合η中，并將集合η作為雙篩選算法的一個(gè)輸入，則loci∈η。具體如算法1所示。

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

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

輸出集合η

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

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

4) 輸入集合η。

4.2 雙篩選算法

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

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

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

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

圖3 迭代四等分劃分

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

算法2雙篩選算法

輸入集合η、ζ，k值

輸出集合η′

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

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

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

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

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

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

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

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

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

輸入集合'η，背景信息

輸出集合δ

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

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

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

圖4 四叉樹(shù)

最后，得到查詢(xún)半徑和相應(yīng)的位置單元、查詢(xún)內(nèi)容，重新構(gòu)成匿名請(qǐng)求和用戶(hù)的真實(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)證。通過(guò)分析證明 En-2PS方案能夠抵御的攻擊類(lèi)型，同時(shí)通過(guò)隱私度量對(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ù)中，用戶(hù)利用無(wú)線(xiàn)信道和基于位置的服務(wù)提供商進(jìn)行交互。無(wú)線(xiàn)信道是開(kāi)放的，基于密碼學(xué)的隱私保護(hù)算法可以避免惡意用戶(hù)竊取無(wú)線(xiàn)信道中的隱私信息，然而基于密碼學(xué)的隱私保護(hù)算法（例如，AES、3DES、RSA等）計(jì)算和處理開(kāi)銷(xiāo)較大。

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

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

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

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

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

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

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

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

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

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

6.2 性能驗(yàn)證

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

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

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

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

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

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

6.3 隱私驗(yàn)證

本節(jié)分別從泄露概率、位置隱私和查詢(xún)隱私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í)信息的概率就越低。

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

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

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

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

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

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