白雨靚，李曉會，陳潮陽，王亞君

(遼寧工業(yè)大學 電子與信息工程學院，遼寧 錦州 121001)

1 概 述

定位技術的逐步發(fā)展和智能設備的全球普及使大量移動對象的軌跡信息被持有和分享，形成了龐大的軌跡數(shù)據(jù)集，這其中所包含的信息，推動了軌跡數(shù)據(jù)分析和挖掘技術的進步，使其成為大數(shù)據(jù)安全領域的一個熱點課題[1-4].研究人員通過對軌跡數(shù)據(jù)的分析和探索，從中獲取大量有價值的信息用于移動對象的隱私保護研究.在數(shù)據(jù)發(fā)布過程中，不恰當?shù)臄?shù)據(jù)處理很可能會造成用戶的隱私泄露，攻擊者可以根據(jù)已掌握的背景知識對移動對象的個人信息進行推斷，從而獲得被攻擊者的經(jīng)濟狀況、家庭住址等隱私信息[5-7].但如果對軌跡數(shù)據(jù)集處理過甚，也會導致對象信息的大量損失，降低發(fā)布數(shù)據(jù)的可用性和完整性，造成信息資源的浪費[8，9].所以降低移動對象隱私泄露風險的同時提高待處理軌跡數(shù)據(jù)的可用性是一個值得深入研究的課題.

現(xiàn)階段，國內(nèi)外在軌跡數(shù)據(jù)隱私保護領域已取得了一些研究成果.例如，Mohammed[10]等利用一種匿名算法來實現(xiàn)了LKC隱私模型使其適用于RFID數(shù)據(jù)，首先識別出軌跡數(shù)據(jù)集中的最小違反序列集，然后通過貪心法對違反序列進行全局抑制，達到盡可能減少最大頻繁序列損失的目的，但全局抑制的方法需要將大量數(shù)據(jù)刪除，沒有有效提高數(shù)據(jù)可用性.Chen[11]等人通過(K，C)L隱私模型及算法提出了局部抑制的概念.該算法首先確定軌跡數(shù)據(jù)集中不滿足(K，C)L隱私模型要求的所有序列；然后在保證數(shù)據(jù)高效可用性的前提下，通過局部抑制將軌跡數(shù)據(jù)集簡化.Ghasemzadeh[12]等人通過對LKC-隱私模型中C=1的情況進行研究，通過全局抑制來實現(xiàn)對軌跡數(shù)據(jù)的隱私保護；Komishani[13]等人提出一種泛化敏感信息的隱私保護算法，該算法通過對敏感信息屬性建立分類樹來實現(xiàn)對高維軌跡數(shù)據(jù)集的抑制，但由于不確定攻擊者所掌握背景知識的長度，所以需要抑制大量數(shù)據(jù)，降低了數(shù)據(jù)挖掘價值.由此，為了提高軌跡數(shù)據(jù)發(fā)布過程中用戶信息的安全性，降低由于全局抑制帶來的數(shù)據(jù)損失率，本文提出了一種面向軌跡數(shù)據(jù)發(fā)布的優(yōu)化抑制差分隱私保護算法.通過對大量軌跡數(shù)據(jù)集的分析結(jié)果表明，相比于其他算法，該算法在保證用戶隱私信息不被泄露的同時有效降低了數(shù)據(jù)損失率，提高了數(shù)據(jù)可用性.

2 相關定義

本節(jié)主要闡述一些基本定義及相關概念，包括軌跡、違反序列、頻繁序列、分類樹等.

2.1 軌跡

定義 1.(軌跡)[14]軌跡是空間中移動對象所產(chǎn)生的時間和位置的有序組合，可表示為tr=(oi；((x1，y1，t1)，(x2，y2，t2)，…，(xn，yn，tn))).其中：oi為用戶標識符；((x1，y1，t1)，(x2，y2，t2)，…，(xn，yn，tn))為軌跡序列，t1

定義 2.(軌跡數(shù)據(jù)集)軌跡數(shù)據(jù)集T是一系列軌跡數(shù)據(jù)的集合，表示為：T=(tr1，tr2，…，trn)，其中n表示T中包含的軌跡條數(shù)，也可用|T|表示，即|T|=n.

