一種基于多元數據的假位置篩選算法

張 琳，張鴻剛，劉茜萍

1.南京郵電大學計算機學院、軟件學院、網絡空間安全學院，江蘇 南京 210023

2.南京郵電大學江蘇省無線傳感網高技術研究重點實驗室，江蘇 南京 210023

隨著智能手機，平板電腦和其他物聯網（Internet of Things，IoT）設備的激增，基于位置的服務（Location?Based Services，LBS） 已變得越來越流行，并開始改變使用互聯網的方式，在社會生活中發(fā)揮著極其重要的作用。

然而，LBS為用戶提供便利的同時也帶來了隱私泄露的風險，用戶獲取LBS服務后，需要提交位置信息。通過收集用戶的位置信息，攻擊者可以用獲取到的用戶位置數據來跟蹤用戶的移動，或者進一步推知出用戶的工作場所、家庭住址、社會關系、身體狀況和愛好等私人信息，將其賣給第三方以獲取經濟利益［1］。

因此，用戶在使用LBS時必須保護其位置隱私。近年來，世界各地的研究人員已經提出了許多解決位置隱私保護問題的技術，例如位置擾動和混淆［2－3］、區(qū)域匿名［4－6］和假位置［7］。 較為常用的區(qū)域匿名技術將一塊包含k個用戶的匿名區(qū)域發(fā)送給LBS服務器，使得識別真實用戶的概率降低到1/k，然而，這種方法過于依賴可信第三方（Trusted Third Party，TTP），容易造成單點故障，而且大量查詢信息也會造成性能瓶頸。而假位置技術則沒有這些限制和問題，該技術依賴客戶端生成額外的假位置來隱匿用戶真實位置，實現了位置匿名，因此很好地彌補了空間匿名技術的各種不足。而現有研究中基于假位置的隱私保護技術在選擇假位置時，或者沒有充分考慮到背景知識等輔助信息，或者只能工作在特定的環(huán)境下，不具備一般通用性，用戶的位置隱私也因此很難得到預期的隱私保護效果。

本文充分考慮訪問概率、位置語義等地理位置的信息特征，提出了一種基于多元數據的假位置選擇 （Multidata?based Dummy Location Selection，MDLS）算法。該方案首先基于大頂堆初步篩選出與用戶真實位置相似的位置，構成假位置候選集，然后根據候選位置與用戶真實位置語義信息的Jaro?Winkler相似度篩除掉語義相似的位置，最后綜合考慮候選位置與真實位置的物理距離以及語義距離選擇假位置。在保證提交的假位置間物理距離盡量分散，以及用戶實際位置訪問概率相似的同時，還要保證提交的假位置集合盡量分散且位置語義信息盡量豐富。本文使用真實軌跡數據集進行實驗，從生成時間、位置熵、物理距離、語義相似度以及識別率5個方面評估了提出的假位置生成方案，并將其與已有的其他算法相比較，結果表明，提出的算法能夠快速有效地生成物理分散且語義多樣的假位置集合。

1 相關工作

為了解決基于位置服務的隱私問題，國內外學者在先前的工作中已經提出了數種不同的方法?，F有的大多數研究都關注于通過位置擾動和混淆［8－10］的方法來保護用戶的位置隱私，這些方法通常采用諸如k?匿名［11］之類的隱私度量。 Gruteser 等［12］首次將k?匿名這一概念引入了位置隱私領域并提出了一種自適應隱匿算法，該算法可以將用戶位置隱匿于至少包含k個用戶的區(qū)域中，使攻擊者難以從至少包含k個用戶的隱藏區(qū)域中識別出真實的用戶位置。Bamba等［13］提出了一種網格劃分方法，該方法提供了兩種算法：自上而下的網格隱藏算法和自下而上的網格算法，可以根據用戶的需要進行選擇。Xu等［14］證明了k?匿名區(qū)域的大小對查詢結果的一致性有很大影響，為匿名區(qū)域劃分的研究提供了指導。在此基礎上，文獻［15－18］提出了多種幾何形狀的匿名區(qū)域構造方法。但是，這些方法過于依賴TTP［19－20］，容易造成單點故障，而且大量查詢信息也會造成性能瓶頸。

