Abstract
In trust negotiation and other forms of distributed proving, networked entities cooperate to form proofs of authorization that are justified by collections of certified attribute credentials. These attributes may be obtained through interactions with any number of external entities and are collected and validated over an extended period of time. Although these collections of credentials in some ways resemble partial system snapshots, current trust negotiation and distributed proving systems lack the notion of a consistent global state in which the satisfaction of authorization policies should be checked. In this article, we argue that unlike the notions of consistency studied in other areas of distributed computing, the level of consistency required during policy evaluation is predicated solely upon the security requirements of the policy evaluator. As such, there is little incentive for entities to participate in complicated consistency preservation schemes like those used in distributed computing, distributed databases, and distributed shared memory. We go on to show that the most intuitive notion of consistency fails to provide basic safety guarantees under certain circumstances and then propose several more refined notions of consistency that provide stronger safety guarantees. We provide algorithms that allow each of these refined notions of consistency to be attained in practice with minimal overheads and formally prove several security and privacy properties of these algorithms. Lastly, we explore the notion of strategic design trade-offs in the consistency enforcement algorithm space and propose several modifications to the core algorithms presented in this article. These modifications enhance the privacy-preservation or completeness properties of these algorithms without altering the consistency constraints that they enforce.
- Adve, S. V. and Gharachorloo, K. 1996. Shared memory consistency models: A tutorial. IEEE Comput. 66--76. Google ScholarDigital Library
- Babaoğlu, O. and Marzullo, K. 1993. Consistent global states of distributed systems: Fundamental concepts and mechanisms. In Distributed Systems, S. J. Mullender, ed. Addison-Wesley, 55--96. Also available as University of Bologna Tech. rep. UBLCS-93-1 at http://www.cs.unibo.it/pub/TR/UBLCS/1993/93-01.ps.gz.Google Scholar
- Bauer, L., Garriss, S., and Reiter, M. K. 2005. Distributed proving in access-control systems. In Proceedings of the IEEE Symposium on Security and Privacy (SSP’05). 81--95. Google ScholarDigital Library
- Becker, M. Y. and Sewell, P. 2004. Cassandra: Distributed access control policies with tunable expressiveness. In Proceedings of the 5th IEEE International Workshop on Policies for Distributed Systems and Networks (NDSS’04). 159--168. Google ScholarDigital Library
- Bertino, E., Ferrari, E., and Squicciarini, A. C. 2004. Trust-X: A peer-to-peer framework for trust establishment. IEEE Trans. Knowl. Data Eng. 16, 7, 827--842. Google ScholarDigital Library
- Bonatti, P. and Samarati, P. 2000. Regulating service access and information release on the web. In Proceedings of the 7th ACM Conference on Computer and Communications Security (CCS’00). 134--143. Google ScholarDigital Library
- Cellary, W., Gelenbe, E., and Morzy, T. 1988. Concurrency Control in Distributed Database Systems. Elsevier Science Publishing. Google ScholarDigital Library
- Chandy, K. M. and Lamport, L. 1985. Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 1, 63--75. Google ScholarDigital Library
- Cheriton, D. R. and Skeen, D. 1993. Understanding the limitations of causally and totally ordered communication. In Proceedings of the ACM Symposium on Operating Systems Priniciples (SOSP’93). 44--57. Google ScholarDigital Library
- Housely, R., Ford, W., Polk, W., and Solo, D. 1999. Internet X.509 Public Key Infrastructure Certificate and CRL Profile. IETF Request for Comments RFC-2459.Google Scholar
- Irwin, K. and Yu, T. 2005. Preventing attribute information leakage in automated trust negotiation. In Proceedings of the 12th ACM Conference on Computer and Communications Security (CCS’05). 36--45. Google ScholarDigital Library
- Koshutanski, H. and Massacci, F. 2005. Interactive credential negotiation for stateful business processes. In Proceedings of the 3rd International Conference on Trust Management (iTrust’05). 257--273.Google Scholar
- Lamport, L. 1977. Proving the correctness of multiprocess programs. IEEE Trans. Softw. Eng. SE-3, 2, 125--143. Google ScholarDigital Library
- Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 7, 558--565. Google ScholarDigital Library
- Lee, A. J., Minami, K., and Winslett, M. 2007. Lightweight consistency enforcement schemes for distributed proofs with hidden subtrees. In Proceedings of the 12th ACM Symposium on Access Control Models and Technologies (SACMAT’07). 101--110. Google ScholarDigital Library
- Lee, A. J. and Winslett, M. 2006. Safety and consistency in policy-based authorization systems. In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS’06). 124--133. Google ScholarDigital Library
- Li, J., Li, N., and Winsborough, W. H. 2005. Automated trust negotiation using cryptographic credentials. In Proceedings of the 12th ACM Conference on Computer and Communications Security (CCS’05). 46--57. Google ScholarDigital Library
- Li, N. and Mitchell, J. 2003. RT: A role-based trust-management framework. In Proceedings of the 3rd DARPA Information Survivability Conference and Exposition (DISCEX’03). 201--213.Google Scholar
- Merkle, R. C. 1979. Secrecy, authentication, and public key systems. Ph.D. thesis, Stanford University. Google ScholarDigital Library
- Mills, D. L. 1992. Network Time Protocol (Version 3) Specification, Implementation and Analysis. IETF Request for Comments RFC-1305. Google ScholarDigital Library
- Minami, K. and Kotz, D. 2005. Secure context-sensitive authorization. J. Perv. Mob. Comput. 1, 1, 123--156. Google ScholarDigital Library
- Minami, K. and Kotz, D. 2006. Scalability in a secure distributed proof system. In Proceedings of the 4th International Conference on Pervasive Computing (PERVASIVE’06). 220--237.Google Scholar
- Myers, M., Ankney, R., Malpani, A., Glaperin, S., and Adams, C. 1999. X.509 Internet public key infrastructure online certificate status protocol - OCSP. IETF RFC 2560. Google ScholarDigital Library
- Tanenbaum, A. S. and van Steen, M. 2002. Distributed systems: Principles and Paradigms. Prentice Hall, Upper Saddle River, NJ. Google ScholarDigital Library
- Winsborough, W. H. and Li, N. 2002. Towards practical automated trust negotiation. In Proceedings of the 3rd IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY’02). 92--103. Google ScholarDigital Library
- Winsborough, W. H. and Li, N. 2006. Safety in automated trust negotiation. ACM Trans. Inf. Syst. Secur. 9, 3, 352--390. Google ScholarDigital Library
- Winslett, M., Yu, T., Seamons, K. E., Hess, A., Jacobson, J., Jarvis, R., Smith, B., and Yu, L. 2002. Negotiating trust on the web. IEEE Internet Comput. 6, 6, 30--37. Google ScholarDigital Library
- Winslett, M., Zhang, C., and Bonatti, P. A. 2005. PeerAccess: A logic for distributed authorization. In Proceedings of the 12th ACM Conference on Computer and Communications Security (CCS’05). 168--179. Google ScholarDigital Library
- Yu, T., Winslett, M., and Seamons, K. E. 2003. Supporting structured credentials and sensitive policies through interoperable strategies for automated trust negotiation. ACM Trans. Inf. Syst. Secur. 6, 1, 1--42. Google ScholarDigital Library
- Zhou, L., Schneider, F. B., and van Renesse, R. 2002. COCA: A secure distributed online certification authority. ACM Trans. Comput. Syst. 20, 4, 329--368. Google ScholarDigital Library
Index Terms
- Enforcing Safety and Consistency Constraints in Policy-Based Authorization Systems
Recommendations
Safety and consistency in policy-based authorization systems
CCS '06: Proceedings of the 13th ACM conference on Computer and communications securityIn trust negotiation and other distributed proving systems, networked entities cooperate to form proofs that are justi?ed by collections of certi?ed attributes. These attributes may be obtained through interactions with any number of external entities ...
Lightweight consistency enforcement schemes for distributed proofs with hidden subtrees
SACMAT '07: Proceedings of the 12th ACM symposium on Access control models and technologiesIn distributed proof construction systems, information release policies can make it unlikely that any single node in the system is aware of the complete structure of any particular proof tree. This property makes it difficult for queriers to determine ...
Consistency in Non-Transactional Distributed Storage Systems
Over the years, different meanings have been associated with the word consistency in the distributed systems community. While in the ’80s “consistency” typically meant strong consistency, later defined also as linearizability, in recent years, with the ...
Comments