鄭振青，毋小省，王 輝，劉 琨，申自浩

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作 454003)

1 概 述

近年來，隨著智能移動設(shè)備和移動應(yīng)用的快速普及，為基于位置的服務(wù)(Location Based Service，LBS)[1，2]奠定了基礎(chǔ).如今LBS服務(wù)已不僅僅應(yīng)用于軍事，同時也廣泛應(yīng)用于商業(yè)用戶.用戶使用移動設(shè)備(智能手機，平板等)通過位置服務(wù)查詢并獲取興趣點(points of interests，POIs)，在用戶使用位置服務(wù)帶來便利的同時，大量的位置信息在個人不知情的情況下被第三方收集、分析并加以利用.由于用戶移動軌跡中包含用戶眾多隱私信息，惡意攻擊者通過非法途徑獲取用戶的位置信息，進(jìn)而推測出各類感興趣的事件和位置，造成用戶位置隱私泄露[3，4].因此在位置隱私保護(hù)中用戶軌跡隱私安全對用戶來說尤為重要.

為了保護(hù)軌跡隱私數(shù)據(jù)安全，在軌跡數(shù)據(jù)發(fā)布前，需使用適當(dāng)?shù)碾[私保護(hù)技術(shù)對軌跡數(shù)據(jù)進(jìn)行預(yù)處理[5].目前的軌跡隱私保護(hù)技術(shù)主要分為泛化法、抑制法和假數(shù)據(jù)法.1)泛化法，基于k匿名(k-anonymity)的方法是比較主流的泛化法.即對任意一條軌跡，至少需要k-1條其他軌跡被轉(zhuǎn)換成完全相同的匿名軌跡來構(gòu)成一個匿名軌跡集合[6]，從而使惡意攻擊者無法對一個區(qū)域內(nèi)的k個匿名用戶進(jìn)行區(qū)分.該種方法在軌跡隱私保護(hù)中使用廣泛，并延伸出了不同的改進(jìn)方法.2)抑制法，該方法在軌跡數(shù)據(jù)信息發(fā)布過程中，對敏感數(shù)據(jù)限制發(fā)布或經(jīng)過轉(zhuǎn)換處理后發(fā)布，降低用戶數(shù)據(jù)的敏感性.3)假數(shù)據(jù)法，該方法生成用戶位置信息假數(shù)據(jù)并和真實數(shù)據(jù)進(jìn)行混合，以此來降低用戶數(shù)據(jù)泄露的概率.但這些方法也有局限性，k匿名在連續(xù)位置查詢中安全性降低.抑制法抑制的點一旦過多，會影響發(fā)布數(shù)據(jù)的可用性，導(dǎo)致服務(wù)質(zhì)量降低.假數(shù)據(jù)法易造成服務(wù)質(zhì)量下降，查詢的準(zhǔn)確度會受到一定的影響.另外惡意攻擊者利用已獲得的多個匿名數(shù)據(jù)，并根據(jù)掌握的相關(guān)背景知識有很大概率推測出移動用戶的隱私信息，攻擊者根據(jù)用戶發(fā)起的連續(xù)查詢位置信息，收集這些位置信息再重構(gòu)出用戶軌跡，從而推測出用戶的工作地居住地甚至用戶的行為模式等敏感信息[7].

針對上述問題，本文提出一種個性化軌跡隱私保護(hù)方法(Personalized trajectory privacy protection method，PTPM)，主要貢獻(xiàn)如下：

1)在用戶移動端增加緩存區(qū)，緩存每次查詢得到的候選結(jié)果集，供用戶后續(xù)查詢使用.

2)在用戶和LBS服務(wù)器之間部署安全中心(Security Center，SC)和多匿名器，安全中心對用戶進(jìn)行簽名注冊，并調(diào)配公私鑰對位置信息進(jìn)行安全驗證.另外SC對同一用戶查詢信息進(jìn)行拆分并發(fā)送給多匿名器，多匿名器對用戶信息進(jìn)行隨機并發(fā)式k匿名，在安全性上有很大提升.

3)在LBS服務(wù)器端加入前綴樹，使用基于分簇數(shù)據(jù)融合隱私保護(hù)算法(Cluster-based Private Data Aggregation，CPDA)對數(shù)據(jù)庫位置信息進(jìn)行加密保護(hù)，將位置信息經(jīng)過加密處理生成密文，密文具有不可閱讀性，防止攻擊者非法入侵?jǐn)?shù)據(jù)庫.并使用最優(yōu)二叉樹算法查詢用戶POIs，提升用戶位置查詢效率.

2 相關(guān)工作