文獻［10］和文獻［21］中提出的解決方案通過在對等（P2P）用戶網絡中傳輸信息來避免通過TTP隱藏位置。然而，移動設備交換信息所需的額外資源花銷使得該方案難以實施。為了解決這個問題，Kido等［22］提出在一組虛擬位置中隱藏用戶位置的方法。Lu等［23］提出類似的方法，該方法在覆蓋用戶位置的虛擬圓或網格內生成k－1個虛擬位置，同時考慮隱藏區(qū)域的面積。Niu等［24］通過位置熵度量假位置集的不確定性，通過最大化位置熵實現了假位置集的構建。Sun等［25］針對統(tǒng)計攻擊，根據隱私需求將地圖區(qū)域分為不同的保護要求等級，通過概率估計選擇虛擬位置，可以防止攻擊者通過分析歷史記錄判斷真實位置信息。夏興有等［26］基于半可信第三方服務的隱私保護系統(tǒng)結構，提出了一種根據用戶歷史查詢概率分布選擇假位置的匿名算法，并基于Stackelberg博弈對匿名結果進行優(yōu)化。然而以上方案都沒有考慮到用戶位置的語義信息，不能保證構造假位置集的語義多樣性。王潔等［27］在構造假位置集時則綜合考慮了假位置的語義信息、查詢概率以及地理位置，但是該方案需要提前構造好地區(qū)的位置語義樹，而且只適用于POI類型較多的地區(qū)，實現匿名的條件較為苛刻，也很難達到預期的隱私保護效果。

本文將在這些文獻的基礎上進行改進和完善，提出的算法在充分考慮用戶位置背景知識的同時，還可以適用于不同的環(huán)境，有效抵御基于位置語義等信息的背景知識攻擊，保護用戶的位置隱私。

2 預備知識

2.1 系統(tǒng)架構

首先，用戶使用移動設備或本地網絡基礎結構來確定他們的位置，用戶的位置信息使用二維坐標（x，y）表示，即用戶的緯度和經度。LBS請求由位置信息（x，y）提交請求的日期和時間以及請求內容的查詢內容組成。用戶將這些信息發(fā)送到LBS服務器，最終收到適當的基于位置的響應，完整的過程如圖1所示。

圖1 系統(tǒng)架構

基于位置的服務可以通過在LBS請求中使用的通信機制直接向用戶分發(fā)歷史查詢概率等背景信息。由于歷史查詢概率之類的背景信息不會隨著時間變化太多，傳播之間的間隔可能會很長，因此開銷不會很大。在文獻［24］的另一種方法中，用戶能夠通過WiFi接入點（Access Point，AP）彼此共享各自的信息。AP收集他們通信范圍內的歷史查詢概率，然后用戶可以下載這些信息并與他們連接的其他接入點共享。本文采用后一種方法，通過AP共享AP覆蓋范圍內位置的歷史查詢概率以及語義信息。

2.2 攻擊模型

攻擊者的目標是獲取有關特定用戶的敏感信息，按照攻擊的類型可將其分為被動攻擊者和主動攻擊者。被動攻擊者可以通過監(jiān)視和竊聽用戶之間的無線渠道，獲取用戶的敏感信息。主動攻擊者可能會破壞LBS服務器并獲取該服務器存儲的所有信息，這些信息包括用戶發(fā)送的當前查詢假位置集以及該用戶的歷史查詢數據。攻擊者根據獲取的用戶發(fā)送的假位置集，并結合有關背景知識，可以嘗試推斷有關用戶的其他敏感信息。常見的背景知識攻擊方式包括同源攻擊、概率分布攻擊和位置相似性攻擊，這些攻擊通過分析用戶歷史請求數據、查詢概率分布以及語義信息，不難推斷出用戶的真實位置。

2.3 篩選準則

令Rlocal＝｛n×n，Slocal｝表示實驗中所選取的矩形區(qū)域，該區(qū)域由n×n個大小相同的網格組成，Slocal表示該區(qū)域的所有位置點集合。lreal表示用戶當前所處真實位置，dque表示與真實位置歷史查詢概率之差，dphy表示兩位置之間的物理距離，即歐式距離，dsem表示兩位置之間的語義距離，本文中則是由兩位置之間的Jaro?Winkler相似度計算得出。

