連續服務請求下基于假位置的用戶隱私增強方法

劉海，李興華，王二蒙，馬建峰

（西安電子科技大學網絡與信息安全學院，陜西 西安 710071）

連續服務請求下基于假位置的用戶隱私增強方法

劉海，李興華，王二蒙，馬建峰

（西安電子科技大學網絡與信息安全學院，陜西 西安 710071）

基于假位置的隱私保護方案在為用戶提供準確位置服務查詢結果的同時，還無需第三方和共享密鑰。然而，當用戶連續請求位置服務時，由于現有保護單次查詢的假位置方案未考慮相鄰位置集合間的時空關系，使攻擊者能推斷出假位置，降低用戶的位置隱私保護等級。針對上述問題，采用現有假位置方案生成候選假位置，并通過連續合理性檢查和單次隱私增強對其進行篩選，提出一個適用于連續請求的假位置隱私保護增強方法。安全性分析表明，所提方法能保證連續請求中形成的移動路徑在時空上不可區分，有效保護連續請求中的用戶位置隱私。大量實驗表明，所提方法在不增加用戶計算開銷的同時，與采用的候選假位置生成方案相比，還能提高用戶單次查詢的隱私保護等級。

基于位置的服務；隱私增強；連續請求；假位置；連續合理性檢查

1 引言

基于位置的服務[1～4]（LBS, location-based service）是指服務提供商為用戶提供其指定位置的地理信息，或與其指定位置信息相關的其他業務。隨著無線通信技術的迅猛發展和移動智能終端設備的普及，LBS已成為人們日常生活不可或缺的重要組成。

然而，位置服務提供商在為用戶提供便捷服務的同時，還可能搜集并濫用用戶提交的數據，從而非法獲取他們的個人隱私信息。因此，位置服務中的用戶隱私保護得到了國內外學者的廣泛關注[5～14]。基于假位置的方法[5,6]作為一種最常用的位置隱私保護方法，與其他位置隱私保護方法相比，它具有以下優點：1) 不依賴第三方；2) 可讓用戶獲得準確的查詢結果；3) 無需用戶存儲密鑰。這就使基于假位置的方法已被廣泛用于保護單次查詢中的用戶位置隱私[5, 6, 15～18]。

在現實生活中，除了使用單次LBS外，用戶還會連續地發送LBS請求。例如，在駕車前往度假的途中，司機可能會不斷地查詢最近加油站的位置；到陌生城市旅行時，游客也會不斷地查詢周圍的景點和美食，從而更好地享受假期。在連續LBS請求中，用戶提交的相鄰位置集合在地理時空上存在緊密的關聯性。如果將現有保護單次查詢的假位置方案直接用于連續請求場景時，攻擊者就可利用相鄰位置集合間的地理時空關系，通過識別虛假移動路徑的方法正確推測出假位置，降低用戶的位置隱私保護等級，甚至推測出用戶的真實位置。

針對上述問題，本文利用現有保護單次查詢的假位置方案生成候選假位置，從時間可達性檢查、方向相似判斷和出入度這3個方面評估候選假位置的連續合理性，對其進行篩選，提出了一種適用于連續 LBS請求的基于假位置的用戶隱私保護增強方法。此外，本方法還基于個人查詢熵和位置分散度，從單次查詢隱私保護的角度再次對剩余的候選假位置進行篩選，使最終生成的位置集合在有效保護連續LBS請求中用戶位置隱私的同時，還能為用戶的單次請求提供更好的隱私保護。本文的主要貢獻如下。

1) 通過實驗發現，現有保護單次查詢的假位置方案直接用于連續LBS請求場景時，攻擊者可通過相鄰位置集合間的地理時空關系，正確推測出假位置，從而降低用戶的位置隱私保護等級，甚至推測出用戶的真實位置。

2) 從時間可達性、方向相似性和出入度這 3個方面考慮連續請求中相鄰位置集合間的地理時空關系，提出一個基于假位置的連續 LBS請求位置隱私保護增強方法。安全性分析表明，本方法能保證在連續請求中形成的移動路徑在地理時空上具有不可區分性，有效保護用戶在連續請求中的位置隱私。

3) 大量實驗對比表明，與采用的候選假位置生成方案相比，本方法在不降低單次請求中個人查詢熵的同時，能增大位置分散度，為用戶提供更高的單次查詢隱私保護等級。此外，該方案還具有較低的計算開銷。

2 相關工作

本節主要介紹現有連續 LBS請求中的用戶位置隱私保護方案和現有保護單次查詢的假位置方案。

2.1 連續請求下的位置隱私保護

