劉佳　方賢進　康佳

摘要：隨著智能終端設備和社交網(wǎng)絡服務的廣泛使用，移動互聯(lián)網(wǎng)發(fā)展的一個重要趨勢是社交、位置和移動相融合，在這些應用中，位置是一項非常重要的信息。該文從位置隱私泄露的風險出發(fā)，介紹了幾種位置隱私保護技術(shù)，比較它們的優(yōu)劣，提出了移動感知的匿位區(qū)域生成方法，通過信息熵理論將用戶位置的不可推測性最大化，實現(xiàn)了社交網(wǎng)絡中個人隱私保護。

關(guān)鍵詞：社交網(wǎng)絡；個人位置；隱私保護；匿名模型

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）28-6616-04

隨著智能終端設備（如手機、平板電腦等）和社交網(wǎng)絡服務（SNS）的廣泛使用，移動互聯(lián)網(wǎng)發(fā)展的一個重要趨勢是社交、位置和移動相融合[1]。不僅社交網(wǎng)站如FaceBook、Twitter、新浪微博等都擴展了位置服務（Location-base Service）功能，傳統(tǒng)的位置服務如周邊信息搜索（如微信/QQ）也加入了社交化元素，形成了全新的移動社交網(wǎng)絡。在這些應用中，位置是一項非常重要的信息。按用途來分，位置數(shù)據(jù)可分為三類：第一類是作為服務的輸入信息，比如要查找周邊的事物如餐館、銀行，需要用戶提供當前的位置；第二類是用戶主動分享的數(shù)據(jù)，比如位置簽到；第三類是作為服務的使用代價，現(xiàn)在有不少應用提供免費使用，但會要求訪問用戶位置等個人信息。

位置也是一項非常敏感的信 息，除了位置信息本身涉及個人隱私，通過位置信息還可以推測出用戶的其它信息。根據(jù)愛倫·威斯汀 （Alan Westin） 在《Privacy and Freedom》一書 [2]中的定義，隱私是指個人或團體決定何時、在何種程度下、以何種方式把關(guān)于自己的信息傳達給他人的權(quán)利。換句話說，隱私是指用戶不想泄露的個人信息。因此，位置隱私保護主要針對上述第一類位置信息，使用時做到既能保護位置信息，又不影響正常的位置服務。

位置信息的不當使用或外泄可能會造成各種各樣的風險。比如，通過統(tǒng)計用戶常去的地方，攻擊者可推測用戶的私人信息，如興趣愛好、生活習慣、健康狀況等等。又如，知道了用戶晚上經(jīng)常待的地方，攻擊者可以推斷用戶的家庭住址，進而估計用戶的收入水平等。另外，如果廣告商獲知了用戶的當前位置，就可以向用戶推送與位置相關(guān)的廣告，可能對用戶造成不必要的騷擾。隨著大數(shù)據(jù)（big data）時代的到來，位置信息外泄的風險變得更大了，原因在于攻擊者從各種渠道可獲取的數(shù)據(jù)更多更廣，運用多數(shù)據(jù)源的交叉比對、協(xié)同分析等手段可對個人隱私信息進行更精準細致的推測[3]。

目前，工業(yè)界對位置隱私保護通常采用的方法是基于規(guī)則協(xié)議的策略，在訪問用戶位置前需取得用戶的授權(quán)。比較好的方法是遵循“最小特權(quán)原則”，即服務提供商只會在必要的情況下存取用戶的位置信息，并且不會長期保存用戶數(shù)據(jù)而用于其它非授權(quán)的用途。但這種方法的前提是對服務提供商有足夠的信任度，同時也對服務提供商的系統(tǒng)可靠性提出了非常高的要求。不幸的是，即使是完全遵從安全規(guī)范的服務提供商，也無法避免系統(tǒng)性的安全漏洞，用戶的個人信息依有可能外泄。另一種做法是移除用戶的ID標識信息，對位置數(shù)據(jù)進行匿名化處理。最近美國麻省理工學院的研究人員通過對150多萬移動用戶長達15個月的軌跡數(shù)據(jù)分析發(fā)現(xiàn)，人們的移動模式是非常獨特的，只要給出4個獨立的位置點，就能識別出95%以上的用戶[4]。換言之，對位置數(shù)據(jù)進行簡單的匿名化處理（如去掉ID標識）不足以保護用戶的位置隱私。

因此，學術(shù)界近年來致力于研究更可靠的位置隱私保護技術(shù)，希望最大限度地保護用戶位置等個人信息。該項研究主要面臨以下挑戰(zhàn)：首先，位置隱私保護是個性化的需求。不同的用戶有不同的隱私保護要求。即使是同一用戶，在不同的時間、地點對隱私保護的要求也可能不同。其次，位置隱私保護與位置信息可用性是一對矛盾體。服務提供商需要獲得用戶的位置信息來處理與位置相關(guān)的服務請求，而這又恰恰是用戶希望保護的個人隱私信息。因此，位置隱私保護技術(shù)需要在隱私保護與信息可用性之間取得一個很好的平衡。

