基于k—匿名的軌跡數(shù)據(jù)隱私發(fā)布研究綜述

趙凱毅，朱麟，路士兵

摘 要：隨著移動定位技術(shù)的發(fā)展，大量移動軌跡數(shù)據(jù)使信息泄露于公開的互聯(lián)空間中，使攻擊者可以通過計(jì)算推理挖掘軌跡信息。軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)是近年來網(wǎng)絡(luò)空間安全領(lǐng)域研究的熱點(diǎn)問題。為了防止該類軌跡數(shù)據(jù)隱私的泄露，通常采用k-匿名技術(shù)實(shí)現(xiàn)軌跡的隱私保護(hù)。該技術(shù)在國內(nèi)外研究中取得了一定的成果。本文闡述了軌跡隱私保護(hù)的相關(guān)定義及研究方法，對國內(nèi)外移動軌跡數(shù)據(jù)k-匿名隱私保護(hù)研究的成果進(jìn)行了總結(jié)，并介紹了國內(nèi)外有關(guān)軌跡數(shù)據(jù)k-匿名隱私保護(hù)研究的相關(guān)技術(shù)。同時(shí)對國內(nèi)外的技術(shù)進(jìn)行了比較，詳細(xì)敘述了國外與國內(nèi)各自方法的優(yōu)點(diǎn)，指出了研究中存在的不足與今后研究的大致方向。

關(guān)鍵詞：軌跡數(shù)據(jù)；軌跡數(shù)據(jù)發(fā)布；隱私保護(hù)；k-匿名

中圖分類號：T391 文獻(xiàn)標(biāo)識碼：A

A Research Review on Privacy-Preserving of Trajectory Data

Publishing Based on K-Anonymity

ZHAO Kaiyi，ZHU Lin，LU Shibing

（Department of Electronics，China Maritime Police Academy，Ningbo 315801，China）

Abstract：With the development of mobile localization technology，large amounts of mobile trajectory data expose information to open cyberspace，so that hackers can dig out trajectory data by computing and reasoning.Recently，privacy-preserving of trajectory data publishing is one of the hottest topics in Internet security.In order to prevent the disclosure of trajectory data，k-anonymous privacy preserving model is widely applied，on which some research achievements have been made both at home and abroad.This paper presents some related definitions and research methods in trajectory data privacy preserving，summarizes domestic and abroad research achievements on the k-anonymous privacy preserving of mobile trajectory data，introduces and compares related technology on the k-anonymous privacy preserving of mobile trajectory data both at home and abroad，elaborates on respective advantages of each method at home and abroad，and points out the limitation in previous studies and the direction in future studies.

Keywords：trajectory data；trajectory data publishing；privacy preserving；k-anonymity

1 引言（Introduction）

隨著移動設(shè)備和定位技術(shù)的發(fā)展，移動軌跡數(shù)據(jù)的隱私保護(hù)也受到了人們的關(guān)注。軌跡數(shù)據(jù)不僅蘊(yùn)含著豐富的個(gè)人、位置等顯性信息，而且還可以通過推理計(jì)算軌跡的隱性信息，挖掘移動終端設(shè)備的軌跡行為特征、行為模式和行為習(xí)慣，從而獲取設(shè)備的信息數(shù)據(jù)，導(dǎo)致設(shè)備對象的隱私泄露。為有效保證數(shù)據(jù)的安全性，移動軌跡數(shù)據(jù)的隱私保護(hù)成為迫切需要解決的問題。

當(dāng)前，普遍采用的軌跡隱私方法是基于k-匿名模型[1，2]，它是由Gruteser等人提出的。該技術(shù)是指在相關(guān)空間領(lǐng)域中，給定該空間節(jié)點(diǎn)位置形成的軌跡。當(dāng)任意一條軌跡T在任意采樣時(shí)刻ti時(shí)，當(dāng)至少有k-1條軌跡在相應(yīng)的采樣位置上與T泛化為同一區(qū)域時(shí)，則滿足軌跡的k-匿名。k-匿名的技術(shù)的核心思想是將敏感屬性泛化，使得單條記錄無法和其他k-1條記錄區(qū)分開，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)。