軌跡隱私保護(hù)方法中k匿名方法廣泛使用[8，9]，但是k匿名也存在如下缺點：1)在人群稀疏地區(qū)很難尋找k-1個匿名用戶來構(gòu)建k匿名；2)k匿名方法一般只適用于查詢小范圍匿名域，若進(jìn)行連續(xù)查詢，攻擊者通過分析多個連續(xù)的匿名區(qū)域中重復(fù)出現(xiàn)的用戶，從而可以鎖定并重構(gòu)用戶的真實軌跡.

針對軌跡隱私中使用的匿名算法，國內(nèi)外許多學(xué)者在傳統(tǒng)k匿名基礎(chǔ)上進(jìn)行改進(jìn)或創(chuàng)新，針對k匿名在連續(xù)查詢中的缺陷，文獻(xiàn)[10]提出了一種面向連續(xù)查詢的隱私保護(hù)方法.用戶與用戶之間通過移動設(shè)備附帶的無線功能進(jìn)行短距離傳輸，從鄰近用戶的緩存信息中收集需要的信息，然后通過發(fā)布假的查詢信息與用戶的真實位置信息進(jìn)行混淆.但是該方法在人群稀少地方增加了系統(tǒng)查詢時間.文獻(xiàn)[11]通過打亂路徑軌跡的順序性，然后在匿名區(qū)域進(jìn)行匿名并隨機發(fā)送不同的軌跡給用戶，使惡意攻擊者無法重構(gòu)用戶的真實軌跡，該方法可有效抵御惡意攻擊者的連續(xù)查詢攻擊.文獻(xiàn)[12]在基于位置服務(wù)查詢過程中，提出一種關(guān)于k匿名防止位置注入攻擊的隱私保護(hù)方法，它結(jié)合用戶的行為習(xí)慣建立可信的k匿名機制，使惡意攻擊者獲取真實用戶的概率僅為1/k.為了提升用戶的軌跡隱私安全性，文獻(xiàn)[13]針對用戶軌跡隱私保護(hù)方法Silent Cascade，提出一種新的軌跡隱私度量方法，文中引入了帶權(quán)無向圖，用來描述用戶的運動軌跡，并從信息熵的角度計算用戶的軌跡隱私水平.

基于點對點(peer to peer，P2P)的結(jié)構(gòu)和基于可信第三方(fully-trusted third party，TTP)的中心服務(wù)器結(jié)構(gòu).他們大都有類似的模型對用戶的軌跡隱私進(jìn)行保護(hù)，模型組成主要有3部分：用戶、第三方可信匿名器和LBS服務(wù)器.P2P結(jié)構(gòu)中用戶與用戶之間相互可信，且用戶之間相互配合形成匿名域后再向LBS服務(wù)器發(fā)送位置請求[14]，該種方法中的點對點用戶并不能隨時保證每個地點有足夠的用戶來進(jìn)行信息交互，而且匿名器負(fù)責(zé)處理所有用戶的位置信息和查詢內(nèi)容，如果匿名器出現(xiàn)故障或被攻擊者攻破，對用戶軌跡隱私將會帶來嚴(yán)重的安全威脅.并且單個匿名器容易造成性能瓶頸.針對該種問題，文獻(xiàn)[15]提出了一種多匿名器保護(hù)方法，通過在用戶和LBS服務(wù)器之間部署多個匿名器，在連續(xù)查詢過程中，用戶分別隨機選擇不同的匿名器進(jìn)行匿名.

軌跡隱私保護(hù)問題可以分為連續(xù)查詢中的軌跡隱私保護(hù)和數(shù)據(jù)發(fā)布中的軌跡隱私保護(hù)[16，17].多數(shù)文獻(xiàn)對軌跡隱私的保護(hù)采取的措施大都是針對數(shù)據(jù)傳輸過程中的保護(hù)，LBS是保存所有位置信息發(fā)布的終端設(shè)備，一旦被攻擊者攻破將泄露大量的位置隱私信息.為了防止攻擊者通過某些途徑鎖定LBS服務(wù)器中用戶的位置信息，在PTPM的LBS服務(wù)器端對位置信息使用CPDA進(jìn)行加密保護(hù)，當(dāng)需要查詢位置信息時通過SC調(diào)配公私鑰進(jìn)行解密.

3 系統(tǒng)模型和相關(guān)定義

3.1 系統(tǒng)模型

PTPM軌跡隱私保護(hù)模型如圖1所示.

圖1 PTPM軌跡隱私保護(hù)模型

PTPM中包括用戶，安全中心SC，多匿名器和LBS服務(wù)器4類主要的實體模型.其具體的工作流程為：

