OPEN ACCESS
For resources in an open environment, the access control rules (ACRs), which are described by extensible access control markup language (XACML), might have conflicts between each other. To improve the rule management, the root causes of rule conflicts must be identified. This paper firstly formally models the resource attributes by dynamic description logic (DDL), and then investigates inference problems like attribute consistency and rule satisfiability by setting up concept, instance and action knowledge bases. Next, DDLbased rule conflict detection algorithms were designed to identify possible rule conflicts. Finally, the feasibility and decidability of the proposed algorithms were verified through experiments on expanded Continue dataset. The research results provide new insights to the detection of conflicts between resource authorization rules (RARs).
dynamic description logic (DDL), extensible access control markup language (XACML), access control rule (ACR), rule conflict detection
In an open environment, resources are often scheduled and accessed through the collaboration and combination among multiple organizations and systems. The access control rules (ACRs) for descriptive attributes of interdomain resources need to be maintained and updated by decision makers from other domains. This crossdomain resource access control mode raises new requirements for ACR formulation and verification.
For one thing, the knowledge sharing and permission coverage might exist in the conceptual structure and correlations of resource attributes. For another, the intradomain resources could be combined and migrated at any time, and ACR authorization and revocation add difficulty to rule management, pushing up the possibility of conflicts between resource authorization rules (RARs).
Most access control systems provide mitigating methods for the abovementioned rule conflicts, namely, prioritizing “allow”, “deny”, or “use” permissions. Focusing only on the final judgement of the rules, these mitigation methods merely ensure the determinism of the evaluation for access control system. For resource visitors and rule makers, the process and causes of rule conflicts are not available, making it impossible to find the source of conflicts from the structure of resource attributes and RARs.
Considering the RAR conflicts in a distributed environment, this paper probes into the mitigating methods adopted in extensible access control markup language (XACML). The ACRs were formally expressed by dynamic description logic (DDL). The possible RAR conflicts were verified through model inference.
As a description standard for RARs, the XACML [1] was formulated by Organization of the Advancement of Structured Information Standard (OASIS) to promote the consistency of ACR descriptions on the network layer. With a finegrained description method for attribute authorization and an easily expandable form of rule description, the XACML offers a suitable tool to describe the access control and authorization of distributed resources.
In recent years, the XACML has been frequently adopted for logic description and reasoning of ACRs in distributed environments. Facing the heterogeneous Internet of things (IoT), Atlam et al. [2] depicted the ACRs of lightweight IoT devices with the XACML, and designed a distributed and flexible crossdomain resource access control method. Based on the grammar rules of the XACML, the designed method expands the application scope and enhances the fault tolerance and authorization validation of the original model. Focusing on cloud service application scenarios in health services, Ayache et al. [3] developed an XACMLbased cloud service for verifying ACRs, which realizes data sharing, task invocation and activity coordination across service domains. Kanwal et al. [4] tackled the security of data release and sharing of electronic medical records in a hybrid cloud environment, made finegrained XACML description of resource ACRs in that environment, and thereby improved the capabilities of the ACRs in privacy protection and access control. For safe access to IoT devices in distributed network, Charaf et al. [5] proposed an XACMLbased access control method for terminal devices, which is reliable, available and confidential.
Damiano et al. [6] applied blockchain technology to describe ACRs and establish a decentralized trust verification mechanism for crossdomain resources. Specifically, the security performance of resource attributes was subject to finegrained description, and the attributes and rules were linked to the blockchain in the form of smart contract. The proposed mechanism was validated in the Ethereum environment. Based on the blockchain technology, Ma et al. [7] created a distributed key management architecture for the hierarchical access control of the IoT. The architecture satisfies the demand for access control of crossdomain cloud services, supports decentralized and finegrained verification of attributes, and integrates privacy protection into the ACRs. Zyskind and Nathan [8] combined blockchain technology and offchain storage into a data management platform for privacy protection. In the platform, the access control process mainly focuses data reading, failing to form a complete access control system. Sukhodolskiy and Zapechnikov [9] put forward an access control method for data storage in a cloud environment. Wang et al. [10] realized data storage and sharing without the participation of providers, using Ethereum and an attributebased access control method. Furthermore, many other researchers have studied the access control strategy described by XACML about Policies formalization [11], Automatic Testing [12], Model testing [13], policy tracing [14], automated fault localization [15].
The above studies mainly explored the access control mechanism of crossdomain resources in different application environments, and developed some mitigation methods for rule conflicts based on the XACML. Most of these methods mitigate the impact of rule conflicts on the authorization process from the perspective of authorization results. However, the nature of the mitigation has not been analyzed from the angles of rule description and attribute structure, weakening the ability of reasoning and verification. The XACMLbased rule combination algorithms neglect the attributes and the underlying causes leading to rule conflicts, and overlook the influence of rule correlations and attribute hierarchy on the rule conflicts. To make up for the gaps, the rule conflicts should be detected and mitigated before judging the authorization, using the reasoning ability of dynamic description logic (DDL). In this way, the security management personnel in the domain can discover rule conflicts in time, find the reasons of conflicts, and simplify the relevant rules.
The attributes of cloud resources have an abundance of semantic ontology descriptions, making the authorization reasoning between resources a possibility. Here, the ontology language of resource attributes is mapped to the DDL language environment, and the resource authorization is formally verified by the DDL reasoning mechanism.
3.1 Attributebased access control model
The modelling of attribute access control mainly describes the knowledge of TBox, ABox, and ActBox. As shown in Figure 1, the attributebased finegrained access control model encompasses a concept submodel, an instance submodel, and an action submodel.
The TBox knowledge uses axioms to systematically describe the conceptual structure of ontology resources. The structured knowledge can depict the inheritance and inclusion semantics expressed by attributes.
The ABox knowledge mainly verifies whether the conceptual implication relationship (CIR) of instance attributes is consistent.
The ActBox knowledge mainly describes the necessary conditions, formula set, and result set for resource authorization. The actions in the ActBox fall into atomic authorization action, combined authorization action and transfer authorization action.
3.1.1 Concept submodel
The hierarchical conceptual knowledge in TBox lays the basis for judging the completeness of resource instance set. This subsection defines the concept submodel through formal description, paving the way for DDL reasoning.
Definition 1. Concept submodel $\mathcal{M}_{\text {Concept}}$: For TBox T in knowledge base KB, there exists a concept submodel $\mathcal{M}_{\text {Concept}}\left(A_{1}, A_{2}, \ldots\right) \vDash \mathrm{T}$.
(1) If and only if any concept in T contains axiom $A \equiv A^{\prime}$, there exists an interpretation I(ω) that satisfies $A^{I(\omega)} \equiv A^{\prime I(\omega)}$ in any space ω of the world W.
(2) If and only if any relationship in T contains axiom $R \sqsubseteq R^{\prime}$, there exists an interpretation I(ω) that satisfies $R^{I(\omega)} \subseteq R^{\prime I(\omega)}$ in any space $\omega$ of the world W.
Figure 1. The attributedbased finegrained access control model
3.1.2 Instance submodel
The resource instances in ABox are formal resource descriptions based on the ontology resource model, providing the basic information of resources. These instances are essential to judging the realizability of authorization actions. Hence, it is necessary to verify the satisfiability of the concept submodel for each instance. The instance submodel is defined as follows:
Definition 2. Instance submodel $\mathcal{M}_{\text {Instance}}$: For ABox A and TBox T in knowledge base KB, there exists an instance submodel $\mathcal{M}_{\text {Instance}}\left(a_{1}, a_{2}, \ldots\right) \vDash \mathrm{T}$. If and only if $a_{1} \in A$, I(A) is an instance submodel $\mathcal{M}_{\text {Instance}}$ in Τ.
3.1.3 Action submodel
The action submodel is the abstract description of finegrained access control and authorization. Each authorization action is formally depicted as a transition between instance submodels realized by the assignment of a formula set. With the action submodel, the decisionmaker can assign values from the instance set in ABox to each action, judge the realizability of the action, and determine whether the resources are suitable for authorization access.
Definition 3. Action submodel $\mathcal{M}_{\text {Action }}$: According to the authorization rules in ActBox ACT, there exists an assignment $\gamma^{\mathcal{F}}$ in the precondition set $\mathcal{F}$ that makes instance submodel $\mathcal{M}_{\text {Instance}_{\mathrm{P}}}$ satisfy the preconditions of action $\alpha=\left(\mathcal{F}, \mathcal{M}_{\text {Instance}_{P}} / \mathcal{M}_{\text {Instance}_{E}}\right)$, and transfers the result into another instance submodel $\mathcal{M}_{\text {Instance}_{E}}$. The action submodel can be denoted as $\mathcal{M}_{\text {Action}}(\alpha, \beta \ldots) \vDash \exists \gamma^{\mathcal{F}}$, $\mathcal{M}_{\text {Instance}_{P}} \rightarrow_{\alpha}^{\gamma} \mathcal{M}_{\text {Instance}_{E}}$.
3.2 Reasoning based on the authorization model
The preceding subsection models the authorization in resource access control, using TBox, ABox, and ActBox in knowledge base KB. The established authorization model can be reasoned based on the inference engine.
During the authorization, the reasoning task mainly checks the consistency of concepts and instances, the realizability of authorization actions, and the containment between actions. The consistency check ensures that the instances in each ABox satisfy the attributes and attribute correlations of conceptual knowledge structure. The realizability check reflects whether an authorization action on resources is achievable. The containment check clarifies the partial ordering of authorization actions among resources, and helps to reduce redundant RARs. The consistency, realizability, and satisfiability in model reasoning are defined as follows:
3.2.1 Consistency of concepts and instances
The consistency reasoning targets the instances and concepts in ABox and TBox under the static scene. The reasoning deals with the satisfiability of concepts in TBox, and the instance checking and consistency judgement of ABox instances under the constraint of TBox.
Definition 4. Concept satisfiability: Any concept A in concept submodel $\mathcal{M}_{\text {Concept}}$ is satisfiable, if there exists an interpretation $I^{\mathcal{M}\text {Concept}} \neq \emptyset$ for that concept in the model.
Definition 5. Instance checking: For instance submodel $\mathcal{M}_{\text {Instance}}$, there exists an interpretation $I^{\mathcal{M \text{Instance}}}\neq \emptyset$ of instance $C(a)$ about the model in ABox A.
Definition 6. Instance consistency: For instance submodel $\mathcal{M}_{\text {Instance}}$, there exist two instances $C(a), C \in T B ox T$. The instance consistency can be denoted as $A^{I(T)} \vDash C(a)$.
For a given instance ABox A, it should first satisfy the requirement of instance checking, that is, there exists a concept that matches this instance. Next, the concept should be satisfiable, as evidenced by the interpretation of TBox in the concept submodel. Then, the instance consistency can be checked by detecting the conflicts between ABox and the concepts in TBox.
3.2.2 Realizability
The realizability check of authorization actions is a dynamic reasoning in access control. The realizability of complex actions can be extended from the realizability of atomic authorization actions.
Definition 7. Realizability of authorization actions: The atomic authorization action $\alpha$ is realizable, if the instance submodel $\mathcal{M}_{\text {Instance}} \subseteq I(u)=(\Delta, ·^{I(u)})$ and concept submodel $\mathcal{M}_{\text {Concept}} \subseteq I(v)=(\Delta, ·^{I(v)})$ in the initial ABox A description and TBox T satisfy $u \rightarrow_{\mathcal{F}}^{\mathcal{M}_{\text {Instance}}} v$. The realizability can be denoted as $\operatorname{Rel}_{I(u)}^{T}(\alpha)$.
The realizability of an atomic authorization action contains the satisfiability of the preconditions and the consistency of the instances in ABox. The ABox instances in interpretation $I(u)$ can be judged by the instance consistency check, and those in interpretation $I(v)$ can be judged by the concept consistency check in TBox. Then, it can be determined intuitively that there is no inconsistency between the preconditions and the consequences of the authorization action.
The realizability of complex actions can be described as follows:
For combined authorization actions, the realizability can be expressed as: $\operatorname{Rel}_{I(W)}^{T}(P A) \Rightarrow \operatorname{Rel}_{I(u)}^{T}(\alpha) \operatorname{VRel}_{I\left(u^{\prime}\right)}^{T}(\beta) \vee \cdots$ ;
For transfer authorization actions, the realizability can be expressed as: $\operatorname{Rel}_{I(W)}^{T}(P A) \Rightarrow \operatorname{Rel}_{I(u)}^{T}(\alpha) \wedge \operatorname{Rel}_{I\left(u^{\prime}\right)}^{T}(\beta) \wedge \cdots$ .
3.2.3 Satisfiability
The satisfiability of an authorization action is mainly judged based on the satisfiability of the precondition set of the action. The latter is verified against the given TBox, ABox, and ActBox.
Definition 8. Satisfiability of authorization actions: For the given TBox, ABox, and ActBox, an action $\alpha$ with a precondition or precondition set $\mathcal{F}$ is satisfiable if:
The atomic action with $\mathcal{F}$ as the precondition is realizable in T and A;
There exists a possible space $\omega$ making $(\mathcal{M}, \omega) \vDash \mathcal{F}$.
In the XACMLbased resource authorization framework, there are two kinds of assignments, namely, permit and deny. Permit allows the subject to acquire the resource access right, and deny rejects the subject’s access request. Each request for resource access may have different authorization results, causing rule conflicts [1618].
From the hierarchical inheritance of attribute concepts, this section analyzes the causes of rule conflicts. The attributebased finegrained access control mode was adopted to derive the CIRs in attribute hierarchy, and thus detect rule conflicts.
Figure 2. The hierarchy of RAR conflicts
4.1 Types of rule conflicts
The rule authorization effect depends on whether the subject is permitted to access or denied from accessing the requested resource. For the attributes of the subject, rule conflicts may arise from the CIRs in concepts and instances; for the attributes of the resource, rule conflicts may arise from the CIRs. The potential rule conflicts are classified as Figure 2, where AS is subject attribute, AO is resource attribute, hollow arrow is the implication and inheritance between attribute concepts, the plus sign is permit, and the minus sign is denied.
For subject attributes, the lower attributes inherit the rights of the upper attributes. For resource attributes, the lower attributes are the finegrained expression of the upper attributes. As shown in Figure 2, the RARs were divided into eight types (a)(h) according to the CIRs of subjects and resources, the granularity of resource attributes, and the requirements on permit and deny. The difference between RAR types comes from the hierarchy of conceptual knowledge. The following analyzes the possible rule conflicts in each type of RARs. Note that Rule1 and Rule2 are denoted as action submodels $\mathcal{M}_{A c t_{1}}$ and $\mathcal{M}_{A c t_{2}}$, respectively.
(a) $\mathcal{M}_{A c t_{1}} \vDash A S \rightarrow_{\alpha^{+}}^{\gamma} A O_{1}, \mathcal{M}_{A C t_{2}} \vDash A S \rightarrow_{\alpha^{}}^{\gamma} A O_{2}$
$\left\{\begin{array}{c}\mathcal{M}_{A c t_{1}} \neq \mathcal{M}_{A c t_{1}}^{\prime}=A S \rightarrow_{\alpha^{+}}^{\gamma} A O_{2} \\ \mathcal{M}_{A c t_{2}} \vDash A S \rightarrow_{\alpha^{}}^{\gamma} A O_{2}\end{array}\right\} \nRightarrow$ conflict $_{M_{A c t_{1}}}^{\mathcal{M}_{A c t_{2}}}$
In Figure 2, (a) and (b) describe the authorization of hierarchical resources to the same subject. AS means the permit for coarsegrained attribute AO_{1}. The permit cannot be inherited by the finegrained attribute AO_{2}, that is, there exists no interpretation of action submodel $\mathcal{M}_{A c t_{1}}^{\prime}$ that meets the permit for AO_{2}. Therefore, the two RAR actions will not have any conflict.
(b) $\mathcal{M}_{A c t_{1}} \vDash A S \rightarrow_{\alpha^{}}^{\gamma} A O_{1}, \mathcal{M}_{A c t_{2}} \vDash A S \rightarrow_{\alpha^{+}}^{\gamma} A O_{2}$
$\left\{\begin{array}{c}\mathcal{M}_{A c t_{1}} \Rightarrow \mathcal{M}_{A c t_{1}}^{\prime} \vDash A S \rightarrow_{\alpha^{}}^{\gamma} A O_{2} \\ \mathcal{M}_{A c t_{2}} \vDash A S \rightarrow_{\alpha^{+}}^{\gamma} A O_{2}\end{array}\right\} \Rightarrow$ Conflict $_{M_{A C t_{1}}}^{M_{A c t_{2}}}$
If the access to coarsegrained resource attributes is denied, the deny will be inherited by the lower finegrained resource attributes, that is, there exists an interpretation of action submodel $\mathcal{M}_{A c t_{1}}^{\prime}$ to meet the deny of finegrained attribute AO_{2}. In this case, the RARs will conflict each other.
(c) $\mathcal{M}_{A c t_{1}} \vDash A S_{1} \rightarrow_{\alpha^{+}}^{\gamma} A O, \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O$
$\left\{\begin{array}{c}\mathcal{M}_{A c t_{1}} \Rightarrow \mathcal{M}_{A c t_{1}}^{\prime}=A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O \\ \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O\end{array}\right\} \Rightarrow$Conflict$_{\mathcal{M}_{A c t_{1}}}^{\mathcal{M}_{A c t_{2}}}$
(c) and (d) are the resource authorization of subject attributes with CIRs. In the case of (c), the permit of AS_{1} for AO can be transferred to its subattribute AS_{2}, such that there exists an interpretation of action submodel $\mathcal{M}_{A c t_{1}}^{\prime}$ that permits AS_{2} to access AO. This conflicts with the deny of the other rule $\mathcal{M}_{A c t_{2}}$.
(d) $\mathcal{M}_{A c t_{1}} \vDash A S_{1} \rightarrow_{\alpha^{}}^{\gamma} A O, \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O$
$\left\{\begin{array}{c}\mathcal{M}_{A c t_{1}} \Rightarrow \mathcal{M}_{A c t_{1}}^{\prime} \vDash A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O \\ \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O\end{array}\right\} \Rightarrow$Conflict$_{\mathcal{M}_{A c t_{1}}}^{\mathcal{M}_{A c t_{2}}}$
Both (c) and (d) are resulted from the authorization inheritance of subject and resource attributes. In the case of (d), the deny of AS_{1} for AO leads to the deny of AS_{2} for AO, that is, there exists an interpretation of action submodel $\mathcal{M}_{A c t_{1}}^{\prime}$ that denies AS_{2} from accessing AO. This conflicts with the permit of the other rule $\mathcal{M}_{A c t_{2}}$.
(e) $\mathcal{M}_{A c t_{1}} \vDash A S_{1} \rightarrow_{\alpha^{}}^{\gamma} A O_{2}, \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O_{1}$
$\left\{\begin{array}{l}\mathcal{M}_{A c t_{1}} \Rightarrow \mathcal{M}_{A c t_{1}}^{\prime} \vDash A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O_{2} \\ \mathcal{M}_{A c t_{2}} \neq \mathcal{M}_{A c t_{2}}^{\prime}\vDash A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O_{2}\end{array}\right\} \Rightarrow$Conflict$_{\mathcal{M}_{A c t_{1}}}^{\mathcal{M}_{A c t_{2}}}$
(a)(d) are four basic RARs of atomic level attributes. Considering more complex situations, (e) describes the crossauthorization of hierarchical subjects and resources. The subject attributes can inherit the authorization effect of the upper attributes according to the CIRs. Hence, there exists an $\mathcal{M}_{A c t_{1}}^{\prime}$ that denies AS_{2} from accessing AO_{2}. Since the permit for a coarsegrained resource attribute cannot be inherited by lower finegrained attribute, there is no $\mathcal{M}_{A c t_{2}}^{\prime}$ that describes the permit for AO_{2}. In this case, the two rules will not have any conflict.
$(\mathrm{f}) \mathcal{M}_{A c t_{1}} \vDash A S_{1} \rightarrow_{\alpha^{+}}^{\gamma} A O_{2}, \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O_{1}$
$\left\{\begin{array}{l}\mathcal{M}_{A c t_{1}} \Rightarrow \mathcal{M}_{A c t_{1}}^{\prime}=A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O_{2} \\ \mathcal{M}_{A c t_{2}} \Rightarrow \mathcal{M}_{A c t_{2}}^{\prime}=A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O_{2}\end{array}\right\} \Rightarrow$Conflict$_{\mathcal{M}_{A c t_{1}}}^{M_{A c t_{2}}}$
The crossauthorization of (f) is opposite to the effect of (e). In this case, the CIR of each subject attribute make it possible to transfer permit to subattribute AS_{2}. Hence, there exists an $\mathcal{M}_{A c t_{1}}^{\prime}$ that allows AS_{2} to access AO_{2}. Meanwhile, the deny for coarsegrained resource attribute AO_{1} can be inherited by lower finegrained attribute AO_{2}. Thus, there exists an $\mathcal{M}_{A c t_{2}}^{\prime}$ that denies AS_{2} from accessing AO_{2}. As a result, the two rules will have conflict.
$(\mathrm{g}) \mathcal{M}_{A c t_{1}} \vDash A S_{1} \rightarrow_{\alpha^{+}}^{\gamma} A O_{1}, \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O_{2}$
$\left\{\begin{array}{c}\mathcal{M}_{A c t_{1}} \Rightarrow \mathcal{M}_{A c t_{1}}^{\prime} \vDash A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O_{1} \\ \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha}^{\gamma}A O_{2}\end{array}\right\} \nRightarrow$ Conflict $_{\mathcal{M}_{A c t_{1}}}^{M_{A c t_{2}}}$
(g) and (h) are two parallel authorizations. (g) describes the different authorization effects between upper resource attributes to upper subject attributes. The subject attribute AS_{1} transfers the permit for AO_{1} to the lower subattribute AS_{2} via the CIR. Hence, there exists an $\mathcal{M}_{A c t_{1}}^{\prime}$ that allows AS_{2} to access AO_{1}. For action submodels $\mathcal{M}_{A c t_{1}}^{\prime}$ and $\mathcal{M}_{A c t_{2}}$, (g) can be transformed into atomic authorization (a). Therefore, the two rules will have no conflict.
(h) $\mathcal{M}_{A c t_{1}} \vDash A S_{1} \rightarrow_{\alpha^{}}^{\gamma} A O_{1}, \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O_{2}$
$\left\{\begin{array}{c}\mathcal{M}_{A c t_{1}} \Rightarrow \mathcal{M}_{A c t_{1}}^{\prime} \vDash A S_{2} \rightarrow_{\alpha^{}}^{\gamma} A O_{1} \\ \mathcal{M}_{A c t_{2}} \vDash A S_{2} \rightarrow_{\alpha^{+}}^{\gamma} A O_{2}\end{array}\right\} \Rightarrow$Conflict$_{\mathcal{M}_{A c t_{1}}}^{M_{A c t_{2}}}$
Similar to the conflict analysis of (g), the subject attribute AS_{1} in the case of (h) transfers the deny for AO_{1} to the lower subattribute AS_{2} via the CIR. Hence, there exists an $\mathcal{M}_{A c t_{1}}^{\prime}$ that denies AS_{2} from accessing AO_{1}. For action submodels $\mathcal{M}_{A c t_{1}}^{\prime}$ and $\mathcal{M}_{A C t_{2}}$, (h) can be transformed into (b). Therefore, the two rules will have conflict.
4.2 DDLbased conflict detection
From the above analysis on the types of rule conflicts, the possible situations of rule conflicts can be divided into four kinds of atomic authorizations (a)(d). Based on the subject CIRs and inheritance of resource granularity, the cases (e)(h) could be transformed into (a)(b).
Among the four cases, no conflict will occur in (a), for the permit for coarsegrained resource attribute AO_{1} cannot be transferred to lower finegrained attribute AO_{2}. In the other three cases, rule conflicts may occur due to the presence of CIR and deny transfer to finegrained attributes. To detect the conflicts between XACML rules, two issues must be taken into account: the CIRs and type of authorization between subject AS and resource AO.
To facilitate the description of the permit and deny in XACML rules, the action submodel was divided into a set of positive interpretations $\mathcal{M}_{A c t}^{\text {Permit}} \equiv A S \rightarrow_{\alpha^{+}}^{\gamma} A O$ and a set of negative interpretations $\mathcal{M}_{A c t}^{D e n y} \equiv A S \rightarrow_{{\alpha}^}^{\gamma}A O$. Depending on the authorization effect, the RAR with resource is included in different interpretation sets. In case (a), $\mathcal{M}_{A c t_{1}} \in \mathcal{M}_{A c t}^{\text {Permit}}$ and $\mathcal{M}_{A c t_{2}} \in \mathcal{M}_{A c t}^{D e n y}$. Besides, the subject attributes needed for each authorization action were represented by an interpretation of an instance submodel $\mathcal{M}_{\text {instance}_P}^{\mathcal{F}}$, where $\mathcal{F}$ is the precondition made up of subject attributes. The authorized resource attributes were represented by another instance submodel $\mathcal{M}_{\text {instance}_{E}}$. Next, the rule conflicts were detected from subject and resource attributes, respectively.
The inputs of Algorithm 1 include the positive RAR set $\mathcal{M}_{A c t}^{\text {Permit}}$ and the negative RAR set $\mathcal{M}_{A c t}^{D e n y}$, as well as the conceptual knowledge base TBox T. The algorithm detects the rule conflicts arising from the hierarchical inheritance of the resource attributes accessed by the subject, and returns a conflict symbol Conflict $_{M_{A c t_{1}}}^{M_{A c t_{2}}}$.
In Lines 1 and 2, positive RARs and negative RARs in the rules are traversed. The action submodels are expressed as $\mathcal{M}_{A c t_{1}}$ and $\mathcal{M}_{A c t_{2}}$. If there exists an assignment $\gamma^{\mathcal{F}}$ that makes instance $\mathcal{M}_{\text {Instance}_{P}}$ satisfy the preconditions of $\mathcal{M}_{A c t_{1}}$ and $\mathcal{M}_{A c t_{2}}$ (Line 3), and if there exist concept submodels $\mathcal{M}_{\text {Concept }_{E_{1}}}^{I}$ and $\mathcal{M}_{\text {Concept }_{E_{2}}}^{I}$ that satisfy instances among the authorization objects $\mathcal{M}_{\text {Instance}_{E_{1}}}$ and $\mathcal{M}_{\text {Instance}_{E_{2}}}$ of the rules (Line 4), then the satisfiability of the concept submodels will be judged by TBox T. If TBox T contains the deny for finegrained resource attributes, i.e. there exists a CIR $\mathcal{M}_{\text {Concept}_{E_{2}}} \sqsubseteq \mathcal{M}_{\text {Concept}_{E_{1}}}$, then the rules will conflict as in case (b).
Algorithm 1. Rule conflict detection based on the hierarchy of resource attributes 
Inputs: $\mathcal{M}_{A c t}^{\text {Permit}}$; $\mathcal{M}_{A c t}^{D e n y}$; TBox T; Outputs: Conflict $_{\mathcal{M}_{A c t_{1}}}^{\mathcal{M}_{A c t_{2}}}$ 1: For each $\mathcal{M}_{A c t_{1}}$ in $\mathcal{M}_{A c t}^{\text {Permit}}$ do 2: For each $\mathcal{M}_{A c t_{2}}$ in $\mathcal{M}_{A c t}^{D e n y}$ do 3: $\exists \gamma^{\mathcal{F}}, \mathcal{M}_{A c t_{1}} \vDash \mathcal{M}_{\text {Instance}_{P}} \rightarrow_{\alpha^{}}^{\gamma} \mathcal{M}_{\text {Instance}_{E_{1}}}$ AND $\mathcal{M}_{A c t_{2}} \vDash \mathcal{M}_{\text {Instance}_{P}} \rightarrow_{\alpha^{+}}^{\gamma} \mathcal{M}_{\text {Instance}_{E_{2}}}$; 4: $\mathcal{M}_{\text {Instance}_{E_{1}}} \vDash \mathcal{M}_{\text {Concept}_{E_{1}}}^{I}$, $\mathcal{M}_{\text {Instance}_{E_{2}}} \vDash \mathcal{M}_{\text {Concept}_{E_{2}}}^{I}$; 5: If $\mathcal{M}_{\text {Concept}_{E_{2}}} \sqsubseteq \mathcal{M}_{\text {Concept}_{E_{1}}}$, in T then 6: ConfictDissolve $\left(\mathcal{M}_{A c t_{1}}, \mathcal{M}_{A c t_{2}}\right)$; 7: Return true; 8: Else 9: Return false; 10: End if 11: End for each 12: End for each 
Then, the conflicting action submodels are processed: the permit $\mathcal{M}_{A c t_{2}}$ for finegrained resource attributes is deleted to terminate the inheritance between resource attributes (Line 6). If there is a permit for coarsegrained resource attributes, or if the rule sets contain no assignment that meets the requirements, then the rule sets do not contain rule conflicts (Case a).
Algorithm 1 mainly detects the RAR conflicts arising from the inheritance between resource attributes (Cases a and b). The algorithm locates the conflicting rules, and calls the conflict mitigation function to handle these rules.
TBox provides a hierarchical relationship reflecting the concepts of resource attributes, and determines the existence of rule conflicts by verifying the $\subseteq$ relationship between resource attributes. This CIR belongs to the problem of concept consistency verification in description logic.
The rule conflicts arising from the hierarchy of subject attributes can also be detected by verifying the $\subseteq$ relationship (Algorithm 2).
Similar to those of Algorithm 1, the inputs of Algorithm 2 contain rule sets and the conceptual knowledge base. The algorithm detects the rule conflicts arising from the hierarchy of subject attributes, and returns a conflict symbol.
The algorithm firstly traverses the rule sets (Lines 1 and 2). Under the following conditions, the rules will have conflicts of types (c) and (d): there exist the assignments $\gamma^{\mathcal{F}_{1}}$ and $\gamma^{\mathcal{F}_{2}}$ among subject attributes that make instance submodels $\mathcal{M}_{\text {Instance}_{P_{1}}}$ and $\mathcal{M}_{\text {Instance}_{P_{2}}}$ satisfy the preconditions of $\mathcal{M}_{A c t_{1}}$ and $\mathcal{M}_{A c t_{2}}$, respectively (Line 3); TBox T contains interpretations $\mathcal{M}_{{Concept}_{P1}}^{I}$ and $\mathcal{M}_{{Concept}_{P2}}^{I}$ that satisfy concept submodels (Line 4); the concept submodels have the CIR (Line 5).
Then, the conflicting rules are processed: the lower subject attributes are deleted to keep the consistency between the authorization of higher subject attributes (Line 6). If there is no CIR between subject attributes, then the rule sets will not face any rule conflict arising from the hierarchy of subject attributes.
The abovementioned atomic RAR conflicts can be detected and resolved by the two algorithms. The complex and crossauthorizations can be handled similarly.
Algorithm 2. Rule conflict detection based on the hierarchy of subject attributes 
Inputs: $\mathcal{M}_{A c t}^{\text {Permit }}$; $\mathcal{M}_{A c t}^{D e n y}$; TBox T; Output: $\text { Conflict }_{\mathcal{M}_{A C t_{1}}}^{\mathcal{M}_{A C t_{2}}}$ 1: For each $\mathcal{M}_{A c t_{1}}$ in $\mathcal{M}_{A c t}^{\text {Permit }}$ do 2: For each $\mathcal{M}_{A C t_{2}}$ in $\mathcal{M}_{A c t}^{D e n y}$ do 3: $\exists \gamma_{1}^{\mathcal{F}_{1}}, \gamma_{2}^{\mathcal{F}_{2}}, \mathcal{M}_{A c t_{1}} \vDash \mathcal{M}_{\text {Instance}_{P_{1}}} \rightarrow_{\alpha^{+}}^{\gamma_{1}} \mathcal{M}_{\text {Instance}_{E}}$ AND $\mathcal{M}_{A c t_{2}} \vDash \mathcal{M}_{\text {Instance}_{P_{2}}} \rightarrow_{{\alpha}^}^{\gamma_{2}}\mathcal{M}_{\text {Instance}_{E}}$; 4: $\mathcal{M}_{\text {Instance}_{P_{1}}} \vDash \mathcal{M}_{\text {Concept}_{P_{1}}}^{I}$, $\mathcal{M}_{\text {Instance}_{P_{2}}} \vDash \mathcal{M}_{\text {Concept}_{P_{2}}}^{I}$; 5: If $\mathcal{M}_{\text {Concept}_{P_{2}}} \sqsubseteq \mathcal{M}_{\text {Concept}_{P_{1}}}$ in T then 6: $ConfictDissolve \left(\mathcal{M}_{A c t_{1}}, \mathcal{M}_{A c t_{2}}\right)$; 7: Return true; 8: Else 9: Return false; 10: End if 11: End for each 12: End for each 
4.3 DDLbased reasoning
The DDL can reason about the ACR authorization based on the process and transfer, and provide the reasoning ability for the global rule library via the Tableau algorithm. In rule conflict detection, the reasoning mainly covers two aspects: if the rule conflict arises from the hierarchy of attributes, the key is to validate the CIR that interprets the instance submodel; if the rule conflict arises from RAR transfer, the key is to verify the consistency between the assertion sets of RAR action and instance submodels. These reasoning problems are comparable to the satisfiability problem and the consistency detection problem in the DDL [19, 20].
Definition 9. Concept submodels $\mathcal{M}_{\text {Concept}_{1}}$ and $\mathcal{M}_{\text {Concept}_{2}}$ satisfy the CIR $\mathcal{M}_{\text {Concept}_{1}} \sqsubseteq \mathcal{M}_{\text {Concept}_{2}}$, if and only if TBox T contains an interpretation I that makes $\mathcal{M}_{\text {Concept }_{1}}^{I} \subseteq \mathcal{M}_{\text {Concept }_{2}}^{I}$.
Theorem 1. The CIR $\mathcal{M}_{\text {Concept}_{1}} \sqsubseteq_{T} \mathcal{M}_{\text {Concept}_{2}}$ holds between the concept submodels in TBox T, if and only if $\mathcal{M}_{\text {Concept}_{1}}^{I} \sqcap \neg \mathcal{M}_{\text {Concept}_{2}}^{I}$ is unsatisfiable, i.e. $\mathcal{M}_{\text {Concept }_{1}}^{I} \sqcap \neg \mathcal{M}_{\text {Concept }_{2}}^{I}=\emptyset$.
If TBox T contains an interpretation I that makes two submodels $\mathcal{M}_{\text {Concept}_{1}}$ and $\mathcal{M}_{\text {Concept}_{2}}$ satisfy the CIR, and if there exists a concept model $\mathcal{M}_{\text {Concept }_{1}}^{I} \sqcap \neg \mathcal{M}_{\text {Concept }_{2}}^{\text {I }} \neq \emptyset$ that satisfies T, then there exists an instance submodel $\mathcal{M}_{\text {Instance}_{1}}^{I} \in \mathcal{M}_{\text {Concept}_{1}}^{I}$ that satisfies interpretation I. Due to the existence of the CIR, there also exists $\mathcal{M}_{\text {Instance}_{2}}^{I} \in \mathcal{M}_{\text {Concept}_{2}}^{I}$, which contradicts $\mathcal{M}_{\text {Instance}_{1}}^{I} \in \neg \mathcal{M}_{\text {Concept}_{2}}^{I}$. Hence, no such instance exists in $\mathcal{M}_{\text {Instance}_{1}}^{I} \sqcap \neg \mathcal{M}_{\text {Concept}_{2}}^{I}$.
Definition 10. If the two assertions $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ in instance submodels $\mathcal{M}_{\text {Instance}_{1}}$ and $\mathcal{M}_{\text {Instance}_{2}}$ that transfer RAR results obey $\mathcal{F}_{1} \sqcap \mathcal{F}_{2}=\emptyset$, then the two instance submodels are inconsistent, i.e. $\mathcal{M}_{\text {Instance}_{1}} \sqcap \mathcal{M}_{\text {Instance}_{2}}=\emptyset$.
The satisfiability verification of the DDL can be achieved by the Tableaux algorithm [19]. The reasoning verification of two concept or instance submodels can be realized by the following rules.
Take the satisfiability verification of instance submodels for example. By the following rules, an expansion set $\mathcal{E} \mathcal{S}$ of attributes can be extended from $\mathcal{M}_{\text {Instance}_{1}}$ and $\mathcal{M}_{\text {Instance}_{2}}$. Then, the satisfiability of the two submodels can be evaluated by judging whether the expansion set brings rule conflicts. If the expansion set contains $\perp$, then the two submodels are not satisfiable, and face rule conflicts.
П rule: If there exists an interpretation I in TBox T that makes $\mathcal{M}_{\text {Instance}_{1}}^{I} \sqcap \mathcal{M}_{\text {Instance}_{2}}^{I} \in \mathcal{E} \mathcal{S}$( $\mathcal{M}_{\text {Instance}_{1}}^{I} \notin \mathcal{E S}$, $\mathcal{M}_{\text {Instance}_{2}}^{I} \notin \mathcal{E} \mathcal{S}$), then $\left\{\mathcal{M}_{\text {Instance}_{1}}, \mathcal{M}_{\text {Instance}_{2}}\right\}$ should be expanded to $\mathcal{E} \mathcal{S}$;
$\sqcup$ rule: If there exists an interpretation I in TBox T that makes $\mathcal{M}_{\text {Instance}_{1}}^{I} \sqcup \mathcal{M}_{\text {Instance}_{2}}^{I} \in \mathcal{E} \mathcal{S}$( $\mathcal{M}_{\text {Instance}_{1}}^{I} \notin \mathcal{E S}$ , $\mathcal{M}_{\text {Instance}_{2}}^{I} \notin \mathcal{E} \mathcal{S}$), then $\mathcal{M}_{{\text {Instance}}_*}$ should be expanded to $\mathcal{E} \mathcal{S}$, where $\mathcal{M}_{\text {Instance}_{*}}=\mathcal{M}_{\text {Instance}_1}^{I}$ or $\mathcal{M}_{\text {Instance}_{*}}=\mathcal{M}_{\text {Instance}_2}^{I}$;
$\exists$ rule: If there exists an interpretation I in TBox T that makes $\exists R . \mathcal{M}_{\text {Instance}_{1}}^{I} \in \mathcal{E S}$, and $\nexists \mathcal{M}_{\text {Instance}_{2}}^{I}, R$$\left(\mathcal{M}_{\text {Instance}_{1}}^{I}, \mathcal{M}_{\text {Instance}_{2}}^{I} \in \mathcal{E} \mathcal{S}, \mathcal{M}_{\text {Instance}_{2}}^{I} \in \mathcal{E} \mathcal{S}\right)$, then $\left\{\mathcal{M}_{\text {Instance}_{2}}, R\left(\mathcal{M}_{\text {Instance}_{1}}, \mathcal{M}_{\text {Instance}_{2}}\right)\right\}$ should be expanded to $\mathcal{E} \mathcal{S}$;
$\forall$ rule: If there exists an interpretation I in TBox T that makes $\forall R . \mathcal{M}_{\text {Instance}_{1}}^{I} \in \mathcal{E} \mathcal{S}$, $\mathcal{M}_{\text {Instance}_{2}}^{I} \notin \mathcal{E S}$, then $\left\{\mathcal{M}_{\text {Instance}_{2}}\right\}$ should be expanded to $\mathcal{E} \mathcal{S}$;
Action $\alpha$ rule: If there exist an interpretation I in TBox T and an assignment set $\gamma^{\mathcal{F}}$ that make $\mathcal{M}_{\text {Instance}_{1}}^{I} \longrightarrow_{\alpha}^{\mathcal{F}} \mathcal{M}_{\text {Instance}_{2}}^{I}$( $\mathcal{M}_{\text {Instance}_{2}} \in \mathcal{E} \mathcal{S}$), then $\mathcal{M}_{\text {Instance}_{1}}$ should be replaced with $\mathcal{M}_{\text {Instance}_{2}}$ in $\mathcal{E} \mathcal{S}$.
Theorem 2. Reliability: The DDLbased rule conflict detection is reliable.
The DDLbased rule conflict detection method targets two kinds of rule conflicts in authorization: the conflicts arising from the hierarchy of attributes and those arising from the transfer of authorization.
For the first kind of rule conflicts, the implication and inheritance relationships that stem from the hierarchy of attributes can be converted by Algorithms 1 and 2 into the CIRs in TBox for satisfiability verification. The satisfiability problems can be solved by the Tableaux algorithm in description logic.
For the second kind of rule conflicts, the rule conflict detection can be converted by RAR transfer rules into the satisfiability problem of instance submodels of the authorization results.
Action α rule is derived from the DDL description and reasoning mechanism. The correctness of the algorithm can be ensured by replacing elements in the extended set. Therefore, the DDLbased rule conflict detection must be correct.
Theorem 3. Decidability: The DDLbased rule conflict detection is decidable.
The abovementioned rules can solve the rule conflict detection problem, for the problem can be converted into the satisfiability and consistency reasoning problems in the DDL. Among these rules, П, $\exists$ and $\forall$ rules can be completed in polynomial time. Despite the uncertainty of its completion time, $\sqcup$ rule is a complete binary tree in the worstcase scenario, which can be completed in a limited time. Action α rule contains replacement operations, which can also be completed in a limited time. The final judgement based on the extension set has two results $\perp$ and T. Therefore, The DDLbased rule conflict detection is decidable.
5.1 Experimental environment
The DDLbased reasoning of RAR conflicts between finegrained resource attributes was verified through experiments on rule inference and conflict detection. As shown in Figure 3, the experimental model contains three main parts: an XACMLDDL converter, a rule analyzer, and an output generator.
The XACMLDDL converter is responsible for converting XACML rules into DDL semantics. During the working, the converter firstly traverses the element nodes in each rule, and loads the information of the corresponding rule. Then, the DDLConverting is called to convert the information into a rule described in DDL language. Based on the instance and concept submodels in the PIP ontology library, the rule analyzer performs logic reasoning on the rules described in DDL language, and feedbacks the reasoning results and anomaly handling to the output generator.
The rule inference components include attribute matching (Comparison), satisfiability verification (Verification) and conflicting rule checking (Conflict Checking). The rule analyzer provides an inference engine interface, allowing different DL inference engines (e.g. Pellet, Fact++, and Racer) [2123] to participate in the rule inference of description logic. During Tableaubased rule inference, the inference engine is supported by the data from the ontology library provided by the decisionmaker. The rules being inferred and their inference results are forwarded by the rule analyzer to the output generator for further processing. The output generator aggregates the abnormal rules into a rule set and feeds it back to the rule administrator, who will handle the abnormal rules.
The experimental data consists of two parts: Continue dataset and its expansion. Continue dataset was adopted by the XACML rule analyzer Margrave [24, 25], which is based on binary decision diagram (BDD). This dataset was selected to validate the XACMLbased DL inference engine. The Continue dataset contains various complex and available XACML rules, which control the access of qualified users to article resources. A total of 26 rule files are provided in the dataset, including 86 RARs and 37 kinds of elements about user and article attributes. There are five description structures for identities and roles: pcmember, pcchair, subreviewer, editor and admin. As shown in Table 1, the inheritance relationship in the dataset has a maximum of four layers: pcMember $<$ pcChair $<$ subReviewer $<$ editer $<$admin.
The Continue dataset was also expanded, according to the situation in lightweight applications of attribute set and rule set in the IoT. The attribute descriptions of resources were refined, and the descriptions of IoT resource attributes were added to the original dataset. The expansion process is detailed in the next subsection.
Four layers of inheritance relationships may exist, depending on the identities and roles. The number of service attributes in the rules of the dataset and the number of rules is denoted as $\# \sum a t b s_{r u l e}$ and $\# \sum r u l e S_{p o l}$, respectively. Different layers of inheritance may have the same RAR. The greater the number of inheritance layers, the more the attribute values in the rules. The experiments were carried out on Intel Pentium 4 2.4GHz CPU, 2GB memory, Windows XP SP3, and Java Runtime Environment 1.6.
Figure 3. Analysis framework of rule inference experiments
Table 1. Inheritance relationships between attributes
Inheritance relationship 
CIR 
$\# \sum a t b s_{r u l e}, \# \sum$rules$_{p o l}$ 
Onelayer inheritance 
(admin, editor) 
9, 24 
Twolayer inheritance 
(editor, subreviewer) (admin, subreviewer) 
16, 33 
Threelayer inheritance 
(subreviewer, pcchair) (editor, pcchair) (admin, pcchair) 
28, 42 
Fourlayer inheritance 
(pcchair, pcmember) (subviewer, pcmember) (editor, pcmember) (admin, pcmember) 
31, 69 
Table 2. Time overheads of inference engines on authorization reasoning (unit: second)
Inheritance relationship 
Pellet 
Racer 
Fact++ 
Margrave 

