基于統(tǒng)計(jì)差分的軌跡隱私保護(hù)

朱維軍 游慶光 楊衛(wèi)東 周清雷

1(鄭州大學(xué)信息工程學(xué)院 鄭州 450001) 2(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院 鄭州 450001)

基于統(tǒng)計(jì)差分的軌跡隱私保護(hù)

朱維軍1游慶光1楊衛(wèi)東2周清雷1

1(鄭州大學(xué)信息工程學(xué)院 鄭州 450001)2(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院 鄭州 450001)

(zhuweijun@zzu.edu.cn)

隨著車聯(lián)網(wǎng)不斷地發(fā)展,車聯(lián)網(wǎng)為駕乘者提供便捷服務(wù)的同時(shí)，也帶來(lái)了相應(yīng)的隱私保護(hù)問(wèn)題.軌跡數(shù)據(jù)發(fā)布將可能泄露用戶位置隱私,從而危害用戶人身安全；為改變已有差分隱私保護(hù)方法中添加隨機(jī)噪音的弊端，提出一種基于統(tǒng)計(jì)差分隱私的軌跡隱私保護(hù)方法.車輛行駛軌跡具有Markov過(guò)程的特點(diǎn)，根據(jù)車輛軌跡的特征計(jì)算軌跡中位置節(jié)點(diǎn)敏感度；并根據(jù)位置敏感度，統(tǒng)計(jì)閾值和敏感度閾值添加適量Laplace噪音；使用平均相對(duì)誤差評(píng)價(jià)軌跡數(shù)據(jù)的可用性大小.實(shí)驗(yàn)證實(shí)了基于統(tǒng)計(jì)差分隱私的軌跡隱私保護(hù)方法的可用性和有效性.

軌跡數(shù)據(jù)；差分隱私；Markov過(guò)程；數(shù)據(jù)發(fā)布；隱私保護(hù)

隨著車聯(lián)網(wǎng)的快速發(fā)展，車輛產(chǎn)生大量軌跡數(shù)據(jù).在信息時(shí)代中，交通部門可以對(duì)大量的軌跡數(shù)據(jù)挖掘和分析，從而優(yōu)化交通道路并減少交通事故等.軌跡數(shù)據(jù)中存在大量的敏感信息[1-4](用戶ID、家庭地址、醫(yī)院和學(xué)校等)；若直接發(fā)布原始軌跡數(shù)據(jù)，攻擊者可以對(duì)發(fā)布的軌跡數(shù)據(jù)進(jìn)行挖掘分析，從而獲取用戶的敏感信息；用戶隱私泄露將威脅到用戶的人身安全,因此軌跡隱私保護(hù)至關(guān)重要.

軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)技術(shù)主要有假數(shù)據(jù)法、抑制法和泛化法[5].其中k-匿名[6]和l-diversity[7]是基于泛化法的軌跡隱私保護(hù)方法中最常用的方法，但k-匿名易受到一致性攻擊和背景知識(shí)攻擊；l-diversity易受到相似性攻擊等.為解決其相關(guān)問(wèn)題，2006年Dwork[8-9]首次提出利用差分隱私保護(hù)解決基于背景知識(shí)的攻擊等.

差分隱私[9]建立在堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)上,并對(duì)隱私保護(hù)進(jìn)行了嚴(yán)格的數(shù)學(xué)定義；確保差分隱私保護(hù)在攻擊者擁有任意背景知識(shí)下仍能夠保護(hù)用戶隱私；其中，差分隱私保護(hù)模型的基本思想是對(duì)原始數(shù)據(jù)[2,10]、原始數(shù)據(jù)的轉(zhuǎn)換數(shù)據(jù)或者統(tǒng)計(jì)結(jié)果[1,11]添加噪音來(lái)達(dá)到隱私保護(hù)效果；而對(duì)原始數(shù)據(jù)擾動(dòng)將影響軌跡數(shù)據(jù)中位置的可用性，影響數(shù)據(jù)的挖掘和分析.現(xiàn)有基于統(tǒng)計(jì)的差分隱私保護(hù)方法[11-12]對(duì)統(tǒng)計(jì)結(jié)果添加隨機(jī)噪音，但添加隨機(jī)噪音不能有效控制噪音量和控制數(shù)據(jù)可用性.為解決差分隱私保護(hù)中添加隨機(jī)噪音的弊端，本文對(duì)軌跡統(tǒng)計(jì)結(jié)果添加適量噪音實(shí)現(xiàn)隱私保護(hù)效果，同時(shí)確保數(shù)據(jù)的可用性.

