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

劉 陽，祝永志，遲玉良

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

0 引言

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

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

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

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

表1 敏感位置信息表

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

1 相關定義

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

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

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

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

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

(1)

則在時間范圍[t1,tn]內，軌跡Tr1和Tr2的距離為：

(2)

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

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

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

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

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

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

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

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

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

算法1：Pre?proc(D，π)輸入：原始數據庫D，整形參數π輸出：同步軌跡數據庫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中的軌跡劃分為若干等價類，使得每個等價類中至少包含k條軌跡，并且類半徑小于max_radius。同步軌跡聚類后的軌跡數據庫記為Dc。

算法2：SL?NWAclust輸入：同步軌跡數據Dt，匿名閾值k，參數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)軌跡空間平移處理

將不在以類中心為圓心，δ為半徑的圓柱內的軌跡平移到圓柱的邊緣，空間平移處理后的軌跡數據庫記為D′。

3 匿名軌跡的質量評估

數據匿名化處理會造成原始數據的信息損失，使得數據的可用性降低，因此，匿名化算法的研究目標是在保證數據安全的前提下，盡可能地減少數據的信息損失。目前，可以從兩個方面——安全性和可用性對數據質量進行評估。其中，匿名數據對信息的保護能力可用安全性進行評估；匿名軌跡所包含原始軌跡的信息程度可以用可用性進行評估。

3.1 安全性評估

由于同一敏感級別位置之間的關聯性比較大，如果將隱私級別相同的軌跡聚類在同一等價類中，將導致敏感信息的披露，從而導致匿名數據安全性降低。因此，軌跡匿名化算法需要盡可能地將不同級別的位置點聚類在同一等價類中。

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

(3)

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

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

(4)

其中，|CTrp|=n表示等價類中的軌跡數，則匿名數據庫D′的敏感性差異為：

(5)

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

3.2 可用性評估

本文主要用信息失真來評估匿名數據的可用性。

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

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

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

ID(Tr,Tr′)=

其中，T是軌跡Tr中包含的所有時間點集。n=|T|表示軌跡Tr的位置數。

那么，匿名軌跡數據庫D′相對于原始數據庫D的總信息損失量為：

4 實驗與分析

4.1 實驗數據與環境

實驗采用的數據集由Brinkhoff移動對象數據生成器[15]基于德國奧爾登堡(Oldenburg)市地圖產生。該數據集表示奧爾登堡一天的移動數據，Brinkhoff移動對象數據生成器可以在http：//www.fh-oow.de/institute/iapg/personen/brinkhoff/generator/中下載。表4為數據集的統計信息。其中，|D|表示軌跡條數，|Points|表示采樣點個數，|Dt|表示預處理后等價類個數，MBB(Minimum Bounding Box)radius表示數據庫D中最小覆蓋矩形對角線的一半，File_size表示數據文件大小。

表4 實驗數據集信息

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

4.2 隱私保護有效性分析

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

圖1 敏感性差異

4.3 信息損失量分析

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

5 結論

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

圖2 總信息損失量

[1] 鄭永星.軌跡發布中的隱私保護研究[D].福州:福建師范大學,2016.

[2] 霍崢,孟小峰.軌跡隱私保護技術研究[J].計算機學報,2011,34(10):1820-1830.

[3] 鄭路倩,韓建民,魯劍鋒,等.抵制時空位置點鏈接攻擊的(k,δ,l)-匿名模型[J].計算機科學與探索,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] 翁國慶.隱私敏感軌跡數據發布技術研究[D].南京:東南大學,2014.

[6] 賈明正.面向數據發布的軌跡隱私保護技術研究[D].成都:西南交通大學,2016.

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

[8] 胡兆瑋,楊靜.軌跡隱私保護技術研究進展分析[J].計算機科學,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] 王爽,周福才,吳麗娜,等.移動對象不確定軌跡隱私保護算法研究[J].通信學報,2015, 36(s1):94-102.

[12] 朱麟,黃勝波.不確定環境下軌跡k-匿名隱私保護[J].計算機應用,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] 金華,張志祥,劉善成,等.基于敏感性分級的(ai,k) -匿名隱私保護[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.