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

李維皓，丁晟，孟佳潔，李暉

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

1 引言

移動(dòng)智能終端的普遍應(yīng)用為用戶提供了便利的生活方式，其中基于位置服務(wù)的應(yīng)用更是受到廣大用戶的喜愛(ài)，例如，美團(tuán)外賣、大眾點(diǎn)評(píng)、微博等應(yīng)用軟件。用戶可以在智能終端安裝各種基于位置服務(wù)的應(yīng)用程序，這為用戶的日常生活帶來(lái)了無(wú)往不利的便捷。然而，用戶在享受LBS帶來(lái)的便利時(shí)，自身的隱私信息也在使用各類應(yīng)用的過(guò)程中泄露給服務(wù)提供商，惡意用戶通過(guò)獲取發(fā)送請(qǐng)求的內(nèi)容分析出用戶的隱私信息，例如，ID地址、工作、生活習(xí)慣甚至健康狀況。為了保證用戶在享有服務(wù)的同時(shí)，不泄露用戶個(gè)人的隱私信息，保護(hù)移動(dòng)用戶的位置信息已經(jīng)成為當(dāng)下眾多學(xué)者們研究的課題之一。

現(xiàn)有的隱私保護(hù)方案主要分為2類，基于可信匿名中心的隱私保護(hù)方案[1]和基于移動(dòng)終端的隱私保護(hù)方案[2～4]。利用可信匿名中心來(lái)完成用戶和服務(wù)提供商之間的交互，減少了移動(dòng)終端在計(jì)算和存儲(chǔ)上的壓力，然而可信匿名中心成為系統(tǒng)性能和安全性的瓶頸，從而無(wú)法避免單點(diǎn)泄露的問(wèn)題。當(dāng)下移動(dòng)終端不斷智能化，在處理能力和存儲(chǔ)能力都有著跨越式的提高，能夠高效、準(zhǔn)確地完成基本的處理、計(jì)算和存儲(chǔ)任務(wù)，實(shí)現(xiàn)相應(yīng)的功能，相比之下，沒(méi)有可信匿名中心的參與，基于可信匿名終端的方案有效地避免了單點(diǎn)泄露問(wèn)題，在隱私保護(hù)方面有著更明顯的優(yōu)勢(shì)。根據(jù)隱私保護(hù)方案技術(shù)的不同，主要分為位置偏移和模糊技術(shù)[5,6]、空間匿名技術(shù)[7,8]、群組協(xié)作技術(shù)[9,10]以及基于密碼學(xué)技術(shù)的隱私保護(hù)方案[11,12]。其中位置偏移和模糊技術(shù)的安全性較低、執(zhí)行簡(jiǎn)單，群組協(xié)作技術(shù)需要較高的假設(shè)前提，而密碼學(xué)技術(shù)較高的安全性需要依靠強(qiáng)大的計(jì)算處理能力，并且十分耗時(shí)。綜合考慮，空間匿名技術(shù)避免了較高的計(jì)算量和較低的安全性等弊端，能夠在用戶的智能終端實(shí)現(xiàn)較高的隱私保護(hù)，包含位置隱私和查詢隱私。相較于位置隱私，查詢隱私是通過(guò)用戶發(fā)送的查詢內(nèi)容來(lái)分析、推斷，進(jìn)而得到用戶潛在的隱私信息，查詢內(nèi)容背后潛在的用戶隱私則被視為查詢隱私。例如，用戶查詢附近的醫(yī)院，那么該用戶很有可能是一名病患。在移動(dòng)社交網(wǎng)絡(luò)中，用戶的查詢隱私和位置隱私都是現(xiàn)有隱私保護(hù)方案需要考慮、設(shè)計(jì)來(lái)實(shí)現(xiàn)保護(hù)的方面。

在隱私保護(hù)方案中，背景信息的存在成為攻擊者推斷用戶真實(shí)信息的一項(xiàng)必不可少的條件，然而有些方案并未考慮背景信息的存在[13]，或不全面地考慮背景信息[7,8]，單一考慮地圖中的歷史查詢概率，而忽略了在每個(gè)特定時(shí)間點(diǎn)的概率分布情況。從而為攻擊者提供了可乘之機(jī)，通過(guò)分析、推斷背景信息和發(fā)布的請(qǐng)求信息之間的關(guān)聯(lián)，得到隱藏在請(qǐng)求信息后的用戶隱私。因此，在設(shè)計(jì)隱私保護(hù)方案時(shí)，背景信息的存在是不容忽略的。

基于偽位置生成的隱私保護(hù)方案，即時(shí)空關(guān)聯(lián)的隱私保護(hù)方案，利用空間匿名技術(shù)來(lái)保護(hù)用戶的位置信息，輕量級(jí)的算法能夠成功并高效地運(yùn)行在移動(dòng)智能終端，從而很好地避免了可信匿名中心的存在和單點(diǎn)泄露問(wèn)題。此方案首先利用維諾多邊形將地圖分割為若干個(gè)多邊形，進(jìn)而通過(guò)用戶的移動(dòng)模型來(lái)預(yù)測(cè)用戶在下一個(gè)時(shí)間段可能出現(xiàn)的位置，并通過(guò)該位置的POI（point of interest）來(lái)決定前一時(shí)刻的請(qǐng)求內(nèi)容。本文創(chuàng)新點(diǎn)共分為以下3個(gè)方面。

