康茜，晏慧，雷建云

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

目前數(shù)據(jù)共享時(shí)最需要解決的問(wèn)題是保護(hù)個(gè)體的數(shù)據(jù)隱私.一方面，如果在發(fā)布共享時(shí)沒(méi)有對(duì)數(shù)據(jù)進(jìn)行加密保護(hù)，這將會(huì)對(duì)個(gè)體造成隱私困擾；另一方面，如果不對(duì)數(shù)據(jù)進(jìn)行發(fā)布共享，這將不利于社會(huì)研究發(fā)展.如何在發(fā)布共享數(shù)據(jù)的同時(shí)對(duì)數(shù)據(jù)進(jìn)行隱私保護(hù)成為眾多研究者關(guān)注的問(wèn)題.在發(fā)布數(shù)據(jù)時(shí)需要以犧牲數(shù)據(jù)精度為代價(jià)，給科研者提供較高的數(shù)據(jù)研究?jī)r(jià)值的同時(shí)，最大程度地保護(hù)個(gè)體的數(shù)據(jù)隱私.K-匿名算法[1]是一種早期提出的有效保護(hù)數(shù)據(jù)隱私的方法:將準(zhǔn)標(biāo)識(shí)屬性進(jìn)行泛化等處理，使得在劃分的同一等價(jià)組內(nèi)至少有K條不可區(qū)分的準(zhǔn)標(biāo)識(shí)屬性.當(dāng)攻擊者想要通過(guò)已獲得的數(shù)據(jù)表進(jìn)行數(shù)據(jù)關(guān)聯(lián)來(lái)獲取個(gè)體隱私時(shí)，攻擊者至少要排除掉K-1個(gè)元組.K-匿名算法的提出有效地抵御了來(lái)自攻擊者的關(guān)聯(lián)攻擊，很大程度上保護(hù)了個(gè)體的隱私安全.但是，當(dāng)同一等價(jià)組中的敏感屬性值大部分相同時(shí)，攻擊者即使無(wú)法確定具體元組也能知曉被攻擊者的敏感信息，這就造成了個(gè)體的隱私泄露.L-匿名算法[2]的提出在一定程度上解決了同質(zhì)攻擊的問(wèn)題：在滿足K-匿名算法的同時(shí)，L-匿名算法規(guī)定同一等價(jià)組中至少有L個(gè)不同的敏感屬性值.這在一定程度上抵御了同質(zhì)攻擊帶來(lái)的隱私問(wèn)題.然而，即使對(duì)數(shù)據(jù)進(jìn)行了來(lái)自關(guān)聯(lián)攻擊和同質(zhì)攻擊的保護(hù)，攻擊者也可能因?yàn)橥坏葍r(jià)組中的某些敏感屬性值具體語(yǔ)義相同而推理出個(gè)體在某個(gè)較小范圍內(nèi)的隱私.如：胃潰瘍，胃脹氣，胃結(jié)石等在具體語(yǔ)義上都屬于胃病，攻擊者即使不知道患者的具體病情也可以通過(guò)關(guān)聯(lián)獲知該患者患有胃病，在一定程度上個(gè)體隱私?jīng)]有得到較好的保護(hù).針對(duì)這種相似性攻擊，已有研究者提出了(P,K,d)匿名算法[3]：在滿足K-匿名算法的同時(shí)，該算法規(guī)定同一等價(jià)組中至少有p個(gè)滿足d-相異程度的敏感屬性值.(P,K,d)匿名算法的提出有效抵御了敏感屬性值相似性問(wèn)題，阻礙了攻擊者獲取被攻擊者某一小范圍隱私的途徑.在這些算法的基礎(chǔ)上本文做了一些改進(jìn)，使數(shù)據(jù)達(dá)到更高的使用價(jià)值的同時(shí)對(duì)數(shù)據(jù)實(shí)施更有效的隱私保護(hù)，解決數(shù)據(jù)有效性和數(shù)據(jù)隱私保護(hù)兩者的矛盾.個(gè)體的隱私不僅僅只有一個(gè)，針對(duì)多維敏感屬性[4]的出現(xiàn)，本文改進(jìn)了算法使之適用于多維敏感屬性，從而保障了多維敏感屬性的隱私安全.

