軌跡隱私保護研究綜述

許志凱　張宏莉　余翔湛

摘 要： 隨著智能終端的普及和無線通信技術的發展，基于位置的服務已滲入到人們的日常生活當中這些服務在給人們的日常生活帶來便利的同時，也帶來隱私泄漏的風險。針對軌跡數據的推理攻擊不僅可得出用戶可分析出目標用戶的家庭住址、工作地點等敏感位置信息，甚至可推測出用戶的生活習慣、健康狀態、宗教信仰等隱私信息。軌跡隱私能否得到妥善保護已成為制約移動互聯網發展的瓶頸問題。本文對已有的軌跡隱私保護方法進行了分類描述，并分析已有工作的優缺點，最后指明未來的研究方向。

關鍵詞：軌跡隱私；隱私保護，位置隱私，網絡安全

中圖分類號：TP391.41 文獻標識號：A

0 引言

隨著智能終端的普及和無線通訊技術的發展，基于位置的服務（Location-based Service，LBS）已滲入到人們的日常生活當中。然而，許多基于位置的服務，如電子地圖、運動計步、移動廣告，需用戶實時提交自己的位置信息。這些服務可為人們的生活帶來巨大的便利。以電子地圖服務提供商Google地圖、百度地圖為例，這些應用不僅可為用戶提供實時交通導航，還可為用戶提供實時路況信息，并規劃最優線路。然而，這些服務也帶來隱私泄漏的風險，在使用這類服務時，LBS用戶需實時地將自己的位置信息提交給LBS服務器，但這些軌跡數據往往含有豐富的時空信息。針對軌跡數據的推理攻擊不僅可得出用戶在什么時間去過什么位置，還可分析出目標用戶的家庭住址、工作地點等敏感位置信息，甚至可推測出用戶的生活習慣、健康狀態、宗教信仰等隱私信息。因此，軌跡隱私保護受到用戶及研究者的廣泛關注。

針對上述問題，本文介紹基于位置的服務，在此基礎上分別綜述位置隱私保護技術的主要研究現狀及存在的問題，同時，根據目前研究的不足指出未來可能的研究方向。

1 基于位置的服務

圖1表示了基于位置服務的一般架構，該架構包含3個實體；

1）為LBS用戶提供定位服務的導航定位基礎設施，主要包括GPS衛星、無線網絡基站、WIFI等。

2）持有移動智能終端的LBS用戶（本文的研究中將LBS用戶與移動智能終端可視為同一主體）。移動智能終端可通過硬件（如GPS芯片）和軟件（如基站信號定位、WIFI指紋定位）技術確定該LBS用戶所在地理位置，并通過無線信號與LBS服務器進行通信。

3）為LBS用戶指定基于位置服務的服務提供商，如百度地圖、Google地圖、大眾點評等。

連續型LBS服務指的是用戶需實時提交的自己的位置信息才能獲取到相應服務的LBS服務，這類服務主要包括智能導航服務、無人駕駛汽車、基于位置的新聞（廣告）推送、運動計步及某些社交類APP（如定位附近與我興趣相同的人）等。 以智能導航服務為例，一次典型的連續型LBS服務如圖1所示。具體可做如下闡釋：

1）用戶通過定位服務如GPS等獲取自身位置；

2）用戶將自身位置及所需的服務請求發送給LBS服務提供商；

3）LBS服務提供商根據用戶當前的位置及道路擁塞情況為用戶規劃行駛線路，并提供導航服務；

4）重復過程（1）至（3）直到滿足用戶的服務要求，如完成一次從地點A到地點B的導航服務。

2 威脅模型

在軌跡隱私保護的研究中，研究者一般認為GPS等定位設備是可信的，即用戶可獲取其位置坐標的過程是安全的，而LBS服務提供商是不可信的， 即LBS服務提供商可能會利用用戶的軌跡信息挖掘用戶的隱私信息。這是因為用戶在將位置數據提交給LBS提供商后沒有能力驗證服務提供商是否可信，其次可信的服務提供商也可能會被惡意第三方攻擊，導致用戶位置隱私的泄漏。

3 軌跡隱私保護技術

