唐印滸， 鐘 誠(chéng)

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,廣西 南寧 530004)

動(dòng)態(tài)多敏感屬性匿名保護(hù)多線程并行算法

唐印滸， 鐘 誠(chéng)

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,廣西 南寧 530004)

文章通過(guò)建立偽記錄表,將新添加的記錄與偽記錄進(jìn)行匹配,創(chuàng)造刪除偽記錄的機(jī)會(huì),以達(dá)到減少匿名數(shù)據(jù)集中偽記錄的目的,將記錄桶進(jìn)行分割,設(shè)計(jì)實(shí)現(xiàn)一種動(dòng)態(tài)多敏感屬性匿名保護(hù)的多線程并行算法c-m-inv。實(shí)驗(yàn)結(jié)果表明,算法c-m-inv高效、生成的多敏感屬性匿名數(shù)據(jù)集具有較高的可用性。

數(shù)據(jù)匿名;多敏感屬性;m-不變性;多線程并行

近年來(lái),動(dòng)態(tài)數(shù)據(jù)集重發(fā)布的隱私保護(hù)問(wèn)題得到了廣泛關(guān)注。文獻(xiàn)[1]率先研究了動(dòng)態(tài)數(shù)據(jù)集的匿名化,提出了針對(duì)數(shù)據(jù)插入行為的匿名策略,它要求新插入的記錄需要滿足匿名模型要求之后,才能加入到發(fā)布的下一版本中,且限于增量數(shù)據(jù)集。文獻(xiàn)[2]考慮了數(shù)據(jù)增量更新的情形,提出防止數(shù)據(jù)重發(fā)布過(guò)程中發(fā)生隱私泄漏的單調(diào)概化原則,設(shè)計(jì)基于劃分的增量數(shù)據(jù)重發(fā)布k-匿名算法。文獻(xiàn)[3]提出了m-不變性(m-invariance) 單敏感屬性的數(shù)據(jù)集動(dòng)態(tài)匿名算法,它解決了需要插入和刪除操作的動(dòng)態(tài)數(shù)據(jù)集重發(fā)布中敏感信息泄露的問(wèn)題,但它沒(méi)有處理屬性值更新的情形。為了提高單敏感屬性的數(shù)據(jù)集動(dòng)態(tài)匿名的效率,文獻(xiàn)[4]改進(jìn)了m-不變性動(dòng)態(tài)匿名算法,使之處理不同類(lèi)型的數(shù)據(jù)時(shí)效率更高。為了使得算法能夠同時(shí)處理動(dòng)態(tài)插入、刪除、屬性值更新的隱私保護(hù),文獻(xiàn)[5]提出了基于泛化的m-Distinct匿名原則,它要求假設(shè)“各個(gè)插入、刪除的數(shù)據(jù)記錄之間獨(dú)立不相關(guān)”。文獻(xiàn)[6-7]研究了針對(duì)單敏感屬性的動(dòng)態(tài)數(shù)據(jù)集的匿名算法。文獻(xiàn)[8]提出一種全局擔(dān)保的方案,以期確保記錄數(shù)據(jù)在各個(gè)發(fā)布版本中的隱私不被泄露,該方案未考慮攻擊者的背景知識(shí)。文獻(xiàn)[9]提出了θ-inclusion模型,對(duì)記錄插入和刪除的情況提供隱私保護(hù),利用該模型進(jìn)行隱私保護(hù)時(shí),損失的信息量較少。θ-inclusion模型未考慮屬性值更新的情形，通過(guò)保持記錄中敏感元素在更新過(guò)程中的連續(xù)性和多樣性,文獻(xiàn)[10]提出一種面向動(dòng)態(tài)集值屬性數(shù)據(jù)重發(fā)布的隱私保護(hù)模型,以及采用局部重編碼泛化和隱藏技術(shù)降低數(shù)據(jù)匿名信息損失的重發(fā)布算法,該算法需引入較多的偽記錄。文獻(xiàn)[11]引入敏感屬性更新集和同一等價(jià)敏感組概念,給出一種修改、添加和刪除數(shù)據(jù)時(shí)的數(shù)據(jù)可用性較高的重發(fā)布策略,該策略的使用可能存在需要推遲發(fā)布某條數(shù)據(jù)記錄的情形。

