趙宏偉++徐嘉勃

摘要：文章首先介紹了當(dāng)前關(guān)于隱私保護(hù)的模型；然后結(jié)合多維映射的思想實(shí)現(xiàn)了一種K-匿名模型的算法和一種L-diversity模型的算法，同時(shí)在實(shí)現(xiàn)K-匿名模型的算法時(shí)，采用歐幾里得矢量距離計(jì)算了不同K值下匿名化數(shù)據(jù)表后的信息損失度，并通過實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了信息損失度隨著K值的增大而增大的預(yù)期結(jié)論。最后，文章實(shí)現(xiàn)了匿名化數(shù)據(jù)實(shí)驗(yàn)平臺(tái)可供醫(yī)療研究機(jī)構(gòu)。

關(guān)鍵詞：K-匿名；L-diversity；多維映射；歐幾里得矢量距離；隱私保護(hù)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）32-0053-03

1 概述

近年來隨著數(shù)據(jù)挖掘技術(shù)的快速發(fā)展，大量數(shù)據(jù)中的知識(shí)和價(jià)值開始被人類利用起來，從而創(chuàng)造新的價(jià)值造福于人類。尤其是在醫(yī)療信息發(fā)布領(lǐng)域，里面包含大量用戶身體狀況等隱私信息，這些內(nèi)容不僅僅是醫(yī)生進(jìn)行疾病預(yù)防的重要依據(jù)，而且是醫(yī)學(xué)研究的重要依據(jù)。對(duì)這些數(shù)據(jù)進(jìn)行合理的發(fā)布，意義重大。

對(duì)要發(fā)布的數(shù)據(jù)表進(jìn)行匿名化操作處理，是實(shí)現(xiàn)隱私保護(hù)的較為有效的技術(shù)手段之一。即在數(shù)據(jù)發(fā)布以前，首先去掉一些能夠唯一標(biāo)識(shí)一個(gè)個(gè)體的屬性，然后采用一些方法對(duì)其中的一些屬性進(jìn)行匿名化處理，使得發(fā)布的信息不能完全顯示用戶的信息，從而使攻擊者無法從發(fā)布的信息中通過鏈接攻擊暴露用戶的敏感信息，從而達(dá)到隱私保護(hù)的效果。

K-匿名隱私保護(hù)技術(shù)是Samarati和 L Sweeney 在1998年提出來的[1]，2002年，L.Sweeney將它正式命名為K-匿名模型[2]。在數(shù)據(jù)發(fā)布應(yīng)用場景中，該匿名化技術(shù)可以有效地防止攻擊者通過鏈接攻擊的手段獲取用戶的敏感信息。在最近幾年中，基于K-匿名的隱私保護(hù)技術(shù)已經(jīng)成為很多科研院校和科研機(jī)構(gòu)研究的熱門課題之一[3-14]。

2 匿名化技術(shù)的基本概念

2.1 K-匿名技術(shù)的相關(guān)概念

1） 顯示標(biāo)識(shí)符屬性（Idenyifiers）：表示一個(gè)個(gè)體或者是一條記錄的唯一標(biāo)識(shí)。在數(shù)據(jù)發(fā)布之前，通常是會(huì)被刪除的。例如，身份證號(hào)、姓名等。

