基于差分隱私的個人軌跡信息保護機制

侯 堯，陶 洋，楊 理，熊 煉

重慶郵電大學 通信與信息工程學院，重慶400065

1 引言

隨著智能手機的發展，獲取用戶位置提供相關服務的應用程序得到了快速發展。這些基于位置的應用程序其主要關注點之一是位置隱私[1-2]。要使用這些應用程序，用戶必須將其位置提供給各自的服務提供商（或其他第三方）。這種位置泄露引起了嚴重的隱私問題，因為用戶位置可能會受到攻擊，使其接受不想要的基于位置的垃圾郵件、敲詐勒索，甚至是人身危險。

在過去的研究中，提出的大多數解決方案都是基于位置混淆，即泛化[3-4]（將軌跡上每個時刻的真實位置泛化到一個區域）、抑制[5-6]（根據真實位置所在區域的敏感程度有選擇的抑制發布）或擾動[7-9]（對每個時刻的真實位置添加隨機噪聲生成擾亂位置）。大多數空間變換都依賴于語義上的隱私模型，比如k-匿名[10-11]，或是特定的不確定性模型，并且沒有提供嚴格的隱私。為此，研究人員將廣義的差分隱私概念引入了位置信息保護中，這是一個能夠提供嚴格數學證明的隱私保護模型[12]。簡單地來說，差分隱私意味著：一定距離內的任何兩個位置進行擾動會產生相似的發布位置，因此攻擊者無法知道用戶的真實位置。

在本文中，給出了一種后置映射平面拉普拉斯機制。考慮一個具有敏感位置流的移動用戶，該用戶需要將位置提供給基于位置的應用程序（或其他第三方）。首先，根據每個位置設置的隱私級別生成擾動位置，再利用后置映射機制將生成的擾動位置映射到附近的位置，并使其服務質量損失最小。后置映射平面拉普拉斯機制可以在滿足相同的隱私級別同時改善其平均服務質量。最后結合真實數據，對機制進行了仿真分析，證明了機制的服務質量損失低于平面拉普拉斯機制。

2 理論分析

2.1 差分隱私和空間不可區分

差分隱私[13]是統計數據庫領域中的隱私概念。它的目標是在發布關于數據庫的聚合信息時保護個人數據。差分隱私要求修改單個用戶的數據對查詢結果的影響可以忽略不計。空間不可區分的定義是基于廣義的差分隱私，可以定義在任意一組位置集X 上，并配備一個度量d[14]。歐幾里德距離度量d(x,x′)表示位置x和x′之間的可區分程度，距離小表示位置是不可區分的，距離大表示允許攻擊者區分它們。

設Z 是提供給服務提供商的一組值，P(Z)表示Z 上的概率測量集。P(Z)上的乘法距離dP定義為：

機制被設計為概率函數K:X →P(Z)，在發布位置集Z 上分配每個真實位置x 的概率分布K(x)。差分隱私的廣義變體，稱為d-隱私，被定義為[4]：

定義1（d-隱私）機制K:X →P(Z)滿足d-隱私，當且僅當：或等價于：