1 相關(guān)概念

以表1為例進(jìn)行相關(guān)概念的描述.

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

定義1元組(tuple):數(shù)據(jù)表中的每一行即為一個(gè)元組.

定義2屬性(property)：數(shù)據(jù)表中的每一列都屬于同一個(gè)屬性.如{姓名}，{性別}等.

定義3準(zhǔn)標(biāo)識(shí)符集(quasi-identifier attribute set)：準(zhǔn)標(biāo)識(shí)符集是在一定程度上可以公布的、能夠與外部的數(shù)據(jù)表進(jìn)行聯(lián)接來(lái)識(shí)別個(gè)體的最小屬性集合.如表2中的屬性集{性別，年齡，住址}即為一個(gè)準(zhǔn)標(biāo)識(shí)符集.

表2 刪除標(biāo)識(shí)符后的數(shù)據(jù)表

定義4敏感屬性：數(shù)據(jù)表中的有些屬性是個(gè)體本身比較在意的信息，不愿被暴露在公眾視野之下，這些屬性即為敏感屬性，數(shù)據(jù)在被發(fā)布之前必須將這些信息保護(hù)起來(lái)以防隱私泄露.如表2 中的{病史}屬性即為敏感屬性，但是該敏感屬性在某些研究領(lǐng)域是具有研究?jī)r(jià)值的，倘若在發(fā)布之前直接刪除會(huì)導(dǎo)致數(shù)據(jù)的可用性大大降低.

表3為一張登記信息表，倘若攻擊者從某些途徑獲取到該數(shù)據(jù)表，并將其與表2進(jìn)行關(guān)聯(lián)來(lái)獲取被攻擊者的個(gè)體信息[5]，將會(huì)導(dǎo)致嚴(yán)重的隱私泄露.

定義5泛化：泛化是一種匿名化方法，它主要針對(duì)準(zhǔn)標(biāo)識(shí)符集進(jìn)行操作，通過(guò)將準(zhǔn)標(biāo)識(shí)符集的具體值泛化為某一不確定具體值的值域，來(lái)達(dá)到防止攻擊者通過(guò)準(zhǔn)標(biāo)識(shí)符集進(jìn)行數(shù)據(jù)關(guān)聯(lián)以保護(hù)被攻擊者個(gè)體隱私的目的.表4是對(duì)表3進(jìn)行泛化后的數(shù)據(jù)表.

表3 登記信息表

表4 泛化后的數(shù)據(jù)表

為了阻止關(guān)聯(lián)攻擊以防隱私泄露，要求在同一個(gè)等價(jià)組中的所有準(zhǔn)標(biāo)識(shí)屬性都不可區(qū)分地相同.例如在對(duì)表4進(jìn)行2-匿名處理后的數(shù)據(jù)表5中，記錄1與記錄2組成了同一等價(jià)組，該等價(jià)組中性別、年齡、住址是不可區(qū)分的.假若每個(gè)等價(jià)組中都至少有K條記錄的準(zhǔn)標(biāo)識(shí)屬性不可區(qū)分，則稱該表滿足K-匿名數(shù)據(jù)表.可知，如若每個(gè)等價(jià)組中的記錄都只有一條，那么該表必然會(huì)遭受到關(guān)聯(lián)攻擊.

表5 K-匿名數(shù)據(jù)表(K=2)

定義6同質(zhì)性攻擊[6]:假若在同一等價(jià)組中的敏感屬性值全部或者大多數(shù)都相同，在此種情況下，即使攻擊者無(wú)法關(guān)聯(lián)到具體元組也能獲取被攻擊者的隱私情況.例如序號(hào)5與序號(hào)6的敏感屬性病史值都為肺炎，那么攻擊者進(jìn)行數(shù)據(jù)關(guān)聯(lián)后將得知個(gè)體孫鑫和周私雪兩人患過(guò)肺炎，這就造成了主體的隱私泄露.信息的有用程度不應(yīng)以泄露個(gè)體的隱私為代價(jià)，應(yīng)該以犧牲數(shù)據(jù)的最低使用價(jià)值為代價(jià)來(lái)保護(hù)數(shù)據(jù)的隱私安全.L-匿名算法要求同一等價(jià)組中的敏感屬性都至少有L個(gè)不同的值，該算法的提出有效地解決了同質(zhì)攻擊帶來(lái)的隱私保護(hù)問(wèn)題.表6是對(duì)表5進(jìn)行2-匿名處理后的數(shù)據(jù)表.

