Lambda the Ultimate

SecPAL: Design and Semantics of a Decentralized Authorization Language. Moritz Y. Becker; Andrew D. Gordon; Cédric Fournet. September 2006

We present a declarative authorization language. Policies and credentials are expressed using predicates defined by logical clauses, in the style of constraint logic programming. Access requests are mapped to logical authorization queries, consisting of predicates and constraints combined by conjunctions, disjunctions, and negations. Access is granted if the query succeeds against the current database of clauses. Predicates ascribe rights to particular principals, with flexible support for delegation and revocation. At the discretion of the delegator, delegated rights can be further delegated, either to a fixed depth, or arbitrarily deeply.

Our language strikes a fine balance between semantic simplicity, policy expressiveness, and execution efficiency. The semantics consists of just three deduction rules. The language can express many common policy idioms using constraints, controlled delegation, recursive predicates, and negated queries. We describe an execution strategy based on translation to Datalog with constraints and table-based resolution. We show that this execution strategy is sound, complete, and always terminates, despite recursion and negation, as long as simple syntactic conditions are met.

The SecPAL project lives here (MSR). The project aims are to develop a language for expressing decentralized authorization policies, and to investigate language design and semantics, as well as related algorithms and analysis techniques.