基于位置語義和查詢概率的假位置選擇算法

王潔，王春茹，馬建峰，李洪濤

（1.山西師范大學數(shù)學與計算機科學學院，山西 臨汾 041099；2.西安電子科技大學網(wǎng)絡與信息安全學院，陜西 西安 710071）

1 引言

近年來，隨著手機等移動智能終端的普及和移動互聯(lián)網(wǎng)技術的發(fā)展，基于位置的服務（LBS,location based service）在日常生活中得到廣泛的應用。用戶下載LBS 應用程序后，使用這些應用程序可以很方便地向LBS 服務器發(fā)送請求，從而獲取與某個興趣點相關的信息，如交通導航信息、附近的餐廳等。然而，人們在享受LBS 提供便利的同時，也面臨著嚴重的隱私泄露風險。不受信任的LBS 服務器會獲取用戶的查詢數(shù)據(jù)，如用戶的位置、提交的查詢類型等。根據(jù)這些數(shù)據(jù)，LBS 服務提供者可以進一步推斷出用戶的一些個人敏感信息，如目標用戶的社會關系、家庭住址、日常行為等；也可以直接追蹤用戶或泄露用戶的個人信息，這將導致用戶的隱私泄露，因此，位置隱私的保護變得越來越重要。

針對位置隱私保護問題，國內(nèi)外研究學者提出了多種用戶位置隱私保護方法，其中k-匿名是最常用的方法之一?，F(xiàn)有的位置k-匿名技術通常依靠可信第三方服務器將用戶的準確位置泛化為一個包含k 個用戶（包含目標用戶）的區(qū)域[1-3]。這樣不受信任的LBS 服務器很難從此區(qū)域中區(qū)分出目標用戶的真實位置。但是上述隱私保護模型存在一定的局限性。首先，存在單點故障。因為它依賴于一個受信任的匿名服務器，一旦匿名器服務器被對手控制，那么所有用戶的隱私都將受到損害；其次，很難平衡服務可用性和位置隱私，如果泛化區(qū)域過大，會影響服務質(zhì)量，泛化區(qū)域過小，又容易造成位置泄露。為了在不受第三方影響的情況下保護用戶的位置隱私，有研究者提出了同樣能實現(xiàn)k-匿名的假位置技術，但是如何選擇合適的假位置是一個難題?，F(xiàn)有的假位置選擇方案考慮到對手已掌握了位置查詢概率，提出基于熵度量選擇虛擬位置的方法，保護了用戶的位置隱私[4-6]。然而當真實位置和k-1 個假位置都是同一語義類型時，對手還是可以很容易地推斷出用戶的個人信息，例如所有的地點都位于學校時，對手就能推斷出用戶的身份可能是教師或者學生，因此，在選擇假位置時要充分考慮位置的語義信息，生成的假位置集需滿足語義差異性?，F(xiàn)有的方案[7-8]大多采用歐氏距離或余弦距離度量語義差異度，計算量龐大，影響算法的執(zhí)行效率，降低用戶的服務質(zhì)量。文獻[9]采用樹形結(jié)構(gòu)組織所有位置，并根據(jù)位置節(jié)點間的跳數(shù)來計算語義距離，將語義距離作為語義差異度的度量標準，使生成的假位置集滿足語義差異性，但是當假位置集中包含湖泊、森林等訪問概率較低的位置時，對手很容易將它們過濾；此外，如果生成的假位置都在真實位置附近，對手就會將真實位置鎖定在一個小區(qū)域，進而推測出真實位置。

本文充分考慮了用戶邊信息和背景知識可能被攻擊者手利用的情況，提出了一種基于位置語義和查詢概率的最大最小假位置選擇（MMDS,maximum and minimum dummy selection）算法。在選擇假位置時，首先保證最后生成的假位置集中k個位置的語義滿足差異性；然后，使假位置集中k個位置間的查詢概率盡量相近；最后，使假位置間的地理位置盡量分散，并針對考慮位置之間在地圖上分散且查詢概率盡可能相近這2 個因素進行了多目標優(yōu)化。本文算法解決了攻擊者具有邊信息可以排除部分假位置的問題，能有效保護用戶的位置隱私。仿真實驗分別從假位置集生成時間、物理分散度、語義差異性以及位置熵這4 個方面將本文算法與已有算法進行對比，驗證了本文算法的有效性。

