相同敏感值數據表泛化算法的安全性度量研究

鄭明輝 楊晨 譚杰 呂含笑

摘? ?要：在k-匿名隱私保護策略的發展中，數據表的數據質量與安全性是相互制約的關系，在多樣化敏感值數據表的隱私保護研究中，如何平衡數據質量與安全性之間的矛盾，也是備受關注的重點。但是，對相同敏感屬性值的數據表進行泛化保護時，此方面的評價理論不適用于度量該類數據的可用性與安全性，文章針對這一不足，提出了一個基于熵理論的相同敏感值數據表泛化算法的評價方案。該方案引入了加權屬性熵和鏈接匹配熵的概念，加權屬性熵根據不同屬性的重要程度計算數據損失量，鏈接匹配熵將鏈接攻擊數據表消耗的正確匹配元組的信息量作為安全性度量。最后，利用提出的評價方案對兩種泛化算法處理后的數據表進行評價，豐富了在相同敏感值條件下泛化算法的評價體系。

關鍵詞：泛化算法;信息熵;信息損失量;鏈接攻擊

中圖分類號：TP3-05? ? ? ? ? 文獻標識碼：A

Abstract： In the development of k-anonymity privacy protection， the relation between data quality and security is mutually restrictive. And in the research of multi-sensitive attribute value data， how to balance the contradiction between data quality and security is also the focus of attention. However， there works are not applicable for data with same sensitive attribute value. To solve this problem， we proposed an evaluation scheme of generalization algorithm for data with same sensitive attribute based on entropy. In this paper， weighted attribute entropy and linking matched entropy are introduced at first. Weighted attribute entropy individually calculates the amount of data loss according to the importance of quasi attributes. Linking match entropy measured the safety of algorithm by calculating the attackers information cost on correctly linked. Finally， the proposed evaluation scheme is used to evaluate the data tables processed by the two generalization algorithms， which enriches the evaluation system of the generalization algorithm under the same sensitive values.

Key words： generalization algorithm; information entropy; information loss; linking attack

1 引言

近年來在對數據隱私保護策略的研究中，平衡隱私泄露和數據可用性之間的矛盾關系是其關注的重點。隱私保護一直都是信息安全領域的熱點問題，大數據時代的到來，使該問題更為突出和嚴峻[1]。數據挖掘的快速發展，容易導致用戶的個人信息泄露[2]。k-匿名技術[3]常用作數據發布前的保護，其未來發展研究的重要內容包括如何精確評價公開數據表的安全性和信息損失量。

在隱私保護策略的發展中，不斷有學者提出各種方法來度量數據可用性與安全性。Gionis等人提出了三種基于信息熵的信息損失度量方法[4]，其缺點在于計算復雜，度量公式中的數值屬性度量方法沒有反映出泛化前和泛化后屬性值之間的差異。李永凱等人根據屬性選擇性匹配問題，設計了匹配度量函數，并提出一個可以實現選擇性匹配的隱私安全協議[5]。文獻[6]利用聚類的質心與元組的距離表示信息的損失量。蘇潔等[7]人提出了一種基于信息損失量估計的k匿名圖流構造方法，實驗表明所提方法能夠較理想地控制信息損失量，缺點往往在于對網絡圖結構破壞比較大，使擾動后圖數據的可用性較低。李釗等人提出一種基于擴展熵的信息損失量計算方法[8]。王芳等人[9]提出了一種基于局部劃分的匿名算法，提高了數據匿名后的可用性，在減少信息損失量和提高關聯關系保留率方面具有較高的合理性和有效性。

關于泛化算法安全性度量的相關研究，Domingo等人用元組之間成功鏈接的個數百分比、基于似然性方法的正確鏈接數的百分比以及原始數據落入泛化后區間的百分比來衡量安全性[10];吳振強團隊[11]在單個屬性的前提下對兩個系統的匿名性進行對比，實用性不高;后又進行改進，文獻[12]提出用聯合熵作為匿名等級的評價指標，能夠達到多屬性系統的匿名性度量。Bertino等[13]人用匿名前后信息熵的改變來評估從不確定的數據集中獲取一個確定值的難度，該值代表了數據集的安全性。Brickell等[14]人將泛化算法安全性的損失定義為攻擊者從發布的數據中學習到新知識的量。張磊[15]等人從用戶屬性泛化的角度出發，提出了一種基于Hash 函數的泛化算法，并證明了該算法具備一定的隱私保護能力。熊平等[6]人把攻擊者將某元組鏈接定位到一個最大等價類中，推斷出該元組的敏感屬性值的困難程度定義為泛化算法的安全性，適合于多樣化敏感屬性值的數據表，缺點在于層次聚類泛化算法的計算復雜度較高。文獻[16]使用信息熵理論構造隱私量化模型，為隱私泄露風險的分析和度量提供理論基礎。可以看出，在隱私保護中安全性的定義因安全性本身的抽象性而不同，如何用合適的參數量化安全性，還需視具體情況而定。在相同敏感值條件下，本文將泛化算法的安全性定義為攻擊者利用微數據表鏈接出全集數據表中敏感信息的困難程度。

