基于輪廓泛化的位置隱私保護(hù)模型及方法

張 磊, 馬春光, 楊松濤, 鄭曉東,3

(1. 哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 黑龍江 哈爾濱 150001; 2. 佳木斯大學(xué)信息電子技術(shù)學(xué)院,黑龍江 佳木斯 154007; 3. 齊齊哈爾大學(xué)應(yīng)用技術(shù)學(xué)院, 黑龍江 齊齊哈爾 161006)

?

基于輪廓泛化的位置隱私保護(hù)模型及方法

張 磊1,2, 馬春光1, 楊松濤1,2, 鄭曉東1,3

(1. 哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 黑龍江 哈爾濱 150001; 2. 佳木斯大學(xué)信息電子技術(shù)學(xué)院,黑龍江 佳木斯 154007; 3. 齊齊哈爾大學(xué)應(yīng)用技術(shù)學(xué)院, 黑龍江 齊齊哈爾 161006)

連續(xù)位置服務(wù); 隱私保護(hù); 用戶輪廓信息; 關(guān)聯(lián)攻擊

0 引 言

移動(dòng)用戶在申請(qǐng)連續(xù)位置服務(wù)時(shí)產(chǎn)生的連續(xù)位置可按時(shí)間序列鏈接成位置軌跡,位置軌跡含有多種時(shí)空信息,可被攻擊者利用進(jìn)而獲取用戶的個(gè)人隱私。這種情況限制了基于快照服務(wù)的隱私保護(hù)方法[1-4]的保護(hù)效力。為有效保護(hù)位置軌跡隱私,研究者們提出了大量的隱私保護(hù)方法。在現(xiàn)有方法中主要存在兩種方案[5]:一種將位置軌跡與其他相似軌跡泛化[6-10]模糊真實(shí)軌跡;另一種則在假設(shè)攻擊者已獲得部分子軌跡的前提下,通過擾亂或模糊軌跡后續(xù)位置降低攻擊者識(shí)別出用戶的概率[11-16]。其中相似軌跡泛化方案存在歷史軌跡的時(shí)間差異可用于剔除部分匿名軌跡[7];協(xié)作軌跡因分布范圍易被識(shí)別[8];單一匿名框泛化導(dǎo)致服務(wù)質(zhì)量降低等問題[9-10]。因此,研究更傾向于擾亂或模糊后續(xù)位置的方法。

1 隱私保護(hù)模型及攻擊方法

1.1 系統(tǒng)架構(gòu)及攻擊模型

由于IRDA主要應(yīng)用于歐氏空間或路網(wǎng)環(huán)境下的位置導(dǎo)航以及連續(xù)最近鄰查詢,其移動(dòng)通信設(shè)備計(jì)算能力有限,本文采用如圖1所示的3層中心服務(wù)器架構(gòu)。該架構(gòu)包含3個(gè)實(shí)體:移動(dòng)用戶(mobileuser,U),中心服務(wù)器(centralservers,CS),服務(wù)提供商(locationserviceprovider,LSP)。U攜帶定位設(shè)備(例如:智能手機(jī)、GPS定位器等),能夠精確定位并與LSP交互,但其通信和計(jì)算能力有限。CS負(fù)責(zé)輪廓信息計(jì)算,具有較強(qiáng)的計(jì)算和數(shù)據(jù)處理能力。LSP為User或CS提供服務(wù),具有極強(qiáng)的數(shù)據(jù)分析和處理能力。本文假設(shè)U和CS是可信的LSP是半可信的,即LSP在嚴(yán)格執(zhí)行協(xié)議和算法的前提下,同時(shí)使用收集到的位置和背景知識(shí)推斷U的敏感信息,甚至LSP可能將U的敏感信息出賣給不友好的第三方。

圖1 3層系統(tǒng)架構(gòu)示意圖Fig.1 System structure of three entities

為了后繼內(nèi)容的表述,本文對(duì)相關(guān)術(shù)語(yǔ)給出如下定義。

定義 1 連續(xù)位置服務(wù)是指用戶User向LSP發(fā)起的連續(xù)基于位置服務(wù)申請(qǐng),可表示為R=(ID, Li, t, C)。其中:ID表示用戶的身份標(biāo)識(shí)或假名;Li=(xi, yi)表示當(dāng)前申請(qǐng)所處的位置;t表示時(shí)間間隔;C表示服務(wù)申請(qǐng)內(nèi)容,如:查詢最近的餐廳、加油站等。

定義 2 用戶輪廓信息是指具有用戶特征的唯一標(biāo)識(shí)指定用戶的基本信息,n種不同的用戶輪廓信息可表示為PRO={pro1, pro2, …, pron}。

