基于位置服務的隱私保護綜述

魏興民 杜鵬懿

摘? 要：隨著社會的發展，技術快速進步，高精度的定位設備使得我們能夠使用多種不同類型的基于位置服務（LBS）。這些設備獲得的位置信息包括十分隱私的個人信息，所以隱私保護成了現在基于位置服務最重要的問題之一。本文總結了三種基于位置服務的隱私保護方法，包括使用仿真品的匿名通信技術，使用人造的仿真品位置信息，讓服務提供者不能區分哪一個是真實的用戶信息。點對點的空間隱形方法，用戶使用自己的對等體作為代理，這些對等體將用戶的查詢消息轉發給服務提供者，實現了空間隱形。空間和時間隱藏方法，是通過權衡空間分辨率和時間分辨率，來滿足指定的匿名性要求。最后提出了自己的一些創新的研究思路和解決方案。

關鍵詞：隱私保護;基于位置服務;匿名;點對點;空間隱藏;時間隱藏

中圖分類號：TP309? ? ? ?文獻標識碼：A 文章編號：2096-4706（2019）08-0154-04

Abstract：With the development of society，technology advances rapidly，highly accurate positioning devices enable us to entertain many different types of location-based services （LBS）. But location information obtained by these devices includes deeply personal information. Therefore，the protection of privacy has been one of the most significant issues of location-based services. This paper reviews three privacy protection methods for location-based services（LBS），including anonymous communication technique using dummies，this method use dummies together with real user information，so the service provider can’t distinguish which one is the real user information. Peer-to-Peer （P2P） spatial cloaking algorithm，in which user’s peers act as agents，they forward user’s queries to service provider，thus this method achieves spatial cloaking. Spatial and temporal cloaking method，in which spatial resolution and temporal resolution is traded off to meet specify anonymity requirement. Finally，this paper proposed some innovative research ideas and solutions.

Keywords：privacy protection;LBS;anonymity;P2P;spatial cloaking;temporal cloaking

0? 引? 言

近年來，計算機網絡和通信技術的飛速進步使得移動互聯網得到了迅速發展，隨之而來的位置服務使人們的生產和生活方式發生了很大變化。位置數據被用于各種不同類型的基于位置服務（LBS），如隨時都可網上預約滴滴出租車等。利用位置服務，用戶可先把真實位置信息提供給服務提供者，再從服務提供者那里獲取服務。發送數據之后用戶不能刪除或者修改已經發送的信息，即用戶不能防止服務提供者根據存儲的真實位置數據分析用戶的運動模式。針對位置服務出現的隱私泄露問題，必須采取措施進行隱私保護。本文對以往的一些基于位置服務的隱私保護方法進行總結，然后提出自己的創新研究思路與解決方案。

1? 基于位置服務（LBS）的位置隱私

A.Beresford和F.Stajano將位置隱私定義為防止其他團體根據某個人現在或者過去的位置進行學習的能力[1]，且認為一個系統能夠獲得位置數據侵犯了個人隱私。

在基于位置服務中，用戶發送的信息至少由用戶ID和用戶真實位置信息組成。本文假設用戶的ID不與用戶的隱私信息相連接，可使用假名。盡管用戶的ID是隱藏的，仍可能通過位置數據侵犯用戶隱私。如某人每天在固定時間都會一個地方，如果這樣的位置數據被累積起來被分析，那么便可推知此人的住址。為保護位置隱私，需匿名化位置數據。其匿名性的程度需考慮以下方面：

（1）普遍性。指對象存在于整個區域中。當所有的用戶居住在相同的區域中，普遍性意味著對象存在于整個區域中，服務提供者可以指定用戶。另一方面，當用戶居住在不同的區域中，服務提供者指定用戶很困難。因此，普遍性增強了整個區域中用戶的位置匿名性。

（2）擁擠性。指大量的對象存在于一個區域中，這源自M.Gruteser和D.Grunwald提出的k-anonymous[2]。用戶在一個區域中發送位置信息給服務提供者。當許多用戶生活在這個區域中，服務提供者很難指定某一個用戶。這樣就增強了一個區域中用戶的位置匿名性。普遍性保證了每個用戶的位置匿名性，但擁擠性只保證了局部用戶的位置匿名性。