現有連續請求下的用戶隱私保護大多采用K匿名的方法。Xu和Cai[19]提出利用匿名集合大小來度量LBS連續請求中的用戶的位置隱私保護需求。在他們的方案中，用戶通過在最小邊界圓（minimum bounding circle）中查找不在上一匿名區內其他用戶的方法來構造匿名集合。文獻[20]則通過讓用戶制定公共區域來表示自己的隱私保護需求，提出了基于感覺（feeling）的連續LBS請求用戶隱私保護模型。不幸的是，上述2個方案均不能避免LSP利用查詢追蹤攻擊[21]推測出用戶的真實位置。為了抵抗查詢追蹤攻擊，潘曉等[22]通過預測用戶未來發送LBS請求的位置，讓用戶在連續請求的最初時刻為所有請求生成統一匿名區，來保護連續請求中的用戶位置隱私。Wang等[23]指出，在連續LBS請求中，用戶可能具有不同隱私保護需求。他們讓匿名服務器查找能滿足用戶所有隱私需求的歷史足跡來構造匿名區。Li等[24]指出，在利用其他用戶歷史足跡構造匿名區時，會出現匿名區域過大、服務質量降低的問題。他們通過抑制用戶的少量LBS請求，在滿足用戶連續請求中個性化位置隱私保護需求的同時，通過刪除最遠足跡縮小匿名區面積，提高服務質量。然而，一旦用戶在預定/預測位置之外進行 LBS請求，上述方案仍不能抵抗查詢追蹤攻擊。

Schlegel等[24]基于密文匹配的思想，提出了首個基于密碼學方法的連續 LBS請求位置隱私保護方案。然而，在他們的方案中，一旦半可信第三方與LSP進行合謀，就能縮小用戶真實位置所屬的區域，降低用戶的隱私保護。

與基于假位置的方法相比，現有連續請求位置隱私保護的方法均引入第三方，這會導致用戶與第三方之間存在通信瓶頸。并且，在基于K匿名的方法中，還要求第三方是完全可信的。然而在現實環境中，完全可信的第三方難以找到，這都降低了現有連續請求隱私保護方案的實用性。

2.2 單次請求下基于假位置的用戶隱私保護

基于假位置的用戶隱私保護方案最早是由 Kido等[5,6]于2005年提出的。其基本思想是指用戶根據自己的隱私保護需求生成假位置，并將這些假位置與真實位置一同發送給服務提供商，使服務提供商無法正確推測出用戶的真實位置。Lu等[15]指出如果生成的假位置過于集中，會降低用戶的位置隱私保護等級。在他們的方案中，用戶根據自己的隱私需求，將匿名區域等份劃分，使每個位置（包括用戶的真實位置）均位于不同的圓半徑或矩形頂點上。Niu等[16]指出，上述方案均未考慮攻擊者所擁有的背景知識。一旦攻擊者掌握如地圖信息等某些背景知識，這些方案生成的如位于河流中和山峰頂的假位置就能被攻擊者輕易地識別。因此，他們提出在假位置生成過程中，首先應讓每個假位置的查詢頻率與其真實位置的查詢頻率盡可能地相等，避免生成不合理的假位置；其次，在確保查詢頻率不發生改變的同時，讓位置分散度變大，從而更好地保護用戶的位置隱私。隨后，他們還對文獻[15]未考慮攻擊者背景知識的缺陷進行改進[17]，通過平移原方案生成的各個假位置，使最終生成的位置集合的查詢信息熵達到最大。此外，Niu等[18]又提出利用接入熱點的緩存來存儲用戶歷史查詢結果的方法，避免用戶在同一位置頻繁地生成假位置和向LBS服務器發送請求，從而降低其通信開銷和計算開銷。

從上述介紹中可知，現有基于假位置的隱私保護方法的研究僅集中在單次LBS請求場景。因此，將這些方案直接用于連續請求場景時，攻擊者就能利用相鄰位置集合間的地理時空關系正確推測出假位置，甚至直接推測出用戶的真實位置。

3 基于假位置的隱私增強方法

針對現有保護單次查詢的假位置方案并不適用于連續請求場景的問題，本文采用現有假位置方案生成候選假位置，并利用連續合理性檢查和單次請求隱私增加對候選假位置進行篩選，提出了一個適用于連續 LBS請求的基于假位置的用戶隱私增強方法。該方法主要由2個部分組成：連續合理性檢查算法和單次請求隱私增強算法。其基本框架如圖1所示。

圖1 連續LBS請求下基于假位置的用戶隱私增強流程

1) 候選假位置

本文的目的是針對現有基于假位置的用戶隱私保護方案提出一個適用于連續請求情形的用戶隱私保護增強算法。在本方法中，候選假位置可由現有保護單次查詢的假位置方案直接生成。對于任意的第Qi次連續LBS請求，首先生成的n個候選假位置，用集合表示。其中，∈Ci表示用戶在第Qi次請求中生成第 l(1 ≤l≤n)個候選假位置；n >Ki，Ki表示用戶在第Qi次連續LBS請求中對當前真實位置的隱私保護需求。