2） 準(zhǔn)標(biāo)識(shí)符屬性（Quasi-Idenyifiers，QI）：在給定的數(shù)據(jù)表T=（[A1]，[A2]，[…]，[An]），其中表T中的一組最小的屬性集合QI=（[Ai1]，[Ai2]，[…]，[Aim]）（[i1

3） 敏感屬性（sensitive attributes，SA）：數(shù)據(jù)表發(fā)布時(shí)，進(jìn)行保密設(shè)置的屬性，即一些用戶比較敏感的信息。如薪水，疾病，電話等。

4） 等價(jià)類（QI-group）是指經(jīng)過泛化處理后的表T，在準(zhǔn)標(biāo)識(shí)符屬性上取值完全相同的記錄的集合。

5） 對(duì)于準(zhǔn)標(biāo)識(shí)符，可以分為兩類。其中一類是數(shù)值型，一般被泛化成區(qū)間。另一類是分類型，一般的做法是用一個(gè)更一般、更普通的值來替代。

下面參考[6]給出K-匿名模型的定義：

K-匿名（K-anonymity）給定正整數(shù)k，表T=（[A1]，[A2]，[…]，[An]）以及它的準(zhǔn)標(biāo)符QI（[Ai1]，[Ai2]，[…，][Aid]），如果對(duì)于任何一個(gè)元組t[∈]T在表中存在至少k-1條其他元組[t1]（[Ai1]，[Ai2]，[…]，[Aim]）[=…]（[Ai1]，[Ai2]，[…]，[Aim]），那么該匿名化的數(shù)據(jù)表T滿足k-匿名約束。

在判斷一張經(jīng)過匿名化后的數(shù)據(jù)表是否滿足K-匿名時(shí)[14]，一般可以通過劃分等價(jià)類的方式來進(jìn)行判斷。所謂等價(jià)類（QI-group），是指除了其中的敏感屬性（SA）外，各個(gè)準(zhǔn)標(biāo)識(shí)符（QI）的值完全相同。

2.2 [l]-diversity模型的介紹

由上面的介紹可知，經(jīng)過泛化處理后的數(shù)據(jù)，仍然可能受到同質(zhì)攻擊以及背景知識(shí)攻擊。2006年，Machanavajjhala提出了[l]-diversity模型[16，17]，這種模型在k-匿名模型的基礎(chǔ)上，增加了對(duì)敏感屬性的約束，這種模型規(guī)定匿名化后的每個(gè)等價(jià)類中的敏感屬性都必須包含[l]個(gè)不同的值。這種模型很好的解決了K匿名模型不能抵御同質(zhì)攻擊和背景知識(shí)攻擊的缺陷。

下面根據(jù)[18]對(duì)[l]-diversity多樣性模型的定義。

L-多樣性（[l]-diversity），給定正整數(shù)[l]，以及數(shù)據(jù)表T，準(zhǔn)標(biāo)識(shí)符QI，和敏感屬性[As]，在滿足k-匿名約束的同時(shí)，對(duì)于匿名化后的數(shù)據(jù)表T，其中的每個(gè)等價(jià)類（QI-group），設(shè)[s]是在[Gi]中出現(xiàn)最多的敏感屬性S的值，[qs]是它所對(duì)應(yīng)的元組集合，如果均有[qsG<=1l]，那么稱表T滿足[l]-多樣性約束。

3 模型和算法描述

文章在學(xué)習(xí)了總結(jié)了前人的算法的基礎(chǔ)上，采用多維映射的思想[7]，即在劃分等價(jià)類時(shí)，把多維的準(zhǔn)標(biāo)識(shí)符映射到一維上進(jìn)行處理，實(shí)現(xiàn)了K-匿名模型的一種算法和[l]-diversity的模型的算法。在實(shí)現(xiàn)基于K-匿名的算法時(shí)，通過分治迭代的思想劃分等價(jià)類，每次劃分時(shí)，選取多樣性最多的一個(gè)屬性進(jìn)行排序，然后從中間一分為二，直到每個(gè)等價(jià)類的記錄數(shù)在K到2K-1之間為止。在實(shí)現(xiàn)基于[l]-多樣性模型的算法時(shí)，通過循環(huán)使得每個(gè)等價(jià)類的記錄數(shù)均為K，并且滿足每個(gè)等價(jià)類中敏感屬性出現(xiàn)的概率均不大于1/[l]。

3.1 K-匿名算法描述

輸入：K值、導(dǎo)入原始數(shù)據(jù)表；

輸出：匿名化后的數(shù)據(jù)表；

Step1：首先判斷K值輸入是否合法，如果K值大于等于2并且小于等于記錄數(shù)的一半，進(jìn)入Step2；

Step2：在準(zhǔn)標(biāo)識(shí)符中，選擇數(shù)值型的標(biāo)識(shí)符屬性進(jìn)行泛化。首先會(huì)判斷哪個(gè)準(zhǔn)標(biāo)識(shí)符的多樣性最多，就選取哪個(gè)準(zhǔn)標(biāo)識(shí)符進(jìn)行排序，然后通過記錄中間的下標(biāo)，已該下標(biāo)進(jìn)行一分為二，記錄此時(shí)的list的頭start和尾end。則此時(shí)記錄的中間下標(biāo)為（start+end）/2。然后進(jìn)入Step3進(jìn)行迭代；

Step3：然后對(duì)Step2中一分為二的兩個(gè)List，即（start，mid-1）、（mid+1，end）進(jìn)行Step2進(jìn)行迭代，直到使得每個(gè)等價(jià)類的個(gè)數(shù)均在K到2K-1之間，停止迭代。進(jìn)入Step4；

Step4：然后通過記錄的小標(biāo)，將原始表分為n個(gè)等價(jià)類，分別統(tǒng)計(jì)每個(gè)等價(jià)類的每個(gè)準(zhǔn)標(biāo)識(shí)符的最大值Max和最小值Min，然后將各個(gè)等價(jià)類的準(zhǔn)標(biāo)識(shí)符修改為Min-Max這個(gè)形式區(qū)間值，完成匿名化的工作，進(jìn)入Step5；

Step5：然后將上面修改的結(jié)果遍歷輸出。

3.2 [l]-diversity模型算法描述

輸入：K值，L值，原始數(shù)據(jù)表。

輸出：匿名化后的數(shù)據(jù)表。

Step1：首先判斷K值輸入是否合法，如果K值大于等于2并且小于等于記錄數(shù)的一半并且L值也大于等于2并且L值小于等于K值，進(jìn)入Step2；

Step2：初始時(shí)將每個(gè)等價(jià)類的大小定為K。通過總記錄數(shù)（S）/等價(jià)類的大?。↘）值，求出等價(jià)類的個(gè)數(shù)，即循環(huán)的次數(shù)。如果剛好整除，則有所等價(jià)類的大小均為K，如果有余數(shù)，則將多余的數(shù)據(jù)舍去。然后進(jìn)入循環(huán)Step3；

Step3：通過統(tǒng)計(jì)所有準(zhǔn)標(biāo)識(shí)符的多樣性，選擇多樣性最大的準(zhǔn)標(biāo)識(shí)符，并按照這個(gè)準(zhǔn)標(biāo)識(shí)符進(jìn)行排序。然后按照順序往等價(jià)類中放置數(shù)據(jù)，這里往進(jìn)放的數(shù)據(jù)的敏感屬性值不同，直到往里面放的數(shù)據(jù)的敏感屬性的多樣性大于等于L值，里面才可以放與前面放置的敏感屬性值相同的數(shù)據(jù)。直到使每個(gè)等價(jià)類的大小剛好為K值。然后進(jìn)入Step4；

Step4：分別統(tǒng)計(jì)每個(gè)等價(jià)類的每個(gè)準(zhǔn)標(biāo)識(shí)符的最大值Max和最小值Min，然后將各個(gè)等價(jià)類的準(zhǔn)標(biāo)識(shí)符修改為Min-Max這個(gè)形式區(qū)間值，完成匿名化的工作，進(jìn)入Step5；

Step5：然后將上面修改的結(jié)果遍歷輸出。

3.3 信息損失度

實(shí)驗(yàn)在選取K-匿名算法的基礎(chǔ)上，通過計(jì)算歐幾里得距離（Euclidean）的度量方法計(jì)算了不同K值情況下的信息損失度（IL）。下面給出信息損失度的計(jì)算公式[6]，其計(jì)算方法見（1）-（2）-（3）。

[SSE=i=1gj=1ni（Xij-Xi_）（Xij-Xi_）] （1）

[SST=i=1gj=1ni（Xij-X_）（Xij-X_）] （2）

其中，[g]表示等價(jià)類的個(gè)數(shù)，[Xij]表示表中數(shù)據(jù)在空間上的位置，X-i表示第i個(gè)等價(jià)類的重心（空間的平均值），X-表示整張表的重心（空間的平均值）。

SSE代表每個(gè)等價(jià)類中所有準(zhǔn)標(biāo)識(shí)符屬性（[Ai1]，[Ai2]，…，[Aid]）在空間上的位置到該等價(jià)類所有準(zhǔn)標(biāo)識(shí)符構(gòu)成的空間的重心的距離之和。

SST代表整張表的所有準(zhǔn)標(biāo)識(shí)符屬性（[A1]，[A2]，…，[An]）在空間上的位置到整張表所有準(zhǔn)標(biāo)識(shí)符構(gòu)成的空間的重心的距離之和。

[IL=SSESST] （3）

IL為衡量信息損失度的度量標(biāo)準(zhǔn)。其中IL越小，信息損失量越小，反之越大。

如表1，為本實(shí)驗(yàn)中在選取不同的K值產(chǎn)生的計(jì)算結(jié)果。

從上圖我們可以看出，信息損失量IL隨著變量K的增大而增大，也驗(yàn)證了實(shí)驗(yàn)預(yù)期的結(jié)論。

4 匿名化實(shí)驗(yàn)平臺(tái)的搭建

4.1 實(shí)驗(yàn)環(huán)境

操作系統(tǒng)：Windows7旗艦版

實(shí)驗(yàn)環(huán)境：Tomcat、MyEclipse、Mysql

編程語言：HTML+CSS+JavaScript、jsp/Servlet

編程模式：MVC設(shè)計(jì)模式

4.2 匿名化實(shí)驗(yàn)平臺(tái)功能分析

該實(shí)驗(yàn)平臺(tái)可利用該自身提供的數(shù)據(jù)集，采用本實(shí)驗(yàn)所提供的算法對(duì)原來數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗、數(shù)據(jù)匿名化等操作。

（1） 數(shù)據(jù)清洗

數(shù)據(jù)清洗的主要功能是清除數(shù)據(jù)庫中的臟數(shù)據(jù)，進(jìn)而保證后續(xù)匿名化操作的順利進(jìn)行。在現(xiàn)實(shí)提供的數(shù)據(jù)集中，可能存在很多屬性值不符合泛化要求。比如屬性值為空、或者重復(fù)值等。因此，在匿名化數(shù)據(jù)之前，先進(jìn)行數(shù)據(jù)清洗。本實(shí)驗(yàn)平臺(tái)提供了數(shù)據(jù)的修改以及刪除操作，以便后續(xù)的實(shí)驗(yàn)?zāi)涿僮髂軌蝽樌瓿伞?/p>