2? 使用仿真品的匿名通信技術

M.Gruteser和D.Grunwald提出匿名使用基于位置服務[2]，用戶發送的位置數據，精度被減少，然后被發送給服務提供者，如圖1所示，位置數據的精度用灰色區域表示，服務提供者只能學習到用戶位置的模糊的細節，這就增強了位置匿名性。但問題是通過追蹤幾分鐘的數據，觀察者能夠很容易地理解用戶的移動。因為位置數據創造出了一個粗略的軌跡。（b）用戶產生兩個與（a）不同的仿真品，它們能與真實的位置數據向不同的方向移動，因為其他用戶同時發送位置數據，用戶更加安全。

（a）準確率縮減

（b）虛擬生成

2.1? 基本過程

為解決可追蹤問題，這篇文章提出了一個新的基于位置服務匿名通信技術，用戶發送包含噪聲的位置數據給服務提供者。噪聲包括一組被稱作“仿真品”的假的位置數據[3]。如圖2所示，服務的過程如下：

（1）一個基于位置服務（LBS）用戶從GPS設備獲得自己的位置信息r。

（2）仿真品在位置1和位置2處產生。

（3）用戶創造一個服務請求消息S，包括位置數據r、1和2，發送S給服務提供者。

（4）服務提供者創造一個服務應答消息R，R應答接收到的所有位置數據，并且把R發送給用戶。

（5）用戶接收R，并且只從R中抽取出必要的數據。用戶知道真實的位置數據，但服務提供者不知道。所以服務提供者不能從接收到的一組位置數據中識別出用戶真實的位置數據。這樣匿名服務就完成了。

2.2? 仿真品生成算法

仿真品生成算法的主要目的是使觀察者不能區別真實位置數據和仿真品。一般而言，每個對象在固定時間內的移動是有限的。如果隨機產生仿真品，那么很容易發現真實位置數據和仿真品之間的區別，因為使用基于位置服務（LBS）需要位置數據是連續的。仿真品不能表現得和真實的位置數據完全不同。本文提出兩種不同的仿真品生成算法，來防止服務提供者發現真實的位置數據。

在領域內移動（MN）：如圖3（a）所示，仿真品的下一個位置是由仿真品的當前位置的鄰域決定的。用戶的通信設備記住每個仿真品之前的位置，然后設備根據仿真品之前的位置產生新的仿真品位置。

在有限領域內移動（MLN）：如圖3（b）所示，仿真品的下一個位置也是由仿真品當前的位置決定的。但是下一個位置也被當前區域的密度所限制。這個算法是自適應的，首先，用戶的通信設備獲得其他用戶的位置數據。然后，設備根據記憶產生仿真品，這和MN算法一樣。接著，如果有很多用戶在生成的小區域中，設備再一次產生仿真品。這個過程重復很多次。

3? 點對點（P2P）空間隱形算法

3.1? 算法概述

C.Y.Chow等人提出了用于匿名的基于位置服務（LBS）的空間隱形算法[4]，主要解決目前基于位置服務（LBS）的隱私問題，用戶向服務提供者報告他們真實的位置信息來獲得想要的服務。本文提出了點對點（P2P）空間隱形算法，主要思想是在查詢任何基于位置服務前，移動用戶先使用單跳通信或多跳路由和他的對等點形成一個組。然后空間隱形區域被計算為覆蓋整個組用戶的區域。提出的P2P空間隱形算法支持按需模式和主動模式兩種類型的操作。實驗表明，使用按需模式操作比使用主動模式操作具有更低的通信開銷和更好的服務質量，但按需模式需要更長的響應時間。

3.2? 算法介紹

在基于位置服務（LBS）中，用戶需要把他的真實位置數據發送給服務器。假如服務器不可靠，用戶的位置隱私將被侵犯。目前已經有不少方法被提出來[5-7]解決此問題。一個可信的第三方被用作中間件，來把用戶的位置模糊化到一個空間區域中，以獲得k匿名性，即一個用戶不能從另外k-1個用戶中區別開來。這樣的集中式隱私保護策略有兩個缺點：

