面向軌跡數(shù)據(jù)發(fā)布的優(yōu)化抑制差分隱私保護(hù)研究

白雨靚，李曉會(huì)，陳潮陽，王亞君

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

1 概 述

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

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

2 相關(guān)定義

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

2.1 軌跡

定義 1.(軌跡)[14]軌跡是空間中移動(dòng)對(duì)象所產(chǎn)生的時(shí)間和位置的有序組合，可表示為tr=(oi；((x1，y1，t1)，(x2，y2，t2)，…，(xn，yn，tn))).其中：oi為用戶標(biāo)識(shí)符；((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ù)集中的某個(gè)敏感屬性和某些位置點(diǎn)共同頻繁出現(xiàn)在同一序列中，攻擊者不用確認(rèn)移動(dòng)對(duì)象的具體軌跡，也可以通過對(duì)其他擁有部分相同序列對(duì)象的分析，推斷出被攻擊者的敏感屬性，例如表1是一個(gè)包含移動(dòng)對(duì)象敏感屬性的簡單軌跡數(shù)據(jù)集T.

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

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

定義 3.(LKC-privacy)[15]L是攻擊者掌握的最大軌跡長度值，T是所有用戶的軌跡數(shù)據(jù)集，S是數(shù)據(jù)集T中的敏感屬性值，若T滿足LKC-隱私當(dāng)且僅當(dāng)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))，當(dāng)且僅當(dāng)序列p的任一子序列均不為違反序列.

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

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

2.3 分類樹

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

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

2.4 差分隱私

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

3 算法的基本思想

3.1 設(shè)計(jì)思路

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

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

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

3.2 算法描述

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

圖2 算法框架圖

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

(4)

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

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

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

3.3.2 算法的第2部分(TDP)

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

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

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

4.2 衡量標(biāo)準(zhǔn)

4.2.1 算法的第1部分(TOS)

本文中數(shù)據(jù)損失是衡量軌跡數(shù)據(jù)可用性的重要參考，本文從頻繁序列(MFS)和軌跡序列兩方面進(jìn)行衡量[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)

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

(7)

4.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

圖3 不同K值對(duì)MFS損失率的影響

圖4 不同K值對(duì)序列損失率的影響

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

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

圖5 不同C值對(duì)MFS損失率的影響

圖6 不同C值對(duì)序列損失率的影響

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

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

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

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

5 結(jié)束語

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