可預測的差分擾動用戶軌跡隱私保護方法

胡德敏,詹 涵

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

1 引 言

近年來,有定位能力移動設備的日益普及和無線通信技術的不斷提高,基于位置服務(loaction-based service,LBS)得到廣泛應用,給人們生活帶來極大便利,但用戶獲取服務的同時,也有可能泄露自己真實位置.如果用戶連續查詢,由于軌跡位置間的相關性更易泄露真實位置.

位置服務分兩種類型:快照LBS和連續LBS.快照LBS指用戶只發送一次當前位置信息給位置服務器獲取服務,連續LBS指用戶按照一定頻率周期性地發送當前位置信息給位置服務器獲取連續的服務.現實生活中,用戶多執行連續查詢,因此連續LBS軌跡隱私保護比快照LBS位置隱私保護更具有挑戰性.

2 相關工作

越來越多的學者開始關注連續LBS軌跡隱私保護.由于軌跡位置間的相關性,現有的快照LBS位置隱私保護方法在連續查詢時不能很好的起到軌跡隱私保護作用.因此,對用戶軌跡隱私保護需要提出更有效的方法,目前,這方面的研究主要有泛化、混合區和擾亂等方法[1].

泛化指用一個泛化的空間區域代替用戶真實位置,也稱隱藏區.文獻[2]提出一個支持連續空間查詢的k匿名隱藏區生成算法KAA.為了保證n次連續查詢后,該隱藏區仍然滿足k匿名,需要包含最初生成的k個用戶,因此隱藏區會隨著這k個用戶的運動而逐漸擴展,最終導致隱藏區因過大而失效.文獻[3]使用假名代替用戶真實身份的方法.但攻擊者可以很容易地從用戶日?；顒又蝎@得輔助信息,將用戶的假名與他的真實身份相關聯,因此,使用長期假名不足以保護用戶軌跡位置隱私.為了解決這個問題,Xu等人[4]提出將用戶的活動區域劃分為混合區和應用區,用戶在混合區交換假名,在應用區請求服務,混合區指的是一個小區域,例如一個道路交叉口.混合區打破了持續暴露的位置信息,從而保護了用戶的下一個位置,但混合區部署將影響查詢的服務質量.擾亂的方法在近年來有較多的研究,它的思想是將各個時刻的真實位置通過一定的變換,生成假位置,用假位置代替用戶真實位置請求服務.文獻[5]先使用DLG算法為每個快照位置生成一組虛假位置,再使用DPC算法將生成的虛假位置連接成幾條虛擬路徑,此方法無法判斷生成的虛擬軌跡是否合理.

近年來,開始采用差分隱私[6]來控制連續查詢中添加的噪聲量,把噪聲和隱私建立定量的關系.文獻[7]用馬爾科夫鏈表示兩個連續位置的關系,提出基于差分隱私的“δ位置集”來保護每個時間戳的真實位置,進而提出位置擾動機制PIM,但只考慮了單個時刻上的位置發布,忽略了已發布的當前位置對之前真實位置的影響.文獻[8]通過添加高斯噪聲,產生與原始軌跡序列自相關函數一致的相關性噪聲序列,但統計相關特性的方法只適用于相關性較強的平穩序列中,對于非平穩序列不再適用.文獻[9]將原始軌跡數據集轉換成用戶位置二分圖,并且注入仔細校準的噪聲以滿足所需的差分隱私保證,但關聯矩陣的選擇是一個問題.文獻[10]向用戶真實位置添加可控的平面拉普拉斯噪聲生成干擾位置并將其作為錨點發送給位置服務商,解決了單次查詢的位置隱私保護問題.若將該方法直接用于連續查詢,由于軌跡位置間的相關性,隨著查詢次數的增加,用戶軌跡位置隱私水平越來越低.

