對等通信輔助下抗攻擊的位置隱私保護方法

孫丹丹，羅永龍，范國婷，郭良敏 ，鄭孝遙

SUN Dandan1，2,LUO Yonglong1，2,FAN Guoting1，2,GUO Liangmin1，2,ZHENG Xiaoyao1，2

1.安徽師范大學 計算機科學與技術系，安徽 蕪湖 241003

2.安徽師范大學 網絡與信息安全工程技術研究中心，安徽 蕪湖 241003

1.Department of Computer Science and Technology,Anhui Normal University,Wuhu,Anhui 241003,China

2.Engineering Technology Research Center of Network and Information Security,Anhui Normal University,Wuhu,Anhui 241003,China

1 引言

移動通信的通訊質量不斷提高以及移動定位技術越來越精確，使得基于位置的服務（Location-Based Service，LBS）得到高速發展。移動用戶只需提供自身準確、實時的位置信息給位置服務器，便可獲得相關服務，例如：查找離我最近的餐廳、休閑場所、購物場所等。然而盲目地發送位置信息給服務器必然會造成自身信息的泄露，將給用戶帶來巨大的風險。因此，位置隱私保護越來越受到人們的重視。

在位置隱私保護研究領域中，Gruteser等[1]首先引入k-匿名模型：通過搜索查詢用戶周邊的k-1個相互之間不能區別的用戶，用覆蓋它們的匿名區域代替查詢用戶真實的位置，即使發送的位置信息被攻擊者獲取，也不能準確地從k個用戶中定位到該用戶，從而達到保護真實用戶位置隱私的目的。現有很多方法都是以k-匿名為基礎。

多數研究通常采用第三方中心服務器架構[2-4]，但作為核心的位置匿名服務器容易成為受攻擊的對象，且該架構還存在如下不足：（1）需通過大量用戶的注冊使用，才能實現匿名區域的構建，并且要求注冊用戶誠實可信；（2）僅支持靜態快照定位；（3）匿名服務器承擔生成匿名區和過濾結果集的工作，若大量用戶頻繁請求查詢，必然導致計算量急劇上升，造成系統瓶頸，限制了位置服務更好的發展。

針對中心服務器存在的上述不足，諸多研究者開始采用無中心服務器的結構。文獻[5]首先提出一種分布式算法，但效率并不高；Chow等[6]率先提出P2P模式下使用匿名算法的思想，通過對等點查詢算法構建匿名區域。用戶自組織通信形成用戶組，然后計算組內最小邊界矩形，查詢節點隨機選取組內成員作為代理，由代理代替查詢節點發起查詢，最后返回結果。但Chow在匿名組選擇成員時沒有考慮用戶的移動性，且往往導致查詢節點位于匿名區中心處，導致區域中心攻擊。文獻[7]對文獻[6]作了改進，通過隨機擴大匿名區來避免匿名區中心攻擊，但仍存在查詢節點分布不隨機等問題。Pingley等[8]提出一種不需要可信第三方的方法，該方法避免攻擊者從查詢內容中推斷用戶的興趣和習慣。

另外，傳統方法由于使用匿名區域易受攻擊[9]，因此部分研究不再使用匿名區域。Yiu等[10]提出了SpaceT-wist方法，用戶使用錨點代替自身真實位置向服務器發起增量近鄰查詢，直至供應空間包含需求空間為止。但該方法無法達到位置k-匿名，隱私保護度不高。Gong等[11]在文獻[10]基礎上提出了一種改進算法，能達到k-匿名，但使用了中心服務器。黃毅等[12]提出了一種用戶協作無匿名區域的CoPrivacy方法，通過用戶協作形成匿名組，組內用戶用該組的密度中心代替真實位置，增量地從服務器獲得近鄰查詢結果，再通過近鄰查詢結果與自身位置之間的距離計算得到精確的查詢結果。但該方法要求周邊用戶全部誠實可信，無法防止惡意攻擊者冒充用戶節點發起攻擊的情況。張國平等[13]使用了代理轉發查詢的方法，避免了用戶隱私在服務器端泄露，但無法避免攻擊者偽裝成代理用戶獲取用戶隱私；楊松濤等[14]提出了一種位置隱私保護模型并設計了一種基于偽隨機置換的位置隱私保護方案，實現了完美匿名和位置盲查詢，但無法抵抗惡意節點的主動攻擊；徐建等[15]提出了在動態P2P環境下基于匿名鏈的位置隱私保護算法，但不能有效抵御連續查詢攻擊[16-17]。以上基于用戶協作的方法通常無法抵御不誠實用戶的攻擊行為。近年來，還出現了基于私有信息檢索的位置隱私保護方法[18-20]，雖然隱私保護度較高且可避免多種攻擊，但此類方法預計算開銷和運行時計算開銷比較大，還無法廣泛應用。

