基于數(shù)據(jù)隱私保護的(L,K,d)算法

康茜，晏慧，雷建云

(中南民族大學 計算機科學學院，武漢 430074)

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

1 相關(guān)概念

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

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

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

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

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

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

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

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

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

表3 登記信息表

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

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

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

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

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

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

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

2 算法及改進

2.1 泛化層次樹

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

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

2.2 元組之間的泛化距離

(1)在泛化層次樹中并非每層的泛化程度都是一樣的，層次樹越高則泛化程度越大，數(shù)據(jù)失真度越高.故本文引入權(quán)重W來衡量準標識屬性的泛化程度：假設(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)

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

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

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

(2)

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

(3)

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

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

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

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

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

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

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

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

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

步驟

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

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

1)隨機選擇一個小于K的等價組C;

2)計算C與其他所有等價組的泛化距離:

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

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

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

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

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

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

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

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

(4)返回匿名表S′.

3 實驗

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

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

圖2 信息損失比較

如圖3所示，橫軸為屬性，縱軸為隱私泄露概率.取3種屬性來分別檢測兩種算法的隱私泄漏概率：native-country為準標識屬性中的隱私屬性，是個體在意的需要保護的屬性；marital-status為敏感屬性，且易受背景知識攻擊；occupation為敏感屬性，相對于marital-status個體更為在意，因此更需要隱私保護.對于第1種屬性native-country：(L,K,d)多樣化匿名算法相對于(P,K,d)匿名算法有很明顯的隱私保護度，這是因為改進的(L,K,d)多樣化匿名算法對該隱私屬性進行了更強的泛化，更好地保護了該屬性的隱私；對于第2種屬性marital-status：兩種算法的隱私保護度相差甚小，但該屬性容易受到背景知識攻擊，故隱私泄漏概率比occupation要高一些；對于第3種屬性occupation：改進的(L,K,d)多樣化匿名算法具有較高的隱私保護度，這是因為新算法對d-相異度做了改進，對于更需保護的敏感屬性d-相異度取更大的值，故明顯降低了該敏感屬性被泄漏的概率.

圖3 隱私泄露比較

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

4 結(jié)語

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