Resiliency Policies in Access Control

ABSTRACT

We introduce the notion of resiliency policies in the context of access control systems. Such policies require an access control system to be resilient to the absence of users. An example resiliency policy requires that upon removal of any s users, there should still exist d disjoint sets of users such that the users in each set together possess certain permissions of interest. Such a policy ensures that even when emergency situations cause some users to be absent, there still exist independent teams of users that have the permissions necessary for carrying out critical tasks. The Resiliency Checking Problem determines whether an access control state satisfies a given resiliency policy. We show that the general case of the problem and several subcases are intractable (NP-hard), and identify two subcases that are solvable in linear time. For the intractable cases, we also identify the complexity class in the polynomial hierarchy to which these problems belong. We discuss the design and evaluation of an algorithm that can efficiently solve instances of nontrivial sizes that belong to the intractable cases of the problem. Furthermore, we study the consistency problem between resiliency policies and static separation of duty policies. Finally, we combine the notions of resiliency and separation of duty to introduce the resilient separation of duty policy, which is useful in situations where both fault-tolerance and fraud-prevention are desired.

REFERENCES

• 1: Gail-Joon Ahn , Ravi Sandhu, Role-based authorization constraints specification, ACM Transactions on Information and System Security (TISSEC), v.3 n.4, p.207-226, Nov. 2000 [doi>10.1145/382912.382913]
• 2: Clark, D. D. and Wilson, D. R. 1987. A comparision of commercial and military computer security policies. In Proceedings of the IEEE Symposium on Security and Privacy (SP’87). IEEE Computer Society Press, 184--194.
• 3: Jason Crampton, Specifying and enforcing constraints in role-based access control, Proceedings of the eighth ACM symposium on Access control models and technologies, June 02-03, 2003, Como, Italy [doi>10.1145/775412.775419]
• 4: Du, D., Gu, J., and Pardalos, P. M., Eds. 1997. Satisfiability problem: Theory and applications. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 35. AMS Press.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: Gligor, V. D., Gavrila, S. I., and Ferraiolo, D. F. 1998. On the formal definition of separation-of-duty policies and their composition. In Proceedings of IEEE Symposium on Research in Security and Privacy (SP’98). 172--183.
• 7: G. Scott Graham , Peter J. Denning, Protection: principles and practice, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada [doi>10.1145/1478873.1478928]
• 8: 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]
• 9: 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]
• 10: Manuel Koch , Luigi V. Mancini , Francesco Parisi-Presicce, Decidability of Safety in Graph-Based Models for Access Control, Proceedings of the 7th European Symposium on Research in Computer Security, p.229-243, October 14-16, 2002
• 11: Manuel Koch , Luigi V. Mancini , Francesco Parisi-Presicce, A graph-based formalism for RBAC, ACM Transactions on Information and System Security (TISSEC), v.5 n.3, p.332-365, August 2002 [doi>10.1145/545186.545191]
• 12: Lampson, B. W. 1971. Protection. In Proceedings of the 5th Princeton Conference on Information Sciences and Systems (CISS’71). (Reprinted in ACM Operat. Syst. Rev. 8, 1, 18--24).
• 13: Le Berre, D. 2006. SAT4J: A satisfiability library for Java. Retrieved from http://www.sat4j.org/.
• 14: Ninghui Li , Ziad Bizri , Mahesh V. Tripunitara, On mutually-exclusive roles and separation of duty, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030091]
• 15: Ninghui Li , William H. Winsborough , John C. Mitchell, Beyond Proof-of-Compliance: Safety and Availability Analysis in Trust Management, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.123, May 11-14, 2003
• 16: Ninghui Li , Mahesh V. Tripunitara, Security analysis in role-based access control, 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.990058]
• 17: 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]
• 18: Nash, M. J. and Poland, K. R. 1990. Some conundrums concerning separation of duty. In Proceedings of IEEE Symposium on Research in Security and Privacy (SP’90). 201--209.
• 19: Papadimitriou, C. H. 1994. Computational Complexity. Addison Wesley Longman.
• 20: Saltzer, J. H. and Schroeder, M. D. 1975. The protection of information in computer systems. Proc. IEEE 63, 9, 1278--1308.
• 21: Sandhu, R. 1990. Separation of duties in computerized information systems. In Proceedings of the International Federation Information Processing WG11.3 Workshop on Database Security (IFIP’90).
• 22: Ravinderpal Singh Sandhu, The schematic protection model: its definition and analysis for acyclic attenuating schemes, Journal of the ACM (JACM), v.35 n.2, p.404-432, April 1988 [doi>10.1145/42282.42286]
• 23: Sandhu, R. S. 1988b. Transaction control expressions for separation of duties. In Proceedings of the 4th Annual Computer Security Applications Conference (ACSAC’88).
• 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 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]
• 26: 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
• 27: Wang, Q. and Li, N. 2007. Satisfiability and resiliency in workflow systems. In Proceedings of the European Symposium on Research in Computer Security (ESORICS’07).

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

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

General Terms:
Security, Theory

Keywords:
Access control, fault-tolerant, policy design