（2） 數(shù)據(jù)匿名化

數(shù)據(jù)匿名化是該實(shí)驗(yàn)平臺(tái)的核心模塊，模塊提供了一種基于K-匿名的算法和一種基于L-多樣性的算法供用戶選擇去匿名化數(shù)據(jù)，而且提供了一個(gè)利用歐幾里得矢量距離法計(jì)算匿名化后的信息損失度，以供用戶參考衡量信息的損失量。

4.3 關(guān)鍵技術(shù)

本匿名化實(shí)驗(yàn)平臺(tái)集成了兩種模型的算法，可以選擇相應(yīng)的算法設(shè)置不同的值進(jìn)行實(shí)驗(yàn)，并可以針對(duì)基于K-匿名模型的算法計(jì)算在不同K值下的信息損失量，并且可將匿名化的結(jié)果以excel的數(shù)據(jù)格式導(dǎo)出。

（1） 匿名化后的數(shù)據(jù)表

下表2為經(jīng)過K-匿名模型的算法匿名化后部分?jǐn)?shù)據(jù)表。

（2） 計(jì)算信息損失度

在選擇了K-匿名模型的算法后，可計(jì)算在不同K值下的信息損失度（IL）。圖3是當(dāng)K=2時(shí)，該平臺(tái)給出的計(jì)算結(jié)果頁面。

