基于優(yōu)化局部抑制的軌跡數(shù)據(jù)發(fā)布隱私保護算法

俞慶英,王燕飛,葉梓彤,張雙桂,陳傳明

(安徽師范大學(xué) a.計算機與信息學(xué)院; b.網(wǎng)絡(luò)與信息安全安徽省重點實驗室,安徽 蕪湖 241002)

0 概述

隨著GPS、Wi-Fi等定位技術(shù)以及存儲技術(shù)的快速發(fā)展,大量移動用戶的軌跡數(shù)據(jù)被搜集并存儲[1-3]。軌跡數(shù)據(jù)包含著豐富的時空信息,對軌跡數(shù)據(jù)進行深入研究和分析已成為數(shù)據(jù)挖掘領(lǐng)域的一個研究熱點[4-6]。可用性高的軌跡數(shù)據(jù)是有效軌跡數(shù)據(jù)挖掘的基礎(chǔ),研究者通過對軌跡數(shù)據(jù)的分析和挖掘,可以得到有價值的信息[7-8]。但是,軌跡數(shù)據(jù)也包含著移動用戶的大量隱私信息,如果軌跡數(shù)據(jù)在發(fā)布前不進行保護處理,掌握背景知識的攻擊者就可以通過分析軌跡數(shù)據(jù)從而推斷出用戶的隱私信息,例如身體狀況、生活習(xí)慣和家庭住址等,甚至?xí)o用戶帶來經(jīng)濟損失以及人身安全問題[9-11]。因此,如何保證所發(fā)布的軌跡數(shù)據(jù)不會泄露用戶的隱私并且具有較高的可用性是一個急需解決的問題[12-14]。

目前,軌跡數(shù)據(jù)發(fā)布中的隱私保護方法研究已取得了一定的成果。文獻[15]提出適用于RFID數(shù)據(jù)的LKC隱私模型,并設(shè)計一種有效的匿名算法以實現(xiàn)LKC隱私模型。該算法首先識別數(shù)據(jù)集中的最小違反序列集合,然后在每次迭代中用貪心算法對違反序列進行全局抑制,目的在于盡可能減少最大頻繁序列的損失,從而提高數(shù)據(jù)的可用性。由于全局抑制導(dǎo)致大量數(shù)據(jù)損失,文獻[16]在全局抑制的基礎(chǔ)上引入了局部抑制,并提出了(K,C)L隱私模型以及實現(xiàn)該模型的算法。該算法由2個階段組成,首先確定在軌跡數(shù)據(jù)集中違反給定(K,C)L隱私要求的所有序列,然后進行一系列的局部和全局抑制對軌跡數(shù)據(jù)集進行簡化,同時保持盡可能高的數(shù)據(jù)效用。文獻[17]提出可消除身份鏈接攻擊、屬性鏈接攻擊和相似性攻擊的PPTD算法,其為一種執(zhí)行敏感屬性泛化和移動點的軌跡局部抑制方法,該方法對軌跡的隱私等級進行劃分,并通過敏感屬性泛化識別臨界軌跡數(shù)據(jù)記錄,然后對軌跡進行局部抑制,通過MPSTD算法來識別剩余的關(guān)鍵軌跡數(shù)據(jù)記錄,并從中消除多個移動點,使得匿名軌跡數(shù)據(jù)集中沒有關(guān)鍵軌跡數(shù)據(jù)記錄,并最小化信息損失。文獻[18]在局部抑制和全局抑制的基礎(chǔ)上引入了分裂的思想,并提出LSUP、GSUP、SPLIT和MIX 4種匿名算法,前3種算法分別采用局部抑制、全局抑制和軌跡分裂的方法,第4種算法采用抑制混合分裂方法來減少信息損失。

