Authorization and Role-Based Access control. Survey and notes.

  1. Trust-management systems
  2. KeyNote
    1. Keynote problems
  3. Binder system
  4. SAML
  5. RTC: Datalog with constraints
  6. Policy checking
  7. Datalog


Trust-management systems

Most of the access control systems discussed below belong to a class of trust-management systems. RFC 2704 succinctly describes these systems as follows [RFC2704]:

A trust-management system provides standard, general-purpose mechanisms for specifying application security policies and credentials. Trust-management credentials describe a specific delegation of trust and subsume the role of public key certificates; unlike traditional certificates, which bind keys to names, credentials can bind keys directly to the authorization to perform specific tasks.

Trust management unifies the notions of security policy, credentials, access control, and authorization. An application that uses a trust-management system can simply ask the compliance checker whether a requested action should be allowed. Furthermore, policies and credentials are written in standard languages that are shared by all trust-managed applications; the security configuration mechanism for one application carries exactly the same syntactic and semantic structure as that of another, even when the semantics of the applications themselves are quite different.

Trust-management policies are easy to distribute across networks, helping to avoid the need for application-specific distributed policy configuration mechanisms, access control lists, and certificate parsers and interpreters.



KeyNote [KeyNote] [RFC2704] is one particular framework and a language to build trust-management systems. In KeyNote, principals are identified by names, which can be cryptographic keys. Policies and credentials are called `assertions': typically cryptographically signed statements describing trusted actions and conditions that yield a policy compliance value. The latter is often a binary value (e.g., grant and deny); a range of restricted access permissions may also be specified. A principal may issue an assertion delegating authorization to perform (a subset) of actions to other principals. Top-level assertions are usually stored locally. Others are fetched from remote authorities or delivered by clients. In the latter cases, the assertions should be signed.

Particularly attractive properties of KeyNote are an ability of principals to delegate a subset of their privileges to other principals, and an ability to express authorization conditions as logical formulas. A condition is a logical proposition over attributes whose values can be strings, integers, and floating-point numbers. The values of the attributes are provided by an application that requests an authorization advice. The conditions can express, for example, that a particular file is accessible for reading only within a specific time window and only if the request is vouched for by at least two trusted administrators. Examples at the end of RFC2704 are quite illustrative.

KeyNote is a mature system. There is a reference implementation and several others. KeyNote is a part of a secure distributed file system [DisCFS] and of OpenBSD's IPSEC stack. Apache-SSL can also use KeyNote. The KeyNote page [KeyNote] lists other real-world applications of the system. Google search for KeyNote trust management yields quite a few links.

One of the important properties of the KeyNote system is its monotonicity: access permissions never decrease as more security assertions are made available to the system. That is, KeyNote will never authorize an action only because some crucial assertion was not delivered to the system in time. We should note however that the monotonicity property, however beneficial, precludes using KeyNote assertions for revocation. Revocation of privileges must be handled in some other way (e.g., through expiration of certificates).

The monotonicity property (adding certificates may only increase the trust value) seems to be sound: it is guaranteed by the fact that the Licensees: field of an assertion uses monotone operators ( &&, || and k-of), and the Conditions: field cannot refer to other certificates.

The notion of an application scope provides some kind of scoping of attributes. The calling application is responsible for dereferencing attributes -- either by passing a dictionary or providing a look-up function (call-back). To the KeyNote system, the values of attributes and the bindings themselves are immutable. KeyNote provides for indirect references (e.g., $foo refers to an attribute whose name is in the attribute foo).


Keynote problems

The KeyNote system is not without problems.

  1. RFC2704 says, ``Attribute names may be given literally or calculated from string expressions and may be recursively dereferenced.'' It is not clear if self-references or cyclical references are expressible. If they are, a non-termination of a policy decision becomes an issue.
  2. Type conversion seems quite sloppy. Attribute values are strings; a user may request a conversion of a string to an integer or an IEEE floating-point number. If the conversion fails, no error is reported but the conversion result is assumed to be 0. Likewise, dereferencing an unbound attribute reports no error but yields the empty string instead.
  3. Local attributes (defined in an assertion itself) override application-supplied attributes. However, if the name of a local attribute is mis-spelled (or mis-cased -- names are case-sensitive), trouble ensues. No error is reported but the overriding fails. The error becomes especially insidious if a mis-spelled name is used as an indirect attribute name. The latter fact may cause a wrong value used in a condition formula, and consequently, authorizing an action that should have been denied.
  4. A design decision making a numeric conversion failure yield 0 is a security concern. Here's the example from RFC2704 itself:
           @user_id == 0 -> "full_access";             # clause (1)
           @user_id < 1000 -> "user_access";           # clause (2)
           @user_id < 10000 -> "guest_access";         # clause (3)
           user_name == "root" -> "full_access";       # clause (4)
    Here @ is a string-to-integer conversion operator. Let us suppose that user_id was meant to be 65535 but by mistake was 65535-. The conversion fails, @user_id yields the value of zero, which triggers the answer full_access. A client would be given an authorization for the full access when no access should have been granted. This security concern becomes especially serious if the values of the attributes are accepted from clients, without exhaustive checking.
  5. It has been proven [RTC] that an analysis of all requests authorized by a set of assertions is undecidable. In fact, we cannot in generally tell if a policy with a single assertion authorizes any request at all. It is therefore impossible in general to analyze the effect of security assertions, e.g., to verify global policy constraints.


Binder system

Binder is a logic-based security language: an extension of Datalog. Binder was introduced in a paper [Binder]. Google search for ``Binder security language'' offers many links to that paper -- but no real applications or implementations. In that respect, KeyNote is more developed. On the other hand, Binder is developed by an experienced security researcher, has a clean design and sound logical foundations [Logic-AC].

A security statement in Binder is a logical program written in a subset of Prolog without function symbols (i.e., Datalog). Binder extends Datalog [Datalog] with the notion of a context and a distinguished relation says. A statement in Binder can be a simple fact, e.g., can(john_smith,read,resource_r) or a rule, e.g., can(X,read,resource_r) :- employee(X,bigco). One rule like that replaces a great number of conventional access control list items. Security statements in Binder are therefore concise. Binder can easily express role-based access control, delegation, and quite complex security policies, for example [Binder]:

     can(X, read, resource_r) :-
        employee(X, bigco),
        boss(Y, X),
        approves(Y, X, read, resource_r).
     employee(john_smith, bigco).
     boss(fred_jones, john_smith).
     approves(fred_jones, john_smith, read, resource_r).
The first statement in the above certificate is a rule stating that any employee of a BigCo may read resource_r provided such an action is approved by his boss. The other three statements are facts about employees of BigCo and the approval action. More examples along with their detailed descriptions can be found in the Binder paper [Binder].

Granting access to a resource in Binder is deriving an atom that asserts such a permission, e.g., an atom can(john_smith,read,resource_r) in the example. The derivation constitutes a logical proof of the permission. The proof can be generated by a service, in polynomial time. Alternatively, a client can generate a proof and submit it with the request. The service needs merely to check the proof. The latter approach distributes the load of authorization computations and helps prevent denial-of-service attacks.

Binder programs do not contain negation. Therefore, Binder is monotonic: adding more statements can only make more atoms provable. In other words, we cannot cause elevated access permissions by withholding statements.

Binder is specifically designed for a distributed computing environment. Each authorization service has its own Binder context. A context with a set of facts and rules can be exported into a signed certificate and transmitted to another service. Statements in an exported context are marked with the identity of the exporting service using the quotation form says. A service can import a context and use the context's statements in local proofs if the local service trusts the remote one. The trust relationship is itself expressed as a set of Binder statements.

Identities of Binder principals -- for instance, identities of the exporting services -- are represented by cryptographic keys. The latter may be encoded in the format described in [RFC2792]. One may bind a local name to a cryptographic key for easy reference, e.g., [Binder]:

     employee(X, bigco, full_time) :-
       Y says employee(X, bigco, full_time),
       bound(bigco_hr, Y).
     bound(bigco_hr, rsa:3:c1ebab5d).
The local context with its name bigco_hr can be exported in turn. This feature lets Binder simulate the linked name spaces of SDSI/SPKI, but without built-in language support.

The paper [Binder] states the following distinguished features of the system:

  1. A statement in Binder can be translated into a declarative, stand-alone English sentence.
  2. Binder programs can explicitly define new, application-specific predicates, which can act as lemmas in proofs. Predicates can be defined recursively. Rich proofs are allowed.
  3. Certificates may contain arbitrary facts and rules, over local, application-specific -- or remote and quoted predicates. Certificates can be safely interpreted outside their exporting context.
  4. Binder statements can appear in certificates, in policies, in ACLs, and elsewhere, and these statements can inter-operate freely.
  5. Binder queries are decidable in polynomial time.

Section 7 of the paper [Binder] compares Binder with X.509 Certificates, SDSI and SPKI, PolicyMaker, KeyNote, SD3 and similar logic-based security languages, and digital rights management languages. The paper shows that none of those systems possesses all five key Binder properties.



SAML is a Security Assertion Markup Language [SAML]. SAML seems to be more a certificate format and a certificate transport format than a trust management language.

It seems that DecisionType of a SAML assertion only specifies Permit, Deny and Indeterminate. KeyNote provides for far more variety of decisions. The conditions on the assertion are also far less expressive: NotBefore, NotOnOrAfter, <AudienceRestrictionCondition>, <DoNotCacheCondition>.


RTC: Datalog with constraints

Ninghui Li and John C. Mitchell have proposed a family of declarative trust-management languages based on Datalog with constraints [RTC].


Policy checking

An access control system advises an application if an action requested by a particular principal is consistent with a security policy. We may also need to check if the security policy itself is consistent, that is, if it actually protects valuable resources. In a policy with many rules, the overall effect may be difficult to see. Unpleasant surprises do happen in practice:

Firewalls that rely on chained rule sets are vulnerable to cascade failures -- a change in one rule can have an effect on every rule that follows it. I've seen systems that relied on a firewall to block services that were only supposed to be available on the local network, but which were made available to the entire Internet due to the unforeseen results of a firewall rule change. [Firewalls] (p. 35)

The first quantitative study of firewall configuration errors [Firewall-errors] found the results dismal. ``Only one of the 37 firewalls exhibited just a single misconfiguration. All the others could have been easily penetrated by both unsophisticated attackers and mindless automatic worms.''

To prevent such unforeseen results we need to check policy's invariants and consistency. Unfortunately, many access control systems have quite low expressivity, which results in a large set of rules. For example, SELinux policy has around 50,000 statements. We need automated tools to verify policies. The tools must be built on firm logical foundations. Because the policy check is an off-line process (executed only when the policy is updated), the performance of the tools is not of prime importance.

Unfortunately, some of the access control systems such as KeyNote have not been designed with policy checking in mind: in general, policy checking in KeyNote is undecidable [RTC].

One real-life example of policy checking is testing that SELinux policies are consistent with the trusted computer base requirements: `Analyzing Integrity Protection in the SELinux Example Policy' by Trent Jaeger, Reiner Sailer, Xiaolan Zhang presented at USENIX Security Symposium 2003 [VALI]. The authors have developed a Gokyo policy analysis tool, which seems to rely on a human-aided exhaustive search. No inference seem to be present. In fact, the words `infer' and `formal' are not even mentioned, and the word `logic' occurs only in the title of two referenced papers. It is not clear how the tool itself was verified -- if it was at all. Perhaps the stress must be on rigor rather than on the development of visual tools.



