基于属性轻量级可重构的访问控制策略

谢绒娜，李晖，史国振，郭云川

（1.西安电子科技大学网络与信息安全学院，陕西 西安 710071；2.北京电子科技学院电子与通信工程系，北京 100070；3.中国科学院信息工程研究所，北京 100093）

1 引言

访问控制策略用来保护系统和网络中敏感资源被合法访问和使用，创建正确的满足安全需求的访问控制策略是保证系统安全、网络安全的前提和基础。复杂网络环境中包含多个安全域和各种复杂的分布式信息系统，不同的安全域和系统千差万别，安全需求也不同。复杂的网络环境下，描述出正确的、满足安全需求的访问控制策略是保证系统安全、网络安全急需解决的问题。

随着系统复杂度的增加和安全需求的差异，访问控制策略的数量、长度和复杂度急剧增加，这势必造成访问控制策略冗余与冲突检测难度增加，访问控制策略评估的效率急剧下降。另一方面，在计算资源、存储资源和能耗受限的设备中，访问控制策略的长度、数量和复杂度都受到很大限制。如何生成轻量级、不存在冗余和冲突的访问控制策略是复杂网络环境中访问控制策略生成面临的挑战。

在访问控制策略语言方面，研究人员先后提出了Ponder、安全策略语言（SPL,security policy language）、可扩展的访问控制标记语言（XACML,extensible access control markup language）[1-3]。XACML是一种采用XML 格式的通用访问控制策略语言，它的通用性使各系统访问控制策略得到标准化，受到了学术界和工业界的广泛关注。然而，XACML 面临的最大挑战是策略部署和实施，其部署和实施的困难性导致XACML 的应用受到一定的限制。为降低访问控制策略数量，文献[4-5]提出了访问控制策略组合方法，把2 个不同的访问控制策略组合成一个等效的访问控制策略。文献[6]提出了基于主体、客体属性，将访问控制列表（ACL,access control list）生成等效的基于属性的访问控制策略，降低了访问控制策略的数量和复杂度。为提高访问控制策略评估效率，文献[7]通过把策略中复杂的逻辑表达式转换为决策树的方式来提高访问控制策略评估的效率。针对访问控制策略冲突问题，研究人员先后提出了基于有向无环图模型、概念格、策略决策树等方法实现访问控制策略的冲突检测。姚键等[8]提出了一种基于有向图模型的冲突检测机制，解决了冲突检测中形式化证明过于复杂的问题。李瑞轩等[9]提出了最小代价和字典编辑优选2 种基于优先级的冲突消解方法，解决了策略非一致性冲突问题。但上述文献在轻量级可重构的访问控制策略生成、冗余与冲突检测、评估等方面并没有提出很好的解决方法。

针对上述问题，本文提出了基于属性轻量级可重构的访问控制策略。基于操作类型、主体、客体和环境属性将访问控制策略分解为多个不相交的原子访问控制规则，通过代数表达式对原子访问控制规则进行复合生成复杂访问控制策略，降低了访问控制策略数量、尺寸和复杂度，提高了访问控制策略冲突和冗余检测的效率以及访问控制策略评估的效率。

本文主要贡献如下。

1)提出了根据访问控制策略中的操作类型、主体属性、客体属性和环境属性将基于属性的访问控制策略划分为多个不相交的原子访问控制规则，给出了基于属性的原子访问控制规则范式描述以及原子访问控制规则冗余与冲突检测的方法。

2)提出了利用与、或等逻辑运算构造出代数表达式，通过原子访问控制规则和代数表达式重构出复杂访问控制策略的方法。

3)提出了将复杂访问控制策略分解为等效的原子访问控制规则和代数表达式，通过对等效的原子访问控制规则和代数表达式进行冗余与冲突检测实现对复杂访问控制策略的冗余与冲突检测，提高了访问控制策略冗余与冲突检测的效率。

2 相关工作

访问控制策略语言定义了访问控制策略描述语言的语义和语法，文献[1]提出的SPL 是一种事件驱动的策略语言。伦敦大学的Policy 小组在2000 年提出了一种面向对象的策略表示语言——Ponder[2]，与其他策略表示语言相比，Ponder 具有一定的通用性。在自主型访问控制模型中，一般使用访问控制列表和访问能力表来表述主体、客体与访问权限之间的对应关系。XACML[3]是采用XML 格式的通用访问控制策略描述语言。在策略表达上，XACML结构清晰且具有很大的灵活性，它将安全规则表示为主体、客体、行为和约束4 个主要属性的属性值集合，通过逻辑操作把属性集合连接在一起实现对访问控制请求授权。同时XACML 中包含了规则联合算法来解决安全策略中不同安全规则可能造成的冲突，以保证每个访问请求只得到一个最终授权结果。

