丁婷婷，陳家明，方賢進，楊高明，余方超

(1.安徽現(xiàn)代信息工程職業(yè)學(xué)院信息工程系，安徽 淮南 232001; 2.安徽理工大學(xué)計算機科學(xué)與工程學(xué)院，安徽 淮南 232001)

近年來，由于移動端(如智能手機、車載GPS)以及通信網(wǎng)絡(luò)的發(fā)展，使基于位置的服務(wù)(Location Based Service，LBS)廣泛應(yīng)用于人們的生活中。瑞典市場研究公司Berg Insight發(fā)布的報告預(yù)測，全球LBS市場規(guī)模將以22.5%的復(fù)合年增長率(CAGR)從2014年的103億歐元增加至2020年的348億歐元[1]。LBS有如此大的市場需求，但同時也存在著隱私泄露的問題，例如，用戶利用手機查詢“離我最近的醫(yī)院”，如果查詢請求被攻擊者獲取，用戶的位置隱私可能會泄露。因此，在基于位置的服務(wù)中如何保護用戶的位置隱私成為目前研究的熱點。

目前，主要的位置隱私保護方法可以分為時空偽裝[2]、假位置[3]、假名[4]、空間加密[5]等。時空偽裝是用一片區(qū)域來代替用戶的精確位置，位置k-匿名就是一種典型的時空偽裝算法；假位置是指查詢用戶用一個代理用戶的位置來代替自己真實位置向服務(wù)器發(fā)出查詢請求，其服務(wù)質(zhì)量與查詢用戶位置和代理用戶位置的距離成反比；假名技術(shù)是用一個虛假的用戶名來代替真實的身份標(biāo)識，使攻擊者不能將LBS查詢和真正的用戶聯(lián)系起來；空間加密技術(shù)是指用某種加密協(xié)議對用戶的位置信息進行加密，使攻擊者不能破解出用戶的真實位置信息。然而這些位置隱私保護技術(shù)對用戶的位置隱私起到怎樣的保護作用或者位置隱私保護的強度如何，則需要用隱私的度量結(jié)果來評估。這種度量結(jié)果一方面可以為位置隱私保護算法的設(shè)計提供參考，另一方面也可以讓使用LBS服務(wù)的用戶了解其位置隱私泄露的風(fēng)險。因此，對位置隱私保護算法度量的研究具有一定的意義。

1 相關(guān)工作

對位置隱私保護算法度量的研究最早是從對匿名系統(tǒng)的匿名性度量開始的。近年來，學(xué)者們針對不同的位置隱私保護算法，提出很多不同的度量方法。

k-匿名是度量位置隱私保護算法保護強度的常用方法，它是指查詢用戶的位置被泛化為k個用戶的位置區(qū)域，攻擊者不能從區(qū)域中唯一識別查詢發(fā)出者的位置。k值越大，攻擊者識別出查詢發(fā)出者的可能性就越小，k值越小，則情況相反，因此可以用k值的大小來度量位置隱私保護算法的隱私保護水平。但是，林欣等人指出當(dāng)攻擊者收到連續(xù)的一組快照時，匿名區(qū)域中用戶發(fā)出查詢請求的概率不再相等，攻擊者會選擇概率最大的用戶作為查詢請求的發(fā)出者[6]。所以k-匿名只適合單點位置隱私的度量[7]。文獻[8]對k-匿名方法作出改動后用來度量軌跡隱私，即在客戶-服務(wù)器系統(tǒng)結(jié)構(gòu)的基礎(chǔ)上使用k-匿名度量，使其更加實用。

信息熵[9]是量化不確定性的重要工具。Diaz和Serjantov首先用信息熵度量匿名通信系統(tǒng)的匿名性。后來，信息熵被廣泛應(yīng)用于位置隱私的度量中，這種度量方法將攻擊者猜測用戶的真實位置或軌跡看成隨機變量X，X的概率記為p(x)。用公式(1)或者其變形來度量位置隱私和查詢隱私。

(1)