綜合上述問題，本文提出一種對等通信輔助下抗攻擊的位置隱私保護方法（以下簡稱P2P AG算法）。該方法不使用中心服務器，未生成匿名區域，解決P2P結構中用戶不誠實協作問題。它在k-匿名思想的基礎上使用構建匿名組的方式混淆身份信息與位置信息的對應關系，以此隱藏用戶身份與位置信息的關聯性，達到隱私保護的目的；將速度引入匿名組的構建，并通過緩存機制增加匿名組的可重用性，以此抵御一般惡意攻擊和連續查詢攻擊，且減少系統開銷。

2 P2P AG位置隱私保護方法

2.1 相關定義

定義1（速度夾角θ）兩個移動節點的當前速度矢量所形成的夾角（規定大小為0的速度矢量以其所在道路方向為速度方向），如圖1所示，n1和n2是兩個移動節點，速度分別為V1、V2，則當前的速度夾角θ為：

圖1 速度夾角

定義2（速度分類）指以速度為標準的分類方法，具體而言，以查詢用戶的速度方向為中心軸，周邊區域邊界夾角為90°的區域范圍為移動用戶的類別，速度方向與查詢用戶速度方向的夾角在這個范圍內的節點均為查詢用戶的同類節點，如圖2所示。

圖2 速度分類

定義3（節點Node）在一定范圍內的移動用戶，可用數據結構Node(IP,Loc,vec,k,List,Lt,t0,v)加以表示，其中：

IP為節點唯一的身份標識；

Loc表示當前位置坐標；

vec為當前速度，由節點自身設定一個時間片不停更新；

k為節點要求的匿名度，即匿名組內節點的個數，由節點決定，顯然k越大，匿名組內成員個數越多，隱私保護程度越高[21]；

List為緩存內周邊節點的信息表，包含周邊k-1個節點的信息，該信息包括序號、位置坐標以及速度，初始為空；

Lt表示匿名組的生存時間，超過這個時間段，緩存內的List將不能再被使用；

t0表示記錄下來的上一次構建List表時的時間點；

v表示記錄下來的上一次構建List表時的節點速度。

定義4（查詢節點）查詢節點q指發起位置查詢服務請求的移動節點。

定義5（代理節點）代理節點a指代替查詢節點向位置服務提供商發出查詢請求、并將返回的結果集返回給查詢節點的節點，它是查詢節點從產生的匿名組中隨機選擇出的一個節點。

定義6（組內節點）組內節點I指除查詢節點、代理節點以外的匿名組內節點。

定義7（偽代理節點）偽代理節點w由于查詢節點q在匿名組中選中的代理節點a可能是其他周邊節點p的List表中的節點，查詢節點q無法與這類節點（即a）建立通信連接，所以選擇List表中含a的這個周邊節點p作為偽代理節點，由它承擔代理節點a的任務。

定義8（匿名組）匿名組ano_group指一個由查詢節點、代理節點（或偽代理節點）、若干組內節點組成的節點集合。可形式化地表示為：

ano_group(q,a,I1,I2,…,In)，q為查詢節點，a為代理節點，Ii為第i個組內節點。

定義9構建匿名組的請求信息Req查詢節點廣播至周邊節點的信息，用以請求協助構建匿名組，可形式化地表示為Req(RID,vec,min)，其中RID為請求序列號，是由節點唯一身份標識IP和自身當前請求信息的序號數N（指第N次請求）確定；vec為當前查詢節點的速度；min為請求回復信息數，初始時為1。

