基于本地化差分隱私的時序位置發(fā)布方案研究

康海燕，冀源蕊

（北京信息科技大學(xué)信息管理學(xué)院信息安全系，北京 100192）

1 引言

隨著GPS定位技術(shù)和可穿戴設(shè)備的廣泛應(yīng)用，基于位置的服務(wù)（Location Based Service，LBS）可以提供諸如實時位置共享、路線導(dǎo)航和興趣點查詢等服務(wù)，為人們的生活提供了便利.與此同時，這些移動設(shè)備不斷記錄著用戶的位置數(shù)據(jù)，LBS服務(wù)通過收集并發(fā)布這些位置數(shù)據(jù)可以為數(shù)據(jù)分析提供基礎(chǔ)數(shù)據(jù)，結(jié)合數(shù)據(jù)挖掘和機器學(xué)習(xí)等技術(shù)對位置軌跡大數(shù)據(jù)的分析，企業(yè)可以用挖掘有價值的商業(yè)信息，政府部門可以通過分析交通數(shù)據(jù)進行道路規(guī)劃［1］，在COVID-19疫情防控背景下，政府部門可以通過對用戶位置數(shù)據(jù)的收集和分析實現(xiàn)接觸者追蹤和疫情傳播監(jiān)控［2］.然而位置數(shù)據(jù)中包含大量個體的隱私信息，如果不加保護直接發(fā)布會造成大量用戶的隱私泄露，用戶對隱私問題的顧慮限制了其分享個人位置數(shù)據(jù)的意愿，阻礙了位置大數(shù)據(jù)的收集和分析工作，因此針對位置數(shù)據(jù)發(fā)布時的隱私保護研究具有必要性.

最早用于解決位置數(shù)據(jù)隱私發(fā)布的方案是k-匿名技術(shù)，如Gedik等［3］提出的匿名位置發(fā)布方法，通過對軌跡Ti在任意時刻采樣，使得在該時刻內(nèi)，至少有k-1條軌跡在相應(yīng)的位置能和Ti泛化在同一區(qū)域內(nèi)然而k-匿名理論面臨的最大問題是，一旦攻擊者能力超過了預(yù)先的假設(shè)，就能夠進一步區(qū)分等價類內(nèi)的不同記錄，實現(xiàn)去匿名化.由Dwork等［4］提出的差分隱私技術(shù)因其嚴格的數(shù)學(xué)定義備受青睞，是目前最受歡迎的隱私保護技術(shù)，在隱私保護的數(shù)據(jù)分析與數(shù)據(jù)發(fā)布領(lǐng)域應(yīng)用廣泛［5］.而在位置軌跡隱私發(fā)布背景下，基于差分隱私模型的研究同樣取得了許多成果［6～17］.然而現(xiàn)有的差分隱私模型下位置軌跡發(fā)布的方案存在以下不足：（1）現(xiàn)有方案基于第三方LBS服務(wù)可信的前提假設(shè)，對收集到的位置數(shù)據(jù)進行集中加噪處理后再發(fā)布，沒有考慮第三方服務(wù)器不可信的情況.（2）現(xiàn)有方案在隱私保護選擇上不夠靈活，只允許用戶根據(jù)單一的隱私預(yù)算決定隱私保護程度.（3）現(xiàn)有方案將軌跡發(fā)布看作一系列連續(xù)位置的發(fā)布，沒有考慮連續(xù)提交多個位置數(shù)據(jù)的情況下時序關(guān)聯(lián)對位置隱私發(fā)布的影響.

為了解決以上問題，本文進行了深入研究，主要貢獻如下：（1）提出一種定制隱私策略位置擾動算法（Customized Privacy policy Location Perturbation algorithm，CPLP），允許用戶在本地對位置數(shù)據(jù)加噪后上傳給LBS服務(wù)器，通過定制隱私策略實現(xiàn)多隱私因子支持.（2）結(jié)合隱馬爾可夫模型提出一種時序關(guān)聯(lián)位置隱私發(fā)布算法（Temporal Relational Location Privacy publishing algorithm，TRLP），解決時序關(guān)聯(lián)對位置隱私發(fā)布的影響.（3）在GeoLife數(shù)據(jù)集和Gowalla數(shù)據(jù)集上通過大量的對比實驗驗證了該模型的可用性.

2 研究現(xiàn)狀

2.1 中心化差分隱私位置數(shù)據(jù)發(fā)布