在m-不變性動(dòng)態(tài)匿名算法的基礎(chǔ)上,本文通過(guò)建立偽記錄表,創(chuàng)造減少數(shù)據(jù)集中偽記錄數(shù)目的機(jī)會(huì),以提高匿名數(shù)據(jù)集的數(shù)據(jù)可用性;將記錄桶分割處理,采用多線程并行技術(shù)以提高算法處理大數(shù)據(jù)集多敏感屬性匿名的效率。

1 算 法

1.1 算法優(yōu)化策略

將m-不變性算法直接應(yīng)用于處理多敏感屬性數(shù)據(jù)集會(huì)產(chǎn)生2個(gè)問(wèn)題:① 多敏感屬性之間的組合將使得算法處理的時(shí)間大大增加。② 隨著時(shí)間的推移、發(fā)布版本的增多,偽記錄的數(shù)目將會(huì)越來(lái)越多,偽記錄占匿名數(shù)據(jù)集的比例會(huì)越來(lái)越大,這將大大降低匿名數(shù)據(jù)集的數(shù)據(jù)可用性。而且記錄需要滿足所有敏感屬性值的要求才能加入到對(duì)應(yīng)的桶中,這樣滿足條件的記錄數(shù)量會(huì)相對(duì)減少,需要添加的偽記錄數(shù)量會(huì)進(jìn)一步增多。

為了解決上述問(wèn)題,本文引入一個(gè)不發(fā)布的偽記錄表,存放所有添加的偽記錄。當(dāng)在下一時(shí)刻有新的記錄添加進(jìn)來(lái)時(shí),首先查看這個(gè)偽記錄表中是否有與待增加的新記錄的敏感屬性值相同的偽記錄。若有,則可將該偽記錄從偽記錄表中刪除,并在其所在的分組用新記錄替換該偽記錄。從而可以減少匿名數(shù)據(jù)表中偽記錄的個(gè)數(shù),在不降低匿名數(shù)據(jù)集的隱私保護(hù)程度的前提下,達(dá)到提高匿名數(shù)據(jù)集的數(shù)據(jù)可用性的目的。

另一方面,在匿名算法的分割步中,桶與桶之間的分割沒(méi)有關(guān)聯(lián)、沒(méi)有數(shù)據(jù)共享或交換,因此對(duì)所有的桶進(jìn)行分割,采用多線程技術(shù)實(shí)現(xiàn)匿名算法的并行化,以減少算法的運(yùn)行時(shí)間,同時(shí)設(shè)計(jì)有效的數(shù)據(jù)結(jié)構(gòu)保存數(shù)據(jù),減少多敏感屬性數(shù)據(jù)的匹配時(shí)間,進(jìn)一步提高算法的效率。

1.2 算法描述

算法1給出了基于m-不變性的動(dòng)態(tài)多屬性數(shù)據(jù)匿名并行算法，即c-m-inv算法。

算法1c-m-inv算法

輸入:tn-1時(shí)刻的原始數(shù)據(jù)表T(n-1)和匿名數(shù)據(jù)表T*(n-1)、tn時(shí)刻的原始數(shù)據(jù)表T(n)。

輸出:tn時(shí)刻的匿名數(shù)據(jù)表T*(n)。

Begin

(1) 由原始數(shù)據(jù)表T(n-1)和T(n),求出S∩=T(n)∩T(n-1),S-=T(n)-T(n-1)。

(2) 根據(jù)匿名數(shù)據(jù)表T*(n-1)中的分組數(shù)num構(gòu)建相應(yīng)數(shù)目的桶BUCi,并給各桶BUCi賦予相應(yīng)的敏感屬性值,i∈[1,num]。

(3) 將S∩中的記錄按照分組號(hào)G-ID及敏感屬性值Sensitives劃分到對(duì)應(yīng)桶BUCi中的對(duì)應(yīng)敏感屬性值維度上。

(4) 若|S-|=0,則轉(zhuǎn)到步驟(6)。