定義 3 輪廓關(guān)聯(lián)攻擊是指攻擊者通過掌握的用戶子軌跡L,從中獲取當(dāng)前用戶的輪廓信息PRO,并進(jìn)一步關(guān)聯(lián)后續(xù)服務(wù)中的不確定位置,獲得用戶完整軌跡T的攻擊方法。

輪廓關(guān)聯(lián)攻擊可通過輪廓相似度來(lái)描述。對(duì)不確定位置集合S中的任一位置l′,其用戶輪廓的關(guān)聯(lián)概率p可表示為已知子軌跡L中的位置l與不確定性位置l′之間的相似程度,于是有

(1)

(2)

式中,v表示輪廓信息數(shù)值;min和max分別表示最小和最大值。當(dāng)p=1時(shí)表示兩個(gè)位置屬于同一軌跡T。

在實(shí)際環(huán)境中攻擊者計(jì)算得到的p可能低于預(yù)期,此時(shí),還可以通過排除不確定位置集合S中其他位置與l之間的關(guān)聯(lián)概率較低的位置來(lái)識(shí)別真實(shí)位置。

1.2 隱私保護(hù)模型及方法

), 0≤p≤1

(3)

相似度sim可表示為

(4)

算法 1 相似輪廓信息的虛假位置生成

輸入 l, l′,k,n,θ

輸出 S′∥2k-1個(gè)虛假位置集合

1 S=randomchosen4klocation;∥初始位置集

2 i=0;

3while(i<=S.count)

6for(j=1;j<=n;++j)

9end

13end

14 ++i;

15if(S′.count>=2k-1)

16break;

17end

18end

第二階段,剔除備選位置集合S′中不可到達(dá)的位置。篩選過程可按照算法2中所示加以計(jì)算。其中對(duì)于不可到達(dá)位置的判斷,采用生成位置與不可到達(dá)位置集合Ur的方法。

算法 2 提交位置篩選

輸入 Ur,S′∥不可到達(dá)位置集合

輸出 S″∥篩選后的虛假位置集合

1 i=0;

2while(i<=S′.count)

4for(j=1:j<=Ur.count;++j)

5 c=0;

7break;

8end

9 c=c+1;∥校驗(yàn)所有不可到達(dá)位置

10end

11if(c==Ur.count)

13end

14 ++i;

15if(S″.count>=k-1)

16break;

17end

18end

2 性能評(píng)估

2.1 隱私度量與性能分析

由式(1)可知,攻擊者根據(jù)輪廓相似程度判斷某一位置是否屬于該用戶,進(jìn)而用戶輪廓關(guān)聯(lián)概率可用條件概率表示,于是有

p(l′)=p(l′∈T|PROl′=PROT)

(5)

(6)

為驗(yàn)證IRDA能夠取得最大熵,假設(shè)一個(gè)在挑戰(zhàn)者A與用戶U之間的雙方博弈。A指定一個(gè)區(qū)域給U,U選定一段連續(xù)的位置T,將T中前n-1個(gè)位置發(fā)送給A,同時(shí)根據(jù)最后一個(gè)位置的輪廓信息,生成具有相似輪廓的k-1個(gè)虛假位置,U將虛假位置與最后一個(gè)位置建立集合S″后發(fā)送給A。A在集合S″中識(shí)別出T的最后位置,則A獲勝。由以上博弈可以得出如下定義。

定義 5 若隱私保護(hù)方法可抵抗輪廓關(guān)聯(lián)攻擊,當(dāng)且僅當(dāng)對(duì)于匿名集合中任意兩個(gè)位置存在

?0

(7)

(8)

(9)

(10)

證畢

IRDA算法的時(shí)間復(fù)雜度主要取決于算法1和算法2表示的虛假位置生成和篩選兩個(gè)階段。算法1中的計(jì)算量取決于用戶選擇的k值與輪廓信息數(shù)量,其時(shí)間復(fù)雜度為O(4kn)=O(kn)。算法2的計(jì)算量取決于不可到達(dá)位置和生成位置數(shù)量,在最壞的情況下若不可到達(dá)位置為m,則該算法的時(shí)間復(fù)雜度為O(2km)=O(km)。而在最好的情況下無(wú)不可到達(dá)位置,則該時(shí)間復(fù)雜度為O(k)。由此可得IRDA的平均時(shí)間復(fù)雜度位于O(k)與O(kn+km)之間。

2.2 實(shí)驗(yàn)設(shè)定