雖然差分隱私機制作為一種隨機擾動方法被廣泛研究,但現有的軌跡差分隱私保護方法大多將軌跡位置作為獨立的序列來處理,添加獨立的噪聲,攻擊者可以利用一些濾除噪聲的方法過濾噪聲,同時利用軌跡間位置的相關性提高推測成功的概率.

本文提出一種可預測的差分擾動軌跡隱私保護方法.由預測函數、測試函數和噪聲機制三部分構成,如果預測函數生成的干擾位置通過測試函數,則直接使用該干擾位置去請求服務,否則使用噪聲機制向當前真實位置添加噪聲,重新生成一個干擾位置去請求服務.

本文的組織結構如下:第1節介紹軌跡隱私保護的背景;第2節介紹軌跡隱私保護的研究現狀;第3節描述可預測的差分擾動用戶軌跡隱私保護方法;第4節進行實驗以及實驗結果分析;第5節對全文進行總結.

3 可預測的差分擾動用戶軌跡隱私保護方法

3.1 相關定義

定義1.用戶軌跡T={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)}.其中(xn,yn,tn)表示用戶在tn時刻的位置為(xn,yn),T[i]表示軌跡T的第i個元素,|T|=n表示軌跡T的長度.

定義2.用戶軌跡隱私需求Tq={ε,r}.其中ε表示軌跡隱私水平即軌跡隱私預算,r表示隱私保護區域的半徑.

3.2 獨立噪聲機制

文獻[10]通過向用戶真實位置添加平面拉普拉斯噪聲生成干擾位置,用該干擾位置代替用戶真實位置請求位置服務器獲取服務.在連續查詢中,如果以同樣的方法向用戶軌跡中的每個真實位置都添加這樣的噪聲,為每個位置生成一個干擾位置,同時生成一條虛假軌跡稱做獨立噪聲機制(Independent Noise Mechanism,INM),算法1中N(εN)表示噪聲機制,εN表示噪聲機制隱私水平,滿足εN-地理不可區分性.

用戶每次查詢都會消耗一部分隱私預算,連續n次查詢消耗n次隱私預算,當隱私預算全部消耗完時查詢停止.由于軌跡位置間的相關性,隨著查詢次數的增加,位置點越來越多,隱私程度越來越低,隱私水平要求也越來越高,消耗的隱私預算總比前一次要多,導致隱私預算快速消耗.因此,該方法僅在查詢次數很少時才適用.

算法1.獨立噪聲機制INM

輸入:用戶軌跡T,隱私水平εN;

輸出:虛假軌跡T′.

1.T′←0;

2.for(i=1;i++;i≤|n|);

3.z←N(εN)(T[i]);//為每個真實位置生成干擾位置

4.add z toT′;

5.returnT′;

3.3 預測噪聲機制

預測噪聲機制(Predictive Noise Mechanism,PNM)由預測函數Ω、測試函數Θ和噪聲機制N組成.預測函數Ω根據已有的干擾位置預測一個新的接近真實位置的點,如果該點通過測試函數,直接使用該點請求服務;若未通過,則用噪聲機制N重新生成一個干擾位置,用新生成的這個干擾位置代替用戶真實位置去請求服務.軌跡位置間的相關性是預測噪聲機制較大的一個優點,相關性越高,生成的干擾位置通過測試概率越大,需要重新添加噪聲的真實位置點越少,測試函數消耗的隱私預算遠低于噪聲機制消耗的隱私預算.

a)預測函數

序列r=[z1,b1,z2,b2,…,zn,bn]由每個真實位置對應的干擾位置和布爾值b組成.其中z表示干擾位置,布爾值b表示干擾位置是否通過了測試,b=0通過,稱當前真實位置為容易點,b=1未通過,稱當前真實位置為困難點.預測函數Ω:r→z以序列r為輸入,當前真實位置的預測干擾位置z為輸出.

b)測試函數

