程楠楠， 劉樹波， 熊星星， 蔡朝暉， 張家浩

(武漢大學(xué) 計算機學(xué)院 湖北 武漢 430072)

0 引言

信息化的快速發(fā)展加速了數(shù)據(jù)表在網(wǎng)絡(luò)上的發(fā)布，為信息共享帶來極大便利.但各類數(shù)據(jù)表中可能包含大量涉及用戶隱私的敏感信息，如身體疾病信息、生活軌跡信息等.因此，需要在數(shù)據(jù)表發(fā)布前對表中信息加以處理，以避免發(fā)布過程中的信息泄露.1999年，匿名概念首次被提出[1].隨后，有學(xué)者提出k-匿名模型[2]，模型要求等價類中的k條記錄匿名化處理后不可區(qū)分，從而實現(xiàn)用戶的隱私保護.但該模型在劃分等價類時沒有對記錄的敏感屬性做出約束，數(shù)據(jù)表易遭受攻擊.針對k-匿名模型的不足，文獻[3]提出l-diversity模型，要求等價類中至少含有l(wèi)個不同的敏感屬性值；文獻[4]提出t-closeness模型，要求等價類中敏感屬性值分布與原始數(shù)據(jù)表的分布規(guī)律相似；文獻[5]和文獻[6]分別提出(a,k)-匿名模型與(p,k)-匿名模型，以上模型在抵制某種特定攻擊時效果良好，但在同時抵制背景知識攻擊[7]與相似性攻擊[8]方面效果不佳.為了給用戶隱私提供更有效的保護，達到同時抵制背景知識攻擊與相似性攻擊的目的，本文提出一種分組的(θ,k)-匿名隱私保護模型，模型依據(jù)敏感屬性值間存在的語義關(guān)系將等價類分組，使組內(nèi)記錄的敏感屬性值保持較高的相似性，組間記錄的敏感屬性值保持較高的相異性.同時，本文考慮數(shù)據(jù)可用性問題，采用距離度量方法減少信息損失，提高了數(shù)據(jù)可用性，并通過實驗證明了(θ,k)-匿名模型的有效性.

1 相關(guān)概念及技術(shù)

1.1 基本概念

待發(fā)布的原始數(shù)據(jù)表通常包括標(biāo)識符、準(zhǔn)標(biāo)識符、敏感屬性三種屬性信息[9]，發(fā)布前需要對數(shù)據(jù)表進行處理.

定義1等價類:對于一個數(shù)據(jù)表T(A1,A2,…,An)，n代表數(shù)據(jù)表中的屬性個數(shù)，等價類為數(shù)據(jù)表T中具有相同準(zhǔn)標(biāo)識符投影的記錄集合，這些記錄通過準(zhǔn)標(biāo)識符不可區(qū)分[10-12].

定義2k-匿名模型:等價類中至少包含k條在準(zhǔn)標(biāo)識符上不可區(qū)分的記錄.

定義3(p,k)-匿名模型:數(shù)據(jù)表T在滿足k-匿名模型的前提下，每個等價類中至少含有p個不同的敏感屬性值.

例如，表1為原始數(shù)據(jù)表，經(jīng)過(p,k)-匿名泛化后得到表2的匿名數(shù)據(jù)表(p=6,k=6).若攻擊者已知被攻擊者屬于表2的等價類，由于該等價類中胃部疾病比例高達50%，因此攻擊者可認(rèn)為患者大概率患有胃部疾病，這種攻擊稱之為相似性攻擊.若攻擊者根據(jù)背景知識得知被攻擊者患有骨科疾病，但不能明確具體的疾病值，根據(jù)表2中記錄，由于只有骨折為骨科疾病，因此攻擊者可推測出患者所患疾病為骨折，這種攻擊稱之為背景知識攻擊.劃分等價類時若記錄敏感屬性值語義相似的個數(shù)較多，等價類易受相似性攻擊；若語義相似的個數(shù)較少，等價類易受背景知識攻擊.對記錄敏感屬性值約束不足，導(dǎo)致數(shù)據(jù)表泛化后同時抵制兩種攻擊的性能不佳.本文提出(θ,k)-匿名保護模型，旨在通過分組優(yōu)化模型的抗攻擊性能.

