丁婷婷，陳家明，方賢進(jìn)，楊高明，余方超

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

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

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

1 相關(guān)工作

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

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

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

(1)

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

此外，文獻(xiàn)[13]提出用攻擊者計(jì)算用戶真實(shí)位置出錯(cuò)的概率來(lái)度量位置隱私。文獻(xiàn)[14]提出了基于貝葉斯條件概率的隱私度量模型。

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

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

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

2 位置隱私度量方法

2.1 位置隱私保護(hù)模型

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

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

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

2.2 隱私度量方法

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

100010010000002010001020100010010100

圖2 用戶分布矩陣

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

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

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

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

(2)

(3)

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

(a)有無(wú)背景知識(shí)對(duì)度量結(jié)果的影響 (b)背景知識(shí)量對(duì)度量結(jié)果的影響圖3 背景知識(shí)對(duì)度量結(jié)果的影響

3 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

4 總結(jié)和展望

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