基于敏感度的個性化(α,l)-匿名方法

趙 爽,陳 力

(天津財經大學管理信息系統系,天津300222)

·安全技術·

基于敏感度的個性化(α,l)-匿名方法

趙 爽,陳 力

(天津財經大學管理信息系統系,天津300222)

目前多數隱私保護匿名模型不能滿足面向敏感屬性值的個性化保護需求,也未考慮敏感屬性值的分布情況,易受相似性攻擊。為此,提出基于敏感度的個性化(α,l)-匿名模型,通過為敏感屬性值設置敏感度,并定義等敏感度組的概念,對等價類中各等敏感度組設置不同的出現頻率,滿足匿名隱私保護的個性化需求。通過限制等價類中同一敏感度的敏感屬性值出現的總頻率,控制敏感屬性值的分布,防止相似性攻擊。提出一種基于聚類的個性化(α,l)-匿名算法,實現匿名化處理。實驗結果表明,該算法能以與其他l-多樣性匿名模型近似的信息損失量和時間代價,提供更好的隱私保護。

隱私保護;l-多樣性;敏感度;聚類;個性化;相似性攻擊

1 概述

隨著信息化時代的到來,數據的高共享和大容量存儲技術,便于各類機構收集和發布數據。其中大量數據與個體存在對應關系,這種對應關系往往會泄露人們的隱私信息,如收入水平、健康狀況、消費記錄等敏感信息。因此,如何在數據發布的過程中保護隱私信息成為當前研究的熱點,目前匿名化方法已成為隱私保護在數據發布方面的重要技術。

自1998年Samarati等人[1]提出匿名化以來,國內外專家對匿名化技術開展了廣泛研究。文獻[2]進一步對k-匿名模型進行了闡述,通過發布一定數量不可區分的個體,使攻擊者不能判別隱私信息所屬的個體,從而防止鏈接攻擊。文獻[3]在k-匿名的基礎上提出了l-多樣性(l-diversity)模型,對敏感屬性值的多樣性提出要求;文獻[4]提出(α,k)-匿名模型,對敏感屬性值的出現頻率提出要求;p-sensitivek-匿名模型[5]要求發布的數據滿足k-匿名的同時,還要求同一等價類中至少出現p個不同的敏感屬性值。這些在k-匿名基礎上改進的模型,可以有效防御k-匿名不能防御的一致性攻擊和背景知識攻擊。

然而以上研究,都沒有考慮不同個體對于同一敏感信息保護程度的差異,即沒有考慮隱私自治的需求。文獻[6]提出個性化匿名的概念以及解決相應問題的方法;文獻[7]分析了不同類型的個性化服務需求及相應的匿名模型;文獻[8]提出完全(α,k)-匿名模型,通過給各敏感值在等價類中設置不同的出現頻率來實現個性化保護;文獻[9]提出一種面向個體的個性化擴展l-多樣性隱私匿名模型。但這些研究大多只針對敏感屬性值的字面差異,而設置不同的約束條件,往往不能抵御相似性攻擊。

本文基于這些研究,定義了敏感度和等敏感度組的概念,考慮到敏感屬性值之間的語義相似關系,提出一種基于敏感度的個性化(α,l)-匿名模型,該模型在滿足l-多樣性原則的同時,通過為不同的敏感度設置不同的α頻率約束來實現隱私匿名的個性化要求,并且通過控制敏感屬性值在等價類中的分布,避免相似性攻擊。給出基于局部泛化的貪心聚類算法能減少信息損失量,個性化的約束條件也可使數據可用性更高。

2 基本概念和問題定義

2.1 基本概念

數據表中包含的屬性按功能分為以下3類[10]:

(1)標識符:即惟一標識個體身份的屬性,如姓名、身份證號等,一般標識符在發布時,都會直接刪除來保護隱私;

(2)準標識符:與其他數據表進行鏈接以標識個體身份的屬性或屬性組合,如出生日期、性別、種族等。準標識符取決于進行鏈接的外表,不同的外表,準標識符的選擇不同;

(3)敏感屬性:描述個體隱私信息的屬性,如診斷結果、健康狀況、收入水平等。

定義1(k-匿名) 數據表T包含n個屬性,設QI是T的準標識符,T[QI]表示T在QI上的投影,當且僅當在T[QI]上出現的每組值至少要在相應的投影上重復出現k次,則稱T滿足k-匿名。