中心化差分隱私模型下的位置數(shù)據(jù)發(fā)布形式包括空間直方圖、地理位置熵和軌跡數(shù)據(jù)集.空間直方圖是位置軌跡發(fā)布的經(jīng)典形式，差分隱私模型通過對空間直方圖添加隨機噪聲，發(fā)布加噪后的直方圖來抵御攻擊者對于數(shù)據(jù)集中是否包含某用戶的推測攻擊.然而直接對構(gòu)成直方圖的每個網(wǎng)格單元添加噪聲導(dǎo)致查詢結(jié)果的誤差太大，為了提高任意范圍內(nèi)查詢結(jié)果的精度，通常采用四叉樹［9］對劃分后的網(wǎng)格提供索引服務(wù)，樹中的每個節(jié)點代表本區(qū)域范圍內(nèi)的位置軌跡數(shù)目，由于該數(shù)目涉及用戶的位置隱私，通過對節(jié)點計數(shù)查詢添加噪聲實現(xiàn)差分隱私，在響應(yīng)用戶的計數(shù)查詢時，采用類似索引樹的查詢模式自上而下在四叉樹中搜索與該查詢節(jié)點匹配的節(jié)點集合，根據(jù)加噪后的節(jié)點計數(shù)結(jié)果進行回答.為了解決位置數(shù)據(jù)分布不均衡導(dǎo)致四叉樹中添加噪聲過大的問題，Hay等［10］提出一種基于k-叉平均樹的位置數(shù)據(jù)構(gòu)建方法，使得劃分后直方圖各個區(qū)間內(nèi)位置軌跡數(shù)目比較均衡，同時通過最優(yōu)線性無偏估計對其進行一致性修正，降低中間節(jié)點造成的查詢噪聲誤差.Zhang等［11］提出一種基于不完全四叉樹的位置發(fā)布方法PrivTree，通過對高維空間數(shù)據(jù)進行合理的劃分擺脫了加入噪聲時樹高的影響，并采用局部敏感度和近似誤差的方法降低噪聲誤差.為了解決軌跡中多個單元的子軌跡被重復(fù)計數(shù)導(dǎo)致大范圍內(nèi)軌跡聚集查詢誤差較大的問題，Xie等［12］提出了層次化模型（Euler Histograms Tree，EHT），通過降低子軌跡重復(fù)帶來的查詢誤差以支持矩形空間聚集查詢.除了直接發(fā)布位置軌跡的計數(shù)信息，位置相關(guān)統(tǒng)計信息還包括位置熵（Location Entropy，LE），位置熵以熵的形式衡量地理位置受用戶歡迎的程度，熵越大，說明該地理位置越受用戶歡迎.為了防止攻擊者根據(jù)發(fā)布的位置熵直方圖推測出某個用戶的位置隱私，To等［13］采用拉普拉斯機制對位置熵進行噪聲處理，注入噪聲的規(guī)模由全局敏感度決定，為了解決全局敏感度導(dǎo)致噪聲過大的問題，采用本地敏感度或平滑敏感度的方法代替全局敏感度.

空間直方圖和位置熵的缺陷在于丟棄了用戶軌跡的時序信息，無法滿足數(shù)據(jù)使用者對序列進行深入分析的需求，而直接發(fā)布軌跡數(shù)據(jù)可以在最大程度上保留軌跡的時序特征.目前有基于樹重構(gòu)和軌跡聚類等多種差分隱私軌跡發(fā)布方法.如Chen等［14］提出一種基于前綴樹的軌跡差分隱私保護方法，通過構(gòu)造加噪前綴樹并為加噪前綴樹中每個節(jié)點計數(shù)添加噪聲實現(xiàn)差分隱私.霍崢等［15］在噪音樹的基礎(chǔ)上分別針對自由空間和路網(wǎng)空間提出了兩種差分隱私軌跡數(shù)據(jù)發(fā)布方法.基于聚類的軌跡發(fā)布方法［16］在位置精度高，候選位置集合規(guī)模大的情況下更適用.這種方法采用分階段處理的思想，將長度為的軌跡集處理分為個階段，在每個階段對所有位置進行聚類分組，使用聚類中心點代替該聚類中的真實位置點，通過在聚類中心點的隨機化和軌跡計數(shù)的隨機化過程中引入隨機化噪聲實現(xiàn)差分隱私，最后發(fā)布擾動后的數(shù)據(jù)集.如Zhao等［17］提出的差分隱私軌跡聚類算法TLDP（Trajectory Location Data Protection），通過將Laplace噪聲添加到軌跡計數(shù)中來抵抗連續(xù)查詢攻擊.

2.2 本地化差分隱私研究現(xiàn)狀

與傳統(tǒng)的差分隱私［4］技術(shù)相比，本地化差分隱私技術(shù)已經(jīng)成為一種更為健壯的隱私保護模型，與傳統(tǒng)的中心化差分隱私不同，該技術(shù)的核心思路是在本地給用戶數(shù)據(jù)添加滿足本地化差分隱私的擾動，將擾動后數(shù)據(jù)傳輸給第三方數(shù)據(jù)收集者，再通過一系列查詢操作得到有效的結(jié)果.本地化差分隱私的目標在于解決服務(wù)器不可信場景下數(shù)據(jù)的安全采集與分析問題.本地化差分隱私中常用的擾動機制是隨機響應(yīng)，如楊高明等提出一種滿足本地化差分隱私約束的關(guān)聯(lián)屬性不變后隨機響應(yīng)擾動方法［18］.除此以外還有壓縮機制Compression［19］和扭曲機制Distortion［20］.這些擾動機制在頻數(shù)統(tǒng)計、均值估計和機器學(xué)習(xí)等學(xué)術(shù)領(lǐng)域有大量應(yīng)用［21］.除了學(xué)術(shù)研究以外，本地化差分隱私在工業(yè)界也有所應(yīng)用，如蘋果公司將該技術(shù)應(yīng)用在操作系統(tǒng)ios 10上以隱私保護的方式收集用戶的統(tǒng)計數(shù)據(jù)［22］，谷歌公司同樣使用該技術(shù)從Chrome瀏覽器上采集用戶的行為統(tǒng)計數(shù)據(jù)［23］.

3 背景知識

3.1 位置數(shù)據(jù)建模

本文使用兩種坐標系來表示用戶的位置點.一種是狀態(tài)坐標系，將原始地圖劃分成多個網(wǎng)格，使得每個網(wǎng)格單元表示用戶的一個位置狀態(tài).另一種是地圖坐標，通過二維經(jīng)緯度坐標點來表示用戶的位置.

這兩種坐標系之間可以互相轉(zhuǎn)化，狀態(tài)坐標中每個網(wǎng)格單元的索引可以由經(jīng)緯度表示，從而對應(yīng)到地圖坐標上.如圖1所示，橫坐標表示向東方向數(shù)據(jù)，縱坐標表示向北方向數(shù)據(jù)，網(wǎng)格表示位置狀態(tài).

圖1 狀態(tài)坐標系和地圖坐標轉(zhuǎn)化示意圖