1)用戶：用戶攜帶具有無線定位、無線通信功能的智能移動設(shè)備.將用戶所在的地理區(qū)域劃分成一個邊長為m的正方形二維平面，并將該區(qū)域劃分出g×g個網(wǎng)格單元.地理區(qū)域從左到右為x軸正方向，從下到上為y軸正方向.用戶緩存范圍為一個半徑為R的圓形區(qū)域.用戶發(fā)送位置查詢信息經(jīng)過SC和多匿名器給LBS服務(wù)器，LBS服務(wù)器將查詢到的位置信息原路反饋給SC，SC規(guī)劃緩存區(qū)并發(fā)送給用戶，用戶接收位置信息使用移動設(shè)備緩存該區(qū)域，在該區(qū)域范圍內(nèi)用戶不需要和LBS服務(wù)器交互.用戶移動設(shè)備定時向SC發(fā)送緩存區(qū)查詢，當(dāng)用戶移動到緩存邊緣時繼續(xù)向LBS服務(wù)器發(fā)送查詢.

2)安全中心SC：安全中心為一個可信實體，主要負(fù)責(zé)存儲用戶移動端設(shè)定的隱私參數(shù)，并對位置信息進(jìn)行加密.安全中心提前接收用戶發(fā)送的安全驗證并保存驗證信息.在用戶查詢位置信息時驗證用戶提前設(shè)定的隱私參數(shù)，并為用戶頒發(fā)數(shù)字證書PRu，PRu作為用戶的私鑰，另外安全中心給LBS服務(wù)器發(fā)送對應(yīng)的公鑰PKu，公鑰與私鑰用于對位置信息加密解密.

3)多匿名器：多匿名器主要的作用是形成k匿名區(qū)域，以此來保證用戶位置信息數(shù)據(jù)在傳輸過程中的安全性.匿名器需要獲取用戶當(dāng)前的位置信息，以便進(jìn)行并發(fā)k匿名處理，SC將用戶查詢信息分為M份并隨機轉(zhuǎn)發(fā)給M個匿名器，每個匿名器對收到的位置信息片段單獨進(jìn)行k匿名.

4)LBS服務(wù)器：LBS服務(wù)器能及時存儲和更新位置服務(wù)信息，使用前綴樹保存加密的位置信息，并為用戶提供各種位置數(shù)據(jù)服務(wù).LBS服務(wù)器根據(jù)匿名器發(fā)送的匿名域范圍，查詢該區(qū)域內(nèi)包含的POIs信息.另外LBS服務(wù)器根據(jù)用戶查詢興趣點，在數(shù)據(jù)庫查詢對應(yīng)位置，將查詢到的位置信息使用公鑰加密經(jīng)多匿名轉(zhuǎn)發(fā)給SC，SC規(guī)劃緩存區(qū)并發(fā)送給用戶，用戶移動端利用私鑰PRu對位置信息進(jìn)行解密并求精.

3.2 相關(guān)定義

定義2.匿名緩存區(qū).多匿名器形成的匿名區(qū)域由k個查詢點構(gòu)成，用戶移動端緩存區(qū)需滿足以下條件，k-1個用戶的查詢點必須以查詢用戶為中心，設(shè)定最小半徑minr和最大半徑maxr.大于minr是為了保證匿名區(qū)的面積不能過小，若匿名區(qū)面積過小則匿名度不夠.小于maxr是為了保證匿名區(qū)的k個匿名成員不能過于分散，防止k匿名喪失對真實用戶查詢點的保護(hù).

定義3.數(shù)據(jù)緩存隱私度量[18].根據(jù)信息熵對數(shù)據(jù)集的影響，基于緩存的隱私度量可表示為：

(1)

其中|Ecache|為緩存區(qū)域，|Eserver|表示向LBS服務(wù)器查詢的區(qū)域，g2表示劃分的網(wǎng)格數(shù)量，H(e)表示在查詢過程中查詢結(jié)果的不確定性.在用戶緩存區(qū)獲取過程中緩存區(qū)單元命中率可以表示為：

|Ecache|=ξ×(|Ecache|+|Eserver|)

(2)

將式(2)代入式(1)為：

(3)

從式(3)中可以看出，隱私度量值λ的大小和緩存區(qū)單元命中率ξ成正比，通過提高緩存命中率可以提高隱私度量值，準(zhǔn)確獲取緩存區(qū)位置，可以減少用戶連續(xù)向LBS服務(wù)器查詢的次數(shù)，保障用戶軌跡隱私安全.

定義4.時間截點NT[19].匿名器搜索k-1個用戶進(jìn)行k匿名時，如果在人群稀少的地方，在一定時間截點NT內(nèi)搜索不到k-1個匿名用戶，則產(chǎn)生虛假位置來代替剩下難以搜索到的匿名用戶，用來限制匿名器在搜索k-1個匿名用戶上花費過多的時間.

