REFEREE version 1.4

Rule-controlled Environment for Evaluation of Rules,
and Everything Else

Jonathan Brezin (, Yang-Hua Chu (,
Rohit Khare (, Brian LaMacchia (,
Jim Miller (, Paul Resnick (,
Martin Strauss (

Draft of 10/25/96

1. Introduction

Digital signatures alone are not sufficient for code signing and other applications: signatures can solve the problem of message integrity and authentication, but not more general notions of security or trust. These applications require not only cryptographic tools for determining authenticity and message integrity but also a mechanism that permits users to clearly state their own security policies and evaluate digital signatures with respect to those policies. For example, in a code signing application a user must state under what conditions do they trust the code. Similarly, the entity signing the code must state precisely what properties they claim the code has (e.g. virus-free, works with particular hardware platforms). We believe that digital signature applications will benefit from a simple language that can describe most common user policies and can be extended to handled more complex policies.

In this paper we propose a general mechanism for expressing and evaluating trust management policies. In addition to authorization of actions, this mechanism places fetching, authentication, installation and execution of credentials (including arbitrary programs) all under local policy control. We call this system REFEREE, both because it is a policy arbiter and also because the system provides a "Rule-controlled Environment For Evaluation of Rules and Everything Else." That is, REFEREE is a system for writing policies about policies, as well as policies about cryptographic keys, PICS label bureaus, certification authorities, or anything else. Within REFEREE every policy evaluation is under the control of some other local policy.

We also propose in this document a simple profiles language, Profiles-0.92, that describes policies in terms of what PICS labels are needed in order to authorize operations. Mechanically, policies are programs that can fetch and process PICS labels in order to determine whether a requested operation is permitted. In the course of execution, they can call other programs/policies, for example to check signatures to determine the authenticity of labels.

Section two of this document describes the underlying architecture of the REFEREE trust management engine. Section three describes the Profiles-0.92 language for specifying user policies. Section four presents a library of primitive functions that must be provided by every conforming implementation. Finally, Section five presents a detailed example of operation within the environment of the World-Wide Web where the policy refers to PICS labels.

2. Underlying Architecture


The core of the REFEREE trust management system is premised on the following three assumptions:
  1. An application calls REFEREE to find out whether it may perform a particular action.
  2. For every possible action the application can ask about, there is a corresponding program (a "policy") that is responsible for determining whether the action should be taken.
  3. The result of calling REFEREE is a pair of two values: a tri-value and a justification for the tri-value. A tri-value is a three-valued logic element, corresponding to the following three possible statements from the trust management system:
    1. Allow: the action may be taken.
    2. Block: the action may not be taken.
    3. "I don't know": the trust management system doesn't have enough information to know whether the action may be taken or not.
    The justification returned with the tri-value is a list of statements (assertions) generated during the system's evaluation of the proposed action. These statements may provide the application with information concerning why the action request was allowed/denied/left unanswered.
We discuss the API in more detail below.

Primitive Data Types

REFEREE has three primitive underlying data types: they follow directly from the three operating assumptions in the previous section. The underlying data types are: Program databases provide bindings between symbolic names and executable code. When an application calls the trust management system on a particular action request, a global program database tells the core system what program is responsible for making policy decisions about the requested action. Once the responsible program is known the core system passes on the action, plus any additional arguments, for further processing. Applications calling REFEREE are required to provide a core set of trusted action-program bindings to bootstrap the system; additional bindings may be installed dynamically pursuant to policy control.

Tri-values are three-valued logic operands. We designate the three possible values as "allow", "block" and "unknown" to distinguish tri-values from traditional Boolean values. Tri-values may be combined in manner similar to boolean values. They are one of the outputs of policies.

Statements express information acquired during the execution of policies. They are the common information interexchange containers among different programs. All statements are two-element s-expressions. The first element conveys the context of the statement and the second element provides the content. (For example, a context might be the program that was running when the information was acquired. The content might be an assertion that a particular document has been virus-checked.)

                 Input------->| Program |---------->Output
Inputs					       Outputs
------					       -------
list of statements		               return-value, pair of:
additional arguments (optional)                  tri-value
                                                 list of statements

Dynamically-scoped variables: program databases 
The basic computing unit within REFEREE is a program. All programs have a single mandatory input argument: a list of statements (conveying information). Programs may have any number of additional arguments. As mentioned above, every program returns a pair containing a tri-value and a statement list as its return-value. There are two variables, pointing to program databases, that are guaranteed to be present in the environment of every program. These two variables have dynamic scope and may be modified during the execution of the trust management system. Modification to the program databases are not persistent across calls to REFEREE. Of course, as the system is bootstrapped by a calling application the application may provide some persistent storage on its own.

Program-names, Programs and Interpreters

As mentioned above, a program database provides a set of bindings between symbolic names and executable program objects, making it possible to call programs by name (as is common in almost all programming languages). The program database provides a level of indirection that is under policy control; that is, a policy can selectively "install" or "uninstall" elements of the table of programs to control the availability of those programs.

We make the distinction between "programs" and "interpreters" so that one interpreter can process any number of programs written in a particular language. Thus, the program database is segretated into a "program" table and an "interpreter" table. Each entry in a program table is a triplet (program-name, program, language-name); each entry in the interpreter table maps language-names (strings) to interpreters.

Program Table                                Interpreter Table

Program-name | Program | Language-name       Language-name  | Interpreter
--------------------------------------       ----------------------------
...          | ...     | ...                      ...       | ...
...          | ...     | ...                      ...       | ...
There can only be one entry in the program table for a particular program-name, and likewise there may only be one entry in the interpreter table for a particular language-name. All conforming implementation are required to provide an interpreter for the Profiles-0.92 language described in Section 3 below. A binding between the symbolic language name "Profiles-0.92" and the interpreter for Profiles-0.92 must exist in the bootstrap interpreter table provided by the calling application.

3. Profiles-0.92: A Simple Profile Language

In this section we present Profiles-0.92, a simple language for describing top-level trust management policies. Profiles-0.92 allows the user to: Profiles-0.92 has no language constructs that generate either statements or tri-values; other programs must be invoked to produce such values. However, Profiles-0.92 provides constructs that combine return-values (or pieces of return-values) produced by other invoked programs.

Provided special forms and their semantics

Profiles-0.92 provides seven types of primitive operations. They are:
  1. Invocations (ways to run other programs)
    (invoke <program-name> <statement-list> <additional-args>*)
    invoke calls the program named <program-name> with a copy of the <statement-list> and possibly some other additional arguments. When the called program returns, its return values is a pair consisting of a tri-value and a statement-list. By convention, the statement-list contains statements that the called program wants appended to the statement-list. For every statement in the returned statement-list, Profiles-0.92 (a) prepends the name of the called program to the context of the statement, and (b) appends the statement to the original statement-list that was references in the call to invoke. The return value of the (invoke ...) construct is a pair of the tri-value returned by the called program and the tagged statements appended to the statement-list.

  2. Installations (ways to install bindings between names and programs or interpreters)
    (install-program <statement-list>)
    (install-interpreter <statement-list>)
    Recall that in Profiles-0.92 there are two independent, global program databases, the program table and the interpreter table. install-program creates bindings in the program table and install-interpreter creates bindings in the interpreter table. In both cases, the information required to make these bindings are passed within a statement list containing a single statement. install-program expects to see a statement of the form:
    ((<context>) (<program-name> <program-body-or-pointer> <language-name>))
    Similarly, install-interpreter expects to see a statement of the form:
    ((<context>) (<language-name> <interpreter-body-or-pointer>))

  3. Explicit lists
  4. (allow URL <URL>+)
    (block URL <URL>+)

    For example, the operation (allow URL "" "") returns the tri-value allow if the requested URL has any of the listed URLs as a prefix, and otherwise the tri-value block. The operation (block URL "" "") reverses the sense and returns block if the requested URL has either of the arguments as a prefix and allow otherwise. (These never return unknown.)

    Each combinator returns a statement list consisting of statements of the form "(allow <prefix>)" for each relevant URL prefix. In the above example, if "" was requested then (allow URL "" "") returns ( (allow "") ) as a list containing one statement.

    For use in combinations, it is also convenient to have unconditional allows and blocks. The operation (allow) returns tri-value allow and the empty statement list; the operation (block) returns tri-value block and the empty statement list.

  5. Combinations (ways to combine tri-values)
    (any-allow <rule>+)
    (any-block <rule>+)
    (only-if-all-allow <rule>+)
    (unless-all-block <rule>+)
    These functions all operate on pairs of tri-values and statement lists and return pairs of tri-values and statement-lists. The semantics are below.

  6. Local variable binding
    (let (<var> <rule1>) <rule>+)
    Let binds the variable <var> to the value of evaluating <rule1> for the scope of the remaining rules in the body.

  7. Pattern matching
    (match <pattern> <statement-list>)
    match returns the subset of <statement-list> that matches the given <pattern>. The pattern-matching language is detailed below.

  8. Projection functions
    (statement-list <return-value>)
    (tri-value <return-value>)
    These two functions operate on pairs of return values and extract either the statement-list or tri-value contained within.

Provided local variables

Profiles-0.92 also provides the following local variables:

Semantics of Combinations

We first give the rules of 3-valued logic for producing a tri-value and then describe the operation on statement-lists.

An any-allow list consists of one or more rules, and its semantics are:

An any-block list is evaluated analoguously. Any of its constituent rules with tri-value block causes the tri-value of the list to be block, and so on.

An only-if-all-allow list consists of one or more rules, and its semantics are:

An unless-all-block list is evaluated analogously: its tri-value is block if each of its member rules has a tri-value of block; otherwise its tri-value to allow.

An any-allow or any-block list may evaluate to unrated. If an any-allow or any-block list appears as a member of an only-if-all-allow list, then a tri-value of unrated for the any-... list has exactly the same semantics as if the tri-value were block.

Similarly, if an any-allow or any-block list appears as a member of an unless-all-block list, then a tri-value of unrated for the any-... list has exactly the same semantics as if the tri-value were allow.

Besides the tri-value, each rule returns a statement-list of data that was relevant in forming the decision. Each of the combinations

(any-allow <rule>+)
(any-block <rule>+)
(only-if-all-allow <rule>+)
(unless-all-block <rule>+)
currently unions the statement-lists returned by all of its constituent rules, although we believe that this issue is more complex and requires further study.

Pattern matching language

The pattern matching language for the match operator is basically an s-expression-aware structure matcher extended with restrictions. That is, the patterns and the matcher understand s-expression syntax and structure, so that patterns can be written that match particular subexpressions within an generic s-expression.

In addition to parentheses and literal elements, the pattern matcher has two generic match elements: "*" and "...". A "*" matches any single s-expression, and a sequence of dots ("...") matches any sequence of s-expressions. Thus, "( ... 3 ... )" matches "(3)", "(2 3 4)", but not "(2 4 5)". Similarly, "(* (sha-1 ...) ...)" matches "((foo) (sha-1 3))" but not "((foo) bar (sha-1 3))".

Restrictions are numeric comparison operators that perform simple evaluation on elements of the pattern. a restriction of the form (operator literal value) syntactically matches an s-expression of the form (literal value). The pattern matcher then compares the matched value to the value compared within the give pattern and tests equality/inequality.

Restriction examples:

The pattern matcher supports the following comparison operations: <, >, =, <=, >=, <> (NOT), and each operator exists in both normal and "-!" form. The presence of an "!" does not modify the matching operation but does change the way the overall match construct computes the returned tri-value. For operators ending in "!", match returns "allow" only if every statement that syntatically matches the restriction (not taking into account the comparison operation) satisfies the predicate. For non-"!" operators match returns "allow" if any syntactically-matching statement also satisfies the predicate.

Formal Grammar

The grammar is written in modified form of BNF.
rule :: let-rule | explicit-rule | combine-rule | invoke-rule | install-rule |
        projection-rule | match-rule | variable-name

let-rule :: '(' 'let' '(' variable-name rule ')' rule+ ')'

explicit-rule :: '(' permission-type ['URL' quotedURL+] ')'
permission-type :: 'allow' | 'block'

combine-rule :: '(' combine-operator rule+ ')'
combine-operator :: 'any-allow' | 'only-if-all-allow' | 'any-block' |

invoke :: '(' 'invoke' program-name statement-list optional-argument* ')'

install-rule :: install-program | install-interpreter
install-program :: '(' 'install-program' program-name program-object
                       language-name ')'
install-interpreter :: '(' 'install-interperter' language-name interpreter-object ')'
program-object :: s-expression
interpreter-object :: <binary-object>

projection-rule :: '(' 'tri-value' rule ')' | '(' 'statement-list' rule ')'

match-rule :: '(' 'match' pattern rule ')'
pattern :: '*' | '...' | string-literal | symbol-literal | restriction |
           '(' pattern ')'
restriction :: '(' restriction-operator transmit-name value ')'
restriction-operator :: '<' | '>' | '=' | '<=' | '>=' | '<>' |
                        '<!' | '>!' | '=!' | '<=!' | '>=!' | '<>!'
Note: patterns may contain at most one restriction.

program-name :: quoted-name
statement-list :: '(' statement* ')'
statement :: '(' context content ')'
context :: s-expression
content :: s-expression
optional-argument :: s-expression

Persistence of objects in this system

It is our assumption that none of the structures described here inherently persist across multiple invocations of the trust management environment. That is, when a program installs another program into the program table, that installation is only in effect for the remainder of the current trust management computation. A new top-level input will start with a new program table. We suspect that individual applications will want to create or maintain their own persistent storage (or designate an area of the filesystem for same) and pass in richer initial program and interpreter tables to the trust management system. Individual applications will want for performance reasons to cache

4. Library of Primitive Programs

It is suggested that conforming implementations provide these three standard languages for minimum expressiveness, although applications are only required to provide Profiles-0.92. As mentioned above, applications calling the trust management system are required to provide a language-name/interpreter binding for Profiles-0.92. Applications that provide other languages on bootstrap must also provide those bindings.

5. Examples

In the following examples, the given policy is bound to the action view-URL in the bootstrap program table. The bootstrap program table also provides bindings for "load-label" and, in example 4, "check-md5". The bootstrap interpreter table provides similar, appropriate bindings.
Program Table

Action       | Program                    | Language        
"view-URL"   | <as below>                 | Profiles-0.92
"load-label" | <implementation-dependent> | load-label-language
"check-md5"  | <implementation-dependent> | check-md5-language

Interpreter Table

Language             | Interpreter
Profiles-0.92        | [Profiles-0.92 interpreter]
load-label-language  | [implementation-dependent]
check-md5-language   | [implementation-dependent]

Sample Policy 1: View a URL only if a PICS labels for the URL using the "witnessing" system that asserts "witnessed"

(invoke "load-label" INITIAL-STATEMENT-LIST URL)
 (("load-label" ...) 
  (... (PICS-1.1 ... "service"
        ... (ratings (witnessed 1)))))
This policy loads labels for the given URL and searches for labels in the "third-party-witness.html" rating service that assert "witnessed". If any label matches the given pattern the policy returns a tri-value of "allow".

Sample Policy 2: View any URL with a PICS label in the RSAC system with "s < 2"

(invoke "load-label" INITIAL-STATEMENT-LIST URL)
 (("load-label" ...) 
  (... (PICS-1.1 ... "service" "" ... (ratings (< s 2))))))
This policy has two steps. First, we invoke to find and download labels for the given URL; any labels found will be put on the statement list. We then run the pattern matcher over the now-modified statement list looking for any label using the rating service from "" and with an s rating less than 2.

Sample Policy 3: View URLs only if all PICS label in the RSAC system for the URL say "s < 2"

(invoke "load-label" INITIAL-STATEMENT-LIST URL)
 (("load-label" ...) 
  (... (PICS-1.1 ... "service" "" ... (ratings (<! s 2))))))
This policy is almost identical to Sample Policy 2 above, except that the restriction operator within the pattern matcher is "<!" instead of "<". The "!"-ending restriction operators require every matching statement that is tested against the operator to satisfy the operator.

Sample Policy 4: Combinations of simple filters

(invoke "load-label" INITIAL-STATEMENT-LIST URL)
  (("load-label" ...) 
   (... (PICS-1.1 ... "service"
         ... (ratings (= data-reselling 0))))))
  (("load-label" ...) 
   (... (PICS-1.1 ... "service" "" 
        ... (ratings (< personal-data-collected 3))))))
Here is an example policy that uses labels from multiple rating services. This policy has four steps. In the first step, we load labels for URL by invoking "load-label"; "load-label" adds statements to the statement-list. We then search the returned statements for two types of labels:
  1. Labels using a rating service described by E-Trust, and
  2. Labels using a rating service described by CDT.
Each pattern-match uses criteria specific to one a rating service, and then the results of those two pattern-matches are combined using only-if-all-allow. Thus, in order for the policy to be satisfied there must be labels in both rating services.

Sample Policy 5: A More Complex Profile using multiple invocations

Here is a more complicated example, showing how multiple invocations can be used to "chain" processing of statements.
(invoke "load-label" INITIAL-STATEMENT-LIST URL)
(invoke "check-md5"
 (match ((...) ("" 
                (PICS-1.1 ... ("md5" ...) ...)))
  (("check-md5" ...) 
   ("md5-verified" ("" 
                    (PICS-1.1 ... "service"
                     (ratings (= data-reselling 0)))))))
  (("check-md5" ...)
   ("md5-verified" ("" 
                    (PICS-1.1 ... "service" ""
		     (ratings (< personal-data-collected 3)))))))
This policy takes two arguments, the require statement list and an additional argument of a URL which the application wants to view. These arguments are bound initially to the global variables INITIAL-STATEMENT-LIST and URL by the Profiles-0.92 interpreter.

Sample Policy 5 is like Sample Policy 4 except that this policy additionally requires that labels have valid MD5 hashes before their ratings are used by the system. We assume the existence of a "check-md5" program that verifies the correctness of MD5 hashes contained within PICS labels.