焦薈聰，劉文菊，王賾

天津工業(yè)大學計算機科學與技術學院，天津 300384

0 引言

基于位置的服務近年來不斷地出現(xiàn)在各個社交軟件中，隨著大數(shù)據(jù)時代的到來，多種軟件帶有全球定位系統(tǒng)（global positioning system，GPS），便于數(shù)據(jù)提供商收集用戶信息進行數(shù)據(jù)分析和數(shù)據(jù)挖掘，以便為用戶提供更優(yōu)質的服務。連續(xù)的基于位置的服務（location-based service，LBS）簽到形成一系列帶有時間屬性的軌跡數(shù)據(jù)，這些軌跡信息攜帶很多可通過相關性及某些屬性信息帶來推斷攻擊的信息，造成用戶敏感信息隱私泄露，帶來很大的安全隱患。為了達到保護隱私軌跡數(shù)據(jù)的目的，相比于僅對單個位置點進行保護，對整條軌跡進行保護才是當下更重要的問題。目前針對軌跡的隱私保護方法可以大致分為3類：泛化（匿名區(qū)域）、抑制（抑制敏感位置）、擾動（差分隱私，生成假位置）。參考文獻[1]通過保護停留點，使用k匿名算法構建匿名區(qū)域的方式保護了敏感信息，同時降低了整個軌跡暴露的概率。參考文獻[2]提出基于k-means++的軌跡(k, l,δ)-匿名算法，能有效抵抗軌跡相似性攻擊?？臻g匿名技術具有較高的隱私保護水平，部署簡單，計算開銷較小，但是要以犧牲服務質量為代價。參考文獻[3]依據(jù)語義位置流行度、用戶設定的敏感語義位置類型及語義安全閾值對軌跡停留位置進行空間匿名，構建語義安全匿名區(qū)域，防止語義推斷攻擊。參考文獻[4]以局部抑制代替全局抑制的方式實現(xiàn)軌跡數(shù)據(jù)的隱私保護，降低數(shù)據(jù)損失率并提高軌跡數(shù)據(jù)的可用性。參考文獻[5]通過離散度控制假位置的分布情況，生成語義安全且分布稀疏的匿名集。然而，這些方法雖然可以保護數(shù)據(jù)的隱私，但它們都需要特殊的攻擊假設和背景知識，而且無法提供一種有效且嚴格的方法來證明其隱私保護水平。

2008 年Dwork C[6]提出了一種更加嚴格的可證明隱私定義，即差分隱私保護方法。差分隱私由于其嚴格的可證明的安全性被廣泛應用于數(shù)據(jù)隱私保護領域，目前逐漸成為主流的位置隱私保護方法。它主要有3個優(yōu)點：一是用戶的隱私泄露風險與攻擊者掌握的背景知識量無關；二是它基于嚴格的數(shù)學證明，提供的隱私保護水平可以定量分析；三是隱私保護需要添加的噪聲大小可以通過調整差分隱私預算來控制，不會隨著數(shù)據(jù)集的變化而變化。參考文獻[7]綜合考慮軌跡上位置點的分布規(guī)律，利用希爾伯特曲線的性質對空間上的位置點進行降維映射，對空間點離散模式進行研究，提出了一種空間劃分方法，劃分后的區(qū)域全部使用其區(qū)域中心點來替換，對聚合后的軌跡進行發(fā)布，但是未考慮語義位置對聚類產(chǎn)生的語義推斷攻擊。參考文獻[8]利用最小描述長度（minimum description length, MDL）算法對整條軌跡進行精簡處理，利用前綴樹存儲軌跡段信息，對軌跡段計數(shù)進行差分隱私保護。但是由于前綴樹結構假設數(shù)據(jù)有很多相同的前綴，而實際軌跡中位置點大多是分散的，因此該方法并不理想。參考文獻[9]根據(jù)空間稀疏性以及最大運行速度提出兩種空間攻擊模型，以用戶最大運行速度為約束提出了一種有效的一致性處理方法，使用四叉樹對空間進行數(shù)據(jù)索引以及使用R樹對路網(wǎng)進行數(shù)據(jù)索引發(fā)布。參考文獻[10]提出了隱式位置的概念，建立了推演泄露模式的模型，通過位置替換和抑制對敏感位置進行匿名，同時考慮了用戶行為模式和軌跡特征提出了兩種約束模型。基于此，為了避免軌跡發(fā)布過程中語義信息帶來的隱私泄露，同時提高軌跡發(fā)布的可用性，本文將位置空間屬性和位置語義特征屬性相結合，提出一種基于指數(shù)機制的軌跡差分隱私保護方法。