5 總結(jié)

文章首先介紹了當(dāng)前的隱私保護(hù)技術(shù)的一些基本概念，重點(diǎn)講述了K-匿名技術(shù)，并詳細(xì)介紹了K-匿名模型和L-diversity模型的概念、定義。然后結(jié)合多維映射的思想實(shí)現(xiàn)了一種基于K-匿名模型的算法和一種基于L-diversity模型的算法。在使用中K-匿名模型的算法，文章采用歐幾里（Euclidean）得矢量距離的度量方法，計(jì)算了在不同K值下的匿名化處理后數(shù)據(jù)表的信息損失度（IL），并通過實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了信息損失度隨著K值的增大而增大的預(yù)期結(jié)論。最后，采用上述實(shí)現(xiàn)的兩種算法，設(shè)計(jì)并實(shí)現(xiàn)了匿名化實(shí)驗(yàn)平臺(tái)。endprint

參考文獻(xiàn)：

[1] Samarati P，Sweeney L.Generalizing data to provide anonymity when disclosing information（abstract）[C].Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems，Seattle United States；ACM，1998：188-188.

[2] Sweeney.k-anonymity L.a model for protecting privacy[J].International Journal on Uncertainty，F(xiàn)uzziness and Knowledge-based Systems，2002，10（5）：557-570.