(5) 將S-中的記錄Recordj(j∈[0, |S-|-1])與偽記錄表的偽記錄Counterfeits(s∈[0, |Counterfeit|-1])進(jìn)行比較:若有匹配項(xiàng),則在該偽記錄所在的桶(分組)中將偽記錄Counterfeits替換為該條新增加的記錄Recordj,并在偽記錄表中將其刪除,更新偽記錄統(tǒng)計(jì)表。

(6) 對(duì)每個(gè)桶BUCi,判斷其每一維敏感屬性值上是否具有相同數(shù)目的記錄,直到所有桶達(dá)到平衡狀態(tài)。若每一維敏感屬性值上具有相同數(shù)目的記錄,則該桶達(dá)到平衡狀態(tài);否則,在S-中尋找敏感屬性值與該不平衡桶BUCi記錄缺少的那一維敏感屬性值相同的記錄Recordj。若找到,在保證S-滿足m-eligible性質(zhì)的前提下,將Recordj加入到桶BUCi中對(duì)應(yīng)的敏感屬性值維度上,將Recordj從S-中刪除;若找不到或者找到了但刪除Recordj后S-不再滿足m-eligible性質(zhì),則需要在桶BUCi中對(duì)應(yīng)的敏感屬性值維度上添加一條偽記錄,并更新偽記錄表和偽記錄統(tǒng)計(jì)表。

(7) 若|S-|=0,則轉(zhuǎn)到步驟(8);否則,在確保桶BUCi滿足平衡條件的前提下,將S-中的記錄Recordj加入到包含Recordj的敏感屬性值的桶BUCi中。

(8) fori=1 to num do in parallel

線程i計(jì)算桶BUCi能分割的分組數(shù),分別在每個(gè)敏感屬性值維度上選擇1條記錄構(gòu)成1個(gè)分組,將分組存到匿名數(shù)據(jù)表T*(n)中。

(9) 將匿名數(shù)據(jù)表T*(n)發(fā)布。

End

c-m-inv算法與原始的m-不變性算法的隱私保護(hù)程度都是通過(guò)參數(shù)m來(lái)決定的,參數(shù)m取值相同,則隱私保護(hù)程度相同,因此c-m-inv算法并沒(méi)有降低隱私保護(hù)程度。c-m-inv算法在判斷桶是否平衡之前,增加了一個(gè)匹配偽記錄表的步驟,若匹配成功則可以將偽記錄刪除掉,從而可以在一定程度上減少總體偽記錄的數(shù)目。與m-不變性算法相比,c-m-inv算法中偽記錄數(shù)目占整個(gè)匿名數(shù)據(jù)集的比例降低了,從而達(dá)到了提高匿名數(shù)據(jù)集的數(shù)據(jù)可用性目的。c-m-inv算法并行分割桶,實(shí)現(xiàn)線程級(jí)并行處理,提高了多敏感屬性數(shù)據(jù)匿名算法的效率。

2 實(shí) 驗(yàn)

實(shí)驗(yàn)硬件環(huán)境為AMD Athlon(tm) II X2 250 3.00 GHz CPU、4.0 GB RAM的計(jì)算機(jī),運(yùn)行的操作系統(tǒng)為Microsoft Windows 7,軟件環(huán)境為Microsoft Visual Studio 2008,采用C++編程實(shí)現(xiàn)算法并分別與m-inv算法[3]和NCm-inv算法[4]進(jìn)行實(shí)驗(yàn)比對(duì)。

實(shí)驗(yàn)數(shù)據(jù)集是從網(wǎng)站http://ipums.org下載的真實(shí)數(shù)據(jù)集SAL,共包含有60萬(wàn)條記錄,每條記錄包括Age、Gender、Education和Birthplace4個(gè)準(zhǔn)標(biāo)識(shí)符屬性,以及Occupation和Income 2個(gè)敏感屬性。

