基于隨機網格的位置隱私保護方法

楊松濤, 王慧強, 馬春光

(1. 哈爾濱工程大學計算機科學與技術學院, 黑龍江 哈爾濱 150001; 2. 佳木斯大學信息電子技術學院, 黑龍江 佳木斯 154007)

0 引 言

基于位置服務(location-based services, LBS)是移動互聯網中的典型應用。通常,LBS系統包括移動設備、定位系統、通信網絡和LBS提供商4個主要部分。用戶使用移動設備通過定位系統獲得位置信息的過程[1-2]可表示為:移動用戶按照服務提供商要求生成服務請求,該請求為四元組,其中,u代表用戶身份標識,(x,y)代表用戶二維平面坐標,c代表查詢內容,t代表查詢的時間。移動用戶在生成該請求以后將其發送給LBS提供商。

但是,在這個服務過程中移動用戶的位置信息可能會受到隱私威脅。位置信息可以作為一個重要的因素被定性和定量的分析[3-4]。例如:人們的行動軌跡本身可被追蹤,在現有的定位技術下,形成了一個近似軌跡,該軌跡可能包含有移動用戶更多的時空關聯信息。當這些信息被缺乏職業道德或者出于商業利益的LBS提供商所獲得時,極有可能會造成用戶個人隱私的泄露,甚至產生可能威脅移動用戶個人安全的事件發生。

針對隱私泄露問題,典型的方法是在用戶與LBS提供商之間增加一個可信的第三方服務器,由其使用位置k-匿名技術或位置模糊技術為用戶提供隱藏保護。近年來,基于這兩種技術，研究者提出了大量的[5-10]隱私保護方法。隨著研究的深入,人們更關心隱私的個性化問題,進而利用k-匿名模型[11-12]允許用戶自由調整個人隱私要求和最大時空容忍度,同時縮小匿名集的勢。基于差分隱私模型,相關研究人員又提出了地理空間的限制下的隱私保護模型[13]。

然而,用戶即使采用了一定的針對位置的隱私保護方法,攻擊者還是可以通過誤差軌跡和精確軌跡的相似度擬合的方法,斷定用戶身份與軌跡的關聯關系,進而暴露用戶的軌跡以及實時位置隱私。這種關聯關系可表現為移動用戶公開的查詢內容與潛在的位置坐標之間的有效關聯性。

針對這種利用關聯關系的攻擊行為，希爾伯特匿名算法(Hilbert cloak, HC)[14]定義了互質性概念,降低了同一匿名集的用戶對于匿名區域的依賴度相同。緩存隱藏[15]借鑒混合區域和路徑混淆的優點,采用一階馬爾可夫模型預測路徑,進而實現在交叉點處匿名,使得攻擊者無法確定用戶路徑和查詢。CoPrivacy[16]擴展了SpaceTwist,設計了一種新的錨點產生策略,通過用戶之間協作形成匿名組,利用該組的密度中心代替真實位置發出查詢,進一步隱藏了用戶的真實位置?；诩贁祿能壽E隱私保護方法[17]通過假軌跡對原始數據進行干擾,使攻擊者無法區分用戶的真實位置。但這些基于空間區域內模糊位置和降低位置信息空間粒度的方法無法保障在用戶較少環境下使用。針對這一問題,本文提出了基于隨機網格的位置隱私保護方法,該方法利用多網格融合來隱匿移動用戶的真實位置,通過網格內興趣點與用戶位置的模糊性,以及網格的不規則變化來切斷查詢與位置之間的關聯關系,保護用戶的位置查詢隱私。該方法具有較好的隱私保護能力和算法執行效率。

1 系統模型

本文所采用的系統模型包括3個部分,即查詢用戶(query issuer,QI)、位置匿名服務器(location cloak server,LCS)和LBS服務器(LBS server,LBSs)。各部分之間使用安全通道傳輸數據(例如SSL)。在如圖1所示的系統模型中,攻擊者攻擊遵循Honest-but-Curious模型,即LBSs在嚴格執行協議和算法的前提下,同時使用收集到的位置信息和背景知識推斷用戶的敏感信息。

圖1 LBS系統結構Fig.1 System architecture of LBS

依照圖1所示的系統模型,可確定以下4個基本假設:

假設1LBSs和LCS是半可信的,即為用戶提供服務的同時,但可能直接或間接泄露用戶的隱私信息。

