一種個性化(p,k)匿名隱私保護算法

,

(西北師范大學 計算機科學與工程學院,蘭州 730070)

0 概述

在信息發(fā)達的當代,人類大量個人信息被政府部門、商業(yè)機構(gòu)等存儲、發(fā)布,這極大地激發(fā)了各部門從海量數(shù)據(jù)中挖掘有用信息的需求[1]。數(shù)據(jù)挖掘在用于公開分析大量的私人信息時,如在醫(yī)療記錄、人口普查中,若公開某位病人的患病情況,或者公開個人的婚姻狀況等這些敏感信息,將會對個人隱私構(gòu)成威脅。因此,個體隱私信息的安全性問題在數(shù)據(jù)挖掘的研究中顯得尤為重要。個體隱私信息的保護技術(shù)主要分為3類[2]:數(shù)據(jù)加密,數(shù)據(jù)失真,數(shù)據(jù)匿名化。其中,數(shù)據(jù)加密的安全性最高,對信息的有用性破壞較大,數(shù)據(jù)失真在給數(shù)據(jù)添加噪聲的同時仍需保持數(shù)據(jù)基本性質(zhì)不變,降低了可用信息的數(shù)量,因此,通常采用數(shù)據(jù)匿名技術(shù)實現(xiàn)隱私保護,既保證數(shù)據(jù)的有用性,同時又能兼顧數(shù)據(jù)的隱私性。

文獻[3]建立了k匿名模型,要求發(fā)布數(shù)據(jù)中的每個元組至少有(k-1)個與其相同的元組。k匿名模型能有效地解決標志泄露問題,但對于敏感屬性泄露問題并沒有相應的保護機制[4],無法達到保護隱私的目的。之后文獻[5-6]建立了p-sensitive k匿名模型,要求在滿足k匿名的同時,在每個等價類中敏感屬性至少有p個不同的值,這對敏感屬性起到一定的保護作用。

然而在日常生活中,相同的敏感屬性針對不同的個體敏感程度也不盡相同,需要針對個體的差異對敏感屬性實施個性化保護[7]。文獻[8]提出自頂向下個性化泛化回溯,動態(tài)構(gòu)建泛化樹,有效抵制了同質(zhì)攻擊和背景知識攻擊。文獻[9-10]皆是提出一種基于k匿名的個性化匿名算法,其中文獻[9]算法增加匿名群記憶模塊,以此加快匿名的速度,文獻[10]根據(jù)個人隱私自治原則提出基于局部編碼和敏感屬性泛化的個性化k匿名算法。文獻[11]建立基于(α,k)個性化匿名模型,通過設(shè)置等價類中敏感值出現(xiàn)的頻率來實現(xiàn)個性化保護。由此可見,針對個體差異的個性化保護越來越受到關(guān)注和重視。通常敏感屬性的保護方式分為2種:一種是對不同的敏感屬性設(shè)置不同的閾值,敏感程度較高的閾值較小;另一種保護方式是對敏感屬性泛化,用精度較低的敏感屬性值取代原值。文獻[12-13]運用前者提出敏感屬性劃分泛化的策略,對不同的敏感屬性設(shè)置不同的級別。之后,文獻[14-15]提出基于L多樣性的個性化匿名模型,同樣提到設(shè)置參數(shù)?實現(xiàn)分級別保護。文獻[16]方法在p-sensitive k匿名模型的基礎(chǔ)下為敏感屬性設(shè)置不同的閾值,實現(xiàn)個性化保護。

本文基于p-sensitive k匿名模型提出針對敏感屬性的個性化隱私保護算法,通過建立敏感屬性泛化樹,根據(jù)個體間敏感程度的差異將敏感屬性泛化到不同的層次,降低敏感屬性的精度后再發(fā)布數(shù)據(jù),以達到對敏感屬性進行個性化隱私保護的目的。

1 相關(guān)概念

1.1 表屬性劃分

可將數(shù)據(jù)表的屬性劃分為3個部分:標識符屬性A,準標識符屬性QI和敏感屬性S,其中:標識符屬性是能唯一確定某個個體的屬性,如身份證號;準標識符屬性是指通過其與外部數(shù)據(jù)表某些屬性進行鏈接以標識個體身份的屬性,例如性別、年齡、郵編等;敏感屬性是指包含個體隱私信息的屬性,例如疾病、婚姻狀況等。

