The Equivalent Conversions of the Role-Based Access Control Model Nadezda Bogachenko Dostoevsky Omsk State University Omsk, Russia nfbogachenko@mail.ru Abstract — The problems which are important for the Based on these factors a set of the problems which are effective functioning of an access control policy in a large important for the effective work of a LIS safety subsystem is information system (LIS) are selected. The general concept of a selected. local optimization of a role-based access control (RBAC) model is formulated. The optimization criteria are proposed. The 1. The creation and the supporting of the RBAC. algorithms of a local optimization of the RBAC model are defined 1.1. The deleting the duplicate roles. and justified. The developed algorithms are used in the methods of the solution of the following problems: the assessment of risks 1.2. The taxonomic distribution of permissions. of the leakage of permissions in the RBAC policy, the access control in the distributed hierarchical systems, the combining of 1.3. The optimal file representation of a role hierarchy. role-based and mandatory access control models. In the first 1.4. The assessment of risks of the leakage of permissions. problem the question of the permissions distribution in the role hierarchy is researched. The analytic hierarchy process (AHP) is 2. The access control on the basis of the computable applied to creation of the estimates. The method is based on the cryptographic keys. hierarchical structure of a role set. The offered technique can order the permissions according to the value of the risks of their 3. The combining of the different security models in a leakage. In the second problem the algorithm of the distribution computer system. of the cryptographic keys in the system with a hierarchical The efficiency of the solution of these problems arrangement of the objects is offered. The cryptography significantly depends on the structure of the role hierarchy protocols for the practical use of this algorithm are defined. The which is used in the LIS access control policy. The additional conditions of the implementation of the discretionary and properties of the role hierarchy which are required for the mandatory principles of the access control on the basis of the developed algorithm are formulated. solution of the formulated problems are found: tree-like hierarchy; leaf hierarchy; RP-reduced hierarchy; transitive- Keywords — access control; role hierarchy; local optimization; reduced hierarchy (tab. I) [14, 15]. permissions leakage risks; analytic hierarchy process; hash There is a need for development of the conversion methods function; sequential access. of the role hierarchy according to the specified characteristics. At the same time changes of an access control subsystem must I. INTRODUCTION be transparent for the user: a user is obliged to receive the same The research objective is the development of methods and permissions before and after the conversions. algorithms of the solution of the problems which arise in the case of the implementation of an access control policy in a LIS. II. LOCAL OPTIMIZATION OF THE RBAC The specifics of the data access arrangement in a LIS are The graph-based representation of the RBAC model was defined. Here are the most significant factors: formalized for more strict determination of the possible  The demand of the RBAC mechanisms as the object- conversions of the role hierarchy. It is known that RBAC oriented decision which is capable to reduce model is defined by the set of following elements: U, P, R – complexity of the LIS administration [1, 2]. sets of users, permissions and roles; RP: R → 2P, UR: U → 2R, RR: R → 2R, UP: U → 2P – mappings which define the  The need for the combination of the several access distribution of permissions between roles, the authorization of control models in the case of the continuous users for roles, the authorization of roles at each other, the functioning of subsystems where these principles of users permissions. the access control are implemented [3 – 5]. The directed marked graph which has no directed cycles Now interest in RBAC is shifted towards the role mining (the role graph) G = (R, E, RP) is the graphical representation problem [6 – 9] and different “supermodels” [10, 11]. One of sets P, R and mappings RP, RR. The arc (ri, rj) exists in the more direction of scientific activities is development of role graph if and only if rj  RR(ri). methods of RBAC configuration for cloud computing [12, 13]. 11 TABLE I. CHARACTERISTICS OF THE ROLE HIERARCHY WHICH ARE TABLE II. ALGORITHMS OF THE LOCAL OPTIMIZATION OF THE RBAC NECESSARY FOR THE SOLUTION OF SOME ACCESS CONTROL PROBLEMS MODEL Role transitive- Algorism Conversion Features of the optimal role graph tree-like leaf RP-reduced hierarchy reduced Main algorithms Number (1.4) (1.1) (I) RP-admissible single, leaf of the (2) (1.3) (II) RP-equivalent RP-reduced (1.2) problem (3) (III) RP-equivalent tree-like (IV) RP-equivalent transitive-reduced Derivative algorithms RBAC models are named the equivalent models if the sets (Iа) RP-admissible leaf of permissions coincide, the sets of users coincide too, and the (I+II) RP-admissible single, taxonomic, leaf, RP-reduced (III+I) RP-admissible leaf, tree-like user's permissions mappings are isomorphic in these models. (III+Iа) RP-admissible single, leaf, tree-like Required conversions of the RBAC model must consist in the following: The complexity of the constructed algorithms is a  to lead the role hierarchy to the required look; polynomial in the number of roles and permissions.  to lead to creation of the equivalent RBAC model; The algorithms of the local optimization of the RBAC model were used for creation of the methods of the solution of  to make the minimum changes to the main sets and some access control problems (tab. 1). The results received for mappings of the RBAC model. problems (1.4) (2) and (3) follow. These conversions are named the local optimization of the RBAC model. By definition the local optimization comes III. APPLICATIONS OF THE ALGORITHMS OF THE LOCAL down to conversions of a role graph. OPTIMIZATION For further formalization the RP-conversions of a role The assessment problem of risks of the leakage of graph are defined. These conversions must lead to creation of permissions in the RBAC policy is formalized: probability of the equivalent RBAC model. The conversion of a role graph G leakage of each permissions pi  P must be evaluated. The new to a role graph G* is RP-admissible if the following conditions algorithm of the solution of this problem uses AHP and the role are satisfied: graph of the RBAC policy. The tree-like leaf role hierarchy is necessary for implementation of the offered approach. This  RP(G)  RP(G*); type of hierarchy is provided by algorithm (III+I). The advantages of the developed technique are defined and   directed path (ri, rj)  G  “conjugate” directed justified: path (ru, rv)  G*: RP(ri) = RP(ru) ˄ RP(rj) = RP(rv).  The "model" error of AHP which arises in a The conversion of a role graph G to a role graph G* is RP- consequence of inconsistency of opinions of experts is equivalent if the following conditions are satisfied: removed.  RP(G) = RP(G*);  The automation of the process of the ordering of the  the requirement of the existence of the "conjugate" permissions according to the value of the risks of their directed path must be fulfilled both for an initial role leakage is possible. graph and for a resultant role graph. The problem of the access control in the hierarchical It is proved that the conversion F of a role graph G to a role system is defined: the set of the system’s objects is partially graph G* is the local optimization of the RBAC model if the ordered; access control model for this system must be defined following conditions are satisfied: [16]. The execution of the following conditions is supposed:  G* meets the selected criterion of optimality;  The object hierarchy is defined by the digraph G; the order G is n.  F is RP-admissible (or RP-equivalent) conversion;  Each object Oi (i = 1, …, n) is encrypted by a secret  the number of the nodes and/or of the arcs of a role key ki (an access key); a symmetric encryption is used. graph did not increase or this increase is minimum.  An access to the object Oi is possible if the access key Four criteria of the local optimization of a role graph are ki is known and the condition of a sequential access is selected: tree-like role graph, leaf role graph, RP-reduced role satisfied. The sequential access consists in the graph and transitive-reduced role graph. following: if a user wants to get an access to the object Some propositions and theorems which define and justify Oi, he must have an access to all objects which form the algorithms of the local optimization of the RBAC model the directed path from the hierarchy root to the object are proved [14, 15]. These algorithms lead to creation of the Oi. equivalent RBAC model. Four main and four derivative In the local systems this problem can be solved by a algorithms are received (tab. II). security subsystem. In the distributed system a uniform security subsystem is absent; the access control is reached by 12 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 [16]. For the implementation of this approach the object hierarchy must be tree-like. Algorithm (III) provides this requirement. 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 Fig. 1. The fragment of the extended tree Tp must meet requirements of the both models and must not contradict each other. The Cartesian product of the MAC At the second stage the combined coefficients (probabilities lattice and the “role” lattice which is generated by the role or risks of the leakage of permissions) are calculated. The hierarchy is considered. Algorithm (III) is involved for the probability of the leakage of the permission p is equal to the receiving a “role” lattice. sum over all directed paths from the root to the leaves which contain this permission. Each item of the sum is the product of Further problems (1.4) and (2) will be represented in more the relative coefficients of the nodes which form one of the detail. directed paths. IV. THE ASSESSMENT OF RISKS OF THE LEAKAGE OF   PERMISSIONS P( p)       (root, leaf): RP (leaf)  { p}  j : r j  (root, leaf) wj  .  The heuristic assumptions are formulated:  1. The more the number of permissions of the role is, the The complexity of the suggested algorithm is a polynomial more probability of the attack on this role is. in the number of roles n and permissions m: T = O((n  m)2). 2. The more the prevalence of the permission in the role V. THE ACCESS CONTROL ON THE BASIS OF THE hierarchy is, the more the probability of the leakage of this COMPUTABLE CRYPTOGRAPHIC KEYS. permission is. One secret key k0 is determined and stored. All access keys 3. The more the distance of the role from the hierarchy root are calculated one of another according to an object hierarchy: is, the less the probability of the attack on this role is. if an arc (Oi, Oj) is in the hierarchy then the access key kj of the According to algorithm (III+I) of a local optimization of the object Oj is a value of the function h, which is infeasible to RBAC model we can assume that the role graph is the tree-like invert (h is one-way function). The function h depends on the leaf digraph T. 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 At the preparatory stage the tree T extends to the tree Tp: to access keys for a tree-like object hierarchy is defined. This each leaf rl of the tree T the new nodes are added; the new node algorithm uses cryptographic hash function as function h. 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 1. The unique identifier idi is assigned to each object Oi. tree Tp. The general initialized key k0 is defined. At the first stage the relative coefficients of all nodes 2. The access key k1 of the object O1 which is a root of the (except a root) of the tree Tp are calculated. The calculation of object hierarchy is calculated by the formula: k1 = h(k0  id1), the coefficients takes place in the direction from the root to the where (k0  id1) is the concatenation of the key and the leaf. The nodes rs1, …, rsk which are subordinated to one node identifier. rs from the previous level are considered. In terms of AHP the selected nodes rs1, …, rsk are the alternatives for the criterion rs. 3. For each arc (Oi, Oj) of the object hierarchy the access For each subset {rs1, …, rsk} the paired comparisons matrix Ms key kj of the object Oj is calculated by the formula: is built. This matrix is used for the calculation of the relative kj = h(ki  idj). coefficients of the nodes rs1, …, rsk. The matrix element [Ms]ij which corresponds to pair (rsi, rsj) is equated to the relation of The suggested algorithm is named "hash-based access keys the number of permissions of the role ri to the number of distribution" (HBAKD). It is proved that existence of the tree- permissions of the role rj: like object hierarchy is necessary and sufficient condition of uniqueness of the computation of access keys according to the M s ij  RP(rsi ) RP(rsj ) . HBAKD algorithm. The generalized algorithm of the formation of computable access keys for arbitrary object hierarchy which It is proved that these paired comparisons matrixes are is described by the digraph G is defined: ideally coordinated. As a result the relative coefficient wsi of 1. The directed tree T which is ID-equivalent to the digraph the node rsi is calculated according to the formula: G is constructed. For this purpose the modification of algorithm (III) of a local optimization of the RBAC model is  k wsi  RP ( rsi ) j 1 RP (rsj ) . used. 13 TABLE IV. CONDITIONS OF THE IMPLEMENTATION OF THE DISCRETIONARY AND MANDATORY PRINCIPLES OF THE ACCESS CONTROL Access control Identifiers It is known to the S Mandatory Open ki Discretionary Secret k0 + IDS Mandatory and discretionary Secret ki + IDS REFERENCES Fig. 2. The scheme of "Key-change" protocol [1] Boadu E.O., Armah G.K. Role-Based Access Control (Rbac) Based In Hospital Management. International Refereed Journal of Engineering 2. According to the HBAKD algorithm the access keys for and Science (IRJES). 2014. Vol. 3, Issue 9. P. 53–67. URL: all nodes of the tree T are computed. http://www.irjes.com/Papers/vol3-issue9/H395367.pdf. [2] Cheung H., Li C., Yu Y., Yang C. Privacy Protection for Role-Based 3. Secret sharing scheme can be applied to each ID class of Access Control in Service Oriented Architecture. International Journal the tree T if this class consists of several elements. of Network Security & Its Applications (IJNSA). 2014. Vol. 6, No. 3. DOI: 10.5121/ijnsa.2014.6301. The cryptographic protocols for the practical use of the [3] Amini M., Arasteh M. A combination of semantic and attribute-based HBAKD algorithm are offered. The main one is "Key-change" access control model for virtual organizations. International Journal of protocol (fig. 2). The possible attacks on these protocols are Information Security. 2015. Vol. 7, Issue 1. P. 27-45. DOI: analyzed. The additional safety measures which are put in 10.22042/ISECURE.2015.7.1.4. protocols are proved (tab. III). [4] Shi S., Xu C. Design and Implementation of a Role-Based Access Control for Categorized Resource in Smart Community Systems. Cloud The conditions of the implementation of the discretionary Computing and Big Data (CCBD). 2016. 7th International Conference. and mandatory principles of the access control on the basis of DOI: 10.1109/CCBD.2016.044. the HBAKD algorithm are formulated. It is supposed that the [5] Mallare I.J.G., Pancho-Festin S. Combining Task- and Role-Based set of the objects is partially ordered and the access to any Access Control with Multi-Constraints for a Medical Workflow System. IT Convergence and Security (ICITCS). 2013. International Conference. object is possible only sequentially from the "parent" object to DOI: 10.1109/ICITCS.2013.6717814. the "child" object. It is proved that the implementation of the [6] Mitra B., Sural S., Atluri V., Vaidya J. The generalized temporal role mandatory and discretionary models of the access control is mining problem. Journal of Computer Security. 2015. Vol. 23, Issue 1. possible for a tree-like object hierarchy in the case of the P. 31–58. URL: https://dl.acm.org/citation.cfm?id=2746190. execution of the conditions which are listed in table IV (IDS is [7] Mitra B., Sural S., Vaidya J., Atluri V. A Survey of Role Mining. ACM the set of the identifiers of the objects which are accessible for Computing Surveys (CSUR). 2016. Vol. 48, No. 4. P. 1–37. DOI: the subject S). 10.1145/2871148. [8] Huang H., Shang F., Liu J., Du H. Handling least privilege problem and role mining in RBAC. Journal of Combinatorial Optimization. 2014. VI. CONCLUSIONS Vol. 30, Issue 1. P. 63–86. DOI: 10.1007/s10878-013-9633-9. Some problems which are important for the effective work [9] Zhang W., Chen Y., Gunter C., Liebovitz D., Malin B. Evolving role of an access control policy in a LIS have been discussed. The definitions through permission invocation patterns. Proceedings of the 18th ACM symposium on Access control models and technologies. solution of these problems significantly depended on the 2013. P. 37–48. DOI: 10.1145/2462410.2462422. structure of the hierarchy of the system's entities. A special [10] Liu C., Peng Z., Wu L. Role of Time-Domain Based Access Control attention has been paid to the RBAC model. The general Model. Journal of Software Engineering and Applications. 2016. Vol. 9, concept of the local optimization of the RBAC model has been No. 2. DOI: 10.4236/jsea.2016.92004. formulated. This process consists in the equivalent conversions [11] Bogaerts J., Lagaisse L., Joosen W. Idea: Supporting Policy-Based of a role graph. The equivalent conversions make the minimum Access Control on Database Systems. In: Caballero J., Bodden E., changes to the main sets and mappings of the RBAC model Athanasopoulos E. (eds) Engineering Secure Software and Systems. ESSoS 2016. Lecture Notes in Computer Science, vol 9639. Springer, and increase the efficiency of the functioning of the system due Cham. DOI: 10.1007/978-3-319-30806-7_16. to the coercion of the role hierarchy to the required look. The [12] Tang Z., Wei J., Sallam A., Li K., Li R. A New RBAC Based Access tools which can execute the specified conversions of the RBAC Control Model for Cloud Computing. In: Li R., Cao J., Bourgeois J. model have been developed. On the basis of optimization (eds) Advances in Grid and Pervasive Computing. 2012. Lecture Notes algorithms the methods of the creation and of the supporting of in Computer Science. Vol. 7296. Springer, Berlin, Heidelberg. DOI: the access control policy in a LIS have been obtained. The 10.1007/978-3-642-30767-6_24. correctness of the offered approaches, methods and algorithms [13] Li W., Wan H., Ren X., Li S. A Refined RBAC Model for Cloud Computing. Computer and Information Science (ICIS). 2012. has been confirmed by the rigorous mathematical proofs and IEEE/ACIS 11th International Conference. DOI: 10.1109/ICIS.2012.13. by the results of the computing experiments. [14] Bogachenko N.F. Local Optimization of the Role-Based Access Control Policy. CEUR Workshop Proceedings. 2017. Vol. 1965. URL: http://ceur-ws.org/Vol-1965/paper14.pdf. TABLE III. THE ADDITIONAL SAFETY MEASURES OF THE “KEY-CHANGE” PROTOCOL [15] Belim S., Bogachenko N., Ilushechkin E. An analysis of graphs that represent a role-based security policy hierarchy. Journal of Computer Possible attacks Safety measures Security. 2015. V. 23, No. 5. P. 641–657. DOI: 10.3233/JCS-150532. Interception of the message "Key-change"; substitution of the “child” [16] Belim S.V., Bogachenko N.F. Distribution of Cryptographic Keys in Step 2 of the protocol Systems with a Hierarchy of Objects. Automatic Control and Computer Sending the false message "Key-change"; substitution of the "parent" Sciences. 2016. Vol. 50, No. 8. P. 777–786. DOI: 10.3103/S0146411616080071. 14