30-08-2014, 03:56 PM
Discovery and Resolution of Anomalies in Web Access Control Policies
Discovery.docx (Size: 1.27 MB / Downloads: 10)
Abstract—
Emerging computing technologies such as web services, service-oriented architecture, and cloud computing has enabled us to perform business services more efficiently and effectively. However, we still suffer from unintended security leakages by unauthorized actions in business services while providing more convenient services to Internet users through such a cutting-edge technological growth. Furthermore, designing and managing web access control policies are often error-prone due to the lack of effective analysis mechanisms and tools. In this paper, we represent an innovative policy anomaly analysis approach for web access control policies, focusing on extensible access control markup language policy. We introduce a policy-based segmentation technique to accurately identify policy anomalies and derive effective anomaly resolutions, along with an intuitive visualization representation of analysis results. We also discuss a proof-of-concept implementation of our method called XAnalyzer and demonstrate how our approach can efficiently discover and resolve policy anomalies
1 INTRODUCTION
WITH the tremendous growth of web applications and web
services deployed on the Internet, the use of a policy-based approach has recently received considerable attention to accommodate thesecurity requirements cover-ing large, open, distributed, and heterogeneous computing environments. eXtensible Access Control Markup Language (XACML) [25], which is a general-purpose access control policy language standardized by the Organization for the Advancement of Structured Information Standards, has been broadly adopted to specify access control policies for various applications, especially web services [28]. In an XACML policy, multiple rules may overlap, which means one access request may match several rules. Moreover, multiple rules within one policy may conflict, implying that those rules not only overlap each other, but also yield different decisions. Conflicts in an XACML policy may lead to both safety problem (e.g., allowing unauthorized access)and availability problem (e.g., denying legitimate access). An intuitive means for resolving policy conflicts by a policy designer is to remove all conflicts by modifying the policies. However, resolving conflicts through changing the policies is notably difficult, even impossible, in practice from many aspects. First, the number of conflicts in an XACML policy is potentially large, since an XACML policy may consist of hundreds or thousands of rules.
Second, conflicts in XACML policies are probably very complicated, because one rule may conflict with multiple other rules, and one conflict may be associated with several rules. Besides, an XACML policy for a distributed application may be aggregated from multiple parties. Also, an XACML policy may be maintained by more than one administrator. Without a priori knowledge on the original intentions of policy specification, changing a policy may affect the policy’s semantics and may not resolve conflicts correctly. Furthermore, in some cases, a policy designer may intentionally introduce certain over-laps in XACML policy components by implicitly reflecting that only the first rule is important. In this case, conflicts are not an error, but intended, which would not be necessary to be changed.
Since the conflicts in XACML policies always exist and are hard to be eliminated, XACML defines four different combining algorithms to automatically resolve conflicts [25]: Deny-Overrides, Permit-Overrides, First-Applicable, and
Only-One-Applicable. Unfortunately, XACML currently lacks a systematic mechanism for precisely detecting conflicts. Identifying conflicts in XACML policies is critical for policy designers since the correctness of selecting a combining algorithm for an XACML policy or policy set component heavily relies on the information from conflict diagnosis. Without precise conflict information, the effectiveness of combining algorithms for resolving policy conflicts cannot be guaranteed.
Another critical problem for XACML policy analysis is redundancy discovery and removal. A rule in an XACML policy is redundant if every access request that matches the rule also matches other rules with the same effect. As the response time of an access request largely depends on the number of rules to be parsed within a policy, redundancies in a policy may adversely affect the perfor-mance of policy evaluation. Therefore, policy redundancy is treated as policy anomaly as well. Redundancy elimination
2 BACKGROUND
2.1 Overview of XACML
XACML has become the de facto standard for describing access control policies and offers a large set of built-in functions, data types, combining algorithms, and standard profiles for defining application-specific features. At the root of all XACML policies is a policy or a policy set. A policy set is composed of a sequence of policies or other policy sets along with a policy combining algorithm and a target. A policy represents a single access control policy expressed through a target, a set of rules and a rule combining algorithm. The target defines a set of subjects, resources, and actions the policy or policy set applies to. A rule set is a sequence of rules. Each rule consists of a target, a condition, and an effect. The target of a rule determines whether an access request is applicable to the rule and it has a similar structure as the target of a policy or a policy set.
An XACML policy often has conflicting rules or policies, which are resolved by four different combining algorithms:
Deny-Overrides, Permit-Overrides, First-Applicable, and
Only-One-Applicable [25]. Fig. 1 shows an example XACML
policy. The root policy set PS1 contains two policies, P1 and P2, which are combined using First-Applicable combin-ing
algorithm. The policy P1 has three rules, r1, r2, and r3, and its rule combining algorithm is Deny-Overrides. The policy P2
includes two rules r4 and r 5 with Deny-Overrides combining algorithm. In this example, there are four subjects: Manager,
Designer, Developer, and Tester; two resources: Reports and
Codes; and two actions: Read and Change. Note that both r2 and r3 define conditions over the Time attribute.
2.2 Anomalies in XACML Policies
An XACML policy may contain both policy components and policy set components. Often, a rule anomaly occurs in a policy component, which consists of a sequence of rules. On the other hand, a policy set component consists of a set of policies or other policy sets; thus, anomalies may also arise among policies or policy sets. We address XACML policy anomalies at both policy level and policy set level:
. Anomalies at policy level. A rule is conflicting with other rules, if this rule overlaps with others but defines a
different effect. For example, the deny rule r1 is in
conflict with the permit rule r2 in Fig. 1 because rule r2 allows the access requests from a designer to change codes in the time interval [8:00, 17:00], which are
supposed to be denied by r1; and a rule is redundant if there is other same or more general rules available that have the same effect. For instance, if we change the effect
of r2 to Deny, r3
Manager and Developer. If we only examine pairwise redundancies, r3 is not a redundant rule. However, if we check multiple rules simultaneously, we can identify r3 is redundant
considering r2 and r5 together. We observe that precise anomaly diagnosis information is crucial for achieving an effective anomaly resolution. In this paper, we attempt to design a systematic approach and corre-sponding tool not only for accurate anomaly detection but also for effective anomaly resolution.
3 UNDERLYING DATA STRUCTURE
Our policy-based segmentation technique introduced in subsequent sections requires a well-formed representation of policies for performing a variety of set operations. BDD [9] is a data structure that has been widely used for formal verification and simplification of digital circuits. In this work, we leverage BDD as the underlying data structure to represent XACML policies and facilitate effective policy analysis.
Given an XACML policy, it can be parsed to identify subject, action, resource, and condition attributes. Once these attributes are identified, all XACML rules can be transformed into Boolean expressions [5]. Each Boolean expression of a rule is composed of atomic Boolean expressions combined by logical operators _ and ^. Atomic Boolean expressions are treated as equality constraints or range constraints on attributes (e.g., Subject ¼
“Designer”) or on conditions (e.g., 8:00 _ Time _ 17:00).
Example 1. Consider the example XACML policy in Fig. 1 in terms of atomic Boolean expressions. The Boolean
expression for rule r1 is
Subjectð¼ ‘‘Designer’’ _ Subject ¼ ‘‘Tester’’Þ
^ ðResource ¼ ‘‘Codes’’Þ ^ ðAction ¼ ‘‘Change’’Þ:
The Boolean expression for rule r2 is
ðSubject ¼ ‘‘Designer’’ _ Subject ¼ ‘‘Developer’’Þ
^ ðResource ¼ ‘‘Reports’’ _ Resource ¼ ‘‘Codes’’Þ
^ ðAction ¼ ‘‘Read’’ _ Action ¼ ‘‘Change’’Þ
^ ð8:00 _ Time _ 17:00Þ:
Boolean expressions for XACML rules may consist of atomic Boolean expressions with overlapping value ranges. In such cases, those atomic Boolean expressions are needed to be transformed into a sequence of new atomic Boolean expressions with disjoint value ranges. Agrawal et al. [1] have identified different categories of such atomic Boolean expressions and addressed corre-sponding solutions for those issues. We adopt similar approach to construct our Boolean expressions for XACML rules.
We encode each of the atomic Boolean expression as a Boolean variable. For example, an atomic Boolean expression
Subject ¼ “Designer” is encoded into a Boolean variable S1. A complete list of Boolean encoding for the example XACML policy in Fig. 1 is shown in Table 1. We then utilize the Boolean encoding to construct Boolean expressions in terms of Boolean variables for XACML rules.
4 CONFLICT DETECTION AND RESOLUTION
We first introduce a concept of authorization space, which adopts the aforementioned BDD-based policy representa-tion to perform policy anomaly analysis. This concept is defined as follows:
Definition 1 (Authorization space). Let Rx, Px, and PSx be the set of rules, policies, and policy sets, respectively, of an XACML policy x. An authorization space for an XACML policy component c 2 Rx [ Px
[ PSx represents a collection of all access requests1 Qc to which a policy component c is applicable.
4.1 Conflict Detection Approach
Our conflict detection mechanism examines conflicts at both policy level and policy set level for XACML policies. To precisely identify policy conflicts and facilitate an effective conflict resolution, we present a policy-based segmentation
to partition the entire authorization space of a policy into disjoint authorization space segments. Then, conflicting authorization space segments (called conflicting segment in the rest of this paper), which contain policy components with different effects, are identified. Each conflicting segment indicates a policy conflict.
4.1.1 Conflict Detection at Policy Level
A policy component in an XACML policy includes a set of rules. Each rule defines an authorization space with the effect of either permit or deny. We call an authorization space with the effect of permit permitted space and an authorization space with the effect of deny denied space.
Algorithm 1 shows the pseudocode of generating conflicting segments for a policy component P . An entire authorization space derived from a policy component is first partitioned into a set of disjoint segments. As shown in lines 17-33 in Algorithm 1, a function called Partition() accomplishes this procedure. This function works by adding an authorization space s derived from a rule r to an authorization space set S. A pair of authorization spaces must satisfy one of the following relations: subset (line 19), superset (line 24), partial match (line 27), or disjoint (line 32). Therefore, one can utilize set operations to separate the overlapped spaces into disjoint spaces.
Conflicting segments are identified as shown in lines 6-10 in Algorithm 1. A set of conflicting segments CS: fcs1; cs 2; . . . ; csng from conflicting rules has the following three properties:
1. All conflicting segments are pairwise disjoint: csi \
2. any two different requests q and q0 within a single conflicting segment (csi) are matched by exact same set
of rules: GetRuleðqÞ ¼ GetRuleðq0Þ;2 8q 2 csi; q0 2 csi; q 6¼ q0; and
3. the effects of matched rules in any conflicting segments contain both “Permit” and “Deny.”
To facilitate the correct interpretation of analysis results, a concise and intuitive representation method is necessary. For the purposes of brevity and understandability, we first employ a two-dimensional geometric representation for each authorization space segment. Note that a rule in an XACML policy typically has multiple fields; thus, a complete representation of authorization space should be multidimensional. Also, we utilize colored rectangles to denote two kinds of authorization spaces: permitted space (white color) and denied space (gray color), respectively. Fig. 3a gives a representation of the segments of authoriza-tion space
derived from the policy P1 in the XACML example policy shown in Fig. 1. We can notice that five unique disjoint segments
are generated. In particular, three conflicting segments cs1, cs2, and cs3 are identified, representing three policy conflicts.
4.2 Fine-Grained Conflict Resolution
Once conflicts within a policy component or policy set component are identified, a policy designer can choose appropriate conflict resolution strategies to resolve those identified conflicts. However, current XACML conflict resolution mechanisms have limitations in resolving con-flicts effectively. First, existing conflict resolution mechan-isms in XACML are too restrictive and only allow a policy designer to select one combining algorithm to resolve all identified conflicts within a policy or policy set component. A policy designer may want to adopt different combining algorithms to resolve different conflicts. Second, XACML offers four conflict resolution strategies. However, many conflict resolution strategies exist [14], [17] but cannot be specified in XACML. Thus, it is necessary to seek a comprehensive conflict resolution mechanism for more effective conflict resolution. Toward this end, we introduce a flexible and extensible conflict resolution framework to achieve a fine-grained conflict resolution as shown in Fig. 6.
4.2.1 Effect Constraint Generation from a Conflict Resolution Strategy
Our conflict resolution framework introduces an effect constraint that is assigned to each conflicting segment. An effect constraint for a conflicting segment defines a desired response (either permit or deny) that an XACML policy should take when any access request matches the conflict-ing segment. The effect constraint is derived from the conflict resolution strategy applied to the conflicting segment, using a similar process of determining the effect of a conflicting segment described in Section 4.1.2. A policy designer chooses an appropriate conflict resolution strategy for each identified conflict by examining the features of conflicting segment and associated conflicting components. In our conflict resolution framework, a policy designer is 4.2.2 Conflict Resolution Based on Effect Constraints
A key feature of adopting effect constraints in our framework is that other conflict resolution strategies assigned to resolve different conflicts by a policy designer can be automatically mapped to standard XACML combining algorithms, without changing the way that current XACML implementations perform. As illustrated in Fig. 6, an XACML combining algorithm can be derived for a target component by examining all effect constraints of the conflicting segments. If all effect constraints are “Permit,”
Permit-Overrides is selected for the target component to resolve all conflicts. In case all effect constraints are “Deny,” Deny-Overrides is assigned to the target compo-nent. Then, if the target component is a policy set and all effect constraints can be satisfied by applying Only-One-Applicable combining algorithm, Only-One-Applicable is selected as the combining algorithm of the target compo-nent. Otherwise, First-Applicable is selected as the combin-ing algorithm of the target component. To resolve all conflicts within the target component by applying First-Applicable, the process of reordering conflicting components is compulsory to enable that the first-applicable component in each conflicting segment has the same effect with corresponding effect constraint.
Fig. 7. Example of conflicting segment correlation.
introduce a correlation mechanism to identify dependent relationships among conflicting segments. The major ben-efit of identifying dependent relationships for a conflict resolution is to lessen the searching space of reordering conflicting components.
Fig. 7 shows an example for conflicting segment correlation, considering an XACML policy component P with eight rules. Five conflicting segments are identified in this example. Several rules in this XACML policy compo-nent are involved in multiple
conflicts. For example, r2 contributes to two policy conflicts corresponding to two conflicting segments cs1 and cs2, respectively. Also, r8 is associated with two conflicting segments cs2 and cs3. Suppose we want to satisfy the effect constraint of cs2 by reordering associated conflicting rules, r2, r5, and r8. The position change of r2 and r8 would affect conflicting segments, cs1 and cs2, respectively. Thus, a dependent relationship can be
derived among cs1 , cs2, and cs3 with respect to the conflict resolution. Similarly, we can identify the dependent relation
between cs4 and cs5. We organize those conflicting segments with a dependent relationship as a group called conflict correlation group. The pseudocode of an algorithm for identify conflict correlation groups is given in Algorithm 3.
5 REDUNDANCY DISCOVERY AND REMOVAL
Our redundancy discovery and removal mechanism also leverage the policy-based segmentation technique to ex-plore redundancies at both policy level and policy set level.
5.1 Redundancy Elimination at Policy Level
We employ following steps to identify and eliminate redundant rules at policy level.
5.1.1 Authorization Space Segmentation
We first perform the policy segmentation function Partition_P() defined in Algorithm 1 to divide the entire authorization space of a policy into disjoint segments. We classify the policy segments in following categories: nonoverlapping segment and overlapping seg-ment, which is further divided into conflicting overlapping segment and nonconflicting overlapping segment. Each nonoverlapping segment associates with one unique rule, and each overlapping segment is related to a set of rules, which may conflict with each other (conflicting overlapping segment) or have the same effect (nonconflicting overlapping segment). Fig. 8a illustrates a grid representation of authorization space segmentation for a policy with eight rules. In this example, one
policy segment s4 is a nonoverlapping segment. Other policy segments are over-lapping segments, including three conflicting
overlapping segments s1, s2, and s6, and two nonconflicting overlapping segments s3 and s5.
5.1.2 Irremovable Rule Identification Considering Multivalued Requests
An XACML request may be multivalued. For example, an
XACML request can be “a person, who is both a Developer and a Designer, wants to change reports,” where the subject has two values, Developer and Designer. A multivalued request may match several rules, which do not overlap with each other in terms of single-valued requests. For instance, the above
multivalued request matches both r4 and r5 in the example policy
shown in Fig. 1, although r4 and r5 have no overlapping relation considering single-valued requests. We observe that an XACML rule may be removable with respect to single-valued requests but irremovable taking into account multivalued requests. Therefore, we introduce a process to examine whether an XACML rule is irremovable considering multivalued requests based on the three cases of rule combining algorithm (CA):
1. CA ¼ First-Applicable. In this case, since a multi-valued request may match the examined rule and any subsequent rule(s) in the policy, if there is a subsequent rule with a different effect, the examined rule is considered irremovable.
5.1.4 Rule Correlation Break and Redundancy Removal
Rules covered by an overlapping segment are correlated with each other when the effect of the overlapping segment can be determined by any of those rules. Thus, keeping one correlated rule and removing others do not change the effect of the overlapping segment. In addition, some rules may get involved in
multiple correlated relations. For example, in Fig. 8b, r4 has two subspaces that are involved in the correlated relations with r2 and
r7, respectively. Therefore, similar to the construction of conflict correlation groups, we build rule correlation groups based on these two situations so that dependent relationships among multiple correlated rules within one group can be examined simultaneously. For example, a correlation group consisting of
three rules r2, r4, and r7 can be identified in Fig. 8b.
The goal of rule correlation break is to discover as many redundant rules as possible. Different sequences to break rule correlations may lead to different results for redun-dancy removal. For example, Fig. 9a shows correlated relations of rules
r2, r4, and r7, and we can break their correlated relations into different sequences. As shown in Fig. 9b, if we first choose r2 as an irremovable rule and assign r2 ’ subspace SI property, only r4 becomes an removable rule and r7 is turned to be irremovable. However, as shown in Fig. 9c, if we first choose r4 as an irremovable rule and assign two subspaces of r4 with SI
property, both r2 and r7 then become removable rules. To seek
an optimal solution for rule correlation break, we measure a breaking degree for each correlated rule r, denoted as BDðrÞ, which indicates the number of removable rules if choosing r as an irremovable
5.2 Redundancy Elimination at Policy Set Level
Similar to the solution of conflict detection at policy set level, we handle the redundancy removal for a policy set based on an XACML tree structure representation. If the children nodes of the policy set is a policy node in the tree, we perform RedundancyEliminate_P() function to eliminate redundancies. Otherwise, RedundancyElimi-nate_PS() function is excused recursively to eliminate redundancy in a policy set component.
After each component of a policy set PS performs redundancy removal, the authorization space of PS can be then partitioned into disjoint segments by performing Partition() function. Note that, in the solution for conflict detection at policy set level, we aggregate author-ization subspaces of each child node before performing space partition, because we only need to identify conflicts among children nodes to guide the selection of policy combining algorithms for the policy set. However, for redundancy removal at policy set level, both redundancies
6 IMPLEMENTATION AND EVALUATION
We have implemented a policy analysis tool called XAnalyzer in Java. Based on our policy anomaly analysis mechanism, it consists of four core components: segmenta-tion module, effect constraint generation module, strategy mapping module, and property assignment module. The segmentation module takes XACML policies as an input and identifies the authorization space segments by parti-tioning the authorization space into disjoint subspaces. XAnalyzer utilizes APIs provided by Sun XACML
7 RELATED WORK
Many research efforts have been devoted to modeling and verification of XACML policies [2], [8], [11]. In [8], the authors formalized XACML policies using a process algebra known as communicating sequential processes. This work utilizes a model checker to formally verify properties of policies and to compare access control policies with each other. Fisler et al. [11] introduced an approach to represent XACML policies with multiterminal BDDs. They developed a policy analysis tool called Margrave, which can verify XACML policies against the given properties and perform change-impact analysis. Ahn et al. [2] presented a for-malization of XACML using answer set programming (ASP), which is a recent form of declarative programming, and leveraged existing ASP reasoners to conduct policy verification. However, lacking an exhaustive elicitation of properties, the completeness of the analysis results of policy verification cannot be guaranteed. In contrast, our approach for policy anomaly analysis can indicate accurate anomaly information without the need of any external properties.
8 CONCLUSION
We have proposed an innovative mechanism that facilitates systematic detection and resolution of XACML policy anomalies. A policy-based segmentation mechanism and a grid-based representation technique were introduced to achieve the goals of effective and efficient anomaly analysis. In addition, we have described an implementation of a policy anomaly analysis tool called XAnalyzer. Our experimental results showed that a policy designer could easily discover and resolve anomalies in an XACML policy with the help of XAnalyzer. We believe our systematic mechanism and tool will significantly help policy managers support an assurable web application management service. As our future work, the coverage of our approach needs to be further extended with respect to obligations and user-defined functions in XACML. Moreover, we would explore how our anomaly analysis mechanism can be applied to other existing access control policy languages. In addition, we plan to conduct formal analysis [2], [12] of policy anomalies, particularly dealing with multivalued requests.