楊姿,寧博,李毅

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院,遼寧大連116026)

基于k-泛化技術(shù)的時(shí)空數(shù)據(jù)個(gè)人隱私保護(hù)方法

楊姿,寧博,李毅

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院,遼寧大連116026)

近些年來,基于位置系統(tǒng)的設(shè)備越來越多,從而導(dǎo)致用戶的大量位置信息被移動設(shè)備獲取并利用,從數(shù)據(jù)挖掘的角度來說,這些數(shù)據(jù)具有不可估量的價(jià)值,但從個(gè)人隱私方面來說卻恰恰相反,每個(gè)人都不希望自己的信息被泄露和利用,從而引發(fā)了人們強(qiáng)烈的隱私關(guān)注.目前許多文獻(xiàn)都提出了隱私保護(hù)技術(shù)來解決這個(gè)問題,概括來說是干擾、抑制和泛化幾大類.為了對個(gè)人時(shí)空數(shù)據(jù)的隱私進(jìn)行保護(hù),本文提出了k-泛化的方法.對用戶可能出現(xiàn)的點(diǎn)進(jìn)行范圍限定,更好地提高了數(shù)據(jù)的可用性;對泛化節(jié)點(diǎn)的選取要使得用戶的安全性最高;考慮了多個(gè)敏感節(jié)點(diǎn)存在情況下的解決方案,并且出于提高數(shù)據(jù)效用的目的對多個(gè)敏感節(jié)點(diǎn)進(jìn)行了優(yōu)化.最后通過實(shí)驗(yàn)評估了算法的性能并且驗(yàn)證了算法保護(hù)個(gè)人隱私是有效的.

隱私;時(shí)空數(shù)據(jù);匿名;泛化

0 引言

隨著計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展,人們的生活發(fā)生了日新月異的變化.近年來,個(gè)人位置信息的可用性增加導(dǎo)致了越來越多的系統(tǒng)記錄和處理位置數(shù)據(jù),尤其是基于位置系統(tǒng)的設(shè)備的日益普及,例如智能手機(jī)、GPS設(shè)備等深入人們的生活[1],這些設(shè)備收集大量的關(guān)于用戶的位置信息,這些位置信息加上時(shí)間的概念便是時(shí)空數(shù)據(jù),設(shè)備得到的時(shí)空數(shù)據(jù)具有很大的實(shí)用價(jià)值,例如可以用來和朋友共享位置信息,尋找最近的飯店,甚至可以用來分析路況,調(diào)節(jié)交通流,避免道路擁堵等.

雖然基于位置的系統(tǒng)得到的個(gè)人時(shí)空數(shù)據(jù)已經(jīng)被證明可以給個(gè)人和社會帶來巨大的利益,但是越來越多用戶的位置信息曝光引發(fā)了人們對于位置隱私的強(qiáng)烈關(guān)注,并提出了重要的隱私問題[2].首先,位置信息本身可以被認(rèn)為是敏感的.此外,它可以很容易地鏈接到各種其他信息,通過定期收集和處理準(zhǔn)確的位置數(shù)據(jù),可以推斷出個(gè)人的家庭或工作地點(diǎn)、政治觀點(diǎn)或宗教傾向等.但是一個(gè)人通常并不希望泄露自己的個(gè)人信息.例如,一個(gè)人可能不希望別人知道他或她經(jīng)常停留在夜總會[3].

解決隱私問題的最常用的方法是去除個(gè)人的標(biāo)識符[4-6]以及將數(shù)據(jù)進(jìn)行加密[7],例如標(biāo)識符有姓名等,將標(biāo)識符去除后將其他信息發(fā)布出去,攻擊者看到的只是一系列的時(shí)空數(shù)據(jù)點(diǎn)而無法找到所對應(yīng)的每個(gè)人[3];而加密則是將數(shù)據(jù)加密之后再發(fā)布,缺點(diǎn)在于加密所需要的計(jì)算代價(jià)很大.然而,這些方法是遠(yuǎn)遠(yuǎn)不夠的,因?yàn)楣粽哂凶约旱南闰?yàn)知識,例如鄰域圖,攻擊者所擁有的額外的信息可以重新鑒定出被攻擊的用戶[8-9].為了克服鏈?zhǔn)焦暨@個(gè)問題,一種稱為k-匿名的算法被提出來.在時(shí)空數(shù)據(jù)方面,k-匿名的含義是對于目標(biāo)用戶的軌跡來說至少有k-1條區(qū)分軌跡[10].這就意味著,對于攻擊者來說,相對于目標(biāo)用戶至少可以映射到一組k個(gè)軌跡從而分辨不出目標(biāo)用戶.但是,k-匿名技術(shù)也存在著缺陷,例如它在一個(gè)等價(jià)組中不執(zhí)行多樣性的敏感信息.之后Ashwin等人提出l-多樣性的概念[11].l-多樣性最基本的策略思想是保證每一個(gè)等價(jià)組的敏感屬性至少有l(wèi)個(gè)不同的值,即使得等價(jià)組中的狀態(tài)呈現(xiàn)出多樣性,以抵御同質(zhì)攻擊.