1) 區(qū)別于現(xiàn)有方案，不僅考慮了背景信息的存在，同時(shí)分別考慮了在不同的時(shí)間點(diǎn)上每一個(gè)位置的查詢概率。

2) 考慮時(shí)空關(guān)聯(lián)性，避免了攻擊者通過(guò)分析在特定時(shí)間點(diǎn)發(fā)送請(qǐng)求的可能性以及移動(dòng)用戶在特定位置發(fā)送請(qǐng)求的合理性來(lái)推斷用戶的隱私信息。

3) 通過(guò)分析計(jì)算數(shù)據(jù)集Geolife得到用戶在相鄰時(shí)間段可能前進(jìn)的位置，預(yù)測(cè)用戶在下一個(gè)時(shí)間段可能出現(xiàn)的位置，從而決定前一個(gè)時(shí)間段的查詢內(nèi)容。這一創(chuàng)新點(diǎn)成功地考慮了查詢內(nèi)容和位置之間的可行性，提高了偽位置對(duì)攻擊者的混淆程度。

2 相關(guān)工作

本節(jié)根據(jù)是否有可信匿名中心的參與，分析、介紹現(xiàn)有的隱私保護(hù)方案中使用的技術(shù)以及存在的問(wèn)題。

2.1 基于可信匿名中心方案

目前，在基于位置服務(wù)的隱私保護(hù)方案中，大多數(shù)的方案都需要依靠可信匿名中心的參與來(lái)完成隱私保護(hù)的全過(guò)程。k-匿名技術(shù)是最為廣泛應(yīng)用的一項(xiàng)技術(shù)，其中將用戶真實(shí)的位置信息和k?1個(gè)虛假的用戶信息發(fā)送給移動(dòng)服務(wù)提供商，在暴露給服務(wù)提供商的位置信息中保證用戶的真實(shí)位置信息和其他的虛假位置信息不可區(qū)分，從而實(shí)現(xiàn)對(duì)位置信息的保護(hù)[1,14]。l-多樣性[15]作為k-匿名的一種擴(kuò)展，要求隱匿區(qū)域內(nèi)至少包含一種隱私信息?？尚拍涿行慕橛谝苿?dòng)用戶和服務(wù)提供商之間，移動(dòng)用戶將信息發(fā)送到可信匿名中心進(jìn)行匿名處理，然后將匿名處理后的信息發(fā)送給服務(wù)提供商來(lái)?yè)Q取服務(wù)信息。Beresford等[16]提出了Mixzone的概念，在Mixzone中的用戶不需要更新自己的位置信息，從而不需要和服務(wù)提供商進(jìn)行交互，避免了多次交互泄露的隱私信息。Palanisamy等[17]利用Mixzone的概念，在用戶離開(kāi)Mixzone時(shí)對(duì)其進(jìn)行假名更換，攻擊者不能通過(guò)分析進(jìn)入Mixzone和離開(kāi)該區(qū)域的關(guān)聯(lián)性來(lái)獲取用戶的真實(shí)信息。Meyerowitz等[18]通過(guò)緩存用戶請(qǐng)求的服務(wù)信息來(lái)避免和服務(wù)提供商的多次交互，通過(guò)減少交互次數(shù)保護(hù)了用戶的隱私信息。Xu等[19]提出了一種基于感知的隱私保護(hù)模型，利用信息熵來(lái)衡量位置區(qū)域的受歡迎程度，并且利用四叉樹(shù)來(lái)分離請(qǐng)求信息和特定用戶，針對(duì)不同的分類提供個(gè)性化的隱私保護(hù)。

2.2 非基于匿名中心方案

隨著科技的進(jìn)步，當(dāng)下的移動(dòng)智能終端具有強(qiáng)大的計(jì)算、處理能力和大容量的存儲(chǔ)空間。近幾年來(lái)，基于移動(dòng)終端的隱私保護(hù)方案也被不斷提出[3,20,21]。相較基于匿名中心的隱私方案，此類方案的架構(gòu)中不需要任何可信第三方的參與，完全避免了可信第三方潛在的安全和性能隱患。CAP[2]利用四叉樹(shù)對(duì)地圖進(jìn)行細(xì)粒度的劃分，并利用Hilbert曲線對(duì)地圖進(jìn)行遍歷。該方案考慮了道路的多樣性，但并未將移動(dòng)用戶的運(yùn)動(dòng)模式考慮在內(nèi)。SMILE[3]利用k-匿名技術(shù)來(lái)度量用戶的隱私程度，在基于遇見(jiàn)的位置服務(wù)中，通過(guò)獲取用戶位置信息前綴的散列值，從而避免了將用戶的個(gè)人信息泄露給服務(wù)提供商。Fawaz等[22]提出了一個(gè)新型的隱私保護(hù)框架，能夠針對(duì)每一個(gè)應(yīng)用程序來(lái)實(shí)現(xiàn)細(xì)粒度的隱私保護(hù)，并且不需要依靠任何的可信第三方。

