An analysis of graphs that represent a role-based security policy hierarchy

Abstract

The present work considers structural modification of the role hierarchy in a formal model of the role-based access control. The marked directed graph (the role graph), graphically representing an ordered set of roles, was analyzed to define the ordering relation in the role set and to distribute permissions according to the generated hierarchy. We constructed algorithms of the role graph’s transformations using different criteria of optimality and proved correctness of these algorithms. In the process, such characteristics as principles of permission distribution in the system, presence of role duplicates, the role graph’s peculiarities, e.g. how tree-like the graph is, were considered. The main result of the work is proof of possibility of constructing several role graphs corresponding to the same RBAC model. Thus, on the basis of relevant criteria, one can transform the role graph to make analysis and modification of a given RBAC model more effective.

Keywords

Role-based access control permission distribution equivalence classes of roles role hierarchy

1. Introduction

Role-based access control (RBAC) has been widely used for protection of computer systems in recent years. RBAC is most commonly used in different database management systems [1,2,33]. It is less common in operating systems [18,21,31]. The role-based security policy is based on mapping permissions onto actions in computer systems [23]. Using the RBAC is reasonable for implementing role permission inheritance mechanisms. In the absence of inheritance the role-based access control becomes not very different from the discretionary access control (DAC). Inheritance is implemented via authorizing one role for some other. In this case, the authorized role is said to dominate over the role it is authorized for [23]. Role dominance can be represented as a partial order, that is why a role set is partially ordered. The ordering relation in a role set can be graphically represented as a role graph [23].

The mathematical model of the role-based security policy was developed in several works [6,7,28,29]. So there is such a term as a family of role-based policy models. Model RBAC₀ is a basic model with minimal system requirements that supports role-based access control. RBAC₁ adds to RBAC₀ the concept of role hierarchies, and RBAC₂ includes RBAC₀ requirements along with different model component restrictions. For example, the users are not permitted to be assigned with two mutually exclusive roles or there are roles with a limited number of owners. The concept of prerequisite roles or permissions also imposes some restrictions. Models RBAC₁ and RBAC₂ are incomparable to one another. The consolidated model, RBAC₃, includes both RBAC₁ and RBAC₂ and, by transitivity, RBAC₀. In addition to common roles, a system may also have administrative roles. Administrative roles can be used to describe systems with alterable protection [19].

Most works analyzing role hierarchies within the RBAC model are focused on the algorithms that either build a role graph or modify it by adding or removing roles. The paper [15] considers a visual graph-based representation of a security policy that opens new perspectives for computer system security examination. The work in [12] proves possibility of building a graph representation of a security system based on semantic rules if certain conditions are fulfilled. The proposed method is applied for DAC and RBAC analysis. The methods for constructing graphs on the basis of information about the roles and their relationships in a system are considered in [11,13]. The methodology for constructing role graphs for UNIX-based operating systems and relational databases is presented in [24]. The role graph transformations connected with role insertions as well as the “role–role” and “privilege–privilege” conflict avoiding algorithms are presented in [20]. The issues of role graph integration during integration of computer systems are considered in [22]. Possibility of combining role-based and mandatory access control using graphs to ensure confidentiality is considered in [36].

In the majority of computer systems, role hierarchy optimality is taken into account only at the moment of designing. Further system evolution introduces new roles created rather spontaneously and, as a result, the role relationships become tangled and duplicate roles appear. Role graphs often have a too complex structure in real systems, while a tree remains the simplest form for analysis. This article is focused on examination of the role graph’s transformations that preserve role connections, but result in a graph convenient for analyzing how permissions are distributed between the roles. The final goal is to find an equivalent graph that corresponds to the given RBAC model and allows to reveal role duplicates and to consider distributing permissions in an optimal way.

2. Related works

The problems of RBAC analysis based on a role graph as well as transforming the role graph itself for access control policy optimization were examined in a number of works. It should be noted, though, that the role graph optimality criteria are still a subject for discussion.

The graphical role hierarchy representation and the RBAC analysis based on it are presented in [34]. In this work the authors propose a sequential graphical formalism allowing us to consider the role hierarchy and the constraints applied to the roles. The suggested formalism makes it possible to detect constraint violations while configuring the roles and their hierarchy.

The issues of role graph transformations in terms of role administration are considered in [17]. The authors define three principles of role hierarchy optimization: flexibility and scalability, psychological acceptability and economy of mechanism. They also identify six main types of the role hierarchy. The designed methods are used to analyze models ARBAC97 [25–27] and SARBAC [4,5].

The graph-based formalization of RBAC is presented in [13]. The authors use the graphical specification technique based on generalization of classical string grammars to non-linear structures. This formalization is a basis for an intuitive description providing a way to manipulate the graph’s structures. The suggested approach allows us to optimize role administration.

Graph theory analysis was applied to RBAC in [35] to provide system security. The method proposed there is remarkable for using optimal data structures.

The construction and optimization of role hierarchies for spatial roles in distributed systems are examined in [32]. The paper is focused on the methods of solving disambiguation of role definitions.

Leitner [16] proposed delta-analysis that compares an expected RBAC model with the existing security policy.