2 預備知識

2.1 系統(tǒng)架構(gòu)

本文采用的系統(tǒng)架構(gòu)如圖1 所示，主要由Wi-Fi接入點（AP,access point）、LBS 服務器及智能終端三部分組成。

圖1 系統(tǒng)結(jié)構(gòu)

目前，Wi-Fi 覆蓋面較廣，計算能力和存儲能力也較強。本文系統(tǒng)中Wi-Fi AP 可提供網(wǎng)絡支持，計算并存儲當前覆蓋范圍內(nèi)所有位置的歷史查詢概率，在其無線電范圍內(nèi)收集位置語義信息，并生成和保存位置語義樹。對任意Wi-Fi AP，它所覆蓋范圍內(nèi)的位置是相對穩(wěn)定的，所以位置語義樹和歷史查詢概率不需要頻繁變化。

各種智能終端設備用于執(zhí)行假位置選擇算法，生成假位置集，并篩選由LBS 服務器返回的候選結(jié)果集。

LBS 服務器提供基于位置的服務。本文假設攻擊者能夠成功攻破LBS 服務器，并且攻擊者所掌握的邊信息包括用戶的匿名機制、位置的歷史查詢概率以及位置的語義信息和地圖信息。

查詢前，智能終端用戶首先請求Wi-Fi AP，獲取當前Wi-Fi AP 覆蓋范圍內(nèi)的地圖信息、位置語義樹及歷史查詢概率；其次，根據(jù)假位置選擇機制生成滿足自身隱私保護需求的k-1 個假位置；然后，用戶將真實位置和k-1 個假位置發(fā)送至LBS服務器請求查詢，LBS 服務器根據(jù)用戶發(fā)送的位置返回候選結(jié)果集；最后，用戶篩選結(jié)果，得到當前查詢的目標結(jié)果。

2.2 假位置集構(gòu)造原則

定義1用戶的真實位置 lreal。lreal包含用戶位置的地理坐標及語義信息。

定義2用戶隱私需求S。以二元組(k,u)表示某用戶的隱私需求S，其包含以下2 個方面含義。

1)匿名度k，表示每次查詢時都發(fā)送一個真實位置和至少k-1 個假位置給服務器，且判斷出真實位置的概率為。

2)語義差異度u，表示假位置集中任意2 個位置間的語義距離的最小可接受值。本文設置u=4，即對假位置集中任意 2 個位置 li和 lj，滿足[dsem(li,lj)]min ≥ u(1)，則生成的假位置集中位置之間滿足語義差異性。

2.3 位置地圖距離計算方法

令Mapcur表示當前Wi-Fi AP 覆蓋范圍內(nèi)的地圖信息，對于任意2 個位置 li,lj(i≠ j)，位置地圖距離dphy(li,lj)為2 個位置在地圖信息Mapcur上的距離，其取值范圍為幾米到幾千米。

2.4 位置查詢概率距離計算方法

定義3位置查詢概率（LQP,location query probability）。將每個Wi-Fi AP 將其覆蓋范圍內(nèi)的地圖作為樣本空間按照網(wǎng)格進行劃分，如圖2 所示，每個網(wǎng)格中包含一個位置單元，確定每個位置單元的坐標，通過數(shù)據(jù)訓練集來訓練每個位置的查詢概率。使用計算每個位置單元的歷史查詢概率并保存，其中，i=1,2,…,m2，ni表示某個位置單元的查詢次數(shù)，表示所有位置單元的總查詢次數(shù)，。

圖2 樣本空間劃分

對于任意2 個位置 li,lj(i≠ j)，位置查詢概率距離即2 個位置查詢概率之間的差值，用 dque(li,lj)表示。

2.5 位置語義距離計算方法

