基于K匿名的隐私保护算法研究.doc

基于 K- 匿名的隐私保护算法研究秦晓薇，门爱华，邹妍（赤峰学院计算机科学与技术系，内蒙古赤峰024000）摘 要：随着数据共享的出现与发展，如何合理地保护隐私数据，同时又保证数据的可用性，成为当今信息安全领域面临的重大挑战.K- 匿名是数据发布隐私保护的一种重要方法，它能够有效防止链接攻击所造成的隐私泄露问题. 本文阐述了K- 匿名模型的基本思想，给出了模型的概念描述，给出了一些典型的实现算法，并对隐私保护的未来研究方向进行了展望.关键词：K- 匿名；隐私保护；泛化；数据共享中图分类号：TP311文献标识码：A文章编号：1673- 260X（2010）05- 0014- 03况.在本例中，可以获得选民 Andre 的疾病情况.这就是一个简单的链接攻击.表 1 医疗信息数据表1 引 言随着互联网技术的飞速发展，数据共享为人们发布、检 索和使用数据带来了极大地便利，然而与此同时也带来了 隐私泄漏的安全隐患.已发布的数据经常会无意识地泄漏个 人隐私，这将对隐私数据所有者的利益造成严重的损害.因 此，如何在数据发布中对个人隐私数据进行合理的保护，又 保证数据的可用性，成为当今信息安全领域研究的热点.在现实生活中，为了人口统计、医疗、卫生等研究需要， 一些机构经常要发布相关数据.虽然，在发布的数据中已经 隐匿了个人的标识信息，如姓名、身份证号码等属性，但是， 用户仍然可以通过对发布的数据和其他渠道获得的数据进 行链接处理，推演出隐私数据，从而造成隐私泄露，这就是 链接攻击1.例如，某些属性具有较强的辨认性（如性别、出生 日期、邮编等），使得链接操作的结果只有一条或者几条，这 样目标信息的范围就会极大地缩小，从而泄露个人隐私.如 果在数据发布之前适当地作一些预处理，那么就可以减少 用户作链接操作时候导致这样信息泄露的可能，或者增加 非法用户猜测的难度.1998 年，Samarati 和 L.Sweeney 提出了 K- 匿名模型，该 模型能够防止链接攻击所造成的隐私泄露问题，是隐私保 护的有效方法.本文阐述了 K- 匿名模型的基本思想，给出 了模型的概念描述，分析和评价了一些典型的实现算法，并 对 K- 匿名模型实现算法的未来研究方向进行了展望.2 K-匿 名 模 型2.1 基本思想表 1 是某医院发布的医疗信息数据表，其中，不包含姓 名、身份证号码等能够唯一标识某个病人的属性.如果用户在获得了表 1 的同时，又可以获得选民登记 表，如表 2 所示. 那么，通过两个表在属性Sex，Birthdate， Zipcode上的链接，就可以很容易的确定某个选民的疾病情BirthdateSexZipcodeDisease1/21/762/28/762/28/761/21/764/13/864/13/86MaleMale Male Male Female Female537155370653703537035372553736FluHang Nail Bronchitis Broken Arm Hepatitis Sprained Ankle表 2选民登记表NameBirthdateSexZipcodeAndreBeth Carol Dan Ellen1/21/761/10/8110/1/442/21/844/19/72MaleFemale Female Male Female5371555412902100217402237我们将表 1 中的属性分为敏感属性和非敏感属性.敏感属性指对于相对应的个体来说是不愿意被其他人所知道 的，如 Disease，称为隐私属性.非敏感属性是那些可以与其 他数据表进行链接的属性，如 Birthdate，Sex 和 Zipcode，称为 准标识符.K- 匿名模型的基本思想就是设法切断准标识符与隐 私属性之间的一对一关系来保护隐私属性.数据持有者能够 识别出可以与外部信息相连接的准标识符，并通过检验原 始数据表中在准标识符上相同元组的个数来判断是否会造 成隐私泄漏.即要求所发布的数据表中的每一条记录 r，至少 有 K?1 条记录与 r 在准标识符上的投影值相等,称这样的数定 义 1（属性） 令 B(A1,An)是由有限个元组构成的数据表，其中，A1,An是数据表 B 的有限属性集.给定一个数据表 B(A1,An)，令Ai,AjA1,An，且 元组 tB，则 tAi,Aj表示元组 t 在属性 Ai,Aj 上的值 vi,vj 的有序序列；BAi,Aj表示表 B 在属性 Ai,Aj 上的 投影.定 义 2（准标识符） 给定一个实体集 U，一个特定的实 体表 T(A1,An)，fc：UT 以及 fg：TU，其中 U哿U.则 T 的 准标识符记为 QIT，是一组属性Ai，AjA1,An.其中 Pi U，那么 fg(fc(Pi)QIT)=Pi 成立.定 义 3（K- 匿名）有一个数据表 T(A1,An)，QI 是与数 据表 T 相关的准标识符，当且仅当在 TQI中出现的每一个 有序的值至少要在 TQI中出现 K 次，就称数据表 T 满足 K- 匿名.推 论 1 假设一个数据表 T(A1,An)，QI=（Ai，A）j 是 与表 T 相关的准标识符，其中Ai,AjA1,An，且 T 满足 K- 匿名，那么，在 TAx中出现的每一个值至少要在 TQI中 出现 K 次，其中 x=i,j.表 3 为匿名化表 1 中原始数据后的结果，其满足 2- 匿 名. 在采用准标识符 Birthdate，Sex 和 Zipcode 进行链接攻击 时，在准标识符的投影上至少有两条相同的记录，因此，攻 击者获得真正隐私的概率仅为 50%.一般 K 值越大，对隐私 的保护效果更好，但丢失的信息越多.表 3 2- 匿名约束要求，但还要继续参与 K- 匿名化处理，从而造成了过量的信息损失，降低了数据的可用性.3.2 MinGen(Minimal Generalization)最小泛化算法L.Sweeney 在文献3中提出了 MinGen 算法，并给出了 最小泛化和最小失真的定义. 该算法对原始数据表进行泛 化，找出所有满足 K 匿名约束的表，然后通过计算失真度来 确定具有最高精度的 K 匿名表.MinGen 算法能最大限度地保证泛化后的表满足 K- 匿 名约束的要求，而且能够对单元的数据进行泛化，这样泛化 的结果信息损失较小.但是该算法在原始数据表规模比较大 的时候，对表的所有可能元组的泛化将会成为 NP 难题.3.3 Classfly 和 Classfly+ 算法杨晓春、刘向宇等人在 2005 年提出了 Classfly 算法4， 并于 2006 年提出了支持多匿名约束的 Classfly+ 算 法 5. Classfly 和 Classfly+ 算法是在 Datafly 算法的基础上，引用了 过滤的思想，即先将原始数据表在准标识符上的投影表中 满足匿名约束的元组过滤出去，再对剩余元组中不同属性 值个数最多的属性进行泛化，如有满足匿名约束的元组再 过滤出去，反复执行上述的泛化和过滤操作，直到不满足K- 匿名约束的元组个数小于 K 为止，最后将不满足匿名约 束的元组抑制.Classfly 和 Classfly+ 算法通过泛化过滤机制，使得符合 多约束的元组不参与以后的泛化操作，减少信息损失，保证 K- 匿名化的数据精度.3.4 Incognito 算法Incognito 算法6由 K.LeFevre 等人提出.该算法首先构建 包含所有全域泛化方案的泛化图 （Generalization Graph）， 然后自底向上的深度优先算法对原始数据进行泛化，每次 选取最优泛化方案前，预先对泛化图进行抑制以缩小搜索 范围，不断进行以上操作直到数据满足 K- 匿名约束.Incognito 算法没有针对信息损失给出有效解决方法，导 致信息损失大，且分布的数据也有泄漏敏感信息的可能.3.5 多维 K- 匿名算法多维 K- 匿名算法是在多维空间上对所有元组进行划 分，使划分的每个子集中元组个数至少为 K，然后对准标识 符上的多个属性值同时进行泛化，使划分的每个元组子集 具有相同值.Mondrian 算法7是一种典型的多维 K- 匿名划分方法， 它的设计是在简单满足 K- 匿名模型要求的前提下，追求数 据划分精度的最大化. 但是该算法只能对连续属性划分，对 不连续属性处理能力较差.而实际发布的数据属性多数是不 连续的，如 Birthdate，Zipcode 等，这样就使得该算法的实际 应用性降低.如果两组数据分布具有相同数值范围但数据分 布不同，那么数据分布离散程度高的数据安全性高于数据 分布相对集中的数据，因此，Mondrian 算法不能很好地平衡3 K-匿名模型实现算法 当前，K- 匿名的研究主要集中在如何对原始数据表进 行有效的匿名化，即实现匿名效果最好、数据可用性最高、 且时间空间花销最小.通常，采用泛化和抑制技术来实现 K- 匿名.泛化是对数据进行更概括、抽象的描述，例如对整数 5 的一种泛化形式是3，6，因为 5 在区间3，6内；而抑制就是 直接从数据表中删除一些属性值或元组.本节对一些典型的 K- 匿名实现算法进行了分析和评价.3.1 Datafly 算法L.Sweeney 在文献2中提出了 Datafly 算法.该算法将原 始数据表在准标识符上的投影作为子表，当子表中不满足 K- 匿名约束的元组数目大于 K 时，将子表中不同属性值个数最多的属性进行泛化，并循环上述步骤，当循环结束后，BirthdateSex ZipcodeDisease*/*/76 Male53706，53715*/*/76 Male53706，53715*/*/76 Male53703*/*/76 Male53703*/*/86 Female53725，53736*/*/86 Female53725，53736Flu Hang Nail Bronchitis Broken Arm HepatitisSprained Ankle熵的多维 K- 匿名划分算法.该算法采用自顶向下的贪心方法对准标识符空间不断地划分，直至所有的子标识符空间 不可再分.在划分过程中，总是选择数据离散程度最高的维 对数据进行划分，并采用熵作为划分原则，每组划分结果中 的数据点分布相对离散，这样，将会减小竞争对手正确猜测 数据点实际值的概率，从而在保证数据划分精度的同时进 一步提高了划分结果的安全性.文献9提出了能够有效降低匿名信息损失的基于多维泛化路径的完整 Filter K- 匿名算法和部分 Filter K- 匿名 算法.算法的基本思想类似于 Incognito 算法，首先对原始数 据表进行匿名化处理，构建包含所有全域泛化方案的泛化 层次结构图，在进行路径选择之前剔除满足要求的元组到 结果表里，使它们不参与泛化，然后将余下的元组按不同路 径参与不同泛化. 这两种算法根据 N 维泛化层次结构图生 成的路径集，在泛化过程中不破坏泛化层次，将满足要求的 元组提前保存在结果数据集里，获取最优的 K- 匿名数据 集，从而提高匿名数据精度和处理效率.前面所提到 K- 匿名算法，都是针对静态数据而言，未 考虑数据动态变化时带来的挑战.在动态环境下，数据通常 会随时间的推移增加或减少，数据发布要求亦会不相同.文 献10中提出了一种能够适应动态数据需求的算法基 于 R 树多维 K- 匿名算法.该算法通过将准标识符属性值转 化为空间的点数据来构造 R 树，其中每个元组都是叶子节 点，那么用该叶子节点的父亲节点的区域代替所有孩子节 点，由于每个父亲节点的孩子节点数目不小于 K，所以算法 保证所有替代节点都是至少有 K 条同样的记录. 这种算法 对于一些经常变更的数据集有较好的响应时间和信息保存 完整度.4 总 结 与 展 望数据共享以及数据获取渠道的多样化，使得隐私保护 成为人们关注的焦点.K- 匿名模型可以有效防止链接攻击 所造成的隐私泄露问题.研究表明，采用 K- 匿名技术在一 个原始多属性数据表基础上导出最优的匿名数据表是一个 NP 难题，因此，很大一部分实现 k- 匿名的算法研究着眼于 设计高效的近似算法以有效匿名化原始数据.大部分现有 K- 匿名实现算法都是基于静态数据集的，且，数据的变化一般都不是完全随机、独立的，数据与数据之间，数据与数据变化之间，都是相互关联的.因此，怎样在 这种更加复杂的环境下，实现对动态数据的利用和隐私保 护，是一个更具挑战的难题，有待于进一步的研究.参 考 文 献 ：1Sweeney L. K-anonymity: a model for protecting priva- cyJ. International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, 2002, 10(5): 557-570.2Sweeney L.Computational Disclosure Control: Aprimer on data privacy protection. Ph.D. Thesis, Mas-sachusetts Institute of Technology, 2001:67-82.3Sweeney L. Achieving k-anonymity privacy protection using generalization and suppression J. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 2002, 10(5):571-588.4Liu XY, Yang XC, Yu G. A representative class basedprivacy preserving data publishing approach with high precisionJ. Computer Science, 2005,32(9A):368?373.5杨晓春,刘向宇,王斌,于戈.支持多约束的 K-匿名化方法J. Journal of Software, 2006,17(5):1222-1231.6LeFevre K, DeWitt D, Ramakrishnan R. Incognito: Ef- ficient Full -domain k -anonymity Z. In Proc. Of the ACM SIGMOD