Datalog seems to be the foundation for many logic-based access control languages and systems.

Introduction to datalog, top-down and bottom-up strategies, and Herbrand interpretation:

Computational Intelligence, a logical approach. D. Poole, A. Mackworth and R. Goebel.Oxford University Press, 1998. ISBN 0-19-510270-3. Chapter 2
The handouts are available at

A more advanced comparison of top-down and bottom-up strategies:

Datalog Bottom-up is the Trend in the Deductive Database Evaluation Strategy. Yurek K. Hinz

Even more advanced, and more detailed papers:

Greedy Algorithms In Datalog. Sergio Greco and Carlo Zaniolo.
Top-Down vs. Bottom-Up Revisited. Ramakrishnan, R., Srivastava, D., & Sudarshan, S. (2000).
Magic Sets and Other Strange Ways to Implement Logic Programs. Francois Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman. PODS 1986: 1-16
Voronkov, A. (1999). Deductive Database. Computing Science Department Uppsala University, Uppsala, Sweden.
Answer-set programming

XSB: An efficient logical system with top-down and bottom-up strategies. XSB can evaluate according to Well-Founded Semantics through full SLG resolution.

Disjunctive Datalog

A disjunctive Datalog system DLV is the very first system supporting full disjunctive logic programming with answer set semantics. It supports answer set semantics for full disjunctive logic programs with negation, integrity constraints, queries, and arithmetic built-ins.

