# Elimination of the Redundancy Related to Combining Algorithms to Improve the PDP Evaluation Performance

Authors: Fan Deng; Li-Yong Zhang; Bo-Yu Zhou; Jia-Wei Zhang; Hong-Yang Cao
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

If there are lots of redundancies in the policies loaded on the policy decision point (PDP) in the authorization access control model, the system will occupy more resources in operation and consumes plenty of evaluation time and storage space. In order to detect and eliminate policy redundancies and then improve evaluation performance of the PDP, aredundancy related to combining algorithms detecting and eliminating engine is proposed in this paper. This engine cannot only detect and eliminate theredundancy related to combining algorithms, but also evaluate access requests. AResource Brick Wall is constructed by the engine according to the resource attribute of a policy’s target attributes. By theResource Brick Wall and the policy/rule combining algorithms, three theorems for detectingredundancies related to combining algorithms are proposed. A comparison of the evaluation performance of theredundancy related to combining algorithms detecting and eliminating engine with that of Sun PDP is made. Experimental results show that the evaluation performance of the PDP can be prominently improved by eliminating theredundancy related to combining algorithms.


---

## Body

## 1. Introduction

Currently, access control is an important protection mechanism in the network and information security [1]. And using the security policy to describe security requirements in information systems has been the main method for authorization access control [2]. A policy can be defined as a group of descriptive principles implemented on the basis of practical requirements. These principles are the constraints for authorizing the system to make a decision. The XACML (eXtensible Access Control Markup Language) [3] is widely used in a distributed application system [4] in the SOA (Service-Oriented Architecture) [5] environment so that the security policy can be better expressed. The XACML is an open-standard language based on the XML and is used to standardize access control implemented in the XML (eXtensible Markup Language). It provides a uniform policy description language and improves the efficiency of collaboration among different organizations in the SOA environment. The XACML’s characteristics are as follows:(i)
Great adaptability: the XACML can be normally applied in multiple application environment.
(ii)
Preferable compatibility: the XACML supports multiple data types and policy/rule combining algorithms.
(iii)
Outstanding expression ability: the XACML can accurately express access control requirements with different complexities and fine grains.The XACML is a policy describing language with strong adaptability, universality, and extensibility and it supports distributed applications [6]. However, it does not have a standard agreement on factors such as granularity size, resource level, and condition interval [7]. Some rules in a policy may lose their effect because of policy/rule combining algorithms [8]. And a policy set may be formulated and edited by multiple administrators, each of whom has a different understanding of the policy and a different opinion on policy setting, which could lead to redundancies in a policy set’s rules [9]. Thus, detecting and eliminating theredundancy related to combining algorithms is the core and key point of our research.On the other hand, the XACML assumes that all the rules can be trusted, so a request might be responded to repeatedly [10]. In the authorization access control model, if the policy loaded on the PDP contains lots of redundancies related to policy/rule combining algorithms, it not only consumes and wastes lots of system resources, but also greatly increases the time the PDP spends in evaluating access requests. And then the evaluation performance of the PDP is affected. In policy management [11] based on the XACML, as many redundancies related to policy/rule combining algorithms must be eliminated as possible to accelerate the speed of policy matching so that the PDP in the authorization center can effectively make authorization decisions and feed authorization results back [12].To sum up, the important and critical problem to be solved is how to find an effective way to detect and eliminate theredundancy related to combining algorithms accurately and then improve the evaluation performance of the PDP.This paper makes the following contributions.(1)
Aredundancy related to combining algorithms detecting and eliminating engine is presented, which not only can detect and eliminate theredundancy related to combining algorithms in a policy and between policies, but also has the same ability as the PDP. This engine can evaluate the access control by loading policies whoseredundancies related to combining algorithms have been eliminated.
(2)
AResource Brick Wall is constructed by theredundancy related to combining algorithms detecting and eliminating engine according to theresource attribute in a policy’s target attributes. TheResource Brick Wall can effectively express the dependent relationship between resource attributes and detecting and eliminating theredundancy related to combining algorithms by the additional subject attribute, condition attribute, and effect information.
(3)
By theResource Brick Wall and policy/rule combining algorithms, the corresponding detecting and eliminating algorithm is proposed aiming at different types ofredundancies related to combining algorithms. This algorithm only compares a rule with those which are likely to generate redundancies and this could avoid a large number of unnecessary comparisons with irrelative rules. And it optimizes the traditional traversal redundancy detection and greatly improves the efficiency of detecting and eliminating redundancies.The remainder of this paper is organized as follows. Section2 reviews the related work on policy analysis, management, and high performance evaluation. Section 3 introduces definitions used in the research on theredundancy related to combining algorithms detection and elimination. In Section 4, aredundancy related to combining algorithms detecting and eliminating engine is introduced which can detect and eliminate theredundancy related to combining algorithms in a policy and between policies and evaluate access requests. In Section 5, aResource Brick Wall is proposed when we discuss theredundancy related to combining algorithms detecting and eliminating algorithm. Section 6 focuses on the theorems for detectingredundancies related to combining algorithms. A relevant detection and elimination algorithm for theredundancy related to combining algorithms is given in Section 7. Section 8 makes a comparison in evaluation performance between theredundancy related to combining algorithms detecting and eliminating engine and Sun PDP. Finally, Section 9 presents some conclusions and directions for our future work.


## 2. Related Work

There are numerous prior works on access control policies that mainly focus on policy evaluation, analysis, and testing to detect and eliminate redundancy. Masi et al. [13] formalized the XACML 2.0 semantics and proposed an alternative syntax supporting policy composition. They implemented a tool to compile policies into Java classes following the proposed semantic rules, where these classes are executed to compute policy decisions. Liu et al. [14] proposed XEngine, which can convert a textual XACML policy to a numerical policy and can convert a numerical policy with complex structures to a numerical policy with a normalized structure. Also, XEngine can convert the normalized numerical policy to tree data structures for efficient processing of requests. Marouf et al. [15] applied a clustering technique to policy sets based on the K-means algorithm. The proposed clustering technique categorizes policies and rules within a policy set and policy, respectively, in respect to target subjects. When a request is received, it is redirected to applicable policies and rules that correspond to its subjects, hence, avoiding unnecessary evaluations from occurring. Mourad and Jebbaoui [16] proposed (1) a mathematical intermediate representation of policies based on set theory that maintains the same XACML structure and accounts for all its elements and their subelements including rule conditions, obligations, policy request, and policy response and (2) a formal semantics that takes advantage of the mathematical operations to provide efficient evaluation of policy elements and constructs through deductive logic and inference rules. Jebbaoui et al. [17] resolve the complexity of policies by elaborating an intermediate set-based representation to which the elements of XACML are automatically converted. Moreover, it allows detecting flaws, conflicts, and redundancies between rules by offering new mechanisms to analyze the meaning of policy rules through semantics verification by inference rule structure and deductive logic.Recently, people focus more and more on studying the methods for detecting and eliminating policy redundancies. And researches on the policy redundancies can be categorized into two groups.(1)
The first group detect and eliminate redundancies by optimizing the XACML or improving the policy itself. Chen and Xu [18] analyzed the reason why policy redundancies exist first. Then they proposed formal methods based on the descriptive logic so that the machine can understand a policy’s semantics and context. On the basis of this, policy expansion and reasoning were carried on, which made the XACML gain better reasoning ability and semantics expressing ability. The method based on the descriptive logic can detect policy redundancies and eliminate these redundancies according to policy/rule combining algorithms. But every attribute in a policy’s target elements may cause redundancies and this problem was not fully considered in this paper. Lei et al. [19] indicated that although the XACML provides a convenient way to describe the security policy, this method still has its weakness. This paper analyzed the fact that using the XACML to express the inheritance relationship of rules will lead to policy redundancies and introduced atomic privilege to eliminate policy redundancies. Martin [20] indicated that if a rule is unreachable because of a group of constraints that this rule cannot meet, then it becomes a redundancy rule. A policy redundancy detection method based onChang-Impact analysis was presented in this paper; however, no corresponding detection model was proposed and the support and application of this detection technique were absent. Besides the above researches, policy redundancies can be detected by classifying the subject based on the security level and role [21, 22], and then all policy redundancies can be eliminated by revising policies.
(2)
The second group put forward policy redundancy detecting methods by establishing research models and relevant mechanisms. Aiming at this problem, Hu et al. [23] indicated that the Internet provides users with more convenient services, and at the same time the information system suffers from security attacks caused by unauthorized operations in business service. Besides, the design and management of the Web access control policy are always prone to errors for lack of efficient analysis mechanisms and tools. A policy analyzing method based on the Web access control was proposed in this paper. Also, a splitting technique based on the XACML policy was introduced to identify policy redundancies accurately and then policy redundancies could be eliminated. Dinu et al. [24] indicated that the XACML itself does not support policy redundancy analysis, though it has the great expression ability. The thought of state coverage was utilized to analyze the cause of policy redundancy, and a judging theorem that can be applied for redundancies within a policy or between policies under multiple policy/rule combining algorithms was put forward. The target element of a policy was considered when detecting redundancies in this paper while the condition factor’s effect on policy redundancies was ignored, which lead to the imperfection of redundancy detection. Zhang et al. [25] focused on security policy integration and redundancy elimination among different medical institutions. They emphasized that eliminating policy redundancies before healthcare institutions collaborate with each other is vitally important and pointed out that the present research does not consider how to eliminate redundancies in the dynamically loaded policy set according to the type of redundancy in the healthcare collaborative procedure. On the premise of taking both the constraint condition and metadata information, they also proposed a method based on the role-based access control policy model to eliminate redundancies in the XACML policy. Finally, they proposed a method of filtering and collecting the policies the user needs among different organizations and institutions. Guarnieri et al. [26] proposed three methods of eliminating redundancies in the access control policy and these methods reduced the authorization operation frequency in a policy step by step. They also indicated that problems relevant to redundancy belong to an NP-hard problem. Aiming at the Minimum Policy Problem and Minimum Irreducible Policy Problem in these problems, they proposed solutions for eliminating redundancies in the security policy.Mainly on the basis of optimizing the XACML or improving the policy itself, the above researches pointed out the great flexibility of the XACML policy structure and the difficulty in detecting policy redundancies. Detection was only applied to part of a policy while how to detect and eliminate the redundancy related to policy/rule combining algorithms was not considered. And their research did not go in depth and rarely considered the complex situation. Then, although the above researches can detect redundancies in a policy and between policies, they traverse rules in a policy many times in the process of detecting policy redundancies, which unavoidably increases the detection time. TheResource Brick Wall proposed in our paper carries out the reasonable partition and hierarchical process on resources. These processes can effectively avoid unnecessary comparisons among resources in different levels. Thus, they can optimize comparisons among rules and reduce the frequency of traversing each rule in a policy set when detecting redundancies and then improve the efficiency of detecting policy redundancies and lay a foundation for an efficient evaluation of the PDP.


## 3. Related Definitions

