Abstract: In this study, we propose the redundancy and inconsistency checking algorithms to support the policy management of systems employing role based access control model. Present method is based on the formal definition of the policy redundancy and policy inconsistency. Via constructing the role graph, we analyze the redundancy and inconsistency one by one. According to the features of each type of redundancy and inconsistency, present algorithm checks all the possible violations and generates the related policy elements to help the security administrator to amend the policy afterwards. The performance test demonstrates that the approach is efficient enough for practical usage. Present approach could guarantee the conciseness as well as consistency of the access control policy, at same time reduce the burden of access control administration significantly.
INTRODUCTION
The prominent progress of Internet and related technologies has promoted tremendous information and data sharing. There is a growing concern for security and privacy of data and numerous studies have shown that unauthorized access can cause great losses, especially for the financial software (Ferraiolo et al., 2003; Schaad et al., 2001). Access control becomes more and more essential for safe and secure access to the software and hardware resources. Role Base Access Control (RBAC) model, which was proposed by Ferriaiolo and Sandhu (2001) at the 90s of last century, provides a powerful way to satisfy the access control needs (Li and Tripunitara, 2006). RBAC96 is currently the most widely used access control model in enterprise area since its fine grained control over the privilege (Ferraiolo et al., 2001; Li and Mao, 2007). Furthermore, RBAC is capable of modeling a wide range of access control policies including Discretional Access Control (DAC) and Mandatory Access Control (MAC). An access control policy is a statement which specifies the rules about how to setup the process for grating or denying authorizations to the users (Coyne, 1996; Beznosov and Deng, 1999). The access control redundancy means there are unwanted specifications about the same access rule and the access control inconsistency means there are access control rules conflicting with each other in the policy, for example rule A claims that granting role R to user Bob, however rule B claims that denying the request of assigning R to Bob, when the above access control rules coexist in one policy, the access control policy inconsistency occurs, which may conceal the security danger or even breakdown the entire access control system (Schaad et al., 2001; Nyanchama and Osborn, 1999). Thus, it is extremely important to make sure that there is no inconsistency of an access control policy. For the access control system employing RBAC model, it is much more complicated for the policy inconsistency management, since RBAC supports more advanced constraints.
Centonze et al. (2006) present a theoretical foundation for correlating an operation-based RBAC policy with a data-based RBAC policy via., a location consistency property. The research shows how to infer whether an operation-based RBAC policy is equivalent to any database RBAC policy and a static analysis tool called SAVES is introduced to facilitate the consistency validation. However, the inconsistencies concerning role hierarchies and cardinality constraints are not discussed. Chang and Hoh (2005) discussed the inconsistency detection in distributed component environment. Via analyzing the server-centric RBAC system, they proposed an inconsistency detection method between two access control policies and also investigated the conditions of guaranteeing consistency. However, there is no the discussion of the inconsistency in each individual distributed system, which is actually the pre-condition of the consistency in the entire distributed system. Strembeck (2004) presents the experiences with the implementation of conflict-checking methods for separation of duty constraints in the XORBAC access control service and only provides a concise method to check the separation of duty conflicts, which is obviously not sufficient to make sure the consistency of system. All of the above work addressed little on the policy redundancy, which is obviously not safe and efficient enough for the policy management.
The redundancy and inconsistency management need a systematic way (Li et al., 2007). In this study, pointing to the problems listed above we take all of the elements of a RBAC policy including role hierarchies, separation of duty constraints and cardinality constraints into consideration and present the formal definition of the policy redundancy and inconsistency. We also show the algorithm to check the redundancy and inconsistency of RBAC access control policy which is based on the Tarjan’s SCC algorithm (Tarjan, 1972). Compared to the methods by Chang and Hoh (2005) and Strembeck (2004), present will provide much more confidence for the consistency in RBAC policy.
The purpose of this study is to develop a comprehensive algorithm to check the policy redundancy and inconsistency to support the management of RBAC policy. The algorithm should take all the policy constraints into account and due to the frequent policy checking in daily management, the algorithm should be efficient enough for practical application.
BACKGROUND
RBAC is widely used for the specification of security requirement of most commercial applications (Yao et al., 2001; Park et al., 2001; Essmayr et al., 2004). RBAC96 model currently being used consists of the following four basic components: a set of users, a set of roles, a set of permissions and a set of sessions. A user is a human being or a process within a system. A role is a collection of permissions associated with a certain job function. Permission defines the access rights that can be exercised on a particular object in a system. A session relates a user to several roles. The whole picture of RBAC96 model is as shown in Fig. 1.
Definition 1
RBAC policy: An RBAC policy is a 7-tuple (U, R, P, RH, RP, UR, C):
| • | U, R, P are respectively, finite sets of users, roles and permissions, where, P is defined as P = 2OperationsxObjects |
| • | RH: Role hierarchy is a partial order relation defined on role
sets, RH ⊆(RxR), if (r1, r2)εRH, r1
is a senior role whereas r2 is junior role and r1
inherits all the permissions of r2. The relation can also be
expressed as: r1 |
| • | RP: Role-permission is a relation defined on role set and permission set, RP⊆(RxP) |
| • | UR: User-pole is a relation defined on the user set and role set, UR ⊆(UxR) |
| • | C: The constraint set defined on the above entity and relation sets, including the separation of duty and cardinality constraint |
| Fig. 1: | RBAC96 model |
RBAC global functions:
| • | senior: R →2R, mapping each role to a set of roles, which are senior to the role |
| • | role_u: R →2U, mapping each role to a set of users who own the role, including the ones who own the role via., role hierarchy |
| • | role_p: R →2P, mapping each role to a set of permissions which are assigned to the role, including the ones which are inherited from senior roles |
| • | user_p: U →2P, mapping each user to a set of permissions which are owned by the user |
| • | user_r: U →2R, mapping each user to a set of roles which are assigned to the user |
| • | pms_u: P →2U, mapping each permission to a set of users who owns the permission |
| • | pms_r: P →2R, mapping each permission to a set of roles, which have been assigned the permissions |
Separation of Duty (SOD) is a fundamental technique to prevent fraud and errors, known and practiced long before even the existence of computers. SOD reduces the possibility of fraud or significant errors which may cause damage to an organization. By partitioning the tasks and the associated privileges, the accomplishment of a sensitive task requires the cooperation of multiple users imperatively. SOD constraint is not only the most important constraint in RBAC policy but also the most complicated part which causes the management of RBAC policy more difficult. There are three kinds of separation of duty in RBAC, permission separation SOD-P, role separation SOD-R and user separation SOD-U.
Definition 2
Separation of duty:
| • | SOD-P: SOD-P is the finest grained control of separation of duty, which specifies the exclusive set of permission |
SOD-P⊆2PxN, which satisfies the following conditions:
If n = 1, we can use (p1, p6) εSOD-P for simplicity.
| • | SOD-R: SOD-R is the constraint over the role set, which specifies the user could not be assigned the exclusive roles in the meanwhile |
SOD-R⊆2RxN, which satisfies the following: ≥2, ∀(rs, n) ε SOD-R
The simplified expression can be written as (r1, r2)εSOD-R, when n = 1
| • | SOD-U: SOD-U is the third form of separation of duty, which specifies that only one of the two users could be assigned the certain role. SOD-U⊆2UxR, which satisfies the following conditions: |
Besides the above SOD constraints, Cardinality Constraint (CC) is also one of the most important constraints in RBAC. Cardinality constraint regulates that at the given time, there is only one can be assigned as the certain role. For example in a company, at any time, there should be only one employee can be assigned as the general manager, otherwise there must be confusion of the management.
Definition 3
Cardinality Constraint (CC):
| • | CC-P: CC-P constraint specifies the restriction that the certain permissions which can be assigned to role only once. CC-P⊆P, which satisfies the following condition: |
| • | CC-R: CC-R constraints specifies the restriction that the specified role can only be assigned to one user. CC-R⊆R, which satisfies the following condition: |
POLICY MANAGEMENT
The major problems encountered in the management of RBAC policy are redundancy and inconsistency. Redundancy means there are unwanted specifications to describe the control rules and inconsistency means there are conflicting rules for the access control.
Take following policy pl for example:
pl = (U, R, P, RH, UR, C) |
| Where | ||
| U | = | {u1, u2} |
| R | = | {r1, r2, r3, r4, r5, r6, r7} |
| p | = | {p1, p2, p3, p4, p5, p6} |
| RH | = | {(r1, r2), (r2, r3), (r1, r3), (r5, r6), (r6, r4), (r4, r5), (r7, r3), (r7, r4)} |
| RP | = | {(r3, p1), (r3, p2), (r4, p6)} |
| UR | = | {(u1, r1), (u2, r5)} |
| SOD-P | = | {{p2, p4}} |
| SOD-R | = | {{r3, r4}} |
| SOD-U | = | {({u1, u2},r5)}, CC-R(r5) |
There are several redundancies and inconsistencies in the above RBAC policy.
Depicting the policy pl in the Fig. 2, the redundancy of the
role hierarchies among r1, r2 and r3 is obvious,
since the hierarchy relation of r1
| Fig. 2: | Example RBAC policy |
For the hierarchy relations among r4, r5 and r6, it is obvious that there should be no cycle in the role graph as hierarchy is a kind of partial order relation.
Boolean matrix for relations: The above policy example demonstrates that the management of RBAC policy is fundamental and challenging. Boolean matrix is a good way to express the relations among the users, roles and permissions.
Definition 4
Multiplication of Boolean matrix: Boolean matrix multiplication between
Boolean matrices Aε{0, 1}lxm and Bε{0, 1}mxn
and A
Definition 5
MRH, MUR, MRP and MUP: MRH, MUR, MRP and MUP are the matrices to
represent the RH, UR, RP and user-permission relation in the policy. Setting
l = |U|, m = |R|, n = |P|
| • | MRH: An mxm Boolean matrix, satisfying: |
| • | MUR+: The transitive closure of MRH, representing the complete hierarchy relations on role set |
| • | MUR: An lxm Boolean matrix, satisfying: |
| • | MUR+: An lxm Boolean matrix, satisfying: |
MUR+ = MRU |
| • | MRP: An mxn Boolean matrix, satisfying: |
| • | MRP+: An mxn Boolean matrix, satisfying: |
MRP+ = MRH+ |
which indicate the whole role and permission relation
| • | MUP: lxn Boolean matrix, representing the relations between users and permissions, satisfying: |
MUP = MUR |
RBAC policy redundancy: Redundancy means there are unwanted specifications to describe the control rules, following lists the types of the redundancy:
| • | Redundancy between role hierarchies |
For ri
then ri
The proof is simple, since
| • | Redundancy between SOD-P and SOD-R |
For sod-r(r1, r2) ε SOD-R,
if ∃sod-p(p1, p2)εSOD-P, satisfying:
then sod-r(r1, r2) is redundant. Figure 3b shows this type of redundancy.
| • | Redundancy between SOD-U and CC-R |
For sod-u({u1, u2}, r)εSOD-U, if ∃cc-r(r), εCC-R, then sod-u({u1, u2},r) is redundant. Figure 3c shows this type of redundancy
Following is the algorithm to check the redundancies:
Algorithm 1: RBAC policy redundancy checking
Input: Policy pl = (U, R, P, RH, UR, C)
Output: Return false indicating there is no redundancy in the policy,
otherwise return true indicating redundancy exists.
| Fig. 3a-c: | RBAC policy redundancy |
| • | For policy pl, construct the relation matrices, MRH, MUR, MRP and MUP and assuming the redundant set is RSet←Φ |
| • | Retrieve next unchecked rh = (r1, r2) from RH, set MRH(r1, r2)←0, then using the Warshall algorithm compute the transitive closure of MRH, which is MRH+ |
| • | If MRH+(r1, r2) = 1, then (r1, r2) is a redundant role hierarchy relation, add (r1, r2) to the redundant set RSet, mark it as role hierarchy redundancy |
| • | If MRH+(r1, r2) = 0, then (r1, r2) is not redundant, reset MRH (r1, r2)←1 and continue step 2 until all the role hierarchy relation are checked |
| • | Retrieve next unchecked sod-r(r1, r2), for each sod-p(p1, p2), if MRP+(r1, p1) = 1, MRP+(r2, p2) = 1 or =1 or MRP+ (r1, p2) = 1 and MRP+(r2, p1) = 1, then sod-r(r1, r2) is redundant, add it to the redundant set and mark it as SOD-R and SOD-P redundancy. Continue step 5 until all the sod-r constraints are checked |
| • | For each sod-u({u1, u2}, r), if cc-r(r) = 1, then sod-u({u1, u2}, r) is redundant, add it to the redundant set |
| • | If redundant set is empty, return false, otherwise return true |
For redundancy checking, the redundancy between SOD-P and SOD-R and the redundancy of SOD-U and CC-R are easy to do, which can be accomplished according to the corresponding relation matrix, via., verifying whether the unwanted condition is true. The redundancy among the role hierarchy is more complicated than the former two, since it involves the transitive relation among roles, which cause the computation more time-consuming.
We utilize the Warshall algorithm (Floyd, 1962) to computer the research-ability between two role nodes in the policy graph. The time complexity is:
m is the role number in the policy.
The efficiency can be improved via., using DFS (Depth First Search) based reach-ability algorithm, which can reduce the time complexity to:
O(m2 + mn) |
where, n is the role hierarchy relation edge in the role policy graph. In practice, usually, n<<m2, so DFS based reach-ability algorithm offers an advantage here.
| Fig. 4a-f: | RBAC policy inconsistency |
RBAC policy inconsistencies: A security and safe access control policy should give the indicated responses of an access request. Any confusion or uncertainty may conceal the security danger or even breakdown the entire system. Inconsistency is the major cause of the uncertainty. RBAC policy is more complicated than DAC and MAC, since RBAC supports role hierarchy relation and more advanced constraints which facilitate the fine grained control. Figure 4 shows the inconsistencies in an RBAC policy:
| • | Inconsistency between role hierarchies For r1, r2, r3εR, if r1ε senior(r2)∧r2 ε senior (r3) ∧ r3 ε senior(r1). Then there is inconsistency of the role hierarchies among r1, r2 and r3. In Fig. 4a, r1 is senior to r2, r2 is senior to r3 and r3 is senior to r1, which makes all of the three roles involve the conflicts, since the junior should not get the permissions of the senior roles |
| • | Inconsistency between RH and SOD-R For r1, r2, r3εR and sod-r(r2, r3), if r1 ε senior(r2)∧r1εsenior(r3) |
Then there is inconsistency between the role hierarchy and SOD-R constraint. In Fig. 4b, r1 is senior to role ri and rj, which are restricted by the SOD-R constraint. This inconsistency will expose the system under the danger, since any user who is assigned the role r1 can do the operations of ri and rj at the same time which is supposed to be prohibited.
| • | Inconsistency between RP and SOD-P |
| For r1εR and p1, p2εP, sod-p(p1,
p2) if p1εrole_p(r1)∧p2ε role_p(r1) |
Then there is inconsistency between the role-permission assignment and the SOD-P constraint. In Fig. 4c, role r1 gains the mutual exclusive permissions via., the role hierarchy, which may cause the security danger similar to the 1 in 2.
| • | Inconsistency between UR and SOD-R |
| For uεU, r1, r2εR and sod-r(r1, r2) if r1ε user_r(u)∧r2εuser_r(u) |
Then there is inconsistency between the user-role assignment and the SOD-R constraint. In Fig. 4d user u1 is assigned with role r1 and r2, which are involved in the SOD-R relation via., role hierarchy from ri and rj. Thus, u1 gains the exclusive permissions which is not allowed.
| • | Inconsistency between UR and CD-R |
| For rεR and cc-r(r) if ›u1, u2εU, u1 ≠ u2 and rεrole_u(u1)∧rεrole_u(u2) |
Then there is inconsistency between user-role assignment and the cardinality constraint. In Fig. 4e, user u1 and u2 are assigned with role r1, which has the cardinality constraint or inherits the cardinality constraint via., role hierarchy from role ri, which cause the inconsistency.
| • | Inconsistency between RP and CD-P |
| For pεP and cc-p(p) if ›r1, r2 ε R, r1 ≠ r2 and p ε role_p(r1)∧p ε role_p(r2) |
Then there is inconsistency between role-permission assignment and CD-P constraint. In Fig. 4f , role r1 and r2 are assigned with the same permission p, which is restricted by the cardinality constraint. Such kind inconsistency will turn the system into complete confusion.
The above inconsistency definitions are the basic forms. Since, role hierarchy relation is transitive and other RBAC relations are transitive-kind relations, like the UP can be delivered via., UR and RP, there are more complicated inconsistencies which can be composed of the above basic forms.
Based on the analysis of RBAC policy inconsistency, the inconsistency checking algorithm is given as following:
Algorithm 2: RBAC policy inconsistency checking
Input: Policy pl = (U, R, P, RH, UR, C)
Output: Return false indicating there is no inconsistency; otherwise
return true indicating inconsistency exists.
| • | Construct role graph RG = (V, E), where, V = R and E = RH and set the inconsistency set ISet←Φ |
| • | Find the Strong Connected Components (SCC) in RG via Tarjan’s SCC algorithm, if the output is empty set then there is no role hierarchy inconsistency, otherwise, there are inconsistencies among the role hierarchy and the output set contains the roles which cause the inconsistency |
| • | Retrieve next unchecked sod-p(p1, p2), for each rεR, if MRH+(r, r1) and MRH+(r, r2) = 1, then there is inconsistency of r, r1, r2 and sod-r constraints, add them to the ISet. Continue step 3 until all the sod-r constraints are checked |
| • | Retrieve next unchecked sod-p(p1, p2) from the policy, for each rεR, if MRP+(r, p1) = 1 and MRP+(r, p2) = 1, then add r and sod-p(p1, p2) to the inconsistency set. Continue step 4 until all the sod-p constraints are checked |
| • | Find the next unchecked sod-r(r1, r2), for each uεU, if MUR+(u, r1) = MUR+ (u, r2) 1, then sod-r(r1, r2) and u cause the inconsistency, add them to the ISet. Continue this step until all the sod-r constraints are checked. |
| • | For each cc-r(r), if |
| (l is the user number), then there is inconsistency, add the user set {uεU|MUR(u, r) = 1} and cc-r(r) to the ISet | |
| • | For each cc-p(p), if |
| then there is inconsistency, add the role set {rεR|MRP(r, p) = 1} and cc-p(p) to the ISet |
| • | If ISet is empty, return false, else return true |
After calculate the relation matrix MRH, MRH+, MUR, MRP, it is easy to check the inconsistencies via., the algorithm except the role hierarchy inconsistency.
The essential reason of the role hierarchy inconsistency is that there are strongly connected roles (i.e., role cycle) in the role graph. Tarjan’s SCC algorithm is based on DFS, which can be used for the role hierarchy inconsistency checking. It begins from a starting role and the roles involved in a cycle will form a sub-tree of the whole DFS search tree and the root of the sub-tree is the root of the strongly connected roles.
The time complexity of Tarjan’s SCC algorithm is:
O(m+k) |
where, m = |R| and k = |RH|, so the complexity of inconsistency checking can be calculated as following:
O(m+k)+O(m*C1)+O(m*C2)+O(l*C1)+O(C3+C4) |
where in n=|P|, l=|U|, C1=|SOD-R|<m2, C2=|SOD-P|<mn, C3=|CC-R|<m and C4=|CC-P|<n and since m<<l and n<<l so the time complexity is: O(lm2).
Although, we separate the steps to check the inconsistency for clarity, the steps can be combined to improve efficiency.
RESULTS AND DISCUSSION
The purpose of the experimental evaluation is two fold. First, we would like to validate that present algorithm works in a wide variety of environments ranging from small to large organization, with a few to a large number of roles and comprising of complex role hierarchy. Secondly, we would like to examine the performance of present approach with complex access control constraints. However, it is hard to find the real data of complex access control constraints that we would like to evaluate. Therefore, we created a test data generator that would allow us to verify the effectiveness of this algorithm under various conditions.
The test data generator performs as follows: first a set of roles are created, the number of which is set to a certain maximum number and the hierarchy relationships are constructed randomly under a certain ratio. Next for each role a random number of permissions are chose to form the role. Next the constraints among roles and permissions are generated randomly. Finally, the redundancy and inconsistency are generated according to the specified amount the generating algorithm is shown in Fig. 5. It is obvious that the generator uses a simple randomization strategy in order to generate the test data. This allows us to test in a completely unbiased manner with several different situations.
The input parameters of the test data generator algorithm are as follows:
| NR | = | No. of roles |
| NRH | = | No. of role hierarchies |
| NU | = | No. of users |
| NRd | = | No. of redundancies |
| NI | = | No. of inconsistency |
The experimental data is collected under the following test environment:
| • | CPU: Intel Core 2 T7500 @ 2.20 GH |
| • | Memory: 2.00 GB |
| • | OS: Windows XP, SP4 |
| • | Program language: Java |
| • | JRE Version: 1.6.0_02 |
Table 1 shows the CPU time records of the redundancy checking method based on Warshall algorithm and DFS algorithm, in the table the column head RNum is row number and role hierarchy ratio is defined as:
According to the data in Table 1, we can get the conclusion that the Warshall based redundancy checking algorithm is much more sensitive to the role number. Obviously, the DSF based redundancy checking algorithm offers the significant performance advantage and DSF based method is actually the one we choose in our real application.
Table 2 shows the CPU time records of the inconsistency checking algorithm, as the role hierarchy ratio increases, the CPU time which is taken to perform inconsistency checking also increase. This makes sense since more hierarchies involved in the checking algorithm indicates that there are more edges in the role graph which makes the graph traverse more time consuming.
| Table 1: | CPU time records of redundancy checking based on Warshall algorithm and DSF |
| Fig. 5: | Test data generator |
| Table 2: | CPU time records of inconsistency checking |
Compared to the methods by Chang and Hoh (2005) and Strembeck (2004), present approach is different in several ways: Firstly,present approach takes all the RBAC constraints into consideration, including three types of separation of duty and two types of cardinality constraints. Constrains, which provide the advanced manipulation of the access control policy, are the most important feature of RBAC model. Thus, the policy management methods with no support for the constraints are of no practical use. Present approach is the first attempt to take all the RBAC constraints, which makes this approach the one which could provide the maximum management confidence. Secondly, the access control policy management is the daily basic work of security administrator, thus the policy checking algorithm should be efficient enough due to frequent calls. From the above experimental evaluation, we can see that for an access system with role number up to 1000, present approach still maintain a high performance. According to present experience and the case study (Ferraiolo et al., 2003), the role number of enterprise system is much less than 1000, so the method is efficient enough for practical usage. Another advantage of present approach is that we reduce the redundancy and inconsistency to the graph problems, for which there have been a lot of existing well-known algorithms. Another point worth mentioning is the role hierarchy ratio, which is a kind of description of the complexity of the hierarchy relations. Similar to the concepts in graph theory, it could be considered as the graph complexity. Since, the role graph is a diagraph and in most circumstances is acyclic diagraph, the ratio of the number of edges and the number of vertexes will be relatively small. According to the experience, the role hierarchy ratio is usually less than 0.2, in such kind of situation, our approach demonstrates excellent performance. Although, the above work has not discussed the dynamic constraints, there is no significant difference compared to the static constraints except the checking happens at runtime, which requires the algorithm should be much more efficient and our approach can be extended easily to provide such kind of support.
CONCLUSIONS
In this study, we analyze the redundancy and inconsistency in role based access control policy. We give the formal definitions for each type of policy redundancy and inconsistency. Based on the analysis, the algorithms are given to check both redundancy and inconsistency. The redundancy checking algorithm is based on Warshall and depth first search algorithm and the redundancy can be identified via., detecting whether there is the redundant path in the role graph. The inconsistency checking algorithm is based on Tarjan’s SCC algorithm and the inconsistency can be identified via checking whether the role cycle exists. Compared to the others similar studies, present methods covers all the elements of RBAC policy and the checking algorithm is efficient enough for the practical usage, which could guarantee the conciseness and consistency of the RBAC policy and prevent the system from concealing security danger. The future study includes the study of redundancy and inconsistency resolution. And the severity of different inconsistencies and the automated method of inconsistency resolution will be the focus of the future research.