定義4位置語義樹（LST,location semantic tree）。將當前Wi-Fi AP 覆蓋的所有位置根據(jù)其語義組織為一種樹形結(jié)構(gòu)，每個葉節(jié)點表示地圖上的真實位置 lreal，每個非葉節(jié)點表示其子節(jié)點的類別，LST 的深度為h，h 的值等于LST 中分類的層數(shù)加1。

對于任意 2 個位置 li,lj(i≠ j)，語義距離dsem(li,lj)即位置語義樹中2 個位置葉節(jié)點之間的跳數(shù)。下面舉例說明語義距離計算方法。以某一Wi-Fi AP 覆蓋的一塊真實的地圖信息為例，圖3(a)為該區(qū)域的示意圖，★表示真實位置。將圖3(a)中位置分為教育與科學、行政與居住等類型，在圖3(b)中顯示所形成的部分LST，其葉節(jié)點表示真實位置，非葉節(jié)點表示子節(jié)點的類別。根據(jù)此LST 可以得出實驗小學與職業(yè)技術學院（圖中灰色實線路徑）的語義距離為2，文化展覽館與社區(qū)（圖中灰色虛線路徑）的語義距離為6。

圖3 真實地圖信息及其LST

根據(jù)上述分析，最后的假位置集需要滿足位置在地圖上盡量分散且其歷史查詢概率盡可能相近，即最后的假位置集DLS 需同時滿足式(2)和式(3)。

由于需要同時考慮2 個因素，可將其轉(zhuǎn)化為多目標優(yōu)化問題，由此本文提出一種最大最小假位置選擇（MMDS）算法，該算法確保DLS 滿足式(4)。

其中，li,lj∈DLS，i≠ j。dque(li,lj)+1 避免了兩位置概率相同，即差值為0 的情況。為了平衡地理距離和概率差值這2 個因素，設置參數(shù)r=100。通過式(4)使假位置在地圖上盡量分散且其歷史查詢概率盡可能相近。

3 最大最小假位置選擇算法

根據(jù)假位置集構(gòu)造原則，選擇合適的假位置構(gòu)成假位置集DLS。本文采用邊選擇邊判斷的策略，其主要思想是，選擇與當前假位置集中已有位置滿足語義差異的所有位置作為候選假位置集；然后，在候選假位置集中選擇一個最優(yōu)位置，最優(yōu)位置是指由該位置構(gòu)成的DLS 滿足式(3)；最后，生成一個由用戶所在真實位置和k-1 個假位置構(gòu)成的集合DLS。算法1 給出了最大最小假位置選擇算法的偽代碼。

算法1最大最小假位置選擇（MMDS）算法

輸入真實位置 lreal，用戶隱私需求S，當前Wi-Fi AP 覆蓋范圍內(nèi)的地圖信息Mapcur，位置語義樹LST，位置查詢概率LQP

輸出假位置集DLS

算法1 的輸入?yún)?shù)為用戶的真實位置 lreal、用戶隱私需求S（包含隱私需求參數(shù)k 和語義差異性需求參數(shù)u）、當前Wi-Fi AP 覆蓋范圍內(nèi)的地圖信息Mapcur、位置語義樹 LST、位置查詢概率LQP。首先，將地圖信息Mapcur中的所有位置生成候選假位置集CLS（第1）行），然后由位置語義樹LST 得到語義差異度矩陣SDM，由Mapcur得到位置地理距離矩陣GDM，由位置查詢概率LQP生成概率距離矩陣PDM（第2）行），將真實位置加入假位置集DLS 中，并將其從CLS 中移除，根據(jù)SDM 將CLS 中與DLS 新加入的假位置（DLS.last）語義距離小于u 的位置過濾掉（第3)～11)行），再根據(jù)LDM 及QDM 從CLS 剩余位置中選擇與DLS.last 滿足的位置Loc 作為新的假位置放入DLS（第14)～18)行），并將此位置從CLS 中移除（第19)行），循環(huán)執(zhí)行以上語句（第5)～20)行），直到DLS 的個數(shù)等于k，最后返回最優(yōu)假位置集DLS。

4 算法理論分析

4.1 安全性分析

