Dominator-tree analysis for distributed authorization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Dominator-tree analysis for distributed authorization

Full text

Pdf (279 KB)

Source

Programming languages and analysis for security archive
Proceedings of the third ACM SIGPLAN workshop on Programming languages and analysis for security table of contents

Tucson, AZ, USA

SESSION: Program analysis for security and policy enforcement table of contents

Pages: 101-112

Year of Publication: 2008

ISBN:978-1-59593-936-4

Authors

Miranda Mowbray	HP Laboratories, Bristol, United Kingdom
Antonio Lain	HP Laboratories, Bristol, United Kingdom

Sponsors

ACM: Association for Computing Machinery
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 41, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1375696.1375709 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	The Debian Project: debian--keyring--2005.05.28, May 2005. http://keyring.debian.org/.
	2	Martin Abadi, On SDSI's Linked Local Name Spaces, Proceedings of the 10th IEEE workshop on Computer Security Foundations, p.98, June 10-12, 1997
	3	Martín Abadi , Michael Burrows , Butler Lampson , Gordon Plotkin, A calculus for access control in distributed systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.706-734, Sept. 1993 [doi>10.1145/155183.155225]
	4	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	5	Wolfram Amme , Niall Dalton , Jeffery von Ronne , Michael Franz, SafeTSA: a type safe and referentially secure mobile-code representation based on static single assignment form, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.137-147, June 2001, Snowbird, Utah, United States
	6	Andrew W. Appel, Modern compiler implementation in Java: basic techniques, Cambridge University Press, New York, NY, 1997
	7	M. Blaze , J. Feigenbaum , J. Ioannidis , A. Keromytis, The KeyNote Trust-Management System Version 2, RFC Editor, 1999
	8	Roland N. Bol , Krzysztof R. Apt , Jan Willem Klop, On the Power of Subsumption and Context Checks, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.131-140, April 10-12, 1990
	9	Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998 [doi>10.1145/295656.295663]
	10	Alan Bundy , Andrew Stevens , Frank van Harmelen , Andrew Ireland , Alan Smaill, Rippling: a heuristic for guiding inductive proofs, Artificial Intelligence, v.62 n.2, p.185-253, Aug. 1993 [doi>10.1016/0004-3702(93)90079-Q]
	11	CCITT (Consultative Committee on International Telegraphy and Telephony). Recommendation X.509: The Directory?Authentication Framework, 1988.
	12	Dorothy E. Denning , Peter J. Denning, Certification of programs for secure information flow, Communications of the ACM, v.20 n.7, p.504-513, July 1977 [doi>10.1145/359636.359712]
	13	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.
	14	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.
	15	Boudewijn R. Haverkort, Performance of Computer Communication Systems: A Model-Based Approach, John Wiley & Sons, Inc., New York, NY, 1998
	16	Sotiris Ioannidis , Angelos D. Keromytis , Steve M. Bellovin , Jonathan M. Smith, Implementing a distributed firewall, Proceedings of the 7th ACM conference on Computer and communications security, p.190-199, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.353052]
	17	Antonio Lain , Miranda Mowbray, Distributed Authorization Using Delegation with Acyclic Paths, Proceedings of the 19th IEEE workshop on Computer Security Foundations, p.257-269, July 05-07, 2006 [doi>10.1109/CSFW.2006.12]
	18	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.
	19	Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
	20	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.
	21	Alberto O. Mendelzon , Peter T. Wood, Finding Regular Simple Paths in Graph Databases, SIAM Journal on Computing, v.24 n.6, p.1235-1258, Dec. 1995 [doi>10.1137/S009753979122370X]
	22	Ronald L. Rivest and Butler Lampson. SDSI ? A simple distributed security infrastructure. Presented at CRYPTO?96 Rumpsession, April 1996. SDSI Version 1.0.
	23	Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, Identifying loops using DJ graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.6, p.649-658, Nov. 1996 [doi>10.1145/236114.236115]
	24	Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, Incremental computation of dominator trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.2, p.239-252, March 1997 [doi>10.1145/244795.244799]
	25	Robert Tarjan, Testing flow graph reducibility, Proceedings of the fifth annual ACM symposium on Theory of computing, p.96-107, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804040]
	26	Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
	27	Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States
	28	Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298576]