本文闡述了軌跡隱私保護(hù)的相關(guān)定義及的研究方法，對國內(nèi)外移動軌跡數(shù)據(jù)k-匿名隱私保護(hù)研究的成果進(jìn)行了總結(jié)，并介紹了國內(nèi)外有關(guān)軌跡數(shù)據(jù)k-匿名隱私保護(hù)研究的相關(guān)技術(shù)。同時(shí)對國內(nèi)外的技術(shù)進(jìn)行了比較，詳細(xì)敘述了國外與國內(nèi)各自方法的優(yōu)點(diǎn)，指出了研究中存在的不足與今后研究的大致方向。

2 軌跡隱私保護(hù)方法（Privacy preserving methods）

軌跡數(shù)據(jù)發(fā)布中的隱私保護(hù)方法主要是假數(shù)據(jù)法、抑制法和泛化法。其中，假數(shù)據(jù)法是在原數(shù)據(jù)的基礎(chǔ)上，采用與原始軌跡不同的信息來抵御攻擊，同時(shí)保證數(shù)據(jù)統(tǒng)計(jì)屬性的真實(shí)性。該方法計(jì)算量較小，容易產(chǎn)生數(shù)據(jù)存儲量過大而導(dǎo)致數(shù)據(jù)的有效性降低，一般用于數(shù)據(jù)量不大的情況，可以體現(xiàn)方法的可用性；抑制法可以有條件地選擇發(fā)布的數(shù)據(jù)，對敏感數(shù)據(jù)和頻繁訪問數(shù)據(jù)則不再選擇發(fā)布，但是計(jì)算方法時(shí)間性能太大，會導(dǎo)致數(shù)據(jù)信息的損失量過大，一般也用于訓(xùn)練計(jì)算數(shù)據(jù)量較小的軌跡集合；泛化法是通過獲取軌跡上的位置采樣點(diǎn)，將這些采樣點(diǎn)泛化為匿名區(qū)域，從而實(shí)現(xiàn)隱私保護(hù)。軌跡k-匿名技術(shù)就是一種基于泛化方法的隱私保護(hù)技術(shù)，可以平衡隱私保護(hù)度量和增加服務(wù)質(zhì)量。endprint

3 軌跡k-匿名隱私保護(hù)技術(shù)（K-Anonymous privacy

preserving technology）

3.1 （k，δ）-匿名技術(shù)

軌跡（k，δ）-匿名的隱私保護(hù)技術(shù)最先是由國外研究者Abul等人[3]提出的。經(jīng)過大量研究與分析，移動軌跡數(shù)據(jù)抽樣和定位系統(tǒng)存在不精確性，而Abul與其他幾位研究者正是利用這一不確定性，提出了軌跡（k，δ）-匿名的隱私保護(hù)技術(shù)。該技術(shù)在基于簇的方法基礎(chǔ)上，實(shí)現(xiàn)了基于簇的軌跡（k，δ）-匿名。

所謂（k，δ）-匿名模型，是指在不確定性閾值δ和匿名閾值k給出的情況下，當(dāng)且僅當(dāng)|D|≥k時(shí)，軌跡集合D滿足（k，δ）-匿名。同時(shí)D中任意兩條軌跡tr1和tr2均滿足Coloc（tr1，tr2）。如果對于每一條軌跡，在該軌跡距離δ的半徑區(qū)域內(nèi)，應(yīng)當(dāng)至少存在與當(dāng)前軌跡相似度較高的k-1條軌跡，δ越大，則說明通過聚類的組就越大，信息發(fā)布的安全性就越高，但信息損失率越高。

