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 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.
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>*)
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.
(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>))
(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 (block URL
"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
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 "http://www.whitehouse.gov/president" was requested
then (allow URL "http://www.whitehouse.gov/"
"http://w3.org/") returns ( (allow
"http://www.whitehouse.gov/") ) 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.
(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>+)
Let binds the variable <var> to the
value of evaluating <rule1> for the scope of the
remaining rules in the body.
(match <pattern> <statement-list>)
match returns 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
statement-list or tri-value contained within.
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.
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.
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.
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-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]
(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.