張文靜，劉樵，朱輝

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

1 引言

隨著移動設(shè)備、無線網(wǎng)絡(luò)的高速發(fā)展以及先進(jìn)的感知和定位技術(shù)的出現(xiàn)，產(chǎn)生了大量的基于位置的服務(wù)（LBS,location-based services），如谷歌地圖、打車軟件Uber、Foursquare、Yelp，以及用于廣告推廣的應(yīng)用等。發(fā)布位置數(shù)據(jù)具有很高的應(yīng)用價值，為了保護(hù)用戶的位置隱私，學(xué)者們已在研究中提出大量的位置隱私保護(hù)技術(shù)。然而，對外發(fā)布的位置數(shù)據(jù)的使用者可能具有不同的使用需求、使用權(quán)限或信任等級，因此，有必要對位置數(shù)據(jù)進(jìn)行分級發(fā)布。使用權(quán)限高或信任程度高的數(shù)據(jù)使用者被認(rèn)為是高等級的使用者。高等級的數(shù)據(jù)使用者（或數(shù)據(jù)挖掘者）可以訪問數(shù)據(jù)可用性更高（即失真更低或擾動程度更低）的位置數(shù)據(jù)，而低等級的數(shù)據(jù)使用者被允許訪問的位置數(shù)據(jù)的擾動程度會更高。然而，當(dāng)前大多數(shù)的位置隱私保護(hù)機(jī)制（LPPM,location privacy protection mechanism）都將數(shù)據(jù)使用者考慮為同一等級，并未區(qū)分不同數(shù)據(jù)使用者的級別。在數(shù)據(jù)使用者都屬于同一等級的假設(shè)下，位置數(shù)據(jù)發(fā)布者通過LPPM僅生成一種具有固定隱私泄露的擾動數(shù)據(jù)，這種假設(shè)不再適用于數(shù)據(jù)使用者具有不同等級的應(yīng)用場景。一個等級分為2個級別的例子如下。某一位置服務(wù)提供商的內(nèi)部員工可能需要使用收集到的位置數(shù)據(jù)進(jìn)行數(shù)據(jù)分析，同時這些位置數(shù)據(jù)也可以被發(fā)布給外部人員使用。由于內(nèi)部員工信任等級比外部人員高，因此這些位置數(shù)據(jù)在發(fā)布給內(nèi)部人員和外部人員時，需要被提前劃分好等級。此外，與只擁有單一級別權(quán)限用戶的場景相比，具有多等級權(quán)限數(shù)據(jù)使用者的場景中存在某一數(shù)據(jù)使用者可能會通過惡意截取、共謀等方式獲取多個不同等級（即擾動程度不同）的位置數(shù)據(jù)。此時的數(shù)據(jù)使用者被視為攻擊者。攻擊者通過分析這幾種數(shù)據(jù)間的差異，能夠更加精確地推測數(shù)據(jù)擁有者的真實(shí)位置數(shù)據(jù)。

本文針對數(shù)據(jù)使用者對發(fā)布的擾動位置數(shù)據(jù)具有不同的訪問權(quán)限，在問題描述中將數(shù)據(jù)使用者分級，分析不同級別情況下的隱私泄露，設(shè)計(jì)基于信息論方法用于發(fā)布給不同權(quán)限（等級）的數(shù)據(jù)使用者位置數(shù)據(jù)的LPPM。選擇信息論中的互信息作為隱私度量方法是因?yàn)樾枰环N能夠從本質(zhì)上考慮到位置數(shù)據(jù)中先驗(yàn)知識的度量方法，而互信息則能夠非常清晰地描述這種信息。此外，本文分析了攻擊者擁有不同等級發(fā)布數(shù)據(jù)，并且能夠利用這些不同等級的發(fā)布數(shù)據(jù)來更精確地推測真實(shí)位置數(shù)據(jù)這一場景下的隱私泄露，并提出一種可能用于最小化該場景下隱私泄露的優(yōu)化方案。

2 相關(guān)工作