Since redundancy exists in rules within a policy or between different policies, the formal description of the relative definition of rules will be given first and the rules needed in detecting redundancies are also presented.Definition 1 (rule).
s
u
b
i
1, r
e
s
i
2, a
c
t
i
3, e
n
v
i
4, c
o
n
i
5, and E
f
f
e
c
t
i represent the elements of attributes like subject, resource, action, environment, condition, and effect, respectively, and these six attributes belong to the rule R
u
l
e
i. ⋃
i
1
=
1
m
s
u
b
i
1, ⋃
i
2
=
1
n
r
e
s
i
2, ⋃
i
3
=
1
o
a
c
t
i
3, ⋃
i
4
=
1
p
e
n
v
i
4, and ⋃
i
5
=
1
q
c
o
n
i
5 represent the union of elements of each attribute, respectively. And m
,
n
,
o
,
p and q are the number of each attribute’s elements. The definition of R
u
l
e
i can be represented by Formula (1) as follows:(1)
R
u
l
e
i
=
⋃
i
1
=
1
m
s
u
b
i
1
,
⋃
i
2
=
1
n
r
e
s
i
2
,
⋃
i
3
=
1
o
a
c
t
i
3
,
⋃
i
4
=
1
p
e
n
v
i
4
,
⋃
i
5
=
1
q
c
o
n
i
5
,
E
f
f
e
c
t
i
.There are three aspects needed to be made clear.(1)
Each resource discussed in this paper has a unique resource path. Resources on different resource paths are identified as different resources. In other words, we think that two identical resources can only appear on an identical resource path and cannot appear on different resource paths.
(2)
We just focus on the clock time when studying the condition attribute.
(3)
The environment attribute will be ignored in the following analysis and discussion, because it does not cause theredundancy related to combining algorithms, which is studied in this paper.Definition 2 (state satisfaction).
If a subject attributes
u
b
i
1 in R
u
l
e
i can access the resource attribute r
e
s
i
2 with action a
c
t
i
3 in the condition of c
o
n
i
4 and its effect is E
f
f
e
c
t
i (Deny orPermit), then one has the definition that S
t
a
t
e
i satisfies (
s
u
b
i
1
,
r
e
s
i
2
,
a
c
t
i
3
,
c
o
n
i
4
,
E
f
f
e
c
t
i
), as shown in Formula (2) as follows:(2)
S
t
a
t
e
i
⊳
s
u
b
i
1
,
r
e
s
i
2
,
a
c
t
i
3
,
c
o
n
i
4
,
E
f
f
e
c
t
i
.Definition 3 (atomic attribute).
If an attribute in a rule has no more than one element which may be absent, then one calls this attribute theatomic attribute.Definition 4 (composite attribute).
If an attribute in a rule has more than one element, then one calls it thecomposite attribute.Since rules containing the atomic attribute are easier to store and process than those containing the composite attribute, so we need to apply attribute atomization to rules containing composite rules.Rule 1 (rule attribute atomization).
If there arecomposite attributes in a rule, one can divide acomposite attribute into severalatomic attributes and then composite it with other attributes’ elements. Finally, one can get several rules which only containatomic attribute.By Rule1, we can carry out attribute atomization on all rules in a policy and transfer them into rules containing only the atomic attribute. Thus, we lay the foundation for building and theoretical analysis of theredundancy related to combining algorithms detecting and eliminating engine.Definition 5 (dependent relationship of resources).
For resource attributesr
e
s
1 and r
e
s
2, if r
e
s
1 is in the upper level compared to r
e
s
2, then one says that resource attributes r
e
s
1 and r
e
s
2 satisfy thedependent relationship of resources. r
e
s
2’s dependency on r
e
s
1 is denoted as r
e
s
1
↦
r
e
s
2.Definition 6 (overlapping relationship of conditions).
For condition attributesc
o
n
1 and c
o
n
2, if c
o
n
1
∩
c
o
n
2
≠
⌀, one says that condition attributes c
o
n
1 and c
o
n
2 satisfy theoverlapping relationship of conditions. The intersection between c
o
n
1 and c
o
n
2 is denoted as c
o
n
1
⊙
c
o
n
2.Definition 7 (redundancy).
For a rule in a policy, if its function cannot work, namely, this rule will not affect the result of evaluating access requests, then one calls this rule a redundancy rule:(3)
R
1
=
s
u
b
1
,
r
e
s
1
,
a
c
t
1
,
c
o
n
1
,
E
f
f
e
c
t
1
,
R
2
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
,
E
f
f
e
c
t
2
.Definition 8 (common resource redundancy).
For two rulesR
1 and R
2 as shown in Formula (3), they belong to the same policy or two different policies. If R
1 and R
2 have the same subject attribute, resource attribute, action attribute, and environment attribute (the environment attribute will be ignored), and without loss of generality, their condition attributes have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀) and their effects are the same (i.e., to say these two rules’ E
f
f
e
c
t
i should beDeny orPermit at the same time); then thecommon resource redundancy happens between R
1 and R
2. These conditions could be expressed by Formula (4) as follows:(4)
s
u
b
1
=
s
u
b
2
∧
r
e
s
1
=
r
e
s
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
∧
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
.Definition 9 (dependent resource redundancy).
For two rulesR
1 and R
2 as shown in Formula (3), they belong to the same policy or two different policies. If R
1 and R
2 have the same subject attribute, action attribute, and environment attribute (the environment attribute will be ignored), and without loss of generality, there exists thedependent relationship of resources between R
1 and R
2 (r
e
s
1
↦
r
e
s
2), their condition attributes have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀), and their effects are bothDeny; then thedependent resource redundancy happens between R
1 and R
2. These conditions could be expressed by Formula (5) as follows: (5)
s
u
b
1
=
s
u
b
2
∧
r
e
s
1
⟼
r
e
s
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
∧
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
D
e
n
y
.Definition 10 (redundancy related to combining algorithms).
For a redundancy identified as theredundancy related to combining algorithms, the prerequisite is that the detection is on the basis of the policy/rule combining algorithms.This paper aims at statically detecting and eliminating theredundancy related to combining algorithms in the policies loaded on the PDP, so that the evaluation performance of the PDP can be improved. The research in this paper focuses on theredundancy related to combining algorithms and its detecting and eliminating algorithm is proposed to solve this kind of problem.


## 4. Redundancy Related to Combining Algorithms Detecting and Eliminating Engine XDPRE

Our proposedredundancy related to combining algorithms detecting and eliminating engine termed theXDPRE (XiDian Policy Redundancy Engine) is shown in Figure 1. TheXDPRE is able to detect and eliminate theredundancy related to combining algorithms within a policy or between policies. TheXDPRE receives all the policies P
o
l
i
c
y
1
,
P
o
l
i
c
y
2
,
…
,
P
o
l
i
c
y
n in the policy setPolicySet as the input and its responsibilities are shown in the following three aspects.(1)
Detect and eliminate theredundancy related to combining algorithms within a policy.
(2)
Detect and eliminate theredundancy related to combining algorithms between policies.
(3)
TheXDPRE itself has the function of the PDP. By loading policies whoseredundancies related to combining algorithms have been eliminated, theXDPRE can evaluate access requests and return the authorization result to context processors and the PDP.Figure 1
Redundancy related to combining algorithms detecting and eliminating engine XDPRE.The output of theXDPRE is a new policy set termed P
o
l
i
c
y
S
e
t
′. And there is noredundancy related to combining algorithms in the policy P
o
l
i
c
y
1
′
,
P
o
l
i
c
y
2
′
,
…
,
P
o
l
i
c
y
n
′ of the policy set P
o
l
i
c
y
S
e
t
′.We adopt theXDPRE to detect and eliminate theredundancy related to combining algorithms within a policy and between policies successively.


## 5. Resource Brick Wall

In order to detect and eliminate theredundancy related to combining algorithms contained in the policies loaded on the PDP, so as to achieve the purpose of efficient evaluation of the PDP, in this section, we construct theResource Brick Wall (RBW) in theXDPRE, an engine for detecting and eliminating theredundancy related to combining algorithms, based on the resources existing in the target attribute of policies, as shown in Figure 2.Figure 2
Resource Brick Wall.
(a)
Relation between Resource Brick Wall and three-dimensional coordinate axes
(b)
Resource Brick Wall and its SCELDefinition 11 (Resource Brick Wall).
For each resource in the rules, one builds aresource brick, and then according to the dependent relationship between resources, one can build aResource Brick Wall of all the bricks representing resources from top to bottom, as shown in Figure 2(a). The axisCon represents the condition attribute in the rules corresponding to each resource and the height of a resource brick is equal to the size of time distinct of its condition attribute. The axisLev represents the level corresponding to each resource. The axisRes represents resources; the length of a resource brick in the ith  (
i
≥
1
) layer equals the sum of all the resources which have the dependency with it in the (i
+
1)th layer. Each resource brick has correlation with aSubject-Condition-Effect List (SCEL). TheSCEL stores all the subject attributes’ information corresponding to the resources the resource brick represents, as well as the condition attribute information and effect information of these subjects, as shown in Figure 2(b). As for the resource brick r
e
s, itsSCEL is denoted as the S
C
E
L
r
e
s in which any subject attribute s
u
b is denoted as s
u
b
r
e
s. In Figure 2(a), r
e
s
0 is the first layer resource, and r
e
s
1, r
e
s
2(r
e
s
2
′), and r
e
s
3(r
e
s
3
′) are all the lower resources of r
e
s
0, that is, the second layer resource. r
e
s
2 and r
e
s
2
′ are the same resource attribute of two different rules, whose condition attributes have an overlapping relationship. r
e
s
3 and r
e
s
3
′ are also the same resource attribute of two different rules whose condition attributes do not have an overlapping relationship.It is worth noting that if two resource bricks are the same, we should view them as one and merge their correspondingSCELs to ensure that each of the resource bricks in theRBW is the only one. TheRBW can efficiently represent thedependent relationship of resources.There is a hierarchical relationship between resource attributes. For example, the hierarchical relationship of the system resource directory is represented by the dependent relationship between resource attributes. According to the definition specification of the target attribute in the XACML (Version 3.0) OASIS [27], together with the definition of state satisfaction, we give the transmission rules of access authority, as shown in Rule 2.Rule 2 (transmission rules of access authority).
As for the two resource attributesr
e
s
1 and r
e
s
2 in the two rules R
1 and R
2, when r
e
s
1 and r
e
s
2 satisfy r
e
s
1
↦
r
e
s
2, consider the following:
① If a subjects
u
b
0 of the subject set S
u
b
j
e
c
t
S
e
t
r
e
s
1
D
e
n
y of the resource attribute r
e
s
1 denies accessing resource attribute r
e
s
1, then it also denies accessing its dependent resource r
e
s
2, as shown in Formula (6) as follows:(6)
S
t
a
t
e
i
⊳
s
u
b
0
,
r
e
s
1
,
a
c
t
,
c
o
n
i
,
D
e
n
y
r
e
s
1
⟼
r
e
s
2
⟹
S
t
a
t
e
i
⊳
s
u
b
0
,
r
e
s
2
,
a
c
t
,
c
o
n
i
,
D
e
n
y
.
② If a subjects
u
b
0 of the subject set S
u
b
j
e
c
t
S
e
t
r
e
s
1
P
e
r
m
i
t of the resource attribute r
e
s
1 permits accessing resource attribute r
e
s
1, then we cannot deduce what operation of access authority it has to the dependent resource attribute r
e
s
2 (E
f
f
c
e
t
i isDeny orPermit), as shown in Formula (7) as follows:(7)
S
t
a
t
e
i
⊳
s
u
b
0
,
r
e
s
1
,
a
c
t
,
c
o
n
i
,
P
e
r
m
i
t
r
e
s
1
⟼
r
e
s
2
⇏
S
t
a
t
e
i
⊳
s
u
b
0
,
r
e
s
2
,
a
c
t
,
c
o
n
i
,
E
f
f
e
c
t
i
.The transmission rules of access authority can be summarized as the form of Figure3. In Figure 3, between r
e
s
1 and r
e
s
2 exists the dependent relationship r
e
s
1
↦
r
e
s
2. If a subject s
u
b
0 denies accessing the upper layer resource attribute, we can deduce that it also denies accessing the lower layer resource attribute r
e
s
2. The solid line marked Y in the figure indicates thatDeny access authority can be transmitted from the upper resource attribute to the lower resource attribute. If a subject s
u
b
0 permits accessing the upper resource attribute, we cannot deduce what operation of access authority it has to the lower resource attribute r
e
s
2, and the dotted line marked N in the figure indicates thatPermit access authority cannot be transmitted from the upper resource attribute to the lower resource attribute. For example, if the subject E
m
p
l
o
y
e
e denies the writing operation to the resourceE:∖File, then we can deduce that it denies the writing operation to the resourceE:∖File∖ProductFile. However, if the subject E
m
p
l
o
y
e
e permits the writing operation to theE:∖File, then we cannot deduce what operation of access authority it has to the resourceE:∖File∖ProductFile.Figure 3
Transmission relationship of access authority.


## 6. Detection and Elimination of Redundancy Related to Combining Algorithms

