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

内蒙古科技大学硕士学位论文 论文题目：印耷零獬弘保护技术研究 指导教师： 协助指导教师： 作者： 毕红净 堕堕堕墼撂单位：宇霎直p 彬 论文提交日期：2 0 10 年0 6 月1 2 日 学位授予单位：内蒙古科技大学 单位： 单位： 一_ 一 动态数据集隐私保护技术研究 r e s e a r c ho nd y n a mi cd a t a s e t sp r i v a c yp r e s e r v a t i o n t e c h n o l o g y 一， 研究生姓名：毕红净 指导教师姓名：张晓琳 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 c a n d i d a t e ： b ih o n g j i n g 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 fi n f o r m a t 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 u0 1 4 0 1 0 ，p r c h 烈a l i r l 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意。 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵循此规定) 导师签名：日期：z 口口莎，1 内蒙古科技大学硕士学位论文 摘要 在各式各样的数据库应用中，隐私保护越来越受到人们的关注，因为在数据库 的信息组织与管理中出现了大量隐私泄露现象。对个人而言，由于工作和生活的关 系，常常需要向医院、银行和企业等机构提供自己的个人信息。这些信息可能会被 发布以满足某些机构的运作或者满足科学研究的要求等。但是，这些信息中往往含 有一些敏感信息，即个人不愿意被他人所获知的隐私信息。如果数据发布后隐私信 息被泄露，将会侵犯到个人隐私权。所以，隐私保护已成为当今信息安全领域的主 要课题。 数据匿名化是实现隐私保护的一个有效手段，匿名化技术能在保护隐私信息的 同时，保证对外发布数据的真实性，如何对含有隐私信息的数据进行匿名化已经吸 引了大量研究工作。然而，现有的匿名发布技术大多数是基于静态数据集进行的， 即假设数据集不经过任何更新，只进行“一次 发布。也就是说，大部分隐私保护 匿名算法都不支持数据集经过插入、删除和修改后的重发布。但是，真实数据集往 往随着时间的推移不断被更新，更新后的数据集再次被发布出去，如果把现有的针 对静态数据集匿名技术直接应用于动态数据集重发布上，将会导致大量隐私信息的 泄露。 最近，有少数研究者开始关注如何对动态数据集进行匿名化，但是，他们所考 虑的更新情况并不全面。在很多领域，有些属性值可能发生改变，而有些属性值是 不会被更新的。例如，在医学领域，某人所患疾病可能随着时问转化为另一种疾病 或者痊愈。然而，一旦病人患上永久疾病，如“肺癌”，将不可能痊愈或转化为另 外一种疾病。所以，针对此类情况的动态数据集匿名化将面临着更多的挑战。 本文采用医疗数据，对含有永久疾病动态数据集的匿名化进行研究。以典型的 现有匿名化方法为例，全面地讨论了已有方法面对含有永久疾病动态数据集发布可 能造成的各种泄漏风险。继承了基于“不变性”的思想，提出有效的匿名算法来解 决上述问题。实验结果显示，该算法具有较高的隐私保护度和较低的信息损失度。 关键词：隐私保护：匿名化；动态数据集；永久敏感值 内蒙古科技大学硕十学位论文 a b s t r a c t p r i v a c yp r e s e r v a t i o nb e c o m e sm o r ea n dm o r ec r i t i c a li nm a n yd a t aa p p l i c a t i o n s ， b e c a u s eal a r g en u m b e ro fp r i v a c yi st h r e a t e n e di nt h ei n f o r m a t i o no r g a n i z a t i o na n d m a n a g e m e n to fd a t a b a s e s f o ra ni n d i v i d u a l ，b e c a u s eo ft h ej o ba n dl i f e ，i ti sn e c e s s a r y t op r o v i d ei t sp e r s o n a li n f o r m a t i o nt oh o s p i t a l s ，b a n k s ，e n t e r p r i s e sa n do t h e ri n s t i t u t i o n s g e n e r a l l y t h i si n f o r m a t i o nm a yb er e l e a s e dt om e e tt h eo p e r a t i o no f c e r t a i ni n s t i t u t i o n s a n dt h er e q u i r e m e n t so fs c i e n t i f i cr e s e a r c h h o w e v e r ，t h i si n f o r m a t i o no f t e nc o n t a i n s s e n s i t i v ei n f e l r m a t i o nt h a ti n d i v i d u a l sd on o tw a n tt ob ek n o w nb yo t h e r s i ft h ed a t ai s l e a k e da f t e rt h er e l e a s i n go fi n f o r m a t i o n ，i tw i l li n f r i n g eu p o np e r s o n a lp r i v a c y t h e r e f o r e ，p r i v a c yp r o t e c t i o nh a sb e c o m e am a j o rt o p i co fi n f o r m a t i o ns e c u r i t yf i e l d a n o n y m i z a t i o ni sa ne f f e c t i v ea p p r o a c ht op r e v e n tp r i v a c yl e a k a g e ，t h ea n o n y m i z a t i o n t e c h n i q u ec a np r e s e r v ep r i v a c yw h i l eg u a r a n t e et h et r u t ho ft h ep u b l i s h e dd a t a , e f f i c i e n t a n o n y m i z a t i o nh a sa t t r a c t e dm u c hr e s e a r c hw o r k ，m o s to fw h i c h , h o w e v e r , h a s b e e nd o n eo n s t a t i cd a t a s e t ，w h i c hh a sn ou p d a t ea n dn e e do n l y “o n e - t i m e ”r e l e a s e s i no t h e rw o r d s ，m o s t o ft h ep r i v a c yp r e s e r v i n ga l g o r i t h m sd on o ts u p p o r tt h er e - p u b l i c a t i o no fd a t a s e t sa f t e r i n s e r t i o n s ，d e l e t i o n sa n du p d a t e s h o w e v e r , m o s to ft h er e a lw o r l dd a t as o u r c e s a l ed y n a m i c a p p l y i n gt h ee x i s t i n gs t a t i cd a t a s e tp r i v a c yp r e s e r v i n gt e c h n i q u e sd i r e c t l yc a u s e su n e x p e c t e d p r i v a t ei n f o r m a t i o nd i s c l o s u r ef r e q u e n t l y r e c e n t l y ，af e wr e s e a r c h e r sb e g i n t o p a ya t t e n t i o nt oa n o n y m i z i n gd y n a m i c d a t a s e t s m e a n w h i l e ，t h e r ea r es o m ed e f i c i e n c i e si nt h e s er e s e a r c h e s i nm a n yf i e l d s ， s o m ea t t r i b u t ev a l u e sc h a n g ep r o b a b l yb u ts o m en o t f o re x a m p l e ，i nt h em e d i c a lf i e l d ， o n ep e r s o n sd i s e a s em a yb ec o n v e r t e di n t oa n o t h e ro rb ec u r e do v e rt i m e h o w e v e r ， o n c es u f f e r i n gf r o map e r m a n e n td i s e a s e ，s u c ha s “l u n gc a n c e r ，i tc a nn o tb ec u r e do r c o n v e r t e dt oo t h e rd i s e a s e s t h e r e f o r e ，a n o n y m i z i n gd y n a m i cd a t a s e ti ns u c hs i t u a t i o ni s m o r ec h a l l e n g e a b l e t h i sp a p e ri n v e s t i g a t e st h ea n o n y m i z a t i o nw o r ko fp e r m a n e n td i s e a s e sd y n a m i c d a t a s e t su s i n gm e d i c a ld a t a b a s e s t a k i n gt h et y p i c a lc u r r e n ta n o n y m i z a t i o nt e c h n i q u e sa s e x a m p l e ，w ed i s c u s se x h a u s t i v e l yv a r i o u si n f e r e n c ec h a n n e l so fs e r i a lr e l e a s i n gd y n a m i c d a t a s e t so nm e d i c a lr e c o r d su s i n ge x i s t i n gm e t h o d s ，a n dt h e np r o p o s ea ne f f i c i e n ta l g o r i t h m o nt h ei d e ao f “i n v a r i a n c e ”t h ee x p e r i m e n t a lr e s u l t ss h o wt h a to u rm e t h o dp r o t e c t sp r i v a c y a d e q u a t e l ya n dh a sl o wi n f o r m a t i o nl o s sm e t r i c k e yw o r d s ：p r i v a c yp r e s e r v a t i o n ；a n o n y m i l i z a t i o n ；d y n a m i cd a t a s e t s ； p e r m a n e n ts e n s i t i v ev a l u e s u o _ 内蒙古科技人学硕十学位论文 目录 摘要i a b s t r a c t i i 1 绪论1 1 1 研究背景1 1 1 1 传统的隐私权。2 1 1 2 信息时代的隐私权3 1 1 3 隐私保护特点一3 1 2 国内外研究现状4 1 3 研究意义。6 1 4 研究内容与论文组织7 1 4 1 本文研究内容7 1 4 2 论文组织结构7 2 数据隐私保护相关技术9 2 1 隐私泄露类型。9 2 2 隐私泄露度量9 2 3 匿名数据质量度量1 0 2 4 隐私泄露控制技术1 1 2 5 匿名化技术1 2 2 5 1 匿名化相关定义12 2 5 2 匿名化原则1 2 2 5 3 匿名化算法。1 6 2 6 隐私保护的数据挖掘技术16 3 含永久敏感值动态数据集重发布的隐私泄露分析1 9 3 1 问题分析和动机l9 3 2 隐私威胁剖析19 3 2 1m - d is tin c t 的局限19 3 2 2h d - c o m p o s i t i o n 的不足2 1 内蒙古科技人学硕十学何论文 4 含永久敏感值动态数据集重发布的匿名原则与算法2 2 4 1 相关定义2 2 4 2 动态更新概念2 3 4 3 匿名重发布原则2 3 4 4 匿名算法2 5 4 4 1 标记永久敏感值及伙伴记录2 6 4 4 2 创建桶队列2 6 4 4 3 处理桶中永久敏感值2 7 4 4 4 插入记录2 7 4 4 5 分裂桶生成q i g r o u p 2 8 5 实验测试和结果分析2 9 5 1 实验环境2 9 5 2 实验数据2 9 5 3 测试结果及分析2 9 5 3 1 隐私保护度测试3 0 5 3 2 信息损失度测试3 0 5 3 3 伪元组与隐匿记录个数测试3 1 结论3 3 参考文献一3 4 在学研究成果3 9 致谢一4 0 内蒙古科技人学硕十学位论文 1 绪论 1 1 研究背景 随着信息技术不断进步，计算机和网络在全世界范围内对商业、教育、娱乐乃至社 会生活各个方面的发展都起到了迅猛的推动作用，信息成为一个国际最重要的资源。一 方面，大部分信息，包括个人信息，均以数据的形式存储在各种数据库中，并在互联网 中传播。另一方面，我们自然人在计算机和网络中的表现形式也成为姓名、性别、年 龄、籍贯等数据记录。因此，个人隐私在信息时代的主要表现形式就是个人数据。这些 数据包括可以公开的非隐私数据和不能公开的隐私数据。但是，随着数据挖掘技术的崛 起，个人数据、企业数据等多方数据时刻都存在着被泄漏的可能，一旦不能公开的隐私 数据被泄露，将给数据所有者带来损失。因此，数据库隐私保护己成为当今信息安全领 域一个亟待解决的课题i l 捌。 数据已经成为一个重要资源，越来越多数据的应用己经涉及到微数据的发布和使 用。所谓微数据，就是那些包含了个人信息但未经任何处理的原始数据。大量访问 数据、共享数据和数据挖掘方法的出现使得数据拥有者对隐私保护的要求越来越高。这 个现象主要有两方面的原因，一是越来越多的数据应用涉及到个人隐私。医学研究者为 了进行医学研究，可能需要医院提供患者的病例信息；银行为了核对每天的交易记录， 可能要查看自动存提款机上的一些交易细节等等，所有这些行为都有可能涉及个人的隐 私信息。然而，为了根据这些数据进行某些公共目的的研究，数据所有者不得不对这些 数据进行发布，这无疑将会把数据中的个人隐私信息暴露给研究人员或攻击者，给用户 的隐私带来严重的威胁。另一方面是由于人们的自我保护意识正在逐步增强，人们都不 希望自己的隐私被公众所获知。 大多数企业、医疗机构以及政府部门这些保存着如员工薪水、医疗记录、个人借贷 等个人资料的组织，虽然它们在发布数据时会采取措施来隐藏发布数据中的个人身份标 识或者某些隐私数据，但是值得注意的是，通过在多个公开的数据源问进行链接操作往 往会导致意想不到的隐私信息泄漏问题。近年来的研究表明大量美国居民可以根据非身 份属性集合，例如年龄( a g e ) 、性别( g e n d e r ) 、邮编( z i pc o d e ) 等来进行个体识 别。假设某家医院要将诊断记录表1 1 发布给医学研究者，其中疾病( d i s e a s e ) 为个人 不愿意被泄露的隐私属性。即使删除表1 1 中的身份属。i 生n a m e ，如表1 2 所示，如果攻击 者知道目标个体l a r k 性别为f e m a l e ，年龄为7 0 ，邮编为4 3 0 0 0 ，根据表1 2 ，攻击者仍然 可以确定l a r k 对应表1 2 中的第一条记录。因此，攻击者便获知t l a r k 所患疾病为“l u n g c a n c e r 。 内蒙占科技人学硕十学位论文 表1 1 原始数据表 表1 2 删除n a m e 属性后的数据表 因此，根据传统的数据隐私保护方法得到的匿名数据根本保护不了个人隐私不被侵 犯，攻击者依然可以根据所知道的某些背景知识推测目标个体的隐私信息。因此，必须 对待发布数据进行更加严格的匿名处理才能到达隐私保护的目的。尽管如何在发布个人 信息数据的同时保证个人隐私不被泄露已经成为众多学者关注的问题，但数据发布中的 隐私保护仍然存在很多值得研究的方面。 1 1 1 传统的隐私权 隐私是一个受文化、环境和社会等因素影响的抽象概念。事实上，自从人类社会形 成以来，隐私便随之产生，并伴随着社会的发展逐步赋有了内涵。“隐”是指某种活动 及领域是隐蔽的，不被他人干涉的；“私”是指纯粹私人的，与公共利益、群体利益无 关的事情。 关于隐私权的最早定义是源于美国哈佛大学两位教授w a r r e n 和b r a n d i e s 在h a r v a r d l a wr e v i e w 上发表的n er i g h tt op r i v a c y p j ，他们提到“隐私权是个人不受旁人干涉的 权利，这种权利是宪法规定的人所共享的自由权利的重要组成部分，只有文明教养达到 一定程度的人才会认识到它的价值，进而才能重视它”。 另外，1 9 6 7 年，w e s t i n 认为“隐私是人们自由选择环境和公开自己行为及其程度 的一种愿望【4 】，它应该包含离群独处、亲密交往、隐藏身份、保留隔阂等四种基本情 况。1 9 8 4 年，s c h o e m a n 将隐私定义为“个人决定与他人交换哪些信息和控制这些信息 的一种权利【5 j ，。2 0 0 1 年，g a r f i n k e l 指出“隐私就是自治、完整性和自我所有1 6 1 ”。然 而，在2 0 0 0 年，r o s e n b e r g 却认为“隐私不是一种权利而是一种品位1 7 1 ”。关于传统隐 _。h”。i 内蒙古科技人学硕士学位论文 私权的定义有很多，而到了近代社会，随着信息技术的发展，人们对隐私的定义又上升 到了一个更新的层次。 1 1 2 信息时代的隐私权 信息技术推动了人类社会的变革和发展，信息化逐步融入进了人们的工作、生产和 生活中。伴随着信息化的发展，产生的关于个人、企业的数据信息正在无声无息地被保 存在不同的数据库中，当这些信息被不正当地使用时，就有可能产生隐私泄露的问题。 基于网络的便捷、开放、几乎全透明的特点，传统的隐私权从其存在的现实世界进 入到虚拟世界中，网络隐私权也应运而生。网络隐私权是公民在网络媒体上享有的私人 生活与私人信息依法受到保护的一种人格权，私人数据信息不能被他人非法侵犯、获 知、公开和利用；也指禁止在网络上泄露任何与个人有关的敏感信息。除了网络隐私权 之外，计算机中存储的个人或团体机构的数据都被视为隐私数据。信息时代的隐私可 分为以下四个方面： ( 1 ) 个人属性的隐私：姓名、身份、肖像、声音等。由于其直接涉及个人领域 的第一层次，可谓是“直接”的个人属性，为隐私权保护的首要对象。 ( 2 ) 个人资料的隐私：个人属性被抽象成文字的描述或记录，如个人的消费习 惯、病历、宗教信仰、财务资料、工作、犯罪前科等记录。若其涉及的客体为一个 人，则这种资料即含有高度的个人特性而能辨识该个人的本体，可以说“间接 的 个人属性也应以隐私权加以保护。 ( 3 ) 通信内容的隐私：个人的思想与感情。原本存在于内心之中，别人不可能 知道，当与外界通过电子通信媒介如网络、电子邮件沟通时，即充分暴露于他人的 窥探之下，所以通信内容应加以保护，以保护个人人格的完整发展。 ( 4 ) 匿名的隐私：可以保障人们愿意对于社会制度提出一些批评。 1 1 3 隐私保护特点 过去对数据库安全的研究，多是授权或加密技术。授权和加密技术对于信息和数据 的保护非常重要，它们是通过身份认证和数据编码方式来预防外部威胁或未授权的访问 企图。通过对信息安全问题的进一步研究，提出了更高层次密码技术的要求，要求相应 的保护模型从基于服务器的保护装置到基于客户机的保护模型，以及到后来的逻辑架构 保护模型来确保访问授权策略。为了阻止攻击者识别目标个体在原始数据中的对应记 录，从而进一步获取目标个体的隐私信息，传统的方法将数据中能够唯一识别具体记录 的身份属性，例如身份证号等删除后进行发布。近来的研究表明大量个人信息可以根据 非身份属性集合，例如年龄、性别和邮编等来进行识别。利用这种方法至少能识别一个 内蒙占科技人学硕士学位论文 具体个体在数据表中对应的记录。此方法在一定程度上可以防止敏感信息的泄漏，却无 法避免用户通过非敏感数据，综合其它外部知识间接推理出敏感信息。当前应用中出现 的大量隐私泄漏和攻击行为使得隐私保护技术层出不穷。 隐私保护技术是近几年新产生的信息安全技术，它与传统的访问控制技术和加 密技术有着本质的区别。访问控制和加密这两种技术的核心思想都是保护数据的隐 秘性，保证隐私数据不能被没有授权访问的人访问。它们的方法一般都是通过切断 从攻击者到隐秘数据的道路( 访问控制技术) 或者使得攻击者获得的数据变得不能 再使用( 加密技术) 来实现。攻击者则是以获得可用的隐私数据为最终的目的。而 隐私保护技术并不保障数据的隐秘性，隐私数据对外是完全公开的，甚至任何人都 可以访问它。隐私保护技术的核心思想是要保护隐私数据与个人之间的准确对应关 系，换句话说就是隐私数据可以被任何人得到，但是却不能把该数据对应到某个特 定的人身上。从攻击者的角度看，攻击的目标是获取隐私数据与个人之间的准确对 应关系。 1 2 国内外研究现状 、 近年来，随着互联网技术和信息技术的发展以及现实环境中数据应用的实际需求， 隐私保护技术引起越来越多研究者的关注，涉及的研究范围也很广泛。根据信息共享中 隐私保护对象不同，将其分为两类：一类是以原始数据为隐私保护的对象，另一类是以 数据中隐含的知识为隐私保护的对象。论文主要考虑第一类以原始数据为隐私保护的对 象，这一类研究中考虑以全部原始数据或其中部分敏感数据为隐私保护的对象，根据研 究方向的不同，主要可以分为基于数据干扰( d a t ap e r t u r b a t i o n ) 的研究，基于安全多方 计算( s e c u r em u l t i p a r t yc o m p u t a t i o n ，s m c ) 的研究和基于数掘匿名化的研究。 数据发布的隐私保护研究可以被分为两个分支。第一个分支是对于静态数据集 一次发布的保护，第二个分支是对于动态数据集重发布的保护。 对于一次发布，很多隐私保护算法模型已经被提出。传统的算法模型就是k 匿 名1 8 , 9 9 ，1 0 l ，它要求对一个发布表中的每一条记录r ，保证至少有k 1 条记录与r 在准标 识符上的值相等，这样该记录的个体身份将不能被唯一确定。然而，k 匿名技术在 抵制同质攻击【1 1 】和背景知识攻击1 1 1 】上存在着不足。所以，一个更有效的模型l 一多样 性j 被提出，它考虑了q i 属性组和敏感属性的关系，要求每个组内至少出现l 个 不同的敏感值。n “等人也考虑了这种相关性，提出了t - c l o s e n e s s ! 忆j ，它要求q i 组 内敏感属性值的分布与敏感属性值的整体分布的差异不超过t 。当数据表中准标识符 属性的个数较多时，通过泛化和隐匿的方法对数据进行k 匿名化会损失大量信息， 因此文献 1 3 1 提出了一种不基于泛化和隐匿的新颖方法a n a t o m y 。它通过将原始 内蒙占科技大学硕士学位论文 关系的准标识符属性和敏感属性以两个不同的关系发布，利用它们之间的有损链接 来保护隐私数据的安全，并且给出了基本的a n a t o m y 算法保证发布的数据满足l 多 样性的要求。同样，文献 1 4 】也提出了一种基于有损链接的隐私数据匿名发布算 法。于戈【l5 】等对单一约束k 一匿名方法进行扩展，提出了多约束k 匿名方法 c l a s s f l y + ，c l a s s f l y + 继承了c l a s s f l y 的元组泛化思想，减少了信息损失，保证了匿名 精度。 针对一次发布的一些文献【1 l ，1 6 ，1 7 也考虑了背景知识攻击的情况。在文献【ll 】 中提到，同本人几乎不可能患心脏病。m a r t i n 等人在文献 1 6 】中提出一种新的背景 知识攻击考虑个体之间的联合。例如，如果一个个体被确认患了“a i d s ”，那么 此人的亲密朋友也可能患此疾病。r w o n g 等人在文献 1 7 1 中提出背景知识可以成为 匿名算法的原则。x x i a 0 1 1 8 1 提出了一种基于人性化匿名的新泛化框架，该方法实现 了满足个体需求的最小泛化，保留了原数据中大量信息。 上述文献都是基于数据集一次发布进行匿名研究，而对数据集重发布的研究甚 少。k w a n g 和b c m f u n 9 1 1 9 1 研究了连续发布的匿名问题，但是每次的发布都是针对 同一个数据集发布不同的属性集合。 j b y u n l 2 0 等人最早针对持续增长数据集的发布进行研究，其方法是当有新数据 插入时，并不是直接插入到其某个等价组中，而是等到新的数据达到一定量并能满 足l 多样性时，才将其添加到下一版本的数据表中。但是它的匿名方法需要推迟记 录的释放，而且这种推迟可能是无限的，因此记录不能及时被发布。文献【2 l 】和文 献【2 2 】提出了一种隐私模型，沿用k 匿名来抵御增长的数据集。文献【2 3 】提出了一 种利用经典的空间索引技术来实现k 匿名的模型，具有很好的扩展性，并且能很好 地支持增量数据发布。 x x i a o l 2 4 j 首次研究了在数据集重发布中既支持记录插入又支持记录删除的方 法。他提出了一个新的匿名概念“m i n v a r i a n c e ”，若有一条记录t 被多次发布，那么 包含t 的所有q i 组必须有相同的敏感值，被称为签名1 2 4 j 相同。这种方法可以消除多 个版本之间的推理通道，要实现此方法还需要加入“伪元组1 2 4 1 ”。但是如果有记录 的敏感属性值被修改，i n i n v a r i a n c e 算法模型是不能达到隐私保护要求的，也就是说 m i n v a r i a l i c e 不适用于数据集中记录被修改的情况。 y b u i 2 5 】等人首次提出了永久敏感值的概念，结合动态登记表，保护连续数据发 稚隐私泄露的问题。他们指出，如果没有永久敏感值的存在，传统模型如l 多样性 就能很好的保护连续发布数据集的隐私信息。如果攻击者获得所有人的参与情况， 那么没有一种泛化算法可以杜绝隐私泄露。然而，得知所有人的参与情况的假设是 不现实的，所以文献 2 5 】限制了攻击者获得背景知识的可能性。 内蒙古科技人学硕十学位论文 文献【2 6 】针对动态数据集重发布匿名化算法中还没有可行的匿名化原则和相应 的算法能处理一般化的全动态数据集( 包括数据集的增加、删除和属性值更新) 重 发布问题，首次提出了内部更新与外部更新的概念，并给出了一个能实现全动态数 据集重发布的匿名化原则“m d i s t i n c t 。但是m d i s t i n c t 却忽略了永久敏感值【2 5 】更新 。， 的复杂情况，如果数据集中包含永久敏感值，此匿名化原则依然会造成隐私泄露。 1 3 研究意义 随着计算机技术、网络技术的迅猛发展，包含个人信息的数据种类和数量呈指数增 长。为了进行数据挖掘，数据所有者需要发布这些包含个人信息的数据集。然而，在发 布的过程中无疑会造成个人信息被暴露。同时，无论企业还是个人，隐私保护的意识观 念也越来越强，都不希望自己的隐私信息被泄露出去，从而可能对自己造成意外的危 害。所以，隐私保护问题若不能得到很好的解决，将阻碍各类技术及应用的前进。保护 私有信息的隐私保护技术有着重要的理论价值和实际应用价值，因此一直是相关领域专 家们的研究重点。 目前，数据隐私保护技术研究已经产生了大量的理论成果和系统原型，他们的主要 工作大多集中在对静态数据集的匿名保护处理，即只考虑数据集的“一次”发布，即使 数据集有多次发布，也把每次发布都看成是“独立”的数据集来处理。随着隐私保护技 术研究的深入，人们研究静态数据集已经达到一定水平，开始了对动态数据集的研究， 将来的研究趋势也将主要针对动态数据集。因为真实的数据集基本上都是动态的，随着 时间的推移，这些数据的内容会因为插入、删除和修改等操作而改变。因此，当数据的 内容发生改变时，必须对数据集重新进行发布。那么，如果还按照原来的静态匿名策略 进行发布，即使每次发布的版本本身都满足匿名要求，但是如果攻击者结合多次发布的 数据表，很可能会形成多个版本之问的推理通道，从而造成隐私信息泄漏，由此激发了 人们对支持重发御匿名化技术的研究。 本文的主要工作在于： 。 ( 1 ) 本文总结了隐私泄露的类型和度量，以及控制隐私泄露的常用技术； ( 2 ) 针对现有匿名技术不能满足对动态数据集的隐私保护以及信息损失程度较大 等问题，提出了一种基于“不变性”思想的匿名模型，并给出算法； ( 3 ) 通过与m d i s t i n c t 算法比较隐私保护力度以及与h d - c o m p o s i t i o n 算法比较匿 名后的数据质量，结果表明本文提出的算法在隐私保护力度和匿名数据有效利用率上都 有所提高。 内蒙古科技人j ；乏硕+ 学位论文 1 4 研究内容与论文组织 1 4 1 本文研究内容 对数据进行匿名化是实现隐私保护的一个有效手段，数据匿名化的基本思想是通过 泛化刚原始数据使改变后的数据不能被唯一识别，从而保护隐私信息不被外界披露。值 得注意的是，在大多数应用中，对数据的单次发布已经不能满足应用的需求，而是需要 对数据进行多次更新发布。例如医疗记录集，人口统计记录集等，随着时问的推移，这 些数据不断被更新，而且这些更新还要立足于现实情况。因此，在不同的时刻，往往需 要对动态数据进行多次重发布，从而引出了对真实情况的动态数据集重发布隐私保护技 术研究。 在分析现有算法面对真实的不断更新的动态数据集不安全匿名基础上，本文完成了 通用的、适用于真实的含有永久敏感值动态数据集匿名化问题的隐私保护算法，并实验 测试该算法具有较高的隐私保护度和较低的信息损失度。 本文研究内容如下： 1 详细介绍数据隐私保护相关技术； 2 详细分析含有永久敏感值的数掘集重发布可能造成的隐私泄露情况； 3 对聚类泛化算法进行深入研究，使用其算法实现对原始表的泛化； 4 设计支持含有永久敏感值的数据集重发布的匿名原则，并给出匿名算法； 5 通过实验对本文算法和现存算法进行比较测试。 1 4 2 论文组织结构 本文对含有永久敏感值动态数据集的隐私保护进行了深入的研究。论文按如下方式 进行组织： 第一章绪论部分阐述了研究背景，隐私与隐私保护的发展，介绍数据发布中隐私保 护的研究现状以及明确本文研究意义和贡献； 第二章总结了数据隐私保护相关技术，包括隐私泄露类型、隐私泄露度量、匿名数 据质量的衡量方法和隐私泄露控制技术，主要介绍匿名化技术，最后给出隐私保护数据 挖掘技术； 第三章首先提出问题并阐明本文研究动机，最后详细剖析现有匿名技术针对真实动 态数据集的隐私泄露风险以及匿名后信息损失程度大等问题； 第四章首先描述动态更新的概念，之后详细介绍本文的匿名重发布原则，最后给出 匿名算法； 第五章实验测试以及结果分析、评估； 内蒙古科技人学硕+ 学位论文 最后对本文工作进行总结，并展望今后可能的研究方向。 内蒙占科技人学硕十学位论文 2 数据隐私保护相关技术 2 1 隐私泄露类型 数据集隐私信息泄露与否，关键在于使用何种方法束发布数据集。为了保护个人隐 私信息，以往的方法是在数据发布的时候从数据表中删除标识符，但是攻击者通过从外 部数据源获得的数据进行链接处理，获得可以推演敏感信息的渠道，从而造成个人隐私 的泄露，这种攻击方式称为“链接攻击”。例如，1 9 9 7 年美国马萨诸塞州东部剑桥市 的选举列表包括5 4 8 0 5 个投票信息，包括投票人的性别、出生日期和邮政编码。调查发 现，仅通过出生日期就可以准确确定近1 2 的投票人的姓名和地址，联合出生r 期和性 别可以准确确定近2 9 ，联合出生日期和5 位数字的邮编就可以准确确定近6 9 ，通过 邮编全称和出生日期可以准确确定近9 7 的投票人名字和住址( 近5 3 0 3 3 人) ，通过三 者就几乎可以将任意一条投票记录唯一对应到一个投票人。 链接攻击又可以称作是推理泄露问题，推理问题也是指通过不敏感的数据或者原始 数据集以相当高的概率推断出敏感数据信息。为了解决这种潜在的推理泄露问题所带来 的隐私泄露，当前研究成果主要有以下两个方面： ( 1 ) 在多级安全数据库中，通过在数据库设计阶段检测推理通道，在查询处理阶 段排除推理通道来实现推理控制，避免隐私泄露1 2 8 】。 ( 2 ) 在通用数据库中，提出了对数据库推理问题形式化的描述，同时提出了要有 对推理算法进行评估的方法，例如最小限度地偏序泄露、对现有的数据仓库进行分类、 通过知识发现防止推理泄露等1 2 9 1 。 值得注意的是，泄露的数据可以是确切的数据，也可以是近似的数据。如果能准确 的求得数据值，那么是确切泄露，不能准确的求得数据值，则为近似泄露。对于近似的 泄露，可以有以下三种： ( 1 ) 范围泄露，就是要降低确定的值的不确定性，这样推理出来的概率就相应提 高，也就可以推理出敏感数据更为精确的取值范围。 ( 2 ) 否定结果泄露，就是通过执行查询确定一个否定的结果。 ( 3 ) 泄露带有概率性，就是泄露的信息可靠程度以某种概率来表示，确定出某个 域是某个值的概率。 2 2 隐私泄露度量 隐私保护技术产生的主要目的就是保护数据库中个人信息的安全性，也就是减小信 息泄露的风险。信息泄露风险是指攻击者通过获取已知的背景知识，推断出某条记录真 内蒙占科技大学硕+ 学位论文 实信息的可能性。数据发布中的标识隐私泄露问题属于记录联接 3 0 1 范畴，记录联接是指 两个具有共同属性的记录集之间发生匹配的情况。数掘发布中主要存在两种隐私泄露风 险度量，一种是概率型记录联接的度量，另一种是基于距离的记录联接的度量。 ( 1 ) 概率型记录联接的度量是指某数据源a 有m 条记录，某数据源b 有n 条记 录，b 中的每一条记录都有可能与a 中的任一条记录发生匹配，两个数据源之间共存在 m n 种可能发生的匹配。a 中的记录a 和b 中的记录b 的一致性度量是一个函数a 和 b 的二元函数，通过设置关键的阀值就可以将记录组标记为匹配的、未确定的和不匹配 的，从而可以判断出泄露风险度。 ( 2 ) 基于距离的记录联接度量是指首先计算数据源a 中的任意一条记录a 与数据 源中的每一条记录的距离，然后从这些距离值的集合中选取两个与数据源a 中记录a 距 离最近的值，如果这两个值中存在与记录a 发生匹配的记录，那么记录a 的匹配就是正 确的，否则就是错误的。此度量方法的关键在于对不同类型、不同取值范围的变量定义 标准化的距离计算方法和对不同的属性设置合适的权值，所以基于距离的计算方法在计 算上更加复杂一些，但是研究者d e y 认为基于距离的度量方法比基于概率型的度量方 法，具有更好的鲁棒性1 3 l 】。 2 3 匿名数据质量度量 理想的隐私保护1 3 2 , 3 3 】技术保证发布的匿名数据不泄漏任何个人隐私信息。为了保 护个人的隐私信息，将原始数据转换成匿名数据进行发布。同时，大量的研究任务又是 基于发布的数据，因此，数据发布的隐私保护必须均衡隐私泄漏风险和数据的可用性这 两个方面。发布匿名数据质量的度量反映在通过隐私保护技术处理后数据的信息丢失 上，信息丢失越多，匿名数据的质量越差，数据的利用率就越低。造成信息损失的原因 主要有两个方面：一是修改后的数据比原始数据更加概括含有更少的有效信息；二是原 始数据预处理时进行了抑制或加入了噪声等，后者对数据有效性的影响更大。对数据进 行预处理时有可能将一些错误信息加入到结果数据中，从而影响数据的可用性，所以必 须尽可能地降低这种错误的产生，保证匿名数据的质量。 衡量匿名数据质量的标准有很多，最早的标准有利用泛化高度瞰j 。泛化高度标准实 际上是原始数据集上所有泛化步骤的总和，这样的衡量标准被提出是因为研究者认为一 个泛化步骤可以表示一次信息损失。但是泛化高度标准的问题在于并不是所有的泛化步 骤都会导致等量的信息损失，完全从客观角度进行信息损失衡量，而数据的有效性在具 体应用环境中具有不同要求。因此，对于不同的应用需求，需要定义具体的信息损失衡 量方法。 内蒙古科技人学硕十学t 带论文 其它的衡量标准还有分类标准1 3 5 j 和信息获得与隐私丢失比【3 6 1 ，这两种是考虑了匿名 数据可用性的衡量标准。分类标准适合应用在通过匿名