1 相關(guān)工作

軌跡數(shù)據(jù)有2種類型[13-16]，本文使用以軌跡為數(shù)據(jù)庫(kù)記錄的軌跡數(shù)據(jù)庫(kù).目前，軌跡數(shù)據(jù)隱私保護(hù)相關(guān)研究如下，Abul等人[17]計(jì)算軌跡距離相近的k條軌跡構(gòu)成匿名集，并發(fā)布k條軌跡對(duì)應(yīng)采樣點(diǎn)的匿名區(qū)域，實(shí)現(xiàn)軌跡隱私保護(hù)；孟小峰等人[18]遍歷軌跡數(shù)據(jù)構(gòu)建前綴樹，并對(duì)前綴樹進(jìn)行剪枝和重構(gòu)形成k-匿名前綴樹，遍歷經(jīng)過(guò)處理的k-匿名前綴樹得到k-匿名軌跡數(shù)據(jù)，從而達(dá)到軌跡k-匿名隱私保護(hù)效果.雖然軌跡k-匿名方法是目前最常用并且簡(jiǎn)單的隱私保護(hù)方法，但基于知識(shí)背景的攻擊將威脅到用戶隱私泄露.

為解決軌跡k-匿名隱私保護(hù)方法中存在的問(wèn)題，Mir等人[11]首次將基于統(tǒng)計(jì)的差分隱私運(yùn)用到軌跡數(shù)據(jù)中，通過(guò)對(duì)軌跡數(shù)據(jù)中軌跡統(tǒng)計(jì)構(gòu)造成前綴樹，并對(duì)其統(tǒng)計(jì)結(jié)果添加隨機(jī)Laplace噪音實(shí)現(xiàn)差分隱私保護(hù)；而后Chen等人[12]為提高軌跡數(shù)據(jù)的可用性，提出自適應(yīng)差分預(yù)算決定添加噪音量，但是該方法容易耗盡差分預(yù)算使差分隱私失效影響隱私保護(hù)等；Jiang等人[14]通過(guò)采樣相應(yīng)方向和距離的軌跡，進(jìn)行差分隱私處理達(dá)到隱私保護(hù)的效果；Yang等人[19]根據(jù)w-event privacy[20]對(duì)其進(jìn)一步改進(jìn)優(yōu)化為l-trajectory privacy，通過(guò)自適應(yīng)差分預(yù)算添加隨機(jī)噪音，從而提高數(shù)據(jù)的可用性；Yu等人[21]提出一種高效的差分隱私保護(hù)方法實(shí)現(xiàn)無(wú)線網(wǎng)絡(luò)數(shù)據(jù)軌跡的隱私保護(hù).Hua等人[2]利用k-means聚類軌跡中位置并通過(guò)指數(shù)機(jī)制實(shí)現(xiàn)最優(yōu)泛化，然后應(yīng)用添加隨機(jī)Laplace噪音的差分隱私，構(gòu)建成并發(fā)布噪音軌跡數(shù)據(jù)集，實(shí)現(xiàn)用戶隱私保護(hù),但這種軌跡隱私保護(hù)的方法不能解決軌跡數(shù)據(jù)集較大并且軌跡位置域大的問(wèn)題.

為避免對(duì)原始軌跡數(shù)據(jù)直接添加噪音[2,14,19,22]影響數(shù)據(jù)的可用性；本文也是通過(guò)構(gòu)建前綴樹，并對(duì)其統(tǒng)計(jì)結(jié)果添加相應(yīng)的Laplace噪音實(shí)現(xiàn)隱私保護(hù)；本文與文獻(xiàn)[1，22]的不同之處：1)車聯(lián)網(wǎng)中車輛的行駛軌跡具有Markov過(guò)程的特性，并根據(jù)其特性計(jì)算軌跡中位置節(jié)點(diǎn)的敏感度，通過(guò)敏感度控制噪音量；2)遍歷軌跡數(shù)據(jù)庫(kù)中完整軌跡，并統(tǒng)計(jì)軌跡數(shù)據(jù)的位置節(jié)點(diǎn)，從而確保軌跡數(shù)據(jù)的完整性和可用性；3)本文為確保經(jīng)過(guò)差分隱私后的軌跡數(shù)據(jù)的安全性和可用性，使用軌跡統(tǒng)計(jì)閾值θ、敏感度閾值μ和極大敏感度閾值μm，在確保實(shí)現(xiàn)差分隱私保護(hù)的情況下對(duì)軌跡數(shù)據(jù)添加適量噪音實(shí)現(xiàn)軌跡隱私保護(hù)，同時(shí)提高軌跡數(shù)據(jù)的可用性等.