在論文中提出的k-泛化概念不同于之前的k-匿名,因?yàn)橹発-匿名的所有頂點(diǎn)都是一致的,論文區(qū)分了敏感和非敏感的點(diǎn),非敏感節(jié)點(diǎn)被視為公共區(qū)域,不能夠暴露用戶的隱私,而對于敏感節(jié)點(diǎn),假若用戶停留,則被認(rèn)為是一條敏感信息,應(yīng)該被保護(hù),敏感節(jié)點(diǎn)可以是夜總會等.論文根據(jù)數(shù)據(jù)表塑造一個(gè)模型地圖,點(diǎn)對應(yīng)于真實(shí)的位置節(jié)點(diǎn),邊對應(yīng)于道路連接節(jié)點(diǎn)指示道路的方向.

本文的貢獻(xiàn)點(diǎn)列舉如下:

(1)對用戶可能出現(xiàn)的點(diǎn)進(jìn)行范圍限定,更好地提高了數(shù)據(jù)的可用性;

(2)提出了k-泛化的概念,泛化的過程也出于數(shù)據(jù)可用性的考慮;

(3)對泛化節(jié)點(diǎn)的選擇采用基于安全性最高的原則;

(4)當(dāng)多個(gè)敏感節(jié)點(diǎn)存在時(shí),我們出于數(shù)據(jù)效用的目的做了簡單的優(yōu)化.

論文的章節(jié)安排如下:在第1部分,提出了基于隱私保護(hù)的研究現(xiàn)狀,介紹了當(dāng)前所流行的隱私保護(hù)技術(shù).在第2部分,提出了本文的模型定義,給出了攻擊者模型以及圖和軌跡的定義,也給出了k-泛化、近鄰區(qū)域、相似軌跡集的概念等.在第3部分,給出了方法的詳細(xì)實(shí)現(xiàn)過程以及例子描述.在第4部分,給定了真實(shí)的數(shù)據(jù)集并且對算法進(jìn)行了性能分析.最后第5部分是本文的結(jié)論和未來的工作.

1 相關(guān)工作以及背景知識介紹

從原始數(shù)據(jù)中僅僅去除個(gè)人標(biāo)識符之后進(jìn)行數(shù)據(jù)發(fā)布已被證明是不足以保護(hù)隱私.其他在數(shù)據(jù)集中記錄的屬性,如年齡、性別和家庭住址等公共知識的存在同樣可以用來鏈接到個(gè)人的身份.k-匿名技術(shù)最初提出是用于表格數(shù)據(jù),而后在時(shí)空數(shù)據(jù)上進(jìn)行了擴(kuò)展,也同樣適用.該方法保證了對于每一條記錄,根據(jù)選定的屬性,都至少有k-1條難以分辨的記錄相對應(yīng).在匿名未能保護(hù)隱私在匿名組的所有成員都有相同的敏感信息,即不能抵抗同質(zhì)性攻擊.為了克服這個(gè)問題提出了l-多樣性的技術(shù),它限制了個(gè)人可以與一個(gè)敏感的信息相關(guān)聯(lián)的概率.而l-多樣性模型不能有效防止相似性攻擊,即攻擊者可以根據(jù)每個(gè)組的敏感屬性值具有的語義相似性推測出用戶的敏感信息,因此提出了t-clossness方法[12],該方法要求敏感屬性值在每個(gè)組中的分布和原始數(shù)據(jù)集中的分布之間的差值不超過t.

通過抑制和擾動也是隱私保護(hù)的常用的方法.抑制的方法也就是說不發(fā)布敏感的地點(diǎn);而擾動則是通過泛化或者加入假數(shù)據(jù)的方法將敏感節(jié)點(diǎn)進(jìn)行隱藏,從而實(shí)現(xiàn)用戶的隱私保護(hù).而針對于軌跡數(shù)據(jù)來說,軌跡聚類亦可作為隱私保護(hù)的一個(gè)步驟[13-14].論文利用了泛化的思想,通過泛化將敏感節(jié)點(diǎn)進(jìn)行隱藏.

文獻(xiàn)[3]提出了基于位置服務(wù)的匿名和靜態(tài)數(shù)據(jù)發(fā)布的時(shí)空數(shù)據(jù)的隱私保護(hù),其目標(biāo)和本論文類似,但是方法不同,他們的目標(biāo)是發(fā)布一個(gè)軌跡數(shù)據(jù)集,同時(shí)保持?jǐn)?shù)據(jù)集中的個(gè)人的身份.他們泛化/凝聚地實(shí)現(xiàn)k-匿名.本文的方法是先對用戶可能出現(xiàn)的位置進(jìn)行范圍限定,去除掉“假的”位置.論文在泛化點(diǎn)的選擇原則是保證最小的變動實(shí)現(xiàn)最高的安全性.文獻(xiàn)[15]是在空間數(shù)據(jù)的隱私保護(hù),在k-同構(gòu)的基礎(chǔ)上提出了k-對稱的概念,并且設(shè)計(jì)了兩個(gè)基于骨干的抽樣算法.