測試函數Θ(εθ,l,z):x→b,以當前真實位置x為輸入,b為輸出,測試z是否可用作當前真實位置的干擾位置.如果測試成功,z直接使用;否則,使用噪聲機制N重新另生成一個干擾位置,測試函數定義如下:

(1)

其中,d(,)是兩點之間的歐幾里得距離,測試函數消耗的隱私預算εθ>0,測試閾值l∈[0,+∞),Lap(εθ)為測試函數添加的線性拉普拉斯噪聲,干擾位置z∈Z,真實位置x∈R2.

c)噪聲機制

噪聲機制[10]N(εN):x→z,其中εN表示噪聲機制消耗的隱私預算.即利用差分隱私按照期望的隱私預算,向用戶真實位置添加可控的拉普拉斯噪聲產生擾動,該擾動位置在一定范圍內和用戶真實位置不可區分,文獻[10]詳細講解了以下算法.

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

輸入:用戶位置Ω,隱私需求Θ(εθ,l,z),用戶所在區域N(εN),位置坐標精度T′,可接受區域半徑ψ=neasy/|T|.

輸出:干擾位置neasy.

1.ρ=εβ(r)/ε;

3.calculate angelεuniformly inρ;//計算derr

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;

噪聲機制用來給未通過測試的干擾位置為相應的真實位置添加噪聲,用算法1重新生成一個干擾位置請求服務.

d)預算管理器

測試函數的參數εθ,l和噪聲機制的參數εN在每步都需要重新計算,這通過預算管理器β動態配置.β(r)=(εθ,εN,l)以當前時刻的序列r為輸入,以測試函數和噪聲機制的參數εθ,l,εN為輸出.測試函數消耗的隱私預算遠小于噪聲機制消耗的隱私預算,否則使用獨立噪聲機制更加方便.軌跡間位置的相關性越高,預測點大部分通過測試,不需要額外添加噪聲;若相關性太低,測試總是失敗,不僅噪聲機制消耗隱私預算,測試函數消耗也需要消耗隱私預算,這種情況下隱私預算水平消耗迅速.

使用預算管理器β配置序列r的預算εβ(r)定義如下:

(2)

其中,βθ(r)為當前測試函數消耗的隱私預算,b(r)為測試函數結果,βN(r)為噪聲機制消耗的隱私預算,εβ(r-1)為之前序列消耗的隱私預算.

我們知道,測試函數Θ對于?εθ,l,z滿足εθ-地理不可區分性,噪聲機制N對于?εN滿足εN-地理不可區分性,則預測噪聲機制PNM滿足εβ(r)-地理不可區分性,如下,

PIM(T)(r)≤eεβ(r)d(x,x′)PIM(T′)(r)

(3)

預測噪聲機制的準確性α(δ)取決于噪聲機制N(εN)的準確性和測試函數添加的拉普拉斯機制Lap(εθ)的準確性,分別用αN(δ)和αθ(δ)表示,則α(δ)=max(αN(δ),l+αθ(δ)),通常取δ=0.9.

引入一個參數γ調節測試閾值?和添加的線性拉普拉斯噪聲比例,γ=αθ/l(0≤γ≤1),γ不能超過1,否則添加的噪聲比閾值l還大,通常把γ設置為0.8.介紹兩種預算管理器:限制軌跡偏移度和固定隱私預算消耗率.

1) 限制軌跡偏移度

我們總是希望生成的虛假軌跡盡可能接近真實軌跡,如果距離太遠得不到想要的服務質量,軌跡隱私保護也不再有意義,考慮限制軌跡偏移度的情況下,用戶需要提供參數ε.

預算管理器1.限制軌跡偏移度

budget managerβ(r)

ifε(r)≥εthen stop

returnεθ,εN,l;

2) 固定隱私預算消耗率

2)困難點在軌跡中均勻分布.這兩個假設幫助計算預測成功率,預測成功率越高,噪聲機制消耗隱私預算越少.ρ在固定隱私預算消耗率情況下是常量,在限制軌跡偏移度情況下動態計算.

