基于k-匿名的隐私保护

摘 要:随着数据挖掘等相关技术的快速发展,数据过程中敏感信息的泄漏问题也日益突出。在数据的使用过程中,对数据分析的同时,需要一种既能保护数据的完整性,又能对隐私数据进行保护的方法,即隐私保护。隐私保护已成为数据库安全研究中的一个新热点。k-匿名技术就是一种在数据过程中实现隐私保护的有效方法。分析了基于k-匿名的隐私保护的概念、k-匿名模式、k-匿名模式保护数据中个人信息的方法以及k-匿名模式存在的问题,同时对一些用来克服这些问题的加强模式进行了研究,总结了一些可以用来实施k-匿名模式的主要技术。

关键词:数据挖掘 隐私保护 k-匿名

中图分类号:TP39文献标识码:A 文章编号:1007-3973 (2010) 03-041-03

1引言

随着信息技术,特别是网络技术、数据存储技术和高性能处理器技术的飞速发展,海量数据的收集管理和分析变得越来越方便,知识发现和数据挖掘更是在一些深层次的应用中发挥了积极的作用。但与此同时,也带来了隐私保护方面的诸多问题。例如,治安系统中的违法记录,银行卡客户的交易行为,电信用户的个人信息,购房等信息中的关联关系,都对政府和企业决策具有相当重要的意义,但同时又都是公民非常注重的个人隐私。所以,如何在数据挖掘过程中解决好隐私保护的问题,目前已经成为数据挖掘界的一个研究热点。

首先需要明确的是,可能泄露隐私的并不是数据挖掘技术本身,而是数据挖掘方法的特定应用和具体过程。数据挖掘有一个重要特征,就是从大量数据中挖掘得到模式或者规则,通常是针对综合数据而非细节数据。那么,我们是否可以基于非精确的原始数据而抽取出准确的模式与规则呢?实现隐私数据的合理保护和基于统计数据的模式抽取两者兼得,正是隐私保护数据挖掘方法研究的出发点和最终目标。

2 k-匿名模式

越来越多的机构正在通过交换或者有关个人的未经整理的信息来共享资源。这些数据通常不包括用户标识符、准标识符。例如,个人的姓名、医保卡号、家庭住址通常不包括在内。假定这些个人信息是未被识别的,那么他们的隐私,如诊断的病情信息就可以得到保护。

然而,采用这种未识别的处理方式并不能保护数据中的个人隐私。Sweeney报道了在美国,87%的人可以根据结合他们的几项属性而被分辨出来:性别、生日和5位数的邮政编码。Sweeney研究了有关Massachusetts州总督的医疗记录,假设医疗记录以匿名模式存在,结果显示总督的医疗数据可以通过链接攻击而被分辨出来。Massachusetts州的投票注册记录包括名字、性别、邮政编码和生日,而在医疗记录中,性别、邮政编码、生日是对病人病情进行诊断的依据,需要记录。这样通过对两个表进行链接,如图1所示,就可以得到个人的身体健康状况,造成个人隐私泄漏。

图1链接攻击

Samarati和Sweeney提出一种隐私保护模式――k-匿名模式。如果数据集中的每一个记录都与至少k-1个关于这个数据集中的准标识符属性记录相同,那么这个数据集满足k-匿名,这个数据集就被称为k-匿名。结果,在k-匿名数据集中,个人就无法从最少k-1个个人群中被分辨出来。

例如,表1显示了一个原始的医疗数据集。它不包括个人的身份证号、医保号、姓名、家庭地址等标识符。但一些准标识符,如性别、年龄和邮政编码依然存在于表1中,这些属性集可以间接的用于分辨个人的信息。通过这种独特的组合,病人的医疗信息就可能被泄漏。

表 1原始医疗数据集

为了避免侵犯隐私,表1可以修改为表2。

表 2表1的k-匿名表

在表2中,年龄以间隔形式分组,邮政编码被集束到广大地区,‘*’代表一个任意数字。一项准标识符中的记录至少与其他3个记录相同,因此,没有任何个人可以被识别。

由于k-匿名模式的简洁性和适用于多种算法的属性,k-匿名模式在数据中变得非常流行。但是,在受到攻击的情况下,k-匿名模式仍然会泄漏一些敏感的信息,因此,它并不能完全保证隐私的安全性。