表1 原始數(shù)據(jù)表Tab.1 A raw data table

表2 (p,k)-匿名數(shù)據(jù)表Tab.2 A (p,k)-anonymous data table

定義4語義層次樹[13]：對數(shù)據(jù)表中的屬性值進行語義分析得到語義層次樹，樹中根節(jié)點為屬性值全集，父節(jié)點為其葉子節(jié)點的泛化，葉子節(jié)點為父節(jié)點的子類.

圖1為簡化后的疾病語義層次樹.根節(jié)點是疾病全集，父節(jié)點是其子節(jié)點疾病值不同程度的泛化，葉子節(jié)點代表具體的疾病值.屬性的相似或相異度可通過層次樹中葉子節(jié)點到其最小公共父節(jié)點的距離進行度量.圖1中胃炎與胃潰瘍到最小父節(jié)點胃部疾病的距離相等且均為1，屬于相同類型疾病，相似程度較高；胃炎與流感的最小父節(jié)點是根節(jié)點，兩者到公共父節(jié)點的距離均為3，屬于不同類型疾病，相異程度較高.

圖1 疾病語義層次樹Fig.1 Disease semantic hierarchy tree

定義5(θ,k)-匿名模型：將等價類中k條記錄分為θ組，使同組記錄的敏感屬性值具有較高的相似性以抵制背景知識攻擊，不同組記錄的敏感屬性值具有較高的相異性以抵制相似性攻擊，以此避免等價類中記錄敏感屬性相異程度過高或相似程度過高的情況，達到同時抵制背景知識與相似性雙重攻擊的目的.

表3 (θ,k)-匿名數(shù)據(jù)表Tab.3 A (θ,k)-anonymous data table

表3是一個經(jīng)(θ,k)-匿名方法處理得到的數(shù)據(jù)表(θ=3,k=6).表中等價類分為三組，序號表示記錄組號.三組記錄之間敏感屬性所屬疾病類型相異，可達到抵制相似性攻擊的目的；每組包含兩條敏感屬性值相似的記錄，可達到抵制背景知識攻擊的目的.數(shù)據(jù)表抗攻擊性能得到改善，用戶隱私得到更有效的保護.

1.2 距離度量與信息損失計算

k-匿名通常將等價類中記錄的準(zhǔn)標(biāo)識符泛化，以達到保護用戶隱私的目的.進行泛化必然導(dǎo)致數(shù)據(jù)信息損失，因此在保護用戶隱私的前提下減少信息損失是本文的關(guān)注點之一.在滿足(θ,k)-匿名模型的前提下，若劃分到同一等價類中記錄的準(zhǔn)標(biāo)識符具有較高的相似性，可有效減少泛化時的信息損失.本文采用距離度量方法衡量記錄準(zhǔn)標(biāo)識符之間的相似性[14-15].

準(zhǔn)標(biāo)識符通常包含數(shù)值型屬性與分類型屬性兩類，不同類型需采用不同的距離度量公式.數(shù)值型屬性之間存在序關(guān)系，相對容易計算；部分分類型屬性的度量方式為：若兩條記錄的某一屬性值相同，則該屬性距離記為0，否則記為1.該度量方式?jīng)]有考慮分類型屬性的語義關(guān)系，泛化時易造成較高的信息損失.本文對分類型屬性進行語義分析，得到屬性的語義層次樹，并根據(jù)屬性值在語義層次樹中的距離定義記錄之間的距離.

數(shù)據(jù)表T的準(zhǔn)標(biāo)識符集合為QI={N1,N2,…,Nm,C1,C2,…,Cn},其中Ni(i=1,2,…,m)為數(shù)值型屬性，Cj(j=1,2,…,n)為分類型屬性.

定義6數(shù)值型屬性距離度量：若某一屬性的值域為有限域D，|D|表示D中最大值與最小值的差值，則兩個屬性值vi、vj之間的標(biāo)準(zhǔn)距離定義為δN(vi,vj)=|vi-vj|/|D|.