預算管理器2.固定隱私消耗率

budget managerβ(r)

ifε(r)≥εthen stop

returnεθ,εN,l;

若預算管理器β返回的參數εθ=0,l=+∞,此時測試函數一定值為0;若預算管理器β返回的參數εθ=0,l=-∞,此時測試函數一定值為1,此時選擇跳過測試函數以節約隱私預算水平.

預測噪聲機制PNM整體算法描述如下:

算法3.預測噪聲機制PNM

輸入:用戶軌跡T,軌跡隱私預算ε.

輸出:虛假軌跡T′.

1.T′←0,r←0;

2.for(i=1;i++;i≤|n|) do;

3.β(r)=(εθ,εN,l);//預算管理器動態配置參數εθ,εN,l

4.z←Ω(r);//預測函數生成干擾位置

5.b←Θ(εθ,εN,l);//測試函數測試干擾位置是否通過測試

6. if(b=0)thenz′←z

7. elsez′←N(εN)(x)//沒有通過測試使用噪聲機制

8. end if

9.addb,z′ to r

10.end for;

11.returnr,T′;

算法3中,首先通過預算管理器配置預測噪聲機制每步需要的參數,以當前時刻的結果訓練r為輸入,輸出測試函數需要的隱私預算εθ,l,噪聲機制需要的隱私預算εN,然后運行預測函數Ω得到預測干擾位置z,再使用測試函數Θ(εθ,l,z)測試預測.如果測試成功,則返回預測,否則使用噪聲機制N(εN)生成新的干擾位置,最后得到用戶真實軌跡對應的虛假軌跡T′.

4 實 驗

實驗在Windows7系統上用Java語言實現,運行環境為Intel Core i5、CPU3.2 GHz、4GB內存.實驗數據來自著名的數據集GeoLife[11],它收集了北京182個用戶軌跡,軌跡長度大致劃分三組:小于5公里、5-20公里和20公里以上,用戶移動時間58%少于1小時,26%為1至6小時內,16%為6小時以上.我們假設用戶僅在靜止或以低速(低于15km/h)移動時才查詢LBS,如果位置變化很快,那么查詢相對于當前位置信息沒有意義.

數據集僅收集了用戶移動軌跡,而不是用戶實際查詢LBS的位置點集合,為了符合真實LBS場景,對數據集做一些預處理,根據用戶的移動速度,選擇速度小于15公里/時的軌跡部分,采用3個指標來評價算法的有效性:

1)預測成功率.預測成功率ψ=neasy/|T|表示預測函數輸出的干擾位置是容易點的個數占總位置個數的比例,其中neasy表示生成干擾位置是容易點的個數.

2)隱私預算消耗率.軌跡中每個發送請求位置消耗的隱私預算率ρ=εβ(r)/ε,表示預測噪聲機制隱私預算消耗的速率,通過這個值,可以知道隱私預算需消耗的有多快,大概估算初始預算下能夠覆蓋多少個查詢點.

雖然該機制的目的是隱藏用戶真實位置,但每個位置發出請求的時間是公開的,我們可以使用上一位置請求服務的時間來估計用戶可能已經經過的距離.如果這個距離小于所要求的范圍,那么相鄰的這兩個位置一定滿足ε-地理不可區分性,我們可以跳過測試直接使用上一位置生成的干擾位置.如果用戶比預期的要快(比如他坐的是地鐵),預測函數將會預測出一個不準確的干擾位置.這種方法的風險在于關聯時間和移動距離的速度,為了安全起見,應該設定期望的最大移動速度,值太小跳過的測試點太多沒有意義,值太大達不到所要求的偏移范圍.

