相異敏感度下最小信息損失增量優(yōu)先的隱私保護(hù)方法

謝靜，張健沛，楊靜，張冰

?

相異敏感度下最小信息損失增量優(yōu)先的隱私保護(hù)方法

謝靜1, 2，張健沛2，楊靜2，張冰3

(1. 武漢紡織大學(xué) 管理學(xué)院，湖北 武漢，430200；2. 哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱，150001；3. 哈爾濱理工大學(xué) 軟件學(xué)院，黑龍江 哈爾濱，150080)

針對不同敏感值的隱私保護(hù)程度需求，提出一種敏感度計(jì)算方法，將敏感值進(jìn)行等級劃分，再對不同等級的敏感值設(shè)定不同的敏感度；給出一種隱私保護(hù)原則(,)- sensitivity來控制等價類中敏感度的分布情況，使得等價類中高敏感度的元組不會過多而造成隱私泄露；提出一種最小信息損失增量優(yōu)先算法(minimum information loss increment first，MILIF)來實(shí)現(xiàn)隱私保護(hù)的要求。研究結(jié)果表明：所提出的方法在降低少量時間和保持?jǐn)?shù)據(jù)效用的前提下，充分提高了數(shù)據(jù)表抵御敏感性攻擊的能力。

隱私保護(hù)；敏感度；鄰域；信息損失增量

