Lightweight consistency 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. S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, pages 66--76, Dec. 1996.
2. J. Al-Muhtadi, A. Ranganathan, R. Campbell, and D. Mickunas. Cerberus: a context-aware security scheme for smart spaces. In Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, pages 489--496. IEEE Computer Society, March 2003.
3. O. Babaoğlu and K. Marzullo. Consistent global states of distributed systems: Fundamental concepts and mechanisms. In S. J. Mullender, editor, Distributed Systems, pages 55--96. Addison-Wesley, 1993.
4. J. Bacon, K. Moody, and W. Yao. A model of OASIS role-based access control and its support for active security. ACM Transactions on Information and System Security, 5(4):492--540, 2002.
5. D. Balenson. Privacy enhancement for internet electronic mail: Part III: Algorithms, modes, and identifiers. IETF RFC 1423, Feb. 1993.
6. L. Bauer, S. Garriss, and M. K. Reiter. Distributed proving in access-control systems. In Proceedings of the 2005 IEEE Symposium on Security and Privacy, pages 81--95, 2005.
7. M. Y. Becker and P. Sewell. Cassandra: distributed access control policies with tunable expressiveness. In Proceedings of the 5th IEEE International Workshop on Policies for Distributed Systems and Networks, pages 159--168, June 2004.
8. E. Bertino, E. Ferrari, and A. C. Squicciarini. Trust-X: A peer-to-peer framework for trust establishment. IEEE Transactions on Knowledge and Data Engineering, 16(7):827--842, Jul. 2004.
9. W. Cellary, E. Gelenbe, and T. Morzy. Concurrency Control in Distributed Database Systems. Elsevier Science Publishing Company, Inc., 1988.
10. K. M. Chandy and L. Lamport. Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems, 3(1):63--75, Feb. 1985.
11. M. J. Covington, W. Long, S. Srinivasan, A. K. Dey, M. Ahamad, and G. D. Abowd. Securing context-aware applications using environment roles. In Proceedings of the Sixth ACM Symposium on Access Control Models and Technologies, pages 10--20, 2001.
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. A. J. Lee and M. Winslett. Safety and consistency in policy-based authorization systems. In Proceedings of the 13th ACM Conference on Computer and Communications Security, pages 124--133, Nov. 2006.
15. J. Li, N. Li, and W. H. Winsborough. Automated trust negotiation using cryptographic credentials. In Proceedings of the 12th ACM Conference on Computer and Communications Security, pages 46--57, 2005.
16. P. McDaniel. On context in authorization policy. In Proceedings of the Eighth ACM Symposium on Access Control Models and Technologies (SACMAT 2003), pages 80--89, June 2003.
17. K. Minami and D. Kotz. Secure context-sensitive authorization. Journal of Pervasive and Mobile Computing, 1(1):123--156, Mar. 2005.
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. G. Myles, A. Friday, and N. Davies. Preserving privacy in environments with location-based applications. IEEE Pervasive Computing, 2(1):56--64, January - March 2003.
21. R. L. Rivest. The MD5 message-digest algorithm. IETF RFC 1321, Apr. 1992.
22. A. S. Tanenbaum and M. van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, 2002.
23. W. Winsborough and N. Li. Towards practical automated trust negotiation. In Proceedings of the 3rd International Workshop on Policies for Distributed Systems and Networks (POLICY'02), page 92, 2002.
24. M. Winslett, C. C. Zhang, and P. A. Bonatti. PeerAccess: a logic for distributed authorization. In Proceedings of the 12th ACM Conference on Computer and Communications Security, pages 168--179, 2005.
25. T. Yu, M. Winslett, and K. E. Seamons. Supporting structured credentials and sensitive policies through interoperable strategies for automated trust negotiation. ACM Transactions on Information and System Security, 6(1), Feb.2003.
26. L. Zhou, F. B. Schneider, and R. van Renesse. COCA: A secure distributed online certification authority. ACM Transactions on Computer Systems, 20(4):329--368, Nov. 2002.

Index Terms

• Security and privacy

  • Security services

    • Access control

    • Authentication

  • Systems security

    • Operating systems security

• Social and professional topics

  • Computing / technology policy

    • Computer crime

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications