基于屬性分區(qū)的（αi，k）-p隱私保護(hù)算法

摘 要：針對(duì)（αi，k）—匿名算法使用有損鏈接思想無法對(duì)用戶身份進(jìn)行保護(hù)的問題，引入屬性分區(qū)置換概念，提出基于屬性分區(qū)的（αi，k）-p匿名算法，對(duì)桶中QI屬性采取分區(qū)、置換的方式保護(hù)用戶身份信息。在人口真實(shí)數(shù)據(jù)集21 956條數(shù)據(jù)上對(duì)兩種算法進(jìn)行敏感值保護(hù)和會(huì)員身份保護(hù)有效性對(duì)比實(shí)驗(yàn)。結(jié)果表明，敏感值泄露概率最高時(shí)只剛好超過0.05，接近傳統(tǒng)方法的1/4;在會(huì)員身份保護(hù)方面，F(xiàn)OR值在0.7以上。相對(duì)于（αi，k）—匿名算法，該算法能更好地保護(hù)敏感值信息和會(huì)員身份信息。

關(guān)鍵詞：隱私保護(hù);數(shù)據(jù)發(fā)布;屬性分區(qū)

DOI：10. 11907/rjdk. 191457 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2019）008-0063-03

（αi，k）-p Privacy Preserving Algorithm Based on Attribute Partition

WU Shao-xin

（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

Abstract： The （αi，k）-anonymity algorithm proposed by Jinhua uses the idea of lossy links， and it can not provide the protection of user identity. In this paper， the idea of attribute partition replacement is introduced， and an （αi，k） - p anonymity algorithm based on attribute partition is proposed. QI attribute partition and replacement in bucket are adopted to protect user's identity information. This paper implements two algorithms for 21 956 data sets of real population， and compares the effectiveness of sensitive value protection and membership protection. The results show that the leakage probability of sensitive value is just over 0.05， which is close to 1/4 of the traditional method， and FOR value is above 0.7 in membership protection. Compared with （αi，k）-anonymous algorithm， the proposed algorithm can better protect sensitive value information and membership information.

Key Words： privacy protection; data publishing; attribute partition

作者簡介：武紹欣（1995-），男，山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)安全、隱私保護(hù)。

0 引言

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，數(shù)據(jù)交互越來越方便，大量數(shù)據(jù)被政府機(jī)構(gòu)或企業(yè)收集[1-2]，對(duì)此進(jìn)行數(shù)據(jù)挖掘等研究，能幫助決策并創(chuàng)造商業(yè)價(jià)值，但也存在個(gè)人隱私泄露風(fēng)險(xiǎn)[3-5]。因此，隱私保護(hù)越來越受到重視。但對(duì)數(shù)據(jù)過分保護(hù)使挖掘的信息減少，因此隱私保護(hù)研究的重點(diǎn)是在數(shù)據(jù)可用性與隱私保護(hù)之間求得平衡。

現(xiàn)有的隱私保護(hù)技術(shù)大體分為數(shù)據(jù)失真、數(shù)據(jù)加密和限制發(fā)布3類[6]。數(shù)據(jù)失真技術(shù)主要通過添加噪聲等方式使數(shù)據(jù)失真，從而達(dá)到保護(hù)數(shù)據(jù)隱私的目的;數(shù)據(jù)加密是通過加密算法實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù);限制發(fā)布則是將數(shù)據(jù)中的隱私信息先進(jìn)行泛化或匿名等操作后再發(fā)布，限制性地發(fā)布處理后的數(shù)據(jù)。

Sweeney等[7]通過對(duì)數(shù)據(jù)匿名化研究提出k—匿名模型，該模型對(duì)數(shù)據(jù)表中的準(zhǔn)標(biāo)識(shí)符屬性進(jìn)行約束，要求發(fā)布的數(shù)據(jù)表任意一條記錄，在準(zhǔn)標(biāo)識(shí)符屬性上都無法與其它 k-1 條記錄區(qū)分，這樣即使攻擊者能夠了解目標(biāo)用戶的所有QI信息，也無法確切知道用戶的敏感信息。

為克服 k—匿名模型難以抵御同質(zhì)性攻擊的缺陷，Machanavajjhala A等[8]提出了l—多樣性匿名方法，要求在同一等價(jià)類中都有l(wèi)個(gè)表現(xiàn)良好的敏感值，解決了某些情況下由于敏感屬性取值單一導(dǎo)致的隱私泄漏問題。但是該模型下的數(shù)據(jù)集會(huì)有遭受到偏斜攻擊和相似性攻擊的可能。

Li等[9]提出t—接近模型，它要求每個(gè)等價(jià)類中所有敏感值的分布要與原始數(shù)據(jù)表中敏感值的分布接近，差異不要超過預(yù)先設(shè)定的閾值，但是沒有給出具體算法，且由于較為嚴(yán)格的限制致使該模型難以實(shí)現(xiàn)。

隨后，Wong等[10]提出了（α，k）—匿名模型。（α，k）—匿名模型要求匿名數(shù)據(jù)集在等價(jià)組上滿足k值約束條件下，任意敏感屬性值在等價(jià)組中出現(xiàn)的概率都小于等于α值約束，即0≤α≤1。

解剖[11]與泛化和抑制不同，該方法在兩個(gè)單獨(dú)的表中給出關(guān)于QI和SA上的數(shù)據(jù)：包含QI屬性的QIT、包含SA的ST以及QIT和ST都具有一個(gè)共同屬性，即組ID。解剖學(xué)的最大好處是QIT和ST都沒有數(shù)據(jù)修改。

這些方案可以應(yīng)對(duì)一些攻擊類型，如背景知識(shí)攻擊[12]和合成攻擊[13]等，但依然有別的攻擊方式不能抵御，如相似性攻擊和敏感性攻擊。

在上面模型基礎(chǔ)上，姜火文[14]提出基于貪心的聚類算法，減小了信息損失，但不能應(yīng)對(duì)敏感性攻擊。張健沛[15]提出基于敏感值語義桶分組的隱私保護(hù)模型;曹敏姿[16]提出個(gè)性化（α，l）-多樣性k-匿名模型，可以應(yīng)對(duì)敏感性攻擊，但卻改變了一些元組的敏感值;毛慶陽[17]提出基于聚類的S-KACA算法，能夠提供敏感性保護(hù)，但存在很多等價(jià)類沒有最小化，增加了信息損失;劉湘雯[18]提出了個(gè)性化擴(kuò)展（α，k）匿名模型，根據(jù)敏感度將敏感屬性值分為若干組，每組都有自己的頻率約束閾值，為每個(gè)人設(shè)置一個(gè)保護(hù)節(jié)點(diǎn)，必要時(shí)替換敏感值，但該模型同樣改變了一些元組的敏感值。

金華[19]提出（αi，k）—匿名模型，預(yù)先設(shè)置每個(gè)敏感值的敏感級(jí)別，然后在一個(gè)桶中限制所有級(jí)別敏感值的頻率從而實(shí)現(xiàn)對(duì)隱私的保護(hù)。一個(gè)等價(jià)類中，任意一條元組的敏感值比例不高于α，且任意級(jí)別的敏感值占比均不超過閾值αi，則稱該等價(jià)類滿足（αi，k）—匿名，但它無法提供會(huì)員身份保護(hù)。

為改善（αi，k）-匿名模型缺點(diǎn)，本文提出一種基于屬性分區(qū)的（αi，k）-p匿名算法，在選取元組構(gòu)成等價(jià)類之前先對(duì)元組中的QI信息進(jìn)行分區(qū)，在構(gòu)成等價(jià)類后再置換QI組。該算法在會(huì)員身份保護(hù)和敏感值保護(hù)方面均有很大優(yōu)勢(shì)，可應(yīng)對(duì)敏感性攻擊。

1 基于屬性分區(qū)的（αi，k）-p算法

（αi，k）-anonymity模型無法對(duì)身份信息進(jìn)行保護(hù)，因此算法需對(duì)屬性進(jìn)行分區(qū)，使高度相關(guān)的屬性位于同一列中，這有利于實(shí)用性和隱私性。在數(shù)據(jù)實(shí)用性方面，將高度相關(guān)的屬性分組以保留這些屬性之間的相關(guān)性。在隱私方面，不相關(guān)屬性的關(guān)聯(lián)比高度相關(guān)屬性的關(guān)聯(lián)具有更高的識(shí)別風(fēng)險(xiǎn)，因?yàn)椴幌嚓P(guān)屬性值的關(guān)聯(lián)頻率要低得多，更容易識(shí)別。為保護(hù)隱私，就要打破不相關(guān)屬性之間的關(guān)聯(lián)，具體算法如下：

算法

輸入：原始數(shù)據(jù)表T，參數(shù)k，敏感性分級(jí)（L1，L2，…，Li，…），頻率約束（α1，α2，…，αi，…）

輸出：置換匿名表Tanony

步驟如下：

使用均方偶然系數(shù)計(jì)算出QI屬性中的相關(guān)度;

使用PAM聚類算法對(duì)列屬性進(jìn)行聚類;

將T中每個(gè)元組的的QI值按照列聚類的結(jié)果使用集合代替;

[j=max（1α，k），θi=j？αi，i=1，2，？];

while 剩余元組可以構(gòu)造元組桶;

E=Φ;

while 元組桶E不滿足（αi，k）匿名;

在所有級(jí)別的 Li中按照級(jí)別從高到低的順序一次選取敏感屬性為個(gè)數(shù)最多的元組加入元組桶E，在T中取出該元組，且在下一次選擇當(dāng)前敏感級(jí)時(shí)跳過該敏感值的元組;

檢查在每一級(jí)別挑選的個(gè)體個(gè)數(shù)是否小于對(duì)應(yīng)的θi，如果不小于θi，則下一次選取個(gè)體時(shí)跳過該敏感級(jí)。如果當(dāng)前敏感級(jí)除去選擇的SA為空，則下次選擇SA時(shí)跳過該敏感級(jí);

end while;

將E中每一列隨機(jī)置換;

將E添加到Tanony，并標(biāo)注classID;

end while;

對(duì)于剩余的元組，添加到某個(gè)元組桶中，該元組桶仍然滿足（αi，k）匿名，則將該元組添加到該等價(jià)類中。

隱匿所有的無法添加到等價(jià)類的元組;

輸出匿名表Tanony。

給定兩個(gè)屬性A1、A2，其中值域分別為{V11，V12，…，V1d1}、{V21，V22，…，V2d2}，其對(duì)應(yīng)的值域大小分別是d1、d2。A1、A2之間的均方偶然系數(shù)計(jì)算方法如公式（1）所示。

[φ2（A1，A2）=1min（d1，d2）-1i=1d1j=1d2（fij-fi？f？j）2fi？f？j]? ? （1）

其中[fi？]、[f？j]分別是數(shù)據(jù)表中V1i、V2j，[fij]表示數(shù)據(jù)表中的數(shù)目。

2 實(shí)現(xiàn)方法

硬件環(huán)境：Intel（R） Core（TM）i5-3230M CPU@2.6GHz，內(nèi)存4G，操作系統(tǒng)Win7 x64旗艦版;軟件環(huán)境：使用python編程語言實(shí)現(xiàn)，IDE開發(fā)工具為Pycharm。

本文使用真實(shí)的美國人口普查數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)[20]，去除其中的無效數(shù)據(jù)，隨機(jī)挑選21 956條數(shù)據(jù)。其中，age、sex、relate、marst、race、education作為QI屬性，salary作為敏感屬性，詳細(xì)信息如表1所示。

表1 屬性說明

對(duì)數(shù)據(jù)集中敏感屬性salary的屬性值采用如表2所示的分級(jí)，并設(shè)置在同一合并桶中每一級(jí)別敏感屬性出現(xiàn)的頻率。

表2 敏感屬性分級(jí)

2.1 敏感值泄露概率

假定攻擊者已經(jīng)了解所有用戶的QI信息，并且知道用戶在這種匿名表上，攻擊者通過將QI值匹配該匿名表獲得敏感信息。下面通過敏感值泄露概率[21]驗(yàn)證算法對(duì)敏感值的保護(hù)能力。

