一种访问控制系统用户授权查询请求问题的快速求解方法

摘要

本发明提供一种访问控制系统用户授权查询请求问题的快速求解方法，应用于访问控制领域。本发明将zchaff引入到RBAC系统中，首先通过静态裁剪缩小所需考虑的请求权限的规模，然后通过预处理削减不包含请求权限的角色的数量，最后将该问题连同RBAC系统状态及安全约束转化为合取范式，继而通过调用SAT求解器zchaff以获取高效的计算效率。本发明建立在现有RBAC系统状态下，为用户授权查询请求问题提供高效的求解效率，既保证了安全性，又有较好的可扩展性。

说明书

技术领域

本发明涉及访问控制领域，具体涉及一种基于zchaff的RBAC系统用户授权查询请求问题的快速求解方法。

背景技术

网络和信息技术的快速发展使得我们可以通过网络应用共享资源和服务，有效地提高了数据的利用率。然而，网络自身的开放性、匿名性、数据传输透明性等特征对保障信息的机密性和完整性提出了许多新的挑战，严重阻碍了网络技术的进一步普及和应用。访问控制是保证网络安全最重要的核心技术之一，它允许被授权的主体对某些客体的访问，同时拒绝向非授权的主体提供服务。

基于角色的访问控制RBAC(Role Based Access Control)这一概念最早由Ferraiolo等人于1992年提出。RBAC策略的基本思想是通过引入角色这一中介，权限直接指派给角色而不是指派给用户，用户通过角色指派从而间接获取对客体的操作权限，实现了用户与权限的逻辑分离。驱动RBAC发展的动力是在简化安全策略管理的同时，允许灵活地定义安全策略。这一优点使得在过去的二十年中，无论是RBAC理论研究还是实际应用都有了很大的发展。目前，RBAC已被广泛应用到各个领域，包括操作系统、数据库管理系统、PKI、工作流管理系统和Web服务等领域。

用户授权查询请求UAQ(User Authorization Query)问题是RBAC系统中的一个关键问题，即在某个会话中，用户请求授予一个完成某项特定任务所需要的权限集合，问题的关键在于如何寻找一个优化的角色集合，用户激活该角色集合从而能够得到所请求的权限集合。该问题在复杂的协同系统中十分普遍，例如，在一个基于web的RBAC系统中，用户‐角色指派关系的建立基于用户证书。假设在某个会话中，一名用户需要获得一组特定的权限集合以完成某项特定的任务，系统必须依据该权限集合寻找一组可被激活的角色集合，使得激活该角色集合从而能够获取用户所需的权限集合。在理想情况下，选定的角色集合恰好能够满足用户需要的权限集合，即没有多余的权限，亦没有缺失的权限。但是，在很多时候这种理想情况可能并不存在。因此，找到一组尽可能接近于用户所需要的权限的角色集合是非常必要的。一种解决思路出于安全性考虑，在不允许存在任何超出用户需求的权限的前提下，所激活的权限集尽可能多的接近所请求的权限集。另外一种解决思路则是强调可用性，在保证包含所有请求的权限集的前提下，尽可能减少多余权限的数量。

发明内容

本发明提供一种访问控制系统用户授权查询请求问题的快速求解方法，并为用户提供可自主设定问题求解的目标，提供了很好的灵活性。

本发明采取的技术方案是，包括下列步骤：

步骤(1)用户请求登录系统；

步骤(2)系统接收登录请求用户的属性证书；

步骤(3)系统利用公密钥机制验证属性证书的真伪，若鉴定证书为伪造，则结束；否则，系统从属性证书中获取用户的合法身份信息，进入步骤(4)；

步骤(4)判断用户输入的角色层次结构是否为平坦分布方式，若是则进入步骤(5)，否则将其转化为平坦分布方式；

步骤(5)用户输入所请求访问的权限集合的上限和下限；

步骤(6)设定安全约束以及用户的安全目标；

步骤(7)对用户输入数据进行合法性判断，如果合法则进入步骤(8)，否则返回步骤(5)；

步骤(8)通过静态裁剪缩小所需考虑的请求权限的规模；

步骤(9)通过预处理削减不包含请求权限的角色的数量；

