差分擾動的均衡增量近鄰查詢位置隱私保護方法

胡德敏，詹 涵

(上海理工大學 光電信息與計算機工程學院，上海 200093)

1 引 言

具有定位能力移動設備的日益普及和無線通信技術的快速發展，大大增加了基于位置服務(location-based service，LBS)的使用.基于位置服務是指移動終端利用各種定位技術獲得自己當前的位置，并提出與用戶位置有關的服務.雖然這種服務已經證明可以為社會和個人提供巨大的便利，但同時也引起了嚴重的隱私問題，泄露用戶私人生活的敏感信息，如家庭住址、興趣愛好、健康狀況等.因此如何保護用戶位置隱私而又不妨礙服務的可用性是一個重要挑戰[1].基于LBS的用戶隱私保護研究得到了越來越多學者的重視，目前，這方面的研究主要有k-匿名、假位置、位置擾亂、空間加密等方法[2].

大部分k-匿名方法采用可信第三方(trusted third party，TTP)服務器將用戶的真實位置替換為包含k個用戶的匿名區域，發送給位置服務商(location-based service provider，LSP)，使得LSP無法分辨出查詢用戶的真實位置.一種方法[3，4]是向真實位置中添加假位置，另一種方法[5，6]是加入附近k-1個真實用戶位置.然而，當TTP不是完全可信時，用戶的位置和查詢信息等隱私將面臨風險，而且TTP容易成為系統性能瓶頸和集中攻擊點.為了避免TTP，Chow等人[7]基于無中心服務器思想提出了P2P結構，仍然需要使用匿名區，且要求用戶相互通信以獲取額外信息.Yiu等人提出了SpaceTwist隱私保護算法[8]，采用客戶—服務器結構，移動用戶隨機選擇用戶真實位置附近的一個錨點，代替用戶真實位置向LSP發送請求，進行增量近鄰查詢.由于隨機選擇錨點，所獲得的查詢結果無法得到保證.文獻[9]參照路網密度和興趣點密度，構造匿名區和獲取錨點，將其發送給代理用戶進行查詢，但無法保證查詢結果圍繞真實位置均勻分布.

這些方法都假定對手沒有用戶的背景信息，然而，當有背景信息的對手存在時，上述方法的隱私保護強度顯然不夠.在已知匿名區的情況下，對手利用匿名區和用戶的背景信息，縮小用戶位置范圍，并且當用戶分布稀疏時，很難在一個合理的匿名區中發現足夠的用戶.近年來，開始采用差分隱私[10]來保護用戶在LBS中的位置.差分隱私是統計數據庫領域的隱私概念，具有兩大優點，一方面，差分隱私具有可證明的隱私保障；另一方面，差分隱私能應對具有不同背景信息的對手.差分隱私模型比k-匿名模型具有更嚴格的隱私保障.文獻[11]采用差分隱私和有k個位置的匿名集計算干擾位置，可以抵御有背景信息對手的攻擊，但匿名集選擇嚴重影響隱私保障.文獻[12]提出基于差分隱私的δ-位置集合來保護用戶在時間相關性下每個時間點的真實位置，移動模型的選擇是一個難點.文獻[13]通過使用隱式馬爾可夫模型和差分隱私解決多個用戶之間位置相關性泄露問題，但只考慮了恒定時間和兩個用戶之間的位置相關性.

本文提出一個能抵擋背景信息攻擊且無需任何TTP的差分擾動位置隱私保護方法.按照期望的隱私水平向用戶真實位置添加可控的拉普拉斯噪聲產生擾動，該擾動位置在一定范圍內和用戶真實位置不可區分，然后用該擾動位置代替用戶真實位置請求LSP.同時采用改進的增量近鄰查詢算法，需求空間再次擴大使得返回的興趣點既滿足用戶期望的k近鄰結果，又使興趣點圍繞真實位置均勻分布，提高查詢準確率.

本文的組織結構如下：第1節介紹位置隱私保護的背景和研究現狀；第2節描述差分擾動的均衡增量近鄰查詢位置隱私保護方法；第3節進行安全性分析；第4節進行實驗以及實驗結果分析；第5節對全文進行了總結.

2 差分擾動的均衡增量近鄰查詢位置隱私保護方法

2.1 相關定義

定義1.用戶位置loc.用戶在某一時刻的位置可以用loc={x，y，t}表示，其中x表示經度，y表示緯度，t表示用戶所處當前位置的時間.

定義2.位置隱私需求Qc.用戶位置隱私需求Qc={e，r}，其中r表示需要隱私保護區域的半徑，表示區域內各個點之間的差異水平.