定義7分類型屬性距離度量:設(shè)TD為某一屬性值域D上的語義層次樹，H(TD)代表層次樹的高度，∧(vi,vj)代表兩個屬性值vi、vj在層次樹上的最小公共父節(jié)點，則vi、vj之間的標(biāo)準(zhǔn)距離定義為

δC(vi,vj)=H(∧(vi,vj))/H(TD).

定義8記錄距離度量: 結(jié)合數(shù)值型與分類型屬性的距離度量公式,兩條記錄r1、r2之間的距離為

式中：ri[A]表示第i條記錄在屬性A上的值.

定義9信息損失:設(shè)e={r1,r2,…,rk}是使用(θ,k)-匿名泛化后的一個等價類，泛化處理的信息損失為

2 (θ,k)-匿名模型

現(xiàn)有k-匿名模型及其改進模型在等價類劃分過程中對敏感屬性約束不足，導(dǎo)致模型同時抵制背景知識攻擊與相似性攻擊的性能不佳.本文提出(θ,k)-匿名模型，在數(shù)據(jù)表發(fā)布前對表中敏感屬性進行語義分析得到敏感屬性語義層次樹，劃分等價類時依據(jù)層次樹對等價類分組，使分組后的等價類滿足記錄在組內(nèi)保持敏感屬性值相似，在組間保持敏感屬性值相異，達到降低敏感信息泄露概率和保護用戶隱私的目的.為提高數(shù)據(jù)可用性，減少不必要的信息損失，本文在劃分等價類時采用距離度量方法，使同一等價類中記錄的準(zhǔn)標(biāo)識符具有較小的距離，以減少因泛化帶來的數(shù)據(jù)信息損失.

2.1 (θ,k)-匿名模型算法的思想

(θ,k)-匿名模型算法的基本思想：① 對需要保護的敏感屬性進行語義分析并構(gòu)建相應(yīng)的語義層次樹，利用哈希技術(shù)將記錄根據(jù)敏感屬性值在語義層次樹中所屬類別分成若干個hash桶，同一hash桶中記錄的敏感屬性類別相同.同時，根據(jù)桶中記錄個數(shù)多少對hash桶降序排列. ② 定義組數(shù)θ，將包含k條記錄的等價類分為θ個組，每組應(yīng)包含k/θ條記錄，由于記錄數(shù)應(yīng)為整數(shù)，故對結(jié)果值向下取整為?k/θ」.從降序序列的前θ個桶中分別選取?k/θ」條敏感屬性互不相同且具有最小距離的記錄組成一個等價類.從θ個桶中選取記錄并確保記錄屬于不同類別，以保證記錄的組間相異性；每個桶中取?k/θ」條敏感屬性不同的記錄以保證組內(nèi)相似性；規(guī)定所選記錄滿足最小距離，目的在于減少泛化帶來的信息損失. ③ 重復(fù)上述過程，直至無法創(chuàng)建新的滿足(θ,k)-匿名模型的等價類，并將剩余記錄插入到與它距離最近的等價類中. ④ 泛化滿足(θ,k)-匿名模型的等價類，產(chǎn)生可用的匿名表.

2.2 (θ,k)-匿名模型算法的實現(xiàn)

算法： (θ,k)-匿名模型算法.

輸入：原始數(shù)據(jù)表T，hash桶個數(shù)m,等價類k值，組數(shù)θ；輸出：匿名數(shù)據(jù)表T′，T′中等價類滿足組內(nèi)敏感屬性相似，組間敏感屬性相異.

(1) 通過語義分析，確定敏感屬性有m個不同的類別，將數(shù)據(jù)表T依據(jù)語義層次樹劃分到m個hash桶中，每個hash桶代表不同的類別；

