周志剛,張宏莉,葉 麟,余翔湛

(哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150001)

?

F-Seeker：基于重匿名的粒度化好友搜索架構(gòu)

周志剛,張宏莉,葉 麟,余翔湛

(哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150001)

針對社交網(wǎng)絡(luò)中好友檢索服務(wù)的隱私保護(hù)問題，本文提出一種基于重匿名技術(shù)的粒度化好友搜索架構(gòu)F-Seeker.對用戶發(fā)布的位置信息采用增強(qiáng)的k匿名策略—(k,m,e)-匿名，用以防止“好奇”的搜索服務(wù)提供方對用戶隱私的推測.在處理好友搜索服務(wù)過程中，由服務(wù)提供方根據(jù)粒度化的可視策略對數(shù)據(jù)實施重匿名，實現(xiàn)了對用戶位置信息粒度化的訪問控制.此外，文中對發(fā)布數(shù)據(jù)采用Z序編碼并在搜索過程中通過運(yùn)用剪枝策略提高搜索效率.實驗結(jié)果表明，文中提出的匿名策略在保護(hù)用戶隱私的同時并沒有大幅度地增加計算開銷.

重匿名；粒度化檢索；基于位置的服務(wù)；泰森多邊形；Z序空間填充曲線

1 引言

隱私保護(hù)的“好友”搜索是社交網(wǎng)絡(luò)領(lǐng)域研究的熱點問題.它可以看成是數(shù)據(jù)隱私保護(hù)、海量數(shù)據(jù)檢索以及基于地理位置的服務(wù)(Location Based Service，LBS)三種技術(shù)的有機(jī)融合；即在不泄露用戶隱私的前提下，由服務(wù)提供商從海量的數(shù)據(jù)中搜索符合條件的目標(biāo)用戶的位置信息.近年來隨著智能手機(jī)的普及，基于地理位置的社交網(wǎng)絡(luò)應(yīng)用服務(wù)層出不窮(如Gowalla、Brightkit、陌陌等).“好友”搜索服務(wù)為生活在都市快節(jié)奏的人群構(gòu)建了一座無形的溝通橋梁，拉近了人與人之間的距離，因此一經(jīng)推出就自然吸引了大量用戶.然而在用戶享受這些社交服務(wù)所帶來便捷的同時，其對隱私信息泄露風(fēng)險的顧慮已經(jīng)成為阻礙這類應(yīng)用服務(wù)發(fā)展的首要問題.其次，在如何實現(xiàn)對用戶上傳的社交數(shù)據(jù)實施粒度化的訪問控制以及高效的海量數(shù)據(jù)檢索方面也面臨極大挑戰(zhàn).

針對社交網(wǎng)絡(luò)好友搜索應(yīng)用中所存在的隱私保護(hù)及海量多維數(shù)據(jù)搜索問題，本文提出一個基于重匿名策略的粒度化好友搜索架構(gòu).在用戶將位置信息上傳至社交網(wǎng)絡(luò)服務(wù)器前，首先由位置匿名服務(wù)器使用(k,m,e)-匿名算法對其進(jìn)行匿名化操作，并將匿名后的數(shù)據(jù)發(fā)給LBS服務(wù)器.LBS端使用Z序編碼技術(shù)對高維用戶信息進(jìn)行編碼，在處理好友搜索服務(wù)過程中，采用基于Z序編碼的剪枝策略對候選集進(jìn)行篩選，從而極大地提高搜索效率.同時為實現(xiàn)粒度化的訪問控制，LBS服務(wù)器根據(jù)粒度化的可視策略對數(shù)據(jù)實施重匿名.

2 相關(guān)工作

