一種基于停頓和映射的隱私軌跡混淆策略

唐 禹 吳正華

(電子科技大學信息與軟件工程學院 成都 611731)

近年來，基于位置的服務(LBS)變得越來越普遍，LBS提供商基于用戶的位置提供例如定位、導航、路線規劃、興趣點(POI)搜索、定制化廣告等服務.其可以通過用戶移動設備的GPS定位、蜂窩移動網絡信息、WiFi信息等來獲取用戶定位.一方面，豐富的LBS便利了用戶的生活，但是另一方面，LBS也竊取了用戶的隱私，Fechner的報告[1]顯示攻擊者可能會因為牟利的目的進行一些騷擾行為.根據Busic和Filjar的調查[2]，大多數商業LBS要求我們每隔幾分鐘更新一次定位.當用戶連續使用LBS時情況會愈發嚴重，如果用戶的軌跡被惡意使用，通過數據挖掘[3-5]可以獲取用戶的更多隱私，包括家庭住址、愛好、生活情況、健康狀況、親密關系等.因此軌跡信息的保護得到了廣泛的應用研究，受到國內外學者的關注.

為了保護用戶的位置隱私，目前國內外已有很多研究.Kato等人[6]認為，一個能夠保證用戶位置隱私的系統應該滿足以下2個條件：1)它應該是一個封閉的系統，即能夠在用戶的移動設備上部署，并且不會向外部泄露用戶的位置隱私；2)它不應破壞用戶或LBS提供商的利益.第2個要求對于使整個生態系統受益至關重要.否則，沒有用戶或LBS會使用該系統來保護隱私.但是，前人的研究基本上是基于K-匿名算法，在真實使用中，使用者往往不具備專業知識背景，他們無法為每個LBS構建請求，通常是LBS應用直接向移動設備請求位置信息，這種請求的結果是固定的，即某一個經緯度標識的點，也就無法通過返回給應用多個定位數據，以實現K-匿名算法.

應用在LBS中的位置隱私保護系統架構主要有3類[7]：集中式模型、分布式模型和獨立式模型.其中集中式模型需要有可信的第三方服務器，分布式模型需要用戶進行分布式組網，都需要外部服務或設備的幫助，而獨立式模型的隱私保護皆由用戶設備完成，不干涉外部網絡與服務，也與本文的研究方向最為貼切.

在獨立式模型中的軌跡隱私保護算法主要分為3種：K-匿名軌跡算法、軌跡抑制算法和虛擬軌跡算法.

軌跡抑制算法是選擇性地抑制敏感位置的發布[14]，軌跡抑制法雖然實現簡單，但是卻容易導致數據丟失，降低數據可用性.Weng等人[15]提出一種基于擾動的軌跡數據隱藏發布方法，找到出現頻率低的位置節點來替換出現頻率高或有隱私泄露風險的節點.

虛擬軌跡算法是通過對真實軌跡的處理，得到1條虛擬軌跡，此軌跡在LBS等位置服務和用戶軌跡隱私中取得折中.Duckham等人[16]提出了一種通過混淆的方式在LBS與位置隱私中取得一定平衡的框架.Ardagna提出了3種混淆策略[17]：1)通過擴大其半徑來降低定位區域精準度；2)通過移動其中心來降低定位區域精準度；3)通過減小半徑來降低定位區域精準度.

本文致力于在無第三方可信服務器的情況下獨立保護用戶的位置隱私，同時為使用者提供可用的LBS.本文的方法著重于維護可用LBS和用戶位置隱私之間的平衡，通過一定的混淆策略降低用戶的位置信息質量，以達到保護用戶位置隱私的目的.同時考慮到真實軌跡中存在的停頓現象及工作、住宅等地的固定點存在，在普通混淆策略的基礎上增加了停頓處理和固定點映射策略，使得本文的方法在擬真方面更加優秀.在降低定位精度方面，本文創新性地提出了通過時延來獲取混淆區域中心，在降低定位精準度的同時保證了軌跡的擬真性.

1 本文的隱私保護模型

1.1 條件假設

1.2 度量標準

為了明確在使用混淆算法前后用戶獲得的LBS差異，本文提出通過命中率AR來度量模型對于用戶獲取LBS的影響.命中率AR表示為

(1)

