Trust Management for the World Wide Web

4.3Profiles-0.92

The Profiles-0.92 language [BCKLMRS] was developed in conjunction with the REFEREE trust management system. Profiles-0.92 is a flexible and modular policy language aiming to exploit and demonstrate important features in the REFEREE trust management system.

An instance of a Profiles-0.92 language is a policy. A policy consists of an ordered sequence of rules. Each rule is represented as an s-expression, in which the first token is an operator, and the rest of the tokens are operands. The evaluation of a policy is top-down. The returned value of the last rule is the returned value of the policy itself. To be easily ported to REFEREE, the returned value of a rule is the same as REFEREE itself, and is the same as REFEREE modules: a tri-value answer with a statement list as justifications.

Profiles-0.92 is rich in expressiveness compared with PicsRULZ. This section highlights six important rule syntax and semantics. Readers should refer to [BCKLMRS] for more detail. A snapshot of the complete language syntax in the modified BNF form is provided in Appendix B..

URL Prefix Matching

(url-match URL (+) [
])

This function provides a means of explicitly returning a tri-value based on substring matches against particular URLs. The first argument is the symbol URL. The second argument is a list of strings to be matched against the given URL. The third argument is a Boolean value which determines whether the string matching should be exact or prefix. If this argument is true then URL must exactly match one of the strings for the resulting value to be true. If false, one of the strings must be a prefix of URL in order for the resulting value to be true. The

argument is optional; if it is not present it is assumed to be false and prefix matching is performed.

For example, the function

(url-match URL ("http://web.mit.edu"

"http://www.wellesley.edu"))

returns true if the requested URL has any of the listed URLs as a prefix, and otherwise it returns false. It is not possible for url-match to return an unknown tri-value.

The statement-list returned by URL prefix match consists of statements of the form (url-match +) for each relevant URL prefix. In the above example, if "http://web.mit.edu/benbiddle" was requested then the function returns

((url-match "http://web.mit.edu"))

as the content of the returned statement.

Pattern Matching

(match
)

The pattern matching function matches the s-expression
against statements in . A match happens when a pattern and a statement are syntactically and structurally equivalent.

In the simplest form, a parenthesis in the pattern matches a parenthesis and a literal element matches a literal element. In addition, there are four special pattern-matching elements:

.	zero or one literal or parenthesized s-expression
*	zero or more literals and parenthesized s-expressions
+	matches one or more literals and parenthesized s-expressions
(RESTRICT operator literal value)	matches some s-expressions of the form (literal value)

Thus, (* 3 *) matches (3) and (2 3 4), but not (2 4 5). Similarly, (. (sha-1 +) *) matches ((foo)(sha-1 3)), but not ((foo) bar (sha-1 3)). Quoted strings are matched on a case-sensitive basis; all other elements are matched insensitive to case.

RESTRICT pattern-matching elements allow arithmetic comparison on numbers in an s-expression. This is important in the PICS environment, in which a policy may want to test whether the value associated with a transmit-name is less than some threshold value. Arithmetic comparison operator can be one of <, >, =, <=, >=, <>, where <> represents "not equal". Literal is a symbol (transmit-name in PICS) that identifies the value. A comparison operation happens only if both the pattern and the matching statement have the same literal field. For example, (RESTRICT < n 3) matches (n 2), and (* (RESTRICT < n 3) *) matches (foo bar baz (n 2) quux), but does not match (foo bar baz (n 3) quux).