針對社交數(shù)據(jù)的隱私保護(hù)問題，相關(guān)研究人員提出了許多用戶位置隱私保護(hù)方案.根據(jù)匿名原理的不同，這些方案大體可分為兩類：基于位置模糊化的匿名策略[1～3]和基于k-匿名的空間位置匿名策略[4～8].基于位置模糊化的匿名模型是通過發(fā)布虛假位置信息或位置坐標(biāo)區(qū)域化等策略對用戶位置隱私實施保護(hù).文獻(xiàn)[1,2]提出基于“插入假人”的位置隱私保護(hù)策略，即用戶在提交自身真實位置信息的同時，還發(fā)送若干偽造的虛假位置給LBS服務(wù)器，使得攻擊者無法辨別出用戶的真實位置.但由于用戶的精確位置會混在虛假的信息中，所以該策略依然會造成一定的安全隱患.文獻(xiàn)[3]提出位置相似度的概念：將服務(wù)區(qū)域細(xì)化為網(wǎng)格，位置服務(wù)器根據(jù)每個網(wǎng)格的興趣點查詢結(jié)果的相似度，計算出服務(wù)區(qū)域的相似地圖，并傳遞給移動設(shè)備；用戶再依據(jù)相似地圖構(gòu)造出一個服務(wù)輪廓，用于替代自身位置向LBS服務(wù)器請求服務(wù)，從而實現(xiàn)位置保護(hù).Gruteser M等人[4]首次將k-匿名方法應(yīng)用到用戶位置隱私保護(hù)中.該策略為每個用戶構(gòu)造一個匿名化的空間區(qū)域(Anonymous Spatial Region，ASR)，其中ASR內(nèi)至少含有k個不可區(qū)分的用戶(含目標(biāo)用戶)，使得攻擊者無法以高于1/k的概率識別出目標(biāo)用戶.Gedik B等人[5]提出了一種帶有區(qū)域約束的匿名策略，該策略增加了一個最小匿名區(qū)域Amin的隱私保護(hù)約束，從而防止因這k個用戶的匿名區(qū)域過小而造成的位置泄露問題.然而由這類策略生成的匿名區(qū)域可能落在某個敏感位置(Point Of Interest，POI)附近，攻擊者能夠據(jù)此推測出目標(biāo)用戶身份、職業(yè)、健康狀況等隱私信息.一個自然的解決思路是在滿足k-匿名的基礎(chǔ)上實現(xiàn)對ASR位置多樣化的需求[6]，即在生成的ASR中至少包含m個POIs，同時為了防止匿名退化攻擊*匿名退化攻擊：攻擊者可以根據(jù)用戶在POIs間分布的不均衡性，在概率上縮小ASR的范圍，使得能以高于1/k的概率推測出目標(biāo)用戶的精確位置.，要保證ASR中用戶在各個POIs間分布的均衡性；從服務(wù)效用看，用戶希望構(gòu)造的ASR是最小的.然而，構(gòu)造符合以上需求的ASR是一個NP-complete問題.

在海量數(shù)據(jù)的高效檢索方面，目前大多數(shù)研究集中在通過構(gòu)造高效的索引結(jié)構(gòu)檢索數(shù)據(jù)，如基于R-tree[9]的索引(RUM-tree[10]，TPR-tree[11])，基于B+-tree的索引(Bx-tree[12])，基于quad-tree的索引(STRIPES[13])，然而這些技術(shù)僅僅根據(jù)移動用戶空間地理位置的鄰近關(guān)系存儲數(shù)據(jù)，難以滿足現(xiàn)實的社交網(wǎng)絡(luò)應(yīng)用中用戶對好友多維度立體式的搜索需求，且在海量多維數(shù)據(jù)下，這些技術(shù)在處理范圍查詢(如經(jīng)典的最近鄰查詢)時，需要掃描待搜索區(qū)域內(nèi)所有的實體，產(chǎn)生極大的計算及存儲開銷，無法適用于對實時性要求較高的社交網(wǎng)絡(luò)應(yīng)用場景.

3 系統(tǒng)設(shè)計架構(gòu)

在現(xiàn)行的“用戶-LBS服務(wù)器”二元社交網(wǎng)絡(luò)模型中，所有用戶的社交數(shù)據(jù)(如Check-In、興趣、社交關(guān)系)都置于LBS服務(wù)器上，LBS服務(wù)器宛然成為與用戶群構(gòu)成星形拓?fù)渲械暮斯?jié)點.一旦LBS服務(wù)器被外部攻擊者入侵或內(nèi)部員工惡意泄露其上數(shù)據(jù)，則用戶個人隱私及其社交關(guān)系隱私都將泄露.為此，本文提出一種基于“用戶-位置匿名器-LBS服務(wù)器”的三元社交網(wǎng)絡(luò)架構(gòu)如圖1所示，其中，位置匿名器作為可信第三方被引入系統(tǒng)，采用(k,m,e)-匿名算法對用戶的位置信息進(jìn)行匿名，并將匿名后的區(qū)域ASR發(fā)送給LBS服務(wù)器.為防止位置匿名器成為第二個超級節(jié)點，這里位置匿名器僅用來處理用戶的位置信息，而無法獲知用戶間的社交關(guān)系；同理，LBS服務(wù)器僅處理好友搜索業(yè)務(wù)邏輯而無法獲知用戶精確的位置信息.