The RBAC optimization as reducing the number of roles is considered in [37]. Several role graph building strategies are suggested for solving the problem.

The problem of the optimal role search is addressed in [3]. A strategy consisting of three steps is proposed: each role is weighed, each user gets a threshold value and is then assigned with a best fitting role considering the constraints.

The modules for the role graph’s modification and for designing the specifications allowing us to construct real role-based access control systems are presented in [9,14].

3. Distribution of permissions in a role-based security policy

The main issue of the role-based security policy construction is the assignment of permissions to a particular role. The basic problem here is considering the ordering relations between the roles in distributing the permissions. As one can see from [23], there are three possible approaches differing in the intersection of the roles.

Despite role-based security policies are widespread, some problems of the role hierarchy’s construction remain unsolved. In this section we examine distributing permissions between the roles in RBAC₃ model.

Let us consider a basic model of role-based access control [8,10,30] that has constant security system parameters and highlight its main elements that will be used in the further description. Here are the main sets of the model:

U – the set of the system users.

R – the set of the system roles.

P – the set of the permissions that enable certain actions in the system.

Define two mappings that determine operation of a role-based security policy controlled system:

$RP : R \to 2^{P}$ – the set of permissions for a certain role, at that point $\forall p \in P \exists r \in R : p \in RP (r)$ .

$UR : U \to 2^{R}$ – the set of the roles that a certain user can be authorized for.

It should be noticed that there may be roles not assigned to any user.