除了上述方法,還有一種方法也很流行,叫做差分隱私[16].由于其嚴(yán)格的理論保證已成為隱私數(shù)據(jù)發(fā)布的常用的隱私模型.該模型的優(yōu)點(diǎn)在于不需要特殊的攻擊假設(shè)、不關(guān)心攻擊者所擁有的背景知識,同時(shí)給出了定量化分析來表示隱私泄露風(fēng)險(xiǎn).文獻(xiàn)[17]提出了w-event的概念,提出了一個(gè)滑動窗口方法捕獲廣泛的w-event隱私機(jī)制,引入了預(yù)算分配和預(yù)算合并的方案,但是這種機(jī)制并不適用于本論文的時(shí)空數(shù)據(jù).文獻(xiàn)[18]提出了一個(gè)差異隱私機(jī)制,通過添加噪聲給前綴樹之后發(fā)布交通數(shù)據(jù).作者討論了在時(shí)間維度的軌跡上擴(kuò)展他們的方法,但不包括任何復(fù)雜性分析或經(jīng)驗(yàn)評估.文獻(xiàn)[19]提出了l-軌跡的概念,設(shè)計(jì)嚴(yán)謹(jǐn)和靈活的隱私模型,彌合的理論局限性和實(shí)際需求之間的差距.它們以嚴(yán)謹(jǐn)性以及靈活性的重要性為目的,然后提出了兩種差分隱私模型能夠以一個(gè)實(shí)際的方式擴(kuò)展差分隱私,它們和本文的目的不同,但是彌補(bǔ)理論局限和實(shí)際需求之間的差距是一樣的,本文也考慮了效用性的要求使得文中的方法在實(shí)際應(yīng)用中效用能夠有一個(gè)很好的體現(xiàn).文獻(xiàn)[20]提出差分隱私的泛化概念,提出了平面拉普拉斯機(jī)制,該論文是在空間位置上進(jìn)行的隱私保護(hù),而本論文是基于時(shí)空數(shù)據(jù).

2 問題的定義

本章假設(shè)攻擊者具有的背景知識:

(1)攻擊者知道敏感節(jié)點(diǎn)的所在,例如,我們都知道夜總會可以當(dāng)成一個(gè)敏感節(jié)點(diǎn),因此敏感節(jié)點(diǎn)對于攻擊者來說是公開的;

(2)攻擊者擁有移除掉個(gè)人標(biāo)識符的軌跡數(shù)據(jù)集;

(3)攻擊者可以根據(jù)一些背景知識推測出用戶的軌跡,因?yàn)榧彝プ≈泛凸ぷ鲉挝贿@些信息可以比較容易地獲得.

本章將在每個(gè)時(shí)間戳i收集到的用戶的時(shí)空數(shù)據(jù)點(diǎn)Di,i∈{1,n}.在Di中每一個(gè)數(shù)據(jù)點(diǎn)(用戶i,時(shí)間t,地點(diǎn)v)表示用戶i在時(shí)間t的地點(diǎn)是v,在表1中所示,其中0代表用戶在相應(yīng)的時(shí)間是停在了最早0之前出現(xiàn)的位置點(diǎn).本章根據(jù)表1中的數(shù)據(jù)畫出一個(gè)圖M,如圖1所示,不用的線代表不同的用戶的軌跡.將用戶經(jīng)過的位置作為一個(gè)有向軌跡圖M,M=(V,E),V代表頂點(diǎn)的集合,即V=(v1,v2,…,vn).E代表邊的集合,即E=(e1,e2,…,em).ei=(vx,vy)代表從頂點(diǎn)vx到頂點(diǎn)vy的一條路徑.敏感節(jié)點(diǎn)S?V, S=(s1,s2,…,sf),|S|表示敏感節(jié)點(diǎn)的總數(shù).用戶的軌跡用tr來表示.

在論文中,軌跡圖包含興趣點(diǎn)的節(jié)點(diǎn)(例如,學(xué)校、醫(yī)院、酒吧、夜總會和酒店等).這樣的興趣點(diǎn)在數(shù)據(jù)表中出現(xiàn)并且位置的經(jīng)緯度是已知的,那么這個(gè)興趣點(diǎn)可以被添加在圖中作為一個(gè)節(jié)點(diǎn).其中定義1到4為已知定義,定義5到9是為了提出方法而新引入的定義.

定義1一個(gè)軌跡圖M=(V,E),一組gi=(Vi,Ei)是一個(gè)M的連通子圖,即ej=(vx, vy)∈Ei當(dāng)且僅當(dāng)ej∈E和vx,vy∈Vi.符號g.s表示在g中的敏感節(jié)點(diǎn).

定義2地圖M?=(V?,E?)是M=(V,E)的泛化[3],當(dāng)且僅當(dāng)V?=(V-Vi)∪B,其中B=(b1,b2,…,bi)表示由gi泛化出的區(qū)域.E?=(E-Ei)∪P∪Q,其中P={(vx,ni)|?vy∈Vi,(vx,vy)∈E∧vx∈V?}并且Q={(ni,vx)|?vy∈Vi,(vy,vx)∈E∧vx∈V?},其中N={n1,…,nc}表示新加入的節(jié)點(diǎn).

定義3用戶的軌跡是由一系列有序的時(shí)間戳對組成的,{(v1,t1),(v2,t2),…,(vi, ti),…,(vm,tm)},其中(vi,vi+1)∈E,ti＜ti+1.

本章用元組(vi,ti)表示一個(gè)用戶的軌跡,其中用(0,ti)表示用戶在ti時(shí)刻停在了ti時(shí)刻之前的最先出現(xiàn)的0之前的位置.其中,每個(gè)時(shí)間間隔是30 min,用戶移動的速度v給定.例如tr1={(2,t1),(3,t2),(4,t3),(6,t4),(0,t5),(0,t6),(7,t7),(0,t8),(0,t9)},意思是用戶1在t1時(shí)刻在2位置,之后t2時(shí)刻去了3位置,之后t3時(shí)刻去了4位置,之后t4時(shí)刻停在了6位置,停下的時(shí)間是1 h,而后在t7時(shí)刻去了7位置并停在了7位置.