定義5.虛假位置速度差spe.虛假位置與真實用戶在相同時間段內(nèi)速度的差異性，在時刻ti-1和ti用戶對應(yīng)的位置為posi-1和posi，相同時刻虛假位置對應(yīng)的位置分別為fpi-1和fpi，則速度偏差為：

(4)

(5)

用Q表示用戶軌跡信息熵，用戶到達(dá)目的地總共查詢的次數(shù)為η.log2k為k匿名中最大信息熵，則Q定義為：

(6)

定義7.匿名前綴樹.定義tree=(ID，record，children，POI)，ID表示用戶標(biāo)識，record為節(jié)點軌跡的位置記錄，children表示子節(jié)點，POI表示用戶查詢位置興趣點，前綴樹的構(gòu)造、剪枝、重構(gòu)等技術(shù)為可信第三方隱私保護(hù)模塊提供了可行性.

定義8.位置軌跡數(shù)據(jù)集.移動對象Ui的軌跡數(shù)據(jù)集URi由移動對象連續(xù)移動構(gòu)成的時空序列L1→L2→…→Llengthi(1≤i≤n)，其中l(wèi)engthi為數(shù)據(jù)集URi的長度，n為軌跡節(jié)點，用path來表示用戶的有序軌跡集.path={L1，L2，…，Ln}.

4 PTPM軌跡隱私保護(hù)方法

PTPM軌跡隱私保護(hù)過程，主要分為5個步驟，下面將分別進(jìn)行介紹.

4.1 SC安全布局

1)用戶服務(wù)注冊：用戶首先使用移動設(shè)備向SC進(jìn)行安全注冊，根據(jù)定義1，用戶身份標(biāo)識ID和私鑰一起加密得到用戶驗證注冊信息DSC(IDk).SC接收用戶注冊信息保存在數(shù)據(jù)庫并向用戶發(fā)送私鑰PRu，同時SC生成公鑰PKu發(fā)送給LBS服務(wù)器.

2)用戶查詢認(rèn)證：當(dāng)用戶需要查詢POI時需要向SC驗證用戶注冊信息，用戶使用私鑰PRu對ID進(jìn)行簽名得到SigPRu(ID)，SC通過SigPRu(ID)驗證用戶注冊信息DSC(IDk).驗證通過后，SC將SigPRu(ID)、用戶身份標(biāo)識ID、以及用戶私鑰PRu一起進(jìn)行加密，初步生成用戶位置請求消息DSC(IDk‖SigPRu(ID)‖PRu).

3)LBS服務(wù)器安全驗證：LBS服務(wù)器接收到DSC(IDk‖SigPRu(ID)‖PRu)后，使用PKu對請求信息進(jìn)行驗證，驗證通過后對位置信息解密，查詢求精形成用戶POI信息.LBS結(jié)合PKu對查詢到的位置信息重新加密生成DSC(IDk‖SigPRu(ID)‖PRu‖PKu)，將該位置信息經(jīng)過M個匿名器發(fā)送給SC，SC根據(jù)用戶查詢路徑，規(guī)劃緩存區(qū)并發(fā)送給用戶.

4.2 用戶移動端緩存查詢

用戶所在地理區(qū)域進(jìn)行網(wǎng)格劃分.用戶緩存區(qū)定義為：

buffer←((locx1，locy1)，(locx2，locy2)，Gs，S)

(7)

(colummx，rowy)=([locxi-locx1]，[locyi-locy1])

(8)

其中：

(1≤i≤m，locx2-locx1≤

locxi-locx1，locy2-locy1≤locyi-locy1)

(9)

根據(jù)定義2，用戶查詢半徑R應(yīng)滿足minr≤R≤maxr，并確定用戶端緩存查詢應(yīng)局限在S區(qū)域范圍內(nèi)，查詢的網(wǎng)格標(biāo)識區(qū)限制在Gs地理區(qū)域內(nèi)，如果能夠找到對應(yīng)的(colummx，rowy)包含緩存區(qū)S，且滿足：

S≤columnx×rowy≤Gs，

(10)

則直接對候選結(jié)果集進(jìn)行求精，并得到準(zhǔn)確的用戶緩存區(qū).如果未找到對應(yīng)的緩存區(qū)，對該區(qū)域的網(wǎng)格標(biāo)識區(qū)形成查詢集LOCh.

LOCh←{(columnx，rowy)}

1≤x≤m，1≤y≤m，1≤h≤σ

(11)

其中σ為移動軌跡緩存區(qū)需要緩存的次數(shù).然后執(zhí)行3.1節(jié)的2)生成用戶位置請求消息DSC(IDk‖SigPRu(ID)‖PRu).位置查詢緩存區(qū)最后需經(jīng)SC重新規(guī)劃.一旦緩存區(qū)不滿足式(9)，需要重新查詢緩存區(qū)，根據(jù)定義3，分別將緩存區(qū)S、DSC(IDk‖SigPRu(ID)‖PRu)分別代入|Ecache|和|Eserver|，并根據(jù)式(3)可以判斷用戶緩存區(qū)查詢精度.

