Efficient policy analysis for administrative role based access control

ABSTRACT

Administrative RBAC (ARBAC) policies specify how Role-Based Access Control (RBAC) policies may be changed by each administrator. It is often difficult to fully understand the effect of an ARBAC policy by simple inspection, because sequences of changes by different administrators may interact in unexpected ways. ARBAC policy analysis algorithms can help by answering questions, such a suser-role reachability, which asks whether a given user can be assigned to given roles by given administrators. This problem is intractable in general. This paper identifies classes of policies of practical interest, develops analysis algorithms for them, and analyzes their parameterized complexity, showing that the algorithms may have high complexity with respect to some parameter k characterizing the hardness of the input (such that k is often small in practice) but have polynomial complexity in terms of the overall input size when the value of k is fixed.

REFERENCES

• 1: American National Standards Institute (ANSI), International Committee for Information Technology Standards (INCITS). Role-based access control. ANSI INCITS Standard 359-2004, Feb. 2004.
• 2: Arosha K. Bandara , Emil C. Lupu , Alessandra Russo, Using Event Calculus to Formalise Policy Specification and Analysis, Proceedings of the 4th IEEE International Workshop on Policies for Distributed Systems and Networks, p.26, June 04-06, 2003
• 3: M. Y. Becker. Cassandra: Flexible Trust Management and its Application to Electronic Health Records. PhD thesis, University of Cambridge, Oct. 2005.
• 4: Edmund M. Clarke, Jr. , Orna Grumberg , Doron A. Peled, Model checking, MIT Press, Cambridge, MA, 2000
• 5: Jason Crampton, Understanding and developing role-based administrative models, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102143]
• 6: Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
• 7: Mark Evered , Serge Bögeholz, A case study in access control requirements for a Health Information System, Proceedings of the second workshop on Australasian information security, Data Mining and Web Intelligence, and Software Internationalisation, p.53-61, January 01, 2004, Dunedin, New Zealand
• 8: Kathi Fisler , Shriram Krishnamurthi , Leo A. Meyerovich , Michael Carl Tschantz, Verification and change-impact analysis of access-control policies, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062502]
• 9: Patrice Godefroid , J. van Leeuwen , J. Hartmanis , G. Goos , Pierre Wolper, Partial-Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 10: Joshua D. Guttman , Amy L. Herzog , John D. Ramsdell , Clement W. Skorupka, Verifying information flow goals in security-enhanced Linux, Journal of Computer Security, v.13 n.1, p.115-134, January 2005
• 11: J. Y. Halpern and V. Weissman. Using first-order logic to reason about policies. In Proc. 16th IEEE Computer Security Foundations Workshop (CSFW), pages 187--201. IEEE Computer Society Press, 2003.
• 12: Michael A. Harrison , Walter L. Ruzzo , Jeffrey D. Ullman, Protection in operating systems, Communications of the ACM, v.19 n.8, p.461-471, Aug. 1976 [doi>10.1145/360303.360333]
• 13: Keith Irwin , Ting Yu , William H. Winsborough, On the modeling and analysis of obligations, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180423]
• 14: Daniel Jackson , Ian Schechter , Hya Shlyahter, Alcoa: the alloy constraint analyzer, Proceedings of the 22nd international conference on Software engineering, p.730-733, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337616]
• 15: Sushil Jajodia , Pierangela Samarati , V. S. Subrahmanian, A Logical Language for Expressing Authorizations, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.31, May 04-07, 1997
• 16: S. Jha , T. Reps, Model checking SPKI/SDSI, Journal of Computer Security, v.12 n.3,4, p.317-353, May 2004
• 17: Axel Kern , Andreas Schaad , Jonathan Moffett, An administration concept for the enterprise role-based access control model, Proceedings of the eighth ACM symposium on Access control models and technologies, June 02-03, 2003, Como, Italy [doi>10.1145/775412.775414]
• 18: Ninghui Li , Ziqing Mao, Administration in role-based access control, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore [doi>10.1145/1229285.1229305]
• 19: Ninghui Li , John C. Mitchell , William H. Winsborough, Beyond proof-of-compliance: security analysis in trust management, Journal of the ACM (JACM), v.52 n.3, p.474-514, May 2005 [doi>10.1145/1066100.1066103]
• 20: Ninghui Li , Mahesh V. Tripunitara, Security analysis in role-based access control, ACM Transactions on Information and System Security (TISSEC), v.9 n.4, p.391-420, November 2006 [doi>10.1145/1187441.1187442]
• 21: Richard J. Lipton, Reduction: a method of proving properties of parallel programs, Communications of the ACM, v.18 n.12, p.717-721, Dec. 1975 [doi>10.1145/361227.361234]
• 22: R. J. Lipton , L. Snyder, A Linear Time Algorithm for Deciding Subject Security, Journal of the ACM (JACM), v.24 n.3, p.455-464, July 1977 [doi>10.1145/322017.322025]
• 23: Sejong Oh , Ravi Sandhu, A model for role administration using organization structure, Proceedings of the seventh ACM symposium on Access control models and technologies, June 03-04, 2002, Monterey, California, USA [doi>10.1145/507711.507737]
• 24: Ravi S. Sandhu, The Typed Access Matrix Model, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.122, May 04-06, 1992
• 25: Ravi Sandhu , Venkata Bhamidipati , Qamar Munawer, The ARBAC97 model for role-based administration of roles, ACM Transactions on Information and System Security (TISSEC), v.2 n.1, p.105-135, Feb. 1999 [doi>10.1145/300830.300839]
• 26: 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]
• 27: Amit Sasturkar , Ping Yang , Scott D. Stoller , C. R. Ramakrishnan, Policy Analysis for Administrative Role Based Access Control, Proceedings of the 19th IEEE workshop on Computer Security Foundations, p.124-138, July 05-07, 2006 [doi>10.1109/CSFW.2006.22]
• 28: Andreas Schaad , Jonathan Moffett , Jeremy Jacob, The role-based access control system of a European bank: a case study and discussion, Proceedings of the sixth ACM symposium on Access control models and technologies, p.3-9, May 2001, Chantilly, Virginia, United States [doi>10.1145/373256.373257]
• 29: Andreas Schaad , Jonathan D. Moffett, A lightweight approach to specification and analysis of role-based access control extensions, Proceedings of the seventh ACM symposium on Access control models and technologies, June 03-04, 2002, Monterey, California, USA [doi>10.1145/507711.507714]
• 30: A. P. Sistla and M. Zhou. Analysis of dynamic policies. In Joint Workshop on Foundations of Computer Security and Automated Reasoning for Security Protocol Analysis (FCS-ARSPA), Aug. 2006. Full version to appear in Information & Computation.
• 31: www.cs.stonybrook.edu/~stoller/ccs2007/.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

General Terms:
Security