基于信息論方法的多等級位置隱私度量與保護

張文靜，劉樵，朱輝

（西安電子科技大學網絡與信息安全學院，陜西 西安 710071）

1 引言

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

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

2 相關工作

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

3 問題描述

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

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

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

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

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

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

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

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

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

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

4 預備知識

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

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

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

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

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

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

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

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

5 多等級隱私保護位置發布機制

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

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

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

算法1多隱私保護等級的位置數據發布機制

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

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

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

6 多樣性攻擊隱私泄露的計算方法

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

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

根據信息熵的定義有

由于V1,V2,V3分別為真實位置L經由3種不同隱私保護等級處理后的發布數據，因此V1,V2,V3之間相互獨立。因此有

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

根據條件熵的定義，有

其中，有

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

同樣地，有

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

7 實驗與性能

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

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

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

本節在模擬數據集上進行仿真，分析了算法1中提出的LPPM在數據使用者僅擁有符合自己相應權限的發布數據情況下的隱私泄露，并與文獻[21]中的LPPM產生的隱私泄露進行對比。為了分析真實位置L的先驗概率分布的變化對隱私泄露的影響，在模擬數據集中將真實位置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}。注意到模擬數據集中真實位置L的4個先驗概率分布的變化有一定的特點，即在每個概率分布中，位置受歡迎程度的差別逐漸增大。換句話說，當真實位置L的概率分布為p1(L)=，即均勻分布時，每個位置受歡迎程度的大小是同等的；而當真實位置L的概率分布為p1(L)={0.8,0.04,0.04,0.04,0.04,0.04}時，每個位置受歡迎程度的差別最大。本文將通過實驗來了解當位置受歡迎程度區別較大或較小時，對單一時刻隱私泄露的影響。

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

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

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

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

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

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

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

與第6節中的舉例一致，本節在分析多樣性攻擊隱私泄露的實驗部分也將數據使用者分為3個等級。首先，需要保證數據使用者等級的選取具有一般性。考慮到本文所提方案中的數據使用者等級由λ決定，因此使用程序在[0.01;0.01;10]這個區間范圍內隨機選出3個λ值，對比分析2種方案在受到多樣性攻擊時的隱私泄露。在模擬數據集中仍然假設真實位置L的先驗概率分布為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}。實驗結果分別如表1～表4所示。

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

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

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

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

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

8 結束語

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