步骤(10)通过调用外部程序对用户所给出的用户授权查询请求进行计算，首先用户所请求的数据会被外部程序转化成合取范式的格式，并被保存在当前程序的根目录下，然后再通过调用zchaff求解器来计算合取范式，根据求解器返回的值再进行相应的转换，并反馈回用户当前可激活的角色数量，以及可激活的权限数量；

步骤(11)返回计算结果，并对计算结果进行相应处理并最终反馈给用户；

步骤(12)判断用户是否结束系统，如果选择是则系统结束，选择否则转入步骤(5)。

本发明一种实施方式是：在步骤(4)中，当判断用户输入的角色层次结构不为平坦分布方式，依照如下方法将用户设定的角色层次转化为平坦分布方式：

当满足以下条件时：

r_m和r_n分别表示编号为m和n的两个角色；

$>\forall r_m,r_n(r_m\ge r_n)\in H\to \left(r_m{\ge }_i{r}_n\right)\in \mathrm{HI}$>

将一种单调的I-层次(高级角色自动继承低级角色的所有权限，记为≥_i)HI称为H(H表示混合层次：记为≥)的I分解；

当满足以下条件时：

$>\forall r_m,r_n\left(r_m{\ge }_a{r}_n\right)\in H\to \left(r_m{\ge }_a{r}_n\right)\in \mathrm{HA}$>

$>\forall r_m,r_n(r_m\ge r_n)\in H\to \left(r_m{\ge }_a{r}_n\right)\in \mathrm{HA}$>

将一种单调的A-层次HA(高级角色能够激活低级角色，记为≥_a)称作H的A分解；

当计算某个角色的可用权限时，必须考虑HI层次，通过HI层次可能获得更多的权限；HA层次则用来计算可以被用户激活的角色；

如果(p,r)∈PA(权限-角色指派关系)，那么角色r被授权拥有权限p，假设存在另外一个角色r'使得r≥_ir'∨r≥r'，并且(p,r')∈PA；r₁通过继承r₃获得授权拥有权限集合{p₂}，通过继承r₅获得授权拥有权限集合{p₃,p₄}；如果(u,r)∈UA(用户-角色指派关系)或另外一个角色r'使得r'≥_ar∨r'≥r，且(u,r')∈UA那么角色r可以被用户激活，如果用户被指派给角色r₁，那么就可以激活{r₁,r₃,r₅}；

用Perm_HI(r)表示角色r∈R中通过I-层次或IA-层次被授权的权限集合，用Active_HA(r)表示可以被任何用户通过A-层次或IA-层次激活角色r∈R而激活的角色集合；则有：假定角色层次通过基于用户-角色，权限-角色指派和角色层次的关系被编码为平坦的，则令：对于角色集合R，令Perm(R)＝U_r∈RPerm(r)。

本发明一种实施方式是：步骤(6)通过以下步骤设定安全约束以及用户的安全目标：

(1).输入安全约束，安全约束是指在用户给出的角色集合R中，有n个角色不能同时存在于一组解中，

(2).设置关于权限、角色数量的用户目标，用户可以选择期望所求出的解能够激活的权限数量最大化：尽可能的接近P_UB，即给用户u授予尽可能多的权限，侧重于保障系统的安全性或是最小化：尽可能接近P_LB，即尽可能少的给用户u授权，侧重于保障系统的可用性，或者是角色数量最大化或最小化；或设定一个目标k值，这个k值表示用户希望求出的解中的权限或角色集合的个数必须小于或者大于k，否则系统就返回解不存在，此操作实现对用户需求进行细粒度的控制，能够根据用户不同需求进行弹性扩展。

本发明一种实施方式是：步骤(8)通过静态裁剪缩小所需考虑的请求权限的规模，对于权限冗余或缺失等各种复杂情形进行如下处理，基于给定的角色集合R，权限集合P，以及所请求的权限集上限与下限(P_LB,P_UB)，分以下四种不同的情形分别进行相应处理：

情形1：最小化匹配且冗余权限数量最少

1.构造角色集合R'，该集合中的所有角色其权限集合不包含于所请求的权限集，即