4.3 多匿名器位置匿名

(12)

通過隨機轉(zhuǎn)發(fā)機制將DLoc分為M份，每份都附帶有用戶唯一標(biāo)識ID、當(dāng)前位置信息等.隨機形成的M份子信息為：{(IDk1，DLoc1)，(IDk2，DLoc2)，…，(IDkM，DLocM)}.

根據(jù)定義6可知當(dāng)Q越小，匿名度越高隱私保密程度越高.

4.4 LBS服務(wù)器位置信息加密與查詢

4.4.1 數(shù)據(jù)庫位置信息加密

用戶所查詢的POI信息以明文的形式保存在LBS數(shù)據(jù)庫中，為了保護(hù)LBS數(shù)據(jù)庫的數(shù)據(jù)安全，使用CPDA算法對數(shù)據(jù)庫中位置信息進(jìn)行保護(hù).根據(jù)定義7，前綴樹的節(jié)點record用來保存位置信息，葉子節(jié)點children用來表示路徑拐點位置信息.位置信息經(jīng)過加密處理生成密文，具有不可閱讀性，防止攻擊者非法入侵?jǐn)?shù)據(jù)庫獲取位置信息.當(dāng)用戶需要查詢位置信息時又可以將密文經(jīng)過解密處理，還原成明文.

數(shù)據(jù)在轉(zhuǎn)發(fā)前各節(jié)點需要對信息進(jìn)行交換，節(jié)點A可表示為：

(13)

(14)

(15)

節(jié)點B和C將交換后的數(shù)據(jù)發(fā)給A，節(jié)點A構(gòu)造一個滿秩的方程組ψ=G-1F，且：

F=[FA，F(xiàn)B，F(xiàn)C]

(16)

節(jié)點A包含所有的x，y，z和FA，F(xiàn)B，F(xiàn)C的值，經(jīng)過上述公式的計算，得到加密位置數(shù)據(jù)信息，加密密文為(a+b+c).最后該加密軌跡匯總到數(shù)據(jù)庫等待LBS服務(wù)器后續(xù)位置信息解密和查詢.該算法在保證一定精確度的情況下，阻止外部節(jié)點竊取隱私信息.

4.4.2 位置信息查詢

為了提高用戶POI查詢精度和效率，本文引入最優(yōu)二叉搜索樹算法進(jìn)行搜索位置信息，根據(jù)定義8，path={L1，L2，…，Ln}，表示有序集path的二叉搜索樹利用二叉樹的節(jié)點來存儲有序集中的軌跡節(jié)點.在表示Path的二叉搜索樹中搜索一個興趣點POI時返回的結(jié)果有兩種形式：

1)在二叉搜索樹的內(nèi)節(jié)點中找到L=Li；

2)在二叉搜索樹的葉節(jié)點中確定L∈(Li，Li+1).

設(shè)在第1種情形中找到元素L=Li的概率為bi；在第2種情形中確定L∈(Li，Li+1)的概率為ai.其中約定L0=-∞，Ln+1=+∞所以：

ai≥0，0≤i≤n；bj≥0，1≤j≤n；

(17)

(a0，b1，a1，…，bn，an)為軌跡path的存取概率分布.

在表示Path路徑的二叉搜索樹Tree中，設(shè)存儲位置興趣點Li的終點深度為ci；葉節(jié)點(Lj，Lj+1)的節(jié)點深度為dj則：

(18)

式(18)表示在二叉搜索樹Tree中進(jìn)行一次搜索所需的平均比較次數(shù).P為Tree中的平均路長，一般情況下，不同的二叉搜索樹的P是不相同的.

最優(yōu)二叉搜索樹對于有序集Path及其存取概率分布(a0，b1，a1，…，bn，an)，在所有軌跡中根據(jù)用戶提供的興趣點POI，在所有有序集Path中能找到具有最小平均路長的軌跡.該方法能有效提升LBS服務(wù)器查詢效率.

LBS服務(wù)器查詢到對應(yīng)的用戶POI，服務(wù)器通過公鑰PKu對查詢到的位置信息進(jìn)行區(qū)域規(guī)劃并加密，形成用戶移動軌跡預(yù)測點UPath：

UPath=DSC(IDk‖QmPRu(ID)‖PRu‖PKu‖Path)

(19)

另外LBS服務(wù)器根據(jù)UPath查詢附近的興趣點網(wǎng)格集ρGrids并用匿名器公鑰PKu進(jìn)行加密形成候選結(jié)果集LOCbuffer：

