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

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

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

?

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

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

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

連續位置服務; 隱私保護; 用戶輪廓信息; 關聯攻擊

0 引 言

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

1 隱私保護模型及攻擊方法

1.1 系統架構及攻擊模型

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

圖1 3層系統架構示意圖Fig.1 System structure of three entities

為了后繼內容的表述,本文對相關術語給出如下定義。

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

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

定義 3 輪廓關聯攻擊是指攻擊者通過掌握的用戶子軌跡L,從中獲取當前用戶的輪廓信息PRO,并進一步關聯后續服務中的不確定位置,獲得用戶完整軌跡T的攻擊方法。

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

(1)

(2)

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

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

1.2 隱私保護模型及方法

), 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′中不可到達的位置。篩選過程可按照算法2中所示加以計算。其中對于不可到達位置的判斷,采用生成位置與不可到達位置集合Ur的方法。

算法 2 提交位置篩選

輸入 Ur,S′∥不可到達位置集合

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

1 i=0;

2while(i<=S′.count)

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

5 c=0;

7break;

8end

9 c=c+1;∥校驗所有不可到達位置

10end

11if(c==Ur.count)

13end

14 ++i;

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

16break;

17end

18end

2 性能評估

2.1 隱私度量與性能分析

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

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

(5)

(6)

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

定義 5 若隱私保護方法可抵抗輪廓關聯攻擊,當且僅當對于匿名集合中任意兩個位置存在

?0

(7)

(8)

(9)

(10)

證畢

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

2.2 實驗設定

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

表1 實驗參數閾值設定表

3 實驗結果

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

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

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

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

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

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

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

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

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

圖7 隨申請人數變化的執行時間Fig.7 Execute time with Sr

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

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

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

4 結 論

[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.(馬春光, 張磊, 楊松濤. 位置軌跡隱私保護綜述[J]. 信息網絡安全, 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. (薛姣, 劉向宇, 楊曉春, 等. 一種面向公路網絡的位置隱私保護方法[J]. 計算機學報, 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的隱私保護模型及方案[J]. 通信學報, 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;網絡優先出版日期:2016-10-21。

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

TP

A

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

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

E-mail:8213662@163.com

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

E-mail:machunguang@hrbeu.edu.cn

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

E-mail:songtao_y@163.com

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

E-mail:lnxiaodong@126.com

網絡優先出版地址:http:∥www.cnki.net/kcms/detail/11.2422.TN.20161021.1059.010.html