4 位置匿名算法

k-匿名算法要求每一個實體所對應(yīng)的記錄在數(shù)據(jù)集中存在其它k-1條與其不可區(qū)分的記錄，由于其符合人們對數(shù)據(jù)安全的共識，且易于實現(xiàn)，已經(jīng)成為數(shù)據(jù)安全評價指標(biāo)并廣泛應(yīng)用于和數(shù)據(jù)隱私保護(hù)相關(guān)的各個領(lǐng)域.針對移動用戶的位置發(fā)布場景，位置匿名器通過構(gòu)造一個ASR使得其中包含至少k個移動用戶(含目標(biāo)用戶)，從而保護(hù)用戶的位置隱私.然而使用傳統(tǒng)k匿名算法構(gòu)造的ASR并沒有對其中包含的POI的數(shù)量進(jìn)行限制，當(dāng)ASR中僅包含一個敏感POI(如腫瘤醫(yī)院)時，用戶的個人隱私將可能因此而被泄露.本文提出一個k-匿名的增強(qiáng)策略(k,m,e)-匿名并將其作為安全評價指標(biāo).(k,m,e)-匿名策略在k-匿名算法的基礎(chǔ)上還限定了匿名區(qū)域中POI的數(shù)量以及用戶在期間的分布.

位置匿名器對用戶位置的匿名化處理包含兩個階段：(1)預(yù)處理階段,位置匿名器離線地對其管理范圍的POI集合進(jìn)行劃分；(2)匿名階段,采用(k,m,e)-匿名策略生成ASR.

4.1 預(yù)處理階段

在預(yù)處理階段，根據(jù)Voronoi規(guī)則[14,15]，位置匿名器使用其管理范圍內(nèi)所覆蓋的POI集合對區(qū)域進(jìn)行劃分，使得

(1)每一個劃分區(qū)域Voronoi cell(Vcell)中包含且僅包含一個POI.

(2)給定一個Vcelli及其覆蓋的POI(Pi)，則其上任意一點q到Pi的距離小于等于其到其它POI的距離，當(dāng)且僅當(dāng)q位于區(qū)域邊界點時，等號成立.

基于Voronoi規(guī)則的區(qū)域劃分建立了子區(qū)域與POI集合元素的一一映射關(guān)系，其目的在于當(dāng)給定目標(biāo)用戶的位置信息能夠快速檢索到其鄰近的POI，從而提高位置匿名的效率.圖2展示了一個區(qū)域劃分實例，其中四個POI(P1,P2,P3,P4)基于Voronoi規(guī)則分別被劃分到V1,V2,V3,V4四個Vcells中.給定目標(biāo)用戶q位于Vcell(V1)，能夠得出P1為與之最近的POI.

雖然基于Voronoi規(guī)則的區(qū)域劃分能夠精確地表述POI間及目標(biāo)用戶與POI間的近鄰位置關(guān)系，然而僅使用Voronoi規(guī)則劃分的區(qū)域存在以下幾方面問題：(1)劃分的子區(qū)域形狀不規(guī)則，難以坐標(biāo)化表示；(2)子區(qū)域的大小不均一，難以量化評估據(jù)此生成ASR中用戶分布與POI分布的映射關(guān)系；(3)子區(qū)域的劃分個數(shù)等于POI集合元素的個數(shù)，無法進(jìn)一步對其進(jìn)行加細(xì)劃分，以致難以細(xì)粒度地構(gòu)造ASR.為此，在以Voronoi規(guī)則對區(qū)域進(jìn)行劃分的基礎(chǔ)上，本文使用Hilbert空間填充曲線[16,17]對空間區(qū)域進(jìn)行迭代劃分.給定待劃分區(qū)域:(1)首先將劃分為N×N個大小均一的格狀子區(qū)域(Grid cell，Gcell)，其中N∈2n(n=1,2,…)；(2)使用Hilbert線序?qū)Ρ緦拥腉cells進(jìn)行編號排序；(3)返回到步驟(1)對每一個Gcell迭代地進(jìn)行加細(xì)劃分.顯然，使用Hilbert空間填充曲線劃分的區(qū)域解決了上文提出的三方面問題，此外，Hilbert線序相近的區(qū)域其地理位置也具有近鄰性.結(jié)合Voronoi規(guī)則及Hilbert空間填充曲線的對區(qū)域劃分的優(yōu)點，本文構(gòu)造基于網(wǎng)格的B+-tree(grid-based B+-tree，gB+-tree)存儲各個子區(qū)域Gcells中POI和用戶的位置及分布信息.