由系統(tǒng)架構(gòu)可知，本文的假位置選擇算法在智能終端設備上進行時，智能終端設備不會將其準確位置坐標發(fā)送給任何實體。所以攻擊者無法通過鏈路攻擊來獲取用戶的準確位置。

攻擊能力較強的強攻擊者企圖根據(jù)已獲得的地圖和語義信息以及歷史查詢概率數(shù)據(jù)來推測用戶的真實位置，本文算法可以有效抵抗此類攻擊者。首先，在選擇假位置時保證了其與當前假位置集DLS 中已有位置的語義均不同，即對于任意2個位置 li、lj，滿足 dsem(li,lj)≥ u，使攻擊者無法推斷用戶的位置語義信息；其次，假位置間的查詢概率接近，即滿足pi≈ pj(pi,pj表示位置 li、lj的歷史查詢概率)，根據(jù)位置熵的計算式可知，查詢概率越接近時信息熵越大，且對于含k 個位置的假位置集DLS，攻擊者推出真實位置的概率約為，因此本文算法可以有效抵抗強攻擊者，保護用戶的位置隱私。

4.2 算法復雜度分析

MMDS 算法開始時，假位置集DLS 中只有用戶的真實位置 lreal，假設候選位置有n 個。MMDS算法分為2 個階段，第一階段是通過比較將候選位置中與DLS中新加入的假位置語義相同的位置過濾掉，第二階段是通過式(3)從剩余候選位置中選擇出最優(yōu)假位置加入DLS。每個階段的時間復雜度均為 O(n)，因此總的時間復雜度為 O(n)。

5 實驗結(jié)果與分析

5.1 實驗設置

實驗選用某城市真實地圖數(shù)據(jù)，其中心城區(qū)已經(jīng)被Wi-Fi 全面覆蓋且擁有大量的LBS 用戶。每個Wi-Fi AP 覆蓋范圍約為700～800 m，樣本空間被均勻劃分為28×28 的矩形網(wǎng)格，共13 579 個樣本軌跡點作為歷史數(shù)據(jù)，計算每個網(wǎng)格內(nèi)地理位置的歷史查詢概率。實驗將位置語義主要分為六大類，分別為教育與科學、行政與居住、醫(yī)療救護、商城、公共場所和餐飲娛樂。

實驗采用MyEclipse 開發(fā)平臺，以Java 編程語言實現(xiàn)。硬件環(huán)境為Windows 7 操作系統(tǒng)，3.40 GHz Intel Core i7 處理器，4 GB 內(nèi)存。實驗參數(shù)如表1 所示。

表1 實驗參數(shù)

5.2 實驗結(jié)果

首先，通過分析匿名成功率對MMDS 評價；然后，將MMDS 樣考慮位置語義的MaxMinDistDS算法[9]和SimpMaxMinDistDS算法[9]從假位置集生成時間、物理分散度、語義差異性比較，以及位置熵四方面進行比較，驗證MMDS 算法的有效性。

5.2.1 匿名成功率

圖4 匿名成功率的變化情況

圖4 給出了匿名成功率相對于地圖中位置的數(shù)目Mapi.LN、匿名度k 以及語義差異度u 的變化情況。圖4(a)結(jié)果顯示，地圖中位置數(shù)越多，越有利于匿名執(zhí)行，匿名成功率越高。這是因為位置數(shù)越多，位置語義的種類數(shù)就越多，更有利于構(gòu)造滿足隱私需求的假位置集，匿名成功率得到提高。反之，當?shù)貓D中位置的數(shù)目較少時，很難使匿名集位置間的語義互不相同，導致匿名失敗。在圖4(b)中，隨著隱私需求的匿名度k 的增加，匿名成功率有所下降，因為滿足語義差異度的位置數(shù)不能滿足匿名度k 的要求。圖4(c)中，隨著語義差異度u 的增加，匿名成功率同樣呈下降趨勢，因為語義差異度要求越高，假位置集的語義差異性越難滿足。綜上所述，實際操作中匿名度k 與語義差異度u 不能設置得過大。

5.2.2 假位置集生成效率