在信息化時代，各個領(lǐng)域需要收集和分析的個人數(shù)據(jù)正以驚人的速度增長，這些原始形式的數(shù)據(jù)是公共資源分配、醫(yī)學(xué)探索、趨勢預(yù)測等研究的寶貴來源。例如，醫(yī)院可能發(fā)布病人的診斷記錄以用于分析多種疾病的特征或者生成統(tǒng)計(jì)報告。然而，在進(jìn)行數(shù)據(jù)研究的同時，往往會造成個人敏感信息泄露，因此，需要提出有效的隱私保護(hù)技術(shù)以保證個人數(shù)據(jù)在被使用的同時不泄露機(jī)密信息。數(shù)據(jù)發(fā)布中隱私保護(hù)的主要目的就是將原始數(shù)據(jù)進(jìn)行處理，然后以新的形式發(fā)布數(shù)據(jù)以避免隱私泄露和抵御多種攻擊[1]。對于個人數(shù)據(jù)，將某些可以唯一確定個體身份的屬性如姓名、身份證號等稱為身份標(biāo)識符屬性(identifier)；然后，通過組合可以確定某個個體的屬性稱為準(zhǔn)標(biāo)示符屬性(quasi-identifiers, QI)，如年齡、性別和郵編等；包含個體敏感信息的屬性稱為敏感屬性(sensitive attributes, SA)，如疾病、薪資等。近年來，數(shù)據(jù)發(fā)布中的隱私保護(hù)技術(shù)受到越來越多的關(guān)注?，F(xiàn)有的研究成果中大部分是-匿名[2?5]或者-多樣性[6?8]模型的擴(kuò)展，其主要目的是為了控制等價類中元組數(shù)和敏感值的多樣性。此外，-closeness模型[9?11]的研究也是一個熱點(diǎn)方向，其主要思想是將數(shù)據(jù)表與等價類間敏感值的分布距離控制在一定閾值內(nèi)。上述研究模型大多沒有對敏感屬性值的敏感程度進(jìn)行約束，而在實(shí)際生活中，不同敏感屬性值的隱私保護(hù)需求的程度存在很大的差異。例如，假設(shè)待發(fā)布數(shù)據(jù)表的敏感屬性為疾病，對于感冒、胃疼等疾病，患者并不介意其他人知道自己患此類疾病，因此，此類疾病的隱私保護(hù)程度要求較低；而對于肺結(jié)核、癌癥等疾病，患者不希望他人知道自己患此類疾病，擔(dān)心引起別人的歧視，因而，此類疾病的隱私保護(hù)程度要求較高。在生成等價類的過程中，如果不考慮這些敏感值自身的敏感程度，可能會出現(xiàn)某個等價類中的敏感值均為高度敏感值的情況。以-多樣性為例，令=3，即等價類中至少包含3個敏感值不相同的元組。若一個等價類中敏感值的取值為{肺癌，腸癌，胃癌}，此等價類中滿足3-多樣性。然而，肺癌、腸癌、胃癌均為敏感程度較高的疾病，攻擊者只要知道某個體屬于該等價類，即使不能推理出該個體敏感值的具體取值，攻擊者也能得出該個體患有癌癥的結(jié)論，造成了個體的隱私泄露。由此可見，如果對于敏感屬性值不考慮它們自身的敏感程度，可能會導(dǎo)致高敏感度的屬性得不到充分保護(hù)。在數(shù)據(jù)發(fā)布中的隱私保護(hù)研究領(lǐng)域，Sweeney等[2]首先提出了-匿名隱私模型，要求每個等價類至少包含個元組，并且該個元組的QI值相等。-匿名使得即使攻擊者知道某個體的QI值也不能推導(dǎo)出該個體的敏感信息(因?yàn)樵搨€體記錄所在等價類中的QI值相等)。然而，當(dāng)個QI值不可區(qū)分的元組恰好具有相同的敏感值時，該等價類中個體的敏感值已經(jīng)被披露。為此，研究者們提出了2個改進(jìn)的模型——(,)-匿名[3]和-多樣性[6]來解決-匿名存在的問題。(,)-匿名要求每個等價類中不僅包含個QI值上不可區(qū)分的元組，并且等價類中每個敏感值出現(xiàn)的頻率不大于閾值，使得等價類中敏感值分布不會過于傾斜。-多樣性要求每個等價類中不僅滿足-匿名的要求，并且等價類中不同敏感值的數(shù)量不少于個，以此來保證敏感值的多樣性。上述模型中都是考慮敏感值自身的取值，通過各種策略來增加敏感值的多樣性，沒有考慮敏感值的敏感度。Sun等[7]提出一種擴(kuò)展的(,)-多樣性模型，該模型對敏感值進(jìn)行等級劃分，然后對不同等級的敏感值設(shè)置權(quán)重，它要求每個等價類中敏感值的權(quán)重之和不低于閾值。文獻(xiàn)[7]中對敏感值設(shè)置權(quán)重其實(shí)就是敏感度的一種體現(xiàn)。但是(,)-多樣性模型仍存在隱私泄露的風(fēng)險。文獻(xiàn)[12]也針對敏感值自身的敏感性進(jìn)行了研究，它根據(jù)隱私保護(hù)的需求程度，將各敏感屬性值劃分為高、中、低3個等級類，通過隱私保護(hù)度參數(shù)靈活控制泄露風(fēng)險，提出了(,)-分級匿名模型，該模型要求等價類中每個敏感值出現(xiàn)的頻率不大于閾值雖然該模型可以控制等價類中敏感值出現(xiàn)的概率，但是也可能出現(xiàn)等價類中的敏感值均為高敏感度的情況，會產(chǎn)生隱私泄露。文獻(xiàn) [7，12]采用預(yù)定義的方式來設(shè)置敏感屬性等級。由領(lǐng)域?qū)＜一蛘邤?shù)據(jù)擁有者來確定敏感屬性值的敏感程度，此方法雖然可以反映出一些實(shí)際的需求，但是存在一定的主觀性。本文作者針對敏感值的敏感度不同，提出一種敏感度的計(jì)算方法，將敏感值按照其自身的敏感性進(jìn)行等級劃分，并按照敏感等級設(shè)定不同的敏感度；然后提出一種(,)- sensitivity原則來控制等價類中敏感度的分布情況；最后，提出一種最小信息損失增量優(yōu)先算法來實(shí)現(xiàn)提出的(,)- sensitivity原則。

1 敏感度計(jì)算

首先給出敏感屬性等級劃分的定義，然后提出一種敏感屬性等級劃分算法，根據(jù)敏感值在數(shù)據(jù)表中的出現(xiàn)頻率對敏感值進(jìn)行劃分；最后，給出敏感度的計(jì)算方法。設(shè)用戶待發(fā)布的數(shù)據(jù)表={QI1，…，QI，…，QI，SA}，其中QI(1≤≤)為準(zhǔn)標(biāo)識符屬性，SA為敏感屬性。對于中的任一個元組，[]表示元組中屬性的取值。

定義1 等價類。給定數(shù)據(jù)表，為中某些元組的集合，如果中元組在準(zhǔn)標(biāo)識符屬性上具有相同的取值，那么稱為數(shù)據(jù)表的等價類。

定義2 敏感屬性等級劃分。令()為數(shù)據(jù)表在敏感屬性上的值域，將()劃分為個類別()={1，2，…，m}，稱()是敏感屬性等級劃分，則()應(yīng)滿足下列條件：

2) 若＞，則S的敏感度比S的敏感度高。

