多级安全数据库中的推理问题一直是数据库安全领域的重要研究内容。推理问题描述的是低安全级别的用户可以通过推理的方法从低安全级别的信息中得到高安全级别的信息。通常，低级用户都是通过一系列的查询来完成推理的。例如，假设支持某个项目的公司信息是高安全等级的，但用户可以访问诸如项目、参加会议的人员以及人员所属的公司等信息，这样用户就可以推断出每个公司具体支持哪个项目。
　　在处理推理问题时存在着柔性访问和响应时间" title="响应时间">响应时间的内在平衡。在决定是否授予一个用户查询权限时，为了阻止多个用户合作进行推理，不仅需要考虑该用户，而且需要考虑具有相同安全等级的所有用户以及他们的所有查询，这个特性称为防共谋。这个特性强化了推理问题的复杂性，因为这个特性需要一个新的推理控制方法。该推理方法能够区别在一个推理通道中的n个用户、每个用户访问" title="用户访问">用户访问m－1个对象的情况和n(m－1)个用户、每个用户访问1个对象的情况。
　　国内外有许多学者进行推理控制方面的研究，并取得了丰富的成果。在参考文献^[1]中，FRANCIS CHIN提出了关于统计数据库的推理控制方法。在参考文献^[2]和^[7]中Su和Ozsoyolu以及吴恒山等提出了关于函数依赖和多值依赖的推理控制方法。在参考文献^[3]中Xiaolei Qian等提出了基于语义网络的推理通道的检测方法。在参考文献^[4]中R.Yip和K.Levitt提出了基于推理规则的推理控制方法。在参考文献^[5]中M.Stickel提出了基于最大" title="最大">最大信息共享的推理控制方法。以上这些都是设计期推理控制方法和推理通道检测方面的研究。在查询期的推理控制方面，一直以来都是集中在研究基于用户的查询历史的控制方法。2003年Staddon提出了动态推理控制的方法^[6]。本文提出一种基于标记的动态推理控制方法。该方法使用访问标记来控制查询过程，因此又称为标记方法。该方法能够有效预防共谋而且易于实现。与参考文献^[6]的方法不同，这种方法在解决推理问题并保持快速查询处理的同时，还能够保证用户的最大访问能力。
1 相关定义和定理
　　定义1 对象：数据库中存储的信息单元，例如事实、属性或者关系等。本文中以O表示对象。
　　定义2 推理通道：由完成一次推理所必需的对象组成，由n个对象组成的推理通道称为n－通道。
　　定义3 防共谋策略：设c为一个整数，0〈c≤n。对于一个推理控制策略，如果c个用户共谋也无法查询到任一推理通道上的所有对象，则称此策略为c防共谋策略。
　　定义4 拥挤控制：如果存在用户访问一个推理通道中的对象数量达到最大对象数量(m个对象中的m－1个)，则没有用户可以通过查询完成这个推理通道。
　　定义5 拥挤控制：设0〈ε〈1，U表示任意一个用户。对于一个c防共谋策略，如果c个用户中的多于x组的用户共同访问了m－通道{O₁，……O_m}中的m－1个对象：，用户U能访问剩余对象{O₁，……O_m}-{}的概率小于ε，则称该策略具有(x，c，ε)拥挤控制。
　　定理1 设0〈ε〈1，采取c防共谋策略，q为标记数量。如果这个策略具有(x，c，ε)拥挤控制，则：
　　