若軌跡數(shù)據(jù)集中的某個敏感屬性和某些位置點共同頻繁出現(xiàn)在同一序列中，攻擊者不用確認移動對象的具體軌跡，也可以通過對其他擁有部分相同序列對象的分析，推斷出被攻擊者的敏感屬性，例如表1是一個包含移動對象敏感屬性的簡單軌跡數(shù)據(jù)集T.

表1 軌跡數(shù)據(jù)集T

從表1可知，軌跡數(shù)據(jù)集T中，包含e2、e3兩個位置點的序列有tr3、tr5、tr7這3條，其中tr3、tr5兩條軌跡所對應的敏感屬性均為SARS.因此，假設被攻擊對象為A，當攻擊者掌握A曾經(jīng)到過e2、e3兩個位置點這一背景知識時，其可推斷出用戶A患有SARS的概率為2/3=66.7%.

定義 3.(LKC-privacy)[15]L是攻擊者掌握的最大軌跡長度值，T是所有用戶的軌跡數(shù)據(jù)集，S是數(shù)據(jù)集T中的敏感屬性值，若T滿足LKC-隱私當且僅當T中任意子序列P在|P|

1)|T(p)|≥K，T(p)是軌跡中包含p的用戶.

2)Conf(s|T(P)≤C，Conf(s|T(p))=|T(P∪s)|/|T(P)|，其中0≤C≤1，s∈S，C是匿名集的置信度閾值，可以根據(jù)需求靈活地調(diào)整匿名的程度.

2.2 序列

定義 4.(違反序列)假定軌跡序列集上的序列p長度|p|滿足0<|p|≤L，若序列p不滿足LKC-privacy定義中的任一條件，則稱p為違反序列.

定義 5.(最小違反序列)給定違反序列p，若序列p為最小違反序列(記為MVS(Minimal Violating Sequence))，當且僅當序列p的任一子序列均不為違反序列.

定義 6.(頻繁序列)給定閾值E>0和軌跡數(shù)據(jù)集T中的任一子序列p，若|T(p)|≥E，則稱p為頻繁序列，其中|T(p)|為序列p在T中出現(xiàn)的次數(shù).

定義 7.(最大頻繁序列)給定頻繁序列p，當且僅當p的父序列都不是頻繁序列，則稱序列p為最大頻繁序列，記為MFS(Maximal Frequent Sequence).

2.3 分類樹

定義 8.(分類樹)[16]根據(jù)軌跡數(shù)據(jù)集T建立分類樹，將數(shù)據(jù)集中敏感信息逐一添加到分類樹的葉子節(jié)點中，葉子節(jié)點自底向上泛化成為分類樹的節(jié)點，所有葉子節(jié)點的集合即為分類樹的根節(jié)點，對于所有分支，劃分后選擇相同分支的所有實例都屬于同一類.圖1為根據(jù)表1數(shù)據(jù)建立的簡單分類樹.

圖1 表1中敏感屬性的簡單數(shù)據(jù)分類樹

2.4 差分隱私

差分隱私保護技術通過向數(shù)據(jù)中添加噪聲技術來實現(xiàn)數(shù)據(jù)失真，降低數(shù)據(jù)敏感度的同時保持數(shù)據(jù)屬性不變，在數(shù)據(jù)集中更改任一條數(shù)據(jù)信息，算法輸出結(jié)果保持不變，所以即使攻擊者掌握了除一條記錄外的所有敏感數(shù)據(jù)，這一條記錄中的敏感信息仍然不會被泄露.

定義 9.(差分隱私)[17]給定一個隨機算法Q，Rang(Q)代表其值域，若算法Q對于任意兩個鄰近數(shù)據(jù)集T1和T2的輸出結(jié)果O(O∈Rang(Q))均滿足不等式(1)，則Q滿足ε-差分隱私.

Pr[Q(T1)=O]≤exp(ε)·Pr[Q(T2)=O]

(1)

其中，ε表示隱私預算，Pr[Q(Ti)=O]表示算法的概率，其由算法Q決定.(本文采用的差分隱私保護噪音機制為拉普拉斯噪音機制)

定義 10.(全局敏感度)輸入一個軌跡數(shù)據(jù)集T，對于任一函數(shù)f：T→Rd其全局敏感度可表示為：

(2)

其中，R代表映射的實數(shù)閾，d代表f：T→Rd的查詢維度，‖f(T1)-f(T2)‖1表示f(T1)和f(T2)之間的1-階范數(shù)距離.

定理 1.(拉普拉斯機制)對于任一函數(shù)f：T→Rd，給定隨機算法A，則使A滿足ε-差分隱私，當且僅當算法A滿足等式(3).

A(T)=f(T)+〈Lap1(Δf/ε)，Lap2(Δf/ε)，…，Lapi(Δf/ε)〉

(3)

其中，Lapi(Δf/ε)(1≤i≤d)是相互獨立的拉普拉斯變量，噪音通常由拉普拉斯分布產(chǎn)生，噪音量大小與Δf成正比，與ε成反比.

3 算法的基本思想

3.1 設計思路

本文提出一種面向軌跡數(shù)據(jù)發(fā)布的優(yōu)化抑制差分隱私保護算法，主要包括兩個部分：

1)將需要進行全局抑制的序列進行局部抑制的操作，根據(jù)位置點的抑制優(yōu)先級得分決定抑制順序，計算其可能產(chǎn)生的最小違反序列，并將其從軌跡數(shù)據(jù)集中舍棄；