對于位置域S={s1，s2，…，sN}，記si(1≤i≤N)代表圖上的第i個網(wǎng)格單元，該網(wǎng)格單元表示為一個單位向量，其中第i個元素為1，其余N-1個元素為0，用二維向量xt表示t時刻用戶在地圖坐標上的位置，xt[0]表示該位置點的經(jīng)度，xt[1]表示該位置點的維度，與t時刻用戶在狀態(tài)坐標上的真實位置互相對應(yīng)，位置查詢f(s)：s→R2表示網(wǎng)絡(luò)坐標中位置點到地圖坐標的映射，以圖1為例，設(shè)用戶位置域S={s1，s2，…，s56}，若用戶在t時刻真實位置狀態(tài)為s10，則s10=[0，0，0，0，0，0，0，0，0，1，…，0]，對應(yīng)地圖坐標xt=[3，5]，即s10的維度坐標為3，經(jīng)度坐標為5，存在位置查詢f(s10)=[3，5].

3.2 位置隱私攻擊

在位置隱私發(fā)布的研究背景下，針對位置的隱私攻擊可視為根據(jù)發(fā)布的擾動位置推測出某時刻用戶真實位置的過程，本文采用隱馬爾可夫模型對該過程進行建模.每一時刻用戶的真實位置是不可觀測的，對應(yīng)隱馬爾可夫模型中的隱藏狀態(tài)，經(jīng)過隱私保護處理（如4.2中的CPLP算法）后發(fā)布的位置數(shù)據(jù)可由攻擊者直接觀察得到，對應(yīng)隱馬爾可夫模型中的觀測狀態(tài)，記矩陣M∈[0，1]N×N為用戶的位置狀態(tài)轉(zhuǎn)移矩陣，矩陣中的元素mij表示由位置狀態(tài)si轉(zhuǎn)移到位置狀態(tài)sj的概率大小，在后續(xù)隱私保護位置擾動算法設(shè)計中，假設(shè)矩陣M可根據(jù)用戶的歷史位置數(shù)據(jù)訓(xùn)練得到.在位置攻擊模型中，t時刻用戶的位置狀態(tài)可以通過概 率 分 布pt∈[0，1]1×N表 示，其 中代表t時刻用戶真實位置位于si的可能性大小，假設(shè)t時刻用戶以相同的概率分布于位置集合S={s1，s3，s4，s6}中，則此時用戶的位置概率分布表示為pt=[1/4，0，1/4，1/4，0，1/4，0，0，...，0].再使用和分別表示攻擊者觀察擾動輸出zt前后該時刻位置狀態(tài)的先驗概率和后驗概率.t時刻的先驗概率可以通過前一時刻t-1的后驗概率結(jié)合狀態(tài)轉(zhuǎn)移矩陣M計算得到，即后驗概率可根據(jù)式（1）中的貝葉斯公式計算，其中表示隱馬爾可夫模型的發(fā)射概率，即在給定真實位置概率分布的情況下輸出擾動位置為zt的概率.

假設(shè)攻擊者掌握的背景知識包括隱馬爾可夫模型的狀態(tài)轉(zhuǎn)移矩陣和初始概率分布，則攻擊者可以推測出t時刻用戶可能出現(xiàn)的位置，表現(xiàn)為該時刻先驗概率大于0的位置，將這個區(qū)域定義為時序關(guān)聯(lián)域Ct，如定義1所示.

定義1時序關(guān)聯(lián)域.時序關(guān)聯(lián)域Ct代表t時刻用戶所有可能出現(xiàn)的位置集合，即0，si∈S}.

3.3 本地化差分隱私

本地化差分隱私模型基于嚴格的數(shù)學(xué)背景，形式化定義如下所示.