在現(xiàn)實(shí)生活中，某種敏感值出現(xiàn)的頻率越低，說明具有該敏感值的個體數(shù)越少，這些少數(shù)個體在一般情況下不愿意讓其他個體知道自己的敏感值，因?yàn)樵撁舾兄蹬c大多數(shù)人的不同，容易引起大眾的關(guān)注或者歧視。因此，出現(xiàn)頻率低的敏感值其敏感度要高。按照敏感值出現(xiàn)頻率來對敏感值進(jìn)行劃分，能夠反映出敏感值的敏感度高低，具有一定的合理性。根據(jù)敏感值的出現(xiàn)頻率來對敏感值等級進(jìn)行劃分，劃分方法見算法1。

算法1 敏感屬性等級劃分算法。

輸入：數(shù)據(jù)表，閾值；

輸出：等級劃分集合()。

1) 計(jì)算數(shù)據(jù)表中敏感值的出現(xiàn)頻率；

2)={將敏感值按照其出現(xiàn)頻率降序排列}；

3) while ||＞do

4) 計(jì)算集合中所有相鄰元素的合并范圍;//合并范圍的計(jì)算公式見定義3

5) 合并值最小的2個相鄰元素v, v+1，new={v, v}；

7) end while

8) return()=；

定義3 合并范圍。對于集合中的任意2個相鄰元素v和+1，min是v中元素頻率的最小值，max是v中元素頻率的最大值，v和v的合并范圍。

將敏感屬性進(jìn)行等級劃分之后，不同等級內(nèi)敏感值所代表的敏感等級也不同，因此，需對不同等級的敏感值設(shè)定不同的敏感度。

定義4 敏感度計(jì)算。令()={1，2，…，m}是數(shù)據(jù)表中敏感屬性的等級劃分，是等級S的敏感度，是相鄰等級S?1，S的權(quán)重，則敏感

2 (,)- sensitivity原則

提出一種隱私保護(hù)原則(,)- sensitivity控制等價類中敏感度的分布情況，避免等價類中的敏感值均為高敏感度的情況。

定義5 敏感度的鄰域。給定數(shù)據(jù)表，為敏感度的集合，對于任意敏感度，，則敏感度的鄰域。

定義6 元組鄰域集。給定等價類，是中任意元組，元組包含敏感值的敏感度為，則元組的鄰域集。其中，是′包含敏感值的敏感度，是的鄰域。

定義7 (,)- sensitivity原則。給定數(shù)據(jù)表，為的某個等價類，稱滿足(，)- sensitivity原則，當(dāng)且僅當(dāng)滿足下列條件：

1) 等價類中至少包含個元組，＞1；

2) 對于中的任意元組，其敏感值的敏感度為，在等價類中，的鄰域集至多包含個元組。

由定義7中的條件2)可知，當(dāng)元組的敏感度較高時，等價類中要求其敏感度的鄰域內(nèi)的元組數(shù)會較少，使得等價類中不會出現(xiàn)元組的敏感度都較高的情況。假設(shè)某個等價類中的元組敏感值各不相同，但是它們的敏感度都較高，則攻擊者即使不能推理出個體準(zhǔn)確的敏感值，也可以得出該個體具有較敏感的信息的結(jié)論。若等價類滿足(,)- sensitivity原則，則避免了此類情況的發(fā)生。

定理1 對于包含個元組的等價類，如果其任意2個元組的鄰域集都不存在交集，那么等價類滿足(,)- sensitivity原則。

證明：由已知條件可得，等價類中包含個元組，滿足定義7中的條件1)。又因?yàn)橹腥我?個元組的鄰域集都不存在交集，即元組的鄰域集只包含元組本身。定義7中條件2)要求元組的鄰域集最多為，顯然，，因?yàn)橹忻總€元組的鄰域集只包含1個元組，由此可見等價類滿足條件2)。證畢。

定義8 等價類的敏感度。令為數(shù)據(jù)表的等價類，等價類中敏感屬性的值域?yàn)閧1，2，…，r}，則的敏感度為。其中，表示敏感值s的敏感度，(s)表示敏感值s在等價類中出現(xiàn)的次數(shù)。

定義9 數(shù)據(jù)表的敏感度。給定數(shù)據(jù)表，={1，…，g}為中所有等價類的集合，表的敏感度為

3 基于相異敏感度的數(shù)據(jù)發(fā)布方法

3.1 信息損失度量方法