文獻[10]人提出一種基于信息熵的隱私度量方法用來度量V2X應(yīng)用系統(tǒng)中的位置隱私。文獻[11]提出用條件熵和互信息來度量用戶的查詢隱私。文獻[12]總結(jié)了幾種隱私度量的模型并提出了基于信息熵的度量方法。

此外，文獻[13]提出用攻擊者計算用戶真實位置出錯的概率來度量位置隱私。文獻[14]提出了基于貝葉斯條件概率的隱私度量模型。

以上的位置隱私度量方法大都忽略了攻擊者的背景知識，而攻擊者的背景知識和位置隱私的度量是密切相關(guān)的。

文獻[15]是一種基于四叉樹的位置隱私保護算法，它采用可信的第三方匿名服務(wù)器的系統(tǒng)結(jié)構(gòu)對用戶的位置隱私進行匿名化處理，將用戶的隱私保護需求表示為生成匿名區(qū)域的最小面積a以及匿名區(qū)域中用戶的個數(shù)n。其方法為：將用戶所在區(qū)域劃分成一個個網(wǎng)格，檢查用戶所在網(wǎng)格參數(shù)是否滿足用戶隱私需求，若不滿足，則將匿名區(qū)域擴大到相鄰網(wǎng)格，若仍不滿足，再將匿名區(qū)域擴大到父類網(wǎng)格。這樣可以使發(fā)出查詢的用戶被攻擊者識別出的概率不大于1/n。但是，該方法在合并網(wǎng)格時，沒有考慮相鄰網(wǎng)格的用戶分布情況，同時也可能會返回空間更大的父類網(wǎng)格，因而造成獲得的匿名區(qū)域中存在較大的冗余區(qū)域。文獻[16]提出改進GLKA算法來減小冗余區(qū)域，即根據(jù)相鄰網(wǎng)格的用戶密度生成匿名區(qū)域，再根據(jù)發(fā)出查詢的用戶所在網(wǎng)格距離匿名區(qū)域邊界行(或列)的距離以及邊界行(或列)中的用戶密度進行冗余邊界去除，最終生成冗余區(qū)域更小的匿名區(qū)域。

本文以GLKA算法為例，提出一種位置隱私泄露的度量方法，將發(fā)出查詢請求用戶的準(zhǔn)確位置泛化成至少包含k個用戶的區(qū)域，評估其位置被攻擊者識別出來的風(fēng)險。該方法融入了攻擊者的背景知識，用來度量攻擊者在具有背景知識的情況下，發(fā)出查詢請求用戶位置時的隱私泄露情況。

2 位置隱私度量方法

2.1 位置隱私保護模型

建立隱私保護模型是進行隱私泄漏度量中必不可少的環(huán)節(jié)，以下是基于GLKA的位置隱私保護模型。

在圖1(a)中，用戶u向LBS服務(wù)器發(fā)出查詢請求，并要求形成的匿名區(qū)域(AR)中用戶數(shù)量不少于k(假設(shè)k=6)；用戶的查詢請求和所在位置被提交到第三方匿名服務(wù)器，其所在空間被劃分成一個個網(wǎng)格，如圖1(b)所示；計算出用戶u所在單元格的四個相鄰區(qū)域中用戶的密度，將用戶密度最大的區(qū)域合并入AR形成新的AR，如果用戶密度最大的區(qū)域不止一個，則按照上、下、左、右的順序選擇一個相鄰區(qū)域加入AR。之后，判斷形成的AR是否是矩形以及是否滿足用戶的隱私需求，若AR不是矩形，需要將新的AR轉(zhuǎn)化成最小限定矩形(MBR)，若AR不滿足用戶隱私需求，需要選擇下一個相鄰區(qū)域加入AR，重復(fù)這一過程直到最終形成滿足用戶隱私需求k=6的AR，如圖1(c)；最后計算用戶所在單元格離四個邊界行(或列)的距離和四個邊界行(或列)的用戶密度，將其按照距離由大到小、用戶密度由低到高的順序排列，將排在第一的行(或列)去除后，若k仍然大于用戶隱私需求，形成新的AR，重新計算距離和密度，否則，去除排在第二的行(或列)，直至沒有行(或列)可去除為止。最終形成圖1(d)隱私需求k=6的最終AR。

