基于數(shù)據(jù)匿名化的隱私保護(hù)研究

孔志偉, 魏為民, 楊 朔, 酆 華, 趙 琰

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

隨著網(wǎng)絡(luò)的發(fā)展,各種數(shù)據(jù)的爆炸性增長給人們帶來了諸多信息,但與此同時也產(chǎn)生了許多安全隱患.其中,數(shù)據(jù)發(fā)布作為一項(xiàng)將數(shù)據(jù)庫中的數(shù)據(jù)直接展示給公眾的技術(shù),文獻(xiàn)[1]至文獻(xiàn)[3]指出,經(jīng)過簡單處理的源數(shù)據(jù)仍有可能暴露數(shù)據(jù)所有者的隱私,可能對個人或公司造成嚴(yán)重?fù)p失.例如企業(yè)公布的員工工資信息,即使將員工姓名刪除后發(fā)布,攻擊者通過對比數(shù)據(jù)等方式仍然可能獲得員工的姓名,從而得到隱私數(shù)據(jù).匿名數(shù)據(jù)發(fā)布就是針對這一問題而提出的解決方法之一.

匿名數(shù)據(jù)發(fā)布是一種基于限制發(fā)布的隱私保護(hù)技術(shù),其目的在于平衡數(shù)據(jù)的安全性和有效性之間的關(guān)系,使得發(fā)布的數(shù)據(jù)既不失可用性,又能保證隱私性.目前,匿名數(shù)據(jù)發(fā)布的主要研究方向分為數(shù)據(jù)匿名化模型和算法兩個方面.

1 數(shù)據(jù)匿名化模型

本文均以關(guān)系型數(shù)據(jù)表為例來介紹相關(guān)研究,在待發(fā)布數(shù)據(jù)表T中,每一行代表一個個體,每一列代表個體的屬性.如在常見的醫(yī)療數(shù)據(jù)表中,每一行代表一個患者,每一列代表患者的相關(guān)屬性,如表1所示.

表1 醫(yī)療數(shù)據(jù)

個體屬性大致分為3類:顯示標(biāo)識符(ExplicitIdentifier,ID),能唯一地確定一個個體的屬性,如姓名、身份證號;準(zhǔn)標(biāo)識符(Quasi-Identifier,QI),聯(lián)合起來能唯一確定一個個體的最小屬性集合,如郵編、生日、性別等聯(lián)合起來就可能是準(zhǔn)標(biāo)識符;敏感屬性(Sensitive Attributes,SA),包含隱私的數(shù)據(jù),但是無法唯一確定一個個體,如薪水、患病信息.

1.1 傳統(tǒng)的匿名模型

傳統(tǒng)的匿名模型一般指的是在匿名模型剛提出時的一種不針對特定環(huán)境、特定應(yīng)用的匿名模型.其特點(diǎn)是相對簡單,能夠在一般情況下保證數(shù)據(jù)的安全性和有效性.

SWEENEY L在2002年的一篇文章中提出了k-anonymity隱私保護(hù)模型[4].在數(shù)據(jù)表T中,每條記錄的準(zhǔn)標(biāo)識符至少與其他k-1條記錄相同,即k條記錄之間無法相互區(qū)別,則稱這k條記錄屬于一個匿名組.

表2是將表1進(jìn)行匿名化后的結(jié)果.由表2可以看出,任意一條記錄都無法與另一條區(qū)分,即滿足2-anonymity模型.

表2 醫(yī)療數(shù)據(jù)2-匿名

然而k-anonymity無法抵御Homo-geneity Attack(同質(zhì)攻擊)和Background Knowledge Attack(背景知識攻擊),這是由于該模型對敏感屬性沒有約束[5].(α,k)-anonymity模型[6]在此基礎(chǔ)上進(jìn)行了改進(jìn),在滿足k-anonymity的前提下保證了每個匿名組中出現(xiàn)的敏感屬性的百分比不高于α.l-diversity保證了每個匿名組的敏感屬性具有至少l個不同值,這樣可以使得攻擊者最多以1/l的概率確認(rèn)某個樣本的敏感信息.t-closeness模型[7]是在l-diversity的基礎(chǔ)上考慮了敏感屬性的分布問題,它要求所有匿名組的敏感屬性分布應(yīng)盡量接近該屬性的全局分布.

1.2 面向特定環(huán)境的匿名模型

面向特定環(huán)境的匿名模型的基本思想與傳統(tǒng)匿名模型無異,只是關(guān)注的重點(diǎn)不同.常見的有針對多敏感屬性、屬性權(quán)重以及個性化敏感屬性的匿名模型等.