1 相關定義

1.1 語義軌跡數(shù)據(jù)庫

語義是具有坐標位置的一個很重要的屬性，本文通過高德地圖公開的應用程序接口（application program interface，API）獲取每一個位置的地理標簽及語義類別編碼，將語義分為如圖1所示的3個類別，以餐飲服務為例，餐飲服務屬于大類，餐飲服務包括快餐廳，快餐廳包含肯德基、麥當勞等具體快餐品牌。本文共有23個大類、800多個小類。語義軌跡數(shù)據(jù)代表空間中一個移動對象的運行軌跡，包含多個時空位置點。單個位置的數(shù)據(jù)結構l={userid, lon, lat, time, sen_type, sen_typecode}，其中userid代表用戶ID，lon代表經(jīng)度，lat代表緯度，time代表時間，sen_type代表語義類型，sen_typecode代表語義類型編碼。語義時空軌跡數(shù)據(jù)庫是由|D|條語義軌跡構成的數(shù)據(jù)集，D={T1,T2,…,Tn}。

圖1 語義分類

1.2 語義位置敏感度

信息熵的概念起源于香農(nóng)信息論[11]，是一種可應用在很多領域的隱私度量方法，熵值越大，說明該位置的不確定性越高[12]，基本計算式如式（1）所示：

設sloc是一個語義位置，用戶ui對位置sloc的訪問總次數(shù)記為ni，對所有位置的訪問總次數(shù)記為N。因此，用戶ui對位置sloc訪問總次數(shù)占所有位置被訪問總次數(shù)的比例可表示為式（2）：

根據(jù)式（1）可以計算出位置信息熵，如式（3）所示：

不同于傳統(tǒng)概念中針對所有用戶進行計算，本文根據(jù)不同用戶需求，設計語義位置敏感度計算式，如式（4）所示：

Sen(ui.sloc)的值越大，該位置對于當前用戶越重要，隱私保護水平越高。

1.3 差分隱私

定義1差分隱私[12-13]給定隨機算法M及相鄰數(shù)據(jù)集D1和D2，其中D1和D2相差1條數(shù)據(jù)。對于算法M在數(shù)據(jù)集D1和D2上的任意輸出O，若滿足式（5），則稱隨機算法M滿足ε-差分隱私。

其中，Pr[·]由隨機算法M控制，表示隱私被披露的風險。ε是一個可以調節(jié)的參數(shù)，稱為隱私預算，它決定隱私保護的程度和發(fā)布數(shù)據(jù)集的精度，ε越接近0，算法M在D1和D2上輸出相同結果的概率越接近1，隱私保護程度越高，相應的發(fā)布數(shù)據(jù)集的精度也就越低，可用性越低。

定義2全局敏感度。對于任意一個查詢函數(shù)f:D→Rd，D表示數(shù)據(jù)集，R表示所映射的實數(shù)空間，d表示函數(shù)f的查詢維度，該函數(shù)作用于數(shù)據(jù)集D后返回一個d維向量，其全局敏感度如式（6）所示：

其中，D1和D2是任意兩個相鄰數(shù)據(jù)集。

定義3指數(shù)機制。給定數(shù)據(jù)集D及隨機算法M，M的輸出為實體對象r，用u(D,r)表示打分函數(shù)，用來評估輸出值r的優(yōu)劣程度，Δf表示打分函數(shù)的全局敏感度，如果M以正比于P的概率從R中選擇并輸出r，那么M滿足ε-差分隱私，如式（7）所示：

1.4 停留區(qū)域

GPS愈來愈精確。在海量的軌跡數(shù)據(jù)中，每條軌跡位置點擁有很大的體量，但并非所有位置點都是有意義的，用戶頻繁且長時間停留的區(qū)域容易暴露用戶的行為模式[14]，只有能代表用戶行為模式的位置點具有代表性。本文利用已有文獻中提出的興趣區(qū)域的概念，設置時間閾值和距離閾值，將用戶長時間停留的相近位置點集合定義為停留區(qū)域，對停留區(qū)域包含的實際位置點進行隱私保護。