(a)用戶u發(fā)出查詢請求 (b)用戶所在區(qū)域被網(wǎng)格化 (c)生成匿名區(qū)域(d)去除匿名區(qū)域中的冗余區(qū)域圖1 GLKA算法生成用戶匿名區(qū)域

2.2 隱私度量方法

用戶提出查詢請求后，其所在的空間S會被網(wǎng)格化，我們可以用m*n的矩陣Am*n來描述S被劃分后的用戶分布情況，矩陣中的每個元素代表著每個網(wǎng)格中的用戶數(shù)量，例如，可以用圖2中的矩陣來描述圖1(b)中的用戶分布。這樣空間S中的所有用戶數(shù)量|S|可以描述為

100010010000002010001020100010010100

圖2 用戶分布矩陣

其中aij表示用戶分布矩陣的元素。匿名區(qū)域AR初始時是發(fā)出查詢用戶所在的單元格，如果不滿足隱私需求，需合并相鄰單元格并轉(zhuǎn)化成最小限定矩形MBR，形成新的AR，若用s、t和o、p分別表示AR左下角單元格和右上角單元格的行列號，則

其中Sij表示行列號分別為i和j的單元格。在減小匿名區(qū)域的冗余區(qū)域時，需要根據(jù)AR四個邊界行(或列)中的用戶密度NUM去除行(或列)，AR邊界行中的用戶密度計算公式為

在網(wǎng)格化的過程中，如果網(wǎng)格過大，會使LBS服務(wù)器的效率變低，生成的匿名區(qū)域也很大，影響到用戶的服務(wù)質(zhì)量；網(wǎng)格很小，則會增加服務(wù)器的計算復(fù)雜度，延長響應(yīng)時間。所以，選擇合適的網(wǎng)格精度非常重要。

在攻擊者沒有任何背景知識的時候，會認(rèn)為AR中所有用戶發(fā)出查詢的可能性相等，即等于1/k’，把此時的分布看成Q(x)。但是，現(xiàn)實中，攻擊者通常都包含了一定的背景知識，例如醫(yī)療信息、地圖信息、統(tǒng)計信息甚至是有關(guān)個人的信息，所以，攻擊者通常推測AR中的用戶發(fā)出查詢的概率不相等，此時的分布看成P(x)。而KL距離(Kullback-Leibler差異)通常被用來描述兩個分布之間的差異，我們可以通過公式(2)來度量P(x)和Q(x)的差異，即實際情況下隱私信息和在攻擊者沒有任何背景知識情況下隱私信息之間的距離。

(2)

(3)

L(u)越小，說明用戶位置隱私泄露越低，反之，則越高。

(a)有無背景知識對度量結(jié)果的影響 (b)背景知識量對度量結(jié)果的影響圖3 背景知識對度量結(jié)果的影響

3 實驗設(shè)計

實驗在Windows8平臺下，用matlab仿真實現(xiàn)。實驗機器的參數(shù)為2.1 GHz Intel Core(TM)i3處理器、4GB內(nèi)存。

實驗使用Network-Based Generator of Moving Objects[17]模擬器隨機成生德國奧登堡市內(nèi)10 000個用戶位置信息，從中隨機選取100個用戶作為發(fā)出查詢用戶，模擬器的參數(shù)采用默認(rèn)設(shè)置。將地圖信息劃分成不同大小的網(wǎng)格，在不同的隱私需求下，利用GLKA算法生成發(fā)出查詢用戶的匿名區(qū)域，匿名區(qū)域中用戶發(fā)出查詢請求的概率隨機生成，利用第3節(jié)中提出的方法度量位置隱私泄露，取100個用戶度量結(jié)果的平均值作為實驗輸出，實驗結(jié)果及分析如下。

3.1 背景知識對度量結(jié)果的影響