定義2(gB+-tree) 給定待劃分區(qū)域，并將其設(shè)定為gB+-tree的根節(jié)點(root)，根據(jù)Hilbert空間填充曲線迭代地對其進(jìn)行加細(xì)劃分，其中每一個節(jié)點被劃分為2n×2n(n=1,2,…)個Gcells，稱最細(xì)層劃分的Gcells為葉節(jié)點，其它節(jié)點為中間節(jié)點.對于每一個中間節(jié)點，使用二元組(|P|,|Q|)統(tǒng)計其覆蓋區(qū)域中POI及用戶的數(shù)量；對于葉節(jié)點，使用三元組(P,Q,H)記錄其內(nèi)POI及用戶的信息，其中P記錄其上的POI集合，Q記錄其上用戶集合，H是屬性P的擴(kuò)展屬性，當(dāng)P=?時，H記錄在Voronoi規(guī)則空間劃分下該葉節(jié)點所屬Vcells中POI所在的Gcell節(jié)點的Hilbert序ID；否則H記錄在Voronoi規(guī)則空間劃分下P屬性值所對應(yīng)Vcell覆蓋的所有格狀區(qū)域的Hilbert序ID.

例如，圖3展示了針對圖2區(qū)域?qū)嵗膬蓪觛B+-tree存儲結(jié)構(gòu).所有的中間節(jié)點被劃分為2×2子格區(qū)域，并使用Hilbert線序?qū)⑵錁?biāo)記為H1～H16.其中root節(jié)點H1～16:(4,7)表示整個區(qū)域內(nèi)包含4個POIs及7名移動用戶，類似地，H1～4:(1,2) 表示子區(qū)域{H1,H2,H3,H4}內(nèi)包含1個POIs及2名移動用戶；葉節(jié)點H7:{?,{q3,q4},{H3,H11}}表示區(qū)域H7內(nèi)不含POI(P=?)，僅包含2名移動用戶(Q={q3,q4})，且根據(jù)Voronoi規(guī)則對空間區(qū)域的劃分，H7分屬于Vcell{V3,V4}，因此與其對應(yīng)的POI(p3,p4)是距H7最近的POI集合，如圖2所示，p3,p4分別位于H3,H11；H11:{{p4},{q5},{H7,H9,H10,H11,H12}}表示區(qū)域H11內(nèi)覆蓋POI(P={p4})，僅包含1名移動用戶(Q={q5})，且根據(jù)Voronoi規(guī)則對空間區(qū)域的劃分，p4屬于Vcell(V4)，且V4覆蓋{H7,H9,H10,H11,H12}.

4.2 基于(k,m,e)-匿名的位置匿名策略

在現(xiàn)實的應(yīng)用需求中，用戶要求ASR在滿足隱私需求(即ASR對隱私保護(hù)的安全度越高越好)的同時滿足可用性(utility)需求(即ASR應(yīng)該盡可能的小).一個自然的解決方案是設(shè)定一個隱私泄露的上限而求最小化的ASR.這里首先定義一個效用函數(shù)U(ASR)用于描述ASR所覆蓋的區(qū)域面積，

(1)

U(ASR)≤A

(2)

subject toE(ASR)≥e,

U(ASR)≤A

(3)

其中，λ是權(quán)重參數(shù)，