定義10查詢信息Query代理節點（或偽代理節點）代替查詢節點向位置服務器發送的查詢信息，可形式化地表示為Query(ano_group,Q_Info)，其中Q_Info為查詢節點輸入的查詢內容。

定義11（位置更新）當緩存中的List可用時，查詢節點使用該List中各個節點的歷史位置信息和速度估算當前的位置信息，并構成匿名組，如圖3所示，將當前所有節點的新位置坐標近似表示為List內歷史位置坐標加上其速度和時間差的乘積的和，即：

圖3 位置的近似估算

其中L1(x,y)為某節點歷史位置坐標，V為該節點的速度，t為當前時間，t0為List創建時間。

定義12（結果集）結果集R指位置服務器返回給代理節點（或偽代理節點）的查詢結果，對應ano_group內k個節點的位置，即生成的k個結果。

2.2 系統框架

本文采用的系統結構如圖4所示，由兩個部分組成，即位置服務器和移動節點。位置服務器是提供位置服務的服務器，要求有計算功能，可完成大量的定位、查詢并返回結果。移動節點是具備定位、計算功能的移動設備。系統主體主要包括兩個模塊：通信模塊及查詢模塊。

圖4 系統框架

在通信模塊中，每個移動節點需要支持兩種通信方式，一種用于與位置服務提供商之間的通信，包括發起查詢及獲得查詢結果，可使用2G、3G或4G網絡；另一種用于用戶之間進行自組織的P2P通信，可采用無線局域網（WLAN），例如IEEE 802.11等方式實現[22-23]。顯然，無線局域網覆蓋范圍越廣，可搜索到的節點就越多，匿名成功率越高，匿名效果越好。

在查詢模塊中，移動節點被分為三類：查詢節點、組內節點和代理節點（或偽代理節點）。首先，查詢節點q構建匿名組，利用匿名組內節點的位置來隱匿q的真實位置，以此實現k-匿名；然后由q從匿名組中選出代理節點（或偽代理節點）A，并將匿名組和查詢信息發給A，由A向位置服務器完成查詢；最后當A從位置服務器獲得結果集R后，會將R返回給q，q通過R獲得自己所需要的信息。

2.3 查詢過程

移動節點請求一次位置服務就是一次查詢過程，包括發起請求、響應階段、匿名處理和查詢處理4個步驟。

步驟1發起請求

當查詢節點q需要請求位置服務時，首先查看自身緩存內的List表是否可用，即檢查如下兩個條件：（1）當前系統時間與上一次參與匿名的時間差t是否小于其自身規定的緩存生存時間；（2）當前節點速度vec與上一次匿名時記錄下的節點速度v的類別是否一致（可用classify()函數進行判斷，若返回1，表示速度一致，否則表示速度不一致），然后根據檢查結果分為以下兩種情況進行處理：

（1）q.Lt≥t-t0and classify(q.vec,q.v)==1，此時直接調用自身List表并進行處理（見算法1中第3～6行）。由于此時List表內各個節點的新位置未知，且考慮多數節點是移動的，因此需要計算出各個節點的近似位置來代替新位置，即位置更新（見定義11）。處理完所有的節點后，節點q將自身位置信息隱匿于上述節點的位置信息中，構成一個包含k個節點的匿名組，并直接轉向步驟4。

對于List表的生存時間，節點可自行規定它的大小：生存時間越短，新位置估算的越精確，越符合實際情況，但可重復使用的次數越少，再次搜索及構建的可能性增大，增加系統的負荷；生存時間越長，使用List表越多，可減少搜索及構建的次數，減輕運算負載。由于節點移動方向的不確定性，計算所得的新位置可能與真實位置存在少許偏差，會使真實位置模糊化，可更好地保護匿名組內用戶的真實位置，但生存時間不可過長，否則也會導致與實際情況差別太大，可能使部分估算的位置信息不合理，降低隱私保護度[24]。

（2）q.Lt＜t-t0or classify(q.vec,q.v)!=1，此時需要重新構建匿名組（見算法1中第5～11行）。首先，節點q清空List、初始化構建請求信息Req(RID,vec,min)，并廣播Req，然后等待周邊節點的回應，接收到Req的合適節點最終將返回響應，（響應階段處理過程具體見步驟2），搜索過程結束。

