（计算机软件与理论专业论文）多级安全数据库系统集合推理问题研究.pdf

华 中 科 技 大 学 硕 士 学 位 论 文 摘要 数据库安全技术是信息安全的重要研究领域。数据库推理控制是研究高安全等级 的安全数据库系统的关键技术之一，是保障数据库安全的重要手段。我们将研究多级 安全数据库系统属性关联集合推理问题和势集合推理问题。 对于多级安全数据库系统属性关联集合推理问题，分析了表级密级模式下的属性 关联集合推理问 题， 提出了检测和消除属性关联集合推理问题的算法。该算法将该问 题转化为属性关联无向图的问题，通过判断包含敏感信息的表的属性关联无向图是 否存在环路并分析环路中是否存在推理路径来判断是否存在属性关联集合推理。如果 存在推理路径， 则存在属性关联集合推理。 此时可以 通过提高一个或多个表的安全级 来消除推理路径。通过分析该表的所有推理路径，找出消除所有推理路径信息丢失 量最小的安全级调整方案， 该方案可能有很多种，由用户选择一种合适的 方案消除属 性关联集合推理。通过消除所有包含敏感信息表结点的推理路径，消除属性关联集 合推理。 对于多级安全数据库系统势集合推理问题，分析了消除势集合推理的策略，提出 了消除势集合推理的算法。该算法允许建表者定义敏感概念以及敏感概念允许访问的 最大元组个数，当安全级等于表的安全级的用户查询该表时，引入限制的概念计算访 问敏感概念元组的个数，防止这些用户访问敏感概念元组的个数超过预先定义的最 大值， 从而消除势集合推理。 在多级安全数据库系统s d m3 安全机制的 基础上， 对多 级安全数据库系统s d m3 源代码进行改进， 使多级安全数据库系统s d m3 能够消除势 集合推理。 关键词: 多级安全数据库系统，安全模型，属性关联集合推理，势集合推理 华 中 科 技 大 学 硕 士 学 位 论 文 ab s t r a c t d a t a b a s e s s e c u r i t y i s a n i m p o rt a n t r e s e a r c h a r e a o f i n f o r m a t i o n s e c u r i t y . i n f e r e n c e c o n t r o l i n d a t a b a s e s i s a k e y f i e l d o f m u l t i l e v e l s e c u r e d a t a b a s e s y s t e m ( ml s - d b s ) a n d i s a n i m p o r t a n t m e a n s t o a c h i e v e d a t a b a s e s e c u r i t y . w e w i l l r e s e a r c h o n a g g r e g a t i o n i n f e r e n c e a n d c a r d i a l a g g r e g a t i o n in f e r e n c e . f o r a t t r ib u t e s a s s o c i a t i o n a g g r e g a t i o n i n f e r e n c e i n ml s - d b s , t h e p r o b l e m u n d e r t a b l e c l a s s i f i c a t i o n g r a n u l a r i t y i s a n a l y s i z e d a n d a n a l g o r i t h m t o d e t e c t a n d e l i m i n a t e a t t r i b u t e s a s s o c i a t i o n a g g r e g a t i o n i n f e r e n c e i s p r o p o s e d . t h e a l g o r i t h m t r a n s l a t e s t h e p r o b l e m t o u n d i r e c t e d g r a p h o f a t t r i b u t e s a s s o c i a t i o n p r o b l e m. b y d e t e c t i n g t h e l o o p s o f u n d i r e c t e d g r a p h o f a tt r i b u t e s a s s o c i a t i o n o f t h e s e n s i t i v e t a b l e , t h e i n f e r e n c e p a t h s a r e f o u n d .t h e r e m u s t b e a t t r i b u t e s a s s o c i a t i o n a g g r e g a t i o n i n f e r e n c e i f t h e i n f e r e n c e p a t h s e x i s t .t h e n w e c a n a d j u s t t h e s e c u r i t y l e v e l s o f o n e o r m o r e t a b l e s t o e l i m i n a t e t h e i n f e r e n c e p a t h s . b y a n a l y z i n g a l l t h e p a t h e s , a l l t h e c a s e s o f t h e m i n i m u m i n f o r m a t i o n l o s t c a n b e f o u n d a n d t h e u s e r c a n s e l e c t o n e o f t h e m t o e l i mi n a t e a t t r i b u t e s a s s o c i a t i o n a g g r e g a t i o n i n f e r e n c e . l f a l l t h e i n f e r e n c e p a t h s o f t h e s e n s i t i v e t a b l e s a r e e l i m i n a t e d , a t t r i b u t e s a s s o c i a t i o n a g g r e g a t i o n i n f e r e n c e w i l l b e e l i m i n a t e d . f o r t h e c a r d i n a l a g g r e g a t i o n i n f e r e n c e , t h e s t r a t e g i e s o f e l i m i n a t i n g c a r d i n a l a g g r e g a t i o n i n f e r e n c e a r e a n a l y s i s e d , a n d a n a l g o r i t h m t o e l i m i n a t e c a r d i n a l a g g r e g a t i o n i n f e r e n c e i s p r o p o s e d .t h e t a b l e c r e a t e r c a n d e f i n e s e n s i t i v e c o n c e p t a n d t h e m a x m u m n u m b e r o f t ri p l e t o b e a c c e s s e d . wh e n u s e r s w h o s e s e c u r i t y l e v e l i s e q u a l t o t h a t o f t a b l e a c c e s s t h e t a b l e , t h e c o n c e p t i o n o f l i m i t a t i o n i s i n t r o d u c e d t o c o u n t t h e t u p l e s o f t h e s e n s i t i v e c o n c e p t . t h e u s e r s c a n o n l y a c c e s s t h e n u m b e r o f t ri p l e s i n s e n s i t i v e c o n c e p t l e s s t h a n t h a t o f t h e p r e d e f i n e d n u m b e r . i n t h i s w a y , t h e c a r d i n a l i n f e r e n c e i s e l i m i n a t e d . w e i m p l e m e n t t h e a l g o r i t h m o n t h e b a s i s o f t h e s e c u r i t y m e c h n a n i s m o f m u l t i l e v e l s e c u r i t y d a t a b a s e s y s t e m s d m3 1 1 华 中 科 技 大 学 硕 士 学 位 论 文 k e y w o r d s mu l t i l e v e l s e c u r e securemo d e l , a tt r i b u t e s a s s o c i a t i o n a g g r e g a t i o n i n f e mc e , d a t a b a s e s y s t e m, mu l t i l e v e l c a r d i n a l a g g r e g a t i o n i n f e r e n c e 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已 经发表或撰写过的研究成果。 对本文的研究做出 贡献的个人和集体， 均已 在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学 位 论 文 作 者 签 名 : 史凌云 日 期: 加夺年 斗月 8 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和 借 阅 。 本 人 授 权 华 中 科 技 大 学 可 以 将 本 学 位 论 文 的 全 部 或 部 分内 容 编 入 有 关 数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口 ， 在 _年 解 密后 适用 本授 权书。 本论文属于 不保密叮. ( 请在以上方框内打 “ ,/ ) 学 位 论 文 作 者 签 名 : 史麦么 日 期:又 ， 午年 夺月 2 $ 日 指 导 教 师 签 名 : 沐玄 ， 日 期: j 加举年冷月2 牙 日 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论 1 . 1 本课题的研究背景、目的及意义 以计算机和网络技术为代表的信息技术的广泛应用是现代社会信息化的标志。 信息技术给人们的生活和工作带来了极大的方便，但同时也带来许多新的问题，其 中数据的安全问 题就是其中最突出的问题之一。在信息化社会中，国 家的许多重要 信息都是存放在计算机系统中的，计算机信息系统的安全已经成为涉及国家主权的 重要问题。数据库管理系统作为管理信息系统的基础软件，其安全性在信息系统中 起着至关重要的作用。 为保护机密信息不被窃取、 篡改、破坏，仅仅使用硬件保护 是不够的，还必须采取必要的软件保护措施。对数据库安全的威胁主要有:未经授 权非法访问、修改数据库信息;窃取数据或使数据失去真实性、可用性;来自网络 的入侵;隐通道攻击和推理攻击等m 。数据库安全技术的研究已成为信息安全的重 要研究课题z 1 多级安全数据库管理系统( m u l t i l e v e l s e c u r e d a t a b a s e m a n a g e m e n t s y s t e m m l s - d b ms ) 通过给每一个主体和每一个客体都分配一个安全级，根据主体和客体 安 全级的 支配关系来控制主体对客体的 访问， 保护数据库中的数据3 1 。当前国际 上 m l s - d b m s 通常使用的 安 全模型是b e l l 另一种运行在裸机上， 在硬件级实现了任务分离和内存保护，把敏感数据分配到自己的地址空间，完全脱 离了不可信的地址空间，是满足 b 2级标准的安全数据库系统。两种数据库产品提 供 给用户的 接口 是 一 样的。 o r a c l e , i n f o r m i x 1 9 .2 0 1等大型 数据库公 司 也 推出了 自己的安全数据库系统t r u c t e d o r a c l e ? 和i n f o r m i x - o n l i n e / s e c u r e . 国内 在这方面的研究虽然起步较晚，但也取得了一些可喜成果。如北京大学研 制的安全数据库系统原型c o b a s e v 2 . 0 通过在安全策略方面增加强制访问控制， 在责任方面增加审计功能，具备了 b 1级所要求的功能。武汉华工达梦数据库公司 自 主开发的安全数据库管理系统s d m3 ，它采用三权分立的机制，并采用了多级安 全机制实现数据库管理系统的强制存取控制，具备了部分b 2 级的功能2 1 . 2 3 1 1 .2 .2多级安全数据库系统推理问题 由 于人类用以 推理的信息千差万别( 包括已 有的数据库信息和外部知识) ， 推理 新信息的方式也极为不同，所以要防止未授权的推理是非常复杂的，也不可能给出 通用的解决方案。 我们分别对用于推理的信息以及推理的方法进行一个简单的描述。 i . 用于推理的信息来源 推理 信息的广泛性是造成推理问 题复 杂的首要因素。 用于推理的 信息主要有2 4 1 . ( 1 )包括关系名和属性名的模式元数据以及其它元数据如值约束和关键字 约束等; ( 2 )存储在关系中的数据，即数据的值; ( 3 )统计数据; ( 4 )派生数据: ( 5 )数据的存在性; 华 中 科 技 大 学 硕 士 学 位 论 文 ( 6 )数据的改变或消失 ( 如安全级别上升) : ( 7 )未存于数据库中，但在应用域已知的数据语义; ( 8 )未存于数据库中的特定领域的知识; ( 9 )普通知识和普通常识。 2 . 常用的推理方法及其解决方法 推理的策略和方法也很多。常见的推理方法主要有基于查询敏感数据的推理、 统计数据库推理、 主键完整性推理、 外键完整性推理、 值约束推理、 分类约束推理， 函数依赖推理，多值依赖推理以及集合推理等。 由于推理信息的多样性以及推理方法的复杂性，多级安全数据库系统的推理问 题还没有得到根本的、有效的解决。 针对一些特定推理问题，国内外的很多专家学 者经过多年的研究，提出了一些解决特定推理问题的技术和方案。 ( 1 )基于查询敏感数据的推理 对于 基于查 询敏感 数据的 推理， d . g . m a r k : 提出了 一 个处理该问 题的 方法2 6 他假定数据库由一个全局关系r组成， 全局关系r可以通过所有关系的笛卡尔积得 到。从查询、谓词和推理模式表示数据库元组等价的角度出发，通过检查用户形如 a ,- a ; ( 其中a ; 是常量)的选择子句的查询，提出了几乎可以找到所有推理的方法。 在该方 法中， 输入参数是含有敏感信息的视图c 和用户的查询q ， 然后求得覆盖视 图c和查询q的最大的视图d ，及覆盖视图d的q的最小子集，如果id i= iq i ，则 有可能存在推理，不允许查询。否则一定不存在推理，允许查询。这样，就可以得 出一个不存在基于查询敏感数据推理的 数据库。假设数据库目 前没有推理危害， 有 一个元组 t ，加入数据库。通过检索这个元组，上面的方法可以检查这个元组是否 会引起推理及是否应该被标记为敏感信息。这样如果t 被标记为敏感信息，那么所 有包含 t 的视图都要被标记为敏感信息。这样通过对所有新加入元组都进行如此处 理，就可以使数据库中不存在基于查询敏感数据的推理。 ( 2 )统计数据库的推理问 题 统计数据库安全问题是关于如何不泄露自身数据，而回答对数据统计查询的问 题 2 6 ,2 7 。 这样的统计查询有平均数中间值，标准偏差等。统计数据库安全的威胁 在于攻击者可能通过某一段时间提出聚集统计查询，并对返回结果执行算术操作， 华 中 科 技 大 学 硕 士 学 位 论 文 使用所涉及的个体集合的大小和种类信息来发现个体的统计信息。严格地说，统计 数据库并不属于推理问 题范畴，它有自己的论题。国际上一些学者在统计数据库安 全领域做了很多的研究。 ( 3 )主关键字推理 主关键字推理是由 于主关键字唯一性约束而产生的推理。它是数据库中的最基 本的要求之一。当数据的标记粒度是表级时，该要求不会引起推理问题，因为关系 中的主关键字有相同的安全级别，但如果标记粒度是元组级或者是属性级的时候就 会引起推理。表 1 . 1 是员工表 ( 主关键字是姓名) 。 表 t . 1员工表 安 全 级 秘密 年 龄 假设有一个安全级别为普通的用户想插入元组 ( 普通， 李明， 2 5 ) 。 如果要保持 关键字唯一性，要么删除安全级别为秘密的这条元组，要么拒绝这个插入。 如果删 除这条元组，显然这不可以接受。如果拒绝插入，低安全级别的用户就可以得到这 样的推理，高安全级别的员工李明存在于数据库中。处理主关键字推理的一个方法 是在数据库中引入多实 例机制2 8 ,2 9 ) 。 即 数据库中允许存在安全级别不同 但主关键字 相同的元组，也就是说把安全级别作为主关键字的一部分。这样，即使数据库中存 在高安全级别的元组， 也允许具有相同主关键字的低安全级别的数据插入，从而解 决了主关键字完整性问题。 ( 4 )外关键字推理 外 关 键字推理是由 于 表之间的 外关 键字完整性约束而 产生的 推理 3 0 。 当 标记 粒 度是列级、元组级或者表级时可能产生外关键字推理问题。独立的、非赢利的研究 机构s r i i n t e rn a l 开发出了检测外关键字的推理工具d i s s e c t 。该工具的输入参数 是查询语言m s q l 定义的数据库模式， 它检测两个关系之间是否存在两个安全级不 同的推理路径，如果存在的话，将会输出推理路径，但是这个推理路径是否是真正 的推理路径，将由用户来判断。如果存在推理路径的话，通过提高表、 元组或者列 的安全级来消除推理。 华 中 科 技 大 学 硕 士 学 位 论 文 ( 5 )值约束推理 值约束是涉及一个或多个数据项上的数据值的约束。如果一个约束是定义在不 同安全级别的数据上， 则该约束的可用性可能导致推理通道的产生。 c . m e a d o w s 和 s . j a j o d i a 研究了 值约束推理的产生和消除方法， 提出 值约束推理问 题的一 般的 解决 方 法是只能 在单一的安全级别上定义值约束3 1 。 如果一个值约束定义在几个安 全级 别上， 或者改 变不同的 安全级别， 使得值约束涉及的安全级别相同，或者把该值约 束分割为几个单一级别上的约束来消除推理通道。 ( 6 )分类约束推理 g . l . s i c h e r m a n , w . d . j o n g e 和r . p . v a n d e r i e t 对分类约束推理进行了 研究3 2 分类约束是一个描述数据依照什么样的标准来分类的规则。 如果分类约束是可知的， 那么通过分类约束自 身也可能推理得到敏感数据。在该文献中，他们研究了如何在 分类约束分别为可知和不可知的情况下保护秘密信息，在他们的系统里，需要定义 许多拒绝回答查询的条件，并给出一个基于这些条件的策略集合。提出一个包含推 理规则的安全数据库的形式模型，并证明依赖分类约束是否可知，什么样的回答才 是安全的响应。特别地，当分类约束是可知的时候，如果他们的策略仅有一个是安 全的， 该策略要求如果一个元组的某个值是秘密的， 那么对该值的查询都不会响应。 这种策略带来的结果是每个策略都始终如一地采用一组标准。因此，它不可能像一 些统计数据库那样，最初时采用一个更自由的策略，当可选的安全值减少时，就转 换到一个更严格的策略。然而，由于它的极其一般性，这个策略可被运用于所有数 据库和推理系统。 ( 7 )函数依赖和多值依赖推理 对 于 函 数 依 赖和 多 值 依 赖 推 理， t . a . s u 和g o z s o y o g lu 对 此 作了 比 较多 的 研 究 3 3 ,3 4 他们对属性密级模式下可能存在的函数依赖推理和记录密级模式下可能存在的多值 依赖推理进行了较为深入的 研究。 在属性密级模式下， 考虑函数依赖推理， t . a . s u 和g o z s o y o g lu 提出了 一些提高属性的安 全级的算 法。 其中一个算法是把属性列表、 属性的安全级和能引起推理的函数依赖集作为输入，输出为属性列表、属性的安全 级。新输出的属性的安全级可能和输入的安全级不同。这样，经过算法对属性安全 级的 调整，就消除了由函数依赖引起的推理通道。同样，在记录密级模式下，考虑 华 中 科 技 大 学 硕 士 学 位 论 文 多 值依赖推理， t . a . s u 和g . o z s o y o g l u 也提出了一 些算法来消除多 值依赖推理。 其 核心思想就是把存在多值依赖推理的关系实例中的某些元组的安全级升高，经过元 组的安全级调整后，新的关系实例就不存在多值依赖推理。 1 .2 .3多级安全数据库系统集合推理问题 集合推理问题是指敏感信息可以从数据集合推出，但不能从该集合的任何子集 推出，并且数据集合的安全级大于该集合中任一子集数据的安全级。 有些研究者按照实体和属性之间的关系把集合推理问 题分成两类 3 5 -3 7 1 . 属性关联集合推理问题，不同实体间数据属性的关联产生的推理问题。 2 . 基于记录个数的集合推理问题， 同一实体中多个实例或者多个实例的部分信 息的关联产生的推理问 题， 这类集合推理问 题也称为势集合推理问 题。 典型的势集 合推理问题的例子是安全部门的电话号码薄，用户最多只能查询n个电话号码，也 就是说用户查询小于或者等于n个电话号码不能够推出敏感信息， 但当查询的电话 号码的个数大于n时则有可能推出敏感信息。 对于属性关联集合推理问题，t . h . h i n k e 提出用语义数据模型的方法找出推理 通道 3 6 ， 该模型用一个语义关系图来表示数据库中可能的推理。 数据项用结点表示， 由表示关系的边连接起来。 从结点a到结点b的两条路径， 如果在其中一条路径上 可以看到所有边，而另一条却不能看到所有边，则可能存在的推理通道。如果存在 推理通道，则提高一条或多条边的安全级，直到消除所有的推理通道。 对 于 势 集合 推理， a l 级原型 系统l d v 和s e a v i e w 对 势集合推理 进行了 处 理 3 8 ,3 9 a . m o t r o , d . m a r k s ，和s . 7 a j o d i a 提出了 一种记录用户以 前访问 所有数 据个数的 方 法 来消除 势 集合 推理问 题4 0 1 ， 该 信息 可以 用 来决定 用户是否能 够进行新的 查 询。 该 方法允许用户自由定义敏感信息以及允许用户访问敏感信息的最大值。如果用户要 对敏感信息进行新的的查询，则首先判断用户以前访问数据的个数和新的查询的数 据的个数是否超过预先定义的最大值，如果不超过则允许用户查询，否则不允许用 户进行新的查询，这样就有效的消除了势集合推理问题。 多级安全数据库系统的推理问题研究是一个比较新的研究领域，尽管国外许多 专家学者对此进行了大量的研究，对特定的推理问题提出了相应的解决办法，但国 华 中 科 技 大 学 硕 士 学 位 论 文 内致力于推理问题研究的学者并不多。国标g b 1 7 8 5 9 - 1 9 9 9( 计算机信息系统安全 保护等级划分准则 ) 应用指南的数据库部分对第四级的系统要求处理推理问题， 也 提出 了 多 级安 全d b m s 中 实 现 推 理 控 制的 技 术 规范。 但目 前国内 并 没 有 一 个 系统 能 够达到这些规范的要求，并且推理问题没有通用的解决办法。 1 .3本文的主要研究工作 本课题主要致力于多级安全数据库系统的集合推理控制问题，包括属性关联集 合推理问题和势集合推理问题的研究。本文的主要研究工作包括三个方面。 1 . 将研究表级密级模式下，因表之间的属性关联引起的属性关联集合推理问 题。把属性关联集合推理问题转化为属性关联无向图的问题，判断所有包含敏感信 息的表结点的属性关联无向图是否存在推理路径，如果存在推理路径的话，则提高 一个或多个表的安全级消除推理路径， 这样就消除了属性关联集合推理问 题。 2 . 设计并实现消除属性关联集合推理的工具， 它根据用户的输入， 判断在属性 关联无向图中是否存在环路确定是否存在推理路径，如果存在推理路径，则通过提 高一些表的安全级消除属性关联集合推理，由用户选择合适的安全级调整方案，输 出的表及其安全级不存在属性关联集合推理。 3将研究势集合推理问题， 分析消除势集合推理问题的策略，提出消除势集合 推理问 题的算法，该算法引入限制的概念计算用户访问敏感概念元组的个数，防止 用户访问敏感概念元组的个数超过预先定义的最大值，从而消除势集合推理，并对 算法进行分析。在多级安全数据库系统s d m3 安全机制的基础上，实现了该算法， 使多级安全数据库系统s d m3 能够消除势集合推理。 华 中 科 技 大 学 硕 士 学 位 论 文 2 属性关联集合推理研究与实现 数据库中大量的信息是以表的形式存放的，而这些表不是独立的，它们是互相 联系的，属性关联集合推理问题就是因为表之间的属性关联而引起的推理问题。本 章将首先通过引入例子，说明属性关联集合推理问题，然后把该问题转化为属性关 联无向图的问题，给出形式化的定义以及定理，最后在此基础上，提出解决该问题 的算法。 2 . 1 问题的提出 安全级是分层密级和非分层范围 组 成的 二元组2 3 。 本文在考虑安全级时均不考 虑非分层范围， 认为所有的非分层范围都相同， 仅考虑分层密级。 不同的安全系统， 可能实现不同的数据密级模式。根据数据密级标记粒度的不同，有几种不同的数据 密级模式，分别是表级密级模式、属性级密级模式、记录( 元组) 级密级模式、元素 级密级模式。 按照b l p 模型的安全策略要求， 在多级安全数据库系统中， 数据( 或客体) 以不 同的安全级存储，不同的用户( 或主体) 被授予不同的安全级。只有当用户u 的安全 级l 。 大于或等于数据d 的安全级l d 时， 用户u 才能读取数据d ; 当u 的安全级小于 d 的安全级时，u 不能读取d o 属性关联集合推理与数据的密级标记粒度有关，当标记粒度为属性级、元素级 时，不存在属性关联集合推理;当标记粒度为表级或元组级时，才可能产生属性关 联集合推理问题。本章将探讨在表密级粒度下，多级安全数据库系统因属性关联而 引起的集合推理问题。 下面以“ 公司一工程”的例子来具体说明这个问题。 例2 . 1现有若干个工程，有一些公司想参与这些工程，同时每个工程都会召开 若干会议， 会议邀请一些员工参加会议。 在关系数据库中， 用工程承接表， 工程表， 公司表，员工表，会议表五张表来存储这些信息。其中 “ 公司表”记录承接了工程 华 中 科 技 大 学 硕 士 学 位 论 文 的公司的相关信息; “ 员工表”记录公司的员工信息; “ 会议表”记录工程召开的会 议信息; “ 工程表”记录工程的相关信息; “ 工程承接表”记录工程的承接公司及与 承接工程相关的信息，所有的表都有一定的安全级，只有安全级大于等于这些表的 用户才能看到相应的信息。假设数据库中的安全级别有绝密、机密、秘密和普通四 个安全级别 ( 其中绝密 机密 秘密 普通) 。考虑数据库信息的最大可用性，五张表 的安全级别定义如下:工程承接表定义为绝密;会议表为机密;工程表为秘密;公 司表和员工表为普通。这些表之间通过属性相关联，表与表之间的边表示该两个表 之间有属性相关联。根据各表之间的关系可画出图2 . 1 0 图2 . 1 “ 公司一工程”图 根据b l p 模型， 安全级为机密的用户， 他不能直接访问安全级为绝密的“ 工程 承接表”中的信息，即无法知道哪些公司承接了哪些工程。但是他可以 访问员工表 和会议表的信息。这样，通过查询哪些员工参与了哪个项目 举行的会议，员工表中 记录了这些员工属于哪些公司，同时会议表中也记录了会议是为哪个项目召开的会 议，这样就可以推断工程承接表中的信息，这样，安全级为机密的用户间接地获取 了安全级为绝密的敏感信息，成功的利用推理进行了一次入侵。这样的一个推理过 程就是针对该敏感信息的一个推理路径，即工程承接表，员工表，会议表，工程承 接表是推理路径。我们还要注意的是即使有推理路径，推理也有可能不存在，只有 推理路径有信息的时候，才存在推理，否则就不存在推理。对于推理路径工程承接 表，员工表，会议表，工程承接表。只有当查询 s e l e c t公司号，工程号 f r o m 员工表，会议表 华 中 科 技 大 学 硕 士 学 位 论 文 w h e r e员工表. 会议号=会议表. 会议号; 有值时，才真正存在推理，而这只有在对数据库进行查询时才能知道。因此我们的 目的是找出潜在的推理路径。如果不存在潜在的推理路径，就肯定不存在推理。 上面的例子说明，如果数据库中各个表的安全级设置得不合理，用户根据它可 以访问到的低安全级的表，以及这些表之间的属性关联，有可能推出他不能访问的 高安全级的表信息。 2 .2 问题的描述 为了更好的描述属性关联集合推理问题，下面我们给出一些形式化的定义。 定义2 . 1实体属性关联: 设a , b是两个不同的实体， 分别有属性( a , , a 2 , ， a n ) 和 ( b 1 , b 2 ,， b . ) ， 如果实体a中有某个属性a ; ，实体b中 有某个属性场 ， a 、 和b ; 意 义相同， 则 称实体a和实 体b属性 关联， 如果实体a和实体b 分别 通过 a ; 和场 相关 联， 记为a . a i 一 b . 炳 。 例 2 . 2假设有两个表，公司表 ( 公司名，公司号，) ，员工表 ( 员工名，员 工号， 公司号， ) ， 这两个表的属性公司号都表示某个公司的公司号， 因此这两个 表通过属性公司号关联，公司表. 公司号二员工表， 公司号，在这个例子中公司表和 员工表的 属性公司号名字是相同的， 也有可能是两个表相关联的属性意义上相同( 例 如都表示公司的代号) ，但是属性名字不同，这样两个表也称为属性关联。 定义 2 . 2属性关联集合推理:假设有关系模式 r 1 ( a 1 1 ， a 1 n 1 , l , ) ,， r n ( a n l , ， a n n n , l n ) ， 其中a ii ( 1 _ i _ n , 1 l s ? , ， l , ( 2 _ s _ n , 2 _ p u，则称表t为包含敏 感信息的表。 在例 2 . 1 中，多级安全数据库系统中有四个安全级，从高到低分别为绝密、 机 密、秘密和普通，工程承接表、会议表、工程表的安全级均大于普通，因此工程承 接表、 会议表和工程表都是包含敏感信息的表。 2 .3 消除属性关联集合推理问题的算法 2 .3 . 1 属性关联无向图 对每一包含敏感信息的表，根据用户输入的可能存在推理的表信息以及表之间 的属性关联信息，可以把属性关联集合推理问题可以转化为一类无向图来解决，我 们把称它为属性关联无向图。 定义2 . 4属性关联无向图:图g= ( v , e ) , v中的每一个结点v , v e v，在属 性关联无向图中表示一张表，称为表结点，对于 v中每一对表的属性关联 a . a ; = b . h ， 在属性 关联无向 图中 表示为一 条无向 边e = ( a , b ) ， 则图g称为 属性关 联无 向图。 定义 完全相同 后的集合 2 . 5表结点的属性关联无向图: 设v是表集合， 其中的表结点的安全级不 v 。 是安全级最高的表结点，设v 为v中除去所有最高安全级的表结点 则由v = v u v o 及边e ，组成的属性关联无向图g = ( v , e ) , e 为v 中属性关联组成的边，则图g称为表结点v 。 的属性关联无向图。 例2 . 3假设数据库中有表v = t o , t , , t 2 , t 3 ，其中t o 是安全级最高的表， t i , t 2 , t : 的 安 全级小 于t 。 的 安全级， 下面用t ;j 表示表t ; 的 第.l 个属 性， v中 各 个 表之p i 存在属性关联t o . t o o = t 1 . t l 4 , t o . t o t =t 2 , t 2 5 , t o . t 0 3 = t 3 . t 3 6 , t i . t l 7 = t 2 . t 2 g , t 2 . t 2 9 =t 3 . t 3 2 - 由 于v中各个表之0 1 存在属性关联t o . t o o = t 3 . t 1 4 , t o . t o e = t 2 . t 2 5 , t o . t o 3 = t 3 . t 3 6 , t l . t l 7 = t 2 . t 2 8 , t 2 . t 2 9 = t 3 . t 3 2 。 所以 各 个表 之间 存在边e = ( t o , t , ) , ( t o , t 2 ) , ( t o , 华 中 科 技 大 学 硕 士 学 位 论 文 t 3 ) , ( t i , t 2 ) , ( t 2 , t o ) ， 根据v和e可画出 表结点t 。 的属性关联无向图，如图 2 . 2 所示。 图2 . 2 t 。 的 属性关联无向图 定 理2 . 1设v 。 的 属性关联无向图g = ( v , e ) , v = v v , ， v ， 不存在属性 关联集合推理，如果下列条件之一成立: 1 .从v 。 到v 。 不存在环路; 2 . 如果从v o 到v 。 存在环路v o , v k ,， v . , v a ( 1 _ k _ n , 1 5 m5 n ) ，且v o , v k 以 及v o , v ,n 之间 存 在 属性 关联v o . t p i = v k . t k j . v. t m c = v o . t o l， 则i=1. 证明:假设表结点v 。 的安全级是l o , v = v - v o , v i 是v ， 中安全级最高的表结点， 安全级为l i ，假设用户u的安全级是l i . 假 设条件1 满足， 从v 。 到v 。 不 存 在环路， 因 此必存在结点v p v q ( o s p _ n , 0 _ q _ n ) ， 它们之间 没 有边， 即v p 和v q 之间 没有属性关联， 假设v o , v i , . . . , v p ( 1 s i _ n , 1 _ p _ n ) 以 及v o , v j , ， v q ( 1 _ j - n , 1 _ q _ n ) 都有边相连， v p 和v q 没 有属 性关联， 不 存 在 任何属 性使得v p . t a = v q . t b ， 所以 用户不能 通过属性关联从v p 推 理出v q 中 的 信息， 即 用 户不能从 v ; , ， v i 推理出v 。 的 信息， 所以 不存 在属性 关 联集合 推 理。 假 设条 件2 满足， 安 全级为l i 的 用 户 可以 访问 v k l . , v m ) ， 因 为v o . t o ; = v k . t kj , v m . t , 。 一 v o . t o l( 1 - 1) , 所以v k . t k j = v m . t m c r t k! 和t m c 属 性意义 相同， 且 是v k 和v m 中的属性，因此用户并不能推出v o 中的信息。口 定义 2 . 5 推理路径:给定结点v o 及它的属性关联无向图g= ( v , e ) , v = v o , v i , ， v n ) 。 如 果图g 中 存 在 简 单 环 路p : v o , v m ， 一 v s , v o ( 1 _ m _ n , 1 _ s _ n ) , 其中v o , v m , v 5 , v 。 存 在属性关 联v o . t o ; = v m . t m j , v s . t s u v o . t o 、 且1 # v ， 且v m ， 一， v 、 的 任何子集不能推出v 。 中相同的信息， 则称路径p是推理路径。 在例2 . 1 中，工程承接表，员工表，会议表，工程承接表是推理路径，用户可 华 中 科 技 大 学 硕 士 学 位 论 文 以通过访问员工表和会议表的信息推理出工程承接表的信息。 定义2 .6伪路径:给定结点v 。 及它的属性关联无向图g一( v , e ) , v = ( v o , v i ,， v n ) 。 从v 。 到v 。 的 环路p o : v o , v ; , ， v m , v o ( 1 _ i _ n , 1 m _ n ) ， 其 中v o , v v o , v m 之i u l 存在属性关联v o . t o p 一 v ;. t ij , v - t m k = v p . t p ， 且p = 1 ; 环 路 p i : v o , v q , ， v s , v o ( 1 _ q 5 n , 1 k n ， 有w ,m 5 w m 。 这样， 每次 提高v , 的 安 全级， 就 得到 新的非 增长的 权 值。 这 样， 就可以 定义因安全级调整导致的表的信息丢失量。 定义 2 . 7表的信息丢失量:表的权值在调整前和调整后的差值。 在例2 . 1 中，假设安全级绝密、机密、秘密、 普通的权值分别是3 , 5 , 7 , 9 , 华 中 科 技 大 学 硕 士 学 位 论 文 对于包含敏感信息的表结点工程承接表和推理路径工程承接表，员工表，会议表， 工程承接表，提高员工表或者会议表的安全级至工程承接表就可以消除推理路径， 显然提高会议表的信息丢失量最小，提高会议表的信息丢失量是2 e 我们在本节中研究的属性关联集合推理的安全级标记粒度是表级的，即数据库 中的每个表都可以 转化成图中的一个结点，它们通过边相连，在数据库设计阶段消 除属性关联集合推理问题，比较易于实现。如果安全级粒度是元组级的话，需要在 数据库运行阶段消除，它会随着数据库元组的增加而产生变化，复杂性和效率都比 较高，我们在此不做研究。 2 .3 .2消除属性关联集合推理问题的算法 假定所有存储在表级密级模式的多级安全数据库系统中的表都已经被指定了初 始的安全级。由于表之间存在属性关联，因此可能存在属性关联集合推理，为了消 除可能存在的属性关联集合推理，我们的目 标就是找到一个高效的算法来调整表的 安全级。 基于定理2 . 1 ， 我们提出算法2 . 1 来消除属性关联集合推理。 首先对表按照 安全级从高到低进行排序，判断安全级为最高的表结点是否存在环路，如果存在环 路，则判断环路是否是推理路径，找出所有的推理路径，对该表结点的所有推理路 径进行处理，通过提高一个或多个表结点的安全级消除所有的推理路径，找出信息 丢失量最小的安全级提高方案，这可能有几种方案，由 用户选择一种方案，根据用 户选择的方案，对表的安全级进行调整。然后再对其余所有包含敏感信息的表进行 同样的处理，消除属性关联集合推理。 1 . 算法描述 算法2 . 1消除属性关联集合推理问题的算法。 属性关联集合推理算法通过对每一个包含敏感信息的表进行处理，消除属性关 联集合推理。 算法共有三个输入参数: 表及其对应的安全级链表t a b l e ; 表之间属性关联的链 表a t t r a s s o c ;每个安全级的权值分配方案w e i g h t . 算法输出是调整后的表的安全级分配方案，该方案有效地消除了属性关联集合 华 中 科 技 大 学 硕 士 学 位 论 文 推理，并且对每一个包含敏感信息的表，信息丢失量最小。 该算法共有六个步骤。 ( 1 )初始化不包含推理的表及其安全级链表n o i n f e r = 0 a ( 2 )把链表 t a b l e按照安全级从高到低进行排序，如果所有表的安全级相同， 则不存在推理问 题， n o i n f e r = n o i n f e r u t a b l e ， 程序结束。 ( 3 )对安全级最高的表结点v o ， 根据表集合t a b l e 找出所有安全级小于v 。 的表 和 v 。 组成新的集合 t a b l e ，根据 a t t r a s s o c ，找到 t a b l e 之间的属性关联信息 a tt r a s s o c ， 调用函数b u i l d g r a p h ( t a b l