假設用戶移動速度v=0.8km/h,同時設定r=0.5km,ε=In10,ε是全局隱私水平,表明在半徑r為0.5km的范圍區域內,任意兩點生成同一干擾位置的可能性最多相差10,這在人口密集的城市區域是一個合理的隱私水平.如果固定隱私消耗率為3%,對應大約30次查詢,對大多數用戶來說,是一個合理的查詢次數,如果限制軌跡偏移度在3公里范圍內,對步行用戶來說,也是一個合理的范圍.

為了便于實驗觀察,選取8個用戶作為連續查詢用戶,分別以t=5min、10min、15min、20min、25min、30min、35min、40min作為查詢時間間隔,t值越小表明查詢越頻繁,依次編號1,2,3,4,5,6,7,8.選取符合要求的用戶軌跡分別運行預測噪聲機制PNM和獨立噪聲機制INM20次,計算其平均值,先固定隱私預算消耗率,得到實驗結果如圖1-圖3所示.

由圖1可以看出,預測函數生成干擾位置的預測成功率隨查詢時間間隔的變長而逐漸減小.查詢時間間隔短,查詢頻繁,生成的干擾位置點就越多,預測函數的輸入結果序列r越長,預測輸出干擾位置更加準確,預測成功率也更高.同樣變化的是跳過測試函數的干擾位置個數,預測成功率越高,跳過測試函數的干擾位置個數也越多,節省更多的隱私預算.

圖1 預測噪聲機制統計數據Fig.1 Prediction noise mechanism statistics

由圖2和圖3可以看出,固定隱私預算消耗率ρ為3%,預測噪聲機制的隱私預算消耗率整體來說較平穩且接近獨立噪聲機制.軌跡偏移度上因軌跡間位置相關性,預測噪聲機制性能要優于獨立噪聲機制,但兩者均隨著時間而逐漸增大.

圖2 預測噪聲機制和獨立噪聲機制軌跡偏移度對比Fig.2 Comparison of predicted noise mechanism and independent noise mechanism trajectory offset

圖3 預測噪聲機制和獨立噪聲機制隱私預算消耗率對比Fig.3 Comparison of predictive noise mechanism and independent noise mechanism privacy budget consumption rate

現在限制軌跡偏移度derr在3公里范圍內,得到實驗結果如圖4-圖6所示.由圖4可以看出,和固定隱私預算消耗率一樣,預測成功率和跳過測試點仍然隨著查詢更加偶然而呈下降趨勢,但是比固定隱私預算消耗率速率緩慢的多,這是因為限制了軌跡偏移度范圍,使得出的干擾位置點更接近用戶查詢真實位置,預測成功率自然也更高.

圖4 預測噪聲機制統計數據Fig.4 Prediction noise mechanism statistics

由圖5和圖6可以看出,限制軌跡偏移度情況下,獨立噪聲機制INM軌跡偏移度為一常量3000m,而預測噪聲機制PNM小幅度波動,但沒有超過3000m;隱私預算消耗率比固定隱私預算消耗率情況下消耗更多,且隨著查詢間隔時間變長而逐漸增大.

圖5 預測噪聲機制和獨立噪聲機制軌跡偏移度對比Fig.5 Comparison of predicted noise mechanism and independent noise mechanism trajectory offset

圖6 預測噪聲機制和獨立噪聲機制隱私預算消耗率對比Fig.6 Comparison of predictive noise mechanism and independent noise mechanism privacy budget consumption rate

5 結束語

本文提出一種可預測的差分擾動軌跡隱私保護方法,通過預測噪聲機制實現,預測噪聲機制由預測函數、測試函數和噪聲機制三部分組成,同時使用兩種預算管理器來配置測試函數和噪聲機制需要的參數,節省每次查詢時消耗的隱私預算.實驗結果表明,不管是固定隱私預算消耗率還是限制軌跡偏移度,與獨立添加平面拉普拉斯噪聲到軌跡中的每個位置相比,預測噪聲機制在軌跡偏移度和隱私預算消耗率上均有較高優勢,很好地解決了用戶軌跡位置隱私保護問題.