1.2.1 針對多敏感屬性的匿名模型

一般的數(shù)據(jù)表結(jié)構(gòu)往往只有一個敏感屬性,因此傳統(tǒng)的匿名模型并沒有考慮多個敏感屬性的問題.然而在實(shí)際情況中卻常出現(xiàn)多敏感屬性的數(shù)據(jù)表.針對這種數(shù)據(jù)表,文獻(xiàn)[8]提出了一種基于多維桶分組技術(shù)的模型,該模型能夠在一定程度上保護(hù)多敏感屬性數(shù)據(jù)的安全發(fā)布.文獻(xiàn)[9]建立了差異化多敏感屬性lq-diversity模型,其定義如下:對于含q個敏感屬性的數(shù)據(jù)表T中的匿名組而言,如果任意匿名組中所有敏感屬性的每一維敏感屬性值都滿足l-diversity 性質(zhì),那么就稱該數(shù)據(jù)表滿足lq-diversity模型.

1.2.2 考慮屬性權(quán)重匿名模型

在發(fā)布的數(shù)據(jù)表中,準(zhǔn)標(biāo)識符中的不同屬性通常具有不同的重要程度,然而這一點(diǎn)在傳統(tǒng)的匿名模型中卻沒有體現(xiàn)出來.文獻(xiàn)[10]通過對屬性賦予不同的權(quán)重,優(yōu)化了在特定情況下不同屬性的泛化程度,從而在一定程度上解決了該問題.

1.2.3 個性化匿名模型

并非所有的敏感屬性都需要被保護(hù),同樣的,相同的敏感屬性在不同的數(shù)據(jù)擁有者看來其重要程度也不相同,如一個人對患感冒和絕癥的反應(yīng)截然不同;城市居民和農(nóng)村居民對工資的關(guān)注度不同.(α,l)多樣化k-匿名模型提出了敏感屬性分級的概念,實(shí)現(xiàn)了敏感屬性的個性化保護(hù)問題[11].

數(shù)據(jù)匿名化模型是實(shí)現(xiàn)數(shù)據(jù)匿名化的第一步,其數(shù)據(jù)樣式各異,發(fā)布環(huán)境也不盡相同.傳統(tǒng)的匿名模型易于實(shí)現(xiàn),但抗攻擊性較差;面向特定環(huán)境的匿名模型種類繁多,且具有較強(qiáng)的針對性,但過分依賴于特點(diǎn)數(shù)據(jù)表的特征,適用性較低.

2 數(shù)據(jù)匿名化算法

數(shù)據(jù)匿名化算法是實(shí)現(xiàn)數(shù)據(jù)匿名化模型的過程,目前提出的算法有泛化、抑制、聚類、微聚類、分解、置換[12],其中比較熱門的算法是泛化和聚類.

2.1 采用泛化的算法

泛化就是指將具體屬性值用不具體的值來表示,如將原本顯示為“回族”的屬性用“少數(shù)名族”來代替.通過泛化可以使發(fā)布的數(shù)據(jù)具有一定的保密性和真實(shí)性,很好地實(shí)現(xiàn)了隱私保護(hù)的效果.

早期的泛化算法有MinGen算法、Datafly算法以及μ-Argus算法[13],然而這些算法的效率并不高.廣泛使用的Incognito算法[14]通過首先構(gòu)建包含所有全域泛化方案的泛化圖,再自底而上對初始數(shù)據(jù)泛化,逐步裁剪優(yōu)化泛化圖,直到滿足k-anonymity原則.該算法的實(shí)現(xiàn)步驟如下.

輸入:原始表T,準(zhǔn)標(biāo)識符Q,一組多維表(一維是Q中的每個準(zhǔn)標(biāo)識符)

輸出:一組全域泛化k-anonymity的表T

C1={在Q中的屬性的域泛化層次結(jié)構(gòu)的節(jié)點(diǎn)}

E1={在Q中的屬性的域泛化層次結(jié)構(gòu)的邊界}

q=一個空q//q表示數(shù)列

fori=1 tondo

//Ci和Ei定義一個泛化圖

Si=Ci

將{r}插入到q中,將q按照權(quán)重排列 //r表示所有屬于Ci且不在屬于Ei邊界內(nèi)的節(jié)點(diǎn)

Whileq非空 do

n=從q中刪除第一個 //n表示節(jié)點(diǎn)

ifn沒有標(biāo)記 then

ifn是根 then

frequencySet= 相對于使用T的節(jié)點(diǎn)屬性的計(jì)算頻率集

else

frequencySet= 相對于使用父類頻率集的節(jié)點(diǎn)屬性的計(jì)算頻率集