定義4對于泛化得到的泛化區(qū)域gi,本章將軌跡中通過gi中的點(diǎn)的部分用gi代替,從而得到泛化之后的用戶的軌跡tr?,并且不指定gi的時(shí)間,因?yàn)闀r(shí)間都被隱含在通過gi的這段時(shí)間內(nèi)部.如圖1所示,泛化區(qū)域g1,對于用戶2來說,用g1代替之后的軌跡列舉如下tr1={(1,t1),(2,t2),(3,t3),(4,t4),(0,t5),g1,(5,t7),(0,t8),(7,t9)}

表1 用戶軌跡數(shù)據(jù)表Tab.1 User trajectory data table

圖1 用戶軌跡圖Fig.1 Graph of user trajectory

圖2 相似軌跡集圖例Fig.2 Similar trajectory set example

定義5近鄰區(qū)域:近鄰區(qū)域Close Area指以泛化區(qū)域gi為原點(diǎn),以目標(biāo)用戶在敏感節(jié)點(diǎn)停下的時(shí)間間隔內(nèi)所能走過的路程s為半徑所得到的范圍,s=v*t,t表示目標(biāo)用戶在敏感節(jié)點(diǎn)停下的時(shí)間間隔,表示的含義是目標(biāo)用戶在時(shí)間間隔內(nèi)所能出現(xiàn)的所有可能的地點(diǎn),而去除掉了不符合條件的地點(diǎn).時(shí)間選用以目標(biāo)用戶在敏感節(jié)點(diǎn)停下的時(shí)間間隔的原因在于敏感節(jié)點(diǎn)存在泛化區(qū)域中并且攻擊者攻擊的目標(biāo)是目標(biāo)用戶,因此采用目標(biāo)用戶的停留時(shí)間更為合理.采用這種方式首先去除用戶在時(shí)間間隔內(nèi)不能到達(dá)的地點(diǎn),為泛化區(qū)域的選擇圈定了選擇范圍,為了更好地達(dá)到“以假亂真”的效果,更好地提高了數(shù)據(jù)的可用性.因?yàn)榧僭O(shè)有一種情況是將離目標(biāo)用戶很遠(yuǎn)的地點(diǎn)泛化到了泛化區(qū)域,那么攻擊者可以很明確地知道該地點(diǎn)目標(biāo)用戶是無法在時(shí)間間隔內(nèi)到達(dá)的,攻擊者知道這個(gè)點(diǎn)是假的.

例如圖1,假設(shè)用戶U1停在敏感節(jié)點(diǎn)6,用戶在停留時(shí)間內(nèi)所能到達(dá)的距離是17,那么以節(jié)點(diǎn)6為圓點(diǎn),半徑17范圍內(nèi)為近鄰區(qū)域,包含在近鄰區(qū)域的點(diǎn)只有節(jié)點(diǎn)5.

定義6相似軌跡集Similar Trajectory Set:所有的和目標(biāo)用戶的軌跡方向相似,時(shí)間相近,在gi泛化點(diǎn)中停下的軌跡都可以被認(rèn)為是相似軌跡集中的元素.通俗的說就是在一個(gè)相似軌跡集中的軌跡遵循相同的路徑,那么就認(rèn)為軌跡是相互相似的.

例如圖2,假設(shè)目標(biāo)用戶是U1,軌跡是tr1,那么在泛化區(qū)域g1中,包含節(jié)點(diǎn){5,6},停在泛化區(qū)域g1中的點(diǎn)的軌跡包括tr1,tr3,tr5,而tr5方向和目標(biāo)用戶相反,最終Similar Trajectory Set={tr1,tr3}.

定義7 gi泛化區(qū)域公開的概率:一般來說,最簡單的方式是將停在敏感節(jié)點(diǎn)的軌跡值和所有在相似軌跡集中的軌跡的比值來定義,即

定義8 k-泛化:我們說泛化之后的圖M?滿足k-泛化,當(dāng)且僅當(dāng){p≤k|?gi∈G},即所有的敏感節(jié)點(diǎn)的泛化之后的泛化區(qū)域gi公開的概率都滿足k-泛化.

定義9收益比:

p?表示在gi中找的前一個(gè)點(diǎn)的泛化區(qū)域公開的概率,p+表示在gi中找的后一個(gè)點(diǎn)的泛化區(qū)域公開的概率.

提出收益比的意義在于要使得用戶的安全性最高,安全性最高對于用戶來說是被發(fā)現(xiàn)的概率最低,即在泛化區(qū)域中和用戶類似的軌跡越多則用戶越不容易被發(fā)現(xiàn).假設(shè)在滿足條件的前提下,添加點(diǎn)1進(jìn)去泛化區(qū)域之后,用戶被發(fā)現(xiàn)的概率是1/2,而如果添加點(diǎn)2進(jìn)入泛化區(qū)域之后,用戶被發(fā)現(xiàn)的概率是1/5,那么在同等條件下選擇點(diǎn)2添加進(jìn)泛化區(qū)域.

假設(shè)情形1:添加點(diǎn)1進(jìn)入?yún)^(qū)域之后不滿足k-泛化,需要繼續(xù)添加;情形2:只添加點(diǎn)2,既使得用戶被發(fā)現(xiàn)的概率低,又比情形1添加的點(diǎn)數(shù)少.因此,收益比的提出既提高了數(shù)據(jù)的效用性又保障了目標(biāo)用戶擁有更好的安全性.