在考慮位置語義的假位置選擇算法中，MaxMinDistDS 算法、SimpMaxMinDistDS 算法和MMDS算法生成假位置集的平均生成時間如表2所示。圖5 為這3 種算法假位置集生成時間的對比結(jié)果，其中k 的取值范圍為2～8。

表2 假位置集平均生成時間

從圖5(a)可以看出，隨著k 值的增加，MMDS 算法的假位置集平均生成時間遠小于MaxMinDistDS算法，MMDS 算法生成假位置集的效率更高。因為MMDS 算法在選擇候選位置時，過濾了與當前假位置集已有位置語義距離相近的位置，避免了不必要的時間開銷。從圖5(b)可以看出，當k ≤5 時，MMDS 算法的假位置集生成時間要高于SimpMaxMinDistDS 算法，當k ≥6 時，MMDS算法的假位置集生成時間低于SimpMaxMinDistDS算法。

通過對比還可以看出，隨著k 值的增加，3 種算法生成假位置集所花費的時間都增加，但MMDS 算法明顯比SimpMaxMinDistDS 算法和MaxMinDistDS算法的增加幅度小。也就是說，隨著k 值的增大，MMDS 算法所花費的時間更小，優(yōu)勢更加明顯，更具有實用性。

圖5 假位置集生成時間隨k 的變化

5.2.3 物理分散性比較

假位置間的距離越大則位置越分散，本文通過比較假位置集中任意兩位置間的最小距離來衡量假位置集的物理分散性，最小距離越大說明越分散。圖6 表示本文MMDS 算法、MaxMinDistDS 算法、SimpMaxMinDistDS 算法這3 種算法在不同k值下假位置間的最小距離。

圖6 假位置間的最小距離

通過實驗對比可以看出，當k ≤ 4時，MMDS算法與 MaxMinDistDS 算法的最小距離接近；k ≥ 5時，MaxMinDistDS 算法的最小距離要大于MMDS 算法。在相同k 值下，MMDS 算法的最小距離略大于SimpMaxMinDistDS 算法。這3 種算法假位置間的最小距離都隨k 值的增加而呈下降趨勢，且隨著k 值的增大，最小距離趨近相同，均能保持良好的物理分散性。

5.2.4 語義差異性比較

本實驗采用θ-安全值來度量假位置集的語義差異性。θ-安全值的計算如下

其中，SEM={dsem|dsem(li,lj)＜ u}，k =|DLS|，DLS是包含真實位置在內(nèi)的假位置集，表示組運算式。當θ 無限接近1 時，則說明假位置集滿足語義差異性。

MMDS 算法、MaxMinDistDS 算法、Simp-MaxMinDistDS 算法的θ-安全值如圖7 所示?？梢钥闯?，3 種算法的θ-安全值始終接近1，這是因為它們在選擇假位置時均考慮到了位置的語義信息，從而保證了語義差異性。

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

5.2.5 位置熵比較

在位置隱私保護中位置熵主要用來衡量真實位置的不確定性，熵值越大表明匿名化程度越高,反之則匿名化程度越低。

3 種算法在不同k 值下的位置熵如圖8 所示，可以看出，隨著k 值的增大，3 種算法的位置熵都呈整體增大趨勢，但是MMDS 算法的位置熵要明顯大于另外2 種算法，這是因為MMDS 算法不僅考慮到位置語義差異性，還考慮到位置的訪問概率，用戶真實位置的不確定性更大，可以更有效地保護用戶的位置隱私。

通過以上實驗對比發(fā)現(xiàn)，MMDS 算法在盡可能滿足地理位置之間分散和語義多樣化的同時，還具有較高的假位置生成效率和位置熵值，能有效提高位置服務質(zhì)量。

圖8 3 種算法在不同k 值下的位置熵

6 相關工作