定義3.查詢請求Qa.用戶以Qa={id，s，con，kresult}的形式向LSP發出查詢請求.其中id表示該用戶的標識符，s表示錨點位置，con表示用戶的查詢請求內容，kresult表示用戶期望的k近鄰查詢結果.

定義4.差分隱私.對于任意兩個數據集D1和D2，他們兩者之間最多相差一條數據，一個隨機函數k提供ε-差分隱私，ε表示隱私預算參數，即隱私保護程度，Range(k)表示隨機函數的取值范圍，如果對所有的S∈Range(k)，則有，

Pr(k(D1)∈S)≤eεPr(k(D2)∈S)

(1)

定義5.地理不可區分性[14].標準差分隱私可以成功應用于有多個用戶的聚合信息發布情況，但不適合單個用戶場景.地理不可區分性是標準差分隱私的變體，適合單個用戶情況.在以用戶真實位置為圓心，r為半徑的區域內，用戶享有隱私水平，ε=/r表示單位距離隱私水平.通過向用戶的真實位置添加平面拉普拉斯噪聲生成干擾位置，有背景信息的對手可以觀察到干擾位置，但不能以高準確率判斷用戶的真實位置.定義如下，機制K滿足ε-地理不可區分性，對于x，x′?X，z?Z，X表示輸入點集合，Z表示干擾位置集合，d(x，x′)≤r，則有，

K(x)(z)≤eεd(x，x′)K(x′)(z)

(2)

其中d(，)是兩點之間的歐幾里得距離，K(x)(z)是x經過機制K生成的擾動位置z的概率.

2.2 系統結構

本文采用客戶—服務器結構，如圖1所示.移動終端具備基本的定位能力，通過手機設備和位置服務器直接通信，不需要TTP.另外，由于集中關注用戶提交位置信息給LBS服務器帶來的位置隱私泄露問題，因此假設用戶只將位置信息傳遞給LBS服務器，不傳遞如用戶id和網絡地址等更多信息.查詢過程主要如下：a)在移動終端執行擾動機制(具體算法見2.3節)，生成干擾位置z，此過程不需要進行大量的計算和額外的帶寬使用；b)移動終端發出一個查詢請求Qa給LBS服務器；c)移動終端接受LBS服務器返回的查詢結果并進行過濾.

圖1 體系結構圖Fig.1 System architecture

2.3 移動終端的錨點計算

以一定的方式向真實位置添加拉普拉斯噪聲，生成干擾位置，將其作為錨點，進行增量近鄰查詢，錨點和真實位置在以loc為圓心，r為半徑的區域內，滿足地理不可區分性.把位置區域建模成歐幾里得平面模型，該模型可以看作地球表面一個良好近似.首先，在連續平面上定義地理不可區分性連續機制；其次，由于位置坐標是有限的點，因此需要向獲得的連續點進行離散化；此外，在現實生活中，我們通常只對一定區域感興趣，如果用戶知道真實位置位于特定區域內，則希望生成的干擾位置也在同一區域，因此需要截取有限區域.

a)地理不可區分性的連續機制

在連續平面上定義地理不可區分性機制是構成我們方法的基礎，需要保證的屬性是當真實位置分別是x和x′時，在一定區域內生成干擾位置z的概率，最多相差因子e-εd(x，x′).如果噪聲函數使得在z周圍生成干擾位置的概率隨著距真實位置x的距離而呈指數下降，該屬性滿足.在線性空間，這剛好是拉普拉斯分布的特性，概率密度函數為：

(3)

f(x)已被證明滿足1/b-差分隱私[15]，但該函數不能直接使用，因為該函數定義在線性空間，我們需要的是定義在平面空間的概率密度函數.于是把拉普拉斯分布從一維空間延伸到二維空間，如下：

(4)

其中，ε2/2π是標準化因子，真實位置x∈R2，經過噪聲機制生成的干擾位置z∈R2.該函數叫做以x為中心的平面拉普拉斯分布，滿足ε-地理不可區分性，證明如下：

Dε(x)(z)≤eεd(x，x)Dε(x′)(z)

K(x)(t)≤eεd(x，x′)K(x′)(t)

b)生成干擾位置

平面拉普拉斯的概率密度函數僅和干擾位置z與x的距離有關，因此，把笛卡爾坐標系轉化為以x為原點的極坐標系更方便計算干擾位置.點z表示成點(r，θ)，r是z到x的距離，θ是射線xz與x軸的夾角.以x為原點的極性拉普拉斯概率密度函數，如下：

(5)

兩個隨機變量半徑和角度相互獨立，該概率密度函數可以表示為兩個函數的乘積，如下：

Dε(r，θ)=Dε，R(r)Dε，Θ(θ)

(6)

兩個函數分別為：

(7)

(8)

