云环境下基于匿名方法的隐私保护技术实现

赵宏伟++徐嘉勃

摘要：文章首先介绍了当前关于隐私保护的模型；然后结合多维映射的思想实现了一种K-匿名模型的算法和一种L-diversity模型的算法，同时在实现K-匿名模型的算法时，采用欧几里得矢量距离计算了不同K值下匿名化数据表后的信息损失度，并通过实验数据验证了信息损失度随着K值的增大而增大的预期结论。最后，文章实现了匿名化数据实验平台可供医疗研究机构。

关键词：K-匿名；L-diversity；多维映射；欧几里得矢量距离；隐私保护

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）32-0053-03

1 概述

近年来随着数据挖掘技术的快速发展，大量数据中的知识和价值开始被人类利用起来，从而创造新的价值造福于人类。尤其是在医疗信息发布领域，里面包含大量用户身体状况等隐私信息，这些内容不仅仅是医生进行疾病预防的重要依据，而且是医学研究的重要依据。对这些数据进行合理的发布，意义重大。

对要发布的数据表进行匿名化操作处理，是实现隐私保护的较为有效的技术手段之一。即在数据发布以前，首先去掉一些能够唯一标识一个个体的属性，然后采用一些方法对其中的一些属性进行匿名化处理，使得发布的信息不能完全显示用户的信息，从而使攻击者无法从发布的信息中通过链接攻击暴露用户的敏感信息，从而达到隐私保护的效果。

K-匿名隐私保护技术是Samarati和 L Sweeney 在1998年提出来的[1]，2002年，L.Sweeney将它正式命名为K-匿名模型[2]。在数据发布应用场景中，该匿名化技术可以有效地防止攻击者通过链接攻击的手段获取用户的敏感信息。在最近几年中，基于K-匿名的隐私保护技术已经成为很多科研院校和科研机构研究的热门课题之一[3-14]。

2 匿名化技术的基本概念

2.1 K-匿名技术的相关概念

1） 显示标识符属性（Idenyifiers）：表示一个个体或者是一条记录的唯一标识。在数据发布之前，通常是会被删除的。例如，身份证号、姓名等。