假設2攻擊者可以從公共數據庫(例如:電話黃頁、家庭住址等)獲得先驗知識。同時,攻擊者具備統計分析和推理能力,可以利用匿名信息和先驗知識形成后驗知識。

假設3移動用戶可自由選擇匿名度,并且其客戶端具有一定的計算和通信能力。

假設4匿名過程和算法都是公開的。

為了便于后續描述,本文給出以下定義：

定義1位置軌跡不可追蹤性。位置軌跡是按時間排序的位置序列,可以表示為

T={Ti,(x1,y1,t1),…,(xn,yn,tn)}

(1)

式中,Ti表示該位置軌跡的標識符；(xi,yi,ti)(i=1,2,…,n)表示移動對象在ti時刻的位置坐標為(xi,yi),其中ti為采樣時間。位置軌跡不可追蹤指LBSs利用公共信息庫和用戶查詢樣例信息分析出該用戶位置軌跡的概率很低。

定義2身份不可關聯性。用戶集合表示為U={u1,u2,…,uk},查詢內容表示為c。匿名集內用戶身份不可關聯是指LBSs關聯ui(i=1,2,…,n)與c之間的概率很低。k-匿名度量是針對位置隱私保護最流行的度量標準,量化的匿名度k可以有效地度量不可關聯性,k值越大,不可關聯性越好。

2 基于網格的位置隱匿方法

2.1 網格內用戶數量的更新過程

如果每個移動用戶周期性地向LCS更新位置信息,則會帶來巨大的網絡負載。而且,LCS獲得用戶精確的位置更新數據,就可以追蹤用戶的軌跡,進而暴露了用戶的位置軌跡隱私。

如圖2所示,本文將LBSs服務區域劃分為若干個彼此相鄰的正方形網格,每個單元格被賦予一個序號。

圖2 網格圖Fig.2 Grid chart

鑒于無線傳感器網絡受到射頻芯片通信距離的限制,單個移動節點僅能夠知道鄰居節點的信息。如圖3所示,我們采用洪泛法探測網格中的移動節點數量。網格內每個節點執行如下位置更新算法。

算法1位置更新算法

(1) 初始化狀態,所有節點向LCS更新所在網格的信息;

(2) 從離散的整數集合[0,1,…,N]中隨機選取一個數n,等待n×t的時間后執行洪泛法;

(3) 計算節點所在的網格;

(4) 通過洪泛方式向網絡傳播位置樹組建消息;

(5) 依據位置樹計算網格內的節點數量;

(6) 向LCS更新網格內的移動用戶數量。

圖3 位置更新Fig.3 Location update

2.2 網格匿名查詢過程

本文采用多個隨機的、離散的網格實現位置k-匿名、網格l-多樣性和位置模糊的目的。

定義3網格查詢(Gq)。Gq以四元組形式表示,表達式為

Gq=(uid,gs,k,l,E(c),t)

(2)

式中，uid代表用戶身份的假名;gs代表用戶所在的網格序號;k代表用戶要求的匿名度;l代表用戶要求的網格數量;E(c)代表使用LBSs公鑰加密的查詢內容;t代表當前查詢時間。

定義4匿名查詢(Cq)。Cq以三元組形式表示,表達式為

Cq=(uid,{gi,…,gi+l},E(c),t)

(3)

式中,{gi,…,gi+l}代表隨機網格的集合。

定義5標記查詢(Sq)。Sq以三元組形式表示,表達式為

Sq=(uid,s,t)

(4)

式中,s代表用戶隨機生成的密鑰。

根據以上定義可得到隨機網格位置匿名算法,該算法在LCS內執行。

算法2隨機網格位置匿名算法

(1) 依據Gq,提取gs,k,l,E(c);

(2) 隨機選取l-1個網格;

(3) 判斷網格gs和隨機選取的網格中的用戶總數量是否大于k;如果大于k,執行下一步,否則回到第(2)步;

(4) 向LBSs發出匿名查詢Cq。

如圖4所示,網格匿名查詢過程如下:

(1) 用戶向LCS發出網格查詢Gq,同時向LBSs發出標記查詢Sq;

(2) LCS執行網格位置匿名算法;

(3) LBSs對l個網格分別進行最近鄰查詢,查詢結果集為P={pi,…,pi+l},其中,pi代表對序號為gi網格的查詢結果集合;

(4) LBSs使用用戶提供的密鑰加密Es(P)={Es(pi),…,Es(pi+l)},擾亂Es(P)內元素順序,并計算網絡序號與加密數據的對應關系表;