3加强型k-匿名模式

在受到以下两种攻击的情况下,k-匿名模式可能会揭露一些敏感的信息。

(1)对k-匿名表的同质性攻击

张三和李四是两个并不和睦的邻居。张三知道李四最近到医院检查,张三试图通过医院的与表2相似的k-匿名的医疗数据表推断出李四的病情。他知道李四是年龄40多岁,居住地的邮政编码为650500。李四一定属于报告编号为9、10、11、12其中之一。所有这四个人都患有神经衰弱。张三可以确切地知道李四患有神经衰弱。

因此,k-匿名表中的敏感属性的相似性可能导致个人信息的泄漏。

(2)利用背景知识对k-匿名表进行攻击

李明和赵宁是好朋友,但李明不想让赵宁知道他的病情。赵宁知道李明到医院检查了病情,可并不知道李明病情如何。赵宁得知李明的病情就在与表2相似的k-匿名的医疗数据表中。李明是25岁,居住地的邮政编码为650000。所以,李明的病情报告一定是1、2、3或者4。基于这个表,赵宁并不能知道李明的病情。但是,他知道李明很久没有患流行性感冒了,所以,赵宁可以推断出李明患了抑郁性神经症。

因此,k-匿名模式并不可以保护个人信息免受利用背景知识进行攻击。

3.1L-多样性匿名模型

Machanavajjhala et al.提出了一种叫做L-多样性的模型来加强k-匿名模型。在已经的表中,一个k-匿名组包含的敏感属性中最少有L个具有很好代表意义的值。例如,在表2中,报告5,6,7和8形成了一个具有3种多样性的组。报告中包含了出现频率为25%,25%和50%的值,并且没有一个值具有主导的功能。但是,使每一个k-匿名组来做为已数据集的L平衡值,可能会降低数据集中准标识符信息的有效性。

一种有效的实用模型通常会对数据效用实行有效的保护。L-多样性模型很有效,但并不一定有用。如果我们设法保护敏感属性中的每个值,那么它可能不会敏感属性或者准标识符。尤其是针对背景知识的攻击,我们很难推测出我们的敌人有多少背景知识,如果对手有很强的知识背景,任何已的数据都会变得不安全。

3.2 ( ,k)-匿名模型

一个更实际的做法是不考虑每个敏感属性中的值为敏感。例如,人们可能想把成绩不及格的作为隐私,而对于考试成绩优秀或者良好的不视为隐私。如果我们只有少量的敏感值,合理的保护措施就是从一个k-匿名组到一个敏感值的推理可信度必须低于一个界限值。这就是( ,k)-匿名模型最基本的概念。这个模型使推理可信度到敏感之间的值低于 ,一个用户自定义的界限值。这个模型简洁并且有效地防止针对敏感值的同质性攻击。如表3所示:

表3(0.25, 4)-匿名表

表3提供了一个( ,k)-匿名表。在这个表中,流行性感冒和神经衰弱被认为不是敏感的信息,从(女,30-39, 65*)到抑郁性神经症推理可信度值是25%。

3.3 基于模板的模型

另一个防止同质性攻击的模型就是基于模板的模型。这种模型使用户在公布的数据模板中指定哪些类型的推理渠道应该被阻止。模型设法除去已数据集中的一些敏感的推理,并且保护数据的分类特征。模型使个人组与敏感值之间的敏感信息推理可信度低于用户指定的级别。基于模板模型对于那些已经确切知道哪些推理渠道应该被阻止的用户来说是好的,但是不适用于那些并不了解哪些推理渠道应该被阻止的用户。

4多样的 k-匿名方法

有几种不同的方法来把数据集转化为k-匿名,或者成为k-匿名法。

4.1泛化

达到k-匿名的目的的一个普通的方法就是泛化――一个属性值是根据它的属性域的级别来归纳的。例如,生日的格式日/月/年被格式月/年代替。所有的属性域都在层次化的结构中。对于属性来说,拥有更少的值的域比拥有更多的值的域更加普遍一般。最一般的域只包含了一个值。例如,生日格式日/月/年是一个低级别的域,年在生日中是一个高一点的域。最一般级别的生日域包含了未知值“*”。用数字表示的属性也在一个层次化的结构中,那就是{值,间隔,*}。间隔可以由用户或者机器算法决定,比方说一个离散化。