Loading 
Verify 
Loading 
Verify 
Loading 
Verify 
Loading 
Verify 

Onelayer inheritance 
0.715 
0.582 
0.746 
0.631 
0.683 
0.660 
0.915 
0.014 
Twolayer inheritance 
0.752 
0.577 
0.781 
0.659 
0.714 
0.689 
1.298 
0.019 
Threelayer inheritance 
0.929 
0.625 
0.912 
0.647 
1.057 
0.729 
1.553 
0.026 
Fourlayer inheritance 
1.602 
0.697 
1.419 
0.720 
1.377 
0.741 
2.084 
0.028 
5.2 Performance evaluation
Rules with different inheritance layers were selected from the dataset to measure the time overhead of loading and reasoning for Continue dataset rules on the experimental platform. The time overhead on the platform is made up of the rule loading time (Loading) and rule verification time (Verify). The former refers to the time to traverse the elements in XACML rules and convert them into DDL logic description. The latter refers to the time to logically reason about DDL formal models based on the PIP.
The time overheads of four inference engines, namely, Pellet, Racer, Fact++ and Margrave, were compared. The first three inference engines are grounded on DDL formal descriptions, and the formal description and reasoning of the last engine are based on the BDD.
Firstly, a rule instance needs to be converted into a formal DDL description. Take a onelayer inheritance rule in Continue dataset for example. If the subject is an admin or editor, then the meetingflag of the conference turntable can be modified. The assertion P of the rule can be converted into a DDL formal description. In the subinstance model, the instances and actions satisfy: $P \equiv$$\left(\exists \mathcal{M}_{\text {Instance}}^{\text {Admin}} \sqcup \mathcal{M}_{\text {Instance}}^{\text {Editor}}\right) \sqcap \exists \mathcal{M}_{\text {Action}}^{\text {Write}} \sqcap \exists \mathcal{M}_{\text {Instance}}^{\text {MeetingFlag}}$. Then, the satisfiability of the DDL formal description can be verified by the inference engine.
The time overheads of each inference engine on inheritance rules of different layers were recorded on the experimental platform (Table 2).
As shown in Table 2, the DLbased inference engines differed slightly in time overhead in the rule loading phase. Their time overheads were basically 1s, which is smaller than the BDDbased Margrave. The superiority of DLbased inference engines comes from the convenient conversion of XACML resource attributes into DL descriptions. Compared with Margrave, the DLbased inference engines are strong and efficient in formal expression of subjects, resources and RAR ontologies in the XML format.
In the verification phase, Margrave had an obvious advantage, as its time overheads were basically on the order of 10ms. This inference engine has a high efficiency in assertion verification, due to the rule inference based on the BDD. As for the three DLbased inference engines, the time overhead in rule inference and verification basically stabilized within 1s. The mean time overhead of Pellet stood at 0.6s, and that of Racer and Fact++ fell between 0.6s and 0.8s. Considering the actual application environment, the time overheads of DLbased inference engines, coupled with XACML conversion mechanism, are acceptable in the verification phase.
The Continue dataset offers a limited number of attributes and rules, which are insufficient to effectively simulate the application environment of the access authorization for cloud resources. Therefore, the dataset was expanded from two aspects, aiming to disclose the effects of the massive resources and RARs in cloud environment on the time overhead in DDL reasoning.
(1) Expanding attribute values without changing rule structure
Each attribute description in a rule was expanded by adding new attribute values. First, a similar attribute list $\left\{v_{1}, v_{1}, \cdots, v_{l i m i t}\right\}$ was prepared for each attribute description in the rule, where limit is the threshold for the scale of attribute expansion. Next, each element node in the rule is traversed. If the original attribute value v was detected, it would be replaced by a random attribute in the similar attribute list. The expansion was terminated once all attribute values were replaced. The hierarchy of attributes was not changed through the expansion.
(2) Expanding rule set
The original rule set was expanded to increase the number of rules available. Specifically, a new reference node was added to the root node rule file (RPSlist.xml) in the Continue dataset. Under the node, new rules were generated by the XACML rule generator [26]. During the generation, the number of generated rules was controlled by configuring the following parameters: the maximum depth of rule tree (maxDepth), the maximum number of attributes (maxAttributePerCategory), the maximum attribute value (maxValuesPerAttribute), and the maximum number of rules (maxChildren). The attributes in the expanded rules must be those s that already exist in the Continue dataset.
The number of attributes and rules in the expanded Continue dataset could be controlled according to the experimental needs.
To verify the time overheads in conflict detection in Table 2, three experiments were designed to reveal (1) the effects of growing number of rules on the time overheads in detecting a single rule conflict, (2) the time overheads in detecting multiple rule conflicts at a fixed number of rules, and (3) the effects of the number of attributes on the efficiency of conflict detection.
Figure 4. Effects of the number of rules on time overhead in detecting a single conflict
Figure 5. Effects of the number of rules on time overhead in detecting multiple conflicts
Figure 6. Effects of the number of attributes on the efficiency of conflict detection
In Experiment 1, six rule sets containing rule conflicts were selected from the expanded Continue dataset. The six sets include 50, 75, 100, 125, 175, and 200 rules, respectively. The algorithms in Subsection 4.2 were applied to detect the single rule conflict in these sets. The time overheads in conflict detection are recorded as Figure 4.
In Experiment 2, the number of rules in the rule set was controlled at 126. The proposed algorithms were adopted to detect the multiple rule conflicts. The time overheads in conflict detection are recorded as Figure 5.
The experimental results demonstrate that the efficiency of the conflict detection algorithms depends on the number of rules and conflicts in the rule set. As shown in Figure 4, the time overhead in detecting a single conflict increased linearly with the number of conflicts in the rule set. As shown in Figure 5, the time overhead in detecting multiple conflicts also increased linearly with the number of conflicts, except slight fluctuations at some nodes. For example, the time overhead in detecting 9 conflicting nodes differed from that in detecting 19 nodes. However, the fluctuation of time overhead was within 2s, and the time overheads for neighboring nodes exhibited no significant changes. Hence, the fluctuations can be neglected in actual applications. To sum up, the efficiency of conflict detection is basically linearly correlated with the number of conflicts. The proposed algorithms could detect the conflicts in the expanded Continue dataset within polynomial time, which satisfies the description in Theorem 3.
In Experiment 3, the Continue dataset was expanded by increasing attribute values without changing rule structure. Five rule sets with the same number of rules (175) were selected for the experiment. The number of attributes in the five sets was 27, 49, 65, 81 and 107, respectively. According to the hierarchical inheritance relationship among the policies, the data in five data sets are classified as four data groups. The proposed algorithms were adopted to detect the rule conflicts in these four data groups. The time overheads in conflict detection are recorded in Figure 6.
The four rule sets, which have different layers of inheritance, performed differently with the changing number of attributes. With the growing number of attributes, the time overheads of all four sets in conflict detection increased. The reason is that the addition of attributes increases the traversal time of all resource attribute nodes. The time overheads increased linearly with the number of attributes, which are acceptable on the expanded Continue dataset.
Owing to the difference in inheritance relationship, the four rule sets also differed in the time overhead under the same number of attributes. The difference is attributable to the following factors: a lower rule set has a smaller time overhead, because it contains fewer rules and the CIRs between its concepts could be computed in a shorter time. With the growth in the number of attributes, the time overhead difference between the rule sets continued to widen. This means, when the number and structure of rules remain the same, the number of attributes is the main influencing factor of the time overhead in conflict detection.
The XACML, as an attributebased ACR description language, is suitable for authorizing access to resources in an open environment. Focusing on the possible RAR conflicts, this paper explores the causes of rule conflicts, and formally describes resource attributes with the DDL. Next, problems like attribute consistency and rule satisfiability were examined by setting up concept, instance and action knowledge bases. Then, a conflict detection algorithm was designed to identify the rule conflicts arising from the hierarchy of resource attributes. The algorithm relies on Tableau rules to detect rule conflicts in the light of satisfiability. The reliability and decidability of the algorithm were fully demonstrated. After that, three experiments were carried out to verify the feasibility of DDLbased authorization and reasoning, and to analyze the actual time overheads in loading and verification phases on expanded Continue dataset. The efficiency of the proposed algorithm was analyzed from three aspects: the number of rules, the number of conflicts, and the hierarchy of attributes. The results show that the DLbased inference is decidable in polynomial time.
[1] http://docs.oasisopen.org/xacml/3.0/xacml3.0corespecosen.pdf.
[2] Atlam, H.F., Alassafi, M.O., Alenezi, A., Walters, R.J., Wills, G.B. (2018). XACML for building access control policies in internet of things. In IoTBDS, pp. 253260. http://doi.org/10.5220/0006725102530260
[3] Ayache, M., Erradi, M., Khoumsi, A., Freisleben, B. (2016). Analysis and verification of XACML policies in a medical cloud environment. Scalable Computing: Practice and Experience, 17(3): 189206. http://doi.org/10.12694/scpe.v17i3.1180
[4] Kanwal, T., Jabbar, A.A., Anjum, A., Malik, S.U., Khan, A., Ahmad, N. (2019). Privacyaware relationship semantics–based XACML access control model for electronic health records in hybrid cloud. International Journal of Distributed Sensor Networks, 15(6): 97114. http://doi.org/10.1177/1550147719846050
[5] Charaf, L.A., Alihamidi, I., Addaim, A., Abdessalam, A.I.T. (2020). A distributed XACML based access control architecture for IoT systems. In 2020 1st International Conference on Innovative Research in Applied Science, Engineering and Technology (IRASET), pp. 15. http://doi.org/10.1109/IRASET48871.2020.9092276
[6] Damiano, D., Paolo, M., Laura, R. (2019) A blockchain based approach for the definition of auditable access control systems. Computers & Security, 84: 93119. https://doi.org/10.1016/j.cose.2019.03.016
[7] Ma, M., Shi, G., Li, F. (2019) PrivacyOriented blockchainbased distributed key management architecture for hierarchical access control in the IoT scenario. IEEE Access, 7: 3404534059. https://doi.org/10.1109/ACCESS.2019.2904042
[8] Zyskind, G., Nathan, O. (2015). Decentralizing privacy: Using blockchain to protect personal data. In 2015 IEEE Security and Privacy Workshops, pp. 180184. https://doi.org/10.1109/SPW.2015.27
[9] Sukhodolskiy, I., Zapechnikov, S. (2018). A blockchainbased access control system for cloud storage. In 2018 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), pp. 15751578. https://doi.org/10.1109/EIConRus.2018.8317400.
[10] Wang, S., Zhang, Y., Zhang, Y. (2018). A blockchainbased framework for data sharing with finegrained access control in decentralized storage systems. IEEE Access, 6: 3843738450. https://doi.org/10.1109/ACCESS.2018.2851611
[11] Turkmen, F., den Hartog, J., Ranise, S., Zannone, N. (2017). Formal analysis of XACML policies using SMT. Computers & Security, 66: 185203. https://doi.org/10.1016/j.cose.2017.01.009
[12] Bertolino, A., Daoudagh, S., Lonetti, F., Marchetti, E. (2018, May). An automated modelbased test oracle for access control systems. In 2018 IEEE/ACM 13th International Workshop on Automation of Software Test (AST), pp. 28. https://doi.org/10.1145/3194733.3194743
[13] Hsaini, S., Azzouzi, S., Charaf, M.E.H. (2019). FSM modeling of testing security policies for MapReduce frameworks. In 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT), pp. 14801485. https://doi.org/10.1109/CoDIT.2019.8820685
[14] Lonetti, F., Marchetti, E. (2018). Online tracing of XACMLbased policy coverage criteria. IET Software, 12(6): 480488. https://doi.org/10.1049/ietsen.2017.0351
[15] Xu, D., Wang, Z., Peng, S., Shen, N. (2016). Automated fault localization of XACML policies. In Proceedings of the 21st ACM on Symposium on Access Control Models and Technologies, pp. 137147. https://doi.org/10.1145/2914642.2914653
[16] Calabrò, A., Lonetti, F., Marchetti, E. (2017). Access control policy coverage assessment through monitoring. In International Conference on Computer Safety, Reliability, and Security, pp. 373383. https://doi.org/10.1007/9783319662848_31
[17] Mourad, A., Tout, H., Talhi, C., Otrok, H., Yahyaoui, H. (2016). From modeldriven specification to designlevel setbased analysis of XACML policies. Computers & Electrical Engineering, 52: 6579. https://doi.org/10.1016/j.compeleceng.2015.09.021
[18] Mejri, M., Yahyaoui, H., Mourad, A., Chehab, M. (2020). A rewriting system for the assessment of XACML Policies Relationship. Computers & Security, 97: 101957. https://doi.org/10.1016/j.cose.2020.101957
[19] Chernov, A.V., Butakova, M.A., Kartashov, O.O., Alexandrov, A.A. (2019). Intelligent decision support by means of dynamic description logic. In 2019 XXII International Conference on Soft Computing and Measurements (SCM), pp. 138141. https://doi.org/10.1109/SCM.2019.8903760
[20] Baader, F., Gil, O.F., Marantidis, P. (2018). Matching in the Description Logic FL0 with respect to General TBoxes. In LPAR, pp. 7694. https://doi.org/10.29007/q74p
[21] Vijayalakshmi, K., Jayalakshmi, V. (2020). A prioritybased approach for detection of anomalies in ABAC policies using clustering technique. In 2020 Fourth International Conference on Computing Methodologies and Communication (ICCMC), pp. 897903. https://doi.org/10.1109/ICCMC48092.2020.ICCMC000166
[22] Silvestre, D., Hespanha, J., Silvestre, C. (2020). Resilient desynchronization for decentralized medium access control. IEEE Control Systems Letters, 5(3): 803808. https://doi.org/10.1109/LCSYS.2020.3005819
[23] Sabitha, S., Rajasree, M.S. (2017). Access control based privacy preserving secure data sharing with hidden access policies in cloud. Journal of Systems Architecture, 75: 5058. https://doi.org/10.1016/j.sysarc.2017.03.002
[24] Fisler, K., Krishnamurthi, S., Meyerovich, L.A., Tschantz, M.C. (2005). Verification and changeimpact analysis of accesscontrol policies. In Proceedings of the 27th International Conference on Software Engineering, pp. 196205. https://doi.org/10.1109/ICSE.2005.1553562
[25] http://www.margravetool.org/v1+v2/margrave/versions/0101/documentation/.
[26] Sanchez, M., López, G., GómezSkarmeta, A.F., Cánovas, Ó. (2006). using microsoft office infopath to generate XACML policies. In International Conference on EBusiness and Telecommunication Networks, Springer, Berlin, Heidelberg, pp. 134145. https://doi.org/10.1007/9783540707608_11