Subject: Policy Execution Requirements

From: "Black, David" <[email-masked]>
Date: Fri, 19 Feb 1999 20:19:08 -0500

Here's the (long) explanation of this area that I promised/was volunteered
for earlier this week.  I'd like to thank Silvano Gai, Hugh Mahon,
and Andrea Westerinen for their contributions, but since these
are my words, credit should be shared with them for the good
ideas in here, but blame for the bad ideas is primarily mine.

Apologies for the length of this, but I hope the fact that this
is required for a coherent explanation is indicative of the importance
of addressing this area in the schema draft.

--- Policy Execution Engine Determinism ---

The basic problem is that we want different PDPs looking at the same policy
under the same circumstances to come to the same conclusion.  The
engineering
group that brought you the policy schema has had long discussions about this
topic that can be summarized as follows:

	- This is about distribution and time, specifically what happens
when
		multiple PDPs have the same policy rules and/or a PDP
evaluates
		the same rules under more or less the same conditions at
different times.
	- This is about error cases of policy underspecification where the
decision about
		which rule 	to fire makes a big difference, but the
network administrator
		has not expressed a preference (via setting priority) for
some reason.
	- Under these circumstances, is it ok for parts of the network to
make
		different decisions based on the same policy at different
times
		when the policy expresses no reason why the decisions should
be different?

IPsec already requires this for obvious reasons (connectivity fails
otherwise), and
I believe it's the case that QoS policy needs this for dealing with QoS that
spans multiple PDPs in order to avoid peculiar failure cases.  The basic
argument
is that it's much easier to cope with something that is consistently wrong
as
opposed to sporadically wrong in both time and space.

Consider one of our well-worn examples - we have two rules
	Engineers get Bronze service
	John gets Gold service
Now suppose John is an engineer, and the policy has failed to express a
priority among these two rules (yes, this is a mistake, but policies are
written by humans, and humans make misteaks).  If we allow arbitrary PDPs
to reach independent decisions at arbitrary times, all kinds of peculiar
failure
modes become possible.  For example, at 3am, one of the PDPs suddenly
reevaluates
policy because some unrelated portion of policy got updated, and decides
that John is entitled only to Bronze -- suddenly John doesn't have
Gold service, and a transfer that John cared about is suddenly disrupted --
this
could be even worse if the PDP re-reevaluates 10 minutes later and restores
Gold.

This sort of problem can be resolved by specifying criteria for how to
choose
between two potentially conflicting rules that are equally eligible for
execution.
The criteria can be arbitrary but must be consistent (i.e., yield the same
decision)
over time and space.

-- Scope of Determinism

Global won't work, as one would like to have unrelated things happen
concurrently
in the policy engine.  Hence I think we need a notion of activation (there
is a
reason the policy engine has been asked to do something), and a notion of
state bindings.

Example: The policy engine has been invoked because someone is trying to log
on to the system.  The username "johns" and the password "mumblefratz" are
bound
to the variables $user and $password, resulting in it being reasonable to
write a
rule of the form:

	If $user is a member of Group::engineers then ...

(Apologies for the mangled syntax)

Absent the ability to do runtime binding of $user, one winds up with a rule
for
each member of the group, an approach that loses the benefits of groups and
does not scale. Additional useful notions are (1) default binding for values
not present
and (2) required values (invocation fails if value is unbound - can be
implemented by
not specifying a default).  Further binding can occur during the invocation
(e.g.,
bind $ipaddr to the IP address allocated by the DHCP.allocate action).

The scope of determinism is then the activation -- the thing that the policy
engine
does to respond to a specific invocation, and this is also the scope of the
variable
bindings.

-- The Determinism Requirement

The requirement is:

  Given a set of policy rules, and system state (i.e., the values
  that make it possible to evaluate all conditions), and an invocation (with
  associated variable bindings), there is exactly one correct sequence of
rule
  firings (execution of the action portion of a rule) that the policy engine
  performs in direct response to the invocation (i.e., in the binding
context
  of the invocation).  A sequence may consist of one or no rule firings.

