A Practically Implementable and Tractable Delegation Logic

Authors: Ninghui Li and Benjamin N. Grosof and Joan Feigenbaum


We address the goal of making Delegation Logic (DL) into a practically implementable and tractable trust-management system. DL is a logic-based knowledge representation (i.e., language) for authorization in large-scale, open, distributed systems.

As introduced in Li, Feigenbaum, and Grosof, DL inferencing is computationally intractable and highly impractical to implement. We introduce a new version of Delegation Logic that remedies these difficulties. To achieve this, we impose a syntactic restriction and redefine the semantics somewhat. We show that, for this revised version of DL, inferencing is computationally tractable under the same commonly met restrictions for which Ordinary Logic Programs (OLP) inferencing is tractable (e.g., Datalog and bounded number of logical variables per rule). We give an implementation architecture for this version of DL; it uses a delegation compiler from DL to OLP and can modularly exploit a variety of existing OLP inference engines. As proof of concept, we have implemented a large expressive subset of this version of DL, using this architecture.

In Proceedings of the 2000 IEEE Symposium on Security and Privacy, pages 27--42. IEEE Computer Society Press, May 2000.

Paper: PDF.

Related papers:
Superseded by the journal version to appear in ACM Transaction on Information and System Security (TISSEC).

BibTex Data:

  author =       "Ninghui Li and Benjamin N. Grosof and Joan Feigenbaum",
  title =        "A Practically Implementable and Tractable {Delegation Logic}",
  booktitle =    "Proceedings of the 2000 IEEE Symposium on Security and Privacy",
  month =        may,
  year =         "2000",
  publisher =    "IEEE Computer Society Press",
  pages =        "27--42",

Back to Ninghui's publications, Ninghui's home page.