摘 要： 在K-匿名模型的基礎上提出了(s，d)-個性化K-匿名隱私保護模型，該模型能很好地解決屬性泄漏問題，并通過實驗證明了該模型的可行性。
關鍵詞： K-匿名；隱私保護；個性化；屬性泄漏
隨著互聯網技術的飛速發展，基于網絡的虛擬社會逐步形成，信息的收集、加工、傳播更加快捷。現代社會是信息高度共享的社會，使得數據庫安全問題日益突出，其中對數據的竊取、篡改和破壞直接危害著數據庫的安全，成為亟待解決的問題。隨著數據挖掘技術的興起，大量的信息如：病人就診信息、學生學籍信息、員工工資及檔案信息等面臨著泄漏的風險。對個人、企業甚至國家的危害是不容小覷的，個人信息的泄露容易造成詐騙的發生；企業和國家信息的泄露容易造成國家機密的暴露，直接危害國家安全。
自由保護型的數據庫隱私保護處理的隱私信息是對外公開的，所有人都可以使用，主要保護隱私信息和個人的對應關系[1]。即攻擊者可以輕松獲取數據庫中的記錄，攻擊的目標是某條隱私信息和某個體的一對一關系。典型的攻擊方法是鏈接攻擊(Linking Attack)[2]。
1 K-匿名技術
較好地解決鏈接攻擊的方法是參考文獻[2]中Samarati和Sweeney引入的K-匿名機制。它要求公布后的數據中存在一定數量的不可區分的個體，從而使攻擊者無法判斷出敏感屬性的具體個數，以此達到保護個人隱私的目的。為了使數據表滿足K匿名性質，需要對原始表在準標識符上進行加工，如采用抑制或者泛化技術。
K-匿名技術通過生成若干等價組，使等價組內QI屬性和隱私屬性不再是一一對應的關系，從而保證了個人隱私信息不被泄露。等價組的概念為：在準標識符上的投影完全相同的、記錄組成的記錄集合，即等價組內所有的記錄在準標識符上的屬性值完全相同，但是其他屬性可以不同。
定義1 K-匿名。給定數據表A(B1，B2，……Bn)，QI是與A相關聯的準標識符，當且僅當在A[QI]中出現的每個值序列至少在A[QI]中出現K次，則A滿足K-匿名。A[QI]表示A表中的元組在QI上的投影[3]。
表1為原始數據表，其中年齡、性別、地區編碼為準標識符，疾病為敏感屬性，沒有任何可以唯一標識個體身份的屬性存在，如身份證號碼、姓名等。經過3-匿名化處理后如表2所示，每一條記錄都有另外兩條記錄在準標識符上與其相同。即使攻擊者知道某條記錄在表2中，也無法確定哪條記錄與其對應，但這樣并不能完全防止隱私泄露。因此參考文獻[3]提出了1-多樣性概念，即把等價組內出現頻率最高的敏感屬性限制在1/1以內。p-sensitive K-匿名模型[4]是在K-匿名模型的基礎上要求每個等價組內至少要有p個不同的敏感屬性值，在一定程度上抵御了屬性泄漏問題，但是當K值很大的時候就表現得不是很好。(a，k)-匿名模型[5]限制了等價組內敏感屬性出現的頻率不高于a，在一定程度上防止了一致性攻擊，但是它對所有敏感屬性采用相同的約束，無法達到實用的目的。參考文獻[6]提出了一種不基于概括和隱匿的新方法——Anatomy，通過將原始關系的準標志符屬性和敏感屬性以兩個不同的關系發布，利用它們之間的有損連接保護隱私數據的安全。這些模型都沒有考慮敏感屬性敏感度問題，而且無法抵御背景知識攻擊。
2 (s，d)-個性化K-匿名隱私保護模型
K-匿名的主要缺陷：(1)K-匿名沒有考慮到匿名后可信屬性由于缺乏多樣性而導致的隱私泄露問題(同質性攻擊)；(2)默認所有屬性都有相同的重要性；(3)不能抵御背景知識攻擊。
本文介紹的(s，d)-個性化K-匿名隱私保護模型就是為了解決這些問題而提出來的。在介紹(s，d)-個性化K-匿名隱私保護模型前需要給出的定義：s-相似等價組、臨界敏感度、高危敏感度、d-非關聯約束。
定義2 s-相似等價組。是指在敏感屬性值上相似的至少s個記錄組成的等價組，在這里相似的定義根據具體的應用會有所不同。例如：如果敏感信息是疾病，則可以將病變器官作為相似劃分標準，如胃部疾病，肝部疾病等。
定義3 臨界敏感度。由專家確定或者根據具體應用領域靈活確定的、能夠較好體現對敏感屬性保護程度的一個數值度量，其值在0~1之間。
定義4 高危敏感度。高危敏感度是指敏感屬性值的敏感度大于、等于臨界敏感度，其值在0~1之間。
定義5 d-非關聯約束。對于s-相似等價組E，在E中高危敏感度屬性值出現的頻率f不高于d，即|f|/|E|<d(0≤d≤1)，其中d是用戶確定的參數。但其必須滿足d不能等于1且不能過大，即不能太接近1。
定義6 (s，d)-個性化K-匿名隱私保護模型。如果一等價組由位于不同相似組的s-相似等價組組成，每個s-相似等價組都滿足d-非關聯約束，并且每個等價組至少由K條記錄組成，如果數據表T中的每個等價組都滿足以上條件，那么就稱數據表T滿足(s，d)-個性化K-匿名隱私保護模型。
(s，d)-個性化K-匿名隱私保護模型就是利用一個等價組中如果包含了多組s-相似等價組，并且每個s-相似等價組都滿足d-非關聯約束，就可以更加有效地抵御同質性攻擊及屬性泄漏。另外如果每組相異值包含了多組相似值，可更加有效地抵御背景知識攻擊，從而大大降低隱私信息泄漏的風險。本文闡述的(s，d)-個性化K-匿名隱私保護模型如表3所示。
根據病變器官這一相似性進行2-相似分組，可以看出該等價組滿足2-相似條件，從K=4的匿名表可以看出，由于敏感屬性疾病這一列都是高危敏感度屬性值，敏感度高達0.9，即使其滿足匿名條件，但是該等價組的隱私信息也已經暴露出來了，攻擊者很容易得出該等價組對應的個體患有很嚴重的疾病，也就造成了屬性泄漏。雖然從某種程度上來說還沒有造成身份泄露，但這也是人們所不希望的。
根據(s，d)-個性化K-匿名隱私保護模型的規定，調整如表4、表5所示。
表4、表5中的每個等價組都滿足s=2，d=0.5(即sensitivity>0.70的敏感屬性值出現在每個2-相似等價組中的頻率≤0.5)，K=4條件，但是可以較好地防止屬性泄漏問題。從敏感屬性敏感度的分布來看，經過調整記錄得到的這兩個表其實就是減少了每個2-相似分組中高危屬性值的出現頻率。表4中將癌癥的出現頻率控制在了50%以內，表5中也將癌癥的出現頻率控制在了50%以內。本文提出的(s，d)-個性化K-匿名隱私保護模型，在K-匿名模型基礎上做出了改進，有效地解決了由高危屬性值出現頻率過高而導致的屬性泄漏問題，同時能很好地抵御同質性攻擊和背景知識攻擊。
3 (s，d)-個性化K-匿名隱私保護模型算法
輸入：數據表T，對敏感屬性的敏感度進行標記s={S1，S2……Sn}，敏感屬性按相似性分組g=(g1，g2，…，gn)，準標識符各個屬性的權重W=(w1，w2，…，wn)，參數為s，d，K。
輸出：滿足(s，d)-個性化K-匿名隱私保護模型的數據表Ta’。
處理過程：
(1)生成s-相似等價組，并且這些等價組滿足d-非關聯約束。
(2)對生成的s-相似等價組尋找使泛化信息損失最少的、K/s個不位于相同相似組內的s-相似等價組：
Ta’={}
For(對于Ga中的每一個分組Ga’)
Gt={}，在Ga’中取一條記錄
If(|Gt|!=K/s)
在Gt中找一分塊Gt’，使得Gt’中的記錄t’和t的敏感屬性值不屬于同一個敏感屬性組，并且dist(QI[t]，QI[t’])最小 ，Gt=Gt∪Gt’， Ga= Ga/Gt。
End if Ta’= Ta’∪Gt
End for
(3)對生成的滿足(s，d)-個性化K-匿名隱私保護模型條件的各等價組進行泛化處理，即對Ta’中的每個分塊進行泛化處理。
4 實驗
實驗所使用的數據集來自UCI機器學習數據庫[7]中的adult數據庫，該數據庫在研究K-匿名應用最多，已經成為該領域事實上的標準測試集。數據庫大小為5.5 MB，本文選取其中的30 704條記錄及15個屬性，其中準標識符數量選擇6個，將職業(WORKCLASS)作為敏感屬性。敏感屬性泄漏分析如表6所示。
實驗軟硬件環境：
硬件環境：Intel Pentium(R) Dual-Core CPU，2GB RAM。
操作系統：Microsoft Windows XP。
編程環境：Eclipse+Mysql Server 5.1。
執行時間分析如圖1所示。
本文針對K-匿名沒有考慮到匿名后可信屬性由于缺乏多樣性而導致的隱私泄露、默認所有屬性都有相同的重要性、不能抵御背景知識攻擊等問題，提出了一種新的(s，d)-個性化K-匿名隱私保護模型。該模型通過s-相似分組，并且限制每個s-相似等價組內的高危敏感屬性值出現的頻率小于d，然后組合不同相似分組內的s-相似分組使其滿足K-匿名條件。實驗證明該模型能很好地彌補K-匿名的不足，有效地防止了隱私泄露。
參考文獻
[1] 劉喻，呂大鵬，馮建華，等.數據發布中的匿名化技術研究綜述[J].計算機應用，2007，27(10)：2361-2364.
[2] SWEENEY L. K-anonymity：a model for protecting privacy[J].International Journal on Uncertainty，Fuzzi-ness and Knowledge-based Systems，2002，10(5)：557-570.
[3] MACHANAVAJJHALA A， GEHRKE J， KIFER D， et al. L-diversity： Privacy beyond K-anonymity[C]// Proc of the 22 nd International Conference on Data Engineering New York： ACM Press， 2006.
[4] TRAIAN T M， BNDU V. Privacy protection： p-sensitive k-anonymity property[C]//.Proc of the 22 nd International Conference on Data Engineering New York： ACM Press，2006.
[5] WONG R C， Li Jinyong， FU A W， et al. (a，k)-anonymity： an enhanced k-anonymity model for privacy preserving[C]//. Proc of the 12 th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining New York： ACM Press， 2006.
[6] Xiao Xiaokui， Tao Yufei. Anatomy： simple and effective privacy preservation[C]//Proc of the 32 nd International Conference on Very Large Data Bases[SI]：VLDB Endowment， 2006：139-150.
[7] HETTICH C B S， MERZ C. UCI repository of machine learning databases[EB/OL]. (1996-05-01) [2008-04-20].http：//archiveics uci edu/ml/datasets/Adult.