2) 連續合理性檢查

將用戶第Qi次連續請求生成的n個候選假位置,,…與用戶在第Q次請求中最終提交的i?1Ki?1個位置進行連續合理性檢查，包括時間可達性檢查、方向相似性判斷和出入度評估，最終得到滿足連續合理性檢查的連續假位置集合候選組。

3) 單次請求位置隱私增強

對于每一個滿足連續合理性檢查的連續假位置集合候選組，對其為用戶提供的單次隱私保護等級進行比較，選擇提供單次隱私保護等級最高的連續假位置集合候選組作為最終生成的假位置集合與真實位置一起提交給服務提供商。

當用戶第一次進行LBS請求時，仍由原始方案初始生成n個候選假位置，并對個假位置集合進行單次請求的位置隱私增強檢查后，得到最終的假位置集合。

3.1 連續合理性檢查算法

該算法主要是對利用現有保護單次查詢的假位置方案生成的候選假位置進行篩選，使連續請求中形成的移動路徑在地理時空上具有不可區分性，具體流程如圖2所示。候選假位置在經過連續合理性檢查后，可得到適用于連續LBS請求的連續假位置集合候選組。如果經過連續合理性檢查后未產生滿足用戶位置隱私需求的候選組，即篩選后剩下的假位置個數小于用戶的隱私保護需求，則擴大生成的候選假位置個數，并重新生成候選假位置。

圖2 連續請求的可達性檢查流程

3.1.1 時間可達性檢查

時間可達性檢查的目的是為了讓用戶在相鄰LBS請求中形成的虛假移動路徑能在請求時間間隔內可達。這將使攻擊者無法利用城市交通地圖等公共信息，通過識別虛假移動路徑的方法，正確推測出某些假位置，從而降低連續請求中用戶的位置隱私保護等級。

假設用戶相鄰2次LBS請求分別為第Qi?1次和第Qi次請求，可利用有向圖 GT=來表示在第Qi次請求中滿足時間可達性檢查的候選假位置。

3.1.2 方向相似性判斷

方向相似性判斷的目的是為了避免在相鄰請求中形成的可達虛假路徑的移動方向與用戶真實路徑的移動方向相差過大，防止攻擊者通過移動方向識別出可達虛假移動路徑，推測出某些假位置，從而降低連續請求中用戶的位置隱私保護等級。

在方向相似性判斷中，利用可達的虛假移動路徑與真實移動路徑間的方向夾角作為判斷標準。同樣地，利用有向圖 GD=來表示第Qi次請求下滿足方向相似性判斷的候選假位置。

下的候選假位置集合，其滿足

3.1.3 出入度評估

本文借用出入度的概念來度量相鄰請求中形成移動路徑的數量，即用各個位置的出度來表示以它為起點的移動路徑的數量，用入度來表示以它為終點的移動路徑的數量。出入度評估是為了避免在相鄰請求形成的方向相似的可達移動路徑中，用戶真實位置的出入度值與假位置的出入度值相差過大，使攻擊者能以較大概率直接推測出用戶的真實位置。為了實現上述目的，分別將用戶真實位置的出度值和入度值作為期望值，利用方差來度量生成的候選假位置集合中假位置出度值與入度值的波動情況。

本文繼續用有向圖 GN=來表示第Qi次請求中滿足出入度評估后，篩選剩下的候選假位置。

綜上所述，連續合理性檢查算法如下所示。

算法1 連續合理性檢查算法

輸入 Qi?1次請求最終生成的位置集合Si?1=

Qi次請求的候選假位置候選集合

輸出 Qi請求的連續假位置集合候選組

1) for each ci∈C do

i

direction (< ci?1,c?i>,< ci?1,ci>)

3) C′′← ci;

i

4) end if

5) end for

6) if |Ci′′ |< Ki? 1 then

7) exit;

8) end if

10) for each j∈ [1,m ′] do

and

13) end if

14) end for

3.2 單次請求的位置隱私增強

當生成的候選假位置經過連續合理性檢查算法篩選后，可得到滿足連續合理性的連續假位置集合候選組。當把任意一個連續假位置集合候選組與當前真實位置一同提交給服務提供商時，由于它們與第Qi?1次服務請求中最終提交的位置集合所形成的移動路徑在地理時空上具有不可區分性，因此攻擊者將無法推測出假位置，從而有效保護連續請求中用戶的位置隱私，并且，為了避免降低用戶單次請求中的位置隱私保護等級，本文還利用個人查詢熵和位置分散度[4,16]，對上述生成的連續假位置集合候選組再次進行篩選，使最后剩下的連續假位置集合候選組還能從單次請求隱私保護的角度，為用戶提供最高的位置隱私保護等級。其流程如圖3所示。