定義2ε-本地化差分隱私［21］.給定n個用戶，每個用戶對應(yīng)一條記錄，對于隨機化算法A，其定義域為Dom(A)，值域為Ran(A)，若算法A在任意兩條記錄t和t'(t，t'∈Dom(A))上得到相同輸出結(jié)果(o(o?Ran(A)))的概率滿足Pr(A(t)=o)≤eεPr(A(t')=o)，則稱算法A滿足ε-本地化差分隱私.

本地化差分隱私技術(shù)通過控制任意兩條記錄輸出結(jié)果的相似性來確保算法的隱私性，即根據(jù)隨機化算法A的某個輸出結(jié)果無法推測出輸入數(shù)據(jù)為哪一條記錄，根據(jù)3.2節(jié)中位置隱私攻擊的描述，位置隱私發(fā)布的目標就是確保攻擊者不能根據(jù)已發(fā)布的擾動位置推測出某個時刻用戶的真實位置，也就是保證時序關(guān)聯(lián)域中任意兩個位置不能被攻擊者區(qū)分出來，基于此本文提出ε-不可區(qū)分性的定義，表示時序關(guān)聯(lián)域內(nèi)的差分隱私.

定義3ε-不可區(qū)分性.對于時序關(guān)聯(lián)域中相鄰的兩個位置si和sj，在隨機化算法A的作用下，若對任意輸出o?Ran(A)，存在Pr(A(si)=o)≤eεPr(A(sj)=o)成立，則稱隨機化算法A滿足不可區(qū)分性.

定義3中參數(shù)ε非負，表示隱私保護的程度，該參數(shù)越小隱私保護的程度越高.由于定義2只是理論模型，而要實現(xiàn)具體的位置差分隱私則需要噪聲機制的介入，Laplace機制是實現(xiàn)差分隱私最常用的方法，該機制建立在l1-敏感度（l1-norm Sensitivity）的基礎(chǔ)上，相關(guān)定義如下：

定義4l1-敏感度［4］.對于查詢f(s)：s→R2，l1-敏感度指f(x1)-f(x2)的最大l1范式值，如式（2），其中x1和x2是相鄰數(shù)據(jù)集中的兩個元素.

定義5Laplace機制［4］.對于查詢f(s)：s→R2，查詢函數(shù)的敏感度為Δf，如果查詢算法A滿足式（3），則算法A具有ε-不可區(qū)分性，所添加的噪聲符合位置參數(shù)為0，尺度參數(shù)為Δf/ε的拉普拉斯分布.其中，敏感度Δf表示兩個相鄰位置查詢結(jié)果的最大l1范式值.

位置隱私保護中另一種高效的擾動機制是Xiao等［24］提出的平面各向同性擾動機制（Planar Isotropic Mechanism，PIM），該機制基于計算幾何學(xué)［25］中凸包（Convex Hull）和各向同性位置（Isotropic Position）的定義構(gòu)造凸包敏感度，并基于K-機制［25］生成噪聲.

定義6凸包［25］（Convex Hull）.對于給定集合X={x1，x1，…，xn}，包含X中所有點的凸集稱作X的凸包，記作Conv(X)，凸包可以用X中所有點的線性組合來構(gòu)造.

定義7各向同性位置［25］（Isotropic Position）.若凸集K?Rd滿足式（4），則稱K位于各向同性位置上，式中LK表示每個單位向量的各向同性常數(shù).

定義8凸包敏感度［24］（Sensitivity Hull）.對于位置s和查詢f(s)：s→R2，凸包敏感度K是Δf的凸包，如式（5）所示，Δf表示時序關(guān)聯(lián)域中兩個位置點x1和x2的查詢差值.

定義9K-機制［25］（K-norm Mechanism）.對于給定的查詢函數(shù)f(s)：s→Rd以及凸包敏感度K，若任意擾動輸出z的概率分布滿足式（6），則稱其滿足K-機制，式中表示凸包敏感度，Γ()表示伽馬函數(shù)，‖·‖K表示凸包敏感度的閔可夫斯基范數(shù).

4 本地化差分隱私時序位置發(fā)布模型

為了解決位置數(shù)據(jù)發(fā)布時存在的隱私泄露問題，本文設(shè)計了一種基于本地化差分隱私的時序位置發(fā)布模型，如圖2所示，模型主要思想為允許用戶在本地進行隱私策略的定制，根據(jù)定制的隱私策略對時序關(guān)聯(lián)的位置數(shù)據(jù)添加噪聲后發(fā)布，實現(xiàn)位置數(shù)據(jù)發(fā)布時的隱私保護.

圖2 本地化差分隱私時序位置發(fā)布模型

在用戶端，模型由兩個主要算法構(gòu)成，分別是基于定制隱私策略的位置擾動算法CPLP和基于隱馬爾可夫模型的時序關(guān)聯(lián)位置隱私發(fā)布算法TRLP.將經(jīng)過隱私保護處理后的時序位置進行發(fā)布，并上傳給LBS服務(wù)器，用于后續(xù)的位置大數(shù)據(jù)分析工作.

4.1 定制隱私策略

本文參考Blowfish Privacy［26］來設(shè)計位置隱私發(fā)布時的定制隱私策略.Blowfish Privacy是一種針對統(tǒng)計數(shù)據(jù)集的定制隱私保護方案，使用無向圖的節(jié)點表示需要保護的數(shù)據(jù)集，邊表示對兩個數(shù)據(jù)集提供不可區(qū)分性，用戶可以在本地通過定制無向圖來決定隱私保護程度，然而Blowfish Privacy并不能直接應(yīng)用在位置數(shù)據(jù)中，因此結(jié)合3.1中定義的位置網(wǎng)格坐標，將定制隱私引入位置數(shù)據(jù)的隱私保護發(fā)布中，提出隱私策略的定義，如定義9所示.

定義10隱私策略.隱私策略表示為一個無向圖G=(S，ξ)，其中S是無向圖的節(jié)點，代表網(wǎng)格坐標中需要保護的位置狀態(tài)點，ξ是無向圖的邊，代表為兩個節(jié)點提供ε-不可區(qū)分性.

圖3展示了幾種不同的隱私策略，如圖3（a）表示一種寬松的隱私策略，圖中所有節(jié)點都沒有連線，表示可以直接發(fā)布用戶真實位置，不提供位置隱私保護（仍然需要提供匿名隱私保護），圖3（b）的隱私策略為區(qū)域內(nèi)部分位置點之間提供不可區(qū)分性，但不要求對圖中所有節(jié)點提供不可區(qū)分性.與圖3（b）相比，圖3（c）的隱私要求更為嚴格，需要保護所選區(qū)域內(nèi)所有位置點之間的隱私性，表現(xiàn)為一個全連接圖，這種隱私策略適用于對隱私需求很高的用戶.

除了選擇圖3所示的隱私保護級別外，若用戶需要更嚴格的隱私策略，還可進一步通過定制隱私策略的粒度調(diào)整隱私保護級別，粒度代表所保護最小位置范圍.模型為用戶提供如圖4所示三種粒度的隱私策略，分別是PGk9，PGk16，PGk25，下標中的數(shù)字表示隱私策略的粒度，圖4中黑色邊框表示提供隱私保護的最小位置范圍，以PGk9為例，該隱私策略表示網(wǎng)格坐標中每9個網(wǎng)格單元（3×3）內(nèi)所有位置點彼此完全連接，即在該區(qū)域內(nèi)所有點之間都有連接路徑，是一個3×3的全連接圖，需要保證該區(qū)域內(nèi)所有位置點不可區(qū)分.

圖3 定制隱私策略示意圖

圖4 三種隱私策略粒度示意圖

為了將定制隱私策略應(yīng)用到位置差分隱私中，本文結(jié)合定義1中的時序關(guān)聯(lián)域Ct，給出時序關(guān)聯(lián)域隱私策略的定義.定義11時序關(guān)聯(lián)域隱私策略.t時刻的時序關(guān)聯(lián)域隱私策略是隱私策略G在時序關(guān)聯(lián)域中Ct的子圖，只包含屬于時序關(guān)聯(lián)域Ct中的邊，即GC=(C，ξC)，其中C?S且ξC?ξ.

在傳統(tǒng)差分隱私定義中，相鄰數(shù)據(jù)集（neighboring databases）被定義為只相差一條記錄的兩個數(shù)據(jù)集，在定制隱私策略的背景下，引入相鄰節(jié)點的概念.

定義12相鄰節(jié)點集合N(s).位置s的相鄰節(jié)點是指和s有公共邊連接的一系列節(jié)點集合，記作N(s)，則有N(s)={s'|dG(s，s')=1，s'∈S}，用dG(si，sj)表示隱私 策略上點si和sj之間的距離，該距離可通過兩點間最短路徑數(shù)計算.

結(jié)合時序關(guān)聯(lián)域隱私策略，本文提出{ε，G}-位置差分隱私的定義，通過確保時序關(guān)聯(lián)域隱私策略中每一對相鄰節(jié)點的ε-不可區(qū)分性，使得攻擊者無法區(qū)分時序關(guān)聯(lián)域隱私策略中的相鄰位置點.

定義13{ε，G}-位置差分隱私.給定一個隨機化算法A，對于時序關(guān)聯(lián)域隱私策略中所有相鄰節(jié)點s和s'，若對于任意的輸出z?Ran(A)，存在Pr(A(s)=z)≤eεPr(A(s')=z)成立，則認為s和s'滿足{ε，G}-位置差分隱私.

