（计算机应用技术专业论文）数据发布中隐私保护关键技术的研究.pdf

n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y r e s e a r c ho nk e yt e c h n o l o g i e s o fp r i v a c y p r o t e c t i o ni nd a t ap u b l i s h i n g a t h e s i si n c o m p u t e rs c i e n c ea n dt e c h n o l o g ye n g i n e e r i n g b y h u a n g c a n a d v i s e db y p r o f q i nx i a o l i n s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g j a n u a r y , 2 0 1 0 咖2m1舢952舢8 iiii-哪y 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：盘i 丛 日 期：到2 ：墨：12 南京航空航天大学硕士学位论文 摘要 当今信息技术朝着电子化与网络化的趋势发展，人们的个人信息被大规模地收集与共享， 隐私泄漏正日益成为一个重要的信息安全问题。 在数据发布领域，隐私数据完全是对外公开的，任何人都可以访问。如何保护发布数据中 的个人隐私信息不被攻击者恶意获取，同时又使数据接收者充分利用数据信息进行有效的探索 和科学研究，这是一项亟待解决的问题。本文正是在这样的背景下，对数据发布中以泛化为代 表的隐私保护技术进行研究。具体工作和创新点如下： ( 1 ) 介绍现有匿名策略与匿名算法的理论方法和实现技术，分析各种方法自身存在的问 题，并就一些新的研究问题进行探讨。 ( 2 ) 提出了基于属性泛化层自修正的泛化算法r i n c o g n i t o ，该算法是对经典算法i n c o g n i t o 的改进。通过考察原始表中属性值的频数分布，按尽量合并小频数值的原则对属性域作划分， 形成更合理的泛化层，从而减少泛化过程中不必要的泛化，提高发布数据的精确度。实验证明， 原始数据在经过r i n c o g n i t o 匿名后，精确度得到提高。 ( 3 ) 提出了新的数据隐私度和精确度的度量方法。鉴于泛化数据的隐私度目前还没有具体 的度量标准，提出了一种定量测算数据隐私度的度量方法平均泄露概率比；同时归纳整理 现有的各种数据精确度度量，并提出基于信息论相关理论的泛化数据精确度度量加权属性 熵，用来表示模糊值给出信息量的多少。最后由实验表明隐私度和精确度之间的关系。 ( 4 ) 设计与实现了自主研发的安全数据库系统n h s e e u r e 的数据发布子模块，引入采用k 匿名策略的隐私保护机制，实现原始数据的泛化与发布，并以实例表明隐私保护机制增强了发 布的安全性。 关键词：安全数据库，数据发布，隐私保护，隐私度，精确度，泛化算法 数据发布中隐私保护关键技术的研究 a b s t r a c t a st h ed e v e l o p m e n to fe l e c t r o n i c sa n dn e t w o r kt e c h n o l o g y , p e r s o n a li n f o r m a t i o ni s b e i n g c o l l e c t e da n ds h a r e de x t e n s i v e l y t h a tl e a d st oaf a c tt h a tp r i v a c yd i s c l o s u r ei sb e c o m i n ga l li m p o r t a n t s e c u r i t yp r o b l e mn o w a d a y s i nt h ef i e l do fd a t ap u b l i s h i n g ，p f i v a t ed a t ai so p e nt ot h ep u b l i cw h i c hc a nb ea c c e s s e db y a n y b o d y t h u sak e yi s s u ei sh o wt op r o t e c tp r i v a t ei n f o r m a t i o ni np u b l i s h e dd a t af r o mb e i n ga b t a i n e d b ym a l e v o l e n ta t t a c k e r sw h i l ek e e p i n ge n o u g hd a t au t i l i t ys ot h a tr e c e i v e r sc o u l dd ot h e i rr e s e a r c h w o r ke f f e c t i v e l y t h i st h e s i sf o c u s e so nt h et e c h n o l o g yo fp r i v a c yp r o t e c t i o ni nd a t ap u b l i s h i n g ，i n w h i c hg e n e r a l i z a t i o ni sam a i nm e t h o d t h em 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 ) i n t r o d u c et h et h ee m s t i n gp o l i c i e sa n da l g o r i t h m so fa n o n y m i z a t i o n ，a n a l y z ep r o b l e m so f t h o s em e t h o d s ，a n dt a k ead i s c u s s i o na b o u taf e wn e w q u e s t i o n si nt h ef i e l d ( 2 ) p r o p s eag e n e r a l i z a t i o na l g o r i t h r nb a s e do ns e l f - r e v i s i o no fa t t r i b u t eh i e r a r c h i e sc a l l e d r i n c o g n i t ow h i c hi sa ni m p r o v e m e n to ft h ek - a n o n y m i t ya l g o r i t h mi n c o g n i t o t h i sa l g o r i t h m c o n s i d e r st h ed i s t r i b u t i o no fa t t r i b u t ev a l u e si nt h em e t ad a t a ，a n dm a k e sap a r t i t i o nt ot h ea t t r i b u t e d o m a i nw h i c hm e r g e st h ev a l u e sh a v i n gs m a l lf r e q u e n c yt og e tb e t t e rh i e r a r c h i e s i tc a ni m p r o v ed a m a c c u r a c yb e c a u s eo ft h er e d u c t i o no fu n n e c c e r a r yg e n e r a l i z a t i o n e x p e r i m e n t ss h o wt h a tw eg e t h i g h e rd a t aa c c u r a c ya f t e rg e n e r a l i z i n gd a t au s i n gt h i sr i n c o g n i t o ( 3 ) p r o p o s en e w m e t r i c so fd a t ap r i v a c ya n da c c u r a c y p r i v a c yo fg e n e r a l i z e dd a t as t i l lc a nn o tb e a c c u r a t e l yc a l c u l a t e d w ed e f i n eam e t r i c ，a v e r a g ep r o b a b i l i t yr a t et h a td e t e r m i n e st h ed a t ap r i v a c y q u a n t i t a t i v e l y i nt h em e a n t i m e ，w ea n a l y z et h ee x s i t i n gm e t r i c so fd a t aa c c u r a c ya n dd e f i n ean e w o n eb a s e do i li n f o r m a t i o nt h e r o y , t h a ti sw e i g h e da t t r i b u t e se n t r o p y i tm e s u a l sh o wm u c h i n f o r m a t i o nag e n e r a l i z e dv a l u ed e r i v e r s f i n a l l yw es h o wt h ec o n e c t i o nb e t w e e nt h e s et w om e t r i c s t h r o u g he x p e r i m e n t s ( 4 ) d e s i g n ea n di m p l e m e n tt h ed a t ap u b l i s h i n gm o d u l ei nn h s e c u r e ，as e c u r ed b m s d e v e l o p e db yo u rr e s e a r c ht e a m w ei n t r o d u c et h ep r i v a c yp r o t e c t i o nm e c h a n i s mo fk - a n o n y m i t y p o l i c yt ot h ei m p l e m e n t a t i o no fd a t ag e n e r a l i z a t i o na n dp u b l i s h i n g a tl a s tw es h o wt h a tp r i v a c y p r o t e c t i o nm e c h a n i s me n h 锄c e ss e c u r i t yo ft h em o d u l et h r o u g hi n s t a n c e s k e y w o r d s ：s e c u r ed a t a b a s e ，d a t ap u b l i s h i n g , p r i v a c yp r o t e c t i o n ，p r i v a c ym e t r i c ，a c c u r a c ym e t r i c ， g e n e r a l i z a t i o na l g o r i t h m 南京航空航天大学硕士学位论文 第一章 1 1 1 2 1 3 1 4 第二章 2 1 2 2 2 3 目录 绪论。1 研究背景。l 论文选题依据和意义2 本文的主要研究工作3 本文组织结构。3 数据发布中隐私保护的相关技术。4 隐私保护规则4 扰乱、加密与标识符隐藏4 匿名策略。5 2 3 1 链接攻击5 2 3 2k 匿名策略6 ： 2 3 3 其他匿名策略1 0 2 4 隐私保护中的新问题1 3 2 4 1 多次发布中的隐私保护1 3 2 4 2 数值型隐私数据的保护1 6 2 4 3 多敏感属性的隐私保护1 7 2 5 本章小结1 7 第三章基于泛化层自修正的k 匿名全域泛化算法1 8 3 1 r z n c o g n i t o 相关概念和基本性质1 8 3 1 1 相关概念。1 8 3 。1 2 基本性质2 l 3 2算法思想和描述。2 l 3 2 1 原算法存在的问题2 l 3 2 2 算法描述2 3 3 3 实验结果和分析2 6 3 3 1 实验环境和数据2 6 3 3 2 数据质量的度量2 7 3 3 3 数据质量和执行时间分析2 7 3 4本章小结：3 0 i h 数据发布中隐私保护关键技术的研究 第四章k 匿名策略下的数据精确度和隐私度研究3 l 4 1 基于泄露概率的数据隐私度度量3 l 4 2 数据精确度的度量3 2 4 2 1 常见的数据精确度计算3 2 4 2 2 基于信息熵的数据精确度度量3 4 4 3 泛化数据隐私度和精确度度量对比实验3 6 4 3 1 实验环境与数据3 6 4 3 2 实验结果分析3 7 4 4本章小结3 8 第五章n h s e c u r e 中发布模块的设计与实现。3 9 5 1 n h s e c u r e 的设计结构3 9 5 2 n i - i s e c u r e 发布模块设计3 9 5 2 1 发布模块设计概述。3 9 5 2 2 发布模块功能语句说明4 l 5 2 3 泛化模式选取流程：4 2 5 3 n h s e c u r e 发布模块的实现4 3 5 3 1 基本数据结构和文件结构4 4 5 3 2 关键功能函数。4 7 5 4 数据发布示例分析4 9 5 4 1 数据表泛化示例4 9 5 4 2 泛化表结果查询示例5 1 5 5 本章小结。5 2 第六章总结与展望。5 3 参考文献5 4 1 i ! i ：谢 5 7 在学期间的研究成果及发表的学术论文5 8 i v 南京航空航天大学硕士学位论文 图表清单 图2 1 标识符隐藏示例图5 图2 2 链接攻击与重标识示意图6 图2 3 基于泛化技术的k _ 匿名示例图8 图2 4 单维划分、严格多维划分和宽松多维划分1 0 图2 5k _ 匿名的不适用情形。l l 图2 6a n a t o m y 匿名示例1 2 图2 7 基于泛化的通用匿名算法流程1 3 图2 8 医疗记录多次发布示例1 4 图2 9 不同版本匿名表的兼容等价组1 5 图2 1 0m - i n v a r i a n c e 匿名示例16 图2 1 l 数值型隐私保护安全隐患示例。1 7 图3 1 属性“z i p c o d e ”的域泛化层和值泛化层1 9 图3 2 属性a g e 和z i p c o d e 的泛化层。1 9 图3 3 表t 的全域泛化1 9 图3 ：4 表t ( a ，s ，z ) 的属性域泛化层和2 维泛化图示意：。2 0 图3 5 理想情况下的2 一匿名全域泛化2 2 图3 6 极端情形下的2 一匿名全域泛化2 2 图3 7 泛化层自修正示例结构2 3 图3 8 泛化层自修正s t e p 0 ) 示例2 4 图3 9 泛化层自修正s t e p ( 2 ) 示例2 5 图3 1 0 泛化层自修正s t e p ( 3 ) 示例2 5 图3 1 l 属性a g e 和e d u c a t i o nn u m 的泛化2 7 图3 1 2c m 值对比图( 2 属性) 2 8 图3 1 3 执行时间对比图( 2 属性) 2 8 图3 1 4c m 对比图( 4 属性) 2 9 图3 1 5 执行时间对比图“属性) 2 9 图4 1 等价组g 及其各分量属性示例3 5 图4 2 属性a g e ，m ，g e n d e r , c o u n t r y 的泛化层3 7 图4 33 一匿名下w a e 和a b s ( a p p 0 度量值的关系曲线3 7 图4 43 一匿名下w a e 和a ir 度量值的关系曲线3 8 图5 1n h s e c u r e 的框架4 0 图5 2 发布模块结构图4 1 图5 3 泛化模式选取流程图4 3 图5 4 表泛化层结构示意图4 5 图5 5 泛化表结构图4 6 图5 6 泛化信息表结构图4 7 图5 7e m p l o y e e 表和d e p a r t m e n t 表数据示例。5 0 v 数据发布中隐私保护关键技术的研究 v i 图5 8 泛化表的底层存储示例5 l 图5 9 泛化表p u b _ s a l a r y 的查询示例5 l 图5 1 0 泛化信息查询示例5 2 南京航空航天大学硕士学位论文 第一章绪论 随着当今社会信息技术的发展，信息电子化与网络全球化为大规模数据收集与共享提供了 极大的便利，也把人类社会推进到信息高度共享的时代。在各种应用中如数据发布、数据挖掘、 通信、移动网络，用户个人信息泄漏的问题正亟待解决。隐私信息的非授权共享将会严重影响 隐私所有者的利益，目前保护隐私数据在发布或者使用的时候不被识别出来的安全数据发布机 制的研究已成为一个研究热点。 1 1 研究背景 隐私一词源自西方。在西方法学界，一般都认为“隐私”和“隐私权”概念是由美国人沃 伦与布兰代斯最早提倡的。他们在隐私权中首次提出了保护个人隐私、个人隐私权不容侵 犯的观点，认为隐私权本质上是一种个人对其自身事务是否公开给他人的权力，保护个人的隐 私权就是保障个人的“思想、情绪及感受”不受他人打扰的权利，保护自己人格不受侵犯的权 利【4 9 】。到2 0 世纪6 0 年代，隐私权的观念逐渐为美国法律界所熟悉，但隐私权的内容为何，却 始终未见有明确的界定。1 9 6 0 年，w i l l i a mlp r o s s e r 教授在加州法律评论上发表了隐私 一文，试图就隐私权的内容做一归纳。根据他的整理，法律上的隐私权侵害应包含四种侵权行 为，这四种类型的侵害包括：对他人私生活隐私权的侵害；公开他人的姓名、肖像或揭发其他 不愿为他人所知悉的私人信息；使他人处于人为误解情况；基于商业上的目的，侵犯他人人格。 基于此许多国家对隐私保护问题进行了立法，如美国1 9 7 4 年制定的 隐私权法、澳大利 亚的隐私法、瑞典在1 9 7 3 年制定的数据库法、法国于1 9 7 8 年通过的 数据处理、档案 与自由法案、1 9 8 4 年英国制定的数据保护法、日本于1 9 9 0 年实施的关于保护行政机构 与电子计算机处理有关的个人数据法律、1 9 9 5 年在布鲁塞尔部长级会议上欧盟通过了 个人 数据保护指令，我国宪法、 k 其中q i 表示一条元组在q i 属性上的值，c o u n t ( q i ) 为值序列q i 在t q 1 d p 出现的次数，即t 的每个等价组中至少包含k 条元组。 私有表泛化表 a 铲 s e xz i p c o d ed i s e a s e 5m1 2 0 0 0g a s 拉i cu l o e r 9m1 4 0 0 0 d y s p e p s i a 6ml8 0 p n e u m o n i a 8m1 9 0 0 0b r o n c h i t i s 1 2m2 2 0 0 0 p n e u m o n i a 1 9m2 4 0 0 d p n e u m o n i a 2 lf5 8 0 0 0f l u 2 6f3 6 0 g a s t r i t i s 2 8f3 7 0 0 0 p n e u m o n i a 5 6f3 3 0 0 0f l u ，r、i a g e s e x z i p e o d e d i s 姐s e 【l ，l o 】 m 1 0 0 0 1 ，1 5 0 0 0 】 g a s t r i cu l c e r 【l ，l o 】 m 1 0 0 0 1 ，1 5 0 0 0 】 d y s p e p s i a 【l ，l o 】 m 1 5 0 0 1 ，2 0 0 0 0 】 p n e u m o n i a 【l ，l o 】 m 1 5 0 0 1 ，2 0 0 0 0 】b r o n c h i t i s 【1 1 ，2 0 m 2 0 0 0 1 ，2 5 0 0 0 】 p n e u m o n i a 【l 】，2 0 m1 2 0 0 0 l ，2 5 0 0 0 1p n e u m o n i a 【2 1 ，6 0 】 f 3 0 0 0 0 , 6 0 0 0 0 】 f l u 2 1 ，6 0 f 3 0 0 0 0 ，6 0 0 0 0 】g a s t r i t i s 2 1 ，6 0 f 【3 0 0 0 0 , 6 0 0 0 0 】p n e u m o n i a 2 1 ，6 0 f 3 0 0 0 0 , 6 0 0 0 0 】 f l u 图2 3 基于泛化技术的k _ 匿名示例图 图2 3 为基于泛化技术的k 匿名方法的示例，设定私有表中属性d i s e a s e 的值为敏感信息， 取( a g e ，s e x ，z i p c o d e ) 为准标识符。经过泛化，私有表中的a g e 属性值被替换成区间【1 ，1 0 】、 1 1 ，2 0 、 【2 1 ，6 0 ，z i p c o d e 值也被替换为数值区间，泛化表中形成4 个等价组，每组中都包含了至少2 条记录，因此满足2 匿名性质。在得到满足k 匿名的泛化表和已知攻击目标的准标识符信息的 前提下，攻击者根据目标的q i 属性值只能将其锁定在某个等价组中，那么，攻击者猜测到目 标个体隐私信息的概率p 1 k ，图2 3 示例中的攻击成功率则不大于1 2 。可见，当k 取值越大， k - 匿名的隐私性越高，保护力度也越强。 2 3 2 2k 匿名算法 k - 匿名自提出以来，得到了学术界的普遍关注，国内外很多学者都从不同层面研究和发展 了该技术。文献伫习证明了求解最优k - 匿名是n p 难问题，因此大部分k - 匿名算法都是进行局部 最优或采用启发方法。其中以kl e f e v r e 和r a g h ur a m a k r i s h n a n 等人提出的i n c o g n i t o 4 和 m o n d r i a n s l 为比较经典的k - 匿名算法。 ( 1 ) i n c o g n i t o 算法 i n c o g n i t o 是一种广泛应用的k 匿名算法，能够产生给定表的所有可能的k 匿名全域泛化 ( 一种全局重编码技术) 。算法首先检查q i 属性中的单属性子集是否满足k - 匿名，然后迭代地 检查q i 属性的多维属性子集，每次迭代，用于检查的属性子集宽度增加l 。迭代过程包含两个 主要的部分：寻找k 匿名泛化点、候选点和边的生成。 每轮迭代从一个由若干候选多属性泛化模式构成的图开始。第i 次迭代的泛化模式由若 8 个等价组 、lrj、，j1_jirj 南京航空航天大学硕士学位论文 千宽度为i - l 的q i 属性集生成，记作c i ；图中表示直接泛化关系的连接边的集合记作e i 。算法 对图中的候选点进行宽度优先搜索，通过判断原始表在候选点上是否满足k _ 匿名，筛选出宽度 为i 的多属性泛化模式，记作s i 。 算法从s i 生成宽度为i + l 的候选点集c i + l 和直接泛化连接边e i + 1 。i n c o g n i t o 的第i 轮 迭代使用一种经过改进的自底向上的宽度优先搜索搜索来判断原始表t 在候选泛化模式集c i 上的k 匿名状态。搜索开始于候选泛化图中没有边指向的“根”节点，基于“上卷性质 ，算 法通过自底向上地集成来得到各点上的元组计数。这种宽度优先搜索同时也是基于“泛化性质” 的，如果原始表在某点上是k - 匿名的，则该点的所有有连接的上层点也能使表满足k 匿名。因 此，当搜索算法发现匿名点，就将其直接泛化点做标记，并且后面的计算中不再予以考虑。这 里的上卷性质、泛化性质以及下文提到的子集性质将会在第三章中具体阐述。 泛化图的生成分为三个步骤。对于点集，首先将上轮迭代的匿名点集s i 1 进行自连接，得 到候选点集c i 的一个超集c i ，自连接过程可用s q l 语句表示f 4 】： 然后，根据“子集性质”，剪除c i 中存在子集不属于s i 1 的点及其连接边，得到c i ，即有 可能使原始表达到匿名的点集。最后，由c i 和e i 1 生成c i 的边集e i ，可用s q l 语句表示为【4 】： i n c o g n i t o 算法的优势在于1 ) 用带有层次结构的图来表示泛化模式的集合，分析得出不同 9 数据发布中隐私保护关键技术的研究 层模式之间所对应的元组数目的关系，只要在根节点上读取原始表数据，其它节点对应的元组 数目则通过自底向上地集成来计算，避免了为统计数据而频繁地进行i o 操作；2 ) 采用连接、 剪枝技术来生成新一轮循环的泛化图，将一部分肯定不满足条件的泛化模式在进行处理前就先 行剔除，从而减小待处理的泛化图规模。与此之前的一些k 匿名算法相比，i n c o g n i t o 在算法效 率上的优越性是比较明显的。 ( 2 ) m o n d r i a n 算法 文献【5 j 提出了多维k _ 匿名的概念，根据k d - t r e e 的分割方法提出了m o n d r i a n 算法，该方法 允许同一时刻在多维类身份属性上进行泛化处理。多维k _ 匿名从全局泛化( g l o b a lr e c o d i n g ) 和 局部泛化( 1 0 c a lr e c o d i n g ) 的角度归纳出两种多维划分模型严格多维划分和宽松多维划分。 这两种模型用d 维空间来表示准标识符属性x l ，x 2 ，x d ，将每条元组根据各属性值映射为多 维空间的一个点，因此一张表就是一个点集。 与单维划分对各属性的域分别作划分不同，多维划分模型将所有属性域作为一个整体进行 分割。严格多维划分在各属性域的笛卡尔积d x t d x a 上定义一个划分，也就是把多维空间 分割为多个互不重叠的区域，并将数据点映射为它们所在的那个子空间。宽松多维划分则是在 d x t d x a 上定义互不相同的多维区域，可以有重叠，并将每个数据点映射为它所在区域中 的一个。如图2 4 是单维划分、严格多维划分和宽松多维划分的一个示例。 笛 2 7 翘 5 钾 05 盯1 15 3 7 1 2 囝囝 囝 国 国 s i n g l e d i m e n s i o n a l s t r i c t - m u l t i d i m e n s i o n a lr e l a x e d m u l t i d i m e n s i o n a l 图2 4 单维划分、严格多维划分和宽松多维划分 2 3 2 3k 匿名算法的一些问题 包括i n c o g n i t o 在内的一些k 匿名算法在时间效率上获得较好的效果，却忽视了发布数据泛 化的另一个重要问题进行泛化前并不对表中数据的状态或分布情况进行分析，也未对泛化 结构做任何说明，这就有可能导致当数据呈现一定的分布规律时，产生不必要的泛化过程，从 而降低发布后数据的可用性。甚至严重的情况下可能会使泛化后数据的信息量完全丢失。因此， 本文第三章以经典算法i n c o g n i t o 为例，从数据质量的角度提出对于i n c o g n i t o 算法的改进，具 体内容在此不再赘述。 2 3 3 其他匿名策略 k - 匿名泛化策略因其思想简明易了和广泛的适用性一直广受研究者的关注，但它也并不是 1 0 南京航空航天大学硕士学位论文 完美无缺的，在某些特定的情景下，对于某些特定的数据，k 匿名也会存在一些漏洞。于是研 究者们又在k - 匿名的基础上提出各种其它的匿名策略，如l l i v e r s i t y 匿名1 6 1 、t - c l o s e n e s s 匿名 7 1 、 个性化匿名1 8 】等。 ( 1 ) - d i v e r s i t y 匿名 - d i v e r s i t y 的提出来源于k - 匿名在某些情形下的不足，l 【- 匿名策略在产生等价组，进行元组 计数时仅判断准标识符属性的值，而不考虑隐私属性的值是什么状态。一种可能的情形如图2 5 所示，表被泛化后每个等价组均包含4 条元组，因此满足4 匿名。但是最后一组的4 条记录拥 有相同的隐私属性值，那么对于b o b 其人( 邮编1 3 0 6 8 ，3 5 岁，国籍a m e r i c a n ) ，若攻击者已 知b o b 的这些信息，便仍然可以从右表中推断出b o b 患的是癌症。这种攻击类型被称作同质攻 击( h o m o g e n e i t y a t t a c k ) o l 。 准标识符属性隐私属性 准标识符属性隐私属性 z l pa g e n a t i o nc o n d i t i o n 1 3 0 5 3 2 8r u s s i a nh e a r td i s e a s e 1 3 0 6 82 9a m e r i c a nh e a r td i s e a s e 1 3 0 6 82 1 j a p a n e s e 蹦i n f e c t i o n 1 3 0 5 32 3a m e r i c a n删i n f e c t i o n 1 3 0 5 33 1a m e r i c a nc a n o b r 1 3 0 5 33 7i n d i a nc a _ r l c e r 1 3 0 6 83 6 j a p a n e s e c a n c e r 1 3 0 6 83 5a m e r i c a nc a n c e r z i pa g e n a t i o n c o n d i t i o n 1 3 0 * 3 0 毒 h e a r td i s e a s e 1 3 0 * 3 0 h e a r td i s e a s e 1 3 0 * 3 0 v i r a li n f e c t i o n ： 1 3 0 * l o g ，那么所发布的数据满足 基于熵的- d i v e r s i t y 。其中，等价组的熵定义为 。 e n l o p y ( e ) f f i p 但，s ) l o g p ( e ，s ) s e $ p 饵，s ) 为等价组e 中敏感属性值为s 的记录的百分比。熵越大，表示等价组的敏感属性值分布 越均匀，攻击者揭露个人的隐私就越困难。基于熵的- d i v e r s i t y 具有比简单- d i v e r s i t y 更强的保 护力。但另一方面，m a c h a n a v a j j h a l a 已证明，为了使每个等价组都满足基于熵的- d i v e r s i t y ，必 须保证整张表的熵大于或等于l o g ( 2 ) 。对于少部分值频繁出现的数据表，其熵值通常会比较低。 l l 数据发布中隐私保护关键技术的研究 那么熵值至少为l o g ( 0 的要求就可能过于严格，导致某些匿名问题无解。 递归( c ，) - d i v e r s i t y 。如果每个等价组都满足功 c ( r t + r t + l + ”卜r m ) ，那么就说所发布 的数据满足递归( c ，i f ) 刁i v e 璐时。这里，m 表示等价组中不同值的数目，r i ( 1 i m ) 表示该等价 组中第i 频繁的敏感属性值的个数。递归( c ，) - d i v e r s i t y 与基于熵的厶d i v e 璐时相比是一种相对 保守的方法，它保证了等价组中频率最高的敏感属性值不至于出现频度太高，频率最低的值不 至于出现频度太少。 采用- d i v e r s i t y 策略的一个例子是肖小奎等人提出的基于分解技术的a n a t o m y 算法【1 6 】。分 解方法与泛化不同，它不对准标识符属性值做任何修改，而是将准标识符属性和敏感属性拆分 到两个表中以切断两者之间的联系。 a n a t o m y 算法首先初始化两个空表，分别称作准标识符表q r r 和隐私表s t ，将原始表的 记录按敏感属性值分别装入a s 桶中，使每个桶包含敏感属性值相同的记录。然后，算法通过创 建等价组、剩余记录分配两步对原始表做一个- d i v e r s i t y 的划分。最后按- d i v e r s i t y 划分出的等 价组进行表拆分，将原始表t ( ”l ，a q 2 ，”d ，a s ) 拆分为准标识符表q r r ( a q l ，a q z ，a q d ， g r o u p i d ) 和隐私表s t ( g r o u p i d ，a 8 ，c o u n t ) 。a n a t o m y 算法示例如图2 6 。 t q r r a g e s e x z i p d i s e a s e 2 3m1 1 0 0 0 p n e u m o n i a 2 7m1 3 0 0 0 d y s p e p s i a 3 5m5 9 0 0 0 d y s p e p s i a 5 9m1 2 0 0 0 p n e u m o n i a 6 1f5 4 0 0 0f l u 6 5f2 5 0 0 0 g a s t r i t i s 6 8f2 5 0 0 0 f l u 7 0f3 0 0 0 0b r o n c h i t i s 分解 _ a g e s e x z l p g i d 2 3ml l o o ol 2 7m1 3 0 0 0l 3 5m5 9 0 0 0 l 5 9m1 2 0 0 0l 6 1 f5 4 0 0 0 2 6 5f2 5 0 0 02 6 8f2 5 0 0 02 7 0f3 0 0 0 02 g i d d i s e a s e c o u n t 1 d y s p e p s i a 2 1 p n e u m o n i a 2 2b r o n c h i t i sl 2 f l u2 2 g a s t r i t i s 1 图2 6a n a t o m y 匿名示例 ( 2 ) t - c l o s e n e s s 匿名 t - c l o s e n e s s 在l - d i v e r s i t y 的基础上，考虑了敏感属性的分布问题，它要求所有等价组中敏感 属性值的分布尽量接近该属性的全局分布【刀。 t - c l o s e n e s s 的定义为，令p = p i ，p 2 ，p m ，q i = q 1 ，q 2 ，q m 分别表示各敏感值的全局 分布和在等价组c i 中的分布。对任意等价组c i ，若p 与q i 的距离d 【p q i 】满足d 【p ，q i 】 t ， 则发布的数据满足匿名化原则t - c l o s e n e s s 。其中，阈值t e o ，1 】；度量距离可采用可变距离 。【p q i 】2 喜丢i p i - q i l或kl距离d吸qi】=喜pmg万pii-i o 扭1q ( 3 ) 个性化匿名 南京航空航天大学硕士学位