當攻擊者長期收集某用戶發送的服務請求時，他能計算出這個用戶在每個位置上發送服務請求的次數。若用戶在生成的假位置上的個人查詢次數與其在真實位置上的個人查詢次數相差較大，則攻擊者就能推測出用戶此次請求的假位置，從而降低用戶真實位置的隱私保護等級。為了避免上述問題，利用個人查詢熵對經過連續合理性檢查后形成的連續假位置集合候選組進行度量，確保在最終篩選出的連續假位置集合候選組中，用戶在每個假位置的個人查詢次數與其真實位置的個人查詢次數盡可能相同。個人查詢熵越大，則表示該連續假位置集合候選組中每個假位置的個人查詢次數與真實位置的個人查詢次數就越相近。因此，用戶會將篩選出的個人查詢熵最大的連續假位置集合候選組作為最終的假位置集合，與用戶真實位置一同發送給服務提供商。

此外，若存在多個連續假位置集合候選組的個人查詢熵相等且均是最大值時，將利用位置分散度對它們再次進行篩選，得到最終的假位置集合。假位置集合的位置分散度越大，則表示其所形成的區域面積就越大，能避免由于生成的假位置過于集中，使攻擊者能推測出用戶真實位置所屬區域的隱私泄露問題。具體的單次請求位置隱私增強算法如下所示。

輸入 Qi次請求的假位置集合候選組

輸出 Qi請求的最終假位置集合

3) F[ l] ←H( Al)； //計算集合 Al的個人查詢熵

4) end for

7)

10) for each

12) end for

13) A′← argmax_ dispersion( A ′′[?]);

1)

3.3 安全性分析

在本文所提的基于假位置的連續 LBS請求用戶隱私保護增強方法中，候選假位置是由現有保護單次查詢的假位置方案直接生成的。因此，本文不再從單次查詢的角度對本方法能否抵抗相應的推測攻擊進行闡述，而僅通過安全性分析說明本方法能保證在連續請求中形成的可達移動路徑在地理時空上具有不可區分性，使攻擊者無法通過識別可達的虛假移動路徑的方法推測出假位置，有效保護連續請求中用戶的位置隱私。

與現有基于假位置的隱私保護方案一樣，假設攻擊者的目的是得到用戶的準確位置，從而獲得與用戶位置信息緊密相關的個人隱私信息。本文假定攻擊者具有如下的背景知識：1) 攻擊者能攻陷LBS服務器，即他能知道用戶提交的LBS請求的時間和位置信息。其中，位置信息包括用戶的真實位置和生成的假位置。此外，攻擊者還會長期收集并統計該用戶在各個位置發送請求的頻率；2) 攻擊者具備地圖背景知識，即他知道任意2個位置的距離和地圖顯示的可達時間。

在本文所提的連續合理性檢查算法中，通過時間可達性檢查、方向相似性判斷和出入度評估對候選假位置進行篩選，最終生成假位置集合候選組。從時間可達性檢查描述中可以發現，在利用時間可達性檢查，對第Qi次請求生成的候選假位置進行篩選后，可保證篩選剩下的候選假位置與第次請求提交的位置間至少存在1條在σ time <,>

T時間內可達的虛假移動路徑。隨著σT的變小，所形成的可達虛假移動路徑的可達時間與用戶真實移動路徑的可達時間越相近。并且，方向相似性判斷又對經時間可達性檢查篩選后剩下的候選假位置再次進行篩選，使篩選后剩下的候選假位置與第Qi?1次請求最終提交的位置間形成的可達虛假移動路徑與用戶真實移動路徑間的方向夾角不大于σD。隨著σD的變小，所形成的可達虛假路徑在移動方向上與用戶真實路徑的移動方向越相似。而在最后的出入度評估中，所形成的連續假位置集合候選組能避免用戶真實位置的出入度值與假位置的出入度值相差過大，使攻擊者能以較大概率推測出用戶的真實位置。隨著用戶指定的評估閾值σin?D和 σout?D的不斷變小，在位置集合S與 ∪ {}形成的方

i?1向相似的可達移動路徑中，Si?1中各假位置的出度與的出度越接近，而中各假位置的入度則與的入度也越接近。因此，當用戶與攻擊者具有相同的連續合理性檢查知識時，本方法能保證在連續請求中形成的移動路徑在地理時空上具有不可區分性，使攻擊者無法通過識別虛假移動路徑的方法推測出假位置，從而有效保護連續請求中用戶的位置隱私。

4 實驗仿真

為了說明現有假位置隱私保護方案不適用于連續請求場景，本文進行了大量的實驗仿真。在此，本文選取2014年INFOCOM會議上的方案[16]作為實例，說明將該方案直接用于連續請求場景時，并不能有效保護用戶的位置隱私。并通過與其進行比較，表明本方法在不增加用戶計算開銷的同時，不僅能有效保護連續請求中用戶的位置隱私，還能為用戶的單次請求提供更高的隱私保護等級。