近年來，位置隱私的研究已成為非?；钴S的研究領(lǐng)域。大部分位置隱私保護(hù)機(jī)制都是基于位置數(shù)據(jù)的擾動來實(shí)現(xiàn)的。這種擾動技術(shù)包括假位置[1]、加密[2]、空間位置隱身[3-8]、基于差分隱私的位置擾動[9-10]等。使用假位置來代替真實(shí)位置可以保護(hù)位置隱私，但隱私保護(hù)程度和服務(wù)質(zhì)量卻依賴于真實(shí)位置和假位置之間的距離?；诩用芗夹g(shù)的位置隱私保護(hù)提供非常強(qiáng)的隱私保護(hù)程度，然而，被加密后的位置數(shù)據(jù)可以被使用的范圍僅限于具有解密能力的使用者，因此應(yīng)用場景十分受限。k-匿名技術(shù)最初被用于保護(hù)數(shù)據(jù)庫隱私[11]，然后被應(yīng)用到保護(hù)位置隱私的場景[12]。此后，基于空間位置隱身的位置隱私保護(hù)技術(shù)被廣泛研究[5,8,13]。然而，這些方案都沒有考慮位置隱私泄露的最小化問題。在數(shù)據(jù)分級發(fā)布方面，文獻(xiàn)[14]中研究了支持多級位置隱私保護(hù)的位置隱身方法，當(dāng)用戶的訪問權(quán)限更高時，允許用戶訪問的擾動位置數(shù)據(jù)的精度更高。然而，基于位置隱身技術(shù)的方法并不能從信息論的角度來最小化位置隱私泄露。

3 問題描述

本文使用隨機(jī)變量L和Vk來分別表示用戶的真實(shí)位置和發(fā)布給等級為k的數(shù)據(jù)使用者的擾動位置，l和vk分別表示這2個隨機(jī)變量的可能取值。假設(shè)數(shù)據(jù)使用者是不可信的，即其會利用擾動后的位置數(shù)據(jù)來推測用戶的真實(shí)位置信息。不同等級的數(shù)據(jù)使用者被允許訪問的位置數(shù)據(jù)擾動程度不同，等級越高的數(shù)據(jù)使用者獲得的位置數(shù)據(jù)擾動程度越小，即擾動數(shù)據(jù)更接近真實(shí)位置數(shù)據(jù)，可用性更高，反之亦然。下文中將交替使用數(shù)據(jù)擁有者和數(shù)據(jù)發(fā)布者。

定義1隱私保護(hù)等級為k時的位置隱私度量方法。當(dāng)位置數(shù)據(jù)擁有者使用隱私保護(hù)等級為k的LPPM生成擾動位置數(shù)據(jù)Vk，并發(fā)布給等級為k的數(shù)據(jù)使用者時，由擾動位置Vk導(dǎo)致的隱私泄露定義為I(L;Vk)。其中，I(L;Vk)是數(shù)據(jù)擁有者的真實(shí)位置和擾動位置之間的互信息；k取自正整數(shù)集，k越小表示等級越高。使用I(L;Vk)作為發(fā)布擾動位置數(shù)據(jù)Vk時的隱私泄露的度量方法。

定義2擾動位置的可用性度量方法。給定用戶的真實(shí)位置L和要發(fā)布給等級為k的數(shù)據(jù)使用者的擾動位置Vk，將擾動位置的可用性度量方法定義為，其中，p(l)是真實(shí)位置L的先驗(yàn)概率分布；q(vk|l)為條件概率，即LPPM；d(l,vk)是真實(shí)位置與擾動位置間的失真函數(shù)（如漢明距離或歐幾里得距離）。

命題1發(fā)布擾動位置數(shù)據(jù)Vk時的隱私?可用性折中問題。給定用戶在某一時刻的真實(shí)位置L，該時刻要發(fā)布給等級為k的不可信數(shù)據(jù)使用者的擾動位置Vk和可用性約束Dk，一個LPPMq(vk|l)在給定的可用性約束Dk的條件下達(dá)到了位置隱私的最小泄露時，這個LPPM是如下優(yōu)化問題的解

其中，I(L;Vk)是位置隱私的度量方法。