然而對式(2)及式(3)的求解是NP-complete.本文提出一個基于貪心策略的啟發(fā)式算法(算法1)近似地解決式(2)及式(3)中的優(yōu)化問題.算法1的基本思想是迭代地掃描gB+-tree：

(1)逐層加細(xì)地定位目標(biāo)用戶所在的區(qū)域，直到其子節(jié)點覆蓋的POI數(shù)量少于用戶設(shè)定的閾值m.

(2)檢測目標(biāo)用戶所在子區(qū)域內(nèi)用戶的數(shù)量及用戶分布熵：(a)若用戶的數(shù)量小于k，則根據(jù)Hilbert序?qū)ψ訁^(qū)域進(jìn)行擴(kuò)張；(b)若用戶分布熵小于e，則根據(jù)Voronoi規(guī)則對用戶分布熵貢獻(xiàn)最小的格狀區(qū)域進(jìn)行擴(kuò)張.直到滿足用戶的隱私需求或打破可用性需求，算法終止.

算法1 基于貪心策略的ASR構(gòu)造算法(GenASR)

輸入:匿名參數(shù)k,m,e;

目標(biāo)用戶的精確位置qloc;

gB+-tree*b

GenASR(k,m,e,qloc,b)

1: for each entryiinbdo

2: if 2D to L(qloc)≤entryi.ID then

//2D to L() transforms 2D region to Hilbert ID

3: if entryi.|P|≥mthen

4: GenASR(k,m,e,qloc,entryi→child);

5: else

7:k=k-entryi.|Q|;

8:m=m-||;

9: ifm>0 then

10: GenASR(k,m,e,qloc,entryi→next);

11: ifk>0 then

12: GenASR(k,m,e,qloc,entryi→next);

15:foreachGiindo

16: ifGi.P=pxthen

inGi.HandGj∩=?);

18: break;

// Procedure FindPOI

FindPOI(*b,p)

1:for each entryiinbdo

2: if entryi→child≠? then

3: FindPOI(entryi→child,p);

4: ifp≠0 then

6:p=p-|entryi.H|;

7: else

5 細(xì)粒度的好友搜索算法

5.1 基于Z序的數(shù)據(jù)編碼

除了位置信息外，在社交網(wǎng)絡(luò)系統(tǒng)中，用戶會發(fā)布一些可公開的個人基本信息(如年齡、性別、愛好等)以便于“好友”對其的搜索.本文提出一種基于Z序的編碼方案對用戶社交數(shù)據(jù)進(jìn)行編碼.

性質(zhì)1(聚簇性) 在Z序編碼下，兩條數(shù)據(jù)擁有的公共Z序編碼越長，其數(shù)據(jù)各個屬性的相似度也越高.

定義4(支配操作)[18]稱一個點qi在M維空間上支配另一個點qj，當(dāng)且僅當(dāng)?ar∈A，有qi.ar≤qj.ar，并且?at∈A使得qi.at

性質(zhì)2(單調(diào)性) 在基于Z序編碼的M維空間上，若qi支配qj，則在Z序空間填充曲線上qi的位置先于qj.

5.2 查詢剪枝策略

為了便于描述，文中以對2維社交網(wǎng)絡(luò)數(shù)據(jù)集的最近鄰(Nearest Neighborhood，NN)查詢?yōu)槔榻B剪枝策略.