2.构造角色集合R″，令$>R^{\prime \prime }=\{r\in R:\mathrm{Perm}\left(r\right)\subseteq P_{\mathrm{LB}}\}$>

3.构造权限集合P'，令$>P^{\prime }=\{p\notin P_{\mathrm{LB}}:p\in \mathrm{Perm}\left(R^{\prime }\right)\}$>

4.令且|Perm(R_sat)|最小化，令且|Perm(R'_sat)|最小化，则Perm(R_sat)＝Perm(R'_sat)∪Perm(R")从而得到一个角色集合是在满足可用性情形下，冗余权限最小的角色集合；

情形2：最小化匹配且限定冗余权限数量为t

1.构造角色集合R'，令

2.构造角色集合R″，令$>R^{\prime \prime }=\{r\in R:\mathrm{Perm}\left(r\right)\subseteq P_{\mathrm{LB}}\}$>

3.构造权限集合P'，令$>P^{\prime }=\{p\notin P_{\mathrm{LB}}:p\in \mathrm{Perm}\left(R^{\prime }\right)\}$>

4.令且|Perm(R_sat)/P_LB|＝t，令且|Perm(R'_sat)/PLB|＝t，则Perm(R_sat)＝Perm(R'_sat)∪Perm(R")；

情形3：最大化匹配且缺失权限数量最小化

情形4：最大化匹配且缺失权限数量为t

令R'＝R,P'＝P_UB。

本发明一种实施方式是：步骤(9)中，基于给定角色集合R'，权限集合P，用户所请求的权限集合对四种不同的情形，分别进行相应处理：

情形1：最小化匹配且冗余权限数量最少

情形2：最小化匹配且限定冗余权限数量为t

对于角色集合R'中的任意角色r中的任意权限均不在用户的需求权限集合，即，如果则将角色r从R'中删除；

情形3：最大化匹配且缺失权限数量最小化

情形4：最大化匹配且缺失权限数量为t

对于角色集合R'中的任意角色r，如果则将角色r从R'中删除。

本发明一种实施方式是：步骤(10)通过以下步骤调用外部程序进行CNF转换，再调用zchaff求解器对用户授权查询请求问题进行计算：

1.在设定RABC系统状态，输入UAQ问题，经过静态裁剪和预处理两个优化步骤之后，生成一个新的RBAC系统状态；

2.在新的系统状态中，对于每一个(r,p)∈RP，将r→p作为一条子句，在这里“→”为“蕴含关系”；

3.同样对于每一个权限p，如果r₁,…,r_n是包含权限p的角色，则加入一条子句p→r₁∨…∨r_n；

4.在角色层次树的状态下，对于(r₁,r₂)∈RH，加入一条子句r₁→r₂；

5.对于每一个p∈P_LB，加入一条只有一个变量的子句p；

6.对于每一个权限p∈P/P_UB中，加入一条子句

7.对每一个SMER约束<{r₁,L,r_n},k>，通过以下两个步骤将其转换成CNF：

首先把<{r₁,L,r_n},k>转换成一个布尔回路满足性问题CIRCUIT‐SAT；

然后将CIRCUIT‐SAT转换为一个CNF‐SAT问题，保存至一个记事本文件中(对于存在多个SMER约束的情形，将新生成的CNF‐SAT追加到该记事本文件尾部)；

对于上述步骤，给定SMER约束<{r₁,L,r_n},k>(k≤n)，调用函数CircuitSAT({r_n,r_n-1,L,r₁},k)求解，当且仅当真变量的数量在x_n，x_n-1，L，x₁里最大为k时，返回值z＝1，否则返回0，其中z＝Contrast(Add(r_n,L,r₁),(s_m,L,s₁))，并且y_m,L,y₁满足下面就CircuitSAT()函数作如下说明：

a)对于Contrast()函数，其输入为(x_n,x_n-1,L,x₁)，(y_n,y_n-1,L,y₁)，输出为z(z＝1当且仅当否则z＝0，令e₁,L,e_n和l₁,L,l_n分别相等且形成下级变量。然后对于所有的i∈{1,…,n-1}，有且，最后z＝l₁∨e₁)；

b)对于Add()函数，其输入为(x_n,x_n-1,L,x₁)，输出为(z_m,z_m-1,L,z₁)Add＝AddBit(x_n,AddBit(x_n-1,L,AddBit(x₁,y_m,y_m-1,L,y₁)L))，当(y_m,y_m-1,…,y₁)＝(0,0,…,0)时；