數(shù)據(jù)泛化后的信息損失度量用以衡量數(shù)據(jù)的效用，也能直接反映出隱私模型的質(zhì)量，現(xiàn)有的衡量匿名信息損失的度量標(biāo)準(zhǔn)包括泛化高度[13?14]、分辨率度量[15]和查詢精度[16]。本文中將QI屬性的初始值與匿名后的屬性值之間的距離作為信息損失度量，采用一般損失度量GLM(generalized loss metric)來衡量信息損失。GLM的度量方法如下。

定義10 數(shù)值型屬性的泛化信息損失。設(shè)準(zhǔn)標(biāo)識符屬性為數(shù)值型屬性，屬性取值的范圍區(qū)間為[,]。設(shè)是屬性的某一取值，泛化為區(qū)間[L,U]，那么匿名的信息損失()=(U－L)/(－)。

定義11 分類型屬性的泛化信息損失。設(shè)準(zhǔn)標(biāo)識符屬性′為分類型屬性，為屬性′的層次樹，為屬性′的某一取值，′是泛化后的取值，那么的信息損失()=(M?1)/(?1)(其中：為′在層次樹中對應(yīng)的節(jié)點(diǎn)；M為以為根節(jié)點(diǎn)的子樹中葉子節(jié)點(diǎn)數(shù)；為層次樹中葉子節(jié)點(diǎn)數(shù))。

在-多樣性[6]中采用分辨率度量DM(discernibility metric)作為數(shù)據(jù)效用的度量標(biāo)準(zhǔn)。DM的度量依賴于數(shù)據(jù)表中等價類的值，對于每一個泛化的元組指定懲罰值||，||表示該元組所在等價類的值。因此，

其中：為分辨率度量；為等價類的數(shù)量。

3.2 最小信息損失增量優(yōu)先算法

定義13 等價類的信息損失增量。給定數(shù)據(jù)表，是數(shù)據(jù)表的等價類，的泛化結(jié)果為(1，2，…，g)。當(dāng)新元組加入到等價類中時，等價類的泛化結(jié)果變?yōu)?′1，′2，…，′)，則等價類的信息損失增量定義為：。

在生成等價類的過程中，如果每次選取的元組使得等價類的信息損失增量最小，將會減少數(shù)據(jù)表的信息損失，保持較高的數(shù)據(jù)效用，因此，提出一種最小信息損失增量優(yōu)先算法(minimum information loss increment first，MILIF)。首先，將元組按照敏感度降序排列；然后，以最小信息損失增量優(yōu)先的策略來生成包含個元組的分組，并且分組中元組的鄰域集各不相交，由定理1可知，生成的分組都滿足 (,)-sensitivity，如此迭代繼續(xù)，直到不能生成滿足要求的分組；最后，對于剩余元組進(jìn)行處理，同樣以最小信息損失增量優(yōu)先的策略將剩余元組加入到滿足(,)-sensitivity原則的分組內(nèi)，若沒有相應(yīng)的分組，則將該元組隱匿。具體的實(shí)現(xiàn)過程見算法2。

算法2 最小信息損失增量優(yōu)先算法。

輸入：數(shù)據(jù)表，閾值和；

輸出：數(shù)據(jù)表′。

//分組階段

根據(jù)算法1中得出的敏感度等級將分為維集合={1，2，…，B}；

//每個集合包含敏感度相同的元組，并且1中元組的敏感度最高，B中元組的敏感度最低。

在首個非空集合B中選取任一元組，；

for=:

if(,) then

//判斷B中的元組加入后，中元組的鄰域集是否互不相交

′=(B,)；//選取使信息損失增量最小的元組

else

continue;

end if

end for

if ||＜then

將集合加入集合中;

else

將集合加入集合中;

end if

end while

//處理剩余元組階段

for中的每一個元組

if (在中存在集合使得添加后仍滿足(,)- sensitivity) then

將加入到信息損失增量最小的集合中;

else

隱匿元組;

end if

end for

將集合以數(shù)據(jù)表′形式發(fā)布。

算法3(,)

是等價類中敏感值的敏感度最小的元組;

if ||=1 then

return true;

else

return false;

else

return true;

end if

end if

算法4(B,)

()是等價類的信息損失；

for 集合B中的每個元組

計(jì)算加入E之后等價類的信息損失增量(,);

end for

4 實(shí)驗(yàn)結(jié)果及分析