3 準(zhǔn)備工作

為了方便后文的閱讀和理解，本節(jié)主要介紹文中所需要用到的一些基本概念、研究動(dòng)機(jī)和基本解決方案。

3.1 基本概念

1) 查詢內(nèi)容

移動(dòng)用戶發(fā)送服務(wù)請(qǐng)求給服務(wù)提供商，其中主要包含用戶的身份信息、位置信息、查詢內(nèi)容和時(shí)間戳。這不僅保護(hù)了用戶的位置信息，同時(shí)避免了查詢內(nèi)容所導(dǎo)致的隱私泄露問(wèn)題，即查詢隱私[23]。在現(xiàn)有的隱私保護(hù)方案中，將用戶的隱私主要分為位置隱私和查詢隱私。例如，用戶請(qǐng)求附近 1 km以內(nèi)的加油站，其中加油站被視為查詢內(nèi)容，查詢內(nèi)容所代表的隱私稱為查詢隱私。攻擊者通過(guò)分析用戶發(fā)出的查詢內(nèi)容，推斷出用戶的隱私信息，相較位置隱私，查詢隱私同樣需要保護(hù)。

2) 位置信息

移動(dòng)用戶在發(fā)送請(qǐng)求服務(wù)時(shí)，根據(jù)服務(wù)需求，需要將用戶當(dāng)前所處的位置信息發(fā)送給相關(guān)的服務(wù)提供商，以便獲取相關(guān)的服務(wù)信息。本文提到的位置信息是指在請(qǐng)求服務(wù)時(shí)，用戶所處的位置坐標(biāo)。用戶利用智能終端中的GPS定位模塊獲取當(dāng)前的位置坐標(biāo)，隱私保護(hù)方案旨在保護(hù)用戶的位置信息不被泄露，從而避免非法用戶推測(cè)出用戶的真實(shí)敏感信息。

3) POI

POI指的是在某一個(gè)位置點(diǎn)區(qū)別于坐標(biāo)信息來(lái)辨別該位置的點(diǎn)。例如，Alice在麥當(dāng)勞請(qǐng)求周圍公交車站，那么麥當(dāng)勞就是該位置的POI，而該位置的坐標(biāo)則是位置信息，公交車站是查詢內(nèi)容。

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

4) 背景信息

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

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

現(xiàn)有的隱私保護(hù)方案忽略了背景信息的存在，從而給用戶的隱私帶來(lái)的潛在威脅，即使某些方案考慮到背景信息也可能會(huì)被惡意用戶獲取來(lái)推斷用戶的隱私，但是通常都只單一地考慮某一個(gè)位置的歷史查詢概率，而忽略了在不同時(shí)間點(diǎn)之間、時(shí)間和空間之間存在的關(guān)聯(lián)性。通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)解釋研究動(dòng)機(jī)，如圖1所示。選取地圖的一部分，其中，[0, 20]×[0, 20]是用戶的請(qǐng)求區(qū)域，虛線表示地圖中的道路情況，12∶00am，用戶Alice位于位置(5, 5)?；诒尘靶畔⑺芴峁┑牡缆沸畔?，與該區(qū)域連通的道路有且只有 2條，它們分別是[0,10]×[0,10]→[10,20]×[0,10]和[0,10]×[0,10]→[0,10]×[10,20]，其中第一條路通往餐館（如肯德基、麥當(dāng)勞、星巴克），第二條路通往酒吧。首先，在偽位置生成的隱私保護(hù)方案中，如果選取的偽位置是一間酒吧，那么在時(shí)間戳為12∶00am的時(shí)候發(fā)送請(qǐng)求給服務(wù)提供商，攻擊者則可以根據(jù)在該時(shí)間酒吧不營(yíng)業(yè)的原因?qū)⒃搨挝恢眠^(guò)濾掉，因此，需要考慮時(shí)間和位置所代表的POI之間的可行性。其次，為了保護(hù)Alice的位置信息，將 Alice的隱身空間設(shè)置為[0,10]×[0,10]，基于用戶的心理，在用戶想要請(qǐng)求相應(yīng)的服務(wù)時(shí)，一定是在下一個(gè)時(shí)間點(diǎn)或?qū)?lái)某個(gè)時(shí)間段要去的位置，那么在該位置發(fā)送的查詢內(nèi)容一定是在時(shí)間允許情況下可達(dá)的，即用戶極有可能請(qǐng)求附近存在的POI。在圖1右側(cè)，用戶將要去的地方一定是他的請(qǐng)求區(qū)域[0, 20]×[0, 20]中，而非區(qū)域以外的位置，那么用戶的查詢內(nèi)容應(yīng)該存在于該查詢區(qū)域。同理，如果選取的偽位置周圍的可達(dá)范圍內(nèi)只有餐館和酒吧2種POI，那么如果發(fā)送的查詢內(nèi)容為醫(yī)院，則會(huì)被攻擊者判定該位置為虛假位置，即需要考慮到查詢內(nèi)容和所選取位置之間的關(guān)聯(lián)性。