以上研究中采用的方法都是全局抑制聯(lián)合局部抑制,無法解決全局抑制造成的數(shù)據(jù)損失率大的問題。為了在保證軌跡隱私保護水平較高的同時提高軌跡發(fā)布數(shù)據(jù)的可用性,本文提出一種滿足(K,C)L模型的優(yōu)化局部抑制方法,該方法僅使用局部抑制來進行軌跡隱私保護。

1 相關(guān)定義

定義1(軌跡) 軌跡是由一系列按時間戳排序的位置點構(gòu)成的集合,如式(1)所示:

tr={ID,loc1t1→loc2t2→…→lociti→…→locntn}

(1)

其中,ID表示軌跡用戶標(biāo)識符,loci表示軌跡tr的第i個位置,ti表示軌跡tr的第i個時間戳,表示軌跡tr中的第i個時間戳位置點,也稱軌跡的實例,n=|tr|表示軌跡tr的長度,即軌跡tr中含有的位置點個數(shù)。

本文研究的軌跡還包含敏感屬性特征s,具體可見式(2):

tr={ID,loc1t1→loc2t2→…→lociti→…→locntn:s}

(2)

定義2(軌跡數(shù)據(jù)集) 由一組軌跡組成的集合稱為軌跡數(shù)據(jù)集,記作T,如式(3)所示:

T={tr1,tr2,…,tri,…,trl}

(3)

其中,tri表示T中的第i條軌跡,l表示T中包含的軌跡條數(shù),也可以用|T|表示,即|T|=l。

表1所示為一個包含敏感屬性的軌跡數(shù)據(jù)集T的數(shù)據(jù)格式示例。

表1 原始軌跡數(shù)據(jù)集T的數(shù)據(jù)格式示例Table 1 Sample data format of original track dataset T

在軌跡數(shù)據(jù)集中,如果某個敏感屬性值與一些位置點序列頻繁地出現(xiàn)在同一條軌跡中,攻擊者即使不能唯一地識別出受害者的軌跡,也可以從這些序列中推斷出敏感值。下面舉2個例子進行說明:

例1如表1所示,假設(shè)攻擊者掌握了某用戶曾經(jīng)到過a1、d2和f63個位置點的背景知識,那么攻擊者可以推斷出該用戶患有HIV的概率高達2/3≈66.7%,原因是同時包含a1、d2和f6的3條軌跡記錄(tr1、tr5、tr8)中有2條都包含了敏感屬性值HIV。

例2表1只是本文實驗數(shù)據(jù)集的數(shù)據(jù)格式示例,該軌跡數(shù)據(jù)集共包含80 000條軌跡,但其中同時包含a3、e4和a53個位置點的軌跡僅有32條,而在這32條軌跡中敏感屬性值為SARS的就有13條,如果攻擊者掌握了某用戶曾經(jīng)到過a3、e4和a5這3個位置點的背景知識,那么攻擊者可以推斷出該用戶患有SARS的概率就為13/32≈40.6%。

定義3((K,C)L隱私模型) 假定L為攻擊者所掌握背景知識的最大長度,S是數(shù)據(jù)擁有者從軌跡數(shù)據(jù)集的敏感屬性中挑選的敏感值集合,軌跡數(shù)據(jù)集T滿足(K,C)L隱私模型當(dāng)且僅當(dāng)T中長度大于0且小于等于L的序列p符合以下2個條件[17]:

1)|T(p)|≥K,其中,T(p)指軌跡數(shù)據(jù)集T中包含p的軌跡集合,|T(p)|表示其中的軌跡條數(shù),K是一個正整數(shù)。

2)對于任一s∈S都滿足Conf(s|T(p))≤C,其中,0≤C≤1,Conf(s|T(p))是T(p)中包含s的軌跡所占比例。

定義4(頻繁序列) 給定閾值E>0,若序列p在軌跡中出現(xiàn)的次數(shù)大于等于E,則稱p為頻繁序列。

定義5(最大頻繁序列) 若序列p是軌跡數(shù)據(jù)集T中的頻繁序列并且p的父序列都不是頻繁序列,則稱p為最大頻繁序列,記作MFS(Maximal Frequent Sequence)[19]。