4.1 實驗數據及平臺

本文首先選取 enhanced-DLS算法[16]為本方案生成候選假位置。為了保證候選假位置的篩選成功率，首先生成4K個候選假位置，其中，K表示用戶的位置隱私保護需求。當經過時間可達性檢查、方向相似性判斷和出入度評估后，若篩選剩下的候選假位置個數少于K?1，就再次使用enhanced-DLS算法重新生成8K個候選假位置。

本文采用基于網絡的移動對象生成器（network-based generator of moving objects）[26]生成實驗數據。該生成器是以德國城市Oldenberg（面積大約為16 km× 16 km）的城市交通路線圖為基礎，通過設置移動速度，可生成一系列用戶的移動路徑。選取該地圖中心部分作為實驗區域，面積為8 km×8 km，將其劃分為6 400個網格，其中，每個網格的面積為100 m× 100 m。并且，本文使用上述生成器的默認設置，隨機生成38 000條移動路徑（包含約150 000個不同的位置信息）作為用戶歷史LBS請求數據，用于統計用戶在各個網格中所發送的歷史服務請求次數。虛假移動路徑的可達時間是通過查詢Google地圖獲得。另外，在本實驗中，用戶的位置隱私需求K的變化范圍為 3～20，并針對不同的K值，分別做了10次連續LBS請求假位置生成實驗。本實驗的算法均采用C++編程語言實現，實驗環境為3.00 GHz Core 2 Duo CPU，4 GB DDR3-1600 RAM，操作系統為Windows 7-64 bit。

4.2 連續請求對現有基于假位置方案帶來的影響

為了證明現有保護單次查詢的假位置保護方案并不適用于連續請求場景，本文選用enhanced-DLS算法[16]為用戶不同的隱私保護需求，分別連續生成 10次服務請求位置集合。具體實驗過程如下：1) 針對不同的隱私保護需求，使用缺省設置，利用移動對象生成器為分別生成1條包含10個位置的移動路徑，從而模擬用戶連續 10次發送服務請求時的真實位置；2) 根據每條移動路徑中的10個真實位置的經緯度，確定其所屬的網格，并統計相應網格的用戶歷史查詢次數；3) 利用enhanced-DLS算法為每個真實位置生成相應的假位置集合；4) 利用Goolge地圖獲取相鄰請求是可達時間，并將該時間作為用戶相鄰2次請求的時間間隔；5) 構造用戶相鄰請求各位置間的移動路徑，設置時間可達性檢查閾值σ=對它們進行篩選，

T獲得用戶相鄰請求中形成的可達移動路徑，若在第Qi+1次請求生成的位置集合中的每個位置至少能與第Qi次請求生成的位置集合中的任意一個位置構成可達的移動路徑，則繼續進行方向相似性判斷；6) 設置方向相似性判斷閾值 σD=75°對上述形成的可達移動路徑進行判斷，若無法篩選出均由假位置構成的可達虛假移動路徑，就繼續進行出入度評估；7) 統計相鄰請求中，形成的方向相似的可達移動路徑，并基于此計算出各位置的出入度，對假位置進行識別。在本文中，其他部分的實驗過程基本與本部分的實驗相似，唯一不同的就是各閾值的設定。因此，在之后的實驗中不在對具體的實驗過程進行描述。

針對不同的隱私保護需求K值，在這10次連續LBS請求中，最多只有4次連續請求生成的位置集合能通過連續合理性檢查，如圖4所示。而在其他請求中，由于生成的位置集合因在經過連續合理性檢查后，剩下的假位置數量小于用戶的隱私保護需求，從而無法保護連續請求中的用戶位置隱私。

圖4 enhanced-DLS假位置算法應用在連續請求情形下的通過次數

因此，enhanced-DLS算法并不能有效保護連續請求中的用戶位置隱私。而造成這一問題的根本原因就是用戶在連續請求場景下生成假位置時，并未考慮生成的位置集合與上次請求生成的位置集合間的地理時空關系，從而使LSP能通過識別虛假移動路徑的方法推測出生成的假位置。

4.3 本方法提供的隱私保護等級評估

1) 連續請求場景中的隱私保護等級

在連續LBS請求中，利用連續請求中所形成的連續合理的移動路徑數量對用戶位置隱私保護等級進行度量。當設定用戶連續發送10次LBS請求、時間可達性檢查閾值方向相似性判斷閾值出入度評估閾值σin?D和σout?D分別選擇各次實驗中的計算得到的最小方差值時，本方案在相鄰2次請求中，所生成的可達移動路徑數量如圖5所示。

圖5 連續合理的移動路徑數量與理想情況的對比