算法1描述了查詢節點請求構建匿名組時的初始處理過程，具體如下：

算法1 Initial processing of query node

步驟2響應階段

當周邊節點 p收到查詢節點q發送的構建請求消息時，它檢查此請求是否為新的請求，若不是新請求，則拋棄該消息，否則，繼續檢查速度類別，若q的類別與 p的類別不一致，則拋棄，否則就檢查q.Req.min的值，根據q.Req.min的值來返回響應結果（一般情況下，節點 p首先是為了滿足自身查詢需求而開啟位置服務，因此p.List通常不會為空），響應結果用于查詢節點構建匿名組：

當q.Req.min==1時，節點 p將隨機抽取 p.List內的一條節點信息，即 p.List內某個節點 p′的速度及位置信息（見算法2第4～6行），然后返回給q；

當q.Req.min!=1，則從 p.List中隨機抽取 Minist(number(p.List),q.Req.min)（表示 p.List中的節點數值和q.Req.min值相比較，返回最小值）條節點信息，返回給q（見算法2第7～14行）。算法2描述了在構建匿名組時，構建請求信息接收端的處理過程，具體如下：

算法2 Response of receiver

步驟3匿名處理

當返回的節點信息總數不小于k-1時，查詢節點q便可從中隨機挑選k-1個節點作為匿名組的成員，并將自身信息隱匿其中，形成一個有k個節點的匿名組，并存入List中，其中保存了所有組內節點的位置信息和速度。若返回響應的節點總數小于k-1，說明一次單跳搜索無法滿足查詢節點q的匿名需求。此時節點q將修改Req中的min值：

其中，q.k為查詢節點q的匿名度，k'為首次請求返回的節點個數，并再次向周邊節點發出構建請求，以此獲得更多周邊節點List表中的節點信息來完成此次匿名。若再次返回的節點信息數目仍不足k-1，說明當前周邊節點過少，構建匿名組失敗，這時節點q需要等待一段時間，待網絡覆蓋范圍內的節點數增多時再重新構建。為防止惡意攻擊，查詢節點q將List做了如下處理：表內不使用移動節點的真實IP，而是使用編號用以標識區分，這樣即使該表被惡意攻擊者截獲，由于表內采用的編號標識使其無法準確定位到某個用戶，為保持通信，查詢節點q還需保留組內節點的通信地址與編號的對應關系。構建ano_group時，為了防止將q暴露于表頭或表尾，節點的順序是隨機打亂的，如表1所示。

表1 構建完成的匿名組

算法3描述了構建過程中節點q的匿名處理過程：

算法3 Anonymity Processing

步驟4查詢處理

經過步驟3后，ano_group已經構成。為防止被惡意攻擊者追蹤定位，查詢節點不直接發起查詢，而是在ano_group內隨機挑選一個節點作代理節點，由代理節點實現轉發查詢。不失一般性，查詢節點自身也有可能會被選中，因而，在排除自身節點的集合中隨機選擇代理節點。另外，由于被選中的代理節點可能是周邊節點pi(i=1,2,…,n)中List表中存儲的節點，而它可能沒有與查詢節點q建立通信連接，此時，依據定義7，用偽代理節點轉發查詢請求，也就是說偽代理節點可能未被歸入匿名組內，但是充當了代理節點的角色。查詢節點將ano_group和Q_Info發送給代理節點（或偽代理節點）a，a再將已被匿名化的查詢信息發送給位置服務器。位置服務器接收到查詢信息后經過計算返回一系列結果集。代理節點（或偽代理節點）接收到結果集后將其轉發給查詢節點，查詢節點篩選出所需要的結果，整個查詢過程結束。由上文可知，不論ano_group是通過步驟1直接獲得、還是經過步驟2及步驟3重新構建的，查詢用戶得到的都是準確的結果。

2.4 算法復雜度及服務質量分析

