動態多敏感屬性匿名保護多線程并行算法

唐印滸， 鐘 誠

(廣西大學 計算機與電子信息學院,廣西 南寧 530004)

動態多敏感屬性匿名保護多線程并行算法

唐印滸， 鐘 誠

(廣西大學 計算機與電子信息學院,廣西 南寧 530004)

文章通過建立偽記錄表,將新添加的記錄與偽記錄進行匹配,創造刪除偽記錄的機會,以達到減少匿名數據集中偽記錄的目的,將記錄桶進行分割,設計實現一種動態多敏感屬性匿名保護的多線程并行算法c-m-inv。實驗結果表明,算法c-m-inv高效、生成的多敏感屬性匿名數據集具有較高的可用性。

數據匿名;多敏感屬性;m-不變性;多線程并行

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

在m-不變性動態匿名算法的基礎上,本文通過建立偽記錄表,創造減少數據集中偽記錄數目的機會,以提高匿名數據集的數據可用性;將記錄桶分割處理,采用多線程并行技術以提高算法處理大數據集多敏感屬性匿名的效率。

1 算 法

1.1 算法優化策略

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

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

另一方面,在匿名算法的分割步中,桶與桶之間的分割沒有關聯、沒有數據共享或交換,因此對所有的桶進行分割,采用多線程技術實現匿名算法的并行化,以減少算法的運行時間,同時設計有效的數據結構保存數據,減少多敏感屬性數據的匹配時間,進一步提高算法的效率。

1.2 算法描述

算法1給出了基于m-不變性的動態多屬性數據匿名并行算法，即c-m-inv算法。

算法1c-m-inv算法

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

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

Begin

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

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

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

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

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

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

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

(8) fori=1 to num do in parallel

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

(9) 將匿名數據表T*(n)發布。

End

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

2 實 驗

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

實驗數據集是從網站http://ipums.org下載的真實數據集SAL,共包含有60萬條記錄,每條記錄包括Age、Gender、Education和Birthplace4個準標識符屬性,以及Occupation和Income 2個敏感屬性。

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

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

圖1 不同時刻c-m-inv算法和m-inv算法的偽記錄數

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

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

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

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

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

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

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

圖3 m值變化時c-m-inv算法和m-inv算法的平均運行時間

為了進一步檢驗本文c-m-inv算法的性能,c-m-inv算法和NCm-inv算法[4]在不同時刻的發布版本中添加的偽記錄數如圖4所示。

圖4 不同時刻c-m-inv算法和NC m-inv算法的偽記錄數

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

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

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

圖5的實驗結果表明，隨著m值的增大,算法需要加入更多的偽記錄來確保桶的平衡,因此c-m-inv算法和NCm-inv算法的平均偽記錄數均呈逐漸增加趨勢。另一方面,當m值較小時,NCm-inv算法的平均偽記錄數小于c-m-inv算法的平均偽記錄數;但當m值大于7時,c-m-inv算法的平均偽記錄數低于NCm-inv算法的平均偽記錄數。這是因為c-m-inv算法在平衡桶的過程中有機會能將之前添加的偽記錄刪除。

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

圖6 m值變化時c-m-inv算法和NC m-inv算法的平均運行時間

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

綜上所述,c-m-inv算法發布的匿名數據集的數據可用性較高,更適用于處理大數據集的動態多敏感屬性匿名保護。

3 結 論

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

[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:一種基于劃分的增量數據重發布敏感信息保護k-匿名算法[J].小型微型計算機系統,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].上海:復旦大學,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].南昌:南昌大學,2010.

[10] 武毅,王丹,蔣宗禮.基于事務型K-Anonymity 的動態集值屬性數據重發布隱私保護方法[J].計算機研究與發展,2013,50(增刊1):248-256.

[11] 左蘇楠,卞藝杰,吳慧.基于DMSA算法的多敏感屬性數據重發布隱私保護新策略[J].計算機系統應用,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

廣西自然科學基金資助項目(2014GXNSFAA118396;2011GXNSFA018152)

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

鐘 誠(1964-),男,廣西桂平人,博士,廣西大學教授,碩士生導師.

10.3969/j.issn.1003-5060.2017.09.011

TP309.2

A

1003-5060(2017)09-1204-05

(責任編輯 閆杏麗)