数据发布中匿名技术研究.doc

分类号： 密级： U D C ： 编号： 工学硕士学位论文数据发布中匿名技术研究硕士研究生： 商 宗 民 指导教师： 刘 杰 教授学科、专业： 数据库与知识工程论文主审人： 张 沛 键 教授哈尔滨工程大学 2012年1月分类号： 密级： U D C ： 编号： 工学硕士学位论文数据发布中匿名技术研究硕士研究生：商 宗 民指导教师：刘 杰 教 授学位级别：工 学 硕 士学科、专业：计算机应用技术所在单位：计算机科学与技术学院论文提交日期：2013年1月论文答辩日期：2013年3月学位授予单位：哈尔滨工程大学Classified Index: U.D.C:A Dissertation for the Degree of M. Eng Anonymous technology research In Data PublishingCandidate:Shang Zong Min Supervisor:Prof. Liu JieAcademic Degree Applied for:Master of EngineeringSpecialty:Computer Applied TechnologyDate of Submission:Jan, 2013Date of Oral Examination:Mar, 2013University:Harbin Engineering University 哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 作者（签字）： 日期： 年 月 日哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文，可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。本论文（在授予学位后即可 在授予学位12个月后 解密后）由哈尔滨工程大学送交有关部门进行保存、汇编等。作者（签字）： 导师（签字）：日期： 年 月 日 年 月 日 摘要数据挖掘和数据发布是当前数据库应用的两个重要领域。一方面，数据挖掘与知识发现在各式各样的数据应用领域中都扮演着非常重要的角色。数据挖掘的目的在于从大量的数据中抽取出潜在的、有价值的知识、模型、规则等；另一方面，数据发布是将数据库中的数据直接地展现给用户，促进数据的交流和共享，而在数据的各种应用中，直接发布数据表中的数据会暴露数据所有者的隐私信息，给个人造成不必要的精神伤害或是财产的损失，因此我们在数据发布前有必要对相关数据进行匿名化处理。匿名化方法是一种安全有效的数据隐私保护方法，它是数据发布隐私保护方法里基于限制发布的一种，它能有效的平衡数据的有效性和隐私保护之间的关系，是近年来数据发布隐私保护的一个研究热点。匿名化的基本思想是把原始数据表进行某种变换，使攻击者不能从变换后的数据表中轻易分析出某个元组的敏感属性值，从而不能识别敏感信息所属的具体个体，达到隐藏个体隐私信息的目的。本文首先分析了数据发布隐私保护中现有的主要技术和匿名化方法，并归纳、总结了现有匿名模型的优缺点。为了解决目前存在的多维敏感属性信息泄露问题我们结合了现有多敏感属性隐私泄露保护的多维桶分组技术，提出了一种敏感性分级的基于有损链接的(g，k)-匿名模型，并给出了此模型的形式化描述和相应的实现算法。本文的具体工作有：（1） 现有的隐私保护模型在匿名处理时主要是采用泛化和隐匿的技术，该技术首先需要为每一维准标识符属性预定义一颗泛化树，在准标识符维数较多的情况下信息损失很大，容易出现过度泛化的情况，本文基于有损链接的思想，在Anatomy分解发布的基础上引入了组内属性值交换的概念，通过把组内每一维属性值随机交换，可以有效抵制现有模型因为泛化和隐匿造成的较大信息损失，同时克服了所有模型都存在的背景知识攻击和存在性攻击问题。（2） 针对多维敏感属性隐私数据发布的多维桶分组技术存在的近似猜测攻击问题，本文在多维桶分组技术基础上提出了一种基于多维桶技术并综合考虑多维敏感属性值敏感级别分布的(g，k)-匿名模型。该模型因为控制了分组中同一敏感度属性值的分布数量，从而能有效抵制近似猜测攻击。（3） 通过大量数据集的实验，对实验结果的分析比较表明本文所提方法的正确性和有效性，测试了数据的发布质量和执行效率，并通过与最大多维桶分组方法的比较，表明基于有损链接的组内属性值交换(g，k)-算法在信息损失准许范围内能更好的保护多维敏感属性数据的安全。关键词：隐私保护，敏感度分级，多维桶，组内属性值交换，Anatomy发布VAbstractData mining and data publishing is the two important fields in database application. One side, Data mining and knowledge discovery plays a very important role in every kind of database application field, Data mining aimed is found a large number of potential valuable knowledge, model, rules from large amount of data; on the other hand, Date publishing is directly displayed the data to the user, To facilitate date exchange and share, But in a variety of applications of the date, Direct release the data will expose privacy information of data owner in the data table, Cause unnecessary personal mental injury or property loss, Therefore, It is necessary anonymous processing for the relevant data before we publish the date.Anonymous method is a safe and effective data privacy protection method, It is one of the data publishing privacy protection method based on limited release. It can effectively balance the relationship between the validity of data and privacy protection, Data publishing privacy protection is a research hotspot in recent years. The basic idea of anonymous is take a kind of transformation for the original data table, that the attacker cannot easy analysis the sensitive attribute values from the transformed data table, and thus can not identify the sensitive information of specific individuals, Achieve the goal of hiding the individual privacy information.This paper firstly analyzes the existing main technology and anonymous method of data publishing privacy protection, And Induction、summarize advantages and disadvantages of the existing anonymous model, In order to solve the information leakage problem of the multiple sensitive attributes ,we combine the existing multiple sensitive attributes privacy protected multidimensional bucket packet technology, Put a kind of sensitivity attributes classification based on Loss link ( g, K ) anonymous model, and gives the formal description of the model and corresponding algorithm.In this paper, the specific work:( 1) the existing privacy protecting model in anonymous processing is used mainly for generalization and occult techniques, the technique first required predefined a generalization tree for each one dimensional quasi identifier attribute, On the cases of large quasi identifier dimension will Cause a great deal of information loss, prone to excessive generalization to the case, In this paper, based on the loss link ideas, introduced the concept of group internal transfer based on Anatomy decomposition, By each dimension attribute value random permutation within the group, can effectively resist the existing model cause great loss of information through generalization and occult, At the same time, overcome the problems of all the models having the background knowledge attack and existence attack.(2) for the multidimensional bucket packet technology of multiple sensitive attributes data privacy published existing approximate guessing attack problems, In this paper based on multidimensional bucket packet technology and considering the multiple sensitive attributes value sensitive level distribution ( g, K ) anonymous model, because this model control the number of the same sensitivity attribute values distribution in a group, which can effectively resist the approximate guessing attack.(3) through a large data set of experiments, the analysis of experimental results shows that the method proposed in this paper is correct and effective, Test the data of the issues quality and efficiency, and comparison with maximum multidimensional bucket packet method, Show based on Loss link group ( g, K ) built-in exchange algorithm can be better protected multidimensional sensitive attribute data security in information loss allowed range.Key words: privacy protection, sensitivity classification, multidimensional barrels, within the group of replacement, Anatomy Publishing. 目录摘要IAbstractIII第一章 绪论11.1 论文研究的背景和意义11.1.1 隐私保护问题的提出11.1.2 研究数据发布隐私保护意义31.2 国内外研究现状41.3 论文研究的主要内容61.4 论文的组织结构71.5 本章小结8第二章 隐私保护匿名相关技术和模型92.1 数据匿名化概述92.2 数据发布中的匿名方法112.3 隐私保护模型132.4 匿名数据性能评价152.5 本章小结17第三章 多维敏感属性的隐私保护193.1问题的提出193.2 相关概念213.3 (g，k)-模型的建立223.3.1 基本思想223.3.2 敏感属性分类233.3.3 g差异性和构建d维桶253.3.4 (g，k)-匿名模型263.4 (g，k)-匿名模型实现方法283.5 本章小结28第四章 基于有损链接的(g，k)-匿名算法314.1 组内属性值交换及与Anatomy区别314.2算法描述364.3算法实例384.4算法分析404.5 本章小结41第五章 实验和结果分析435.1 测试数据和实验环境435.2 评价指标445.3 实验结果分析455.4 本章小结50结论511 总结512 展望52参考文献53攻读硕士学位期间发表的论文和取得的科研成果57致谢59第一章 绪论第一章 绪论1.1 论文研究的背景和意义1.1.1 隐私保护问题的提出隐私是我们人类社会文明进步的产物，是随着经济社会发展而不断更新完善的概念。在原始社会隐私可能仅仅指不在公共场合暴露自己，是建立在人们原始感官认识之上，随着人类社会文明的发展和进步，我们对自己的隐私保护观念越来越强烈，现代隐私概念包含的内容非常丰富多样，如个人的私密信息不得被窥探和转发，个人的肖像不能随便使用等。下面首先让我们来了解一下有关名词：什么是隐私？隐私1是一种仅仅涉及到有关个人的与大众、群体利益无关的，他人不便干涉的或是当事人不愿他人干涉的相关个人私事；他人不便知道或者当事人不愿他人知道的有关个人信息；以及他人不便侵入的或当事人不愿他人侵入的个人相关领域。 那什么是隐私权呢?隐私权是指从法律上授予的单个自然人所享有的仅包含其个人的、且要与公共利益无关的,对个人活动、私有信息以及专有领域进行支配的具体人格权2。隐私权是人类社会民主制度发展的高度文明产物，是以法律的形式确立的个人隐私信息不受侵犯的权利。随着计算机技术的发展和互联网应用的推广，个人的很多信息都能被人肉搜索出来，这里的隐私权就可以进一步扩展成为个人对自己私有相关信息的控制和处理权3，从法律上保护个人的隐私信息不被他人肆意广泛传播、搜集、利用和转发。 隐私信息4指的是个人不愿对外公开或是被他人知晓的私人信息。 隐私侵害：从法律上讲隐私侵害可以分为以下几种情况： 隐私信息收集者在不具备收集个人信息的义务和资格的情况下而越权收集；处理时违反规定，超出了相关使用权限；处理个人隐私信息时没有提供相应的保护，导致了不良后果；违法使用个人隐私信息。我们本文讨论的主要是征对第三种情况，也就是在处理个体隐私信息的时候需要提供相应的保护措施，防止个人隐私信息的泄露，造成不良后果。 随着人们对自己个人隐私信息的关注和重视，各个国家都建立了相应的法律法规，以保护个人隐私信息不受侵犯。如早在网络未普及的1970年，德国联邦政府就设立了联邦数据保护法来全面保护德国公民个人信息和隐私，英国在1984建立了数据保护法，1990年健康档案查阅法，1991年人口普查保密法，希腊有私人信息保护法，葡萄牙有个人信息保护法，新西兰1993年隐私法修正案，拉脱维亚有拉脱维亚私人数据保护法5，而我国在立法这一块相对比欧美落后许多，香港1996年颁布了个人资料私隐条例，内地于2002年由卫生部起草了医疗机构病例管理规定行业规范，2003年居民身份证法出台，个人信息保护法立法准备工作已经开始，随着互联网络的普及和应用，针对网络用户的信息保护问题也在相关部门的努力下正在积极推进。随着计算机网络技术日新月异的发展和数据库应用技术的普及，大量的与个人相关的私人信息被挖掘出来，如：商场客户购物数据、医院患者医疗数据、新生儿人口出生统计数据等。这些数据中包含了大量的可供参考的有用信息，可给相关机构和人员做研究之用，如商场客户购物数据可用于分析物品消费人群、畅销物品等，以便采购部门进货以及销售部门做促销活动，患者医疗数据可以给病理专家分析疾病遗传和变异情况等，但是因为这些原始数据中同时包含了很多个人相关信息，如果直接发布这些数据信息势必会引起个人隐私信息的泄漏，造成社会恐慌，数据所有者就不愿意把这些有用数据拿出来跟人分享，从而阻碍这些有用信息的充分利用。社会上，由隐私问题所引发的纠纷越来越多，影响也越来越大。隐私是一种个人享有的权利，人们要求保护属于自己的隐私信息，避免因为个人信息的泄漏而给自己带来精神或者物质上的损害，然而包含有个人隐私的统计信息同时也是一种宝贵的社会财富，社会研究和科学技术的发展需要利用这些资源，发现并解决实际问题，创造社会价值。隐私信息的利用和保护就是一把双刃剑，过度的注重隐私保护势必降低数据的利用率，过分强调数据的有用性又容易侵犯个人的隐私权，所以要恰当的处理好隐私信息的保护和利用的关系。随着数据库应用技术的普及和计算机网络技术的发展，各个大的组织单位都有属于自己的海量有用信息，这些有用信息可以用来分析研究，人们希望通过这些海量数据来分析发现数据背后的规律，指导我们分析预测。因而越来越多的公司和单位都主动把自己拥有的数据送给专门机构做分析预测，以期望发现数据间潜在的关联规则，为未来领导决策提供参考。高度的数据收集和共享机制可以保证这些数据被有效利用和开发，数据挖掘就是要从这些海量数据中寻找潜在的规律，发现新的知识。但是之前的数据挖掘技术在给我们带来新知识的同时，也给我们个人隐私信息的保护带来了挑战，因为通过挖掘出来的知识有时能够从非敏感数据推导出敏感数据，甚至数据挖掘出来的知识自身就是敏感数据，这就要求各有关数据收集机构不但要保护好原始数据，而且对数据挖掘出来的新知识也要进行隐私保护，是在隐私保护策略下的知识发现。例如，新生儿监护中心时常需要收集各个医院的新生儿出生信息，以用于人口正态分布和性别比例监测，在这个过程中，传统的数据挖掘方式不可避免的就暴露了新生儿父母的工作单位、家庭住址等敏感信息，而这些敏感数据正是一些不法推销婴幼儿产品的销售商所希望得到的，这就给新生儿父母日常生活带来了麻烦。2010年7月深圳市某医院就因为出卖了两万条新生儿出生信息在社会上造成了很大不良影响。最近几年来，涉及到个人信息泄露的案例非常多，而且形式样式也越来越丰富，下面就简单列举几起关于个人信息泄露的案例： （1）2009年3月15号晚上8：00，央视3.15晚会主题为用户信息泄露幕后，对山东移动逆势发送垃圾信息的行为进行了曝光，同时也对各种非法获取个人信息的行为进行了曝光。 （2）仅2010年底，360就违规收集并致141万份用户隐私被泄露。其中包含9万个淘宝用户的订单和联系方式，2474家公司内网记录，以及网友看苍井空AV电影的记录。 （3）卖个人信息的网站，如2009年被中央电视台曝光的海量信息科技网，公开兜售个人信息。当前数据库应用的两大方向是数据发布和数据挖掘，本文重点研究的数据发布是数据库应用的其中一个分支。近年来，数据库领域兴起的关于数据发布中隐私保护技术研究很多，其目标就是致力于要找寻到一种效果较佳的隐私保护策略和方法6，对某个需要待发布的数据表进行事先预处理，在信息源头上解决因为数据表的发布和共享所导致的隐私泄露问题。具体而言，数据发布中的隐私保护研究需要考虑两大主要方面问题7：（1） 如何保证在分析应用这些个人数据时尽量少的暴露个人信息；（2） 尽量减少因为在实施个人隐私信息保护的过程中而导致其他的非敏感信息的丢失问题，即需要保证原始数据发布的质量。 1.1.2 研究数据发布隐私保护意义数据发布隐私保护与传统的基于加密和安全控制技术有着本质上的差别，加密技术是对原始数据进行加密而让没有数据密钥的非法用户即使截获了数据也不能使用，以此保证数据的安全，而传统的安全控制技术则主要是通过身份论证的方法来防止未经授权的第三方对数据库的非法访问。而我们这里需要讨论的数据发布隐私保护技术是一种与以上处理方式完全不同的信息安全技术，隐私保护技术对外公开发布所保护的数据，每个人都有访问数据的权利，隐私保护技术的基本思想是不让受保护数据表中的数据记录与具体个体相关联，换句话说就是被保护数据可以被任何人访问，但是潜在攻击者不能把被保护数据中的任何一条记录关联到具体的某一个体上，在处理的过程中，主要是需要隐藏好被发布数据记录与个体之间的关联关系。而从攻击者的角度看，则是为了获取发布数据表中的记录与个体之间的对应关系。 数据发布隐私保护技术研究无论是对行业交流、个人以及社会信息技术的发展都有着重要作用，首先，对各个行业来说都需要积累已有数据，并通过已有数据发掘新的知识，为日后制定正确的决策安排，没有对已有数据分析研究，就没法做出正确的趋势分析和决策，这就需要各行业之间的数据共享和交流，实现已有数据的价值；其次，对个人而言，我们人人都有隐私，谁都不想把自己的隐私信息暴露给公众，以免给自己带来精神或物质上的损失；最后，隐私保护问题已严重影响了数据挖掘和数据分析，阻碍了相关技术的发展，由此可见，研究数据发布隐私保护技术是很有必要的，同时也是有着实际应用前景的。 数据发布的隐私保护问题研究目的，一方面是为了减少个体私有信息的泄露，消除数据所有者分享自己数据的担忧，促进信息共享和交流以及新知识的研究；另一方面则是要尽量保持原有数据的真实性，保证匿名发布数据的可用性。1.2 国内外研究现状随着数据库应用的推广数据发布隐私保护问题的提出才有其现实要求，隐私保护的研究方向重点：一是寻找数据发布策略，二是有关隐私保护算法，其主要研究成果如表（1）所示：表1 数据发布隐私保护研究方向基于隐私保护的数据发布策略k-anonymity、l-diversity、m-Invariance、t-Closeness、( ,m)、（，k）匿名保护算法Anonymized PublicationAnonymization with High Utility对数据发布隐私保护问题研究较早由国外兴起，有很多专家学者已在数据发布领域进行过相关研究，在国际主要会议(SIGMOD, PODS,VLDB,ICDE等)和期刊上每年都有一百多篇优秀论文发表。数据发布隐私保护问题的研究最早起源于统计泄密控制（Statistical Disclosure Control，简称SDC）领域，SDC研究的主要内容就是在保证统计信息真实可信的情况下如何尽量不泄露或最大限度地减少泄露个体的隐私信息，即是要尽量保持数据保密性和数据可用性两者之间的平衡。统计泄密控制采取的主要方法有数据交换、子抽样、添加噪声、合成伪数据、随机化等技术，其中心思想是在破坏原有数据的同时保持原有数据的基本统计特征。随着人们对个人隐私信息关注度的提高以及计算机网络技术的发展，隐私保护问题已由传统的社会领域发展成为计算机科学领域的一个研究课题，经过十多年的努力，数据发布中的隐私保护已发展成为两大分支：隐私保护的数据挖掘（Privacy-Preserving Date Ming,简称PPDM）8和隐私保护的数据发布（Privacy-Preserving Date Publishing,简称PPDP）9。本文讨论的是PPDP中的基于多维敏感属性数据表的隐私保护匿名化问题。 PPDP是由Banjamin Fung等人9于2007年提出来的，其研究的目标是要找寻到一个通用的、能保护个体隐私信息的数据发布匿名策略和算法。数据发布隐私保护中较常使用的方法有数据加密、数据干扰、和基于限制发布等。每个方法都有其各自不同的优缺点和相应的应用范围，具体的比较分析见下表2： 表2 隐私保护方法比较隐私保护技术主要优点主要缺点典型应用数据加密数据真实无缺损，隐私保护度强。计算复杂，通信开销大。不同数据需设计不同算法分布式下的关联规则挖掘、匿名数据发布等数据干扰计算简单，计算开销小数据失真，严重依赖于数据，找到合适的噪音数据比较困难。各种数据挖掘操作，如关联规则挖掘，关联规则隐藏等限制发布算法通用性好，数据有效性高存在一定的信息损失，有一定的信息泄露发布匿名数据，可进行各类数据挖掘操作从表2很容易看出，每类隐私保护技术都有其各自不同的适用范围，这主要是每类隐私保护方法的性能在不同应用下表现各异。可以看出：当需要对有规律数据实施隐私保护时，可以考虑采用数据干扰的隐私保护技术；当需要对发布数据进行较严格的隐私保护时，则必须采用数据加密的隐私保护技术，但数据加密需要很大的计算开销，且针对不同数据需设计不同的算法；而限制发布技术与以上方法相比性能比较折中：在一定的信息损失和计算开销下能较好地完成对数据表的隐私保护。我们本文后面所讨论的基于多维敏感属性数据表的多维桶分组并综合考虑敏感属性敏感度分级的隐私保护方法就是基于限制发布的一种。美国卡梅隆大学的Samarati博士和Sweeney博士于1998年就开始着手研究数据发布中的匿名隐私保护算法，并于2002年在PODS(ACM on Principles of Database Systems)上将其命名为K-匿名算法10，在数据匿名发布中K-匿名算法具有难以撼动的始祖地位，因为其他所有匿名算法几乎都是在K-匿名算法基础上演化而来的。K-匿名模型要求分组中的所有记录都具有的基本特性是：在发布数据分组中最少有K条记录需在准标识符属性上取值一致，这样攻击者即使通过外部表的链接能够判断数据记录所有者所在的分组，但是最多也只能以小于1/k的准确率确定数据所有者所对应的具体数据记录，从而很好的起到了对个体隐私保护的目的，这里的参数k是由数据发布者根据实际要求预先设定的。有关数据发布已有匿名策略在第二章再具体一一介绍。1.3 论文研究的主要内容论文首先分析了数据发布中的隐私保护现有的主要匿名方法和技术，并归纳、总结了现有匿名模型的优缺点，同时为了抵制目前存在的基于多敏感属性数据表信息泄露问题，我们继承了已有多维敏感属性隐私泄露保护的多维桶分组技术，提出了一种多维敏感属性分级的基于有损链接的组内属性值交换(g，k)-匿名模型，并给出了此模型的形式化描述和相应的实现算法，实现一种更贴近实际需求的、增强发布数据隐私保护度的匿名方案。本文的研究工作属于PPDP分支中的一部分，采取的匿名方法是基于数据发布隐私保护中的限制发布技术。 本文的主要工作如下：1） 现有与多维敏感属性相关的隐私保护模型较少，而仅有的多维桶分组技术还存在的近似猜测攻击问题，本文在继承多维桶分组技术基础上，同时考虑对多维敏感属性值敏感度进行分级的(g，k)-匿名模型。该模型由于控制了分组中同一敏感级别属性值的分布数量，从而能够有效抵制近似猜测攻击。2） 现有的隐私保护模型在匿名处理时主要是采用泛化和隐匿的技术，该技术首先需要为每一维准标识符属性预定义一颗泛化树，在准标识符维数较多的情况下信息损失会很大，容易出现过度泛化的情况，本文基于有损链接的思想，在Anatomy分解发布的基础上引入了组内属性值交换的概念，通过把组内每一维属性值随机交换，可以有效抵制现有模型因为泛化和隐匿造成的较大信息损失，同时克服了所有模型都存在的背景知识攻击和存在性攻击问题。3） 通过公认数据集进行实验，对实验结果的分析比较表明本文所提算法的正确性和有效性，测试了数据匿名后的发布质量和执行效率，并通过与最大多维桶分组方法的比较，表明基于有损链接的组内属性值交换（g，k）-算法在信息损失准许范围内能更好的实现对多维敏感属性数据的保护。1.4 论文的组织结构本文按照如下的方式进行组织：论文共有五章如图所示第一章绪论第二章 隐私保护匿名相关技术第三章 多维敏感属性的隐私保护第四章 基于有损链接的（g，k）-匿名算法第五章 实验和结果分析 结论第一章为绪论，主要介绍了本课题研究的背景，以及做本课题研究的目的和意义，在本章全面介绍了目前数据发布隐私保护的国内外发展研究现状，并重点介绍了本论文的主要内容和所做工作。第二章 隐私保护匿名相关技术，讨论了匿名化的相关概念，并对各个隐私保护技术做了分析比较；介绍已有数据发布中的隐私保护主要模型，并对各个模型的优缺点进行了分析；介绍了本文需要吸收引用的基于有损链接的Anatomy分解发布技术，以及多维桶分组技术；最后简单介绍了匿名数据性能评价指标。第三章 基于现有模型不能很好地实现对多维敏感属性数据表的隐私保护，借鉴多维桶分组技术的思想，提出一种多维桶分组技术并同时考虑对多维敏感属性敏感度进行分级的(g，k)-匿名模型，有效的克服了现有k-匿名模型、L-多样性模型、多维桶分组的不足，更好的实现了基于多维敏感属性数据表的隐私保护，最后对模型的实现方法进行了讨论。 第四章 为了克服泛化和隐匿带来的数据损失过大问题，针对多维敏感属性的隐私保护模型(g，k)，提出相应的算法实现，结合Anatomy有损链接的思想，提出组内属性值交换的匿名化方法，并给出实例详细说明算法的实现过程，最后对算法的正确性和复杂性进行了分析。第五章 采用公认数据集来验证算法的有效性和正确性，并跟多维桶分组技术在相关的性能指标上做了比较。分析最终结果表明基于有损链接的组内属性值交换(g，k)-匿名算法在执行时间、信息损失等都容许范围内能提高多维敏感属性数据表的隐私保护度。结论 全文的总结和展望。对本文研究内容进行了总结，并对未来研究发展的方向进行展望，提出下一步我们需要着力解决的一些主要问题。1.5 本章小结 本章主要介绍了数据发布隐私保护问题研究的背景及目的意义，论述了数据发布隐私保护技术在国内外的发展现状和进展情况，最后对本课题主要的研究内容和本论文行文安排作了简单的介绍。 59第二章 隐私保护匿名相关技术和模型第二章 隐私保护匿名相关技术和模型隐私保护技术从技术上大致分为两种，一种是自由访问型(Access-Free Type)隐私保护，另一种是受限访问型隐私保护(Access-Restricted Type)。受限访问型隐私保护是指访问者需要取得数据库管理者的授权才可以对有关数据进行访问11，传统的数据隐私保护方法主要是基于受限访问型隐私保护，例如口令设置、身份认证等。随着数据发布隐私保护技术的进一步发展，自由访问型隐私保护12越来越受到学者的关注。即访问数据库对所有人都是公开的，任何人都可以自由访问，但是却不能将数据库中的任一记录对应到具体的某一个体上。为了对数据表中的数据进行隐私保护，自由访问型隐私保护通常采取的办法是对原始数据实施“数据匿名化”操作。所谓“数据匿名化”就是数据发布者在数据发布前需要对原始数据实施一定的预处理，使攻击者无法从经过匿名变换后的数据表中唯一推导出某个具体个体对应的敏感信息来，从而实现对个体隐私信息的隐藏。匿名化的处理过程可以用图简单表示为： 张三李四王五收集原始数据匿名化预处理对外发布匿名化预处理后的数据表 图2.1数据匿名化处理过程2.1 数据匿名化概述数据匿名化所需处理的原始数据一般都是以表的形式出现，如人口出生信息表、招生报名表等，表中的每一行（或每条记录）都代表一个具体个体信息，每个个体信息又都包含了多个描述个体相关信息的属性值，例如设图2.1中有记录（张三，硕士，M，18310，27，肺炎）就表示了张三的姓名、学历、性别、邮编、年龄、疾病等属性信息，将数据表中的这些属性信息按照其功能效果大致可分为三类13：（1）显示标识符EI（Explicit Identifier）：它是能够唯一准确描述单一个体记录的属性，如姓名、身份证号等，通常是由单一属性构成，在数据发布前往往都要将这些显示标示符属性直接删除或加密。(2) 准标识符QI(Quasi Identifier)：准标识符属性是由多个属性的联合体构成，在数据表中如果存在多个属性能够通过外部表链接来唯一标识单一个体，则称这多个属性的联合体为准标识符。准标识符的定义随外部表提供的信息而变化，也就是说准标识符具有不确定性。 （3）敏感属性SA（Sensitive Attribute）：指含有个体隐私信息的且需要重点保护的属性，如健康状况、薪资收入、宗教信仰等。敏感属性可以是单维属性也可以是多维属性，拿原始数据表2.1来说，显示标识符为（姓名），准标识符为（性别，年龄，邮编），敏感属性为(疾病)。 表2.1 原始数据表姓名性别年龄邮编疾病MaryF21129002肺炎AliceF26183104艾滋BobM25259803感冒JohnF20190030发烧DavidM31409248胃溃疡数据发布隐私保护技术就是要将如表2.1所示原始数据表进行某种匿名变换后，转发给相关专业机构或者是供大众直接查询，发布表是完全对外公开的，对不同的访问者包括潜在的攻击者都提供了相同的访问权限，因此可以把其归属于自由访问型隐私保护。攻击分析者之所以能够利用背景知识并联合外部表的有关属性推导出攻击对象的敏感属性值，是因为数据表中的这三类属性之间存在着某种内在的关联关系，具体而言这三类属性之间存在的关系有14：1.发布表中准标识符属性与外部数据表中准标识符属性的对应关系，通过两表的公共属性对应推导发布表的身份信息ID。2.发布表中准标识符属性与敏感属性值的对应关系，由多个准标识符可以推导出对应的敏感属性。3.准标识符属性中各个属性之间的关联，由其中的一个或几个准标识符推测出其它准标识符的过程。 图2.3显示了个人身份信息ID、准标识符属性以及敏感属性之间存在的上述三种关系，只要破坏或者是弱化这三类属性之间的任何一种对应关系都可以取到隐私保护的作用。通常的泛化技术就是破坏这里的第二、第三类关系，而Anatomy分解发布则是弱化了第二种关系，本文第四章提出的组内属性值交换则是要弱化第二种关系以及破坏第三种关系，这也就是为什么我们后面要讨论的组内属性值交换能够提供比Anatomy分解发布提供更强的隐私保护原因所在。 图2.2 身份信息、准标识符、敏感属性关系姓名 IDMaryAliceBob年龄性别34M22F57MSensitiveCancerHIVFlu2.2 数据发布中的匿名方法 常用于数据发布的预处理匿名方法有很多，大致总结起来有：去标识、数据泛化、数据抑制、子抽样、数据交换、插入噪音、微集合、分解等，在诸多预处理匿名方法中泛化和抑制技术用的最为频繁。去标识：就是把原始数据表中唯一准确标识记录的显示标识符去除的过程，一般仅用于作为匿名数据预处理的第一个环节或是非常简单数据的发布情况。由于去标识过于简单，容易失效。数据泛化：是对数据表中的原始属性值依照某种规则进行变换，使得变换后的数据属性值与真实数据相比涵盖的信息量更大10，数据泛化本质是以降低数据的精度来换取对数据的匿名，泛化的好处是不会引入错误的数据，并且能够保留原始数据的一些重要统计特性。数据抑制：数据抑制通常都不会单独使用，而是配合数据泛化使用10，因为数据泛化有时会存在过度泛化导致信息损失过大的情况，而在抑制某条记录可以减少数据损失的情况下，我们就采取直接抑制该记录的办法。子抽样：是指从原始数据表中抽取出小部分具有代表性的数据记录进行分析研究，通过减少对外发布记录的数量，使大部分记录因为没有发布来减少隐私泄露的可能15。但是由于子抽样只是从原始数据中抽取的少部分记录，因此增加了数据挖掘分析的难度，同时子抽样也同样存在对样本的攻击的问题。数据交换：其基本思想是在保持原始数据一些重要统计特性的情况下对各个数据记录的相应属性值进行随机置换，而只对外发布置换后的数据表以达到隐私保护的效果16，通过交换数据使得攻击者无法将发布后的数据记录与原始数据一一对应，增加了攻击者分析的难度，确保了数据信息的安全，我们后面第四章所介绍的组内属性值交换技术就是基于数据交换匿名方法的具体应用。插入噪音：该方法最早在统计泄密控制里就有应用，其核心思想是在原始数据中添加一些与原始数据相符的干扰信息，使得新数据在继承原有基本统计特性以及相关性不变的条件下，通过降低具体数据记录的准确性来增加攻击者推理攻击的难度17。添加噪音需要遵循的原则是：添加的噪音要与原有数据信息相吻合，不至于对原有数据做太大的变动，因此选取恰当的干扰信息是插入噪音匿名技术研究的难点。微集合：是将原始数据表中的记录依据它们属性的取值近似程度组合在一起形成一个等价组18，取等价组中最具代表性的元组作为等价组的类质心，采用类质心代替等价组内所有元组的办法，而在发布的时候只发布类质心及等价组中所包含的元组数目32,33。由于同一等价组中的所有元组具有不可区分性，因而降低了发布数据表隐私泄露的风险。如表2.2所示的原始表，经过微集合后的匿名发布表如表2.3 。 表2.2 原始数据表 表2.3 微集合后的数据表年龄邮编工资收入2012400200024123003000364650060003246300700034464005000年龄邮编记录数工资收入221235022000221235023000344