現(xiàn)有的基于位置服務的隱私保護技術主要有空間轉(zhuǎn)換、匿名區(qū)域和偽造數(shù)據(jù)3 類。文獻[10]提出一種基于空間轉(zhuǎn)換的位置隱私保護方法。該方法采用Hilbert 曲線來轉(zhuǎn)換用戶坐標，使匿名服務器無法獲得用戶的位置信息，但匿名服務器可以從中得到用戶的運動方向、運動速度等信息，造成用戶位置信息泄露。文獻[11]提出基于差分隱私的位置隱私方案，考慮由于軌跡中位置之間的相關性，獨立應用噪聲會泄露隱私，利用一個簡單的預測函數(shù)和2 個預算支出策略，改善獨立應用噪聲易造成隱私泄露的問題。文獻[12]中提出基于查詢范圍的匿名區(qū)構(gòu)造方案，考慮位置服務提供商（LSP,location service provider）的查詢區(qū)域面積，將用戶的查詢范圍引入匿名區(qū)的構(gòu)造中，在保護用戶隱私的同時有效降低LSP 的查詢區(qū)域面積。文獻[13]提出基于用戶偏好選擇的假位置生成方案，根據(jù)歷史查詢概率選取用戶發(fā)出請求較多的位置生成假位置，并考慮其速度、行駛方向，選取與用戶位置相似度較高的假位置構(gòu)造匿名區(qū)域。

文獻[10-13]在一定程度上保護了位置隱私，但未考慮位置的語義信息，無法應對具有一定語義背景知識的攻擊。文獻[14]為了防止敏感語義信息泄露，充分考慮了每種語義位置類型的普及度與敏感度，提出一種滿足個性化需求的位置語義保護方法。文獻[15]通過 Voronoi 分割區(qū)域“有選擇”的擴展來構(gòu)建θ-語義安全的隱匿區(qū)域，θ 越小，其保護程度越高。文獻[16]提出一種針對路網(wǎng)環(huán)境下的語義位置隱私保護方法，使匿名集中用戶所處語義位置類型所占比例盡可能小，從而增加用戶所處語義位置的不確定性。文獻[17]提出一種面向連續(xù)查詢的敏感語義位置隱私保護方案，為同時抵抗連續(xù)查詢追蹤攻擊和語義推斷攻擊，構(gòu)建滿足-隱私模型的匿名區(qū)域。文獻[14-17]均有效保護了用戶的位置語義信息，但均存在匿名區(qū)域過大的問題，影響用戶的服務質(zhì)量，且大部分都需要第三方服務器的參與，容易引發(fā)單點故障。文獻[18]提出一種基于假位置的k-匿名位置隱私保護方法。該方法采用獨立式架構(gòu)，并充分考慮了位置的語義信息等特征，選取語義相似度最小的k-1 個位置點作為假位置集，保證了位置的語義安全。但因未考慮位置的查詢概率信息，所以無法應對具有查詢概率背景知識的攻擊。

通過以上分析可知，本文所提的MMDS 算法充分考慮了位置語義和概率信息，能夠抵抗攻擊者具有位置語義和查詢概率信息的背景知識攻擊，可以提供較強的位置隱私保護。

7 結(jié)束語

針對當前大多數(shù)基于假位置的k-匿名位置隱私保護方案沒有充分考慮攻擊者擁有邊信息或者背景知識等問題，本文的假位置集構(gòu)造方法可以從3 個方面達到位置隱私保護的效果。首先，保證假位置集k 個位置之間滿足語義差異性，提高用戶位置語義的不可區(qū)分性，防止因語義推斷造成的位置語義泄露；然后，使位置之間查詢概率盡量相近，防止因過濾查詢概率較低的位置，影響用戶隱私需求的實現(xiàn)；最后，使假位置之間的地理位置盡量分散，防止因匿名區(qū)域過小造成的位置隱私泄露。實驗分別從假位置集生成時間、物理分散度、語義差異性比較以及位置熵四方面將本文所提 MMDS 算法與 MaxMinDistDS 算法和SimpMaxMinDistDS 算法進行對比，結(jié)果表明，MMDS 算法能有效提高位置熵值，且具有更好的生成效率，可以有效保護用戶的位置隱私。本文方案主要考慮了快照查詢的位置隱私保護，而快照查詢可以看作連續(xù)查詢的特殊情況，因此下一步將研究連續(xù)查詢的位置隱私保護。