引理1對于隨機化算法A，當且僅當時序關(guān)聯(lián)域隱私策略中任意兩個節(jié)點滿足ε-不可區(qū)分性時，算法A才滿足{ε，G}-位置差分隱私.

4.2 定制隱私策略位置擾動算法

在4.1節(jié)中，本文根據(jù)定制隱私策略對位置差分隱私模型進行了拓展，提出了{ε，G}-位置差分隱私，本節(jié)設(shè)計一種基于定制隱私策略的位置擾動算法CPLP，對單一時刻真實位置的查詢結(jié)果添加噪聲，生成擾動位置，在4.4.1節(jié)證明所提算法滿足{ε，G}-位置差分隱私.對位置數(shù)據(jù)的擾動可以看作以隱私保護的方式響應(yīng)查詢函數(shù)，使得攻擊者無法根據(jù)擾動后的位置推測出用戶的真實位置，具體流程如算法1所示.

算法1定制隱私策略位置擾動算法(CPLP)輸入:隱私預(yù)算ε,時序關(guān)聯(lián)隱私策略GC t,真實位置s輸出:擾動位置z 1. 根據(jù)定義12計算相鄰位置點集合NP(s):2. Δf G=[]3. FOR i IN range(len(Np(s)))4. FOR j IN range(i，len(Np(s)))5. Δf G.append(f(si)-f(sj))6. END FOR 7. END FOR 8. KI(GC t)=Conv(Δf G)9. 從K(GC t)中采樣得到(y1，y2，…，yl)10. 根據(jù)式(8)計算矩陣T 11. KI(G)=TK(G)12. 從KI(G)中采樣得到z″13. 從Γ(3，ε-1)中采樣得到r 14. z″=rT-1z″15. z'←f(s)+z″16. z←find_nearest_location(z')RETURN z

首先是查詢函數(shù)敏感度的計算.傳統(tǒng)差分隱私中查詢函數(shù)的敏感度代表有無某條數(shù)據(jù)記錄對查詢結(jié)果的最大影響值，在本文定制隱私策略的背景下，查詢函數(shù)的敏感度代表查詢時序關(guān)聯(lián)隱私策略域中相鄰位置節(jié)點時查詢結(jié)果的最大變化值，在定制隱私策略背景下，查詢函數(shù)的的敏感度計算方法進行對應(yīng)算法1中步驟1～7，對于t時刻的位置狀態(tài)s，根據(jù)時序關(guān)聯(lián)域隱私策略，結(jié)合定義12計算當前時刻真實位置狀態(tài)在時序關(guān)聯(lián)域隱私策略中相鄰位置點的集合NP(s)，用Δf G表示NP(s)中每兩個位置查詢差值結(jié)果的集合，計算公式如式（7）所示.

其次將凸包敏感度應(yīng)用到定制隱私策略位置擾動的背景中.通過計算Δf G的凸包得到凸包可直觀理解為由集合X={x1，x1，…，xn}最外沿的所有點連接所組成的凸多邊形表示t時刻查詢函數(shù)的敏感度，記作隱私策略凸包敏感度，表現(xiàn)為一組二維坐標對.將平面各向同性擾動機制應(yīng)用到定制隱私策略位置擾動的過程對應(yīng)算法1中步驟8～11，對于所得的隱私策略凸包敏感度根據(jù)定義7將轉(zhuǎn)化為其各向同性位置從集合中均勻采樣得到y(tǒng)1，y2，…，yl，代入式（8）中計算矩陣可根據(jù)矩陣相乘得來，即在二維平面上一個凸包的各向同性位置可直觀理解為保持凸包原始方向不變，以凸包的各個頂點為坐標中心對凸包進行旋轉(zhuǎn)排列構(gòu)成的圖形.

最后是擾動噪聲的生成過程.對應(yīng)算法1中步驟12～14，先從中均勻采樣得到z″，再從伽馬分布Γ(3，ε-1)中隨機產(chǎn)生變量r，此時得到噪聲z″=rz″，將得到的結(jié)果轉(zhuǎn)換回中得z″=T-1z″，這里的z″就是添加的噪聲大小，表現(xiàn)為一個二維向量.算法1中第15步表示對t時刻真實位置狀態(tài)的查詢結(jié)果添加噪聲，得z'=f(s)+z″.算 法1中 第16步 所 用 到 的 函 數(shù)find_nearest_location(z')表示在地圖坐標系中找到距離z'最近的真實位置z作為擾動輸出返回.記t時刻經(jīng)過算法1處理后所發(fā)布的擾動位置為zt，用Pr(zt|s*t=si)表示發(fā)布擾動位置zt的概率大小，根據(jù)定義8中的K-機制，使用式（9）計算.