選擇任意一個(gè)元組t，計(jì)算t的匹配個(gè)體數(shù)量Numtuples（t），匹配桶MB中t的匹配個(gè)體數(shù)量，記作Num（t，MB），以及t的敏感值s在MB中出現(xiàn)的次數(shù)Num（t，MB），[MB]表示MB中包含個(gè)體的數(shù)量，計(jì)算公式如下：

[p（t，s）=MBNum（t，MB）？Num（s，MB）Numtuples（t）？MB] （2）

2.2 偽元組比率

使用偽元組比率[22]驗(yàn)證兩個(gè)算法對(duì)會(huì)員披露的保護(hù)，定義為偽元組的數(shù)量除以總元組的數(shù)量。FOR越大，提供的會(huì)員披露保護(hù)越多。計(jì)算公式如下：

[FOR=tuplefaketupleall]? ? ? ? ?（3）

假定每個(gè)桶有k個(gè)元組，被分為c列，每列有k個(gè)不同的值，那么偽元組個(gè)數(shù)為kc-k個(gè)，F(xiàn)OR=1-1/kc-1。

3 實(shí)驗(yàn)結(jié)果

采用（αi，k）-pGCA算法和（αi，k）-GCA算法[19]對(duì)數(shù)據(jù)集進(jìn)行匿名分析。取k為固定值5，c值為2，隨著α值的變化，對(duì)比兩種算法結(jié)果。首先對(duì)比兩個(gè)算法的敏感值泄露概率，結(jié)果如圖1所示。

圖1 敏感值泄露概率

因?yàn)椋é羒，k）-GCA算法完全沒有對(duì)元組的QI值提供保護(hù)，所以所有的元組幾乎能百分之百匹配到所在的元組桶，因此該算法對(duì)敏感值的保護(hù)取決于元組桶大小。而（αi，k）-pGCA算法對(duì)QI值分區(qū)，并對(duì)每一個(gè)元組桶內(nèi)的QI值置換，所以對(duì)每一個(gè)元組都能匹配到多個(gè)元組桶，因此敏感值泄露概率遠(yuǎn)低于（αi，k）-GCA算法。在敏感值保護(hù)方面，（αi，k）-pGCA算法更好。

每次實(shí)驗(yàn)值選取1 000個(gè)元組桶，計(jì)算FOR的平均值，對(duì)比結(jié)果如圖2所示。

圖2 偽元組比率

因?yàn)椋é羒，k）-GCA算法對(duì)QI值做匿名操作，所以在一個(gè)元組桶中不會(huì)產(chǎn)生任何偽元組，因此FOR都為0。（αi，k）-pGCA算法的元組桶中產(chǎn)生更多的元組，偽元組比率隨著元組桶的增大而增大，在α取到1/15及更小時(shí)，元組桶中偽元組的比重已經(jīng)占到絕大多數(shù)，能更好地應(yīng)對(duì)會(huì)員身份披露。

4 結(jié)語

為解決現(xiàn)有（αi，k）-GCA算法無法保護(hù)身份和無法應(yīng)對(duì)會(huì)員身份披露的問題，本文提出一種新的（αi，k）-pGCA算法。通過對(duì)原始數(shù)據(jù)集元組的QI信息進(jìn)行分區(qū)置換，可以更好地保護(hù)隱私信息。可以看到，在分區(qū)置換后，敏感值泄露概率遠(yuǎn)遠(yuǎn)超過需求。未來將通過優(yōu)化算法進(jìn)一步研究如何最小化元組桶大小，使其既符合隱私保護(hù)需求，又能減少后續(xù)數(shù)據(jù)分析誤差。

參考文獻(xiàn)：

[1] 馮登國，張敏，李昊. 大數(shù)據(jù)安全與隱私保護(hù)[J]. 計(jì)算機(jī)學(xué)報(bào)， 2014， 37（1）：246-258.

[2] 閆蒲. 互聯(lián)網(wǎng)社交大數(shù)據(jù)下行為研究的機(jī)遇與挑戰(zhàn)[J]. 中國統(tǒng)計(jì)，2016（3）：15-17.