本文用“最優解”來表示的理想狀態下應形成的移動路徑數量。通過圖5可以發現，隨著用戶位置隱私保護需求的提高，理想狀態下應形成的移動路徑數量與本文方法生成出的位置集合間形成的連續合理的移動路徑的數量均隨之增多。以用戶在第Qi次和第Qi+1次請求時的隱私保護需求Ki= Ki+1= 6為例，在理想狀態下應形成36條連續合理的移動路徑。然而，由于用戶的下次服務請求具有很強的隨機性，如果將出入度評估的閾值設置為 σin?D= σout?D= 0，將難以生成滿足該條件的連續假位置集合候選組。雖然，本文在實驗中將出入度評估閾值σin?D和 σout?D分別選擇為各次實驗中的計算得到的最小方差值，使本方案在相鄰2次請求中形成的連續合理的移動路徑數量少于理想狀態，但是仍能滿足用戶的隱私保護需求。

2) 單次請求場景中的隱私保護等級

基于個人查詢熵和位置分散度，從單次位置隱私保護的角度，對本文提出的隱私增強方法與enhanced-DLS算法進行對比，以說明本方法在有效保護連續請求中用戶位置隱私的同時，也能為用戶提供更高的單次隱私保護等級。在本實驗中，仍設定用戶連續發送10次LBS請求、時間可達性檢查閾值σ=、方向相似性判斷閾值σ=75°、出入

TD度評估閾值σin?D和 σout?D分別選擇各次實驗中的計算得到的最小方差值。

本方法與 enhanced-DLS算法生產的位置集合的個人查詢熵如表1所示。從該表中可以發現，隨著用戶隱私保護需求K的增大，enhanced-DLS算法和本文提出的適用于連續請求下的基于假位置的用戶隱私增強算法所產生的信息熵均在增大。當用戶隱私保護需求從K=3變化到K=7時，所生成位置集合的個人查詢熵值完全相等；而當K=20時，本方法所生成的位置集合的個人查詢熵僅比enhanced-DLS算法降低了0.003。這表明本方法在利用連續合理性檢查對 enhanced-DLS算法生成的候選假位置篩選后，從個人查詢熵的角度來說，并沒降低單次請求時用戶的隱私保護等級。

表1 平均信息熵值的對比

下面將對本文提出的隱私增強方法與enhanced-DLS算法在單次請求情形下生成的位置集合的匿名區面積和位置分散度進行比較，分別如圖6和圖7所示。

圖6 位置分散度比較

圖6和圖7表明，隨著用戶隱私保護需求K的提高，本方法與 enhanced-DLS算法所生成的位置集合的位置分散度和形成的匿名區面積均呈增大趨勢。位置分散度反映了各位置之間距離的乘積。分散度越大，各位置間的距離就越大，所形成的匿名區域面積也就越大。雖然在圖 7中，匿名區域面積的增大存在一定的波動，但是造成這個波動的原因是由于本方法與enhanced-DLS算法均考慮假位置與真實位置間的查詢頻率。通過對比可以發現，本方法所生成的位置集合的分散度與形成的匿名區域面積始終大于enhanced-DLS算法，這表明與enhanced-DLS算法相比，本方法能為用戶提供更好的單次查詢隱私保護等級。

圖7 匿名區域面積比較

4.4 計算開銷

首先分析時間可達性檢查閾值σT與方向相似性判斷閾值σD的設定對本方案在計算開銷上的影響。由于在發送當前服務請求時，用戶無法預測下次進行服務請求時的真實位置，這就使在連續請求所形成的方向相似的可達移動路徑中，用戶真實位置的出入度具有很強的隨機性。因此，在此并不考慮出入度評估閾值σin?D和 σout?D的設定對本方案在計算開銷上的影響。

在這部分實驗中，設定用戶的隱私保護需求K= 6，連續發送10次LBS請求，出入度評估閾值σin?D和 σout?D分別選擇各次實驗中的計算得到的最小方差值。即在利用出入度對候選假位置集合進行篩選時，選擇出入度方差最小的候選假位置集合進行單次隱私增強篩選。在對時間合理性判斷閾值設定對本文所提方案的性能影響實驗中，設定方向相似性的閾值 σD=75°；而在對方向相似性的判斷閾值變化對本文所提方案的性能影響實驗中，設定時間可達性檢查閾值σ=。具體的實驗結果如

T

圖8所示。

圖8 本方法性能測試

通過圖8可以發現，隨著時間可達性檢查閾值σT與方向相似性判斷閾值σD的不斷變大，本方法所需要的計算時間也不斷變小。其主要原因是：隨著閾值的變大，滿足時間可達性檢查和方向相似性判斷的候選假位置逐漸增多，減少了由于篩選后剩下的候選假位置個數不滿足用戶隱私保護需求情況的出現，從而避免重新生成更多的候選假位置。以時間可達性檢查閾值σ的設定為例，當σ=