c)对于AddBit()函数，其输入为(y_n,y_n-1,L,y₁)和x，其输出为(z_n,z_n-1,L,z₁)令b₁,L,b_n-1表示变量，b₁＝x∧y₁，则对于所有的i∈{2,L,n}，有b_i＝b_i-1∧y_i；

8.通过函数PermCircuit()来设置关于权限数量的用户目标，该函数的输入为{p₁,L,p_n}和k≤n，输出为z(z＝1当且仅当真变量的个数在{p₁,L,p_n}中最少为k个，否则z＝0)，z＝Contrast((y_m,K,y₁),Add(p_n,K,p₁))且当z＝1，表示权限集{p₁,L,p_n}中选中的权限不少于k个。当z＝0，表示权限集{p₁,L,p_n}中选中的权限少于k个。例如：如果要求授予用户的权限向P_LB靠齐，冗余的权限数量不超过x个，则可以通过设置{p₁,L,p_n}＝P_UB-P_LB，k＝x，调用函数PermCircuit()来，以判断输出结果z是否等于0来实现；

9.通过函数RoleCircuit()来设置关于权限数量的用户目标，该函数的输入为{r₁,L,r_m}和t≤m，输出为z(z＝1当且仅当真变量的个数在{r₁,L,r_m}中最少为t个，否则z＝0)，z＝Contrast((y_s,K,y₁),Add(r_m,K,r₁))且当z＝1，表示角色集{r₁,L,r_m}中选中的角色不少于t个。当z＝0，表示角色集{r₁,L,r_m}中选中的角色少于t个；

10.生成合取范式的文件。经过以上各步处理，将所有子句转换成为一个合取范式的文件，存入系统默认的temp文件夹下；

11.调用zchaff求解器来计算合取范式，并返回运算结果，根据求解器返回的值再进行相应的转换，并反馈回用户当前可激活的角色数量，以及可激活的权限数量。

本发明涉及访问控制系统中的用户授权查询请求问题，为之提供一种快速的求解方法，该方法采用了静态裁剪、预处理等优化技术，并调用SAT求解器zchaff，以获取高效的计算效率。具体而言，本发明具有以下三方面优点：

(1)高效性：用户授权查询请求问题是一个NP难度问题，本发明采用了把UAQ问题转换成合取范式再调用zchaff求解器，以获取高效求解效率。zchaff求解器基于DPLL(Davis Putnam Logemann Loveland)算法，而DPLL算法主要由变量决策、布尔约束传播、基于冲突的学习过程和非同步回溯构成，在求解计算复杂度较高问题时效率非常可观。

(2)安全性：在UAQ问题中，对于用户所请求的权限集合，如果不允许存在任何超出用户需要的权限，则能够保障系统的安全性；如果要求保证包含所有请求的权限集，则尽可能的把系统中的冗余权限和多余角色数目降到最低，降低了系统中因冗余权限的增加而加大的风险，较大程度上保障了系统的安全性。

(3)可扩展性：本系统在处理UAQ问题方面具有良好的可扩展性。例如可实现对用户需求进行细粒度的控制，即可由用户指定一个目标k值(k为正整数)，该值表示用户希望求出的解中的权限或角色集合的个数必须小于或者大于k，否则系统就返回解不存在。以上请求可根据用户的需求作相应的修改。

附图说明

图1为UAQ问题求解流程图；

图2为单调混合角色层次分解图；

图3为静态裁剪图；

图4为预处理图。

具体实施方式

下面结合附图和实例对本发明作进一步详细的说明。

本发明是基于zchaff的RBAC系统用户授权查询请求问题的求解方法，用户可根据系统中RBAC的状态以及授权查询请求问题创建需求，还可以设立相应的安全约束、期望的权限数量目标及期望的角色数量目标。具有良好的灵活性和友好的用户界面，方便用户的使用和数据的修改。