為驗(yàn)證IRDA的效力與效率,本文將所涉及的算法在Windows7上使用Matlab7加以模擬。實(shí)驗(yàn)運(yùn)行環(huán)境為1.70GHzIntelCorei5,內(nèi)存大小為4GB。實(shí)驗(yàn)數(shù)據(jù)集采用BerlinMODDataSet1真實(shí)數(shù)據(jù)集中的城市中心區(qū)域,以獲取較多的申請(qǐng)用戶,并假設(shè)存在足夠的CS提供保護(hù)服務(wù)。表1為實(shí)驗(yàn)中采用的相關(guān)參數(shù)閾值設(shè)定。

表1 實(shí)驗(yàn)參數(shù)閾值設(shè)定表

3 實(shí)驗(yàn)結(jié)果

圖2展示了在攻擊者掌握包括用戶ID、服務(wù)時(shí)間間隔、服務(wù)內(nèi)容、運(yùn)動(dòng)模式和查詢概率等情況下,不同隱私保護(hù)方法的隱私保護(hù)熵。從該圖中可以看出,CLAPPINQ和mix-zone的取值較低,這是由于這兩種方法對(duì)連續(xù)位置服務(wù)中的時(shí)間間隔和服務(wù)內(nèi)容的隱私保護(hù)程度相對(duì)較差。enhanced-DLS由于添加了對(duì)不同位置查詢概率情況的考慮,其隱私保護(hù)效果相對(duì)較好,但這種方法主要針對(duì)快照服務(wù),其抵抗關(guān)聯(lián)攻擊的能力在連續(xù)服務(wù)中表現(xiàn)較差。Snet由于服務(wù)時(shí)間間隔和內(nèi)容并不能同時(shí)模糊,所以其熵相對(duì)較低。LTTPM的協(xié)作用戶輪廓與真實(shí)用戶相似度較高,但在連續(xù)服務(wù)過程中存在部分用戶輪廓可被攻擊者關(guān)聯(lián)的情況。IRDA由于本身針對(duì)用戶輪廓信息關(guān)聯(lián)攻擊所設(shè)計(jì),充分考慮可能存在的用戶輪廓信息,具有最好的隱私保護(hù)效果。

圖2 不同算法的熵比較Fig.2 Entropy of various algorithms

從圖3中可以看出各算法的匿名用戶識(shí)別率。其中,由于真實(shí)軌跡被協(xié)作軌跡所包圍,使得LTTPM方法的識(shí)別率最高。CLAPPINQ和Snet算法由于連續(xù)查詢過程中的匿名用戶差異增加識(shí)別的概率。enhanced-DLS算法擴(kuò)大了用戶間距,在一定程度上增加了識(shí)別難度,但是在連續(xù)匿名過程中,仍可以通過用戶輪廓加以關(guān)聯(lián)識(shí)別。mix-zone通過不可探測(cè)區(qū)域切斷了部分輪廓關(guān)聯(lián),但是仍存在其他輪廓信息可被使用的情況。最后,IRDA使每個(gè)生成的虛假用戶具有與真實(shí)用戶相似的輪廓信息,最大程度地模糊了用戶之間的差異,其匿名用戶識(shí)別概率最低。

圖3 隨匿名值變化的匿名用戶識(shí)別率Fig.3 Identification ratio with k

圖4 隨匿名值變化的隱私保護(hù)成功率Fig.4 Success ratio with k

圖5 隨申請(qǐng)人數(shù)變化的隱私保護(hù)成功率Fig.5 Success ratio with Sr

為驗(yàn)證隱私保護(hù)成功率,本文假設(shè)10人同時(shí)申請(qǐng)隱私保護(hù),協(xié)作用戶為當(dāng)前區(qū)域人數(shù)的1/2。此時(shí),隨用戶申請(qǐng)匿名值增加而產(chǎn)生的隱私保護(hù)的成功率變化如圖4所示。從該圖中可看出,由于LTTPM需要依靠協(xié)作用戶來(lái)完成匿名,因此其隱私保護(hù)成功率相對(duì)較低。CLAPPINQ和mix-zone只需找到對(duì)應(yīng)用戶即可完成匿名,其隱私保護(hù)成功率好于LTTPM。Snet通過建立模糊路段來(lái)保護(hù)用戶隱私,其隱私保護(hù)成功率取決于當(dāng)前路段是否能抽象為更高層次的路段,當(dāng)該路段不存在相似路段可進(jìn)行路段抽象情況下,算法執(zhí)行失敗。最后,enhanced-DLS和IRDA方法由于采用生成虛假位置機(jī)制,使得在匿名過程中不受真實(shí)用戶數(shù)量的限制,在隱私保護(hù)成功率上具有較好的表現(xiàn)。圖5展示了在限定用戶匿名度閾值情況下隨申請(qǐng)人數(shù)變化的隱私保護(hù)成功率變化。從該圖中可以看出,隨申請(qǐng)人數(shù)變化的隱私保護(hù)成功率逐漸降低,其基本原因與隨匿名值變化的隱私保護(hù)成功率變化相似。

