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).
The KeyNote system is not without problems.
Conditions:
@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.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:
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>.
Ninghui Li and John C. Mitchell have proposed a family of declarative trust-management languages based on Datalog with constraints [RTC].
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 2The 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
<http://faculty.ed.umuc.edu/~meinkej/inss690/hinz.pdf>
Even more advanced, and more detailed papers:
Greedy Algorithms In Datalog. Sergio Greco and Carlo Zaniolo.
<http://www.cs.ucla.edu/~zaniolo/papers/tplp01.pdf>
Top-Down vs. Bottom-Up Revisited. Ramakrishnan, R., Srivastava, D., & Sudarshan, S. (2000).
<http://citeseer.nj.nec.com/374977.html>
Magic Sets and Other Strange Ways to Implement Logic Programs. Francois Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman. PODS 1986: 1-16
<http://www.informatik.uni-trier.de/~ley/db/conf/pods/BancilhonMSU86.html>
Voronkov, A. (1999). Deductive Database. Computing Science Department Uppsala University, Uppsala, Sweden.
<http://www.csd.uu.se/~voronkov/ddb.htm>
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.
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.
<http://www.rfc-editor.org/rfc/rfc2704.txt>
[KeyNote]
<http://www.crypto.com/trustmgt/kn.html>
[RFC2792] M. Blaze, J. Ioannidis, A. Keromytis. DSA and RSA Key and Signature Encoding for the
KeyNote Trust Management System.RFC 2792. March 2000.
<http://www.rfc-editor.org/rfc/rfc2792.txt>
[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.
<http://www.usenix.org/events/usenix03/tech/freenix03/miltchev.html>
[Binder] J. DeTreville. Binder, a logic-based security language. IEEE Security and Privacy, 2002.
<http://research.microsoft.com/research/pubs/view.aspx?tr_id=545>
[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.
<http://www.cse.ucsc.edu/~abadi/Papers/lics2003.pdf>
[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.
<http://xml.coverpages.org/saml.html>
<http://www.oasis-open.org/committees/tc_home.php?wg_abbrev=security>
[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.
<http://www.research.ibm.com/vali/>
This site's top page is http://soutei.sf.net/
Converted from SXML by SXML->HTML