（1）集中式的第三方可能成為系統的瓶頸或者單點故障。

（2）集中式的第三方具有位置信息的全部知識和所有的用戶查詢，可能因第三方入侵引入嚴重的隱私威脅。

本文提出點對點的（P2P）的空間隱形算法，移動用戶采用點對點空間隱形算法能夠保護他們的隱私，而不用尋求集中式的第三方的幫助。除了集中式方法的缺點，這個算法還有以下事實：

（1）大部分移動設備的計算能力和存儲容量都以很快的速度增長。

（2）P2P通信協議，比如IEEE 802.11和藍牙已經被廣泛部署。

（3）許多基于P2P信息共享的新應用已經快速成型，比如合作信息訪問[8，9]和P2P空間時間查詢處理[10，11]。

文章提出的P2P空間隱形算法能夠以按需模式和主動模式操作。在按需模式中，當移動客戶端需要從基于位置的數據庫服務器那里獲得信息時，就執行隱形算法。另一方面，在主動模式中，移動客戶端定期在周圍尋找，以發現預期數量的對等體。因此，在任何時候移動客戶端想要從基于位置的數據庫服務器那里檢索信息時，都能夠把真實位置隱藏到空間區域中。文章的主要貢獻為：

（1）引入了一個分布式系統架構來為移動用戶提供匿名的基于位置的服務。

（2）提出了第一個空間隱形算法來為移動用戶享受高質量的基于位置的服務，而不使他們的隱私受到威脅。

（3）提供了實驗證據來說明提出的算法在響應時間方面的有效性，它對大規模移動客戶也具有伸縮性，并且是有效的，它能為移動客戶提供高質量的服務而不需要真實的位置信息。

4? 通過空間和時間隱藏來匿名使用基于位置服務（LBS）

4.1? 算法概述

匿名能夠提供很高程度的隱私，使得使用服務的用戶不需要處理服務提供者的隱私策略，并且減少了服務提供者保護隱私信息的需要。然而，確保匿名使用基于位置服務，需要用戶傳輸的精確位置信息不能被很容易地用來重新識別對象。這篇文章提出了一個中間件架構和算法，它們能夠被集中式的位置代理服務使用。這個自適應的方法沿著空間和時間維度調整位置信息的分辨率，來滿足規定的匿名性限制，基于給定的區域中可能使用位置服務的實體。

4.2? 算法介紹

M.Gruteser和D.Grunwald提出通過空間和時間隱藏來匿名使用基于位置服務[2]，研究了一種專注于最小化收集原理的方法。在這個方法中，基于位置的服務只收集和使用去個性化的數據，即匿名數據[12]，并承諾對兩方都有利。對服務提供者而言，匿名數據會產生更少的開銷。它可以不經用戶同意，被收集，處理，然后分發給第三方。

實際的匿名需要對象不能從位置數據中被重新鑒別。如一個發送給地圖服務的消息，它由網絡地址，用戶ID和用戶當前位置的坐標組成。用戶ID和網絡地址是重新鑒別首先考慮要用的信息。對于匿名服務使用，用戶的ID可以被省略。網絡地址問題可以被Crowds[13]或者Onion Routing[14]這樣的機制解決，它提供了發送者匿名性。如果位置信息被記錄下來并且連續地分布，這個隱私問題便增大了。LBS中的匿名性必須在網絡中的多個協議棧層次得到解決，這取決于怎樣的實體可以被信任。這篇文章在應用層解決匿名性問題，通過讓服務提供者訪問匿名位置數據，即位置信息被充分改變來防止重新鑒別。文章的主要貢獻是：

（1）一個位置匿名性正式的度量。

（2）一個自適應的基于四叉樹的算法，它能夠降低位置信息的空間分辨率來滿足一個指定的匿名性限制。

（3）一個算法，它能夠通過降低時間分辨率來提高空間分辨率，以滿足同樣的匿名性限制。

