一种高阶权限指派约束的安全性与一致性验证

,,,

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 概述

访问控制是保障网络安全重要的核心技术之一,它允许被授权的主体对特定客体的访问,同时拒绝向非授权的主体提供服务[1]。安全与可用是访问控制2个重要需求,也是运用访问控制技术保护网络环境中信息机密性和完整性的关键所在。访问控制策略侧重于安全原则,主要是对用户访问进行限制以保障系统的安全性需求。职责分离策略将执行一项任务的相关权限分配给不同的用户,形成系统内部用户之间的相互牵制,阻止少量用户拥有过多权限,以防止系统权限被滥用,是一种典型的基于安全需求的访问控制策略[2-4]。相对于被看作为限制访问的安全性需求而言,可用性需求则可以被看作是对访问的启用[5-6]。可用策略要求协作完成某个任务的用户数量不能超过某个阈值,因为用户的数量上限直接关系到该任务是否能被顺利执行,是访问控制策略基于可用性需求的一个典型实例[7-9]。

访问控制策略的安全性需求与可用性需求互为彼此补充。如果缺少了可用性需求,可以轻易构造出满足任何安全性需求的访问控制状态,例如令该状态不包含任何用户集合能够拥有完成该任务所需的全部权限[6]。同样,如果缺少了安全性需求,也可以轻易构造出满足任何可用性需求的访问控制状态,例如给系统中所有用户均授予所有权限,使得系统中任何单个用户都能够独立完成该任务[5]。现有权限指派约束往往侧重于保障系统的安全性而忽略了可用性。因此,设计一种兼顾系统安全性与可用性需求的高阶权限指派约束显得尤为必要。然而,安全性与可用性需求彼此互斥,两者并存且当访问控制系统中的主体、客体、权限又隶属于不同的约束时,有可能引发安全冲突[10-15]。

关于安全冲突消解方面的代表性研究较多,例如文献[13]将策略看作是一种规定系统管理行为的方法,研究了策略冲突的离线检测和解决技术及其工具支持,主要涉及授权策略和强制策略。在策略之间建立优先级关系来消除冲突,并给出了4种策略优先级:否定策略优先,指定策略的优先级,基于距离规定优先级,域嵌套优先级。文献[14]从策略角度分析了大规模分布式系统中元素间的相互关系,并统一抽象成有向无环图模型,从而将抽象的安全策略冲突检测问题转化为具有成熟算法的有向图的连通性问题,提出一种检测策略冲突的定量方法检测分布式系统中安全策略冲突,包括模态冲突和内外冲突,并得出影响冲突检测复杂性的主要因素及其程度。文献[15]使用Prolog实现谓词规范以验证访问控制元策略。将冲突检测窗口中的策略集合自动转换为Prolog断言,并对谓词加以评估。一个谓词的全部解决方案就是存在冲突的策略集。安全性需求与可用性需求之间的冲突不能直接按照以上消解方法来进行消解。上述方法适用于求解计算复杂性较低的问题,当问题求解的复杂性为NP-hard级别时,其计算开销往往呈指数级增长趋势,因此,设计一种针对一致性验证问题的优化求解方法尤为必要。

针对上述问题,本文首先提出一种兼顾系统安全性与可用性需求的高阶权限指派(High-level Permission Assignment,HPA)约束,定义高阶权限指派约束的安全性验证问题和一致性验证问题;然后证明安全性验证问题和一致性验证问题在一般情形下分别是NP-complete及NPNP问题;最后设计一种求解一致性验证问题的优化算法,并通过仿真实验验证其有效性。

1 高阶权限指派约束的定义

定义1一个高阶权限指派约束防止用户集{u1,u2,…,un}中任何基数小于s的用户子集的权限并集包含{p1,p2,…,pm},同时保证{u1,u2,…,un}中至少存在一个基数为t的用户子集的权限并集包含{p1,p2,…,pm},形式化描述如下:

hpa〈{p1,…,pm},{u1,…,un},s,t〉

其中,pi(1≤i≤m)表示一个权限,uj(1≤j≤n)表示一个用户,s和t都是整数,且1≤s≤t≤min(m,n),min(m,n)返回m和n两者之中较小的一个数。

HPA约束防止少量的用户拥有全部权限,而将执行某一任务的权限指派给用户集合中s个以上的用户,以保障系统安全,同时保证访问控制系统中至少存在一个包含t个用户的用户组被指派全部权限,以保障系统可用。