現(xiàn)有的基于偽位置生成的隱私保護(hù)方案總是根據(jù)概率分布來(lái)選取相應(yīng)的偽位置，而并未考慮到在不同的時(shí)間點(diǎn)所選取到的偽位置并不具有足夠的說(shuō)服力，即午餐時(shí)間，在酒吧發(fā)送請(qǐng)求的可能性遠(yuǎn)小于在辦公室請(qǐng)求周邊餐館的可能性。同時(shí)，用戶請(qǐng)求身邊并不存在的POI也將會(huì)被攻擊者判定為虛假的位置，即午餐時(shí)間，在城南請(qǐng)求城北的公園的可能性很小。

3.3 基本解決方案

根據(jù)以上提出的研究動(dòng)機(jī)，提出了基于偽位置生成的時(shí)空關(guān)聯(lián)的隱私保護(hù)方案，能夠更好地保護(hù)用戶的位置隱私和查詢隱私。該方案包含了2個(gè)算法，算法1是地圖分割算法，不同于現(xiàn)有方案中單一考慮地圖中的查詢概率，而忽略了在特定時(shí)間點(diǎn)不同的位置具有不同的查詢概率的情況，算法1首先從Google地圖中的popular time中獲取到在特定的時(shí)間段某一個(gè)具體位置的概率情況，然后通過(guò)在特定時(shí)段發(fā)送請(qǐng)求的可能性對(duì)地圖進(jìn)行第一層的過(guò)濾，得到了若干個(gè)位置點(diǎn)。接著，基于第一層過(guò)濾后的位置點(diǎn)，利用維諾圖將地圖分割為若干個(gè)不規(guī)則的維諾多邊形，每一個(gè)維諾多邊形中有且只有一個(gè)離散的位置存在（維諾圖的性質(zhì)）。通過(guò)選取與用戶所在的維諾多邊形共邊的維諾多邊形，保證了待選的離散位置單元能夠盡可能遠(yuǎn)，且與用戶的位置單元不相鄰。從而過(guò)濾掉和用戶所在的維諾多邊形公共邊的位置單元，并將算法1最后得到的位置單元集作為算法2的輸入。

算法2為偽內(nèi)容生成算法，其中包含選取偽位置和偽查詢內(nèi)容。為了避免攻擊者分析用戶在相鄰時(shí)間段的位置可達(dá)性，通過(guò)數(shù)據(jù)集 Geolife得到轉(zhuǎn)移矩陣來(lái)推測(cè)每一個(gè)位置單元在相鄰的2個(gè)時(shí)間點(diǎn)之間的移動(dòng)概率，通過(guò)選取概率高的位置單元所處的POI為前一時(shí)刻想要請(qǐng)求的查詢內(nèi)容，作為偽查詢內(nèi)容，結(jié)合算法1所得到的位置單元集合，尋找偽查詢位置相臨近的位置作為偽位置單元。最終，用戶將自身的真實(shí)信息和偽位置以及偽查詢內(nèi)容一起發(fā)送給服務(wù)提供商來(lái)?yè)Q取服務(wù)。

3.4 移動(dòng)模型

利用二維坐標(biāo)空間來(lái)表示地圖信息，將地圖劃分為M個(gè)大小相同的單元，即其中，。如圖2所示，單元C4的向量可表示為

X= [4 ,6]T，其中X[1] = 4,X[2 ]= 6。

圖2 二維坐標(biāo)空間

根據(jù)用戶的移動(dòng)模型，利用隱馬爾可夫模型[24,25]來(lái)描述用戶在時(shí)間不同時(shí)位置的關(guān)聯(lián)性。用戶將處理過(guò)的位置信息暴露給服務(wù)提供商，攻擊者通過(guò)觀測(cè)發(fā)送出的信息對(duì)用戶的真實(shí)信息進(jìn)行推斷。

在時(shí)間點(diǎn)t，利用向量tP來(lái)表示用戶位置的概率分布，其中，表示向量Pt中的第i個(gè)元素，Ci∈Map。通過(guò)轉(zhuǎn)移矩陣MA來(lái)定義用戶從一個(gè)位置移動(dòng)到另一個(gè)位置概率，在矩陣MA中存在元素maij，其中，i表示矩陣中的第i行，j表示矩陣中的第j列。

已知t?1時(shí)刻用戶的位置向量Pt?1，從而通過(guò)轉(zhuǎn)移矩陣可得知t時(shí)刻用戶的位置向量Pt，Pt=Pt?1MA。假設(shè)當(dāng)前地圖上存在5名移動(dòng)用戶，如圖2所示，分別位于地圖中的{C2,C4,C6,C8,C9}，則可以得到以下的概率向量。

Pt=[00.2 0 0.2 0 0.2 0 0.2 0.2 …0]

