社交網(wǎng)絡(luò)中的位置隱私保護(hù)研究

劉佳　方賢進(jìn)　康佳

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

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

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）28-6616-04

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

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

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

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

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

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

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

1.1 基于粒度的空間匿位

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

這種方法有兩個不足：一是服務(wù)器查詢處理時(shí)間較長，因?yàn)樾枰幚砟湮粎^(qū)域內(nèi)所有可能點(diǎn)的最近鄰查詢；二是查詢結(jié)果返回時(shí)間較長，因?yàn)闆]有考慮服務(wù)請求而隨機(jī)生成的匿位區(qū)域可能導(dǎo)致太多的最近鄰結(jié)果需要返回，增加了數(shù)據(jù)傳輸量。

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

1.2 位置K匿名

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

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

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

2.1 近鄰檢測

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

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

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

2.2 零知識地理信息檢索

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

[1] 李德毅.大數(shù)據(jù)時(shí)代的位置服務(wù)[J].第七屆中國電子政務(wù)高峰論壇主題演講，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.