其中，Lr表示真實定位，Lf表示此真實定位對應的虛擬定位，POI(L)表示在定位L處所獲得的LBS興趣點集合，故AR可以用通過虛假軌跡獲取到的興趣點集合中命中真實定位獲取到的興趣點集合的數量與真實定位獲取到的興趣點數量的比值來表示.

為表示所生成軌跡的真實性，本文提出通過判正率CR來度量生成的假軌跡被判斷為真實軌跡的概率.即所有生成軌跡中，被定性判斷為真實軌跡的軌跡條數占生成的所有軌跡條數的比例.

1.3 軌跡生成策略

本文提出的虛擬軌跡生成策略通過延遲使用，暫停處理和固定點映射的方法達到保護用戶軌跡隱私的目的.當用戶使用提供LBS服務的應用時，應用將會通過系統API調用獲取當前的定位，本策略在這一環節通過修改系統API返回的數據，以達到返回虛假定位、保護用戶隱私的目的，并使得此算法具有普適性，可以為無相關背景知識的用戶所使用.

1.4 延遲使用

常規的虛擬軌跡生成策略通過當前位置生成虛擬節點“啞元”(dummies)，由啞元生成半徑r控制定位精準度，r越大則定位精準度越低，用戶隱私保護程度越高.然而一方面單一的增減r會使得軌跡無序性隨r增大而增大，即生成的虛假軌跡更容易被識別；另一方面此策略在某些情況下極易暴露用戶真實位置，如高速路出口處等位置，此時即使啞元并不在出口處，但是攻擊者也可以輕易結合時間信息推斷被攻擊者的位置.故本文的生成策略考慮到Ardagna等人[17]的研究，通過移動區域中心的方法，降低定位精準度的同時更大程度地保護用戶位置隱私.為了使虛假軌跡更加擬真(如圖1所示)，生成虛假定位的區域中心選擇一定延遲時間D之前的真實定位.

圖1 控制生成定位精準度的方式

1.5 停頓處理

用戶并非一直在行走，如果用戶在某個地方停下來如觀看風景或短暫休息，此時在以往的匿名軌跡生成算法中將會繼續在當前節點周圍生成啞元，然而停留時間越長，生成的啞越有可能暴露真實定位所在.如圖2所示，在同一真實定位附近，分別生成5，20，100個虛擬定位，真實定位越來越接近所有定位的中心.故本策略擁有停頓處理功能，當使用者停頓后，其相應的啞元也會停頓，避免隱私泄露的風險.

圖2 生成不同個數虛假定位時真實定位所在位置

1.6 固定映射

在前人的研究中很少考慮到固定的映射策略，但是固定點映射在反惡意檢測中有很大的作用，如果從攻擊者的角度出發，大部分使用者都會有常駐點，如家或工作地點等，可以通過判斷一段時間內用戶有沒有常駐點來表明此軌跡是否是虛假軌跡，所以常駐點映射是十分必要的，例如當用戶回到家之后，相應的啞元也會最終到達一個固定點停留，防止攻擊者的虛假軌跡識別.而從用戶的角度出發，一段路徑中的某些點可能是必須暴露的，此時固定點映射也可以暴露出用戶指定的點，達到定制化的效果.

1.7 算法思路

首先得到真實軌跡集合RT，由于用戶設備本身存在定位誤差，所以需要先對真實軌跡進行預處理，把誤差范圍內的定位處理為同一定位，解決用戶停頓后因為定位誤差帶來的前后定位不一致問題.同時為了方便后續依據時延t獲取混淆區域半徑，在前t個時間內重復第1個定位節點.

隨后進行啞元生成，根據處理好的真實軌跡集合中的每一個定位，在混淆半徑r內取出1個滿足可達性的點.即前一個啞元能夠在單位時間內到達此啞元.在此過程中如有遇到在固定點映射集合M中的點，則啞元不必自己生成，而是從M中取得.

最后將所有啞元合并就得到了用戶的虛假軌跡，使用者可以根據需求從中提取數據.

1.8 軌跡預處理

為了使延遲使用和暫停處理的算法策略更好地發揮作用，需要對用戶真實軌跡RT進行處理，將相似定位處理為同一定位，解決移動設備本身定位精度問題帶來的誤差，同時依據時延時間t在真實軌跡開始處不斷填充相同的起始節點.

算法1.真實軌跡預處理算法.

步驟1.將PRT置為空集；

步驟2.重復t次；