為了更好、更準(zhǔn)確地獲取轉(zhuǎn)移矩陣MA，有研究者對(duì)用戶在不同時(shí)間點(diǎn)的具體位置信息進(jìn)行了采集[26,27]，利用數(shù)據(jù)集Geolife[22]中的位置信息，計(jì)算出轉(zhuǎn)移矩陣MA。在數(shù)據(jù)集Geolife中，研究者收集了 182名用戶在北京三環(huán)內(nèi)、每隔 1～60 s所處的位置信息，其中每一個(gè)位置信息包含了經(jīng)、緯度和當(dāng)前的時(shí)間戳，歷時(shí)3年。通過(guò)該數(shù)據(jù)庫(kù)所提供的位置信息Pt?1和Pt，通過(guò)Pt=Pt?1MA可進(jìn)一步推算出矩陣，即轉(zhuǎn)移矩陣MA默認(rèn)為已知的。

根據(jù)隱馬爾可夫模型，用戶的每一個(gè)狀態(tài)取決于前面的有限狀態(tài)，即用戶在t時(shí)刻的位置取決于t?1時(shí)刻的位置信息。利用這一特性，通過(guò)轉(zhuǎn)移矩陣獲知用戶下一時(shí)刻可能出現(xiàn)的位置，并將該位置的 POI作為當(dāng)前時(shí)刻的查詢內(nèi)容。其中，轉(zhuǎn)移矩陣MA的獲取是通過(guò)現(xiàn)有數(shù)據(jù)庫(kù)的訓(xùn)練學(xué)習(xí)后得到的矩陣，能夠利用該矩陣推測(cè)得到用戶下一時(shí)刻的位置信息。

3.5 隱私度量

現(xiàn)有很多隱私保護(hù)方案采用不同的數(shù)學(xué)工具來(lái)衡量位置隱私的程度[4,7,8]，其中信息熵是最為廣泛運(yùn)用的一種隱私度量。利用信息熵作為隱私度量，具體定義如下。

定義1 已知位置j，則信息熵為

其中，指的是在時(shí)刻t，用戶在位置j處請(qǐng)求POIi時(shí)的條件概率。

因?yàn)樾畔㈧氐挠?jì)算并不需要過(guò)高的計(jì)算能力，現(xiàn)有的智能終端能夠承載信息熵的計(jì)算，從而不需要和可信第三方或其他的用戶終端進(jìn)行交互，避免了額外的風(fēng)險(xiǎn)。該隱私度量選取的位置概率不同于現(xiàn)有方案單一地考慮用戶在傳統(tǒng)的背景信息下的查詢概率，而是針對(duì)某一個(gè)特定的時(shí)間戳，位置j請(qǐng)求查詢內(nèi)容為i，其中i表示某一種特定的POI。

4 時(shí)空關(guān)聯(lián)隱私保護(hù)方案

本節(jié)詳細(xì)介紹了時(shí)空關(guān)聯(lián)隱私保護(hù)方案所包含的算法，即地圖分割算法和偽內(nèi)容生成算法，系統(tǒng)結(jié)構(gòu)如圖3所示。圖3中，用戶通過(guò)移動(dòng)終端向GPS獲取位置信息，作為算法的輸入，然后在移動(dòng)終端中對(duì)地圖進(jìn)行分割，通過(guò)維諾多邊形篩選出不相鄰的位置區(qū)域，在偽內(nèi)容生成算法中通過(guò)概率和轉(zhuǎn)移矩陣構(gòu)造偽位置請(qǐng)求，并通過(guò)移動(dòng)終端發(fā)送給LBS服務(wù)提供商。

在用戶使用LBS的相關(guān)服務(wù)時(shí)，在不同的需求和客觀條件下，為用戶選取最佳的匿名數(shù)目k，例如，在Wi-Fi條件允許的條件下，可以選取較大的k值，而在移動(dòng)數(shù)據(jù)流量時(shí)則選取較小的k值。

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

4.1 地圖分割算法

在該算法中，首先需要將地圖劃分為M個(gè)位置單元，用戶位于其中某一個(gè)位置單元。在t時(shí)刻，用戶請(qǐng)求身邊1 km以內(nèi)的POI，如圖4(a)所示，將地圖等分為8×8個(gè)區(qū)域，即M=64，每一個(gè)區(qū)域代表一個(gè)位置單元，即Map={C1,C2,… ,C64}。在圖4(a)中，每個(gè)單元中不同的灰度代表在t時(shí)刻該位置單元的查詢概率，用表示。用戶Alice位于單元C中，該單元在t時(shí)刻的查詢概率為。在t

22時(shí)刻Ci的查詢概率滿足，其中δ為閾值，并且滿足δ＞0。將選取出來(lái)的位置單元存儲(chǔ)在集合α中，該集合中的元素包含了符合要求的位置單元，即α={C3,C5,C15,C22,C24,C25,C36,C41,C43,C46,C56,C58,C61}。在圖4(b)中，選取出來(lái)的位置單元用度較高的位置單元表示。

圖4 地圖分割