表6 L-匿名數(shù)據(jù)表(L=2)

定義7相似性攻擊[7]:相似性攻擊的攻擊對(duì)象為同一等價(jià)組中語(yǔ)義相似的準(zhǔn)標(biāo)識(shí)屬性值，如果數(shù)據(jù)保護(hù)者沒(méi)有考慮到準(zhǔn)標(biāo)識(shí)屬性的語(yǔ)義相似性問(wèn)題，攻擊者將會(huì)攻擊到某一小范圍的隱私.例如表6中的第一組等價(jià)組中的腳踝脫臼和膝蓋骨折都屬于骨科疾病，即使攻擊者無(wú)法獲知具體的疾病史也能了解到個(gè)體曾有過(guò)與骨骼相關(guān)的疾病史.后文有改進(jìn)的算法來(lái)抵御相似性攻擊.

在眾多數(shù)據(jù)攻擊中，背景知識(shí)攻擊[8]是最難解決的，因?yàn)閿?shù)據(jù)保護(hù)者無(wú)法得知攻擊者已經(jīng)掌握了哪些背景知識(shí)，無(wú)法有效解決隱私泄露問(wèn)題.例如表5中的第一組等價(jià)組，假若攻擊者通過(guò)數(shù)據(jù)關(guān)聯(lián)來(lái)查詢王海的隱私情況，又得知王海喜歡打籃球中間卻有段時(shí)間沒(méi)打籃球，那么就可以得知王海曾有過(guò)腳踝脫臼的病史.此種背景知識(shí)攻擊是很難抵御的.

2 算法及改進(jìn)

2.1 泛化層次樹

如圖1中的泛化層次樹，采用泛化的思維來(lái)實(shí)施K-匿名算法，目的是以犧牲最低的數(shù)據(jù)真實(shí)度為代價(jià)來(lái)抵御關(guān)聯(lián)攻擊，通過(guò)泛化準(zhǔn)標(biāo)識(shí)屬性值使之成為同一等價(jià)組.泛化會(huì)導(dǎo)致生成的準(zhǔn)標(biāo)識(shí)屬性值與原始的標(biāo)準(zhǔn)屬性值存在差異，從而使數(shù)據(jù)失真.數(shù)據(jù)泛化程度越高，失真度越大.為了使數(shù)據(jù)泛化時(shí)失真度盡可能小(即盡可能地保護(hù)數(shù)據(jù)的真實(shí)性和有用性)，準(zhǔn)標(biāo)識(shí)屬性值泛化為同一等價(jià)組時(shí)要求元組泛化后的距離[9]盡可能的小，即保障數(shù)據(jù)因泛化導(dǎo)致的失真盡可能的小.

兩個(gè)準(zhǔn)標(biāo)識(shí)屬性值(V1,V2)之間的相異程度(Distance)可以由它們距離其最小公共祖先結(jié)點(diǎn)Vm的距離的最小值來(lái)表示.即Distance(V1,V2)=min{level(V1)-level(Vm),level(V2)-level(Vm)}，其中l(wèi)evel表示準(zhǔn)標(biāo)識(shí)屬性所在的泛化層次樹中的層次數(shù)[10].例如：在圖1的泛化層次樹中，葉子結(jié)點(diǎn)(第4層為葉子結(jié)點(diǎn))中的兩個(gè)屬性風(fēng)濕病和關(guān)節(jié)炎其最小公共祖先結(jié)點(diǎn)為骨骼病變(第3層)，那么這兩個(gè)屬性值之間的相異程度Distance=min(4-3,4-3)=1，兩者屬于同一類型疾病，相異程度很小，共同泛化后失真代價(jià)小；但是圖1中的咽喉炎和關(guān)節(jié)炎的最小公共祖先結(jié)點(diǎn)為病史(第一層)，兩個(gè)屬性值之間的相異程度Distance=min(4-1,4-1)=3,兩者的相異程度極大，共同泛化后將導(dǎo)致巨大的數(shù)據(jù)失真，嚴(yán)重影響數(shù)據(jù)的研究?jī)r(jià)值.由此可見，如果準(zhǔn)標(biāo)識(shí)屬性值離其最小公共結(jié)點(diǎn)越遠(yuǎn)，則屬性值之間的相異程度越大，越不適合作為等價(jià)組來(lái)進(jìn)行泛化.