d 的選擇不同產生的隱私概念也不同，并可以通過隱私參數ε 來縮放本文的度量。本文主要考慮位置隱私，在這種情況下，真實位置X 和發布位置Z 都是位置集合，K 是一種干擾機制。采用歐幾里德距離度量d，得到的εd-隱私，稱為ε-空間不可區分[12]。即當實際位置為x 時，與x 相距d(x,x′)的位置x′都發布位置z 的概率幾乎相同，則這種機制提供了空間上的不可區分性。其中“幾乎相同”表示概率的比率受exp(ε·d(x,x′)的約束，其中ε表示單位距離實現的不可區分的程度。兩個位置越近，生成相同發布位置z 的概率應該越相似。通過K 機制，服務提供商無法準確推斷用戶的位置，但可以獲得提供服務所需的近似信息。

從另外的角度來看，這個概念提供了用戶在任意半徑r 內的隱私，并具有與r 成正比的可區分性εr。因此，在較小的半徑范圍內，用戶享有很強的隱私，而他的隱私會隨著r 的增大而減小。此外，還可以靈活地在不同地點之間選擇不同的度量標準，例如曼哈頓或基于地圖的距離。文獻[12]給出了兩個特征結果，并詳細地解釋了空間不可區分。最后，通過在二維拉普拉斯分布中加入噪聲來實現這一概念。在本文中，主要假設d 是歐幾里德度量。

2.2 服務質量損失

實現位置隱私的常用方法是采用位置擾動機制，即概率函數K:X →P(Z)，其中X 是可能的位置集合，P(Z)表示Z 上的概率分布集合。K將位置x作為輸入，并產生一個發布位置z，p(z|x)表示真實位置為x 發布位置z 的概率。

從用戶的角度來看，希望量化由機制K 產生的服務質量損失（Service Quality Loss，SQL）。給出位置集X的先驗概率P-和度量d，其P-可視為對用戶的行為模型或攻擊者獲取的用戶背景知識，d(x,z)表示真實位置x與發布位置z的質量損失度量，用于衡量發布z而不是x 時服務質量損失的程度。所以可以將服務質量損失定義為真實和發布位置之間的期望距離[15]，換句話說，服務提供商應該提供與其接收到的位置的準確性成比例的質量。故服務質量損失可以被定義為位置的先驗概率和機制的條件概率的函數：

2.3 平面拉普拉斯機制

平面拉普拉斯機制是滿足ε-空間不可區分的機制，這種機制是從以真實位置x 為中心的二維拉普拉斯分布中得出干擾位置。給定參數ε ∈R+，真實位置x ∈R2，在任意位置z ∈R2，機制的概率密度函數為：

其中，ε2/2π 是歸一化因子。根據文獻[12]中提出的將笛卡爾坐標系轉換為極坐標系更方便計算上式，轉換為極坐標后的形式為：

干擾位置z可以使用點(r,θ)來表示，r表示x與z之間的距離，θ是r與笛卡爾坐標系橫坐標的夾角。根據文獻[12]可推導出真實位置為x時滿足“ε-空間不可區分”性質的干擾位置z的極坐標點(r,θ)的半徑計算公式：

其中，W-1(x)函數表示朗伯W 函數的區間(-∞,-1)分支，ρ是服從[0，1]均勻分布的隨機數。θ 是服從[0,2π]均勻分布的隨機數。最后得出干擾位置z=x+(r·cos(θ),r·sin(θ))。

獲得的位置z是對應于z周圍的R2子集，由于R2具有對稱性，故平面拉普拉斯機制采用歐幾里德度量的服務質量損失與P-無關，對任意P-∈P(X)有SQL(K,P-)=2/ε。

3 發布機制

3.1 后置映射機制

顯然，用戶總是希望服務質量損失是最優的，即最小化服務質量損失，為此給出了一種后置映射的方法來達到目的。后置映射機制可以在滿足相同的隱私級別同時改善其平均服務質量。空間不可區分要求x 附近的位置x′以相同的概率發布z，z 不必離x 很遠。例如，靠近湖邊的兩個地點，使用平面拉普拉斯機制在所有方向上對稱地增加噪聲，則z 很有可能在湖中。現實中用戶在湖中的概率很小，可以將其映射到湖的邊緣，使其更接近真實位置。當然，如果用戶確實在湖中，映射則會降低服務質量，但這種可能性很小，所以總體上可以改善服務質量。

給定機制K:X-P(Z)，真實位置為x，首先使用K 產生干擾位置z，然后使用后置映射函數M:Z →Z 將z 映射到新位置z*=M(z)，最后發布z*。

在Z ?Z 中，KM 發布觀測位置的概率與K 發布觀測位置的概率相同，則：

其中，M-1(Z)={z ∈Z:M(z)∈Z}。由此可以看出若K 滿足εd-隱私，那么KM 也同樣滿足。

若后置映射M 對于所有其他后置映射M′有SQL(KM,P-)＜SQL(KM',P-)，則稱M 為最優映射。可以通過后置映射實現其最優性，即選擇出最小服務質量損失的位置z*。利用貝葉斯規則，將能從先驗概率P-和機制K 得到后驗概率P+∈P(x)，即：

若后置映射：

從上式易看出，對于所有z，z*∈Z

即：SQL(KM',P-)≥SQL(KM,P-) （11）

則式（11）為最優映射。

3.2 最優后置映射

后置映射第一步是計算后驗，然后找到最小化服務質量損失的點z*∈Z。如果X，Z 是有限的，則可以使用公式（10）直接計算后置映射。

通過迭代所有Z 來找到最小化服務質量損失的點z*是不現實的，則可以通過僅考慮以z 為中心的某個圓Or(z)內的位置來近似映射，即用argmin z*∈Or(z)替代argmin z*∈Z。直觀上來說，Or(z)包含的點越多（半徑越大），服務質量損失越接近最小值，故其中半徑r 可以選擇為包含所有K(x)(Or(x))≥0.99 點圓的半徑。

在許多情況下，用戶希望能夠靈活地將自己定位在平面上的任何位置，以及發布任意位置，因此可以將X，Z 看為完整的R2平面。此時Z 是連續的，則問題變得困難，因為即使在有界區域Or(z)中，仍然需要考慮許多不可忽略的點。

該情況下的首要問題是計算后驗。雖然用戶可能位于任何位置，但由于先驗是過去訪問服務的位置或興趣點等一系列有限數據集構成的，所以可以假設能被構造的后驗P+∈P(R2)也是有限的。盡管P+是有限的，但最小化服務質量損失的z*不一定是后驗點中的位置，所以仍然有無數的z*候選者。

直觀地，z*應該在有限后驗P+之間的點，即在后驗構成的凸包中。因此從幾何角度來看，本文的問題轉化為要在平面中找到一個點，該點到給定集合的加權距離最小，則該問題是位置理論中的韋伯問題。故對于歐幾里德度量的情況，可以有效地構造最優z*。采用Weiszfeld算法解決，其迭代公式修改為：

用Weiszfeld(P+)表示其迭代結果，并可以設置一些停止條件（例如，當期望距離下降到ε 以下時，或者運行時間為1 s）。

經分析易知z*應該在有限后驗P+構成的凸包中，且應該靠近質心附近，故為了更有效的計算，迭代公式中y0可以從質心開始，其質心的計算由公式（13）給出。

3.3 后置映射拉普拉斯機制

在R2平面上使用連續的先驗概率是困難的，因此假設關于位置服務的先驗概率信息采用以前使用的數據集形式提供，甚至以有關感興趣點信息的形式提供。令Q ∈R2是一個可能性很大的有限位置集合，集合中每個q ∈Q 與權重w(q)＞0相關聯。例如，Q 表示過去訪問位置服務的位置集合，則w(q)表示該位置訪問服務的用戶數。或者Q 可以是與位置服務相關的興趣點列表，其中w(q)表示捕獲每個興趣點的流行度。

給定平面拉普拉斯機制生成了干擾位置z，然后為了構造一個有限且合理的后驗概率P+∈P(R2)，則需要將Q（可能非常大）限制在z周圍的有限區域。本文設置r=C-1（0.99），其中C-1是平面拉普拉斯機制的半徑累積分布函數的倒數，讓Qr=Q ∩Or(z)。也就是說，平面拉普拉斯機制以99%的概率生成x 與r 之間的點，因此將z 重新映射到距z 不遠的z*（即“附近位置”）是合理的。

注意，可以使用k-d 樹的空間數據結構來地計算Qr。0.99閾值可用于轉換效率以獲得準確性，較小的值將導致較小的Qr，但可能導致最佳點位于區域之外。如果Q 密集，則可以使用預處理階段來減小Qr的大小，將點合并為小群集，并將w(q)設置為群集的權重。

權重w(q)，q ∈Qr可以（在歸一化之后）作為R2上的有限先驗概率。采用貝葉斯定律（公式（9））和平面拉普拉斯的概率密度函數（公式（5））來計算先驗概率，可以得出有限的后驗P+：

最后，通過Weiszfeld(P+)計算后置映射的點z*。注意，實際上數據集Q 可能不夠詳細，無法為每個位置提供足夠的信息。新用戶可能在過去沒有或很少有其他用戶訪問過的位置訪問服務，此時認為映射的數據質量很低會降低用戶的隱私，因此可以使用簡單的啟發式方法來評估數據的質量：如果Qr的大小（或者總重量）低于某個閾值qmin，那么就跳過重映射并直接報告z，整個機制發布數據的算法1如下所示。

算法1后置映射拉普拉斯機制

輸入：x ∈R2，ε ＞0，qmin≥0，Q ?R2，w

輸出：z*

1.通過平面拉普拉斯機制生成干擾位置z；

2.設r=C-1（0.99）；

3.計算Qr=Q ∩Or(z)；

4.if(|Qr|＜qmin)

5.z*=z；

6.else

7.通過公式（14）計算后驗P+(x)；

8.z*=Weiszfeld(P+)；

9.end if；

10.return z*；

4 實驗評估

對本文方法進行了實驗評估。所有算法都在MATLAB上進行了測試，使用的是2.9 GHz英特爾i7 CPU和8 GB內存的PC 機。數據集使用Geolife 數據，Geolife 數據是通過182 位用戶且超過三年時間所收集的真實數據。移動軌跡由一系列包含緯度、經度和時間戳的記錄。提取了北京五環內的軌跡，證明了有效的后置映射可以不受感興趣區域的任何限制。

為了保證所提出機制的可用性，將訓練和評估數據分開。更準確地說，將整個位置數據集分成兩個不重疊的部分。第一部分包含了大約80%用戶的位置數據，作為訓練集。在這一部分中，構造出了一個全局先驗，作為訪問該區域所有用戶的個體先驗概率的平均值，然后將其用于后置映射機制得到最優服務質量損失的位置。請注意，此后置映射是針對全局先驗優化的，而不是針對特定用戶的。

數據集的另一部分，包含其余20%用戶的數據，被看作是評估機制的測試集。更準確地說，為至少20 個用戶構造了一個用戶專用的先驗，并度量用戶使用自己的先驗時機制的服務質量損失。雖然機制只針對數據集訓練部分的用戶進行了訓練，但是發現它們也為測試集的用戶提供了較低的服務質量損失。

注意，分割是對用戶執行的：訓練數據集中沒有測試用戶的任何數據。這種非常保守的方法旨在模擬一個新用戶的情況，對于這個新用戶，除了關于整個服務的一般可用信息之外，沒有其他任何信息。在這種情況下，改善服務質量損失是一個強有力的結果；顯然，如果對用戶自己的部分數據進行訓練，結果可以得到進一步的大幅度改進。

所有的評估機制都是為了滿足ε-空間不可區分而構造的，使用ε=l/r，其中r=0.1 km，且l 的范圍為ln（1.4）到ln（2.6）。同時評估平面拉普拉斯機制本身和后置映射拉普拉斯機制。數據集Q 是由48 000 用戶和超過5 MB的訪問服務位置點組成的訓練集。在訪問服務位置點列表中，構造了一個k-d 樹，可以快速構建Qr，為了避免單個用戶對后驗產生較大影響，取w(x)=1/u，其中u為該用戶在Qr中的訪問服務次數，并設置qmin=20。在實驗評估中，盡管數據集很大，但每次映射只需要幾毫秒。機制在12 000 用戶的整個測試數據集中對這兩種機制進行了實驗評估。

圖1 顯示了不同l 值下各用戶平均的服務質量損失。注意，平面拉普拉斯機制的平均服務質量損失總是相同的為2/ε。另一方面，使用后置映射時的平均服務質量損失取決于用戶：由于映射是使用全局先驗概率計算的，因此它可能并不總是能夠提供改進。不過，雖然沒有使用用戶數據進行訓練，但實驗評價表明，大多數用戶的服務質量損失有很大的改善。ln（1.4）的結果表明，后置映射拉普拉斯機制的平均服務質量損失為499 m，而平面拉普拉斯機制的平均服務質量損失為594.4 m，高出19%。

圖1 隱私級別l對SQL的影響

圖2 顯示了圖1 中l=ln（1.4）時的100 個時間戳測試數據，由圖可以看出并不是所有用戶的服務質量損失都能被改善，但是只有8.17%的用戶服務質量損失有所增加，其中僅有1.27%的用戶服務質量損失增加了10%（59.4 m）或更多。

圖2 軌跡的SQL

5 結束語

在本文中，提出了一種后置映射平面拉普拉斯機制。考慮一個具有敏感位置流的移動用戶，該用戶需要將位置提供給基于位置的應用程序。首先，根據每個位置設置的隱私級別生成擾動位置，然后利用后置映射機制將生成的擾動位置映射到附近的位置，并使其服務質量損失最小。后置映射平面拉普拉斯機制可以在滿足相同的隱私級別同時改善其平均服務質量。最后結合真實數據，對機制進行了仿真分析，結果顯示機制的服務質量損失低于平面拉普拉斯機制。