(5) LBSs將擾亂的Es(P)發送給LCS,將對應關系表發送給查詢用戶;

(6) 用戶根據對應關系表計算自身網格對應的數據元素序號j,向LCS檢索第j個數據;

(7) LCS向用戶發送Es(Pj);

(8) 用戶解密后獲得最終結果。

圖4 網格匿名查詢Fig.4 Grid anonymous query

2.3 隱私性分析

匿名性、位置軌跡不可追蹤性和身份不可鏈接性是度量隱私保護水平的主要指標,相關的研究工作都是圍繞這3個指標來探討LBS隱私保護技術的隱私保護能力。在本文方法中,移動用戶、LCS和LBSs都是半可信的。首先,用戶沒有暴露具體的位置數據給LCS和LBSs,滿足位置軌跡不可追蹤性。其次,LCS通過隨機網格匿名實現了位置k-匿名,滿足了身份不可鏈接性。最后,通過非對稱加密方法保證了LBSs資源不被LCS惡意竊取。

3 仿真實驗

通信量和計算時間是衡量LBS系統可用性的重要性能指標。本文對所提出的方法和基于位置k-匿名的兩種經典方法HC[14]和隱私網格(privacy grid,PG)[9]進行比較分析,闡述隨機網格匿名方法的可用性。實驗使用C#語言編寫匿名算法和網格匿名查詢,程序在Intel 酷睿i5處理器,4GB內存的Windows7平臺上運行。移動對象數據集以城市Oldenburg為例,由網絡移動目標生成器(network-based generator of moving objects,NGMO)生成。默認參數值如表1所示。

表1 實驗參數表

第1個實驗測試網格大小對隱私度的影響。如圖5所示,如果網格太小,在連續查詢過程中,LCS能夠追蹤用戶的行動軌跡,原因是網格內的移動用戶數量無法保證,進而無法保障用戶隱私;如果網格過大,雖然可以保證匿名度,但是增加了LBSs的計算量和通信量。

圖5 網格對隱私度的影響Fig.5 Effect of grid on privacy

本文采用動態調整網格方式解決以上問題,如圖6所示,LCS根據用戶位置更新情況,動態合并移動用戶數量少的網格,并定期向用戶發布。利用動態網格解決當前區域用戶數量過少對匿名效果的影響問題。

圖6 動態網格Fig.6 Dynamic grid

第2個實驗測試匿名網格數量對通信量(候選POIs的數量)和計算量(平均計算時間)的影響。如圖7所示,隨著匿名網格數量的增加,3種方法的候選POIs的數量和平均計算時間都線性增長,隨機網格隱匿(random grid cloak ,RGC)方法所受影響更大。這是符合現實情況的,用戶要求的隱私度越高,即匿名網格的數量越多,隱私度提高的同時降低了LBS系統運行的性能。

圖7 匿名網格的影響Fig.7 Impact of anonymous grid

第3個實驗測試匿名度k對通信量(候選POIs的數量)和計算量(平均計算時間)的影響。如圖8所示,隨著k值的增加,3種方法的候選POIs的數量和平均計算時間都線性增長,RGC方法變化不大。原因是RGC方法容易實現位置匿名,而且在有大量用戶的環境下匿名區域受k值的影響很小。

圖8 匿名度的影響Fig.8 Impact of anonymous degree

第4個實驗測試用戶數量N對通信量(候選POIs的數量)和計算量(平均計算時間)的影響。如圖9所示,隨著N值增加,3種方法的候選POIs數量和平均計算時間都線性減少,RGC方法變化不大。原因是用戶數量遠大于用戶的匿名度的要求。

圖9 用戶數量的影響Fig.9 Impact of user number

由此可見,本文所提出的算法通過隨機網格較好地解決了當前區域用戶數量對匿名效果的影響問題,同時在保護用戶隱私的前提下更適合在真實環境中提供較高的服務質量。

4 結 論

當前位置隱私的研究主要基于權衡服務質量和隱私保護能力,這種“零和博弈”的觀點促使位置k-匿名和位置模糊技術成為該問題研究的主流。然而,定期更新位置信息逐漸成為中心服務器結構的根本瓶頸,而且在現實情況下假設參與匿名的各方均可信也是不現實的,匿名參與者可能直接或間接泄露精確的位置信息。針對這樣的實際問題,本文提出了基于隨機網格的位置隱私保護方法,該方法包括位置更新算法、位置匿名算法和匿名查詢過程,利用網格化的不確定性實現了連續查詢過程中的軌跡不可追蹤性和身份不可關聯性。同時,本文針對所提出的方法在效率和服務質量方面進行了分析和實驗驗證,進一步證明了所提出方法的隱私保護能力和實際部署下的算法執行效率。