2.2 元組之間的泛化距離

(1)在泛化層次樹中并非每層的泛化程度都是一樣的，層次樹越高則泛化程度越大，數(shù)據(jù)失真度越高.故本文引入權(quán)重W來(lái)衡量準(zhǔn)標(biāo)識(shí)屬性的泛化程度：假設(shè)某個(gè)準(zhǔn)標(biāo)識(shí)屬性Vj從p層泛化到了q層(1≥p>q≥h,h為泛化層次樹的高度)，則W(p,q)=1/q.q值越小，泛化程度越高，權(quán)重越大，數(shù)據(jù)失真度越高[11].定義加權(quán)層次距離(Weighted Hierarchical Distance)如下：

(1)

例如屬性風(fēng)濕病從4層泛化到2層，j=3,則:

WHD(4，2)=(1/2+1/3)/(1+1/2+1/3)=0.45.

(2)所有準(zhǔn)標(biāo)識(shí)屬性泛化后的加權(quán)層次距離之和即為元組t泛化后的距離：

(2)

(3)有些準(zhǔn)標(biāo)識(shí)屬性在一定意義上是個(gè)體不愿意過(guò)度暴露的隱私，在保障數(shù)據(jù)的可用價(jià)值的同時(shí)，數(shù)據(jù)在發(fā)布時(shí)理應(yīng)對(duì)其進(jìn)行高度泛化處理來(lái)解決個(gè)體的隱私隱患.例如有以下元組：元組1住址為湖北省武漢市洪山區(qū)關(guān)山大道金地太陽(yáng)城15號(hào)樓10-311.若元組1的住址屬性只在相鄰泛化層次樹之間進(jìn)行泛化(即p=q+1)，則元組1的住址將會(huì)泛化為武漢市洪山區(qū)關(guān)山大道金地太陽(yáng)城15號(hào)樓，此種程度的泛化結(jié)果是個(gè)體不愿意看到的，因?yàn)樽≈穼傩赃^(guò)于具體，很有可能給個(gè)體帶來(lái)騷擾甚至安全隱患.針對(duì)此種情況，專門提出了一種新的元組泛化后的距離算法：

(3)

其中，當(dāng)Vj為需要高度保護(hù)的準(zhǔn)標(biāo)識(shí)屬性時(shí)(例如住址)，則要求p>q+1(即該屬性必須在泛化層次樹上滿足兩層以上的泛化距離).

意義：新的元組泛化距離對(duì)某些準(zhǔn)標(biāo)識(shí)屬性更有針對(duì)性，在加強(qiáng)了用戶隱私安全保護(hù)的同時(shí)，又最大程度減少了數(shù)據(jù)泛化的失真度.

2.3 多維敏感屬性d-相異度

