基于差分隱私的混合位置隱私保護

徐啟元 陳珍萍 付保川 許馨尹 邵雪蓮

(蘇州科技大學(xué)電子與信息工程學(xué)院 江蘇 蘇州 215009)

0 引 言

隨著智能終端的廣泛應(yīng)用，智能手機、平板等設(shè)備已經(jīng)成為人們生活中的必須品，用戶使用全球定位系統(tǒng)(Global Position System，GPS)和通信運營商的定位服務(wù)也在日益精確，基于位置的服務(wù)(Location-Based Services，LBS)得到越來越廣泛的應(yīng)用，用戶可以通過這些LBS應(yīng)用搜索附近的所有餐廳、距離自己最近的電影院等[1]。然而，LBS的廣泛應(yīng)用也帶來了一系列問題，其中一個重要問題就是用戶位置信息存在被泄露的風(fēng)險[2]。近些年來，關(guān)于位置隱私保護的研究非常活躍，取得了很多研究成果。

文獻[3]采用模糊策略對位置進行模糊化處理，雖然可以保護位置隱私，但影響了感知數(shù)據(jù)的服務(wù)質(zhì)量，降低了數(shù)據(jù)可用性。文獻[4]采用假名替換，即把用戶真實身份用預(yù)先設(shè)定的假名替代，從而隱藏了用戶真實身份，但若攻擊者掌握了替代規(guī)律，也可能挖掘出用戶的真實信息。文獻[5-6]通過K-匿名方法來保護位置隱私，將K個用戶位置組成一個匿名集，使得攻擊者即使獲得了每個用戶的具體位置，仍無法從K個用戶中確定真正的查詢請求用戶，從而在一定程度上達到了保護用戶位置隱私的目的。然而，K的增加可能會使隱形區(qū)域最大化，由于是在服務(wù)器端處理開銷，導(dǎo)致響應(yīng)時間延遲。因此，隱形區(qū)域的最大化可能會降低LBS應(yīng)用程序提供查詢服務(wù)的質(zhì)量。文獻[7]提出了地理l-多樣性原則，要求用戶位置信息不能被l個位置集所識別，防止由于用戶間相距過近而被攻擊者推導(dǎo)出用戶所處區(qū)域的大致位置。

上述方法都是在假定對手沒有用戶背景信息的基礎(chǔ)上進行的研究，因而當(dāng)對手擁有用戶的背景信息時，上述方法很可能將用戶的信息泄露，例如在利用k-means聚類算法進行位置泛化時，簡單地通過歐幾里得函數(shù)計算每個距離當(dāng)前用戶位置最近的聚類中心很容易遭到數(shù)據(jù)攻擊進而泄露位置信息。文獻[8]提出一種將k-means聚類算法與差分隱私保護技術(shù)相結(jié)合的方法，差分隱私是一種具有完全獨立于攻擊者背景信息的強隱私保護技術(shù)，使得該方法具有較強的隱私保護能力。但是在仿真實驗過程中，這種差分隱私k-means隱私保護方法的聚類結(jié)果可用性較低，本文針對這一問題并結(jié)合LBS的自身特點提出一種基于差分隱私的k-means混合位置隱私保護方法。

用戶先將位置發(fā)送到可信匿名服務(wù)器，通過對用戶位置的人流密度參數(shù)進行分析將用戶位置點分成離散位置點和非離散位置點。對于離散點我們采用基于差分隱私的單獨加噪技術(shù)進行隱私保護；對于非離散點，選取其中人流密度較大的點作為初始聚類中心點，通過改進的k-means聚類算法來實現(xiàn)位置數(shù)據(jù)的泛化處理，并在泛化過程中使用差分隱私技術(shù)對可能泄露的發(fā)布數(shù)據(jù)進行加噪，最終將算法收斂后的聚類中心點和離散點位置集發(fā)送給LBS服務(wù)器來獲取位置服務(wù)。仿真實驗證明算法能夠在相同隱私性的條件下提高數(shù)據(jù)的可用性。

1 位置隱私保護模型

1.1 差分隱私技術(shù)

差分隱私技術(shù)是文獻[9]提出的，是一種與背景知識無關(guān)的強隱私保護模型。文獻[10]在此基礎(chǔ)上提出位置差分隱私，其定義如下：

定義1ε-位置差分隱私:對于2個位置數(shù)據(jù)集D和D′，假定兩者最多只有一條位置信息不同，即兩者的線性相異距離|D-D′|≤1，M為隨機查詢函數(shù)，并具有差分隱私保護，Rang(M)代表M的取值范圍，若D和D′在查詢函數(shù)M下得到的任意位置L(L?Rang(M))滿足下式，則查詢函數(shù)M滿足ε-位置差分隱私[10]。

Pr[M(D)∈L]≤Pr[M(D′)∈L]eε

(1)

式中:Pr[·]表示位置信息被泄露的概率，由算法M的隨機性控制；參數(shù)ε為隱私保護預(yù)算，ε越小隱私保護程度越高。

全局敏感度是差分隱私保護算法的一個重要度量指標(biāo)。它的大小只與函數(shù)f本身有關(guān)，與數(shù)據(jù)集大小無關(guān)。全局敏感度的定義如下。