定義2(等價類) 如果數據表T滿足k-匿名,則把T中在準標識符上具有相同值的元組的集合,稱作等價類。

由此可得,k-匿名表中的每個等價類的大小至少為k,攻擊者以準標識符與外表進行鏈接時,至少能對應到k個不同的個體,就無法判別出個體與敏感屬性的對應關系,因此,k-匿名可以防御鏈接攻擊。然而,k-匿名并沒有對敏感屬性進行約束,同一敏感屬性值可能集中出現在一個等價類中,這樣即使滿足k-匿名,攻擊者也很容易能直接或憑借已知的相關知識推理出敏感屬性值與個體的對應關系,k-匿名易受到一致性攻擊和背景知識攻擊[11]。l-diversity模型和(α,k)-匿名模型在此基礎上進行了改進。

定義3(l-diversity模型) 如果一個等價類中所含不同敏感屬性值的個數大于等于l(l≥2),則稱該等價類滿足l-diversity原則。如果給定數據表T,經泛化后得表T′,其中每個等價類都滿足l-diversity原則,則稱T′滿足l-diversity模型。

定義4((α,k)-匿名模型) 給定數據表T,經泛化后得表T′,若T′滿足k-匿名的同時,每個等價類中任何一個敏感屬性值出現的頻率小于等于α(0＜α＜1),則稱T′滿足(α,k)-匿名模型。

2.2 問題定義

定義5(相似性攻擊) 在同一等價類中,敏感屬性值雖然字面上存在差異,但語義上相似或相近,攻擊者可以通過這些語義相似的敏感屬性獲得個體隱私信息的大體范圍。

l-diversity模型和(α,k)-匿名模型雖然對敏感屬性進行了約束,卻忽略了敏感屬性值的語義相似關系,尤其是針對一些“高危相似”的敏感屬性值,若都集中分布在一個或幾個等價類中,就會給個體造成較嚴重的隱私泄露。當然,對于那些“非高危”的敏感屬性值,可以降低對其的保護程度。匿名模型應該根據個體對敏感屬性值的保護程度,對不同的敏感屬性值設定不同的約束條件,從而減少過度保護帶來的信息損失。

例如,表1所示的原始診斷結果,當編號8,9,10的3條記錄經泛化后組成一個等價類時,若設l=3或α=0.4,該等價類雖然是符合約束原則的,但“骨癌、肺癌、胃癌”都屬于語義相似的“高危”敏感屬性值,攻擊者如果確定某個體在該等價類中,就可以推測其患了較重的癌癥,同樣造成隱私泄露。但對于“流感”等被保護的需求程度普遍較低的敏感屬性值,即使被攻擊者推斷出大致范圍,對多數個體來說也是可以接受的。

表1 原始診斷結果

因此,應該從控制敏感屬性值的分布入手,同時為不同的敏感屬性值設定不同的約束條件,提出既能防止相似性攻擊又能滿足個性化需求的匿名模型。

3 基于敏感度的個性化(α,l)-匿名模型

3.1 個性化隱私保護

對于個性化隱私保護的模型,一般分為面向個體和面向敏感屬性值[7],面對龐大的數據量,如果為每個個體設置約束條件,將產生巨大的工作量,因此面向個體的個性化隱私保護模型具有一定的局限性。而面對敏感屬性值的保護模型中,由于不同敏感屬性值的敏感程度有很大差別,就需要為不同的敏感屬性值提供不同的保護程度。

定義6(敏感度) 設數據表T中的敏感屬性為S,si表示S中的敏感屬性值,根據si需要被保護的程度,為其設定敏感級別,將敏感級別數值化后相應的值稱作si的敏感度,記作Di(0＜Di＜1)。si需要被保護的程度越高,敏感級別越高,Di越大。由此給表1中疾病屬性的不同敏感值設敏感度,如表2所示。

表2 疾病敏感度

定義7(等敏感度組) 將具有相同敏感度的敏感屬性值所在的元組構建的集合,稱作等敏感度組,記作SD,|SD|表示組內所含元組的個數,等敏感度組的敏感度即為該組中敏感屬性值的敏感度。例如,由表1、表2可知,編號8、編號9、編號10的元組組成了一個SD,且|SD|=3,該組的敏感度為0.7。

3.2 個性化(α,l)-匿名模型