然而，在存在著多個等級數(shù)據(jù)使用者的場景下，若某一數(shù)據(jù)使用者成為具有惡意目的的攻擊者，他可能會通過惡意截取或與其他等級數(shù)據(jù)使用者共謀等方式，來獲取原本要發(fā)布給其他等級數(shù)據(jù)使用者的擾動位置數(shù)據(jù)，然后該攻擊者即可通過對多個具有不同隱私保護(hù)等級的發(fā)布數(shù)據(jù)進(jìn)行聯(lián)合分析，進(jìn)而更精確地推測真實(shí)位置數(shù)據(jù)L。將這類攻擊定義如下。

定義3多樣性攻擊。數(shù)據(jù)發(fā)布者對數(shù)據(jù)使用者信任程度不同的場景下，數(shù)據(jù)發(fā)布者會依據(jù)不同的信任程度來對數(shù)據(jù)使用者進(jìn)行等級劃分。在這種場景中會存在以下一種攻擊。設(shè)數(shù)據(jù)發(fā)布者的真實(shí)位置數(shù)據(jù)是l，其發(fā)布給不同等級數(shù)據(jù)使用者的位置數(shù)據(jù)分別為v1,v2,…,vm,…,vM，其中，m為等級序號，m值越大表示數(shù)據(jù)使用者等級越高。在這種場景中，當(dāng)?shù)燃墳閙的數(shù)據(jù)使用者成為惡意攻擊者時，其可通過惡意截取等方式獲取發(fā)布給其他等級數(shù)據(jù)使者的數(shù)據(jù)集為VM，其中，VM表示v1,v2,…,vm,…,vM中除了vm以外任意發(fā)布數(shù)據(jù)組成的集合。例如，攻擊者可獲得等級為2和等級為M的發(fā)布數(shù)據(jù)v2和vM，有VM=v2vM，然后將其根據(jù)自身權(quán)限獲取的發(fā)布數(shù)據(jù)vm與VM進(jìn)行聯(lián)合數(shù)據(jù)分析，攻擊者可以更精確地推斷出數(shù)據(jù)發(fā)布者的真實(shí)位置數(shù)據(jù)l。將這類攻擊定義為多樣性攻擊。

當(dāng)多等級隱私保護(hù)的位置數(shù)據(jù)發(fā)布中存在多樣性攻擊時，會對數(shù)據(jù)擁有者的真實(shí)位置數(shù)據(jù)l造成更多的隱私泄露。為了衡量這種隱私泄露的多少，本文提出一種基于信息論方法的用于衡量多樣性攻擊造成的隱私泄露的度量方法。

定義4多樣性攻擊隱私泄露的度量方法。設(shè)等級為m的數(shù)據(jù)使用者為惡意攻擊者，當(dāng)其獲取了多個發(fā)布給不同等級數(shù)據(jù)使用者的數(shù)據(jù)集VM后，能夠?qū)m與VM進(jìn)行聯(lián)合數(shù)據(jù)分析來推測數(shù)據(jù)擁有者的真實(shí)位置數(shù)據(jù)L，將這種攻擊對數(shù)據(jù)擁有者的真實(shí)位置數(shù)據(jù)L造成的隱私泄露定義為I(L;vm∪VM))，其中，I(L;vm∪VM)是真實(shí)位置L與數(shù)據(jù)集vm∪VM之間的互信息。

定義4提供了一種通用的、用于度量隱私保護(hù)機(jī)制在受到多樣性攻擊情況下所產(chǎn)生的隱私泄露。該度量方法可用于衡量任何能夠計(jì)算出互信息I(L;vm∪VM)的隱私保護(hù)機(jī)制的多樣性攻擊隱私泄露。第6節(jié)將詳細(xì)介紹多樣性攻擊隱私泄露的計(jì)算過程。

4 預(yù)備知識

