（计算机软件与理论专业论文）推理通道和隐蔽通道的检测与消除.pdf

哈尔滨工程大学硕士学位论文 摘要 常见的商业数据库的安全性对于一般的企业应用来说是足够了，但是 对于像军队、政府等特殊部门，必须研究特种数据库以确保其信息的绝对 安全性，因此就产生了对安全数据库的需求。国外对安全数据库的研究已 经比较成熟了，并推出了相关的产品。但国内对安全数据库的研究还很不 成熟，并且由于涉及到国家安全国外的产品不向中国出口，所以必须要研 究自己的安全数据库以弥补这方面的空白。 本文首先介绍了安全数据库的概念和安全数据库的分级，然后介绍了 推理通道的概念以及多级安全数据库中推理通道的研究现状，并且描述了 一些检测和消除推理通道的方法。本文通过使用泄漏推理引擎扩展了强制 存取控制机制，确保了数据的安全性。本文使用具有高度表达性的h o r n 子句约束开发了用于数据依赖和数据独立泄漏的推理算法。本文引入了多 实例以解决多级数据库中的隐蔽信号通道，因此必须对传统的关系模型进 行根本变革。本文介绍了多级关系的概念并阐述了更新操作在多级关系中 的语义。本文提出了一种新的多级关系的分解和恢复算法并使用实例说明 了它的操作过程。 关键词：安全数据库；推理通道；隐蔽通道；多实例 哈尔滨工程大学硕士学位论文 a b s t r a c t t h es e c u r i t yo ft h ec o m m o nc o m m e r c i a ld a t a b a s es h o u l db ee n o u g hf o r g e n e r a le n t e r p r i s e s ，b u ti ti s n te n o g hf o rs o m es p e c i a ld e p a r t m e n t ss u c ha s a r m y , g o v e r n m e n t ，e t c s ow em u s ts t u d yt h es p e c i a ld a t a b a s et og u a r a n t e et h e a b s o l u t es e c u r i t yo ft h e i ri n f o r m a t i o n ，a n dw ec a l li ts e c u r ed a t a b a s e t h e f o r e i g ns t u d yo ns e c u r ed a t a b a s eh a sb e e na l r e a d yr i p e r , a n dh a sr e l e a s e dt h e r e l e v a n tp r o d u c t s ，b u tt h ed o m e s t i cs t u d yo ns e c u r ed a t a b a s ei ss t i l lv e r yu n r i p e b e c a u s ew ec a n n tb u yt h e s ep r o d u c t sf r o mf o r e i g nc o u n t r yf o rs e c u r i t y p r o b l e m s ，w em u s ts t u d y o u ro w ns e c u r ed a t a b a s e f i r s to fa l lw ei n t r o d u c et h ec o n c e p to ft h es e c u r ed a t a b a s ea n d c l a s s i f i c a t i o no ft h es e c u r ed a t a b a s e ，t h e nw ei n t r o d u c et h ec o n c e p ta n d r e s e a r c hc u r r e n ts i t u a t i o no ft h ei n f e r e n c ec h a n n e l si um u l t i l e v e ls e c u r e d a t a b a s e w ed e s c r i b es o m em e t h o d st od e t e c ta n de l i m i n a t ei n f e r e n c ec h a n n e l s w ep r e s e n ta ni n t e g r a t e ds e c u r i t ym e c h a n i s m c a l l e dt h ed i s c l o s u r e m o n i t o r ( d i m o n ) ，w h i c hg u a r a n t e e s d a t ac o n f i d e n t i a l i t yb ye x t e n d i n ga m a n d a t o r ya c c e s sc o n t r o lm e c h a n i s m ( m a c ) w i t ht h ed i s c l o s u r ei n f e r e n c e e n g i n e ( d i l e ) w ed e v e l o pa c t u a li n f e r e n c ea l g o r i t h m sf o rb o t hd a t a - d e p e n d e n t a n dd a t a - i n d e p e n d e n td i s c l o s u r e sf o rah i g h l ye x p r e s s i v ef a m i l yo fh o r n c l a u s e c o n s t r a i n t s w eu s ep o l y i n s t a n c et oe l i m i n a t et h ec o v e r ts i g n a lc h a n n e li nt h e m u l t i l e v e ls e c u r ed a t a b a s e ，s ow em u s tc h a n g et h et r a d i t i o n a lr e l a t i o n a ld a t a m o d a l w ei n t r o d u c et h ec o n c e p to ft h em u l t i l e v e lr e l a t i o na n dw ee x p l a i nt h e u p d a t es e m a n t i c sf o rm u l t i l e v e lr e l a t i o n w ep u tf o r w a r dan e wm e t h o df o rt h e d e c o m p o s i t i o na n dr e c o v e r yo fm u l t i l e v e lr e l a t i o n ，a n dw eu s es o n i ce x a m p l e s t oi l l u s t r a t et h i s k e ) n v o r d s ：s e c u r ed a t a b a s e ；i n f e r e n c ec h a n n e l ；c o v e r tc h a n n e l ；p o l y i n s t a n c e 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 随着计算机资源共享和网络技术的应用日益广泛和深入，特别是i n t e m e t 技 术的发展，计算机的安全性问题越来越得到人们的重视。对各种计算机及其相关 产品、信息系统的安全性要求越来越高。为此，在计算机安全技术方面逐步发展 建立了一套可信( t r u s t e d ) 计算机系统的概念和标准。只有建立了完善的可信或 安全标准，才能规范和指导安全计算机系统部件的生产，比较准确的测定产品的 安全性能指标，满足民用和国防的需要。 在目前各国所引用或指定的一系列安全标准中，最重要的当推1 9 8 5 年美国国 防部( d o d ) 正式颁布的d o d 可信计算机系统评估标准( t r u s t e dc o m p u t e r s y s t e m e v a l u a t i o n c r i t e r i a ，简称t c s e c 或d o d 8 5 ) 。1 9 9 1 年4 月美国n c s c ( 国 家计算机安全中心) 颁布了可信计算机系统评估标准关于可信计算机系统的解 释( t r u s t e dd a t a b a s ei n t e r p r e t a t i o n ，简称t d d 。将t c s e c 扩展到数据库管理系 统。t d i 中定义了数据库管理系统的设计和实现中需满足和用以进行安全性级别 评估的标准。 t c s e c ( t d i ) 将系统分为四组七个等级，依次是d ( 最小保护) 、c 1 ( 自 主安全保护) 、c 2 ( 受控存取保护) 、b i ( 标记安全保护) 、b 2 ( 结构化保护) 、 b 3 ( 安全域) 、a 1 ( 验证设计) ，按系统可靠或可信程度逐渐增高。在t c s e c 中 建立的安全级别之间具有种偏序向下兼容的关系，即较高安全l 生级别提供的安 全保护要包含较低级别的所有保护要求，同时提供更多或更完善的保护能力。 安全数据库区别于普通数据库的主要标志在于安全数据库实施了强制存取控 制“( m a n d a t o r y a c c e s sc o n ：i z o l ，简称m a c ) 。强制存取控制要求对系统的数据加 以标记，并且要求仅当主体( 用户或代表用户的进程) 的级别大于等于客体( 数 哈尔滨工程大学硕士学位论文 据库表，元组，数据元素等) 的级别时主体才能读取客体数据，仅当主体的级别 等于客体的级别时主体才能向客体写数据，即不允许高级数据流向低级主体。所 以要想实现一个安全数据库，首先必须实现强制存取控制，这也是安全数据库跟 一般数据库的主要区别之一。 1 2 国内外研究现状 国外对数据库安全的研究从七十年代就开始进行，理论上已达到一定深度并 付诸实践，在一些原型系统及商用系统中已经达到了b 1 级安全，少数个别系统 甚至达到了a 1 级。 a 1 安全d b m s ( 简称a s ) 是由美国汤普森拉莫伍尔德里奇公司( 柳) 国防系统组的高级安全d b m s 内部研究开发工程开发的多级安全关系d b m s 。 它是一个用a d a 语言开发的可用的系统原型。开发a s d 的主要目的是开发一个 符合美国国防部a 1 标准的d b m s ，因此a s d 是遵照a 1 标准设计实现的。a s d 的主要特征是系统保证数据同时受自主存取控制和强制存取控制规则保护，因此， 它允许可信系统与非可信系统的互联。在系统中只存储共享数据，这些数据对于 不同安全级别的用户均是可存取的，这改进了数据的完整性。 s e a v i e w ”工程是由斯坦福研究所( s i u ) 、g e m i n i 和o r a c l e 公司合作完成的 个原型系统。它使用一个核心结构来实现s e a v i e w 模型，它的目的是实现一个 符合a 1 级安全标准的d b m s 原型系统。 目前，几乎所有的商品化d b m s 都实现了自主存取控制，其中不少系统还提 供了基于强制存取控制策略的安全版本，如s y b a s e ，o r a c l e 等。其中o r a c l e 提供 了u n i x 上的有关b 1 级安全版本和个g e m s o s w 上的a 1 级安全版本，而s y b a s e 则提供了b 1 级和b 2 级两个安全版本。商品化d b m s 安全版提供的满足工业和 商业所需的安全要求的功能包括：用户认证、强制，自主存取控制、与安全相关的 事件的审计、以及基于角色( 安全管理员、d b a 、数据库宿主、般用户等) 的用 户责任等。 可信c o b a s e 即c o b a s ev 2 0 安全版，是国内设计的数据库管理系统m 。 哈尔滨工程大学硕士学位论文 它的安全功能包括自主存取控制、强制存取控制和审计，基本达到了b 1 级标准， 但它在强制存取控制方面还比较简单，也没有处理推理通道和隐蔽通道问题。 另外，华中理工大学达梦数据库多媒体技术研究所和安全技术课题组也基本 实现了b 1 级的多级安全数据库管理系统。 1 3 本文的研究内容 本文全面研究了安全数据库的各个方面以及安全数据库的存取控制机制，并 指出推理通道和隐蔽通道是安全数据库面临的主要威胁。本文提出了针对这些问 题的解决方案。总的来说，本文做的工作主要包括以下几点。 1 介绍了推理通道的概念以及多级数据库中推理通道的研究现状。然后描述了 为某些推理问题而提出的专门的策略，以及关于推理问题的通用的模型，还 有为处理这些问题而开发的一些工具。 2 。提出了一个检测推理通道的算法。该算法使用具有高度表达性的h o r n 子旬来 表达数据库约束，并开发了用于数据依赖和数据独立泄漏的推理算法。 3 提出了使用多实例解决数据库中隐蔽通道的方法，介绍了多实例的概念，以 及在数据库中引入多实例后对传统的关系数据模型的影响，更新操作的语义 以及它们的实现方法。 4 介绍了一个实施b l 级安全的数据库系统的体系结构，安全级的定义和实现， 多级关系和泄漏监控器的实现，以及系统的工作流程。 哈尔滨工程大学硕士学位论文 2 1 引言 第2 章推理通道和隐蔽通道 推理通道是指在数据库中用户可以从低密级的数鼹睢导出高密级的数据。推 理问题m 是指检测和消除推理通道。很明显推理问题对于安全数据库的设计者和 用户来说都很重要。然而到现在为止多级数据库的推理问题研究的还不够深入， 一方面是由于这个问题的难度，另一方面也是因为只有在解决了决定如何存取和 检索多级数据这个相对来说更为基础性的问题之后，才能够实现某种形式的推理 控制“。 隐蔽通道是指系统的一个用户用违反系统安全策略的方式传送信息给另一 用户的机制。在一个系统( 操作系统或数据库管理系统) 中，给定个安全策略模 型m 及其解释i ( m ) ，i 中的任何两个主体i ( 瓯) 和i ( s ，) 间的潜在通信是隐蔽 的当且仅当m 的相应主体只和s 的通信在m 中是非法的。 本章首先描述了一些多级数据库设计阶段的推理通道和消除这些通道的技 术，然后对推理问题进行更为般化的考虑，描述了一般推理问题的形式化模型 和特征。本章也描述了一些已经提出并实现的用于处理数据库中的推理问题的工 具。本章的最后介绍了隐蔽通道，隐蔽通道的分类和特征。隐蔽通道产生的原因 比较复杂，预防起来也 匕较困难，本文主要研究了隐蔽通道在多级数据库中产生 的原因，以及针对它的解决方案。 2 2 特殊推理通道 本节描述了在对数据库安全研究的过程中已经发现的大量的推理通道，还有 一些已经提出来的处理这些问题的技术。 4 哈尔滨工程大学硕士学位论文 2 2 1 基于查询中敏感数据的推理 假定用户向数据库提交了一个查询序列q 。，g ：，q 。，然后用户就可以利用这 些查询的响应信息推出比检索数据密级高的数据。下面通过个例子解释这种情 况。 假定数据在关系级进行分级。有两个关系，一个非密级关系e p ，它有两个属 性：e m p l o y e en a m e 和p r o j e c tn a m e ，还有一个机密级关系p t ，它也 有两个属性：p r o j e c t _ n a m e 和p r o j e c tt y p e ，这里e m p l o y e e _ n a m e 是第一个关系的关键字，p r o j e c tn a m e 是第二个关系的关键字。假定一个用 户做了下面一个s q l 查询： s e l e c te p e m p l o y e en a m e f r o m e p , p t w h e r ee p p r o j e c t _ n a m e 2 p t p r o j e c t _ n a m e 如果这个查询是通过对两个关系e p 和p t 在p r o j e c tn a m e 上进行自然 连接，然后在e m p l o y e e _ n a m e 上进行投影，则虽然返回的只有非密级的数据 ( 雇员姓名) ，但用户仍然可以得到一条推理通道。因此尽管查询的输出是非密级 的，它也泄漏了机密的信息。 下面有一个用户提交的s q l 查询表示了一个类似的问题： s e l e c te p e m p l o y e e _ n a m e f r o m e p , p t w h e r e e p p r o j e c t _ n a m e2p t p r o j e c t _ n a m e a n dp t p r o j e c tn a m e = c s d i 如果仔细的检查上述的s q l 查询，就能很快发现虽然返回给用户的数据的级 别比较低，但是用来执行这个查询的数据却有个比较高的级别。由于这些查询 的条件部分是建立在假定对用户不可见的数据的基础上，所以产生了上面的推理 通道m 。 这种类型的推理通道很容易消除。系统可以通过修改用户的查询使查询仅包 含授权的数据，也可以简单的放弃这个查询。如果用户被许可能看到包含在查询 哈尔滨工程大学硕士学位论文 中的所有数据，那么查询结果就可以返回给他，不过这些数据必须被标记为查询 中包含的所有标记的最小上界。 2 2 2 统计数据库的推理问题 一般的，统计数据库允许用户查询聚集类型的信息( 比如合计、平均值等) ， 但是不允许查询单个记录信息。例如，查询“程序员的平均工资是多少? ”是合 法的，但是查询“程序员张勇的工资是多少? ”就不允许。 在统计数据库中存在着特殊的安全问题，即可能存在着隐蔽的信息通道，使 得可以从合法的查询中推导出不合法的信息。例如下面两个查询都是合法的： 本公司共有多少女高级程序员? 本公司女高级程序员的工资总额是多少? 如果第一个查询的结果是“l ”，那么第2 个查询的结果显然就是这个程序员 的工资数。这样统计数据库的安全性机制就失效了。为了解决这个问题，可以规 定任何查询至少要涉及n 个以上的记录( n 足够大) 。但是即使这样，还是存在 另外的泄密途径，看下面的例子： 某个用户a 想知道另用户b 的工资数额，他可以通过下列两个合法查询获 取： 用户a 和其他n 个程序员的工资总额是多少? 用户b 和其他n 个程序员的工资总额是多少? 假设第1 个查询的结果是x ，第2 个查询的结果是y ，由于用户a 知道自己 的工资是z ，那么他可以计算出用户b 的工资= y 岱劢。 这个例子的关键之处在于两个查询之间有很多重复的数据项( 即其他n 个程 序员的工资) 。因此可以再规定任意两个查询的相交数据项不能超过m 个。这样 就使得获取他人的数据更加困难了。可以证明，在匕述两个规定下，如果想获知 用户b 的工资额，用户a 至少需要进行l + ( s - 2 ) n 次查询。 当然可以继续规定任佣户的查询次数不能超过1 + 州- 2 ) m ，但是如果两个 用户合作查询就可以使这一规定仍然失效。 6 哈尔滨工程大学硕士学位论文 另外还有其他一些方法用于解决统计数据库的安全性问题，例如数据污染。 但是无论采用什么安全性机制，都仍然会存在要过这些机制的途径。好的安全| 生 措施应该使得那些试图破坏安全的人所花费的代价远远超过他们所得到的利益， 这也是整个数据库安全机制设计的目标。 2 2 3 结合元数据从数据中推理 在多级安全数据库管理系统w n n 中产生的许多推理通道是由于将从数据库中 检索的数据和用于存储和检索的元数据相结合产生的，尤其是对于完整性约束。 在一个比较低的安全级上的用户可以利用低安全级的数据和约束的信息( 如果这 对用户来说是可以得到的) 来推出也同样受约束影响的高安全级数据的信息。在 这一节中将会考虑数据库中用到的一些类型的元数据，并且显示它是如何被用来 帮助产生推理的。 实体完整性关系模型最基本的完整性需求之一就是实体完整性，它要求关 系的每一个元组必须有一个唯一的键。当数据在关系一级或列一级进行分级时， 这种约束不会引起问题，因为在这种睛况下一个关系的所有的键都在相同的安全 级上。但是当一个低安全级的用户想要在一个关系里插入一个元组( 在这个关系 里数据在元组或元素级进行分级) ，如果这个关系中已经存在一个具有相同键的高 安全级的元组，那么为了维护实体完整性，d b m s 必须删除这个己经存在的元组 或者是通知用户一个具有相同键的高安全级的元组已经存在。选择任何一种方法 都会有问题。在第种情况下，低级用户的动作能够导致高级用户插入的数据被 删除，这是不可接受的。在第二种情况下，就产生了一条推理通道，高级数据的 存在影响了低级数据的存在，低级用户由此可以推出高级数据的存在。 为了迸一步阐述，考虑下面的实例( 这里“n a m e ”是关系的主键，l a b e l 是 元组的标记) ： 表2 1 一个关系实例 7 哈尔滨工程大学硕士学位论文 假定个非密级的用户想要插入记录( w o m b a t ，n o f f o l l ( ，n u c l e a r ) 。如果选 择保护实体完整性，则必须删除这个保密的元组或者是拒绝这个插入。如果删除 这个保密的元组，就可能遇到完整性问题( 因为有可能在这个插入的非密级元组 里，元素“n o f f o l k ”只是用于掩盖真正的密级元素“p e r s i a nc “f j ) 。如果拒绝这 个插入，那么这个低级的用户就能够得出一个推理。 这个问题可以通过多实例解决。在多实例的情况下，这两个元组都允许存在。 多实例和它的作用将在第四章中进行详细讨论。 函数和多值依赖s u 和o z s o y o 百u “考虑了比前一节讨论的更为通用的情 况，他们研究了由于关系中属性之间的函数和多值依赖约束而引起的推理通道。 下面的例子说明了如何应用函数依赖来产生推理通道。 假定一个公司的数据库中包含了关系模式e m ps a l ，它有三个属性： n a m e ，r a n k 和s a l a r y 。属性n a m e 和r a n k 被认为在数据库中是不敏感 的，而属性s a l a r y 被认为是敏感的( 因此，标记要被加在列级上) 。假定每一 个雇员都知道这条规定：级别相同的雇员具有相同的薪水。在这种情况下，一个 被禁止访问敏感数据的雇员能够很容易的推出别的雇员的薪水，而薪水是敏感的。 如果仔细的检查一下上面的例子，就能够发现它之所以包含一条推理通道是 因为在确定属性r a n k 和s a l a r y 的安全级别时，没有仔细的考虑过如何把函 数依赖r 暇哼s a i 。a r y 反映出来。如果一个用户知道一个雇员的级别的话，那 么这个雇员的薪水也同时被这个用户获知。在这种情况下避免这个问题的方法就 是将属性r a n k 的级别从非密级提升到机密级。如果属性能够被以一种与函数依 赖一致的方式加上安全标记，那么这些问题就能够被解决了。 s u 和o z s o y o u 给出了好几个算法用来基于属性间的函数和多值依赖提升属 性的分级标记。其中有一个是以一个属性列表、属性的分级标记以及能够引起推 理通道的函数依赖的集合作为输入。这个算法输出另个属性列表以及它们的分 级标记( 可能与输入时指定的标记不样) ，并且这个新的列表可以免于由于函数 依赖而引起的推理问题。 值约束值约束是种对于包含个或多个数据项的数据值的约束。如果一 个约束被定义在具有不同安全级别的数据上，就可以利用这个约束导出推理通道。 哈尔滨工程大学硕士学位论文 假定个属性a 是非密级的而属性b 是机密级的。假设在数据库中强加了一 个约束a + b 2 0 。这对于非密级用户来说也是可用的。b 的值不直接影响a 的 值，但是它确实影响了a 可能取的值的集合，因此就有了一条推理通道。这个问 题通常的解决方案就是仅允许这样的约束被定义在具有单个安全级别的属性上。 如果一个约束被定义在几个安全级别上，那么j 炙有必要把它分解成几个单级别的 约束。比如说，约束a + b 2 0 可以被分解成a 1 0 且b l o 。 分级约束一个分级约束是一个规则，它描述了对数据进行分级的标准。如 果这些分级约束被用户获知的话，也可以从这些约束自身推导出敏感数据。考虑 下面的例子。 假定下面的完整性约束被强加到一个数据库上，该数据库包含了 m e d i o c r a t e s 是雅典人这样一个事实。 每个人都是一个雅典人，毕欧钦人，科林斯人，或多里安人。 所有的雅典人和科林斯人都是爱好和平的。 所有的毕欧钦人和多里安人都是崇尚暴力的。 m e d i o c r a t e s 不希望被人知道他是爱好和平的。f i h i n o l o g u s ，一个公认的坏 蛋，试图从一个不论什么时候只要答案涉及到完整性约束就拒绝回答的系统中发 现m e d i o c r a t e s 的信息。于是他就开始问系统： r h i n o l o g u s ：m e d i o c r a t e s 是雅典人吗? s y s t e m ：我不告诉你。 r h i n o l o g u s ：他是一个毕欧钦人吗? s y s t e m ：不是。 r h i n o l o g u s ：他是科林斯人吗? s y s t e m ：不是。 r h i n o l o g u s ：那么他是多里安人吗? s y s t e m ：我不告诉你。 r h i n o l o g u s 注意到m e d i o c r a t e s 正在试图隐藏自己。因为如果他不是一个雅 典人，那么这个系统将早就对第一个问题回答“不是”而不用隐藏这个答案。因 此n e d i o c r a t e s 肯定是个爱好和平的雅典人。 9 哈尔浜工程大学硕士学位论文 s i c h e r m a n 、d e j o n g e 和v a n d e r i e t t 6 嗜虑了当分级约束被知道或不知道的情况 下如何保护机密信息的问题。f 岍 定义了一大堆条f 牛用于判断是否拒绝回答一个 问题，并且基于这些条件描述了一个策略集合。然后他们就开发了一个正式的带 有安全规则的安全数据库的模型，并且证明了依赖于分级约束是否被获知什么是 安全的响应。 s i c h e r m a n 、d ej o n g e 和v a nd er i e t 提供的结果是相当悲观的。f 电f 门显示在特 定睛况下，如果分级约束被知道的话，想要保密一个值唯一安全的策略就是要求 对于这个元组的值的任何查询都应该被拒绝。这就是f 也f 门策略的一个僵化的结果： 他们的每一个策略都采用了一组随着时间的过去一致的标准。因此不可能一开始 采用种更加灵活的策略，后来随着机密值选项数目的减少转向一种更加严格的 策略，如同在一些统计数据库中做的那样。然而，他们的结果因为它们极端的通 用性还是非常重要的：它是用于所有的数据库和所有的推理系统，因此可以被用 作进一步研究这个问题的基础。 2 3 推理问题的一般特征 前一节讨论了某些特定的推理通道，他们能够很容易的被特征化，并且有相 对简单的解决方案。但是阻止一般的推理通道并非都是如此简单。作为一个相关 的案例，考虑下面的来自于s t a n i s l a wu l a m 的一个数据家的历险中的两个故 事。这个故事是关于美国政府在二战期间企图保密“曼哈顿计划”的存在和它的 位置： 最后我知道我们准备去新墨西哥，去一个离s n a t af e 不远的地方。从来没听 说过新墨西哥，我去图书馆借了本联邦作家规划编写的去新墨西哥的导游书。在 这本书的最后，在借阅者签名的卡片上，我看到了j o a n h i n t o n ，d a v i df r i s c h ，j o s e p h m c k i b b e n 的大名，还有其他的一些曾经神秘消失的去从事秘密的战争工作而没有 说去那的人。我无意中揭开了他们的目的地，以种最简单的和没有想到的方式。 这等于说几乎不可能在战争期间保持绝对的机密和安全。 这使我想起了另外一个故事。因为我跟s t e b b i n s 很熟，在到达l o s a l a m o s 哈尔滨工程大学硕士学位论文 个月以后，我给他写了封信。我没说我在那，但是我提起了在一月份, u _ - j q 份 我曾经在地平线上看到过老人星。后来我突然想到对于一个天文学家来说他能够 很轻松的推出我的纬度因为这颗星在南半球高于3 8 度是不可见的。 这些故事中有几件重要的事情值得注意。首先，在推出他神秘消失的同事的 目的地的过程中，u l a m 没有使用标准的逻辑推理。相反，他找到了这个事实最好 的解释就是他们都查阅过去相同地方的导游书。其次，尽管u l a r n 能够从这本导 游书中推出他朋友的目的地，他并不知道去查找这本导游书，除非他早已得知了 某些敏感信息：他自己将要去工作的工程的位置。如果他不知道这个信息的话， 他可能不得不在图书馆里查找每一本导游书以找出“曼哈顿计划”的确切位置。 第三，u l a m 也需要某些相对来说不敏感的信息进行他的推论，也就是，他知道他 的某些同事离开去参加一项看起来 卧十秘的政府工程。最后，并不总是可能预测 出用户知道的什么信息能够被用来推导出某些结论，也许他用到的都是些明显不 敏感的信息；这是老 、星和纬度3 8 度的故事的结论。 可能最早的推理问题在数据库中的形式化描述是由g o g t m n 和m e s e g u c f 一做 出的。考虑一个数据库，每一个数据项都被指定一个访问级别，并且假设访问级 别的集合是偏序的。定义关系寸如下：给定数据项x 和y ，x _ y 表示可能从x 推 出y 。关系一是自反的和传递的。集合s 是推理封闭的，如果x 属于集合s ，并 且x 专y 成立，则y 也属于s 。对于一个访问级别l ，让e ( l ) 表示由所有可能的访 问级别小于或等于l 的响应组成的集合。如果e ( l ) 不是推理封闭的，那么就存在 一条推理通道。 g o g u e n 和m e s e g u e r 没有提出关系斗的任何候选方案。他们只是要求它是自 反的和传递的，并且说它可能根据某个推理规则的集合产生：比如说，一阶逻辑、 统计推理、非单调逻辑、基于知识的推理等。然而f i 乜们确实提到了对于大部分感 兴趣的推理系统，决定a b ( 这里a 是事实的集合，b 是一个事实) 最好是半决 定盼电就是，有个算法，如果a b ，它将在有限时间内给出答案，否则的 话它将永远不会停止。t h r u a i s i n g h a m m 进一步考虑了多级数据库中推理关系的复 杂性理论性质。 g o g u e n 和m e s e g u e r ，除了没有专注于任何推理系统或者推理系统的集合，还 哈尔滨工程大学硕士学位论文 留下了好几个问题没有考虑。比如说，他们没有考虑可能存在于数据库之外的信 息对推理问题的影响( 比如说在上面引用的老人星的例子里) 。他们也没有尝试测 量计算这个推理的难易程度。下面的工作将讨论这些问题。 在对g o g u e n 和m e s e g u e r 的定义进行精炼的过程中，d e n n i n g 和m o r g e n s t e r n 从传统的信息理论抽取推理关系。给定两个数据项x 和y ，让h ( y ) 表示y 的不确 定性，让。( ，) 表示给定x 以后y 的不确定性( 这里不确定性是以传统的信息论 的方式定义的) 。因此，给定x 之后y 的不确定性的减少量可以如下定义： i n f e r 仅_ y 1 ：垒塑二堡塑( 2 1 ) 。h ( y ) 式中：i n f e r ( x 哼y ) 给定x 以后y 的不确定性的减少量 日( y ) y 的不确定性 日，( y ) 给定x 以后y 的不确定性 i n f e r ( x - + y ) 的值介于0 到1 之间。如果值等于0 ，那么不可能从x 推出y 的任何信息。如果值在o 到l 之间，那么给定x 就有可能推出y 。如果值是1 ，那 么给定x 就肯定能推出y 。 i n f e r 关系可以如下使用：绘定个e 0 ，定义一个数据集合( 或内核) 的 影响域为存在一个内核元素x ，满足i n f e r ( x y ) 的数据项目y 的集合。一 个系统是推理安全的，如果对于每个安全级c ，所有安全级小于等于c 的数据 项的影响域不包含任何具有更高的或不可比的级别的数据项。 注意，不像g o g u e n 和m e s e g u e r 讨论的推理关系，影响域关系是非传递的。 比如说，知道某个人住在那条街可以减少关于那个人的不确定性，知道某个人正 在参加一项工程可以减少关于那项工程的性质的不确定性。但是知道正在参加某 项工程的某个人住的街的名字并不能使关于那项工程的不确定性减少点。 这个公式有用是函为它显示了推理不是一个绝对的问题，而是个相对的问 题。它给出了一种方式丈量非法信息流的带宽。另一方面，d e n n i n g 和m o r g e n s t e m 也指出了它的潜在的退步性i m ： 1 在大部分情况下，判断日。( ，) 的值是很困难的，甚至是不可能的。 2 它没有考虑得出推理的计算复杂性。 1 2 哈尔滨工程大学硕士学位论文 为了阐述第2 点，f 电 门给出了下面的来自于密码学的例子：只要你试过了所 有的密码，原始文本肯定能够从密码文本中推导出来( h ， ) = 1 就是这种情况) 。 然而实际上这几乎是不可能的。 2 4 处理推理通道的工具和技术 这一节将讨论已经提出来的各种各样的技术和工具。它们可以帮助查找推理 通道，并且一旦发现了将阻止它们继续被利用。基本上已经提出两种技术可以查 找和消除推理通道。一种就是在数据库设计时用语义数据模型技术检测推理通道， 然后重新设计数据库使这些通道不再存在。另外种就是评估数据库的事务( 包 括读事务、写事务和读写事务) ，判断它们是否能导致非法推理。如果刮门确实能 导致非法推理，那么这个查询要么被拒绝要么被重新定级为更高的级别。 关于语义数据模型方法的例子可以在h i n k e 有关a s dv i e w s 工程“”的工作中 找到。他的工作描述了构建一个语义关系图来表达数据库中可能的推理。数据项 被表示为节点，它们之间的关系由连结节点的边表示。一个关系可能会也可能不 会被定级。如果从结点a 到结点b 有两条路径，并且从一条路经可以看到所有的 边，而从另外一条路经则不能，我们就说可能存在一条推理通道。一旦发现了这 样一条推理通道，可以进一步分析看它是否是一条真正的推理通道。如果是，我 们可以提升一条边或多条边的级别，如果可能的话。这个过程将持续下去直到所 有的推理通道被关闭。 这种技术非常简单。没有对数据项之间的关系的性质做任何假定，除了它们 存在或不存在。举例来说，如果a 蕴含b ，那么就可以假定存在一条推理路径， 不仅仅是从a 到b ，而且也可能从b 到a 。因此看起来主要的危险在于数据之间 是高度关联的，在这种情况下将会发现大量的推理通道，数据库设计者不得不花 费大量的时间来消除它们。 s m i t h m , - ，提出了一种新的使用语义数据模型的模式，它允许用户表达不同类 型的关系。在s m i t h 的系统中，定义了大量的可能类型的数据项和它们之间的关 系。这些数据项包括抽象类、属性、标识符、关系、外部的标识符、概括和不相 1 3 哈尔滨工程大学硕士学位论文 交的子类。这些项中的任何一个都可以被分级。因此，如果我们希望隐藏员工和 工资之间的关系，只需要提升这个关系的级别，而员工和工资都可以是无级别的。 上面描述的方法被用来支持数据库的设计和分级，还有别的研究者考虑使用 一些工具来评估查询。m a z u m d a r ，s l e m p l e 和s h e a r f f 。1 提出了一个能够评估事务 的安全| 生的系统。他们使用一个定理证明器来判断是否某个预定义的机密信息能 够从数据库的完整性约束、事务的前提条件和输入事务的数据的类型中提取出来。 因为他们的技术不依赖于存储在数据库中的任何特定的数据，所以他们能够在事 务编译的时候应用到一个事务上，因此它们能眵被用来判断某种类型的事务的安 全级别。m a z u m d a r 也指出他们的技术能够被用来测试数据库的安全性，并且给 出重新设计使之更安全的方法。 l o c kd a t av i e w s ( l d v ) w 工程使用了另外一种方法。分级约束被定义在一组数 据上，它是根据可以从数据库推出的信息的级别确定的。当一个查询被提交给系 统时，查询结果将根据分级约束被升级到合适的级别上去，然后再交给用户。可 以在系统中包含一个推理控制机制以便于分级约束可以基于查询分析的结果，也 可以利用历史机制防止用户随着时间的过去收集可以推出敏感数据的信息。因此 如果a 和b 一起能够推出c ，这里c 是敏感的而a 和b 不是，假定一个低级用 户早已经看到a ，根据安全策略我们就可以阻止j 塞价用户看到b 或者阳i e 任何低 级用户看到b 。 t h u r a i s i n 蛐m 描述了一种方法使用查询修改。一个查询首先被评估以决定 它是否会导致推理通道，如果会的话，它将被转换成一个不会导致推理的查询。 这样一种方法对用户来说是有用的，因为系统不仅阻止了用户做非法查询，它也 可以帮助他做合法查询。然而，这样一个系统必须被仔细的实现，因为个用户 可能使用合法查询区别于非法查询的方式形成推理。 在处理查询时检测推理也有它的不足。正如前面所说的m ，有可能需要保存 以前访问的历史，并且在评估一个查询的安全级别时使用这个历史，所以就防止 了低级用户通过使用重复的查询积累起来的低级信息推出高级信息。在某些环境 中，这可能使系统容易遭受拒绝服务攻击：制氐级用户能够阳i e 其他低级用户 访问其所需要的数据，因为，与这些需要的数据结合起来，将会导致一个推理攻 1 4 哈尔滨工程大学硕士学位论文 击。 虽然如此，这种方法可能在某些特定的应用里有用。首先，在许多情况下为 查找非法信息流而查找整个数据库是异常昂贵的。但是评估一个特定的查询稍微 容易点。此外，在更新时增加新的数据可能引起新的非法推理，这些推理最好在 更新的时候检查：一个查询时推理检测器可能有益于检测这样的推理。 2 5 隐蔽通道 隐蔽通道包括存储隐蔽通道与定时隐蔽通道。如果隐蔽通道的实现是通过一 个主体直接或间接地写一存储位置，然后另一个主体直接或间接地读取这一存储 位置，这种隐蔽通道就被称作是存储隐蔽通道；如果隐蔽通道的实现是通过个 主体调整自己对系统资源( 如e p u 时间等) 的使用时间影响另一个主体的实际响 应时间，从而发送信息给另一主体时，这种隐蔽通道则被称作是定时隐蔽通道。 系统中存在既是存储隐蔽通道又是定时隐蔽通道的通道，隐蔽通道往往通过 系统原本不用于数据传送的系统资源来发送信息，并且这种通讯方式往往不被系 统的存取控制机制所检测和控制。存储隐蔽通道采用符合其编码方式的对某存储 位置的处理来发送信息，即发送者更改系统的某个共享资源属性而接收者能检测 到这种更改。定时隐蔽通道则是通过改变其经历的时间来影响另一用户的系统响 应时间而传送信息。尽管高安全级的用户有可能利用隐蔽通道给低安全级的用户 传送信息，但是隐蔽通道的主要的潜在威胁在于它有可能被特洛伊木马所利用。 图2 1 举例说明系统中存在的利用并发控制上锁机制的隐蔽通道使用场景。 用户h 用户l 图2 1 利用并发控制上锁枫制的隐蔽通道 1 5 哈尔滨工程大学硕士学位论文 假设在上述的d b m s 中存在两个不同安全级的用户( 主体) 之间的非法通信，即 高安全级的用户可以发送信息给低安全级的用户。假定有一个高安全级的用户h 可以查询某个表a ，另一州氐安全级的用户l 可以更新某个具有与l 相同的安全 级的表a 。为方便说明，我们假设这两个用户间可共同操作的表只有a ，且此时系 统中只有两个用户在工作。现在将h 和l 操作a 分为以下两种情形： 1 h 发出一查询请求：s e l e c t f r o ma 然后h 又作了其他操作，没有提交； 在这期间，l 发出一更新请求：u p d a t eas e t w h e r e ；然后提交结束 事务的执行。此时l 处于提交等待状态，我们将这种情形编码为1 2 h 不发出查询请求：s e l e c t f r o ma ；而是作了其他操作，在这期间，l 发 出一更新请求，u p d a t eas e t w h e r e ；然后提交结束事务的执行，此 时l 提交成功，我们将这种情形编码为o 。 由此可见，如果l 可以测量每一次正常提交事务的时间，h 就能够向l 成功 地传送l 位数据，这种数据传送方式在系统的安全策略的解释下是非法的。h 通 过读表a ，修改了表a 的锁属性，而l 也通过写表a 查看到h 是否修改了表a 的 锁属性，从而达到了传送数据的目的。h 通过改变占用系统资源的使用时间影响 了l 的响应时间，因此是一个定时隐蔽通道。 本文将主要研究存储隐蔽通道，即由于高级用户和低级用户同时读写某个表 而产生的隐蔽信号通道。并且给出这个问题的解决方案：引入多实例。本文的第 四章将详细的介绍多实例以及多级数据库的更新语义w 。 2 6 本章小结 本章提出了各种各样的方法来处理数据库中的推理问题。首先描述了某些特 定类型的推理问题，并且对各种消除推理的方法进行了归纳。进而描述了一些通 用的模型，以及实现这些模型的工具和方法论。本章的最后也对隐蔽通道作了简 要的介绍。 推理问题是数据库安全中一个非常重要的但是仍然相对来说还没有解决的方 面。要实现个完全的和通用的推理问题的解决方案是不可能的。然而，假设将 1 6 哈尔