2)建立分類樹，引進差分隱私保護方法實現(xiàn)對軌跡數(shù)據(jù)保護操作.

3.2 算法描述

面向軌跡數(shù)據(jù)發(fā)布的優(yōu)化抑制差分隱私保護算法框架圖如圖2所示.

圖2 算法框架圖

第1部分(TOS)：計算新產(chǎn)生的最小違反序列(NewMVS)，具體過程如下：首先找出軌跡數(shù)據(jù)集中的MVS集合，根據(jù)給定的頻繁閾值E，找出最大頻繁序列集，然后構(gòu)建MFS樹，根據(jù)點p的抑制優(yōu)先級[18]得分Score(p)來決定抑制的順序：

(4)

其中Eliminate(p)代表抑制點p可以消除的MVS數(shù)目，Loss(p)代表抑制點p帶來的有用性損失.算法偽代碼如下：

輸入：原始軌跡數(shù)據(jù)集T、敵手掌握的軌跡長度上限L、匿名數(shù)K、置信度閾值C、敏感值合集S、最小違反序列合集MVS

輸出：更新最小違反序列集(NewMVS)

1.X<-Find all MFSs from T；

2.Y<-Based an MFS tree based on the data in X；

3.For each m in MVS；

4.P<-Suppress the point p in m；

5.V<-Single violation sequence point and the violation sequence point of P；

6.Remove the points belong to V from P except p；

7.Generate a new sequence by P；

8.Loop the above operation from 3 to 7；

9.Build the score sheet by Score(p)=Eliminate(p)/Loss(p)；

10.Choose the highest point；

11.If Partial inhibition；

12.Delete the highest p；

13.Update MFS；

14.Else

15.Restrain all instance；

16.Delete the MFS including p；

17.Update score sheet；

18.Return NewMVS；

第2部分(TDP)：利用軌跡數(shù)據(jù)集經(jīng)LKC隱私模型處理過的數(shù)據(jù)迭代構(gòu)建分類樹，并利用Laplace噪聲機制對敏感信息進行保護[17].首先初始化數(shù)據(jù)集T，在軌跡數(shù)據(jù)集選出兩組頻繁序列構(gòu)造一棵分類樹.其思想為：挑選出每條軌跡記錄中任意兩個位置點出現(xiàn)次數(shù)最多所對應的軌跡序列作為第一組，然后在包含這個位置點的所有序列中挑出次數(shù)最小的序列，將這個序列所在的軌跡中最頻繁的位置點當做第二組，以此類推，將所有軌跡都迭代挑選進分類樹中，就構(gòu)造好了一棵分類樹T-tree(0).鑒于軌跡數(shù)據(jù)集的不斷更新，所以要不斷向分類樹中添加新的記錄，我們需要一個給定的隱私預算ε，每增加新數(shù)據(jù)集ΔTi時，ΔTi中所有記錄都會被添加到T-tree(i-1)的根節(jié)點繼而遞歸到不相交的子集中，若某些記錄被添加到T-tree(i-1)的葉子節(jié)點，則需要重新分配該節(jié)點的隱私預算后才能繼續(xù)分割該節(jié)點；若某些記錄被添加到T-tree(i-1)的非葉子節(jié)點中，就根據(jù)T-tree(i-1)的分類方法處理這些記錄；如果某些記錄為空，則對下一條記錄做上述步驟，直到所有節(jié)點都分配完成，形成新的分類樹T-tree(i)，并向分類樹的葉子節(jié)點中添加拉普拉斯噪聲.算法偽代碼如下：

