Miranda Mowbray
ABSTRACT
Practical analysis tools for distributed authorization need to answer quickly and accurately the question: who can access this resource? DAP (Delegation with Acyclic Paths) is a distributed authorization framework (introduced in [17]) that tries to inter-operate better with standard PKI mechanisms while retaining some of the benefits of new trust management schemes. DAP has an acyclicity requirement which makes it more difficult to answer the question quickly. In this paper we use a technique borrowed from compiler optimization, dominator-tree problem decomposition, to overcome this limitation of DAP with a fast heuristic. We show through simulation the heuristic's performance in a realistic federated resource management scenario.
We also show how this heuristic can be complemented by clone-analysis techniques that exploit similarities between principals to further improve performance. We are currently using the heuristic and clone-analysis in practice in a design/analysis security tool.
- The Debian Project: debian--keyring--2005.05.28, May 2005. http://keyring.debian.org/.Google Scholar
- Martín Abadi. On SDSI?s Linked Local Name Spaces. In Proceedings 10th IEEE Computer Security Foundations Workshop, June 1997. Google ScholarDigital Library
- Martín Abadi, Michael Burrows, Butler Lampson, and Gordon Plotkin. A Calculus for Access Control in Distributed Systems. ACM Transactions on Programming Languages and Systems, 15(4):706--734, September 1993. Google ScholarDigital Library
- Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Princiles, Techniques, and Tools. Addison-Wesley, 1986. Google ScholarDigital Library
- Wolfram Amme, Niall Dalton, Jeffery von Ronne, and Michael Franz. SafeTSA: a type safe and referentially secure mobile-code representation based on static single assignment form. In PLDI?01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, pages 137--147, New York, NY, USA, 2001. ACM. Google ScholarDigital Library
- Andrew W. Appel. Modern Compiler Implementation in Java: Basic Techniques. Cambridge University Press, 1997. Google ScholarDigital Library
- M. Blaze, J. Feigenbaum, J. Ioannidis, and A. Keromytis. The Keynote trust-management system, version 2. IETF RFC 2704, September 1999. Google ScholarDigital Library
- Roland N. Bol, Krzysztof R. Apt, and Jan Willem Klop. On the Power of Subsumption and Context Checks. In DISCO?90: Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, pages 131--140, London, UK, 1990. Springer-Verlag. Google ScholarDigital Library
- Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, and Jeffery R. Westbrook. A new, simpler linear-time dominators algorithm. ACM Transactions on Programming Languages and Systems, 20(6):1265--1296, 1998. Google ScholarDigital Library
- Alan Bundy, Andrew Stevens, Frank van Harmelen, Andrew Ireland, and Alan Smaill. Rippling: A Heuristic for Guiding Inductive Proofs. Artificial Intelligence, 62(2):185--253, 1993. Google ScholarDigital Library
- CCITT (Consultative Committee on International Telegraphy and Telephony). Recommendation X.509: The Directory?Authentication Framework, 1988.Google Scholar
- Dorothy E. Denning and Peter J. Denning. Certification of programs for secure information flow. Commun. ACM, 20(7):504--513, 1977. Google ScholarDigital Library
- Carl M. Ellison, Bill Frantz, Butler Lampson, Ron Rivest, Brian M. Thomas, and Tatu Ylonen. Simple public key certificate. Internet Engineering Task Force Draft IETF, July 1997.Google Scholar
- Loukas Georgiadis, Renato Fonseca F. Werneck, Robert Endre Tarjan, Spyridon Triantafyllis, and David I. August. Finding dominators in practice. In Susanne Albers and Tomasz Radzik, editors, ESA, volume 3221 of Lecture Notes in Computer Science, pages 677--688. Springer, 2004.Google Scholar
- Boudewijn R. Haverkort. Performance of Computer-Communication Systems. John Wiley and Sons, 1998. Google ScholarDigital Library
- Sotiris Ioannidis, Angelos D. Keromytis, Steve M. Bellovin, and Jonathan M. Smith. Implementing a distributed firewall. In Sushil Jajodia and Pierangela Samarati, editors, Proceedings of the 7th ACM Conference on Computer and Communications Security (CCS-00), pages 190--199, N.Y., November 1--4 2000. ACM Press. Google ScholarDigital Library
- Antonio Lain and Miranda Mowbray. Distributed authorization using delegation with acyclic paths. In Proc. 19th IEEE Computer Security and Foundations Workshop, Venice, Italy, pages 257--269. IEEE Computer Society Press, July 2006. Google ScholarDigital Library
- B. W. Lampson. Protection. In 5th Princeton Symposium on Information Sciences and Systems,. Princeton University, March 1971. Reprinted in Operating Systems Review 8,1 January 74.Google Scholar
- Thomas Lengauer and Robert Endre Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121--141, 1979. Google ScholarDigital Library
- Ninghui Li and John C. Mitchell. Understanding SPKI/SDSI using first-order logic. In Proc. 16th IEEE Computer Security and Foundations Workshop, Pacific Grove, CA, USA, pages 89--108. IEEE Computer Society Press, June 2003.Google Scholar
- Alberto O. Mendelzon and Peter T. Wood. Finding regular simple paths in graph databases. SIAMJournal on Computing, 24(6):1235--1258, 1995. Google ScholarDigital Library
- Ronald L. Rivest and Butler Lampson. SDSI ? A simple distributed security infrastructure. Presented at CRYPTO?96 Rumpsession, April 1996. SDSI Version 1.0.Google Scholar
- Vugranam C. Sreedhar, Guang R. Gao, and Yong-Fong Lee. Identifying Loops Using DJ Graphs. ACM Transactions on Programming Languages and Systems, 18(6):649--658, 1996. Google ScholarDigital Library
- Vugranam C. Sreedhar, Guang R. Gao, and Yong-Fong Lee. Incremental computation of dominator trees. ACM Transactions on Programming Languages and Systems, 19(2):239--252, 1997. Google ScholarDigital Library
- Robert Tarjan. Testing flow graph reducibility. In STOC?73: Proceedings of the fifth annual ACM symposium on Theory of computing, pages 96--107, New York, NY, USA, 1973. ACM. Google ScholarDigital Library
- Robert Endre Tarjan. Fast algorithms for solving path problems. J. ACM, 28(3):594--614, 1981. Google ScholarDigital Library
- Mark Weiser. Program slicing. In ICSE ?81: Proceedings of the 5th international conference on Software engineering, pages 439--449, Piscataway, NJ, USA, 1981. IEEE Press. Google ScholarDigital Library
- Mihalis Yannakakis. Graph-theoretic methods in database theory. In PODS, pages 230--242. ACM Press, 1990. Google ScholarDigital Library
Index Terms
- Dominator-tree analysis for distributed authorization
Recommendations
An authorization mechanism for a relational database system
A multiuser database system must selectively permit users to share data, while retaining the ability to restrict data access. There must be a mechanism to provide protection and security, permitting information to be accessed only by properly authorized ...
PBDM: a flexible delegation model in RBAC
SACMAT '03: Proceedings of the eighth ACM symposium on Access control models and technologiesRole-based access control (RBAC) is recognized as an efficient access control model for large organizations. Most organizations have some business rules related to access control policy. Delegation of authority is among these rules. RBDM0 and RDM2000 ...
Authorization in trust management: Features and foundations
Trust management systems are frameworks for authorization in modern distributed systems, allowing remotely accessible resources to be protected by providers. By allowing providers to specify policy, and access requesters to possess certain access rights,...
Comments