基于属性的访问控制策略面临的最大挑战是策略部署和实施[10]。为提高基于属性访问控制策略部署实施的效率，基于属性的访问控制策略挖掘成为近期的一个研究热点，并取得了不少成果[6,11-12]。文献[6]提出了从ACL 中自动挖掘基于属性访问控制策略的算法。该算法基于用户和权限的关系、用户和客体的属性值，通过用约束替换属性表达式中的连接词来建立关系的方法进行访问控制规则挖掘，并通过合并和简化方法来提高访问控制规则的质量。Iyer 等[11]给出了基于属性访问控制策略中肯定授权和否定授权规则的挖掘方法。Chakraborty等[12]根据操作、主体和客体属性把基于属性的访问控制规则划分为多个不相交的规则集合。基于属性的访问控制策略的数量、长度同样也会影响访问控制策略实施的效率。Bonatti 等[13]提出了利用代数表达式来描述安全策略，以及把复杂访问控制策略形式化为代数的方法。针对访问控制策略复合问题，Rao等[4]提出了通过3 个二元操作和2 个一元操作组成代数表达式的方式实现复杂访问控制策略细粒度的复合。文献[5]提出了通过3 个二元操作把多个访问控制策略复合成一个丰富的访问控制策略，实现对于任意访问控制请求通过复合前后访问控制策略评估得到相同的访问控制结果，减少了访问控制策略的数量。针对使用XACML 描述的访问控制策略评估效率的问题，文献[7]提出了XACML 逻辑模型和决策图的方法，通过语义分析把策略中复杂的逻辑表达式转换为决策树来提高访问控制决策的效率。

在策略冲突检测和消解方面，不少文献也取得了许多成果。Lupu 等[14]研究了Ponder 语言中策略形式的一致性问题，在进行策略冲突检测时，将策略分解为主体、客体和行为3 个要素。当2条策略的某个要素的作用域相互覆盖时，就会引起符号冲突。姚健等[8]研究了分布式系统中元素之间的关系，并统一抽象成有向无环图模型，提出了一种应用该模型检测分布式系统中安全策略冲突的定量方法。针对XACML 描述的各种复杂访问控制策略不同规则之间存在的冲突问题，St-Martin 等[15]提出了冲突检测算法并进行了正确性证明。

上述文献对于如何生成轻量级可重构的访问控制策略，以及重构后策略的冗余与冲突检测并没有给出很好的解决方案。

3 基于属性访问控制策略生成与检测

3.1 基于属性访问控制策略

基于属性访问控制策略根据主体、客体和环境属性进行访问授权。

定义1S为主体s集合，AS 为主体属性atts集合，VS 为主体属性值values 集合，values 包括单值属性值、多值属性值和区间属性值。

主体属性对可以描述为二元组＜atts,values＞。atts=SAE(s)表示主体属性的表达式，简称主体属性，values=e(atts)表示主体属性atts 的属性值。比如，主体s1的部门（department）是“部门A”，那么atts1=SAE(s1)=“department”，values1=e(atts1)=“部门A”。主体s1的属性对可以表示为＜department,“部门A”＞。

主体属性值除了单值外还包括多值和区间，比如不同场景下主体s1的角色（role）不同，主体s1的第二个属性role，atts2=SAE(s1)=“role”,values2=e(atts2)={“administrator”,“teacher”,“father”}。主体s1的角色属性对可以表示为＜role,{“administrator”,“teacher”,“father”}＞。主体属性值还包括区间情况，比如主体s1的上班时间t为8:00—17:00，主体s1的第三个属性对可以表示为＜t,8:00≤t≤17:00}＞或者＜t,[8:00,17:00]＞。

按照同样的方法可以定义客体属性和环境属性。

定义2O为客体o集合，AO 为客体属性atto集合，VO 为客体属性值valueo 集合，valueo 包括单值属性值、多值属性值和区间属性值。

客体属性对可以描述为二元组＜atto,valueo＞。atto=OAE(o)表示客体属性的表达式，valueo=e(atto)表示客体属性atto 的值。

定义3C为环境c集合，AC 为环境属性attc集合，VC 为环境属性值valuec 集合，valuec 包括单值属性值、多值属性值和区间属性值。

环境属性对可以描述为二元组＜attc,valuec＞。attc=CAE(c)表示环境属性的表达式，valuec=e(attc)表示环境属性attc 的值。