本節(jié)介紹率失真函數(shù)的定義以及計(jì)算率失真函數(shù)的算法。率失真函數(shù)問題最初被用在有損壓縮的研究中，有損壓縮的目的是在一定失真約束條件下最小化壓縮率。注意到，命題1中的隱私?可用性折中問題與率失真問題有緊密關(guān)聯(lián)。實(shí)際上Sankar等[15]、Calmon等[16]已分別研究過這種關(guān)聯(lián)。特別地，當(dāng)分析隱私?可用性折中問題時，他們把信息速率和失真分別類比為折中問題中的信息（隱私）泄露和可用性。然而，這些工作是將率失真與隱私?可用性折中問題的關(guān)聯(lián)關(guān)系用于數(shù)據(jù)庫的場景中。此外，Oya等[17]將這種關(guān)聯(lián)關(guān)系用于研究單一時刻位置的隱私?可用性折中問題，并設(shè)計(jì)了相應(yīng)的位置隱私保護(hù)機(jī)制，但其并未考慮數(shù)據(jù)使用者分為多等級的情況。本節(jié)簡要描述率失真問題和該問題的計(jì)算，以及其與命題1中的隱私?可用性折中問題的關(guān)聯(lián)關(guān)系。

定義5率失真函數(shù)[18]。假設(shè)編碼器的輸入是X，相應(yīng)的輸出是X′，設(shè)信源的失真度量為d(x,x)′，分布服從X～p(x)，該信源的率失真函數(shù)定義為

其中，最小值取自使聯(lián)合分布p(x′|x)=p(X)p(x′|x)滿足期望失真限制的所有條件分布q(x′|x)，并且

為了便于介紹用于計(jì)算率失真函數(shù)的算法，首先簡要描述一個用于尋找2個凸集之間最小距離的算法。這個算法可被用于求解率失真函數(shù)中的最優(yōu)化問題。

尋找2個凸集之間最小距離的算法[18-19]。已知d(a,b)表示元素a和b之間的歐幾里得距離，給定2個凸集A和B，它們之間的最小距離dmin=mina∈Aminb∈Ad(a,b)可通過以下的步驟來尋找。首先，在集合A中任取一點(diǎn)x∈A，在集合B中找出與x∈A距離最近的一點(diǎn)y∈B。然后，固定點(diǎn)y∈B，找出集合A中與y∈B最近的點(diǎn)。重復(fù)上述過程，很明顯，該距離會隨著重復(fù)次數(shù)的增加而減小。文獻(xiàn)[19]中提出如果2個集合都是凸集，并且距離度量滿足一定的條件，那么這個交替最小化算法最終會收斂到距離的最小值。特別地，若2個集合是概率分布的集合且距離度量是相對熵時，該算法的結(jié)果會收斂到2個概率分布集合之間的最小相對熵。

下面簡要介紹使用上述算法中基本思想的用于計(jì)算率失真函數(shù)的Blahut-Arimoto算法。

Blahut-Arimoto算法[18,20]是一種最終會收斂到率失真函數(shù)中凸優(yōu)化問題最優(yōu)解的迭代算法。首先，為r(x′)選擇一個初始分布（如均勻分布），使用r(x′)和計(jì)算q(x′|x)。在獲得q(x′|x)后，通過等式更新r(x)′。然后，使用新的r(x′)和等式來更新q(x′|x)。重復(fù)上述步驟直到算法收斂，即可獲得率失真函數(shù)中凸優(yōu)化問題的最優(yōu)解q(x′|x)。

本質(zhì)上來說，Blahut-Arimoto算法可以被用于求解命題1中的最優(yōu)LPPM，即q(vk|l)。

5 多等級隱私保護(hù)位置發(fā)布機(jī)制

基于第3節(jié)的預(yù)備知識，本節(jié)提出多等級隱私保護(hù)位置發(fā)布機(jī)制。具體地，提出了基于互信息的位置數(shù)據(jù)分級發(fā)布機(jī)制，該發(fā)布機(jī)制可保證在一定的可用性約束條件下，每一級別的擾動位置數(shù)據(jù)對真實(shí)位置數(shù)據(jù)具有最小的隱私泄露。需要特別強(qiáng)調(diào)的是，多級隱私保護(hù)位置數(shù)據(jù)發(fā)布機(jī)制中的級別k由該算法中的輸入?yún)?shù)λ（即拉格朗日乘子）決定，即數(shù)據(jù)發(fā)布者根據(jù)λ來定義等級k。例如：當(dāng)λ的值取自集合{0.01,2,5} 時，可以定義λ=5,2,0.01 時對應(yīng)的等級分別為k=1,2,3。

