面向連續查詢的敏感語義位置隱私保護方案

王永錄，左開中 ，曾海燕，劉 蕊，郭良敏

1.安徽師范大學 計算機與信息學院，安徽 蕪湖 241002

2.安徽師范大學 網絡與信息安全安徽省重點實驗室，安徽 蕪湖 241002

1 引言

隨著移動技術與定位技術的不斷發展，基于位置的服務（Location-Based Services，LBS）已逐步應用到更為廣泛的領域[1-3]。根據用戶查詢方式不同，LBS主要分為快照查詢和連續查詢。其中，連續查詢作為常見的LBS服務，用戶需要在查詢有效期內不斷更新位置，存在一定的風險，即位置隱私泄漏問題[4-5]。因此，如何在連續查詢中保護位置隱私已成為國內外學者關注的熱點。

現有路網環境下面向連續查詢的位置隱私保護方法大多基于K-匿名和L-路段多樣性[6-8]，即匿名區域至少包含K個用戶和L條路段。Wang等[9]通過歷史數據預測移動用戶在路網中的運動情況，來構造匿名區域。潘曉等[10]通過在連續查詢的最初時刻為用戶生成統一匿名用戶集，結合路網環境構建具有L條連通路段的匿名區域，來保護用戶位置隱私。Zhang等[11]提出在混合區域中共享相同查詢內容和時間間隔，使得攻擊者無法通過子軌跡推測真實用戶，保護位置隱私。張磊等[12]提出一種提高當前路段查詢密度值的密度壓縮算法，通過在用戶真實位置附近添加大量噪聲用戶，保護位置隱私。與基于語義位置的方法相比，現有連續查詢位置隱私保護方法均未考慮用戶所處語義位置信息，存在語義推斷攻擊[13]，導致用戶隱私泄漏。

已有路網環境下的語義位置隱私保護方法主要集中于快照查詢，即用戶只需向LBS服務器提供一次位置信息，LBS服務器根據用戶的位置和查詢內容提供服務。針對語義推斷攻擊問題，Li等[14]利用城市路網中的道路交叉口和語義位置進行Voronoi圖劃分，通過位置語義信息有選擇地添加鄰近Voronoi單元，構建語義安全匿名區域，實現隱私保護，但該方法存在匿名區域過大問題。Xu等[15]針對匿名區域過大問題，提出一種基于全局最優和局部最優的增量查詢方法，通過減少添加不必要的Voronoi單元，縮減匿名區域面積，降低查詢開銷，提升服務質量。陳慧等[16]針對敏感位置信息泄漏問題，提出一種基于用戶個性化隱私需求的語義位置保護方法。然而，若將這些方法簡單應用于連續查詢，攻擊者就可以利用相鄰時刻匿名用戶集間的關聯關系，通過識別用戶身份標識信息推測真實查詢用戶，即連續查詢追蹤攻擊[17]，導致用戶隱私泄漏。

基于此，本文提出一種路網環境下面向連續查詢的敏感語義位置隱私保護方案，通過設計(K,θ)-隱私模型構建匿名區域，提高用戶身份的不確定性和所處敏感語義位置的隱私保護程度，更為有效地同時抵御連續查詢追蹤攻擊和語義推斷攻擊。

2 預備知識

2.1 相關定義

連續查詢可以分為新到查詢用戶和活動查詢用戶兩種[10]。新到查詢用戶是指首次發出連續查詢的用戶；活動查詢用戶是指在連續查詢有效期內發生位置更新的用戶。鑒于路網環境下的連續查詢過程中，用戶在交叉路口的運動具有不可預知性，本文假設已知用戶在查詢有效期內的移動路徑[10]，如“查詢從北京大學路徑清華大學、人民大學到達上地過程中距離我最近的醫院”。

定義1（帶Voronoi劃分的路網）路網是現實生活中多條道路（即路段）構成的交通網絡，可以形式化表示為一個無向圖G(V,E)，其中：

（1）E是邊的集合，每條邊對應一條路段，記為e={eid,(vi,vj),velmax}，其中，eid表示路段編號，(vi,vj)表示路段始點和終點（即路段結點），velmax表示路段最大速度限制。