相異程度(Distance)用來(lái)描述兩個(gè)屬性之間的相似程度.為了抵御由于敏感值屬性相似造成的同質(zhì)攻擊和背景知識(shí)攻擊，早期的(P,K,d)匿名算法已經(jīng)很好地解決了這些安全問(wèn)題，(P,K,d)匿名算法要求在滿足K-匿名的條件下，同一等價(jià)組內(nèi)至少有P個(gè)滿足d-相異度的敏感屬性值(此處的d一般大于1即可，即敏感屬性值不屬于同一層語(yǔ)義樹即可)[12].但是此算法只適用于解決單維敏感屬性相似性問(wèn)題，而現(xiàn)實(shí)數(shù)據(jù)中往往會(huì)存在多維敏感屬性相似性攻擊問(wèn)題，例如{職業(yè)，疾病，工資}會(huì)組成三維敏感屬性，發(fā)布者必須同時(shí)保護(hù)這3種屬性的隱私安全.在實(shí)際情況中各個(gè)維度的敏感屬性隱私保護(hù)程度不同，需要加以區(qū)分.故此提出了多維敏感屬性d-相異度的概念：在多維敏感屬性中，由于不同維度的敏感屬性所需要的隱私保護(hù)程度存在差異性，故需要根據(jù)實(shí)際情況取不同的d值，以此來(lái)約束各個(gè)維度敏感屬性的泛化程度，從而滿足不同維度敏感屬性的隱私保護(hù)程度.d值越大，泛化程度越高，該敏感屬性保護(hù)程度越高;反之敏感屬性保護(hù)度越低.例如在三維敏感屬性{職業(yè)，疾病，工資}中，工資和職業(yè)為一般保護(hù)的隱私，只需滿足一般的d-相異度即可.而疾病涉及到個(gè)體的人身安全問(wèn)題，個(gè)體最不希望將自己的病史公之于眾，疾病這一敏感屬性對(duì)于另外兩維敏感屬性來(lái)說(shuō)更需要隱私保護(hù).故取不同的d值來(lái)滿足不同維度敏感屬性的隱私保護(hù)度，d(職業(yè)，工資)=1，d(疾病)=2，故將d設(shè)置為2以此來(lái)提高敏感屬性值間的相異程度，從而更好地防止多維敏感屬性數(shù)據(jù)遭受攻擊.

2.4 (L,K,d)多樣化匿名算法

(L,K,d)多樣化匿名算法要求在滿足K-匿名算法的同時(shí)，在同一等價(jià)組中所有維度的敏感屬性值至少都有L條不同的記錄滿足d-相異度.既保證了數(shù)據(jù)不受到關(guān)聯(lián)攻擊，又保障了不同維度的敏感屬性不受到同質(zhì)性攻擊和背景知識(shí)攻擊.

算法(L,K,d)多樣化匿名算法

輸入原始數(shù)據(jù)集S，等價(jià)類中不同屬性值個(gè)數(shù)L，d-相異度

輸出匿名表S′，S′中的每個(gè)等價(jià)組中至少有K個(gè)元組的準(zhǔn)標(biāo)識(shí)屬性值不可區(qū)分，且同一等價(jià)組中所有維度的敏感屬性都至少有L個(gè)值滿足d-相異度

步驟

(1)由數(shù)據(jù)集S中生成初始等價(jià)組;

(2)循環(huán)，直至不存在元組個(gè)數(shù)小于K的等價(jià)組:

1)隨機(jī)選擇一個(gè)小于K的等價(jià)組C;

2)計(jì)算C與其他所有等價(jià)組的泛化距離:

3)找出距離C最近的等價(jià)組C′;

4)將C與C′泛化合并為同一等價(jià)組;

循環(huán)結(jié)束，得到K-匿名表T;

(3)循環(huán)，直至同一等價(jià)組中所有維度的敏感屬性d-相異度個(gè)數(shù)都不少于L:

1)隨機(jī)選擇一個(gè)多維敏感屬性d-相異度個(gè)數(shù)少于L的等價(jià)組A;

2)找出距離A最近的等價(jià)組A′;

3)將A與A′合并為同一等價(jià)組;

循環(huán)結(jié)束;

(4)返回匿名表S′.

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

選取的實(shí)驗(yàn)數(shù)據(jù)集為UCI中的Adult標(biāo)準(zhǔn)數(shù)據(jù)集，該數(shù)據(jù)集中含有48842條有效數(shù)據(jù)，選取其中的5個(gè)屬性進(jìn)行實(shí)驗(yàn)：sex(性別)、age(年齡)、native-country(出生地)、marital-status(婚姻狀況)、occupation(職業(yè))，具體屬性情況如表7所示.實(shí)驗(yàn)將從信息損失數(shù)、隱私泄露概率兩方面來(lái)比較已有的(P,K,d)算法和提出的(L,K,d)多樣化匿名算法，并從信息損失度的大小和隱私泄露率的高低兩方面來(lái)評(píng)估(L,K,d)多樣化匿名算法.