Dε，R(r)是伽馬分布的概率密度函數，Dε，Θ(θ)是恒定常量1/2π.根據Dε(r，θ)計算點(r，θ)可以從Dε，R(r)，Dε，Θ(θ)分別計算r和θ.因Dε，Θ(θ)是常量，生成θ較容易：以均勻概率1/2π在[0，2π)之間隨機生成一個數θ.然后考慮Dε，R(r)的積分函數Cε(r)，如下：

(9)

給定笛卡爾坐標系中真實位置x=(m，n)，根據如上所述生成噪聲(r，θ)，干擾位置點z=(m+rcosθ，n+rsinθ).

c)離散化

在現實生活中，通常用離散坐標表示一個位置，比如，位置坐標的經緯度達到某個精度.然而，前面部分描述的拉普拉斯機制可以在平面上任意位置生成干擾位置，則需要將上述生成的干擾位置重新定義在離散的笛卡爾坐標系網格G上最接近x的點，網格G的單元網格劃分方式取決于位置坐標精度.

d)截取有限區域

假設用戶可接受干擾位置的指定區域是以loc為圓心，ra為半徑的圓型區域A，則把由極坐標系下生成的干擾位置點重新映射到Α∩G中近似的點.

算法1.干擾位置生成算法.

輸入：用戶位置loc，隱私需求Qc，用戶所在區域area，位置坐標精度δ，可接受區域半徑ra.

輸出：干擾位置z.

1.z←0；

3.calculate angelθuniformly in[0，2π)；//計算θ

4.calculatez=(x+rcosθ，y+rsinθ)；

5.divide area intoGaccording toδ；

6.getz′ by remappingzto the closest pointzonG；

7.ifra≤rand ifz′?A

8.getz′′ onA∩G

9.z←z′′；

10.returnz；

2.4 均衡增量近鄰查詢算法

本文在用戶端執行均衡增量近鄰查詢算法，在第一次供應空間包含需求空間后繼續進行增量近鄰查詢，直到用戶找到圍繞自身均勻分布的k個興趣點.

算法2.均衡增量近鄰查詢算法.

輸入：用戶真實位置loc，隱私需求半徑r，錨點位置s，查詢內容con，目標數kresult.

輸出：查詢結果集.

1.wn←；//初始化小頂堆

2.γ←r；//初始化需求空間半徑

3.τ←0；//初始化供應空間半徑

4.count←0；//初始化查詢興趣點個數

5.send an INN query to the LBS server；

6.while(γ+dist(loc，s)>τ)do

7.for each p

8.count++；wn←p；τ←dist(s，p)；

9.if(dist(loc，p)<γ) then

10.γ←dist(loc，p)；

11.end if

12.end while

13.if(count

14.further for each p

15.count++；wn←p；τ←dist(s，p)；

16.end if

17.γ←dist(loc，pkresult)；

18.while(γ+dist(loc，s)>τ) do

19.further for each p

20.wn←p；τ←dist(s，p)；

21.end while

22.return the k points of interest inwn；

在算法2中，錨點s首先應該通過算法1計算得出.初始化需求空間半徑γ、供應空間半徑τ、查詢興趣點個數count、小頂堆wn.用戶使用錨點s發起k近鄰查詢，根據LBS服務器返回的興趣點，更新需求空間和供應空間，直到供應空間完全包含需求空間.然后查詢count是否不小于目標數kresult，如果count小于目標數kresult，查詢繼續，直到返回的興趣點數等于kresult.如圖2所示，是kresult=3時的增量近鄰查詢過程，圖2(a)為第一次供應空間包含需求空間，按照SpaceTwist算法描述，此時查詢結束，查詢結果為{p2，p3，p1}，但此時3個興趣點主要圍繞錨點分布，查詢不準確.為了讓用戶獲取圍繞自身分布的興趣點，繼續進行查詢.首先擴大需求空間半徑為dist(loc，kresult)，如圖2(b)，繼續查詢，如圖2(c)，直到供應空間再一次完全包含需求空間，查詢停止，如圖2(d).此時用戶獲取的查詢結果為{p2，p3，p6}，圍繞用戶當前位置均勻分布，查詢結果更準確.

圖2 均衡增量近鄰查詢過程Fig.2 Process of homogeneous incremental nearest neighbor query method

3 安全性分析

考慮兩種類型的對手：主動對手和被動對手.被動對手總是竊聽無線信道里的消息，進行修改，這種類型的攻擊可以通過使用一些成熟的加密技術來避免.因此，本文主要關注主動對手的共謀攻擊和推理攻擊，這兩種類型的攻擊會引發嚴重的隱私泄露問題.

我們的方法是抗共謀攻擊的.共謀攻擊經常發生在一組用戶之間，由于本文方法不存在和其他用戶交互，所以抗共謀攻擊.

我們的方法是抗推理攻擊的.隱藏函數f用來隱藏用戶真實位置，σ表示對手觀察干擾位置之后得到的結論.

理論1.如果對于f：x→f(x)，輸入集合X上的輔助信息π，干擾位置z?Z，機制K滿足ε-地理不可區分性，則：

dp(σ1，σ2)≤2εd(x，f(x))

其中σ1=Bayes(π，K，z)，σ2=Bayes(π，K·f，z)

此理論的解釋在文獻[16]中給出，這是標準差分隱私能應對有不同輔助信息的對手特點的使用，指出對手在觀察干擾位置之后得到的結論仍然相似，不管對手之前擁有何種輔助信息，查詢中用戶的真實位置是否使用，對手都不能以高概率猜測出用戶真實位置.本文通過在一定區域內向用戶真實位置添加拉普拉斯噪聲，使得生成的干擾位置和真實位置在這個區域內不可區分，滿足ε-地理不可區分性，有效抵擋有背景信息對手的推理攻擊.

4 實 驗

實驗在Windows7系統上用Java語言實現，運行環境為Intel Core i5、CPU3.2 GHz、4GB內存.實驗數據是Thomas Brinkhoff路網數據生成器生成的模擬數據并以Oldenburg城市的交通路網產生移動對象.本文采用以下4個指標來評價算法的有效性：

1)接近度.用戶設置隱私需求Qc實現ε-地理不可區分性時也要保證生成的干擾位置以盡可能大的概率落在這個區域內，接近度表示干擾位置和真實位置不同距離的比例.