移動客戶端計算能力有限，因此算法不能過于復雜。而直接在查詢端生成一組假位置的方法將導致大量的計算開銷，且生成的假位置可能受語義攻擊[24]，因此利用多個真實的接收端協作完成匿名，且使用的是其List表內更接近真實情況的位置信息，以避免語義攻擊帶來的危害。在整個過程中，發起查詢的節點需要選擇多個其他節點信息以構成包含k個成員的匿名組，因此查詢端的時間復雜度為O()k，k為查詢端指定的匿名度；其他節點接收消息，經選擇后發出消息，因此接收端的時間復雜度為O()k*，k*為接收端指定的匿名度。

服務質量方面，本文使用隱匿的位置信息向位置服務器發起查詢。在緩存中已有的List表不可用時，節點是使用當前真實位置進行構建匿名組并查詢，查詢結果是精確的；當緩存中已有的List表可用時，將查詢節點的真實位置混在一系列虛假位置中進行查詢，查詢結果也是精確的，因此，在保護用戶位置隱私的情況下并未犧牲服務質量。

3 實驗及分析

3.1 實驗環境

模擬實驗采用Java實現，在Q9500 2.83 GHz處理器、2 GB內存的Windows 7平臺上運行。移動節點的位置模擬數據由移動數據管理研究業界廣泛使用的Thomas Brinkhoff路網數據生成器[25]生成。取城市Oldenburg的交通路網中一塊1 000 m×1 000 m的空間作為模擬器的輸入，如圖5所示，從而生成模擬的移動節點數據集。

圖5 城市Oldenburg交通路網及節點的仿真

實驗中假設每個移動節點在組內使用半雙工無線通道進行通信，帶寬為2 Mb/s。當某節點發出通信請求時，需要等待其他成員的回應，若響應節點數不足，它將再次發出請求，若多次請求無果且超過節點可容忍的等待時間，則該節點請求失敗。首先使用該模擬器產生1 000個不同節點的運動信息，模擬器各項參數設置如表2所示，為列出的表示為默認值。其中，obj./begin（M）為初始狀態下產生的運動對象數，obj./begin（E）則為外部對象數；obj./time（M）為每個時間戳下產生的移動對象數，obj./time（E）則為外部對象數；classe（sM）為移動對象類的個數，classe（sE）則為外部對象類的個數。

表2 參數設置

3.2 結果分析

規定N為當前無線網覆蓋范圍內的節點總數，n為請求查詢的節點數目，即查詢節點數，k為節點要求的匿名度，緩存生存時間設置為30 s。接下來將從算法性能和安全性兩個方面來評估。

3.2.1 算法性能

本文從匿名成功率、平均響應時間及消息數量三方面分析算法性能，并與文獻[12]的CoPrivacy方法做了一定比較。

（1）匿名成功率

匿名成功率是指在查詢過程中實現成功匿名的節點在發起查詢的節點中所占的比例，計算公式為：匿名成功率=匿名成功節點數/查詢節點數。

圖6是節點總數相同N=1 000，n和k值不同的情況下P2P AG方法的匿名成功率。隨機選擇50～200個節點作為查詢節點，并在隨機的時間戳下發起查詢。查詢分為四類：k=10、20、30和40，每類執行100次后記錄匿名成功的節點數，計算出平均成功率。如圖所示，當k和n越小，匿名成功率越高且越穩定，最佳情況幾乎達到100%，當k和n增大，匿名成功率將有所降低，但整體成功率仍較高。

圖6 基于不同n和k值的匿名成功率（N=1 000）

圖7為k和n相同、N不同時，P2P AG方法與CoPrivacy方法匿名成功率的對比結果。分別產生50～400個節點，隨機定義20個節點發起k=10的查詢，各自模擬10次查詢。從圖中可看出，前者在節點總數較少時，匿名成功率較低，這是由于此時符合構建匿名組條件的節點數較少。節點數越多，匿名成功率就越高，當N=400時，已基本達到100%。對于后者，匿名成功率也是隨節點總數的增加而增加，但并不是很穩定，當請求查詢的次數增加，匿名成功率會降低，特別是節點總數較少時，下降是明顯的，這是因為查詢次數增多時周邊可用的節點會越來越少。而P2P AG方法一直保持著波動不大的匿名成功率，因此比較穩定，且在多數節點同時進行查詢時匿名效果較好，符合實際需求。

（2）平均響應時間及消息數量