定義8基于敏感度的個性化(α,l)-匿名模型,給定數據表T,經泛化后得表T′,若T′滿足ldiversity,且每個等價類E中任一等敏感度組SDi都滿足,其中,αi=1-Di,|E|表示等價類E中的元組個數,則稱數據表T′滿足基于敏感度的個性化(α,l)-匿名模型。

例如,將原始表1經泛化匿名后得到表3,其中包括3個等價類,按照表2設定的敏感度并要求l=2,第1個、第2個等價類都符合該模型,在第3個等價類中,由{肺癌,骨癌}組成的等敏感度組的敏感度為0.7,由αi=1-Di得,該等敏感度組中的元組出現頻率應該小于等于0.3,而實際的0.3,不符合該匿名模型,因此,表3不是符合基于敏感度的個性化(α,l)-匿名的匿名數據表。

表3 泛化匿名后的診斷結果

4 基于敏感度的個性化(α,l)-匿名算法

4.1 信息損失的度量

在匿名化過程中,數據處理會產生一定量的信息損失,信息損失的度量作為評價數據可用性的指標,也用于衡量匿名化算法的優劣并指導其策略[12]。本文通過構造加權確定性代價模型,表示數據處理過程中所產生的信息損失量。

定義9(泛化層次) 在對屬性值泛化的過程中,通常將泛化層次樹作為泛化規則。設屬性A的泛化層次樹為TA,RA表示根節點,LA表示葉節點的集合,層次樹由最底層的LA按分類關系,依層向上遞增直到RA。當屬性A為數值型時,TA表示域泛化的規則,圖1表示“年齡”屬性的層次泛化樹;當屬性A是分類型時,TA表示值泛化的規則,圖2表示“省份”屬性的層次泛化樹。

圖1 “年齡”屬性的層次泛化樹

圖2 “省份”屬性的層次泛化樹

定義10(屬性值的信息損失) 對于屬性A,用確定性代價模型度量其屬性值被泛化到s的信息損失量,記作NCPA(s):

若A為數值型屬性,則NCPA(s)其中,Range(s)表示屬性值s的區間大小;Range(RA)表示屬性A的值域。

若A為分類型屬性,則其中,Sub(s)表示以s為根節點的子樹中所含葉節點的集合;表示該集合的大小。

定義11(元組的信息損失) 對于包含n個屬性的元組t,用加權確定性代價模型度量其信息損失量,記作NCP(t):

其中,wi表示屬性Ai的權重;NCPAi(t.Ai)分為數值型和分類型分別計算。

定義12(總信息損失) 對于聚類形成的聚簇e,進行泛化處理所產生的信息損失NCP(e)定義為:

對于匿名表T′,設E為T′中等價類的集合,則T′的總信息損失NCP(T)定義為:

4.2 個性化(α,l)-匿名算法

本文提出一種基于敏感度的個性化(α,l)-匿名算法,該算法以滿足敏感度個性化(α,l)-匿名模型為約束,通過基于貪心策略的聚類算法,將數據集分成若干聚簇后進行局部泛化,過程中以信息損失最小化為目標。

該算法具體思路是:

(1)根據不同敏感屬性值將數據集分成若干元組集合,同一集合中的元組具有相同的敏感屬性值,那么每個元組集合都有相應的敏感度,將各元組集合按敏感度由高至低排列。

(2)從非空最高敏感度的元組集合中任選一個元組作為原型,然后按照敏感度由低到高的順序,依次從1個～l個非空元組集合中各抽選一個元組從而建立l-多樣性聚簇。每次抽選的元組,要使得新形成的聚簇滿足:1)基于敏感度的個性化(α,l)-匿名模型;2)增加的信息損失量最小。

(3)重復操作步驟(2),形成若干聚簇,直到非空元組集合的數量不足 l,或剩余元組不符合步驟(2)中的抽選約束。

(4)將剩余元組按照步驟(2)中的約束插入到已有聚簇中,再將無法插入的元組進行隱匿。

(5)對每個聚簇的準標識符進行泛化處理,形成若干等價類,產生符合匿名條件的數據表。

算法基于敏感度的個性化(α,l)-匿名算法

輸入原始數據表T,敏感屬性值的敏感度表,多樣性參數l,屬性權重wi

輸出滿足基于敏感度的個性化(α,l)-匿名的數據表T′

步驟:

(1)計算數據表T中敏感屬性值個數n,若n＜l,則返回重新設置多樣性參數l;