2 預(yù)備知識(shí)

2.1 軌跡數(shù)據(jù)庫(kù)

軌跡和軌跡數(shù)據(jù)集[1-2,11,13,23]的定義如下：

定義1. 軌跡.軌跡中的位置節(jié)點(diǎn)Ci是由時(shí)間和位置構(gòu)成(ti,Li)；軌跡T是由有限個(gè)位置節(jié)點(diǎn)組成:(t1,L1)→(t2,L2)→(t3,L3)→…→(ti,Li)；其中T(ti)=Li.每條軌跡代表車聯(lián)網(wǎng)中車輛行駛的軌跡，作為軌跡數(shù)據(jù)庫(kù)中的一條記錄.車聯(lián)網(wǎng)中車輛的軌跡形成軌跡數(shù)據(jù)庫(kù)D={T1,T2,…,T|D|}.

表1是軌跡數(shù)據(jù)庫(kù)樣例，軌跡數(shù)據(jù)庫(kù)中位置節(jié)點(diǎn)域L={L1,L2,L3,L4}；下面以該數(shù)據(jù)庫(kù)為例具體闡述該隱私保護(hù)方法.

Table 1 Trace Database表1 軌跡數(shù)據(jù)庫(kù)

2.2 位置敏感度

車聯(lián)網(wǎng)中車輛的行駛軌跡具有Markov過(guò)程的特征，因此軌跡中位置節(jié)點(diǎn)的敏感度與當(dāng)前位置節(jié)點(diǎn)發(fā)生的概率有關(guān).

Markov過(guò)程.設(shè){T(t),t∈}的狀態(tài)空間為S,如果對(duì)于任意的n≥2,任意的t1

P(T(tn)=Ln|T(t1)=L1,…,T(tn-1)=Ln-1)=
P(T(tn)=Ln|T(tn-1)=Ln-1)，

(1)

則稱其是Markov過(guò)程.

定義2. 位置節(jié)點(diǎn)敏感度ω.指軌跡中發(fā)生在位置節(jié)點(diǎn)在泄露軌跡用戶隱私的概率：ω=Ps×Pm；其中Pm是時(shí)刻ti下軌跡位置節(jié)點(diǎn)Ci在T(ti)=Li狀態(tài)時(shí)發(fā)生的概率：

Pm=P(Li|L1→L2→…→Li-1)=P(Li|Li-1)，

(2)

Ps是車輛在當(dāng)前軌跡中處于Ci-1位置節(jié)點(diǎn)的敏感度.

2.3 差分隱私保護(hù)理論基礎(chǔ)

差分隱私保護(hù)是基于數(shù)據(jù)失真的隱私保護(hù)技術(shù)，通過(guò)添加噪聲實(shí)現(xiàn)差分隱私保護(hù)，同時(shí)確保擾動(dòng)后的數(shù)據(jù)保持某些統(tǒng)計(jì)方面的性質(zhì)，以便進(jìn)行數(shù)據(jù)挖掘等操作[24].

定義3. 差分隱私[12,22,24-27].設(shè)隨機(jī)算法A，Pr[z]表示事件z的披露風(fēng)險(xiǎn).對(duì)于任意差別至多為一個(gè)記錄的數(shù)據(jù)集D1和D2，若算法A在數(shù)據(jù)集D1和D2上任意輸出結(jié)果D滿足:

(3)

則稱算法A滿足ε-差分隱私保護(hù).其中，ε為隱私預(yù)算；ε與其隱私保護(hù)強(qiáng)度成反比.

定義4. 全局敏感度.對(duì)任意一個(gè)函數(shù)f:D1→d函數(shù)f的全局敏感度為

(4)