else if

使用frequencySet相對于節(jié)點(diǎn)屬性檢查k-anonymity

if T相對于節(jié)點(diǎn)屬性是k-anonymity then

標(biāo)記所有n的引導(dǎo)泛化

else

從Si中刪除n

在q中插入n的引導(dǎo)泛化,使得q按權(quán)重排列

end if

end if

end while

Ci+1,Ei+1=泛化圖(Si,Ei)

end for

returnSn中屬性的投影到T和多維表中

泛化算法容易出現(xiàn)過度泛化現(xiàn)象,即泛化后屬性值的有效性很低,或變成無用屬性.為此,文獻(xiàn)[15]提出了泛化約束的匿名算法,可以在一定程度上優(yōu)化泛化操作.

2.2 采用聚類的算法

基于泛化的匿名算法有一個明顯的缺點(diǎn),那就是數(shù)據(jù)可用性較低,基于聚類的匿名算法可以在一定程度上解決這一問題.聚類是近年來提出的新技術(shù),核心思想是根據(jù)數(shù)據(jù)的特點(diǎn),將其分到不同的簇中[16].同一個簇中的數(shù)據(jù)相似,不同簇的數(shù)據(jù)有較大差距.

文獻(xiàn)[17]提出了兩種聚類算法,分別是r-gather和r-cellular.這兩種算法的相似之處是發(fā)布每個聚類的中心、半徑和相關(guān)屬性,區(qū)別是r-gather只發(fā)布一個最大的半徑,而r-cellular則發(fā)布每個聚類的半徑.FUNG B C M等人提出了一種針對聚類分析的啟發(fā)式數(shù)據(jù)隱藏發(fā)布方法[18].楊高明等人設(shè)計(jì)了聚類與概化/隱匿相結(jié)合的(α,k) -匿名聚類算法[19].其中,針對單敏感值表的具體算法步驟如下.

輸入:數(shù)據(jù)表TD,匿名約束k,指定的敏感值s及其頻率約束α

(1)C=φ;

(2) 計(jì)算數(shù)據(jù)表TD的相異矩陣Matrix(TD);

(3) 任選一點(diǎn)ti作為簇Ci的中心點(diǎn);

(4) 選擇距離ti最近的k-1 個數(shù)據(jù)點(diǎn)加入Ci,調(diào)整簇Ci的質(zhì)心;

(5)TD=TD-Ci;C=C+Ci;

(6) 在剩余數(shù)據(jù)集TD中選擇一點(diǎn)作為簇Cj的質(zhì)心;

(7) 若 |TD| >k,轉(zhuǎn)到步驟 4,否則放棄步驟(6);

(8) 對每個包含敏感值s的簇,計(jì)算s的頻度,并把簇按照s的頻度由大到小排序;

