Lightweight cnsistency enforcement schemes for distributed proofs with hidden subtrees

ABSTRACT

In 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 whether the proofs constructed using these protocols sampled a consistent snapshot of the system state; this has previously been shown to have dire consequences in decentralized authorization systems. Unfortunately, the consistency enforcement solutions presented in previous work were designed for systems in which only information encoded in certificates issued by certificate authorities is used during the decision-making process. Further, they assume that each piece of certified evidence used during proof construction is available to the decision-making node at runtime.

In this paper, we generalize these previous results and present lightweight mechanisms through which consistency constraints can be enforced in proof systems in which the full details of a proof may be unavailable to the querier and the existence of certificate authorities for certifying evidence is unlikely; these types of distributed proof systems are likely candidates for use in pervasive computing and sensor network environments. We present modifications to one such distributed proof system that enable two types of consistency constraints to be enforced while still respecting the same confidentiality and integrity policies as the original proof system. Further, we detail a performance analysis that illustrates the modest overheads of our consistency enforcement schemes.

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611 ]
• 2: Jalal Al-Muhtadi , Anand Ranganathan , Roy Campbell , M. Dennis Mickunas, Cerberus: A Context-Aware Security Scheme for Smart Spaces, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.489, March 23-26, 2003
• 3: Özalp Babaoğlu , Keith Marzullo, Consistent global states of distributed systems: fundamental concepts and mechanisms, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 4: Jean Bacon , Ken Moody , Walt Yao, A model of OASIS role-based access control and its support for active security, ACM Transactions on Information and System Security (TISSEC), v.5 n.4, p.492-540, November 2002 [doi>10.1145/581271.581276]
• 5: D. Balenson. Privacy enhancement for internet electronic mail: Part III: Algorithms, modes, and identifiers. IETF RFC 1423, Feb. 1993.
• 6: 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]
• 7: Cassandra: Distributed Access Control Policies with Tunable Expressiveness, Proceedings of the Fifth IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY'04), p.159, June 07-09, 2004
• 8: 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]
• 9: W. Cellary , E. Gelenbe , T. Morzy, Concurrency control in distributed database systems, Elsevier Science Inc., New York, NY, 1988
• 10: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 11: Michael J. Covington , Wende Long , Srividhya Srinivasan , Anind K. Dev , Mustaque Ahamad , Gregory D. Abowd, Securing context-aware applications using environment roles, Proceedings of the sixth ACM symposium on Access control models and technologies, p.10-20, May 2001, Chantilly, Virginia, United States [doi>10.1145/373256.373258]
• 12: Data Encryption Standard (DES). Federal Information Processing Standard FIPS PUB 46-3, October 1999.
• 13: A. J. Lee, K. Minami, and M. Winslett. Lightweight consistency enforcement schemes for distributed proofs with hidden subtrees (extended version). Technical Report UIUCDCS-R-2007-2839, University of Illinois at Urbana-Champaign Department of Computer Science, Apr. 2007.
• 14: Adam J. Lee , Marianne Winslett, Safety and consistency in policy-based authorization systems, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180422]
• 15: 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]
• 16: Patrick McDaniel, On context in authorization policy, Proceedings of the eighth ACM symposium on Access control models and technologies, June 02-03, 2003, Como, Italy [doi>10.1145/775412.775422]
• 17: Kazuhiro Minami , David Kotz, Secure context-sensitive authorization, Pervasive and Mobile Computing, v.1 n.1, p.123-156, March 2005 [doi>10.1016/j.pmcj.2005.01.004]
• 18: K. Minami and D. Kotz. Scalability in a secure distributed proof system. In Proceedings of the Fourth International Conference on Pervasive Computing(Pervasive), May 2006.
• 19: M. Myers, R. Ankney, A. Malpani, S. Galperin, and C. Adams. X.509 internet public key infrastructure online certificate status protocol - OCSP. IETF RFC2560, June 1999.
• 20: Ginger Myles , Adrian Friday , Nigel Davies, Preserving Privacy in Environments with Location-Based Applications, IEEE Pervasive Computing, v.2 n.1, p.56-64, January 2003 [doi>10.1109/MPRV.2003.1186726 ]
• 21: R. L. Rivest. The MD5 message-digest algorithm. IETF RFC 1321, Apr. 1992.
• 22: Andrew S. Tanenbaum , Maarten Van Steen, Distributed Systems: Principles and Paradigms, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 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: 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]
• 25: 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]
• 26: Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002 [doi>10.1145/571637.571638]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

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

  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

Keywords:
consistency, distributed proving, pervasive computing