1.5 基于語義背景知識的攻擊

一個位置，除了地理上的形狀還有一些語義信息（如學校、醫(yī)院、電影院等），這些語義信息依賴于這個位置上的實體。攻擊者將地理空間信息和語義信息相結合，可以有效推測出用戶的位置?；谖恢谜Z義背景知識的攻擊中最常見的是語義推斷攻擊[15]，當發(fā)布的軌跡數(shù)據(jù)集中包含大量的用戶敏感語義位置時，攻擊者就可以根據(jù)此語義進一步推測出用戶的其他敏感信息。例如，用戶A的簡單軌跡記錄示例見表1。用戶A一個月的軌跡記錄中頻繁出現(xiàn)某小區(qū)到某醫(yī)院的軌跡，攻擊者結合地理信息等其他公開信息可以推測出該用戶的家庭地址，并知曉該用戶是患者或者職業(yè)是醫(yī)生；再結合軌跡中的時間信息，前往醫(yī)院的時間符合上下班的規(guī)律，可以初步推斷用戶A是一名在職醫(yī)生；再通過其他信息得知用戶A的家庭信息、個人愛好等，進而竊取用戶敏感信息。

表1 用戶A的簡單軌跡記錄示例

2 基于指數(shù)機制的軌跡差分隱私保護方法

差分隱私的指數(shù)機制是面向非數(shù)值性數(shù)據(jù)的一種隱私保護機制。指數(shù)機制以一定的概率值返回一個數(shù)值，從而實現(xiàn)差分隱私，概率值由打分函數(shù)確定。筆者基于此提出一種基于位置空間屬性和位置語義的軌跡隱私保護方法，并根據(jù)指數(shù)機制特性進行設計，減少位置語義信息帶來的隱私泄露問題。

為了抵抗語義推斷攻擊，本文通過抑制發(fā)布和差分隱私技術相結合來設計算法。指數(shù)機制核心概念是設計打分函數(shù)，對于數(shù)據(jù)集合中的語義位置來說，對每個位置進行打分，打分越高的位置輸出概率越高，同時加入差分隱私技術的隨機化來達到隱私保護的目的。本文設計打分函數(shù)，使用戶位置敏感度較低的位置分數(shù)高，這樣在隨機輸出時，敏感語義位置大概率不被發(fā)布，同時結合地理位置屬性保持空間特征，保護用戶隱私。

2.1 設計思路

本文提出一種基于指數(shù)機制的軌跡差分隱私保護方法，主要設計思路如下。

● 根據(jù)停留區(qū)域挖掘算法得到整條軌跡中的停留區(qū)域集合，即需保護隱私的軌跡位置區(qū)域。

● 根據(jù)改進的MDL算法計算待保護區(qū)域中包含所有位置點的軌跡特征保持度，根據(jù)語義位置敏感度計算待保護區(qū)域中包含所有位置點的語義隱私度。

● 結合語義隱私度和位置軌跡特征保持度設計打分函數(shù)，利用指數(shù)機制將待保護區(qū)域內(nèi)位置點進行隨機輸出，刪除其他位置點，發(fā)布隱私保護后的軌跡。

2.2 算法設計

基于指數(shù)機制的軌跡差分隱私保護方法框架如圖2所示，其中核心部分在于指數(shù)機制打分函數(shù)設計。

圖2 基于指數(shù)機制的軌跡差分隱私保護方法框架

（1）停留區(qū)域挖掘

假設某條軌跡T={L1，L2，L3，…，Ln},其中Li代表一個位置點，該位置點攜帶語義屬性及地理屬性經(jīng)緯度信息。設置時間閾值ΔT和距離閾值ΔS。從軌跡第一個位置點開始，將該位置點記作start，并將其加入停留區(qū)域area，向后計算下一個位置點與該位置點的時間差Δt。如果Δt大于時間閾值，則計算兩點之間的距離差Δs（使用真實經(jīng)緯度距離計算實際位置距離）；如果Δs小于距離閾值，則將該位置點加入停留區(qū)域area，繼續(xù)遍歷下一個位置點，直至到達該條軌跡最后一個位置點，形成一個以start位置點為基礎點的停留區(qū)域area。接著遍歷除已形成的停留區(qū)域外的第一個位置點，將其作為start繼續(xù)挖掘停留區(qū)域，直至整個軌跡的停留區(qū)域全部形成。