DLV Home page:
DLV Tutorial

A graph coloring problem in the tutorial illustrates the advantages of DLV. The problem is to find out if a given map of countries can be colored with three colors. No two neighbor countries should have the same color. The map, of Mid-Western U.S. states in the example, as represented as a set of nodes and arcs. Arcs connect neighboring states.

     node(minnesota). node(wisconsin). node(illinois). node(iowa). ...
     arc(minnesota, wisconsin). arc(illinois, iowa).

The problem is solved by the following DLV program with only two statements:

     % guess coloring
     col(Country, red) v col(Country, green) v col(Country, blue) :- node(Country).
     % check coloring
     :- arc(Country1, Country2), col(Country1, CommonColor), col(Country2, CommonColor).
The first statement is a disjunctive rule that guesses a coloring. The second statement expresses the strong constraint that deletes all those colorings that do not satisfy our requirements (that there may be no arc between two nodes of equal color). DLV solves the problem rather efficiently.



[RFC2704] M. Blaze, J. Feigenbaum, J. Ioannidis, A. Keromytis. The KeyNote Trust-Management System Version 2. RFC 2704. September 1999.


[RFC2792] M. Blaze, J. Ioannidis, A. Keromytis. DSA and RSA Key and Signature Encoding for the KeyNote Trust Management System.RFC 2792. March 2000.

