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

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

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

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

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

(zhuweijun@zzu.edu.cn)

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 預備知識

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

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

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

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

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

2.2 位置敏感度

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

Markov過程.設{T(t),t∈}的狀態(tài)空間為S,如果對于任意的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過程.

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

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

(2)

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

2.3 差分隱私保護理論基礎

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

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

(3)

則稱算法A滿足ε-差分隱私保護.其中，ε為隱私預算；ε與其隱私保護強度成反比.

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

(4)

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

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

(5)

3 基于軌跡位置節(jié)點統(tǒng)計的差分隱私保護

3.1 Laplace機制噪音添加過程

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

Laplace機制噪音添加過程如下：

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)

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

3.2 基于軌跡位置節(jié)點統(tǒng)計的差分隱私保護方法

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

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

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

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

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

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

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

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

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

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

輸出：含有每個位置節(jié)點敏感度的前綴樹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é)點敏感度和差分預算；遍歷構(gòu)建成的軌跡前綴樹，計算軌跡中節(jié)點的敏感度.通過函數(shù)ComputeMarkovP(N)計算位置節(jié)點N在時刻t發(fā)生的概率；并根據(jù)位置節(jié)點敏感度定義計算軌跡前綴樹中位置節(jié)點敏感度.使用laplace(ω)噪音函數(shù)對軌跡中位置節(jié)點添加相應的Laplace噪音，實現(xiàn)差分隱私保護；其中μ是敏感度閾值，ω是敏感度；根據(jù)μ和ω控制噪音量.如圖2是對表1軌跡數(shù)據(jù)庫計算軌跡中位置節(jié)點的敏感度，并添加相應Laplace噪音，構(gòu)建成的噪音前綴樹.

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

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

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

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

輸出：發(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é)點N；

⑨ Else

⑩ 刪除以N為根的子樹；

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

4 實驗分析

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

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

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

4.2 實驗評估

(8)

為了有效評價軌跡數(shù)據(jù)的可用性，使用平均相對誤差評價軌跡數(shù)據(jù)庫的可用度.

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

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

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

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

5 總 結(jié)

本文研究了車聯(lián)網(wǎng)中軌跡數(shù)據(jù)隱私保護機制，提出了一種對軌跡統(tǒng)計結(jié)果擾動的差分隱私保護機制，即使攻擊者擁有任何的背景知識仍能保護車輛的身份等隱私.我們的主要貢獻在于：對軌跡中的位置統(tǒng)計進行定向而非隨機擾動.如此即可實現(xiàn)軌跡發(fā)布的差分隱私保護，同時又可提高數(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)(周長利, 馬春光, 楊松濤. 路網(wǎng)環(huán)境下保護LBS位置隱私的連 續(xù)KNN查詢方法[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)(霍崢, 孟小峰. 軌跡隱私保護技術(shù)研究[J]. 計算機學報, 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)絡節(jié)點軌跡隱私保護機制[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)(吳英杰, 唐慶明, 倪巍偉, 等. 基于聚類雜交的隱私保護軌跡數(shù)據(jù)發(fā)布算法[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: 一種移動社交網(wǎng)絡中的軌跡隱私保護方法[J]. 計算機學報, 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ù)據(jù)發(fā)布的隱私保護方法研究[J]. 通信學報, 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)(熊平, 朱天清, 王曉峰. 差分隱私保護及其應用[J]. 計算機學報, 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)(蘭麗輝, 鞠時光. 基于差分隱私的權(quán)重社會網(wǎng)絡隱私保護[J]. 通信學報, 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

國家重點研發(fā)計劃項目(2016YFB0800100)；國家自然科學基金項目(61202099，U1204608，U1304606，61572444)；中國博士后科學基金項目(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.