（2）軌跡特征保持度計算

根據(jù)MDL算法計算待保護區(qū)域中包含所有位置點的軌跡特征保持程度權重值。在將MDL算法應用于軌跡數(shù)據(jù)時，D是運動物體的軌跡數(shù)據(jù)集，H是運動物體軌跡的軌跡分割。本文方法中對停留區(qū)域和前后兩個位置點構成的局部軌跡進行軌跡特征保持，可利用MDL算法精確度高的特點，計算每個位置點的軌跡特征保持度。單個停留區(qū)域示意如圖3所示，該停留區(qū)域中n個位置點和前后兩個位置點構成局部特征區(qū)域，根據(jù)實際坐標計算出這n個位置點分別與前后兩個位置點的位置幾何權重，將平均值作為該位置的軌跡特征保持度。

對于停留區(qū)域內(nèi)的位置點ci，有式（8）所示關系：

某位置點的模型精度值等于該位置點與前后兩個端點的歐氏距離的平均值，如式（9）所示：

本文分兩部分計算模型復雜度。取該位置點與區(qū)域外鄰近的兩個位置點（圖3中s點和e點）分別計算復雜度值，根據(jù)MDL算法的定義求出垂直距離和角距離，計算后求平均值，如式（10）～式（13）所示：

圖3 單個停留區(qū)域示意

其中，W為總描述長度，將每個位置點的W作為軌跡特征保持度輸出。

（3）語義隱私度計算

為了防止語義推斷攻擊，將位置語義屬性作為保護區(qū)域內(nèi)位置點的隱私度量。原始軌跡數(shù)據(jù)集中不包括語義屬性，為了保證方案的真實性，使用高德地圖的API，根據(jù)位置點對應實際地圖上的經(jīng)緯度坐標進行語義爬取，采取距離該位置點最近的語義地點標簽定義語義屬性，保證整個爬取過程距離范圍在200 m以內(nèi)。高德地圖將語義分為三大類別，據(jù)此對位置點語義屬性進行語義編碼。挖掘到停留區(qū)域時，對包含的所有位置點提取語義屬性，根據(jù)式（4），基于位置熵的概念計算每個語義位置的語義敏感度，并將其作為語義特征權重，得出每個位置點的語義隱私度。語義隱私度的值越大，代表語義位置隱私需求越高。

（4）指數(shù)機制打分函數(shù)設計

差分隱私的指數(shù)機制關鍵在于打分函數(shù)的設計，打分函數(shù)設計的目的是可以以較大的概率輸出泄露用戶隱私概率最小的位置語義，同時最大限度保持軌跡特征變化，以保證隱私。本文打分函數(shù)如式（14）所示：

其中，D是興趣區(qū)域集合，r是想要輸出的抽樣的語義位置點。以正比于p(D,r)的概率將n種結果隨機輸出，如式（15）所示：

其中，ε是隱私預算，Δf是打分函數(shù)的全局敏感度，對興趣區(qū)域執(zhí)行隱私保護算法，輸出隱私泄露最小的語義位置，刪除其他語義位置。本文將所提方法命名為Index_DP算法，算法偽代碼如下。

算法1Index_DP算法

輸入：原始軌跡T={L1,L2,…,Ln}，軌跡長度N，距離閾值ΔS，時間閾值ΔT

輸出：隱私保護后的軌跡T1

1：fori=1;i＜N；i++ do

2： if Δt(Li,Li+1)＜ΔTand Δs(Li,Li+1)＞ΔSthen

3： 將Li,Li+1加入停留區(qū)域A

4： 對于A={Lj,Lj+1,…,Lj+n}

5： ifLj+n!=Lnthen

6： 將A加入鄰近位置，形成帶邊界區(qū)域E

7：g=MDL(A,E)

8： s=-p×np.log2(p)

9： 設計打分函數(shù)score=1-sen_w/2geo_w

10： out=index_mechanism(A,pr)

11： end if

12： end if

13：end for

14：end

3 實驗分析

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

