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.
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 databasesThe 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.
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.
(invoke <program-name> <statement-list> <additional-args>*)
invokecalls 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
(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-programcreates bindings in the program table and
install-interpretercreates 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-programexpects to see a statement of the form:
((<context>) (<program-name> <program-body-or-pointer> <language-name>))Similarly,
install-interpreterexpects to see a statement of the form:
((<context>) (<language-name> <interpreter-body-or-pointer>))
(allow URL <URL>+) (block URL <URL>+) (allow) (block)
For example, the operation
(allow URL "http://www.whitehouse.gov/"
"http://w3.org/") 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
"http://www.whitehouse.gov/" "http://w3.org/") reverses the sense
and returns block if the requested URL has either of the
arguments as a prefix and allow otherwise. (These never return
Each combinator returns a statement list consisting of statements
of the form "(allow <prefix>)" for each relevant URL prefix. In the
above example, if "http://www.whitehouse.gov/president" was requested
(allow URL "http://www.whitehouse.gov/"
"http://www.whitehouse.gov/") ) as a list containing one
For use in combinations, it is also convenient to have
unconditional allows and blocks. The operation
returns tri-value allow and the empty statement list; the
(block) returns tri-value block and the
empty statement list.
(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.
(let (<var> <rule1>) <rule>+)
Letbinds the variable
<var>to the value of evaluating
<rule1>for the scope of the remaining rules in the body.
(match <pattern> <statement-list>)
matchreturns the subset of
<statement-list>that matches the given
<pattern>. The pattern-matching language is detailed below.
(statement-list <return-value>) (tri-value <return-value>)These two functions operate on pairs of return values and extract either the
INITIAL-STATEMENT-LIST: This global variable is bound to the statement-list that is passed to a Profiles-0.92 program as its mandatory argument.
URL: This global variable is bound to the first additional argument in the call to a Profiles-0.92 program. The first additional argument is assumed to be the URL of the object of the requested action.
any-allow list consists of one or more rules, and
its semantics are:
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.
only-if-all-allow list consists of one or more rules, and
its semantics are:
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.
any-block list may evaluate
any-block list appears as a
member of an
only-if-all-allow list, then a tri-value of unrated
any-... list has exactly the same semantics as if
the tri-value were block.
Similarly, if an
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.
matchoperator 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.
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 "!",
"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.
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' | 'unless-all-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
view-URLin 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]
(invoke "load-label" INITIAL-STATEMENT-LIST URL) (match (("load-label" ...) (... (PICS-1.1 ... "service" "http://www.witness.org/third-party-witness.html" ... (ratings (witnessed 1))))) INITIAL-STATEMENT-LIST)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".
(invoke "load-label" INITIAL-STATEMENT-LIST URL) (match (("load-label" ...) (... (PICS-1.1 ... "service" "http://www.rsac.org/" ... (ratings (< s 2)))))) INITIAL-STATEMENT-LIST)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 "http://www.rsac.org/" and with an s rating less than 2.
(invoke "load-label" INITIAL-STATEMENT-LIST URL) (match (("load-label" ...) (... (PICS-1.1 ... "service" "http://www.rsac.org/" ... (ratings (<! s 2)))))) INITIAL-STATEMENT-LIST)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.
(invoke "load-label" INITIAL-STATEMENT-LIST URL) (only-if-all-allow (match (("load-label" ...) (... (PICS-1.1 ... "service" "http://www.e-trust.org/privacy-descriptions" ... (ratings (= data-reselling 0)))))) INITIAL-STATEMENT-LIST) (match (("load-label" ...) (... (PICS-1.1 ... "service" "http://www.dma.org/privacy" ... (ratings (< personal-data-collected 3)))))) INITIAL-STATEMENT-LIST))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:
only-if-all-allow. Thus, in order for the policy to be satisfied there must be labels in both rating services.
(invoke "load-label" INITIAL-STATEMENT-LIST URL) (invoke "check-md5" (match ((...) ("http://www.label-bureau.org/" (PICS-1.1 ... ("md5" ...) ...))) INITIAL-STATEMENT-LIST)) (only-if-all-allow (match (("check-md5" ...) ("md5-verified" ("http://www.label-bureau.org/" (PICS-1.1 ... "service" "http://www.e-trust.org/privacy-descriptions" (ratings (= data-reselling 0))))))) INITIAL-STATEMENT-LIST) (match (("check-md5" ...) ("md5-verified" ("http://www.label-bureau.org/" (PICS-1.1 ... "service" "http://www.dma.org/privacy" (ratings (< personal-data-collected 3))))))) INITIAL-STATEMENT-LIST))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.