反復(fù)迭代q(vk|l)和r(vk)直至算法收斂，即可獲得最優(yōu)LPPMq(vk|l)。此時，根據(jù)互信息的定義可以計(jì)算出發(fā)布隱私保護(hù)等級為k的擾動數(shù)據(jù)對真實(shí)位置造成的隱私泄露，如式(3)所示。

在算法1中詳細(xì)介紹數(shù)據(jù)發(fā)布者如何通過控制輸入?yún)?shù)來獲取用于生成發(fā)布給多個不同級別數(shù)據(jù)使用者擾動位置數(shù)據(jù)的LPPM（即q(vi|l)）。獲取q(vi|l)后，按照概率分布q(vi|l)進(jìn)行采樣來發(fā)布擾動位置vi。

算法1多隱私保護(hù)等級的位置數(shù)據(jù)發(fā)布機(jī)制

輸入拉格朗日乘子（即等級控制因子）λ，數(shù)據(jù)使用者的等級i，真實(shí)位置的概率分布p(l)，真實(shí)位置數(shù)據(jù)與發(fā)布的擾動位置數(shù)據(jù)間的失真函數(shù)d(l,vi)，算法收斂設(shè)置的閾值δ

輸出發(fā)布擾動位置數(shù)據(jù)給等級為i的數(shù)據(jù)使用者時所使用的LPPMq(vi|l)，將vi發(fā)布給等級為i的數(shù)據(jù)使用者所導(dǎo)致的最小隱私泄露，對應(yīng)于的失真Di，擾動位置vi的邊緣分布p(vi)

本文通過給出算法1中每一步迭代的計(jì)算復(fù)雜度的表達(dá)式，來分析該算法的計(jì)算復(fù)雜度。在每次迭代中，計(jì)算復(fù)雜度是由計(jì)算q(vi|l)和r(v,k)主導(dǎo)的。計(jì)算式(1)中q(vk|l)的復(fù)雜度分析如下。針對變量l的每個取值，對于一個特定的vk，在分母上需要進(jìn)行|vk|次乘法?？紤]到對每個vk都使用這個分母，因此共需要O(|vk|)次計(jì)算操作。考慮到變量l的所有取值，計(jì)算q(vk|l)的復(fù)雜度為O(|Vk||L|)。計(jì)算式(2)中r(vk)的復(fù)雜度分析如下。類似地，對于一個特定的vk需要|L|次乘法?？紤]到所有的vk，計(jì)算r(vk)時的復(fù)雜度為O(|Vk|||L|)。因此，算法1中的每次迭代需要O(|Vk|||L|)次計(jì)算。

6 多樣性攻擊隱私泄露的計(jì)算方法

定義3中指出，攻擊者可能截取到的發(fā)布給其他等級數(shù)據(jù)使用者的數(shù)據(jù)集Vm包括了除vm以外的任意發(fā)布數(shù)據(jù)。以數(shù)據(jù)使用者分為3個等級為例，詳細(xì)介紹如何使用本節(jié)提出的多樣性攻擊隱私泄露的度量方法來衡量當(dāng)攻擊者獲得其他2個等級的發(fā)布數(shù)據(jù)時導(dǎo)致的隱私泄露。設(shè)該場景中數(shù)據(jù)擁有者的真實(shí)位置數(shù)據(jù)為L，通過算法1生成了用于發(fā)布給3個不同等級的數(shù)據(jù)使用者的擾動位置數(shù)據(jù)V1,V2,V3。設(shè)攻擊者的等級為2，當(dāng)他通過截獲等方式獲得其他2個等級用戶的數(shù)據(jù)V1和V3時，該攻擊者可通過將發(fā)布數(shù)據(jù)V1,V2,V3進(jìn)行聯(lián)合分析，進(jìn)而更好地推斷真實(shí)位置數(shù)據(jù)L的值。根據(jù)定義4中提出的度量方法，這種場景下的多樣性隱私泄露為I(L;V1,V2,V3)。