The words "system state" are an oversimplification, because the state of the
system/network is necessarily dynamic, and cannot be frozen in order to
execute
the rule.  If the state is static, there must be exactly one correct
execution
sequence.  Dynamic state complicates this -- in essence there must be a
sequence of state sampling actions leading to the condition evaluation
that leads to the chosen execution.  The moral here is don't change state
underneath the policy engine that the policy depends upon to make decisions
--
the notion of activation variable binding is useful here, as a bound
variable
won't change value until the activation is complete.  In general, policy
ought
not to be highly dependent on values that are necessarily dynamic (e.g.,
small
fluctuations in the level of traffic on the link should not have dramatic
consequences of flip-flopping large portions of the policy).

Now that Andrea has explained the Mandatory attribute, this is similar to
the
dynamic state issue -- there must be some subset of the policy rules that
contains
all of the Mandatory rules that yields the rule firings.  Caveat
administrator
on the use of the Mandatory attribute, because it is inherently
non-deterministic;
the policy engine decides at runtime whether it "feels like" evaluating the
non-mandatory rules, and hence misuse of the Mandatory attribute can yield
policies with bizarre results.

One of the reasons for the "direct response" and "binding context" wording
in the
requirement is that an action of a rule could result in another invocation
of the
policy engine - the results of that invocation may not be deterministic with
respect
to the original one due to system state changes in the interim.  Implicit
passing
of the entire binding context across a rule action that causes a new policy
engine
invocation is a bad idea; one should instead pass only the explicit values
that need
to be bound to variables in the new invocation as parameters to that
invocation.

-- Multiple Rule Firings

IMHO, firing multiple rules in response to an invocation is a requirement.
The
major motivation for this is functional scalability of policy specification.
When a user logs in, one may need to do the following things:
	- Check that the authentication is valid
	- Set up an IP address and other DHCP parameters
	- Configure the border router with packet classification and QoS
parameters
Beyond this, there may be some servers and firewalls that need to be
configured
with the IP address.  All three of the listed items involve policy, and each
may
involves a separate set/group of rules that one would like to write/maintain
independently.  Forcing all of these actions to be combined into a single
rule
is an invitation to complexity and maintenance problems.

An alternative approach if an invocation can only fire one rule is to
convert
the login event into three policy invocations.  IMHO, this is the beginning
of 
a slippery slope, whose end result is a scripting language to which the
policy
engine is slaved to make occasional decisions.  Over time, actions will
migrate
into the scripts, making it necessary to understand both the scripts and the
policy expressed in the schema to figure out what's going on.  IMHO,
scripting
language specification is an area into which I think the policy WG should
*not* go.
I would like to see us make it possible to do meaningful policy
specification
without having to resort to a scripting language to drive the policy engine.

-- Ordering of Rule Firings

The straightforward solution to this problem is that the action sets of
multiple rules
fired in response to a single invocation are ordered with respect to one
other.
This means that all the actions of the first rule occur before all the
actions of
the second rule, etc., but ordering of actions within a rule are governed by
the
existing action ordering support in the schema.  To be more precise, this is
how things should appear to the network administrator should see.  The
actual underlying 
requirement is database-like serializability of the rule action sets, to
allow a policy
engine that understands how actions do/don't interfere to introduce
concurrency that
doesn't affect the final result.

The alternative of allowing the multiple rules to fire concurrently
introduces a
need to specify action ordering across rules, which quickly leads to
unmanageable
complexity.  This idea doesn't deserve the two sentences I've spent
dismissing it.

There are two remaining problems
	- Rule selection: If multiple rules can be fired, what happens?
	- Policy invocation termination: How do we know we're done?

-- Rule selection

If condition evaluation leads to multiple rules that can be fired, the
engine needs to
pick one and fire it.  The rule to be chosen is the one with the highest
priority; if
there are multiple rules with the highest priority, pick the one that has
the
lexicographically first DN.  If the same policy is in multiple repositories,
the
same DN structure SHOULD be used to obtain consistent results (fiddling with
this
structure will also cause problems with our n:DN and n:{+,-}:DN syntaxes,
making this
an obvious thing to discourage).  A policy administrator who doesn't like
the results
of lexicographic choices should go adjust rule priority.  Policy
engines should be able to log an event indicating that a lexicographic
choice was made.
Introducing a priority attribute on policyGroup may be very useful in
helping
administrators achieve the right execution order (this dominates rule
priority, and
one deals with multiple policyGroup priorities via lexicographic ordering).