基于属性的访问控制策略policy 是一个八元组＜OP,AS,AO,AC,VS,VO,VC,Rules＞。其中，OP 是操作op 的集合，Rules 是规则rule 的集合。基于属性的访问控制规则可以表示为＜effect,＜att,value＞,op＞。effect 表示该条规则是肯定授权还是否定授权，effect={“permit”,“deny”}，permit 表示肯定授权，deny 表示否定授权。＜att,value＞表示属性、属性值对。例如，规则rule=＜permit,department={“A”,“B”}∧location=“D://”,read＞表示部门A 或者部门B 的员工可以阅读D 盘上的文件。

访问控制规则是基于属性访问控制策略最核心的部分，基于属性的访问控制规则的巴科斯范式（BNF,Backus-Naur form）描述表示如下。

3.2 基于属性的原子访问控制规则

针对基于属性访问控制策略存在的冗余与冲突检测困难、访问控制请求评估效率低等问题，本文提出了基于属性的原子访问控制规则（atomicRule）的概念，以下简称原子规则。根据访问控制策略中的访问控制规则包含的操作类型、主体属性、客体属性、环境属性等将访问控制策略划分为多个不相交最小原子规则，然后通过代数表达式将原子规则复合成多个复杂访问控制策略。

基于属性的原子规则可以表示成＜effect,＜att,value＞,op＞四元组的形式。假设基于属性的原子规则包含m个属性对，即＜att1,value1＞,＜att2,value2＞,…,＜attm,valuem＞。valuei（0＜i≤m）包括单值属性值、多值属性值和区间属性值。原子规则满足如下条件：1)操作op 是单操作，假设操作集合OP包含k个操作，OP={op1,op2,…,opk}，op 是操作集合OP 中的一个操作；2)访问控制效果effect 只能是{“permit”,“deny”}中的一个，即effect=“permit”或者effect=“deny”；3)属性对＜att,value＞是最小的集合，即减少其中任意一个属性对＜atti,valuei＞，原子规则将不能得到有效的访问控制评估结果。比如规则rule1=＜permit,department={“A”,“B”}∧location=“D://”,read ＞就是一个原子规则，访问控制效果 effect=“permit”,op=read，属性对department={“A”,“B”}和location=“D://”去掉其中任意一个都不能得到有效的访问控制评估结果。规则rule2=＜permit,(department={“A”,“B”}∨role=administrator)∧location=“D://”,read ＞就不是一个原子规则，属性对＜department,{“A”,“B”}＞和＜role,administrator＞满足其中任意一个条件都可以得到有效的访问控制评估效果。rule2可以分解为rule1和rule3这2 个原子规则。rule3=＜permit,(role=administrator)∧location=“D://”,read ＞，rule2=rule1∨rule3。基于属性的原子规则的BNF 描述表示如下。

3.3 基于属性原子访问控制规则的冗余与冲突检测

利用上述原子规则的3 个条件可以判断一个访问控制规则是否为原子规则，但原子规则之间还存在冗余和冲突。比如rule4=＜permit,(department={“B”,“C”})∧location=“D://”,read ＞。rule1和 rule4均为原子规则，但它们之间存在冗余。rule5=＜deny,(department=“C”)∧location=“D://”,read＞。rule4和rule5同样都为原子规则，但它们之间存在冲突。下面讨论原子规则中同一类型操作的不同规则之间的冗余和冲突检测。

1)原子规则的冗余检测

对于任意2 个规则rulei和rulej，分别包含ni和nj个属性对，rulei=＜effecti,＜att1,value1＞,＜att2,value2＞,…,,opi＞,rulej=＜effectj,＜att1,value1＞,＜att2,value2＞,…,,opj＞。如果规则rulei和rulej包含的操作和访问控制效果相同，即opi=opj，effecti=effectj，属性对个数、属性和属性值均相同，即ni=nj，rulei.attk=rulej.attk，rulei.valuek=rulej.valuek(k=(1,…,ni))，那么rulei和rulej为2 个相同的规则。判断属性值是否相同包括判断单值、多值和区间值是否相同。如果属性值为单值，直接判断2 个值是否相等；如果属性值为多值或者区间，判断表示属性值的集合是否相等。如果规则rulei和rulej的操作和访问控制效果相同，属性对个数和属性也相同，但存在2 个属性值不相同，即rulei.valuek≠rulej.valuek，那么规则rulei和rulej存在冗余，rulei和rulej可以合并为一个新的原子规则rule。如果valuek为单值，新的原子规则rule 的属性值valuek改为多值，rule.valuek={ rulei.valuek,rulej.valuek}；如果valuek为多值或者区间，那么rule.valuek=rulei.valuek∪rulej.valuek。对于原子规则的冗余检测可以采用算法1 进行。

算法1RedundancyDetect(rule1,rule2)

函数GetRuleOperator(rule)为得到规则rule 对应的操作op，GetRuleEffect(rule)为得到规则rule的访问控制效果effect，GetRuleAttNumber(rule)为得到规则rule 属性对个数，GetRuleAttSet(rule)为得到规则rule 的属性对＜att,value＞。

