基于敏感性分級(jí)的(k, δ, ai)-匿名模型

劉 陽(yáng)，祝永志，遲玉良

(曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276800)

0 引言

近年來(lái)，移動(dòng)社交網(wǎng)絡(luò)的快速發(fā)展為人們的生活帶來(lái)便利的同時(shí)也產(chǎn)生了大量的軌跡數(shù)據(jù)[1]。這些軌跡數(shù)據(jù)中包含了大量的個(gè)人信息。通過(guò)對(duì)這些數(shù)據(jù)的挖掘、分析，就能夠獲取個(gè)人隱私信息，如單位地址、居住地址、經(jīng)常去的場(chǎng)所等，直接對(duì)這些數(shù)據(jù)進(jìn)行發(fā)布將會(huì)造成個(gè)人隱私信息的披露，甚至對(duì)人身安全造成威脅[2-3]。所以，如何在共享這些軌跡數(shù)據(jù)的同時(shí)，有效地保護(hù)個(gè)人隱私以及防止敏感信息的披露，已成為隱私保護(hù)領(lǐng)域研究的重點(diǎn)。

目前移動(dòng)用戶隱私保護(hù)方法大致可以分成三類[4-6]：(1)假數(shù)據(jù)法，是指用假軌跡替代真實(shí)軌跡或在真實(shí)軌據(jù)中加入假軌跡，以達(dá)到不能唯一標(biāo)識(shí)出真實(shí)軌跡的目的；(2)抑制法，是指有限制地發(fā)布原始軌跡數(shù)據(jù)，即直接發(fā)布一般數(shù)據(jù)，而對(duì)敏感數(shù)據(jù)要限制其發(fā)布或經(jīng)過(guò)擾亂后再發(fā)布；(3)泛化法，是指對(duì)軌跡數(shù)據(jù)進(jìn)行抽象化處理，將線擴(kuò)展為體，從而達(dá)到降低攻擊者標(biāo)識(shí)出用戶概率的目的。其中，軌跡k-匿名是實(shí)現(xiàn)軌跡隱私保護(hù)的重要方法[7-9]，該方法要求匿名軌跡數(shù)據(jù)庫(kù)中只能以不大于1/k的概率重新確定一條軌跡，即要求任一軌跡在匿名數(shù)據(jù)庫(kù)中存在至少k-1條與其相同的副本軌跡，從而使攻擊者無(wú)法確定該軌跡屬于哪個(gè)個(gè)體，進(jìn)而達(dá)到保護(hù)用戶隱私信息的目的[10]。