定義 2Jaro?Winkler相似度［28］是一種度量兩個字符串序列之間編輯距離的指標。給定字符串s1和s2之間的Jaro相似度simj定義為

Jaro?Winkler相似性進一步考慮了字符串的公共前綴長度對字符串語義的影響，給定字符串s1和s2之間的 Jaro?Winkler相似度 simw， 定義為

式中，simj為字符串s1和s2之間的Jaro相似度；l為字符串公共前綴長度，最大值為4；p為一個常量因子，不超過0.25，默認為0.1。

2.4 評估指標

定義3 熵H表示系統(tǒng)內部的混亂和不確定程度，可以用來度量包含k個位置的假位置集Sdummy的不確定性，其定義為

定義4匿名區(qū)域面積D表示假位置集中k個位置點中最外層點圍成的凸包（凸多邊形）面積。凸包的面積可以根據鞋帶公式［29］求出，表示為

式中，c表示假位置集Sdummy中最外層位置點的個數。假位置集凸包面積示意圖見圖2。

圖2 假位置集凸包面積

定義5θ－安全值是用來度量生成假位置集語義差異性的一個指標。其定義為

3 MDLS算法

本文提出了一種基于多元數據的假位置選擇（MDLS）算法，該算法根據位置查詢概率、位置語義等地理位置的信息特征篩選出與用戶真實位置查詢概率相近且物理與語義距離較遠的位置。MDLS算法采用了邊篩選邊判斷的策略，首先基于大頂堆選擇查詢與用戶真實位置查詢概率接近的位置構成假位置候選集，然后分別考慮候選位置與真實位置的物理距離以及語義距離篩選假位置，最后生成一個包含用戶真實位置且大小為k的假位置集Sdummy。算法1給出了MDLS算法的偽代碼表示。

算法1MDLS算法

該算法除需要輸入選取區(qū)域地理信息和用戶所處位置外，還需要提前定義好隱私需求相關的參數匿名度k以及比例系數r。 匿名度k表示生成結果集Sdummy的大小，k越大，攻擊者越難從結果集Sdummy中確定用戶的真實位置，隱私保護效果也越好；比例系數r用來調整綜合距離中語義距離的占比，r越大，語義距離在選擇假位置時越重要。

1～15步構建了一個大頂堆Sc，篩選出與用戶真實位置查詢概率差距最小的4k個位置，作為候選集。首先，2～8步依次將位置集合Slocal的前4k個位置加入候選集Sc，添加完后從最底層的雙親節(jié)點開始根據每個位置的dque自上而下地進行堆調整，直到根節(jié)點結束，至此，初始大頂堆就構建完成了。10～13步將小于堆頂位置dque的待添加位置與堆頂位置進行替換，并從根節(jié)點開始自上而下地堆調整。

17～34步綜合考慮候選位置之間的物理距離和語義距離，記錄并篩選出分散且多樣的假位置。最后返回結果集Sdummy。 18～25步分別算出lcandi與用戶所處位置lreal，最近添加位置llast以及隨機候選位置lrand之間的物理距離dphy，語義距離dsem以及綜合距離并使用dsmin，dmin記錄dsem和d的最小值。

26～32步分別使用lbest和lworst表示最佳候選位置以及最差候選位置，lworst是上文記錄的最小語義距離dsmin對應的位置，該位置與假位置集中用戶真實位置以及其他位置的語義距離最近，容易被攻擊者獲知位置語義信息，需要從候選集中刪除；lbest則是上文記錄的最小綜合距離dmin對應的位置，該位置與假位置集中用戶真實位置以及其他位置的綜合距離最遠，將其加入假位置集Sdummy中，能使集合中的位置最為分散且多樣。經過k輪篩選后，返回假位置集Sdummy。

其中，兩個位置之間的語義距離dsem可以用位置之間的 Jaro?Winkler距離來計算和表示。由于Jaro?Winkler距離既考慮了一定范圍內的匹配字符個數，又考慮了字符串的公共前綴長度對字符串語義的影響，能夠僅從地名較為準確地度量不同位置的語義距離，同時又避免了在POI較少的環(huán)境下匿名失敗的可能。位置語義距離范圍為［0，1］，其偽代碼如算法2所示。

算法2getJWDistance算法

