Delegation logic: A logic-based approach to distributed authorization

ABSTRACT

We address the problem of authorization in large-scale, open, distributed systems. Authorization decisions are needed in electronic commerce, mobile-code execution, remote resource sharing, privacy protection, and many other applications. We adopt the trust-management approach, in which "authorization" is viewed as a "proof-of-compliance" problem: Does a set of credentials prove that a request complies with a policy?We develop a logic-based language, called Delegation Logic (DL), to represent policies, credentials, and requests in distributed authorization. In this paper, we describe D1LP, the monotonic version of DL. D1LP extends the logic-programming (LP) language Datalog with expressive delegation constructs that feature delegation depth and a wide variety of complex principals (including, but not limited to, k-out-of-n thresholds). Our approach to defining and implementing D1LP is based on tractably compiling D1LP programs into ordinary logic programs (OLPs). This compilation approach enables D1LP to be implemented modularly on top of existing technologies for OLP, for example, Prolog.As a trust-management language, D1LP provides a concept of proof-of-compliance that is founded on well-understood principles of logic programming and knowledge representation. D1LP also provides a logical framework for studying delegation.

REFERENCES

• 1: Martín Abadi, On SDSI's linked local name spaces, Journal of Computer Security, v.6 n.1-2, p.3-21, Sept. 1998
• 2: 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]
• 3: T. Aura, On the Structure of Delegation Networks, Proceedings of the 11th IEEE Computer Security Foundations Workshop, p.14, June 09-11, 1998
• 4: Baral C. and Gelfond, M. 1994. Logic programming and knowledge representation. J. Logic Prog. 19/20 (May/July), 73--148.
• 5: Elisa Bertino , Elena Ferrari , Francesco Buccafurri , Pasquale Rullo, A Logical Framework for Reasoning on Data Access Control Policies, Proceedings of the 1999 IEEE Computer Security Foundations Workshop, p.175, June 28-30, 1999
• 6: Blaze, M., Feigenbaum J., Ioannidis J., and Keromytis, A. D. 1999a. The KeyNote trust-management system, version 2. IETF RFC 2704, September 1999.
• 7: Matt Blaze , Joan Feigenbaum , John Ioannidis , Angelos D. Keromytis, The role of trust management in distributed systems security, Secure Internet programming: security issues for mobile and distributed objects, Springer-Verlag, London, 2001
• 8: Matt Blaze , Joan Feigenbaum , Jack Lacy, Decentralized Trust Management, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.164, May 06-08, 1996
• 9: Matt Blaze , Joan Feigenbaum , Martin Strauss, Compliance Checking in the PolicyMaker Trust Management System, Proceedings of the Second International Conference on Financial Cryptography, p.254-274, February 23-25, 1998
• 10: CCITT. 1989. Recommendation X.509: The Directory-Authentication Framework. Consultation Committee, International Telephone and Telegraph, International Telecommunications Union, Geneva.
• 11: Weidong Chen , David S. Warren, Tabled evaluation with delaying for general logic programs, Journal of the ACM (JACM), v.43 n.1, p.20-74, Jan. 1996 [doi>10.1145/227595.227597]
• 12: Yang-Hua Chu , Joan Feigenbaum , Brian LaMacchia , Paul Resnick , Martin Strauss, Referee: trust management for Web applications, World Wide Web Journal, v.2 n.3, p.127-139, Summer 1997
• 13: Dwaine Clarke , Jean-Emile Elien , Carl Ellison , Matt Fredette , Alexander Morcos , Ronald L. Rivest, Certificate chain discovery in SPKI?SDSI, Journal of Computer Security, v.9 n.4, p.285-322, January 2001
• 14: John DeTreville, Binder, a Logic-Based Security Language, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.105, May 12-15, 2002
• 15: Ellison, C., Frantz, B., Lampson, B., Rivest, R. L., Thomas, B., and Ylonen, T. 1999a. SPKI certificate theory. IETF RFC 2693, September 1999.
• 16: Ellison, C., Frantz, B., Lampson, B., Rivest, R. L., Thomas, B., and Ylonen, T. 1999b. Simple public key certificates. Internet Draft (work in progress), July 1999. http://world.std.com∼cme/spki.txt.
• 17: Finney, H. 1996. Transitive trust and MLM. Post to cypherpunks mailing list, archived at http://www.inet-one.com/cypherpunks/dir.1996.05.02-1996.05.08/msg00415.html. May 1996.
• 18: Joseph Y. Halpern , Ron van der Meyden, A logic for SDSI's linked local name spaces, Journal of Computer Security, v.9 n.1-2, p.105-142, Jan. 1,2001
• 19: Amir Herzberg , Yosi Mass , Joris Michaeli , Yiftach Ravid , Dalit Naor, Access Control Meets Public Key Infrastructure, Or: Assigning Roles to Strangers, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.2, May 14-17, 2000
• 20: Jonathan R. Howell , David Kotz, Naming and sharing resources across administrative boundaries, 2000
• 21: Sushil Jajodia , Pierangela Samarati , V. S. Subrahmanian, A Logical Language for Expressing Authorizations, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.31, May 04-07, 1997
• 22: Sushil Jajodia , Pierangela Samarati , V. S. Subrahmanian , Eliza Bertino, A unified framework for enforcing multiple access control policies, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.474-485, May 11-15, 1997, Tucson, Arizona, United States
• 23: Trevor Jim, SD3: A Trust Management System with Certified Evaluation, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.106, May 14-16, 2001
• 24: Stephen T. Kent, Internet Privacy Enhanced Mail, Communications of the ACM, v.36 n.8, p.48-60, Aug. 1993 [doi>10.1145/163381.163390]
• 25: Butler Lampson , Martín Abadi , Michael Burrows , Edward Wobber, Authentication in distributed systems: theory and practice, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.265-310, Nov. 1992 [doi>10.1145/138873.138874]
• 26: Langheinrich, M. 2002. A P3P Preference Exchange Language 1.0 (APPEL1.0). W3C Working Draft, April 2002.
• 27: Ninghui Li, Local Names in SPKI/SDSI, Proceedings of the 13th IEEE Computer Security Foundations Workshop (CSFW'00), p.2, July 03-05, 2000
• 28: Ninghui Li , Joan Feigenbaum , Alan Siegel, Delegation logic: a logic-based approach to distributed authorization, 2000
• 29: Li, N. 2000c. XD1LP: An implementation of D1LP in XSB. http://cs.nyu.edu/ninghui/xd1lp/.
• 30: Ninghui Li , Joan Feigenbaum , Benjamin N. Grosof, A Logic-based Knowledge Representation for Authorization with Delegation, Proceedings of the 1999 IEEE Computer Security Foundations Workshop, p.162, June 28-30, 1999
• 31: Ninghui Li , Benjamin Grosof , Joan Feigenbaum, A Practically Implementable and Tractable Delegation Logic, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.27, May 14-17, 2000
• 32: Ninghui Li , John C. Mitchell , William H. Winsborough, Design of a Role-Based Trust-Management Framework, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.114, May 12-15, 2002
• 33: Ninghui Li , William H. Winsborough , John C. Mitchell, Distributed credential chain discovery in trust management: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502005]
• 34: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 35: Marchiori, M. 2002. The Platform for Privacy Preferences 1.0 (P3P1.0) Specification. W3C Recommendation. April.
• 36: Ueli M. Maurer, Modelling a Public-Key Infrastructure, Proceedings of the 4th European Symposium on Research in Computer Security: Computer Security, p.325-350, September 25-27, 1996
• 37: Naish, L. 1992. Types and the intended meaning of logic programs. In F. Pfenning, editor, Types in Logic Programming. The MIT Press, Cambridge, Mass., pp. 189--216.
• 38: Peter Padawitz, Computing in Horn clause theories, Springer-Verlag New York, Inc., New York, NY, 1988
• 39: Frank Pfenning, Types in logic programming, MIT Press, Cambridge, MA, 1992
• 40: Rivest, R. L. and Lampson, B. 1996. SDSI: a simple distributed security infrastructure. http://theory.lcs.mit.edu/∼rivest/sdsi11.html. October 1996.
• 41: Stephen Weeks, Understanding Trust Management Systems, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.94, May 14-16, 2001
• 42: The XSB Research Group. 2002. The XSB programming system. http://xsb.sourceforge.net/.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Languages, Security

Keywords:
Access control, Delegation Logic, distributed system security, logic programs, trust management