添加噪聲技術(shù)是實(shí)現(xiàn)差分隱私保護(hù)重要機(jī)制；Laplace噪音機(jī)制[28]和指數(shù)噪音機(jī)制[29]是常用的2種實(shí)現(xiàn)差分隱私的噪音添加技術(shù).本文使用Laplace噪音機(jī)制對(duì)軌跡數(shù)據(jù)庫(kù)中位置節(jié)點(diǎn)的統(tǒng)計(jì)結(jié)果添加噪音.

Laplace噪音機(jī)制[10].Laplace噪音機(jī)制是對(duì)數(shù)值型的輸出結(jié)果添加噪音實(shí)現(xiàn)差分隱私.添加的Laplace噪音服從Laplace分布，則Laplace概率密度函數(shù)為

(5)

3 基于軌跡位置節(jié)點(diǎn)統(tǒng)計(jì)的差分隱私保護(hù)

3.1 Laplace機(jī)制噪音添加過(guò)程

Laplace機(jī)制是對(duì)輸出為數(shù)值型的結(jié)果添加噪音.

Laplace機(jī)制噪音添加過(guò)程如下：

0.5×[1+sgn(x)×(1-e-|x|/λ)]，

(6)

根據(jù)Laplace分布得到逆分布函數(shù)：

F-1(x)=-λ×sgn(p-0.5)×
ln(1-2×|p-0.5|)，

(7)

隨機(jī)生成一個(gè)[0,1]的隨機(jī)數(shù)p，通過(guò)逆分布函數(shù)計(jì)算x，故生成了服從Laplace分布的隨機(jī)噪音x.

3.2 基于軌跡位置節(jié)點(diǎn)統(tǒng)計(jì)的差分隱私保護(hù)方法

目前，許多研究是通過(guò)添加Laplace噪音機(jī)制實(shí)現(xiàn)差分隱私保護(hù)，文獻(xiàn)[1]通過(guò)自適應(yīng)計(jì)算差分預(yù)算控制噪音量，但其仍是隨機(jī)添加的噪音，不能有效控制其噪音量.因此本文統(tǒng)計(jì)軌跡數(shù)據(jù)庫(kù)中軌跡的位置節(jié)點(diǎn)，并根據(jù)車輛的軌跡具有的Markov過(guò)程特性計(jì)算軌跡中位置節(jié)點(diǎn)的敏感度；控制敏感度閾值和統(tǒng)計(jì)閾值保證軌跡數(shù)據(jù)的最大可用性.

實(shí)現(xiàn)基于統(tǒng)計(jì)的差分隱私保護(hù)方法步驟如下：

1) 構(gòu)建基于位置節(jié)點(diǎn)統(tǒng)計(jì)的前綴樹.通過(guò)對(duì)軌跡數(shù)據(jù)庫(kù)中的軌跡遍歷并統(tǒng)計(jì)位置節(jié)點(diǎn)，并構(gòu)建軌跡前綴樹，如圖1所示.

2) 構(gòu)建噪音前綴樹.車聯(lián)網(wǎng)中車輛的行駛軌跡具有Markov過(guò)程的特性，根據(jù)其特性計(jì)算軌跡中位置節(jié)點(diǎn)的敏感度；并根據(jù)軌跡中位置節(jié)點(diǎn)敏感度和敏感度閾值μ添加相應(yīng)的Laplace噪音；算法1闡述了具體的構(gòu)建過(guò)程.

3) 發(fā)布噪音軌跡數(shù)據(jù).為提高軌跡數(shù)據(jù)安全性，運(yùn)用文獻(xiàn)[1]對(duì)添加噪音后的處理過(guò)濾技術(shù)等；設(shè)置軌跡統(tǒng)計(jì)閾值θ，通過(guò)閾值決定是否對(duì)噪音樹剪枝；算法2將給出具體算法.

通過(guò)直接遍歷軌跡數(shù)據(jù)庫(kù)的軌跡構(gòu)建軌跡數(shù)據(jù)前綴樹，以表1軌跡數(shù)據(jù)庫(kù)為例構(gòu)建軌跡數(shù)據(jù)前綴樹，如圖1所示：

Fig. 1 Statistical prefix tree of trace data圖1 軌跡數(shù)據(jù)統(tǒng)計(jì)前綴樹