圖8是P2P AG方法關于平均響應時間及消息數量與CoPrivacy方法對比的結果。實驗中，設n=20，k=10，節點總數N=50～400。如圖8（a）所示，隨著節點總數增加，CoPrivacy方法的系統響應時間出現較大增長，而P2P AG方法雖有所增加，但較平緩，未出現很大幅度的增長，說明系統是穩定的。從圖8（b）可以看出，隨著節點總數增加，兩者的平均消息數量會逐漸降低。對CoPrivacy方法而言，節點總數增加使其不需要通過多跳搜索其他節點；而對于P2P AG方法，隨著節點總數增加，匿名成功率也會增加，不需要多次廣播構建請求消息，且由于緩存的使用，會減少消息數量。但CoPrivacy方法需要搜索節點且實現增量近鄰查詢，導致大量的通信，因此平均消息數量的總趨勢高于P2P AG方法。

3.2.2 安全性分析

本文主要分析一般惡意攻擊和連續查詢攻擊的情況。攻擊者感興趣的信息是節點與其位置信息的對應關系，即確定某一個節點及其所在的位置，因此需要對節點與位置信息之間的關聯關系進行保護。

（1）一般惡意攻擊

主要考慮兩種一般惡意攻擊：一是惡意節點是匿名組內節點，獲取匿名組信息；二是竊聽者監聽匿名組內的通信或代理節點與LBS服務器之間的通信。

由于構建匿名組時組內節點和代理節點的選擇是隨機的，即使存在惡意節點，其被選中的可能性也很小。若整個區域內的響應節點數為p，匿名度為k(k＜p)，惡意節點數為c（一般情況下，參與構建的用戶都是誠實或半誠實的，因此可假設c?p），則整個過程中查詢節點選中惡意節點的概率為：

圖7 不同節點總數的匿名成功率（n=20，k=10）

圖8 平均響應時間及消息數量（n=20，k=10）

當c遠小于 p時，這個概率值將很小。此外，即使惡意節點是組內節點，它只能獲取查詢節點的速度類別，并不能獲取其位置信息。只有惡意節點是代理節點時，才會獲取一張包括組內節點信息的ano_group。但是，ano_group中的用戶名是使用編號進行隱匿的，即使惡意節點獲得了ano_group，只能得到一系列位置信息和速度信息，是無法將位置信息與某個確定的用戶關聯起來的，即保護了用戶與其位置信息的關聯關系；另一方面，代理節點充當的是查詢節點與位置服務器間的中間件，且每次請求查詢時都會隨機選出一個用來實現轉發查詢，即便知曉誰是查詢節點，但這是在查詢節點進行搜索周邊節點時就已經知曉的，而搜索過程中查詢節點廣播的Req只包括RID、vec和min，并沒有確切的位置信息，因此查詢節點的位置信息并未暴露。

若惡意節點偽裝成查詢節點期望獲得大量其他節點的信息。然而在算法2中，其他節點返回的響應信息是其List內的某一條節點信息，即并不是自身的信息，即使惡意節點偽裝成查詢節點獲取了這些信息，也無法準確判斷與某個節點的對應關系。同理，若竊聽者截獲到查詢節點發送給代理節點的ano_group或代理節點發送至LBS服務器的查詢信息，也是無法將位置信息與確切的用戶IP關聯起來，保護了匿名組內節點的隱私。

通過抵御以上兩類惡意攻擊，P2P AG算法便可避免受到傳統k-匿名方法中的多數攻擊[26]。例如對于區域密度攻擊：當查詢節點周邊的用戶較多時構建的匿名區域較小，導致直接縮小查詢用戶的真實位置范圍，增加了位置暴露的風險。而P2P AG算法構建的匿名組內的位置信息是真實信息和虛假信息的混合，攻擊者并不能有效定位到查詢用戶的真實位置范圍，因此可較好地抵御區域密度攻擊。

（2）連續查詢攻擊