針對這些挑戰(zhàn)，現(xiàn)有的位置隱私保護技術(shù)大致分為兩類：1）時空匿位（cloaking）技術(shù)[5-12]：降低位置信息的時空粒度，根據(jù)易受到基于背景知識的攻擊，用一個時空區(qū)域來表示用戶的大概位置。2）零隱私泄露技術(shù)[13-18]：采用計算密碼學的方法，對位置數(shù)據(jù)進行加密處理，進而在密文空間內(nèi)進行相關(guān)信息搜索服務的計算。時空匿位技術(shù)對位置隱私的保護力度有限，容易受到基于背景知識的攻擊，但其計算代價比較低。而零隱私泄露技術(shù)的計算代價比較高，但可以做到對位置隱私的完全保護，但降低了位置信息的可用性。

1 時空匿位保護技術(shù)

1.1 基于粒度的空間匿位

時空匿位技術(shù)允許用戶定義可暴露的位置粒度。文獻[5～6]著重考慮如何在滿足用戶隱私保護要求的前提下將匿位區(qū)域最小化，并沒有考慮服務請求的內(nèi)容。以最近鄰查詢?yōu)槔僭O用戶想搜索最近的餐館，但只允許在面積為T的范圍內(nèi)暴露位置。一個簡單直接的做法是根據(jù)用戶當前的位置隨機生成一個面積為T并且包含該用戶的區(qū)域（如圖1（a）中黃色框所示）作為匿位區(qū)域向服務器發(fā)出查詢請求。服務器返回該匿位區(qū)域內(nèi)所有可能點的最近鄰（g， g1， g2） 給用戶，然后用戶根據(jù)自己的精確位置提煉出真正的結(jié)果（g）。

這種方法有兩個不足：一是服務器查詢處理時間較長，因為需要處理匿位區(qū)域內(nèi)所有可能點的最近鄰查詢；二是查詢結(jié)果返回時間較長，因為沒有考慮服務請求而隨機生成的匿位區(qū)域可能導致太多的最近鄰結(jié)果需要返回，增加了數(shù)據(jù)傳輸量。

為了克服這些不足，文獻[7]提出利用沃羅諾伊元（Voronoi cell）的概念來生成匿位區(qū)域。一個對象的沃羅諾伊元定義為一個多邊形區(qū)域，在此區(qū)域內(nèi)所有查詢點的最近鄰都是該對象（如圖1（b）所示）。因此，一個匿位區(qū)域的最近鄰結(jié)果就是它們的沃羅諾伊元與該匿位區(qū)域相交的對象。這樣，對于給定的一個匿位面積T，為了將返回結(jié)果的數(shù)目最小化，最優(yōu)的匿位區(qū)域應該選取和最少個數(shù)沃羅諾伊元相交的區(qū)域，比如圖1（b）中的匿位區(qū)域。另外，既然沃羅諾伊元是潛在的查詢點集合，一個更優(yōu)的方法是直接請求返回對象，比如圖1（c）中的g。這意味著用戶可能的位置是在g的沃羅諾伊元內(nèi)，所以g的沃羅諾伊元可以理解為該用戶的匿位區(qū)域。如果g的沃羅諾伊元面積沒有達到匿位面積T，就可以要求返回鄰近的更多對象，直到它們的沃羅諾伊元面積之和超過T。為了實現(xiàn)此方法，該文設計了新型的沃羅諾伊元索引，以便用戶可以快速有效地選取需要返回的結(jié)果，同時又滿足空間匿位的粒度要求。此外，對于連續(xù)查詢中基于用戶移動模式的攻擊，該文提出移動感知的匿位區(qū)域生成方法[8]，通過信息熵理論將用戶位置的不可推測性最大化。

1.2 位置K匿名

基于粒度的空間匿位技術(shù)比較直觀，但有可能導致查詢隱私的泄漏。假設圖2中用戶從綠色的匿位區(qū)域發(fā)出一個內(nèi)容敏感的匿名查詢請求。如果攻擊者從其它數(shù)據(jù)源得知當時只有用戶A在該匿位區(qū)域內(nèi)，那么就可以把用戶A和該敏感查詢關(guān)聯(lián)起來。為了解決此問題，文獻[9]最早把K匿名的概念應用到位置隱私保護上，提出了位置K匿名，即一個用戶的匿位區(qū)域應覆蓋至少K-1個其它用戶，以至于這K個用戶是不可分辨的。在圖2中，設K為3，那么用戶A的匿位區(qū)域可以為紅色框包圍的區(qū)域。這樣，即使攻擊者知道用戶的位置，也無法和匿位區(qū)域內(nèi)3個用戶中的某一個關(guān)聯(lián)起來，從而降低了隱私泄漏的風險。不過，在用戶密集的地點單獨使用位置K匿名生成的匿位區(qū)域面積較小（如圖2中藍色的匿位區(qū)域）。為了兼顧位置隱私及查詢隱私保護，一般要求空間的匿位粒度也要達到一定的閾值。

