基于敏感屬性值泄露個數期望的匿名模型
2009-01-01 00:00:00王茜屈盛知石香靈
計算機應用研究 2009年3期
(重慶大學 計算機學院，重慶 400044)
摘 要：當前K匿名成為解決隱私保護的重要模型，但其不能解決同質攻擊造成的屬性泄露。對K匿名模型進行了擴展，提出一種新的基于敏感屬性值泄露個數期望的匿名模型，該模型能很好地解決屬性泄露問題，同時通過實驗證明了該模型的可行性。
關鍵詞：K匿名； 隱私保護； 匿名化； 期望
中圖分類號：TP309.2 文獻標志碼：A
文章編號：10013695(2009)03110903
Anonymity model based on expectation of sensitive attribute value
WANG Qian， QU Shengzhi， SHI Xiangling
(College of Computer Science， Chongqing University， Chongqing400044， China)
Abstract:KAnonymity is an important model in the area of privacy protection， however， it is useless for the attribute disclosure made by the homogeneity attack. This paper extended a new model based on expectation of sensitive attribute value， which could deal with the attribute disclosure well.And it is also showed to be feasible by experiments.
Key words：Kanonymity; privacy preservation; anonymilization; expectation
0 引言
隨著互聯網技術的不斷發展，人們進入到信息高度共享的時代，同時越來越多的個人信息被持有，由此造成的隱私信息泄露成為亟待解決的問題，且這個問題變得越來越艱巨。比如，藥店根據就診記錄推斷出一些患者的具體信息，包括姓名、性別、電話，甚至所患疾病，對這些人進行藥物推銷，嚴重威脅到這些病人的隱私。
當前網絡發展應用中出現的大量隱私破壞行為使得隱私保護技術的研究受到高度重視。其中一種稱為自由訪問型隱私保護，該類型處理的隱私是對外公開的，任何人都可以訪問，其核心是保護數據和個人的對應關系。從攻擊者的角度來看，攻擊的目標是隱私數據和個人的對應關系[1]，主要的攻擊方法是鏈接攻擊(linking attack)[2]。最近一份研究報告顯示，87％的美國人可以通過這種方法被惟一確定[3]。隨著數據倉庫和數據挖掘技術的成熟，自由訪問型隱私保護正成為當前信息安全學界的一個熱門研究課題[4]。其中K匿名模型思想直觀簡單，并能有效地保護個人隱私，近年來被廣泛運用。
1 相關工作
在數據發布的過程中，為了避免直接的隱私泄露，發布者把個人數據中顯示標志符，如姓名、身份證號等除去，但遺憾的是攻擊者利用鏈接攻擊結合外部數據源仍可以獲得隱私信息。為了避免發布數據中隱私泄露，一些保護技術在早期數據發布中被運用，如數據交換、添加噪聲、數據擾亂、隨機化等[5]，這些技術雖然可以在一定程度上保護隱私，但同時造成的數據失真使得發布的數據失去價值。
L.Sweeney[2]提出的K匿名模型對于防止鏈接攻擊起到了一定的作用，但許多學者發現K匿名對于同質攻擊不起作用[3]，它只能防止身份泄露，不能防止屬性泄露。同時匿名化也造成一定的信息損失，如何在信息損失和隱私保護之間達到很好的平衡，成為研究的熱點問題。研究證明，獲得最優的K匿名化數據集是NPhard問題[6]。
定義1 準標志符(quasiidentifiers)。給定實體集合U、實體表T(A1，A2，…，An)，fc:U→T 以及fg:T→U′。其中UU′。表T的準標志符QI為屬性組(A1，A2，…，Aj)。其中pi∈U且滿足fg(fc(pi[QI]))= pi。
定義2 K匿名。給定數據表T(A1，A2，…，An)，QI是與T相關聯的準標志符，當且僅當在T[QI]中出現的每個值序列至少在T[QI]中出現K次，則T滿足K匿名。T[QI]表示T表元組在QI上的投影。
依據定義2，滿足K匿名的數據表中，任何個體被惟一確定的概率最多為1/K。
信息的泄露分為身份泄露和屬性泄露。身份泄露主要是指個體被惟一確認，而屬性泄露主要指從所給個人信息中推出了新的信息。K匿名可以防止身份泄露，但不能防止屬性泄露。
為了應對屬性泄露，許多新的模型被提出。比如Idiversity[3]要求任何一個等價組中至少有I 個表現較好的值，(α，k)anonymity[7]要求等價組中任何一個敏感屬性值的頻率不超過α；Psensitive kanonymity[5]則要求同一等價組中任何敏感屬性至少有p個不同值。這些新的模型在一定程度上解決了屬性泄露問題，但均要求任何等價組都必須滿足要求，很容易造成過度泛化。為解決此問題，本文把K匿名模型推廣為基于敏感屬性值泄露個數期望的匿名模型，該模型不是強調所有等價組都滿足一定的條件，而是要求敏感屬性值泄露個數的期望達到一定的要求。因為期望值反映的是整體等價組的情況，而不是某個具體的等價組，實驗證明它能很好地防止過度泛化。同時該模型運用了貪婪思想，因為貪婪法是一種不追求最優解，只希望得到較為滿意解的方法，避免了找最優解要窮盡所有可能而耗費大量時間。
2 基于敏感屬性值泄露個數期望的匿名模型
匿名化后的數據集不僅滿足K匿名，同時敏感屬性值泄露個數的期望值不大于給定的某個值E。為簡單起見，本文假設只有一個敏感屬性的一個敏感值為s需要保護，共有x個等價組，a個s值，各匿名組共有元組數x1，x2，…，xx，對應的s值分別為a1，a2，…，ax，a =xi=1ai，那么當前s值泄露個數的期望值為
E′=a1×a1/x1+a2×a2/x2+…+ ax×ax/xx=xi=1ai/xi×ai
且E′＜ E時滿足條件。
定理1 敏感屬性值泄露個數期望值隨著屬性的泛化非增。
若無等價組合并，則K不變，易證E也不變，要想K增大，必然有等價組的合并。下面證明等價組合并過程中E值非增。
證明 數學歸納法
a) 假設有兩個等價組，依上述定義E1=a1×a1/x1+a2×a2/x2，泛化后兩等價類成為一個等價類，故此時的期望值為E2=(a1+a2)×[(a1+a2)/(x1+x2)]，那么易得
E1-E2=(a1x2-a2x1)2/[x1x2(x1+x2)]
因為x1， x2≥0， 所以E1≥E2恒成立。
b) 假設有x-1個等價組時成立，即
a1×a1/x1+a2×a2/x2+…+ax-1×ax-1/xx-1≥(a1+a2+L+ax-1)2/(x2+x2+…+xx-1)
c) 下面證明當有x個等價組時也成立，即證明:
a1×a1/x1+a2×a2/x2+…+ax×ax/xx≥
(a1+a2+L+ax)2/(x1+x2+…+xx)
[(a1+a2+…+ax-1)×xx-(x1+x2+…+xx-1)×ax]2≥0
得證。故任何等價類合并后其E值不大于原來值。
定理2 期望值的取值范圍為(a2/xi=1xi，a）。
證明 當泛化到最高層次時，等價組個數為1，此時的敏感值個數為a，每個敏感值泄露的概率為a/xi=1xi，故此時泄露的期望為a2/xi=1xi。每個等價組中只有一條記錄時，泄露期望為a=xi=1ai。
2.1 實現K匿名的方法
泛化(generalization)，即給定一個屬性 A，每次用概括值來代替原來值，使其意義更加廣泛[8，9]。A0 →A1→…→An表示一個泛化序列，用DGHA(domain generalization hierarchy on A)表示屬性A的域泛化等級。
2.2 泛化信息損失
用QIi表示準標志符QI的第i個屬性，VQIi表示QIi的一個值，用domain(VQIi)表示VQIi所在的域，用num(domain(VQIi))表示VQIi所在域中屬性值的個數，containNum(VQIi)表示泛化樹中VQIi包含的屬性值個數，則VQIi泛化到VQIi的信息損失量為
loss(VQI′i)=(containNum(VQI′i)-1)/[num(domain(VQIi))]
泛化格lattice(node，edge)中，從nodei到nodej信息損失量。
loss(nodej)=(1-WQIi)nx=1Loss(VQI′i)x
其中：VQI′i是nodej中的一個值；n為總數；WQIi是QIi重要性的權重，且WQIi∈[0，1]。
3 泛化算法
基于敏感屬性值泄露個數期望的匿名模型思想：首先為每個準標志符建立泛化樹及泛化格lattice(node，edge)，自泛化格最底部節點運用貪婪思想而上[10]，搜索信息損失最小的節點泛化，直到達到所設置的K值和期望值E。
算法描述：
輸入：原始數據集table(node0)，匿名參數K，敏感屬性值泄露個數期望E， node0為泛化格最底層的節點。
輸出：滿足K匿名和E值的數據集。
步驟：
table= table(node0);
H=泛化格高度;
while(int i=0;i if(e≤Ek≥K) break;//e、k分別為當前的期望和K值 else{i++; Node node=new Node(); for(int n=0;n //N為當前節點對應下一個節點的個數 if(loss(noden // LOSS為一個很大的數; node= noden;} return table(node); } 4 實驗 4.1 實驗環境 4.1.1 數據集 實驗數據來自 UC Irvine Machine Learning Repository的Adult數據庫Ｉ[11]，是研究 K匿名的常用數據庫，數據庫大小為 5.5 MB。本文選取其中的21 411個元組及5個屬性，最后一個屬性作為敏感屬性，如表1 所示。 4.1.2 實驗軟/硬件環境 硬件環境：Intel Celeron CPU 2.0 GHz、512 MB SDRAM 內存。 操作系統：Microsoft Windows XP。 編程環境：Eclipse+Hibernate+Microsoft SQL Server 2000。 4.2 執行時間分析 圖1 給出了執行時間和K、E之間的關系。從圖中可以看出，隨著K的增加在E不變的情況下執行時間遞增，因為K增加，需要更高層次的泛化。同時相同K情況下，E越小，其執行時間就越長，因為E越小，屬性泄露越少，就需要泛化更多的層次，時間增加。 4.3 數據精確度分析 圖2給出了數據的精確度[8，12]和K、E的關系。從圖中可以看出，精確度在E相同的情況下隨著K的增加而減小， K越大，泛化層次越高，數據損失量就越多。同時在K相同的情況下，E越大，數據精確度越高，造成屬性泄露的越多，泛化程度越低，損失量就越小。 5 結束語 本文針對K匿名不能防止屬性泄露提出了一種新的基于敏感屬性值泄露個數期望的匿名模型，給出了形式化描述并分析了期望的取值范圍。通過控制敏感屬性值泄露個數期望，防止屬性泄露。實驗證明，該模型具有較好的可行性，必將為防止隱私泄露提供更好的技術保護。簡單起見，本文僅有一個敏感屬性，且一個需保護的敏感屬性值。今后將進一步驗證一個敏感屬性多個需保護的敏感屬性值，以及多敏感屬性多需保護的敏感屬性值的情況。 參考文獻： ［1］劉喻，呂大鵬，馮建華，等.數據發布中的匿名化技術研究綜述［J］.計算機應用，2007，27(10):23612364. [2]SWEENEY L. Kanonymity: a model for protecting privacy[J].International Journal on Uncertainty， Fuzziness and Knowledgebased Systems，2002，10(5):557570. [3]MacHANAVAJJHALA A，GEHRKE J，KIFER D.Ldiversity: privacybeyond Kanonymity[C]// Proc of International Conference on Data Engineer(ICDE’06).2006. [4]BERTINO E，BYUN J，LI Ninghui. Privacypreserving database systems[M].Berlin:Springer，2005:178206. [5]TRUTA T M，VINAY B.Privacy protection:psensitive Kanonymity property[C]// Proc of the 22nd International Conference on Data Engineering Workshops.Washington DC: IEEE Computer Society， 2006. [6]MEYERSON A，WILLAMS R.On the complexity of optimal Kanonymity[C]// Proc of the 3rd ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems.New York:ACM Press， 2004:223228. [7]WONG Chiwing，LI Jiuyong，WANG Ke，et al.(alpha，k)Anonymity:an enhanced Kanonymity model for privacy preserving data publishing[C]// Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press，2006:754759. [8]羅紅薇. 防止隱私泄露的K匿名研究[D]. 秦皇島:燕山大學，2007. [9]SWEENEY L. Achieving Kanonymity privacy protectionusing generalization and suppression[J].International Journal on Uncertainty，Fuzziness and Knowledgebased Systems，2002， 10(5):571588. [10]WANG Ke，YU P S， CHAKRABORTY S. Bottomup generalization:a data mining solution to privacy protection[C]// Proc of the 4th IEEE International Conference onData Mining. Washington DC:IEEE Computer Society，2004:249256. [11]HETTICH C B S，MERZ C.UCI repository of machine learning databases [EB/OL]. (19960501) [20080420]. http://archive.ics.uci.edu/ml/datasets/Adult. [12]羅紅薇，劉國華.保護隱私的(L，K)匿名[J].計算機應用研究，2008， 25(2):526528.