3 k-泛化——時(shí)空數(shù)據(jù)隱私保護(hù)的方法

本章提出了我們算法的框架以及算法的實(shí)現(xiàn),并用偽代碼表示.

框架分為2個(gè)階段,階段一將數(shù)據(jù)構(gòu)造成一張圖,查找用戶在敏感點(diǎn)停留時(shí)間內(nèi)所能出現(xiàn)的范圍,以此進(jìn)行范圍限定,將用戶不可能出現(xiàn)的點(diǎn)去除掉,那么只將近鄰區(qū)域中的點(diǎn)作為可能加入到泛化區(qū)域gi中的候選節(jié)點(diǎn);階段二:對敏感節(jié)點(diǎn)進(jìn)行泛化,根據(jù)k值決定泛化的次數(shù),直到所有的敏感節(jié)點(diǎn)泛化之后都滿足k-泛化,將泛化之后的圖發(fā)布軌跡匿名.

由定義9可知,目標(biāo)是限制攻擊者知道目標(biāo)用戶停在敏感節(jié)點(diǎn)的概率,實(shí)現(xiàn)的方式是通過泛化敏感節(jié)點(diǎn)并且使得目標(biāo)軌跡滿足k-泛化.當(dāng)有多個(gè)敏感節(jié)點(diǎn)存在時(shí),要使得目標(biāo)用戶的整個(gè)軌跡在任何一個(gè)泛化區(qū)域gi都要滿足k-泛化.其次,基于提高效用的目的,本章要對泛化區(qū)域中的點(diǎn)進(jìn)行優(yōu)化.要使得匿名后的數(shù)據(jù)有最大程度的效用,本章提出兩個(gè)準(zhǔn)則:

Rule1:泛化區(qū)域gi要盡量少;

Rule2:泛化區(qū)域gi中的點(diǎn)數(shù)要盡量少.

gi中的點(diǎn)數(shù)越少,被泛化的點(diǎn)數(shù)越少,數(shù)據(jù)越真實(shí),既保護(hù)了目標(biāo)用戶的隱私又能達(dá)到提高效用的目標(biāo).針對Rule1,泛化區(qū)域gi中的點(diǎn)要盡量少,本章在第2階段實(shí)現(xiàn).采用的方法是對各個(gè)節(jié)點(diǎn)分別加入泛化區(qū)域,計(jì)算收益比pr,根據(jù)pr挑選出點(diǎn)加入到泛化區(qū)域,既保證了數(shù)據(jù)的效用性又保證了用戶擁有更高的安全性;針對Rule2,倘若敏感節(jié)點(diǎn)和泛化區(qū)域gi相連,則將敏感節(jié)點(diǎn)加入泛化區(qū)域gi中.此方法使得泛化區(qū)域gi減少,提高了算法的效率也使得數(shù)據(jù)可用性提高.

本章提出一個(gè)算法:將隱私值k,軌跡數(shù)據(jù)集D S,敏感節(jié)點(diǎn)集S作為輸入,輸出一個(gè)匿名后的地圖M?.

算法1展示了算法的內(nèi)容.

步驟1:統(tǒng)計(jì)軌跡數(shù)據(jù)集形成一個(gè)圖(行1-2),getSet(數(shù)據(jù)集)方法表示將數(shù)據(jù)集放入到數(shù)據(jù)庫中,creatGraph(DS)表示將數(shù)據(jù)構(gòu)成為一個(gè)圖,G表示所有泛化區(qū)域以及泛化后的軌跡的集合.S為敏感節(jié)點(diǎn)集.

表1 參數(shù)估計(jì)模擬結(jié)果Tab.1 Simulation results of parametric estimation

步驟2:將一個(gè)敏感節(jié)點(diǎn)放入gi中,之后查找用戶在敏感節(jié)點(diǎn)停留的時(shí)間間隔,按用戶的r=v*t來計(jì)算用戶在停留時(shí)間段內(nèi)所能走過的路程,以泛化區(qū)域gi為圓心,路程r為半徑畫圓,找出在包含在圓內(nèi)的所有的節(jié)點(diǎn)(行3-13),candidateSet是可能被添加進(jìn)泛化區(qū)域的候選節(jié)點(diǎn),即在圓內(nèi)中的點(diǎn)的集合,gi是泛化區(qū)域,p是存在路徑,三元組＜gi,vi,p＞表示和泛化區(qū)域gi之間存在路徑.

步驟3:判斷是否有敏感節(jié)點(diǎn)在圓內(nèi)并且和泛化區(qū)域相連,若有則直接加入到泛化區(qū)域(行14-15),若沒有則以此圓為范圍,泛化區(qū)域中的點(diǎn)在圓內(nèi)中選擇,遍歷在圓內(nèi)并且和泛化區(qū)域gi中的點(diǎn)相連的點(diǎn)(行16-17).