現(xiàn)實中，攻擊者通常擁有一定的背景知識，所以將背景知識融入到度量中是非常必要的。實驗中將地圖劃分成32×32大小的網(wǎng)格，用戶的隱私需求被設(shè)置為6。通過2.2節(jié)中提出的位置隱私泄露度量方法，分析在有無背景知識和背景知識逐漸增加的情況下，對位置隱私泄露的影響。

圖3(a)是有無背景知識的情況繪制的度量結(jié)果折線圖。在無背景知識時，用戶的位置隱私泄露維持在最低水平，說明攻擊者認(rèn)為匿名區(qū)域中每個用戶發(fā)出查詢的概率是相等的；在有背景知識時，隨著時間的增加，用戶位置隱私的泄露也逐漸增加。因為隨著時間的增加，攻擊者獲得有關(guān)用戶的背景知識會越多，越有可能推測出發(fā)出查詢請求用戶的真實位置。在“0”時刻，攻擊者沒有任何背景知識，不能確定發(fā)出查詢請求用戶的具體位置，所以攻擊者認(rèn)為用戶的隱私泄露最低。而在“7”時刻，攻擊者根據(jù)背景知識確定了查詢請求的發(fā)出者，并確定了此用戶在匿名區(qū)域中的具體位置，所以從攻擊者的角度來看其位置隱私泄露最高。

從以上實驗中可以看出，用戶的位置隱私和攻擊者的背景有著非常大的關(guān)系，將背景知識考慮入度量中是必要的。

3.2 隱私需求及網(wǎng)格大小對度量結(jié)果的影響

用戶的隱私需求和不同大小的地圖網(wǎng)格也會對用戶的位置隱私泄露有影響。圖4(a)和4(b)是在將地圖劃分成32×32和128×128大小網(wǎng)格情況下，隨著隱私需求的增加，用戶位置隱私的泄露圖?？梢钥闯鲈趦煞N不同大小網(wǎng)格的情況下，用戶的位置隱私泄露都隨著隱私需求的增加而減小。這是由于隨著匿名區(qū)域中用戶的增加，攻擊者識別出查詢發(fā)出者的困難增加，用戶的位置隱私泄露隨之減小。圖4(c)和4(d)是在隱私需求為6和8的情況下，分別將地圖劃分32×32、64×64、128×128、256×256、512×512、1 024×1 024網(wǎng)格大小時，用戶的位置隱私泄露圖。地圖網(wǎng)格大小變大，意味著生成的匿名區(qū)域變大，就可能含有更多的用戶，從而降低了用戶的位置隱私泄露風(fēng)險。從實驗中可以看出隱私需求的增大和地圖劃分網(wǎng)格變大都會降低用戶的隱私泄露風(fēng)險。

(a)隱私需求對度量結(jié)果的影響 (32×32地圖網(wǎng)格) (b)隱私需求對度量結(jié)果的影響(128×128地圖網(wǎng)格)

(c)地圖網(wǎng)格大小對度量結(jié)果的影響(隱私需求為6) (d)地圖網(wǎng)格大小對度量結(jié)果的影響(隱私需求為8)圖4 隱私需求及網(wǎng)格大小對度量結(jié)果的影響

4 總結(jié)和展望

基于位置的服務(wù)(LBS)在不久的將來會有更多的應(yīng)用。對用戶位置隱私保護方法和保護方法度量的研究必定是有意義的。本文提出的度量方法考慮了攻擊者的背景知識，為位置隱私保護方法的設(shè)計者設(shè)計更優(yōu)的位置隱私保護算法提供了參考。由于背景知識多種多樣、隨著時間的推移，攻擊者背景知識的積累、攻擊者知識水平的不同、攻擊者推理能力的不同以及各種攻擊技術(shù)的發(fā)展等等，這些都給隱私的度量工作帶來了嚴(yán)峻的挑戰(zhàn)，但是，將這些因素融入到度量方法中關(guān)乎隱私度量結(jié)果的準(zhǔn)確性，是必須的，也是迫切需要實現(xiàn)的，這也是我們接下來的工作重心。