通過實(shí)驗(yàn)分析(,)- sensitivity的性能，并將其與文獻(xiàn)[3]提出的(,)-anonymity和文獻(xiàn)[7]提出的 (,)-diversity進(jìn)行比較。實(shí)驗(yàn)所采用的數(shù)據(jù)集為隱私保護(hù)研究中廣泛使用的UCI machine learning repository中的Adult數(shù)據(jù)集，該數(shù)據(jù)集包含部分美國人口普查數(shù)據(jù)，共包含45 222條記錄，刪除包含缺失值的記錄之后剩余30 162條記錄，選取數(shù)據(jù)集中的7個屬性來進(jìn)行實(shí)驗(yàn)，其中{Age，Country，Sex，relationship，education，work-class}為QI屬性，Occupation為SA屬性，數(shù)據(jù)集的描述如表1所示。

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

4.1 數(shù)據(jù)效用分析

采用一般損失度量GLM和分辨率度量DM來衡量(,)- sensitivity的數(shù)據(jù)效用。GLM和DM越小，則說明數(shù)據(jù)的效用越高；反之，數(shù)據(jù)效用越低。

4.1.1 一般損失度量GLM

圖1所示為或的變化對3種算法GLM的影響。由圖1可知：當(dāng)或值的增加時，3種算法的GLM都將增大。這是由于隨著或的增加，等價類中元組數(shù)必將增加，在泛化過程中帶來的信息損失也將增加，因此，GLM將增大。圖2給出了準(zhǔn)標(biāo)識符屬性維數(shù)|QI|變化對3種算法GLM得影響。由圖2可知：當(dāng)|QI|增加時，3種算法的GLM都將增加。這是由于|QI|增加使得在泛化過程中處理的屬性數(shù)增加，帶來的泛化信息損失也將增加，因此，GLM將增大。

圖1 不同k或l下GLM的比較

圖2 不同QI維數(shù)下GLM的比較

此外，由圖1和2可知：在同等條件下，(,)- sensitivity的GLM比(,)-anonymity的大，與 (,)-diversity的GLM基本持平。這是由于(,)- sensitivity的隱私保護(hù)要求比其他2種算法的隱私保護(hù)要求更嚴(yán)格，使得其信息損失較大，然而，(,)- sensitivity在選取元組的過程中采用了最小信息損失優(yōu)先策略，因此，與(,)-diversity的GLM基本持平。

4.1.2 分辨率度量DM

圖3所示為或的變化對3種算法DM的影響。由圖3可知：當(dāng)或增加時，3種算法的DM都將增大。這是由于隨著或的增加，為了滿足隱私保護(hù)的需求，等價類中元組數(shù)將增加，按照DM的計(jì)算公式可知，DM將增加。圖4所示為準(zhǔn)標(biāo)識符屬性維數(shù)|QI|變化對3種算法DM的影響。由圖4可以看出：當(dāng)|QI|增加時，3種算法的DM只產(chǎn)生了細(xì)微的波動。這是由于|QI|的增加并不影響等價類中的元組數(shù)，所產(chǎn)生的細(xì)微波動是元組選取的隨機(jī)性造成的，因此，3種算法的DM波動不大。

此外，由圖3和圖4可知：在同等條件下，(,)- sensitivity的DM比(,)-anonymity和(,)-diversity的大，這是由于(,)- sensitivity要求等價類中每個元組的鄰域集至多包含個元組(見定義7)，為了能夠滿足隱私保護(hù)的需求，使得(,)-sensitivity中等價類的元組數(shù)比其他2種算法中的元組數(shù)多，因此，DM較大。

圖3 不同k或l下DM的比較

圖4 不同QI維數(shù)下DM的比較

4.2 執(zhí)行時間分析

圖5~7所示分別為或、準(zhǔn)標(biāo)識符屬性維數(shù)和數(shù)據(jù)集變化對3種算法執(zhí)行時間的影響。由圖5可知：當(dāng)或的增加時，3種算法的執(zhí)行時間都減小。這是由于隨著或的增加，在生成等價類的過程中會有更多的候選元組，更容易生成滿足隱私需求的等價類，因此，執(zhí)行時間將減少。由圖6可知：當(dāng)QI增加時，3種算法的執(zhí)行時間都將增大。這是由于隨著QI的增加，在泛化過程中處理的準(zhǔn)標(biāo)識符屬性增加，消耗了更多的處理時間，因此，執(zhí)行時間將增加。由圖7可知：當(dāng)數(shù)據(jù)集增大時，3種算法的執(zhí)行時間都將增大。這是由于數(shù)據(jù)集增大必然會導(dǎo)致處理時間增加，因此，執(zhí)行時間都將增加。