為了實現(xiàn)位置 K 匿名，文獻[5，6]需要一個可靠的代理服務器來搜集不同用戶 的位置信息，然后進行匿名及匿位化處理。然而在此過程中，代理服務器可能獲知用戶的精確位置。為了消除由代理服務器泄漏 位置信息帶來的風險，文獻[10]提出了一個無須用戶提供具體位置信息的方案，主要思想是利用用戶的鄰近信息來生成匿位區(qū)域。具體來說，服務器首先獲取用戶的鄰近信息，計算出最優(yōu)的K用戶群組；然后用安全界定的方法 動態(tài)地產(chǎn)生能覆蓋全部K個用戶的匿位區(qū)域。此外，針對連續(xù)查 詢中基于歷史K匿名位置的攻擊及位置數(shù)據(jù)發(fā)布中敏感事件的K匿名保護，文獻[11，12]給出了相應的解決方案。

2 零隱私泄露的位置保護技術(shù)

2.1 近鄰檢測

鑒于地理位置社交網(wǎng)絡的日趨活躍，近鄰檢測（proximity detection）成為一種基礎(chǔ)服務。一般而言，近鄰檢測要求移動用戶向服務器上傳明文空間中的位置，后者以此檢測兩個或多個移動用戶是否是近鄰，即判斷距離是否小于某一閾值。文獻[13]提出了一種“grid-and-hashing”的方法，將空間用網(wǎng)格整齊劃分為均一的單元（cell），然后把用戶所在單元的標識符（ID） 進行不可逆哈希轉(zhuǎn)換后發(fā)送給服務器，使得服務器仍然可以進行近鄰檢測，但無法得知每個用戶的具體位置。

然而該項技術(shù)的問題是，由于網(wǎng)格的劃分是預先指定的，因此存在假陰性的檢測結(jié)果，即雖然兩個移動用戶距離很近，但由于被劃分到不同的單元中，導致他們上傳到服務器的哈希值不同。鑒于此，文獻[14]提出了“網(wǎng)格覆蓋”技術(shù)（如圖3 所示）：通過應用一系列相互交錯的網(wǎng)格，使得每個用戶有一個對應的哈希向量，如果兩個移動用戶在某一向量維度上擁有相同的哈希值，則表明他們是近鄰。顯然，網(wǎng)格的擺放和布局會對減少假陰率產(chǎn)生很大影響。在文獻[14]給出了用戶位置隨機分布模型下的最優(yōu)網(wǎng)格覆蓋方案。通過實驗，發(fā)現(xiàn)最優(yōu)布局比隨機布局減少了一半的網(wǎng)格需求，例如16個網(wǎng)格在最優(yōu)布局下可以達到32個網(wǎng)格在隨機布局下同等的10%左右的假陰率。

文獻[14]研究了在網(wǎng)格覆蓋技術(shù)下，用戶在移動過程中哈希值的更新上傳問題。傳統(tǒng)技術(shù)要求用戶在離開本單元后立即更新，以保證近鄰檢測結(jié)果的準確性。然而考慮到很多情況下用戶可能與所有需要進行近鄰檢測的好友都相距甚遠，這樣的更新策略費時費力，因此文獻[14]提出了基于網(wǎng)格層階的更新策略，將每個用戶在當前位置上無須進行更新的范圍最大化，最大程度地降低因用戶移動帶來的更新代價。實驗證明，對于一個數(shù)萬人的地理位置社交網(wǎng)絡，該策略可將每檢測點（checkpoint）的用戶上傳開銷控制在數(shù)百字節(jié)范圍內(nèi)。

2.2 零知識地理信息檢索

基于位置的信息檢索是移動社交網(wǎng)絡中最基礎(chǔ)的服務之一。用戶通過向網(wǎng)絡服務器提交自己的位置，來檢索與該位置相關(guān)的信息。隨著信息產(chǎn)業(yè)的發(fā)展，這些位置相關(guān)的信息已成為服務提供商的無形資產(chǎn)，故而保護它們防止用戶惡意攫取也成為重要的問題。一個流行的例子是用于分享各類安全和非安全（例如有釣魚風險）的Wi-Fi 熱點共享數(shù)據(jù)庫。用戶可以通過提交自己的位置獲取附近的該類Wi-Fi熱點信息?？墒强紤]到上述數(shù)據(jù)隱私的問題，不能僅僅為了保護用戶位置隱私而將整個數(shù)據(jù)庫保存在客戶端。