(9) 選擇s頻度最大的簇Ck,尋找簇Ck內(nèi)距離質(zhì)心最遠(yuǎn)且使簇Ck不滿足(α,k) -匿名約束的l(l

(10) 循環(huán)執(zhí)行步驟(9),直到所有簇內(nèi)的頻

度小于α;

(11) 將未分配的剩余簇加入距離他們較近的簇,且使加入后敏感值的頻率不大于α.

除此之外,姜火文等人考慮現(xiàn)有的匿名方案缺少分類考察準(zhǔn)標(biāo)識符屬性概化,提出了一種貪心聚類匿名方法[20].柴瑞敏等人針對k匿名算法的不足,提出了(k,L)匿名聚類算法,該算法在實(shí)現(xiàn)隱私保護(hù)的同時,減少了數(shù)據(jù)信息的損失,縮短了運(yùn)行時間[21].唐印滸等人提出了變長聚類V-MDAV算法,在選擇聚類種子時應(yīng)加入種子記錄的權(quán)重值,進(jìn)而提出了W-V-MDAV算法,又將W-V-MDAV算法與k-means算法結(jié)合,大大降低了處理大數(shù)據(jù)集時的時間開銷[22].

采用泛化和聚類的數(shù)據(jù)匿名化算法比較如表3所示.

表3 兩類數(shù)據(jù)匿名化算法比較

從表3可以看出,對于一般輕量級的數(shù)據(jù)匿名化而言,可采用泛化相關(guān)算法;對于想體現(xiàn)數(shù)據(jù)之間關(guān)聯(lián)性的數(shù)據(jù)匿名化而言,可使用聚類相關(guān)算法.

3 數(shù)據(jù)匿名化的發(fā)展趨勢

隨著越來越多的人對匿名數(shù)據(jù)發(fā)布技術(shù)的關(guān)注,該技術(shù)的研究熱度也在逐漸提高[26-27].就目前而言,該技術(shù)的發(fā)展趨勢如下.

(1) 基于動態(tài)數(shù)據(jù)的匿名發(fā)布 目前社會中存在的許多數(shù)據(jù),如個人醫(yī)療信息,都是隨著時間的變化而變動的.相關(guān)研究表明,傳統(tǒng)的應(yīng)用于靜態(tài)數(shù)據(jù)表的匿名算法在動態(tài)數(shù)據(jù)結(jié)構(gòu)中已然失效[28],因此亟需基于動態(tài)數(shù)據(jù)的匿名發(fā)布算法.

(2) 基于分布式數(shù)據(jù)的匿名發(fā)布 隨著大數(shù)據(jù)時代的到來,數(shù)據(jù)的存儲結(jié)構(gòu)也在發(fā)生著變化,從結(jié)構(gòu)化到非結(jié)構(gòu)化,從集中式到分布式.因此,傳統(tǒng)的匿名模型和算法在新的數(shù)據(jù)存儲結(jié)構(gòu)中可能不再適用[29-30].

(3) 基于位置服務(wù)的匿名發(fā)布 隨著車載網(wǎng)絡(luò)、車輛導(dǎo)航等一系列功能的實(shí)現(xiàn),基于位置服務(wù)的匿名發(fā)布功能變得越來越重要,如軌跡隱私保護(hù)[31-33].一方面,用戶要向服務(wù)商提供位置信息以便獲取需要的導(dǎo)航信息;另一方面,用戶不想暴露自身的位置隱私,以免遭到攻擊者的攻擊.

(4) 基于社會網(wǎng)絡(luò)的匿名發(fā)布 在社會網(wǎng)絡(luò)中,每個個體用節(jié)點(diǎn)表示,而節(jié)點(diǎn)與節(jié)點(diǎn)之間的任何關(guān)聯(lián)都可能稱為隱私,同時,節(jié)點(diǎn)自身的位置以及社會網(wǎng)絡(luò)圖的結(jié)構(gòu)都可能導(dǎo)致隱私的泄露[34-35].在如今網(wǎng)絡(luò)連接世界的社會中,人們在網(wǎng)絡(luò)上的相互聯(lián)系也是一個社會網(wǎng)絡(luò),從日常的購買記錄、瀏覽信息中不難分析出個人的隱私.因此,社會網(wǎng)絡(luò)中的數(shù)據(jù)發(fā)布也成為研究的熱點(diǎn).

4 結(jié) 語

近些年,基于匿名的數(shù)據(jù)發(fā)布技術(shù)已經(jīng)開始應(yīng)用于無線傳感器網(wǎng)絡(luò)等領(lǐng)域,是一項(xiàng)前景廣闊的技術(shù).本文從匿名數(shù)據(jù)發(fā)布模型和算法出發(fā),介紹了近些年的一些研究成果,客觀分析了已有的技術(shù),并對今后該領(lǐng)域的研究前景提出了展望.

[1] NARAYANAN A,SHMATIKOV V.Robust de-anonymization of large sparse datasets[C]//Proceedings of the 2008 IEEE Symposium on Security and Privacy,2008:111-125.

[2] SRIVATSA M,HICKS M.Deanonymizing mobility traces:using social network as a side-channel[C]//ACM Conference on Computer and Communications Security,2012:628-637.

[3] BLOND S L,ZHANG C,LEGOUT A,etal.I know where you are and what you are sharing:exploiting P2P communications to invade users′ privacy[C]//Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference,2011:45-60.

[4] SWEENEY L.K-anonymity:a model for protecting privacy[J].International Journal on Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):1-14.

[5] MACHANAVAJJHALA A,KIFER D,GEHRKE J.L-diversity:privacy beyondk-anonymity[J].Acm Transactions on Knowledge Discovery from Data,2006,1(1):3.

[6] RAYMOND CHI-WING W,LI J,ADA WAI-CHEE F,etal.(α,k) -Anonymity:an enhanced k-anonymity model for privacy-preserving data publishing[C]//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2006:754-759.

[7] LI N,LI T.T-closeness:privacy beyondk-anonymity andl-diversity[C]//Proceeding s of the 23rd International Conference on Data Engineering,2007:106-115.

[8] 楊曉春,王雅哲,王斌,等.數(shù)據(jù)發(fā)布中面向多敏感屬性的隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2008(4):574-587.

[9] 左蘇楠,卞藝杰,吳慧.差異化多敏感屬性Lq-Diversity模型和算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2016,25(2):173-179.

