（计算机软件与理论专业论文）数据发布中隐私保护的匿名模型及算法研究.pdf

数据发布中隐私保护的匿名模型及算法研究 摘要 目前在数据库领域存在着大量的与个体相关的数据，如：人口统计数据、客户购 物数据、患者医疗数据等，称之为微数据。这些数据对于趋势分析、市场预测等具有 重要的价值。然而，由于这些数据中含有个体的隐私信息，它们的发布和共享会对个 体的隐私构成威胁。因此，数据发布中隐私保护问题的研究具有重要的意义。 在数据发布的隐私保护研究中，匿名化方法以其安全、有效成为目前该领域的研 究热点。匿名化方法的思想是通过对原始数据进行某种变换，使攻击者无法唯一的推 导出敏感信息所属的具体个体，从而实现个体隐私的保护。本文从匿名化模型及算法 两个方面，对数据发布中的隐私保护问题进行了研究，主要工作有： ( 1 ) 提出一个实现舡匿名模型的t o p d o w n k a c a 算法。k a c a 是目前信息损失 较小的肛匿名化算法之一，它产生的匿名数据质量高，但效率低，不适合处理大的数 据集。t o p d o w n 是个高效的匿名化算法，但产生的信息损失大。本文结合t o p d o w n 算法和k a c a 算法，提出一个高效且信息损失少的t o p d o w n k a c a 算法。实验结果 表明：所提出的算法可以达到与k a c a 算法近似的信息损失，与t o p d o w n 算法近似 的效率，能更高效、更好的实现肛匿名模型。 ( 2 ) 提出一个实现敏感值个性化隐私保护的匿名模型。现有的匿名模型如：缸匿 名模型、厶多样性模型等都是针对整个数据表设置一个全局的匿名化约束，而没有考 虑隐私保护的个性化需求。当数据中各个敏感属性值的分布不均匀时，这些模型就不 能很好地实现隐私保护。为此，本文提出完全( 口，七) 匿名模型，通过为每个敏感值设 置不f 司的频率约束，来实现对敏感值的个性化隐私保护；并基于加权层次距离，提出 ( a ，k ) 聚类算法。实验结果表明：完全( 口，k ) 一匿名模型能够有效的实现敏感值的个性 化隐私保护。 ( 3 ) 提出一个面向数值型敏感属性的分级多样性模型。现有的7 - 多样性模型主要 适用于分类型敏感属性的数据，而不适用于数值型敏感属性的数据。为此，本文提出 面向数值型敏感属性的分级多样性模型。该模型首先将数值型敏感属性域分级，再基 于分级信息实现数值型敏感属性的多样性。本文还设计了实现分级多样性模型的 - i n c o g n i t o 算法。从匿名表的多样度的角度对分级多样性和未分级的多样性进行了比 较，实验结果表明：前者产生的匿名数据具有更高的多样度，凶而前者具有更强的抵 摘要 制同质性攻击和背景知识攻击的能力。 关键词：隐私保护；肛匿名；完全( 仅，幼匿名；分级多样性；泛化 i i r e s e a r c ho na n o n y m i t ym o d e l sa n da l g o r i t h m sf o r p r i v a c y p r e s e r v a t i o nd a t ap u b l i s h i n g a bs t r a c t t h e r ea r ep l e n t yo fd a t ar e l a t i n gt oi n d i v i d u a l s ，n a m e dm i c r o d a t a ，i nd a t a b a s ea r e a ， s u c ha sd e m o g r a p h i cd a t a ，c u s t o m e rs h o p p i n gd a t aa n dm e d i a c a ld a t ae t c t h e s ed a t ap l a y a ni m p o r t a n tr o l ei nt r e n da n a l y s i s ，m a r k e tp r e d i c t i o ne t c h o w e v e r , b e c a u s et h e s ed a t a o f t e nc o n t a i np r i v a t ei n f o r m a t i o na b o u ti n d i v i d u a l s ，w h o s ep u b l i s h i n go rs h a r i n gw i l lt h r e a t i n d i v i d u a l s p r i v a c y t h u s ，r e s e a r c ho np r i v a c yp r e s e r v a t i o ni nd a t ap u b l i s h i n go rs h a r i n g h a sg r e a ts i g n i f i c a n c e p r i v a c yp r e s e r v a t i o ni n d a t ap u b l i s h i n gh a sg a i nw i d e l yc o n c e ma n db e c o m eah o t t o p i ci nd a t a b a s ea r e a a m o n gt h ev a r i o u sp r i v a c y - p r e s e r v a t i o nr e s e a r c h e s ，a n o n y m i t yh a s b e c o m eo n eo ft h em o s tp o p u l a rm e t h o d sf o ri t ss e c u r i t ya n de f f e c t i v i t y t h em a i ni d e ao f a n o n y m i t yi st om o d i f yt h eo r i g i n a ld a t at om a k es u r et h a tt h ea d v e r s a r i e s c a nn o tu n i q u e l y i d e n t i f yi n d i v i d u a l s i d e n t i t yo rs e n s i t i v ev a l u e s ，t h e r e b yp r o t e c t i n gi n d i v i d u a l s p r i v a c y t h i st h e s i sm a i n l yc o n c e n t r a t e so nt h ea n o n y m i t ym o d e l sa n da n o n y m i t ya l g o r i t h m s ，a n d o u rm a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： ( 1 ) a ne f f i c i e n ta l g o r i t h mf o rr e a l i z i n gk - a n o n y m i t y , n a m e dt o p d o w n k a c a ，i s p r o p o s e d k a c a i so n eo ft h ek - a n o n y m i z a t i o na l g o r i t h m sw h i c hg e n e r a t el e s s i n f o r m a t i o nl o s s h o w e v e rk a c ai s i n e f f i c i e n t ，e s p e c i a l l y w h e nd a t a s e ti s l a r g e t o p d o w ni sa ne f f i c i e n ta n o n y m i z a t i o na l g o r i t h m ，b u ti tg e n e r a t e sh e a v yi n f o r m a t i o nl o s s t h u s ，t h i st h e s i sp r o p o s e st h et o p d o w n k a c a ，w h i c hc o m b i n e st h et o p d o w nw i t ht h e k a c a e x p e r i m e n t ss h o w t h a tt h ep r o p o s e da l g o r i t h mg e n e r a t e ss i m i l a ri n f o r m a t i o nl o s s w i t hk a c aa n dh a ss i m i l a re f f i c i e n c yw i t ht o p d o w n ，t h u si tc a nr e a l i z ek - a n o n y m i t y e f f e c t i v e l y ( 2 ) a na n o n y m i t ym o d e l ，w h i c hc a nr e a l i z es e n s i t i v ev a l u e s i n d i v i d u a t i o np r i v a c y p r e s e r v a t i o n ，i sp r o p o s e d e x i s t i n ga n o n y m i t ym o d e l sf o rp r i v a c yp r e s e r v a t i o n ，s u c h a s k - a n o n y m i t y ，- d i v e r s i t ye t c ，d on o t c o n s i d e ri n d i v i d u a t i o n p r i v a c yp r e s e r v a t i o n f o r d i f f e r e n ts e n s i t i v ev a l u e s ，t h u st h e yc a nn o tp r o v i d ee n o u g hp r i v a c yp r e s e r v a t i o nf o re a c h i n d i v i d u a l sw h e ns e n s i t i v ev a l u e sa r en o tu n i f o r m l yd i s t r i b u t e d t os o l v et h i sp r o b l e m ，t h e i i i t h e s i sp r o p o s e sac o m p l e t e ( a ，幼一a n o n y m i t ym o d e lw h i c hc a ni m p l e m e n ti n d i v i d u a t i o n p r i v a c yp r e s e r v a t i o nf o re a c hs e n s i t i v ev a l u e sb ys e t t i n gt h ef r e q u e n c yc o n s t r a i n t s0 1 1e a c h s e n s i t i v ev a l u eo fe v e r ye q u i v a l e n c ec l a s s n et h e s i sa l s o p r o p o s e sa ，动一c l u s t e r i n g a l g o r i t h mb a s e do nw e i g h t e dh i e r a r c h i e sd i s t a n c e s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e c o m p l e t e ( 仅，p a n o n y m i t ym o d e lc a nr e a l i z ei n d i v i d u a t i o np r i v a c yp r e s e r v a t i o ne f f e c t i v e l v ( 3 ) am u l t i l e v e l - d i v e r s i t ym o d e lf o rn u m e r i c a ls e n s i t i v ea t t r i b u t e si sp r o p o s e d t h e - d i v e r s i t ym o d e li ss u i t a b l ef o rp r o c e s s i n gc a t e g o r i c a ls e n s i t i v ea t t r i b u t e ，r a t h e rt h a n n u m e r i c a ls e n s i t i v ea t t r i b u t e t oa d d r e s st h i sp r o b l e m ，t h i st h e s i sp r o p o s e sam u l t i l e v e l - d i v e r s i t ym o d e lf o rn u m e r i c a ls e n s i t i v ea t t r i b u t e t h ep r o p o s e dm o d e lf i r s td i v i d e s n u m e r i c a ls e n s i t i v ea t t r i b u t ed o m a i ni n t os e v e r a ll e v e l s ，t h e nr e a l i z e s - d i v e r s i t yo nt h e m t h et h e s i sa l s od e s i g n sa n - i n c o g n i t oa l g o r i t h mt or e a l i z em u l t i l e v e l - d i v e r s i t ym o d e l e x p e r i m e n t sc o m p a r et h ep r o p o s e dm o d e la n dt h ee x i s t i n g - d i v e r s i t ym o d e li nt e r m so f t h ed i v e r s i t yo fa n o n y m i t yt a b l e s ，a n de x p e r i m e n t a lr e s u l t ss h o wt h a tt h ed i v e r s i t yo f a n o n y m i t yt a b l e sg e n e r a t e db yt h ef o r m e ri sh i g h e rt h a nt h a tg e n e r a t e db yt h el a t e r , t h u st h e f o r m e rc a np r o v i d es t r o n g e rp r e s e r v a t i o nt or e s i s t h o m o g e n e i t ya t t a c ka n db a c k g r o u n d k n o w l e d g ea t t a c k 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 ；k - a n o n y m i t y ；c o m p l e t e ( 仅，七) 一a n o n y m i t y ； m u l t i l e v e ld i v e r s i t y ；g e n e r a l i z a t i o n i v 目录 摘要i l b s t r a c t ，i i i 1 绪论1 1 1 研究背景与意义1 1 2 数据发布中隐私保护研究现状2 1 3 本文主要工作及组织结构3 1 3 1 本文的主要工作3 1 3 2 本文的组织结构4 2 隐私保护的匿名化方法6 2 1 匿名模型6 2 1 1 舡匿名模型6 2 1 2 厶多样性模型7 2 1 3 ( a ，砷匿名模型8 2 1 4 卜接近模型8 2 1 5 ( t e ) - 匿名模型和( s ，朋) - 匿名模型9 2 1 6 个性化隐私匿名模型9 2 1 7 ( 矗d 匿名模型1 0 2 2 匿名模型的实现技术1 1 2 2 1 实现匿名化的方法“ 2 2 2 实现匿名化的算法1 4 2 3 匿名化数据的可用性度量1 6 2 3 1 基于等价类大小的可用性度量1 7 2 3 2 基于泛化高度或区间大小的可用性度量1 7 2 3 3 基于属性分布的可用性度量1 7 2 3 4 考虑具体应用的可用性度量1 8 2 4 本章小结1 8 3 高效的肛匿名化算法一t 0 p d o w n k a c a 。1 9 3 1 引言19 v 目录 3 2 相关概念l9 3 2 1k - 匿名模型1 9 3 2 2 泛化2 0 3 2 3 距离度量2 2 3 3t o p d o w n k a c a 算法2 3 3 4 实验结果及分析2 4 3 4 1 实验环境与参数配置。2 4 3 4 2 运行时间分析2 5 3 4 3 信息损失分析2 6 3 4 4 可扩展性分析2 7 3 5 本章小结2 8 4 面向敏感值的个性化隐私保护模型2 9 4 1 引言2 9 4 2 相关概念3 0 4 2 1 简单似，约匿名模型3 0 4 2 2 般( 仅，尼) 匿名模型3l 4 3 完全( a ，约匿名模型3l 4 3 1 完全( 仅，助匿名定义3 2 4 3 2 参数仅值的设置原则3 2 4 3 3 实现( 仅，动匿名模型的聚类算法3 3 4 4 实验结果及分析3 4 4 4 1 四种匿名模型间的比较3 4 4 4 2 域泛化与值泛化算法的比较3 7 4 5 木章小结4 0 5 面向数值型敏感属性的分级多样性模型4 1 5 1 引言4 l 5 2 面向数值型敏感属性的分级厶多样性模型4 2 5 2 1 问题分析4 2 5 2 2 敏感值相异度的度量4 3 5 2 3 分级厶多样性模型定义4 4 5 3 分级厶多样性模型的实现4 5 5 3 1 域泛化4 5 5 3 2 分级厶多样性的性质4 7 v i 目录 5 3 3 基于域泛化的- i n c o g n i t o 算法5 0 5 3 4 分级厶多样性的评估5 1 5 4 实验结果及分析5 1 5 4 1 实验环境及参数配置5l 5 4 2 信息损失比较5 2 5 4 3 执行时间比较5 3 5 4 4 多样度比较5 4 5 5 本章小结5 4 6 总结与展望5 5 6 1 工作总结5 5 6 2 展望5 5 参考文献5 7 攻读学位期间取得的研究成果6 4 致谢6 6 浙江师范大学学位论文独创性声明。6 7 学位论文使用授权声明6 7 浙江师范大学学位论文诚信承诺书6 8 v l l 1 1 研究背景与意义 1 绪论 目前在数据库领域存在着大量的与个体相关的数据，称之为微数据，如：人口统 计数据、客户购物数据、患者医疗数据等。这些数据中蕴含丰富的信息，可以用于趋 势分析、决策支持等，是社会学、统计学、经济学等领域进行相关研究的基础。美国 密歇根大学的p a n e ls t u d yo fi n c o m ed y n a m i c ( p s i d ) 数据自1 9 6 8 年开始收集和公布 后，对于贫困、保险、教育等领域的研究有极大的促进，到目前为i 卜已有超过2 0 0 0 篇正式发表的学术论文以p s i d 数据为基础i lj 。 但是，由于数据中通常含有隐私或机密信息，所以它的发布和共享会给个体( 即 数据所属的个体) 带来隐私泄漏的风险。从而数据的发布和共享仍然受剑严格的限制， 致使大量的数据不能得到有效的利用。2 0 0 6 年8 月，美国在线( a o l ) 将他们收集的部 分用户数据( 个人搜索记录两百万条) 发布以供研究者使用，为了不泄漏用户身份( 隐 私) ，发布的数据巾不含用户的身份信息。但是，这些数据发布几天后，美闲时报( n e w y o r kt i m e s ) 就报导：有人从这些数据中追踪到了其中一个用户( 编号为：4 4 1 7 7 4 9 ) 的 真实身份。随后，a o l 立即将共享的数据从网站上删除【2 j 。 隐私保护问题在很大程度上限制了数据的发布和共享，已经成为数据库领域个 迫切需要解决的问题。一方面，数据中含有大量有价值的信息，而数据不能发布和共 享，这对数据使用者、各个行业甚至是整个社会来说都是一个巨大的损失。另一方面， 在没有考虑隐私保护的情况下，数据的发布和共享会给个体带来不可预料的精神、经 济损失。近年来，数据库领域兴起的关于数据发布中隐私保护的研究的目的就是研究 出一套有效可行的隐私保护方法，从技术上解决数据发布和共享时出现的隐私保护问 题。 数据发布中的隐私保护技术研究对个体、各行业甚至整个社会来说，都具有重要 的意义。首先，对于个体来说，这一技术有利于保护个体的权益，避免因隐私的泄露 而带来对个体造成的精神甚至物质上的损失。目前，随着网上银行等事j i 业的发展和普 及，因个人信息泄露而产生的账户资金流失的案例屡屡出现，因隐私信息泄漏而产生 的手机诈骗案件也大量发生等等，这都给人们的日常生活带来了重大的损失。其次， 对各行业和社会来说，有利于促进数据共享和信息交流，实现数据的价值。信息化时 1 绪论 代，有效的趋势分析、正确决策制定等等都要依赖于对大量的数据的分析与挖掘，没 有数据做支撑，预测、决策都无法有效进行。最后，隐私保护技术的研究有助于推动 数据挖掘、数据分析等技术的继续发展和广泛应用。在数据挖掘、数据分析等技术日 趋成熟的时期，隐私保护问题与其之间的矛盾日益凸显，已在一定程度上影响了这些 技术的推广和应用。由此可见，隐私保护技术的研究是势在必行。 1 2 数据发布中隐私保护研究现状 数据发布中隐私保护技术的研究最早源于统计泄密控$ i j ( s t a t i s t i c a ld i s c l o s u r e c o n t r o l ，简称s d c ) 领域。s d c 中隐私保护研究的目的是在保护隐私的同时尽量保留 数据的统计特性，其实现隐私保护的方法主要有微聚集、样本化、随机化、添加噪音 等。自1 9 9 8 年红匿名模型提出以来，数据发布中的隐私保护问题便开始受到计算机 科学领域学者的广泛关注，成为数据库领域的，个研究热点。近年来，在数据库领域 的顶级期刊和会议( v l d b j ，t o d s ，t k d e ，s i g m o d ，s i g k d d ，v l d b ，i c d e 等) 上 都有许多高质量论文呈现。经过十多年时间的发展，数据发布中隐私保护问题在计算 机科学领域的研究已经形成两大分支：隐私保护的数据挖掘( p r i v a c y p r e s e r v i n gd a t a m i n g ，简称p p d m ) 刚，5 】和隐私保护的数据发布( p r i v a c y p r e s e r v i n gd a t ap u b l i s h i n g ，简 称p p d p ) 6 , 7 。 p p d m 这+ 概念是r a k e s ha g r a w a l 于2 0 0 0 年在a c ms i g m o d 上正式提出，主 要针对数据挖掘过程中可能产生的隐私泄密形式。p p d m 在实现隐私保护的过程中需 要结合具体的数据挖掘方法来解决问题，主要采用的是：修改原始数据的方法和隐藏 敏感知识( 即数据库中的知识隐藏，简称k h d ) t 8 j 的方法。p p d p 的概念是2 0 0 7 年由 b a n j a m i nf u n g 正式提出，目的在于研究通用的、能保护隐私的数据发布方法和工具， 即使是没有统计分析、数据挖掘等领域的专业知识的普通数据使用者也可以使用。而 p p d m 中的方法则要求使用该方法的用户具有数据挖掘等方面的专业知识，并且还要 考虑数据发布后的具体应用。 p p d p 与p p d m 的区别在于：( 1 ) p p d p 主要关注数据本身而不是数据挖掘结果， 要求发布出来的匿名数据记录对分析者来说是有意义的，并且仍然可以用传统的数据 挖掘算法对匿名数据进行挖掘，而不需要针对匿名数据开发新的数据挖掘算法；( 2 ) p p d p 主要采用匿名化技术，通过隐藏个体的身份来匿名数据，而不是通过隐藏敏感 的知识( 数据挖掘结果) ，同时p p d m 的隐私保护中需要考虑到相应的数据挖掘算法， 不具有通用性。 p p d p 研究中要求对数据的隐私保护处理满足以下两个条件：( 1 ) 处理后数据具有 1 绪论 保密性，即要求发布出来的数据不能泄漏数据中任何一个个体的隐私信息。( 2 ) 处理 后数据具有可用性，即要求处于保护下的数据还可供研究者对其进行分析研究。不泄 漏隐私是数据发布隐私保护技术的基本需求，但同时保证隐私保护处理后的数据还能 够用于数据挖掘、数据分析等是研究隐私保护技术的主要目的。如果因为隐私保护措 施过于严密而使得处理后的数据无法使用，那么隐私保护技术的研究与使用实际上也 就完全失去了意义，因为这种情况与数据不发布的情况别无两样。 目前，p p d p 研究中已有多种隐私保护方法提出，根据实现方法的不同可以分为： 数据转换的方法 9 , 1 0 , 1 1 , 1 2 , 1 3 , 1 4 】、数据匿名化的方法、安全多方计算的方法【1 5 , 1 6 , 1 7 , 1 8 】和混 合方法【1 9 , 2 0 , 2 1 1 ( 前几种方法的结合) 。其中，匿名化方法以其安全和有效性，成为目前 隐私保护方法研究中的一大热点，匿名化方法的研究现状将在第2 部分进行总结。 1 3 本文主要工作及组织结构 1 3 1 本文的主要工作 本文的研究工作属于p p d p 分支中的一部分。由于关系型数据库仍然是当今数据 存储和管理的主流，因此，当前p p d p 研究中的数据对象主要是关系型的数据，本文 中也主要考虑的是关系型数据的隐私保护。针对目前匿名化方法中在红匿名算法以及 匿名化模型两大方面存在的一些问题，本文做了以下三个工作： ( 1 ) k a c a 算法实现肛匿名模型时产生的信息损失少，但效率低。t o p d o w n 算法 效率高，但它产生的信息损失大。于是本文结合k a c a 和t o p d o w n 算法思想，提出 一。个高效的肛匿名化算法- t o p d o w n k a c a 算法。并从执行时问、信息损失和可 扩展性三个方面对t o p d o w n 、k a c a 和t o p d o w n k a c a 算法进行了比较。通过实验 说明所提出的算法可以达到与k a c a 算法近似的数据质量，与t o p d o w n 算法近似的 效率，当综合考虑算法效率和信息损失时，能比t o p d o w n 和k a c a 算法更有效地实 现肛匿名模型。 ( 2 ) 针对现有模型没有考虑隐私保护的个性化需求，提出实现对敏感值的个性化 保护的完全( 口，k ) 匿名模型。现有的匿名模型如：肛匿名模型、乒多样性模型等都是 针对整个数据表设置一个全局的匿名化约束，而没有考虑隐私保护的个性化需求。当 数据中各个敏感属性值的分布不均匀时，这些模型就不能很好的实现隐私保护。为此， 提出完全( 口，七) 匿名模型，通过为每个敏感值设置不同的频率约束，来实现对敏感值 的个性化隐私保护；并基于加权层次距离度量方法，提出( 口，七) 一聚类算法。实验表明： 完全( 口，后) 匿名模型能够有效的实现敏感值的个性化隐私保护。 ( 3 ) 针对现有模型在处理数值型敏感属性数据方面的不足，提出分级7 - 多样性模 3 1 绪论 型。分析了分级厶多样性模型的相关性质，并在此基础上提出- i n c o g n i t o 算法来实现 该模型。通过实验证明：该模型能有效处理数值型敏感属性数据，较未分级的乒多样 性更安全，能够更好的抵制连接攻击、同质性攻击和背景知识攻击，同时还能抵制近 似攻击。 1 3 2 本文的组织结构 本文共有六章，组织结构如图1 1 所示。 图1 1 论天组织结构图 第一章，主要介绍了本文的研究背景以及研究意义，并就目前数据发布中隐私保 护研究的现状进行了总结。 第二章，从匿名模型、匿名化技术及算法和匿名化数据可用性度量这三个方面对 现有的匿名化隐私保护研究工作进行了详细的总结与分析。 第三章，提出实现肛匿名模型的t o p d o w n k a c a 算法，并通过对比实验证明所 提出算法较现有算法在数据质量、算法效率以及可扩展性方面优于t o p d o w n 和 k a c a 算法。 4 l 绪论 第四章，提出面向敏感值的个性化隐私保护的( 仅，助匿名模型，弥补现有模型如： 缸匿名、厶多样性等模型的缺陷，实现了对敏感值的个性化保护；并给出参数的设置 原则。然后，提出并实现( a ，助聚类算法。 第五章，提出面向数值型敏感属性的分级，多样性模型，并基于该模型设计了 - i n c o g n i t o 算法。实验表明，相对于敏感属性未分级的- i n c o g n i t o 算法，敏感属性分 级的- i n c o g n i t o 算法能够生成多样度更高的匿名表，因此，可以更好地抵制同质性攻 击和背景知识攻击。 第六章，对本文的工作进行了总结，并分析了本研究工作的不足。最后对我们未 来的研究工作进行展望，介绍在将来的研究中所需解决的一些主要问题。 2 隐私保护的匿名化方法 匿名化方法的思想是通过对原始数据进行某种变换，使攻击者无法唯一的推导出 敏感信息所属的具体个体，从而实现对个体隐私的保护。目前匿名化隐私保护方法的 研究工作主要集中在三个方面：( 1 ) 匿名化模型研究，即研究匿名化的数据应该满足 什么样的约束才能抵制相应的攻击；( 2 ) 匿名化模型的实现研究，其中包括匿名化技 术以及相应的匿名化算法；( 3 ) 匿名数据质量的度量，即匿名数据可用性度量等。以 下将从这三个方面来对现有的匿名化研究工作进行总结。 2 1 匿名模型 现有的研究中，已发现的数据发布中个体可能面临的隐私威胁( 即容易遭受的攻 击形式) 主要有：连接攻击( 1 i i l l ( i n ga t t a c k ) 阮2 3 1 、同质性攻击( h o m o g e n e o u sa t t a c k ) 2 4 , 2 5 】、 背景知识攻击( b a c k g r o u n dk n o w l e d g ea t t a c k ) 2 4 , 2 5 1 和近似攻击( p r o x i m i t yb r e a k ) 1 2 6 1 。为了 抵制不同的攻击，各种匿名化模型相继提出，表2 1 中总结了现有的匿名模型。以下 将对一些典型的匿名模型进行简单介绍。 表2 1 现有的匿名模型 抵制攻击形式( ”表示能抵制) 匿名模型 连接攻击列质性攻击背景知识攻击近似性攻击 k 一匿名 ，一多样性 、， ( 口，j | ) 一匿名 尸一敏感- 七一匿名 、， 、， 、， ( 七，p ) 一匿名 ( s ，脚) 一匿名 、， ，接近 、，、， ( k ，) 匿名 、， 个性化隐私 、， 个件化( 口，后) 一匿名 、，、， 2 1 1 舡匿名模型 为了抵制数据发布中可能遭受的连接攻击，s a m a r a t i 和s w e e n e y 掣2 2 , 2 3 1 于1 9 9 8 年提出肛匿名模型( k - a n o n y m i t y ) 。k - 匿名模型的思想是：在数据发布前对数据进行处 6 2 隐私保护的匿名化方法 理，使得发布的数据中每个元组都存在一定数量( 至少为k 个) 的、在准标识属性上取 值相同的元组。这样，即使攻击者通过与其他数据进行连接也无法唯一的标识出各元 组所有者的身份，仅能以不超过1 k 的概率标识元组所属个体的身份，从而降低了隐 私泄漏的风险。 “匿名模型中的k 是由用户定义的整型参数，通过调整参数后的火小可达到对隐 私不同程度的保护。尼的大小与隐私保护程度的关系是：k 越大，隐私保护越强。对 数据进行处理使其满足肛匿名，必然会产生一定的信息损失。信息损失可作为匿名化 数据质量的一种度量。k 的火小与缸匿名化数据质量的关系是：k 越大，信息损失越 大，匿名化数据质量也就越低。因此，在使用时应权衡隐私保护和数据质量两方面的 需求，选取合理的k 值。 缸匿名模型自提出以来得到了广泛的研究，并已应用到对其他类型数据的隐私保 护，比如：社会网络数据的隐私保护旧，定位隐私保护【2 8 1 ，移动轨迹保护【2 9 】以及通 信隐私保护【3 0 】等。 2 1 2 - 多样性模型 由于肛匿名模型中仪考虑对准标识属性的约束，而末考虑对敏感属性的约束，所 以肛匿名化后的数据仍然可能遭受攻击，如：同质性攻击和背景知识攻击等。为了解 决舡匿名模型不能抵制同质性攻击和背景知识攻击的问题，m a c h a n a v a j j h a l a 提出，- 多样性模型 2 4 , 2 5 】，主要思想是要求每个等价类中敏感属性值都是“乒良性表示”( ， w e l l r e p r e s e n t e d ) ，考虑了对敏感属性的约束。等价类即指数据表中在准标识属性上取 值相同的元组的集合。 m a c h a n a v a j j h a l a 2 4 ，2 5 1 还给出几个相应的多样性实例： 相异乒多样性：若数据表的每个等价类中敏感属性至少取，个不同的值，则数据 表满足相异厶多样性。相异，- 多样性是对“良性表示”最简单的理解，但它无法抵制 概率推导攻击，比如：当一个等价类中某一个敏感属性值出现的频率过高，攻击者会 以较高的概率推导出个体的敏感属性值就是频率最高的那个值。于是，作者又给出了 几个相对严格的多样性实例。 信息熵，_ 多样性：设细，靶，勘 是等价类e 中敏感属性的值，p ( e , s i ) 表示s ，在等 价类中出现的频率，则等价类的信息熵e n t r o p y ( e ) 定义为式( 2 1 ) 。如果等价类的信息 熵满足e n t r o p y ( e ) ；一l o g l ，则称该等价类满足信息熵，多样性。当且仅当数据表巾所 有等价类都满足信息熵7 - 多样性时，则称数据表满足信息熵，_ 多样性。 e n t r o p y ( e ) = 一二p ( e ，j f ) l o g p ( e ，薯) ( 2 1 ) 7 2 隐私保护的匿名化方法 信息熵，- 多样性对数据的约束过于严格，当数据表中某些敏感属性值出现频率过 大时，无法使数据实现信息熵乒多样性。另外，信息熵，- 多样性没能提供一个基于概 率的风险度量，使之对数据发布者来说更直观【j 。 递归( c ，j ) 一多样性：设等价类e 中敏感值个数为刀，r i 为第f 个最频繁敏感值出现 的次数。仅当 k 时，则数据表瞒足舡匿名。 例如：表3 1 是一个4 一匿名表( 忙4 ) ，q = z i pc o d e ，a g e ，n a t i o n a l i t y ) 为准标识属 性集，c o n d i t i o n 为敏感属性。表3 1 中有三个等价类，每个等价类都包含四个元组， 当攻击者在对表3 1 在准标识属性上进行连接攻击时，至少连接到4 个元组，导致攻击 者无法唯一的确定某个元组的身份，最大只能以1 4 的概率推测某个元组属于某个个 体，因此达到隐私保护的目的。 表3 1k - 匿名患者数据表( 扣4 ) q “q u a s i i d e n t i f i e r ) ：s e n s i t i v ea t t r 而u t e z i pc o d ea g en a t i o n a l i t y c o n d i t i o n f l ；1 3 0 料 3 0 木 ；h e a r t d i s e a s e 如：130木+30 i ：h e a r t d i s e a s e 一 ： t 3 ： 1 3 0 木木 _ 4 0 牛 ：h e a r td i s e a s e t 7 ： 1 4 8 5 = 4 0 牛 ： v i r a li n f e c t i o n ，8 ： 1 4 8 5 * = 4 0 宰 ：v 证a l i n f e c t i o n - - 一一 一- - 一- -