定義2全局敏感度[11]:對于任意函數(shù)f:D→Rd，f的全局敏感度定義為:

(2)

差分隱私保護的實現(xiàn)機制主要有拉普拉斯機制[12]和指數(shù)機制[13]，其中拉普拉斯機制多用于數(shù)值型數(shù)據(jù)，指數(shù)機制一般用于非數(shù)值型數(shù)據(jù)。本文采用拉普拉斯加噪機制。

定義3拉普拉斯機制:給定位置數(shù)據(jù)集D，對任意函數(shù)f:D→Rd，其敏感度為Δf，若函數(shù)f輸出結(jié)果滿足：

M(DM)=f(DM)+Lap(b)

(3)

1.2 位置隱私保護

標(biāo)準(zhǔn)差分隱私被證明可以應(yīng)用于有多用戶位置的信息發(fā)布，但并不適用單個用戶位置。文獻[14]提出一種滿足差分隱私的地理不可區(qū)分性理論，它通過向用戶的真實位置添加平面拉普拉斯噪聲生成干擾位置，這種滿足差分隱私的加噪方式即使被有背景信息的對手觀察到，也不能以較高準(zhǔn)確率判斷出真實位置。

對于用戶位置x=(s,t)，其中s和t分別為位置的二維坐標(biāo)，給定隱私保護預(yù)算ε，若添加噪聲后生成位置x′的概率P(x)(x′)滿足：

(4)

則稱該加噪保護機制滿足ε-位置差分隱私。

從式(4)可以看出，在隱私預(yù)算ε一定且d(x,x′)>0時，概率P(x)(x′)隨著x′到x的距離增大而減小，取值只與x′到x的距離d(x,x′)有關(guān)。為簡化起見，可將該概率轉(zhuǎn)化為極坐標(biāo)形式，具體為：

(5)

式中:r表示x′到x的距離，θ為x′在極坐標(biāo)下與極軸的夾角。同樣可將式(5)分解到半徑R和角度Θ上，以得到如下概率分布函數(shù)：

(6)

(7)

2 混合位置隱私保護方法

現(xiàn)有差分隱私k-means算法在進行位置數(shù)據(jù)的隱私保護時，少量的離群點會導(dǎo)致算法輸出結(jié)果產(chǎn)生較大的偏差，且對初始中心點較為敏感，導(dǎo)致其具有較低的位置數(shù)據(jù)可用性。本文提出一種混合位置隱私保護方法，在k-means算法進行初始中心點選擇時，根據(jù)不同地理空間區(qū)域人流密度的不同，將一些離群用戶從用戶集合中剔除，以減少因為離群點對聚類穩(wěn)定性的干擾。然后將初始中心點分配到人流較集中的區(qū)域而不是隨機選取，使初始中心點距離最終輸出的中心點位置較接近，減少算法的迭代次數(shù)，提高了聚類結(jié)果的穩(wěn)定性和LBS服務(wù)的可用性。對于離群用戶點進行單獨加噪方法來對其進行位置隱私保護。本文所提方法根據(jù)不同用戶周圍人流密度的不同，采取的混合隱私保護方法可以提高聚類的穩(wěn)定性，同時也對離群位置點進行了很好的隱私保護。

2.1 離群點的判定

對于用戶位置數(shù)據(jù)集X={x1,x2,…,xn}，任一用戶位置點xi為中心、半徑為Rm的區(qū)域稱為點xi的鄰域，領(lǐng)域內(nèi)的用戶數(shù)ui稱為點xi基于Rm的人流密度。對包含有n個用戶的數(shù)據(jù)集X={x1,x2,…,xn}，取用戶間的平均距離為半徑Rm，則Rm可為：

(8)

ui=|Ni|Ni={xj|d(xi,xj)≤Rm}

(9)

ui值可以反映位置xi周圍點的稀疏程度。

離群點是指與其他點有明顯不同的數(shù)據(jù)點，一般可分為全局離群點、情境離群點、集體離群點[15-16]，鑒于本文主要面對的是數(shù)值型數(shù)據(jù)的保護，不涉及具體情境或者群組，因此只考慮全局離群點，即位置數(shù)據(jù)集X={x1,x2,…,xn}中與其余點差別均很大的數(shù)據(jù)點。對于離群點的判定，由文獻[17]數(shù)據(jù)集中X的稀有類由至多5%的數(shù)據(jù)點組成，因而數(shù)據(jù)集中離群點數(shù)目nD不超過n×0.05，可表示為nD=└n×0.05┘ 。對于位置數(shù)據(jù)集X={x1,x2,…,xn}的nD個離群點的判定，可通過式(9)計算得到的每個位置點xi處的人流密度參數(shù)ui，取密度參數(shù)最小的nD個點作為位置隱私保護中的離群點。

2.2 離群點隱私保護方法

在本文所提混合位置隱私保護中，對于離群點采用單獨加噪的方法來進行隱私保護。具體如算法1所示。

算法1離群點隱私保護