2） 準标识符属性（Quasi-Idenyifiers，QI）：在给定的数据表T=（[A1]，[A2]，[…]，[An]），其中表T中的一组最小的属性集合QI=（[Ai1]，[Ai2]，[…]，[Aim]）（[i1

3） 敏感属性（sensitive attributes，SA）：数据表发布时，进行保密设置的属性，即一些用户比较敏感的信息。如薪水，疾病，电话等。

4） 等价类（QI-group）是指经过泛化处理后的表T，在准标识符属性上取值完全相同的记录的集合。

5） 对于准标识符，可以分为两类。其中一类是数值型，一般被泛化成区间。另一类是分类型，一般的做法是用一个更一般、更普通的值来替代。

下面参考[6]给出K-匿名模型的定义：

K-匿名（K-anonymity）给定正整数k，表T=（[A1]，[A2]，[…]，[An]）以及它的准标符QI（[Ai1]，[Ai2]，[…，][Aid]），如果对于任何一个元组t[∈]T在表中存在至少k-1条其他元组[t1]（[Ai1]，[Ai2]，[…]，[Aim]）[=…]（[Ai1]，[Ai2]，[…]，[Aim]），那么该匿名化的数据表T满足k-匿名约束。

在判断一张经过匿名化后的数据表是否满足K-匿名时[14]，一般可以通过划分等价类的方式来进行判断。所谓等价类（QI-group），是指除了其中的敏感属性（SA）外，各个准标识符（QI）的值完全相同。

2.2 [l]-diversity模型的介绍

由上面的介绍可知，经过泛化处理后的数据，仍然可能受到同质攻击以及背景知识攻击。2006年，Machanavajjhala提出了[l]-diversity模型[16，17]，这种模型在k-匿名模型的基础上，增加了对敏感属性的约束，这种模型规定匿名化后的每个等价类中的敏感属性都必须包含[l]个不同的值。这种模型很好的解决了K匿名模型不能抵御同质攻击和背景知识攻击的缺陷。

下面根据[18]对[l]-diversity多样性模型的定义。

L-多样性（[l]-diversity），给定正整数[l]，以及数据表T，准标识符QI，和敏感属性[As]，在满足k-匿名约束的同时，对于匿名化后的数据表T，其中的每个等价类（QI-group），设[s]是在[Gi]中出现最多的敏感属性S的值，[qs]是它所对应的元组集合，如果均有[qsG<=1l]，那么称表T满足[l]-多样性约束。

3 模型和算法描述

文章在学习了总结了前人的算法的基础上，采用多维映射的思想[7]，即在划分等价类时，把多维的准标识符映射到一维上进行处理，实现了K-匿名模型的一种算法和[l]-diversity的模型的算法。在实现基于K-匿名的算法时，通过分治迭代的思想划分等价类，每次划分时，选取多样性最多的一个属性进行排序，然后从中间一分为二，直到每个等价类的记录数在K到2K-1之间为止。在实现基于[l]-多样性模型的算法时，通过循环使得每个等价类的记录数均为K，并且满足每个等价类中敏感属性出现的概率均不大于1/[l]。

3.1 K-匿名算法描述

输入：K值、导入原始数据表；

输出：匿名化后的数据表；

Step1：首先判断K值输入是否合法，如果K值大于等于2并且小于等于记录数的一半，进入Step2；

Step2：在准标识符中，选择数值型的标识符属性进行泛化。首先会判断哪个准标识符的多样性最多，就选取哪个准标识符进行排序，然后通过记录中间的下标，已该下标进行一分为二，记录此时的list的头start和尾end。则此时记录的中间下标为（start+end）/2。然后进入Step3进行迭代；

Step3：然后对Step2中一分为二的两个List，即（start，mid-1）、（mid+1，end）进行Step2进行迭代，直到使得每个等价类的个数均在K到2K-1之间，停止迭代。进入Step4；

Step4：然后通过记录的小标，将原始表分为n个等价类，分别统计每个等价类的每个准标识符的最大值Max和最小值Min，然后将各个等价类的准标识符修改为Min-Max这个形式区间值，完成匿名化的工作，进入Step5；

Step5：然后将上面修改的结果遍历输出。

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

输入：K值，L值，原始数据表。

输出：匿名化后的数据表。

Step1：首先判断K值输入是否合法，如果K值大于等于2并且小于等于记录数的一半并且L值也大于等于2并且L值小于等于K值，进入Step2；

Step2：初始时将每个等价类的大小定为K。通过总记录数（S）/等价类的大小（K）值，求出等价类的个数，即循环的次数。如果刚好整除，则有所等价类的大小均为K，如果有余数，则将多余的数据舍去。然后进入循环Step3；

Step3：通过统计所有准标识符的多样性，选择多样性最大的准标识符，并按照这个准标识符进行排序。然后按照顺序往等价类中放置数据，这里往进放的数据的敏感属性值不同，直到往里面放的数据的敏感属性的多样性大于等于L值，里面才可以放与前面放置的敏感属性值相同的数据。直到使每个等价类的大小刚好为K值。然后进入Step4；

Step4：分别统计每个等价类的每个准标识符的最大值Max和最小值Min，然后将各个等价类的准标识符修改为Min-Max这个形式区间值，完成匿名化的工作，进入Step5；

Step5：然后将上面修改的结果遍历输出。

3.3 信息损失度

实验在选取K-匿名算法的基础上，通过计算欧几里得距离（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]表示等价类的个数，[Xij]表示表中数据在空间上的位置，X-i表示第i个等价类的重心（空间的平均值），X-表示整张表的重心（空间的平均值）。