（2）V 是路段結點的集合，記為V={v1,v2,…}，其中v表示路段結點。路網G(V,E)中每個路段結點的Voronoi單元滿足Voronoi(v)={z:d(z,v)≤d(z,w),w≠v,(w,v)∈V}，其中，d(z,v)表示z到v的歐式距離，z表示路網中的任意位置。這些Voronoi單元互不重合，包含多條路段。

因此，一個帶Voronoi劃分的路網可以表示為G(V,E,Voronoi(v))。

定義2（語義位置流行度）是指用戶訪問該語義位置的概率。設loc是一個語義位置，U(loc)={u1,u2,…,um}是訪問過該語義位置的用戶集合，并設nj是用戶uj對loc的訪問次數，該語義位置被訪問的總數記為因此該語義位置的流行度定義為P(loc)=中，H(loc)=，它表示該語義位置的信息熵，即被用戶訪問的可能性。為了便于區分語義位置與道路交叉口，設置道路交叉口的流行度為0。

定義3（語義位置）是指具有坐標、語義位置類型（如醫院、學校等）和流行度等特征的位置，記為loc={(x,y),type,P(loc)}，在路網中使用距離最近的路段結點表示，其中，(x,y)表示語義位置坐標，type表示語義位置類型，P(loc)表示語義位置流行度。語義位置是否敏感由用戶定義，例如醫院，部分患者認為是敏感的，醫生則認為是非敏感的。

定義4（連續查詢移動路徑）是指用戶連續查詢期間經過的路段結點。一個連續查詢移動路徑被形式化表示為路段結點的有序序列，記為 path={ }nodes,size，其中，nodes表示經過的路段結點集合，記為nodes=表示經過的路段結點個數。為了簡便，假設系統中連續查詢用戶的起點和終點都為路段結點。若連續查詢用戶位于路段中的某個位置點上，系統會自動將其轉化為最近鄰路段結點。

定義5（用戶）是指在路網上發起連續查詢請求的移動對象，記為u={u id,loc,e,path,vel,PR} ，其中，uid表示用戶編號，loc表示用戶所處語義位置，e表示用戶所在路段，path表示用戶連續查詢移動路徑，vel表示用戶移動速度，PR表示用戶的隱私需求，記為PR={K ,θ,senstype}，其中，K表示用戶定義的匿名用戶數量，θ表示用戶定義的語義安全閾值，senstype表示用戶定義的敏感語義位置類型。

定義6（匿名區域）是指一個用來隱藏用戶語義位置的空間區域，記為CR={ }users,Voronois，其中，users表示CR中的匿名用戶集合，記為users={u1,u2,…}，Voronois表示CR中的Voronoi單元集合，記為Voronois={Voronoi(v1),Voronoi(v2),…}，這些Voronoi單元可以構成連通圖，具有連通性。

定義7（θ-語義安全匿名區域）已知一個匿名區域CR和一個用戶u，對用戶u來說CR中屬于敏感的語義位置用senslocsu表示，則匿名區域敏感語義位置總流行度記為 popCR(senslocsu)，匿名區域語義位置總流行度記為 popCR(?)，匿名區域語義安全程度用d(CR)表示：

若匿名區域的語義安全程度d(CR)≤u.PR.θ，稱CR對用戶u來說是一個θ-語義安全匿名區域。

定義8（平均移動速度）是指用戶移動速度的平均值vavg，可表示為：

其含義是根據用戶當前移動速度來預測在整個連續查詢移動路徑上的平均速度，其中，u.vel表示用戶當前移動速度，u.e.velmax表示用戶所在路段最大限制速度，vi表示用戶經過路段結點集合中第i個路段結點，e.velmax表示以(vi,vi+1)作為始點和終點的路段最大限制速度。

定義9（時空相似性）是指兩個用戶在連續查詢移動路徑和移動速度方面的相似程度，其值越大，移動路徑和移動速度越相似。已知2個用戶ui和uj，其對應的連續查詢移動路徑為 pathi和 pathj，平均移動速度為ui.vavg和uj.vavg，則時空相似性δ可表示為：

2.2 系統架構