實(shí)驗(yàn)開(kāi)始時(shí),從SAL數(shù)據(jù)集的60萬(wàn)條記錄中,隨機(jī)選取30萬(wàn)條記錄作為第1次發(fā)布的原始數(shù)據(jù)集T(1)。SAL中除了T(1)以外剩余的30萬(wàn)條記錄作為更新用的一個(gè)數(shù)據(jù)倉(cāng)庫(kù)storage。從第2次發(fā)布開(kāi)始,每次的原始數(shù)據(jù)集將由上次發(fā)布的原始數(shù)據(jù)集與這個(gè)數(shù)據(jù)倉(cāng)庫(kù)storage一起生成。例如,第2次發(fā)布的原始數(shù)據(jù)集T(2)的生成過(guò)程如下:從T(1)中刪除掉r條記錄,并從storage中隨機(jī)取r條記錄添加到T(1)中,得到T(2)。參數(shù)r表示每次發(fā)布的更新率,r取3 000。根據(jù)文獻(xiàn)[3]的計(jì)算公式,將有H=1+300k/r=101次發(fā)布。本文選取算法在t=2、9、16、23、30、37次的發(fā)布版本中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)對(duì)比。

本文c-m-inv算法和m-inv算法[3]在不同時(shí)刻的發(fā)布版本中添加的偽記錄數(shù)如圖1所示。

圖1 不同時(shí)刻c-m-inv算法和m-inv算法的偽記錄數(shù)

從圖1可以看出,隨著時(shí)間的推移,m-inv算法處理的匿名數(shù)據(jù)集中的偽記錄數(shù)量在逐漸地增加。這是由于m-inv算法中只有增加偽記錄的步驟,沒(méi)有刪除偽記錄,即使每一步只添加少量的偽記錄,偽記錄的數(shù)量在數(shù)據(jù)集中所占的比重還是會(huì)越來(lái)越大,m-inv算法發(fā)布的匿名數(shù)據(jù)集的數(shù)據(jù)可用性也將會(huì)隨著時(shí)間的推移越來(lái)越低。也可看出,c-m-inv算法和m-inv算法在第2次發(fā)布的匿名數(shù)據(jù)集中偽記錄數(shù)目相等。這是由于第2次發(fā)布時(shí),c-m-inv算法和m-inv算法都只進(jìn)行偽記錄的添加,沒(méi)有刪除,而且2個(gè)算法在該時(shí)刻的輸入一樣,它們添加的偽記錄數(shù)目也一樣。

c-m-inv算法在不同時(shí)刻匿名數(shù)據(jù)集中的偽記錄數(shù)有增有減,且數(shù)量少于m-inv算法。這是由于c-m-inv算法增加了1個(gè)匹配偽記錄表的步驟,若匹配成功則將偽記錄刪除掉,從而可以在一定程度上減少偽記錄的數(shù)目,c-m-inv算法發(fā)布的匿名數(shù)據(jù)集的數(shù)據(jù)可用性高于m-inv算法。

參數(shù)m變化時(shí),c-m-inv算法和m-inv算法在所有時(shí)刻的平均偽記錄數(shù)如圖2所示。

圖2 m值變化時(shí)c-m-inv算法和m-inv算法的平均偽記錄數(shù)

圖2的實(shí)驗(yàn)結(jié)果表明:① 隨著m值的增大,c-m-inv算法和m-inv算法的平均偽記錄數(shù)均呈增加趨勢(shì)。這是由于隨著m的增大,數(shù)據(jù)記錄需要滿足所有多維敏感屬性的值才能加入到桶中,此時(shí)滿足要求的記錄數(shù)變少,需要加入更多的偽記錄來(lái)確保桶的平衡；②c-m-inv算法的平均偽記錄數(shù)低于m-inv算法的平均偽記錄數(shù)。這是由于c-m-inv算法在平衡桶的過(guò)程中有機(jī)會(huì)能將之前添加的偽記錄刪除。

參數(shù)m取值變化時(shí),c-m-inv算法和m-inv算法在所有時(shí)刻的平均運(yùn)行時(shí)間如圖3所示。