首先给出本发明中的几个概念：

基于角色的访问控制RBAC(Role‐based Access Control)模型：在RBAC模型中，用户和权限之间引入了角色的概念，用户可以被指派多个角色，角色也可以被分配多个权限，用户通过角色间接获取相应的权限。RBAC模型包括七个组成元素：用户、角色、权限、用户‐角色关系、角色层次关系、角色‐权限关系和约束。

用户授权查询UAQ(User Authorization Query)：在某单个会话中，用户向系统请求激活一个完成某项特定任务所需要的权限集合，问题的关键在于如何寻找一个优化的角色集合，用户激活该角色集合从而能够得到所请求的权限集合。

权限请求的上限：用户向系统提出权限激活请求，要求所激活的角色所包含的权限不能超出用户所给出的权限集合的上限。

权限请求的下限：用户向系统提出权限激活请求，要求所激活的角色所包含的权限集不能低于用户所给出的权限集合的下限。

角色层次树：角色之间具有层次关系，高级角色能够继承低级角色所拥有的权限。例如，Perm(R₁)＝{p₁,p₂,p₃}，Perm(R₂)＝{p₄}，如果R₁≥R₂，则Perm(R₁)＝{p₁,p₂,p₃,p₄}。

静态角色互斥约束SMER(Static Mutually Exclusive Role)：在实际的工作中，一些敏感角色互斥，例如，出纳和会计角色不能指派给同一个人。SMER约束的一般情形描述为<{r₁,L,r_n},k>，其防止系统中任何用户拥有{r₁,L,r_n}中k个及以上数量的角色。

下面就以求解用户的授权查询请求问题为例，详细说明本发明。

一、设定系统状态。

在用户申请登录系统之前，须进行系统状态的设定，用户可根据实际情况进行系统状态的弹性设定：

给定角色集合：用户所期望的RBAC系统中的角色及其数量；

给定权限集合：用户所期望的RBAC系统中的权限及其数量；

给定角色和权限的分布情形；

用户在点击设定按钮对所定制的系统进行文件生成，并进行文件保存路径选择。用户可以随时在自己选择的保存路径中查看自己所生成的RBAC系统的状态。

二、求解用户的授权查询请求问题。

求解流程如图1所示：

步骤(1)至步骤(3)完成了用户登录过程，检测用户u的属性证书，对用户u的信任度进行验证，是否符合登录系统的信任条件；

步骤(4)至步骤(10)是本发明的重点内容，主要根据用户u提出的需要获得的权限集合，求解用户u的授权查询请求问题，下面进一步详细说明步骤(4)至步骤(10)；

步骤(4)判断角色与权限是否为平坦角色关系，若是，则进入步骤(5)；否则角色之间存在继承关系，则将具有层次结构的系统转换为平坦角色；现根据图2，依照如下方法对用户u设定的角色层次进行转换：

当满足以下条件时：

r_m和r_n分别表示编号为m和n的两个角色；

$>\forall r_m,r_n(r_m\ge r_n)\in H\to \left(r_m{\ge }_i{r}_n\right)\in \mathrm{HI}$>

将一种单调的I-层次(高级角色自动继承低级角色的所有权限，记为≥_i)HI称为H(H表示混合层次：记为≥)的I分解；

当满足以下条件时：

$>\forall r_m,r_n\left(r_m{\ge }_a{r}_n\right)\in H\to \left(r_m{\ge }_a{r}_n\right)\in \mathrm{HA}$>

$>\forall r_m,r_n(r_m\ge r_n)\in H\to \left(r_m{\ge }_a{r}_n\right)\in \mathrm{HA}$>

将一种单调的A-层次HA(高级角色能够激活低级角色，记为≥_a)称作H的A分解；

当计算某个角色的可用权限时，必须考虑HI层次，通过HI层次可能获得更多的权限；HA层次则用来计算可以被用户激活的角色。图2给出一个单调混合角色层次分解的实例。如果(p,r)∈PA(权限-角色指派关系)，那么角色r被授权拥有权限p，假设存在另外一个角色r'使得r≥_ir'∨r≥r'，并且(p,r')∈PA。r₁通过继承r₃获得授权拥有权限集合{p₂}，通过继承r₅获得授权拥有权限集合{p₃,p₄}。如果(u,r)∈UA(用户-角色指派关系)或另外一个角色r'使得r'≥_ar∨r'≥r，且(u,r')∈UA那么角色r可以被用户u激活。如果用户u被指派给角色r₁，那么u就可以激活{r₁,r₃,r₅}；