如圖2所示，橫軸為K的不同取值，縱軸為信息損失數(shù)量.可以看出，當(dāng)取相同的K值時(shí)，兩種算法的信息損失度幾乎相同.只是原有的(P,K,d)算法信息損失度相對(duì)較低，而提出的(L,K,d)多樣化匿名算法信息損失度相對(duì)較高.這是因?yàn)?L,K,d)多樣化匿名算法對(duì)某些重要的準(zhǔn)標(biāo)識(shí)屬性增強(qiáng)了泛化程度來(lái)保護(hù)隱私屬性(如表7中的屬性3是個(gè)體希望加強(qiáng)保護(hù)的隱私屬性)，故使得信息損失度稍微增加.另外，隨著K值的增加兩種算法的信息損失度相繼增加，這是因?yàn)镵值增加使得同一等價(jià)組中的泛化元組變多，泛化次數(shù)越多則信息損失度越高.

圖2 信息損失比較

如圖3所示，橫軸為屬性，縱軸為隱私泄露概率.取3種屬性來(lái)分別檢測(cè)兩種算法的隱私泄漏概率：native-country為準(zhǔn)標(biāo)識(shí)屬性中的隱私屬性，是個(gè)體在意的需要保護(hù)的屬性；marital-status為敏感屬性，且易受背景知識(shí)攻擊；occupation為敏感屬性，相對(duì)于marital-status個(gè)體更為在意，因此更需要隱私保護(hù).對(duì)于第1種屬性native-country：(L,K,d)多樣化匿名算法相對(duì)于(P,K,d)匿名算法有很明顯的隱私保護(hù)度，這是因?yàn)楦倪M(jìn)的(L,K,d)多樣化匿名算法對(duì)該隱私屬性進(jìn)行了更強(qiáng)的泛化，更好地保護(hù)了該屬性的隱私；對(duì)于第2種屬性marital-status：兩種算法的隱私保護(hù)度相差甚小，但該屬性容易受到背景知識(shí)攻擊，故隱私泄漏概率比occupation要高一些；對(duì)于第3種屬性occupation：改進(jìn)的(L,K,d)多樣化匿名算法具有較高的隱私保護(hù)度，這是因?yàn)樾滤惴▽?duì)d-相異度做了改進(jìn)，對(duì)于更需保護(hù)的敏感屬性d-相異度取更大的值，故明顯降低了該敏感屬性被泄漏的概率.

圖3 隱私泄露比較

從實(shí)驗(yàn)結(jié)果可以看出，(L,K,d)多樣化匿名算法相對(duì)于傳統(tǒng)的(P,K,d)算法而言，對(duì)數(shù)據(jù)具有更靈活的處理能力.首先，(L,K,d)多樣化匿名算法將數(shù)據(jù)中的準(zhǔn)標(biāo)識(shí)屬性進(jìn)行了不同程度的泛化處理，以此提高了個(gè)別準(zhǔn)標(biāo)識(shí)屬性的隱私保護(hù)程度，但在一定程度上降低了數(shù)據(jù)的可用性;其次，(L,K,d)多樣化匿名算法提出的多維敏感屬性d-相異度對(duì)不同維度的敏感屬性進(jìn)行了不同程度的約束，更加靈活地保證了數(shù)據(jù)的隱私保護(hù)程度的同時(shí)，又維持了數(shù)據(jù)的可用性.

4 結(jié)語(yǔ)

本文首先對(duì)已有的K-匿名算法進(jìn)行了改進(jìn)，通過(guò)控制泛化的程度來(lái)控制不同的準(zhǔn)標(biāo)識(shí)屬性公開度，滿足了個(gè)人對(duì)敏感準(zhǔn)標(biāo)識(shí)屬性的隱私保護(hù)，以此來(lái)提高病人的隱私保護(hù)程度；其次對(duì)(P,K,d)匿名算法進(jìn)行了改進(jìn)，通過(guò)控制不同的d-相異度來(lái)保證個(gè)別重要敏感屬性的隱私保護(hù)，改進(jìn)后的算法不僅適用于抵抗單維敏感屬性中的同質(zhì)性攻擊和背景知識(shí)攻擊，同時(shí)也適用于多維敏感屬性表；最后，綜合K-匿名算法和(P,K,d)匿名算法，提出了一種新的(L,K,d)多樣化匿名算法，使同一等價(jià)組中所有維度的敏感屬性至少有L條不同的記錄滿足d-相異度條件，在提高數(shù)據(jù)的隱私保護(hù)度的同時(shí)，也保障了數(shù)據(jù)的有用性.