從圖3可以看出,隨著m值的增大,c-m-inv算法和m-inv算法在所有時(shí)刻的平均運(yùn)行時(shí)間均呈下降趨勢(shì)。這是由于隨著m值的增大,雖然偽記錄數(shù)也在增加,但相對(duì)于數(shù)據(jù)集大小來(lái)說(shuō),這個(gè)增加量非常小,而且每個(gè)桶中敏感屬性的維度均需要大于或等于m,每次需要生成的桶的數(shù)量將呈下降趨勢(shì),對(duì)桶的初始化、平衡、分割等操作所需的時(shí)間減少,算法的平均運(yùn)行時(shí)間也將下降。當(dāng)m值大于5時(shí),c-m-inv算法的平均運(yùn)行時(shí)間少于m-inv算法。這是由于c-m-inv算法分割了桶(分組)數(shù)據(jù),采用多線程技術(shù)并行處理各桶,提高了算法的運(yùn)行效率。

圖3 m值變化時(shí)c-m-inv算法和m-inv算法的平均運(yùn)行時(shí)間

為了進(jìn)一步檢驗(yàn)本文c-m-inv算法的性能,c-m-inv算法和NCm-inv算法[4]在不同時(shí)刻的發(fā)布版本中添加的偽記錄數(shù)如圖4所示。

圖4 不同時(shí)刻c-m-inv算法和NC m-inv算法的偽記錄數(shù)

從圖4可以看出,在大多數(shù)情形下,c-m-inv算法產(chǎn)生的偽記錄數(shù)少于NCm-inv算法產(chǎn)生的偽記錄數(shù)。另一方面,隨著時(shí)間的推移,NCm-inv算法處理的匿名數(shù)據(jù)集中的偽記錄數(shù)量總是在逐漸增加。這是由于雖然NCm-inv算法采用了將數(shù)值型數(shù)據(jù)轉(zhuǎn)變成分類(lèi)型數(shù)據(jù)的方法來(lái)降低敏感屬性值的取值范圍,一定程度上減少了偽記錄數(shù)量,但是算法中依然沒(méi)有刪除偽記錄的處理步驟,其偽記錄數(shù)量依舊會(huì)逐漸增多。

參數(shù)m取值變化時(shí),c-m-inv算法和NCm-inv算法在所有時(shí)刻的平均偽記錄數(shù)如圖5所示。

圖5 m值變化時(shí)c-m-inv算法和NC m-inv算法的平均偽記錄數(shù)

圖5的實(shí)驗(yàn)結(jié)果表明，隨著m值的增大,算法需要加入更多的偽記錄來(lái)確保桶的平衡,因此c-m-inv算法和NCm-inv算法的平均偽記錄數(shù)均呈逐漸增加趨勢(shì)。另一方面,當(dāng)m值較小時(shí),NCm-inv算法的平均偽記錄數(shù)小于c-m-inv算法的平均偽記錄數(shù);但當(dāng)m值大于7時(shí),c-m-inv算法的平均偽記錄數(shù)低于NCm-inv算法的平均偽記錄數(shù)。這是因?yàn)閏-m-inv算法在平衡桶的過(guò)程中有機(jī)會(huì)能將之前添加的偽記錄刪除。

參數(shù)m取值變化時(shí),c-m-inv算法和NCm-inv算法在所有時(shí)刻的平均運(yùn)行時(shí)間如圖6所示。

圖6 m值變化時(shí)c-m-inv算法和NC m-inv算法的平均運(yùn)行時(shí)間

從圖6可以看出,隨著m值的增大,c-m-inv算法和NCm-inv算法在所有時(shí)刻的平均運(yùn)行時(shí)間均呈下降趨勢(shì)。另一方面,c-m-inv算法的平均運(yùn)行時(shí)間略微多于NCm-inv算法。這是由于c-m-inv算法處理的是多維敏感屬性值數(shù)據(jù)集,其在劃分、平衡、分配數(shù)據(jù)幾個(gè)步驟中耗時(shí)相對(duì)較多,而NCm-inv算法處理的是單敏感屬性數(shù)據(jù)集,故而耗時(shí)較少。

綜上所述,c-m-inv算法發(fā)布的匿名數(shù)據(jù)集的數(shù)據(jù)可用性較高,更適用于處理大數(shù)據(jù)集的動(dòng)態(tài)多敏感屬性匿名保護(hù)。

3 結(jié) 論