維諾多邊形對(duì)地圖劃分的算法采取 plane sweep，因該算法成熟且不是重點(diǎn)，在此并不贅述，該算法的時(shí)間復(fù)雜度分析見(jiàn)第5節(jié)。

根據(jù)集合α中的位置單元構(gòu)造維諾多邊形，其中每2個(gè)相鄰的位置單元連線的中垂線構(gòu)成了|α|個(gè)維諾多邊形，并且每一個(gè)多邊形中有且僅有唯一一個(gè)離散的位置單元。根據(jù)維諾多邊形的性質(zhì)，已知一個(gè)維諾多邊形Vi，與Vi共享一條邊的維諾多邊形則是距離Vi最近的維諾多邊形，那么該多邊形內(nèi)的點(diǎn)則是距離Vi內(nèi)的離散點(diǎn)最近的點(diǎn)。在圖4(b)中，用戶Alice所位于的維諾多邊形具有5條邊，那么共用這5條邊的維諾多邊形其中的位置單元?jiǎng)t是和Alice鄰近的區(qū)域。從集合α中過(guò)濾掉這5個(gè)相鄰的多邊形，剩余的位置單元構(gòu)成集合α′，即|||'|5α?α= 。

算法1 地圖分割算法

輸入 位置信息，地圖信息

輸出α′

1) 等分地圖；

2) 選取滿足的區(qū)域；

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

4) 構(gòu)造維諾多邊形；

5) 獲知真實(shí)用戶所在的維諾多邊形；

6) 刪除具有相鄰邊的維諾多邊形；

7) 篩選過(guò)的維諾多邊形存儲(chǔ)于α中；

8)α′作為下一算法的輸入。

4.2 偽內(nèi)容生成算法

在該算法中，偽內(nèi)容主要包含了偽查詢內(nèi)容和偽位置選取，在地圖分割算法中得到的集合α′的基礎(chǔ)上，偽內(nèi)容算法需要選取合適的偽位置和偽查詢內(nèi)容。根據(jù) 3.4節(jié)，集合α′中有元 素 {C3,C22,C25,C41,C43,C56,C58,C61}，則得到 概率向量其中分別在集合α′中有元素所在的位置定值為，即。已知轉(zhuǎn)移矩陣MA和概率向量Pt，則通過(guò)Pt+1=PtMA得到t+1時(shí)刻的概率向量。通過(guò)得到的t+1時(shí)刻的概率向量Pt+1可以得知集合α′中的位置單元可能去的位置，這些位置所對(duì)應(yīng)的POI相當(dāng)于在t時(shí)刻想要請(qǐng)求的查詢內(nèi)容。

在該算法的例子中，假設(shè)k=4，需要挑k?1個(gè)位置單元，即3個(gè)位置單元作為偽位置發(fā)送給服務(wù)提供商。根據(jù)概率向量Pt+1中每個(gè)位置單元的訪問(wèn)可能性，從大到小降序選取3個(gè)位置單元存儲(chǔ)于集合β={Ca,Cb,Cc}。與地圖對(duì)照，得到集合β中每一個(gè)位置單元所對(duì)應(yīng)的POI以及和集合α'最鄰近的位置單元分別構(gòu)成偽查詢內(nèi)容POIa、POIb、POIc和偽位置Ca′ 、Cb′、Cc′ 。

最后，用戶Alice將自身的位置Ci和查詢內(nèi)容POIi構(gòu)成二元組[Ci,POIi]，同樣得到偽位置請(qǐng)求[Ca,POIa]、[Cb,POIb]、[Cc,POIc]。最后通過(guò)移動(dòng)智能終端將這4個(gè)二元組和相關(guān)信息構(gòu)造成請(qǐng)求信息，繼而發(fā)送給服務(wù)提供商來(lái)獲取相關(guān)的服務(wù)信息。

算法2 偽內(nèi)容生成算法

輸入α′，MA，k

輸出k個(gè)查詢請(qǐng)求

1) 已知用戶的位置；

2) 當(dāng)前時(shí)間為t?1；

3) 通過(guò)得到tP；

4) 選取k?1個(gè)概率向量；

5) 存儲(chǔ)于集合β中；

6) 降序排列β中元素；

7) 對(duì)應(yīng)得到相應(yīng)的POI；

8) 構(gòu)造請(qǐng)求；

9) 發(fā)送k個(gè)請(qǐng)求給LBS服務(wù)器。

5 實(shí)驗(yàn)驗(yàn)證

本節(jié)分別從性能驗(yàn)證以及隱私驗(yàn)證對(duì)所提方案的性能和安全性進(jìn)行測(cè)試和驗(yàn)證。實(shí)驗(yàn)利用Matlab在PC機(jī)（2.9 GHz 英特爾i7 CPU，8 GB內(nèi)存）上進(jìn)行模擬仿真并對(duì)方案的性能進(jìn)行實(shí)驗(yàn)驗(yàn)證。

選取北京三環(huán)內(nèi) 8 km×8 km的地圖，劃分為160×160個(gè)位置單元，每個(gè)位置單元的大小為50×50的矩形。實(shí)驗(yàn)中參數(shù)k指的是k-匿名中發(fā)送給服務(wù)提供商的請(qǐng)求數(shù)量，選取范圍為[3,20]。參數(shù)δ是地圖分割算法中的閾值。

