（计算机应用技术专业论文）增量数据集下的隐私保护技术研究.pdf

指导教师： 协助指导教师： 张晓琳教授 单位：塑鍪重型垫奎兰 论文提交日期：2 0 10 年0 6 月l2 日 学位授予单位：内蒙古科技大学 单位： 单位： 增量数据集下的隐私保护技术研究 t h ep r i v a c yp r o t e c t i o n s t u d ya g a i n s ti n c r e m e n t a l datasets 研究生姓名：李素伟 指导教师姓名：张晓琳 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 c a n d i d a t e ：l is u w e i s u p e r v i s o r ：z h a n gx i a o - l i n s c h o o lo fl n f o r m m i o ne n g i n e e r i n g i n n e rm o n g o l i au n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y b a o t o u 0 1 4 0 1 0 ，p r c h i n a 关于论文使用授权的说明 本人完全了解内蒙占科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵循此规定) 签名：垄盘准 导师签名：塑盘盐日期：趁坦：兰：丛 内蒙古科技人学硕十学位论文 摘要 随着网络技术的发展和数据库应用领域的不断扩大，政府、企业、个人根据需 要在互联网上发布自己的数据，而一些研究部门则研究他们发布的数据。在这些数 据中包含了社会中各种各样的信息，有些还涉及到个人的敏感信息。信息技术的高 速发展，使得全球信息量成指数形式增长。人们为了获得有用的信息，广泛采用数 据挖掘技术。但是随着数据挖掘技术的不断发展，给数据隐私带来了不小的麻烦。 个人的隐私信息，例如医院的病历数据就包含了个人患有某种疾病的敏感信息。数 据隐私泄露的现象越来越严重，很大程度上给人们的生活带来了困扰。 目前，数据隐私保护技术的查询研究已经形成了大量的理论成果和系统原型， 他们的主要工作大都集中在对静态数据库的匿名保护处理。前期的匿名保护方法是 静态的，而数据库中的数据都是时时在发生变化的，是动态的。如何处理好由多次 发布造成的推断攻击是要研究的重点。动态数据的研究有m 不变性，支持插入和删 除的匿名策略。保持增量k 匿名性，只支持插入的匿名策略。 针对上面研究的不足，提出了一种全新的方法解决了多次发布造成的所有隐私 泄露。首先对这些造成隐私泄露的可能性进行分析，在匿名过程中，保证了匿名数 据的k 匿名，而且也保证了匿名数据的l 一多样性。与此同时，还能够保证多次发布的 匿名数据表在攻击者的推理表中能确保k 匿名性和1 多样性。而且多维数据空间索引 随着维数的增加，其运行时问会成几何指数增长，运行的时问效率会非常低。在此 基础上采用空间填充曲线的方法把多维数据转换成一维数据，这样会大大降低运行 时间，提高了数据的索引效率。 关键词：增量数据集；隐私保护：k 一匿名：l 一多样性 。h-oiir i r r l r 内蒙古科技人学硕+ 学位论文 目录 摘要i a b s t r a c t i i l 背景知识l 1 1 研究背景1 1 2 研究意义3 1 3 国内外研究现状4 1 4 课题的主要内容7 2 数据隐私保护的理论基础8 2 1 隐私保护的匿名化原则8 2 2k 一匿名9 2 3l 一多样性12 2 4h il b e r t 空间填充曲线1 2 2 5 隐私保护模型。1 3 2 5 1 信息损失度l6 2 5 2 匿名化效率18 3 基于增量数据集的匿名原则和算法：2 0 3 1 问题提出2 0 3 2 更新表的插入和研究2 2 3 3 多次发布造成的隐私泄漏情况2 3 3 4 增量更新的安全匿名2 6 3 5 增量更新的匿名化质量2 8 4 实验结果和分析3 2 4 1 实验环境3 2 4 2 原始数据库大小变化性能实验分析3 2 4 3 增量数据集的性能实验分析3 5 结论一3 7 参考文献3 8 在学研究成果4 2 i r ， l， 内蒙古科技人学硕十学位论文 致谢4 3 2 - killi-1 个人等都有自己 些数据中包含了 社会中各种各样的信息，有些还涉及到个人的敏感信息。例如：病人的医疗记录，学生 的个人资料，企业的交易信息以及公民的个人信息等。如果这些信息不经过处理而直接 发布出去就有可能造成个人隐私信息的泄漏，那么就会对企业和个人带来潜在的危害。 信息技术的高速发展，使得全球信息量成指数形式增长。人们为了获得有用的信息，数 据挖掘技术得到了广泛的应用。一些企业和个人有时需要从网上的个人资料中得到有价 值的参考信息，例如，商场希望通过分析消费者的购物行为，获取更大的利润，疾病防 控中心为了进行调查研究，需要收集病人的医疗记录，一些政府机构为了获得该地区的 收入状况，需要统计人们的工资收入等，使得个人隐私完全泄露于公众。随着数据挖掘 技术【l 】的发展和搜索技术的提高，当前应用中出现了大量的隐私破坏行为，隐私保护1 2 j 变得越来越艰巨，数据库安全已成为当今信息安全领域的重要课题，数据库的隐私保护 研究也j 下成为当前信息安全界的一个热门研究方向，但是随着数据挖掘技术的不断发 展，给数据隐私带来了不小的麻烦。数据隐私泄露的现象越来越严重，很大程度上给人 们的生活带来了困扰。 过去对数据库安全的研究，多是授权或加密技术。授权和加密技术对于信息和数据 保护是非常重要的，它们是通过身份认证和数据编码方式来预防外部威胁或未授权的访 问企图。通过对信息安全问题的进一步研究，提出了更高的层次密码技术的要求，要求 相应的保护模型从基于服务器的保护装置到基于客户机的保护模型，以及到后来的逻辑 架构保护模型来确保访问授权策略。为了阻止攻击者识别目标个体在原始数据中的对应 记录，从而进一步获取日标个体的隐私信息，传统的方法将数据中能够唯一识别具体记 录的身份属性，例如身份证号等删除后进行发布。近来的研究表明大量美国居民可以根 据非身份属性集合，例如年龄、性别和邮编等来进行识别。利用这种方法至少能识别一 个具体个体在数据表中的对应记录的属性集合称为准标识属性( q u a s i i d e n t i f i e r sq i ) l j j 这 样的方法在一定程度上可以防止敏感信息的泄漏，却无法避免用户通过非敏感数据，综 合其他外部知识间接推理出敏感信息。当前应用中出现的大量隐私泄漏和攻击行为使得 隐私保护技术的研究成为当前信息安全的一个热点问题。 根据对数据库访问的不同类型，可以将数据库的隐私保护分为受限访问型数据库隐 私保护和自由访问型数据库隐私保护。受限访问型数据库隐私保护主要基于数据的隐私 策略或标记以约束用户对数据的访问，使得不同权限的用户访问特定的内容，最突出的 内蒙古科技人学硕十学位论文 特点是低级别的权限无法访问到高级别的内容，达到保护隐私数据的目的。从实现技术 上讲，受限访问型数据库隐私保护主要基于成熟的传统访问控制( a c c e s sc o n t r 0 1 ) 模型 和策略，但是在多数情况下，数据库是依靠数据持有者的能力，来保护给出的查询结果 中不提供对公众有害的信息，这样的方法在一定程度上可以防止敏感信息的泄漏，却无 法避免用户通过非敏感数据，综合其他外部知识间接推理出敏感信息。自由访问型数据 库隐私保护则是基于统计数据库安全保护技术提出的一些实现策略和模型。而自由访问 型数据库隐私保护主要应用在微数据发布。所谓微数据 4 1 可定义为一条描述个体信息的 数据记录，这些信息包括个体的标识信剧5 j ( 如姓名、身份证号等明确标识个体身份的 信息) 、敏感信息( 如薪水、疾病等需要的个人隐私信息) 、及一些非敏感信息( 如性 别、年龄、出生日期等) 。虽然一些模型被提出来，比如抽样方法，但是却无法应对通 过链接发布数据和外部数据造成隐私泄露的攻击，况且该种方法也极大地限制了数据的 有效性。由于微数据发布和基于访问控制的传统方法相比，明显区别是各个用户都有相 同的访问控制权限，即自由访问权限，该种类型的隐私保护还有较大的研究空间。一般 应对自由访问型数据库的隐私保护的做法是匿名化，即将发布的微数据中个人标识属性 删除，比如姓名、身份证号码等，但这种方法对于链接攻击不起作用，攻击者仍可以通 过获得外部数据源得到发布数据中的隐私数据。为解决这种无意识的信息公丌所造成的 信息泄露，s a m a r a t i 和s w e e n e y 在传统的访问控制之上提出来一种新的防止隐私泄漏的 模型，即k 一匿名模型【6 1 ，因其思想直观简单，能够满足安全防护的更高一级要求，并能 有效地保护个人隐私。 数据隐私泄露的情况有多种原因，有的是人们在发布过程中无意识的造成隐私泄 露，而有的是恶意攻击行为造成了隐私泄露 7 1 。个人的资料如姓名、生同、电话号码、 疾病、电子邮箱等被大量、全面地收集，这些数据在被计算机分析处理后，可以迅速地 进行传递和应用，其所带来的危害比传统社会严重得多。使得隐私信息保护变得更加重 要。例如，人寿保险需要收集各医院的疾病信息，来统计和了解某类人群的患病情况。 在这个过程中，数据挖掘技术很可能暴露人们的敏感数据( 如“病人所患疾病”) ，而这 些敏感数据是数据所有者( 医院、病人) 不希望被泄露的。另一方面，在各种数据发布应 用中，如果数据发布者不采取适当的数据保护措施，将可能造成敏感数据的泄漏，从而 给数据所有者带来危害。譬如企业发布的产品信息，或者上市公司发布的则一务年报， 如果不对发布的数据进行保护，就会给商业中的竞争者以可乘之机。随着数据挖掘技术 的讯速发展，利用各类数据挖掘工具，能更加容易的发现隐藏的、有价值的信息，对隐 私信息和敏感数据会造成严重的威胁。因此，保证数据中隐私信息的安全，成为亟待解 决的问题。 内蒙古科技人学硕十学位论文 目前防止私有信息泄漏的主要方法有如下几种：数据扰动、添加随机噪音、抽样、 发布聚合数据和匿名化的方法、数据交换和数据抑制等1 8 1 。数据扰动是对原有数据单元 不进行任何操作，通过限制条件来防止信息泄漏。添加噪声是在原来的敏感属性值中添 加其他的数据，改变原始数据以保护隐私信息，但使得数据一定程度上失真。抽样就是 只释放一部分数据用于公丌发布。发布聚合数据是将一些数据向量组成大小为k 的一 个组( g r o u p ) 。数据隐匿方法，针对数量少的单元可以简单的去除，但是在多次隐匿中， 可能造成多余的数据删除。数数据交换方法是随机将表中的数据从一个单元移到另一个 单元。一个可以替换数据隐匿的方法是为每个单元确定一个安全范围或者一个防护间 隔，发布的仅仅是该单元的保护间隔( 例如，一个数据取值的范围) 。数据抑制是针对 一部分数据记录可以简单的删除，但是在多次匿名信中，可能造成多余的数据删除。上 面提到的方法在理论上可以在一定程度上保证私有信息没有泄露出去。但是在实际应用 中往往出现发布的数据失真或者数据本身是不存在的假数据的情况，信息损失和数据扭 曲往往使发布数据失去意义，没有达到既保护隐私又保证数据有效性的双重目的。 1 2 研究意义 匿名化数据发可以有效的保护数据隐私，它的原理是通过发布泛化后的数据，在保 证数据发布的真实、有用情况下，能够实现隐私信息的匿名，从而保护隐私信息不被外 界揭露。为了能够达到数据匿名，对原始数据进行预处理是必须的，这样就决定了经过 匿名化处理的数据会有一部分信息损失1 9 1 。如何处理好隐私泄露与信息损失是匿名化过 程中的一个需要解决的主要问题。 目前，数据隐私保护技术的查询研究已经产生了大量的理论成果和系统原型，他们 的主要工作大都集中在对静态数据库的匿名保护处理。随着隐私技术的研究，人们在研 究静态数据库已经达到一定的水平，开始对动态的数据库进行研究。将来的趋势也是对 动态数据库的深入研究。现实世界中的大多数应用场景，人们所面临的数据都是动态 的，即随着时问的推移，数据集是在不断更新、增加和删除的。例如企业的员工数据， 医院的病例数据，政府的各项经济指标数据和人口统计数据等等，都是动态变化的。因 此，在不同时刻，常常需要对动念数据进行再次发布。 现在的数据库都是在动态的、时时的在变化。如何处理好多次发布造成的推断攻击 是研究的重点。解决这一问题的有效途径是分析多次发布能够造成的所有隐私泄露的可 能性，然后对这些造成隐私泄露的可能性进行分析和处理。在匿名过程中，不但要保证 匿名数据的k 一匿名条件，也要保证匿名数据的1 一多样性l lo 】的条件。与此i r d i 对，还要能 够保证多次发布的匿名数据表在攻击者的推理表中能够保证k 匿名性和l 多样性。 内蒙古科技大学硕十学位论文 由于数据隐私技术在多种实际应用中的重要性，所以该技术越束越受到人们的重 视。保护私有信息的隐私技术有着重要的理论价值和实际应用价值，因此一直是相关领 域专家们的研究重点。数据隐私技术的研究必将对未来隐私信息的保护提供更强有力的 支持。 1 3 国内外研究现状 近年来，随着互联网技术和信息的发展以及现实环境中数据共享的应用实际需求， 隐私保护技术的研究引起越来越多研究者的关注，涉及的研究范围也很广泛。根据信息 共享中隐私保护对象不同，将其分为两类：一类是以原始数据为隐私保护的对象，另一 类是以数据中的隐含的知识为隐私保护的对象，在本论文中主要关注第一种。这一类研 究中考虑以全部原始数据或其中部分敏感数据为隐私保护的对象，根据研究方向的不 同，主要可以分为基于数据干扰( d a t ap e r t u r b a t i o n ) 的研究，基于安全多方计算( s e c u r e m u l t i p a r t yc o m p u t a t i o n ，s m c ) 的研究和基于数据匿名化的研究。 微数据发布是将微数据集通过某些技术手段处理之后，发布到公共数据库中以方便 大众进行统计分析和通用查询，其相关模型和机制起源于统计数据库( s t a t i s t i c a l d a t a b a s e s d b ) 。该类型数据库对大量数据进行统计分析，以获得可用信息并且保证在 不破坏或尽可能保护原始数据统计特性的同时避免在数据使用过程中可能引发隐私破坏 行为。 近年来，针对信息发布应用中的实际需求，研究假设被共享的数据集中每条数据记 录均与某一个体相对应，且存在涉及个人隐私的敏感属性值( 如医疗记录数据中的疾病 诊断信息) ，同时数据集中存在一些称之为准标识符的非敏感属性的组合，通过准标识 符可以在数据集中确定与个体相对应的数据记录。这样，当直接共享原始数据集时，攻 击者如果已知数据集中某个体的准标识符值，就町能推知浚个体的敏感属性值，造成个 人隐私泄漏。该类研究的目的是防止攻击者通过准标识符将某一个体与其敏感属性值关 联起来，从而实现对共享数据集中敏感属性值的匿名保护。 1 9 9 7 年美国卡基梅隆大学的s a m a r a t i 和s w e e n e y 博士首先研究用于公共数据库或 数据发布的匿名隐私保护算法并在2 0 0 2 年命名为k 一匿名算法；文献j2 j 提出了k 一匿名 模型( k - a n o n y m i t y ) ，数据在发布共享前需要对其进行匿名化处理，使得对于每条数据记 录，都至少有k - 1 条其他数据记录与其具有完全相同的准标识符值。这样，即使攻击者 已知数据集中某个体的准标识符值，也不能将该个体与特定数据记录对应起来。k 一匿名 是数据发布隐私保护技术中一个非常重要的模型，它可以有效的防止通过对已发稚数据 与外部数据的链接造成的标识泄露问题，并要求在匿名化的过程中能够保护个体信息隐 私同时尽量提高数据的可用性。 卜o 内蒙古科技人学硕十学位论文 2 0 0 6 年，m a c h a n a v a j j h a l a 等人指出在某些情况下k 一匿名并不能保证隐私信息的安 全。文献【1 3 , 1 4 1 发现即使被共享的数据集满足k 一匿名模型，也并不能完全阻止某些个体的 敏感属性值泄漏。特别地，如果具有相同准标识符值的数据记录也具有相同的敏感属性 值，攻击者虽然不能将特定数据记录与某一个体相关联，但是也能够获知与该个体相关 的敏感属性值。针对这一缺陷，文献提出了对k 一匿名模型的改进，称之为l 一多样模型 ( d i v e r s i t y ) 。该模型不仅要求对于每条数据记录，在共享数据集中都存在多条与其具 有相同准标识符值的数据记录，而且还要求具有相同准标识符值的数据记录在敏感属性 值上具有一定的多样性。 对原始数据集做匿名化处理，必然会造成一些信息损失。在理论上，数据匿名过程 中的信息损失最小化己被证明是n p 难问题l l5 。在具体实现中，围绕如何降低数据匿名 化处理带来的信息损失，已有多种方法被提出，其中包括文酬1 6 l 提出的基于基因算法的 方法，文献【1 7 】提出的基于模拟腿的方法，文献【8 1 提出的自底向上的方法，文献f 1 9 】提出的 自顶向下的方法，文献【2 0 】提出的基于幂集空间搜索的方法，文献提出的基于划分的方 法，文科2 1 】提出的基于聚类的方法，文献田1 提出的针对多约束条件的方法，文献【冽提出 的针对数据效用的方法，文献1 2 4 提出的基于数据分解的方法，文献【2 5 1 提出的针对个性化 保护的方法等等。 随着对静态数据的研究的深入，尤其是在现实世界中很多的应用数据库都是动态 的，对动态数据库的研究也逐渐增多。文酬2 6 j 是第一个研究增量更新问题，在现实的世 界中，数据发布不是一次的，研究连续发布问题可以服务于各种信息研究目的。该文献 研究的重点内容是更新的过程是水平方向的也就是说对象( 发布表中的记录) 是固定的， 而属性则是随着时问的增长而不断有新的属性的增加。通过对q i 属性和敏感属性的连 接率限制来对连续发布的匿名表进行保护。但是该文献只是针对属性的增加做了研究， 在现实的世界中只有属性的增加是不够的，有时候要面对的是记录的增加和删除，所以 文献提到的方法具有一定的局限性。 2 0 0 6 年b y u n 和s o h n 等人在文献1 27 j 中对增量数据集进行了研究，文献在多次匿名 数据集中分析了各种推理渠道，并且讨论了怎样避免这些推理来保护隐私泄露。在文献 中介绍了一个数据质量度为信息损失度，用来计算在泛化过程中数据的扭曲量。在该文 献中虽然解决了记录的增加问题，可以记录的删除仍然没有提到很好的解决方法。 2 0 0 7 年x i a ox i a o k u i 和t a oy u f e i 在文蒯蹦i 针对动态数据集的重发布提出了自己 的解决方案为m 不变性。在上面提到的解决方案中只支持数据的增加，不支持数据的 删除。而该文献针对数据的增加和删除提出了有效的解决方法。在该文献中提到了签名 这个概念，就是说任一条记录在多次发布的版本中其q i 属性组必须有相同的敏感值。 因此在该文献中对这样条件的限制不利于数据的匿名发布。 多次 值而 是一个精确值，那么个人的隐私就有可能造成泄露，文献分析了造成推断表隐私泄露的 可能情况，针对这些情况提出了自己的解决方法。但是文献只能保证推断表的k 一匿名 性，在对敏感属性的1 一多样性没有做研究。 2 0 0 8 年b c m f u n g 和k ew a n g 等人在文献1 3 0 l 中提出了通信攻击这个概念来分析连 续发布造成的隐私泄露，在每次发布中每个发布表都有自己的时间戳，通过分析每个通 信对记录且每个通信对都有可能造成不同的推理攻击。在每个例子的分析当中总有一条 记录被攻击者通过自己的背景知识删除那么k 一匿名就遭到损害。文献提出了解决该问 题的一个概念b c f - a n o n y r n i t y 来测量攻击者的攻击力度。该方法可以满足熵卜多样性和 ( c ，1 ) 一多样性的要求。 研究内容和思路 本课题所做的工作是在现有的隐私保护技术研究的基础上，通过深入分析了多次匿 名发布中k 一匿名模型、卜多样性及相关隐私保护技术研究中存在的问题，得出能够满足 实际需求，增强数据发布的安全性并且提高发布数据的实用性的隐私保护方案。本课题 的主要研究内容如下： 首先对现有的几个匿名策略进行研究，分析各种匿名策略的优缺点，并主要分析当 前常用的几个匿名模型m o n d r i a n 算法，增量匿名算法和高效快速的匿名算法在数据隐 私方面的表现，特别是他们在面对链接攻击、背景知识攻击等常见攻击的表现。 其次在数据发行过程中要保留更多的数据信息。现有的隐私保护模型在匿名化处理 时都是采用抽象和概括的方法，首先需要预先定义一棵分类树，然后根据分类树采取自 上而下或者自下而上的方式进行抽象，这种方法信息损失较大，本论文采用一个新颖的 方法来保证数据发和时能够保留的更多的数据信息。 最后对原来的动念匿名技术指出其不足之处，从一个更全面的角度对数据发布的数 据进行匿名保护，采用了新的匿名模型。通过对攻击者利用多次发布表而得出的推断表 进行处理，保证推断表的k 匿名性和l 一多样性。提高了匿名的效果。使得在发布匿名数 据集之前就可以进行有效的隐私推理破坏预防，提升数据发布的隐私保护能力。针对多 维数据空间索引随着维数的增加，索引算法的运行时间会成几何指数增长，运行的时间 效率会非常低。在这罩通过把希尔伯特( h i l b e r t ) 空l 日j 填充曲线把多维数据转换成一维 数据其算法的运行时间大大降低，提高了索引效率。 息共 享变的越来越容易和方便。但是，随之产生的隐私泄漏现象也屡见不鲜，使得人们在提 供自己的信息同时，不得不考虑隐私安全问题。 数据发布是信息交换的一种重要手段，为数据交换和数据共享提供了便利，但在数 据发布的过程中的个人敏感信息泄漏也r 益严重。在发布如医疗记录、选民登记信息等 含有敏感信息的数据过程中造成的隐私泄露。如果不保护，直接把患者的疾病史、个人 的婚姻状况等敏感信息发布出去，会造成对于个人隐私的破坏。数据的隐私保护在数据 库安全研究中成为了重点和热点。隐私技术的保护就是在这样的环境下提出的。 现有的隐私保护技术大都应用在静态数据库中，结合目前的数据库现状大都是动态 的。现存的保护隐私技术就存在了不足，现存的算法在结合多次发布表的过程中只能保 证发布表和推断表的k 匿名，而在支持发布表和推断表l 一多样性的问题上还处于空白， 所以本课题在原算法模型基础之上新增了1 多样性，确保发布表和推断表既能保持k 匿 名也能保证1 多样性。最后通过实验进行性能测试。本课题的工作内容和重点就是围绕 这个思路展开和设计的。具体步骤如下： ( 1 ) 对原始数据表进行匿名泛化 ( 2 ) 对插入新数据集后的数据表泛化 ( 3 ) 分析两次发布表造成隐私泄露的多种可能性 ( 4 ) 设计支持发布表和推断表的k 匿名和1 多样性的匿名算法。 ( 5 ) 通过实验进行性能测试 论文的组织结构如下： 第一章介绍了数据隐私的发展，隐私保护技术等相关背景知识； 第二章介绍了数据隐私的相关概念 第三章详细讲述了增量数据集的隐私泄漏分析和理论基础；分析了多次发布的推断 造成的隐私泄漏情况，并提出解决办法。 第四章实验和性能测试； 最后对全文作了总结。 术有这本 不被非授 使得攻击 者获得的数据变得不可用( i f 密技术) 来实现。攻击者则以获得可用的隐秘数据为最终 目标。而隐私保护技术并不保障数据的隐密性，隐私数据完全可以对外公丌的，甚至任 何人都可以访问，其核心是要保护隐私数据与个人之间的对应关系，换句话说就是隐私 数据可以被任何人得到，到时却不能把数据对应到某个特定的人身上。从攻击着的角度 看，攻击的目标是隐私数据与个人之间的对应关系。 数据匿名化所处理的原始数据，如医疗数据、统计数据等，一般为数据表形式：表 中每一条记录( 或每行) 对应一个个人，包含多个属性值。这此属性可以分为三类： 1 显式标识符属性( e x p l i c i ti d e n t i f i e r ) ：或称为d 属性，表示能准一标识单一个 体的属性，如身份证号码、姓名等。通过这些属性值能直接确定具体的个体。 2 准标识属性( q u a s i i d e l l t i f i e r s ) ：联合起来能唯一标识一个人的多个属性，如邮 编、生日、性别等联合起来则可能是q l 属性。q i 属性又成为准标识符。不同的发布数 据表可以根据不同的情况划分不同的准标识符属性，一般情况下准标识符属性由专家选 择，而非用户随便选取。 3 敏感属性( s e n s i t i v ea r t r i b u t e ) ：包含隐私数据的属性，如疾病、薪水等。个人隐私 属性。在数据发布中，个人不希望其他用户了解的信息属性。发布数据时，为了保护个 人敏感信息不被泄露，标识符必须被删除，发布的数据记录只保留准标识符属性和敏感 属性。 4 等价组：在准标识符上的具有完全相同的记录组成等价组，即：等价组中所有 记录在准标识符上的属性值完全相同，其他属性可以不同。 例如，表2 1 为一原始医院数据表，每一条记录对应一个唯一的病人，其中 “姓 名” 为i d 属性，而 “邮编”，“性别”，“年龄” 可以为q i 属性， “疾病”) 为 敏感属性。 表2 1 病人疾病表 n a m e z i p - c o d e s e x a g e d i s e a s e l i n d y 3 0 7 5 9m a l e2 1 b i r d - f l u m a l i n 3 0 7 5 5 一m a l e4 8 h i v 内蒙古科技大学硕+ 学位论文 a n n a a l i c e 3 0 7 5 2 3 0 7 5 1 f e m a l e f e m a l e 2 6 3 l l n s o m n l a c a n c e r 医院在发布数据的时候需要把显式标识符属性的名字属性这- - n 去掉。只留下准标 识属性和敏感属性如下表所示。 表2 2 病人疾病发布表 2 2k 匿名 随着信息技术的发展k 一匿名的提出有了自己的应用环境，在投票、医疗、求职等 众多需要数据发布的应用场合中，即要保证个人标识信息不被泄露又要确保这些发布后 的数据不能推导出相关投票人、病人、求职人的隐私信息，因此对数据发布的隐私保护 研究具有非常重要的意义，k 一匿名是数据发布隐私保护中最主要的模型。当数据发布到 公共数据库后，数据持有者不能控制数据的使用方式和范围，通常使用去标识作为最基 本的数据发布手段，即移除所有涉及个体标识的数据项信息( 如身份证号码) ，但是只移 除诸如姓名、身份证号码等标识信息，这样的匿名数据集并不能真币达到隐私保护的要 求。 为了保护个人隐私，在数掘发布的时候，通常采用从数据表删除标识符的方式，但 是通过对对外部数据源获得的数据进行链接处理，获得可以推演敏感信息的渠道，从而 造成个人隐私的泄露，这种方式称为链接攻击。例如，1 9 9 7 年美国马萨诸塞州东部剑 桥市的选举列表中包括5 4 8 0 5 个投票信息，包括投票人的性别、出生日期和邮编编码。 调查发现，仅通过出生r 期就可以准确确定近1 2 的投票人的姓名和地址，联合出生同 期和性别可以准确确定出近2 9 ，结合出生日期和5 位数字的邮编就可以准确确定近 6 9 ，通过邮编和出生同期可以准确确定出近9 7 的投票人名字和住址( 近5 3 0 3 3 人) ，通过三者就可以近乎将任意一条投票记录唯一对应到一个投票人。 k 一匿名。令t a l ，a 2 ，a n ) 是一个表，q i 是与t 相关联的准标识符，当且仅当 在t q i 中出现的每一个有序的值至少要在te q i 中出现k 次的话，就说t 满足k 一匿 名。 k 一匿名性由s a m a r a t i 和s w e e n e y 提出，实际上已经成为了最为常见的一种匿名化 原则。其基本思想是：如果表t 中任何一个元组都和至少另外k 一1 个元组在准标识符上 内蒙古科技人学硕十学位论文 是不可区分的，那么即使攻击者知道t 中某个人的身份及其准标识符信息，因为t 中至 少有k 个元组可以与之连接( 他们构成一个等价类) ，攻击者就无法确定这个等价类早的 哪条元组与这个人对应。这样的性质使得满足k 一匿名具有良好的隐私保护能力。k 一匿 名性中的参数k 是用来指示隐私保护的程度的，一般来说，k 越大，隐私保护的程度就 越大，反之亦然。 准标识符( q i ) ：一个数据库表t ( a l ，a 2 ，a n ) ，准标识符就是可以和外部信息 想关联能够泄露个人标识的最小属性集q t = a 1 ，a 2 ，a i ) a 1 ，a 2 ，a n 。 下表2 3 中满足要2 匿名，从表中可知即使攻击者知道特定某个人的性别、年龄 和邮政编码分别是m a l e 、3 2 和3 0 7 5 3 ，由于表2 中有2 个元组都有可能和特定某个人 的准i d 信息相符合，攻击者无法确定该人到底患有哪种疾病。 表2 3 表2 1 的匿名表 在k 一匿名模型中，隐私泄露风险是由参数k 来控制的，在满足k 一匿名要求的关系 表中，至少有k l 条记录与它具有相同的准标识属性值，因此任意一条记录的重标识风 险都不会超过1 k 。这样通过选取不同的k 值，数据管理者就能够准确地控制数据发布 的隐私泄露风险度，因此k 一匿名机制是一种简单、有效的隐私保护机制。 1 9 9 8 年s w e e n e y 提出的k 一匿名模型主要解决了由于链接攻击而造成的隐私泄露。 在匿名化的过程中会造成信息损失，如何在满足k 一匿名约束的情况下减少信息损失是 近来研究的热点。2 0 0 2 年s w e e n e y 又进一步提出了k 一匿名保护模型，同年他又论述了 实现这一技术的泛化和隐匿方i ! 去1 3 l l 。2 0 0 5 年r j b a y a r d o 和r a g r a w a l t 提出了卜d 分块 思想1 3 2 j 。并且提出了检测信息损失的度量d m ( d i s c e m a b i l i t ym e t r i c ) 。2 0 0 5 年 k l e f e v r e 等人对全局k 一匿名进行了研刭3 3 】。2 0 0 6 年k l e f e v r e 提出了多维分块思想应 用在不重叠的多维区域。2 0 0 6 年k l e f e v r e 提出了匿名数据的有效性。a g g a r w a l 、 a m e y e r s o n 和r w i1 1i a n m s 在他们的文献中阐述了在计算最优匿名问题是个n p 问题 3 4 】。但是一些人提出了几个近似的方法，例如：d a t a f l y f 3 引、a n n e a l i n g i 蚓和m o n d f i a n m u l t i d i m e n s i o n a l 的k 一匿名算法。2 0 0 5 年b c m f u n g 等人提出了自上向下的泛化方法 1 3 7 1 。2 0 0 6 年k w a n g 等人提出了加强的k 一匿名方法1 3 8 1 。 目前针对k 匿名的研究主要是利用泛化和隐匿技术来实现匿名，一般将实现该算 法分成两大类；一类是全局泛化算法，另一类是局部泛化算法。由于全局泛化研究较 口 ： 一 内蒙占科技大学硕十学位论文 早，所以全局泛化算法比局部泛化算法要多一些，许多论文都有谈及，以下是几个比较 经典的算法，首先是全局泛化算法。a - a r g u s 算法：是h u n d p o l l 和w i l l e n b o r g 提出的一 个泛化和隐匿算法，它能够对确定变量的低维组合进行重新编码和局部隐匿，针对不安 全的属性组合被泛化或者通过单元隐匿来去除。虽然其中的一些数据值会丢失，但是发 布的数据包括了所有元组和初始数据的属性。在处理属性组合比较多的情况下，不能对 发布数据提供足够的保护。d a t a f l y 算法：是2 0 0 1 年s w e e n e y 提出的泛化和隐匿算法， 1 9 9 6 年提出的一个泛化和匿名算法，该算法在对数据集进行匿名泛化时，以属性为单 位对所有记录进行匿名处理。缺点是其中的某些记录已经满足k 匿名要求仍然继续参 与匿名处理，造成过量信息损失。d a t a f l y 算法简单直观，易于实现。m i n g e n 最小泛化 算法1 3 9 1 ：2 0 0 2 年s w e e n e y 提出的一个理论上泛化和隐匿算法，他给出了表的最小泛化 和最小失真的定义，对不满足k 匿名的表，进行泛化通过计算失真度，来确定最小泛 ，化满足k - 匿名模型的表。该算法能在最大限度的保证泛化后的基本表满足k 匿名模型 的要求，而且能够对单元的数据进行泛化，这样泛化的结果失真较小。但是该算法在表 的规模比较大的时候，对表的所有可能元组的泛化是无法实现的。i n c o g n i t o 算法1 4 0 】是 k l e f e w e 等人提出的算法，i n c o g n i t o 算法致力于用泛化和抑制元组技术找到有效的k - 匿名，存在的主要问题是没有发现发布的数据在满足k 匿名的特性后，也有泄漏敏感 信息的可能。 局部泛化算法主要有以下几种。l y e n g a r 等人提出g a ( g e n e t i ca l g o r i t h m ) 算法1 4 ，该 算法虽然能保证k 匿名的特性，但是由于k 匿名是n p 难题，所有该近似算法的实际 运行时间要花费几个小时甚至更多的时问，这样的时间效率是令人难以接受。2 0 0 4 年 m f u n g 等人提出自顶向下特化的局部算法，该算法利用信息熵的来计算信息损失，递 归修剪分类树直到满足k 匿名需求为止。该算法的对数据分类必须在属性中存在分类 标准才能进行划分，而数据集之中的数据类型常常是实际的数据，没有任何分类的标 准，因此必须人为先确定划分标准，这对数据匿名产生的结果也是有很大影响的，常常 会出现分类错误，导致发布数据无效。2 0 0 6 年l e f e v r e 提出多维空间划分来解决k 一匿 名的问题1 4 列，提出的算法属于局部泛化算法，但是该算法只能对连续属性划分，对不连 续属性处理能力较差。发现发布的数据属性多数是不连续的，如性别，居住地等，这样 就使得该算法的实际应用性降低。局部泛化算法与全域泛化算法的研究都是为了解决发 布数据的k 匿名问题。但是2 0 0 5 年a m a c h a n a v a j j h a l a 等人研究发现在满足k 匿名模 型的基础上发布的数据也有泄漏信息的可能，他们给出两种在满足k 匿名特性后对发 布的数据进行的攻击，这种基于背景知识的攻击方法对发命数据的隐私保护提出更高的 要求。 内蒙古科技大学硕十学位论文 2 3l 广多样性 卜多样性。在一个等价类g 中，g 中的q i 属性满足k 匿名属性的要求。关联到g 中的每个敏感属性的概率最多为1 1 。 m a c h a n a v a j j h a l a 等人提出1 多样性的匿名化原则是出于这样的考虑：虽然攻击者无 法确定某个人到底与等价类中的哪个元组对应，但如果这个等价类中某个敏感属性值出 现的频率过高，攻击者还是有很高的相信度将这个人和这个属性值联系起来。例如表1 中，有一个等价类中敏感属性值都是流感，这样只要确定某个人和这个等价类的中的某 个元组对应，就能确定此人得了流感。l 多样性则要求任何一个等价类中，出现频率最 高的那个敏感属性出现的频率不超过1 1 ，这样攻击者无法以很高的相信度将某个人和 某个敏感属性值联系起来。 2 0 0 6 年j o h a n n e sg e h r k e 和d a n i e l 鼬f e r 提出了对k 一匿名模型的改进，称之为卜多 样性模型( 卜d i v e r s i t y ) 。该模型不仅要求对于每条数据记录，在共享数据集中都存在 多条与其具有相同准标识符值的数据记录，而且还要求具有相同准标识符值的数据记录 在敏感属性值上具有一定的多样性。m a c h a n a v a j j h a l a 等人提出了针对k 一匿名模型的两 种攻击方法，一致性攻击和背景知识攻击。k 一匿名模型在这两种攻击下造成敏感属性泄 露。上述两种攻击m a c h a n a v a j j h a l a 给出了通过提高匿名组敏感属性多样性的方法( 1 - d i v e r s i t y ) 来降低隐私泄露。但是基于对于背景知识攻击的不确定性，如何设置卜 d i v e r s i t y 模型中的参数并没有好的办法。表2 1 中敏感属性就满足2 一多样性。 2 4h i l b e r t 空间填充曲线 空问数据是指与二维、三维或更高维空间的空间坐标及与空问范嘲相关的数据，空 间数据库的查询效率是空间数据库性能的重要标志，由于空问数据量的庞大以及空问对 象、空间查询的高度复杂性，因此必须引进一种提高空间数据库查找性能的技术1 4 3 1 。 空问填充曲线描述了一种n 维与1 维空间的映射方法，这种映射关系被应用到许多 的领域，最近还被应用到多维数据的索引中。研究表明，在众多的空| h j 填充曲线族中， 希尔伯特空间填充曲线具有最好数据聚集特性。 h i l b e r t 曲线源于经典的p e a n o 曲线族曲线族1 4 4 1 。p e a n o 曲线族是闭合间隔单元i = 1 ，0 】，到闭合矩形单元s = 【o ，1 】2 的连续映射，也是所有能够填满二维或更高维空间的 连续分形曲线的总称，故又称为空间填充曲线，它是由意大利数学家。p e a n o 于1 9 8 0 年 提出，德国数学家h i l b e r t 于1 9 8 1 年首先给出了构造这种空间坟充曲线的几何过程并 提出了所构造的空问填充曲线“处处连续，但处处不可导”的著名假设，直到1 9 9 4 年，才由s a g a n 将之证明。h i l b e r t 曲线已有广泛的应用，例如在图像存储和检索、空间 内蒙占科技人学硕十学位论文 数据库索引等领域得到了成功的应用。冈此研究h i l b e r t 曲线有重要的理论意义和应用 价值。 已有许多经典算法生成h i l b e r t 曲线：面向字节技术方法、几何方法、系统方法、 i f s ( 迭代函数系统) 方法等。这些算法大部分是按照h i l b e r t 本人初始的思想不断的四 分一个正方形区域，从始点到终点递归地计算画线的位置的过程，因此方向是这些算法 都要考虑的问题。由于这些算法大都是对曲线的每条线段逐渐细分做递归计算，每次运 算粒度小，当迭代次数较大时计算非常耗时。因此，有必要研究大粒度的迭代算法。 通过分析h i l b e r t 空间填充曲线的特征，提出了一种全新的思路以生成这种曲线 根据二分技术，算法设计是正方形区域逐渐二分的过程，而算法实现是其反过程。 二 分技术是一种普适的快速算法设计技术，已成功应用到和递推计算紧密相关的应用领 域。 2 5 隐私保护模型 数据发布中的匿名保护问题针对这样一种应用背景：被共享的数据集中每条数据记 录均与某一个体相对应，且存在涉及个人隐私的敏感属性值( 如医疗记录数据中的疾病 诊断信息) 。研究的目的是实现对共享数据集中敏感属性值的匿名保护，即防止攻击者 将某一特定的个体与其敏感信息关联起来。 如果仅仅将原始数据中能够唯一标识个体的属性( 即标识符，如身份证号码、姓名 等) 去除，并不能有效地实现匿名保护。文献1 4 5 峙旨出，由于在数据集中可能存在一些称 之为准标识符( q u a s i i d e n t i f i e r ) 的非敏感属性的组合，通过准标识符可以在数据集中确 定与个体相对应的数据记录。这样，当直接共享原始数据集时，攻击者如果已知数据集 中某个体的准标识符值，就可能推知陔个体的敏感属性值，造成个人隐私泄漏。这种情 况被称为链接攻击( l i n k i n ga t t a c k ) 。例如，属性组( 出生r 期、性别、居住地邮编) 就叮 构成一个准标识符。研究表明约8 7 的美国居民通过该准标识符能够唯一确剧4 6 j 。 通过准标识符与其他渠道获得的信息进行连接，可形成链接攻击。攻击者据此可推 理出与个体相关的敏感属性值，从而导致隐私泄漏。攻击者可以从医疗机构得到人们的 治疗信息表，其中包含姓名，性别