LOCbuffer←{ρGrids‖PKu}

(20)

4.5 用戶獲得查詢結(jié)果

用戶查詢POIs搜索算法如算法1所示：

算法1.用戶查詢POIs搜索算法：

輸入：{(IDk1，DLoc1)，(IDk2，DLoc2)，…(IDkM，DLocM)}

輸出：用戶興趣點POIs

1.for eachni≤M，{(IDk1，DLoc1)，(IDk2，DLoc2)，…(IDkM，DLocM)}∈DLoc；

2.for(S1，S2，…，SM)to(A1，A2，…，AM)；

3.definitionPath=(L1，L2，…，Ln)；

4.if(a0，b2，a1…，bn，an)為軌跡Path的存取概率分布；

5.search nodeUPathand searchLOCbuffer；

6.for update buffer to SC；

7.end forLOCh←{(colummx，rowy)}；

8.forUPathandLOCbufferto user；

9.user for thePRutoUPath；

10.Orientationpathfor user；

11.user getbuffer；

12.ifbufferbeyond equation(9)return to 1.

5 安全性分析

本節(jié)主要分析PTPM針對強攻擊者和弱攻擊者的抵御能力，并將多匿名器和LBS服務(wù)器視為強攻擊者，竊聽者視為弱攻擊者[20，21].

5.1 強攻擊模型與弱攻擊模型

1)強攻擊者攻擊模型

在PTPM中，強攻擊者可以從獲取的部分特定信息中推測出用戶的其他信息，在PTPM中多匿名器、LBS服務(wù)器可視為強攻擊者，如LBS數(shù)據(jù)庫因為某種原因?qū)⒂脩裘舾行畔⑿孤督o攻擊者；匿名器在用戶位置信息轉(zhuǎn)發(fā)過程中對用戶敏感信息進(jìn)行分析，造成用戶位置信息泄露等情況.

2)弱攻擊者攻擊模型

在弱攻擊者攻擊模型中，惡意攻擊者對用戶個人信息掌握有限.在PTPM模型中弱攻擊通過竊聽用戶查詢信息，并利用相關(guān)背景知識對用戶位置信息進(jìn)行分析，進(jìn)而推斷獲取用戶的敏感信息.

5.2 抵御強攻擊者的連續(xù)查詢攻擊

用戶在第一次查詢位置信息時因為用戶端沒有緩存區(qū)，所以用戶需要發(fā)送查詢，查詢信息通過SC安全驗證后，利用多匿名器匿名再轉(zhuǎn)發(fā)給LBS服務(wù)器進(jìn)行查詢，LBS服務(wù)器收到的查詢匿名域中至少包含k個用戶，強攻擊者能準(zhǔn)確定位指定用戶的概率只有1/k.

在用戶軌跡的后續(xù)查詢過程中，用戶可以通過查詢緩存區(qū)直接得到查詢結(jié)果，此時用戶不需要與LBS服務(wù)器和多匿名器進(jìn)行交互，因此在此期間強攻擊者將不能獲得用戶任何信息.所以PTPM能抵御強攻擊者的連續(xù)查詢攻擊.

5.3 抵御匿名器的攻擊

多匿名器主要負(fù)責(zé)對用戶位置信息進(jìn)行匿名和轉(zhuǎn)發(fā)，在PTPM方法中用戶位置信息被隨機分割為多份，并隨機通過多匿名器進(jìn)行轉(zhuǎn)發(fā).單個匿名器試圖推斷用戶位置信息時，由于僅僅獲取的是部分位置信息片段，所以無法獲取用戶準(zhǔn)確位置信息.即使多個匿名器共謀，由于用戶位置信息片段中含有標(biāo)識ID和位置加密措施，沒有用戶的私鑰是無法獲取用戶當(dāng)前位置信息的.

5.4 抵御LBS服務(wù)器的攻擊

LBS服務(wù)器管理用戶的查詢數(shù)據(jù)，在PTPM方法中用戶可以直接從緩存區(qū)獲取位置信息，在該過程中LBS服務(wù)器將無法獲取用戶的位置信息.另外在LBS數(shù)據(jù)庫中通過CPDA算法對位置信息進(jìn)行加密處理，LBS服務(wù)器需要公私鑰配對才能查詢用戶的興趣點，在用戶多次查詢過程中由于匿名區(qū)的存在，LBS服務(wù)器很難將用戶多次的查詢結(jié)果進(jìn)行匹配獲取用戶的軌跡信息.

5.5 抵御竊聽者的攻擊