本文方案采用的是匿名保護方法下的LBS中心服務器系統架構[9-10]，如圖1所示。該系統架構由用戶、匿名服務器及LBS服務器3部分組成。本文假定匿名服務器是可信的，由匿名區域構造模塊和候選結果集求精模塊組成。其中，匿名區域構造模塊負責對用戶位置進行匿名處理；候選結果集求精模塊負責對LBS服務器返回的結果進行求精。當用戶發出請求時，將自己的位置信息、隱私需求和查詢內容發送給匿名服務器。匿名服務器根據隱私保護算法進行匿名處理，并將處理后的查詢請求發送給LBS服務器。LBS服務器計算出候選查詢結果集并返回給匿名服務器。匿名服務器對LBS服務器返回的結果進行篩選，并將精確查詢結果返回給用戶。本系統中，匿名服務器需要保存當前的地圖信息、語義位置信息及流行度。

3 方案描述

針對連續查詢位置服務中存在連續查詢追蹤攻擊和語義推斷攻擊問題，本文方案通過設計(K,θ)-隱私模型構建匿名區域，來保護用戶身份和敏感語義位置隱私。

3.1 (K,θ)-隱私模型設計

假設CRi(1≤i≤t)為用戶u在第i時刻形成的匿名區域，CR1.users表示用戶u在初始時刻根據時空相似性構建的匿名用戶集，CRi.users表示第i時刻的匿名用戶集，u.loci.type表示用戶在第i時刻所處語義位置類型，u.PR.K表示用戶定義的匿名用戶數量，u.PR.senstype表示用戶定義的敏感語義位置類型，u.PR.θ表示用戶定義的語義安全閾值。如果CRi滿足如下四個條件：

（1）| C Ri.users|≥u.PR.K；

圖1 LBS中心服務器系統架構

（2）CRi.users=CR1.users；

（3）if u.loci.type∈u.PR.senstype,d(CRi)≤u.PR.θ；

（4）?u∈CRi.users,u發布CRi作為匿名區域。

則稱CRi滿足(K,θ)-隱私模型，其中：條件1確保匿名用戶集至少有K個用戶，滿足K匿名性質；條件2確保每個時刻匿名區域的匿名用戶集都包含相同的用戶，防止連續查詢追蹤攻擊；條件3確保匿名區域語義安全程度滿足用戶的語義安全需求，防止語義推斷攻擊；條件4確保每個CRi.users中的用戶在該時刻形成的匿名區域都是相同的，滿足位置K-共享性質。

3.2 算法設計

本文方案基于(K,θ)-隱私模型，提出一種路網環境下面向連續查詢的敏感語義位置隱私保護算法，主要思想如圖2所示。

圖2 算法流程圖

（1）利用城市路網語義位置和道路交叉口進行Voronoi圖劃分。

（2）判斷連續查詢用戶狀態。若用戶為新到查詢用戶，則基于時空相似性為用戶構建滿足K匿名的用戶集，并以此作為該用戶連續查詢的統一匿名用戶集；否則，執行步驟（3）。

（3）根據匿名用戶集各用戶當前時刻所處語義位置的Voronoi單元構建具有連通性的匿名區域。

（4）若匿名用戶集中有用戶處于敏感語義位置，根據用戶設定的敏感語義位置類型計算匿名區域語義安全程度；否則，返回匿名區域。

（5）若匿名區域語義安全程度滿足用戶設定的語義安全閾值，返回匿名區域；否則，遍歷所有與匿名區域相連通的鄰近語義位置。優先添加流行度最大的非敏感語義位置，其次隨機選擇道路交叉口，最后選擇流行度最小的敏感語義位置。

（6）將該語義位置對應的Voronoi單元加入匿名區域，執行步驟（5）。

算法1給出了路網環境下面向連續查詢的敏感語義位置隱私保護算法（Sensitive-semantic Location Privacy Protection Algorithm for Continuous Query under Road Network Environment，SLPP）的偽代碼。首先判斷用戶的查詢狀態（第1行），對于新到查詢用戶，調用算法2分組構建匿名用戶集（第2～11行），根據初始時刻匿名用戶集中各用戶所處語義位置及隱私需求調用算法3構建匿名區域（第12～22行）；對于活動查詢用戶，則根據當前時刻匿名用戶集各用戶所處語義位置、敏感語義位置類型和語義安全閾值調用算法3構建匿名區域（第24、25行）。