Definition 1.
A role hierarchy is a non-strict partial ordering relation over the set of roles R, and if $r_{2} ⩽ r_{1}$ , then $r_{1}$ is higher in the hierarchy, than $r_{2}$ .
Remark 1.
One more condition must be fulfilled here: $\forall u \in U : (r, r^{'} \in R) \land (r \in UR (u)) \land (r^{'} ⩽ r) \Rightarrow (r^{'} \in UR (u))$ . That is, being authorized for a certain role, the user must be authorized for all the roles lying below this role in the hierarchy.

Basing on the given definition, the role hierarchy can be presented as a directed graph $G = (R, E)$ . The set of vertices R of the graph is the set of roles. The arc $(r_{1}, r_{2}) \in E$ if $r_{2} ⩽ r_{1}$ in the role hierarchy.
Remark 2.
In the notations of UML (Unified Modeling Language), a graphical modeling language that provides unified notations to represent various object-oriented projects, the arc must be directed from the subordinate role $r^{'}$ to the superior r. However, to preserve the graph theory terminology we assume that the arcs are directed from the superior roles to the subordinate ones. The ordering relations that define the role hierarchy and the corresponding undirected graphs are obviously the same in both cases.

In the majority of works on the role-based access control, it is assumed that the role hierarchy is presented by DAG (a directed acyclic graph). In the last part of this paper we will call it a role tree, denoted by $T = (R, E)$ .

In the case of the hierarchical role relations special attention is paid to the process of $RP$ -mapping construction. As it was noted previously, $RP$ maps each role from R to the subset of permissions from P. It is important to decide whether it is possible to assign the same set of permissions to two roles, while one of them is subordinated to the other in the hierarchy. In such a case, one applies a “bottom-up” inheritance method, that is assigning permissions starts with leaf nodes (leaf distribution of access permissions). There are three possible approaches to $RP$ -mapping construction:
A taxonomic leaf approach. The set of permissions is partitioned into non-intersecting subsets: $\begin{matrix} (1) & P = ⋃_{i = 1}^{k} P_{i}, \forall i, j : P_{i} \cap P_{j} = \emptyset . \end{matrix}$ Here k denotes the number of the leaf nodes of the role tree. Let $R_{L}$ ( $R_{L} \subset R$ ) be the set of leaf nodes. $RP$ -mapping maps each $r_{i}$ leaf node to one of $P_{i}$ subsets: $\begin{matrix} (2) & \forall r_{i} \in R_{L} : RP (r_{i}) = P_{i} . \end{matrix}$ The permissions of all the other (non-leaf) role tree nodes are calculated as the union of the permissions of the direct child roles: $\begin{matrix} (3) & \forall r \notin R_{L} : RP (r) = ⋃_{r^{'} \in Ch (r)} RP (r^{'}) . \end{matrix}$ Here $Ch (r)$ denotes a full set of node r children.

A non-taxonomic leaf approach. The permissions are also directly assigned only to the leaf roles, and the permissions of the other roles are calculated as the union of the child role permissions. The difference from the previous approach is that the intersection of the leaf role permissions can be non-empty: $\begin{matrix} (4) & P = ⋃_{i = 1}^{k} P_{i}, \exists i, j : P_{i} \cap P_{j} \neq \emptyset . \end{matrix}$

A covering leaf approach. We assign directly (add) to the superior roles only those permissions that are not included in the permission sets of the subordinated roles.
In all the three cases, the resulting permission set includes all the permissions of all the subordinated roles due to the hierarchical structure.
4. Partitioning of the role set into equivalence classes

Suppose the role hierarchy is given by a directed tree $T = (R, E)$ . Consider a partition of the tree T’s set of leaves $R_{L}$ into k subsets: $\begin{matrix} (5) & R_{L} = ⋃_{i = 1}^{k} R_{L}^{(i)}, \forall i, j : R_{L}^{(i)} \cap R_{L}^{(j)} = \emptyset . \end{matrix}$ The partition gives rise to equivalence relation $\overset{R_{L}}{\sim}$ in the set of leaf nodes.

Now consider class-based permission distribution. Let any pair of roles corresponding to the same equivalence class of leaf nodes have identical permissions: $\begin{matrix} (6) & \forall r_{1}, r_{2} \in R_{L} : (r_{1} \overset{R_{L}}{\sim} r_{2}) ⟹ (RP (r_{1}) = RP (r_{2})) . \end{matrix}$

Example 1.
From Fig. 1 it is obvious that the set of leaf nodes can be partitioned into three equivalence classes; the roles of the same class have identical permissions: $p_{1}, p_{2} \in R_{L}^{(1)}$ , $t_{1}, t_{2} \in R_{L}^{(2)}$ , $k_{1}, k_{2} \in R_{L}^{(3)}$ .

Fig. 1.
The role hierarchy that allows partitioning of the set of leaf nodes into equivalence classes.

As for the case of traditional permission distribution, mapping $RP$ of the full set R can be defined in three possible ways.
A taxonomic class-based approach. Suppose k is the number of equivalence classes of the role tree’s leaf nodes. Let us partition the set P into k non-intersecting subsets: $\begin{matrix} (7) & P = ⋃_{i = 1}^{k} P_{i}, \forall i, j : P_{i} \cap P_{j} = \emptyset . \end{matrix}$ The permission distribution is defined by the mapping $RP$ . The mapping is given as follows: $\begin{matrix} (8) & \forall r \in R_{L}^{(i)} : RP (r) = P_{i} . \end{matrix}$ Then the permission set of any non-leaf node is a union of that node’s children: $\begin{matrix} (9) & \forall r \notin R_{L} : RP (r) = ⋃_{r^{'} \in Ch (r)} RP (r^{'}) . \end{matrix}$ Here $Ch (r)$ also denotes the set of all children of the node r.

A non-taxonomic class-based approach. As in the previous case, the first step is distributing permissions between equivalence classes of leaf nodes. The difference is that the intersection of different equivalence classes’ permission sets can be non-empty.

A covering class-based approach. Some permissions are distributed between the equivalence classes of the leaf nodes. The non-leaf nodes inherit the permissions of their children but can also have additional permissions assigned directly to them.
It is obvious that each of the three leaf approaches is a special case of a corresponding class-based approach under the condition: $| R_{L}^{(i)} | = 1$ , where ${R_{L}^{(i)}}_{i = 1}^{k}$ denotes the partition of the list node set. In other words, each leaf node generates a separate class of partition.

The partition of the role tree leaf nodes and the rules of $RP$ -mapping construction generate the partition of the total role set.
Definition 2.
We say that two roles are equivalent if the roles have the same permissions: $\begin{matrix} (10) & \forall r_{1}, r_{2} \in R : (RP (r_{1}) = RP (r_{2})) ⟹ (r_{1} \overset{RP}{\sim} r_{2}) . \end{matrix}$
Definition 3.
The equivalence relation $\overset{RP}{\sim}$ generates the partition of the role set R. The resulting equivalent classes of roles are called $RP$ -classes.
Definition 4.
Label each node r of the role tree with the role’s set of permissions $RP (r)$ . The resulting labelled role tree is called an $RP$ -tree.

So the $RP$ -tree nodes labelled with the same permission set belong to the same $RP$ -class.

We denote the number of $RP$ -classes by K; denote the number of leaf node equivalence classes by k. Obviously, in the case of the taxonomic class-based approach $K ⩾ k$ . In the case of the other two approaches if several equivalence classes are assigned with the same set of permissions, then it is possible that $K < k$ .
5. Optimal $RP$ -trees

Definition 5.
An $RP$ -tree is called confluent if there is only one $RP$ -class in it: $K = 1$ .

For example, if we use the taxonomic class-based approach, then any unary $RP$ -tree is confluent.
Definition 6.
An $RP$ -tree is called optimal if the number of its $RP$ -classes is equal to the number of its nodes: $K = | R |$ .

Note that an $RP$ -tree constructed using a leaf approach can be non-optimal as well as an $RP$ -tree constructed using a class-based one.

Obviously, for an $RP$ -tree to be optimal it is necessary that in the original partition of the leaf node set each leaf form a separate class (leaf distribution of permissions is in use). Let us consider the necessary and sufficient conditions for optimality.
Theorem 1.
Suppose we use the taxonomic leaf approach for permission distribution. Then the $RP$ -tree is optimal if and only if the outdegree (the number of arcs leaving a node, $d^{+}$ ) of each non-leaf node is at least 2: $\begin{matrix} (11) & \forall r \notin R_{L} : d^{+} (r) ⩾ 2 . \end{matrix}$
Proof.
Suppose the $RP$ -tree is optimal. Then by definition: $\begin{matrix} (12) & \forall r_{1}, r_{2} \in R : (r_{1} \neq r_{2}) ⟹ (RP (r_{1}) \neq RP (r_{2})) . \end{matrix}$ The proof is by contradiction. Suppose $\exists r_{1} \notin R_{L} : d^{+} (r_{1}) < 2$ ; then $d^{+} (r_{1}) = 1$ . Then the node $r_{1}$ has only one child; denote it by $r_{2}$ . As the taxonomic leaf approach is used, $RP (r_{1}) = RP (r_{2})$ but that contradicts (12).

Now suppose inequality (11) holds. Show that condition (12) holds and therefore the tree is optimal. Consider two different nodes $r_{1}, r_{2} \in R$ . Note that it follows from (11) that: $\begin{matrix} (13) & \forall r_{1}, r_{2} \in R : (r_{1} \neq r_{2}) ⟹ (R_{L} (r_{1}) \neq R_{L} (r_{2})), \end{matrix}$ where $R_{L} (r_{i})$ denotes the set of leaf nodes of the subtree with root $r_{i}$ . This conclusion obviously follows from the fact that the role hierarchy is acyclic (T is a tree). According to the system of notations in the case of the taxonomic leaf approach we have: $\begin{matrix} (14) & \forall r \in R : RP (r) = ⋃_{r^{'} \in R_{L} (r)} RP (r^{'}) \end{matrix}$ and $\begin{matrix} (15) & \forall r^{'}, r^{″} \in R_{L} : (r^{'} \neq r^{″}) ⟹ (RP (r^{'}) \cap RP (r^{″}) = \emptyset) . \end{matrix}$ It follows from (13) and (15) that: $\begin{matrix} (16) & \forall r_{1}, r_{2} \in R : (r_{1} \neq r_{2}) ⟹ (⋃_{r^{'} \in R_{L} (r_{1})} RP (r^{'}) \neq ⋃_{r^{'} \in R_{L} (r_{2})} RP (r^{'})) . \end{matrix}$ Considering Eq. (14), we get the desired condition (12). □
Theorem 2.
Suppose we use the non-taxonomic leaf approach for the permission distribution. Then an $RP$ -tree is optimal if and only if the outdegree of each non-leaf node is at least 2(condition ( 11 ) holds) and the partitioning of the set of permissions P into subsets $P_{i}$ satisfies the following condition: $\begin{matrix} (17) & \forall j \in {1, \dots, k} : P_{j} ⊈ ⋃_{i = 1, i \neq j}^{k} P_{i} . \end{matrix}$
Proof.
The proof of necessity is similar to the proof of necessity for the previous theorem. To prove sufficiency replace condition (15) with condition (17). Suppose $I_{1}, I_{2} \subseteq {1, \dots, k} : (I_{1} \neq I_{2})$ , then $\exists j : (j \in I_{1}) \land (j \notin I_{2})$ . According to (17): $P_{j} ⊈ ⋃_{i \in I_{2}} P_{i}$ , then, $⋃_{i \in I_{1}} P_{i} ⊈ ⋃_{i \in I_{2}} P_{i}$ . So we have: $\begin{matrix} (18) & \forall I_{1}, I_{2} \subseteq {1, \dots, k} : (I_{1} \neq I_{2}) ⟹ (⋃_{i \in I_{1}} P_{i} \neq ⋃_{i \in I_{2}} P_{i}) . \end{matrix}$ Then, considering inequality (13) and the fact that by definition $\forall r_{i} \in R_{L} : RP (r_{i}) = P_{i}$ , we get (16) and therefore (12). □

Note that in the case of the covering approach an $RP$ -tree with an arbitrary structure (e.g. even a unary tree) can be optimal, because the non-leaf nodes can have non-inherited, i.e., directly assigned, permissions.
6. $RP$ -Tree expansion and optimization

From this moment we call the chosen approach to $RP$ -mapping construction as the $RP$ -tree.

Definition 7.
Let T be an $RP$ -tree. The $RP$ -characteristic of T is a specification that indicates the approach applied to $RP$ -mapping construction:
The tree T is called taxonomic (non-taxonomic, covering) if the taxonomic (non-taxonomic, covering) approach was used for the distribution of permissions.

The tree T is called leaf (class-based) if it is important that leaf (class-based) distribution was used for that tree.

Definition 8.
Expansion of the $RP$ -tree T is construction of an $RP$ -tree $T^{'}$ such, that
T is a subgraph of $T^{'}$ .

$\forall r \in R_{T} : {RP}_{T} (r) = {RP}_{T^{'}} (r)$ – the set of $RP$ -classes of T is included in the set of $RP$ -classes of $T^{'}$ .

Theorem 3.
Any $RP$ -tree can be expanded into a taxonomic (in the general case to a class-based taxonomic) $RP$ -tree.
Proof.
Let us construct a desired $RP$ -tree $T^{'}$ from an arbitrary $RP$ -tree T. In the first step $T^{'}$ gets all the nodes, the arcs and the permissions of T. Therefore the conditions of the definition hold.

Suppose each leaf node $r_{i}$ has a set of permissions $P_{i} = {p_{i 1}, \dots, p_{i m_{i}}}$ . If $| P_{i} | = m_{i} > 1$ , then add $m_{i}$ child leaf nodes to that node in $T^{'}$ so that the jth added node has the only permission $p_{i j}$ ( $j \in {1, \dots, m_{i}}$ ).

Now, traversing the tree $T^{'}$ from the leaves to the root we consider each non-leaf node r. We add to r a child leaf node for each permission from $RP (r)$ that is not inherited by r and assign the corresponding permission to that leaf node.

As a result in the tree $T^{'}$ each non-leaf node inherits all the permissions from its children and has no permission assigned to it directly: $\begin{matrix} (19) & \forall r \notin R_{L} : RP (r) = ⋃_{r^{'} \in Ch (r)} RP (r^{'}) . \end{matrix}$ Now each leaf node of the tree $T^{'}$ is assigned with an only permission. All leaf nodes r having the same value of $RP (r) = {p_{i}}$ belong to the equivalence class of leaf nodes $R_{L}^{(i)}$ . Then $\begin{matrix} (20) & \forall r \in R_{L}^{(i)} : RP (r) = {p_{i}} = P_{i}, \forall i, j : P_{i} \cap P_{j} = \emptyset . \end{matrix}$ Thus the mapping $RP$ satisfies all the requirements of the taxonomic class-based approach; then $T^{'}$ is a taxonomic $RP$ -tree (see Fig. 2). □

Fig. 2.
A covering $RP$ -tree T (left) is expanded to a taxonomic class-based $RP$ -tree $T^{'}$ (right).
Example 2.
Let the permission set of some system consist of 5 access permissions: “1” – Software usage, “2” – Software modification, “3” – Test task editing, “4” – Content editing, “5” – Requirements specification editing. Suppose the permissions are distributed using the covering class-based approach (Fig. 3(a)). According to Theorem 3, this role hierarchy can be expanded into a taxonomic class-based $RP$ -tree (Fig. 3(b)) by adding “fake” roles (FR).

Fig. 3.
Expansion of a role hierarchy.

In fact, by expanding the $RP$ -tree we construct a new role-based access policy that inherits all the roles and the hierarchy from the original one.

According to Theorem 3, the class-based permission distribution has an advantage: it allows us to expand non-taxonomic or covering $RP$ -trees into taxonomic ones, i.e., it allows us to change any $RP$ -characteristic into a taxonomic one. Unfortunately, such transformation often leads to increase of the role (and the $RP$ -classes as well) count.

One can consider an operation which is, in a sense, an inverse of $RP$ -tree expansion. If at least one $RP$ -class includes more than one role, then the tree is not optimal and therefore the security policy has “duplicate” roles. It is natural to try to make the role hierarchy optimal while preserving the set of the system’s $RP$ -classes.
Definition 9.
We say that the trees T and $T^{'}$ are equivalent if the sets of their $RP$ -classes are equal (if one tree has a role with a set of permissions $RP (r)$ , then there exists a role with the same set of permissions in the other tree).

For instance, if we delete the left edge and the leaf node incident to it from the tree T in Fig. 2, then we get an $RP$ -tree that represents another role hierarchy but is equivalent to the original tree.
Definition 10.
Optimization of the $RP$ -tree T is a construction process of such an $RP$ -tree T that
T is equivalent to T.

T is an optimal $RP$ -tree.

Note that, because of optimality, the resulting $RP$ -tree is a leaf one.

Let us try to answer the following questions. Can any $RP$ -tree be optimized? How does the $RP$ -characteristic change after the optimization?

If an $RP$ -tree is a leaf one and the nodes within the same $RP$ -class are not adjacent (otherwise one can contract such nodes pairwise; contraction is the standard operation of the graph theory), then in some cases one can obtain an optimal $RP$ -tree by altering the structure of the tree and changing the $RP$ -characteristic to those of the covering one. However in practice we want to get an optimal taxonomic $RP$ -tree which is equivalent to the original tree.
7. A role-based security policy on an arbitrary digraph

We can get an optimal structure with the same $RP$ -characteristic if we define the role hierarchy by a directed graph (that is not necessarily a tree).

Theorem 4.
A directed graph defines a role hierarchy (i.e., is the digraph of roles) if and only if it has no directed cycles.
Proof.
Absence of directed cycles is necessary and sufficient for the relation given by the graph to be transitive and antisymmetric and therefore to be a partial ordering relation. □

Note that a digraph without directed cycles has at least one sink (a node with zero out-degree: $d^{+} (t_{i}) = 0$ ) and at least one source (a node with zero in-degree: $d^{-} (s) = 0$ ). We will consider digraphs with a single source.

One can distribute permissions on a role digraph using one of the three approaches as in the case of a role tree. The process of $RP$ -mapping construction starts either with sinks (leaf distribution) or equivalence classes of sinks (class-based distribution). The definitions of optimality, expansion, equivalence and optimization can be easily transformed for the case of an $RP$ -digraph (a marked role digraph).
Theorem 5.
Any $RP$ -tree can be transformed into an $RP$ -digraph by optimization.
Proof.
For any pair of vertices that correspond to equivalent roles we contract the arc between them or contract the vertices themselves if there is no arc (edge contraction and vertex contraction are the standard operations of the graph theory). Then the set of $RP$ -classes remains the same, but the directed graph becomes optimal (see Fig. 4). □

Fig. 4.
A taxonomic class-based $RP$ -tree, denoted by T (on the left side) is optimized to a taxonomic leaf $RP$ -digraph, denoted by G (on the right side).
Example 3.
Suppose the system permissions are given by a taxonomic class-based $RP$ -tree (Fig. 5(a)). Let us use Theorem 5 for optimizing the $RP$ -tree; then we have an equivalent taxonomic leaf $RP$ -digraph (Fig. 5(b)).

Fig. 5.
Optimization of a role hierarchy.

Combining the discussions from Examples 2 and 3 one can conclude that a covering class-based $RP$ -tree of roles can be expanded to an optimal taxonomic $RP$ -digraph.
Corollary 1.
It directly follows from the construction procedure of the optimal $RP$ -digraph G that G has the following properties:
G has one source s.

For that graph the number of sinks $t_{i}$ equals to the number of equivalent classes for leaf nodes $R_{L}^{(i)}$ of the original $RP$ -tree T.

$G = T$ if the original $RP$ -tree T is optimal.

G is a leaf $RP$ -digraph.

Corollary 2.
If the original $RP$ -tree is taxonomic, then the optimal equivalent $RP$ -digraph constructed by the algorithm given above is also taxonomic.
Proof.
By contracting the arc between the two vertices corresponding to equivalent roles one does not change the $RP$ -characteristic. If we contract the vertices from the same $RP$ -class, then the resulting set of their children belongs to the same $RP$ -classes as in the original $RP$ -tree. Then the taxonomic structure is preserved. □
Corollary 3.
If the original $RP$ -tree is non-taxonomic, then the optimal equivalent $RP$ -digraph constructed by the algorithm given above is also non-taxonomic.
Corollary 4.
If the original $RP$ -tree is covering, then the optimal equivalent $RP$ -digraph constructed by the algorithm given above may be covering, non-taxonomic or taxonomic.

In general, we can use the following steps to construct a role-based security policy:
Construct an $RP$ -tree $T_{1}$ (leaf or class-based) according to the task.

Expand the tree $T_{1}$ into a taxonomic (in the general case – class-based) $RP$ -tree $T_{2}$ (see Theorem 5).

Transform the tree $T_{2}$ to an equivalent optimal taxonomic $RP$ -digraph $T_{3}$ (see Theorem 5).
Thus, any role model of permission distribution can be expanded to such a policy such that

the role hierarchy is given by digraph without directed cycles,

the taxonomic leaf approach is used for the permission distribution,

the $RP$ -structure is optimal.

It should be mentioned that the algorithm supposed in Theorem 5 is reversible: any $RP$ -digraph can be transformed into an equivalent $RP$ -tree (not necessarily optimal).
Theorem 6.
For any $RP$ -digraph there exists an equivalent $RP$ -tree.
Proof.
Let us construct an equivalent $RP$ -tree T for the given digraph G. Match each sink $t_{i}$ of the digraph G to $d^{-} (t_{i})$ leafs of T (the “original” vertex plus $d^{-} (t_{i}) - 1$ “copies”). This standard operation is called vertex splitting (if the indegree is equal to 1, then we do no actual splitting).

Further, traversing G from the lowest levels to the source we sequentially split each vertex. The “original” and the “copies” get the same permissions as the vertex they were generated by. After splitting a vertex we take already existing nodes of T that have no incoming arcs (T structure guarantees that such nodes always exist) and connect the “original” to them. In this way we restore children of the splitted vertex. For each “copy” we add a subtree that is identical to the subtree generated by the “original” and has the “copy” vertex as a root.

Obviously, the hierarchy T is an $RP$ -tree and has the same $RP$ -classes as the original digraph G, that is, T is equivalent to G (see Fig. 6). □

Fig. 6.
An $RP$ -digraph G (left) and an equivalent $RP$ -tree T (right).
Example 4.
Consider a role hierarchy. Figure 7(a) depicts the corresponding covering $RP$ -digraph. According to Theorem 6 one can easily get the equivalent $RP$ -tree, depicted in the Fig. 7(b).

Fig. 7.
Moving to a tree role hierarchy.
Corollary 5.
The number of the nodes of the $RP$ -tree T, which is constructed by the algorithm described in Theorem 6 and is equivalent to the $RP$ -digraph G, can be found by the formula: $\begin{matrix} (21) & \sum_{r \in R_{G}} (1 + (d^{+} (r) - 1) | R_{T (r)} |) . \end{matrix}$ Here $R_{G}$ denotes the set of vertices of the digraph G, $R_{T (r)}$ is the number of the nodes of the subtree with the root in the node of T corresponding to the vertex r of G.
Example 5.
Let us use formula (21) to calculate the number of the nodes of the $RP$ -tree that is equivalent to the $RP$ -digraph, traversing the digraph from the bottom to the top and from the left to the right (Fig. 7(a)): $\begin{matrix} 1 + (1 + 1 \cdot 2) + (1 + 1 \cdot 3) + (1 + 1 \cdot 3) + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 19 . \end{matrix}$ The result equals to the count of the nodes of the $RP$ -tree constructed by the algorithm of Theorem 6 (Fig. 7(b)).

Note that Theorem 6 allows us to reduce analysis of a role-based security policy defined on an arbitrary $RP$ -digraph to analysis of an equivalent $RP$ -tree. Theorems 5 and 6 allow us to carry out different equivalent transformations of a role hierarchy in order to get either a tree or an optimal structure for more convenient analysis in each particular case.

Thus, to define a security policy on an arbitrary directed graph a model was developed in four following stages:

The “Ascending” principle of $RP$ -mapping construction was generalized for the case when several “leaf” roles are assigned with the same set of permissions (class-based permission distribution).

We introduced the concept of an optimal role tree.

We described the expansion procedure that makes a role tree taxonomic.

Optimization of the obtained taxonomic role tree resulted in construction of the role hierarchy on the directed graph without directed cycles.
8. Conclusion

Thus, we have shown that one RBAC model can be equivalent to several role graphs. Moreover, it is possible to check the graph’s equivalence in the sense of permission distribution. This fact is essential for development of the graph theory as it allows to construct different role hierarchy representations that are optimal from different points of view. We have also shown that these transformations are reversible.

The role graph transformations described here allow making a tree from an arbitrary graph and vice versa without losing functionality and relationships between the roles. Such transformations can be useful for designing the algorithms able to recognize the permission distribution flows on role graphs or to find the duplicate roles.

The role graph’s transformations can also be useful for optimizing RBAC using different criteria. For instance, when one needs reduce the amount of roles in a system, he may start from dividing the roles into equivalence classes and optimizing the hierarchical structure by merging all the roles of each class into one role or finding close equivalence classes.

The series of transformations suggested in the present work cause the amount of roles in a system to increase, but it is not critical if the new roles are considered as the pseudoroles in the same sense as pseudousers in UNIX-systems. There are no users authorized for those pseudoroles, but they allow solving different problems from one universal point of view.

Hence, the results presented here are rather theoretical, some of them are even existence theorems, but they make it possible to design the algorithms enhancing flexibility of development and exploitation of RBAC-based security systems.

Footnotes

Acknowledgment

This work is sponsored in part by the Ministry of Education and Science of the Russian Federation within the framework of the state task for institutions of higher education for 2014–2016, project 2314.

References

[1]

Bertino ,

Terzi ,

Kamra and

Vakali , Intrusion detection in RBAC-administered databases, in: Proceedings of the 21st Annual Computer Security Applications Conference, 2005, pp. 170–182.

[2]

Chandramouli and

Sandhu , Role based access control features in commercial database management systems, in: Proceedings of the 21st National Information Systems Security Conference, Crystal City, Virginia, 1998.

[3]

Colantonio ,

R.D.

Pietro ,

Ocello and

N.V.

Verde , Taming role mining complexity in RBAC, Computers & Security 29(5) (2010), 548–564.

[4]

Crampton and

Loizou , Administrative scope and role hierarchy operations, in: Proceedings of Seventh ACM Symposium on Access Control Models and Technologies (SACMAT 2002), 2002, pp. 145–154.

[5]

Crampton and

Loizou , Administrative scope: A foundation for role-based administrative models, ACM Transactions on Information and System Security 6(2) (2003), 201–231.

[6]

Ferraiolo ,

Cugini and

Kuhn , Role-based access control: Features and motivations, in: Proceedings of 11th Annual Computer Security Applications Conference, IEEE Computer Society Press, 1995, pp. 249–255.

[7]

Ferraiolo and

Kuhn , Role-based access control, in: Proceedings of 15th NIST-NCSC National Computer Security Conference, Baltimore, Maryland, 1992, pp. 554–563.

[8]

Ferraiolo ,

Sandhu ,

Gavrila ,

D.R.

Kuhn and

Chandramouli , Proposed NIST standard for role based access control, ACM Transactions on Information and System Security 4(3) (2001), 224–274.

[9]

Grobe-Rhode ,

F.P.

Presicce and

Simeoni , Formal software specification with refinements and modules of typed graph transformation systems, Journal of Computer and System Sciences 64(2) (2002), 171–218.

10.

[10]

Jaeger and

Tidswell , Rebuttal to the NIST RBAC model proposal, in: Proceedings of 5th ACM Workshop on Role-Based Access Control, Berlin, Germany, 2000, pp. 65–66.

11.

[11]

Koch ,

L.V.

Mancini and

Parisi-Presicce , A formal model for role-based access control using graph transformation, in: Proc. of 5th ESORICS, LNCS, Vol. 1895, 2000, pp. 122–139.

12.

[12]

Koch ,

L.V.

Mancini and

Parisi-Presicce , Decidability of safety in graph-based models for access control, in: Proc. of 7th ESORICS, LNCS, Vol. 2502, 2002, pp. 229–243.

13.

[13]

Koch ,

L.V.

Mancini and

Parisi-Presicce , A graph-based formalism for RBAC, ACM Transactions on Information and System Security 5(3) (2002), 332–365.

14.

[14]

Koch ,

L.V.

Mancini and

Parisi-Presicce , Graph-based specification of access control policies, Journal of Computer and System Sciences 71(1) (2005), 1–33.

15.

[15]

Koch and

Parisi-Presicce , Describing policies with graph constraints and rules, in: Proceeding ICGT’02 Proceedings of the First International Conference on Graph Transformation, 2002, pp. 223–238.

16.

[16]

Leitner , Delta analysis of role-based access control models, in: Lecture Notes in Computer Science, Vol. 8111, 2013, pp. 507–514.

17.

[17]

Li and

Mao , Administration in role-based access control, in: ASIACCS’07 Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, 2007, pp. 127–138.

18.

[18]

Nakamura , SELinux policy editor RBAC guide, 2006, pp. 1–8, available at: http://seedit.sourceforge.net/doc/2.0/rbac_guide.pdf.

19.

[19]

Nyanchama and

S.L.

Osborn , Access rights administration in role-based security systems, in: Proceedings of the IFIP WG11.3 Working Conference on Database Security VII, North-Holland, 1994, pp. 37–56.

20.

[20]

Nyanchama and

S.L.

Osborn , The role graph model and conflict of interest, ACM Transactions on Information and System Security 2(1) (1999), 3–33.

21.

[21]Oracle, Oracle Solaris administration: Security services, 2012, pp. 131–210, available at: http://docs.oracle.com/cd/E23824_01/pdf/821-1456.pdf.

22.

[22]

S.L.

Osborn , Integrating role graphs: A tool for security integration, Data & Knowledge Engineering 43(3) (2002), 317–333.

23.

[23]

S.L.

Osborn , Role-based access control: Past, present and future, in: PST’06 Proceedings of the 2006 International Conference on Privacy, Security and Trust: Bridge the Gap Between PST Technologies and Business Services, ACM International Conference Proceeding Series, 2006, p. 4.

24.

[24]

S.L.

Osborn ,

Han and

Liu , A methodology for managing roles in legacy systems, in: SACMAT’03 Proceedings of the Eighth ACM Symposium on Access Control Models and Technologies, 2003, pp. 33–40.

25.

[25]

R.S.

Sandhu and

Bhamidipati , Role-based administration of user-role assignment: The URA97 model and its Oracle implementation, Journal of Computer Security 7 (1999), 317–342.

26.

[26]

R.S.

Sandhu ,

Bhamidipati ,

Coyne ,

Ganta and

Youman , The ARBAC97 model for role-based administration of roles: Preliminary description and outline, in: Proceedings of the Second ACM Workshop on Role-Based Access Control (RBAC 1997), 1997, pp. 41–50.

27.

[27]

R.S.

Sandhu ,

Bhamidipati and

Munawer , The ARBAC97 model for role-based administration of roles, ACM Transactions on Information and Systems Security 2(1) (1999), 105–135.

28.

[28]

R.S.

Sandhu ,

E.J.

Coyne ,

H.L.

Feinstein and

C.E.

Youman , Role based access control: A multidimensional view, in: Proceedings of 10th Annual Computer Security Applications Conference, Orlando, 1994, pp. 54–62.

29.

[29]

R.S.

Sandhu ,

E.J.

Coyne ,

H.L.

Feinstein and

C.E.

Youman , Role-based access control models, IEEE Computer 29(2) (1996), 38–47.

30.

[30]

R.S.

Sandhu ,

Ferraiolo and

Kuhn , The NIST model for role-based access control: Towards a unified standard, in: Proceedings of 5th ACM Workshop on Role-Based Access Control, Berlin, Germany, 2000, pp. 47–63.

31.

[31]Sun Microsystems, RBAC in the Solaris operating environment, available at: http://www.oracle.com/technetwork/server-storage/solaris/overview/wp-rbac-149876.pdf.

32.

[32]

M.N.

Tahir , Hierarchies in contextual role-based access control model (C-RBAC), International Journal of Computer Science and Security (IJCSS) 2(4) (2008), 28–42.

33.

[33]

Theriault and

Newman , Oracle 9: Oracle Security Handbook, McGraw-Hill/Osborne, 2001.

34.

[34]

Thion and

Coulondre , Representation and reasoning on role-based access control policies with conceptual graphs, in: Proceeding of Conceptual Structures: Inspiration and Application, 14th International Conference on Conceptual Structures, ICCS 2006, Aalborg University, Denmark, 2006, pp. 427–440.

35.

[35]

Toahchoodee ,

Ray and

R.M.

McConnell , Using graph theory to represent a spatio-temporal role-based access control model, International Jornal of Next-Generation Computing 1(2) (2010), 231–250.

36.

[36]

Wang and

S.L.

Osborn , Static and dynamic delegation in the role graph model, IEEE Trans. Knowl. Data Eng. 23(10) (2011), 1569–1582.

37.

[37]

Zhang ,

Ramamohanarao ,

Versteeg and

Zhang , Graph based strategies to role engineering, in: CSIIRW’10 Proceedings of the Sixth Annual Workshop on Cyber Security and Information Intelligence Research, 2010, Article N. 25.