5.1 性能驗(yàn)證

1) 位置單元的數(shù)量與集合α/執(zhí)行時(shí)間的關(guān)系

在地圖分割算法中，需要對(duì)地圖中的位置單元進(jìn)行過(guò)濾，從而所劃分的位置單元越多執(zhí)行算法所消耗的時(shí)間也就越多；隨著地圖中位置單元的數(shù)量增加，在構(gòu)造維諾多邊形時(shí)需要計(jì)算的離散點(diǎn)也就逐漸增加，故而最終得到的集合α的大小也隨著地圖劃分的粒度逐漸增加，具體結(jié)果如圖5所示，在該實(shí)驗(yàn)中選取參數(shù)k=5。在地圖劃分算法中，避免用戶參與過(guò)多復(fù)雜的過(guò)程，為了實(shí)現(xiàn)最簡(jiǎn)便的操作、最合理的隱私保護(hù)力度，地圖的粒度由系統(tǒng)根據(jù)用戶所需要的k值的大小自動(dòng)地匹配出相應(yīng)的粒度。其中用戶所需要的k值和用戶所處的Wi-Fi環(huán)境相關(guān)，由系統(tǒng)自動(dòng)選取，不需要用戶參與，大大簡(jiǎn)化了操作，方便了用戶。

圖5 隨位置單元的數(shù)量不同，α與執(zhí)行時(shí)間的變化情況

2) 參數(shù)δ與通信開(kāi)銷/執(zhí)行時(shí)間的關(guān)系

方案利用的是偽位置生成算法，發(fā)送給服務(wù)提供商的請(qǐng)求信息的條數(shù)取決于參數(shù)k的值，隨著參數(shù)δ的變化，所發(fā)送給服務(wù)提供商的信息條數(shù)是不變的，通信開(kāi)銷不隨δ的變化而變化。在算法的執(zhí)行時(shí)間中，參數(shù)δ的值越大，則對(duì)應(yīng)集合α中的元素就越多，從而在偽位置生成算法中的計(jì)算元素則越多，故而隨著δ的增加，算法的執(zhí)行時(shí)間不斷增加，具體變化如圖6所示。

圖6 隨δ不同，通信開(kāi)銷和執(zhí)行時(shí)間的變化情況

3) 時(shí)間與α/執(zhí)行時(shí)間的關(guān)系

考慮時(shí)間和空間的關(guān)系，在現(xiàn)實(shí)生活中，從0∶00開(kāi)始一直到 24∶00，移動(dòng)用戶的運(yùn)動(dòng)模式不同，從而在不同的時(shí)間段有明顯的概率分布，根據(jù)數(shù)據(jù)集中不同時(shí)間對(duì)應(yīng)的峰值和低谷決定數(shù)據(jù)集α的大小，如圖7(a)所示。然而對(duì)于執(zhí)行時(shí)間則沒(méi)有明確的變化，因?yàn)榈貓D的位置單元數(shù)目一定，δ越大則執(zhí)行時(shí)間會(huì)增加，而在不同時(shí)間點(diǎn)的執(zhí)行時(shí)間并不會(huì)有明顯的變化，如圖7所示。

圖7 隨時(shí)間不同，α和執(zhí)行時(shí)間的變化情況

4) 構(gòu)造維諾多邊形的算法復(fù)雜度

構(gòu)造維諾多邊形的方法分為定義法（intersect of halfplanes）、增量（incremental）算法、分治法、plane sweep算法。采用的是plane sweep的方法，該方法在構(gòu)造維多諾多邊形可以歸約為n個(gè)實(shí)數(shù)的排序問(wèn)題，則實(shí)現(xiàn)該算法的時(shí)間計(jì)算復(fù)雜度為O(nlogn)，同時(shí)該算法在現(xiàn)有的4種算法中具有最優(yōu)的完成效果。

5.2 隱私驗(yàn)證