由式（1，2）可知，決定兩字符串語義距離大小的是匹配窗口內的匹配字符數matches、匹配字符換位數transposition以及匹配前綴長度prefix，對3個變量的計數操作分別對應算法2的12～21步、25～35步以及36～41步。

3.1 復雜度分析

算法首先構造了一個大小為4k的大頂堆，用來篩選與用戶真實位置歷史查詢概率最為相近的4k個位置。假設選取區(qū)域包含n個位置，在遍歷這些位置的同時，還需要調整堆，而調整堆的時間復雜度為O（logk），因此，通過最大堆篩選候選集的復雜度為O（nlogk）。然后將用戶真實位置lreal加入結果集，遍歷大小為4k的候選集，綜合考慮候選位置之間的物理距離和語義距離，記錄并篩選假位置。因為n?k，所以后面從大小為4k的候選集篩選假位置的時間可以忽略不計。因此，該算法的時間復雜度為O（nlogk）。由于本算法中間只構建了大小為4k的候選集，因此，該算法空間復雜度為O（k）。

3.2 安全度分析

當算法生成的假位置集中在一小塊區(qū)域，假位置構成的匿名區(qū)域面積也相應地變小，使得用戶的真實位置更難隱藏。此時，k匿名只能滿足數量上的要求，而不能真正達到匿名的效果。本文提出的算法盡可能選擇與用戶真實位置距離較遠的位置加入假位置集，使得生成的假位置盡量分散，從而使攻擊者難以確定用戶的真實位置。

類似地，當算法生成的假位置集只含有一兩種語義信息，即使不能確定用戶所處的真實位置，用戶所處位置的語義信息也很容易推知，假位置集中單一的位置類型同樣也難以保證用戶的位置隱私安全。本文提出的算法篩除了與用戶真實位置的語義信息幾乎相同的位置，從而保證了假位置集語義信息的多樣，使得攻擊者難以確定用戶所處位置的語義信息。

另外，本算法生成假位置的查詢概率幾乎相同，分布均勻，每個位置能被區(qū)分于其他位置的概率均為1/k，使得攻擊者難以從假位置的概率分布上推測出用戶真實位置。而且，即使攻擊者已經直接得知本文的算法，結果集的隨機性也使攻擊者難以確定用戶真實位置。

4 實驗結果與分析

4.1 實驗設置

實驗使用真實數據集Geolife［30］來模擬地圖不同區(qū)域內的用戶歷史查詢概率，該數據集是微軟亞洲研究院在2007年4月到2012年8月期間記錄的軌跡數據，包含了182名用戶這5年內的17 621條GPS軌跡。

圖3中的熱圖（heatmap）顯示了Geolife數據集大部分的軌跡數據，其中較亮的區(qū)域代表人口密度相對較高的地區(qū)。實驗選取的模擬區(qū)域的緯度坐標范圍為 39.95°N至 40.00°N，經度坐標范圍為116.30°E，至116.35°E，位于北京五環(huán)內的一個面積約為23.7平方千米的方形區(qū)域（圖3方框區(qū)域）。該區(qū)域被劃分為200×200 的網格（c1，c2，…，c40000），分為100組，每個網格用每個網格中心的（緯度，經度）坐標表示。數據集中每名用戶的軌跡數據都包含位置點的緯度、經度和時間數據，將每條軌跡數據都統(tǒng)計到最近的網格，計算用戶在每個網格中花費的時間，從而得到所有網格的歷史查詢概率。此外，由于Geolife數據集并沒有提供位置相關的語義信息，本實驗還通過百度地圖API獲取所有網格的語義信息。

圖3 Geolife軌跡數據熱圖

實驗采用 Java語言編程實現，運行環(huán)境為Windows 10操作系統(tǒng)，2.30 GHz Intel Core i5處理器，8 GB內存。實驗默認參數配置如表1所示。

表1 實驗默認參數配置

4.2 結果分析

實驗從假位置集生成效率、物理分散性、語義多樣性、不確定性以及識別率這5個方面評估本文提出的算法，并將其與同樣使用假位置技術的DLS算法［24］、enhanced?DLS 算法［25］、MMDS 算法［27］在這 5個方面的表現進行比較。

4.2.1 生成效率