[10] 徐勇,秦小麟,楊一濤,等.一種考慮屬性權(quán)重的隱私保護(hù)數(shù)據(jù)發(fā)布方法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(5):913-924.

[11] 闞瑩瑩,曹天杰.一種增強(qiáng)的隱私保護(hù)K-匿名模型——(α,L)多樣化K-匿名[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(21):148-151.

[12] 劉湘雯,王良民.數(shù)據(jù)發(fā)布匿名技術(shù)進(jìn)展[J].江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,37(5):562-571.

[13] SWEENEY L.Achievingk-anonymity privacy protection using generalization and suppression[J].International Journal on Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):571-588.

[14] LEFEVRE K,DEWITT D J,RAMAKRISHNAN R.Incognito:efficient full-domainK-anonymity[C]//ACM SIGMOD International Conference on Management of Data,2005:49-60.

[15] 朱衛(wèi)紅,潘巨龍,時磊.一種泛化約束的(K,L)-匿名算法[J].中國計(jì)量學(xué)院學(xué)報(bào),2016,27(1):80-85.

[16] 倪巍偉,陳耿,崇志宏,等.面向聚類的數(shù)據(jù)隱藏發(fā)布研究[J].計(jì)算機(jī)研究與發(fā)展,2012,49(5):1 095-1 104.

[17] AGGARWAL G,FEDER T,KENTHAPADI K,etal.Achieving anonymity via clustering[C]//ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems,2006:153-162.

[18] FUNG B C M,WANG K,WANG L,etal.A framework for privacy-preserving cluster analysis[C]//IEEE International Conference on Intelligence and Security Informatics,2008:46-51.

[19] 楊高明,楊靜,張健沛.聚類的(α,k)-匿名數(shù)據(jù)發(fā)布[J].電子學(xué)報(bào),2011,39(8):1 941-1 946.

[20] 姜火文,曾國蓀,馬海英.面向表數(shù)據(jù)發(fā)布隱私保護(hù)的貪心聚類匿名方法[J].軟件學(xué)報(bào),2017,28(2):341-351.

[21] 柴瑞敏,馮慧慧.基于聚類的高效(K,L)-匿名隱私保護(hù)[J].計(jì)算機(jī)工程,2015,41(1):139-142.

[22] 唐印滸,鐘誠.基于變長聚類的多敏感屬性概率k-匿名算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014(8):2 660-2 665.

[23] 陳偉鶴,丁蕾蕾.匿名最短路徑的top-k路徑貪心泛化算法[J].計(jì)算機(jī)工程,2016,42(1):116-120.

[24] 吳響,臧昊,俞嘯.基于抽樣路徑的K-匿名隱私保護(hù)算法[J].電子技術(shù)應(yīng)用,2016,42(12):115-118.

[25] 王智慧,許儉,汪衛(wèi),等.一種基于聚類的數(shù)據(jù)匿名方法[J].軟件學(xué)報(bào),2010,21(4):680-693.

[26] 周水庚,李豐,陶宇飛,等.面向數(shù)據(jù)庫應(yīng)用的隱私保護(hù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(5):847-861.

[27] 劉喻,呂大鵬,馮建華,等.數(shù)據(jù)發(fā)布中的匿名化技術(shù)研究綜述[J].計(jì)算機(jī)應(yīng)用,2007,27(10):2 361-2 364.

[28] 張飛.基于動態(tài)數(shù)據(jù)集的匿名化隱私保護(hù)技術(shù)研究[D].重慶:重慶交通大學(xué),2013.

[29] 方煒煒,周長勝,賈艷萍,等.基于SMC的分布式隱私保護(hù)數(shù)據(jù)發(fā)布研究[J].系統(tǒng)工程與電子技術(shù),2012,34(11):2 390-2 395.

[30] 宋玉.基于分布式數(shù)據(jù)庫數(shù)據(jù)隱私安全的K-匿名模型研究和改進(jìn)[D].昆明:云南大學(xué),2011.

[31] 霍崢,孟小峰.軌跡隱私保護(hù)技術(shù)研究[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1 820-1 830.

[32] 潘曉,肖珍,孟小峰.位置隱私研究綜述[J].計(jì)算機(jī)科學(xué)與探索,2007,1(3):268-281.

[33] 趙婧,張淵,李興華,等.基于軌跡頻率抑制的軌跡隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(10):2 096-2 106.

[34] 劉向宇,王斌,楊曉春.社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護(hù)技術(shù)綜述[J].軟件學(xué)報(bào),2014,25(3):576-590.

[35] 羅亦軍,劉強(qiáng),王宇.社會網(wǎng)絡(luò)的隱私保護(hù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2010,27(10):3 601-3 604.