[3] 任向民.基于K-匿名的隱私保護(hù)方向研究[D].哈爾濱工程大學(xué)，2012.

[4] 魏大林.支持隱私保護(hù)的數(shù)據(jù)發(fā)乎技術(shù)研究[D].北京交通大學(xué)，2015.

[5] 趙澤茂.基于K-匿名技術(shù)的隱私保護(hù)研究[D].杭州電子科技大學(xué)，2013.

[6] 何賢芒.隱私保護(hù)中K—匿名算法和匿名技術(shù)研究[D].復(fù)旦大學(xué)，2011.

[7] 蘇弘逸.云計(jì)算數(shù)據(jù)隱私保護(hù)方法的研究[D].南京郵電大學(xué)，2012.

[8] 張志祥.基于匿名模型的數(shù)據(jù)發(fā)布隱私保護(hù)技術(shù)研究[D].江蘇大學(xué)，2010.

[9] Zhang G， Yang Y， Liu X，Chen J. A Time-Series Pattern Based Noise Generation Strategy for Privacy Protection in Cloud Computin[C].Proc. 12th IEEE/ACM Int Cluster， Cloud and Grid Computing （CCGrid） Symp， 2012：458-465.

[10] Blass E.-O， Di Pietro R， Molva R，Цnen M.PRISM： privacy-preserving search in mapreduce[C].Proceedings of the 12th international conference on Privacy Enhancing Technologies， Springer-Verlag， Berlin， Heidelberg， 2012：180-200.

[11] 陳海亮.基于K-匿名的隱私保護(hù)算法研究[D].天津大學(xué)，2010.

[12] 姜寶彥.基于多屬性泛化的K-匿名算法的設(shè)計(jì)與實(shí)現(xiàn)[D].大連理工大學(xué)，2015.

[13] Pei J，Xu J，Wang Z，etal.Maintaining K-anonymity against incremental updates[C].Proceeding of the 19th Int1 conference on Scientific and Statistical Database technology，NewYork，USA：Association for Computing Machinery，2008：264-275.

[14] 劉堅(jiān).K-匿名隱私保護(hù)問題的研究[D].上海：東華大學(xué)，2010.

[15] Cao N， Yang Z， Wang C， Ren K， Lou W.Privacy-Preserving Query over Encrypted Graph-Structured Data in Cloud Computing[C].Distributed Computing Systems （ICDCS）， 2011 31st International Conference on， 2011：393 -402.

[16] Byun J W，SohnY，BertinoE，etal.Secure anonymization for incremental datasets[C].Proceeding of the 3th VLDB Workshop on Secure Data Management，Seoul，Korea，SpringerBerLinHeidelberg：Springer Verlag，2006：48-63.

[17] Ashwin Machanavajjhala，JohannesGehrke，PAshwinMachanavajjhala et al.on the efficiency of checking perfect privacy[C]//Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems，2006：163-172.

[18] 陳海亮.基于K-匿名的隱私保護(hù)算法研究[D].天津大學(xué)，2010.endprint