相同敏感值數(shù)據(jù)集的隱私保護泛化算法

鄭明輝， 呂含笑， 段洋洋

(湖北民族學院 信息工程學院 湖北 恩施 445000)

0 引言

隨著網(wǎng)絡信息與技術(shù)的高速發(fā)展，社會和網(wǎng)絡中的信息逐漸朝著信息共享與資源互利的趨勢發(fā)展.數(shù)據(jù)挖掘在近幾年的大數(shù)據(jù)背景下不斷升溫，各機構(gòu)盡最大可能收集用戶的信息，并從中挖掘關(guān)鍵內(nèi)容，這導致了用戶隱私信息的泄露[1],尤其是家庭住址、醫(yī)療信息、工作情況等重要信息.因此，亟待數(shù)據(jù)發(fā)布前的保護，以避免鏈接攻擊導致個人隱私泄露.文獻 [2]提出k-匿名模型,通過對數(shù)據(jù)集中的屬性進行隱匿的泛化操作，使相互可區(qū)別的元組匿名成k個不可區(qū)分的元組，以此達到攻擊者無法使用多表鏈接出個體隱私的目的.該模型易于理解且實用性強，因此在應用中不斷被優(yōu)化.已有的研究成果主要包括：使敏感值多樣化分布在等價類的l-多樣性模型[3]與t-closeness模型[4]；根據(jù)敏感度劃分等價類的(p,a)-sensitivek-匿名模型[5]；避免偏度攻擊的(n,t)-proximity模型[6]；避免同質(zhì)性攻擊[7]的(C,L)-多樣性模型[8]；避免相似性攻擊的(l,e)-diversity模型[9]等.目前還出現(xiàn)了抗背景知識攻擊、語義攻擊等的k-匿名模型研究，并開始在位置服務領(lǐng)域、社交網(wǎng)絡領(lǐng)域、智慧醫(yī)療、電力系統(tǒng)等方面對k-匿名模型進行應用[10].另外，如何度量算法的有效性也是數(shù)據(jù)隱私保護的主要研究內(nèi)容.文獻[11]將匿名轉(zhuǎn)化率作為信息損失的度量，以此計算數(shù)據(jù)質(zhì)量.文獻[12]提出了一種度量軌跡數(shù)據(jù)隱私風險的模型，通過計算敏感狀態(tài)先驗概率與后驗概率之間的差值，評估軌跡還原造成的隱私泄露程度.

通過分析發(fā)現(xiàn)，以上研究并非建立在2個數(shù)據(jù)表的實際鏈接之上，而是將其中一個鏈接數(shù)據(jù)表抽象為攻擊者，其原因在于微數(shù)據(jù)表中的敏感屬性值不完全相同，鏈接攻擊可被簡化為已知某些個體存在于微數(shù)據(jù)表中的攻擊者意圖獲取這些個體敏感信息的過程.因此，傳統(tǒng)k-匿名技術(shù)研究的重點是對含不同敏感屬性值的數(shù)據(jù)進行隱私保護.事實上，同質(zhì)性攻擊是一種因敏感值相同而出現(xiàn)的攻擊方式[13-14]，k-匿名方案對該攻擊的防御常常依靠其他敏感值嵌入其中以干擾攻擊者，并沒有從根本上解決針對相同敏感值數(shù)據(jù)的攻擊問題.文獻[15]指出k-匿名技術(shù)在對相同敏感值數(shù)據(jù)集進行泛化時易出現(xiàn)過度保護或欠缺保護.為彌補該缺陷，文獻[16]提出了一種基于二元遞歸決策劃分的泛化算法(以下簡稱“決策泛化算法”),用于對相同疾病的數(shù)據(jù)集進行泛化保護，提高了泛化后數(shù)據(jù)的安全性，但其關(guān)注的隱私泄露風險較單一.本文在完善泄露風險計算的基礎上，提出了2種具有不同等價類劃分標準的新泛化算法，構(gòu)造出具有最小隱私泄露風險，數(shù)據(jù)可用性較強，且具有有效迭代停止標準的算法；并根據(jù)泛化后數(shù)據(jù)集的等價類數(shù)量、隱私泄露風險等內(nèi)容評價各泛化算法的優(yōu)勢，從而選取最優(yōu)的泛化算法作為相同敏感值數(shù)據(jù)表的泛化保護方法.

1 相同敏感值條件下的隱私泄露風險

本節(jié)將以醫(yī)療數(shù)據(jù)為應用場景，給出相同敏感值條件下的數(shù)據(jù)隱私泄露定義和隱私泄露風險的計算方法.