另外，值得關注的是k-匿名技術的研究始終建立在多樣化敏感屬性值的基礎上，Liu Xiaoping等人[17，18]指出過度保護或欠缺保護是k-匿名技術在相同敏感值條件下泛化保護所面臨的問題，但沒有提出有效的算法安全性或數據質量的評價方案。鑒于合理的算法評價方案對于推進相同敏感屬性值數據表的泛化算法是有幫助的，本文提出基于信息熵理論的加權屬性熵和鏈接匹配熵，對相同敏感值條件下的數據損失程度和安全性進行計算，本算法不僅在泛化過程中保持了較優的等價類劃分，保證了數據表在數據分析時能產生可靠的效用，且具有較高的安全性。

2 基于加權屬性熵的數據損失量計算

相同敏感屬性值的數據表省略了鏈接攻擊時的敏感值定位過程，可以使用兩個數據表模擬相同敏感值數據表的鏈接攻擊。包含相同敏感屬性值的數據表稱為微數據表 ，全集數據表T用于鏈接攻擊。本節將對相同敏感值數據表的可用性衡量進行分析。

定義1. 微數據表包含個準標識符屬性，其權重為，包含條元組，對應的條元組中共有種數值，每種數值對應的元組為 ，表中每個的信息熵為：

微數據表的加權屬性熵為：

定義2. 微數據表經泛化形成個等價類，用表示中符合取值區間元組的數量，用表示中等價類實際包含的元組個數，則泛化后微數據表加權屬性熵為：

當微數據表被泛化為一個等價類時，各屬性的熵值為0，數據表的可用性最低，因此加權屬性熵越大，數據質量越高。準標識符屬性的權重主要根據屬性對敏感值的重要程度以及各屬性值在劃分區間的方差波動而定，可根據相關研究成果對準標識符屬性進行權重設定，未對權重的精確性進行研究。

定義3. 微數據表中有個準標識符屬性，其權重分別為，需滿足：

3 基于鏈接匹配熵的泛化算法安全性度量

文中給出數據損失量的衡量標準，本節將在此基礎上量化泛化算法的安全性，并給出相關定義。

3.1 相同敏感值數據表的安全性定義

在多樣化的敏感值數據表受到鏈接攻擊時，通常以攻擊者推斷出某條元組對應敏感屬性值的難度作為衡量泛化算法安全性的標準。而在相同敏感值的條件下，攻擊者的攻擊難點在于正確匹配中的某些元組存在于中。

定義4. 相同敏感值條件下，攻擊者利用鏈接出中一條元組敏感值的困難程度稱為泛化算法的安全性。

3.2 鏈接匹配概率

相同敏感值條件下，攻擊者鏈接多個數據表的目的是為了匹配出與共同的元組，同時還能獲知中元組在中的額外屬性信息。泛化算法的目的是確保在受到鏈接攻擊時攻擊者獲取更少的敏感信息。

當的泛化層次越高，攻擊者越難在鏈接攻擊中正確匹配和中的元組。如表1所示，全集數據表T-1中含有4個準標識符屬性、9條元組，表2是微數據表MT-1，表3和表4分別為滿足2-匿名和3-匿名的泛化表。將表2與表1進行鏈接，可以推斷表1中ID為2、7、9的元組以概率1存在于表2中，如表1、表2所示。將表3與表1鏈接，推斷出ID為4、7的元組以概率1對應于等價類1，ID為3、6、8的元組以概率2/3對應于等價類2，ID為1、5的元組以概率1對應于等價類3，如表3、表4所示。將表4和表1鏈接，2、3、8元組以概率1對應于等價類1，1、4、5、7、9元組以概率3/5對應于等價類2。可以看出 中元組落入到各等價類的數量與微數據表的泛化程度有關，從而可計算中元組落入相對應等價類中的概率P。而的泛化程度越高，越難推斷出中元組在中。