2)原子规则的冲突检测

对于任意2 个规则rulei和rulej，如果规则rulei和rulej包含的操作相同、属性个数和属性相同、属性值相同或者存在交集，而访问控制效果相反，那么规则rulei和rulej存在冲突。在对属性值进行判断时，对于单值属性值，直接判断2 个属性值是否相同，即rulei.valuek=rulej.valuek；对于多值属性值或者区间属性值，判断2 个属性值是否存在交集，即rulei.valuek∩rulej.valuek≠Ф。函数ConflictDetect(rule1,rule2)用来检测规则是否存在冲突，存在冲突返回true，不存在冲突返回false。

3.4 基于属性原子访问控制规则的复合

下面讨论如何由原子规则复合出语义丰富的复杂的访问控制策略。本文提出了通过与（AND,∧）、或（OR,∨）布尔操作组成的布尔函数，对原子规则进行复合得到语义丰富的复杂访问控制策略。

1)AND（∧），与操作要求所有的访问控制规则都同意授权时，才允许主体对客体进行对应的操作。例如，rule=rule1∧rule2，deci表示规则rulei的授权结果，dec=dec1∧dec2。将允许授权permit 编码为1，当且仅当dec1=1 和dec2=1 时，dec=1。与操作表示最小的授权原则。

2)OR（∨），或操作表示当有一条访问控制规则同意授权时，就允许主体对客体进行对应的操作。例如，rule=rule1∨rule2，dec=dec1∨dec2。当dec1=1 或dec2=1 时，dec=1。或操作表示最大的授权原则。

令变量xi表示规则rulei，变量y表示规则rule，如果rule=rule1∧rule2，令y=f1(x1,x2)=x1∧x2=x1x2，那么规则rule 可以通过规则rule1、rule2和代数表示式f1(x1,x2)复合而成。如果rule=rule1∨rule2，令y=f2(x1,x2)=x1∨x2=x1+x2+x1x2，那么规则rule 可以通过规则rule1、rule2和代数表示式f2(x1,x2)复合而成。如果规则rule 是通过对n个规则rule1,…,rulen进行与、或操作复合而成，代数表达式y=f(x1,…,xn)表示规则rule 中各个原子规则逻辑关系，规则rule 可以通过代数表达式y=f(x1,…,xn)对规则rule1,…,rulen复合生成。令deci表示规则rulei的授权结果，其中同意授权deci=1，否定授权deci=0。令xi=deci，将规则rulei的授权结果deci代入函数y=f(x1,…,xn)就可以得到规则rule 授权结果。

从前面分析可以看出，通过原子规则和代数表达式f可以复合出语义丰富的复杂访问控制规则。对于复合访问控制规则的授权结果，通过将原子规则的授权结果代入代数表达式f中就可以得到复杂访问控制规则的授权结果。访问控制策略是由多个访问控制规则复合而成，对于访问控制策略同样可以采用原子规则和代数表达式的方式复合生成，访问控制授权结果也可以采用同样的方法得到。

对于复杂访问控制规则的冗余与冲突检测，可以通过对等效的原子规则和代数表达式进行冗余和冲突检测。如果2 个访问控制规则等效的原子规则存在冗余或冲突，那么这2 个访问控制规则一定存在冗余和冲突。对于等效的原子规则不存在冗余和冲突的访问控制规则，可以通过代数表达式进一步判断2 个访问控制规则是否存在冗余和冲突。访问控制规则rulei和rulej对应的代数表达式为fi和fj，如果不存在冗余和冲突，那么访问控制规则rulei和rulej不存在冗余和冲突，如果fi和fj存在冗余和冲突，那么访问控制规则rulei和rulej存在冗余和冲突。对于访问控制策略，可以采用类似的方法进行冗余和冲突检测。复杂访问控制策略冗余与冲突检测转化为对等效原子规则和对应代数表达式进行检测，大大降低了访问控制策略冗余和冲突检测的复杂度，提高了检测的效率。

4 基于属性访问控制策略的分解

根据第3 节的分析可以看出，通过原子规则复合的方式提高了访问控制策略生成、冗余和冲突检测的效率。在实际信息安全系统中，系统管理员根据系统的安全需求进行访问控制策略的配置或者自动生成各种访问控制策略，系统管理员配置或者自动生成的访问控制策略一般都是复杂访问控制策略。本节重点讨论如何将复杂访问控制策略等效转化为原子规则和代数表达式的形式。

4.1 基于属性访问控制规则的分解与等效转化