圖6展示了隨用戶設(shè)定的匿名度閾值增長(zhǎng)各算法的執(zhí)行時(shí)間變化。其中LTTPM由于不需對(duì)匿名用戶進(jìn)行篩選,算法可在最短的時(shí)間內(nèi)完成。Snet和mix-zone不需隨匿名值變化而改變模糊區(qū)域以及混淆空間,因此其執(zhí)行時(shí)間固定。enhanced-DLS由于需要對(duì)每個(gè)生成的假位置考慮該位置存在的查詢概率,其執(zhí)行時(shí)間隨匿名值的增加變化較大。而IRDA由于需要提取用戶的輪廓信息,并同時(shí)建立虛假生成位置,其執(zhí)行時(shí)間受匿名值變化影響最大。

圖6 隨匿名值變化的執(zhí)行時(shí)間Fig.6 Execute time with k

圖7 隨申請(qǐng)人數(shù)變化的執(zhí)行時(shí)間Fig.7 Execute time with Sr

圖7展示了各算法隨申請(qǐng)人數(shù)變化的執(zhí)行時(shí)間差異。CLAPPINQ算法的執(zhí)行時(shí)間隨著申請(qǐng)人數(shù)的增加變化最大,該方法需要預(yù)計(jì)算所有用戶的興趣點(diǎn),導(dǎo)致隨著申請(qǐng)用戶數(shù)量的增加,預(yù)計(jì)算的計(jì)算量增長(zhǎng),因此其執(zhí)行時(shí)間隨著申請(qǐng)用戶數(shù)量的變化呈線性增長(zhǎng)。其次,mix-zone的執(zhí)行時(shí)間高于Snet的執(zhí)行時(shí)間,這是由于隨著申請(qǐng)人數(shù)的增加,mix-zone中不同申請(qǐng)用戶的時(shí)間耽擱選擇不同,使得算法需保持所有用戶的最大耽擱時(shí)間,進(jìn)而其結(jié)果高于直接生成模糊區(qū)域的Snet方法。最后,IRDA方法的執(zhí)行時(shí)間相對(duì)較低,這是由于生成的部分虛假位置具有與其他申請(qǐng)用戶相似的輪廓信息,對(duì)于生成虛假位置的復(fù)用降低了算法的執(zhí)行時(shí)間。

圖8 隨輪廓信息變化的執(zhí)行時(shí)間Fig.8 Execute time with n

從圖8中可以看出Snet和mix-zone方法并未考慮輪廓信息關(guān)聯(lián)攻擊,其執(zhí)行時(shí)間不隨輪廓信息的增加而變化。IRDA方法由于考慮到用戶的不同輪廓信息,在輪廓數(shù)量增加的情況下,其執(zhí)行時(shí)間相應(yīng)的線性增長(zhǎng)。而其他方法由于只針對(duì)部分輪廓信息,隨著輪廓信息數(shù)量的增加,提出的輪廓信息在超過其所能處理的最大數(shù)量時(shí),其執(zhí)行時(shí)間不再變化。

4 結(jié) 論

[1]GruteserM,GrunwaldD.Anonymoususageoflocation-basedservicesthroughspatialandtemporalcloaking[C]∥Proc.of the International Conference on Mobile Systems,2003:31-42.

[2]LiuF,HuaKA,CaiY.Queryl-diversityinlocation-basedservices[C]∥Proc.of the IEEE Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, 2009:436-442.

[3]KhoshgozaranA,ShahabiC.Privateinformationretrievaltechniquesforenablinglocationprivacyinlocation-basedservices[M]∥Privacy in Location-Based Applications.NewYork:Springer-Verlag, 2009:59-83.

[4]Rebollo-MonederoD,ForneJ,Domingo-FerrerJ.Queryprofileobfuscationbymeansofoptimalqueryexchangebetweenusers[J]. IEEE Trans.on Dependable and Secure Computing, 2012, 9(5): 641-654.

[5]MaCG,ZhangL,YangST.Reviewonlocationtrajectoryprivacyprotection[J]. Netinfo Security,2015(10):24-31.(馬春光, 張磊, 楊松濤. 位置軌跡隱私保護(hù)綜述[J]. 信息網(wǎng)絡(luò)安全, 2015(10): 24-31.)