算法1路網環境下面向連續查詢的敏感語義位置隱私保護算法

輸入：連續查詢路徑 path、隱私需求PR、帶Voronoi劃分的路網G(V,E,Voronoi(v))、時空相似性δ

輸出：時刻ti的匿名區域CRi(1≤i≤t)

1.If{NewUsers}是新到查詢用戶 then

2. Uset=?；//記錄分組構造的匿名用戶集

3. While true do

4. If{NewUsers}≠? then

5. 從{NewUsers}集合中隨機選擇u；

6. Uset=Uset?使用算法2為u生成的匿名用戶集users；

7. {NewUsers}={NewUsers}-users；

8. Else

9. Break；

10. End if

11.End while

12.Forusers∈Usetdo

13. 根據匿名用戶集users，找到users中用戶所處語義位置集合vset1；

14. Voronois1=GetVoronoi(vset1)；//獲取各語義位置所在Voronoi單元

15. IfVoronois1是非連通的 then

16. 添加必要連通Voronoi單元，更新Voronois1；

17. End if

18. If ?u∈users,u.loc1.type∈u.PR.senstypethen

19. 使用算法3生成匿名區域；

20. End if

21.End for

22.Return{CR1}；

23.Else//活動查詢用戶

24.使用算法3生成語義安全匿名區域；

25.Return{CRi}；

26.End if

在構建匿名用戶集時，本文方案使用時空相似性選擇匿名用戶。主要思想是從用戶所在路段出發，計算連續查詢用戶與其他用戶的時空相似性，將滿足要求的移動用戶加入匿名用戶集，直至滿足該集合所有用戶的K匿名需求。算法2給出了偽代碼，首先初始化系統變量（第1～4行），從用戶當前所在路段出發，依次計算其他用戶與當前查詢用戶的時空相似性，將滿足要求的用戶加入集合USERset（第9～12行），若能找到K個用戶，則從第5～25行的循環中跳出，否則從連續查詢用戶所在路段進行寬度優先搜索，執行第5～25行。最后判斷USERset中的匿名用戶數量是否大于等于K（第26行），若滿足，則返回匿名用戶集（第27行）。

算法2匿名用戶集構建算法

輸入：連續查詢用戶u、帶Voronoi劃分的路網G(V,E,Voronoi(v))、時空相似性δ

輸出：匿名用戶集合

1. USERset=?；

2. Edgeset=?；//記錄已經遍歷的路段

3. Nearedgeset={u.e}；//相鄰路段集合

4. count=0；//記錄查找相鄰路段的次數

5.While true do

6. Foregde∈Nearedgesetdo//遍歷所有相鄰路段

7. Edgeset.add(edge)；

8. Foruser∈edgedo//遍歷每條相鄰路段上的用戶

9. If(u,user)的時空相似性≥δ then

10. USERset.add(user)；

12. End if

13. End for

14. If |USERset|≥u.PR.K then

15. Break；

16. End if

17. End for

18. If |USERset|≥u.PR.K||count>(1-δ)×10then

19. Break；

20. Else

21. Nearedgeset=?；

22. Nearedgeset=Edgeset所有相鄰路段；

23. count++；

24. End if

25.End while

26.If |USERset|≥u.PR.K then

27. ReturnUSERset；

28.Else

29. Break；

30.End if

在構建語義安全匿名區域時，本文方案根據匿名用戶集各用戶定義的敏感語義位置類型和語義安全閾值構建匿名區域。主要思想是針對處于敏感語義位置的用戶，通過添加非敏感的相鄰語義位置，降低敏感語義位置流行度比重，直至滿足用戶的語義安全需求。算法3給出了偽代碼，首先初始化系統變量（第1～2行），找到連續查詢用戶在初始時刻構建的匿名用戶集Users、當前時刻各用戶所處語義位置集合vseti以及各語義位置所在Voronoi單元集合Voronoisi（第3～5行），將當前時刻處于敏感語義位置的用戶加入集合TUset，并將對應的敏感位置類型加入集合SLset（第6～11行），通過添加必要連通Voronoi單元使得Voronoisi集合內Voronoi單元具有連通性（第12～15行）。若當前時刻TUset為空集，直接返回匿名區域；否則計算匿名區域語義安全程度是否滿足TUset中每一個用戶的語義安全閾值，滿足則返回匿名區域，否則根據SLset添加鄰近Voronoi單元，直至滿足TUset中每一個用戶的語義安全閾值，返回匿名區域（第15～35行）。

