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

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

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

0 引 言

移動用戶在申請連續(xù)位置服務(wù)時產(chǎn)生的連續(xù)位置可按時間序列鏈接成位置軌跡,位置軌跡含有多種時空信息,可被攻擊者利用進(jìn)而獲取用戶的個人隱私。這種情況限制了基于快照服務(wù)的隱私保護(hù)方法[1-4]的保護(hù)效力。為有效保護(hù)位置軌跡隱私,研究者們提出了大量的隱私保護(hù)方法。在現(xiàn)有方法中主要存在兩種方案[5]:一種將位置軌跡與其他相似軌跡泛化[6-10]模糊真實軌跡;另一種則在假設(shè)攻擊者已獲得部分子軌跡的前提下,通過擾亂或模糊軌跡后續(xù)位置降低攻擊者識別出用戶的概率[11-16]。其中相似軌跡泛化方案存在歷史軌跡的時間差異可用于剔除部分匿名軌跡[7];協(xié)作軌跡因分布范圍易被識別[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ù)最近鄰查詢,其移動通信設(shè)備計算能力有限,本文采用如圖1所示的3層中心服務(wù)器架構(gòu)。該架構(gòu)包含3個實體:移動用戶(mobileuser,U),中心服務(wù)器(centralservers,CS),服務(wù)提供商(locationserviceprovider,LSP)。U攜帶定位設(shè)備(例如:智能手機、GPS定位器等),能夠精確定位并與LSP交互,但其通信和計算能力有限。CS負(fù)責(zé)輪廓信息計算,具有較強的計算和數(shù)據(jù)處理能力。LSP為User或CS提供服務(wù),具有極強的數(shù)據(jù)分析和處理能力。本文假設(shè)U和CS是可信的LSP是半可信的,即LSP在嚴(yán)格執(zhí)行協(xié)議和算法的前提下,同時使用收集到的位置和背景知識推斷U的敏感信息,甚至LSP可能將U的敏感信息出賣給不友好的第三方。

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

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

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

定義 2 用戶輪廓信息是指具有用戶特征的唯一標(biāo)識指定用戶的基本信息,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)攻擊可通過輪廓相似度來描述。對不確定位置集合S中的任一位置l′,其用戶輪廓的關(guān)聯(lián)概率p可表示為已知子軌跡L中的位置l與不確定性位置l′之間的相似程度,于是有

(1)

(2)

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

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

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

), 0≤p≤1

(3)

相似度sim可表示為

(4)

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

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

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

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中所示加以計算。其中對于不可到達(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;∥校驗所有不可到達(dá)位置

10end

11if(c==Ur.count)

13end

14 ++i;

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

16break;

17end

18end

2 性能評估

2.1 隱私度量與性能分析

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

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

(5)

(6)

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

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

?0

(7)

(8)

(9)

(10)

證畢

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

2.2 實驗設(shè)定

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

表1 實驗參數(shù)閾值設(shè)定表

3 實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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]. 計算機學(xué)報, 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. (楊松濤, 馬春光, 周長利. 面向LBS的隱私保護(hù)模型及方案[J]. 通信學(xué)報, 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。

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

TP

A

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

張 磊(1982-),男,講師,博士研究生,主要研究方向為信息安全、位置隱私保護(hù)。

E-mail:8213662@163.com

馬春光(1974-),男,教授,博士,主要研究方向為密碼學(xué)、信息安全。

E-mail:machunguang@hrbeu.edu.cn

楊松濤(1974-),男,副教授,博士,主要研究方向為信息安全、隱私保護(hù)。

E-mail:songtao_y@163.com

鄭曉東(1981-),女,講師,博士研究生,主要研究方向為信息安全、隱私保護(hù)。

E-mail:lnxiaodong@126.com

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