近些年軌跡隱私保護受到研究者的廣泛關注。根據用戶的查詢請求在到達LBS服務器之前變換方式的不同，當前的軌跡隱私保護方法可分為以下3類：

1）基于k匿名泛化的方法；

2）基于噪聲數據的方法；

3）基于動態假名的方法。

3.1 基于k匿名泛化的軌跡隱私保護技術

K匿名泛化法[1]是一種經典的位置隱私保護技術。其基本思想是：在發送服務請求時，以一塊空間區域代替用戶的精準位置，即通過降低用戶位置的精度的方式滿足用戶的隱私需求。部分研究者[2-3]將k匿名泛化應用到軌跡隱私保護中。一個直觀的思路是將連續的2次查詢視為2個獨立的LBS服務請求，即分別為這2次查詢構建匿名空間。但這種方法易受基于用戶移動速度的推理攻擊。針對上述問題，文獻[2]基于用戶移動速度構建匿名區域，以保證2個連續提交的匿名區域在速度上可達。然而，這一方法并不能充分保證用戶的位置隱私。如圖2所示，設A正在沿道路行駛，并在實時地查詢周邊的東北菜館。圖（a）是用戶A在時刻ti生成的匿名空間，圖（b）是用戶A在時刻ti+1生成的匿名空間。 由于用戶的移動方向與速度并不會完全相同，2塊匿名空間中只包含用戶A這一共同用戶，即使兩塊匿名空間在速度上是完全可達的，攻擊者也可通過比對2塊匿名空間中的用戶輕易地推測出用戶A正在查詢東北菜館的信息。

綜上問題論述開展研究，文獻[3]認為在連續查詢中，用戶所提交的匿名區域應包含k個相同的用戶。基于上述思想，有針對性地提出一種基于貪心的匿名區域構建算法，但通過該方法構造的匿名空間的面積會隨著查詢次數的上升而帶來線性增加，從而形成嚴重的通信和計算開銷。軌跡隱私保護需建立用戶服務可用性的基礎上， 如何在保護用戶軌跡隱私的同時，盡可能的減小匿名空間的面積，提高基于服務的可用性，是該類方法未來的研究重點。

3.2 基于噪聲數據的軌跡隱私保護方法

基于噪聲數據的軌跡隱私保護方法[4-5]的實現思想是：在將用戶的真實位置發送給LBS提供商的同時，以一定的策略生成若干虛假位置（dummy）并發送給LBS服務提供商作為用戶真實位置的“掩護”，使攻擊者無法分辨出用戶真實位置。文獻[6-8]針對連續查詢查中的噪聲數據添加機制進行了研究。文獻[6]根據上一時刻的位置，按隨機的速度和方向進行移動，并將獲得的隨機的位置點作為虛假位（dummy）進行發布，但這種方法生成的虛假位置點往往與用戶真實的移動特征不符，且這些虛假位置點本身可能是一些實際上不可能到達的位置。針對這一問題，文獻[7]在生成虛假位置點時加入了移動速度、路網等約束條件。文獻[8]認為移動用戶不會始終連續性移動，因此其在生成噪聲數據點時會讓移動對象根據周邊的環境隨機地產生一些停頓，以防止攻擊者識別出噪聲數據。然而，現實社會中，用戶的行駛過程易遇到各種意外事件，如何處理這些意外事件，以生成更“真實”的噪聲軌跡數據仍是一個巨大的挑戰。此外，上述方法對攻擊者的背景知識假設較為保守，當攻擊者獲得了從用戶的日常行為中提取的背景知識時，即使用戶的生成的噪聲軌跡無法模擬出真實用戶的移動軌跡，攻擊者也可辨別出用戶的真實軌跡。

3.3基于動態假名的方法的軌跡隱私保護方法。

基于假名的軌跡隱私保護方法的基本思想為：用戶在發送基于位置的服務請求是以一個假名（pseudonym）來代替用戶的真實身份。然而，研究者發現長時間使用同一假名并不能有效地保護用戶的隱私，這是因為在路網中移動用戶是公開可見的，一次偶然的隱私的泄漏就可能會導致用戶整個移動軌跡的泄漏。因此，研究者[9]提出基于mix-zone的動態假名技術。