算法3語義安全匿名區域構建算法

輸入：連續查詢用戶u，帶Voronoi劃分的路網G(V,E,Voronoi(v))

輸出：θ-語義安全匿名區域

1. SLset=?；//敏感語義位置類型集合

2. TUset=?；//位于敏感語義位置的用戶集合

3. Users=用戶u的匿名用戶集；

4. 找到Users中用戶當前時刻所處語義位置集合vseti；

5. Voronoisi=GetVoronoi(vseti)；//獲取 vseti中各語義位置所在Voronoi單元

6.Foruser∈Usersdo

7. Ifuser.loci.type∈user.PR.senstypethen

8. TUset=TUset?user；

9. SLset=SLset?user.PR.senstype；

10. End if

11.End for

12.IfVoronoisi是非連通的 then

13. 添加必要連通Voronoi單元，更新Voronoisi；

14.End if

15.IfTUset=? then

16.ReturnCRi；

17.Else

18.While true do

19. If ?u∈TUset,d(CRi)≤u.PR.θthen

20. Break；

21. Else//查找與匿名區域具有連通路段的所有語義位置

22.NSset=GetNSLinks(CRi,SLset)；//記錄非敏感語義位置結點

23.INset=GetINLinks(CRi,SLset)；//記錄道路交叉口結點

24.SNset=GetSNLinks(CRi,SLset)；//記錄敏感語義位置結點

25. IfNSset≠? then

26.vlink=SelectMaxpop(NSset)；//選擇流行度最大的語義位置

27. Else ifINset≠? then

28.vlink=RandomSelect(INset)；//隨機選擇一個道路交叉口

29. Else ifSNset≠? then

30.vlink=SelectMinpop(SNset)；//選擇流行度最小的語義位置

31. End if

32.Voronoisi=Voronoisi?Voronoi(vlink)；

33. End if

34.End while

35.ReturnCRi；

36.End if

4 實驗及結果分析

4.1 實驗設置

本文對比了SCPA算法[10]和TB算法[18]，因為SCPA算法、TB算法和本文算法都是通過構建具有K個共同用戶的匿名用戶集抵御連續查詢追蹤攻擊，但沒有考慮語義安全性。其中，SCPA算法基于K匿名和L多樣性（L默認設置為3），TB算法基于K匿名和四叉樹。

所有的匿名算法均用Java實現，并運行在一臺配置為2.83 GHz Intel CoreTM2，2 GB內存的Windows7計算機上。本實驗使用Thomas Brinkhoff移動對象生成器[19]生成模擬移動對象，生成器的輸入是德國Oldenburg地圖，包含6 105個結點和7 035條邊。實驗模擬生成10 000個移動用戶，設每個對象均提出連續查詢，默認包括20個快照位置。同時實驗還設置了1000個均勻分布的語義位置（均分布在路段結點），共6種類型（見表1）。

表1 實驗參數設置

實驗采用控制變量法，在保證其他參數不變的情況下，通過改變匿名用戶數、語義安全閾值和語義位置數量進行驗證。為了計算簡單，假設類型相同的語義位置具有相同的流行度，取值為{學校：0.2，醫院：0.15，辦公：0.25，娛樂：0.15，商場：0.15，公園：0.1，路口：0}，敏感語義位置類型設置為{醫院、娛樂}，時空相似性δ取值為0.7，其中，δ值與文獻[10]取值相同。表1列出了實驗參數具體信息。

4.2 實驗結果分析