此類攻擊主要由查詢節點在連續查詢周期內匿名集合的頻繁變化引起。一種簡單的解決方案就是保持查詢節點的匿名集合盡可能的不變[27]，然而這會使匿名區域隨集合內成員的分散移動而逐漸增大或減小。若匿名區域過大，則降低了服務質量；若匿名區域過小，則較容易泄露隱私。本文舍棄匿名區域，并使用緩存，使匿名組盡量保持不變。假設緩存中的List生存時間較長，連續的幾次查詢中都將使用同一組節點構成的匿名組，使得攻擊者無法確定真實的查詢節點。為盡可能保證節點不會出現大量的添加、刪除且保持組內通信順暢，將速度分類，組內節點屬于同一個類。由于節點沿著道路移動，短時間內發生類別變化的可能性不大，ano_group將保持不變，當發起連續查詢時，即使攻擊者截獲了ano_group，仍無法準確確定查詢節點及其位置信息。

圖9說明了保持匿名組不變的可行性。實驗中記錄了節點總數N=1 000時在不同的情況下使用緩存所占成功匿名節點數的比例。分別隨機使100、200、300個節點發出匿名度k=20～100的查詢。可以看出：當查詢節點數較多或要求匿名度較大時，使用緩存的可能性較大，因此占比例較大，符合實際應用，可有效滿足隱私需求且節省系統開銷。

圖9 緩存使用率（N=1 000）

由于多數位置隱私保護方法的研究重點各異，因此本文與用戶協作的位置隱私保護經典算法P2P Spatial Cloaking[6]（簡稱P2P SC）做比較。若在多個匿名度為k的匿名集合內連續出現的節點個數為m，則查詢節點被暴露的概率為：

對于P2P SC算法，當某個或某幾個成員在多個匿名區域內連續出現，則說明查詢節點必是該成員或存在于這多個成員中，使算法無法達到位置k-匿名，增大暴露的可能性，即受到連續查詢攻擊的威脅。而P2P AG利用緩存，盡可能使連續構建的匿名組不變，降低了暴露的可能性。實驗使40個節點在連續的多個時間戳t內發出查詢請求，匿名度k=10，匿名組生存時間不小于1個時間戳，記錄節點暴露率，并計算平均值。結果如圖10所示，P2P SC的查詢節點暴露率基本高于P2P AG，且前者隨連續時間戳的增加而大幅增長。考慮到P2P AG會在節點速度類別發生改變時構建新的匿名組，為了模糊新舊匿名組間的聯系，算法將組內的用戶名用編號代替，且隨機產生順序，使攻擊者無法識別出兩次查詢是否為同一個查詢節點發出，即一次構建，多次使用，再次構建，全組更名，以更好地抵御連續查詢攻擊。因此P2P AG方法在連續查詢時的安全性優于P2P SC方法。

圖10 安全性比較（N=1 000，n=40，k=10）

4 結束語

大部分傳統的位置隱私保護方法是基于第三方可信中心服務器結構而建立的，因此必然導致中心服務器成為整個系統性能的瓶頸。本文提出一種在對等通信輔助下可抗攻擊的位置隱私保護方法，該方法通過多用戶協作實現位置k-匿名，未生成匿名區域，避免傳統k-匿名模型常見的攻擊。考慮用戶的移動性，引入速度作為構建匿名組的要素之一，組內成員保持模糊的連通性，以此解決組內成員不可信問題，并可抵御一般惡意攻擊。同時，加入了緩存機制，增加匿名組的可重用性，使匿名組在一段時間內保持不變，以此抵御連續查詢攻擊，并可減少系統開銷。該方法保證了用戶的隱私，在降低系統開銷的基礎上滿足了匿名需求，并能夠較好地抵御一般性惡意攻擊和連續查詢攻擊。由于用戶協作的模式需要建立在用戶相對集中且用戶數多的基礎上，當周圍可搜索到的用戶較少或可協助進行查詢的用戶較少時，該方法的實現將可能會受到一定影響。因此，該方法較適用于用戶相對集中且足夠多的密集區域，未來的工作可以在松散用戶或少量用戶上展開。

參考文獻：

[1]Gruteser M，Grunwald D.Anonymous usage of locationbased services through spatial and temporal cloaking[C]//Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，2003：31-42.

[2]Gedik B，Liu L.Protecting location privacy with personalized k-anonymity：Architecture and algorithms[J].IEEE Transactions on Mobile Computing，2008，7（1）：1-18.

[3]Xu T，Cai Y.Feeling-based location privacy protection for location-based services[C]//ACM Conference on Computer and Communications Security（CCS 2009），Chicago，Illinois，USA，November 2009：348-357.