根據(jù)Z序編碼的性質(zhì)1，Z序編碼可以以組為單位迭代細(xì)分.每一條記錄的Z序編碼可以看作是「log2d?層(組)2-bit子編碼構(gòu)成的樹形結(jié)構(gòu)，其中第i(0

當(dāng)接收到好友檢索請求，LBS服務(wù)器首先對其進(jìn)行Z序編碼，并以此為目標(biāo)點，搜索其在空間中的支配最近鄰對象.為了減少候選記錄的數(shù)量，本文提出以下逐層剪枝規(guī)則：

(1)當(dāng)目標(biāo)點位于區(qū)域Ⅰ，則剪切同層的區(qū)域Ⅱ,Ⅲ,Ⅳ.

(2)當(dāng)目標(biāo)點位于區(qū)域Ⅱ，則剪切同層的區(qū)域Ⅲ,Ⅳ.

(3)當(dāng)目標(biāo)點位于區(qū)域Ⅲ，則剪切同層的區(qū)域Ⅱ,Ⅳ.

(4)當(dāng)目標(biāo)點位于葉節(jié)點所在區(qū)域，則剪切由Z序曲線填充的該區(qū)域中位于目標(biāo)點之后的對象.

5.3 基于粒度化可視約束的重匿名策略

為了對不同角色的搜索用戶提供不同粒度的視圖，用戶在發(fā)布個人的社交網(wǎng)絡(luò)數(shù)據(jù)前需向LBS服務(wù)器提交其對不同角色用戶設(shè)定的數(shù)據(jù)訪問控制條件，即粒度化可視約束.

定義5(粒度化可視約束) 給定目標(biāo)用戶q及其好友列表描述(Q,R,f,h)，其中Q={q1,…,qn}表示用戶q的好友列表，目標(biāo)用戶q將Q劃分為l個角色R={r1,…,rl}(l≤n)，(f,h)是一對對偶操作：f:Q→R表示由好友ID到角色的映射，h:R→Q表示由角色到其相應(yīng)的好友ID的映射且?ri,rj,h(ri)∩h(rj)=?.用戶q對角色ri的可視化約束可以表示為一個五元組Sq→ri=(sri,tri,mri,kri,eri)，sri和tri分別表示對角色ri可搜索q的空間及時間約束，(mri,kri,eri)是設(shè)定角色ri對q定位的重匿名化約束且mri≥m,kri≥k,eri≥e((m,k,e)是對其位置信息設(shè)定的初次匿名參數(shù)).

這里，用戶好友列表Q可以包含一個默認(rèn)好友，與之對應(yīng)的角色被設(shè)定為“游客”，即開辟一個與陌生人交互的接口.

LBS服務(wù)器將用戶的可視化約束內(nèi)嵌到其相應(yīng)的個人信息之中，并將(sri,tri)作為查詢篩選條件，即當(dāng)用戶qi滿足搜索用戶q的查詢請求時，LBS服務(wù)器檢測qi對q設(shè)定的搜索時空約束，若滿足，則使用匿名參數(shù)(mri,kri,eri)對ASRqi實施重匿名，并將結(jié)果返回用戶.重匿名算法類似于算法1，由于篇幅有限，此處省略詳細(xì)的算法描述.

6 實驗結(jié)果及分析

實驗配置為服務(wù)器采用Intel Xeon E3處理器，內(nèi)存32GB.位置匿名器和LBS服務(wù)器分別采用3個基于Map-Reduce的計算節(jié)點分布式計算平臺.本實驗將從匿名算法性能以及好友搜索實時性方面進(jìn)行實驗驗證.

6.1 匿名性能

本文使用仿真數(shù)據(jù)模擬現(xiàn)實社交網(wǎng)絡(luò)中用戶Check-In的位置信息，為模擬用戶在空間區(qū)域內(nèi)的均勻分布，數(shù)據(jù)產(chǎn)生器在1000×1000的空間區(qū)域內(nèi)隨機(jī)地生成用戶的位置及POI的坐標(biāo)，生成的數(shù)據(jù)庫包含100K個用戶位置及10K個POIs.實驗中設(shè)置匿名請求提交窗口分別為100、300、500、700、900，其中位置匿名請求的提交用戶是隨機(jī)選擇的，匿名參數(shù)為k=10,m=3,e=1.3(參數(shù)m和e僅適用于(k,m,e)-匿名算法).圖5～7分別展示了在上述設(shè)置中，(k,m,e)-匿名算法在執(zhí)行效率、隱私保護(hù)程度及匿名區(qū)域可用性三個方面與經(jīng)典的k-匿名算法及離線最優(yōu)算法的比較.圖5說明，在同等條件下，隨著請求數(shù)量的增加，本文提出的匿名算法執(zhí)行時間呈線性增長，由于k-匿名算法沒有考慮對參數(shù)m和e的限制，因此執(zhí)行時間開銷總是比本文所提匿名算法要小，然而正如圖6中所展示的，(k,m,e)-匿名算法在隱私保護(hù)的程度上遠(yuǎn)高于同等條件下k-匿名算法對隱私的保護(hù)程度(這里使用用戶在POI間的分布熵來描述ASR中用戶位置隱私的保護(hù)程度，其中熵越高，說明用戶在POI間的分布越均衡).圖7展示了匿名區(qū)域可用性(即ASR的面積)，為了便于比較，這里對實驗結(jié)果進(jìn)行歸一化處理.結(jié)果表明，雖然從統(tǒng)計的角度文中所提算法所生成ASR總是大于k-匿名算法所產(chǎn)生的ASR，但兩者的相差并不大，可以推知其依然滿足現(xiàn)實社交網(wǎng)絡(luò)中對位置可用性的需求.

6.2 搜索實時性

圖8展示了基于Z序編碼的執(zhí)行效率，在上述實驗環(huán)境下，用戶數(shù)量設(shè)置為10K、20K、30K、40K、50K，其中，每一個用戶包含5個屬性且屬性的取值范圍[1,50].結(jié)果表明，對50K用戶的一次Z序編碼的壓力測試大約需要10s，基本滿足現(xiàn)實場景中對編碼效率的需求.

圖9展示了好友搜索執(zhí)行效率，實驗中設(shè)置搜索請求提交窗口分別為100、300、500、700、900，為了便于比較，我們引入了經(jīng)典的位置存儲結(jié)構(gòu)(基于B+-tree的索引(Bx-tree[12])，基于quad-tree的索引(STRIPES[13]))作為參照，實驗結(jié)果表明本文使用的基于Z序編碼的搜索算法及剪枝策略在搜索效率方面明顯優(yōu)于經(jīng)典的搜索算法且具有良好的實時性.

7 結(jié)束語

本文采用重匿名技術(shù)，在保證用戶位置信息可用性的前提下實現(xiàn)對用戶位置信息進(jìn)行粒度化的隱私保護(hù).與k-匿名相比，基于(k,m,e)-匿名技術(shù)的隱私保護(hù)策略防止攻擊者通過用戶分布對用戶位置信息進(jìn)行推理攻擊，僅附加較低的性能懲罰.在好友搜索階段，采用基于Z序的數(shù)據(jù)編碼及相應(yīng)的剪枝策略，大幅降低了對高維多值社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行最近鄰搜索時的時空開銷.

[1]Kido H,Yanagisawa Y,Satoh T.An anonymous communication technique using dummies for location-based services[A].Proceedings of International Conference on Pervasive Services (ICPS'05)[C].USA:IEEE Press,2005.88-97.

[2]劉華玲,鄭建國,孫辭海.基于貪心擾動的社交網(wǎng)絡(luò)隱私保護(hù)研究[J].電子學(xué)報,2013,41(8):1586-1591.

Liu Hua-ling,Zheng Jian-guo,Sun Ci-hai.Privacy preserving in social networks based on greedy perturbation[J].Acta Electronica Sinica,2013,41(8):1586-1591.(in Chinese)

[3]Rinku Dewri.Exploiting service similarity for privacy in location based search queries[J].IEEE Transactions on Parallel and Distributed Systems,2013,25(2):374-383.

[4]Gruteser M,Grunwal D.Anonymous usage of location-based services through spatial and temporal cloaking[A].Proceedings of the International Conference on Mobile Systems Applications and Services[C].USA:IEEE Press,2013.163-168.

[5]Mokbel M F,Chow C Y,Aref W G.The new casper:Query processing for location services without compromising privacy[A].Proceedings of the International Conference on Very Large Data Bases[C].USA:VLDB Press,2006.763-774.

[6]Bhuvan B,Ling L,et al.Supporting anonymous location queries in mobile environments with privacy grid[A].Proceedings of the 17th International Conference on World Wide Web[C].USA:ACM Press,2008.237-246.

[7]王麗娜,彭瑞卿,等.個人移動數(shù)據(jù)收集中的多維軌跡匿名方法[J].電子學(xué)報,2013,41(8):1653-1659.

Wang Li-na,Peng Rui-qing,et al.Multi-dimensional trajectory anonymity in collecting personal mobility data[J].Acta Electronica Sinica,2013,41(8):1653-1659.(in Chinese)

[8]葉阿勇,林少聰,馬建峰,許力.一種主動擴(kuò)散式的位置隱私保護(hù)方法[J].電子學(xué)報,2014,43(7):1362-1368.

Ye A-yong,Lin Shao-cong,Ma Jian-feng,Xu Li.An active diffusion based location privacy protection method[J].Acta Electronica Sinica,2014,43(7):1362-1368.(in Chinese)

[9]Chen Q,Hu H,Xu J.Authenticating top-k queries in location-based services with confidentiality[A].Proceedings of the International Conference on Very Large Data Bases[C].USA:VLDB Press,2014.49-60.

[10]Xiong X,Aref W G.R-trees with update memos[A].Proceedings of the 22nd International Conference on Data Engineering (ICDE'06)[C].USA:IEEE Press,2006.22.

[11]Saltenis S,Jensen C S,Leutenegger S T,Lopez M A.Indexing the positions of continuously moving objects[A].Proceedings of ACM SIGMOD[C].USA:ACM Press,2000.331-342.

[13]Patel J M,Chen Y,Chakka V P.Stripes:An efficient index for predicted trajectories[A].Proceedings of ACM SIGMOD[C].USA:ACM Press,2004.637-646.

[14]Berg M de,Kreveld M van,Overmars M,Schwarzkopf O.Computational Geometry:Algorithms and Applications (2nd edition)[M].Berlin:Springer-Verlag,2000.

[15]Hu L,Ku W-S,Bakiras S,Shahabi C.Spatial query integrity with voronoi neighbors[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(4):863-876.

[16]Kalins P,Ghinita G,Mouratidis K,Papadias D.Preventing location-based identity inference in anonymous spatial queries[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(12):1719-1733.

[17]Ghinita G,Kalnis P,Khoshgozaran A,Shahabi C,Tan K-L.Private queries in location based services:Anonymizers are not necessary[A].Proceedings of the ACM SIGMOD International Conference on Management of Data[C].New York:ACM,2008.121-132.

[18]Lee K,Lee W,Zheng B,Li H,Tian Y.Z-sky:an efficient skyline query processing framework based on z-order[J].The VLDB Journal,2010,19(3):333-362.

[19]William Feller.An Introduction to Probability Theory and Its Applications (Vol.1,3rd Edition)[M].USA:Wiley,1968.

周志剛 男，1986年2月出生，山西太原人，博士生，現(xiàn)就讀于哈爾濱工業(yè)大學(xué)計算機(jī)系，主要研究方向為網(wǎng)絡(luò)與信息安全、位置隱私保護(hù)、云安全等.

E-mail:zzgisgod@sina.com

張宏莉 女，1973年出生，吉林榆樹人，博士、教授、博士生導(dǎo)師，國家計算機(jī)信息內(nèi)容安全重點實驗室副主任，計算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心副主任，信息產(chǎn)業(yè)部十一五科技規(guī)劃組專家.主要研究方向為網(wǎng)絡(luò)信息安全、網(wǎng)絡(luò)測量、并行處理.

F-Seeker:Privacy-Aware Granular Moving-Object Query FrameworkBased on Over-Anonymity

ZHOU Zhi-gang,ZHANG Hong-li,YE Lin,YU Xiang-zhan

(SchoolofComputerScienceandEngineering,HarbinInstituteofTechnology,Harbin,Heilongjiang150001,China)

Aiming to the privacy-preserving problem for moving-object retrieval services in social network,we propose a granular friend retrieval framework based on over-anonymity,called F-Seeker.Before outsourcing data,we adopt an enhanced anonymity strategy--(k,m,e)-anonymity,which preserving user privacy from the curious retrieval service provider.In the processing of providing services,the service provider employs over-anonymity strategy based on visibility requirements to realize granular data access control.In addition,we encode data using Z-order address and the retrieval efficiency can be improved by pruning.Experimental results show that the proposed strategy can protect user privacy while the computation overhead does not increase greatly.

over-anonymity;granular search;location-based service (LBS);Voronoi diagram;Z-order space filling curve

2015-01-30；

2015-10-31；責(zé)任編輯：孫瑤

國家973重點基礎(chǔ)研究發(fā)展計劃(No.2011CB302605，No.2013CB329602)；國家自然科學(xué)基金(No.61202457，No.61173144，No.61402137，No.61402149)

TP393

A

0372-2112 (2016)10-2477-08

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.028