Managing RBAC states with transitive relations

ABSTRACT

In this paper, we study the maintenance of role-based access control (RBAC) models in database environments using transitive closure relations. In particular, the algorithms that express and remove redundancy from a component, a RBAC state, and from conflict constraints. The transitive closure relations on a RBAC state specify the reachability among user groups, roles and from user groups to roles. These relations can assist the process of authorization and make some queries easier to answer. Paper [17] shows that the transitive closure relations on a RBAC model can be used to manage and maintain the model's dynamic changes in a simple and efficient way. In this paper, we firstly show that the transitive closure relations are natural byproducts when formulating RBAC components. We then adapt the conventional RBAC model to accord the inherent reachability of a RBAC model. We show that the use of transitive closure relations as the auxiliary relations for the maintenance of a RBAC state alleviates the process of query evaluation, removing redundancy and the description of hierarchies. Thirdly, in the presence of conflict constraints, we explain how conflicts can be expressed, checked and evaluated under the existence of TC relations, in addition to the removal of conflicts redundancy and finding inferred conflicts. Lastly, we briefly discuss the first-order maintenance operations.All the algorithms for the maintenance are first-order algorithms with simple structures and can be implemented in SQL.

REFERENCES

• 1: A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM J. Comput., 1(2):131--137, 1972.
• 2: ANSI. American national standard for information technology - role based access control. In ANSI INCITS 359--2004, 2004.
• 3: Jason Crampton, On permissions, inheritance and role hierarchies, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948123]
• 4: C. Demetrescu , G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n/sup 2/) barrier, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.381, November 12-14, 2000
• 5: Guozhu Dong , Chaoyi Pang, Maintaining transitive closure in first order after node-set and edge-set deletions, Information Processing Letters, v.62 n.4, p.193-199, May 28, 1997 [doi>10.1016/S0020-0190(97)00066-5]
• 6: Guozhu Dong , Rodney W. Topor, Incremental Evaluation of Datalog Queries, Proceedings of the 4th International Conference on Database Theory, p.282-296, October 14-16, 1992
• 7: Kousha Etessami, Dynamic tree isomorphism via first-order updates to a relational database, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.235-243, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275514]
• 8: David F. Ferraiolo , Ravi Sandhu , Serban Gavrila , D. Richard Kuhn , Ramaswamy Chandramouli, Proposed NIST standard for role-based access control, ACM Transactions on Information and System Security (TISSEC), v.4 n.3, p.224-274, August 2001 [doi>10.1145/501978.501980]
• 9: Phillip Gibbons , Richard Karp , Vijaya Ramachandran , Danny Soroker , Robert Tarjan, Transitive compaction in parallel via branchings, Journal of Algorithms, v.12 n.1, p.110-125, March 1991 [doi>10.1016/0196-6774(91)90026-U]
• 10: Stéphane Grumbach , Jianwen Su, First-order Definability over Constraint Databases, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.121-136, September 19-22, 1995
• 11: Xiaofeng Han , Pierre Kelsen , Vijaya Ramachandran , Robert Tarjan, Computing Minimal Spanning Subgraphs in Linear Time, SIAM Journal on Computing, v.24 n.6, p.1332-1358, Dec. 1995 [doi>10.1137/S0097539791224509]
• 12: Trent Jaeger , Jonathon E. Tidswell, Practical safety in flexible access control models, ACM Transactions on Information and System Security (TISSEC), v.4 n.2, p.158-190, May 2001 [doi>10.1145/501963.501966]
• 13: Sushil Jajodia , Pierangela Samarati , Maria Luisa Sapino , V. S. Subrahmanian, Flexible support for multiple access control policies, ACM Transactions on Database Systems (TODS), v.26 n.2, p.214-260, June 2001 [doi>10.1145/383891.383894]
• 14: Matunda Nyanchama , Sylvia Osborn, The role graph model and conflict of interest, ACM Transactions on Information and System Security (TISSEC), v.2 n.1, p.3-33, Feb. 1999 [doi>10.1145/300830.300832]
• 15: Sylvia Osborn , Yuxia Guo, Modeling users in role-based access control, Proceedings of the fifth ACM workshop on Role-based access control, p.31-37, July 26-28, 2000, Berlin, Germany [doi>10.1145/344287.344299]
• 16: Chaoyi Pang , Guozhu Dong , Kotagiri Ramamohanarao, Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL, ACM Transactions on Database Systems (TODS), v.30 n.3, p.698-721, September 2005 [doi>10.1145/1093382.1093384]
• 17: C. Pang, X. Zhang, Y. Zhang, and K. Ramamohanarao. Maintenance of access roles in sql. In Technical Report, 2005.
• 18: Joon S. Park , Keith P. Costello , Teresa M. Neven , Josh A. Diosomito, A composite rbac approach for large, complex organizations, Proceedings of the ninth ACM symposium on Access control models and technologies, June 02-04, 2004, Yorktown Heights, New York, USA [doi>10.1145/990036.990063]
• 19: Sushant Patnaik , Neil Immerman, Dyn-FO (preliminary version): a parallel, dynamic complexity class, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.210-221, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182614]
• 20: Ravi S. Sandhu , Edward J. Coyne , Hal L. Feinstein , Charles E. Youman, Role-Based Access Control Models, Computer, v.29 n.2, p.38-47, February 1996 [doi>10.1109/2.485845]
• 21: Basit Shafiq , James B. D. Joshi , Elisa Bertino , Arif Ghafoor, Secure Interoperation in a Multidomain Environment Employing RBAC Policies, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1557-1577, November 2005 [doi>10.1109/TKDE.2005.185]
• 22: Mohamed Shehab , Elisa Bertino , Arif Ghafoor, SERAT: SEcure role mApping technique for decentralized secure interoperability, Proceedings of the tenth ACM symposium on Access control models and technologies, June 01-03, 2005, Stockholm, Sweden [doi>10.1145/1063979.1064007]
• 23: Richard Simon , Mary Ellen Zurko, Separation of Duty in Role-based Environments, Proceedings of the 10th IEEE workshop on Computer Security Foundations, p.183, June 10-12, 1997
• 24: He Wang , Sylvia L. Osborn, Delegation in the role graph model, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA [doi>10.1145/1133058.1133072]
• 25: Duminda Wijesekera , Sushil Jajodia , Francesco Parisi-Presicce , Åsa Hagström, Removing permissions in the flexible authorization framework, ACM Transactions on Database Systems (TODS), v.28 n.3, p.209-229, September 2003 [doi>10.1145/937598.937599]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

Keywords:
data integration, directed acyclic graph (DAG), distributed database, graph theory, redundant, role-based access control