TT時，連續 10次請求生成最后位置集合的平均時間為1.75 s，而當σ=時，連續10次請求生成最后T位置集合的平均時間為0.05 s。

下面給出K值變化對本文所提方案的運行時間的影響，從而說明所提方案具有較好的實用性，如表2所示。在這部分實驗中，設定用戶連續發送10次LBS請求、時間可達性檢查閾值σ=、方

T向相似性判斷閾值 σD=75°、出入度評估閾值σin?D和 σout?D分別選擇各次實驗中的計算得到的最小方差值。在此要強調的是，僅羅列出用戶的計算開銷，而不考慮訪問地圖接口的時間（受網速和接口的限制等客觀原因的約束）。

表2 本方法所需的計算時間

5 結束語

本文首先通過實驗證明現有保護單次查詢的假位置方案并不適用于連續請求場景。造成上述問題的根本原因是用戶提交的相鄰位置集合間具有較為緊密的地理時空關系，使攻擊者能通過識別虛假移動路徑的方式正確推測出某些假位置，甚至直接推測出用戶的真實位置。針對該問題，分別從時間可達性、方向相似性和出入度3個方面考慮相鄰請求中位置集合間的時空關系，對利用現有保護單次查詢的假位置方案生成的候選假位置進行篩選，使用戶在相鄰請求中形成的連續合理的移動路徑數量遠大于其位置隱私保護需求，有效保護連續查詢中的用戶位置隱私。并且，本文還基于個人查詢熵和分散度，從單次查詢隱私保護的角度再次對剩余的候選假位置進行篩選，使本方案與采用的候選假位置生成方案相比，在不降低單次請求中個人查詢熵的同時，能增大位置分散度，為用戶提供更高的單次隱私保護等級。同時，還通過大量實驗證明了方案的有效性和實用性。

[1] KRUMM J. A survey of computational location privacy[J]. Personal and Ubiquitous Computing, 2009, 13(6)： 391-399.

[2] TIWARI S, KAUSHIK S, JAGWANI P, et al. A survey on LBS： system architecture, trends and broad research areas[C]//LNCS 7108： The 7th International Conference on Databases in Network Information Systems. Heidelberg： Springer. c2011： 223-241.

[3] 王璐, 孟小峰. 位置大數據隱私保護研究綜述[J]. 軟件學報, 2014,25(4)： 693-712.WANG L, MENG X F. Location privacy preservation in big data era： a survey[J]. Journal of Software, 2014, 25(4)： 693-712.

[4] 王宇航, 張宏莉, 余翔湛. 移動互聯網中的位置隱私保護研究[J].通信學報, 2015, 36(9)： 2015167.WANG Y H, ZHANG H L, YU X Z. Research on location privacy in mobile Internet[J]. Journal on Communications, 2015, 36(9)： 2015167.

[5] KIDO H, YANAGISAWA Y, SATOH T. An anonymous communication technique using dummies for location-based services[C]//The International Conference on Pervasive Services 2005. Washington, IEEE,c2005： 88-97.

[6] KIDO H, YANAGISWA Y, SATOH T. Protection of location privacy using dummies for location-based services[C]//The 21st International Conference on Data Engineering Workshops. Washington, IEEE,c2005： 1248.

[7] GRUTESER M, GRUNWALD. Anonymous usage of location-based services through spatial and temporal cloaking[C]//The 1st International Conference on Mobile, Systems, Applications and Services.New York, ACM, c2003： 31-42.

[8] TALUKDER N, AHAMED S I. Preventing multi-query attack in location-based services[C]//The 3rd ACM Conference on Wireless Network Security. New York, ACM, c2010： 25-36.

[9] BERSFORD A R, STAJANO F. Mix zones： user privacy in location-aware services[C]//The 2nd IEEE Annual Conference on Pervasive Computing and Communications Workshops. Washington, IEEE,c2004：127-131.

[10] GAO S, MA J F, SHI W S, et al. TrPF： a trajectory privacy-preserving framework for participatory sensing[J]. IEEE Transactions on Information Forensics and Security, 2013, 8(6)：874-887.

[11] ARDAGNA C, CREMONINI M, DAMIANI E, et al. Location privacy protection through obfuscation-based techniques[C]//The 21st Annual IFIP WG 11.3 Working Conference on Data and Applications Security,Berlin： Springer. c2007： 47-60.

[12] DAMIANI M L, BERTINO E, SILVESTRI. The probe framework for the personalized cloaking of private locations[J]. Transactions on Data Privacy, 2010, 3(2)：123-148.

[13] GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location based services： anonymizers are not necessary[C]//The 2008 ACM SIGMOD International Conference on Management of Data. New York, ACM, c2008： 121-132..