為了清楚地描述出如何計(jì)算不同隱私保護(hù)機(jī)制在受到多樣性攻擊時導(dǎo)致的隱私泄露，下面將對互信息I(L;V1,V2,V3)進(jìn)行展開計(jì)算。根據(jù)互信息的定義有

根據(jù)信息熵的定義有

由于V1,V2,V3分別為真實(shí)位置L經(jīng)由3種不同隱私保護(hù)等級處理后的發(fā)布數(shù)據(jù)，因此V1,V2,V3之間相互獨(dú)立。因此有

其中，v1,v2,v3的邊緣分布為

根據(jù)條件熵的定義，有

其中，有

該式中第一個等號是基于概率論中的貝葉斯公式，第二個等號是由于考慮單一時刻的位置發(fā)布，因此當(dāng)給定真實(shí)位置L時，Vl完全由L決定，而與其他變量無關(guān)，因此有

同樣地，有

由此可以看出，計(jì)算互信息I(L;V1,V2,V3)的關(guān)鍵是需要知道發(fā)布數(shù)據(jù)V1,V2,V3的邊緣分布，條件概率分布（即LPPM）p(v1|l),p(v2|l),p(v3|l)，以及真實(shí)位置L的概率分布p(l)。

7 實(shí)驗(yàn)與性能

本節(jié)在模擬數(shù)據(jù)集上評估算法1中提出的多級隱私保護(hù)的位置發(fā)布機(jī)制，并與文獻(xiàn)[21]中提出的LPPM進(jìn)行對比。文獻(xiàn)[21]中提出一種基于差分隱私的LPPM——Geo-indistinguishability，該LPPM保證真實(shí)位置x會被以很高的概率映射到一個鄰近的位置，而不是映射到較遠(yuǎn)的位置。Geo-indistinguishability擴(kuò)展了差分隱私的定義，以達(dá)到將用戶的真實(shí)位置保護(hù)在一定直徑范圍內(nèi)的目的。為了合理地比較2種LPPM的隱私泄露，本文也用互信息來計(jì)算文獻(xiàn)[21]中LPPM的隱私泄露。

選擇模擬數(shù)據(jù)集的原因是可以通過改變模擬數(shù)據(jù)集中真實(shí)位置L的先驗(yàn)概率分布，來理解不同的先驗(yàn)概率分布對于位置隱私泄露的影響。位置L的概率分布不同表明數(shù)據(jù)集中的位置具有不同的受歡迎程度（即用戶位于某一位置的概率明顯高于其他位置）。在這個模擬數(shù)據(jù)集中，假設(shè)地圖中有6個位置。具體地，分別在模擬數(shù)據(jù)集上計(jì)算并比較2種LPPM在發(fā)布給單一級別數(shù)據(jù)使用者時的隱私泄露（即數(shù)據(jù)使用者無法獲取其他隱私保護(hù)級別的發(fā)布數(shù)據(jù)）和受到多樣性攻擊時的隱私泄露。所有的實(shí)驗(yàn)都是在一臺配備了2.3 GHz Intel i5 處理器和8 GB 內(nèi)存的筆記本電腦上完成的。

7.1 單一級別的位置隱私泄露

本節(jié)在模擬數(shù)據(jù)集上進(jìn)行仿真，分析了算法1中提出的LPPM在數(shù)據(jù)使用者僅擁有符合自己相應(yīng)權(quán)限的發(fā)布數(shù)據(jù)情況下的隱私泄露，并與文獻(xiàn)[21]中的LPPM產(chǎn)生的隱私泄露進(jìn)行對比。為了分析真實(shí)位置L的先驗(yàn)概率分布的變化對隱私泄露的影響，在模擬數(shù)據(jù)集中將真實(shí)位置L的先驗(yàn)概率分布分別設(shè)置為p2(L)={0.3,0.1,0.2,0.25,0.05,0.1}，p3(L)={0.8,0.04,0.04,0.04,0.04,0.04}和p4(L)={0.04,0.04,0.04,0.04,0.04,0.8}。注意到模擬數(shù)據(jù)集中真實(shí)位置L的4個先驗(yàn)概率分布的變化有一定的特點(diǎn)，即在每個概率分布中，位置受歡迎程度的差別逐漸增大。換句話說，當(dāng)真實(shí)位置L的概率分布為p1(L)=，即均勻分布時，每個位置受歡迎程度的大小是同等的；而當(dāng)真實(shí)位置L的概率分布為p1(L)={0.8,0.04,0.04,0.04,0.04,0.04}時，每個位置受歡迎程度的差別最大。本文將通過實(shí)驗(yàn)來了解當(dāng)位置受歡迎程度區(qū)別較大或較小時，對單一時刻隱私泄露的影響。