[3] 王博. 大數(shù)據(jù)發(fā)展背景下網(wǎng)絡(luò)安全與隱私保護(hù)研究[J]. 軟件導(dǎo)刊，2016， 15（8）：171-172.

[4] 劉雅輝，張鐵贏，靳小龍，等. 大數(shù)據(jù)時(shí)代的個(gè)人隱私保護(hù)[J]. 計(jì)算機(jī)研究與發(fā)展，2015，52（1）：229-247.

[5] 孟小峰，張嘯劍. 大數(shù)據(jù)隱私管理[J]. 計(jì)算機(jī)研究與發(fā)展， 2015， 52（2）：265-281.

[6] JIA J J，YAN G L，XING L C. Personalized sensitive attribute anonymity based on p-sensitive k anonymity[C]. International Conference on Intelligent Information Processing. ACM， 2016： 54.

[7] SWEENEY L. K-anonymity： a model for protecting privacy[J].? International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10（5）： 557-570.

[8] MACHANAVAJJHALA A，GEHRKE J，KIFER D， et al. L-diversity： privacy beyond k-anonymity[C]. Atlanta：Proceedings of the 22nd International Conference on Data Engineering，2006： 24-24.

[9] LI N，LI T，VENKATASUBRAMANIAN S. t-Closeness： privacy beyond k-anonymity and l-diversity[C]. 2007 IEEE 23rd International Conference on Data Engineering. IEEE Computer Society， 2007.

[10] WONG R C， LI J， FU A W， 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，2006：754-759.

[11] XIAO X ，TAO Y.Anatomy： simple and effective privacy preservation[C]. Proceedings of the 32nd International Conference on Very Large Data Bases， 2006，139-150.

[12] 谷汪峰，饒若楠. 一種基于K-anonymity模型的數(shù)據(jù)隱私保護(hù)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件，2008（8）：65-67.

[13] 焦佳. 社會(huì)網(wǎng)絡(luò)數(shù)據(jù)中一種基于K-degree-l-diversity匿名的個(gè)性化隱私保護(hù)方法[J]. 現(xiàn)代計(jì)算機(jī)：專業(yè)版，2016（29）：45-47，60.

[14] 姜火文，曾國蓀，馬海英. 面向表數(shù)據(jù)發(fā)布隱私保護(hù)的貪心聚類匿名方法[J].? 軟件學(xué)報(bào)， 2017，28（2）：341-351.

[15] 張健沛，謝靜，楊靜，等. 基于敏感屬性值語義桶分組的T-closeness隱私模型[J]. 計(jì)算機(jī)研究與發(fā)展，2014，51（1）：126-137.

[16] 曹敏姿. 微數(shù)據(jù)發(fā)布中的個(gè)性化隱私保護(hù)方法研究[D]. 烏魯木齊：新疆大學(xué)， 2018.

[17] 毛慶陽，胡燕. 基于聚類的S-KACA匿名隱私保護(hù)算法[J]. 武漢大學(xué)學(xué)報(bào)：工學(xué)版， 2018，51（3）：276-282.

[18] LIU X W，XIE Q Q，WANG L M. Personalized extended （α， k）-anonymity model for privacy preserving data publishing[J]. Concurrency & Computation Practice & Experience， 2016，33（2）：55-67.

[19] 金華，張志祥，劉善成，等. 基于敏感性分級(jí)的（αi，k）-匿名隱私保護(hù)[J]. 計(jì)算機(jī)工程，2011，37（14）：12-17.

[20] DOCIN[EB/OL]. https：//usa.ipums.org/usa/index.shtml

[21] LI T，LI N，JIAN Z，et al. Slicing： a new approach for privacy preserving data publishing[J]. IEEE Transactions on Knowledge & Data Engineering，2012， 24（3）：561-574.

[22] LI B，LIU Y，XU H，et al. Cross-bucket generalization for information and privacy preservation[J]. IEEE Transactions on Knowledge & Data Engineering，2017，30（3）：449-459.

（責(zé)任編輯：杜能鋼）