4.3 時序關(guān)聯(lián)位置隱私發(fā)布算法

由于4.2節(jié)中所提的定制隱私策略位置擾動算法只能用于單一時刻的位置擾動，而在發(fā)布連續(xù)時刻的位置數(shù)據(jù)時，需要考慮時序關(guān)聯(lián)的影響，即發(fā)布歷史時刻的擾動位置對攻擊者預(yù)測下一時刻真實位置的影響，圖5展示了時序關(guān)聯(lián)位置隱私發(fā)布的過程.

圖5 時序關(guān)聯(lián)位置隱私發(fā)布示意圖

根據(jù)2.2節(jié)中描述的位置隱私攻擊模型，攻擊者掌握的背景知識包括用戶的歷史位置數(shù)據(jù)、用戶初始位置的概率分布p1，在此基礎(chǔ)上對攻擊者的背景知識做最大假設(shè)，假設(shè)攻擊者的背景知識還包括定制隱私策略位置擾動算法CPLP，在這樣的情況下，攻擊者先驗知識（如時序關(guān)聯(lián)域）的計算可以看作隱馬爾可夫模型的推理問題（Inference Problem），即攻擊者試圖結(jié)合定制隱私策略位置擾動算法CPLP、當前時刻的馬爾可夫模型和當前時刻之前的所有擾動輸出推測出當前時刻的真實位置.為了抵御擁有強大背景知識的攻擊者對用戶位置的推測，本節(jié)設(shè)計了時序關(guān)聯(lián)位置隱私發(fā)布算法TRLP，具體流程如算法2所示.

算法2時序關(guān)聯(lián)位置隱私發(fā)布算法(TRLP)輸入:隱私預(yù)算ε,時序關(guān)聯(lián)隱私策略G,狀態(tài)轉(zhuǎn)移矩陣M,前一時刻后驗概率p+t-1,當前時刻位置s*t輸出:每一時刻經(jīng)算法CPLP擾動后的位置1.p-t=p+t-1M 2.Ct←{si|p-t[i]＞0}3.GC t←G∧Ct 4.zt←CPLP(ε，GC t，s*t)5.根據(jù)式(1)計算p+t 6.TRLP(ε，GC t，M，p+t，s*t)//遞歸調(diào)用本算法

算法第1步計算當前時刻的先驗概率，每一時刻的先驗概率由前一時刻的后驗概率與馬爾可夫狀態(tài)轉(zhuǎn)移矩陣M相乘得來；第2步根據(jù)先驗概率計算t時刻的時序關(guān)聯(lián)域Ct，即攻擊者根據(jù)歷史發(fā)布的數(shù)據(jù)所推測出該時刻用戶的所有可能位置集合，第3步將此時的時序關(guān)聯(lián)域和用戶的定制隱私策略求交集得到時序關(guān)聯(lián)域隱私策略，第4步中將隱私預(yù)算、當前時刻的時序關(guān)聯(lián)域隱私策略和當前時刻真實位置狀態(tài)代入定制隱私策略位置擾動算法CPLP中，對此時的真實位置進行擾動得到zt，第5步中將擾動位置zt代入式（1）計算t時刻的后驗概率p+t，最后在第6步中將時序關(guān)聯(lián)域隱私策略、t時刻的后驗概率和t+1時刻的真實位置代入本算法，即遞歸調(diào)用，實現(xiàn)下一時刻擾動位置的發(fā)布.該算法的輸出為每一時刻經(jīng)算法CPLP擾動后的位置（算法2中第4步）.

4.4 算法分析

本節(jié)分別從隱私安全性和時間復(fù)雜度兩方面對所提算法進行理論分析.

4.4.1 算法隱私安全性分析

首先證明單一時刻定制隱私策略位置擾動算法CPLP滿足{ε，G}-位置差分隱私，由于算法CPLP基于對攻擊者能力的最大假設(shè)，因此證明算法CPLP滿足{ε，G}-位置差分隱私即可保證該時刻所發(fā)布位置的隱私性.

定理1算法CPLP滿足{ε，G}-位置差分隱私.

證明取?si，sj∈NP(s)，對于同樣的擾動輸出z，其概率分布如下：

比較兩個概率分布可得：

根據(jù)三角不等式，有：

因此可知對于時序關(guān)聯(lián)域隱私策略中任意兩個相鄰的位置點，算法CPLP滿足ε-不可區(qū)分性，根據(jù)引理1可知算法CPLP滿足{ε，G}-位置差分隱私.

證畢.

其次，分析連續(xù)時刻位置隱私發(fā)布算法TRLP的隱私安全性.根據(jù)差分隱私的序列組合性［4］，記A1，…，AT為T個獨立的隨機化算法，分別表示每一時刻對真實位置的擾動處理，若分別A1，…，AT滿足{ε，G}-位置差分隱私，則其組合{A1，…，AT}滿足{Tε，G}-位置差分隱私，其中Tε表示所有時刻隱私預(yù)算的總和，即連續(xù)時刻的位置發(fā)布算法TRLP同樣滿足{ε，G}-位置差分隱私，因此根據(jù)連續(xù)時刻位置發(fā)布算法所得到的軌跡數(shù)據(jù)具有一定的隱私安全性.

4.4.2 算法時間復(fù)雜度分析