4.2全局的重新编码和局部重新编码匿名法

全局的重新编码和局部重新编码匿名法是两种实现k-匿名的方法,全局重新编码的另一个名字就是全域一般化。在全局的重新编码中,一般化发生在属性域层。当一个属性值被一般化了,每一个值都会被新的一般化的值所代替。许多方法都是全局的重新编码模型,例如DateFly和Incognito就是两个典型的例子。全局的重新编码的优点就是一个匿名的观点有统一的域,但是它可能导致一些信息细节的不必要丢失。

当准标识符不够大时,优化全局重新编码法是有可能的。优化在这里是根据减少一般化的步骤来实现k-匿名的。Incognito和k-optimise 就是两个例子。但是,时间复杂度的最优化查询是准标识符大小的最终指数通过比原始查询具有更快的速度来实现的。这些最优化算法只有在小的准标识符的数据中才可以得到最有用。

另一个主要的问题就是全局重新编码法会过度泛化表格并造成不必要的失真。下面我们用一个例子来解释这个问题。假如我们有100条记录,在这些报告中,只有两个可以通过他们的邮编来识别出来。把所有的值根据这两个值而泛化为k-匿名表会造成邮编栏的许多失真。

局部重新编码法是在单元对属性值进行泛化的。一个被泛化了的属性值与原始值共存。局部重新编码法不会过度泛化一个表,以此来最小化匿名表的失真。上面关于全局重新编码的过度泛化问题的例子,局部重新编码的解决方案只将这两个记录和其他(k-2)个报告泛化。

5结论

在本文中,介绍了k-匿名模型,并讨论了它是怎样保护数据中的私人信息的;介绍了一些有关k-匿名模型的典型的问题,以及克服这些问题的加强模型;总结了一些用来实现k-匿名的主要技术。

k-匿名模型和它的变量之间还有以下一些方面值得探讨:

(1)如何确定数据集中的k-匿名的准标识符。

(2)隐私保护和数据的准确性之间的最好的协议是什么?

(3)一个数据集可以以不同的方式来进行匿名。怎样衡量k-匿名表的质量?

(4)当有一个以上的匿名表因为更新或者给不同的用户时,会发生什么样的隐私风险?

大多数这样的问题对于现实中k-匿名数据程序来说是至关重要的。我将把这些问题作为以后的研究方向。

参考文献:

[1]张鹏,童云海, 唐世渭,杨冬青,马秀莉.一种有效的隐私保护关联规则挖掘方法[J]. Journal of Software, Vol.17, No.8, August 2006, pp.1764 1774.

[2]Sweeney L, k-anonymity: a model for protecting privacy. International journal on uncertainty, Fuzziness and knowledge based systems, 10(5):557 570, 2002.

[3]Samarati P and Sweeney L, Generalizing data to provide anonymity when disclosing information (abstract). In Proceedings of the Seventeenth ACM SIGACTSIGMOD- SIGART Symposium on Principles of Database Systems, page 188, 1998.

[4]Samarati P, Protecting respondents’ identities in Microdata release. IEEE Transactions on Knowledge and Data Engineering, 13(6):1010 1027, 2001.

[5]Machanavajjhala A, Gehrke J, and Kifer D, l-diversity: privacy beyond k- anonymity. In Proceedings of the 22nd International Conference on Data Engineering (ICDE06), page 24, 2006.

[6]Wong R, Li J, Fu A, and Wang K, (alpha, k)-anonymity: An enhanced kanonymity model for privacy-preserving data publishing. In Proceedings of the twelfth ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pages 754 759, 2006.

[7]Wang K, Fung BCM, and Yu PS, Template-based privacy preservation in classification problems. In ICDM05: The fifth IEEE International Conference on Data Mining (ICDM’05), pages 466 473, 2005.

[8]Sweeney L, Achieving k-anonymity privacy protection using generalization and suppression. International journal on uncertainty, Fuzziness and knowledge based systems, 10(5):571588, 2002.

[9]LeFevre K, DeWitt DJ, and Ramakrishnan R, Incognito: Efficient full-domain k-anonymity. In SIGMOD’05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 49 60, 2005.

[10]Bayardo R and Agrawal R, Data privacy through optimal k-anonymization. In ICDE05: The 21st International Conference on Data Engineering, pages 217 228, 2005.