举例说明:假设访问控制系统中执行某一任务所需要的权限集合为P={p1,p2,p3,p4,p5,p6,p7,p8},用户集合为U={u1,u2,u3,u4,u5},HPA约束集合为H={h1,h2,h3,h4},其中h1=hpa〈P,U,2,3〉,h2=hpa〈P,U,5,3〉,h3=hpa〈P,U,s,5〉(s≠1),h4=hpa〈P,U,1,t〉(t≠min(m,n))。

满足约束h1就要防止用户集U中任何基数小于2的用户子集的权限并集包含P,即如果任何一个用户被授予了全部权限则不满足这条约束,同时保证用户集合U中至少存在一个基数为3的用户子集的权限并集包含P,即至少有一个包含了3个U中用户的用户组被指派P中全部权限才满足这条约束。h2约束防止用户集{u1,u2,…,u5}中任何基数小于5的用户子集的权限并集包含P,同时保证U中至少存在一个基数为3的用户子集的权限并集包含P。显而易见h2本身就有冲突,显然是不会被满足的。另外,HPA约束中当参数s,t有特殊的取值时,在约束效果上表现出倾向性。要满足h3除了满足安全性需求即防止少于s个用户的用户组被指派全部权限外,还要保证至少存在一个包含了5个U中用户的用户组被指派P中全部权限,而多于5个用户的用户组是不存在的,同时如果不满足h3的可用性需求约束,该任务将无法执行。因此,当t=min(m,n)时,其对可用性的约束可以忽略。当s=1时,HPA约束的安全性最低。要满足h4除了满足可用性需求即至少有一个包含了t个U中用户的用户组被指派P中全部权限外,还要防止少于1个用户的用户组被指派全权限,后者在任何访问控制系统中显然都是满足的。因此,当s=1时,HPA的安全性约束可以忽略。

2 高阶权限指派约束的安全性验证

HPA约束在保障访问控制系统的安全性的同时又约束了系统的可用性,因此,一个给定的访问控制状态是否能够满足一个给定的HPA约束是需要考虑的问题。给定一个访问控制状态ε,并且满足一个HPA约束集合H,记为satH(ε)。定义2给出了HPA约束的安全性验证问题:

定义2给定一个访问控制状态ε和一个HPA约束h,验证ε是否满足h,即判定sath(ε)是否为真,被称为HPA约束的安全性验证问题(Safety Checking Problem,SCP)。

定理1SCP既是NP-complete问题,又是coNP-complete问题。

证明:

1)证明当s=1时SCP是NP-complete问题。

当且仅当约束hpa〈{p1,p2,…,pm},{u1,u2,…,un},1,t〉在访问控制状态ε中得到满足时,sathpa(ε)才为真。当s=1时,仅考虑参数t。因此,对于任意HPA约束hpa〈Pi,Ui,1,t〉,它要求Ui中至少存在一个用户子集合能够覆盖权限集合Pi,而且该子集合的基数不超过t。如果基数为t的用户集合给定了,验证问题将可以在多项式时间内完成:计算该集合中所有用户的权限并集,并检测其是否为Pi的父集。

下面将集合覆盖问题[16]规约成当SCP的子问题s=1,从而证明当s=1时SCP是NP-complete问题。在该集合覆盖问题中,输入是一个有限的集合S、一个作为S的子集合家族F={S1,S2,…,Sl}以及预算B。目标是判断是否存在B个F中的子集合,使得它们的并集为S。该问题已被证明是一个NP完全问题。规约过程可在多项式时间内完成,具体规约方法如下:

给定S,F和B,构造一个HPA约束f:对于S中的每一个元素,构造一个权限,令t=B,m是集合S的基数。构造一个HPA约束hi=hpa〈Pi,Ui,1,t〉,并构造出一个访问控制状态:对于F中每一个不同的子集Si(1≤i≤l),创造一个用户ui∈{u1,u2,…,un},使得Si中的全部权限指派给ui。则hpa〈Pi,Ui,1,t〉是否为真当且仅当F中存在B个子集合的并集覆盖S。因此,当s=1时的SCP既是NP问题亦是NP难度问题,故而s=1时的SCP是NP-complete问题。

2)证明当t=min(m,n)时,SCP是coNP-complete问题。

综上所述,当s=1时SCP是NP-complete问题,当t=min(m,n)时SCP是coNP完全问题。因此SCP既是NP-complete问题亦是co-NP完全问题。

证毕。

3 高阶权限指派约束的一致性验证

每个HPA约束包含了不同的安全性需求与可用性需求,两者互为补充,又互相排斥,当访问控制系统中同时并存多个HPA约束,互斥的安全性需求与可用性需求可能会引发HPA约束的不一致性。假定存在一个访问控制状态ε满足约束集合H={h1,h2,…,hn}(n≥2),记为satH(ε)。HPA约束的一致性验证问题定义如下:

定义3给定一个HPA约束集合H={h1,h2,…,hn}(n≥2),判定是否存在满足satH(ε)为真的访问控制状态ε,该问题被称为HPA约束的一致性验证问题(Consistency Checking Problem,CCP)。

定理2HPA约束的一致性验证问题的计算复杂度为:CCP是NPNP问题,

证明:

证毕。

4 高阶权限指派约束不一致性求解算法及仿真

以上已证明一般情形下的CCP问题是不可解问题(NPNP),即意味着在最坏情形下解决该问题将要耗费巨大的时间开销,但是依然存在很多情形可以在可接受的时间范围内被有效解决。受到原始算法的启发,结合预处理及规约为SAT求解器的方法,本文设计一种针对一致性验证问题的优化求解算法,并通过仿真实验验证算法的有效性。

4.1 优化算法

下文给出一个原始算法,并在该算法的基础上进行优化。

SA算法的时间复杂度为O(m×2|P|×|U|),该算法可以求解问题规模较小的CCP问题,但是随着系统规模的增加其时间开销呈指数级增长。因此,本文在SA算法的基础上,设计一个基于预处理-规约SAT的优化算法来求解该问题。

优化算法(OA):该算法先经过预处理降低需要考虑的HPA约束的数量,以及需要考虑的访问控制状态的数量,即删除不影响一致性的HPA约束与明显不满足约束集合的访问控制状态。然后将CCP问题规约为SAT实例,使用SAT求解器可以结合SAT现有研究的优点,并利用已有的SAT求解器提高计算效率。算法具体过程如下:

规约为SAT:求解CCP需要判定是否存在一个访问控制状态满足一个HPA约束的集合。令hi=hpa〈Pi,Ui,si,ti〉,给定一个状态ε,sathi(ε)为真意味着在Ui中不存在少于Si个用户的权限并集包含Pi,存在不多于ti个用户的权限并集包含Pi。由于集合覆盖问题已经被证明可以规约为SAT实例[3],sathi(ε)的验证问题又可规约到集合覆盖问题[10],因此可借用已有解决SAT求解器来求解。本文采用的是SAT4J,SAT4J是一个用Java实现的SAT求解器,它支持Pseudo-Boolean约束,与整数系数呈线性非等价关系。

规约步骤如下:给定一个HPA约束h=hpa〈P,U,s,t〉,对于每一个ui∈U,匹配一个参数vi,如果ui是一个基数为t并且基数大于等于k(k≤t)的用户集合中的一员,且该集合覆盖了P中的所有权限,则该参数为真,记为1,否则记为0。接下来给定2种类型的约束。对于每一个p∈P,令ui1,ui2,…,uix表示用户是否被授予权限p。增加第1种类型的约束vi1+vi2+…+vix≥1,它确保P中的所有权限都被U′所覆盖。存在m(m=|P|)个这样的约束。继续增加第2种类型的约束v1+v2+…+vn≤t(n=|U|),它确保|U′|≤t,只有一个这样的约束。

4.2 仿真实验与性能分析

为验证本文优化求解算法的有效性,本节进行了相应仿真实验,运行的计算机配置如下:

CPU:Intel Core i7 4790 CPU 3.6 GHz;

RAM:DDR3 16 GB 1066MHz;

操作系统:Windows 7 旗舰版。

该仿真实验系统由Java编写,并调用了SAT4J求解器。在实际应用中,一个访问控制系统中的权限数量通常不会太大,而用户的数量可能会比较大。因此,本实验仿真了用户与权限之比为2∶1以及10∶1不同环境下的OA算法的执行效率。通过以下方法随机生成的HPA约束实例进行实验:

1)|P|=X,其中X是一个整形随机变量,有X≥2,并且X小于系统中权限的数量MP。

2)|U|=Y,其中Y是一个整形随机变量,有Y≥2,并且Y小于系统中用户的数量MU。

3)s和t都是随机整数,其中s≤t,s的值域为[1,min(|P|,|U|)]。

4)当|P|和|U|被生成后,则从[1,MP]中随机选取|P|个整数{i1,i2,…,ix}作为权限P={pi1,pi2,…,pix}的右下标。同样从[1,MP]中随机选择|U|个整数作为U={ui1,ui2,…,uix}的右下标。