從圖4（a）可以看出，隨著k值的增加，4種算法生成假位置的時間都呈現緩慢上升的總體趨勢，而MMDS算法和本文提出的MDLS算法生成假位置集的花時卻遠小于DLS和enhanced?DLS算法。這主要是因為后兩種算法都需要對區(qū)域內每個位置的查詢概率進行排序，而另外兩個算法并不是通過排序篩選與用戶真實位置查詢概率相近的位置：MMDS算法定義了查詢概率距離，并作為選擇假位置公式的分母；本文提出的MDLS算法則是通過定義的用戶位置查詢概率差距小頂堆篩選出概率相近的位置，用空間換時間，在充分考慮背景知識的同時大大提升了假位置集生成的效率。

作為圖4（a）的補充，圖 4（b）展示了當k值進一步增加時，各個算法生成假位置時間不同的上升趨勢。當k≥10時，由于POI類別的數目有限，MMDS算法能夠匿名成功的幾率特別低，因此圖4（b）只對比了另外3種算法生成假位置集的時間。

圖4 假位置生成時間

從圖 4（b）可以看出，DLS、enhanced?DLS 以及本文提出的MDLS算法呈現不同幅度的上升趨勢：DLS算法的上升趨勢最為平緩，幾乎沒有變化；enhanced?DLS算法的上升幅度最大，前后相差40 ms之多；本文提出的MDLS算法上升速度則介于兩者之間。DLS算法生成假位置集的花時主要在于排序，之后選擇假位置只需要花費常數級的時間，所以k值的增加對于DLS算法生成假位置集幾乎沒有影響；enhanced?DLS算法除了排序花時，因為考慮到覆蓋面積的大小，需要多次反復遍歷候選集和結果集來計算權值，因此k值的增加對于enhanced?DLS算法生成假位置集影響較大；而本文提出的MDLS算法采用了邊選擇邊判斷的策略，只需要遍歷k次候選集按照公式篩選假位置，所以生成假位置的漲幅較為緩慢。

4.2.2 物理分散性

評估算法生成假位置集的物理分散程度可以從兩個方面入手：匿名區(qū)域面積和最小距離。生成假位置間的最小距離和構成的匿名區(qū)域面積越大，表示生成的假位置分布越均勻分散。

圖5是4種算法生成結果集中假位置間的最小距離，可以發(fā)現，這4種算法都是隨著k值增加而逐漸下降并趨于平緩。當k≤4時，本文提出的MDLS算法生成假位置間的最小距離明顯大于DLS和enhanced?DLS算法，前后者的區(qū)別主要在于除了最小距離是否還考慮了語義信息。MDLS算法和MMDS算法都綜合考慮了位置間的物理距離和語義距離，這說明保證位置語義的多樣性也能在一定程度上使得生成的假位置更加分散。

圖5 假位置間最小距離

不過隨著k值進一步增加，4種算法生成假位置間的最小距離的差距也越來越小。這時最小距離也難以評估這些算法生成假位置分散程度，而匿名區(qū)域面積依然能很清楚地比較出4種算法生成假位置的分散程度差異。如圖6所示，當k＞5時 MMDS算法假位置集構成的匿名區(qū)域面積遠遠大于其他算法，這主要因為該算法首先需要保證生成的假位置的興趣點POI類別不同，這也保證了位置之間的距離，而其他3個算法都優(yōu)先考慮了位置的歷史查詢概率。不過，與另外兩種算法相比，本文提出算法生成的假位置依然具有較好的物理分散性。

圖6 覆蓋假位置的匿名區(qū)域面積

4.2.3 語義多樣性

實驗采用θ－安全值評估算法生成假位置的語義多樣性，θ－安全值越大就表示生成假位置集的語義信息越豐富多樣，攻擊者越難確定用戶所處位置的語義信息。

從圖7可以看出，MMDS算法生成假位置的語義信息最為豐富多樣，θ－安全值都在0.9以上，接近于1。而本文提出的MDLS算法同樣考慮了位置的語義信息，但θ－安全值卻處于0.8～0.9之間，稍低于MMDS算法，主要原因在于兩種算法優(yōu)先考慮的因素不同。MMDS算法首先就篩除了POI類型接近的位置，在此基礎上再進行選擇，從而保證了位置語義的多樣性。但隨著k值不斷增加，由于POI類型有限，MMDS算法匿名失敗的幾率越來越大，最終根本無法進行匿名。DLS和enhanced?DLS算法都沒有考慮過位置的語義信息，θ－安全值在0.7左右，遠低于前兩種算法。而enhanced?DLS算法的θ－安全值略高于DLS算法，DLS算法和enhanced?DLS算法的主要區(qū)別在于enhanced?DLS算法額外考慮了匿名面積這一因素，因此，可以發(fā)現物理分散性和語義多樣性呈正相關。