The eventual evaluation result of a rule in a policy depends on the evaluation of the condition attribute. If the return value of the condition isIndeterminate, the rule will returnIndeterminate. If the return value of the condition isFalse, the rule will returnNotApplicable. If the return value of the condition isTrue, the rule will returnEffect, which can bePermit orDeny.For a redundancy identified as theredundancy related to combining algorithms, the prerequisite is that the detection is on the basis of the policy/rule combining algorithms. The definition and application of the policy/rule combining algorithms are related to the return value of evaluation result, which isIndeterminate,NotApplicable,Permit, orDeny. Because the return valueIndeterminate occurs when faults appear in evaluation andNotApplicable occurs when the matched rule is not found, the two return values are meaningless for discussing and analyzing whether there exists redundancy in rules. Therefore, in this section we only discuss and analyze redundancy when the return value isPermit orDeny and ignoreIndeterminate orNotApplicable.This section proposes three theorems for detectingredundancies related to combining algorithms according to the “Deny-Overrides”, “Permit-Overrides”, and “First-Applicable” policy/rule combining algorithms supported by the XACML standards and gives the methods for eliminatingredundancies related to combining algorithms.


### 6.1. Redundancy Related to the Deny-Overrides Combining Algorithm

The policy combining algorithms and rule combining algorithms supported by the XACML standards all contain “Deny-Overrides”; that is, if the effect of either of the policies (or rules) isDeny, the final authorized result isDeny. Next, we give the theorem for detecting theredundancy related to “Deny-Overrides”combing algorithm with the “Deny-Overrides” policy/rule combining algorithm:(8)
R
1
=
s
u
b
1
,
r
e
s
1
,
a
c
t
1
,
c
o
n
1
,
E
f
f
e
c
t
1
,
R
2
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
,
E
f
f
e
c
t
2
.Theorem 12.
In the condition of the “Deny-Overrides” policy/rule combining algorithm, for any two rules R
1 and R
2 in a policy or between policies, as represented by Formula (8), if R
1 and R
2 have the same subject attribute “s
u
b” and action attribute “a
c
t”, and there is an overlapping relationship between the condition attributes of R
1 and R
2 (c
o
n
1
∩
c
o
n
2
≠
⌀), and if, without losing the generality, between the resource attributes of R
1 and R
2 exists the equation relationship (r
e
s
1
=
r
e
s
2) or dependent relationship (r
e
s
1
↦
r
e
s
2) and the effect of R
1 is “Deny”, that is, Formula (9) is satisfied, then R
2 is the redundancy rule: (9)
s
u
b
1
=
s
u
b
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
∧
r
e
s
1
=
r
e
s
2
∧
r
e
s
1
⟼
r
e
s
2
∧
E
f
f
e
c
t
1
=
D
e
n
y
.Proof.
State satisfaction of rulesR
1 and R
2 is as shown in Formula (10) as follows:(10)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
D
e
n
y
,
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
.According to the relationship of resource attributes of rules R
1 and R
2 and the different effect values of R
2, we give the proof in the following four situations:
① Whenr
e
s
1
=
r
e
s
2 and E
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal derivation process as shown in Formula (11) as follows:(11)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
D
e
n
y
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “Deny-Overrides” policy/rule combining algorithm, R
2 is the redundancy rule.
② Whenr
e
s
1
=
r
e
s
2 and E
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀), according to the definition of “Deny-Overrides” policy/rule combining algorithm, under the condition that there appear no faults, we finally should use the effect E
f
f
e
c
t
1
=
D
e
n
y of R
1 as the authorization result. However, the rule R
2 does not have any effect on the process of evaluation, so the function of the rule cannot be realized. Therefore, according to Definition 7, we conclude that R
2 is the redundancy rule.
③ Whenr
e
s
1
↦
r
e
s
2 and E
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal derivation process as shown in Formula (12) as follows:(12)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
⟼
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
D
e
n
y
⇓
R
e
d
u
n
d
a
n
c
y
↦
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
↦
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the assumptions and Definition9, we deduct that rules R
1 and R
2 have thedependent resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “Deny-Overrides” policy/rule combining algorithm, R
2 is the redundancy rule.
④ Whenr
e
s
1
↦
r
e
s
2 and E
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2. According to Rule 2 (the transmission rules of access authority), we can get Formula (13) as follows:(13)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
D
e
n
y
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
⟼
r
e
s
2
⟹
S
t
a
t
e
1
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
1
,
D
e
n
y
.
From Formula (13), we can conclude that S
t
a
t
e
1 satisfies the fact that the subject s
u
b
r
e
s
1 of R
1 denies accessing to the resource r
e
s
1 in the condition c
o
n
1, and from assumptions and Formula (10) we can conclude that S
t
a
t
e
2 satisfies the fact that the same subject s
u
b
r
e
s
2 of R
2 permits accessing to r
e
s
2 which is the same as r
e
s
1 in the condition c
o
n
2. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀), according to the conclusion of proof ②, we can conclude that R
2 is the redundancy rule.According to Theorem12, we can obtain the form derivation of detecting theredundancy related to the “Deny-Overrides”combining algorithm, as shown in Formula (14), where(i)
R
e
d
u
n
d
a
n
c
y
D
O
(
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that S
t
a
t
e
1 satisfying the rule R
1 and S
t
a
t
e
2 satisfying the rule R
2 have theredundancy related to the “Deny-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2;
(ii)
R
e
d
u
n
d
a
n
c
y
D
O
(
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that the rule R
1 corresponding to the S
t
a
t
e
1 and the rule R
2 corresponding to the S
t
a
t
e
2 have theredundancy related to the “Deny-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2: (14)
C
o
m
b
i
n
i
n
g
A
l
g
=
D
e
n
y
-
O
v
e
r
r
i
d
e
s
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
D
e
n
y
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
∪
r
e
s
1
⟼
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
⇓
R
e
d
u
n
d
a
n
c
y
D
O
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
D
O
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.When detecting theredundancy related to the“Deny-Overrides”combining algorithm between the two rules R
1 and R
2 (as shown in Formula (8)) in a policy or between policies, the method for eliminating the redundancy is to reserve the rule R
1 firstly. If c
o
n
1
⊙
c
o
n
2
=
c
o
n
2, we will delete the rule R
2 directly. If c
o
n
1
⊙
c
o
n
2
≠
c
o
n
2, we will update the condition attribute of the rule R
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2, that is, update the rule R
2 to a new rule as shown in Formula (15) as follows: (15)
R
2
′
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2
,
E
f
f
e
c
t
2
.


### 6.2. Redundancy Related to the Permit-Overrides Combining Algorithm

The policy combining algorithms and rule combining algorithms supported by the XACML standards all contain “Permit-Overrides”; that is, if the return effect of either of the policies (or rules) isPermit, the final authorized result isPermit. Next, we give the theorem for detecting theredundancy related to“Permit-Overrides”combing algorithm with the “Permit-Overrides” policy/rule combining algorithm: (16)
R
1
=
s
u
b
1
,
r
e
s
1
,
a
c
t
1
,
c
o
n
1
,
E
f
f
e
c
t
1
,
R
2
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
,
E
f
f
e
c
t
2
.Theorem 13.
In the condition of the “Permit-Overrides” policy/rule combining algorithm, for any two rules R
1 and R
2 in a policy or between policies, as shown in Formula (16), if R
1 and R
2 have the same subject attribute “s
u
b”, resource attribute “r
e
s”, and action attributes “a
c
t”, and there is an overlapping relationship between the condition attributes of R
1 and R
2 (c
o
n
1
∩
c
o
n
2
≠
⌀), without losing the generality, one supposes that the effect of R
1 isPermit; that is, Formula (17) is satisfied, and then R
2 is the redundancy rule: (17)
s
u
b
1
=
s
u
b
2
∧
r
e
s
1
=
r
e
s
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
∧
E
f
f
e
c
t
1
=
P
e
r
m
i
t
.Proof.
State satisfaction of rulesR
1 and R
2 is as shown in Formula (18) as follows:(18)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
P
e
r
m
i
t
,
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
.In Formula (18), r
e
s
1
=
r
e
s
2. According to the different effect values of R
2, we give the proof in the following two situations:
① WhenE
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀), according to the definition of “Permit-Overrides” policy/rule combining algorithm, under the condition that there appear no faults, we should finally use the effect E
f
f
e
c
t
1
=
P
e
r
m
i
t of R
1 as the authorization result. However, the rule R
2 does not have any effect on the process of evaluation, so the function of the rule cannot be realized. Therefore, according to Definition 7, we conclude that R
2 is the redundancy rule in the “Permit-Overrides” policy/rule combining algorithm.
② WhenE
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the form deduction process as shown in Formula (19) as follows:(19)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
P
e
r
m
i
t
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “Permit-Overrides” policy/rule combining algorithm, R
2 is the redundancy rule.According to Theorem13, we can conclude that the form derivation of detecting theredundancy related to the “Permit-Overrides”combining algorithm is as shown in Formula (20), where(i)
R
e
d
u
n
d
a
n
c
y
P
O
(
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that S
t
a
t
e
1 satisfying the rule R
1 and S
t
a
t
e
2 satisfying the rule R
2 have theredundancy related to the“Permit-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2;
(ii)
R
e
d
u
n
d
a
n
c
y
P
O
(
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that the rule R
1 corresponding to the S
t
a
t
e
1 and the rule R
2 corresponding to the S
t
a
t
e
2 have theredundancy related to the “Permit-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2:(20)
C
o
m
b
i
n
i
n
g
A
l
g
=
P
e
r
m
i
t
-
O
v
e
r
r
i
d
e
s
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
P
e
r
m
i
t
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
⇓
R
e
d
u
n
d
a
n
c
y
P
O
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
P
O
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.When detecting theredundancy related to the “Permit-Overrides”combining algorithm between the two rules R
1 and R
2 (as shown in Formula (16)) in a policy or between policies, the method for eliminating the redundancy is to reserve the rule R
1 firstly. If c
o
n
1
⊙
c
o
n
2
=
c
o
n
2, we will delete the rule R
2 directly. If c
o
n
1
⊙
c
o
n
2
≠
c
o
n
2, we will update the condition attribute of the rule R
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2, that is, update the rule R
2 to a new rule as shown in Formula (21) as follows: (21)
R
2
′
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2
,
E
f
f
e
c
t
2
.


### 6.3. Redundancy Related to the First-Applicable Combining Algorithm

The policy combining algorithms and rule combining algorithms supported by the XACML standards all contain “First-Applicable”; that is, the final authorized result of policy (or rule) is the judgment result of the first matched policy (or rule). Next, we give the theorem for detecting theredundancy related to“First-Applicable”combing algorithm with the “First-Applicable” policy/rule combining algorithm: (22)
R
1
=
s
u
b
1
,
r
e
s
1
,
a
c
t
1
,
c
o
n
1
,
E
f
f
e
c
t
1
,
R
2
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
,
E
f
f
e
c
t
2
.Theorem 14.
In the condition of the “First-Applicable” policy/rule combining algorithm, for any two rules R
1 and R
2 in a policy or between policies, as shown in Formula (22), if R
1 and R
2 have the same subject attribute “s
u
b”, resource attribute “r
e
s”, and action attribute “a
c
t”, and there is an overlapping relationship between the condition attributes of R
1 and R
2 (c
o
n
1
⊙
c
o
n
2
≠
⌀), that is, Formula (23) is satisfied, without losing the generality, one supposes that R
1 is the first applicable rule, and then R
2 is the redundancy rule: (23)
s
u
b
1
=
s
u
b
2
∧
r
e
s
1
=
r
e
s
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
.Proof.
State satisfaction of rulesR
1 and R
2 is as shown in Formula (24) as follows:(24)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
,
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
.In Formula (24), r
e
s
1
=
r
e
s
2. According to the different effect values of R
2, we give the proof in the following three situations:
① WhenE
f
f
e
c
t
1
=
D
e
n
y and E
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal deduction process as shown in Formula (25) as follows: (25)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
D
e
n
y
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “First-Applicable” policy/rule combining algorithm and R
1 is the first applicable rule, R
2 is the redundancy rule.
② WhenE
f
f
e
c
t
1
=
P
e
r
m
i
t and E
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal derivation process as shown in Formula (26) as follows:(26)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
P
e
r
m
i
t
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “First-Applicable” policy/rule combining algorithm and R
1 is the first applicable rule, R
2 is the redundancy rule.
③E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2 (i.e., E
f
f
e
c
t
1
=
D
e
n
y and E
f
f
e
c
t
2
=
P
e
r
m
i
t, or E
f
f
e
c
t
1
=
P
e
r
m
i
t and E
f
f
e
c
t
2
=
D
e
n
y) and R
1 is the first applicable rule. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
⊙
c
o
n
2
≠
⌀), according to the definition of “First-Applicable” policy/rule combining algorithm, under the condition that there appear no faults, we finally should use the effect E
f
f
e
c
t
1 of R
1 as the authorization result. However, the rule R
2 does not have any effect on the process of evaluation; the function of the rule cannot be realized. Therefore, according to Definition 7, we conclude that R
2 is the redundancy rule in the “First-Applicable” policy/rule combining algorithm.According to Theorem14, we can conclude the form derivation of detecting theredundancy related to the “First-Applicable” combining algorithm, as shown in Formula (27), where(i)
R
1 is the first applicable rule;
(ii)
R
e
d
u
n
d
a
n
c
y
F
A
(
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that S
t
a
t
e
1 satisfying the rule R
1 and S
t
a
t
e
2 satisfying the rule R
2 have theredundancy related to the “First-Applicable” combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2;
(iii)
R
e
d
u
n
d
a
n
c
y
F
A
(
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that the rule R
1 corresponding to the S
t
a
t
e
1 and the rule R
2 corresponding to the S
t
a
t
e
2 have theredundancy related to the “First-Applicable” combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2:(27)
C
o
m
b
i
n
i
n
g
A
l
g
=
F
i
r
s
t
-
O
v
e
r
r
i
d
e
s
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
⇓
R
e
d
u
n
d
a
n
c
y
F
A
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
F
A
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.When detecting theredundancy related to the “First-Applicable”combining algorithm by Theorem 14 between the two rules R
1 and R
2 (as Formula (22) shows) in a policy or between policies, without losing the generality, we suppose that R
1 is the first applicable rule; the method for eliminating the redundancy is to reserve the rule R
1 firstly. If c
o
n
1
⊙
c
o
n
2
=
c
o
n
2, we will delete the rule R
2 directly. If c
o
n
1
⊙
c
o
n
2
≠
c
o
n
2, we will update the condition attribute of the rule R
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2, that is, update the rule R
2 to a new rule as shown in Formula (28) as follows: (28)
R
2
′
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2
,
E
f
f
e
c
t
2
.


## 6.1. Redundancy Related to the Deny-Overrides Combining Algorithm

The policy combining algorithms and rule combining algorithms supported by the XACML standards all contain “Deny-Overrides”; that is, if the effect of either of the policies (or rules) isDeny, the final authorized result isDeny. Next, we give the theorem for detecting theredundancy related to “Deny-Overrides”combing algorithm with the “Deny-Overrides” policy/rule combining algorithm:(8)
R
1
=
s
u
b
1
,
r
e
s
1
,
a
c
t
1
,
c
o
n
1
,
E
f
f
e
c
t
1
,
R
2
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
,
E
f
f
e
c
t
2
.Theorem 12.
In the condition of the “Deny-Overrides” policy/rule combining algorithm, for any two rules R
1 and R
2 in a policy or between policies, as represented by Formula (8), if R
1 and R
2 have the same subject attribute “s
u
b” and action attribute “a
c
t”, and there is an overlapping relationship between the condition attributes of R
1 and R
2 (c
o
n
1
∩
c
o
n
2
≠
⌀), and if, without losing the generality, between the resource attributes of R
1 and R
2 exists the equation relationship (r
e
s
1
=
r
e
s
2) or dependent relationship (r
e
s
1
↦
r
e
s
2) and the effect of R
1 is “Deny”, that is, Formula (9) is satisfied, then R
2 is the redundancy rule: (9)
s
u
b
1
=
s
u
b
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
∧
r
e
s
1
=
r
e
s
2
∧
r
e
s
1
⟼
r
e
s
2
∧
E
f
f
e
c
t
1
=
D
e
n
y
.Proof.
State satisfaction of rulesR
1 and R
2 is as shown in Formula (10) as follows:(10)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
D
e
n
y
,
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
.According to the relationship of resource attributes of rules R
1 and R
2 and the different effect values of R
2, we give the proof in the following four situations:
① Whenr
e
s
1
=
r
e
s
2 and E
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal derivation process as shown in Formula (11) as follows:(11)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
D
e
n
y
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “Deny-Overrides” policy/rule combining algorithm, R
2 is the redundancy rule.
② Whenr
e
s
1
=
r
e
s
2 and E
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀), according to the definition of “Deny-Overrides” policy/rule combining algorithm, under the condition that there appear no faults, we finally should use the effect E
f
f
e
c
t
1
=
D
e
n
y of R
1 as the authorization result. However, the rule R
2 does not have any effect on the process of evaluation, so the function of the rule cannot be realized. Therefore, according to Definition 7, we conclude that R
2 is the redundancy rule.
③ Whenr
e
s
1
↦
r
e
s
2 and E
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal derivation process as shown in Formula (12) as follows:(12)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
⟼
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
D
e
n
y
⇓
R
e
d
u
n
d
a
n
c
y
↦
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
↦
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the assumptions and Definition9, we deduct that rules R
1 and R
2 have thedependent resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “Deny-Overrides” policy/rule combining algorithm, R
2 is the redundancy rule.
④ Whenr
e
s
1
↦
r
e
s
2 and E
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2. According to Rule 2 (the transmission rules of access authority), we can get Formula (13) as follows:(13)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
D
e
n
y
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
⟼
r
e
s
2
⟹
S
t
a
t
e
1
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
1
,
D
e
n
y
.
From Formula (13), we can conclude that S
t
a
t
e
1 satisfies the fact that the subject s
u
b
r
e
s
1 of R
1 denies accessing to the resource r
e
s
1 in the condition c
o
n
1, and from assumptions and Formula (10) we can conclude that S
t
a
t
e
2 satisfies the fact that the same subject s
u
b
r
e
s
2 of R
2 permits accessing to r
e
s
2 which is the same as r
e
s
1 in the condition c
o
n
2. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀), according to the conclusion of proof ②, we can conclude that R
2 is the redundancy rule.According to Theorem12, we can obtain the form derivation of detecting theredundancy related to the “Deny-Overrides”combining algorithm, as shown in Formula (14), where(i)
R
e
d
u
n
d
a
n
c
y
D
O
(
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that S
t
a
t
e
1 satisfying the rule R
1 and S
t
a
t
e
2 satisfying the rule R
2 have theredundancy related to the “Deny-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2;
(ii)
R
e
d
u
n
d
a
n
c
y
D
O
(
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that the rule R
1 corresponding to the S
t
a
t
e
1 and the rule R
2 corresponding to the S
t
a
t
e
2 have theredundancy related to the “Deny-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2: (14)
C
o
m
b
i
n
i
n
g
A
l
g
=
D
e
n
y
-
O
v
e
r
r
i
d
e
s
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
D
e
n
y
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
∪
r
e
s
1
⟼
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
⇓
R
e
d
u
n
d
a
n
c
y
D
O
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
D
O
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.When detecting theredundancy related to the“Deny-Overrides”combining algorithm between the two rules R
1 and R
2 (as shown in Formula (8)) in a policy or between policies, the method for eliminating the redundancy is to reserve the rule R
1 firstly. If c
o
n
1
⊙
c
o
n
2
=
c
o
n
2, we will delete the rule R
2 directly. If c
o
n
1
⊙
c
o
n
2
≠
c
o
n
2, we will update the condition attribute of the rule R
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2, that is, update the rule R
2 to a new rule as shown in Formula (15) as follows: (15)
R
2
′
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2
,
E
f
f
e
c
t
2
.


## 6.2. Redundancy Related to the Permit-Overrides Combining Algorithm

The policy combining algorithms and rule combining algorithms supported by the XACML standards all contain “Permit-Overrides”; that is, if the return effect of either of the policies (or rules) isPermit, the final authorized result isPermit. Next, we give the theorem for detecting theredundancy related to“Permit-Overrides”combing algorithm with the “Permit-Overrides” policy/rule combining algorithm: (16)
R
1
=
s
u
b
1
,
r
e
s
1
,
a
c
t
1
,
c
o
n
1
,
E
f
f
e
c
t
1
,
R
2
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
,
E
f
f
e
c
t
2
.Theorem 13.
In the condition of the “Permit-Overrides” policy/rule combining algorithm, for any two rules R
1 and R
2 in a policy or between policies, as shown in Formula (16), if R
1 and R
2 have the same subject attribute “s
u
b”, resource attribute “r
e
s”, and action attributes “a
c
t”, and there is an overlapping relationship between the condition attributes of R
1 and R
2 (c
o
n
1
∩
c
o
n
2
≠
⌀), without losing the generality, one supposes that the effect of R
1 isPermit; that is, Formula (17) is satisfied, and then R
2 is the redundancy rule: (17)
s
u
b
1
=
s
u
b
2
∧
r
e
s
1
=
r
e
s
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
∧
E
f
f
e
c
t
1
=
P
e
r
m
i
t
.Proof.
State satisfaction of rulesR
1 and R
2 is as shown in Formula (18) as follows:(18)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
P
e
r
m
i
t
,
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
.In Formula (18), r
e
s
1
=
r
e
s
2. According to the different effect values of R
2, we give the proof in the following two situations:
① WhenE
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
∩
c
o
n
2
≠
⌀), according to the definition of “Permit-Overrides” policy/rule combining algorithm, under the condition that there appear no faults, we should finally use the effect E
f
f
e
c
t
1
=
P
e
r
m
i
t of R
1 as the authorization result. However, the rule R
2 does not have any effect on the process of evaluation, so the function of the rule cannot be realized. Therefore, according to Definition 7, we conclude that R
2 is the redundancy rule in the “Permit-Overrides” policy/rule combining algorithm.
② WhenE
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the form deduction process as shown in Formula (19) as follows:(19)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
P
e
r
m
i
t
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “Permit-Overrides” policy/rule combining algorithm, R
2 is the redundancy rule.According to Theorem13, we can conclude that the form derivation of detecting theredundancy related to the “Permit-Overrides”combining algorithm is as shown in Formula (20), where(i)
R
e
d
u
n
d
a
n
c
y
P
O
(
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that S
t
a
t
e
1 satisfying the rule R
1 and S
t
a
t
e
2 satisfying the rule R
2 have theredundancy related to the“Permit-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2;
(ii)
R
e
d
u
n
d
a
n
c
y
P
O
(
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that the rule R
1 corresponding to the S
t
a
t
e
1 and the rule R
2 corresponding to the S
t
a
t
e
2 have theredundancy related to the “Permit-Overrides”combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2:(20)
C
o
m
b
i
n
i
n
g
A
l
g
=
P
e
r
m
i
t
-
O
v
e
r
r
i
d
e
s
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
P
e
r
m
i
t
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
⇓
R
e
d
u
n
d
a
n
c
y
P
O
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
P
O
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.When detecting theredundancy related to the “Permit-Overrides”combining algorithm between the two rules R
1 and R
2 (as shown in Formula (16)) in a policy or between policies, the method for eliminating the redundancy is to reserve the rule R
1 firstly. If c
o
n
1
⊙
c
o
n
2
=
c
o
n
2, we will delete the rule R
2 directly. If c
o
n
1
⊙
c
o
n
2
≠
c
o
n
2, we will update the condition attribute of the rule R
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2, that is, update the rule R
2 to a new rule as shown in Formula (21) as follows: (21)
R
2
′
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2
,
E
f
f
e
c
t
2
.


## 6.3. Redundancy Related to the First-Applicable Combining Algorithm

The policy combining algorithms and rule combining algorithms supported by the XACML standards all contain “First-Applicable”; that is, the final authorized result of policy (or rule) is the judgment result of the first matched policy (or rule). Next, we give the theorem for detecting theredundancy related to“First-Applicable”combing algorithm with the “First-Applicable” policy/rule combining algorithm: (22)
R
1
=
s
u
b
1
,
r
e
s
1
,
a
c
t
1
,
c
o
n
1
,
E
f
f
e
c
t
1
,
R
2
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
,
E
f
f
e
c
t
2
.Theorem 14.
In the condition of the “First-Applicable” policy/rule combining algorithm, for any two rules R
1 and R
2 in a policy or between policies, as shown in Formula (22), if R
1 and R
2 have the same subject attribute “s
u
b”, resource attribute “r
e
s”, and action attribute “a
c
t”, and there is an overlapping relationship between the condition attributes of R
1 and R
2 (c
o
n
1
⊙
c
o
n
2
≠
⌀), that is, Formula (23) is satisfied, without losing the generality, one supposes that R
1 is the first applicable rule, and then R
2 is the redundancy rule: (23)
s
u
b
1
=
s
u
b
2
∧
r
e
s
1
=
r
e
s
2
∧
a
c
t
1
=
a
c
t
2
∧
c
o
n
1
∩
c
o
n
2
≠
⌀
.Proof.
State satisfaction of rulesR
1 and R
2 is as shown in Formula (24) as follows:(24)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
,
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
.In Formula (24), r
e
s
1
=
r
e
s
2. According to the different effect values of R
2, we give the proof in the following three situations:
① WhenE
f
f
e
c
t
1
=
D
e
n
y and E
f
f
e
c
t
2
=
D
e
n
y, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal deduction process as shown in Formula (25) as follows: (25)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
D
e
n
y
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “First-Applicable” policy/rule combining algorithm and R
1 is the first applicable rule, R
2 is the redundancy rule.
② WhenE
f
f
e
c
t
1
=
P
e
r
m
i
t and E
f
f
e
c
t
2
=
P
e
r
m
i
t, then E
f
f
e
c
t
1
=
E
f
f
e
c
t
2. We have the formal derivation process as shown in Formula (26) as follows:(26)
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
E
f
f
e
c
t
1
=
E
f
f
e
c
t
2
=
P
e
r
m
i
t
⇓
R
e
d
u
n
d
a
n
c
y
=
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
=
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.
According to the known condition and Definition8, we deduct that rules R
1 and R
2 have thecommon resource redundancy in the overlapping condition c
o
n
1
⊙
c
o
n
2. What is more, since we use the “First-Applicable” policy/rule combining algorithm and R
1 is the first applicable rule, R
2 is the redundancy rule.
③E
f
f
e
c
t
1
≠
E
f
f
e
c
t
2 (i.e., E
f
f
e
c
t
1
=
D
e
n
y and E
f
f
e
c
t
2
=
P
e
r
m
i
t, or E
f
f
e
c
t
1
=
P
e
r
m
i
t and E
f
f
e
c
t
2
=
D
e
n
y) and R
1 is the first applicable rule. Because conditions c
o
n
1 and c
o
n
2 have an overlapping relationship (c
o
n
1
⊙
c
o
n
2
≠
⌀), according to the definition of “First-Applicable” policy/rule combining algorithm, under the condition that there appear no faults, we finally should use the effect E
f
f
e
c
t
1 of R
1 as the authorization result. However, the rule R
2 does not have any effect on the process of evaluation; the function of the rule cannot be realized. Therefore, according to Definition 7, we conclude that R
2 is the redundancy rule in the “First-Applicable” policy/rule combining algorithm.According to Theorem14, we can conclude the form derivation of detecting theredundancy related to the “First-Applicable” combining algorithm, as shown in Formula (27), where(i)
R
1 is the first applicable rule;
(ii)
R
e
d
u
n
d
a
n
c
y
F
A
(
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that S
t
a
t
e
1 satisfying the rule R
1 and S
t
a
t
e
2 satisfying the rule R
2 have theredundancy related to the “First-Applicable” combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2;
(iii)
R
e
d
u
n
d
a
n
c
y
F
A
(
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
) indicates that the rule R
1 corresponding to the S
t
a
t
e
1 and the rule R
2 corresponding to the S
t
a
t
e
2 have theredundancy related to the “First-Applicable” combining algorithm in the overlapping condition c
o
n
1
⊙
c
o
n
2:(27)
C
o
m
b
i
n
i
n
g
A
l
g
=
F
i
r
s
t
-
O
v
e
r
r
i
d
e
s
S
t
a
t
e
1
⊳
s
u
b
r
e
s
1
,
r
e
s
1
,
a
c
t
,
c
o
n
1
,
E
f
f
e
c
t
1
S
t
a
t
e
2
⊳
s
u
b
r
e
s
2
,
r
e
s
2
,
a
c
t
,
c
o
n
2
,
E
f
f
e
c
t
2
s
u
b
r
e
s
1
=
s
u
b
r
e
s
2
r
e
s
1
=
r
e
s
2
c
o
n
1
∩
c
o
n
2
≠
⌀
⇓
R
e
d
u
n
d
a
n
c
y
F
A
S
t
a
t
e
1
,
S
t
a
t
e
2
,
c
o
n
1
⊙
c
o
n
2
=
R
e
d
u
n
d
a
n
c
y
F
A
R
1
,
R
2
,
c
o
n
1
⊙
c
o
n
2
.When detecting theredundancy related to the “First-Applicable”combining algorithm by Theorem 14 between the two rules R
1 and R
2 (as Formula (22) shows) in a policy or between policies, without losing the generality, we suppose that R
1 is the first applicable rule; the method for eliminating the redundancy is to reserve the rule R
1 firstly. If c
o
n
1
⊙
c
o
n
2
=
c
o
n
2, we will delete the rule R
2 directly. If c
o
n
1
⊙
c
o
n
2
≠
c
o
n
2, we will update the condition attribute of the rule R
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2, that is, update the rule R
2 to a new rule as shown in Formula (28) as follows: (28)
R
2
′
=
s
u
b
2
,
r
e
s
2
,
a
c
t
2
,
c
o
n
2
-
c
o
n
1
⊙
c
o
n
2
,
E
f
f
e
c
t
2
.


## 7. Detection and Elimination Algorithms for Redundancy Related to Combining Algorithms

By the relevant definitions introduced in the paper andRBW, as well as detection and elimination methods for theredundancy related to combining algorithms, in this section we present the detection and elimination algorithms for theredundancy related to combining algorithms, as shown in Algorithm 1.Algorithm 1:Detection and elimination algorithm for redundancy related to combining algorithms. Redundancy_DetectionAndElimination(PolicySet, CA).
Input: (1) PolicySet
:
P
o
l
i
c
y
1
,
P
o
l
i
c
y
2
,
…
,
P
o
l
i
c
y
n, where P
o
l
i
c
y
i is a policy
(2) policy/rule combination algorithm CA
Output: a policy set where the redundancy related to combining algorithms have been eliminated
(1) ResBrickWallInitialization(PolicySet)
(2) AddRuleToResBrickWall(P, ResBrickWall, CA)
(3) BackTrackingDetectRedundancy(ResBrickWall, PresentResBrickId, CA)
(4) DetectRedundancyBetweenPolicies(R
e
s
B
r
i
c
k
W
a
l
l
1, R
e
s
B
r
i
c
k
W
a
l
l
2, CA)In Algorithm1, rows (1)~(3) complete the detection and elimination of theredundancy related to combining algorithms in a policy, and row (4) completes the detection and elimination of theredundancy related to combining algorithms between policies. Algorithm 1 calls four subalgorithms in turn to finish the work. Here, row (1) is the initialization algorithm for theRBW, responsible for initializing theRBW. Row (2) is the algorithm for adding rules to theRBW, responsible for adding every rule to theRBW. Row (3) is the detection and elimination backtracking algorithm, used for detecting and eliminatingredundancy related to combining algorithms by backtracking methods in the constructedRBW.Next, we will introduce algorithms used in each step of Algorithm1. We will give the time complexity of Algorithm 1 after discussing the four subalgorithms.


### 7.1. Initialization Algorithm for the Resource Brick Wall

Before detecting and eliminatingredundancy related to combining algorithms, we first need to iterate through each rule of each policy of all the policy sets and then get the resource directory structure of each rule. Finally, we initialize theRBW by the resource directory structure. The initialization algorithm for theResource Brick Wall is as shown in Algorithm 2.Algorithm 2:Initialization algorithm for resource brick wall. ResBrickWallInitialization(PolicySet).
Input: PolicySet
:
P
o
l
i
c
y
1
,
P
o
l
i
c
y
2
,
…
,
P
o
l
i
c
y
n, where P
o
l
i
c
y
i is a policy
Output: RBW ResBrickWall
(1)  foreach P
o
l
i
c
y
i
∈
P
o
l
i
c
y
S
e
t
(2)    foreach r
∈
P
o
l
i
c
y
i
(3)       ResPath = GetResPath(r)
(4)       AddResPathToDirectory(ResPath, ResDirectory)
(5)  ResBrickWall = ConvertResDirectoryToResBrickWall(ResDirectory)The functions contained in Algorithm2 are as follows:①GetResPath( ): the parameter of the function is the rule r, whose function is to parse the resource attribute information in the rule r, eventually return the resource path related to the rule r, and give the return value toResPath variables.②AddResPathToResDirectory( ): the parameter of the function is the resource pathResPath and resource directoryResDirectory, whose function is to store the resource pathResPath in the proper place of the resource directoryResDirectory.③CovertResDirectoryToResBrickWall( ): the parameter of the function is the resource directoryResDirectory, whose function is to construct the correspondingRBW through the analysis of the resource directoryResDirectory and return the constructedRBW to theResBrickWall variable.Supposing that the policy setP
o
l
i
c
y
S
e
t has m policies with each policy P
o
l
i
c
y
i having n rules, then the time complexity of Algorithm 2 is O
(
m
∗
n
).


### 7.2. Detection Algorithm for Redundancy Related to Combining Algorithms

The detection algorithm for theredundancy related to combining algorithms is as shown in Algorithm 3. Algorithm 3 contains three situations as follows:(1)
In the condition of the “Deny-Overrides” policy/rule combining algorithm, for any two rules r
1 and r
2 in a policy or between policies, if r
1 and r
2 have the same subject attribute and action attribute, there is an overlapping relationship between the condition attributes of r
1 and r
2, r
1 and r
2 have the same resource attribute, the effect of either of the two rules isDeny, or the resource attributes of r
1 and r
2 have a dependent relationship and the effect of r
1 isDeny, then r
1 and r
2 have theredundancy related to the “Deny-Overrides”combining algorithm.
(2)
In the condition of the “Permit-Overrides” policy/rule combining algorithm, for any two rules r
1 and r
2 in a policy or between policies, if r
1 and r
2 have the same subject attribute and action attribute, there is an overlapping relationship between the condition attributes of r
1 and r
2, r
1 and r
2 have the same resource attribute, and the effect of either of the two rules isPermit, then r
1 and r
2 have theredundancy related to the“Permit-Overrides”combining algorithm.
(3)
In the condition of the “First-Applicable” policy/rule combining algorithm, for any two rules r
1 and r
2 in a policy or between policies, if r
1 and r
2 have the same subject attribute and action attribute, there is an overlapping relationship between the condition attributes of r
1 and r
2, r
1 and r
2 have the same resource attribute, and the sequence of application is certain, then r
1 and r
2 have theredundancy related to the “First-Applicable” combining algorithm.Algorithm 3:Detection algorithm for redundancy related to combining algorithms. CA_DetectRedundancy(r
1, r
2, CA).
Input:  (1) two rules r
1 and r
2
(2) policy/rule combination algorithm CA
Output:   (1) if between rules r
1 and r
2 exists the redundancy related to combining algorithms, output rules r
1 and r
2 where the
redundancy related to combining algorithms has been eliminated
(2) if between rules r
1 and r
2 exists the redundancy related to combining algorithms, output SCEL
(1)   ifr
1
.
s
u
b = r
2
.
s
u
b  &  r
1
.
a
c
t = r
2
.
a
c
t  &  r
1
.
c
o
n
∩
r
2
.
c
o
n
≠
⌀
(2)      & (r
1
.
r
e
s
=
r
2
.
r
e
s
∣
r
1
.
r
e
s
↦
r
2
.
r
e
s)  then
(3)      /∗detection and elimination of the redundancy related to the“Deny-Overrides”combining algorithm
∗/
(4)      ifCA = Deny_Overrides  then
(5)      ifr
1
.
r
e
s = r
2
.
r
e
s  then
(6)        ifr
1
.
E
f
f
e
c
t = Deny  then
(7)EliminateRedundancy(r
1, r
2)
(8)        else ifr
2
.
E
f
f
e
c
t = Deny  then
(9)EliminateRedundancy(r
2, r
1)
(10)     else ifr
1
.
r
e
s
↦
r
2
.
r
e
s  then
(11)       ifr
1
.
E
f
f
e
c
t = Deny  then
(12)EliminateRedundancy(r
1, r
2)
(13)     /∗detection and elimination of the redundancy related to the“Permit-Overrides”combining algorithm
∗/
(14)     ifCA = Permit_Overrides & !(r
1
.
r
e
s
↦
r
2
.
r
e
s)  then
(15)      ifr
1
.
E
f
f
e
c
t = Permit  then
(16)EliminateRedundancy(r
1, r
2)
(17)      else ifr
2
.
E
f
f
e
c
t = Permit  then
(18)EliminateRedundancy(r
2, r
1)
(19)     /∗detection and elimination of the redundancy related to the  “First-Applicable”  combining algorithm
∗/
(20)     ifCA = First_Overrides & !(r
1
.
r
e
s
↦
r
2
.
r
e
s)  then
(21)      ifr
1
.
N
o
<
r
2
.
N
o  then
(22)EliminateRedundancy(r
1, r
2)
(23)      else ifr
2
.
N
o
<
r
1
.
N
o  then
(24)EliminateRedundancy(r
2, r
1)


### 7.3. Elimination Algorithm for Redundancy Related to Combining Algorithms

The elimination algorithm for theredundancy related to combining algorithms is as shown in Algorithm 4. Algorithm 4 adds the corresponding attribute information about rules r
1 and r
2 to the S
C
E
L, and reserve the rule r
1. If c
o
n
1
∩
c
o
n
2
=
c
o
n
2, we will delete the rule r
2 directly. If c
o
n
1
∩
c
o
n
2
≠
c
o
n
2, then we update the condition attribute of r
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
∩
c
o
n
2, so as to achieve the purpose of eliminating redundancies. This algorithm will update the S
C
E
L, which will make administrators instantly track and search for the attribute information about the corresponding rules in the process of detecting and eliminating redundancies conveniently. The time complexity of Algorithm 4 is O
(
1
).Algorithm 4:Elimination algorithm for redundancy related to combining algorithms. EliminateRedundancy(r
1, r
2).
Input:  two rules r
1 and r
2 having the redundancy related
to combining algorithms
Output:   (1) rules r
1 and r
2 where the redundancy related
to combining algorithms has been eliminated
(2) SCEL
(1)r
0
.
c
o
n
←
r
1
.
c
o
n
⊙
r
2
.
c
o
n
(2)AddRuleToSCEL(r
1, r
2)
(3)    ifr
2
.
c
o
n
=
r
0
.
c
o
n  then
(4)      deleter
2
(5)    else
(6)r
2
′
.
c
o
n
←
r
2
.
c
o
n
-
r
0
.
c
o
n


### 7.4. Algorithm for Adding Rules to the Resource Brick Wall

The algorithm for adding rules to theResource Brick Wall is as shown in Algorithm 5. In Algorithm 5, rows (2)~(3) add the rules in the policyP one by one to theRBW. By calling the detection algorithm for theredundancy related to combining algorithms, row (4) accomplishes the detection and elimination of theredundancy related to combining algorithms between the new added rules and rules already in theRBW. The time complexity under the worst condition of Algorithm 5 is O
(
n
).Algorithm 5:Algorithm for adding rules to resource brick wall. AddRuleToResBrickWall(P, ResBrickWall, CA).
Input:  (1) policy P
:
r
1
,
r
2
,
…
,
r
n, where r
i is a rule
(2) initialized RBW ResBrickWall
(3) policy/rule combination algorithm CA
Output: RBW ResBrickWall that is added rules
(1)  foreachr
∈
P do
(2)R
e
s
B
r
i
c
k
I
d
←
R
e
s
B
r
i
c
k
W
a
l
l
.
F
i
n
d(r)
(3)ResBrickWall[ResBrickId].List.Append(r)
(4)CA_DetectRedundancy(r
1, r
2, CA)


### 7.5. Algorithm for Backtracking Detection and Elimination of Redundancies

The algorithm for backtracking detection and elimination of redundancies is as shown in Algorithm6. In Algorithm 6, rows (1)~(2) accomplish backtracking resource bricks from the lower layer to the upper layer through the postorder traversal. By calling the detection algorithm for theredundancy related to combining algorithms, rows (3)~(6) accomplish the detection and elimination of theredundancy related to combining algorithms between rule r
1 of the upper layer resource bricks and rule r
2 of the lower layer resource bricks. The time complexity under the worst condition of Algorithm 6 is O
(
n
2
).Algorithm 6:Algorithm for backtracking detection and elimination of redundancies. BackTrackingDetectRedundancy(ResBrickWall, PresentResBrickId, CA).
Input:  (1) RBW ResBrickWall
(2) current resource bricks PresentResBrickId
(3) policy/rule combination algorithm CA
Output: RBW ResBrickWall where redundancies related to combining algorithms have been eliminated in a policy
(1)  foreach L
o
w
e
r
R
e
s
B
r
i
c
k
I
d
∈
P
r
e
s
e
n
t
R
e
s
B
r
i
c
k
I
d
(2)    BackTrackingDetectRedundancy(ResBrickWall, LowerResBrickId, CA)
(3)  UpperResBrickId = ResBrickWall.getUpperResBrickId(PresentResBrickId)
(4)  foreach r
1
∈
R
e
s
B
r
i
c
k
W
a
l
l[UpperResBrickId].List
(5)    foreach r
2
∈
R
e
s
B
r
i
c
k
W
a
l
l[PresentResBrickId].List
(6)      CA_DetectRedundancy(r
1, r
2, CA)


### 7.6. Detection and Elimination Algorithm for Redundancy Related to Combining Algorithms between Policies

The detection and elimination algorithm for theredundancy related to combining algorithms between policies is as shown in Algorithm 7. Firstly, we add each rule in R
e
s
B
r
i
c
k
W
a
l
l
2 to the resource brick structure of R
e
s
B
r
i
c
k
W
a
l
l
1, that is, combine the two inputRBWs to oneRBW. Then we detect and eliminate theredundancy related to combining algorithms in the combinedRBW. Finally, by the algorithm for backtracking detection and elimination of redundancies, we detect and eliminate theredundancy related to combining algorithms.Algorithm 7:Detection and elimination algorithm for redundancy related to combining algorithms between policies. DetectRedundancyBetweenPolicies(R
e
s
B
r
i
c
k
W
a
l
l
1, R
e
s
B
r
i
c
k
W
a
l
l
2, CA).
Input:  (1) two RBWs, R
e
s
B
r
i
c
k
W
a
l
l
1 and R
e
s
B
r
i
c
k
W
a
l
l
2
(2) policy/rule combination algorithm CA
Output: combined RBW
R
e
s
B
r
i
c
k
W
a
l
l
1
(1)  for each R
e
s
B
r
i
c
k
I
d
∈
R
e
s
B
r
i
c
k
W
a
l
l
1.IDList
(2)    for each r
2
∈
R
e
s
B
r
i
c
k
W
a
l
l
2[ResBrickId].List
(3)      R
e
s
B
r
i
c
k
W
a
l
l
1[ResBrickId].List.Append(r
2)
(4)      for each r
1
∈
R
e
s
B
r
i
c
k
W
a
l
l
1[ResBrickId].List
(5)        CA_DetectRedundancy(r
1, r
2, CA)
(6)  BackTrackingDetectRedundancy(R
e
s
B
r
i
c
k
W
a
l
l
1, root, CA)In Algorithm7, the time complexity of rows (1)~(2) is O
(
n
), the time complexity of rows (3)~(5) under the worst condition is O
(
n
), and the time complexity of row (6) under the worst condition is O
(
n
2
). Thus, the time complexity of Algorithm 7 under the worst condition is O
(
n
∗
n
+
n
2
), that is, O
(
n
2
).To sum up, the time complexity of Algorithm1 is O
(
m
∗
n
+
n
2
+
n
2
+
n
2
), that is, O
m
∗
n
+
n
2
.The problem of detecting and eliminating theredundancy related to combining algorithms between several policies and between policy sets all can be turned into the problem of detecting and eliminating theredundancy related to combining algorithms between two policies, and in this paper we do not go into details about it.


## 7.1. Initialization Algorithm for the Resource Brick Wall

Before detecting and eliminatingredundancy related to combining algorithms, we first need to iterate through each rule of each policy of all the policy sets and then get the resource directory structure of each rule. Finally, we initialize theRBW by the resource directory structure. The initialization algorithm for theResource Brick Wall is as shown in Algorithm 2.Algorithm 2:Initialization algorithm for resource brick wall. ResBrickWallInitialization(PolicySet).
Input: PolicySet
:
P
o
l
i
c
y
1
,
P
o
l
i
c
y
2
,
…
,
P
o
l
i
c
y
n, where P
o
l
i
c
y
i is a policy
Output: RBW ResBrickWall
(1)  foreach P
o
l
i
c
y
i
∈
P
o
l
i
c
y
S
e
t
(2)    foreach r
∈
P
o
l
i
c
y
i
(3)       ResPath = GetResPath(r)
(4)       AddResPathToDirectory(ResPath, ResDirectory)
(5)  ResBrickWall = ConvertResDirectoryToResBrickWall(ResDirectory)The functions contained in Algorithm2 are as follows:①GetResPath( ): the parameter of the function is the rule r, whose function is to parse the resource attribute information in the rule r, eventually return the resource path related to the rule r, and give the return value toResPath variables.②AddResPathToResDirectory( ): the parameter of the function is the resource pathResPath and resource directoryResDirectory, whose function is to store the resource pathResPath in the proper place of the resource directoryResDirectory.③CovertResDirectoryToResBrickWall( ): the parameter of the function is the resource directoryResDirectory, whose function is to construct the correspondingRBW through the analysis of the resource directoryResDirectory and return the constructedRBW to theResBrickWall variable.Supposing that the policy setP
o
l
i
c
y
S
e
t has m policies with each policy P
o
l
i
c
y
i having n rules, then the time complexity of Algorithm 2 is O
(
m
∗
n
).


## 7.2. Detection Algorithm for Redundancy Related to Combining Algorithms

The detection algorithm for theredundancy related to combining algorithms is as shown in Algorithm 3. Algorithm 3 contains three situations as follows:(1)
In the condition of the “Deny-Overrides” policy/rule combining algorithm, for any two rules r
1 and r
2 in a policy or between policies, if r
1 and r
2 have the same subject attribute and action attribute, there is an overlapping relationship between the condition attributes of r
1 and r
2, r
1 and r
2 have the same resource attribute, the effect of either of the two rules isDeny, or the resource attributes of r
1 and r
2 have a dependent relationship and the effect of r
1 isDeny, then r
1 and r
2 have theredundancy related to the “Deny-Overrides”combining algorithm.
(2)
In the condition of the “Permit-Overrides” policy/rule combining algorithm, for any two rules r
1 and r
2 in a policy or between policies, if r
1 and r
2 have the same subject attribute and action attribute, there is an overlapping relationship between the condition attributes of r
1 and r
2, r
1 and r
2 have the same resource attribute, and the effect of either of the two rules isPermit, then r
1 and r
2 have theredundancy related to the“Permit-Overrides”combining algorithm.
(3)
In the condition of the “First-Applicable” policy/rule combining algorithm, for any two rules r
1 and r
2 in a policy or between policies, if r
1 and r
2 have the same subject attribute and action attribute, there is an overlapping relationship between the condition attributes of r
1 and r
2, r
1 and r
2 have the same resource attribute, and the sequence of application is certain, then r
1 and r
2 have theredundancy related to the “First-Applicable” combining algorithm.Algorithm 3:Detection algorithm for redundancy related to combining algorithms. CA_DetectRedundancy(r
1, r
2, CA).
Input:  (1) two rules r
1 and r
2
(2) policy/rule combination algorithm CA
Output:   (1) if between rules r
1 and r
2 exists the redundancy related to combining algorithms, output rules r
1 and r
2 where the
redundancy related to combining algorithms has been eliminated
(2) if between rules r
1 and r
2 exists the redundancy related to combining algorithms, output SCEL
(1)   ifr
1
.
s
u
b = r
2
.
s
u
b  &  r
1
.
a
c
t = r
2
.
a
c
t  &  r
1
.
c
o
n
∩
r
2
.
c
o
n
≠
⌀
(2)      & (r
1
.
r
e
s
=
r
2
.
r
e
s
∣
r
1
.
r
e
s
↦
r
2
.
r
e
s)  then
(3)      /∗detection and elimination of the redundancy related to the“Deny-Overrides”combining algorithm
∗/
(4)      ifCA = Deny_Overrides  then
(5)      ifr
1
.
r
e
s = r
2
.
r
e
s  then
(6)        ifr
1
.
E
f
f
e
c
t = Deny  then
(7)EliminateRedundancy(r
1, r
2)
(8)        else ifr
2
.
E
f
f
e
c
t = Deny  then
(9)EliminateRedundancy(r
2, r
1)
(10)     else ifr
1
.
r
e
s
↦
r
2
.
r
e
s  then
(11)       ifr
1
.
E
f
f
e
c
t = Deny  then
(12)EliminateRedundancy(r
1, r
2)
(13)     /∗detection and elimination of the redundancy related to the“Permit-Overrides”combining algorithm
∗/
(14)     ifCA = Permit_Overrides & !(r
1
.
r
e
s
↦
r
2
.
r
e
s)  then
(15)      ifr
1
.
E
f
f
e
c
t = Permit  then
(16)EliminateRedundancy(r
1, r
2)
(17)      else ifr
2
.
E
f
f
e
c
t = Permit  then
(18)EliminateRedundancy(r
2, r
1)
(19)     /∗detection and elimination of the redundancy related to the  “First-Applicable”  combining algorithm
∗/
(20)     ifCA = First_Overrides & !(r
1
.
r
e
s
↦
r
2
.
r
e
s)  then
(21)      ifr
1
.
N
o
<
r
2
.
N
o  then
(22)EliminateRedundancy(r
1, r
2)
(23)      else ifr
2
.
N
o
<
r
1
.
N
o  then
(24)EliminateRedundancy(r
2, r
1)


## 7.3. Elimination Algorithm for Redundancy Related to Combining Algorithms

The elimination algorithm for theredundancy related to combining algorithms is as shown in Algorithm 4. Algorithm 4 adds the corresponding attribute information about rules r
1 and r
2 to the S
C
E
L, and reserve the rule r
1. If c
o
n
1
∩
c
o
n
2
=
c
o
n
2, we will delete the rule r
2 directly. If c
o
n
1
∩
c
o
n
2
≠
c
o
n
2, then we update the condition attribute of r
2 to c
o
n
2
′
=
c
o
n
2
-
c
o
n
1
∩
c
o
n
2, so as to achieve the purpose of eliminating redundancies. This algorithm will update the S
C
E
L, which will make administrators instantly track and search for the attribute information about the corresponding rules in the process of detecting and eliminating redundancies conveniently. The time complexity of Algorithm 4 is O
(
1
).Algorithm 4:Elimination algorithm for redundancy related to combining algorithms. EliminateRedundancy(r
1, r
2).
Input:  two rules r
1 and r
2 having the redundancy related
to combining algorithms
Output:   (1) rules r
1 and r
2 where the redundancy related
to combining algorithms has been eliminated
(2) SCEL
(1)r
0
.
c
o
n
←
r
1
.
c
o
n
⊙
r
2
.
c
o
n
(2)AddRuleToSCEL(r
1, r
2)
(3)    ifr
2
.
c
o
n
=
r
0
.
c
o
n  then
(4)      deleter
2
(5)    else
(6)r
2
′
.
c
o
n
←
r
2
.
c
o
n
-
r
0
.
c
o
n


## 7.4. Algorithm for Adding Rules to the Resource Brick Wall

The algorithm for adding rules to theResource Brick Wall is as shown in Algorithm 5. In Algorithm 5, rows (2)~(3) add the rules in the policyP one by one to theRBW. By calling the detection algorithm for theredundancy related to combining algorithms, row (4) accomplishes the detection and elimination of theredundancy related to combining algorithms between the new added rules and rules already in theRBW. The time complexity under the worst condition of Algorithm 5 is O
(
n
).Algorithm 5:Algorithm for adding rules to resource brick wall. AddRuleToResBrickWall(P, ResBrickWall, CA).
Input:  (1) policy P
:
r
1
,
r
2
,
…
,
r
n, where r
i is a rule
(2) initialized RBW ResBrickWall
(3) policy/rule combination algorithm CA
Output: RBW ResBrickWall that is added rules
(1)  foreachr
∈
P do
(2)R
e
s
B
r
i
c
k
I
d
←
R
e
s
B
r
i
c
k
W
a
l
l
.
F
i
n
d(r)
(3)ResBrickWall[ResBrickId].List.Append(r)
(4)CA_DetectRedundancy(r
1, r
2, CA)


## 7.5. Algorithm for Backtracking Detection and Elimination of Redundancies

The algorithm for backtracking detection and elimination of redundancies is as shown in Algorithm6. In Algorithm 6, rows (1)~(2) accomplish backtracking resource bricks from the lower layer to the upper layer through the postorder traversal. By calling the detection algorithm for theredundancy related to combining algorithms, rows (3)~(6) accomplish the detection and elimination of theredundancy related to combining algorithms between rule r
1 of the upper layer resource bricks and rule r
2 of the lower layer resource bricks. The time complexity under the worst condition of Algorithm 6 is O
(
n
2
).Algorithm 6:Algorithm for backtracking detection and elimination of redundancies. BackTrackingDetectRedundancy(ResBrickWall, PresentResBrickId, CA).
Input:  (1) RBW ResBrickWall
(2) current resource bricks PresentResBrickId
(3) policy/rule combination algorithm CA
Output: RBW ResBrickWall where redundancies related to combining algorithms have been eliminated in a policy
(1)  foreach L
o
w
e
r
R
e
s
B
r
i
c
k
I
d
∈
P
r
e
s
e
n
t
R
e
s
B
r
i
c
k
I
d
(2)    BackTrackingDetectRedundancy(ResBrickWall, LowerResBrickId, CA)
(3)  UpperResBrickId = ResBrickWall.getUpperResBrickId(PresentResBrickId)
(4)  foreach r
1
∈
R
e
s
B
r
i
c
k
W
a
l
l[UpperResBrickId].List
(5)    foreach r
2
∈
R
e
s
B
r
i
c
k
W
a
l
l[PresentResBrickId].List
(6)      CA_DetectRedundancy(r
1, r
2, CA)


## 7.6. Detection and Elimination Algorithm for Redundancy Related to Combining Algorithms between Policies

The detection and elimination algorithm for theredundancy related to combining algorithms between policies is as shown in Algorithm 7. Firstly, we add each rule in R
e
s
B
r
i
c
k
W
a
l
l
2 to the resource brick structure of R
e
s
B
r
i
c
k
W
a
l
l
1, that is, combine the two inputRBWs to oneRBW. Then we detect and eliminate theredundancy related to combining algorithms in the combinedRBW. Finally, by the algorithm for backtracking detection and elimination of redundancies, we detect and eliminate theredundancy related to combining algorithms.Algorithm 7:Detection and elimination algorithm for redundancy related to combining algorithms between policies. DetectRedundancyBetweenPolicies(R
e
s
B
r
i
c
k
W
a
l
l
1, R
e
s
B
r
i
c
k
W
a
l
l
2, CA).
Input:  (1) two RBWs, R
e
s
B
r
i
c
k
W
a
l
l
1 and R
e
s
B
r
i
c
k
W
a
l
l
2
(2) policy/rule combination algorithm CA
Output: combined RBW
R
e
s
B
r
i
c
k
W
a
l
l
1
(1)  for each R
e
s
B
r
i
c
k
I
d
∈
R
e
s
B
r
i
c
k
W
a
l
l
1.IDList
(2)    for each r
2
∈
R
e
s
B
r
i
c
k
W
a
l
l
2[ResBrickId].List
(3)      R
e
s
B
r
i
c
k
W
a
l
l
1[ResBrickId].List.Append(r
2)
(4)      for each r
1
∈
R
e
s
B
r
i
c
k
W
a
l
l
1[ResBrickId].List
(5)        CA_DetectRedundancy(r
1, r
2, CA)
(6)  BackTrackingDetectRedundancy(R
e
s
B
r
i
c
k
W
a
l
l
1, root, CA)In Algorithm7, the time complexity of rows (1)~(2) is O
(
n
), the time complexity of rows (3)~(5) under the worst condition is O
(
n
), and the time complexity of row (6) under the worst condition is O
(
n
2
). Thus, the time complexity of Algorithm 7 under the worst condition is O
(
n
∗
n
+
n
2
), that is, O
(
n
2
).To sum up, the time complexity of Algorithm1 is O
(
m
∗
n
+
n
2
+
n
2
+
n
2
), that is, O
m
∗
n
+
n
2
.The problem of detecting and eliminating theredundancy related to combining algorithms between several policies and between policy sets all can be turned into the problem of detecting and eliminating theredundancy related to combining algorithms between two policies, and in this paper we do not go into details about it.


## 8. Experimental Results and Analysis

In order to assess the evaluation performance improvement of the PDP after detecting and eliminating theredundancy related to combining algorithms, the test policies are introduced first. We do the following experiments:(1)
A comparison of the evaluation performance of theXDPRE before and after eliminating theredundancy related to combining algorithms is made.
(2)
A comparison in evaluation performance between Sun PDP and theXDPRE after eliminating theredundancy related to combining algorithmsis made.


### 8.1. Test Policies

In order to simulate practical application scenarios, we select the following three XACML access control policies from practical systems [28–30]:(i)
Library Management System (LMS). TheLMS provides access control policies by which a public library can use the web to manage books.
(ii)
Virtual Meeting System (VMS). TheVMS provides access control policies by which the web conference services can be managed.
(iii)
Auction Sale Management System (ASMS). TheASMS provides access control policies by which items can be bought or sold online.The policy of theLMS contains 720 rules, that of theVMS 945 rules, and that of theASMS 1760 rules. In the light of actual requirement, the policies of theLMS,VMS, andASMS need to be expanded to contain more rules. What we do is that according to the Cartesian product of different subjects, actions, resources, and conditions in all rules of a policy, we construct new rules and add them to the original policy. The number of rules in the policies of theLMS,VMS, andASMS is expanded separately to 3000, 6000, and 9000.At present, Sun PDP is a widely used policy decision point [31] and can process redundancies in a policy selectively according to the internal rule matching mechanism [32]. Sun PDP is adopted to evaluate requests as a decision engine in our followingredundancy related to combining algorithms detecting and eliminating experiments. We choose Sun PDP in our experiments for two main reasons. First, Sun PDP is the first and the most widely deployed implementation of XACML evaluation engines. It has become the industrial standard. Second, Sun PDP is open source. To eliminate the performance factor of implementation languages, we implementedXDPRE in Java because Sun PDP is written in Java. The results of Sun PDP are compared with those of theXDPRE to verify that theXDPRE can effectively improve the evaluation performance of the policy decision point.


### 8.2. Generation of Test Requests

Dan et al. [33] put forward that policies are analyzed byChange-Impact in order to automatically generate access requests that conform toChange-Impact. The purpose is to improve the coverage of the test. The main idea is that conflicting policies or rules can be obtained by conflict detection tools according to the fact that different policies or different rules in the same policy could make inconsistent results of evaluation for the same request, and that correlative access requests can be constructed for testing according to the conflicting policies or rules.She et al. [34] proposed that access requests can be automatically generated to test the correctness of the PDP as well as the configured policies. They pointed out that theContext Shema which is defined by the XML Schema of the XACML describes all the structures of the access requests that might be accepted by the PDP, or all the valid input requests. This paper indicates that their developedX-CREATE can generate possible structures of access requests according to the Context Shema of the XACML. The policy analyzer obtains possible input values of every attribute from a policy. The policy manager adopts the method for random allocation to distribute the obtained input values into structures of access requests. Another test scheme isSimple Combinatorial, which can generate access requests according to all the possible combinations of attribute values of subject, action, and resource in the XACML policies. This paper also analyzes the advantages of these two schemes in debugging.According to the actual requirement of the performance test, the method for combiningChange-Imapct,Context Shema, andSimple Combinatorial is adopted to simulate the practical access requests.


### 8.3. Performance Tests and Comparisons

TheXDPRE itself can be viewed as a policy decision point, so the evaluation performance improvement of theXDPRE can verify the evaluation performance improvement of the PDP.


#### 8.3.1. Comparison of Evaluation Performance of the XDPRE before and after Eliminating the Redundancy Related to Combining Algorithms

In order to assess the evaluation performance improvement of theXDPRE after eliminating theredundancy related to combining algorithms in policies, a comparison of evaluation time of theXDPRE before and after eliminating theredundancy related to combining algorithms is made. We generate 500,1000
,
…
,
6000 access requests randomly to measure the evaluation time of the PDP. For the policies of theLMS,VMS, andASMS, the variation of evaluation time of theXDPRE with the number of access requests is shown in Figure 4.Figure 4
Variation of evaluation time with access requests before and after eliminating redundancy related to combining algorithms.In Figure4, we observe the following:(i)
The evaluation time of theXDPRE increases when the number of access requests grows whether theredundancy related to combining algorithms in a policy is eliminated or not.
(ii)
The growth rate of the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms in a policy is less than that of theXDPRE without theredundancy related to combining algorithms elimination.
(iii)
For the policies of theLMS,VMS, andASMS, when the number of access requests reaches 6000, the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms in a policy is shortened by 9.09%, 11.78%, and 14.39%, respectively. Thus, theXDPRE can effectively enhance the PDP’s evaluation performance by eliminating theredundancy related to combining algorithms in a policy.


#### 8.3.2. Comparison in Evaluation Performance between Sun PDP and the XDPRE after Eliminating the Redundancy Related to Combining Algorithms

In order to further assess the evaluation performance improvement of theXDPRE, we compare the evaluation performance of Sun PDP with that of theXDPRE after eliminatingtheredundancy related to combining algorithms. We generate 500,1000
,
…
,
6000 access requests randomly to measure the evaluation time of PDPs. For the policies of theLMS,VMS, andASMS, the variations with the number of access requests of the evaluation time of Sun PDP and theXDPRE after eliminating theredundancy related to combining algorithms are shown in Figure 5.Figure 5
Comparison in evaluation performance between Sun PDP and XDPRE after eliminating redundancy related to combining algorithms.In Figure5, we observe the following:(i)
The evaluation time of Sun PDP and theXDPRE after eliminating theredundancy related to combining algorithmsincreases when the number of access requests grows.
(ii)
The growth rate of the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms is less than that of Sun PDP.
(iii)
For the policies of theLMS,VMS, andASMS, when the number of access requests reaches 6000, the evaluation performance of theXDPRE after eliminating theredundancy related to combining algorithms has been improved by 10.01%, 10.95%, and 12.04%, respectively, compared to that of Sun PDP. Therefore, the evaluation performance of theXDPRE after eliminating theredundancy related to combining algorithms has been improved by 11% on average as compared with that of Sun PDP. So theXDPRE can effectively improve the evaluation performance of PDPs.


## 8.1. Test Policies

In order to simulate practical application scenarios, we select the following three XACML access control policies from practical systems [28–30]:(i)
Library Management System (LMS). TheLMS provides access control policies by which a public library can use the web to manage books.
(ii)
Virtual Meeting System (VMS). TheVMS provides access control policies by which the web conference services can be managed.
(iii)
Auction Sale Management System (ASMS). TheASMS provides access control policies by which items can be bought or sold online.The policy of theLMS contains 720 rules, that of theVMS 945 rules, and that of theASMS 1760 rules. In the light of actual requirement, the policies of theLMS,VMS, andASMS need to be expanded to contain more rules. What we do is that according to the Cartesian product of different subjects, actions, resources, and conditions in all rules of a policy, we construct new rules and add them to the original policy. The number of rules in the policies of theLMS,VMS, andASMS is expanded separately to 3000, 6000, and 9000.At present, Sun PDP is a widely used policy decision point [31] and can process redundancies in a policy selectively according to the internal rule matching mechanism [32]. Sun PDP is adopted to evaluate requests as a decision engine in our followingredundancy related to combining algorithms detecting and eliminating experiments. We choose Sun PDP in our experiments for two main reasons. First, Sun PDP is the first and the most widely deployed implementation of XACML evaluation engines. It has become the industrial standard. Second, Sun PDP is open source. To eliminate the performance factor of implementation languages, we implementedXDPRE in Java because Sun PDP is written in Java. The results of Sun PDP are compared with those of theXDPRE to verify that theXDPRE can effectively improve the evaluation performance of the policy decision point.


## 8.2. Generation of Test Requests

Dan et al. [33] put forward that policies are analyzed byChange-Impact in order to automatically generate access requests that conform toChange-Impact. The purpose is to improve the coverage of the test. The main idea is that conflicting policies or rules can be obtained by conflict detection tools according to the fact that different policies or different rules in the same policy could make inconsistent results of evaluation for the same request, and that correlative access requests can be constructed for testing according to the conflicting policies or rules.She et al. [34] proposed that access requests can be automatically generated to test the correctness of the PDP as well as the configured policies. They pointed out that theContext Shema which is defined by the XML Schema of the XACML describes all the structures of the access requests that might be accepted by the PDP, or all the valid input requests. This paper indicates that their developedX-CREATE can generate possible structures of access requests according to the Context Shema of the XACML. The policy analyzer obtains possible input values of every attribute from a policy. The policy manager adopts the method for random allocation to distribute the obtained input values into structures of access requests. Another test scheme isSimple Combinatorial, which can generate access requests according to all the possible combinations of attribute values of subject, action, and resource in the XACML policies. This paper also analyzes the advantages of these two schemes in debugging.According to the actual requirement of the performance test, the method for combiningChange-Imapct,Context Shema, andSimple Combinatorial is adopted to simulate the practical access requests.


## 8.3. Performance Tests and Comparisons

TheXDPRE itself can be viewed as a policy decision point, so the evaluation performance improvement of theXDPRE can verify the evaluation performance improvement of the PDP.


### 8.3.1. Comparison of Evaluation Performance of the XDPRE before and after Eliminating the Redundancy Related to Combining Algorithms

In order to assess the evaluation performance improvement of theXDPRE after eliminating theredundancy related to combining algorithms in policies, a comparison of evaluation time of theXDPRE before and after eliminating theredundancy related to combining algorithms is made. We generate 500,1000
,
…
,
6000 access requests randomly to measure the evaluation time of the PDP. For the policies of theLMS,VMS, andASMS, the variation of evaluation time of theXDPRE with the number of access requests is shown in Figure 4.Figure 4
Variation of evaluation time with access requests before and after eliminating redundancy related to combining algorithms.In Figure4, we observe the following:(i)
The evaluation time of theXDPRE increases when the number of access requests grows whether theredundancy related to combining algorithms in a policy is eliminated or not.
(ii)
The growth rate of the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms in a policy is less than that of theXDPRE without theredundancy related to combining algorithms elimination.
(iii)
For the policies of theLMS,VMS, andASMS, when the number of access requests reaches 6000, the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms in a policy is shortened by 9.09%, 11.78%, and 14.39%, respectively. Thus, theXDPRE can effectively enhance the PDP’s evaluation performance by eliminating theredundancy related to combining algorithms in a policy.


### 8.3.2. Comparison in Evaluation Performance between Sun PDP and the XDPRE after Eliminating the Redundancy Related to Combining Algorithms

In order to further assess the evaluation performance improvement of theXDPRE, we compare the evaluation performance of Sun PDP with that of theXDPRE after eliminatingtheredundancy related to combining algorithms. We generate 500,1000
,
…
,
6000 access requests randomly to measure the evaluation time of PDPs. For the policies of theLMS,VMS, andASMS, the variations with the number of access requests of the evaluation time of Sun PDP and theXDPRE after eliminating theredundancy related to combining algorithms are shown in Figure 5.Figure 5
Comparison in evaluation performance between Sun PDP and XDPRE after eliminating redundancy related to combining algorithms.In Figure5, we observe the following:(i)
The evaluation time of Sun PDP and theXDPRE after eliminating theredundancy related to combining algorithmsincreases when the number of access requests grows.
(ii)
The growth rate of the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms is less than that of Sun PDP.
(iii)
For the policies of theLMS,VMS, andASMS, when the number of access requests reaches 6000, the evaluation performance of theXDPRE after eliminating theredundancy related to combining algorithms has been improved by 10.01%, 10.95%, and 12.04%, respectively, compared to that of Sun PDP. Therefore, the evaluation performance of theXDPRE after eliminating theredundancy related to combining algorithms has been improved by 11% on average as compared with that of Sun PDP. So theXDPRE can effectively improve the evaluation performance of PDPs.


## 8.3.1. Comparison of Evaluation Performance of the XDPRE before and after Eliminating the Redundancy Related to Combining Algorithms

In order to assess the evaluation performance improvement of theXDPRE after eliminating theredundancy related to combining algorithms in policies, a comparison of evaluation time of theXDPRE before and after eliminating theredundancy related to combining algorithms is made. We generate 500,1000
,
…
,
6000 access requests randomly to measure the evaluation time of the PDP. For the policies of theLMS,VMS, andASMS, the variation of evaluation time of theXDPRE with the number of access requests is shown in Figure 4.Figure 4
Variation of evaluation time with access requests before and after eliminating redundancy related to combining algorithms.In Figure4, we observe the following:(i)
The evaluation time of theXDPRE increases when the number of access requests grows whether theredundancy related to combining algorithms in a policy is eliminated or not.
(ii)
The growth rate of the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms in a policy is less than that of theXDPRE without theredundancy related to combining algorithms elimination.
(iii)
For the policies of theLMS,VMS, andASMS, when the number of access requests reaches 6000, the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms in a policy is shortened by 9.09%, 11.78%, and 14.39%, respectively. Thus, theXDPRE can effectively enhance the PDP’s evaluation performance by eliminating theredundancy related to combining algorithms in a policy.


## 8.3.2. Comparison in Evaluation Performance between Sun PDP and the XDPRE after Eliminating the Redundancy Related to Combining Algorithms

In order to further assess the evaluation performance improvement of theXDPRE, we compare the evaluation performance of Sun PDP with that of theXDPRE after eliminatingtheredundancy related to combining algorithms. We generate 500,1000
,
…
,
6000 access requests randomly to measure the evaluation time of PDPs. For the policies of theLMS,VMS, andASMS, the variations with the number of access requests of the evaluation time of Sun PDP and theXDPRE after eliminating theredundancy related to combining algorithms are shown in Figure 5.Figure 5
Comparison in evaluation performance between Sun PDP and XDPRE after eliminating redundancy related to combining algorithms.In Figure5, we observe the following:(i)
The evaluation time of Sun PDP and theXDPRE after eliminating theredundancy related to combining algorithmsincreases when the number of access requests grows.
(ii)
The growth rate of the evaluation time of theXDPRE after eliminating theredundancy related to combining algorithms is less than that of Sun PDP.
(iii)
For the policies of theLMS,VMS, andASMS, when the number of access requests reaches 6000, the evaluation performance of theXDPRE after eliminating theredundancy related to combining algorithms has been improved by 10.01%, 10.95%, and 12.04%, respectively, compared to that of Sun PDP. Therefore, the evaluation performance of theXDPRE after eliminating theredundancy related to combining algorithms has been improved by 11% on average as compared with that of Sun PDP. So theXDPRE can effectively improve the evaluation performance of PDPs.


## 9. Conclusions

Theredundancy related to combining algorithms detecting and eliminating engine termed theXDPRE is presented in this paper, which not only can detect and eliminate theredundancy related to combining algorithms within a policy, but also has the same ability as the PDP. This engine can evaluate access requests by loading the policies in which theredundancy related to combining algorithms has been eliminated and return the authorization result to the context processors and the PEP. AResource Brick Wall is constructed by theXDPRE on the basis of the resource attribute of a policy’s target attributes. By theResource Brick Wall and the policy/rule combining algorithms, three theorems for detectingredundancies related to combining algorithms are presented. TheResource Brick Wall can effectively avoid unnecessary comparisons of resources at different levels, so it could optimize the comparison of rules and reduce traversing frequency of each rule in the policy set when detecting redundancies. As a result, it greatly improves the efficiency of detecting and eliminating redundancies and the evaluation performance of the PDP. Finally, a detection and elimination algorithm for theredundancy related to combining algorithms is proposed.There still remain some shortcomings in this paper. We simplified the discussion of the condition attribute in the process of detecting and eliminating theredundancy related to combining algorithms. And we focused on condition constraints of the clock time, but factors in practical life such as year and region were not considered. This part of work needs to be further solved and improved in our future research.



---

*Source: 7608408-2016-06-29.xml*