通過(guò)軌跡數(shù)據(jù)前綴樹計(jì)算軌跡數(shù)據(jù)中位置節(jié)點(diǎn)的敏感度；通過(guò)敏感度閾值μ和敏感度ω添加相應(yīng)Laplace噪音，并生成噪音前綴樹.算法1闡述了具體的實(shí)現(xiàn)過(guò)程.

算法1. 構(gòu)建噪音前綴樹.

輸入：通過(guò)遍歷軌跡數(shù)據(jù)庫(kù)并統(tǒng)計(jì)軌跡中位置節(jié)點(diǎn)構(gòu)建的前綴樹PT，μ，μm，θ，ε，其中μ是敏感度閾值，μm是最大敏感度閾值；

輸出：含有每個(gè)位置節(jié)點(diǎn)敏感度的前綴樹PT1.

① 初始化Stack，Stack.push(PT)，ε1=ε/h；

②PT→p=1；

③N=Stack.top()；

④PT→ω=1/PT→c；

⑤ While (!Stack.empty(N))

⑥Pm=ComputeMarkovP(N)；

⑦Ps=N→parent→ω；

⑧N→ω=Pm×Ps；

⑨ IfN→ω>μAndN→ω<μmThen

⑩N→c=N→c+|laplace(ω)|；

算法1首先初始化軌跡前綴樹根節(jié)點(diǎn)敏感度和差分預(yù)算；遍歷構(gòu)建成的軌跡前綴樹，計(jì)算軌跡中節(jié)點(diǎn)的敏感度.通過(guò)函數(shù)ComputeMarkovP(N)計(jì)算位置節(jié)點(diǎn)N在時(shí)刻t發(fā)生的概率；并根據(jù)位置節(jié)點(diǎn)敏感度定義計(jì)算軌跡前綴樹中位置節(jié)點(diǎn)敏感度.使用laplace(ω)噪音函數(shù)對(duì)軌跡中位置節(jié)點(diǎn)添加相應(yīng)的Laplace噪音，實(shí)現(xiàn)差分隱私保護(hù)；其中μ是敏感度閾值，ω是敏感度；根據(jù)μ和ω控制噪音量.如圖2是對(duì)表1軌跡數(shù)據(jù)庫(kù)計(jì)算軌跡中位置節(jié)點(diǎn)的敏感度，并添加相應(yīng)Laplace噪音，構(gòu)建成的噪音前綴樹.

Fig. 2 Noise prefix tree圖2 噪音前綴樹

為提高添加噪音后的軌跡數(shù)據(jù)的安全性和可用性，由于構(gòu)建軌跡前綴樹需要具有一致性約束[1,12]條件.本文利用文獻(xiàn)[1,12]的噪音過(guò)濾技術(shù)；并使用統(tǒng)計(jì)閾值θ對(duì)過(guò)濾過(guò)的噪音前綴樹剪枝，然后將擾動(dòng)后的數(shù)據(jù)發(fā)布.算法2闡述軌跡數(shù)據(jù)發(fā)布的過(guò)程.

算法2. 發(fā)布噪音軌跡數(shù)據(jù).

輸入：噪音前綴樹PT1、統(tǒng)計(jì)閾值θ；

輸出：發(fā)布數(shù)據(jù)D2.

① 初始化T,N,Stack；

②T=FilterNoisyTree(PT1)；

③Stack.push(T)；

④N=Stack.top()；

⑤ While(!Stack.empty(N))

⑥ IfN→c<θThen

⑦ IfNis leaf Then

⑧ 刪除節(jié)點(diǎn)N；

⑨ Else

⑩ 刪除以N為根的子樹；

其中FilterNoisyTree()使用了文獻(xiàn)[1,12]過(guò)濾技術(shù)，算法2首先利用FilterNoisyTree(PT1)對(duì)噪音前綴樹過(guò)濾實(shí)現(xiàn)軌跡前綴樹的一致性約束；并根據(jù)設(shè)置的位置節(jié)點(diǎn)統(tǒng)計(jì)閾值θ對(duì)過(guò)濾后的噪音樹剪枝，從而提高軌跡數(shù)據(jù)的安全性和可用性，并發(fā)布擾動(dòng)后的軌跡數(shù)據(jù).

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

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