文獻[15]集中研究了可以同時保護用戶位置隱私和數(shù)據(jù)庫隱私的零知識檢索算法，即用戶無法獲取除查詢結(jié)果外的任何數(shù)據(jù)，而服務器亦無法得知用戶的查詢內(nèi)容：鑒于過去密碼學所提出的技術(shù)[16-17]由于代價過高而無法直接應用于海量數(shù)據(jù)，文獻[18]中整合最新的同態(tài)加密（homomorphic encryption）和有條件不經(jīng)意傳輸（conditional oblivious transfer）并提出了一種基于樹形索引的不經(jīng)意遍歷框架，包括索引、剪枝、預計算等，解決了鍵值存儲下海量數(shù)據(jù)查詢中的雙向隱私保護問題。實驗證明，與直接應用密碼學技術(shù)相比，該方法將原本線性的時間和傳輸復雜度壓縮到對數(shù)級，從而使得在大數(shù)據(jù)時代下保護雙向隱私成為可能。

3 結(jié)束語

如何保護個人位置隱私正受到學術(shù)界及工業(yè)界越來越多的重視。該文從位置隱私泄露的風險出發(fā)，介紹了幾種位置隱私保護技術(shù)。這些技術(shù)在隱私保護力度和計算代價方面各有優(yōu)劣，采用哪種技術(shù)應結(jié)合具體的應用場景。展望未來，新的位置隱私技術(shù)需要考慮用戶社交關(guān)系對位置隱私泄漏造成的影響。比如，用戶A分享了與用戶B在一起的信息，那么這兩個用戶的位置信息應受到同樣的保護，否則任何一方的位置泄漏都會影響到另一方。因此，未來可以研究結(jié)合社交關(guān)系的新型位置隱私模型及技術(shù)，以便能全方位地保護用戶的個人隱私信息，讓用戶可以放心地使用移動社交網(wǎng)絡中的各項應用服務。

參考文獻：

[1] 李德毅.大數(shù)據(jù)時代的位置服務[J].第七屆中國電子政務高峰論壇主題演講，2013.

[2] Alan F. Westin. Privacy and freedom， Bodley Head， 1970.

[3] McKinsey Global Institute. Big data： the next frontier for innovation， competition， and productivity，2011.

[4] Y.-A. Montjoye， C. A. Hidalgo， M. Verleysen， and V. D. Blondel. Unique in the crowd： the privacy bounds of human mobility. Scienti?c Reports， 2013.

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

[6] C.-Y. Chow， M. F. Mokbel， and W. G. Aref. Casper： query processing for location services without compromising privacy. ACM Transactions on Database Systems， 2009，34（4）， 24.

[7] H. Hu and J. Xu. 2PASS： Bandwidth-optimized location cloaking for anonymous location-based services. IEEE Transactions on Parallel and Distributed Systems （TPDS）， 2010； 21（10）： 1458-1472.

[8] J. Xu， X. Tang， H. Hu， and J. Du. Privacy-conscious location-based queries in mobile environments. IEEE Transactions on Parallel and Distributed Systems （TPDS）， 2010：21（3）： 313-326.

[9] M. Gruteser and D. Grunwald， Anonymous usage of location-based services through spatial and temporal cloaking. ACM MobiSys， 2003.

[10] H. Hu and J. Xu. Non-exposure location anonymity. IEEE ICDE， 2009.

[11] X. Pan， J. Xu， and X. Meng. Protecting location privacy against location-dependent attacks in mobile services. IEEE Transactions on Knowledge and Data Engineering （TKDE）， 2012； 24（8）： 1506-1519 .

[12] H. Hu， J. Xu， S. T. On， J. Du， and J. K. Ng. Privacy- aware location data publishing. ACM Transactions on Database Systems （TODS）， 35（3）， July 2010.

[13] L. ?ik?nys， J. R. Thomsen， S. ?altenis， M. L. Yiu， and O. Andersen， A Location privacy aware friend locator， Proc. of SSTD， 2009， 405-410.

[14] H. P. Li， H. Hu， and J. Xu. Nearby Friend Alert： Location anonymity in mobile geosocial networks. IEEE Pervasive Computing （PC）， 2013， 12（4）： 62-70.

[15] H. Hu， J. Xu， C. Ren and B. Choi. Processing private queries over untrusted data cloud through privacy homomorphism. IEEE ICDE， 2011.

[16] A. Yao， Protocols for secure computations， Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science， 1982.

[17] I. F. Blake and V. Kolesnikov， Strong conditional oblivious transfer and computing on intervals， Proceedings of ASIACRYPT， 2004.

[18] H. Hu， J. Xu， X. Xu， K. Pei， B. Choi， and S. Zhou. Private search on key-value stores with hierarchical indexes. IEEE ICDE， 2014.