（1）隱私保護度。它是指滿足語義安全閾值的匿名區域數量同總產生的匿名區域數量之比，比值越大，隱私保護度越好。圖3比較了θ值以及K值的變化對隱私保護度的影響。從圖3可以看出，由于SLPP算法始終考慮語義安全性，而SCPA算法和TB算法不考慮，所以SLPP算法的隱私保護度始終高于SCPA算法和TB算法，且幾乎不受K值變化影響。因此，SLPP算法所提供的隱私保護度更高。

圖3 隱私保護度比較

（2）系統開銷。它使用平均匿名區域面積來度量，匿名區域面積越大，查詢和處理開銷越大，對應系統開銷越大。圖4比較了θ值以及K值的變化對平均匿名區域面積的影響。如圖4（a）所示，由于SCPA算法和TB算法不考慮語義安全性，所以匿名區域面積不受θ值影響。隨著θ值增加，SLPP算法生成的匿名區域面積呈下降趨勢。這是因為θ值越大，構建語義安全匿名區域需要添加的相鄰語義位置越少，使得匿名區域面積相應減小。如圖4（b）所示，隨著K值增加，三種算法的平均匿名區域面積呈上升趨勢。其中，在K值小于等于5時，SLPP算法的平均匿名區域面積高于TB算法，大于5時要低于TB算法，這是因為K值越大，TB算法需要不斷將匿名區域擴展為所在四叉樹結點的父結點，直至每個時刻的匿名區域都包含K個公共用戶，導致匿名區域不斷變大。但SLPP算法的匿名區域面積始終小于SCPA算法，因此SLPP算法的系統開銷較低。

（3）平均執行時間。平均執行時間是指算法成功匿名所用的時間，平均執行時間越少，算法執行效率越好。圖5比較了θ值以及K值的變化對平均執行時間的影響。如圖5（a）所示，由于SCPA算法和TB算法不考慮語義安全性，所以平均執行時間不受θ值影響。隨著θ值增加，SLPP算法執行時間呈下降趨勢。這是因為θ值越大，語義安全要求越寬松，添加相鄰語義位置的次數逐漸減少，算法執行時間相應減少。如圖5（b）所示，隨著K值增加，三種算法的平均執行時間呈上升趨勢，但SLPP算法的平均執行時間一直低于TB算法，略高于SCPA算法。這是因為SCPA算法只考慮匿名區域的路段多樣性，并沒有考慮語義安全性，因此執行時間略低于SLPP算法；TB算法通過不斷擴展匿名區域，確保每個時刻生成的匿名區域包含K個公共用戶，花費時間較多；SLPP算法始終考慮語義安全性，通過不斷添加相鄰語義位置構建語義安全匿名區域。然而，SLPP算法僅比SCPA算法大約多花費了1%的執行時間。

（4）可擴展性。可擴展性是評價算法可執行性的一個重要指標。圖6給出了總語義位置數量從1 000增加到1 800時，系統開銷和平均執行時間的變化情況。其中：K值為5，θ值為0.5，敏感語義位置類型為{醫院、娛樂}。由于SCPA算法和TB算法不考慮語義安全性，所以語義位置數量的變動與它們無關。從圖6可以看出，隨著語義位置數量的增加，SLPP算法在系統開銷和平均執行時間方面均呈下降趨勢。這是因為隨著語義位置數量增加，非敏感語義位置數量逐漸增多，構建語義安全匿名區域時需要添加的相鄰語義位置數量減少，縮減匿名區域面積，減少算法執行時間。由此可見，SLPP算法的可擴展性更好。

5 結束語

圖4 系統開銷比較

圖5 平均執行時間比較

圖6 可擴展性比較

本文針對連續查詢位置服務中存在的連續查詢追蹤攻擊和語義推斷攻擊，通過設計(K,θ)-隱私模型，提出一種路網環境下面向連續查詢的敏感語義位置隱私保護方案。該方案利用時空相似性為連續查詢用戶構建統一匿名用戶集，并依據該匿名用戶集用戶的語義安全需求構建匿名區域。最后，采用模擬數據進行大量實驗，驗證了本文所提方案的有效性。

然而，本文方案僅利用語義位置的空間分布來構建匿名區域，未考慮時間維度。因此，下一階段的研究可以結合語義位置的空間分布和時間維度構建匿名區域，進一步增強隱私保護程度。