[1] 周傲英,楊彬,金澈清.基于位置的服務_架構與進展[J].計算機學報,2011,34(7): 1156-1171.

ZHOU A Y,YANG B,JIN C Q.Location-based services: architecture and progress[J]. Chinese Journal of Computers, 2011,34(7): 156-1171.

[2] 王璐,孟小峰.位置大數據隱私保護研究綜述[J].軟件學報,2014,25(4): 693-712.

WANG L, MENG X F. Location privacy preservation in big data era: a survey[J]. Journal of Software, 2014, 25(4): 693-712.

[3] 馮登國,張敏,李昊.大數據安全與隱私保護[J].計算機學報,2014,37(1): 246-258.

FENG D G, ZHANG M, LI H. Big data security and privacy protection[J].Chinese Journal of Computers, 2014,37(1): 246-258.

[4] ACQUISTI A, BRANDIMARTE L, LOEWENSTEIN G. Privacy and human behavior in the age of information[J].Science,2015,347(6221):509-514.

[5] 張磊, 馬春光, 楊松濤, 等. 基于輪廓泛化的位置隱私保護模型及方法[J]. 系統工程與電子技術, 2016, 38(12): 2894-900.

ZHANG L, MA C G, YANG S T, et al. Location privacy protection model and algorithm based on profiles generalization[J]. Systems Engineering and Electronics, 2016, 38(12): 2894-900.

[6] NERGIZ M E, GOK M Z. Hybrid k-anonymity[J]. Computers & Security, 2014,44(2): 51-63.

[7] SCHLEGEL R,CHOW C Y,Huang Q, et al. User-defined privacy grid system for continuous location-based services[J]. IEEE Trans.on Mobile Computing, 2015, 14(10):2158-2172.

[8] NI W, GU M, CHEN X. Location privacy-preserving k nearest neighbor query under user's preference[J]. Knowledge-Based Systems, 2016, 103(2016): 19-27.

[9] MOU L, LBATH A. A grid-based location privacy-preserving method for LBS users[C]∥Proc.of the Acm Sigspatial International Workshop on Privacy in Geographic Information Collection and Analysis,2014:1-4.

[10] HARA T, SUZUKI A, IWATA M, et al. Dummy-based user location anonymization under real-world constraints[J]. IEEE Access, 2016, 4(2016)673-687.

[11] DARGAHI T, AMBROSIN M, CONTI M, et al. ABAKA: a novel attribute-basedk-anonymous collaborative solution for LBSs[J].Computer Communications,2016,85:1-13.

[12] MA C G, ZHANG L, YANG S T, et al. Achieve personalized anonymity through query blocks exchanging[J]. China Communications, 2016, 13(11):106-118.

[13] 吳云乘, 陳紅, 趙素云, 等.一種基于時空相關性的差分隱私軌跡保護機制[J]. 計算機學報, 2017.http:∥kns.cnki.net/kcms/detail /11.1826.TP.20170328.2325.004.html.

WU Y C, CHEN H, ZHAO S Y, et al. Differentially private trajectory protection based on spatial and temporal correlation[J]. Chinese Journal of Computers, 2017.http:∥kns.cnki.net/kcms/ detail /11.1826.TP.20170328.2325.004.html.

[14] PENG T, LIU Q, WANG G J. Enhanced location privacy preserving scheme in location-based services[J]. IEEE Systems Journal, 2017, 11(1):219-230.

[15] MEYEROWITZ J, CHOUDHURY R R. Hiding stars with fireworks: location privacy through camouflage[C]∥Proc.of the 15th Annual International Conference on Mobile Computing and Networking, 2009:345-356.

[16] 黃毅,霍崢,孟小峰. CoPrivacy:一種用戶協作無匿名區域的位置隱私保護方法[J].計算機學報,2011, 34(10): 1976-1985.

HUANG Y, HUO Z,MENG X F. CoPrivacy: a collaborative location privacy-preserving method without cloaking region[J]. Chinese Journal of Computers, 2011, 34(10): 1976-1985.

[17] LEI P R, PENG W C, SU I J, et al. Dummy-based schemes for protecting movement trajectories[J]. Information Science and Engineering, 2012, 28(2): 335-350.