但是，由于軌跡數(shù)據(jù)收集時(shí)GPS的不確定性及網(wǎng)絡(luò)的延時(shí)性等問(wèn)題[11-12]，使得獲取的軌跡位置存在一定范圍的誤差。因此，ABUL O等人基于軌跡k-匿名提出了(k, δ)-匿名模型[13]，以及實(shí)現(xiàn)該方法的NWA (Never Walk Along)算法，該方法要求對(duì)于任意一條軌跡，能夠找出離該軌跡最近的n(k-2

(k δ)-匿名模型在實(shí)現(xiàn)k-匿名分組時(shí)，沒(méi)有考慮位置點(diǎn)的語(yǔ)義敏感性[14]。如表1所示，坐標(biāo)不同所對(duì)應(yīng)的實(shí)際位置不同，而不同位置的語(yǔ)義敏感性也不同。如果不考慮位置點(diǎn)的敏感性就有可能會(huì)造成發(fā)布的軌跡數(shù)據(jù)在某一時(shí)刻經(jīng)過(guò)高敏感區(qū)域。如表2所示，發(fā)布的匿名數(shù)據(jù)集滿足(4, 3)-匿名模型，但是軌跡1、4在時(shí)刻7經(jīng)過(guò)賭場(chǎng)，軌跡2、3在時(shí)刻7經(jīng)過(guò)酒吧，即這4條軌跡在時(shí)刻7都經(jīng)過(guò)高敏感區(qū)域。如果攻擊者根據(jù)背景知識(shí)得到Tom的運(yùn)動(dòng)軌跡處于該等價(jià)類，雖然他不能確定哪條軌跡是Tom的運(yùn)動(dòng)軌跡，但是可以得出Tom去了不良場(chǎng)所。因此，仍有隱私泄露的危險(xiǎn)。

表1 敏感位置信息表

為此，本文提出了(k,δ,ai)-匿名模型，該模型首先要求滿足(k, δ)-匿名模型，其次還應(yīng)滿足任一聚類中同一時(shí)刻處于同一敏感級(jí)別的位置點(diǎn)不超過(guò)k/l(本文取l=2)，由于軌跡數(shù)據(jù)獲取的不確定性，假設(shè)當(dāng)兩點(diǎn)距離小于β(本文取β=50)時(shí)為同一點(diǎn)。

1 相關(guān)定義

定義1 (軌跡)軌跡表示移動(dòng)物體(個(gè)人、公共汽車、出租車等)訪問(wèn)這些位置的位置和順序。 也就是說(shuō)，軌跡Tr由一組有序位置集組成，記為Tr=(l1，l2，…，ln)，li∈L，1≤i≤n。其中l(wèi)k=(xk，yk，tk)表示軌跡Tr在時(shí)刻tk的位置為(xk,yk),t1

定義2 (k-匿名軌跡)在發(fā)布的軌跡數(shù)據(jù)集中，對(duì)任意一條軌跡滿足至少存在其他k-1條軌跡與其不能區(qū)分彼此。

定義3 (軌跡的不確定性模型)給定在時(shí)間t1和tn之間的軌跡Tr和不確定閾值δ，對(duì)于Tr上的每一個(gè)點(diǎn)(x，y，t)，其不確定區(qū)域是以(x,y,t)為圓心，以δ為半徑的水平圓盤，其中(x,y)為Tr在時(shí)間t∈[t1,tn]的期望位置。將軌跡Tr關(guān)于δ的不確定性模型Trp=Vol(Tr,δ)，表示在時(shí)間t∈[t1,tn]內(nèi)所有圓盤的集合。

定義4 (軌跡之間的距離)軌跡Tr1和Tr2在t時(shí)刻的距離為：

Dist(Tr1[t],Tr2[t])=

(1)

則在時(shí)間范圍[t1,tn]內(nèi)，軌跡Tr1和Tr2的距離為：

(2)

定義5 (軌跡相似性)在時(shí)間范圍[t1，tn]內(nèi)，稱軌跡Tr1和Tr2為相似軌跡當(dāng)且僅當(dāng)對(duì)于?t∈[t1,tm]，都有Dist((x1,y1),(x2,y2))≤δ。其中Dist表示軌跡Tr1、Tr2距離，(x1,y1)、(x2,y2)分別表示t時(shí)刻Tr1和Tr2上的位置。

軌跡δ同位：設(shè)Tr1、Tr2為定義在時(shí)間區(qū)間[t1,tn]內(nèi)的兩條軌跡，當(dāng)且僅當(dāng)Tr1上的每個(gè)點(diǎn)(x1i,y1i,ti)(1≤i≤n)和Tr2上的每個(gè)點(diǎn)(x2i,y2i,ti)(1≤i≤n)均滿足Dist((x1i,y1i),(x2i,y2i))≤δ，則稱Tr1、Tr2關(guān)于δ同位，記為Colocδ(Tr1,Tr2)。

定義6 ((k,δ)-匿名模型)給定不確定性閾值δ和匿名閾值k，軌跡集合D滿足(k,δ)-匿名當(dāng)且僅當(dāng)|D|≥k，且D中任意兩條軌跡Tr1、Tr2均滿足Colocδ(Tr1,Tr2)。

2 (k, δ, ai)-匿名模型及算法

2.1 (k, δ, ai)-匿名模型

本文提出基于敏感性分級(jí)的(k, δ, ai)-匿名模型。對(duì)個(gè)人隱私而言，不同的位置往往具有不同的敏感性。例如：賭場(chǎng)這類位置的敏感性遠(yuǎn)高于商場(chǎng)這類一般的位置。因此，要實(shí)現(xiàn)更好地隱私保護(hù)，就需要對(duì)敏感位置進(jìn)行敏感性分級(jí)。根據(jù)其語(yǔ)義敏感性由高到低分為分為L(zhǎng)1，L2，…，L5，敏感位置等級(jí)分類如表3所示。在實(shí)現(xiàn)(k, δ, ai)-匿名分組時(shí)，首先應(yīng)該避免具有相同級(jí)別敏感值的記錄分在同一組。

2.2 (k, δ, ai)-匿名算法

(1)軌跡同步化處理(預(yù)處理)

將原始軌跡數(shù)據(jù)庫(kù)D劃分為若干軌跡數(shù)據(jù)集合，使得任意集合中的軌跡具有相同的起點(diǎn)、終點(diǎn)及相同的時(shí)間間隔，同步化處理后的軌跡數(shù)據(jù)庫(kù)記為Dt。

算法1：Pre?proc(D，π)輸入：原始數(shù)據(jù)庫(kù)D，整形參數(shù)π輸出：同步軌跡數(shù)據(jù)庫(kù)DtStep1．for?Tr∈D{Step2． Let[tb，te]bethetimespanofπ；Step3． i=min{t|t≥tb∧tmodπ=0}；Step4． j=max{t|t≤te∧tmodπ=0}；Step5． ifi￡j{Step6． Tr′=Tr[i，j]；Step7． insertTr′inD[i，j]；Step8． }Step9．}Step10．Dt=∪{D[i，j]|imodπ=0∧jmodπ=0}；Step11．returnDt；

(2)同步軌跡聚類處理

將Dt中的軌跡劃分為若干等價(jià)類，使得每個(gè)等價(jià)類中至少包含k條軌跡，并且類半徑小于max_radius。同步軌跡聚類后的軌跡數(shù)據(jù)庫(kù)記為Dc。

算法2：SL?NWAclust輸入：同步軌跡數(shù)據(jù)Dt，匿名閾值k，參數(shù)Trashmax輸出：各聚類組CStep1．Initialize(max＿radius)；Step2．While(|Trash|>Trashmax){Step3． Active=Dt；Cluster=?； Pivots=?；Trash=?；Step4． Trp=averagetrajectoryofDt；Step5． While(Active≠?){Step6． Trp=argmaxTr∈ActiveDist(Trp，Tr)；Step7． CTrp={Trp}∪{2k-1nearestneighborsofTrpinDCluster}；Step8． While(k≠0){Step9． if|sensitivedata|(?Trp}；Step18． }Step19． elseActive=ActiveCTrp；Step20．}Step21．for?Tr∈DCluster{

Step22． CTrp=Step23． argminTr′∈PiontsDist(Tr′，Tr)Step24． if(Dist(Tr′，Tr)≤max＿radius)Step25． CTrp=CTrp∪{Tr}；Step26． elseTrash=Trash∪{Tr}；Step27．}Step28． increase(max＿radius)；Step29．}Step30．return{CTrp|Trp∈Pivots}；

(3)軌跡空間平移處理

將不在以類中心為圓心，δ為半徑的圓柱內(nèi)的軌跡平移到圓柱的邊緣，空間平移處理后的軌跡數(shù)據(jù)庫(kù)記為D′。

3 匿名軌跡的質(zhì)量評(píng)估

數(shù)據(jù)匿名化處理會(huì)造成原始數(shù)據(jù)的信息損失，使得數(shù)據(jù)的可用性降低，因此，匿名化算法的研究目標(biāo)是在保證數(shù)據(jù)安全的前提下，盡可能地減少數(shù)據(jù)的信息損失。目前，可以從兩個(gè)方面——安全性和可用性對(duì)數(shù)據(jù)質(zhì)量進(jìn)行評(píng)估。其中，匿名數(shù)據(jù)對(duì)信息的保護(hù)能力可用安全性進(jìn)行評(píng)估；匿名軌跡所包含原始軌跡的信息程度可以用可用性進(jìn)行評(píng)估。

3.1 安全性評(píng)估

由于同一敏感級(jí)別位置之間的關(guān)聯(lián)性比較大，如果將隱私級(jí)別相同的軌跡聚類在同一等價(jià)類中，將導(dǎo)致敏感信息的披露，從而導(dǎo)致匿名數(shù)據(jù)安全性降低。因此，軌跡匿名化算法需要盡可能地將不同級(jí)別的位置點(diǎn)聚類在同一等價(jià)類中。

設(shè)等價(jià)類中含有n條軌跡，則同一等價(jià)類中時(shí)刻t的敏感性差異可以表示為：

(3)

其中，Wai表示第i條軌跡和第j條軌跡之間級(jí)別距離的權(quán)重，ai=max(Li,Lj)，設(shè)Wai={0.85, 0.9, 0.95, 1}，即級(jí)別5到級(jí)別1,2,3,4的權(quán)重都為1；級(jí)別4到級(jí)別1, 2,3的權(quán)重都為0.95；級(jí)別3到級(jí)別1, 2的權(quán)重都為0.9，級(jí)別2到級(jí)別1的權(quán)重為0.85；Cij=|Li-Lj|。

那么，同一等價(jià)類中的敏感性差異可以表示為：

(4)

其中，|CTrp|=n表示等價(jià)類中的軌跡數(shù)，則匿名數(shù)據(jù)庫(kù)D′的敏感性差異為：

(5)

其中，|D′|表示匿名數(shù)據(jù)庫(kù)中等價(jià)類個(gè)數(shù)，并且敏感性差異(Ds)的值越大，安全性越好。

3.2 可用性評(píng)估

本文主要用信息失真來(lái)評(píng)估匿名數(shù)據(jù)的可用性。

定義7 (信息損失量)原始軌跡Tr在時(shí)刻t的三元組為(x,y,t)，匿名化處理后形成的匿名軌跡Tr′在相應(yīng)的時(shí)間t的三元組為(x′,y′,t)，則此匿名產(chǎn)生的時(shí)空信息損失量可以表示為：

IDt(Tr[t],Tr′[t])=

其中，(x,y)、(x′,y′)分別為軌跡Tr和Tr′在t時(shí)刻的位置；Ω是一個(gè)常數(shù)，是對(duì)刪除位置的信息損失的懲罰。那么，整條匿名軌跡Tr′關(guān)于其原始軌跡Tr的信息損失量為：

ID(Tr,Tr′)=

其中，T是軌跡Tr中包含的所有時(shí)間點(diǎn)集。n=|T|表示軌跡Tr的位置數(shù)。

那么，匿名軌跡數(shù)據(jù)庫(kù)D′相對(duì)于原始數(shù)據(jù)庫(kù)D的總信息損失量為：

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

實(shí)驗(yàn)采用的數(shù)據(jù)集由Brinkhoff移動(dòng)對(duì)象數(shù)據(jù)生成器[15]基于德國(guó)奧爾登堡(Oldenburg)市地圖產(chǎn)生。該數(shù)據(jù)集表示奧爾登堡一天的移動(dòng)數(shù)據(jù)，Brinkhoff移動(dòng)對(duì)象數(shù)據(jù)生成器可以在http：//www.fh-oow.de/institute/iapg/personen/brinkhoff/generator/中下載。表4為數(shù)據(jù)集的統(tǒng)計(jì)信息。其中，|D|表示軌跡條數(shù)，|Points|表示采樣點(diǎn)個(gè)數(shù)，|Dt|表示預(yù)處理后等價(jià)類個(gè)數(shù)，MBB(Minimum Bounding Box)radius表示數(shù)據(jù)庫(kù)D中最小覆蓋矩形對(duì)角線的一半，F(xiàn)ile_size表示數(shù)據(jù)文件大小。

表4 實(shí)驗(yàn)數(shù)據(jù)集信息

實(shí)驗(yàn)環(huán)境為：Intel(R) Core(TM) i5-5200U CPU @ 2.20 GHz；4 GB內(nèi)存；Windows 8操作系統(tǒng)；算法由C編寫，所涉及的代碼在VMware Workstation10.0下的Ubuntu中實(shí)現(xiàn)。

4.2 隱私保護(hù)有效性分析

敏感性差異值是基于3.1節(jié)敏感性差異公式計(jì)算得到的，NWA算法將離聚類中心最近的k-1條軌跡加入到同一等價(jià)類中，而本文提出的SL-NWA算法需要考慮敏感位置的級(jí)別，使得同一時(shí)刻處于同一敏感級(jí)別的位置點(diǎn)的概率不大于1/l，從而提高隱私保護(hù)的有效性。圖1分別是δ=600和δ=2 000時(shí)兩種算法的敏感性差異值，實(shí)驗(yàn)結(jié)果表明SL-NWA算法比NWA算法的敏感性差異更大，即SL-NWA算法更安全。

圖1 敏感性差異

4.3 信息損失量分析

基于3.2節(jié)信息失真標(biāo)準(zhǔn)，本文將(k, δ, ai)-匿名模型提出的SL-NWA算法與(k, δ)-匿名模型提出的NWA算法進(jìn)行對(duì)比，圖2是δ=600、δ=1 000，δ=2 000和δ=3 000時(shí)，兩種算法的總信息損失量。實(shí)驗(yàn)結(jié)果表明兩種算法的總信息損失量均隨k值的增大而增大，隨δ值的增大而減小。并且隨著δ的增大，SL-NWA算法的信息損失與NWA算法的信息損失越來(lái)越接近。

5 結(jié)論

本文提出基于敏感性分級(jí)的(k, δ, ai)-匿名模型，通過(guò)劃分敏感性等級(jí)來(lái)描述它們的敏感性差異，該模型需要滿足所發(fā)布的軌跡數(shù)據(jù)庫(kù)中任意軌跡在其半徑為δ的圓柱內(nèi)被重新標(biāo)識(shí)出的概率不大于1/k，并且同一時(shí)刻處于同一敏感級(jí)別的位置點(diǎn)不超過(guò)k/l。但是該算法并不能總是把敏感屬性值級(jí)別差異較大的軌跡聚類在同一等價(jià)類中。下一步要盡可能把敏感屬性值級(jí)別差異較大的軌跡聚類在同一等價(jià)類中，進(jìn)一步提高匿名數(shù)據(jù)的安全性。

圖2 總信息損失量

[1] 鄭永星.軌跡發(fā)布中的隱私保護(hù)研究[D].福州:福建師范大學(xué),2016.

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

[3] 鄭路倩,韓建民,魯劍鋒,等.抵制時(shí)空位置點(diǎn)鏈接攻擊的(k,δ,l)-匿名模型[J].計(jì)算機(jī)科學(xué)與探索,2015,9(9):1108-1121.

[4] TERROVITIS M, POULIS G, MAMOULIS N, et al. Local suppression and splitting techniques for privacy preserving publication of trajectories[J]. IEEE Transactions on Knowledge & Data Engineering, 2017, 29(7):1466-1479.

[5] 翁國(guó)慶.隱私敏感軌跡數(shù)據(jù)發(fā)布技術(shù)研究[D].南京:東南大學(xué),2014.

[6] 賈明正.面向數(shù)據(jù)發(fā)布的軌跡隱私保護(hù)技術(shù)研究[D].成都:西南交通大學(xué),2016.

[7] 許志凱,張宏莉,余翔湛.軌跡隱私保護(hù)研究綜述[J].智能計(jì)算機(jī)與應(yīng)用,2017,7(1): 125-127.

[8] 胡兆瑋,楊靜.軌跡隱私保護(hù)技術(shù)研究進(jìn)展分析[J].計(jì)算機(jī)科學(xué),2016,43(4):16-23.

[9] TERROVITIS M, POULIS G, MAMOULIS N, et al. Local suppression and splitting techniques for privacy preserving publication of trajectories[J]. IEEE Transactions on Knowledge & Data Engineering, 2017, 29(7):1466-1479.

[10] Li Meng, Zhu Liehuang, Zhang Zijian, et al. Differentially private publication scheme for trajectory data[C].IEEE International Conference on Data Science in Cyberspace. IEEE, 2017:596-601.

[11] 王爽,周福才,吳麗娜,等.移動(dòng)對(duì)象不確定軌跡隱私保護(hù)算法研究[J].通信學(xué)報(bào),2015, 36(s1):94-102.

[12] 朱麟,黃勝波.不確定環(huán)境下軌跡k-匿名隱私保護(hù)[J].計(jì)算機(jī)應(yīng)用,2015, 35(12):3437-3441.

[13] ABUL O, BONCHI F, NANNI M. Never walk alone: uncertainty for anonymity in moving objects databases[C].IEEE International Conference on Data Engineering. IEEE Computer Society, 2008:376-385.

[14] 金華,張志祥,劉善成,等.基于敏感性分級(jí)的(ai,k) -匿名隱私保護(hù)[J].計(jì)算機(jī)工程, 2011,37(14):12-17.

[15] BRINKHOFF T.Generating traffic data[J].Bulletin of the Technical Committee on Data Engineering IEEE Computer Society,2003,26:2003.