基于属性访问控制策略包含一条或多条访问控制规则，下面首先讨论对访问控制策略中的一条访问控制规则进行分解的方法。基于属性的访问控制规则经需要过以下3 个步骤等效转化为原子规则和代数表达式的形式。

Step1算法2 DecomposeRule()根据访问控制规则rule 包含的操作，把规则rule 分解为访问控制规则集合RuleOP 及对应的代数表达式f，访问控制规则集合RuleOP 中的每一个访问控制规则Ruleop只包含一种类型的操作。

Step2算法3 DecomposeRuleOp()对访问控制规则Ruleop 进行语义分析，将Ruleop 分解为多个访问控制规则，生成访问控制规则集合RuleSetOP 及对应的代数表达式fop。访问控制规则集合RuleSetOP 中的访问控制规则RuleSetop 只包含一种类型的操作和一种访问控制效果。

Step3算法4 DecomposeAtomicRule()根据规则RuleSetop 中主体属性、客体属性、环境属性的逻辑关系，将访问控制规则RuleSetop 分解为原子规则集合，并对原子规则集合进行冗余和冲突检测，得到访问控制规则RuleSetop 最终等效的原子规则集合atomicRuleSet 以及对应代数表达式fatomic。

基于属性的访问控制规则的分解与等效转化如图1 所示。

算法2 DecomposeRule(rule,RuleOP,n)根据rule中包含的操作类型把规则rule 分解为多个只包含一种操作类型的访问控制规则集合RuleOP。n为访问控制规则rule 中操作类型的个数，也是最终生成的访问控制规则集合RuleOP 中包含访问控制规则Ruleop 的个数。规则Ruleop 只包含一种操作类型，Ruleop=＜effect,＜att,value＞,op＞，op 是操作集合OP中的一类操作，effect 是{“permit”,“deny”}中的一个。

图1 基于属性的访问控制规则的分解与等效转化

算法2 首先调用函数GetRuleOperator(rule)得到规则rule 包含的所有操作集合OP。然后针对操作集合中的每一个元素op，调用函数GetOPRule(rule,op)得到访问控制规则rule 中操作op 对应的访问控制规则Ruleop。比如访问控制规则rule 包含读（read）操作和写（write）操作，rule 分解为Ruleread和Rulewrite。最后函数GetRuleFExp()根据不同操作的访问规则在规则rule 中的逻辑关系生成rule 的代数表达式f。例如，规则rule=＜permit,department={“A”,“B”}∧location=“D://”,read＞∨＜permit,department={“A”,“C”}∧location=“D://”,read＞∨＜permit,department={“A”,“C”}∧location=“D://”,write＞，规则rule 可以分解为读访问控制规则Ruleread和写访问控制规则Rulewrite，Ruleread=＜permit,department={“A”,“B”}∧ location=“D://”,read＞∨＜permit,department={“A”,“C”}∧location=“D://”,read＞，Rulewrite=＜permit,department={“A”,“C”}∧location=“D://”,write＞。f(x1,x2)=x1∨x2=x1+x2+x1x2。其中x1表示Ruleread，x2表示Rulewrite。通过访问控制规则Ruleread、Rulewrite和代数表达式f可以复合出访问控制规则rule。

算法2DecomposeRule(rule,RuleOP,n)

算法 3 DecomposeRuleOp(Ruleop,RuleSetOP,nop,fop)对访问控制规则Ruleop 的语义和逻辑关系进行分析，把规则Ruleop 分解为nop个等效的、只包含一种访问控制效果的、互不相交的访问控制规则集合RuleSetOP，fop为访问控制规则Ruleop 对应的代数表达式，通过访问控制规则集合RuleSetOP和代数表达式fop可以复合出访问控制规则Ruleop。访问控制规则集合 RuleSetOP 中的每一个规则RuleSetOP[i]只包含一种操作类型和一种访问控制效果，RuleSetOP[i]=＜effect,＜att,value＞,op＞，op 是操作集合OP 中的一个元素，effect 是{“permit”,“deny”}中的一个。

算法3 首先调用函数GetPermitRule(Ruleop)得到规则Ruleop 中肯定授权规则集合rulePSet，调用函数GetRuleFExp(Ruleop,rulePSet,)得到规则Ruleop 中肯定授权规则的代数表达式。调用函数GetDenyRule(Ruleop)得到规则Ruleop 中否定授权规则集合ruleDSet，调用函数GetRuleFExp (Ruleop,ruleDSet,)得到规则Ruleop 中否定授权规则的代数表达式。算法3 生成与规则Ruleop 等效互不相交的访问控制规则集合 RuleSetOP，RuleSetOP 为rulePSet 和ruleDSet 并集，代数表达式。例如，ruleread=＜permit,department={“A”,“B”}∧location=“D://”,read＞∨＜permit,department={“A”,“C”}∧location=“D://”,read＞，通过算法3 规则ruleread分解为RuleSetread[1]=＜permit,department={“A”,“B”}∧location=“D://”,read＞和 RuleSetread[2]=＜permit,department={“A”,“C”}∧location=“D://”,read＞。fread(x1,x2)=x1∨x2=x1+x2+x1x2。