(2)根據敏感屬性值si將數據表T分為若干元組集合ti(i=1,2,…,n),將這些集合按相應的敏感度Di降序排列為:t1,t2,…,tn;

(3)按照i從1～n的順序,對每個元組集合ti,循環:

如果ti為非空集,且非空元組集合的總數大于等于l,循環:

1)從ti中任選一條記錄r;

2)準聚簇e′={r};

3)按照敏感度由低到高的順序,依次從1個～l個非空元組集合中各抽選一條記錄,加入準聚簇e′,使e′滿足基于敏感度的個性化(α,l)-匿名的要求且增加的信息損失最小;

4)如果步驟3)可執行:將準聚簇e′作為聚簇e加入聚簇集,將抽選的記錄從相應的的原元組集合中刪除;否則將準聚簇e′清空,將抽選的記錄保留在相應的原元組集合中。

(4)如果存在非空的元組集合,循環:

1)從非空ti中任選一條記錄r;

2)選取聚簇集中的一個聚簇e,使r加入其后仍滿足基于敏感度的個性化(α,l)-匿名的要求且增加的信息損失最小;

3)如果步驟2)可執行e=e∪{r},ti=ti-{r};否則將r做隱匿處理。

(5)返回聚簇集,對其中各聚簇e做準標識符的泛化處理,形成符合條件的匿名表T′。

5 實驗結果及分析

5.1 實驗數據及參數

實驗采用UCI機器學習數據庫中的Adult數據集,該數據集由美國人口普查數據構成,經過刪除缺省值處理后,包含45 222條記錄,本文選取其中的7個屬性,將Occupation作為敏感屬性,其他6個屬性為準標識符,數據集結構設置見表4,對敏感屬性Occupation的14個敏感屬性值設置敏感度見表5。

表4 Adult數據集結構

表5 敏感屬性值的敏感度設置

實驗從信息損失度與執行時間2個方面進行分析,將本文算法與文獻[3]中基于全域泛化的l-多樣性匿名算法以及文獻[13]中l-clustering聚類算法進行比較,實驗運行環境為 Intel Core(TM)2 Duo CPU@1.80 GHz,2.00 GB內存,操作系統為Microsoft Windows XP,環境為Visual C++6.0與Matlab7.0。

5.2 信息損失度分析

數據表的信息損失按定義7中總信息損失NCP(T)的式子度量,當準標識符屬性個數為6、元組數為45 222且l值變化時的3種匿名算法的信息損失量的比較,如圖3所示。由此可知,3種算法的信息損失度會隨著l值的增大而增加,因為l值越大,生成聚類所含元組的個數增多,對元組泛化的程度會更高,從而引起更多的信息損失。另外,本文算法與l-clustering聚類算法信息損失度相近,相對于l-多樣性算法都產生較小的信息損失。因為l-多樣性算法采用全域泛化策略,其信息損失通常要遠高于局部泛化策略。可見,本文算法以與l-clustering算法類似的信息損失量獲得可以防御相似性攻擊的個性化隱私保護。

圖3 不同l值下各匿名算法的信息損失度

5.3 執行時間分析

當準標識符屬性個數為6、數據集大小為45 222且l值變化時,3種匿名算法的執行時間比較,如圖4所示。由此可知,3種算法的執行時間會隨著l值的增大而增加,因為當l值增大時,等價類中的元組數、聚類次數、泛化次數、執行時間也都相應增加。另外,本文算法與l-clustering聚類算法執行時間相近,都高于l-多樣性算法的執行時間,但為了更好地實現個性化隱私保護,本文算法的時間開銷是可接受的。

圖4 不同l值下各匿名算法的執行時間

6 結束語

本文針對敏感屬性值個性化隱私保護的需求以及l-多樣性匿名模型不能解決的相似性攻擊問題,提出基于敏感度的個性化(α,l)-匿名模型。該模型通過為敏感屬性值設置敏感度,并對等價類中各等級敏感度組的出現頻率按照敏感度進行設置,來實現隱私匿名的個性化需求。此外,本文在敏感度的基礎上提出等敏感度組的概念,通過限制等價類中同一敏感度的敏感屬性值出現的總頻率,控制敏感屬性值的分布,防止相似性攻擊。本文還提出個性化(α,l)-匿名算法,通過基于聚類的局部重編碼策略進行匿名化處理,有效地實現了基于敏感度的個性化(α,l)-匿名模型。實驗結果表明,該算法與傳統基于聚類的l-多樣性算法有相似的信息損失度和執行效率,在可接受的時間開銷下,信息損失量明顯小于全域泛化的l-多樣性算法,且更有效地實現了個性化隱私保護。