2)數據通信量.查詢期間發送的消息數量.

4)響應時間.用戶發出查詢請求到LBS服務器返回的檢索結果滿足用戶需求的時間.

對于接近度，記擾動位置和真實位置的距離為d，圖3為r=0.5km，為不同值時對應不同d值時的比率.當=0.8時，超過97%的擾動位置在距真實位置1km范圍內，超過90%的擾動位置在距真實位置500m范圍內，超過70%的擾動位置在距真實位置300范圍內.隨著的增加，生成的擾動位置也越來越接近真實位置，但是較高的值會降低方法的實際意義，例如，當=0.2時，意味著必須接受7倍的概率(e2=7.39)差異的結果.

圖3 r=0.5 km時對應不同d值時的分布Fig.3 Distribution of different d value when r=0.5 km

對于數據通信量，如圖4所示，兩種方法的數據通信量均隨著用戶查詢興趣點個數k增加，但本文方法略高，這是由于需求空間再次擴大，查詢了更多的興趣點.雖然本文方法擴大了查找范圍，但查詢結果更準確，可以達到與SpaceTwist方法近似的數據通信量.

圖4 與SpaceTwist方法的數據通信量對比Fig.4 Comparison of the data traffic of the SpaceTwist method

圖5 與SpaceTwist方法的查詢相似度對比Fig.5 Comparison of query similarity of SpaceTwist method

由圖5可以看出，用戶通過本文方法得到的查詢結果和實際k近鄰查詢結果基本相符，查詢相似度達到了90%左右；而SpaceTwist方法的相似度隨著查詢點距離真實位置距離的增加逐漸上升并趨于一個穩定值，但始終達不到本文方法的相似度.這是因為SpaceTwist方法的查詢范圍無法覆蓋用戶期望的k近鄰結果的范圍，而本文方法不僅滿足用戶期望的k近鄰結果，同時解決了查詢興趣點圍繞錨點中心分布導致查詢結果不均衡的問題，提高了查詢相似度.

圖6 與SpaceTwist方法的響應時間對比Fig.6 Comparison of response time of SpaceTwist method

由圖6可以看出，SpaceTwist方法在查詢點距用戶位置距離增加時，返回的興趣點數越來越多，以至于響應時間也越來越長.本文方法相對于SpaceTwist方法增加了生成干擾位置過程和檢查LBS服務器返回的興趣點數滿足用戶期望的k近鄰結果，同時也使返回的興趣點數圍繞用戶真實位置均衡分布，所以在返回相同結果數時的響應時間比SpaceTwist方法更久，但響應時間也相對穩定，且在用戶可接受的范圍內.

5 結束語

本文提出一種位置擾動的隱私保護方法，相對于k-匿名方法，不再依賴TTP，同時介紹了一種新的隱私保護概念，地理不可區分性，向真實位置添加平面拉普拉斯噪聲生成干擾位置，能有效阻止有背景信息對手的攻擊，具有很強的隱私保護強度.采用均衡增量近鄰查詢算法進行查詢處理，使興趣點圍繞用戶真實位置均勻分布，提高了查詢準確性.后期工作中，如何排除一些不良擾動將是本文研究重點方向.