(2)E={ },j=1；whilem≥θ{

(3) 根據(jù)hash桶中包含記錄個數(shù)將hash桶降序排列；

(4) 選取降序序列中前θ個hash桶構(gòu)成集合H={h1,h2,…,hθ}；

(5) 從h1中隨機選擇一條記錄r；ej={r}；h1=h1-r；

(6) 從h1中選出距離r最近的一條記錄，并與ej中記錄比較，若屬性值不同，則將本條記錄加入到ej，并將其從h1中刪除，若相同則不做任何處理；重復(fù)此過程，直至從h1中選出?k/θ」條記錄；

(7) 在桶h2～hθ中重復(fù)(6)，依次從每個桶中取?k/θ」條記錄加入ej，并將記錄從原h(huán)ash桶中刪除；

(8) 若θ*?k/θ」

(9)E=E∪ej

(10)j++ } end while

(11) 將hi中剩余記錄插入到距離它最近的等價類中；

(12) 對等價類集合E中的每個等價類ej進行泛化，得到匿名數(shù)據(jù)表T′.

2.3 (θ,k)-匿名模型算法的分析

(θ,k)-匿名模型作用于具有敏感屬性的待發(fā)布數(shù)據(jù)表，目的是保護敏感數(shù)據(jù)，避免用戶隱私泄露.發(fā)布前，需要將數(shù)據(jù)表劃分為若干個等價類，以避免數(shù)據(jù)表發(fā)布后可能遭受的背景知識攻擊與相似性攻擊.當(dāng)前的匿名模型存在等價類中敏感屬性值相似的記錄分布不均現(xiàn)象，若敏感屬性值相似的記錄過多，則數(shù)據(jù)表難以抵制相似性攻擊；若記錄過少，則數(shù)據(jù)表難以抵制背景知識攻擊.數(shù)據(jù)表同時抵制兩種攻擊的關(guān)鍵是一個等價類中敏感屬性值相似的記錄個數(shù)既不過多，也不過少.為滿足等價類中敏感屬性的這一要求，本文提出的(θ,k)-匿名模型在劃分時將等價類分組，使記錄滿足在組內(nèi)的敏感屬性值相似，在組間的敏感屬性值相異，達到同時抵制背景知識攻擊與相似性攻擊的目的.

模型不僅適用于敏感屬性為具有語義關(guān)系的分類型數(shù)據(jù)，也適用于數(shù)值型數(shù)據(jù).對于數(shù)值型敏感屬性，可通過劃分?jǐn)?shù)值區(qū)間模擬分類型敏感屬性的語義關(guān)系從而構(gòu)造語義層次樹；對于分類型敏感屬性，通過語義分析構(gòu)建相應(yīng)的敏感屬性語義層次樹.

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

實驗的硬件環(huán)境為Intel(R) Core(TM) 3.70 GHz，i3-4170 CPU，16.0 GB RAM，軟件環(huán)境為Windows 7 64位旗艦版操作系統(tǒng)，虛擬機為vmware workstation，操作系統(tǒng)為ubuntu 14.04，算法開發(fā)語言為python 2.7.實驗數(shù)據(jù)來自北京市某醫(yī)院醫(yī)療數(shù)據(jù)庫系統(tǒng)，實驗中隨機選取符合要求的30 000條記錄進行實驗，選取{年齡，患病年限，性別，家庭住址，有無過敏史，婚姻狀態(tài)}作為準(zhǔn)標(biāo)識符，選取{疾病}作為敏感屬性.通過比較(θ,k)-匿名模型算法與傳統(tǒng)k-匿名模型算法、(p,k)-匿名模型算法對同一數(shù)據(jù)表的處理結(jié)果，對不同算法的抗攻擊性能、信息損失率、執(zhí)行效率進行分析，實驗中取p=3,θ=3.

3.1 抗攻擊性能比較