表1為某醫(yī)院電子病歷,其中:“Name”為標識符屬性,對表操作時應隱匿標識符屬性避免嚴重的身份泄露[17];“Sex”“Age”“Zip code”是準標識符屬性,對這些屬性通過泛化可以得到匿名表;“Health condition”為敏感屬性。

表1 原始數(shù)據(jù)

1.2 k匿名模型

k匿名算法[3]要求發(fā)布數(shù)據(jù)中每個等價類至少有k個不可區(qū)分的個體,使攻擊者判別出所要攻擊對象的概率為1/k,從而保護了個體隱私信息。k匿名算法可以有效防止鏈接攻擊,但不能防止同質(zhì)性攻擊。

定義1(等價類) 對于數(shù)據(jù)表T{A1,A2,…,An}(n為屬性的個數(shù)),一個等價類是指在子集{A1,A2,…,Aj}(j為子集屬性的個數(shù))上取值相同的元組的集合[17]。

定義2(k匿名) 給定數(shù)據(jù)表T{A1,A2,…,An},QI是T的準標識符,T[QI]為T在QI上的投影(元組可重復),當且僅當在T[QI]中出現(xiàn)的每組值至少要在T[QI]中出現(xiàn)k次,則T滿足k匿名,記為T’[18]。

由此可知,一個數(shù)據(jù)表滿足k匿名,當且僅當在準標識符上的任意一個等價類的大小至少為k。

表2為k=2時的匿名發(fā)布表,將表1中標識標識符屬性姓名隱匿,避免個人身份泄露,對準標識符“Sex”“Age”“Zip code”通過泛化操作輸出精度較低的值,令“Health condition”為敏感屬性。

表2 2匿名數(shù)據(jù)

若攻擊者事先已知Alice的年齡、郵編以及性別可推斷出Alice在匿名表的第2個等價類中,攻擊者可以確定Alice一定患有HIV,泄露了個人隱私。為解決該問題,使用p-sensitive k匿名算法,在該算法中要求每個等價類中至少有p個不同的敏感屬性。

1.3 p-senstitive k匿名模型

定義3((p,k)匿名) 給定數(shù)據(jù)集T’滿足k匿名,對于每個等價類中至少有p個不相同的敏感屬性值且p≤k[16]。

運用(p,k)匿名算法(p=2,k=3)得到表3。其中,類標號相同的元組屬于一個等價類,由此可知,前4條元組是一個等價類,第5條～第7條元組是一個等價類,第8條～第10條元組是一個等價類。在3個等價類中,任意一個等價類中的敏感屬性取值至少為p=2。

表3 (3,3)匿名數(shù)據(jù)

2 個性化p-sensitive k匿名相關(guān)定義

k匿名模型能有效防止鏈接攻擊,但不能解決敏感屬性的保護問題,p-sensitive k匿名要求在每個等價類中至少有p個不相同的敏感屬性值,雖在一定程度上保護了敏感屬性,但是未考慮敏感屬性的敏感程度問題。表2中敏感屬性取值為HIV,與Cancer與Flu相比,前兩者更不想被他人知道,因此,對敏感屬性個性化保護顯得尤為重要,本文給出敏感屬性泛化樹的概念,實現(xiàn)對敏感屬性的個性化保護。

2.1 敏感屬性的敏感級別

本文提出用戶評分機制劃分敏感屬性,保證敏感屬性的劃分更貼合實際個體的敏感信息,針對個體敏感信息的敏感程度實施分級保護。

定義4(敏感度評分) 設(shè)滿分為Y,化為若干個分數(shù)區(qū)間Y{Y1,Y2,…,Yn},數(shù)據(jù)集為T,敏感屬性集為S{S1,S2,…,Si,…,Sn},敏感屬性取值個數(shù)為n。用戶針對個人對敏感屬性的敏感程度評分,分數(shù)較低的敏感屬性,敏感度也較低。將評分對應于相應的分數(shù)區(qū)間Yi(1≤i≤n)中并用yi標記敏感屬性的分數(shù)。

圖1為某醫(yī)院用戶調(diào)查結(jié)果,橫坐標為敏感屬性疾病S的取值,分別用1～6表示Flu、Pneumonia、Fracture、Asthma、HIV、Cancer。縱坐標表示用戶評分,評分系統(tǒng)滿分為90分,劃分為3個區(qū)間:[0,30]表示低敏感度;[30,60]表示中等敏感度;[60,90]表示高敏感度。根據(jù)用戶評分情況,去除離群點,將6個敏感屬性對應至相應的分數(shù)空間。

