云環(huán)境下基于匿名方法的隱私保護技術(shù)實現(xiàn)

趙宏偉++徐嘉勃

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 [l]-diversity模型的介紹

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

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

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

3 模型和算法描述

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

3.1 K-匿名算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 信息損失度

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

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

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

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

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

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

[IL=SSESST] （3）

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

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

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

4 匿名化實驗平臺的搭建

4.1 實驗環(huán)境

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

實驗環(huán)境：Tomcat、MyEclipse、Mysql

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

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

4.2 匿名化實驗平臺功能分析

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

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

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

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

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

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

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

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

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

（2） 計算信息損失度

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

5 總結(jié)

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

參考文獻：

[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-匿名的隱私保護方向研究[D].哈爾濱工程大學(xué)，2012.

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

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

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

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

[8] 張志祥.基于匿名模型的數(shù)據(jù)發(fā)布隱私保護技術(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-匿名的隱私保護算法研究[D].天津大學(xué)，2010.

[12] 姜寶彥.基于多屬性泛化的K-匿名算法的設(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] 劉堅.K-匿名隱私保護問題的研究[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-匿名的隱私保護算法研究[D].天津大學(xué)，2010.endprint