用Perm_HI(r)表示角色r∈R中通过I-层次或IA-层次被授权的权限集合，用Active_HA(r)表示可以被任何用户通过A-层次或IA-层次激活角色r∈R而激活的角色集合。则有：Active_HA(r)＝假定角色层次通过基于用户-角色，权限-角色指派和角色层次的关系被编码为平坦的，则令：对于角色集合R，令Perm(R)＝U_r∈RPerm(r)。

步骤(5)通过进行以下设定，完成UAQ问题的输入。

用户u首先输入所请求权限的上限和下限的集合。上限对应系统承受风险最高需求，下限对应完成某项工作最低权限需求。例如，用户u首先给出所请求权限的上限P_UB＝{p₁,p₂,p₃,p₄,p₅}，即要求用户u最终能够激活的权限集合必须是P_UB的子集。用户u再给出所请求权限的下限P_LB＝{p₂,p₄}，即要求用户u最终能够激活的权限集合必须包含P_LB。

步骤6通过以下操作设定安全约束以及用户u的安全目标：

1.输入安全约束。安全约束是指在用户u给出的角色集合R中，有n个角色不能同时存在于一组解中。如用户u设定一个安全约束<{r₁,r₃,r₄,r₅},2>，即意味着{r₁,r₃,r₄,r₅}其中任意两个角色不能同时存在于一组解里，如果当前有一组解为S＝{r₁,r₂,r₃}，由于r₁和r₃不能被同时激活，故这组解应被舍弃。安全约束严格控制角色集合的分配，为系统的安全提供有力保障。

2.设置关于权限、角色数量的用户目标。用户u可以选择期望所求出的解能够激活的权限数量最大化(尽可能的接近P_UB，即给用户u授予尽可能多的权限，侧重于保障系统的可用性)或是最小化(尽可能接近P_LB，即尽可能少的给用户u授权，侧重于保障系统的安全性)，或者是角色数量最大化(尽可能多的激活角色)或最小化(尽可能少的激活角色)。也可以设定一个目标k值，这个k值表示用户希望求出的解中的权限或角色集合的个数必须小于或者大于k，否则系统就返回解不存在。此操作实现对用户需求进行细粒度的控制，能够根据用户不同需求进行弹性扩展，体现了良好的可扩展性。

步骤(7)对用户输入数据进行合法性判断，检验各项数据是否符合系统要求，对诸如P_LB是否为P_UB的子集，安全约束是否超出了权限集合的范围等进行检验，如果合法则进入步骤(8)，否则返回步骤(5)；

步骤(8)通过静态裁剪缩小所需考虑的请求权限的规模。对于权限冗余或缺失等各种复杂情形进行如下处理。如图3所示，基于给定的角色集合R，权限集合P，以及所请求的权限集上限与下限(P_LB,P_UB)，分以下四种不同的情形分别进行相应处理：

情形1：最小化匹配且冗余权限数量最少

5.构造角色集合R'，该集合中的所有角色其权限集合不包含于所请求的权限集，即

6.构造角色集合R″，令$>R^{\prime \prime }=\{r\in R:\mathrm{Perm}\left(r\right)\subseteq P_{\mathrm{LB}}\}$>

7.构造权限集合P'，令$>P^{\prime }=\{p\notin P_{\mathrm{LB}}:p\in \mathrm{Perm}\left(R^{\prime }\right)\}$>