实验结果如图1和图2所示,其中运行时间由执行10次算法求其平均值得出。OA(50),OA(30)分别代表执行OA算法时仿真的访问控制系统中有50个及30个HPA约束。算法的运行时间依赖于总共需要考虑的访问控制状态的数量,通过实验结果可以看出,随着系统规模的扩大,检测需要的时间开销呈抛物线增长,这是因为本文实验借用SAT求解器来求解,一定程度上提高了其求解效率。在相同的系统规模下,系统中约束数量OA(50)比OA(30)多出20个约束,但是其系统开销却比OA(30)多了5倍以上,这是因为该问题为NPNP问题随着约束数量的增加其系统开销呈指数级增长。当用户与权限的比例比较小时其时间开销也比较小,在系统权限为20时用户权限之比为2∶1的执行时间小于用户与权限之比为10∶1的时间,这是因为前者的访问控制状态的数量相对较少。

图1 U∶P=2∶1时求解CCP问题的运行时间

图2 U∶P=10∶1时求解CCP问题的运行时间

5 结束语

本文兼顾访问控制系统安全性与可用性需求,提出一种高阶权限指派约束。分析该约束的安全性验证问题及一致性验证问题,分别证明这2个问题在一般情形下为不可解问题(计算复杂度分别为NP-complete以及NPNP),同时结合预处理及规约为SAT求解器的方法,设计一种针对一致性验证问题的优化求解算法,并通过仿真实验验证该算法的有效性。下一步将在高阶权限指派约束中考虑权限的权重,分析其对系统安全性与可用性的影响。

[1] 李瑞轩,鲁剑锋,李添翼,等.一种访问控制策略非一致性冲突消解方法[J].计算机学报,2013,36(6):1210-1223.

[2] WANG X,SHI W,XIANG Y,et al.Efficient Network Security Policy Enforcement with Policy Space Analysis[J].IEEE/ACM Transactions on Networking,2016,24(5):2926-2938.

[3] LU J,LI R,LU Z,et al.Specification and Enforcement of Static Separation-of-Duty Policies in Usage Control[C]//Proceedings of the 12th Information Security Conference.Pisa,Italy:[s.n.],2009:403-410.

[4] LI N,WANG Q.Beyond Separation of Duty:An Algebra for Specifying High-level Security Policies[J].Journal of the ACM,2008,55(3):1-30.

[5] LU J,LI R,HU J,et al.Inconsistency Resolving of Safety and Utility in Access Control[J].EURASIP Journal on Wireless Communications and Networking,2011(1):1-12.

[6] LI R,LU J,LU Z,et al.Consistency Checking of Safety and Availability in Access Control[J].IEICE Transactions on Information and Systems Society,2010,E93-D(3):491-502.

[7] MAO B,WU S,JIANG H.Exploiting Workload Characteristics and Service Diversity to Improve the Availability of Cloud Storage Systems[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(7):2010-2021.

[8] RAWAT A S,PAPAILIOPOULOS D S,DIMAKIS A G,et al.Locality and Availability in Distributed Storage[J].IEEE Transactions on Information Theory,2016,62(8):4481-4493.

[9] LI N,WANG Q,TRIPUNITARA M V.Resiliency Policies in Access Control[J].ACM Transactions on Information and System Security,2009,12(4):1-34.

[10] SHEN L,WANG Z,ZHANG X,et al.Study on the Policy Conflict Detection in the Security Management Model[C]//Proceedings of IEEE International Conference on Signal Processing Communications and Computing.Washington D.C.,USA:IEEE Press,2015:1-5.

[11] ELKANDOUSSI A,ELBAKKALI H,ELHILALI N.Toward Resolving Access Control Policy Conflict in Inter-organizational Workflows[C]//Proceedings of the 12th IEEE/ACS International Conference of Computer Systems and Applications.Washington D.C.,USA:IEEE Press,2015:1-4.

[12] 吴迎红,黄 皓,吕庆伟,等.基于开放逻辑R反驳计算的访问控制策略精化[J].软件学报,2015,26(6):1534-1556.

[13] LUPU E,SLOMNA M.Conflicts in Policy-based Distributed Systems Management[J].IEEE Transactions on Software Engineering(Special Issue on Inconsisteney Management),1999,25(6):852-869.

[14] 姚 键,茅 兵,谢 立.一种基于有向图模型的安全策略冲突检测方法[J].计算机研究与发展,2005,42(7):1108-1114.

[15] CHOLVY L,CUPPENS F.Analyzing Consistency of Security Policies[C]//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C.,USA:IEEE Press,1997:103-112.

[16] PAPADIMITRIOU C H.Computational Complexity[M].[S.l.]:Addison Wesley Longman,1994.