定義6(違反序列) 假定序列p的長度大于0且小于等于L,給定(K,C)L隱私模型,若序列p不滿足定義3中的任一個條件,則稱p為違反序列[15]。

定義7(最小違反序列) 若p為違反序列并且p的子序列中都沒有違反序列,則稱p為最小違反序列,記做MVS(Minimal Violating Sequence)[16]。

定義8(有效局部抑制) 對軌跡數(shù)據(jù)集進行局部抑制不會產(chǎn)生新的最小違反序列,則稱該局部抑制為有效局部抑制[16]。

定義9(實例得分表) 設(shè)有實例q,其得分表是指通過抑制q可以消除的最小違反序列的數(shù)量與抑制q損失的實例個數(shù)之比,將得分記為Score(q),計算公式如式(4)所示:

(4)

其中,mvsLoss(q)是包含q的MVS個數(shù),instanceLoss(q)是通過抑制q損失的實例個數(shù)。

定義10(軌跡損失率) 軌跡損失率是指經(jīng)過隱私保護算法處理后數(shù)據(jù)集中減少的軌跡條數(shù)與原始數(shù)據(jù)集T中的軌跡條數(shù)之比,計算公式如式(5)所示:

(5)

其中,TrajectoryLossNum表示經(jīng)過算法處理后減少的軌跡條數(shù),OriginalTrajectoryNum表示原始數(shù)據(jù)集中的軌跡條數(shù)。

2 滿足(K,C)L模型的局部抑制軌跡隱私保護

2.1 算法描述

本文提出一種滿足(K,C)L模型的局部抑制軌跡隱私保護算法,主要包含2個步驟:

1)算法1,在對需要進行全局抑制的序列進行局部抑制操作后,計算可能會產(chǎn)生的最小違反序列。

2)算法2,利用局部抑制方法實現(xiàn)軌跡數(shù)據(jù)的匿名化操作。

本文算法的流程如圖1所示。

圖1 本文算法流程Fig.1 Procedure of the algorithm in this paper

2.1.1 最小違反序列計算

將計算新產(chǎn)生的最小違反序列的算法記為GetNewMVS,算法思想如下:只有p既屬于T(m)又屬于T(q)-T(m)時,p才有可能成為新的最小違反序列[16]。算法偽代碼如算法1所示。首先篩選出所有符合條件的實例(第1行),移除已經(jīng)在MVS中的序列(第2行～第3行),然后將A中實例產(chǎn)生的所有長度不大于L并且包含實例q的序列存放入P中(第4行),并刪除P中不包含實例q的序列(第5行),接著將在T(q)-T(m)中S的子集放入S1中(第6行),最后掃描T(q)-T(m),計算P中每個序列是否滿足(K,C)L隱私模型,若不滿足,則將該序列加入V1中(第7行～第15行)。

算法1GetNewMVS算法

輸入原始軌跡數(shù)據(jù)集T,背景知識長度L,匿名數(shù)K,推斷概率C,敏感值集合S,需要全局抑制的序列m以及實例q,最小違反序列集合MVS

輸出新產(chǎn)生的最小違反序列V1

1.A←Find instances in both T(m) and T(q)-T(m);

2.V1←Extract all MVSs with length one;

3.Delete all non-q instances in V1from A;

4.P← All sequences with length ≤ L generated by natural connection of A

5.Delete the sequences without q from P;

6.S1←Scan T(q)-T(m) to find the subset of S;

7.for each sequence p in P do

8.Scan T(q)-T(m) to calculate T(p) and Conf(s|T(p)) for any s∈S1;

9.maxConf ←MAX(Conf(s|T(p)));

10.if T(p)>0 and (T(p)C) then

11.if p ?MVS then

12.Add newly generated MVS to V1;

13.end if

14.end if

15.end for

