（计算机软件与理论专业论文）基于概率数据库技术的视图发布安全的研究.pdf

摘要 摘要 随着数据库技术的发展，数据交换次数和交换数量不断增多，视图发 布过程中所存在的信息泄漏的问题日渐突出。因此，保证发布视图的安全 成为数据库安全的一个新课题。本文对国内外关于视图发布过程中安全问 题的研究现状进行了综合分析，重点对发布视图的安全性判定进行了研究。 首先，分析了多方共谋、信息推理等不同的攻击方式，并详细地介绍 了目前经常采用的保护隐私数据方法，其中包括查询限制、噪音添加、数 据交换、k - 匿名模型等等。在此基础上对现有的检测视图发布安全性方法 进行了分析，指出了它们的优缺点。 其次，基于以上的研究成果，本文建立了一个视图安全性判定模型， 以布尔查询的形式表示发布视图和隐私信息，并给出了发布视图、隐私信 息、先验知识等的形式化定义，并在此基础上提出了一个新的基于熵的判 定定理。 再次，根据视图安全性判定模型和视图安全性判定定理，提出了基于 熵的视图安全性判定算法和基于渐近性条件概率的视图安全性判定算法， 避免了多视图安全性判定过程中的n p 完全问题，并对这两种算法进行了正 确性和可行性证明。 最后，通过实验对上述两种算法的正确性和可行性进行了验证，并从 测量精度、空间复杂度和时间复杂度等方面对它们进行了比较，分析了这 两种方法的优缺点。 关键词视图发布；概率数据库；关联查询；先验知识；熵；信息泄漏 燕山大学工学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t a b a s et e c h n o l o g y , d a t ae x c h a n g ef r e q u e n c y a n dq u a n t i t yi n c r e a s ec o n t i n u a l l y , t h ep r o b l e mo fi n f o r m a t i o nd i s c l o s u r ei s o u t s t a n d i n gd a yb yd a yi nt h ev i e wp u b l i s h i n gp r o c e s s ，s og u a r a n t e e i n gs e c u r i t y o f p u b l i s h e dv i e wb e c o m e s an e w s u b j e c to f d a t a b a s es e c u r i t y t h i sp a p e ra n a l y z e st h ec u r r e n ts i t u a t i o no ft h ed o m e s t i ca n di n t e m a t i o n a l s e c u r i t yp r o b l e mi nv i e wp u b l i s h i n gp r o c e s s ，a n dr e s e a r c h e sf o r t h ep r o b l e mo f s e c u r i t yd e c i d i n go f v i e w s a tf i r s t ，b y i n t r o d u c i n g s e v e r a ld i f f e r e n ta t t a c km e t h o d s ，s u c ha s m u l t i p a r t y c o l l u s i o na n di n f o r m a t i o ni n f e r e n c e ，a n dt h ew a y st op r o t e c t s e n s i t i v ed a t ai si n t r o d u c e di n d e t a i l ，i n c l u d i n gq u e r y r e t r i c t i o n , d a t a p e r t u r b a t i o n , d a ms w a p p i n ga n dk a n o n y m i t yp r o t e c t i o nm o d e le t c ，i ta n a l y z e s t h ee x i s t i n gm e t h o do fs e c u r i t yd e c i d i n go f v i e w s s e c o n d l y ，o nt h eb a s i so ft h ea b o v er e s e a r c h , ap r o b a b i l i t ym o d e lo f s e c u r i t yd e c i d i n gi np u b l i s h i n gv i e w si s e r e c t e d i nt h i sm o d e l ，p u b l i s h i n g v i e w sa n ds e n s i t i v ei n f o r m a t i o na l ee x p r e s s e db yb o o l e a nq u e r y t h e nt h e f o r m u l a l i z e dd e f i n i t i o no fp u b l i s h i n g v i e w s ，p r i v a t ei n f o r m a t i o n , p r i o r k n o w l e d g ei sg i v e n , a n d an e w d e c i d i n gt h e o r e mb a s e do ne n t r o p yi sp r o v i d e d m o r e o v e r , a c c o r d i n gt ot h e a b o v em o d e la n dd e c i d i n gt h e o r e m , t h e a l g o r i t h mo fs e c u r i t yd e c i d i n go f v i e w sb a s e do ne n t r o p ya n dt h ea l g o r i t h mo f s e c u r i t yd e c i d i n go fv i e w sb a s e do na s y m p t o t i cc o n d i t i o n a lp r o b a b i l i t i e sa l e i n t r o d u c e d 。t h e yb o t hs o l v et h en p c o m p l e t ep r o b l e mi nd e c i d i n gs e c u r i t yo f m u l t i - v i e w s f i n a l l y , t h et w oa l g o r i t h m s w em e n t i o n e da b o v ea l ec e r t i f i e db y e x p e r i m e n t t h e ya l ec o m p a r e di nm e a s u r ep r e c i s i o na n do v e r h e a df o rt i m e a n ds p a c e a b s w a e t k e y w o r d sp u b l i s h i n gv i e w s ；p r o b a b i l i s t i cd a t a b a s e ；c o n j u n c t i v eq u e r y ；p r i o r k n o w l e d g e ；e n t r o p y ；i n f o r m a t i o nd i s c l o s u r e m 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于正交图像的人脸建 模技术研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他 人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和 集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字雏，甲日期：加。年罗月移日 燕山大学硕士学位论文使用授权书 基于正交图像的人脸建模技术研究系本人在燕山大学攻读硕士学 位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学 所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完 全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕 山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的 全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囱。 ( 请在以上相应方框内打“”) 日期：矽。6 年7 月站日 日期：加6 年r 月莎日 女丫 i k m j 玎斫 i 乒l i i 莎 名 名 签 签 者 师 作 导 第1 章绪论 1 1 研究背景 第1 章绪论 随着社会信息化发展的不断深入，特别是i n t e m e t 的飞速发展，使得 数字化信息已经渗透到世界的各个角落。数据库作为信息系统的核心技术 得到了越来越多的关注，其中数据的安全发布成为数据库安全理论的研究 热点。目前随着防火墙技术、“物理隔离”系统【啦】的不断发展，在物理层 面上发布数据的安全性是可以保证的。也就是说，在一定范围内人们能够 使得数据安全地到达授权方。 在逻辑层面上，数据的安全发布问题涉及到统计数据库( s t a t i s t i c a ld a t a b a s e s ) e 3 一，数据加密嘶1 等很多领域。人们很早就对它进行了分析和研究， 但是随着近几年数据共掣7 】、数据挖掘技术( d a t am i n i n g ) 8 , 9 1 的迅速发展， 这一领域的研究正在面临着巨大的挑战，它将会成为社会信息化发展的一 个瓶颈，阻碍社会信息化的发展。 视图是数据库发布数据的重要手段【l o 】。数据库可以针对不同的用户制 定不同的视图，通过用户视图中不包括敏感数据的手段来保证数据安全发 布。这样既满足了数据交换和数据共享的目的，又保护了数据库中的敏感 数据。近几年查询重写技术 1 l , 1 2 的发展，使得视图发布者经常会无意识地 造成敏感数据的泄漏。因而数据库方有必要在发布数据之前对数据进行安 全性分析。 统计数据库技术在满足统计信息要求的同时，能够很好的屏蔽个人信 息，保护敏感数据【1 3 q 5 1 。该领域已经有很长的发展历史了，早在1 9 7 9 年 d d o b k i n 等人就对攻击者由统计数据推理出敏感数据而导致信息泄漏的 情况进行了分析【l6 1 。文献【1 7 】中已经证明单从统计数据库角度出发，依靠 统计量来屏蔽敏感数据是不能对安全的数据发布提供保证的。 8 0 年代随着数据库中知识发现( k n o w l e d g ed i s c o v e ri nd a t a b a s e ) ，又称 燕山大学工学硕士学位论文 数据挖掘的出现 1 8 , t9 】，人们能够从浩如烟海的数据中提取出一些有用的知 识，产生了数据的二次利用。如果私有信息得不到保护，数据库作为第三 方就不能得到用户的信任，那么用户将不会提供正确的个人信息，这必将 阻碍数据共享、数据挖掘等技术的发展【2 们。因此数据库中数据安全发布问 题有了新的挑战。 本文研究的问题就是在这一背景下提出的。本文分析了几种不同攻击 方式，这些攻击方式会在不同程度上导致敏感数据的泄漏。在此基础之上， 深入地研究了数据发布的安全性。这一研究有助于促进数据交换、数据共 享技术的发展，满足了信息时代的需求。 1 2 国内外研究现状 在逻辑层面分析数据发布的安全问题，有着重要的研究意义和应用价 值，在这方面的的研究已经取得了一定的成果。 2 0 0 1 年，在v l d b ( v e r yl a r g ed a t ab a s e s ) 会议上，a h a l e v y 提出“查 询应答法”判定数据发布安全性【l ”。“查询应答法”是将秘密查询s 作用 在视图组v 上，如果能够得到秘密查询s 的结果，那么就可以认为视图组 的发布是不安全的。也就是说这个方法主要是对视图组v 中是否存在查询 s 的结果进行判定。这种方法不能检测出私有信息的部分泄漏。例如私有 信息个数的泄漏。同时，对于“推理”而导致的信息泄漏问题，此判定方 法也显得无能为力。 2 0 0 2 年，l s w e e n e y 提出了一种用来保护私有信息的k 匿名模型【2 n 。 此解决办法就是找出数据持有者能够识别的可以与外部信息相连接的私有 信息全部关键属性( 准标识符) ，禁止通过这些属性将释放信息与外部信息 连接在一起。若此种情况无法避免，那么k 匿名保护模型就会通过“泛化 法”和“抑制法”0 3 1 对要发布的视图作相应的处理，使其满足k 匿名， 再对视图进行发布。这种基于k - 匿名保护模型的方法，没有考虑到数据的 动态收集特性阱】，以及元组的动态添加、删除、改变和移动特征，一旦要 进行动态的添加、删除或改变元组，就需要对要发布视图的安全性进行重 2 第1 章绪论 新判定【2 5 2 6 1 。此外，这个方法也没有分析视图组发布数据的安全性问题。 2 0 0 2 年，在v l d b 会议上，s j r i z v i 和j r h a x i t s a 提出了利用对私有 信息的恢复率来判定数据发布安全性1 2 ”。这一方法经常应用于数据挖掘中 对私有信息的保持技术中。这个判定定理不但定量的分析了数据发布的安 全性，而且还利用数据干扰法对私有信息提供保护。但是它仍然不能判定 发布过程中私有信息的部分泄漏。 2 0 0 3 年，在p o d s ( p r i n c i p l e so f d a t a b a s es y s t e m s ) 会议上，i d i n u r 等人 提出了一种t 时间限制内判定数据发布安全性的方法【2 9 】。对统计数据库进 行了概率建模。首先在输入时利用数据干扰的方法处理私有信息，然后根 据“干扰度”判定统计数据库中的信息泄漏问题。这个判定主要是针对数 据干扰后的私有信息，而对于发布者无意识产生的私有信息的泄漏是不能 判定的。 2 0 0 4 年，在s i g m o d ( s p e c i a li n t e r e s tg r o u p o l lm a n a g e m e n to f d a t a ) 会 议上，g m i k l a u 和d s u c i u 提出了基于概率模型的方法判定数据发布安全 性1 2 9 1 。它提出了一个安全模型，在逻辑层面上分析了两种数据交换场景下 数据交换的不安全性。在此基础上提出了概率模型的方法判定数据发布安 全性，定量的分析了信息的泄漏。这种判定方法对安全性要求过于苛刻， 在实际情况中不能很好的应用。往往在现实生活中可以接受的泄漏，却不 能通过这个判定算法。另外上述的安全模型过于庞大，不但增大相应判定 算法的时间复杂度，而且降低了测量的精度。 2 0 0 5 年，在i c d t ( i n t e r n a t i o n a lc o n f e r e n c eo nd a t a b a s et h c r o y ) 会议上， n d a l v i 等人提出了用渐近条件概率的方法来判定数据发布安全性【3 0 1 ，即 随着域值d 的大小n 逐渐增大，利用l i m n 专j s l v 的值变化来判定数据发 布的安全性。如果l i m n j s l v = o 那么就认为数据发布安全。如果 l i m 。_ 。p s l v o 那么就认为这一信息泄漏是不能忽略的。为了实现此判定 算法，n d a l v i 等人还对关联查询的概率计算进行了详细地分析，给出了在 n 趋向于无穷时计算关联查询概率的算法。解决了用概率学知识判定数据 发布安全性的关键问题。然而在较小的n 的范围内，这一方法是不可行的， 在测量精度方面不能达到需求。同时随着数据挖掘技术的应用，这种判定 3 燕山大学工学硕士学位论文 方法的缺陷更加明显。 1 3 研究内容 本文分析了在逻辑层面上产生信息泄漏的几种形式，其中包括：串谋、 存在先验知识下的推理、属性间的依赖关系等。在此基础上，改进了原有 的判定定理，根据具体情况提出了相应的判定规则。以下对本文的研究内 容进行简单的介绍。 对g m i l d a u 和d s u c i u 提出的安全模型进行改进。在原模型的基础上 考虑攻击者的先验知识及数据项之间的关联关系，建立新的安全模型。 本文提出了基于渐近性条件概率的视图安全性判定算法。这个算法与 原有的算法比较最明显的优势就是有着较少的时间消耗。通过布尔查询表 示发布视图和隐私信息简化了计算过程。另外，这个算法通过分解关联布 尔查询，建立新查询来解决关联布尔查询概率计算中的n p 完全问题。 此外，本文提出了一个新的视图安全性判定算法，基于熵的视图安全 性判定算法。改进原有的条件概率的判定方法，提高泄漏测量的精度。结 合实际的数据交换场景，和数据发布的安全性判定定理，提出相应的判定 算法。另外该算法简化了关联查询概率的计算，从视图结构角度分析，提 出了利用合并视图法求解关联查询概率的算法。 1 4 研究意义 数据发布过程中私有信息泄漏的研究，是数据库安全领域的研究热点， 影响着数据交换、数据共享、数据挖掘等其他领域的发展【3 i 】。逻辑层面上 私有信息泄漏的研究有着重要的理论意义和实际应用价值。 本文改进了原有的安全模型，不仅拓宽了模型的应用范围，还在简化 模型的基础上减小了安全性判定算法的时间和空间复杂度。另外提出了两 种可行的判定发布视图安全性的算法。根据这个模型提出了数据发布的安 全性判定定理，提高了信息泄漏量的测量精度。本文提出的在逻辑层面判 4 第1 章绪论 定数据发布安全性技术具有十分广泛的应用前景，为信息安全理论的研究 奠定了坚实的基础。 1 5 本文组织结构 本文总体上分为5 章，各章具体布局及内容如下 第2 章主要介绍了产生信息泄漏的几种形式、目前现有的判定安全性 方法和消除信息泄漏技术。 第3 章主要研究了安全模型的改进。首先缩小数据域d ，针对要发布 的数据进行建模。其次，为了更好考虑攻击者所知的先验知识k ，数据库 实例i i 应满足：对于任意i = l ，2 ，n ，使k c i i 。最后详细的分析了视图安 全性判定算法的输入模块。 第4 章主要研究了判定发布视图安全性的判定方法。首先在给定安全 模型的基础上，提出了判定发布视图安全性的判定定理，然后提出了两种 可行的视图安全性判定算法。 第5 章主要是对前面所提出的理论进行了实验验证，并对实验结果进 行分析。 最后，总结了本文的工作并提出了下一步设想。 燕山大学工学硕士学位论文 2 1引言 第2 章基础知识 要想在逻辑层面上判定数据发布的安全性，不仅要考虑到攻击者常用 的几种不同的攻击方式，还要明确地了解数据发布者采用的保护数据的方 法。只有综合考虑了这两个因素，才能得到有效的判定方法。本章详细分 析了各种不同的攻击方式和目前经常采用的保护隐私数据的方法，在此基 础上介绍了现有的几种判定数据发布安全性的方法。 2 2 攻击方式 攻击者可以根据多个视图联合或者分析视图结构等方式来获取有用信 息，然后利用这些信息对视图中的隐私信息进行攻击。我们称将多个发布 视图联合起来或者多个拥有不同视图权限的合作者联合起来，进行获取隐 私信息的行为叫多方共谋或者叫“串谋”。 通常会造成信息泄漏的结构信息有：视图中元组的顺序，属性的顺序， 属性的个数以及视图组的关联关系等。假设视图的结构信息有n 种，那么， 就可能有2 - 1 种信息泄漏的方式。 2 2 1多方共谋 多方共谋也称“串谋”，即多个合作者联合起来去攻击数据拥有者的隐 私信息。通常我们将多方共谋分为两类：第一类是多个合作者有权限去交 换数据以便获取更多的信息。一个简单的例子，s w e e n e y 证明了当他查找 w i l l i 锄w e l d 个人的特权医疗信息时，仅仅通过连接w e l d 所在州的投票者 注册信息表( n a m e ，z i p ，s e x ) 和当地保险公司的匿名医疗保险数据( z i p ， b r i t h - d a t e ，m e d i c a l ，d a t a , ) ，就能得到所要的数据【2 ”。这里w e l d 所在州 6 第2 章基础知识 的投票者注册信息和当地保险公司的匿名医疗保险数据都是公开发布给社 会的信息，也就是说s w e e n e y 是有权得到这些数据的。 第二类是合作者并没有权限去得到其他合作者的数据，但是他却通过 非法的途径进行“串谋”攻击获取隐私信息。例如一个公司需要同几个合 作伙伴间交换数据，所采用的方法是发布了若干个关于公司生产信息的动 态视图。假设视图v 1 是面向供应商的( 公司已采取一系列安全手段确保这 个视图仅能被授权的供应商看到) ，它包含有关于某一产品配件的详细信 息，视图v 2 是面向零售商和顾客的( 公司已采取一系列安全手段确保这个 视图仅能被授权的零售商和顾客看到) ，它包含有关于产品特性和价格等方 面的详细信息，视图v 3 是面向税务代理公司的( 公司已采取一系列安全手 段确保这个视图仅能被授权的税务代理公司看到) ，它包含有关劳动力成本 方面的信息。作为商业机密，公司不想让外界知道自己产品的生产成本。 但如果有人能够同时从供应商和税务代理公司得到这个公司的信息并把他 们组合到一起，那么这个公司产品的生产成本就会被计算出来，这样就造 成了商业机密的泄漏。 为了具体说明这个问题，我们用d a t a l o g 语言来描述某一个学校研究 生的学号、导师姓名以及该学生联系电话的基本关系表，s t u d e n t ( i d 。t u t o r , p h o n e ) 。基于该s t u d e n t 关系表之上，发布两个视图v l ( i d ，t u t o r ) ，v 2 ( t u t o r , p h o n e ) ，如果独立发布这两个视图，则视图均是安全的。假设此时敏感信 息为s t u d e n t ( “0 1 1 1 ”， j o l i n ，“1 3 7 ”) ，如果我们将连接查询作用在独立 的视图上，即s e l e g tv 1 斌v 2 t u t o r , v 2 p h o n ef r o mv ii o i nv 2o nv 1 t u t o r = v 2 t u o t r = j o l i n 同时假设i o l i n 仅带了五个学生的话，且每个学生仅有一个电 话号码，那么我们可以正确获取敏感信息的概率为2 0 。这种信息泄漏是 由视图组构造得不合理而造成的。 互联网技术的发展为多用户合作提供了方便，但却使得隐私信息的安 全面临着更大的挑战1 3 2 3 5 1 。例如在i n t e m e t 上进行选举不仅要保证所有的 投票者都是合法的投票者，还要保证投票者在不拥有其它投票者投票信息 的情况下独立地去投票，除此之外还满足统计者在统计投票数的过程中， 不能揭示任何秘密信息。另外，考虑联合解密过程也是一个典型的多方共 燕山大学工学硕士学位论文 谋计算秘密信息问题：当用户作为参与者，想要去解密一些信息。这个类 似于分裂式密钥托管( s p l i tk e ye s c r o w ) ，也就是政府的担保人有着每一个 人的解密密钥，当且仅当把他们的信息联合起来时，才能够解密得到用户 的隐私数据。 除此之外，分析多方共谋过程中秘密信息的安全性还是一个动态的过 程，通常数据持有者往往会发布不同的数据给同一个用户，假设数据持有 者想要发布视图v 给一个用户，考虑到在过去已经发布了一个视图u 给这 个用户，并且确定视图u 对秘密信息已有所泄漏，那么数据持有者就需要 去限定视图v 不能在u 的基础上泄漏更多的秘密信息。 2 2 2 信息推理 攻击者可以在没有得到隐私信息的情况下，通过非隐私信息和隐私信 息之间的关系来推理得到隐私信息。主要包括视图结构推理，背景知识推 理，先验视图推理这几种。以下分别举例介绍这几种不同的信息推理过程。 由于发布视图的结构信息而导致信息泄漏的情况有很多种，下面通过 例2 1 来说明其中一种由于结构信息推理所造成的信息泄漏问题。 例2 1 ：如表2 - 1 所示，某公司员工的基本信息表，其中包括员工的i d 号、职业、基本工资、奖金。 表2 - 1 员工工资基本信息表 t a b l e2 - 1i n f o r m a t i o no f w a g eo f p e o p l e 序号 i d职业 基本工瓷奖金 1 z 1 0 0 l领班25 0 0l0 0 0 2 z 1 0 0 2 厨师34 0 0 l5 0 0 3z 1 0 0 3面点工2 0 0 05 0 0 4z 2 0 0 1服务员l5 0 04 0 0 5z 2 0 0 2服务员l5 0 0 6 0 0 6z 3 0 0 l出纳l5 0 0 5 0 0 z 1 0 0 2 领班 25 0 0l4 0 0 用户1 可能需要其中的部分信息，比如用户需要了解这个公司员工的 8 第2 章基础知识 工资、奖金标准，那么做为该公司的数据库管理人员就会提供给用户1 一 个如表2 2 所示的视图。其中包括加密后的员工i d 号、员工的职业信息、 基本工资信息和奖金获取情况。 表2 - 2 提供给用户1 的视图 1 h b l e2 2v i e wf o ru s e r l 序号 i d 职业基本工资奖金 1z 1 0 0 领班 25 0 0l0 0 0 2z 1 0 0 厨师 3 4 0 0l5 0 0 3z 1 0 0 + 面点工 2 0 0 05 0 0 4z 2 0 0 服务员 l5 0 04 0 0 5z 2 0 0 服务员 l5 0 06 0 0 6 z 3 0 0 出纳 l5 0 05 0 0 7z 1 0 0 领班 25 0 0l4 0 0 另外假如还存在一个用户用户2 ，用户2 需要了解这个公司的员 工d 号和员工职业一个对应关系，那么公司数据库管理人员就会发布表 2 3 所示的视图给用户2 。并且公司数据库管理人员并没有设定这两个表的 权限，也就是说一般用户就可以同时得到这样的两个表。 表2 - 3 提供给用户2 的视图 t a b l e2 3v i e wf o ru s e r 2 序号 i d职业 lz 1 0 0 l领班 2z 1 0 0 2厨师 3z 1 0 0 3面点工 4z 2 0 0 l服务员 5z 2 0 0 2服务员 6z 3 0 0 l出纳 7z l 0 0 2领班 表2 - 2 和表2 3 是基于表2 1 所发布的两个视图，视图中元组的顺序 与基本关系表2 1 中元组的顺序是完全相同的。在视图2 中用户可以得到 9 燕山大学工学硕士学位论文 该公司员工的职业和工资、奖金之间的对应关系，从而了解到这个公司的 工资和奖金的分发的大体情况，在视图3 中可以得到员工和职业的对应关 系。如果在视图2 释放之后释放视图3 ，或是同时释放视图2 和视图3 ，也 就是一个用户同时可以得到视图2 和视图3 ，那么可以看出视图2 的信息 连接上视图3 的信息就能得到每个员工和其相应的工资及奖金。而这个用 户推断出的信息是不应该让任何一个用户获得的，因此这一推断就造成了 信息的窃取。 攻击者可以通过视图多种不同的结构信息对隐私信息进行攻击。以下 将介绍攻击者通过发布视图和视图中元组的个数进行推理，得到获取敏感 信息，从而造成了视图发布的不安全性。 下面通过例2 2 来详细说明这种攻击方式。 例2 2 ：如表2 4 所示，是一间医院关于病人的姓名、性别和已交的医 药费的信息表，保密的信息是属性名为m o n e y 的数据项。 表2 4 某家医院的部分病人的信息 t a b l e2 - 4i n f o r m a t i o no f p a t i e n to f h o s p i t a l 序号n a n l e s e x m o n c y i j i mm 20 0 0 2 l c cm 15 0 0 3砌aw30 0 0 4t o mm48 0 0 5e l l aw20 0 0 6j e r r ymi5 0 0 使用d a t a l o g 语言来描述，基于表2 - 4 的视图可以表示为如下的形式： v ( n a m e ，s e x ) ：- h o s p i t a l ( n a m e ，s e x ，m o n e y ) 。此时我们要保密的信息项是 m o n e y ，即敏感信息通过查询s ( m o n e y ) ：一h o s p i t a l ( n a l t l e ，s e x ，m o n e y ) 给出。 虽然视图发布不会泄漏出具体的信息，但是如果每一个病人存在一项交款 记录的话，我们就可以从视图v 的发布中获得敏感信息的数量，尽管信息 泄漏程度低，但却仍然是不安全的视图发布。 一般情况下，基于元组个数推理的方法不是单独出现的，当此方法和 1 0 第2 章基础知识 具体的实际情况联系在一起，便会造成更大的信息泄漏。如果两个病人接 受的治疗相似的话，那么根据一个病人的情况就有可能推出其他人得信息， 依次推理将造成很严重的隐私信息泄漏。 除了基于结构信息造成的信息泄漏外，通过窃取者了解的背景知识【3 6 】 而导致信息泄漏也是一个经常发生的情况。 背景知识作为先验知识的一部分，它是指从发布视图以外得到的与视 图有关的额外信息，包括常识、某些有用的公共信息。针对单个不同的攻 击者，存在着不同的背景知识。也就是说每个不同的攻击者对发布视图及 其相关信息的掌握情况不同。下面通过例2 3 来说明，由于背景知识与发 布视图联合所导致的信息泄漏。 例2 3 ：我们将表的属性列分为：敏感属性列( s e n s i t i v e a t t r i b u t e s ) 和非 敏感属性列( n o n s e n s i t i v e a t t r i b u t e s ) 。表2 5 给出某医院病人的详细资料。 表2 5 病人微观资料 t 矗b l e2 5p a t i e n tm i c r o d a t a n o n - s e n s i t i v es e r t s i t i v c 序号 z i p c o d e a g e n a t i o n a l i t vc o n d i t i o n 11 3 0 5 32 8r u s s i a nh c a r td i s e a s e 21 3 0 6 82 9a m e r i c a nh c a r td i s e a s e 31 3 0 6 82 1j a o a n e s er a li l l f e c t i o n 41 3 0 5 32 3a m e r i c a nv j m l i n f c c t i o n 51 4 8 5 35 0i n d i a nc a n c e r 61 4 8 5 35 5r u s s i a nh c a r td i s e a s e 71 4 8 5 04 7a m e r i c a nv i m li n f e c t i o n 8 1 4 8 5 04 9 a m e r i c a nv i 脚i n f e c t i o n 9 1 3 0 5 33 l a m e r i c a nc a n c e r l o 1 3 0 5 33 7 i n d i a nc a n c , g f 1 1 1 3 0 6 83 6 j a p a n e s e c a n g e r 1 21 3 0 6 83 5a m e r i c a nc a n g e r 这里，值得声明的是为了不泄漏单个病人的个人信息，在表2 5 中属 燕山大学工学硕士学位论文 性集 z i pc o d e ，a g e ，n a t i o n a l i t y 是需要进行加密处理的数据，所以我们需 要对其进行加密处理后方可发布这个视图。 表2 - 6 是经过处理后可以对外发布的视图。 表2 - 6 处理后的病人微观资料 t a b l e2 - 6w o r k e dp a t i e n tm i c r o d a t a n o n s e n s i t i v es e n s i t i v e 序号 z i p c o d ea g e n a t i o n a l i t y c o n d i t i o n l1 3 0 * 3 0h e a r t d i s e a s c 21 3 0 * 3 0h c a r td i s e a s e 31 3 0 * 4 0h c a r td i s e a s e 71 4 8 5 4 0v i r a li n f e c t i o n 81 4 8 5 4 0 m lm f c c t i o n 9 1 3 0 * 3 c a r l c c l 1 01 3 0 * 3 + c a n c e t 1 1 1 3 0 *3 c a n c e l 1 21 3 0 3 c a r l c c t 当我们进行了如表2 - 6 的处理后，单单通过发布的视图是不能得到单 个病人的个人信息的。 假设作为攻击者a l i c e 有一个朋友u m e k o ，a l i c e 知道他的记录在表 2 - 6 中，作为u m e k o 的朋友，a l i c e 能够知道u m e k o 是一个2 1 岁的日本女 性，目前居住地的地区编号即z i pc o d e 为1 3 0 6 8 。这样根据这些信息，a l i c e 就确定了u m e k o 的信息就被包含在记录1 、2 、3 或者4 当中。众所周知日 本有很低的心脏病( h e a r td i s e a s e ) 发病率，所以a l i c e 就可以确定记录( 2 ， 1 3 0 6 8 ，2 1 ，j a p a n e s e ，v i r a li n f e c t i o n ) 是u m e k o 的个人记录。这样a l i c e 就知 道u m e k o 得的是病毒性感染( v i r a li n f e c t i o n ) 。通过上述叙述，我们就可以 看出仅仅通过背景知识“日本有很低的心脏病发病率”，作为u m e k o 的朋 1 2 第2 章基础知识 友就能够获取她的隐私信息。 2 3 不同的防攻击的解决方法 查询限制提供一些问题的确切答案，但对一些可能造成数据库缺陷的 问题拒绝回答，因此发布信息的统计质量比较高1 3 6 但是这些方法通常是 过分限制的，在面对有经验的用户时不起作用。用于数据挖掘时，查询限 制方法可能会否定一些非常重要的信息和模糊的一般模式。该方法可以提 供严格限制的数据集而不被数据挖掘者所利用，但这已经受到批评。首先， 为什么一个挖掘者会希望得到或查询没有价值的数据；其次，唯一保证数 据集真正不包含模式的方法是将他们都找出来，而这需要花费很大的功夫： 再次，为了使该方法可行，必须假设每个挖掘者将不会跟其他挖掘者合作。 既然查询限制的目的不是为了最大化可回答的问题的数目，而是回答所有 或大部分重要的问题，分配是可能的方法，这要求在重要性的基础上将记 录分为不同的组，可以通过模糊集理论来进行区分。 噪音添加方法通过引入一个数据或查询结果的误差来阻止缺陷【3 ”。这 些方法是稳健的并能够对所有查询提供答案，但牺牲了部分信息的暴露或 提供统计质量有所缺失的信息。o l e a r y 认为噪音添加本身对于那些对噪音 非常敏感的数据挖掘技能非常有用。特别是当一个概率分布数据的干扰方 法被称为是数据交换时，看起来对数据挖掘的隐私保护似乎是合适的。 数据交换将数据库里的记录进行互相交换，这样低阶的统计被保留下 来【3 扪。例如k 阶统计是有k 个属性的。d 数据库认为是可转换d 阶的，如 果存在一个数据库d 跟数据库没有相同的记录，但跟d 有相同的k 列， 因为k o ，1 ，d 。例如表1 中的数据库d 和d ，d 是一个d 的2 阶转 换。所有的2 列都保留下来了，既然d 和d 没有相同的记录，发布的数 据就避免了完全缺陷，但是要发现一个数据交换在计算机上是不能解决问 题的。 在2 0 0 2 年，l s w e e n e y 提出了一种用来保护私有信息的k 一匿名保护 模型，用来解决信息泄漏问题。这个解决办法就是找出数据持有者能够识 燕山大学工学硕士学位论文 别的可以与外部信息相连接的全部关键属性( 准标识符) ，禁止通过这些属 性将释放信息与外部信息连接在一起，以此保证视图安全。如果此种情况 无法避免，那么k 匿名保护模型就会检验此时视图组的连接是否会泄漏具 体的元组信息，也就是说基于某个关键属性的视图表的连接所得的元组必 须为k 个( k 2 ) 。因为当k 值为1 时，说明此时通过视图表的连接可以得 到具体的元组的信息，完全泄漏出敏感信息，这种情况是不允许的，所以 在不满足判定条件的情况下，k 匿名保护模型就会禁止视图的发布。 2 4 判定视图安全性方法 数据交换过程中存在的安全隐患早已引起了人们的关注，目前已经提 出了一些检测视图安全性的方法，有些仅针对其中一种或某种窃取方式。 虽然仍不能有效地判定视图的安全性但对我们的工作却有着很大的启发。 2 4 1 查询问答 应用查询问答技术判定视图安全性：确定私有信息用查询s 的形式给 出，给定一个视图v ，那么用v 中的数据来回答查询s ，如果通过这个查询 可以得到私有信息，视图v 就被确定为不安全视图。但是是不是从v 中得不 到查询s 的回答，那么v 就是可以发布的安全的视图呢? 我们举一个简单的 例子来说明：假设发布视图表示为v 1 ( n ，d ) ：- e m p l o y e e ( n , d ，p ) ；隐私信息表 示为s 1 ( d ) ：一e m p l o y e e ( n , d ，p ) 。这样通过在视图v 1 中进行s 1 查询，就能够知 道v 1 的发布是不安全的。 2 4 2 概率独立事件 概率独立事件模型是在s h a n n o n 的“完全安全概念”1 3 9 1 的启发下产生 的。“完全安全概念”是指如果一个攻击者在了解视图发布信息的情况下猜 出私有信息查询的概率与不存在视图发布的情况下猜出私有信息查询的概 率相等，那么对于视图v l ，v 2 ，v n 来讲，私有信息查询s 是安全的。 在s h a n n o n 的启发下，d s u c i u 在2 0 0 4 年提出“查询视图安全性”判 1 4 第2 章基础知识 定定理。用查询s 表示私有信息，v 表示要检测安全性的视图组。如果存 在p ( s ) = p ( s l v ) ，那么我们就认为该视图组的发布是安全的。当p ( v ) 卸时， 也可以说成p ( s v ) = p ( s ) x p ( v ) ，也就是s 和v 相互独立。用概率独立事件 模型来检测视图发布的安全性是一个很好的思想。该文献提出关键元组的 概念。假定d 是一个有限域，q 是一个查询。q t u p ( q ) 是基于q ( i ) = q 的元 组集。对于q 查询而言的数据库实例集i 。而言，如果对于任意一个数据库 实例i l q 而言，q ( i 一 t ) q ( i ) ，那么一个元组t c q t u p ( d ) 对于q 来讲是非 常关键的，q 的关键元组集被标记为c r i t d ( q ) ，如果c r i t d ( q ) 预先可知的话， 可简化为c r i “q ) 。关键元组概念的提出是问题研究的基础，通过分别确定 视图发布的关键元组以及秘密查询q 的关键元组，通过两者之间是否存在 公共的关键元组来判定视图发布的安全性，从而提高了判定算法的效率。 所谓两者存在公共关键元组就是指通过视图发布的形式，秘密查询s 中的 某些关键元组也被公开，也就是攻击者很可能获取到s 的某些信息。 但是d s u c i u 提出的安全模型对安全的限定过于苛刻，虽然能够得到 完全安全的视图，但却牺牲了信息的可用性。另外，在d s u c i u 的模型中 用查询定义视图、和隐私信息。但是在该文献中提到的查询概率的计算算 法中关键元组的判定问题是一个复杂的计算过程。在文献中已经证明判定 视图组安全性的时候必须需要判定的三个或者三个以上联合查询的关键元 组问题是个n p 完全问题。本文就是在d s u c i u 理论的基础上对发布视图 安全性判定过程研究，目的是对d s u c i u 理论中存在的缺陷进行研究，在 克服这些缺陷的基础上，给出可行的算法来完成数据交换过程中对视图的 安全性检测。 2 4 3 统计数据库 有关统计数据库的安全问题的研究已经有了很长的一段历史。统计数 据库所发布的视图是由作用在记录上的聚集功能所组成的1 4 0 l 。信息是通过 聚集数据来隐藏的，目的是保证每一个独立元组中的数据是安全的【4 1 1 。统 计数据库的安全隐患是指可以从允许的统计查询的结果中推断出一些受保 护的信息【4 2 1 。这种推断的时机实际上就代表了转换通道，可能危及