為了在提高信息隱私保護(hù)安全性的同時(shí)降低信息的損失率，NWA（Never Walk Alone）方法[3]將分布于同一時(shí)間段內(nèi)的軌跡存儲到一個(gè)等價(jià)類中，通過聚類尋找空間距離相似的軌跡，并滿足k-匿名模型。該方法的優(yōu)點(diǎn)可以采用歐式距離計(jì)算軌跡之間的距離。但是當(dāng)數(shù)據(jù)量較多時(shí)，聚類使得當(dāng)前軌跡的離群點(diǎn)增加，數(shù)據(jù)有效性受到影響。因此，在該問題的基礎(chǔ)上，W4M[4]在NWA的基礎(chǔ)上做了優(yōu)化，采用編輯距離[5]來度量軌跡上采樣點(diǎn)間的距離，使軌跡上離群點(diǎn)的數(shù)量較之前的方法相比有了明顯的減少，降低了所舍棄數(shù)據(jù)的數(shù)量，更好且更有效地預(yù)防了攻擊者使用特定的位置信息對發(fā)布的軌跡數(shù)據(jù)隱私進(jìn)行攻擊，同時(shí)保證了所發(fā)布的軌跡數(shù)據(jù)具有較高的質(zhì)量。

上述的幾種方法都將整條軌跡上的所有的采樣點(diǎn)進(jìn)行了泛化的處理，但忽視了準(zhǔn)標(biāo)識符QI的屬性與其他屬性間所存在的區(qū)別。因此，Yarovoy等人[6]針對此問題，對動態(tài)QI的屬性進(jìn)行了處理，查找所有時(shí)刻內(nèi)移動對象的聚集距離最小的k-1個(gè)對象，并將該k-1個(gè)對象匿名到同一匿名的區(qū)域內(nèi)，更加全面地做到了在泛化處理整條軌跡上所有采樣點(diǎn)的同時(shí)，兼顧準(zhǔn)標(biāo)識符屬性與其他軌跡間屬性所存在的區(qū)別，提高了數(shù)據(jù)發(fā)布的服務(wù)質(zhì)量。

3.2 （k，l）-匿名技術(shù)

軌跡（k，l）-匿名技術(shù)[7]與上述國外軌跡（k，δ）-匿名的隱私保護(hù)技術(shù)有所不同，該技術(shù)由RASUAR等人提出，是指在滿足軌跡的k-匿名的基礎(chǔ)上，同時(shí)滿足軌跡l多樣性的軌跡的集合。從構(gòu)建軌跡k-匿名集的原則中我們了解到，在構(gòu)建軌跡k-匿名集的同時(shí)，要使集合內(nèi)的k條軌跡具有相似性，且轉(zhuǎn)化后的數(shù)據(jù)庫與原始數(shù)據(jù)庫的信息扭曲度要盡可能小，這便是所說的NP難的問題。可是，假如軌跡在集合內(nèi)的相似性過高，同樣會導(dǎo)致隱私的泄露，因?yàn)樵诩现熊壽E都是相鄰且靠近的，如果每條軌跡之間的相似性過高，所有移動對象的運(yùn)動方式與路徑便會很容易被攻擊者分析了解到，從而降低了隱私的保護(hù)程度。所以，在構(gòu)造軌跡k-匿名集時(shí)，要盡量避免出現(xiàn)相似的軌跡形狀。

為了避免這一問題，文獻(xiàn)[8]提出了一種面向個(gè)體的、個(gè)性化擴(kuò)展的l-多樣性隱私匿名模型。該模型雖然對傳統(tǒng)的匿名模型進(jìn)行了優(yōu)化，但卻只考慮到了軌跡的時(shí)間與空間屬性。基于軌跡形狀多樣性的軌跡（k，l）-匿名技術(shù)，在考慮了軌跡的時(shí)間與空間屬性的同時(shí)，還考慮到了軌跡的形狀屬性，使匿名集內(nèi)的軌跡在保持相近距離與相似關(guān)聯(lián)的基礎(chǔ)上，依然保持了一定的形狀多樣性，避免了因高度的相似性而導(dǎo)致隱私泄露的可能。