步驟4:尋找停留在泛化區(qū)域的路徑并且方向要和目標(biāo)用戶的路徑方向一致的前一個(gè)節(jié)點(diǎn),之后計(jì)算概率p,記為p?;之后尋找后一個(gè)節(jié)點(diǎn),加入計(jì)算概率p,記為p+,利用收益比,用收益比和1比較,假若比1小則將前一個(gè)點(diǎn)加入泛化區(qū)域,否則將后一個(gè)點(diǎn)加入到泛化區(qū)域,將符合在圓內(nèi)且和泛化區(qū)域gi相連的點(diǎn)遍歷完成(行18-31).Similar Trajectory Set(g,candidateSet[i])候選節(jié)點(diǎn)添加到泛化區(qū)域gi之后的相似軌跡集,Eq表示泛化之后用戶軌跡,p?表示候選集合中第i個(gè)節(jié)點(diǎn)加入泛化區(qū)域之后的概率,p+表示候選集合中第i+1個(gè)節(jié)點(diǎn)加入泛化區(qū)域之后的概率,pr表示收益比,fNode表示概率最小的點(diǎn),G.add(gi,Eq)表示將泛化區(qū)域gi以及泛化后的相似軌跡添加到G中.至此將p值最小的點(diǎn)加入到了泛化區(qū)域,假若此時(shí)滿足k-泛化則結(jié)束,若不滿足,則將此泛化區(qū)域作為圓點(diǎn)繼續(xù)按上一步驟進(jìn)行循環(huán),直到滿足k-泛化.直到所有的敏感節(jié)點(diǎn)都滿足k-泛化.

步驟5:發(fā)布匿名后的地圖M?,anonymizeMap(M,G)表示將M匿名化為地圖M?,M?表示匿名后的發(fā)布的地圖.

圖3、4和5展示了算法流程的例子.敏感節(jié)點(diǎn)是6和7,目標(biāo)用戶為U1,所有用戶的軌跡如下所示:

圖3 只有一個(gè)點(diǎn)的泛化區(qū)域g1Fig.3 Generalization region g1with just one vertex

從單個(gè)的敏感節(jié)點(diǎn)6開始,泛化點(diǎn)g1只包含節(jié)點(diǎn)6.此時(shí)停在敏感節(jié)點(diǎn)的只有目標(biāo)用戶U1,造成了隱私泄露,因此擴(kuò)大泛化點(diǎn)g1.如圖3所示.首先第一步尋找范圍.假設(shè)用戶的速度是30 km/h,停留的時(shí)間是2個(gè)間隔,即1 h,那么圓的半徑是30 km,由圖中可知在范圍內(nèi)的點(diǎn)包括{4,5},若將節(jié)點(diǎn)4加入到g1中,此時(shí)停在g1點(diǎn)的軌跡包括tr1和tr2,分別表示為tr1={(2,t1),(3,t2),g1,(7,t7),(0,t8),(0,t9)},tr2={(1,t1),(2,t2),(3,t3),g1,(5,t7),(0,t8), (7,t9)},形成的相似軌跡集是{tr1,tr2}此時(shí)p?(4)=0.5;若將節(jié)點(diǎn)5加入g1中,此時(shí)停在g1的軌跡包括tr1、tr2、tr3和tr5,因?yàn)閠r5方向和目標(biāo)用戶的方向相反,因此去除,此時(shí)相似軌跡集中的軌跡是{tr1,tr2,tr3},p+(5)=1/3.收益比pr=p?/p+=3/2,因此將節(jié)點(diǎn)5加入到g1中.此時(shí)g1中泛化的點(diǎn)是{5,6},如圖4所示.

若k≥1/3,則泛化過程結(jié)束,若k＜1/3,假設(shè)k=1/4,則繼續(xù)將g1泛化,第一步找范圍,范圍擴(kuò)大到{3,4,7},首先判斷節(jié)點(diǎn)7是敏感節(jié)點(diǎn),加入到g1,當(dāng)把節(jié)點(diǎn)3放入g1時(shí),此時(shí)的相似軌跡集是{tr1,tr2,tr3,tr4},p?(3)=1/4,當(dāng)把節(jié)點(diǎn)4放進(jìn)g1時(shí),p+(4)=1/3,收益比pr=p?/p+=3/4,將節(jié)點(diǎn)3放入g1,此時(shí)滿足k-泛化,結(jié)束泛化.最終g1中的節(jié)點(diǎn)是{3,5,6,7},完成匿名,發(fā)布匿名圖M?.如圖5所示.

圖4 有兩個(gè)點(diǎn)的泛化區(qū)域g1Fig.4 Generalization region g1with two nodes

圖5 最終的泛化區(qū)域g1Fig.5 Final generalization region g1

4 實(shí)驗(yàn)

本章評估算法的性能,評估數(shù)據(jù)集采用2個(gè)真實(shí)的軌跡數(shù)據(jù)集,數(shù)據(jù)集是共享單車數(shù)據(jù),所在城市是美國紐約.分別是2016年的數(shù)據(jù)和2017年的數(shù)據(jù).數(shù)據(jù)量為126 000條.頂點(diǎn)為603個(gè),邊數(shù)為124 287條.實(shí)驗(yàn)通過改變給定的k值的大小來說明各項(xiàng)指標(biāo)的變化.