圖1 敏感屬性評分結(jié)果

根據(jù)圖1的結(jié)果滿分90分,根據(jù)用戶評分結(jié)果將疾病敏感屬性的敏感程度劃分為3級,去掉個別離群點最終得到如表4所示的敏感屬性登記表。

表4 用戶評定敏感屬性泛化數(shù)據(jù)表

2.2 敏感屬性泛化樹

根據(jù)用戶評分將敏感屬性劃分為不同泛化,泛化較高的敏感屬性,敏感信息具有較高隱私度,需要保護的程度也較高。構(gòu)建一棵泛化樹Q,Q的高度至少為敏感等級的個數(shù),將敏感屬性的所有取值存放在樹的葉子結(jié)點中,按照敏感屬性的敏感程度對敏感屬性向上泛化。其中,規(guī)定最低敏感泛化的敏感屬性不進行泛化,直接發(fā)布數(shù)據(jù);其他敏感泛化的敏感屬性按照其敏感度依次向上泛化,找到敏感屬性的祖先結(jié)點,用祖先結(jié)點的值代替敏感屬性值發(fā)布。如圖2所示,敏感屬性為疾病,取值為{感冒,哮喘,肺炎,骨折,燒傷}。若用戶認為哮喘為中級敏感度,對敏感屬性進行泛化,找到哮喘的父節(jié)點呼吸內(nèi)科發(fā)布數(shù)據(jù);若用戶認為肺炎具有最高敏感度,發(fā)布數(shù)據(jù)時用根節(jié)點疾病代替肺炎。

圖2 敏感泛化樹

2.3 精度度量

本文參考文獻[19]的層次泛化的精度測量以及泛化區(qū)間的區(qū)間精度測量,無論是準標識符還是敏感屬性通過泛化操作來實現(xiàn)匿名,必然存在信息損失,因此,給出以下相關(guān)定義。

定義5(分類型屬性精度測量) 設(shè)任意不同類型的屬性泛化有相同的信息損失量,若泛化樹T所有的葉子節(jié)點記為M,某一個節(jié)點P所有的子樹的個數(shù)記為MP,則某一屬性泛化的信息損失量為:

(MP-1)/(M-1)

(1)

如圖2所示,共有葉子節(jié)點5個,則M=5,由感冒泛化至呼吸內(nèi)科,呼吸內(nèi)科所有的子樹個數(shù)為3,即MP=3,因此,由感冒泛化至呼吸內(nèi)科的信息損失量為1/2。

定義6(數(shù)值型屬性精度測量) 若某一數(shù)值被泛化至某一區(qū)間i中,則將這個區(qū)間的左端點標記為Li,右端點標記為Ui;該數(shù)值屬性的所有區(qū)間中,最小左端點標記為L,最大右端點標記為U,則某一屬性泛化至某一區(qū)間的信息損失量為:

(Ui-Li)/(U-L)

(2)

例如,屬性年齡共分為3個區(qū)間,分別為[0,30]、[30,60]、[60,90],若某條記錄的年齡屬性為35,則泛化至第1個區(qū)間,由此可知:L2=30,U2=60,U=90,L=0,則該記錄年齡屬性泛化后信息損失為1/3。

3 個性化p-sensitive k匿名模型

個性化p-sensitive k匿名算法是針對敏感屬性,在原有的p-sensitive k匿名的基礎(chǔ)上,對敏感屬性增加個性化保護的算法。首先用戶針對個人的敏感屬性對敏感度評分,用散列圖表示所有用戶評分結(jié)果,刪除個別離群點,得到較可靠的敏感屬性泛化劃分結(jié)果。再根據(jù)敏感屬性的泛化度構(gòu)建對應的敏感屬性泛化樹。敏感度較高的屬性值泛化的高度也較高,規(guī)定最低敏感度的敏感屬性不進行泛化,直接發(fā)布數(shù)據(jù)。算法具體描述如下:

輸入用戶評分區(qū)間Y,待發(fā)布的(p,k)數(shù)據(jù)集T

輸出個性化敏感屬性匿名集T’

1.users choose merit internal

2.for data table T

3.use (p,k)anonymity

4.getT’;

5.Built a sensitive hierarchy tree A

6.for i to k{

7.If Si∈lowest sensitive degree

8.PublishT’;

9.Else Si∈other sensitive degree

10.According toA find ancestor node of Si

11.Then use ancestor node replace Si}

12.Publish T’