本文的實驗環(huán)境為Windows 10版本操作系統(tǒng)，編程語言使用Python，采用的數(shù)據(jù)集是真實用戶軌跡采樣Geolife數(shù)據(jù)集。Geolife數(shù)據(jù)集是微軟亞洲研究院項目組歷時5年多收集的182位用戶的GPS軌跡數(shù)據(jù)集，GPS軌跡由一系列時間戳點表示，每個點包含緯度、經(jīng)度和時間信息。該數(shù)據(jù)集包含17 621條軌跡，經(jīng)過初步篩選，最短軌跡包含300個攜帶語義屬性的位置點，最長軌跡包含2 000個軌跡點。在原始軌跡數(shù)據(jù)集上，通過高德地圖API爬取每個位置點在地圖上對應的語義信息，將語義類型編碼作為不同語義的象征，并添加到軌跡每個位置點的屬性當中，作為軌跡隱私保護的一個屬性。

3.2 衡量標準

（1）數(shù)據(jù)可用性

本文采用動態(tài)時間彎曲（dynamic time warping，DTW）[14,16]距離來衡量隱私保護前后軌跡的失真度。DTW是一個動態(tài)迭代的過程，原始軌跡T1={L1,L2,L3,…,Lm}和處理后的可發(fā)布軌跡T2={C1,C2,C3,…,Cn}的長度分別為m和n，則兩條軌跡之間的DTW距離計算式如式（16）所示：

（2）隱私保護度

使用差分隱私中的指數(shù)機制對軌跡進行隱私保護，分析不同的隱私預算對軌跡可用性的影響來衡量差分隱私方法的隱私保護度。從差分隱私指數(shù)機制的定義可以得出，隱私預算與可用性成正比，與隱私保護成反比。

3.3 實驗結果

為了分析算法效果，將本文提出的Index_DP算法分別與參考文獻[17]提出的ANoise算法以及參考文獻[18]提出的GNoise算法進行對比。

（1）不同參數(shù)設定下算法性能對比

分析在不同的時間閾值及不同的距離閾值下，Index_DP算法對數(shù)據(jù)可用性產(chǎn)生的影響。首先分析在時間閾值固定的情況下，距離閾值不同時軌跡的失真度變化趨勢。時間閾值為10 min時，距離閾值分別為200 m、400 m、800 m時的失真度變化趨勢如圖4所示。隨著距離閾值的增大，軌跡失真度增加，這是由于在停留區(qū)域挖掘過程中，距離范圍越大，停留區(qū)域中包含的軌跡位置點越多，保護的隱私區(qū)域越大，導致處理之后的軌跡長度越短，與原始軌跡差異性越大。

圖4 時間閾值為10 min時，距離閾值分別為200 m、400 m、800 m時的失真度變化趨勢

分析在距離閾值固定的情況下，時間閾值不同時軌跡的失真度變化趨勢。距離閾值為400 m時，時間閾值分別為5 min、10 min、15 min時3種算法的失真度變化趨勢如圖5所示。隨著時間閾值的增大，軌跡失真度降低，這是由于搜索的時間越短，保護的隱私區(qū)域越小，處理后軌跡失真度越低。

圖5 距離閾值為400 m時，時間閾值分別為5 min、10 min、15 min時3種算法的失真度變化趨勢

（2）不同閾值下算法性能對比

選取距離閾值為400 m，分別取時間閾值為5 min、10 min、15 min和20 min，在軌跡數(shù)據(jù)集中隨意抽取10條軌跡計算出4個時間閾值下的軌跡失真度后取平均值，3種算法分別進行實驗得出結果如圖6所示。圖6中橫軸對應的是本文實驗中選取的4個時間閾值，縱軸對應的是軌跡失真度，失真度的值越高，代表軌跡的可用性越差。由圖6中可以看出，Index_DP算法在不同時間閾值下的平均失真度均小于其他兩種算法。隨著時間閾值的增大，3種算法的失真度都大致呈現(xiàn)減小趨勢，符合停留區(qū)域挖掘算法的閾值影響。在時間閾值為5 min時，Index_DP算法失真度為0.0158；ANoise算法失真度為0.0608，比Index_DP算法高0.045；GNoise算法采用純加噪聲的方法使其失真度最高達到0.209。由此可見Index_DP算法在對軌跡進行隱私保護后，軌跡的信息損失遠低于GNoise算法和ANoise算法，大大提高了軌跡可用性。

