- The problems which are important for the effective functioning of an access control policy in a large information system (LIS) are selected. The general concept of a local optimization of a role-based access control (RBAC) model is formulated. The optimization criteria are proposed. The algorithms of a local optimization of the RBAC model are defined and justified. The developed algorithms are used in the methods of the solution of the following problems: the assessment of risks of the leakage of permissions in the RBAC policy, the access control in the distributed hierarchical systems, the combining of role-based and mandatory access control models. In the first problem the question of the permissions distribution in the role hierarchy is researched. The analytic hierarchy process (AHP) is applied to creation of the estimates. The method is based on the hierarchical structure of a role set. The offered technique can order the permissions according to the value of the risks of their leakage. In the second problem the algorithm of the distribution of the cryptographic keys in the system with a hierarchical arrangement of the objects is offered. The cryptography protocols for the practical use of this algorithm are defined. The conditions of the implementation of the discretionary and mandatory principles of the access control on the basis of the developed algorithm are formulated.
INTRODUCTION
The research objective is the development of methods and algorithms of the solution of the problems which arise in the case of the implementation of an access control policy in a LIS. The specifics of the data access arrangement in a LIS are defined. Here are the most significant factors:
The demand of the RBAC mechanisms as the
objectoriented decision which is capable to reduce
complexity of the LIS administration [
The need for the combination of the several access
control models in the case of the continuous
functioning of subsystems where these principles of
the access control are implemented [
Now interest in RBAC is shifted towards the role mining
problem [
Based on these factors a set of the problems which are important for the effective work of a LIS safety subsystem is selected.
1.
The creation and the supporting of the RBAC.
1.2. The taxonomic distribution of permissions. 1.3. The optimal file representation of a role hierarchy. 1.4. The assessment of risks of the leakage of permissions. 2. 3.
The access control on the basis of the computable cryptographic keys.
The combining of the different security models in a computer system.
The efficiency of the solution of these problems
significantly depends on the structure of the role hierarchy
which is used in the LIS access control policy. The additional
properties of the role hierarchy which are required for the
solution of the formulated problems are found: tree-like
hierarchy; leaf hierarchy; RP-reduced hierarchy;
transitivereduced hierarchy (tab. I) [
There is a need for development of the conversion methods of the role hierarchy according to the specified characteristics. At the same time changes of an access control subsystem must be transparent for the user: a user is obliged to receive the same permissions before and after the conversions.
II.
The graph-based representation of the RBAC model was formalized for more strict determination of the possible conversions of the role hierarchy. It is known that RBAC model is defined by the set of following elements: U, P, R – sets of users, permissions and roles; RP: R → 2P, UR: U → 2R, RR: R → 2R, UP: U → 2P – mappings which define the distribution of permissions between roles, the authorization of users for roles, the authorization of roles at each other, the users permissions.
The directed marked graph which has no directed cycles (the role graph) G = (R, E, RP) is the graphical representation of sets P, R and mappings RP, RR. The arc (ri, rj) exists in the role graph if and only if rj RR(ri).
RBAC models are named the equivalent models if the sets of permissions coincide, the sets of users coincide too, and the user's permissions mappings are isomorphic in these models.
Required conversions of the RBAC model must consist in the following: to lead the role hierarchy to the required look; to lead to creation of the equivalent RBAC model; to make the minimum changes to the main sets and mappings of the RBAC model.
These conversions are named the local optimization of the RBAC model. By definition the local optimization comes down to conversions of a role graph.
For further formalization the RP-conversions of a role graph are defined. These conversions must lead to creation of the equivalent RBAC model. The conversion of a role graph G to a role graph G* is RP-admissible if the following conditions are satisfied:
RP(G) RP(G*); directed path (ri, rj) G “conjugate” directed path (ru, rv) G*: RP(ri) = RP(ru) ˄ RP(rj) = RP(rv).
The conversion of a role graph G to a role graph G* is RPequivalent if the following conditions are satisfied:
RP(G) = RP(G*); the requirement of the existence of the "conjugate" directed path must be fulfilled both for an initial role graph and for a resultant role graph.
It is proved that the conversion F of a role graph G to a role graph G* is the local optimization of the RBAC model if the following conditions are satisfied:
G* meets the selected criterion of optimality; F is RP-admissible (or RP-equivalent) conversion; the number of the nodes and/or of the arcs of a role graph did not increase or this increase is minimum.
Four criteria of the local optimization of a role graph are selected: tree-like role graph, leaf role graph, RP-reduced role graph and transitive-reduced role graph.
Some propositions and theorems which define and justify
the algorithms of the local optimization of the RBAC model
are proved [
Algorism (I) (II) (III) (IV) (Iа) (I+II) (III+I) (III+Iа)
Conversion Features of the optimal role graph
Main algorithms RP-admissible single, leaf RP-equivalent RP-reduced RP-equivalent tree-like RP-equivalent transitive-reduced
Derivative algorithms RP-admissible leaf RP-admissible single, taxonomic, leaf, RP-reduced RP-admissible leaf, tree-like
RP-admissible single, leaf, tree-like
The complexity of the constructed algorithms is a polynomial in the number of roles and permissions.
The algorithms of the local optimization of the RBAC model were used for creation of the methods of the solution of some access control problems (tab. 1). The results received for problems (1.4) (2) and (3) follow.
III.
APPLICATIONS OF THE ALGORITHMS OF THE LOCAL
OPTIMIZATION
The assessment problem of risks of the leakage of permissions in the RBAC policy is formalized: probability of leakage of each permissions pi P must be evaluated. The new algorithm of the solution of this problem uses AHP and the role graph of the RBAC policy. The tree-like leaf role hierarchy is necessary for implementation of the offered approach. This type of hierarchy is provided by algorithm (III+I). The advantages of the developed technique are defined and justified:
The "model" error of AHP which arises in a consequence of inconsistency of opinions of experts is removed.
The automation of the process of the ordering of the permissions according to the value of the risks of their leakage is possible.
The problem of the access control in the hierarchical
system is defined: the set of the system’s objects is partially
ordered; access control model for this system must be defined
[
Each object Oi (i = 1, …, n) is encrypted by a secret key ki (an access key); a symmetric encryption is used. An access to the object Oi is possible if the access key ki is known and the condition of a sequential access is satisfied. The sequential access consists in the following: if a user wants to get an access to the object Oi, he must have an access to all objects which form the directed path from the hierarchy root to the object Oi.
In the local systems this problem can be solved by a
security subsystem. In the distributed system a uniform
security subsystem is absent; the access control is reached by
means of algorithms of a distribution of cryptographic keys and
an encryption. The new method of the distribution of the access
keys is offered. This method is based on the principle of the
computability of keys [
The new method of the combining of RBAC and mandatory access control (MAC) is offered. This approach is based on the search of the "ideal" solution: the access rules must meet requirements of the both models and must not contradict each other. The Cartesian product of the MAC lattice and the “role” lattice which is generated by the role hierarchy is considered. Algorithm (III) is involved for the receiving a “role” lattice.
Further problems (1.4) and (2) will be represented in more detail.
IV.
THE ASSESSMENT OF RISKS OF THE LEAKAGE OF
PERMISSIONS The heuristic assumptions are formulated: 1. The more the number of permissions of the role is, the more probability of the attack on this role is.
2. The more the prevalence of the permission in the role hierarchy is, the more the probability of the leakage of this permission is.
3. The more the distance of the role from the hierarchy root is, the less the probability of the attack on this role is.
According to algorithm (III+I) of a local optimization of the RBAC model we can assume that the role graph is the tree-like leaf digraph T.
At the preparatory stage the tree T extends to the tree Tp: to each leaf rl of the tree T the new nodes are added; the new node contains one permission from the set of permissions RP(rl) of the leaf rl (fig. 1). The tree of the solution of the AHP is the tree Tp.
At the first stage the relative coefficients of all nodes (except a root) of the tree Tp are calculated. The calculation of the coefficients takes place in the direction from the root to the leaf. The nodes rs1, …, rsk which are subordinated to one node rs from the previous level are considered. In terms of AHP the selected nodes rs1, …, rsk are the alternatives for the criterion rs. For each subset {rs1, …, rsk} the paired comparisons matrix Ms is built. This matrix is used for the calculation of the relative coefficients of the nodes rs1, …, rsk. The matrix element [Ms]ij which corresponds to pair (rsi, rsj) is equated to the relation of the number of permissions of the role ri to the number of permissions of the role rj: M RP(rsi ) s ij
RP(rsj ) .
It is proved that these paired comparisons matrixes are ideally coordinated. As a result the relative coefficient wsi of the node rsi is calculated according to the formula: wsi RP(rsi ) k j1 RP(rsj ) .
At the second stage the combined coefficients (probabilities or risks of the leakage of permissions) are calculated. The probability of the leakage of the permission p is equal to the sum over all directed paths from the root to the leaves which contain this permission. Each item of the sum is the product of the relative coefficients of the nodes which form one of the directed paths.
P( p)
(root, leaf): RP(leaf) { p} j: rj (root, leaf) wj .
The complexity of the suggested algorithm is a polynomial in the number of roles n and permissions m: T = O((n m)2).
V.
THE ACCESS CONTROL ON THE BASIS OF THE
COMPUTABLE CRYPTOGRAPHIC KEYS.
One secret key k0 is determined and stored. All access keys are calculated one of another according to an object hierarchy: if an arc (Oi, Oj) is in the hierarchy then the access key kj of the object Oj is a value of the function h, which is infeasible to invert (h is one-way function). The function h depends on the access key ki of the object Oi and the properties of the object Oj: kj = h(ki, Oj). The algorithm of the formation of computable access keys for a tree-like object hierarchy is defined. This algorithm uses cryptographic hash function as function h.
1. The unique identifier idi is assigned to each object Oi. The general initialized key k0 is defined.
2. The access key k1 of the object O1 which is a root of the object hierarchy is calculated by the formula: k1 = h(k0 id1), where (k0 id1) is the concatenation of the key and the identifier.
3. For each arc (Oi, Oj) of the object hierarchy the access key kj of the object Oj is calculated by the formula:
kj = h(ki idj).
The suggested algorithm is named "hash-based access keys distribution" (HBAKD). It is proved that existence of the treelike object hierarchy is necessary and sufficient condition of uniqueness of the computation of access keys according to the HBAKD algorithm. The generalized algorithm of the formation of computable access keys for arbitrary object hierarchy which is described by the digraph G is defined:
1. The directed tree T which is ID-equivalent to the digraph G is constructed. For this purpose the modification of algorithm (III) of a local optimization of the RBAC model is used. 2. According to the HBAKD algorithm the access keys for all nodes of the tree T are computed.
3. Secret sharing scheme can be applied to each ID class of the tree T if this class consists of several elements.
The cryptographic protocols for the practical use of the HBAKD algorithm are offered. The main one is "Key-change" protocol (fig. 2). The possible attacks on these protocols are analyzed. The additional safety measures which are put in protocols are proved (tab. III).
The conditions of the implementation of the discretionary and mandatory principles of the access control on the basis of the HBAKD algorithm are formulated. It is supposed that the set of the objects is partially ordered and the access to any object is possible only sequentially from the "parent" object to the "child" object. It is proved that the implementation of the mandatory and discretionary models of the access control is possible for a tree-like object hierarchy in the case of the execution of the conditions which are listed in table IV (IDS is the set of the identifiers of the objects which are accessible for the subject S).
VI.
CONCLUSIONS
Some problems which are important for the effective work of an access control policy in a LIS have been discussed. The solution of these problems significantly depended on the structure of the hierarchy of the system's entities. A special attention has been paid to the RBAC model. The general concept of the local optimization of the RBAC model has been formulated. This process consists in the equivalent conversions of a role graph. The equivalent conversions make the minimum changes to the main sets and mappings of the RBAC model and increase the efficiency of the functioning of the system due to the coercion of the role hierarchy to the required look. The tools which can execute the specified conversions of the RBAC model have been developed. On the basis of optimization algorithms the methods of the creation and of the supporting of the access control policy in a LIS have been obtained. The correctness of the offered approaches, methods and algorithms has been confirmed by the rigorous mathematical proofs and by the results of the computing experiments.
THE ADDITIONAL SAFETY MEASURES OF THE “KEY-CHANGE”
PROTOCOL
Possible attacks Interception of the message "Key-change";
substitution of the “child” Sending the false message "Key-change"; substitution of the "parent"
Safety measures Step 2 of the protocol
TABLE IV. CONDITIONS OF THE IMPLEMENTATION OF THE DISCRETIONARY AND MANDATORY PRINCIPLES OF THE ACCESS CONTROL Access control
Mandatory
Discretionary Mandatory and discretionary