算法的第1步用戶選擇敏感屬性的評分區(qū)間確定敏感屬性的敏感泛化,第2步～第4步利用(p,k)匿名算法對數(shù)據(jù)集T匿名后,第5步～第11步利用敏感屬性泛化樹泛化每個等價類中的敏感屬性,實現(xiàn)敏感屬性個性化保護;最后發(fā)布匿名表T’,若泛化敏感屬性后不滿足(p,k)匿名要求,則重新劃分等價類再泛化敏感屬性發(fā)布。

4 實驗結(jié)果與分析

實驗環(huán)境:Intel Pentium 2.00 GHz CPU,2.0 GB RAM,Windows 7 旗艦版操作系統(tǒng),MATLAB 7.1。編程語言為Java和MATLAB混合編程。實驗所選用的數(shù)據(jù)集是Adult標準數(shù)據(jù)集,此數(shù)據(jù)集共有48 842條數(shù)據(jù)其中包括部分美國人口普查數(shù)據(jù),去除空值后的數(shù)據(jù)有45 220條可用數(shù)據(jù)。本文選取Age、Salary、Education、Relationship、Education-num、Race、Native-country、Workclass作為準標識符,選取Marital-status作為敏感屬性,取值分別為{Never-married,Married-CIV-spouse,Divorced,Married-spouse-absent,Separated,Widowed,Married-AF-spouse}。實驗數(shù)據(jù)分組如表5所示,具體描述如表6所示。重復進行實驗10次,取相應實驗結(jié)果的平均值作為對比分析數(shù)據(jù)。

表5 實驗數(shù)據(jù)分組

表6 Adult 數(shù)據(jù)集描述

實驗使用以下模型進行比較:

1)k匿名模型:通過泛化構(gòu)造匿名表,敏感屬性不做處理;

2)個性化(α,k)匿名模型:通過設(shè)置閾值α實現(xiàn)對敏感屬性的個性化匿名保護;

3)個性化(p,k)匿名模型:利用敏感屬性泛化樹實現(xiàn)對敏感屬性的個性化匿名保護。

實驗從執(zhí)行時間和信息損失2個角度分析個性化(p,k)匿名模型、k匿名和個性化(α,k)匿名模型的性能。

4.1 執(zhí)行時間分析

圖3為準標識符個數(shù)為8個,數(shù)據(jù)集的大小為45 220,k分別取2、4、6和8時3種匿名模型的執(zhí)行時間比較。由圖3可知:3種模型都隨著k值的增長,執(zhí)行時間逐漸增大,由于個性化(α,k)匿名采用自底向上的聚類策略,當k逐漸增加時,聚類次數(shù)也逐漸變多,因此耗時比k匿名模型要多,而個性化(p,k)匿名算法則首先有用戶輸入評分區(qū)間,之后對敏感屬性泛化實現(xiàn)個性化匿名,因此執(zhí)行時間比較長,隨著k的增長,p越容易達到,則斜率越平緩。

圖3 執(zhí)行時間對比1

圖4是k取6時,改變元組個數(shù)實現(xiàn)3種匿名模型的執(zhí)行時間對比。由圖4可知:3種模型都隨著添加元組個數(shù)的增加執(zhí)行時間變大,因為隨著數(shù)據(jù)增多,需要匿名的元組也增多,因此執(zhí)行時間增大。由于添加元組數(shù)增多,個性化(p,k)匿名的k、p值并不改變,因此隨著元組增多,越容易滿足p值的限制,因此與個性化(p,k)匿名有相似的執(zhí)行時間,個性化(p,k)匿名會得到更好的隱私保護效果。

圖4 執(zhí)行時間對比2

4.2 精度對比

信息損失量用式(1)、式(2)來計算,圖5為準標識符為6個,元組數(shù)為45 200,k取6時,3種匿名模型得到的信息損失量比較。由圖5可知:3種匿名算法的精度都會隨著準標識符個數(shù)的增加而降低。因為隨著準標識符個數(shù)的增加,對元組匿名操作就會越復雜,損失的信息量也就越多。k匿名算法的信息損失量最少是因為它僅需要對準標識符操作,不考慮敏感屬性,而個性化(α,k)匿名模型比個性化(p,k)匿名模型的信息損失量多是因為在控制敏感屬性個性化時采用的方式不同。個性化(α,k)匿名模型采用設(shè)置閾值α,而個性化(p,k)匿名算法采用對敏感屬性泛化的方法,因此精度損失比個性化(α,k)匿名模型多。