通過(guò)比較所提隱私保護(hù)方案和現(xiàn)有的偽位置生成算法隱私保護(hù)方案根據(jù)參數(shù)k的變化引起泄露概率的變化，為了保證可比性，選取同時(shí)保護(hù)位置隱私和查詢隱私相類似的隱私保護(hù)方案，故而比較了Dummy-Q[28]和TTcloak[29]2個(gè)方案，其中最優(yōu)方案是在理論上的最優(yōu)值。該方案發(fā)送給服務(wù)提供商的信息中每一個(gè)位置都會(huì)有不同的查詢內(nèi)容，圖 8比較了泄露概率隨著參數(shù)k的變化趨勢(shì)，隨著參數(shù)k的增加泄露概率逐漸降低，因?yàn)楸┞对蕉嗟恼?qǐng)求，導(dǎo)致攻擊者越難分析出真實(shí)的信息。圖9比較了最優(yōu)方案和隨機(jī)方案的隱私度量，因?yàn)殡[私度量涉及參數(shù)，并未有其他方案涉及該查詢概率，故這2個(gè)方案的隱私度量不會(huì)隨k的變化而變化。在 TTcloak[29]方案中，為了選取相互不相鄰的偽位置，將隱身區(qū)域劃分為4等份，進(jìn)而在每個(gè)等分的區(qū)域選取偽位置。當(dāng)k的取值過(guò)大時(shí)，在等分線附近容易出現(xiàn)偽位置過(guò)于接近的情況。該方案利用維諾多邊形對(duì)地圖進(jìn)行劃分，利用維諾多邊形的性質(zhì)避免了鄰近位置的選取，不會(huì)出現(xiàn)選取的位置處于鄰近區(qū)域的情況。

圖8 泄露概率隨參數(shù)k的變化趨勢(shì)

圖9 隱私度量隨參數(shù)k的變化趨勢(shì)

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

在基于位置服務(wù)中，提出了一種時(shí)空關(guān)聯(lián)的隱私保護(hù)方案，包含了2個(gè)算法，即地圖分割算法和偽內(nèi)容生成算法。地圖分割算法利用維諾圖將地圖劃分為多個(gè)維諾多邊形，并且每一個(gè)多邊形中有且僅有一個(gè)離散點(diǎn)，偽內(nèi)容生成算法利用移動(dòng)模型預(yù)測(cè)用戶在相鄰時(shí)間點(diǎn)中將要去的位置來(lái)選擇前一個(gè)時(shí)間的查詢內(nèi)容，從而有效地避免了時(shí)空關(guān)聯(lián)可能會(huì)導(dǎo)致的隱私泄露問(wèn)題，同時(shí)保護(hù)了用戶的位置隱私和查詢隱私。最后，本文通過(guò)詳細(xì)的性能和安全性實(shí)驗(yàn)驗(yàn)證了所提方案的有效性和安全性。

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

[2] PINGLY A, YU W, ZHANG N, FU X, et al. Cap∶ a context-aware privacy protection system for location-based services[C]// ICDCS.2009∶ 49-57.

[3] LI X, ZHANG C, JUNG T, QIAN J, et al. Graph-based privacy-preserving data publication[C]//INFOCOM.2016.

[4] CHEN Z, HU X, JU X, et al. Lisa∶ location information scrambler for privacy protection on smartphones[C]//CNS. 2013.

[5] ANDRES M, BORDENABE N, CHATZIKOKOLAKIS K, et al.Geo-indistinguishability∶ differential privacy for location-based systems[C]// CCS. 2013.

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

[7] NIU B, LI Q, ZHU X, et al. Achievingk-anonymity in privacy-aware location-based services[C]// INFOCOM.2014.

[8] NIU B, LI Q, ZHU X, et al. Enhancing privacy through caching in location-based services[C]// INFOCOM. 2015.

[9] SHOKRI R, THEODORAKOPOULOS G, PAPADIMITRATIS 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.

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

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

[12] PAULET R, KAOSAR M, 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.

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

[14] MOKEL M, CHOW C, AREF W. The new casper∶ query processing for location services without compromising privacy[J]. The IEEE VLDB Journal 2006.

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

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

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

[18] MEYEROWITZ J, CHOUDHURY R. Hiding stars with fireworks∶location privacy through camouflage[C]//MobiCom.2009.

[19] XU T, CAI T. Feeling-based location privacy protection for location-based services[C]//CCS. 2009.

[20] MONTAZERI Z, HOUMANSADR A, PISHRO H. Achieving perfect location privacy in wireless devices using anonymization[J]. IEEE Transactions on Information Forensics and Security, 2017,PP (99)∶ 1.

[21] WANG X, PANDE A, ZHU J, et al. Stamp∶ enabling privacy-preserving location proofs for mobile users[J]. IEEE/ACM Transactions on Networking, 2016,24(6)∶3276-3289.

[22] FAWAZ K, SHIN K. Location privacy protection for smartphone users[C]//CCS. 2014.

[23] SHOKRI R, THEODORAKOPOULOS G, TRONCOSO C, et al.Protecting location privacy∶ optimal strategy against localization attacks[C]//CCS. 2012.

[24] GOTE M, NATH S, GEHRKE J. Maskit∶ privately releasing user context streams for personalized mobile applications[C]//SIGMOD. 2012.

[25] SHOKRI R, THEODORAKOPOULOS G, BOUDEC J, et al. Hubaux.Quantifying location privacy[C]//SP. 2011.

[26] ZHENG Y, XIE X, MA W. Geolife∶ a collaborative social networking service among user, location and trajectory[C]//Data Eng. Bull.2010.

[27] CHO E, MYERS S, LESKOVEC J. Friendship and mobility∶ user movement in location-based social networks[C]//KDD. 2011.

[28] PINGLEY A, ZHANG N, FU X, et al. Protection of query privacy for continuous location based services[C]// INFOCOM.2011.

[29] NIU B, ZHU X, LI W, et al. A personalized two-tier cloaking scheme for privacy aware location-based services[C]//ICNC.2015.