軌跡（k，l）-匿名技術(shù)中所運(yùn)用的SP算法是以文獻(xiàn)[3]中的NWA算法的框架為基礎(chǔ)所提出的，分為軌跡數(shù)據(jù)預(yù)處理、數(shù)據(jù)聚類、數(shù)據(jù)分組和數(shù)據(jù)（k，l）-匿名處理。數(shù)據(jù)預(yù)處理時(shí)，對所有的軌跡進(jìn)行遍歷，分配并選擇時(shí)間段相等的軌跡，放置于同一個(gè)等價(jià)類中。如果某個(gè)等價(jià)類中的軌跡不足k條，為使損失的信息降低至最小，則通過貪心算法查找另一個(gè)等價(jià)類。通過重復(fù)同步化處理，將兩個(gè)等價(jià)類合并為一個(gè)新的等價(jià)類，以此類推，最后獲得一系列軌跡數(shù)不小于k的等價(jià)類。

軌跡（k，l）-匿名技術(shù)中的SP算法與NWA類似，但相比之下，SP算法將軌跡間的多樣性考慮了進(jìn)去，即在相似復(fù)雜度得以保證的前提下，更有效地實(shí)現(xiàn)了隱私的保護(hù)。并且該算法使大量高度相似的軌跡存在于同一集合中的情況得到了避免，很好地實(shí)現(xiàn)了軌跡的（k，l）匿名，提升了數(shù)據(jù)的可用性。雖然該技術(shù)考慮到了軌跡的多樣性，卻未詳細(xì)考慮軌跡集合經(jīng)過較大敏感區(qū)的情況，故也存在一定不足。

3.3 （k，δ，Δ）-匿名技術(shù)

通過以上幾種基于k匿名隱私保護(hù)技術(shù)的介紹，我們大致可以了解到：傳統(tǒng)的關(guān)于軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)的研究多數(shù)都將聚類的方法運(yùn)用在其中。在很多情況下，其相關(guān)算法都只注重對于每條軌跡的隱私保護(hù)，而忽略了對軌跡聚類組特征的保護(hù)。通過相關(guān)理論研究與實(shí)驗(yàn)的論證，一些學(xué)者發(fā)現(xiàn)，在用聚類技術(shù)產(chǎn)生相應(yīng)的軌跡數(shù)據(jù)后，對該軌跡數(shù)據(jù)進(jìn)行二次聚類，可得到一系列特征，而該特征與在發(fā)布之前的原始軌跡數(shù)據(jù)所擁有的聚類組特征高度相似，從而可能導(dǎo)致隱私泄露。因此，為了有效地預(yù)防這種軌跡聚類的二次攻擊，福州大學(xué)吳英杰等人[9]提出了一種（k，δ，Δ）-匿名模型和基于該模型的聚類雜交隱私保護(hù)軌跡數(shù)據(jù)發(fā)布算法CH-TDP。它是在（k，δ）-匿名模型的基礎(chǔ)上，以（k，δ）-匿名模型為切入點(diǎn)，對聚類分組進(jìn)行雜交，再進(jìn)行組內(nèi)擾亂。通過控制組間擾亂的程度，達(dá)到保護(hù)聚類組的共同特征。（k，δ，Δ）-匿名模型的目的是在抵御發(fā)布軌跡數(shù)據(jù)遭受二次聚類攻擊的前提下，保證發(fā)布軌跡數(shù)據(jù)的質(zhì)量不低于質(zhì)量閾值Δ。

通過了大量的仿真實(shí)驗(yàn)和數(shù)據(jù)分析驗(yàn)證了軌跡（k，δ，Δ）-匿名的隱私保護(hù)技術(shù)中（k，δ，Δ）-匿名模型及CH-TDP算法的有效性。實(shí)驗(yàn)的相關(guān)結(jié)果證明，CH-TDP算法與（k，δ，Δ）-匿名模型不僅可以有效地抵御軌跡聚類過程中所產(chǎn)生的二次聚類攻擊，同時(shí)，該匿名技術(shù)還很好地保證了匿名數(shù)據(jù)的質(zhì)量，確保了軌跡的相似度，控制了區(qū)域查詢結(jié)果的誤差率，在k匿名隱私保護(hù)研究方面起到了至關(guān)重要的作用，更全面地實(shí)現(xiàn)了移動軌跡數(shù)據(jù)的隱私保護(hù)這一根本目的。endprint