圖7 假位置集的θ－安全值

4.2.4 不確定性

熵代表了系統(tǒng)內部的混亂程度，而位置熵是由位置集合內位置的歷史查詢概率分布決定的，可以用來度量用戶所處位置的不確定性。位置熵越大，位置集合內位置的歷史查詢概率越接近，用戶所處位置就越難以確定。

4種算法生成假位置集在不同k值下的位置熵如圖8所示，除了MMDS算法，其他3種算法的位置熵都隨著k增加而穩(wěn)步上升，而且都接近位置熵的最大值log2k。 一方面，因為 DLS、enhanced?DLS以及本文提出的MDLS算法都是優(yōu)先將位置歷史查詢概率相近的位置篩選出再選擇，另一方面，MMDS算法優(yōu)先篩除POI類型相近的位置，隨著k增加反而更難找到與用戶真實位置歷史查詢概率類似的位置。

圖8 假位置集位置熵

通過以上實驗可以發(fā)現，本文提出的MDLS算法能夠快速生成物理分散且語義多樣的假位置集，從而有效地防范攻擊者的各種背景知識攻擊，保護用戶的位置隱私安全，使其獲得更安全更優(yōu)質的服務。

4.2.5 識別率

雖然 DLS、enhanced?DLS以及本文提出的MDLS算法由于優(yōu)先考慮位置的歷史查詢概率都有著接近最大值的熵，攻擊者很難僅僅通過位置的歷史查詢概率推知用戶的真實位置，但是一旦攻擊者知道生成假位置集所用的算法，攻擊者就能針對算法的特點進行推斷，使得用戶真實位置的識別率大大提升。文獻［31］通過分析DLS算法，設計了一種專門針對攻擊的算法ADLS。

ADLS算法通過反復遍歷用戶提交的假位置集和本地地圖的位置集，根據位置的歷史查詢概率查找本地地圖位置集中與假位置構成集合熵最大的組合，最后根據式（6），（7）選出與用戶提交假位置集最為接近的組合假位置，推斷出用戶的真實位置。

式中，ri表示用戶提交的假位置，ci表示ADLS算法預測的假位置，根據與提交假位置集差距最小的集合確定用戶真實位置。

由于MMDS算法在k值較大時匿名成功的幾率特別低，圖9只比較了ADLS算法對DLS、enhanced?DLS以及MDLS 3種算法不同的識別率：3種算法被ADLS識別的概率都隨著k的增加而減小，其中DLS算法的識別率最高，enhanced?DLS算法和本文提出的MDLS算法的識別率則低了不少，這是因為enhanced?DLS算法除了位置的歷史查詢概率外還考慮了其他因素，并隨機選擇比較，使得ADLS算法更難通過生成的假位置集確定用戶真實位置。

圖9 假位置集識別率

5 結束語

針對當前大多數假位置隱私保護方案沒有充分考慮攻擊者具有的背景知識這一問題，本文綜合考慮位置的查詢概率、語義信息以及物理分布，提出了一種基于多元數據的位置隱私保護方案MDLS。首先基于大頂堆選擇查詢與用戶真實位置查詢概率接近的位置構成假位置候選集；然后通過計算候選位置與真實位置的物理距離以及語義距離篩選出物理分散且語義多樣的假位置；最后生成一個包含用戶真實位置且大小為k的假位置集。實驗分別從假位置集生成效率、物理分散性、語義多樣性、不確定性以及識別率這5個維度將本文提出的算法與另外幾種位置隱私保護方案進行比較，證明了本文提出算法不僅能快速生成假位置集，而且能在很大程度上滿足用戶的位置隱私保護需求。然而本文只研究了快照位置隱私保護，沒有考慮時間這一因素，而短時間內用戶位置具有相關性，因此關于連續(xù)時間的位置隱私保護還有待進一步研究。