The popularity of REST grows more and more and so does the need for fine-grained access control for RESTful services. Attribute Based Access Control (ABAC) is a very generic concept that covers multiple different access control mechanism. XACML is an implementation of ABAC based on XML and is established as a standard mechanism. Its flexibility opens the opportunity to specify detailed security policies. But on the other hand it has some drawbacks regarding maintenance and performance when the complexity of security policies grows. Long processing times for authorization requests are the consequence in environments that require fine-grained access control. We describe how to design a security policy in a resource oriented environment so that its drawbacks are minimized. The results are faster processing times for access requests and an easy to manage concept for security policies for RESTful services.
request is permitted or denied. Policies group different rules together and policy
sets group different policies together. Policy sets may contain also other policy
sets enforcing a hierarchical composition. Each of these elements has a target
that describes if the element can be applied to a request by defining a condition.
A single access request may be applied to multiple policy sets, policies and rules.
In that case those rules may have different effects (Permit or Deny) and a
winning rule must be found (based on the structure of the policy). XACML uses
combining algorithms for that purpose. An example for a combining algorithm
is PermitOverrides. It states that an applicable rule with the effect Permit will
always win against a rule with the effect Deny. A full list of algorithms can be
found in [
Listing 1 shows a simplified version of a XACML policy. For simplification some required information like data types or matching methods (e.g. equals, greater than) are removed. The policy contains two rules and is applicable to a HTTP GET request on a resource /users/1/photos. The first rule grants access to a user identified by an URI /users/2 and the second rule prohibits access for any subject. As one can see fine-grained policies may easily become very complex and performance and maintenance need to be optimized. <P o l i c y CombAlg=" F i r s t A p p l i c a b l e "> <Target> <Resource d e s i g n a t o r ="URI" v a l u e ="/ u s e r s /1/ photos " /> <Action d e s i g n a t o r ="HTTP−method " v a l u e ="GET" /> </Target> <Rule E f f e c t ="Permit"> <Target>
<S u b j e c t d e s i g n a t o r ="URI" v a l u e ="/ u s e r s / 2 " /> </Target> </Rule> <Rule E f f e c t ="Deny"/> </P o l i c y > Listing 1. Simplified XACML granting GET access for one user to the photos of another user 2
XACML computes access decisions at runtime and must evaluate multiple
attributes of different categories to find a decision. Therefore the average
computation time for an access request increases with growing policy complexity. The
problem of computation at runtime is related to the architecture resp. the general
concept of XACML. A graph based approach described in [
A second major problem of XACML is the modification of policies. XACML
does not define how to handle changes to a security policy. The most common
way is manually inserting new policy sets, policies and rules supported by a
graphical user interface like in [
An efficient security policy design should enable fast request processing and should be easy to maintain. The security policy described in XACML is a unidirectional graph without cycles. To enable fast request processing we need to consider the costs of processing an access request in a single node of that graph. We define the cost function as:
c : N × Q → Q where N is the set of nodes in the security graph, Q is the set of possible access requests and Q is the set of rational numbers. The set of child nodes of a node k can be expressed as:
Sk := {s ∈ N | ∃p ∈ path(k, s) & length(p) = 1} Let αk be the combining algorithm of a node k and let A be the set of combining algorithms. Let be an effect within the set of effects E. Then one has: ∀αk ∈ A ∃ ∈ E : compute(si) = ⇒ αk stops; si ∈ Sk That means that for any given combining algorithm there are one or more effects that cause the algorithm to stop if one of its child nodes computes to one of these effects. For example a node may half two child nodes and the combining algorithm PermitOverrides. If the first child node computes to Permit the effect of the node will also be Permit no matter what the result of the second child node may be. Therefore the combining algorithm stops and should not process the second child node. We define a function γ that describes this behavior: γk(q, si) = (1 if ∀s ∈ {s1, ..., si−1} : αk does not stop
0 if ∃s ∈ {s1, ..., si−1} : αk does stop With q ∈ Q and i ∈ {1, ..., | Sk |}. The cost function c then can be expressed as: |Sk| ck(q) = tk(q) + X γk(q, si) ∗ csi (q)
i=1 The function tk(q) describes if a target matches the request q. Therefore it is mainly dependent on how many attributes are specified in the target. Hence, the costs for processing a node depends on the number of attributes in the target, the sum of child nodes and the combining algorithm resp. the order of the children. The following sections describe how to minimize the costs of processing access requests and decrease maintenance efforts for each of the listed factors. 3.1
Target design (minimize tk) Attributes should be added carefully to targets to keep the target small and thus reduce the number of comparisons needed to be executed in the worst case. For example a security policy may contain two conditions. Each condition specifies a subject attr. (URI = /users/userid) and a resource attr. (URI = /users/userid/photos). An intuitive way would be handling each condition in a single target of a rule as indicated in Fig. 1. (a). Processing a request with a subject attr. (URI = /users/2) and a resource attr. (URI = /users/3/photos) requires four attribute comparisons in the worst case because XACML does not specify an order in which attributes must be checked. If a single condition is splitted into multiple targets of rules, policies and policy sets as indicated in Fig. 1. (b) a max of three comparisons is required. This optimization has a benefit for targets that are not applicable to a request while the cost for an applicable rule remains unchanged. Variations in processing times are reduced to a minimum. The maintenance benefit is that it becomes easier to add new conditions that affect a subject with attr. (URI = /users/userid) but not a resource with attr. (URI = /users/userid/photos).
(a) Max. of 4 comparisons (b) Max. of 3 comparisons
Number of sub nodes (minimize P|iS=k1| csi ) It is obvious that the overall processing time for few nodes is less than the overall processing time for many nodes. Hence, wherever possible targets should be grouped together. That means an efficient policy design must have its branching points at the lowest possible position. Besides the performance gain maintenance efforts for the resource with attr. (URI = /users/1/photos) are reduced because it does not occur twice (cp. Fig. 2.).
(a) Upper branching point
(b) Lower branching point
The selection of the combining algorithm and the child node order also has an
effect on performance. Processing those rules first that override the effects of
others leads to shorter average processing times. If an overriding rule matches, no
other rule needs to be checked. And if no overriding rule matches, the combining
algorithm can stop after the first match of the non-overriding rules because
they cannot be overridden. This is the basic idea of normalization [
One core concept of REST is resource orientation [
Another important concept of REST is an uniform interface. Therefore we consider that the set of allowed methods is limited to the HTTP methods. We use these methods as possible actions in a security policy. For each action a new policy should be used right under the policy set for the requested resource. Within these policies rules may be specified that describe under which circumstances the resource may be accessed.
Figure 4 shows an efficient security policy for a RESTful application that follows the optimizations described in the previous sections. We performed some first, simple and fragmentary tests on different security policies designed to protect a RESTful service. A first set of policies contains 10 conditions on the URI attribute of 10 resources. For each of the main HTTP methods (GET, POST, PUT, DELETE) we assigned a single policy with one rule, resulting in 40 rules per policy. A second and third set have 100 resp. 1000 more resources resulting in 440 resp. 4440 rules per policy. Each set contains 4 policies: a non-optimized policy (flat structure with a lot of rules in the same policy that follows the pattern of Fig. 1 (a)), a normalized policy with the optimizations described in section 3.3, a structure optimized policy containing the optimizations described in section 3.1 and section 3.2 and finally a policy with all of the optimizations described in section 3 that follows the guideline described in section 4. All policies within a single set are functionally equivalent. We used Balana as XACML engine (https://github.com/wso2/balana). The measurement was executed on a dual core system (Intel i7-3250M, 2,90GHz) with 8GB working memory reserved for the tests. Each test was executed 20 times.
Figure 5 shows the average processing time for an access request. As one can see the processing times for the set with the smallest policies only differ insignificantly. But with growing policy complexity the difference becomes considerably. While the average processing time for the optimized policy remains approximately constant at about 15ms, the average processing time for the non-optimized policies increases up to 304ms. The main contribution to the performance benefit of the optimized policy is delivered by the structure changes as indicated by Fig. 5. Normalization only has a significant impact for larger policies with many rules and without an optimized structure and causes great variations in processing time of up to 200% of the average processing time. The optimized, structure optimized and non-optimized policies have a variation in processing time of about 25%.
300 ) 200 s m ( t 100 0 102
103 number of rules
Norm. XACML
Opt. Struct. XACML With every target on a path to a rule access conditions become more restrictive in XACML. This can be a problem for RESTful services. We may have a resource user list http://example.org/users and access to this resource is granted only to some administrators but not to single users. But a resource http://example.org/users/1 may be accessed by administrators and user 1. Since user 1 is a sub resource of the user list, the policy or policy set that handles access to this sub resource should be placed below the policy set that handles access to the user list. In XACML you cannot extend a condition at sub policy level. In consequence the same condition must be repeated multiple times which causes the policy complexity to grow unnecessarily and increases the maintenance efforts.
To handle the maintenance, performance and restriction problems described in the previous sections, we are developing an alternative language similar to XACML. The language targets RESTful services and should guarantuee that only optimized security policies can be written. A draft version already exists and a prototype is implemented. First results show slightly improved performance even to optimized XACML policies. We want to address the maintenance problems with a structured query language that makes it easy to handle changes in a resource oriented context.