圖5 信息損失量對比1

圖6是在k取不同值時的精度比較,可以看出3種模型都隨著k值的增加,精度損失增加,等價類中的元組個數(shù)增加,泛化準標識符個數(shù)增加,而個性化(p,k)匿名模型取固定的p值,在元組個數(shù)較少時曲線斜率較陡,隨著k值的增加,曲線逐漸變得平緩。

圖6 信息損失量對比2

5 結(jié)束語

本文提出一種基于(p,k)匿名模型的敏感屬性個性化匿名算法。根據(jù)多數(shù)用戶針對敏感屬性的評分結(jié)果建立敏感屬性等級,將少數(shù)與大眾評分結(jié)果存在差異的用戶視為離群點遺棄,之后利用敏感屬性泛化樹泛化敏感屬性,對不滿足(p,k)匿名條件的元組重新劃分等價類。實驗結(jié)果表明,通過損失部分敏感屬性的精度實現(xiàn)個性化保護的方法有效。后續(xù)工作將主要針對個性化匿名模型進行更合理的設(shè)計,并考慮將本文算法與實際問題相結(jié)合。

[1] AGGARWAL C C,YU P S.Privacy-preserving Data Mining:Models and Algorithms[J].Advances in Database Systems,2008,35:11-52.

[2] PATEL B H,SHAH A N.Overview of Privacy Preserving Techniques and Data Accuracy[J].International Journal of Advance Research in Computer Science and Management Studies,2015,3(1):135-140.

[3] LATANYA S.k-Anonymity:A Model for Protecting Privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5):557-570.

[4] JOSHI P,WADE S A,WADKAR C G,et al.The k-Anonymity Approach for Privacy Preservation Against Aggregate Knowledge Attacks[J].The International Journal of Science and Technoledge,2015,3(1):50.

[5] TRUTA T M,VINAY B.Privacy Protection:p-Sensitive k-Anonymity Property[C]//Proceedings of the 22nd International Conference on Data Engineering Workshops.Washington D.C.,USA:IEEE Press,2006:94.

[6] YUAN Yongbin,YANG Jing,LAN Sheng,et al.p-Sensitive k-Anonymity Based on Nearest Neighborhood Search in Privacy Presering[J].Journal of Information and Computational Science,2012,9(5):1385-1393.

[7] 康海燕,楊孔雨,陳建明.基于K-匿名的個性化隱私保護方法研究[J].山東大學學報(理學版),2014,49(9):142-149.

[8] 戢渼鈞.關(guān)于個性化信息服務的隱私保護[J].圖書情報工作,2006,50(2):49-51.

[9] 何 康,吳 蒙.一種個性化的k-匿名位置隱私保護算法[J].南京郵電大學學報(自然科學版),2012,32(6):69-73.

[10] 劉 明,葉曉俊.個性化K-匿名模型[J].計算機工程與設(shè)計,2008,29(2):282-286.

[11] 韓建民,于 娟,虞慧群,等.面向敏感值的個性化隱私保護[J].電子學報,2010,38(7):1723-1728.

[12] LIU Yinghua,YANG Bingru,LI Guangyuan.A Personalized Privacy Preserving Parallel (alpha,k)-anonymity Model[J].International Journal of Advancements in Computing Technology,2012,4(5):265-271.

[13] HUANG Xuezhen,LIU Jiqiang,HAN Zhen,et al.Privacy Beyond Sensitive Values[J].Science China Information Sciences,2015,58(7):1-15.

[14] 王 波,楊 靜.一種基于逆聚類的個性化隱私匿名方法[J].電子學報,2012,40(5):883-890.

[15] 傅鶴崗,曾 凱.多維敏感k-匿名隱私保護模型[J].計算機工程,2012,38(3):145-147.

[16] 王 茜,曾子平.(p,a)-sensitive k-匿名隱私保護模型[J].計算機應用研究,2009,26(6):2177-2179.

[17] TONG Yunhai,TAO Youdong,TANG Shiwei,et al.Identity-reserved Anonymity in Privacy Preserving Data Publishing[J].Journal of Software,2010,21(4):771-781.

[18] 夏贊珠,韓建民,于 娟,等.用于實現(xiàn)(k,e)-匿名模型的MDAV算法[J].計算機工程,2010,36(15):159-161.

[19] IYENGAR V S.Transforming Data to Satisfy Privacy Constraints[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery.New York,USA:ACM Press,2002:279-288.