本文給出的c-m-inv算法引入偽記錄表,通過(guò)將偽記錄表和新增記錄集進(jìn)行匹配,以確定是否刪除偽記錄,從而在一定程度上減少匿名數(shù)據(jù)集中偽記錄的數(shù)目,提高發(fā)布的匿名數(shù)據(jù)集的數(shù)據(jù)可用性;采用多線程技術(shù)并行處理各桶(分組)數(shù)據(jù),提高了大數(shù)據(jù)集多敏感屬性匿名處理效率。下一步工作將研究混合型動(dòng)態(tài)多敏感屬性數(shù)據(jù)集的隱私保護(hù)的高效算法。

[1] BYUN J W,SOHN Y,BERTINO E,et al.Secure anonymization for incremental datasets[J].Secure Data Management,2006,4165:48-63.

[2] 吳英杰,倪巍偉,張柏禮,等.k-APPRP:一種基于劃分的增量數(shù)據(jù)重發(fā)布敏感信息保護(hù)k-匿名算法[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30 (8):1581-1587.

[3] XIAO Xiaokui,TAO Yufei.m-Invariance:towards privacy preserving re-publication of dynamic datasets[C]//Proceedings of 2007 ACM SIGMOD Conference on Management of Data (SIGMOD).New York:ACM,2007:689-700.

[4] XIA Xiaoling,XIAO Qiang,JI Wei.An efficient method to implement data private protection for dynamic numerical sensitive attributes[C]//Proceedings of the 7th International Conference on Computer Science & Education.[S.l.]:IEEE,2012:797-802.

[5] 李豐.面向動(dòng)態(tài)數(shù)據(jù)集重發(fā)布的隱私保護(hù)研究[D].上海:復(fù)旦大學(xué),2009.

[6] WANG K,XU J,PEI J,et al.MaintainingK-anonymity against incremental updates[C]//Proceedings of the 19th International Conference on Scientific and Statistical Database Management,Washington,D.C.:IEEE Conputer Society,2007:5-14.

[7] BU Y Y,FU A W C,WONG R C W,et al.Privacy preserving serial data publishing by role composition[J].Proceedings of the VLDB Endoument,2008,1(1):845-856.

[8] WONG R C W,FU A W C,LIU J,et al.Preserving individual privacy in serial data publishing [J/OL].Computer Science,2009:1-12[2009-03-06].http://arxiv.org/abs/0903.0682.

[9] 李嬋.基于動(dòng)態(tài)數(shù)據(jù)的隱私保護(hù)研究[D].南昌:南昌大學(xué),2010.

[10] 武毅,王丹,蔣宗禮.基于事務(wù)型K-Anonymity 的動(dòng)態(tài)集值屬性數(shù)據(jù)重發(fā)布隱私保護(hù)方法[J].計(jì)算機(jī)研究與發(fā)展,2013,50(增刊1):248-256.

[11] 左蘇楠,卞藝杰,吳慧.基于DMSA算法的多敏感屬性數(shù)據(jù)重發(fā)布隱私保護(hù)新策略[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2016,25(2):16-21.

Multi-threadparallelalgorithmfordynamicmultiplesensitiveattributesanonymousprotection

TANG Yinhu, ZHONG Cheng

(School of Computer and Electronic Information, Guangxi University, Nanning 530004, China)

A table of counterfeits is created, and the new added records are compared with the counterfeits to delete some counterfeits and reduce the total number of counterfeits in the anonymous dataset. The record buckets are split, and a multi-thread parallel algorithmc-m-inv for dynamic multiple sensitive attributes anonymous protection is designed. The experimental results show that the algorithmc-m-inv is efficient and the anonymous dataset generated by it has high serviceability.

data anonymization; multiple sensitive attribute;m-invariance; multi-thread parallel

2016-07-10

廣西自然科學(xué)基金資助項(xiàng)目(2014GXNSFAA118396;2011GXNSFA018152)

唐印滸(1988-),男,廣西河池人,廣西大學(xué)碩士生;

鐘 誠(chéng)(1964-),男,廣西桂平人,博士,廣西大學(xué)教授,碩士生導(dǎo)師.

10.3969/j.issn.1003-5060.2017.09.011

TP309.2

A

1003-5060(2017)09-1204-05

(責(zé)任編輯 閆杏麗)