1.1 傳統(tǒng)的隱私泄露

k-匿名技術(shù)關(guān)注的數(shù)據(jù)隱私泄露有身份泄露和屬性泄露兩種.目前，k-匿名技術(shù)基本上能抵御身份泄露，但是敏感屬性值的多樣性使得屬性泄露不易被解決.因此，仍會出現(xiàn)隱私保護不到位的情況.另外同質(zhì)性攻擊、相似性攻擊等都是因敏感值相同、敏感度相似而發(fā)生的攻擊形式，在多樣化敏感值數(shù)據(jù)表中可利用敏感值的不同分布來抵御這種攻擊，在相同敏感值條件下尚不能有效地解決該問題.

1.2 敏感值條件對隱私泄露的影響

1) 實例多屬性泄露

同質(zhì)性攻擊的原理是攻擊者已知某個體恰好存在于敏感值相同的等價類中，則攻擊者可直接獲知該個體的敏感值信息.而在相同敏感值數(shù)據(jù)表中，無法以目標個體存在于該表中為前提進行屬性值匹配鏈接，對攻擊者而言只能依靠多表鏈接進行攻擊.

實際上，攻擊者的目的不僅局限在獲取個體的敏感信息.以患者疾病數(shù)據(jù)為例描述以下攻擊場景：表1為患者的聯(lián)系方式數(shù)據(jù)，表2為患者的疾病微數(shù)據(jù)(為便于對比不同/相同敏感值，微數(shù)據(jù)表中同時出現(xiàn)相同疾病(S-disease)和不同疾病(Dif-disease))，關(guān)注表2中相同疾病的情況.若攻擊者將2個數(shù)據(jù)表進行鏈接，不僅能確定Brown、Smith、Stone、Green和Miller同患一種疾病，并且能獲知他們各自的電話信息.為區(qū)別“屬性泄露”，本文對相同敏感值數(shù)據(jù)集在鏈接攻擊中產(chǎn)生的額外屬性泄露定義為“實例多屬性泄露”.

表1 患者的聯(lián)系方式數(shù)據(jù)

表2 患者的疾病微數(shù)據(jù)

定義1在含相同敏感值的微數(shù)據(jù)表和對應的去識別化的信息表中，鏈接出一個元組并獲取該元組在信息表中的其他屬性信息，稱為“實例多屬性泄露”.

2) 實例完全泄露

將表2的準標識符屬性泛化至滿足3-匿名標準，表3為滿足3-匿名的疾病微數(shù)據(jù)，其包含兩個等價類，ID為1、2、3的元組為等價類1，ID為4、5、6的元組為等價類2.

表3 滿足3-匿名的疾病微數(shù)據(jù)

定義2微數(shù)據(jù)集泛化后，每個等價類的所有元組在信息表中被攻擊者同時識別出隱私信息，稱為“實例完全泄露”.

從表4可以看出，相同疾病敏感值數(shù)據(jù)集在鏈接攻擊中的泄露風險值大于不同敏感值的數(shù)據(jù)集.因此，對相同敏感值數(shù)據(jù)集進行發(fā)布前的隱私保護非常重要.

表4 不同場景的隱私泄露風險值

1.3 相同敏感值條件下泄露風險的計算

1) 實例多屬性泄露風險的計算

在相同敏感值的微數(shù)據(jù)表和對應的信息表中，第i個等價類中每條元組產(chǎn)生的多屬性泄露風險為

ri=ni/Ni，

(1)

式中：ni為泛化后疾病微數(shù)據(jù)表中第i個等價類中元組的個數(shù)；Ni為泛化后患者信息表中第i個等價類中元組的個數(shù).

實例多屬性泄露并不意味著攻擊者將微數(shù)據(jù)表中第i個等價類中的所有元組以概率ri識別出來，而是信息表中某個體被察覺到存在于疾病微數(shù)據(jù)表中的概率.即從信息表的第i個等價類中任意選取ni條元組，其中至少有一人的敏感信息被泄露，概率為ri.當兩組等價類出現(xiàn)r1=r2這種特殊情況時，這兩組等價類的隱私泄露程度是否一樣還需要更多的參數(shù)來說明.

2) 實例完全泄露風險的計算

由于實例多屬性泄露風險只能對一條元組的泄露情況進行描述，無法從微數(shù)據(jù)表被隱匿泛化后的整體角度描述隱私泄露的情況.尤其當r1=r2時，這2個等價類中所有元組的實例完全泄露風險卻常常不同.在這種特殊情況下，如何判斷微數(shù)據(jù)表的泛化效果，就需要實例完全泄露風險來衡量.