輸入：用戶位置數(shù)據(jù)集X={x1,x2,…,xn}(xi=(st,ti)，隱私預(yù)算ε；

輸出：加噪離群點集D′，非離群點集X2。

2) 由式(9)計算每個位置點xi處的人流密度參數(shù)ui(i=1,2,…,n)；

確定位置極坐標(biāo)表的隨機噪聲ri和θi，其中θi為[0,2π)間均勻分布隨機數(shù)，νi為[0,1)間均勻分布的隨機數(shù)，而Cε(νi)為概率密度函數(shù)Pε,r(νi)在[0,νi]上的積分函數(shù)，滿足：

用以表示隨機半徑ri落在0到νi上的累積概率。

5) 按照：

2.3 混合k-means隱私保護方法

算法2混合k-means隱私保護

輸出：差分隱私保護的位置數(shù)據(jù)集X′=D′∪C″。

確定位置極坐標(biāo)表的隨機噪聲ri和θi，νi為[0,1)間均勻分布的隨機數(shù)，而Cε(νi)為概率密度函數(shù)Dε,r(νi)在[0,νi]上的積分函數(shù)，按照：

8) 輸出通過差分隱私保護的位置數(shù)據(jù)集X′=D′∪C″。

這時離散點的位置由單獨加噪后的位置代替，非離散點的原始位置由加噪后的聚類中心點代替。

3 仿真結(jié)果與分析

為驗證本文所提混合位置隱私保護方法的有效性，在MATLAB仿真平臺上進行算法的數(shù)值仿真。數(shù)值仿真主要關(guān)注目標(biāo)為用戶在獲取LBS服務(wù)的過程中位置數(shù)據(jù)的安全性和可用性，以及改進算法在聚類過程中的聚類效果。

3.1 參數(shù)設(shè)置

本實驗在MATLAB環(huán)境中在2×2的空間隨機生成n=80個二維數(shù)據(jù)點來模擬用戶位置，也即有用戶xi=(si,ti)(i=1,2,…,n)，si∈(0,2),ti∈(0,2)。聚類簇數(shù)通過文獻[18]給出的評價指標(biāo)誤差平方和(Sum of the Squared Errors，SSE)來確定，通過計算不同k值下的SSE觀察到當(dāng)k取3為其最佳聚類數(shù)，因此取k=3，對算法運行10次取平均值作為輸出的結(jié)果進行比較分析。

3.2 聚類誤差分析

下面進行本文所提混合位置隱私保護方法、基于差分隱私的k-means算法以及位置單獨加噪方法的聚類誤差Error的分析。分別記E1、E2、E3為本文所提差分隱私k-means混合隱私保護方法、單獨加噪和傳統(tǒng)差分隱私k-means方法運行結(jié)果的偏移誤差，即每個位置點的原始位置與輸出的加噪后的查詢位置點之間的誤差。

圖1 本文算法的聚類輸出結(jié)果，其中ε=2

圖2 不同隱私預(yù)算ε下對算法誤差的影響

通過圖2可以看出，在隱私預(yù)算ε較小的時候，三種加噪方法的輸出距離原始數(shù)據(jù)誤差均過大；隨著隱私預(yù)算ε的不斷增加，誤差先是急劇減小，然后下降幅度逐漸減少并趨于穩(wěn)定。因而在實際應(yīng)用過程中，可以取趨于穩(wěn)定后并且ε較小的值作為隱私預(yù)算。通過比較三種不同的加噪方式發(fā)現(xiàn)，在相同的隱私預(yù)算ε下本文提出的混合位置隱私保護算法的誤差比另外兩種算法的誤差較小。

3.3 數(shù)據(jù)可用性分析

(10)

圖3 不同隱私預(yù)算ε下的F-measure運行結(jié)果

通過圖3可以看出，本文提出的基于差分隱私的混合k-means聚類算法滿足ε差分隱私的要求，能夠有效地保護用戶的位置隱私，并且與差分隱私k-means算法相比，F(xiàn)-measure值有了較大提升，這說明本文提出的算法在相同隱私預(yù)算ε下具有更高的數(shù)據(jù)可用性。

4 結(jié) 語

對于傳統(tǒng)使用k-means進行數(shù)據(jù)泛化可能導(dǎo)致位置數(shù)據(jù)泄露的問題，本文提出了一種結(jié)合LBS數(shù)據(jù)特點的差分隱私混合k-means位置隱私保護算法。通過使用密度參數(shù)來選擇聚類的初始中心點，對中心點和聚類過程中可能泄露用戶隱私的數(shù)據(jù)添加滿足差分隱私的Laplace噪聲，并將離散點提取出來單獨加噪減少來增加聚類可用性。實驗結(jié)果表明，改進后的算法減少了聚類中簇的迭代次數(shù)，提高了聚類中心精度，并且在添加相同噪聲的情況下提高了位置數(shù)據(jù)的可用性。下一步將根據(jù)用戶對查詢結(jié)果的反饋，根據(jù)不同用戶對數(shù)據(jù)的隱私需求程度不同添加不同的噪聲等級，從而給用戶更好的LBS體驗和滿足用戶的安全性要求。