16.return V1;

例3設(shè)算法GetNewMVS的輸入為表1所示的原始軌跡數(shù)據(jù)集T,L=2,K=2,C=0.5,S={HIV},m={b3→c7},q=b3,MVS={a1,b3→c7,d2→e4}。算法1的執(zhí)行過程如下:

計算出T(m)={tr3},T(q)={tr1,tr3,tr4},根據(jù)算法1的第1行～第3行得到A={b3,d2,e8}、V1={a1};根據(jù)第4行～第5行,得到P={b3,b3→e8,d2→b3};由第6行可得S1=2;由第7行～第15行可得V1={d2→b3}。因此,執(zhí)行算法1后對{b3→c7}進行局部抑制會產(chǎn)生新的最小違反序列{d2→b3}。

2.1.2 滿足(K,C)L模型的優(yōu)化局部抑制算法

將滿足(K,C)L模型的優(yōu)化局部抑制算法記為TPL-Local,其偽代碼如算法2所示。第1行首先調(diào)用文獻[17]算法獲取MVS,第2行判斷所有最小違反序列的抑制方式,并根據(jù)定義9計算各序列得分,第3行初始化V1,第4行～第20行選擇ds中得分最高的實例q進行抑制,循環(huán)上述過程,直至實例得分表為空。第5行～第16行根據(jù)q的抑制方式采取相關(guān)的操作,若q為局部抑制,則抑制T(m)中的實例q;若q為全局抑制,則將所有包含q的最小違反序列加入到V2中,調(diào)用算法1計算出新產(chǎn)生的最小違反序列V1,對V2中的所有最小違反序列m,抑制T(m)中的實例q,并將V1加入到原MVS中。第17行～第18行更新MVS,并重新計算V1中所有序列的抑制方式和得分,第19行將V1的實例加入ds中。重復(fù)上述操作,直至實例得分表為空。

算法2TPL-Local算法

輸入原始軌跡數(shù)據(jù)集T,背景知識長度L,匿名數(shù)K,推斷概率C,敏感值集合S

輸出滿足(K,C)L模型的軌跡數(shù)據(jù)集T′

1.Obtain MVS by calling MVS algorithm presented in literature[17];

2.Perform GetNewMVS algorithm to determine the suppression mode of all sequences in MVS and build ds;

3.V1← ?;

4.while ds≠? do

5.Select an instance q with the highest score in ds and get its MVS;

6.if q is a local suppression instance then

7.V2←the sequence m1which contains q and meets T(m1) == T(m); //m1∈MVS

8.Suppress all instances of q in T(m);

9.else

10.V2←MVS(q);

11.Calculate new MVS V1generated from V2by Algorithm 1;

12.for each sequence m∈V1do

13.Suppress all instances of q in T(m);

14.end for

15.Add V1to MVS;

16.end if

17.MVS←MVS-V2;

18.Update Score(q′) if q′ in V2;

19.Add all instances of V1to ds;

20.end while

21.return the processed T as T′;

例4設(shè)算法TPL-Local的輸入為表1所示的原始軌跡數(shù)據(jù)集T,L=2,K=2,C=0.5,S={HIV}。算法2的執(zhí)行過程如下:

根據(jù)算法2的第1行得到表1中的最小違反序列MVS={a1,b3→c7,d2→e4};由第2行可得實例{a1}的抑制方式為局部抑制,實例{b3,c7,d2,e4}的抑制方式均為全局抑制,ds={a1,b3,c7,d2,e4}中的實例得分值分別為0.333 3、0.333 3、0.200 0、0.142 9和0.250 0;由第4行可得ds≠?;第5行選擇實例得分表中分?jǐn)?shù)最高的實例進行抑制,其中得分最高的實例為q={a1},m={a1};第8行對{a1}進行局部抑制;第17行刪除已經(jīng)被抑制的序列m,得到MVS={b3→c7,d2→e4};第18行更新實例得分表,得到ds={b3,c7,d2,e4}中的實例得分值分別為0.333 3、0.200 0、0.142 9和0.250 0;第19行將V1中的實例加入到ds中,因為V1為空,ds不變,由第4行可得ds≠?,所以循環(huán)沒有結(jié)束,再由第5行可得q={b3},m={b3→c7},因為q的抑制方式為全局抑制,由第10行可得V2={b3→c7};第11行獲取因局部抑制q產(chǎn)生的新的最小違反序列集合,可得V1={d2→b3};第12行～第14行對所有包含q的MVS進行局部抑制;第15行將新產(chǎn)生的最小違反序列加入MVS中,可得MVS={b3→c7,d2→e4,d2→b3};根據(jù)第17行可得MVS={d2→e4,d2→b3};第18行～第19行更新實例得分表,可得ds={d2,e4,d2,b3}中的實例得分值分別為0.142 9、0.250 0、2.000 0和0.500 0。循環(huán)執(zhí)行上述操作,直至匿名化的數(shù)據(jù)集中沒有最小違反序列。對表1中的軌跡數(shù)據(jù)集執(zhí)行算法2后產(chǎn)生的結(jié)果如表2所示。

表2 滿足(K,C)L模型的軌跡數(shù)據(jù)集T′Table 2 Track dataset T′ satisfying (K,C)L model

2.2 算法分析

2.2.1 復(fù)雜度分析

本文算法的時間復(fù)雜度共包含2個部分:

2.2.2 安全性分析

文獻[16]已證明當(dāng)且僅當(dāng)T中不包含最小違反序列時一個軌跡數(shù)據(jù)集滿足(K,C)L模型。本文算法對文獻[16]算法進行改進,文獻[16]中的全局抑制是抑制所有實例,局部抑制僅抑制引起隱私泄露的實例。定義原始軌跡數(shù)據(jù)集為T,數(shù)據(jù)集中的最小違反序列集合為MVS,本文算法通過將軌跡數(shù)據(jù)集T包含q的所有需要全局抑制的最小違反序列V1進行局部抑制,更新序列的抑制方式,并將刪除q后產(chǎn)生的新最小違反序列V2加入到最小違反序列集合中,一次抑制操作后的T′相當(dāng)于一個新的軌跡數(shù)據(jù)集,而其最小違反序列為MVS-V1+V2,新產(chǎn)生的最小違反序列V2的抑制方式有3種情況:

1)產(chǎn)生的最小違反序列都是有效局部抑制。

2)產(chǎn)生的最小違反序列都是無效局部抑制。

3)產(chǎn)生的最小違反序列既有有效局部抑制,也有無效局部抑制。

最好的是第1種情況,通過一次局部抑制可以改變實例q的抑制方式,減少實例q的損失;最差的是第2種情況,產(chǎn)生的最小違反序列仍然都是無效局部抑制,重復(fù)上述操作,直至T中沒有包含q的最小違反序列。因此,本文算法得到的軌跡數(shù)據(jù)集仍滿足(K,C)L模型。

3 實驗驗證

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

本文實驗采用合成數(shù)據(jù)集City80K[15-16,20]來測試數(shù)據(jù)的實用性損失。City80K是模擬擁有26個板塊的大都市中80 000個行人一天24 h移動軌跡的數(shù)據(jù)集,其中包含5種敏感屬性值,實驗選擇其中的一種作為敏感值[16]。所有對比算法用MATLAB語言實現(xiàn),運行在Intel i7-5500U CPU(3.0 GHz)、8 GB內(nèi)存、7200RPM 1 TB硬盤的工作站中,操作系統(tǒng)為Window 10。

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

損失率是衡量軌跡數(shù)據(jù)集實用性的重要參數(shù),本文從實例、MFS和軌跡3個方面衡量實用性損失[16],具體如下:

1)在實例損失方面,使用式(6)進行衡量:

(6)

