A Survey of GraphBased RBAC Efficiency Barry Wittman CS526 Research Project Introduction RBAC has gained a lot of popularity in the access control research world Most papers discuss the power of various versions of RBAC in terms of security capabilities What are the complexity and performance issues Overview Basic Operations Conflicting Privileges Multidomain Policy Integration Safety Information Flow Conclusions Basic Operations Add User We examine the hierarchical framework discussed by Koch et al in 5 and 9 We look at all the basic operations and try to find the minimum time for an operation based on an adjacency list implementation Remove User O U O S R R O 1 amortized Add User to Role Remove User from Role O R O S R R O S amortized Add Session Remove Session O 1 O R O 1 amortized R is the set of roles U is the set of all users S is the set of active sessions t p is the upper bound on the number of operations it takes to determine if a role has permission p Add Role Remove Role O R O S R U O 1 amortized Activate Role Deactivate Role O R 2 O R O 1 amortized Add Inheritance O R Remove Inheritance O R O 1 amortized Check Permission O S R R 2 R t p Conflicting Privileges We examine the algorithms introduced by Nyanchama and Osborn 13 which take into account conflicting privileges R is the set of roles P is the set of all permissions RoleAddition1 O R 2 P R P 2 RoleAddition2 O R P 2 PrivilegeAddition O R P 2 RoleDeletion O R 2 R P log P PrivilegeDeletion O R P EdgeInsertion O R P 2 EdgeDeletion O R 2 P R P log P Multidomain Policy Integration Shafiq et al 1 introduce a framework in which different domains with different RBAC policies can integrate their policies to allow for secure interoperation To find the optimum assignment of roles to users an integer programming problem must be solved Unfortunately this problem is NP hard but can be approximated There is no generic approximation bound on IP problems Safety Koch et al 8 describe a graph based RBAC formulation whose safety can be checked The model has very similar expressive power to the Take Grant model The decidability algorithm is exponential Information Flow MAC models are heavily concerned with the flow of information Some work has been done to analyze information flow in RBAC as well particularly by 14 Analysis is based on two algorithms FlowStart O R P 2 CanFlow O n3 Conclusions Basic Operations At least a simple implementation of graph based RBAC can be quite efficient Conflicting Permissions The algorithms provided by 13 have serious performance problems since most operations require checking every permission in the entire system Multidomain Policy Integration The approximation of the IP problem warrants further study Although it is beyond the scope of this work an approximation bound hopefully constant for the IP should be found Safety The time taken to determine safety with the current algorithm is exponential Work should be done to see if a more efficient algorithm is possible or if the problem is NP complete Information Flow The information flow algorithms have a P 2 term in them However this is a worst case value that will seldom actually be seen Likewise information flow analysis does not necessarily need to be done in real time References 1 Secure interoperation in a multidomain environment employing RBAC policies IEEE Transactions on Knowledge and Data Engineering 17 11 1557 1577 2005 Student Member Basit Shafiq and Member James B D Joshi and FellowElisa Bertino and Fellow Arif Ghafoor 2 D F Ferraiolo R Sandhu S Gavrila D R Kuhn and R Chandramouli Proposed NIST standard for role based access control ACM Trans Inf Syst Secur 4 3 224 274 2001 3 L Giuri and P Iglio A formal model for role based access control with constraints In CSFW 96 Proceedings of the Ninth IEEE Computer Security Foundations Workshop page 136 Washington DC USA 1996 IEEE Computer Society 4 F Glover and M Laguna Tabu Search Kluwer Academic Publishers Dordrecht The Netherlands 1998 5 M Koch L V Mancini and F Parisi Presicce A formal model for role based access control using graph transformation In ESORICS 00 Proceedings of the 6th European Symposium on Research in Computer Security pages 122 139 London UK 2000 Springer Verlag 6 M Koch L V Mancini and F Parisi Presicce Foundations for a graph based approach to the specification of access control policies In FoSSaCS 01 Proceedings of the 4th International Conference on Foundations of Software Science and Computation Structures pages 287 302 London UK 2001 Springer Verlag 7 M Koch L V Mancini and F Parisi Presicce Conflict detection and resolution in access control policy specifications In FoSSaCS 02 Proceedings of the 5th International Conference on Foundations of Software Science and Computation Structures pages 223 237 London UK 2002 Springer Verlag 8 M Koch L V Mancini and F Parisi Presicce Decidability of safety in graph based models for access control In ESORICS 02 Proceedings of the 7th European Symposium on Research in Computer Security pages 229 243 London UK 2002 Springer Verlag References cont 9 M Koch L V Mancini and F Parisi Presicce A graph based formalism for RBAC ACM Trans Inf Syst Secur 5 3 332 365 2002 10 M Koch L V Mancini and F Parisi Presicce Administrative scope in the graph based framework In SACMAT 04 Proceedings of the ninth ACM symposium on Access control models and technologies pages 97 104 New York NY USA 2004 ACM Press 11 M Koch L V Mancini and F Parisi Presicce Graph based specification of access control policies J Comput Syst Sci 71 1 1 33 2005 12 G L Nemhauser and L A Wolsey Integer and Combinatorial Optimization Wiley Interscience Series in Discrete Mathematics and Optimization Wiley 1988 NEM g 88 1 P Ex 13 M Nyanchama and S Osborn The role graph model and conflict of interest ACM Trans Inf Syst Secur 2 1 3 33 1999 14 S L Osborn Information flow analysis of an RBAC system In SACMAT 02 Proceedings of the seventh ACM symposium on Access control models and technologies pages 163 168 New York NY USA 2002 ACM Press 15 R S Sandhu E J Coyne H L Feinstein and C E Youman Rolebased access control models Computer 29 2 38 47 1996