[6]KatoR,IwataM,HaraT,etal.Adummy-basedanonymizationmethodbasedonusertrajectorywithpauses[C]∥Proc.of the International Conference on Advances in Geographic Information Systems,2012:249-258.

[7]GaoS,MaJF,ShiWS,etal.LTPPM:alocationandtrajectoryprivacyprotectionmechanisminparticipatorysensing[J]. Wireless Communications & Mobile Computing, 2015, 15(1): 155-169.

[8]HwangRH,HsuehYL,ChungHW.Anoveltime-obfuscatedalgorithmfortrajectoryprivacyprotection[J]. IEEE Trans.on Services Computing, 2014, 7(2): 126-139.

[9]PanX,XuJ,MengX.Protectinglocationprivacyagainstlocation-dependentattacksinmobileservices[J]. IEEE Trans.on Knowledge and Data Engineering, 2012, 24(8): 1506-1519.

[10]XueJ,LiuXY,YangXC,etal.ALocationPrivacyPreservingApproachonRoadNetwork[J]. Chinese Journal of Computers, 2011, 34(5): 865-878. (薛姣, 劉向宇, 楊曉春, 等. 一種面向公路網(wǎng)絡(luò)的位置隱私保護(hù)方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(5): 865-878.)

[11]MaCG,ZhouCL,YangST.Avoronoi-basedLocationprivacy-preservingmethodforcontinuousqueryinLBS[J]. International Journal of Distributed Sensor Networks, 2015(1): 1-17.

[12]HashemT,KulikL,ZhangR.CounteringoverlappingrectangleprivacyattackformovingkNNqueries[J]. Information Systems, 2013, 38(3): 430-453.

[13]YangST,MaCG,ZhouCL.LBS-orientedlocationprivacyprotectionmodelandscheme[J]. Journal on Communications, 2014, 35(8): 116-124. (楊松濤, 馬春光, 周長(zhǎng)利. 面向LBS的隱私保護(hù)模型及方案[J]. 通信學(xué)報(bào), 2014, 35(8): 116-124.)

[14]PalanisamyB,LiuL,LeeK,etal.Anonymizingcontinuousquerieswithdelay-tolerantmix-zonesoverroadnetworks[J]. Distributed and Parallel Databases, 2014, 32(1): 91-118.

[15]PalanisamyB,LiuL.Attack-resilientmix-zonesoverroadnetworks:architectureandalgorithms[J]. IEEE Trans.on Mobile Computing, 2015, 14(3): 495-508.

[16]WangY,XiaY,HouJ,etal.Afastprivacy-preservingframeworkforcontinuouslocation-basedqueriesinroadnetworks[J].Journal of Network and Computer Applications, 2015, 53: 57-73.

[17]NiuB,LiQ,ZhuX,etal.Enhancingprivacythroughcachinginlocation-basedservices[C]∥Proc.of the IEEE Computer Communications, 2015:1017-1025.

[18]HaraT,SuzukiA,IwataM,etal.Dummy-baseduserlocationanonymizationunderreal-worldconstraints[J]. IEEE Access,2016, 4:673-687.

Location privacy protection model and algorithm based on profiles generalization

ZHANG Lei1,2, MA Chun-guang1, YANG Song-tao1,2, ZHENG Xiao-dong1,3

(1.CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001,China;2.CollegeofInformationandElectronicTechnology,JiamusiUniversity,Jiamusi154007,China;3.CollegeofAppliedTechnology,QiqiharUniversity,Qiqihar161006,China)

location-based service; privacy preservation; user profiles; correlation attack

2016-06-01;

2016-08-02;網(wǎng)絡(luò)優(yōu)先出版日期:2016-10-21。

國(guó)家自然科學(xué)基金(61472097);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20132304110017);黑龍江省自然科學(xué)基金(F2015022) 資助課題

TP

A

10.3969/j.issn.1001-506X.2016.12.32

張 磊(1982-),男,講師,博士研究生,主要研究方向?yàn)樾畔踩?、位置隱私保護(hù)。

E-mail:8213662@163.com

馬春光(1974-),男,教授,博士,主要研究方向?yàn)槊艽a學(xué)、信息安全。

E-mail:machunguang@hrbeu.edu.cn

楊松濤(1974-),男,副教授,博士,主要研究方向?yàn)樾畔踩?、隱私保護(hù)。

E-mail:songtao_y@163.com

鄭曉東(1981-),女,講師,博士研究生,主要研究方向?yàn)樾畔踩?、隱私保護(hù)。

E-mail:lnxiaodong@126.com

網(wǎng)絡(luò)優(yōu)先出版地址:http:∥www.cnki.net/kcms/detail/11.2422.TN.20161021.1059.010.html