輸入：軌跡數(shù)據(jù)集T，增新數(shù)據(jù)集ΔTi，隱私預算ε

輸出：噪聲數(shù)據(jù)集H

19.Initializes the trajectory data set T；

20.Construct matrices A based on data sets；

21.Find the sequence with the most number of occurrences of any two items in A，regard asMmax[i，j]；

22.B1=Mmax[i，j]；

23.Mmin[a，b]←the smallest set of sequences in the rows of i and j；

24.Mmax[c，d]←the largest set of sequences in the rows of a and b；

25.B2=Mmax[c，d]；

26.Repeat the above steps forB1andB2；

27.For each Δ Ti；

28.Z←all trajectory from Δ Ti；

29.Ifz→cut=the root node ofT-tree(0)；

31.Put Z to the root node ofT-tree(i-1)；

32.For eachzi∈ Z；

33.Ifziis leaf node；

34.Separate the node，changeε；

37.Ifziis not a leaf node；

38.Assignziaccording to the classification ofT-tree(i-1)；

39.Else Ifzi=null；

40.Repeat steps 33-36；

41.ReturnT-tree(i)；

42.Add Laplace to A；

43.Return H；

3.3 算法分析

3.3.1 算法的第1部分(TOS)

給定原始軌跡數(shù)據(jù)集T，首先識別其中的最小違反序列集MVS，然后根據(jù)最大頻繁序列集，構(gòu)建MFS樹，再由點p的抑制優(yōu)先級得分Score(p)來決定抑制的順序，更新最小違反序列集，時間復雜度為O(|x|L|T|)，|x|為軌跡數(shù)據(jù)的維數(shù)，|T|為軌跡數(shù)據(jù)集中的軌跡條數(shù)；本算法通過更新最小違反序列對局部抑制進行優(yōu)化，有效解決了全局抑制導致數(shù)據(jù)可用性降低的問題，同時通過局部抑制提高了軌跡數(shù)據(jù)安全性.

3.3.2 算法的第2部分(TDP)

4 實驗分析

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

本實驗在Python環(huán)境下運行，由Myeclipse集成開發(fā)軟件進行算法實現(xiàn)，實驗硬件環(huán)境：處理器為Intel(R)Core(TM)i7-5500U CPU 2.40GH、RAM為8.0G、Lnuix操作系統(tǒng)，本文采用包含18670條真實用戶軌跡的開源數(shù)據(jù)集進行實驗驗證[19]，該數(shù)據(jù)集由微軟亞洲研究院的Geolife項目提供，在軌跡數(shù)據(jù)隱私保護相關研究中廣泛應用.

4.2 衡量標準

4.2.1 算法的第1部分(TOS)

本文中數(shù)據(jù)損失是衡量軌跡數(shù)據(jù)可用性的重要參考，本文從頻繁序列(MFS)和軌跡序列兩方面進行衡量[20]：

1)MFS數(shù)據(jù)損失MFSLoss，取決于原始軌跡數(shù)據(jù)集中的MFS數(shù)和經(jīng)過局部抑制處理后數(shù)據(jù)集中剩余的MFS數(shù)：

(5)

其中M(T)為原始軌跡數(shù)據(jù)集中的MFS數(shù)，M(T°)為經(jīng)過局部抑制處理后的數(shù)據(jù)集中的MFS數(shù).

2)軌跡序列損失TLoss，取決于原始軌跡數(shù)據(jù)集中的序列數(shù)以及經(jīng)過數(shù)據(jù)處理后的序列數(shù)：

(6)

其中L(T)為原始軌跡數(shù)據(jù)集中的軌跡條數(shù)，L(T°)為經(jīng)過局部抑制處理后的數(shù)據(jù)集中的軌跡條數(shù).

4.2.2 算法的第2部分(TDP)

本算法利用計數(shù)查詢[17]計算數(shù)據(jù)的平均相對誤差作為衡量數(shù)據(jù)損失的標準，利用計數(shù)查詢R：