算法3DecomposeRuleOp (Ruleop,RuleSetOP,nop,fop)

通过算法3 分别对访问控制集合RuleOP 中n个访问控制规则Ruleop 进行分解等效转化，分别得到各个访问控制规则Ruleop 对应的互不相交的访问控制规则集合RuleSetOP 及复合代数表达式fop1,fop2,…,fopn，访问控制规则rule 对应的代数表达式为f(fop1,fop2,…,fopn)。

目前，访问控制规则集合RuleSetOP[i]中各个访问控制规则RuleSetop 并不是原子规则，各个规则之间还存在冗余和冲突，算法 4 调用函数DecomposeAtomicRule(RuleSetop,conflictflag,atomicRuleSet,fatomic,natomic)，把只包含一种操作类型和一种访问控制效果的规则ruleSetop 分解成等效的、互不相交的原子规则集合atomicRuleSet，并检测各规则之间是否存在冗余和冲突，如果存在冲突，将冲突标记conflictflag 置为true；如果存在冗余，将原子规则集合atomicRuleSet 中存在冗余的规则进行合并，得到RuleSetop 最终原子规则集合及代数表达式fatomic。

算法4 调用函数GetRuleMinAttSet (RuleSetop,attSet,natomic)生成规则RuleSetop 最小属性对集合attSet。函数 GetRuleMinAttSet()首先对规则ruleSetop 中属性对进行语义分析，根据各属性对之间的逻辑关系将属性对分解成natomic个最小属性对集合。具体分析时，先扫描规则中属性对或操作符，再根据或操作符把属性对分解成多个最小的属性对集合。例如，规则 RuleSetop 中属性对为(＜att1,value1＞∧＜att2,value2＞)∨(＜att3,value3＞∧ ＜att4,value4＞)，函数GetRuleMinAttSet 得到属性对集合attSet，attSet={{＜att1,value1＞∧ ＜att2,value2＞},{＜att3,value3＞∧＜att4,value4＞}}。attSet 共包含2 个元素，attSet[1]={＜att1,value1＞ ∧ ＜att2,value2＞}，attSet[2]={＜att3,value3＞ ∧ ＜att4,value4＞} 。函 数AddRule (atomicRuleSet,＜effect,attSet[i],op＞)根据＜effect,attSet[i],op＞生成规则并加入规则集合atomicRuleSet 中。函数GetRuleFExp (RuleSetop,atomicRuleSet,fatomic)分析原子规则集合atomicRuleSet 中各个原子规则的逻辑关系得到原子规则集合atomicRuleSet 各个原子规则的代数表达式fatomic。例如，规则RuleSetop 分解成了2 个原子规则，atomicRuleSet[1]=＜effect,attSet[1],op＞和atomicRuleSet[2]=＜effect,attSet[2],op＞，规 则RuleSetop 对应的代数表达式fatomic=x1∨x2=x1+x2+x1x2，x1表示规则atomicRuleSet[1]，x2表示规则atomicRuleSet[2]。

目前生成原子规则集合atomicRuleSet 中各原子规则之间可能还存在冗余和冲突，调用函数ConflictDetect()和RedundancyDetect()对原子规则集合atomicRuleSet 各原子规则进行冗余和冲突检测。函数 SimplyRuleFExp(atomicRuleSet,fatomic,natomic)将原子规则集合中存在冗余的规则从代数表达式中删掉，并生成新的代数表达式fatomic。例如，规则RuleSetop=(atomicRuleSet[1]∧atomicRuleSet[2])∨atomicRuleSet[3]对应的复合表达式为fatomic=(x1∧x2)∨x3=x1x2+x3+x1x2x3。如果原子规则atomicRuleSet[1]和atomicRuleSet[2]存在冗余，将atomicRuleSet[1]和atomicRuleSet[2]合并为一个新的原子规则放在 atomicRuleSet[1]，并将atomicRuleSet[3]放在 atomicRuleSet[2]，原来的atomicRuleSet[3]从原子规则集合删掉，新的代数表达式fatomic=x1∨x2=x1+x2+x1x2，natomic由3 更新为2。例如，前文生成的读规则 RuleSetread[1]和RuleSetread[2]存在冗余，RuleSetread[1]和RuleSetread[2]可以合并为一个新的规则RuleSetread[1]，RuleSetread[1]=＜permit,department={“A”,“B”,“C”}∧location=“D://”,read＞。