8.令且|Perm(R_sat)|最小化，令且|Perm(R'_sat)|最小化，则Perm(R_sat)＝Perm(R'_sat)∪Perm(R")从而得到一个角色集合是在满足可用性情形下，冗余权限最小的角色集合。

情形2：最小化匹配且限定冗余权限数量为t

5.构造角色集合R'，令

6.构造角色集合R″，令$>R^{\prime \prime }=\{r\in R:\mathrm{Perm}\left(r\right)\subseteq P_{\mathrm{LB}}\}$>

7.构造权限集合P'，令$>P^{\prime }=\{p\notin P_{\mathrm{LB}}:p\in \mathrm{Perm}\left(R^{\prime }\right)\}$>

8.令且|Perm(R_sat)/P_LB|＝t，令且|Perm(R'_sat)/P_LB|＝t，则Perm(R_sat)＝Perm(R'_sat)∪Perm(R")。

情形3：最大化匹配且缺失权限数量最小化

情形4：最大化匹配且缺失权限数量为t

令R'＝R,P'＝P_UB。

静态裁剪有效地缩减了所需考虑的请求权限的规模，削减了搜索空间，极大地提高了系统的求解效率。

步骤(9)经过静态裁剪之后，剔除了部分不相关的权限，以下再通过预处理削减不包含请求权限的角色的数量，进一步削减搜索空间，进而有效提高系统的求解效率。如图4所示，基于给定角色集合R'，权限集合P，以及所请求的权限集上限与下限(φ,P')，对四种不同的情形，分别进行相应处理：

情形1：最小化匹配且冗余权限数量最少

情形2：最小化匹配且限定冗余权限数量为t

对于角色集合R'中的任意角色r中的任意权限均不在用户的需求权限集合，即，如果则将角色r从R'中删除。

情形3：最大化匹配且缺失权限数量最小化

情形4：最大化匹配且缺失权限数量为t

对于角色集合R'中的任意角色r，如果则将角色r从R'中删除。

步骤(10)通过以下步骤调用外部程序进行CNF转换，再调用zchaff求解器对用户授权查询请求问题进行计算：

12.在设定RABC系统状态，输入UAQ问题，经过静态裁剪和预处理两个优化步骤之后，生成一个新的RBAC系统状态。

13.在新的系统状态中，对于每一个(r,p)∈RP，将r→p作为一条子句，在这里“→”为“蕴含关系”。

14.同样对于每一个权限p，如果r₁,…,r_n是包含权限p的角色，则加入一条子句p→r₁∨…∨r_n。

15.在角色层次树的状态下，对于(r₁,r₂)∈RH，加入一条子句r₁→r₂。

16.对于每一个p∈P_LB，加入一条只有一个变量的子句p。

17.对于每一个权限p∈P/P_UB中，加入一条子句

18.对每一个SMER约束<{r₁,L,r_n},k>，通过以下两个步骤将其转换成CNF：

(1)首先把<{r₁,L,r_n},k>转换成一个布尔回路满足性问题CIRCUIT‐SAT；

(2)然后将CIRCUIT‐SAT转换为一个CNF‐SAT问题，保存至一个记事本文件中(对于存在多个SMER约束的情形，将新生成的CNF‐SAT追加到该记事本文件尾部)。

对于上述步骤(1)，给定SMER约束<{r₁,L,r_n},k>(k≤n)，调用函数CircuitSAT({r_n,r_n-1,L,r₁},k)求解，当且仅当真变量的数量在x_n,x_n-1,L,x₁里最大为k时，返回值z＝1，否则返回0。其中z＝Contrast(Add(r_n,L,r₁),(s_m,L,s₁))，并且y_m,L,y₁满足下面就CircuitSAT()函数作如下说明：

d)对于Contrast()函数，其输入为(x_n,x_n-1,L,x₁)，(y_n,y_n-1,L,y₁)，输出为z(z＝1当且仅当否则z＝0。令e₁,L,e_n和l₁,L,l_n分别相等且形成下级变量。然后对于所有的i∈{1,…,n-1}，有且。最后z＝l₁∨e₁)。

e)对于Add()函数，其输入为(x_n,x_n-1,L,x₁)，输出为(z_m,z_m-1,L,z₁)Add＝AddBit(x_n,AddBit(x_n-1,L,AddBit(x₁,y_m,y_m-1,L,y₁)L))，当(y_m,y_m-1,…,y₁)＝(0,0,…,0)时。