失真使用歐幾里得距離來計(jì)算。文獻(xiàn)[21]中的LPPM是通過使用與模擬數(shù)據(jù)集中相同的初始位置概率分布和失真生成的。此外，為了描繪出平滑的隱私?可用性曲線，在0.01～10這個范圍內(nèi)逐漸遞增地選擇λ。λ越小，失真越大。將算法1中結(jié)果收斂時的閾值設(shè)置為1×10?8，分別在p1(L)、p2(L)、p3(L)和p4(L)上進(jìn)行仿真，結(jié)果如圖1～圖4所示。圖中曲線上的每一個點(diǎn)對應(yīng)于一個相應(yīng)的λ取值。每一個λ對應(yīng)一個數(shù)據(jù)使用者的級別，λ越大，對應(yīng)的數(shù)據(jù)使用者的級別越高。

圖1 真實(shí)位置的先驗(yàn)概率分布為p1(L)時的隱私泄露

圖2 真實(shí)位置的先驗(yàn)概率分布為p2(L)時的隱私泄露

圖3 真實(shí)位置的先驗(yàn)概率分布為p3(L)時的隱私泄露

比較圖1～圖4中的實(shí)驗(yàn)結(jié)果可以看出，本文提出的LPPM的隱私泄露均低于文獻(xiàn)[21]中LPPM的隱私泄露。這是因?yàn)楸疚牡腖PPM是通過求解最小化隱私泄露的優(yōu)化問題而得到的。此外，還觀察到當(dāng)真實(shí)位置L的概率分布越趨向于集中在某些位置時（即用戶位于某些位置的概率遠(yuǎn)高于其他位置，如概率分布為p3(L)={0.8,0.04,0.04,0.04,0.04,0.04}時，用戶真實(shí)位置是第一個位置的概率為0.8，遠(yuǎn)高于其他位置的概率），本文所提LPPM 在隱私泄露方面的優(yōu)勢就越明顯。這是由于攻擊者具有關(guān)于真實(shí)位置L的先驗(yàn)概率p(L)的知識，因此當(dāng)某一位置非常受用戶歡迎時，真實(shí)位置的先驗(yàn)概率分布本身已經(jīng)泄露了很多信息，為了保證可用性，生成的LPPM幾乎不會再通過降低可用性來減小隱私泄露了；相比之下，當(dāng)用戶真實(shí)位置的先驗(yàn)概率為均勻分布時，先驗(yàn)概率分布本身泄露的隱私很少，因此當(dāng)攻擊者一旦觀測到了擾動位置數(shù)據(jù)后，會對真實(shí)位置造成較多的隱私泄露。

圖4 真實(shí)位置的先驗(yàn)概率分布為p4(L)時的隱私泄露

7.2 存在多樣性攻擊時的隱私泄露

與第6節(jié)中的舉例一致，本節(jié)在分析多樣性攻擊隱私泄露的實(shí)驗(yàn)部分也將數(shù)據(jù)使用者分為3個等級。首先，需要保證數(shù)據(jù)使用者等級的選取具有一般性?？紤]到本文所提方案中的數(shù)據(jù)使用者等級由λ決定，因此使用程序在[0.01;0.01;10]這個區(qū)間范圍內(nèi)隨機(jī)選出3個λ值，對比分析2種方案在受到多樣性攻擊時的隱私泄露。在模擬數(shù)據(jù)集中仍然假設(shè)真實(shí)位置L的先驗(yàn)概率分布為p1(L)=，p2(L)={0.3,0.1,0.2,0.25,0.05,0.1}，p3(L)={0.8,0.04,0.04,0.04,0.04,0.04}和p4(L)={0.04,0.04,0.04,0.04,0.04,0.8}。實(shí)驗(yàn)結(jié)果分別如表1～表4所示。