關(guān)于算法的時間復(fù)雜度，TRLP算法最耗時的地方在于計算每個時刻擾動輸出的位置點z，即CPLP算法的輸出，而在CPLP算法中，根據(jù)每個時刻的時序關(guān)聯(lián)域計算凸包敏感度耗時最大，記凸包的頂點個數(shù)為n，時序關(guān)聯(lián)域大小為h，則算法的時間復(fù)雜度表示為O(hlog(n)+n2log(h)).

5 實驗與分析

5.1 實驗數(shù)據(jù)與環(huán)境

本文所使用的實驗平臺操作系統(tǒng)為Windows 10+64位，開發(fā)環(huán)境為Pycharm，編程語言為Python 3.8，CPU為Intel（R）Core（TM）i5-7300HQ，內(nèi)存為8 GB.實驗采用兩個數(shù)據(jù)集，分別是微軟亞洲研究院的Geo-Life數(shù)據(jù)集［27］和斯坦福大學(xué)復(fù)雜網(wǎng)絡(luò)分析平臺公開的真實數(shù)據(jù)集Gowalla數(shù)據(jù)集［28］.GeoLife數(shù)據(jù)集記錄了從2007年4月到2012年8月182個用戶的軌跡數(shù)據(jù)，包含一系列以時間為序的包含經(jīng)緯度、海拔等信息位置點信息，共計包含17621條軌跡.本文提取其中位于北京四環(huán)內(nèi)的軌跡數(shù)據(jù)，將地圖分割成340×340 m2的網(wǎng)格單元，用于馬爾可夫狀態(tài)轉(zhuǎn)移矩陣M的訓(xùn)練.Gowalla數(shù)據(jù)集中包含196586名用戶20個月內(nèi)在6442890個位置上簽到的數(shù)據(jù)，本文提取該數(shù)據(jù)集中所有位于洛杉磯的位置數(shù)據(jù)，將地圖分割成370×370 m2的網(wǎng)格單元用于馬爾可夫狀態(tài)轉(zhuǎn)移矩陣M的訓(xùn)練.

5.2 算法可用性度量指標

為了評估本文所提位置隱私發(fā)布算法TRLP的可用性，在實驗中使用兩個度量指標.第一個度量指標是原始位置和擾動位置之間的歐幾里得距離Eeu，即原始位置和擾動位置之間的誤差，單位為m，該指標是位置隱私發(fā)布算法中通用一個的度量指標，Eeu值越小，即誤差越小，說明位置隱私發(fā)布算法的可用性越高.第二個度量指標是在位置數(shù)據(jù)集上運行k近鄰查詢的精度，分別在原始位置數(shù)據(jù)集和發(fā)布的擾動位置數(shù)據(jù)集上運行k近鄰查詢，假設(shè)在原始位置數(shù)據(jù)上運行近鄰查詢的結(jié)果為R，在擾動位置上運行k近鄰查詢結(jié)果為R'，則k近鄰查詢的精度P計算方式如下：k近鄰查詢是位置數(shù)據(jù)發(fā)布后常用的一種數(shù)據(jù)分析方法，其目的是查找距離用戶最近的k個興趣點，對于不同的位置擾動算法，k近鄰查詢的精度越高，說明經(jīng)過位置隱私發(fā)布算法擾動后所得到的軌跡質(zhì)量越高.

5.3 算法可用性實驗

本節(jié)分別從兩個方面探究所提時序關(guān)聯(lián)位置隱私發(fā)布算法TRLP的可用性，一方面探究定制隱私策略的粒度和隱私預(yù)算對算法可用性的影響，另一方面探究發(fā)布時序位置數(shù)據(jù)時算法可用性的變化情況.

首先探究定制隱私策略的粒度和隱私預(yù)算ε對算法TRLP可用性的影響.在Geolife數(shù)據(jù)集上選擇20個用戶150個時刻下的位置進行隱私發(fā)布，構(gòu)造不同粒度的隱私策略（PGk9，PGk16，PGk25），在這三種隱私策略上分別運行TRLP算法30次，以原始位置和擾動位置之間的歐幾里得距離Eeu作為算法可用性的度量標準，在ε分別取值0.3，0.5，0.7，1時返回Eeu的平均值，實驗結(jié)果如圖6所示.

圖6 定制隱私策略粒度對算法可用性影響

實驗結(jié)果分析如下：

（1）隨著隱私預(yù)算的增加，算法TRLP的誤差逐漸減小，即可用性越高，說明算法TRLP的可用性隨著隱私預(yù)算的增加而增強.

（2）在相同隱私預(yù)算的情況下，隱私策略的粒度越小，則算法TRLP的誤差越小，即算法TRLP的可用性越高，說明可以通過調(diào)整隱私策略的粒度來調(diào)整算法TRLP中隱私保護程度與可用性之間的平衡.

（3）在不同隱私預(yù)算以及不同粒度的隱私策略下，算法TRLP的誤差范圍均在1 m內(nèi)，說明算法TRLP具有較高的可用性.

其次探究算法TRLP發(fā)布連續(xù)位置數(shù)據(jù)時可用性的變化情況.分別在Geolife和Gowalla兩個數(shù)據(jù)集上選擇20個用戶100個時刻的位置數(shù)據(jù)，設(shè)置隱私預(yù)算ε=0.5，基于三種粒度的隱私策略運行時序關(guān)聯(lián)位置隱私發(fā)布算法TRLP，結(jié)果如圖7所示.

圖7 時序關(guān)聯(lián)位置隱私發(fā)布

實驗結(jié)果分析如下：

（1）在Geolife和Gowalla兩個真實的位置數(shù)據(jù)集上運行時序關(guān)聯(lián)位置隱私發(fā)布算法TRLP時，隨著隱私策略粒度的減小，算法TRLP的誤差也隨之減小，即可用性逐漸增加.同樣說明算法TRLP可以通過調(diào)整隱私策略的粒度來調(diào)整隱私保護程度與可用性之間的平衡.