由于在不同泛化層次下中準標識符屬性值所包含的信息量不同，攻擊者則以不同概率獲知中元組存在于中。因此可以用正確匹配元組的概率來表示泛化算法的安全性，將其定義為鏈接匹配概率。

定義5. 將中符合等價類取值區間的元組個數與等價類中元組數的比值定義為鏈接匹配概率。計算公式如下：

3.3 相同敏感值數據表的安全性度量

鏈接匹配概率是以攻擊者的角度計算成功鏈接微數據表中元組的成功率，無需計算多條元組的泄露風險就能衡量攻擊難度。

在與的鏈接過程中存在i個等價類，因此對應有i個鏈接匹配概率。衡量在鏈接攻擊中的安全性可以通過計算這i個概率的熵來實現。

定義6. 鏈接匹配熵是指中本應落在已泛化的等價類取值區間上的元組數量與實際落入該等價類數量的比值P（M）的熵：

其中，T||MT表示與進鏈接匹配的過程。

鏈接匹配熵表示攻擊者成功匹配元組所耗費的信息量。鏈接匹配熵越大，說明攻擊者為實現匹配成功所消耗的信息量越多，即數據表的安全性越高。

3.4 基于信息熵的數據表安全性驗證

泛化微數據表通過模糊化精確的屬性值，使得攻擊者要消耗更多的信息量才能得到泛化前的結果。由于鏈接攻擊的結果不受各屬性對數據質量貢獻度的影響，所以算法的安全程度可以通過計算泛化前后的非加權熵之差來表示。泛化后的數據表信息熵反映的是泛化操作的效果，若該熵值越小，表示數據表包含的信息量越少，泛化程度越高，在鏈接攻擊中越安全。

微數據表泛化前的信息熵為：

微數據表泛化后的信息熵為：

4 實驗仿真

本節將使用加權屬性熵和鏈接匹配熵對兩種泛化算法下數據表的劃分結果進行評價，實驗數據選自數據庫的數據。

4.1 準標識符屬性權重設置

為便于實驗進行，將數據集中14個準標識符屬性降為7個。為不含“”敏感值的數據表，是從該數據表中選取的滿足的近2300條元組成，保證了中的敏感屬性值“”的范圍是相同的。準標識符為{Race，Age，Hours-per-week，Education，Marital-status，Native-country，Gender}，權重根據各屬性的值在劃分區間的方差波動程度進行設置，波動程度越大代表數據越不穩定，則賦予的權重相對較小，本節賦予準標識符屬性的權重如表5所示。

4.2 不同算法的泛化操作分析

實驗中將使用Liu Xiaoping等人提出的決策泛化算法和一種改進算法。在決策泛化算法中，將等價類泄露風險作為劃分等價類的指標，泄露風險計算公式為：

（9）

其中，是中的元組個數（原算法以表示微數據表），表示劃分后數據表的等價類數量，表示第個等價類中元組的數量，表示微數據表與全集數據表中第個等價類的元組數量之比。

決策泛化算法以表示每次劃分后的第 個屬性的泄露風險值，為第個屬性中當前被分割的數據集的方差，可以針對性地對不同的準標識符屬性實施劃分。

改進后的算法稱作加權泛化算法，本文算法在泛化數據表的全過程都有屬性權重的參與，這一點不同于以前的算法。等價類劃分的標準為：

（10）

決策泛化算法主要根據待劃分前各屬性的方差作為權重來劃分等價類，當存在屬性對數據可用性影響較小、但方差起伏較大的情況時，會更多以該屬性作為劃分等價類的標準，導致其他屬性較少參與劃分等價類的過程，使得泛化后數據質量會更低。如果提前對準標識符屬性賦予權重，則會更細致地劃分權重較大的屬性，而即便對權重小的屬性進行粗糙劃分也不會對數據質量產生很大影響。

4.3 實驗分析

如表6所示，將數據量控制為2300條元組，兩種不同的泛化標準產生的不同的泛化結果。明顯可以看出，在等價類數量上，加權泛化算法在劃分時體現出優勢;決策泛化算法的加權屬性熵小于本文算法的熵值，說明在數據可用性方面加權泛化算法更優;鏈接匹配熵越大，攻擊者要想攻擊成功需消耗的信息量越多;而信息熵也驗證了鏈接匹配熵的結果，因為信息熵是從微數據表包含的信息量角度證明了安全性，熵值越小則信息量越少，實驗表明加權泛化算法的泛化程度更高，即更安全。