由于本文只是針對單一的敏感屬性值,因此今后將探討在多敏感屬性值情況下對敏感度的設定和分組,以及多敏感屬性值的個性化隱私保護等問題。

[1] Samarati P,Sweeney L.Generalizing Data to Provide Anonymity When Disclosing Information[C]// Proceedingsofthe 17thACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems.New York,USA:ACM Press,1998:188.

[2] Sweeney L.K-anonymity:A Model for Protecting Privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5):557-570.

[3] Machanavajjhala A,GehrkeJ,KiferD.I-diversity: Privacy Beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):24-35.

[4] Wong R,Li J,Fu A,et al.(α,k)-anonymity:An Enhanced k-anonymity Model for Privacy Preserving Data Publishing[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2006:754-759.

[5] Traian T M,Bndu V.Privacy Protection:p-sensitive kanonymity Property[C]//Proceedings of the 22nd International Conference on Data Engineering Workshops. Washington D.C.,USA:IEEE Computer Society,2006: 94-103.

[6] Xiao Xiaokui,Tao Yufei.Personalized Privacy Preservation[C]//Proceedings of ACM SIGMOD Conference on Management of Data.Chicago,USA:ACM Press, 2006:229-240.

[7] 王 波,楊 靜.數據發布中的個性化隱私匿名技術研究[J].計算機科學,2012,39(4):168-171.

[8] 韓建民,于 娟,虞慧群,等.面向敏感值的個性化隱私保護[J].電子學報,2010,38(7):1723-1728.

[9] 王 波,楊 靜.一種基于逆聚類的個性化隱私匿名方法[J].電子學報,2012,40(5):883-890.

[10] 周水庚,李 豐,陶宇飛,等.面向數據庫應用的隱私保護研究綜述[J].計算機學報,2009,32(5):847-858.

[11] 王平水,王建東.匿名化隱私保護技術研究進展[J].計算機應用研究,2010,27(6):2016-2019.

[12] 朱 拯,王智慧,汪 衛.基于個人隱私約束的k-匿名模型[J].計算機研究與發展,2010,47(21):271-278.

[13] 王智慧,許 儉,汪 衛,等.一種基于聚類的數據匿名方法[J].軟件學報,2010,21(4):680-693.

編輯 陸燕菲

Personalized(α,l)-anonymity Method Based on Sensitivity

ZHAO Shuang,CHEN Li
(Department of Management Information Systems,Tianjin University of Finance&Economics,Tianjin 300222,China)

Currently,the majority of anonymity model for privacy preservation neither meets the need of personalized preservation oriented to sensitive attribute values,nor considers the distribution of sensitive attribute values,therefore they are vulnerable to similarity attack.This paper proposes a personalized(α,l)-anonymity model based on sensitivity.This model provides sensitivity for different sensitive attribute values,and defines the concept of equ-sensitivity group, implements the personalized needs of privacy anonymity by setting the frequency constraints for different equ-sensitivity group in every equivalence class.This model also can defense similarity attack by limiting the total frequency of sensitive attribute values for same sensitivity in every equivalence class,and control the distribution of sensitive attribute values. This paper proposes a personalized(α,l)-anonymity algorithm based on clustering to achieve the purpose of anonymity. Experimental results show that the proposed algorithm provides better privacy preservation than otherl-diversity anonymity models with the similar information loss and time cost.

privacy preservation;l-diversity;sensitivity;clustering;personalized;similarity attack

1000-3428(2015)01-0115-06

A

TP309.2

10.3969/j.issn.1000-3428.2015.01.021

趙 爽(1989-),女,碩士研究生,主研方向:信息安全;陳 力,副教授。

2014-08-13

2014-09-09 E-mail:zhaoshuang_tjufe@163.com

中文引用格式:趙 爽,陳 力.基于敏感度的個性化(α,l)-匿名方法[J].計算機工程,2015,41(1):115-120.

英文引用格式:Zhao Shuang,Chen Li.Personalized(α,l)-anonymity Method Based on Sensitivity[J].Computer Engineering,2015,41(1):115-120.