表1～表4中的實(shí)驗(yàn)結(jié)果表明，本文提出的LPPM在存在多樣性攻擊的場景中仍然有隱私泄露低于文獻(xiàn)[21]中LPPM的隱私泄露的優(yōu)勢。這是因?yàn)椋l(fā)布給不同等級數(shù)據(jù)使用者的擾動數(shù)據(jù)之間相互獨(dú)立，因此，每個擾動數(shù)據(jù)都是通過求解最小化隱私泄露的優(yōu)化問題得到的，多個擾動數(shù)據(jù)隱私泄露的求和也是最小的。此外，為了分析攻擊者所擁有的發(fā)布數(shù)據(jù)的等級差距大小與多樣性攻擊隱私泄露多少的關(guān)聯(lián)關(guān)系，本文固定3個等級中的2個等級，改變第3個等級，進(jìn)而分析這種關(guān)聯(lián)關(guān)系。相比只有2個等級擾動數(shù)據(jù)時的多樣性隱私泄露，當(dāng)攻擊者可以額外獲得一個等級的發(fā)布數(shù)據(jù)時，隱私泄露更多。實(shí)驗(yàn)數(shù)據(jù)表明，文獻(xiàn)[21]中LPPM在受到多樣性攻擊時產(chǎn)生的隱私泄露也有類似的結(jié)論。此外，注意到p3(L)和p4(L)的概率分布中，僅是受歡迎的位置不同，而位置的受歡迎程度是相同的。由表3和表4中的實(shí)驗(yàn)數(shù)據(jù)可以看出，具體哪一個位置受歡迎對隱私泄露的多少并無影響，影響隱私泄露的是位置的受歡迎程度。最后，與7.1節(jié)的結(jié)果類似，當(dāng)真實(shí)位置的概率分布中不同位置的受歡迎程度區(qū)別越大時，隱私泄露越少。

表1 真實(shí)位置的先驗(yàn)概率分布為p1(L)時的多樣性隱私泄露

表2 真實(shí)位置的先驗(yàn)概率分布為p2(L)時的多樣性隱私泄露

表3 真實(shí)位置的先驗(yàn)概率分布為p3(L)時的多樣性隱私泄露

表4 真實(shí)位置的先驗(yàn)概率分布為p4(L)時的多樣性隱私泄露

8 結(jié)束語

本文提出了基于信息論方法、獨(dú)立于任何攻擊、用于單一時刻的位置隱私度量方法。特別地，考慮了數(shù)據(jù)使用者由于可信度不同而被分為多個等級的場景。在一定的可用性約束條件下，依據(jù)本文提出的位置隱私度量方法建立最小化位置隱私泄露的優(yōu)化問題，即隱私?可用性折中問題。通過在該優(yōu)化問題中設(shè)置不同的輸入?yún)?shù)來生成不同隱私保護(hù)等級的擾動位置數(shù)據(jù)，并發(fā)布給相應(yīng)等級的數(shù)據(jù)使用者。此外，還提出了一種用于衡量當(dāng)攻擊者掌握多個不同等級的擾動數(shù)據(jù)時對真實(shí)位置數(shù)據(jù)造成的隱私泄露的度量方法，并將此類攻擊定義為多樣性攻擊。實(shí)驗(yàn)結(jié)果表明，在沒有多樣性攻擊和有多樣性攻擊的2種場景中，本文所提LPPM在隱私?可用性折中方面相比于基于差分隱私的LPPM具有顯著優(yōu)勢，尤其是當(dāng)真實(shí)位置的先驗(yàn)概率分布存在特別受歡迎的一些位置時，這種優(yōu)勢更加明顯。未來的研究工作是如何獲取可最小化多樣性攻擊場景下隱私泄露的位置隱私保護(hù)機(jī)制。