用戶發(fā)送位置查詢信息通過SC加密后發(fā)送給匿名器，包括用戶簽名SigPRu(ID)、加密位置信息DSC(IDk‖SigPRu(ID)‖PRu)以及SC發(fā)布的安全證書等，這些信息中，由于私鑰掌握在用戶手中，且弱攻擊者掌握用戶信息有限，所以弱攻擊者無法得到用戶的精確位置.在多匿名器中位置信息被分為多份，弱攻擊者通過某些途徑得到部分片段也不能恢復(fù)用戶的精確位置信息.在LBS服務(wù)器端使用前綴樹將位置信息加密為密文，并利用最優(yōu)二叉樹算法進(jìn)行查詢，整個過程都需要公私鑰配對才能解密位置信息.弱攻擊者沒有對應(yīng)公鑰也將無法獲得用戶的查詢信息.

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

6.1 實驗數(shù)據(jù)及環(huán)境

本部分通過實驗驗證PTPM的實用性.本次實驗中的數(shù)據(jù)集來自Thomas Brinkhoff移動用戶軌跡生成器，使用德國奧爾登堡市交通網(wǎng)絡(luò)圖.實驗隨機生成10000個移動對象.實驗選取JERRY的移動軌跡作為實驗對象.多匿名器數(shù)量M=10～50個，表1為實驗參數(shù).實驗通過Java編程實現(xiàn)，搭載Eclipse平臺.實驗環(huán)境為：Intel(R)Core(TM)i7-9750H CPU @2.6GHz，8.00GB內(nèi)存，Microsoft Windows 10操作系統(tǒng).

表1 實驗參數(shù)設(shè)置

實驗中移動交通網(wǎng)絡(luò)圖上生成的移動用戶分布情況如圖2所示.

圖2 實驗對象JERRY移動軌跡

實驗中選取移動用戶JERRY來測試安全模型的系統(tǒng)性能，包括緩存區(qū)的測試和安全性測試.圖2(a)、圖2(b)、圖2(c)分別為JERRY 3個時刻的位置查詢情況.

6.2 實驗參數(shù)變化對PTPM的影響

本節(jié)在實驗測試過程中改變緩存區(qū)半徑R、匿名度K、匿名器數(shù)量M和興趣點POIs等參數(shù)，分析對PTPM性能的影響.

如圖3所示，在R=1，POIs=10000時，通過改變匿名度K和匿名器數(shù)量M測試對PTPM性能的影響.由圖3可知系統(tǒng)時間開銷和通信開銷都隨著M和K值的增大而增大.M越大表示匿名器轉(zhuǎn)發(fā)的子信息越多，需要更多的匿名器轉(zhuǎn)發(fā)更多的數(shù)據(jù)，LBS服務(wù)器接收和查詢位置所需的時間和通信量就越大.另外K值越大匿名域就越大，匿名域內(nèi)包含的匿名用戶就越多，相應(yīng)的用戶通信量變大，系統(tǒng)需要更多的時間來處理用戶發(fā)送的位置信息.因此M或K越大，系統(tǒng)所需的時間開銷和通信開銷就越大.

圖3 匿名度及匿名器數(shù)量對PTPM性能的影響

如圖4所示，在M=20，POIs=10000時，通過改變緩存區(qū)半徑R和匿名度K測試對PTPM性能的影響.由圖4可知系統(tǒng)時間開銷和通信開銷都隨著R值和K值的增大而增大.因為R越大，用戶緩存區(qū)的用戶數(shù)量就越多，相應(yīng)的發(fā)送位置查詢信息就越多，所以LBS服務(wù)器需要查詢的POIs就越多，系統(tǒng)需要更多的時間來處理和求精位置數(shù)據(jù)，相應(yīng)的時間和通信開銷就越大.另外K值越大匿名域就越大，匿名域內(nèi)包含的匿名用戶就越多，相應(yīng)的用戶通信量變大，系統(tǒng)需要更多的時間來處理用戶發(fā)送的位置信息.因此，R值或K值越大，系統(tǒng)所需的時間開銷和通信開銷就越大.

圖4 緩存區(qū)半徑及匿名度對PTPM性能的影響

如圖5所示，在R=1，M=20時，通過改變興趣點POIs值和匿名度K值來測試對PTPM性能的影響.由圖5可知系統(tǒng)時間開銷和通信開銷都隨著POIs值和K值的增大而增大.在用戶查詢范圍內(nèi)發(fā)送給LBS服務(wù)器的POIs越多，LBS服務(wù)器需要花費更多的時間來求精用戶的查詢興趣點，因此系統(tǒng)時間開銷越大.另外POIs越多在系統(tǒng)傳輸數(shù)據(jù)過程中，從LBS服務(wù)器到匿名器再到用戶相應(yīng)的通信開銷也越大.另外K值越大匿名域就越大，匿名域內(nèi)包含的匿名用戶就越多，相應(yīng)的用戶通信量變大，系統(tǒng)需要更多的時間來處理用戶發(fā)送的位置信息.因此，POIs或K越大，系統(tǒng)所需的時間開銷和通信開銷就越大.