f)对于AddBit()函数，其输入为(y_n,y_n-1,L,y₁)和x，其输出为(z_n,z_n-1,L,z₁)令b₁,L,b_n-1表示变量，b₁＝x∧y₁，则对于所有的i∈{2,L,n}，有b_i＝b_i-1∧y_i。

19.通过函数PermCircuit()来设置关于权限数量的用户目标，该函数的输入为{p₁,L,p_n}和k≤n，输出为z(z＝1当且仅当真变量的个数在{p₁,L,p_n}中最少为k个，否则z＝0)，z＝Contrast((y_m,K,y₁),Add(p_n,K,p₁))且当z＝1，表示权限集{p₁,L,p_n}中选中的权限不少于k个。当z＝0，表示权限集{p₁,L,p_n}中选中的权限少于k个。例如：如果要求授予用户的权限向P_LB靠齐，冗余的权限数量不超过x个，则可以通过设置{p₁,L,p_n}＝P_UB-P_LB，k＝x，调用函数PermCircuit()来，以判断输出结果z是否等于0来实现。

20.通过函数RoleCircuit()来设置关于权限数量的用户目标，该函数的输入为{r₁,L,r_m}和t≤m，输出为z(z＝1当且仅当真变量的个数在{r₁,L,r_m}中最少为t个，否则z＝0)，z＝Contrast((y_s,K,y₁),Add(r_m,K,r₁))且当z＝1，表示角色集{r₁,L,r_m}中选中的角色不少于t个。当z＝0，表示角色集{r₁,L,r_m}中选中的角色少于t个。

21.生成合取范式的文件。经过以上各步处理，将所有子句转换成为一个合取范式的文件，存入系统默认的temp文件夹下。

22.调用zchaff求解器来计算合取范式，并返回运算结果。根据求解器返回的值再进行相应的转换，并反馈回用户当前可激活的角色数量，以及可激活的权限数量。

至此，一种基于zchaff的RBAC系统用户授权查询请求问题的快速求解方法具体实施过程结束。下面通过一个例子来说明本发明。

设定用户所给定的角色集合为R，权限集合为P，

角色集合R：{r₁,r₂,r₃,r₄,r₅}

权限集合P：{p₁,p₂,p₃,p₄,p₅,p₆,p₇,p₈,p₉,p₁₀}

设定角色和权限的分布情况如下：

角色r₁：{p₂,p₆,p₉}

角色r₂：{p₅,p₈,p₉,p₁₀}

角色r₃：{p₁,p₃,p₄}

角色r₄：{p₃,p₄}

角色r₅：{p₆,p₇,p₁₀}

登录系统之后，用户给出请求的权限的上限P_UB、请求的权限下限P_LB和安全约束D：

用户请求的权限的上限P_UB：{p₁,p₃,p₄,p₆,p₇,p₉,p₁₀}

用户请求的权限的下限P_LB：{p₃,p₄}

安全约束D：<{r₁,r₂,r₃},3>

此时，系统会验证数据是否合法，如P_LB是否为P_UB的子集，D这个集合是否超出了P这个集合的范围等。经验证，输入数据合法。

系统首先会对这些数据进行静态裁剪，

在静态裁剪后，系统还会对数据进行预处理，

得到经过处理的数据后，系统对数据进行SAT规约。如上述例子，我们首先把对应关系转换成P与R的对应关系。

权限p₁：{r₃}

权限p₂：{r₁}

权限p₃：{r₃,r₄}

权限p₄：{r₃,r₄}

权限p₅：{r₂}

权限p₆：{r₁,r₅}

权限p₇：{r₅}

权限p₈：{r₂}

权限p₉：{r₁,r₂}

权限p₁₀：{r₂,r₅}

然后，再把不属于P_UB集合里面的权限改成这样只允许P_UB中的权限可以激活。

通过调用CNF转换器进行转换，再通过调用SAT求解器对此问题进行求解。

并返回结果如下：

opt_k_perm＝4

opt_k_perm＝0

opt_k_role＝3

opt_k_role＝1

Average Time Elapsed＝0.000000

Variance of Time Elapsed＝0.000000

表示有两组解，当在R中选取3个角色时，需要在P_ub‐P_lb中激活4个权限；当在R中选取1个角色时，需要在P_UB‐P_LB中激活0个权限。