（4）一個評價這些算法預期分辨率的方法，它是基于交通模型，交通模型由地圖材料和汽車交通計數組成。

5? 研究思路與解決方案

解決基于位置服務（LBS）的隱私問題時，位置匿名很重要。一個觀察者可以根據對象的位置信息在一個連續時間內的變化，描述出對象的移動軌跡。但想要描述就需要對象在一段時間內的某個標識不發生變化。否則，觀察者只能得到一些孤立的點，并不能辨認哪一個位置信息是屬于哪一個對象的。基于此，我覺得在解決LBS時，可使用完全隱藏用戶標識的方法，這里的標識包括用戶ID，網絡地址等各個方面。隱藏用戶的ID很簡單，可以在每次向服務提供者發送查詢時，不發送用戶ID，只發送網絡地址。要隱藏網絡地址，可以使用一些代理，用戶把帶有網絡地址的請求包發送給代理，由代理向服務提供者發送查詢。代理接收到服務提供者的響應消息后再轉發給用戶，這樣用戶的網絡地址對服務提供者而言就隱藏了，但是這個過程需要代理是可信的。

6? 結? 論

基于位置服務（LBS）的廣泛使用也帶了很多隱私問題。對于LBS中的位置隱私保護問題，國內外已有大量文獻進行了深入研究，本文總結了基于位置服務隱私保護的方法，包括使用仿真品的匿名通信技術，點對點的空間隱形方法以及空間和時間隱藏方法。但諸如如何解決對等點之間的信任問題、如何解決云計算、大數據時代位置隱私保護問題亦需納入后續的研究之中。

參考文獻：

[1] BERESFORD AR，STAJANO F.Location privacy in pervasive computing [J].IEEE Pervasive Computing，2003，2（1）：46-55.

[2] Gruteser，M. and Grunwald，D.Anonymous Usage of Loca-tion-Based Services through Spatial and Temporal Cloaking [C]//Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，San Francisco，2003.

[3] Kido H，Yanagisawa Y，Satoh T. Protection of Location Privacy using Dummies for Location-based Services [C]//International Conference on Data Engineering Workshops. IEEE Computer Society，2005.

[4] Chow C Y，Mokbel M F，Liu X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service [C]//Acm International Symposium on Advances in Geographic Information Systems.ACM，2006.

[5] B.Gedik and L.Liu.A customizable k-anonymity model for protecting location privacy [C]//In Proc.IEEE ICDCS，2005.

[6] M. Gruteser and D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking [C]//ACM International Conference on Mobile Systems，Applications and Services，2003.

[7] Chi-Yin Chow，Mohamed F. Mokbel，Walid G. Aref. Casper*：Query processing for location services without compromising privacy [J].ACM Trans. Database Syst.，2009，34.

[8] Chow C Y，Hong V L，Chan A T S. Distributed group-based cooperative caching in a mobile broadcast environment [C]//International Conference on Mobile Data Management，2005.

[9] Papadopouli M，Schulzrinne H. Effects of power conservation，wireless coverage and cooperation on data dissemination among mobile devices. In [C]//John Wiley & Sons，Ltd.，2001.

[10] Huang Z，Christian S?ndergaard Jensen，Lu H，et al. Skyline Queries Against Mobile Lightweight Devices in MANETs [J].Icde，2006：66.

[11] Ku W S，Zimmermann R，Wang H，et al. ANNATTO：Adaptive Nearest Neighbor Queries in Travel Time Networks [C]//International Conference on Mobile Data Management. IEEE，2005.

[12] Pfitzmann A，Marit K?hntopp. Anonymity，Unobservability，and Pseudonymity — A Proposal for Terminology [J].2001.

[13] Reiter M K，Rubin A D. Crowds：anonymity for Web transactions [J].ACM Transactions on Information and System Security，1998，1（1）：66-92.

[14] GOLDSCHLAG D，REED M，SYVERSON P，et al.Onion routing for anonymous and private internet connections [J].Communications of the ACM，1999，42（2）：39-47.

作者簡介：魏興民（1984.02-），男，漢族，寧夏固原人，研究生，工程師，研究方向：信息安全。