在泛化后的相同敏感值微數(shù)據(jù)表中，第i個等價類中所有元組同時泄露的風險為

(2)

在上述有關(guān)患者數(shù)據(jù)集的攻擊場景中，攻擊者的目的在于只需要知道某個聯(lián)系方式的所屬者患有某疾病，不需要清楚地識別患者的身份.所以在相同疾病的情況下，盡可能讓攻擊者獲取到患者的疾病信息與聯(lián)系方式的概率更小才更加安全.由于相同敏感值條件下的實例完全泄露風險明顯大于以往研究關(guān)注的不同敏感值數(shù)據(jù)集，故針對相同敏感值數(shù)據(jù)集進行隱私保護以降低實例完全泄露風險的研究意義重大.

2 降低隱私泄露風險的泛化算法設計

為了避免含相同敏感值的數(shù)據(jù)在發(fā)布后受到鏈接攻擊產(chǎn)生的隱私泄露過多，需要在數(shù)據(jù)發(fā)布前對其進行泛化保護.泛化是一種將數(shù)據(jù)分類后對其進行隱匿或抑制的操作，使其與同一等價類的數(shù)據(jù)具有不可區(qū)分性.泛化后的數(shù)據(jù)雖然不能完全抵御鏈接攻擊、背景知識攻擊導致的泄露，但卻可以減少相應攻擊下的隱私泄露.

本文提出2種泛化算法，將實例多屬性泄露風險作為算法中等價類的劃分標準，以降低實例多屬性泄露風險和實例完全泄露風險為目標對數(shù)據(jù)集進行泛化.一方面完善決策泛化算法中的停止標準，另一方面通過采取不同的等價類劃分標準，從數(shù)據(jù)集被泛化后的結(jié)果，分析劃分標準對算法達到的不同隱私保護效果.

2.1 參數(shù)符號及其含義

2.2 算法1

需要患者疾病微數(shù)據(jù)表D，患者聯(lián)系方式信息表C，且已知D集合中的患者一定在C集合中，2個集合有d個公共準標識符屬性.

步驟1: 按照升序或降序的排序方法，把d中的每個屬性值進行排列.并在每一個屬性j中，在相鄰的值之間進行一次試驗劃分；

步驟5: 對D集合已經(jīng)劃分出來的2個集合再進行步驟2～4的重復，直到一個待劃分的集合當前的實例完全泄露風險大于或等于劃分后的實例完全泄露風險，停止對該集合的劃分.同理，其余待劃分集合以此作為停止循環(huán)劃分的標準.

2.3 算法2

在對集合進行等價類劃分的過程中，可以采用不同的標準進行.因此，本方案提出第2種劃分標準，將2種劃分標準與決策泛化算法的劃分標準通過實驗進行對比，從而選取最優(yōu)化的算法作為相同敏感值數(shù)據(jù)集的泛化方法.

算法2與算法1的區(qū)別體現(xiàn)在步驟2中，在計算D中每次劃分得到的2個等價類實例多屬性泄露風險ri1與ri2后，選擇max{ri1,ri2}，然后再選擇min{max{rii,ri2}}.最小的max{ri1,ri2}值所對應的屬性中的值，在此處進行D集合的“最佳試驗劃分”.后續(xù)過程以此類推，其他步驟同算法1.

3 實驗仿真

3.1 實驗結(jié)果分析

從等價類的數(shù)量來看，等價類越多則數(shù)據(jù)集的元組泛化程度越低，即數(shù)據(jù)質(zhì)量的損失越少.算法1的等價類略多于算法2，在數(shù)據(jù)可用性方面表現(xiàn)較好.從實例多屬性泄露風險的角度來看，算法1的風險值上下波動明顯，下限雖然小，但是上限值卻很大，數(shù)據(jù)集在泛化后的平均泄露風險也會較大；算法2的風險下限雖略大于算法1，但是最大風險值只有1/2，能良好控制整個數(shù)據(jù)集的泄露風險.從實例完全泄露風險角度來看，算法2的風險值上下限均明顯小于算法1.

表5 3種算法的實驗結(jié)果

3.2 本方案與決策泛化算法的結(jié)果對比

本文對決策泛化算法進行了模擬(由于原算法中沒有明確指出迭代的停止標準，故按本方案的停止標準進行實驗).從實驗結(jié)果來看，3個算法的等價類數(shù)量都比較接近，算法1從等價類數(shù)量上更優(yōu)化；實例多屬性泄露風險的下限值是接近的，但從避免攻擊者成功竊取隱私信息的角度來看，希望該風險的上限更小，因此算法2優(yōu)于其他兩種算法；算法2在實例完全泄露風險上的表現(xiàn)也比較突出，所以算法2的結(jié)果總體上更有說服力.另外，3種算法使同一數(shù)據(jù)集的元組均滿足2-匿名標準，產(chǎn)生該結(jié)果的原因還有待具體分析.