其中,N(T)是原始數(shù)據(jù)集中實例的總數(shù),N(T′)是經(jīng)過算法處理后數(shù)據(jù)集中實例的總數(shù)。

2)在MFS損失方面,使用式(7)進行衡量:

(7)

其中,U(T)是原始數(shù)據(jù)集中MFS的總數(shù),U(T′)是經(jīng)過算法處理后數(shù)據(jù)集中MFS的總數(shù)。本文使用文獻[19]中的MAFIA算法計算MFS。

3)在軌跡損失方面,使用式(8)進行衡量:

(8)

其中,P(T)是原始數(shù)據(jù)集中的軌跡數(shù)目,P(T′)是經(jīng)過算法處理后數(shù)據(jù)集中的軌跡數(shù)目。

3.3 結(jié)果分析

為了充分研究TPL-Local算法的有效性,本文將TPL-Local算法與文獻[16]中的KCL-Local算法進行比較。

3.3.1C值對數(shù)據(jù)損失的影響

圖2所示為2種算法在不同的C值下實例損失率、MFS損失率以及軌跡損失率情況,其中,L=3,K=30,E=800。由圖2可以看出,實例損失率、MFS損失率以及軌跡損失率均隨著C值的遞增而先減小后趨于穩(wěn)定。C值遞增造成最小違反序列數(shù)目遞減并趨于穩(wěn)定,被抑制序列的個數(shù)遞減并穩(wěn)定,因此,實例損失率、MFS損失率和軌跡損失率先遞減后穩(wěn)定。當(dāng)C值較小時,最小違反序列以全局抑制的方式為主,2種算法的損失率相似,隨著C值的增大,最小違反序列數(shù)目減少并且局部抑制序列增多,被抑制的序列個數(shù)減少并穩(wěn)定。2種算法相比,本文TPL-Local算法有效減少了實例損失,因此其損失率更低。

圖2 C值對數(shù)據(jù)損失的影響Fig.2 Effect of C value on data loss

3.3.2K值對數(shù)據(jù)損失的影響

圖3所示為2種算法在不同的K值下實例損失率、MFS損失率以及軌跡損失率情況,其中,L=3,C=0.4,E=800。由圖3可以看出,實例損失率、MFS損失率和軌跡損失率均隨著K值的增大而增大。因為K值的增大造成最小違反序列和全局抑制序列增多,所以被抑制的序列增多,數(shù)據(jù)損失率也會相應(yīng)增加。當(dāng)K值較小時,最小違反序列以局部抑制的方式為主,2種算法的損失率相似,隨著K值的不斷增大,全局抑制序列與被抑制的序列均增多。2種算法相比,本文TPL-Local算法有效減少了實例損失,因此其損失率更低。

圖3 K值對數(shù)據(jù)損失的影響Fig.3 Effect of K value on data loss

3.3.3E值對數(shù)據(jù)損失的影響

圖4所示為2種算法在不同的E值下MFS損失率情況,其中,L=3,C=0.4,K=40。由圖4可以看出,KCL-Local算法的MFS損失率隨著E值的增大先增加后減小,本文算法的MFS損失率先減小后增加。本文算法以局部抑制影響全局抑制的方法有效減少了實例損失,因此,其MFS損失率更低。

圖4 E值對MFS損失率的影響Fig.4 Effect of E value on MFS loss rate

4 結(jié)束語

本文提出一種滿足(K,C)L模型的優(yōu)化局部抑制軌跡隱私保護算法TPL-Local,其采用以局部抑制代替全局抑制的方式實現(xiàn)軌跡數(shù)據(jù)的隱私保護,從而降低軌跡損失率、實例損失率和MFS損失率。實驗結(jié)果表明,TPL-Local算法的數(shù)據(jù)損失率性能優(yōu)于KCL-Local隱私保護算法。后續(xù)將在保證隱私保護算法高效性的同時進一步提高數(shù)據(jù)可用性。