Towards an efficient and language-agnostic compliance checker for trust negotiation systems

ABSTRACT

To ensure that a trust negotiation succeeds whenever possible, authorization policy compliance checkers must be able to find all minimal sets of their owners' credentials that can be used to satisfy a given policy. If all of these sets can be found efficiently prior to choosing which set should be disclosed, many strategic benefits can also be realized. Unfortunately, solving this problem using existing compliance checkers is too inefficient to be useful in practice. Specifically, the overheads of finding all satisfying sets using existing approaches have been shown to rapidly grow exponentially in the size of the union of all satisfying sets of credentials for the policy, even after optimizations have been made to prune the search space for potential satisfying sets.

In this paper, we describe the Clouseau compliance checker. Clouseau leverages efficient pattern-matching algorithms to find all satisfying sets of credentials for a given policy in time that grows as O(NA), where N is the number of satisfying sets for the policy and A is the average size of each satisfying set. We describe the design and implementation of the Clouseau compliance checker, evaluate its performance, and show that it vastly outperforms existing approaches to finding all satisfying sets of credentials. We then present a method for automatically compiling RT policies into a format suitable for analysis by Clouseau and prove its correctness and completeness.

REFERENCES

• 1: Lujo Bauer , Scott Garriss , Michael K. Reiter, Distributed Proving in Access-Control Systems, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.81-95, May 08-11, 2005 [doi>10.1109/SP.2005.9]
• 2: M. Y. Becker. A formal security policy for an NHS electronic health record service. Technical Report UCAM-CL-TR-628, University of Cambridge Computer Laboratory, Mar. 2005.
• 3: Cassandra: Distributed Access Control Policies with Tunable Expressiveness, Proceedings of the Fifth IEEE International Workshop on Policies for Distributed Systems and Networks, p.159, June 07-09, 2004
• 4: E. Bertino , E. Ferrari , A. Squicciarini, X -TNL: An XML-based Language for Trust Negotiations, Proceedings of the 4th IEEE International Workshop on Policies for Distributed Systems and Networks, p.81, June 04-06, 2003
• 5: Trust-X: A Peer-to-Peer Framework for Trust Establishment, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.827-842, July 2004 [doi>10.1109/TKDE.2004.1318565]
• 6: M. Blaze , J. Feigenbaum , J. Ioannidis , A. Keromytis, The KeyNote Trust-Management System Version 2, RFC Editor, 1999
• 7: Matt Blaze , Joan Feigenbaum , Jack Lacy, Decentralized Trust Management, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.164, May 06-08, 1996
• 8: Matt Blaze , Joan Feigenbaum , Martin Strauss, Compliance Checking in the PolicyMaker Trust Management System, Proceedings of the Second International Conference on Financial Cryptography, p.254-274, February 23-25, 1998
• 9: Piero Bonatti , Pierangela Samarati, Regulating service access and information release on the Web, Proceedings of the 7th ACM conference on Computer and communications security, p.134-143, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352620]
• 10: Kevin Borders , Xin Zhao , Atul Prakash, CPOL: high-performance policy evaluation, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102142]
• 11: Yang-Hua Chu , Joan Feigenbaum , Brian LaMacchia , Paul Resnick , Martin Strauss, Referee: trust management for Web applications, World Wide Web Journal, v.2 n.3, p.127-139, Summer 1997
• 12: Nicodemos Damianou , Naranker Dulay , Emil Lupu , Morris Sloman, The Ponder Policy Specification Language, Proceedings of the International Workshop on Policies for Distributed Systems and Networks, p.18-38, January 29-31, 2001
• 13: C. L. Forgy. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence, 27(3):219--227, 1985.
• 14: E. Friedman-Hill. Jess: The rule engine for the Java platform. Web site, Apr. 2007. (http://www.jessrules.com).
• 15: Amir Herzberg , Yosi Mass , Joris Michaeli , Yiftach Ravid , Dalit Naor, Access Control Meets Public Key Infrastructure, Or: Assigning Roles to Strangers, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.2, May 14-17, 2000
• 16: H. Koshutanski and F. Massacci. An interactive trust management and negotiation scheme. In Proceedings of the Second International Workshop on Formal Aspects in Security and Trust (FAST), pages 139--152, Aug. 2004.
• 17: A. J. Lee and M. Winslett. Towards an efficient and language-agnostic compliance checker for trust negotiation systems. Technical Report UIUCDCS-R-2007-2903, University of Illinois at Urbana Champaign Department of Computer Science, Oct. 2007.
• 18: Jiangtao Li , Ninghui Li , William H. Winsborough, Automated trust negotiation using cryptographic credentials, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102129]
• 19: Ninghui Li , John C. Mitchell , William H. Winsborough, Design of a Role-Based Trust-Management Framework, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.114, May 12-15, 2002
• 20: D. P. Miranker. TREAT: A better match algorithm for AI production systems. In Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI-87), pages 42--47, Aug. 1987.
• 21: K. Seamons , M. Winslett , T. Yu , B. Smith , E. Child , J. Jacobson , H. Mills , L. Yu, Requirements for Policy Languages for Trust Negotiation, Proceedings of the 3rd International Workshop on Policies for Distributed Systems and Networks (POLICY'02), p.68, June 05-07, 2002
• 22: Responding to Policies at Runtime in TrustBuilder, Proceedings of the Fifth IEEE International Workshop on Policies for Distributed Systems and Networks, p.149, June 07-09, 2004
• 23: N. Li , W. Winsborough, Towards Practical Automated Trust Negotiation, Proceedings of the 3rd International Workshop on Policies for Distributed Systems and Networks (POLICY'02), p.92, June 05-07, 2002
• 24: W. H. Winsborough, K. E. Seamons, and V. E. Jones. Automated trust negotiation. In Proceedings of the DARPA Information Survivability Conference and Exposition, pages 88--102, Jan. 2000.
• 25: Marianne Winslett , Ting Yu , Kent E. Seamons , Adam Hess , Jared Jacobson , Ryan Jarvis , Bryan Smith , Lina Yu, Negotiating Trust on the Web, IEEE Internet Computing, v.6 n.6, p.30-37, November 2002 [doi>10.1109/MIC.2002.1067734 ]
• 26: Marianne Winslett , Charles C. Zhang , Piero A. Bonatti, PeerAccess: a logic for distributed authorization, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102144]
• 27: D. Yao, K. Frikken, M. Atallah, and R. Tamassia. Point-based trust: Define how much privacy is worth. In Proceedings of the Eighth International Conference on Information and Communications Security (ICICS '06), number 4307 in Lecture Notes in Computer Science, pages 190--209. Springer, 2006.
• 28: Ting Yu , Marianne Winslett , Kent E. Seamons, Supporting structured credentials and sensitive policies through interoperable strategies for automated trust negotiation, ACM Transactions on Information and System Security (TISSEC), v.6 n.1, p.1-42, February 2003 [doi>10.1145/605434.605435]

INDEX TERMS

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

Additional Classification:
  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:
Algorithms, Performance, Security

Keywords:
compliance checker, policy, satisfying sets, trust negotiation