算法 4DecomposeAtomicRule(RuleSetop,conflictflag,atomicRuleSet,fatomic,natomic)

通过算法4，对访问控制规则集合RuleSetOP中nop个访问控制规则RuleSetop 进行分解等效转化，分别得到各个访问控制规则RuleSetop 对应的原子规则集合、复合代数表达式fatomic1,fatomic2,…,以及访问控制规则集合RuleSetOP 对应的复合代数表达式fop(fatomic1,fatomic2,…,)。

4.2 基于属性访问控制策略的分解与等效转化

基于属性访问控制策略是对多个访问控制规则复合而成。假设访问控制策略P是对m个访问控制规则通过复合函数f(x1,x2,…,xm)复合而成，m个访问控制规则对应的代数表达式分别为f1,f2,…,fm。访问控制策略P的代数表达式f(x1,x2,…,xm)=f(f1,f2,…,fm)。

5 基于属性可重构的访问控制策略的评估

本节分别从空间复杂度和时间复杂度对基于属性可重构的访问控制策略进行评估。

5.1 空间复杂度

假设系统的访问控制策略库中共有n个原子规则，n元布尔函数函数f(x1,x2,…,xn)共有，n个原子规则可以重构出个复杂访问控制策略。对于通过原子规则和代数表达式重构生成的访问控制策略库只需要存储n个原子规则和个代数表达式。与访问控制策略相比，代数表达式占用的存储空间可以忽略不计，个复杂访问控制策略占用的空间与n个原子规则占用的空间是指数关系，优势显然而见。

5.2 时间复杂度

下面，从访问控制策略评估效率对本文提出的可重构的访问控制策略的时间复杂度进行定性分析。

访问控制策略的评估包括访问控制策略的匹配和访问控制请求评估两部分。对于基于属性的访问控制策略的评估需要根据访问请求中操作、主体属性、客体属性和环境属性从访问控制策略库一一匹配找到相关的访问控制策略，根据匹配到访问控制策略中的各个访问控制规则来判断是否可以对客体进行相关操作，并根据各个访问控制规则判断结果和组合算法得到访问控制请求的最终结果。从前面评估过程中看出，首先需要对访问控制策略库中的访问控制策略一一进行匹配，找到相关的访问控制策略。当策略库中访问控制策略数量比较大时，策略的匹配需要耗费大量的时间。从评估过程看，需要对匹配到访问控制策略中所有相关的访问控制规则一一进行判断。例如信息系统S，配置有100 个访问控制策略，100 个访问控制策略等效转化为10 个原子规则。系统S 的访问控制策略库由100 个访问控制策略变成10 个原子规则和100 个代数表达式。当系统S 接收到访问控制请求R，根据访问控制请求中的操作、主体属性、客体属性和环境属性对100 个访问控制策略一一匹配，找到最终的访问控制策略。例如访问控制请求为部门A 的员工请求访问D://file1 文件。按照操作、主体属性、客体属性和环境属性的顺序进行匹配。假设首先从100 个访问控制策略中找到与读操作有关的策略80个，与读操作相关的访问控制策略中与主体属性部门A 有关策略50 个，然后根据客体属性D://file1最终找到访问控制规则rule，rule=＜permit,department={“A”,“B”}∧location=“D://”,read＞∨＜permit,department={“A”,“C”}∧location=“D://”,read＞∨＜permit,department={“A”,“C”}∧location=“D://”,write＞。从访问控制策略匹配过程，假设进行一次匹配所花费的时间为1 个单位时间，在上述信息系统S 中最终匹配到访问控制规则rule所花费的时间为100+80+50=230 个单位时间。

对本文提出的通过原子规则重构生成的访问控制策略进行匹配时，首先根据访问请求中的操作，筛选出和访问请求中相同操作的原子规则，然后根据主体属性、客体属性和环境属性从筛选的原子规则找到最终匹配的原子规则集合。对上述信息系统S，10 个原子规则中有5 个原子规则为读操作相关规则，与主体属性部门A 相关的原子规则有3个，而与客体属性D://file1 相关原子规则只有1 个，找到最终原子规则 RuleSetread[1]=＜permit,department={“A”,“B”,“C”}∧location=“D://”,read＞。在10 个原子规则中匹配到最终原子规则RuleSetread[1]所花费的时间为10+5+3=18 个单位时间。230 个单位时间远远大于18 个单位时间。实际上，匹配原子规则花费的时间远远小于复杂访问控制策略，也就是说匹配到最终原子规则RuleSetread[1]所花费的时间小于18 个单位时间。