[DisCFS] S. Miltchev, V. Prevelakis, S. Ioannidis, J. Ioannidis, A.D. Keromytis, J.M. Smith. Secure and Flexible Global File Sharing. Proc. USENIX 2003, FREENIX Track, pp. 165-178.

[Binder] J. DeTreville. Binder, a logic-based security language. IEEE Security and Privacy, 2002.

[RTC] Ninghui Li, J.C. Mitchell. Datalog with constraints: a foundation for trust management languages. Proc. PADL2003: Practical Aspects of Declarative Languages. LNCS 2562, pp. 58-73.

[Logic-AC] M. Abadi. Logic in Access Control. Proc. of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (June 2003), 228-233.

[SD3] T. Jim. SD3: A trust management system with certified evaluation. Proc. 2001 IEEE Symposium on Security and Privacy, pp. 106-115.

[SAML] Security Assertion Markup Language (SAML). Version 1.1. September 2003.

[Firewalls] A. Singer, San Diego Supercomputing Center. Life without firewalls. USENIX ;login:, Dec 2003, v28, N6, pp. 34-41.

[Firewall-errors] Avishai Wool. A Quantitative Study of Firewall Configuration Errors. IEEE Computer, June 2004, pp. 62-67

[VALI] IBM T. J. Watson Research Center. Linux Security Analysis Tools.

Last updated July 23, 2004
Your comments, problem reports, questions are very welcome!

Converted from SXML by SXML->HTML

$Id: Authorization.scm,v 1.5 2004/07/24 01:38:54 oleg Exp oleg $