同決策泛化算法相比，本文的2個算法在計算復雜度方面只改變了劃分等價類時的泄露風險計算方式，算法其他部分的復雜度相同，泄露風險計算方式的不同并未改變算法的復雜度；算法停止條件的約束會減少決策泛化算法實際劃分的次數(shù).因此，本文的泛化算法復雜度不大于原算法.

4 結(jié)論

仿真結(jié)果表明，算法2的數(shù)據(jù)可用性較高、實例多屬性泄露風險上限最小且實例完全泄露風險最小，為最優(yōu)算法.在實驗結(jié)果中發(fā)現(xiàn)，這3種算法對數(shù)據(jù)集泛化后，其等價類中包含的元組數(shù)量符合2-匿名標準，表明對于相同敏感值的數(shù)據(jù)隱私保護也可以滿足k-匿名要求，但其原因還需進一步的研究.當遇到數(shù)據(jù)量過大時，等價類劃分標準存在計算困難的問題，如何解決該問題也是未來需要繼續(xù)研究的.另外，如果能有更全面的關(guān)于算法安全性和有效性的評估模型對本文進行評估則會更加完善，后續(xù)擬從信息熵的角度繼續(xù)深入研究泛化后數(shù)據(jù)集防御鏈接攻擊的表現(xiàn)以及計算數(shù)據(jù)表的數(shù)據(jù)質(zhì)量損失.

參考文獻：

[1] 馮登國, 張敏, 李昊. 大數(shù)據(jù)安全與隱私保護[J]. 計算機學報, 2014, 37(1):246-258.

[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, GEHRKE J, KIFER D, et al.l-Diversity: privacy beyondk-anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering. Atlanta, 2006:24.

[4] LI N, LI T, VENKATASUBRAMANIAN S.t-Closeness: privacy beyondk-anonymity andl-diversity[C]//Proceedings of the 23rd International Conference on Data Engineering. Istanbul, 2007:106-115.

[5] WANG Q, ZENG Z P. (p,a)-Sensitivek-anonymity:privacy protection model[J]. Application research of computers, 2009, 26(6):2176-2177.

[6] PRAKASH M, SINGARAVEL G. A new model for privacy preserving sensitive data mining[C]// Third International Conference on Computing Communication and Networking Technologies. Coimbatore, 2012:1-8.

[7] LEFEVRE K, DEWITT D J, RAMAKRISHNAN R. Incognito:efficient full-domaink-anonymity[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Baltimore, 2005:49-60.

[8] YI T, SHI M Y, SHANG W Q, et al. Graded medical data publishing based on clustering[C]//Proceedings of the 12th International Conference on Fuzzy Systems and Knowledge Discovery. Zhangjiajie, 2015:1647-1652.

[9] WANG H Y, HAN J M, WANG J Y, et al. (l,e)-Diversity：a privacy preserving model to resist semantic similarity attack[J]. Journal of computers, 2014, 9(1)：59-64.

[10] 許長清, 趙華東, 宋曉輝. 基于大數(shù)據(jù)的電力用戶群體識別與分析方法研究[J]. 鄭州大學學報(理學版), 2016, 48(3):113-117.

[11] 王偉, 郭獻彬. 一種增強的匿名化隱私保護模型[J]. 信息通信, 2016(1):1-4.

[12] 彭瑞卿,劉行軍,用戶的行動軌跡還原與隱私風險度量[J].武漢大學學報(理學版),2017,63(2):142-150.

[13] 楊曉春, 劉向宇, 王斌,等. 支持多約束的k-匿名化方法[J]. 軟件學報, 2006, 17(5):1222-1231.

[14] 韓建民, 岑婷婷, 虞慧群. 數(shù)據(jù)表k-匿名化的微聚集算法研究[J]. 電子學報, 2008, 36(10):2021-2029.

[15] LIU X P, LI X B, MOTIWALLA L, et al. Sharing patient disease data with privacy preservation[C]//Proceedings of the AIS SIGSEC Workshop on Information Security and Privacy. Fort Worth, 2015:1-13.

[16] LIU X, LI X B, MOTIWALLA L, et al. Preserving patient privacy when sharing same-disease data[J]. Journal of data and information quality, 2016, 7 (4):17.