實(shí)驗(yàn)數(shù)據(jù)集來(lái)自UCI提供的數(shù)據(jù)集MSNBC真實(shí)數(shù)據(jù)集，MSNBC是一個(gè)公開(kāi)可用的數(shù)據(jù)庫(kù).從MSNBC數(shù)據(jù)集中抽取200多條數(shù)據(jù)進(jìn)行試驗(yàn)；其中數(shù)據(jù)特征為：軌跡數(shù)據(jù)中位置節(jié)點(diǎn)域大小為17、軌跡最大長(zhǎng)度為324、抽取的數(shù)據(jù)集平均長(zhǎng)度為5.4.

實(shí)驗(yàn)的硬件環(huán)境為：AMD CPU X5750 3.40 GHz,4.00 GB內(nèi)存，操作系統(tǒng)為Microsoft Windows 7，算法均是由C++語(yǔ)言編程實(shí)現(xiàn).

4.2 實(shí)驗(yàn)評(píng)估

(8)

為了有效評(píng)價(jià)軌跡數(shù)據(jù)的可用性，使用平均相對(duì)誤差評(píng)價(jià)軌跡數(shù)據(jù)庫(kù)的可用度.

首先,在不同的差分預(yù)算下，實(shí)驗(yàn)運(yùn)行50次，計(jì)算Prefix，N-Garm，CDPM這3種方法的平均相對(duì)誤差.圖3是不同的差分預(yù)算下Prefix,N-Garm，CDPM方法的平均相對(duì)誤差的比較.圖3顯示在不同的差分預(yù)算下CDPM方法的平均相對(duì)誤差比Prefix和N-Garm方法的平均相對(duì)誤差明顯減小；由于Prefix方法是隨機(jī)添加Laplace噪音，故噪音量比較大，平均相對(duì)誤差大，而N-Garm方法通過(guò)自適應(yīng)改變差分預(yù)算，但并沒(méi)改變隨機(jī)添加噪音，減小了平均相對(duì)誤差.隨機(jī)添加噪音，不能有效地控制Laplace噪音量.因此CDPM方法通過(guò)位置節(jié)點(diǎn)敏感度添加適量Laplace噪音.實(shí)驗(yàn)表明在相同的差分預(yù)算下，CDPM方法既可以實(shí)現(xiàn)差分隱私保護(hù)，同時(shí)可以有效地降低平均相對(duì)誤差，提高軌跡數(shù)據(jù)的可用性.

Fig. 3 Average relative error of three different methods of differential privacy protection圖3 3種不同差分隱私保護(hù)方法的平均相對(duì)誤差

Fig. 4 Average relative error vs statistical threshold圖4 平均相對(duì)誤差與統(tǒng)計(jì)閾值

Fig. 5 Average relative error vs sensitivity threshold圖5 平均相對(duì)誤差與敏感度閾值

5 總 結(jié)

本文研究了車聯(lián)網(wǎng)中軌跡數(shù)據(jù)隱私保護(hù)機(jī)制，提出了一種對(duì)軌跡統(tǒng)計(jì)結(jié)果擾動(dòng)的差分隱私保護(hù)機(jī)制，即使攻擊者擁有任何的背景知識(shí)仍能保護(hù)車輛的身份等隱私.我們的主要貢獻(xiàn)在于：對(duì)軌跡中的位置統(tǒng)計(jì)進(jìn)行定向而非隨機(jī)擾動(dòng).如此即可實(shí)現(xiàn)軌跡發(fā)布的差分隱私保護(hù)，同時(shí)又可提高數(shù)據(jù)的可用性，這是使用新方法的益處.