下面分析对访问控制请求评估所花费的时间。通过访问控制规则rule 对访问控制请求R 进行评估时，允许读D://文件的主体为{“A”,“B”}，部门A 在允许的范围内，部门A 的员工可以读文件D://file1。继续扫描规则rule，规则rule 中对读操作的权限限制为＜permit,department={“A”,“B”}∧location=“D://”,read＞和＜permit,department={“A”,“C”}∧location=“D://”,read＞，它们之间为或的关系，当判断部门A 的员工可以读文件D://file1时，后续限制条件＜permit,department={“A”,“C”}∧location=“D://”,read＞不需要再进行判断。继续扫描规则rule，下面为写操作，与读操作无关，也不用判断，得到最终的访问控制结果为部门A 的员工可以读文件 D://file1。通过原子规则RuleSetread[1]对访问控制请求R 进行评估时，允许读D://文件的主体为{“A”,“B”,“C”}，部门A在允许的范围内，部门 A 的员工可以读文件D://file1。从前面的分析过程发现，通过规则rule对访问控制请求R进行判断所花费的时间至少是通过原子规则RuleSetread[1]所花费时间的1 倍多。假设访问控制请求R为部门C 的员工请求访问D://file1 文件，采用前面类似的方法进行分析可以看出，通过访问控制规则rule 进行判断所花费的时间至少是通过原子规则RuleSetread[1]的2 倍多。

5.3 评估实验

为测试本文提出的轻量级可重构的访问控制策略的评估效率，本文采用Python 语言开发了一个中间件（middleware）实现访问控制策略决策功能，中间件运行在Intel1.4 GHz i5CPU 16GiBRAM 计算机。利用上述中间件对不同的访问控制请求R分别通过访问控制规则rule 和原子规则进行了评估，为准确记录评估时间，每个访问控制请求评估10 000次，测试的结果如表1 所示。从实验结果来看，通过原子规则进行评估的效率是通过规则rule 效率的2 倍以上。对于逻辑关系复杂的访问控制策略，采用本文提出的方法生成的访问控制策略效果会更明显，比如部门C 员工的写访问请求，通过原子规则进行评估，效率提高了3 倍左右。

表1 访问控制规则评估效率

5.4 访问控制策略冗余和冲突检测效率

访问控制策略冗余与冲突检测一直是访问控制策略的研究热点。现有文献分别从有向无环图模型、概念格、策略决策树等不同的方面提出了访问控制策略冗余与冲突检测的方法，本文将复杂访问控制策略等效转化为原子规则和代数表达式，通过判断访问控制策略等效的原子规则和代数表达式是否存在冗余或冲突，来判断访问控制策略是否存在冗余和冲突。如果原子规则存在冗余和冲突，那么对应的访问控制策略肯定存在冗余和冲突；如果等效的原子规则不存在冗余和冲突，需要进一步判断代数表达式是否存在冗余和冲突。如果代数表达式不存在冗余和冲突，那么对应的访问控制策略不存在冗余和冲突；如果代数表达式存在冗余和冲突，那么对应的访问控制策略存在冗余和冲突。由于最终复合生成的访问控制策略和原子规则在数量上为指数级关系，复杂度也不是同一个数量级。复杂访问控制策略冗余与冲突检测转化为对等效原子规则和代数表达式的检测，大大降低了难度和复杂度，提高了检测的效率。

6 结束语

以基于属性的访问控制策略为基础，根据访问控制规则中的操作类型、主体属性、客体属性和环境属性将基于属性的访问控制策略划分多个不相交的原子规则，并通过与、或等逻辑关系构成的代数表达式，将原子规则重构出复杂访问控制策略；根据原子规则中包含的属性是否相同，属性值是否相同或者是否存在交集，访问控制效果相同还是相反，判断原子规则是否存在冗余与冲突。实际系统中的访问控制策略大多是复杂访问控制策略，甚至有些策略存在冗余和冲突。本文提出将复杂访问控制策略转化为等效的原子规则和代数表达式的方式，降低访问控制策略的数量和复杂度；通过将原子规则评估结果代入代数表达式中，得到复杂访问控制策略评估结果；通过对转化生成的原子规则和代数表达式进行冗余与冲突检测，实现对复杂访问控制策略进行冗余与冲突检测。从空间复杂度和时间复杂度2个不同角度对本文提出的可重构的访问控制策略进行定性评估，实验结果表明，本文提出的访问控制策略重构方法大大降低了访问控制策略的长度、数量和复杂度，提高了访问控制策略冗余与冲突检测的效率以及访问控制策略评估的效率。

下一步工作将把原子规则等效转化的方法应用到实际信息系统中分析原子规则复合方法的效率，同时研究不同操作之间原子规则的冗余与冲突检测，尤其是有相互影响关系的操作之间原子规则之间的冗余和冲突检测。