步驟4.結束重復；

步驟8.結束遍歷；

步驟9.返回PRT.

1.9 生成虛假軌跡

在之前經過預處理的軌跡PRT的基礎上，通過混淆策略和固定點映射策略生成虛假軌跡FT.

算法2.虛假軌跡生成算法.

步驟1.將FT置為空集；/*生成與PRT中定位數對應的FT*/

步驟7.結束遍歷；

步驟8.返回FT.

2 實驗與數據分析

本文使用微軟亞洲研究院收集的軌跡數據集Geolife[18-20]，使用了其182個用戶在2007-04—2012-08期間記錄的24 876 978個點表示的GPS軌跡的數據，本實驗代碼由Python3.8.3編寫，實驗環境為macOS 10.15.7操作系統.實驗中的POI(L)即定位L處的周圍興趣點通過調用高德地圖開放平臺接口獲取，平均距離s指混淆區域中心與原定位的平均歐氏距離.

2.1 時延t對命中率AR的影響

由于不同用戶對于POI(興趣點)搜索的需求范圍不同，我們使用了3種搜索范圍，分別是300 m，1 000 m和3 000 m，即在這3種POI搜索范圍中探究時延t與命中率AR的關系：命中率1表示在搜索附近300 m時POI的命中率；命中率2表示在搜索附近1 000 m時POI的命中率；命中率3表示在搜索附近3 000 m時POI的命中率.實驗表明，當用戶對POI搜索距離較大時，延遲對命中率影響較小，在3 000 m時POI搜索范圍的情況下，即使時延300 s也可以達到超過94%的命中率.

2.2 混淆區域半徑r對命中率AR的影響

在POI查詢距離分別為300 m時，時延對命中率的影響如圖4所示，當POI的查詢范圍為3 000 m時，時延對命中率的影響如圖5所示，此時時延對命中率的影響非常小，同時從圖3可以看出，時延越長，時延后的節點與原節點歐氏距離越遠，即混淆效果越好，但當POI范圍較近時，時延對命中率的影響較大.

圖3 時延t對命中率的影響

圖4 POI查詢范圍為300 m時混淆半徑對命中率的影響

圖5 POI查詢范圍為3 000 m時混淆半徑對命中率的影響

2.3 與以往方案對比

此次實驗位置采樣設置為每5秒1次，混淆半徑為10 m，分別對比了隨機法、軌跡旋轉法和本文的方法所生成軌跡的判正率CR和命中率方差ARV.

在以往關于虛擬軌跡算法的研究中，并沒有對軌跡的擬真性提出量化標準，本文實驗通過判正率這一判斷指標對各方法進行定性比較.

由圖6可知，隨著平均距離的增大，通過隨機法生成的軌跡迅速失去真實性，極易被判斷為假軌跡，而本文的策略與軌跡旋轉法生成的軌跡則基本不受平均距離的影響，具有較高的真實性.

圖6 不同方法的判正率

如圖7所示，本文的策略在POI命中率的方差上與隨機法是一個量級，遠低于軌跡旋轉法，保證了LBS的穩定可用.

圖7 不同方法的命中率方差

3 結束語

目前基于LBS的位置隱私保護主要集中在K-匿名算法等模型上，然而此類模型要求使用者具有相應的背景知識，不適宜作為普適的解決方案，對于沒有背景知識的普通使用者來說，在位置隱私保護和LBS中取折中的混淆算法無疑是更佳的選擇.本文在以往研究的基礎上，采用了延時處理、停頓處理、固定點映射等策略，提出了一種更優的保護使用者位置隱私的混淆策略.相比于以往的混淆策略，通過隨機法生成的軌跡隨著混淆中心的位移長度增加，軌跡呈現混沌的趨勢，與真實軌跡不符，通過軌跡旋轉法生成的虛假軌跡雖然具有較高的真實性，但是在POI命中率上容易出現極端情況，本文的策略則表現出了更好的擬真性與穩定性.

下一步的研究工作主要包含：

1)本文所采用的數據集主要分布在北京市，建筑密集，POI集中，而對于人口稀疏、POI較少的地區的處理有待進一步研究；

2)本文主要關注的步行軌跡，針對騎行、公共交通或駕車等速度更快的情況缺乏探討，基于時延等策略的混淆是否有效還需要驗證，適用于這些情況的更好的混淆策略也還需進一步研究.