[4]Wang Y，Xu D，He X，et al.L2P2：Location-aware location privacy protection for location-based services[J].Proceedings-IEEE INFOCOM，2012，131（5）：1996-2004.

[5]Kido H，Yanagisawa Y，Satoh T.An anonymous communication technique using dummies for location-based services[C]//ProceedingsInternationalConferenceon Pervasive Services，2005（ICPS’05），2005：88-97.

[6]Chow C Y.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]//Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems，2006：171-178.

[7]Chow C Y，Mokbel M F，Liu X.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica，2011，15（2）：351-380.

[8]Pingley A，Zhang N，Fu X，et al.Protection of query privacy for continuous location based services[C]//IEEE INFOCOM，2011：1710-1718.

[9]Wernke M，Skvortsov P，Dürr F，et al.A classification of location privacy attacks and approaches[J].Personal and Ubiquitous Computing，2014，18（1）：163-175.

[10]Yiu M L，Jensen C S，Huang X，et al.Spacetwist：Managing the trade-offs among location privacy，query performance，and query accuracy in mobile services[C]//IEEE International Conference on Data Engineering，2008：366-375.

[11]Gong Z，Sun G Z，Xie X.Protecting privacy in locationbased services using K-anonymity without cloaked region[C]//2010 Eleventh International Conference on Mobile Data Management（MDM），2010：366-371.

[12]黃毅，霍崢，孟小峰.CoPrivacy：一種用戶協作無匿名區域的位置隱私保護方法[J].計算機學報，2011，34（10）：1976-1985.

[13]張國平，樊興，唐明，等.面向LBS應用的隱私保護模型[J].華中科技大學學報：自然科學版，2010（9）：45-49.

[14]楊松濤，馬春光，周長利.面向LBS的隱私保護模型及方案[J].通信學報，2014，35（8）：116-124.

[15]徐建，黃孝喜，郭鳴，等.動態P2P網絡中基于匿名鏈的位置隱私保護[J].浙江大學學報：工學版，2012，46（4）：712-718.

[16]Dewri R，Ray I，Whitley D.Query m-invariance：Preventing query disclosures in continuous location-based services[C]//2010 Eleventh International Conference on Mobile Data Management（MDM），2010：95-104.

[17]Chen X，Pang J.Exploring dependency for query privacy protection in location-based services[C]//Proceedings of the Third ACM Conference on Data and Application Security and Privacy，2013：37-48.

[18]Ghinita G，Kalnis P，Khoshgozaran A，et al.Private queries in location based services：Anonymizers are not necessary[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，2008：121-132.

[19]Papadopoulos S，Bakiras S，Papadias D.Nearest neighbor search with strong location privacy[J].PVLDB，2010，3（1）：619-629.

[20]Khoshgozaran A，Shahabi C，Shirani-Mehr H.Location privacy：Going beyond K-anonymity，cloaking and anonymizers[J].Knowledge and Information Systems，2011，26（3）：435-465.

[21]張建明，趙玉娟，江浩斌，等.車輛自組網的位置隱私保護技術研究[J].通信學報，2012（8）：180-189.

[22]Chow C Y，Leong H V，Chan A T S.Distributed groupbased cooperative caching in a mobile broadcast environment[C]//Proceedings of the 6th International Conference on Mobile Data Management，2005：97-106.

[23]Papadopouli M，Schulzrinne H.Effects of power conservation，wireless coverage and cooperation on data dissemination among mobile devices[C]//Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking&Computing，2001：117-127.

[24]Brinkhoff T.A framework for generating network-based moving objects[J].GeoInformatica，2002，6（2）：153-180.

[25]Damiani M L，Bertino E，Silvestri C.The PROBE framework for the personalized cloaking of private locations[J].Transactions on Data Privacy，2010，3（2）：123-148.

[26]司超.基于Casper的位置隱私保護模型與算法研究[D].廣州：華南理工大學，2012.

[27]Chow C Y，Mokbel M F.Enabling private continuous queries for revealed user locations[M]//Advances in Spatial and Temporal Databases.Berlin Heidelberg：Springer，2007：258-275.