（2）在Geolife和Gowalla兩個真實的位置數(shù)據(jù)集上運行時序關(guān)聯(lián)位置隱私發(fā)布算法TRLP時，在三種不同粒度的隱私策略下，連續(xù)時刻之間算法TRLP的誤差值變化幅度較小，且所有時刻誤差值均在1 m內(nèi)，同樣說明算法TRLP可用性較高.

（3）在三種不同粒度的隱私策略下，算法TRLP在Gowalla數(shù)據(jù)集上的誤差Eeu均小于Geolife數(shù)據(jù)集上的誤差Eeu，原因是與Geolife數(shù)據(jù)集相比，Gowalla數(shù)據(jù)集收集的用戶數(shù)據(jù)具有明顯的移動模式，所以訓(xùn)練的馬爾可夫狀態(tài)轉(zhuǎn)移矩陣M的準確性更高，因此算法TRLP在Gowalla數(shù)據(jù)集上運行的可用性更高.

5.4 對比實驗

本節(jié)以文獻［24］中的拉普拉斯方法作為基線算法，采用不同的度量指標對算法TRLP與基線算法的可用性進行比較.兩種算法主要的差別是計算敏感度的方式以及噪聲添加的方式不同，算法TRLP通過定制隱私策略的方法計算敏感度并添加滿足噪聲，基線算法僅通過計算l1-敏感度給位置數(shù)據(jù)添加噪聲.

首先以原始位置和擾動后位置之間的歐幾里得距離Eeu作為度量指標，在Geolife數(shù)據(jù)集上選擇20個用戶150個時刻下的位置，基于隱私策略分別運行算法TRLP和基線算法，迭代次數(shù)為30次，ε分別取值0.3，0.5，0.7，1時，計算Eeu的平均值，實驗結(jié)果如圖8（a）所示.

其次以k近鄰查詢的精度P作為度量指標，在Geolife數(shù)據(jù)集上選擇20個用戶150個時刻下的位置，設(shè)置隱私預(yù)算ε=0.5，基于隱私策略PGk9分別運行算法TRLP和基線算法，迭代次數(shù)為30次，在擾動前后的位置數(shù)據(jù)集上運行k近鄰查詢，根據(jù)5.2中的描述計算k近鄰查詢的精度P.在k∈[50，75，100，125，150]的情況下運行k近鄰查詢時算法TRLP和基線算法的精度如圖8（b）所示.

最后比較算法TRLP與基線算法的時效性，同樣在Geolife數(shù)據(jù)集上選擇20個用戶150個時刻下的位置，基于隱私策略分別運行TRLP算法和基線算法，迭代次數(shù)為30次，返回不同隱私預(yù)算下兩種算法針對單個時刻運行所需時間的平均值，ε分別取值0.3，0.5，0.7，1時，實驗結(jié)果如圖8（c）所示.

圖8 TRLP算法與基線算法對比

實驗結(jié)果分析如下：

（1）隨著隱私預(yù)算的增加，算法TRLP和基線算法的誤差均逐漸減小，說明算法TRLP和基線算法的可用性均隨著隱私預(yù)算的增加而增加，然而在同樣的隱私預(yù)算下，算法TRLP的誤差Eeu小于基線算法，即算法的可用更高，說明算法TRLP計算敏感度和添加噪聲的方式與基線算法相比冗余更少，即采用定制隱私策略進行敏感度的計算效果更好，因此算法TRLP可以在滿足位置差分隱私的同時保證更好的可用性.

（2）基于不同的k值對兩種位置隱私發(fā)布算法擾動后的軌跡數(shù)據(jù)進行k近鄰查詢時，算法TRLP的精度P均高于基線算法，因此將經(jīng)過算法TRLP擾動后發(fā)布的軌跡數(shù)據(jù)用于k近鄰查詢時效果更好，說明經(jīng)過算法TRLP擾動后發(fā)布的軌跡數(shù)據(jù)質(zhì)量高于基線算法擾動后所發(fā)布的軌跡數(shù)據(jù)質(zhì)量.

（3）在不同的隱私預(yù)算下，算法TRLP和基線算法針對單個時刻位置進行隱私發(fā)布所需要的時間都在2毫秒內(nèi)，說明兩種算法都具有一定的實時性，但與基線算法相比，算法TRLP的運行時間較長，因為算法TRLP計算敏感度時需要根據(jù)每個時刻的時序關(guān)聯(lián)域計算凸包敏感度，這一步耗時較大.

6 結(jié)束語

本文提出了一種基于本地化差分隱私的時序位置發(fā)布模型，模型采用了靈活的位置隱私保護方案，即由用戶選擇系統(tǒng)已設(shè)定的多種隱私策略或定制隱私策略，在此基礎(chǔ)上設(shè)計了定制隱私策略位置擾動算法（CPLP），同時提出一種基于定制隱私策略的時序位置發(fā)布算法（TRLP），通過保證用戶發(fā)布位置的不可區(qū)分性從而保證用戶的位置隱私.在兩個真實的位置數(shù)據(jù)集上進行實驗，驗證了與基線相比，算法TRLP具有較好的可用性.今后的研究將考慮如下兩個方面：（1）與基線算法相比，算法TRLP的運行時間較長，因此后續(xù)工作中需要研究如何在保證算法TRLP可用性的前提下提高其運行速度，從而將算法TRLP擴展到實時位置服務(wù)中；（2）在設(shè)計定制隱私策略時沒有考慮用戶不同的移動模式（如交通方式），因此在后續(xù)工作中可以將用戶的移動模式引入定制隱私策略的設(shè)計，根據(jù)用戶不同移動模式為用戶提供更細粒度的隱私保護選擇.