If no statements syntactically match the pattern, the returned tri-value is unknown. If some statements match and no restrictions are included, the returned tri-value is true. If statements match and there are restrictions, the returned tri-value is true or false depending on predicates in the restrictions. Each comparison 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 true only if every statement that syntactically matches the restriction satisfies the predicate. For non-"!" operators, match returns "true" if any syntactically-matching statement satisfies the predicate. If more than one restriction is present, their tri-values are implicitly anded together. If any restriction is false the match returns false. For example, if the statement-list ((n 4) (n 2)) and the pattern is (RESTRICT < n 3), the match would return true, because the second statement (n 2) matches the pattern. But if the pattern changes to (RESTRICT , the match would return false because not all statements in the matched statement list match the pattern.

The backslash \ character has special meaning within patterns; it is used to quote pattern elements that would normally have special semantics. That is, to match the character + as opposed to one or more s-expressions, use \+ is used in the pattern. Similarly, the reserved word RESTRICT can be escaped with \RESTRICT to match the actual symbol instead of the special restrict pattern matcher.

Combinations

(and +)

(or +)

(threshold-and +)

(not )

(true-if-unknown )

(false-if-unknown )

Profiles-0.92 provides six tri-value operators. The operators and, or and threshold-and are multi-argument operators and not, true-if-unknown and false-if-unknown are unary operators. Each multi-argument operator takes zero (one for threshold-and) or more rules as input. The output tri-value is computed based on the input tri-values, and the output of the statement-list is a concatenation of the input statement-lists. Unary operators work the same way, except that the output of the statement-list is inherited directly from the input. The truth tables for the six operators are provided below.

The and operator

The and operator is the three-valued version of the Boolean and operator. Table 2 describes the operation of and when it is given two arguments. The first row represent the truth value for the first argument, the first column represent the truth value for the second argument, and the rest of the cells represent the result of an and operation.

rule1 \ rule2	true	unknown	false
true	true	unknown	false
unknown	Unknown	unknown	false
false	False	false	false

Table 2 Truth table for the and operator

The and operator can take any number of arguments. For more than two arguments, and operator recursively reduces itself one argument at a time:

(and arg1 arg2 … argn) = (and (… (and arg1 arg2) … argn)

The and of a single argument is that argument itself. The and of no argument is true by definition. If one of the arguments return false, the and rule terminates and the rule returns a false, because further evaluations will not change the outcome of a false.

The or operator

The or operator is the three-valued version of Boolean or operator. Table 3 describes the operation of or when it is given two arguments:

rule1 \ rule2	true	unknown	False
true	true	true	True
unknown	true	unknown	Unknown
false	true	unknown	False

Table 3 Truth Table for the or operator

As and operator, or operator can take any number of arguments, and they are recursively reduced if more than two arguments are present. The or of a single argument is that argument itself. The or of no arguments is false by definition. If one of the arguments is evaluated to be true, the or terminates and returns a true, because further evaluation does not change the outcome of a true.

The not operator

The not operator is the three-valued version of Boolean not operator. It takes exactly one argument. Table 4 describes the operation of the not operator:

	output
true	false
unknown	Unknown
false	true

Table 4 Truth Table for the not operator

The true-if-unknown operator

The true-if-unknown operator is a projection function from three-valued logic to Boolean logic. It takes exactly one argument:

	output
true	true
unknown	true
false	false

Table 5 Truth Table for the true-if-unknown operator

The false-if-unknown operator

The false-if-unknown operator is also a projection function from three-valued logic to Boolean logic. It takes exactly one argument:

	Output
true	true
unknown	false
false	false

Table 6 Truth Table for the false-if-unknown operator

The threshold-and operator

The threshold-and operator implements "any m of n" semantics on a list of three-valued arguments. The threshold-and operator takes at least one argument, the threshold value as a non-negative integer. A call to threshold-and looks as follows:

(threshold-and threshold arg1 arg2 arg3 … argn)

Let n_T, n_F and n_U be, respectively, the number of arguments to threshold-and arg1…argn that evaluate to true, false, and unknown. We have 0 <= n_T,n_F,n_U, <= n, and further n_T + n_F + n_U = n. Then the value of threshold-and is computed as follows:

• 
  if n_T >= threshold, return true.
  
• 
  else if n_T < threshold and n_T + n_U >= threshold, return unknown.
  
• 
  else if n_T + n_U < threshold, return false.
  
• 
  by definition, (threshold-and 0) evaluates to true.
  

Invocations

(invoke
*)

Invoke calls the policy named
with a copy of the and possibly some other additional arguments. When the called policy returns, its returned value is a pair consisting of a tri-value and a statement-list. By convention, the caller module appends the returned statement-list of the callee to its internal statement-list. For every statement in the returned statement-list, Profiles-0.92 prepends the name of the called policy to the context of the statement, and appends the statement to the original statement-list that was referenced in the call to invoke. The returned value of the (invoke ...) construct is a pair of the tri-value returned by the called policy and the tagged statements appended to the statement-list.

Installations

(install-policy )

(install-interpreter )

Recall that in Profiles-0.92, there are two types of entries in a REFEREE module database: policy and interpreter. Install-policy creates policy bindings in the module database and install-interpreter creates interpreter bindings in the module database. In both cases, the information required to make these bindings are passed within a statement-list containing a single statement, and they are of the form:

(() ( ))

Local Variable Binding

(let (+) +)

Let creates a new sub-environment of the current execution environment and creates in the sub-environment new variable-value bindings. The created local bindings are listed in the list of bindings +. Each is a list of the form: ( ). The variable is bound to the result of evaluating . Each may optionally be null, in which case the variable is defined but its value is unassigned. The bindings remain in effect for the scope of the let rule.

A Profiles-0.92 policy is invoked with a list of argument. Each argument is bound to a local name at the beginning of the evaluation. The first two arguments are mandatory in Profiles-0.92, and are bound to the local name STATEMENT-LIST and URL, respectively. Optional statements are bound to the local names ARG3, ARG4, and so on.