基于隨機網(wǎng)格的位置隱私保護方法

楊松濤, 王慧強, 馬春光

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

0 引 言

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

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

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

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

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

1 系統(tǒng)模型

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

圖1 LBS系統(tǒng)結(jié)構(gòu)Fig.1 System architecture of LBS

依照圖1所示的系統(tǒng)模型,可確定以下4個基本假設(shè):

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

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

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

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

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

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

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

(1)

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

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

2 基于網(wǎng)格的位置隱匿方法

2.1 網(wǎng)格內(nèi)用戶數(shù)量的更新過程

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

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

圖2 網(wǎng)格圖Fig.2 Grid chart

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

算法1位置更新算法

(1) 初始化狀態(tài),所有節(jié)點向LCS更新所在網(wǎng)格的信息;

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

(3) 計算節(jié)點所在的網(wǎng)格;

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

(5) 依據(jù)位置樹計算網(wǎng)格內(nèi)的節(jié)點數(shù)量;

(6) 向LCS更新網(wǎng)格內(nèi)的移動用戶數(shù)量。

圖3 位置更新Fig.3 Location update

2.2 網(wǎng)格匿名查詢過程

本文采用多個隨機的、離散的網(wǎng)格實現(xiàn)位置k-匿名、網(wǎng)格l-多樣性和位置模糊的目的。

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

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

(2)

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

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

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

(3)

式中,{gi,…,gi+l}代表隨機網(wǎng)格的集合。

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

Sq=(uid,s,t)

(4)

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

根據(jù)以上定義可得到隨機網(wǎng)格位置匿名算法,該算法在LCS內(nèi)執(zhí)行。

算法2隨機網(wǎng)格位置匿名算法

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

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

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

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

如圖4所示,網(wǎng)格匿名查詢過程如下:

(1) 用戶向LCS發(fā)出網(wǎng)格查詢Gq,同時向LBSs發(fā)出標(biāo)記查詢Sq;

(2) LCS執(zhí)行網(wǎng)格位置匿名算法;

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

(4) LBSs使用用戶提供的密鑰加密Es(P)={Es(pi),…,Es(pi+l)},擾亂Es(P)內(nèi)元素順序,并計算網(wǎng)絡(luò)序號與加密數(shù)據(jù)的對應(yīng)關(guān)系表;

(5) LBSs將擾亂的Es(P)發(fā)送給LCS,將對應(yīng)關(guān)系表發(fā)送給查詢用戶;

(6) 用戶根據(jù)對應(yīng)關(guān)系表計算自身網(wǎng)格對應(yīng)的數(shù)據(jù)元素序號j,向LCS檢索第j個數(shù)據(jù);

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

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

圖4 網(wǎng)格匿名查詢Fig.4 Grid anonymous query

2.3 隱私性分析

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

3 仿真實驗

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

表1 實驗參數(shù)表

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

圖5 網(wǎng)格對隱私度的影響Fig.5 Effect of grid on privacy

本文采用動態(tài)調(diào)整網(wǎng)格方式解決以上問題,如圖6所示,LCS根據(jù)用戶位置更新情況,動態(tài)合并移動用戶數(shù)量少的網(wǎng)格,并定期向用戶發(fā)布。利用動態(tài)網(wǎng)格解決當(dāng)前區(qū)域用戶數(shù)量過少對匿名效果的影響問題。

圖6 動態(tài)網(wǎng)格Fig.6 Dynamic grid

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

圖7 匿名網(wǎng)格的影響Fig.7 Impact of anonymous grid

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

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

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

圖9 用戶數(shù)量的影響Fig.9 Impact of user number

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

4 結(jié) 論

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

[1] 周傲英,楊彬,金澈清.基于位置的服務(wù)_架構(gòu)與進展[J].計算機學(xué)報,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] 王璐,孟小峰.位置大數(shù)據(jù)隱私保護研究綜述[J].軟件學(xué)報,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] 馮登國,張敏,李昊.大數(shù)據(jù)安全與隱私保護[J].計算機學(xué)報,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]. 系統(tǒng)工程與電子技術(shù), 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] 吳云乘, 陳紅, 趙素云, 等.一種基于時空相關(guān)性的差分隱私軌跡保護機制[J]. 計算機學(xué)報, 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:一種用戶協(xié)作無匿名區(qū)域的位置隱私保護方法[J].計算機學(xué)報,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.