泛化區(qū)域的大小,算法泛化敏感節(jié)點(diǎn)周圍的軌跡,通過用一個(gè)泛化區(qū)域代表軌跡的一部分,更換泛化區(qū)域中軌跡的節(jié)點(diǎn),從而到達(dá)隱藏目標(biāo)軌跡的目的.因此,在泛化區(qū)域中的軌跡是偽軌跡.直觀來說,如果泛化的區(qū)域越大,內(nèi)部包含的節(jié)點(diǎn)越多,泛化區(qū)域中的偽軌跡越多,軌跡被扭曲越多,發(fā)布的數(shù)據(jù)的效用降低.討論一個(gè)極端的情況,假設(shè)所有用戶經(jīng)過的所有的興趣點(diǎn)都包含在一個(gè)泛化區(qū)域gi中,那么所有的軌跡都被偽裝了,發(fā)布出的數(shù)據(jù)完全沒有效用價(jià)值.因此,泛化區(qū)域的大小是評價(jià)算法效用的一個(gè)有用的指標(biāo).而算法運(yùn)行的時(shí)間也是評判算法效用的一種方式,因此時(shí)間也可以作為一個(gè)評判標(biāo)準(zhǔn).其次泛化率,即泛化軌跡和總的軌跡數(shù)量的比值,也體現(xiàn)了數(shù)據(jù)的效用性,若泛化率很高則表明數(shù)據(jù)的可用性很低,因此泛化率也可以作為評判算法優(yōu)劣的標(biāo)準(zhǔn).其次也列舉了敏感節(jié)點(diǎn)n的個(gè)數(shù)對平均泛化區(qū)域的影響.

圖6展示了參數(shù)k是如何影響平均泛化區(qū)域的大小的.實(shí)驗(yàn)結(jié)果是隨著k值的減小,平均泛化區(qū)域的大小增加.因?yàn)閗值越小,意味著更加嚴(yán)格的隱私,需要擴(kuò)大泛化區(qū)域的大小才能滿足k-泛化的要求,結(jié)果是一個(gè)較低水平的效用.

圖6 參數(shù)k對平均泛化區(qū)域大小的影響Fig.6 Average generalization area size for the parameters k limit

圖7顯示了不同的k值對算法運(yùn)行時(shí)間的影響.實(shí)驗(yàn)結(jié)果表明隨著k值越大,運(yùn)行時(shí)間越小.原因在于k值越大,所需要擴(kuò)大泛化區(qū)域的次數(shù)減小,算法運(yùn)行時(shí)間減少,效率有所提高.

圖7 參數(shù)k對運(yùn)行時(shí)間的影響Fig.7 Time performance for the parameters k limit

圖8展示了不同的k值對泛化率的影響.實(shí)驗(yàn)結(jié)果表明k值越大,泛化率越小.因?yàn)閗值增大,泛化區(qū)域中的點(diǎn)變小,通過泛化區(qū)域的軌跡自然減少,泛化率降低.由實(shí)驗(yàn)結(jié)果來看,在k=1/30時(shí),泛化率也很小,而此時(shí)的k對于用戶來說足夠保護(hù)自己的隱私,攻擊者發(fā)現(xiàn)用戶的概率很小,因此,本文的算法數(shù)據(jù)的可用性可以保證.

圖8 參數(shù)k對泛化率的影響Fig.8 Generalization ratio for the parameters k limit

圖9展示了敏感節(jié)點(diǎn)n的個(gè)數(shù)對平均泛化區(qū)域的影響.當(dāng)敏感節(jié)點(diǎn)數(shù)固定時(shí),k的值越小表明用戶所要求的安全性越高,泛化區(qū)域的大小自然變大.當(dāng)n=30時(shí),k值是1/30時(shí),平均泛化區(qū)域的大小對比于總的頂點(diǎn)數(shù)來說是很小的,而此時(shí)的k值完全能夠保證用戶的隱私.

圖9 敏感節(jié)點(diǎn)n的個(gè)數(shù)對平均泛化區(qū)域的影響Fig.9 The inf l uence of the number of sensitive nodes n on the average generalization region

5 結(jié)論

本文提出了k-泛化的概念,通過泛化敏感節(jié)點(diǎn)來達(dá)到保護(hù)用戶隱私的目的.本文的方法限制了一個(gè)用戶停止在一個(gè)敏感位置的概率來抵抗強(qiáng)大的攻擊者,攻擊者知道基本的地圖.本文將用戶可能出現(xiàn)的點(diǎn)進(jìn)行范圍限定,更好地提高了數(shù)據(jù)的可用性;提出了k-泛化的概念,泛化的過程也出于數(shù)據(jù)可用性的考慮;對泛化節(jié)點(diǎn)的選擇采用基于安全性最高的原則;當(dāng)多個(gè)敏感節(jié)點(diǎn)存在時(shí),本文出于數(shù)據(jù)效用的目的做了簡單的優(yōu)化.提出的算法既實(shí)現(xiàn)了最小的泛化又提高了用戶的安全性.并且實(shí)驗(yàn)測試表明,本文的方法是能夠保持實(shí)用性,同時(shí)滿足用戶提供的隱私參數(shù).本文需要說明的是k-泛化方法能夠很好的保護(hù)用戶的隱私,但是并不能說明是最優(yōu)的,即范圍最小或覆蓋點(diǎn)數(shù)最少.本文利用兩個(gè)準(zhǔn)則Rule1和Rule2最大程度的保障算法達(dá)到最優(yōu).未來的方向是將隱私保護(hù)進(jìn)行擴(kuò)展,例如對用戶間的關(guān)系進(jìn)行挖掘并且保護(hù),從而使得用戶的隱私更加得到更大范圍的保護(hù).

[1]XIAO Y,XIONG L.Protecting Locations with Dif f erential Privacy under Temporal Correlations[C]//The ACM Sigsac Conference on Computer and Communications Security.New York:ACM,2014:1298-1309.