4 基于k-匿名技術(shù)的軌跡隱私保護(hù)技術(shù)的比較與

分析（Comparison and analysis of trajectory

data privacy preserving technology based on

k-anonymity）

分析了三種較為典型的基于k-匿名的軌跡隱私保護(hù)技術(shù)，分別詳細(xì)敘述了各自技術(shù)的主要原理、所用方法、重要用途，以及各自存在的優(yōu)點(diǎn)及其所存在的一定局限性與不足。本文以表格的形式進(jìn)行比較。

5 結(jié)論（Conclusion）

在當(dāng)前數(shù)據(jù)隱私保護(hù)研究領(lǐng)域，對于軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)研究很廣泛。本文中所提到的幾種軌跡k-匿名技術(shù)都是比較成功的應(yīng)用案例。軌跡（k，δ）-技術(shù)模型、軌跡（k，l）-技術(shù)模型、軌跡（k，δ，Δ）-匿名技術(shù)都是在k-匿名模型的基礎(chǔ)上所提出來的。這些模型都有各自新穎之處，但其算法的精確性還有待改進(jìn)。因此，雖然移動軌跡數(shù)據(jù)隱私保護(hù)是一個(gè)空間安全領(lǐng)域的研究熱點(diǎn)，但其技術(shù)還不夠成熟。目前，關(guān)于軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)對模型和算法的研究相對較多，且有不少的學(xué)者進(jìn)行了研究并提出了新的技術(shù)與算法。未來若能成功且全面地將軌跡數(shù)據(jù)隱私保護(hù)的研究成果進(jìn)行實(shí)際應(yīng)用，將會更好地促進(jìn)信息共享和融合。

參考文獻(xiàn)（References）

[1] Marco Gruteser，Dirk Grunwald.Anonymous Usage of Loca-tion-Based Services through Spatial and Temporal Cloaking[C].Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，San Francisco，2003：31-42.

[2] 霍崢，孟小峰.軌跡隱私保護(hù)技術(shù)研究[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1820-1830.

[3] O.Abul，F(xiàn).Bonchi and M.Nanni.Never walk alone：Uncertainty for anonymity in moving objects databases[C].Proceedings of the IEEE 24th International Conference on Data Engineering.IEEE，2008：376-385.

[4] O.Abul，F(xiàn).Bonchi，M.Nanni.Anonymization of Moving Objects Databases by Clustering and Perturbation[J].Information Systems，2010，35（8）：884-910.

[5] CHEN L，OZSU M T，ORIA V.Robust and fast similarity search for moving object trajectories[C].Proceedings of the 2005 ACM SIGMOD international conference on Management of data，2005：491-502.

[6] Yarovoy，R.，Bonchi，F(xiàn).，Lakshmanan，S..Anonymizing Moving Objects：How to Hide a MOB in a Crowd？[C].In：12th International Conference on Extending Database Technology，2009：72-83.

[7] Trujillo-R，Domingo-Ferrer J.On the privacy offered by（k，δ）anonymity[J].Information Systems，2014，38（4）：491-494.

[8] 孫丹丹，羅永龍，范國婷，等.基于軌跡形狀多樣性的隱私保護(hù)算法[J].計(jì)算機(jī)應(yīng)用，2016，36（6）：1544-1551.

[9] 吳英杰，唐慶明，倪巍偉，等.基于聚類雜交的隱私保護(hù)軌跡數(shù)據(jù)發(fā)布算法[J].計(jì)算機(jī)研究與發(fā)展，2013，50（3）：578-593.

作者簡介：

趙凱毅（1997-），男，本科生.研究領(lǐng)域：信息安全，數(shù)據(jù)挖掘.

朱 麟（1984-），男，碩士，講師.研究領(lǐng)域：智能計(jì)算，數(shù)據(jù)挖掘，信息安全.

路士兵（1978-），男，碩士，副教授.研究領(lǐng)域：信息安全，嵌入式系統(tǒng).endprint