(7)

4.3 實驗結(jié)果

4.3.1 算法的第1部分(TOS)結(jié)果

為了驗證本文算法的有效性，將本文中的TOS算法與文獻[21]以及文獻[22]中的LSUP、MPSTD算法進行實驗結(jié)果比對.算法中的匿名個數(shù)K、置信度閾值C均會對實驗結(jié)果產(chǎn)生不同程度的影響，所以本實驗在不同的K值(3種算法C值、L值相同)、C值(3種算法K值、L值相同)下對3種算法實驗結(jié)果進行了比較：

1)不同K值對數(shù)據(jù)損失的影響

由圖3、圖4中的實驗結(jié)果可知，當匿名數(shù)K值遞增，MFS損失率和序列損失率也在隨之增加，其原理在于最小違反序列集(MVS)的數(shù)目與K值成正比例關系，K值的增加導致需要被抑制的序列數(shù)增加，加大了數(shù)據(jù)損失率.相比于其他兩種算法，本文中的TOS算法在數(shù)據(jù)處理過程中根據(jù)抑制優(yōu)先得分優(yōu)化了更新最小違反序列集的過程，合理的利用了局部抑制的優(yōu)勢，具有更低的MFS損失率和序列損失率.

圖3 不同K值對MFS損失率的影響

圖4 不同K值對序列損失率的影響

2)C值不同對數(shù)據(jù)損失的影響

由圖5、圖6的實驗結(jié)果可知，當置信度閾值C的值遞增，MFS損失率和序列損失率逐漸減小.C值的增加會減少需要抑制的最小違反序列(MVS)數(shù)，從而導致MFS損失率和序列損失率都在逐步下降.綜合圖3-圖6數(shù)據(jù)結(jié)果，在數(shù)據(jù)處理過程中，不論是C值還是K值的遞增，本文提出的TOS 算法的數(shù)據(jù)處理結(jié)果均在一定程度上優(yōu)于其他兩種算法，因為TOS算法是根據(jù)抑制點得分優(yōu)先級來決定抑制順序，可以更合理的更新最小違反序列集，有效降低由于抑制數(shù)據(jù)導致的數(shù)據(jù)損失.

圖5 不同C值對MFS損失率的影響

圖6 不同C值對序列損失率的影響

4.3.2 算法的第2部分(TDP)結(jié)果

為了驗證本文算法的安全性，將文獻[23]以及文獻[24]中的CTS-DP、DDPA算法與本文TDP算法進行實驗結(jié)果對比.實驗結(jié)果表明隨著軌跡數(shù)據(jù)集長度的增加，數(shù)據(jù)的平均相對誤差也逐漸增加，但在隱私預算值越大的條件下，兩種實驗中數(shù)據(jù)的平均相對誤差均在降低.從實驗結(jié)果可知，相比于其他兩種算法，本文中TDP算法的軌跡數(shù)據(jù)分類樹是在通過局部抑制處理后的數(shù)據(jù)基礎上建立的，避免了由于添加過多拉普拉斯噪聲而導致的數(shù)據(jù)失真，更有效降低了平均相對誤差，提高了軌跡隱私數(shù)據(jù)的可用性與安全性.

圖7 ε=0.5時，數(shù)據(jù)集長度對平均相對誤差的影響

圖8 ε=1時，數(shù)據(jù)集長度對平均相對誤差的影響

5 結(jié)束語

本文提出了一種面向軌跡數(shù)據(jù)發(fā)布的優(yōu)化抑制差分隱私保護算法，在軌跡數(shù)據(jù)的發(fā)布過程中，通過更新最小違反序列對數(shù)據(jù)進行合理局部抑制，代替全局抑制的處理，降低了全局抑制造成的多數(shù)據(jù)損失，提高了軌跡數(shù)據(jù)的可用性，同時根據(jù)處理過后的軌跡數(shù)據(jù)集中的敏感信息建立分類樹，有效減少拉普拉斯噪聲添加，降低數(shù)據(jù)失真，相比于其他算法，本文提出的算法有效降低了MFS損失率和序列損失率，減小了平均相對誤差，降低隱私泄露風險的同時提高了待發(fā)布數(shù)據(jù)的可用性.未來將繼續(xù)對如何進一步提高待發(fā)布數(shù)據(jù)的可用性進行研究.