圖6 距離閾值為400 m，時間閾值分別為5 min、10 min、15 min和20 min時3種算法的失真度變化趨勢

時間閾值為10 min，距離閾值分別為200 m、300 m、500 m和700 m時3種算法的失真度變化趨勢如圖7所示。由圖7可知，在距離閾值變化下Index_DP算法在對軌跡進行隱私保護后軌跡的信息損失仍然最小，且遠低于GNoise算法和ANoise算法。隨著時間閾值和距離閾值的不斷變化，Index_DP算法的平均失真度并未產(chǎn)生較大波動，均小于0.05，而ANoise算法的失真度基本為0.05以上。由實驗可知，Index_DP算法不僅大大提高了軌跡可用性，且具有很好的延展性，在當前大數(shù)據(jù)情況下，軌跡長度越來越長，軌跡數(shù)量越來越多，本文算法仍有良好的普適性。

圖7 時間閾值為10 min，距離閾值分別為200 m、300 m、500 m和700 m時3種算法的失真度變化趨勢

（3）不同隱私保護度下算法性能對比

差分隱私的隱私保護程度與隱私預算ε有關，分析不同的ε取值對平均失真度的影響。由于本文方法設計目的是在越來越長的軌跡趨勢下保護軌跡隱私，且每個用戶軌跡長度各有不同，本文將用戶軌跡大致分為3組進行對比試驗，分別為500～1 000 m、1 000～1 500 m以及1 500～2 000 m。在本文數(shù)據(jù)集中，軌跡長度在1 000～1 500 m的軌跡數(shù)量最多，軌跡長度在500 m以下的軌跡較少，因此不考慮該部分軌跡。由表2可以看出，不同的軌跡長度在軌跡失真度上的變化沒有逐漸增大，1 500～2 000 m分段的軌跡失真度小于500～1 000 m的軌跡失真度，說明Index_DP算法可以適用在更長的軌跡上，具有很好的延展性。

由表2可以看出，隨著隱私預算ε增大，數(shù)據(jù)失真度逐漸降低，這是由Index_DP算法設計的打分函數(shù)的目標及指數(shù)機制的性質決定的。ε越大，選擇出期望結果的可能性也越大，軌跡保持更好。打分函數(shù)設計的目的首先是保證語義位置的隱私，其次是盡可能地保持軌跡特征，軌跡保持得更好的情況下也會更大概率地泄露敏感位置，隱私預算與可用性成正比，與隱私保護成反比，這個結果符合差分隱私指數(shù)機制的規(guī)律。由表2可以看到大部分的軌跡受隱私預算影響不大，這是因為在該機制中加入的語義屬性對打分函數(shù)進行了一部分約束，本文主要目的是在保護隱私的情況下盡可能提高軌跡可用性，因此為了同時兼顧語義安全和保持軌跡特征，犧牲了一部分可用性。

表2 不同隱私預算下的失真度分析

4 結束語

本文提出了一種基于指數(shù)機制的軌跡差分隱私保護方法。此方法針對軌跡位置隱私保護中往往忽略位置點的語義屬性帶來的隱私泄露問題，在對軌跡進行保護時不僅考慮其隱私保護，也要保證軌跡本身的特征盡可能不發(fā)生較大的改變，保證隱私保護后軌跡的可用性。根據(jù)語義時空軌跡本身的特性，使用差分隱私方法中的指數(shù)機制，對停留區(qū)域中具有不同隱私水平的位置點進行概率隨機化選擇輸出，由此對軌跡進行隱私保護?；谕Ａ魠^(qū)域的概念，考慮位置點地理幾何特征的同時，為了防止語義推斷攻擊在原始數(shù)據(jù)集上融入位置語義屬性，使用指數(shù)機制在保證隱私條件下對區(qū)域內(nèi)語義位置進行抽樣選擇。在真實數(shù)據(jù)集上進行的多次仿真實驗證明了Index_DP算法具有良好的延展性和普適性，在軌跡保護中有效地提高了數(shù)據(jù)可用性。由于本文使用了比較復雜的數(shù)學模型，下一階段將考慮如何降低算法的運行時間，提高運行效率。