[1]Chen Rui, Fung B, Desai B, et al. Differentially private transit data publication: A case study on the montreal transportation system[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 213-221

[2] Hua Jingyu, Gao Yue, Zhong Sheng. Differentially private publication of general time-gerial trajectory data[C] //Proc of IEEE ICC 2015. Piscataway, NJ: IEEE, 2015: 163-175

[3] Clarke R. Person location and person tracking-technologies, risks and policy implication[J]. Information Technology & People, 2001, 14(2): 206-231

[4] Zhou Changli, Ma Chunguang, Yang Songtao. Location privacy-preserving method for LBS continuous KNN query in road networks[J]. Journal of Computer Research and Development, 2015, 52(11): 2628-2644 (in Chinese)(周長(zhǎng)利, 馬春光, 楊松濤. 路網(wǎng)環(huán)境下保護(hù)LBS位置隱私的連 續(xù)KNN查詢方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(11): 2628-2644)

[5] Huo Zheng, Meng Xiaofeng. A survey of trajectory privacy-preserving techniques[J]. Chinese Journal of Computers, 2011, 34(10): 1820-1830 (in Chinese)(霍崢, 孟小峰. 軌跡隱私保護(hù)技術(shù)研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(10): 1820-1830)

[6] Sweeney L. K-anonymity: A model for protecting privacy[J]. IEEE Security & Privacy Magazine, 2012, 10(5): 557-570

[7] Machanavajjhala A, Kifer D, Gehrke J. L-diversity: Privacy beyondk-anonymity[C] //Proc of the 29th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2013: 66-92

[8] Dwork C. Differential privacy: A survey of results[G] //LNCS 4978: Proc of Int Conf on Theory and Applications of Models of Computation (TAMC 2008). Berlin: Springer, 2008: 1-19

[9] Dwork C. Differential Privacy[G] //LNCS 4052: Proc of the 33rd Int Conf on Automata, Languages and Programming. Berlin: Springer, 2006: 1-12

[10] Quan Daiyong, Yin Lihua, Guo Yunchuan. Enhancing the trajectory privacy with Laplace mechanism[C] //Proc of IEEE TRUSTCOM’15. Piscataway, NJ: IEEE, 2015: 1218-1223

[11] Mir D, Isaacman S, Cáceres R, et al. Dp-where: Differentially private modeling of human mobility[C] //Proc of IEEE Big Data 2013. Piscataway, NJ: IEEE, 2013: 580-588

[12] Chen Rui, Acs G, Castelluccia C. Differentially private sequential data publication via variable-lengthn-grams[C] //Proc of ACM CCS’12. New York: ACM, 2012: 638-649

[13] Shao Dongxu, Jiang Kaifeng, Kister T, et al. Publishing trajectory with differential privacy: A priori vs a posteriori sampling mechanisms[C] //Proc of the 24th Int Conf on Database and Expert Systems Applications. New York: ACM, 2013: 357-365

[14] Jiang Kaifeng, Shao Dongxu, Bressan S, et al. Publishing trajectories with differential privacy guarantees[C] //Proc of the 25th Int Conf on Scientific and Statistical Database Management. New York: ACM, 2013: 12

[15] He Yunhua, Sun Limin, Yang Weidong, et al. Privacy preserving for node trajectory in VSN: A game-theoretic analysis based approach[J]. Journal of Computer Research and Development, 2014, 51(11): 2483-2492 (in Chinese)(何云華, 孫利民, 楊衛(wèi)東, 等. 基于博弈分析的車輛感知網(wǎng)絡(luò)節(jié)點(diǎn)軌跡隱私保護(hù)機(jī)制[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(11): 2483-2492)

[16] Wu Yingjie, Tang Qingming, Ni Weiwei, et al. A clustering hybrid based algorithm for privacy preserving trajectory data publishing[J]. Journal of Computer Research and Development, 2013, 50(3): 578-593 (in Chinese)(吳英杰, 唐慶明, 倪巍偉, 等. 基于聚類雜交的隱私保護(hù)軌跡數(shù)據(jù)發(fā)布算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(3): 578-593)

[17] Abul O, Bonchi F, Nanni M. Never walk alone: Uncertainty for anonymity in moving objects databases[C] //Proc of the 29th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2008: 376-385

[18] Huo Zheng, Meng Xiaofeng, Huang Yi. PrivateCheckin: Trajectory privacy-preserving for check-in services in MSNS[J]. Chinese Journal of Computers, 2013, 36(4): 716-726 (in Chinese)(霍崢, 孟小峰, 黃毅. PrivateCheckIn: 一種移動(dòng)社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(4): 716-726)

[19] Yang Cao, Yoshikawa M. Differentially private real-time data release over infinite trajectory streams[C] //Proc of the 16th IEEE Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2015: 68-73

[20] Kellaris G, Papadopoulos S, Xiao Xiaokui, et al. Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1155-1166

[21] Yu Jiadi, Dong Xin, Luo Yuan, et al. Differentially private wireless data publication in large-scale WLAN networks[C] //Proc of the 21st Int Conf on Parallel & Distributed Systems. Piscataway, NJ: IEEE, 2015: 290-297

[22] Yu Dong, Kang Haiyan. Privacy protection method on time-series data publication[J]. Journal on Communications, 2015, 36(S1): 243-249 (in Chinese)(于東, 康海燕. 面向時(shí)序數(shù)據(jù)發(fā)布的隱私保護(hù)方法研究[J]. 通信學(xué)報(bào), 2015, 36(S1): 243-249)

[23] Agard B. Mining public transport user behaviour from smart card data[J]. IFAC Proceedings Volumes, 2006, 39(3): 399-404

[24] Xiong Ping, Zhu Tianqing, Wang Xiaofeng. A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014, 37(1): 101-122 (in Chinese)(熊平, 朱天清, 王曉峰. 差分隱私保護(hù)及其應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(1): 101-122)

[25] Chen Rui, Mohammed N, Fung B, et al. Publishing set-valued data via differential privacy[J]. VLDB, 2011, 4(4): 1087-1098

[26] Hay M, Li Chao, Miklau G, et al. Accurate estimation of the degree distribution of private networks[C] //Proc of the 9th Int Conf on Data Mining. Piscataway, NJ: IEEE, 2009: 169-178

[27] Lan Lihui, Ju Shiguang. Privacy preserving based on differential privacy for weighted social networks[J]. Journal on Communications, 2015, 36(9): 145-159 (in Chinese)(蘭麗輝, 鞠時(shí)光. 基于差分隱私的權(quán)重社會(huì)網(wǎng)絡(luò)隱私保護(hù)[J]. 通信學(xué)報(bào), 2015, 36(9): 145-159)

[28] Dwork C, Mcsherry F, Nissim K. Calibrating noise to sensitivity in private data analysis[C] //Proc of the 3rd conf on Theory of Cryptography. New York: ACM, 2006: 265-284

[29] Mcsherry F, Talwar K. Mechanism design via differential privacy[C] //Proc of IEEE FOCS’07. Piscataway, NJ: IEEE, 2007: 94-103

[30] Xiao Xiaokui, Bender G, Hay M, et al. iReduct: Differential privacy with reduced relative errors[C] //Proc of ACM SIGMOD’11. New York: ACM, 2011: 229-240ZhuWeijun, born in 1976. PhD, associate professor. Senior member of CCF. His main research interests include information security, DNA computing and formal methods.

TrajectoryPrivacyPreservingBasedonStatisticalDifferentialPrivacy

Zhu Weijun1, You Qingguang1, Yang Weidong2, and Zhou Qinglei1

1(SchoolofInformationEngineering,ZhengzhouUniversity,Zhengzhou450001)2(CollegeofInformationScienceandEngineering,HenanUniversityofTechnology,Zhengzhou450001)

With the continuous development of Internet of vehicles, Internet of vehicles provides the convenient services to drivers and passengers. But it also brings some new problems of privacy protection. The existing methods for trajectory data publishing may leak users’ location privacy. Thus, it may endanger the users’ personal safety. In order to avoid the drawbacks of adding random noise in the existing methods for differential privacy protection, we propose a novel method for trajectory privacy protection based on statistical differential privacy. At first, one can calculate the sensitivity of position nodes in vehicle traces according to the characteristics of traces since there are some characteristics of Markov process in vehicle traces. And then, one can add some moderate Laplace noises according to the sensitivity of position nodes, statistical threshold and sensitivity threshold. As a result, the new method is obtained. Evaluating the availability of the trajectory data through the average relative error, the experimental results verify the availability and effectiveness of the proposed approach for privacy preserving based on statistical differential privacy.

trajectory data; differential privacy; Markov process; data publishing; privacy protection

2016-08-22；

2016-12-09

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB0800100)；國(guó)家自然科學(xué)基金項(xiàng)目(61202099，U1204608，U1304606，61572444)；中國(guó)博士后科學(xué)基金項(xiàng)目(2015M572120，2012M511588)

This work was supported by the National Key Research and Development Program of China (2016YFB0800100), the National Natural Science Foundation of China (61202099, U1204608, U1304606, 61572444), and the China Postdoctoral Science Foundation (2015M572120, 2012M511588).

游慶光(757383480@qq.com)

TP309

YouQingguang, born in 1990. Master. His main research interests include information security and vehicular ad hoc network.

YangWeidong, born in 1977. PhD, associate professor. Senior member of CCF. His main research interests include vehicular ad hoc network and information security.

ZhouQinglei, born in 1962. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include DNA computing, formal methods and information security.