[2]GEDIK B,LIU L.Protecting location privacy with personalized k-anonymity:Architecture and algorithms[J]. IEEE Transactions on Mobile Computing,2008,7(1):1-18.

[3]CICEK A E,NERGIZ M E,SAYGIN Y.Ensuring location diversity in privacy-preserving spatio-temporal data publishing[J].The VLDB Journal,2014,23(4):609-625.

[4]HUNDEPOOL A J,WILLENBORG L C R J.Mu-and tau-argus:Software for statistical disclosure control[J].

[5]SAMARATI P.Protecting respondent’s identities in microdata release[J].IEEE Trans Knowl Data Eng,2001, 13(6):1010-1027.

[6]YU T,JAJODIA S.Secure Data Management in Decentralized Systems[M].New York:Springer,2007.

[7]田秀霞,王曉玲,高明,等.數(shù)據(jù)庫服務(wù)-安全與隱私保護(hù)[J].軟件學(xué)報(bào),2010(5):991-1006.

[8]ABUL O,BONCHI F,NANNI M.Never Walk Alone:Uncertainty for Anonymity in Moving Objects Databases[C]//IEEE,International Conference on Data Engineering.[S.l.]:IEEE Computer Society,2008: 376-385.

[9]ATZORI M,ATZORI M,SAYGIN Y.Towards trajectory anonymization:A generalization-based approach[C]// Sigspatial ACM Gis 2008 International Workshop on Security and Privacy in Gis and Lbs.New York:ACM, 2008:52-61.

[10]SWEENEY L.K-anonymity:A model for protecting privacy[J].International Journal on Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570.

[11]MACHANAVAJJHALA A,KIFER D,GEHRKE J.L-diversity:Privacy beyond k-anonymity[J].Acm Transactions on Knowledge Discovery from Data,2007,1(1):3.

[12]LI N H,LI T C,VENKATASUBRAMANIAN S.t-Closeness:Privacy Beyond k-Anonymity and l-Diversity[C]// IEEE,International Conference on Data Engineering.[S.l.]:IEEE,2007:106-115.

[13]MAO J,SONG Q,JIN C,et al.TSCluWin:Trajectory Stream Clustering over Sliding Window[M]//Database Systems for Advanced Applications.US:Springer,2016.

[14]ZHANG Z,WANG Y,MAO J,et al.DT-KST:Distributed top-k similarity query on big trajectory streams[J]. 2017:199-214.

[15]WU W,XIAO Y,WANG W,et al.k-symmetry model for identity anonymization in social networks[C]//EDBT 2010,International Conference on Extending Database Technology.Switzerland:DBLP,2010:111-122.

[16]DWORK C.Dif f erential privacy[J].Lecture Notes in Computer Science,2006,4052(2):1-12.

[17]KELLARIS G,PAPADOPOULOS S,XIAO X,et al.Dif f erentially private event sequences over inf i nite streams[J].Proceedings of the Vldb Endowment,2014,7(12):1155-1166.

[18]CHEN R,FUNG B C M,DESAI B C,et al.Dif f erentially private transit data publication:a case study on the montreal transportation system[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2012:213-221.

[19]CAO Y,YOSHIKAWA M.Dif f erentially private real-time data release over inf i nite trajectory streams[C]//IEEE International Conference on Mobile Data Management.[S.l.]:IEEE,2015:68-73.

[20]MIGUEL E ANDR′ES,NICOLAS E BORDENABE,LONSTANTINOS Chatzikokolakis,et al.Geo-indistinguishability:Dif f erential privacy for location-based systems[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications security.New York:ACM,2013:901-914.

(責(zé)任編輯:張晶)

Privacy preserving method of spatio-temporal data based on k-generalization technology

YANG Zi,NING Bo,LI Yi
(College of Information Science and Technology,Dalian Maritime University, Dalian Liaoning 116026,China)

In recent years,more and more devices based on location system,resulting in a large amount of location information by the mobile device users to access and use,from the perspective of data mining,the data is of immeasurable value,but in terms of personal privacy,people don’t want their information to be leaked and used to sparked strong privacy concerns.At present,many papers have proposed privacy protection technology to solve this problem.Generally speaking,there are several categories of interference, suppression and generalization.In order to protect the privacy of personal spatio-temporal data,this paper proposes a method of k-generalization.To limit the scope of the user may appear,improve the availability of data;selection of nodes to generalization so that the user’s maximum security;considers multiple sensitive node solutions exist under the condition,and for the purpose of improving the data utility on a number of sensitive nodesare optimized.Finally,the performance of the algorithm is evaluated by experiments,and it is proved that the algorithm is ef f ective to protect personal privacy.

privacy;spatio-temporal data;anonymous;generalization

TP391

A

10.3969/j.issn.1000-5641.2017.05.016

1000-5641(2017)05-0174-12

2017-06-20

國家自然科學(xué)基金廣東聯(lián)合基金重點(diǎn)項(xiàng)目(U1401256);遼寧省自然科學(xué)基金(201602094)

楊姿,女,碩士研究生,研究方向?yàn)闀r(shí)空數(shù)據(jù)隱私保護(hù).E-mail:winni103@vip.qq.com.

寧博,男,副教授,碩士生導(dǎo)師,研究方向?yàn)閿?shù)據(jù)管理,隱私保護(hù). E-mail:ningbo@dlmu.edu.cn.