After firing one rule, the policy engine needs to go look for the next rule
(if any)
to fire as part of this invocation.  In discussion among the folks who
contributed to
this mail, it was not completely clear whether conditions should be
re-evaluated as
part of looking for this rule.
	Advantages of re-evaluation: Implementation may be simpler as one
doesn't
		have to form a set of candidate rules, any fired rule always
reflects
		the current state of the network.
	Disadvantages of re-evaluation: Some rule condition optimizations
(e.g.,
		common subexpression elimination) no longer apply, the
number of
		rule firings that respond to an invocation is potentially
unbounded,
		and in particular it's too easy to write infinite policy
rule loops
		(e.g., two rules, each of which adjusts the state of the
system to
		cause the other to fire).
The tentative conclusion is to not re-evaluate conditions.  This is based in
part on the underlying assumption that a policy invocation should not run
for very long,
and hence whether the state used to evaluate conditions is still current
shouldn't
be an issue.

-- Invocation Termination and Conflict Resolution

By default an invocation ends when there are no rules to fire.  I think we
also need a DONE action of some sort to terminate the invocation early.
This
is also necessary to distinguish between two possible uses of priority:

	- Execute higher priority rule and its actions INSTEAD of lower
priority
		rule and actions. [Conflict Resolution]
	- Execute higher priority rule and its actions BEFORE lower priority
		rule and actions. [Ordering]

The INSTEAD case is indicated by the DONE action in the rules involved.
Scoping of DONE
is an issue, as global scope (i.e., end the invocation) makes policy
decomposition into
separate written and maintained parts essentially impossible.  I would
suggest
scoping of DONE to a policyGroup, and putting the DN of the group into the
action to
make it explicit.  There are some annoying details about what to do when a
rule is
independently contained by two unrelated policyGroup's -- the right answer
may be
the proverbial "don't do this" -- i.e., don't expect DONE to work properly
in that
context.  The DONE action also complicates the implementation of a policy
engine by
requiring that the set of candidate rules that could be executed for an
invocation
be organized to reflect the policyGroup hierarchy.

Sequential rule firing and the DONE action address an important piece
of the conflict resolution problem.  Runtime conflict resolution is obtained
by picking
one of the "conflicting" rules to fire first.  Notice that it's not
necessary for
the policy execution engine to examine the actions to in order to detect a
conflict. 
The fired rule can then disable conflicting alternatives by executing a DONE
action
against the policyGroup that contains both it and the conflicting
alternatives.  If
multiple "conflicting" rules are fired, then the results are whatever the
results
are of firing those rules in the order fired.  This overall approach
encourages
policy designers to put potentially conflicting rules in the same
policyGroup, which
sounds like an application of good software engineering principles, IMHO,
and should
be encouraged in the draft.

---- General Philosophical Difference ---

In the process of discussing these issues, we ran into a philosophical
difference
about the level of policy specification and the resulting use of policy.
The
two viewpoints can be roughly summarized as follows:

(1) Policy is essentially executable by a PEP device.  The responsibility of
the
	PDP is partial evaluation of policy to determine which rules should
be
	downloaded into a PEP and executed there (e.g., by checking rule
conditions
	on fields in each packet).  This leads to examples of rules that
deal
	with IP address ranges, DSCPs, netmasks, etc. (bottom of Shai's
slide in
	the meeting earlier this week).

(2) Policy does not in general propagate beyond PDPs, and the PDP/PEP
interface
	may well be based on concepts that don't have any resemblance to the
policy
	schema.  Policy is executed in the PDP, with the actions applied to
the PEP.
	This leads to examples of rules that deal with users, QoS services,
bandwidth
	brokerage, etc. (top of Shai's slide earlier this week).  Lower
level
	"conditions" (e.g., if this is http to/from a.b.c.d/32, mark with
DSCP 8)
	turn up as rule actions to do things like set values in a MIB.

My preference is for (2), but I hope I've fairly represented (1).  Part of
the
reason this difference of opinion turns up in this context is that unbounded
policy invocation execution is fatal for things that must be done at wire
speed
[viewpoint (1)].

--David

---------------------------------------------------
David L. Black, Senior Technologist
EMC Corporation, 42 South St., Hopkinton, MA  01748
+1 (508) 435-1000 x75140, FAX: +1 (508) 497-6909
[email-masked]
---------------------------------------------------