圖5 POIs及匿名度對PTPM性能的影響

6.3 LBS服務(wù)器安全性和查詢效率對比

由于LBS服務(wù)器中引入了前綴樹的概念，所以這里測試PTPM中的服務(wù)器與傳統(tǒng)LBS服務(wù)器進(jìn)行對比，通過更改測試數(shù)據(jù)中的查詢點數(shù)量n，在僅使用一個匿名器的情況下，對比測試服務(wù)器查詢用戶查詢點所花費的系統(tǒng)時間.根據(jù)圖6(a)可知該PTPM中的服務(wù)器查詢效率是要優(yōu)于傳統(tǒng)服務(wù)器的，主要原因是因為PTPM中LBS服務(wù)器利用最優(yōu)二叉樹算法能最快且精確的找到最短的路徑軌跡.

通過對PTPM中LBS服務(wù)器和傳統(tǒng)LBS服務(wù)器進(jìn)行位置查詢來測試保護(hù)程度，測試過程中人為模擬強攻擊者攻擊模型.在僅使用一個匿名器的情況下更改用戶查詢點數(shù)量n，測試使用同一條軌跡路徑.由圖6(b)分析，由于PTPM中LBS服務(wù)器包含公鑰PKu，并且LBS數(shù)據(jù)庫對位置信息進(jìn)行CPDA加密保護(hù)，所以PTPM中LBS服務(wù)器安全性要優(yōu)于傳統(tǒng)LBS服務(wù)器.

圖6 LBS服務(wù)器查詢效率與安全性對比

6.4 多匿名器與單匿名器性能對比

如圖7所示，實驗使用同一組數(shù)據(jù)測試多匿名器和單匿名器在轉(zhuǎn)發(fā)數(shù)據(jù)時的系統(tǒng)時間開銷對比，使用同一個用戶請求發(fā)送同樣的興趣點，測試數(shù)據(jù)經(jīng)過多次測試取平均值.測試過程改變匿名度K來對比系統(tǒng)響應(yīng)速度.

圖7 多匿名器和單匿名器性能對比

測試數(shù)據(jù)在測試之初不使用SC進(jìn)行安全加密，在多匿名器的性能測試中，M個匿名器同時處理用戶發(fā)送的位置信息，并且多匿名器轉(zhuǎn)發(fā)的是用戶分割的子信息，在每個匿名器中單獨對子信息片段進(jìn)行K匿名和轉(zhuǎn)發(fā).相較于多匿名器，單個匿名器接收的是用戶發(fā)送的整個數(shù)據(jù)信息，在數(shù)據(jù)轉(zhuǎn)發(fā)過程中需要進(jìn)行K匿名，信息轉(zhuǎn)發(fā)靈活性不足易造成性能瓶頸，特別是當(dāng)轉(zhuǎn)發(fā)信息較多時容易產(chǎn)生延遲和擁堵.所以該PTPM中的多匿名器相較于傳統(tǒng)的單匿名器在數(shù)據(jù)轉(zhuǎn)發(fā)效率上有較大提升.

7 結(jié)束語

在軌跡隱私保護(hù)中，本文提出了一種軌跡隱私保護(hù)方法PTPM，通過在用戶移動端增加緩存區(qū)來減少和LBS服務(wù)器的信息交互，降低用戶位置隱私暴露的風(fēng)險，同時提升了用戶位置查詢效率.在用戶和LBS服務(wù)器之間布置安全中心SC來獲取用戶的驗證信息，并產(chǎn)生公鑰和私鑰，通過配對來解密用戶的位置請求信息.安全性分析可知PTPM可有效阻止弱攻擊者監(jiān)聽用戶隱私信息.另外多匿名器通過k匿名對用戶位置信息進(jìn)行保護(hù)的同時，解決了單匿名器存在的安全隱患和性能不足問題.由于多匿名器對用戶進(jìn)行并發(fā)式k匿名，能有效抵制匿名器、服務(wù)器監(jiān)聽和竊聽者的攻擊.LBS服務(wù)器中引入前綴樹的概念，使用CPDA算法對數(shù)據(jù)庫位置信息進(jìn)行明文加密，并通過最優(yōu)二叉樹算法查詢位置信息.通過實驗驗證，該PTPM能有效提升用戶位置查詢效率并增強了用戶位置隱私的保護(hù)程度.由于該PTPM中增加了SC和多個匿名器，增加了系統(tǒng)維護(hù)難度，因此下一步的做法是優(yōu)化安全算法，將安全中心算法移植到匿名器中.