[14] MASCETTI S, FRENI D, BETTINI C, et al. Privacy in geo-social networks： proximity notification with untrusted service providers and curious buddies[J]. VLDB Journal, 2011, 20(4)： 541-566.

[15] LU H, JENSEN C S, YIU M L. Pad： privacy-area aware, dummy based location privacy in mobile services[C]//The Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access. New York, ACM, c2008： 16-23.

[16] NIU B, LI Q, ZHU X et al. Achieving k-anonymity in privacy-aware location-based services[C]//The 33rd Annual IEEE International Conference on Computer Communications. Washington, IEEE, c2014： 754-762.

[17] NIU B, ZHANG Z Y, LI X Q, et al. Privacy-area aware dummy generation algorithms for location-based services[C]//The 2014 IEEE International Conference on Communication. Washington, IEEE, c2014：957-962.

[18] NIU B, LI Q, ZHU X, et al. Enhancing privacy through caching in location-based services[C]//The 34th Annual IEEE International Conference on Computer Communications. Washington, IEEE, c2015：1017-1025.

[19] XU T, CAI Y. Exploring historical location data for anonymity preservation in location-based services[C]//The 27th Conference on Computer Communications. Washington, IEEE, c2008： 13-18.

[20] XU T, CAI Y. Feeling-based location privacy protection for location-based services[C]//The 16th ACM Conference on Computer and Communications Security. New York, ACM, c2009： 348-357.

[21] CHOW C Y, MOKBEL M. Enabling private continuous queries for revealed user locations[C]//The 10th International Symposium on Spatial and Temporal Databases. Berlin, Springer, c2007： 258-275.

[22] 潘曉, 郝興, 孟小峰. 基于位置服務中的連續查詢隱私保護研究[J].計算機研究與發展, 2010, 47(1)： 121-129.PAN X, HAO X, MENG X F. Privacy preserving towards continuous query in location-based services[J]. Journal of Computer Research and Development, 2010, 47(1)： 121-129.

[23] WANG Y, XU D B, HE X, et al. L2P2： location-aware location privacy protection for location-based services[C]//The 31st Annual IEEE International Conference on Computer Communication. Washington,IEEE, c2012： 1996-2004.

[24] LI X H, WANG E M, YANG W D, et al. DALP： a demand-aware location privacy protection scheme in continuous location-based services[J]. Concurrency and Computation： Practice and Experience,2016, 28(4)： 1219-1236.

[25] SCHLEGEL R, CHOW C Y, HUANG Q, et al. User-defined privacy grid system for continuous location-based services[J]. IEEE Transactions on Mobile Computing, 2015, 14(10)： 2158-2172.

[26] BRINKOFFff T. A framework for generating network-based moving objects[J]. Geo Informatica, 2002, 6(2)： 153-180.

Privacy enhancing method for dummy-based privacy protection with continuous location-based service queries

LIU Hai, LI Xing-hua, WANG Er-meng, MA Jian-feng
(School of Cyber Engineering, Xidian Universality, Xi’an 710071, China)

Without need for the third party and sharing key, the dummy-based privacy protection scheme enabled users to obtain the precise query result in location-based services. However, in continuous queries, since the existing dummybased privacy protection schemes ignored the spatio-temporal relevance of the submitted neighbor location sets, the adversary could infer dummies, making that the protection degree of users’ location privacy was reduced. To solve this problem, a dummy-based privacy protection enhancing method toward continuous queries was proposed. In the proposal,the candidate dummies were first generated by the existing dummy-based schemes, and could be filtered through the check of continuous reasonability and single privacy enhancement. Security analysis shows that, in the proposed method, the formed movement paths are indistinguishable in time and space, so that protecting the user’s location privacy effectively in continuous queries. Moreover, extensive experiments indicate that its computation cost is limited, and compared with the scheme adopted to generate candidate dummies, the user’s privacy protection is also enhanced in snapshot query.

location-based service, privacy enhancing, continuous queries, dummy, check of continuous reasonability

The National Natural Science Foundation of China (No.61372075, No.U1405255, No.61202389, No.61472310)

TP309

A

10.11959/j.issn.1000-436x.2016142

2015-10-25；

2016-05-20

李興華，xhli1@mail.xidian.edu.cn

國家自然科學基金資助項目（No.61372075, No.U1405255, No.61202389, No.61472310）

劉海（1984-），男，貴州貴陽人，西安電子科技大學博士生，主要研究方向為隱私保護和理性密碼協議。

李興華（1978-），男，河南南陽人，博士，西安電子科技大學教授、博士生導師，主要研究方向為隱私保護、網絡與信息安全。

王二蒙（1990-），女，陜西渭南人，西安電子科技大學碩士生，主要研究方向為位置隱私保護。

馬建峰（1963-），男，陜西西安人，博士，西安電子科技大學教授、博士生導師，主要研究方向為信道編碼、網絡與信息安全、密碼學。