程楠楠， 劉樹(shù)波， 熊星星， 蔡朝暉， 張家浩

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

0 引言

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

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

1.1 基本概念

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

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

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

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

例如，表1為原始數(shù)據(jù)表，經(jīng)過(guò)(p,k)-匿名泛化后得到表2的匿名數(shù)據(jù)表(p=6,k=6).若攻擊者已知被攻擊者屬于表2的等價(jià)類(lèi)，由于該等價(jià)類(lèi)中胃部疾病比例高達(dá)50%，因此攻擊者可認(rèn)為患者大概率患有胃部疾病，這種攻擊稱(chēng)之為相似性攻擊.若攻擊者根據(jù)背景知識(shí)得知被攻擊者患有骨科疾病，但不能明確具體的疾病值，根據(jù)表2中記錄，由于只有骨折為骨科疾病，因此攻擊者可推測(cè)出患者所患疾病為骨折，這種攻擊稱(chēng)之為背景知識(shí)攻擊.劃分等價(jià)類(lèi)時(shí)若記錄敏感屬性值語(yǔ)義相似的個(gè)數(shù)較多，等價(jià)類(lèi)易受相似性攻擊；若語(yǔ)義相似的個(gè)數(shù)較少，等價(jià)類(lèi)易受背景知識(shí)攻擊.對(duì)記錄敏感屬性值約束不足，導(dǎo)致數(shù)據(jù)表泛化后同時(shí)抵制兩種攻擊的性能不佳.本文提出(θ,k)-匿名保護(hù)模型，旨在通過(guò)分組優(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語(yǔ)義層次樹(shù)[13]：對(duì)數(shù)據(jù)表中的屬性值進(jìn)行語(yǔ)義分析得到語(yǔ)義層次樹(shù)，樹(shù)中根節(jié)點(diǎn)為屬性值全集，父節(jié)點(diǎn)為其葉子節(jié)點(diǎn)的泛化，葉子節(jié)點(diǎn)為父節(jié)點(diǎn)的子類(lèi).

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

圖1 疾病語(yǔ)義層次樹(shù)Fig.1 Disease semantic hierarchy tree

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

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

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

1.2 距離度量與信息損失計(jì)算

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

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

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

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

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

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

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

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

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

2 (θ,k)-匿名模型

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

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

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

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

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

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

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

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

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

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

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

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

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

(8) 若θ*?k/θ」

(9)E=E∪ej

(10)j++ } end while

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

(12) 對(duì)等價(jià)類(lèi)集合E中的每個(gè)等價(jià)類(lèi)ej進(jìn)行泛化，得到匿名數(shù)據(jù)表T′.

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 抗攻擊性能比較

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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