改變數據規模的大小，對實驗進一步分析。如圖1所示，加權屬性熵反映數據表的數據質量，值越大越能反映數據的可用性。從圖中可以明顯看出隨著數據量的變化，加權泛化算法的熵值明顯優于決策泛化算法，原因主要在于各屬性參與到劃分等價類的過程中，因此總是優先劃分權重最高的屬性，確保數據分析時數據的可靠性和安全性。

如圖2所示，利用泛化后數據表的信息熵的變化，來反映兩種泛化算法對應的抵御鏈接攻擊的能力。可以看出兩種泛化算法得到的數據表信息熵，隨著數據規模的增大都呈現出近似線性增長的趨勢，而決策泛化算法泛化后的數據表信息熵始終高于加權泛化算法，這也表明決策泛化算法所得數據表信息量要相對大一些，也就是說，加權泛化算法的安全性更高一些，抵御鏈接攻擊的能力更強。本算法不僅在泛化過程中保持了較優的等價類劃分，保證了數據表在數據分析時能產生可靠的效用，且具有較高的安全性。

5 結束語

本文就相同敏感屬性值條件下微數據表的泛化算法提出了衡量數據表損失量與安全性的度量方案，以加權屬性熵量化數據損失量，以鏈接匹配熵量化算法安全性。在仿真實驗中將屬性的權重作為改進等價類劃分標準的因素，解決了泛化時利用方差作為權重導致的等價類劃分不合理的問題，提高了泛化后數據的可用性。本文對不同的泛化結果進行對比，完善了相同敏感值條件下數據表的評價體系。但目前實驗沒有就等價類中元組數量k值進行不同取值的實驗，因此未提出全面的評價標準。后續擬對評價標準進行研究，力求達到可量化任一種泛化算法對相同敏感值數據表泛化保護后的數據損失量以及安全性。

參考文獻

[1] 王威，李楠.大數據時代個人隱私防范與保護策略研究[J].網絡空間安全，2017，8（Z2）：9-13.

[2] 馮登國，張敏，李昊.大數據安全與隱私保護[J].計算機學報， 2014，37（1）：246-258.

[3] LATANYA SWEENEY. k-ANONYMITY： A MODEL FOR PROTECTING PRIVACY[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10（5）：1-14.

[4] Gionis A， Tassa T. k-Anonymization with Minimal Loss of Information[M]. IEEE Educational Activities Department， 2009.

[5] 李永凱，劉樹波，楊召喚，等.MSN中用戶屬性隱私安全的選擇性匹配協議[J].華中科技大學學報（自然科學版）， 2015（5）：89-94.

[6] 熊平，朱天清，顧霄.基于信息增益比例約束的數據匿名方法及其評估機制[J].計算機應用研究， 2014，31（3）：819-824.

[7] 蘇潔，劉帥，羅智勇，孫廣路.基于信息損失量估計的匿名圖構造方法[J].通信學報，2016，37（06）：56-64.

[8] 李釗，孫占全，李曉，等.基于信息損失量的特征選擇方法研究及應用[J].山東大學學報（理學版），2016，51（11）：7-12.

[9] 王芳，余敦輝，張萬山.基于局部劃分的匿名算法研究[J/OL].計算機應用研究，2019（11）：1-3[2019-06-12].

[10] Domingo-Ferrer J， Torra V. A quantitative comparison of disclosure control methods for microdata[J]. Confidentiality Disclosure & Data Access， 2001.

[11] 吳振強，馬建峰.基于條件熵匿名模型的優化[C].中國密碼學學術會議，2004.

[12] 吳振強，馬建峰.基于聯合熵的多屬性匿名度量模型[J].計算機研究與發展，2006，43（7）：1240-1245.

[13] Bertino E， Fovino I N， Provenza L P. A framework for evaluating privacy preserving data mining algorithms[J]. Data Mining and Knowledge Discovery， 2005， 11（2）： 121-154.

[14] Brickell J， Shmatikov V. The cost of privacy： destruction of data-mining utility in anonymized data publishing[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2008： 70-78.

[15] 張磊，王斌，于莉莉.基于Hash函數的屬性泛化隱私保護方案[J].信息網絡安全，2018（03）：14-25.

[16] 彭長根，丁紅發，朱義杰，等.隱私保護的信息熵模型及其度量方法[J].軟件學報，2016，27（8）：1891-1903.

[17] Liu X， Li X， Motiwalla L， etal. Sharing patient disease data with privacy preservation[C].Ais Sigsec Workshop on Information Security and Privacy. 2015.

[18] Liu X， Li X B， Motiwalla L， etal. Preserving Patient Privacy When Sharing Same-Disease Data[J]. Acm J Data Inf Qual， 2016， 7（4）：17.