三種模型算法遭受背景知識攻擊與相似性攻擊的脆弱性如圖2、圖3所示.本文采用(θ,k)-匿名模型劃分等價類，分組后的等價類中記錄的敏感屬性包含數(shù)個不同的類別，每個類別下包含不同的敏感屬性值.在k值較小時，相對另外兩種模型，本模型效果優(yōu)勢明顯，由于k值小意味著每個等價類中包含的記錄個數(shù)較少，因此敏感屬性值的類別也相應(yīng)較少，等價類易遭受背景知識攻擊，此時若等價類中包含敏感屬性值相似度較高的記錄，則等價類易遭受相似性攻擊.(θ,k)-匿名模型對等價類分組，使等價類中敏感屬性值均勻分布，可更好地抵制兩種攻擊.k值增大意味著等價類中包含的記錄個數(shù)增多，因此敏感屬性值的類別也相應(yīng)豐富，此時三種匿名模型的背景知識攻擊脆弱性與相似性攻擊脆弱性均降低，代表其抵制攻擊的性能增強，盡管(θ,k)-匿名模型的脆弱性相比其他兩種模型仍然較低，但與另外兩種模型的差距有變小的趨勢.總的來說，相比于k-匿名模型與(p,k)-匿名模型，(θ,k)-匿名模型抵制背景知識攻擊與相似性攻擊的性能均有所提升，且在k值較小時效果更好.

圖2 背景知識攻擊脆弱性Fig.2 Vulnerability of background knowledge attack

圖3 相似性攻擊脆弱性Fig.3 Vulnerability of similarity attack

3.2 執(zhí)行效率與信息損失率分析

圖4、圖5反映了三種模型算法在k值改變時執(zhí)行效率與信息損失率的變化趨勢.可以看出，三種模型的耗時均隨著k值的增大而增多.一方面，k值增大，劃分等價類時需要處理的記錄個數(shù)增多，導(dǎo)致模型的耗時增多；另一方面，記錄增多導(dǎo)致泛化層次的增加，也導(dǎo)致模型的耗時增多.本文提出的(θ,k)-匿名模型由于需要在不同的hash桶中尋找滿足匿名要求的記錄，因此與k-匿名模型和(p,k)-匿名模型相比，耗時更多.同時，k值增大，記錄個數(shù)增多，等價類中需要泛化的準(zhǔn)標(biāo)識符數(shù)增多，泛化層次相應(yīng)增加，故三種模型算法的信息損失率均隨著k值的增大有所增加.(θ,k)-匿名模型在劃分等價類時增加分組操作，因此需要更長的執(zhí)行時間.但模型采用距離度量方法，保證同一等價類中滿足(θ,k)-匿名模型要求的記錄準(zhǔn)標(biāo)識符距離最小，更易于等價類中準(zhǔn)標(biāo)識符的泛化，可以有效減少不必要的信息損失.與k-匿名模型和(p,k)-匿名模型相比，(θ,k)-匿名模型信息損失的增長不超過2%.

圖4 三種算法的執(zhí)行效率Fig.4 Execution efficiency of three algorithms

圖5 三種算法的信息損失率Fig.5 Information loss of three algorithms

4 結(jié)束語

為更好地防止數(shù)據(jù)表發(fā)布后可能存在的隱私泄露，本文在現(xiàn)有k-匿名模型及其改進模型的基礎(chǔ)上提出了(θ,k)-匿名模型.將等價類中記錄分組，旨在對等價類中記錄的敏感屬性做出約束，保持等價類組內(nèi)記錄敏感屬性值相似，組間記錄敏感屬性值相異，使經(jīng)過模型處理后的數(shù)據(jù)表具備同時抵制背景知識攻擊與相似性攻擊的能力，從而降低用戶敏感信息泄露概率.模型不僅適用于敏感屬性為具有語義關(guān)系的分類型數(shù)據(jù)，也適用于可通過劃分區(qū)間模擬分類型數(shù)據(jù)語義關(guān)系的數(shù)值型數(shù)據(jù).為提高數(shù)據(jù)可用性，在劃分等價類時對記錄準(zhǔn)標(biāo)識符進行距離度量，在滿足(θ,k)-匿名模型的前提下，使等價類中記錄之間的距離最小，以降低泛化時的信息損失.實驗結(jié)果表明，在以保護隱私為主要目的的前提下，雖然(θ,k)-匿名模型犧牲了部分時間和信息損失，但同時抵制背景知識攻擊與相似性攻擊的性能得到改善.此外，由于本文只考慮了單一敏感屬性的隱私保護情況，如何保護具有關(guān)聯(lián)關(guān)系的多敏感屬性是下一步研究的方向.