　　引理1 设0〈ε〈1，如果个用户，每个用户的访问对象数量都已经达到了m－通道的最大对象数量，则不属于x个用户中的用户U能够同样访问m－通道中对象的数量可以达到最大对象数量的概率大于1-ε。
　　定理2 设0〈a〈1，如果可以达到最大对象数量的用户的数量为，则其他用户可以访问任何个对象的概率大于1-ε。
　　引理2 如果个用户最多可以访问m－通道，则其他用户可以访问m－通道中个对象的概率为1。
2 基于标记的动态推理控制方法
　　在这个方法中，首先需要产生访问标记的集合，这个集合由系统的标记生成算法自动产生。每个标记拥有对象关联的信息。标记集合中标记的数量由推理通道的长度决定。用K来表示标记集合。本文提供了两种标记方法：(1)标记集合仅由数据库系统使用，因此用户不必保留任何标记；(2)每个用户都有一个秘密标记。在初始阶段，推理通道中的所有对象都与标记集合中的全部或者部分标记相关联。当一个查询处理算法使用一个标记访问一个对象时，其他访问也使用相同的标记访问这个对象，这要通过删除该对象与其他标记之间的关联来实现。通过这样的方法，可以确保最大限度的柔性访问控制(用户可以自主决定访问的对象并且可以访问推理通道中的任何对象，只有其中的一个不能访问)。在这个方法中，响应时间由推理通道的长度而不是用户的查询历史决定，从而实现了快速查询处理。此外，所有的标记都是不同的，不同的标记不能用来访问相同的对象。在后面的讨论中将介绍如何通过该特征防共谋。
　　这种方法分为两部分：第一部分是标记的初始化；第二部分是查询处理，详细说明查询的算法。初始算法只需要运行一次(除非整个系统需要更新)，而查询处理算法只需要在用户访问对象的时候运行。
2.1 单一推理通道的简单情况
　　首先考虑数据库中只有一个推理通道的情况。m表示推理通道的长度。推理通道中的对象由O₁，……，O_m表示。U表示数据库中的一个用户。
　　对象O与由K(O)表示的标记集合相关联。在简单的方案中，全部标记的数量为m－1，标记的集合K={k₁，……，k_m-1}，推理通道中的每一个对象都与全部m－1个初始标记相关联，K(O_i)=K，i=1，2，……，m。
　　查询处理如下：当一个用户试图访问一个对象时，算法将任意选择一个标记，同时删除这个标记与推理通道中其他对象的关联。当所有m－1个标记都被使用时，推理通道中的m个对象中的m－1个对象已经与标记关联。但是，推理通道中还有一个对象没有与任何一个对象所关联。这个对象称为“保留对象”，这意味着没有用户可以访问这个对象。一旦“保留对象”被认定，系统将为其指定一个指示器。在这种情况下，没有用户可以访问保留对象。换句话说，用户可以访问推理通道中除了保留对象之外的全部对象。因此，一组用户试图进行共谋推理是没有意义的。现在通过下面的算法给出该方法的形式化描述。这个算法由标记初始化算法和查询处理算法组成。K表示由m－1个标记组成的标记集合。
　　算法1 单用户访问对象O_i的单个通道方法
　　初始标记
　　K(O_i)=K，i=1，……m；
　　查询处理
　　输入：I；输出：是否允许进行查询。
　　步骤：(1)如果标记集合为空，则禁止访问；(2)在标记集合中任选一个标记；(3)将这个标记赋予查询对象；(4)将这个标记从标记集合中删除；(5)将这个对象指派给这个用户；(6)返回允许查询。
2.2 无重复对象的多推理通道情况
　　对于数据库中有多于一个推理通道的情况，解决方法是为每个推理通道制定一个标记集合。C表示一个推理通道，l表示数据库中推理通道的数量，推理通道为C1，……，CI，C_j的长度由m_j(j=1，……，l)表示，mmax表示所有推理通道中的最大长度。在这部分中，仅考虑所有推理通道彼此区分开的情况。在这种情况下，标记集合K中有mmax－1个标记。
　　查询处理算法与单个推理通道中的相应算法相似。主要区别是标记集合的初始算法。
　　初始状态下，对通道C_j，k_j由K中任意选择的m_j-1个标记组成，j=1，2，……，l。如果O_i∈C_j，则K(O_i)=k_j。
　　算法 2 用户访问O_i的可区分多通道方法
　　初始标记
　　(1)k_j={K中任意选择m_j-1个标记}，j=1，2，……，l。
　　(2)如果(O_s∈C_j)，则对所有可能的s，{K(O_s)=k_j；}
　　查询处理
　　输入：I；输出：是否允许进行查询。
　　步骤：(1)如果找不到j满足对象O_i∈C_j，则转(8)步骤；(2)如果标记集合为空，禁止访问；(3)在标记集合中任选一个标记；(4)将这个标记赋予查询对象；(5)将这个标记从标记集合中删除；(6)将这个对象指派给这个用户；(7)返回允许查询；(8)返回信息未找到。
2.3 有重复对象的多推理通道情况
　　最后，考虑一些对象在多个推理通道中重复出现的情况。查询处理分为两种不同的情况：一种情况是重复的对象在任何通道中都不是“保留对象”。在这种情况下，对重复对象的访问与其他对象相同。另一种情况是用户试图访问的重复对象是“保留对象”，这种情况下的访问请求将被系统拒绝。
　　解决这类问题应使用如下算法。标记集合的初始算法与2.2小节中介绍的相同。所使用的标记的数量是mmax－1。对于重复对象，其标记的数量等于它在所有推理通道中出现的频率。这里使用k_j(O_i)表示通道C_j中对象O_i的标记集合。
　　算法3 用户访问O_i的多通道方法
　　初始标记
　　(1)k_j={K中任意选择m_j－1个标记}，j=1，2，……，l；
　　(2)对所有可能的s，如果(O_s∈C_j)，则k_j(O_s)=k_j，j=1，2，……，l。
　　查询处理
　　输入：I；输出：是否允许进行查询。
　　步骤：(1)如果对象不属于推理通道，则转(8)步骤；(2)如果标记集合为空，则禁止访问；(3)对每一个拥有该对象的推理通道，任意选择一个标记集合中的标记,依次执行(4)～(7)步骤；(4)将这个标记赋予查询对象；(5)将这个标记从标记集合中删除；(6)将这个对象指派给这个用户；(7)返回允许查询；(8)返回信息未找到。
　　假设一个推理通道中存在一个重复对象并存在一个保留对象。为了阻止用户在其余推理通道中得到这个保留对象的信息，需要同步考虑这个对象在所有包括这个对象的推理通道的情况。具体方法是：在重复对象被用户访问之后，在所有包含这个对象的推理通道中都将给这个对象分配一个访问标记。如果在一个推理通道中一个重复对象被确认为保留对象，则在所有包含这个重复对象的推理通道中这个对象都被确认为保留对象。
3 性能分析
　　为了解决推理问题，必须考虑三个因素：(1)安全性：无论单个用户还是多个用户联合，通过推理都不能得到其不能访问的信息。(2)柔性访问：在对推理进行严格控制的基础上保证最大的信息共享。(3)响应时间：查询处理时间需要满足应用的要求。
　　在本方法中，同一安全等级下的所有用户都可以访问推理通道中的m－1个对象。因此对于用户来说，无论单独或者联合进行推理都不能获得足够的推理信息。同时由于用户最多可以访问m个对象中的m－1个对象，从而实现了柔性控制。标记的数量由通道的最大长度决定，而且所占存储空间很小。响应时间与不考虑推理问题的情况基本相同。
　　表1给出了Staddon的动态推理方法^[6]和本文方法的比较。