當前大部分研究工作圍繞如何構建單個mix-zone區域展開。 文獻[10]提出的MobiMix即是其中的代表性方法，對應基本思想為針對現實中可能被攻擊者利用的背景知識，如移動速度，轉移概率等，利用不規則的多邊形及其組合建立混淆區域，使其適應當前場景，提高隱私保護程度。然而，在現實中只有同時部署多個混淆區域才能有效地保護用戶的軌跡隱私，但在mix-zone內用戶必須停止使用基于位置的服務，部署過多的mix-zone可能會嚴重影響服務質量。在此問題基礎上，文獻[11]提出一種基于組合優化的混淆區域部署方案。文獻[12]進一步地考慮路網和交通流量的限制，提出一種基于整數規劃的混淆區域部署方案，可在部署有限個混淆的區域的同時，盡可能提高用戶的隱私保護水平。 單個mix-zone的設計目前已經有較為成熟的方案，如何在城市環境下協調部署多個mix-zone則是該方向未來的研究重點。

4 結束語

隨著移動互聯網的發展，軌跡隱私保護受到研究者的廣泛關注。本文對近些年來該方向已有的研究成果進行了回顧，對比和分析了已有的方法和技術，并指出仍然存在的問題和可能的研究方向。整體來說，目前軌跡隱私保護的研究仍然處于起步階段，仍有許多關鍵性問題尚未解決。

參考文獻：

[1] SWEENEY L. k-anonymity： a model for protecting privacy[J]. International Journal on Uncertainty， Fuzziness and Knowledge-based Systems， 2002， 10（5）： 557-570.

[2] GHINITA G， DAMIANI M L， SILVESTRI C， et al. Preventing velocity-based linkage attacks in location-aware applications[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Washington： ACM ，2009： 246-255.

[3] WANG Y， XU D， HE X， et al. L2P2： Location-aware location privacy protection for location-based services[C]//Proceedings of IEEE INFOCOM. Orlando， Florida： IEEE， 2012：1996-2004.

[4] NIU B， LI Q， ZHU X， et al. Achieving k-anonymity in privacy-aware location-based services[C]//Proc. of IEEE INFOCOM. Toronto： IEEE， 2014：754-762.

[5] NIU B， LI Q， ZHU X， et al. Enhancing privacy through caching in location-based services[C]//Proc. of IEEE INFOCOM. Hong Kong： IEEE， 2015：1017-1025.

[6] KIDO H， YANAGISAWA Y， SATOH T. Protection of location privacy using dummies for location-based services[C]//Proc. of the 21st Intl Conf. on Data Engineering. Tokyo： IEEE， 2005： 1248?1248.

[7] SUZUKI A， IWATA M， ARASE Y， et al. A user location anonymization method for location based services in a real environment[C]//Proc. of the 18th ACM SIGSPATIAL Intl Symp. on Advances in Geographic Information Systems. Sana Jose：ACM， 2010： 398?401.

[8] KATO R， IWATA M， HARA T， et al. A dummy-based anonymization method based on user trajectory with pauses[C]//Proc. of the 20th ACM SIGSPATIAL Intl Conf. on Advances in Geographic Information Systems. Redondo：ACM， 2012： 249?258.

[9] FREUDIGER J， RAYA M， FLEGYHAZI M， et al. Mix-zones for location privacy in vehicular networks[C]//WiN-ITS. Vancouver， British Columbia， Canada：ACM， 2007：1-7.

[10] ALANISAMY B， LIU L. Attack-resilient mix-zones over road networks： architecture and algorithms[J]. IEEE Transactions on Mobile Computing， 2015， 14（3）： 495-508.

[11] FREUDIGER J， SHOKRI R， HUBAUX J P. On the optimal placement of mix zones[C]//Proc. of the 9th International Symposium on Privacy Enhancing Technologies （PETS09）. Seattle：IEEE， 2009：216–234.

[12] LIU X， ZHAO H， PAN M， et al. Traffic-aware multiple mix zone placement for protecting location privacy. In： Proceedings of the IEEE INFOCOM 2012. Orlando， Florida： IEEE， 2012： 972-980.