SSE代表每个等价类中所有准标识符属性（[Ai1]，[Ai2]，…，[Aid]）在空间上的位置到该等价类所有准标识符构成的空间的重心的距离之和。

SST代表整张表的所有准标识符属性（[A1]，[A2]，…，[An]）在空间上的位置到整张表所有准标识符构成的空间的重心的距离之和。

[IL=SSESST] （3）

IL为衡量信息损失度的度量标准。其中IL越小，信息损失量越小，反之越大。

如表1，为本实验中在选取不同的K值产生的计算结果。

从上图我们可以看出，信息损失量IL随着变量K的增大而增大，也验证了实验预期的结论。

4 匿名化实验平台的搭建

4.1 实验环境

操作系统：Windows7旗舰版

实验环境：Tomcat、MyEclipse、Mysql

编程语言：HTML+CSS+JavaScript、jsp/Servlet

编程模式：MVC设计模式

4.2 匿名化实验平台功能分析

该实验平台可利用该自身提供的数据集，采用本实验所提供的算法对原来数据库中的数据进行数据清洗、数据匿名化等操作。

（1） 数据清洗

数据清洗的主要功能是清除数据库中的脏数据，进而保证后续匿名化操作的顺利进行。在现实提供的数据集中，可能存在很多属性值不符合泛化要求。比如属性值为空、或者重復值等。因此，在匿名化数据之前，先进行数据清洗。本实验平台提供了数据的修改以及删除操作，以便后续的实验匿名化操作能够顺利完成。

（2） 数据匿名化

数据匿名化是该实验平台的核心模块，模块提供了一种基于K-匿名的算法和一种基于L-多样性的算法供用户选择去匿名化数据，而且提供了一个利用欧几里得矢量距离法计算匿名化后的信息损失度，以供用户参考衡量信息的损失量。

4.3 关键技术

本匿名化实验平台集成了两种模型的算法，可以选择相应的算法设置不同的值进行实验，并可以针对基于K-匿名模型的算法计算在不同K值下的信息损失量，并且可将匿名化的结果以excel的数据格式导出。

（1） 匿名化后的数据表

下表2为经过K-匿名模型的算法匿名化后部分数据表。

（2） 计算信息损失度

在选择了K-匿名模型的算法后，可计算在不同K值下的信息损失度（IL）。图3是当K=2时，该平台给出的计算结果页面。

5 总结

文章首先介绍了当前的隐私保护技术的一些基本概念，重点讲述了K-匿名技术，并详细介绍了K-匿名模型和L-diversity模型的概念、定义。然后结合多维映射的思想实现了一种基于K-匿名模型的算法和一种基于L-diversity模型的算法。在使用中K-匿名模型的算法，文章采用欧几里（Euclidean）得矢量距离的度量方法，计算了在不同K值下的匿名化处理后数据表的信息损失度（IL），并通过实验数据验证了信息损失度随着K值的增大而增大的预期结论。最后，采用上述实现的两种算法，设计并实现了匿名化实验平台。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，Fuzziness and Knowledge-based Systems，2002，10（5）：557-570.

[3] 任向民.基于K-匿名的隱私保护方向研究[D].哈尔滨工程大学，2012.

[4] 魏大林.支持隐私保护的数据发乎技术研究[D].北京交通大学，2015.

[5] 赵泽茂.基于K-匿名技术的隐私保护研究[D].杭州电子科技大学，2013.

[6] 何贤芒.隐私保护中K—匿名算法和匿名技术研究[D].复旦大学，2011.

[7] 苏弘逸.云计算数据隐私保护方法的研究[D].南京邮电大学，2012.

[8] 张志祥.基于匿名模型的数据发布隐私保护技术研究[D].江苏大学，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].天津大学，2010.

[12] 姜宝彦.基于多属性泛化的K-匿名算法的设计与实现[D].大连理工大学，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].上海：东华大学，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].天津大学，2010.endprint