Subject: Re: PFDL draft

From: [email-masked]
Date: Wed, 25 Nov 1998 13:35:53 -0800

The following is being forwarded to the policy mailing list.
Message originally sent by "John C. Strassner" <[email-masked]>
---------------------------------------------------------------------------

This is a resend; the original appears NOT to have made it to the policy list.

Sanjay,

comments inline.

regards,
John and Stephen

At 07:27 PM 11/24/98 -0500, [email-masked] wrote:
>The following is being forwarded to the policy mailing list.
>Message originally sent by Sanjay Kamat <[email-masked]>
>---------------------------------------------------------------------------
>
>John and Stephen,
>    Thanks for posting pointer to the PFDL document on the policy list.
>After first quick reading of it, I am concerned about the complexity
>of the specification. I am not advocating a quick and dirty approach,
>but I think we should start off with something simple and let it evolve
>based on requirements and implementation experience. 
>
>Here are a few examples of where I believe the spec is getting quite
>overambitious:
>1. You allow "negation" as a valid operator in the conditions. While
>you acknowledge the importance of ability to resolve inter-policy 
>conflicts, have you considered the impact of allowing the "negation"
>operator on the complexity of this problem?  The consistency checking
>with rules whose conditions are: "policyCondition_OR_lists made up of
>policyCondition_AND_lists with negations allowed in individual
>conditions" is an NP-Complete problem, even in its simplest form.

[js] Why is this an NP-Complete problem, "even in its simplest form"?
The simplest form of this expression is a policy_condition_OR_list
comprised of a single policy_condition_AND_list, and a
policy_condition_AND_list comprised of a single
policy_condition_statement. A "simple" policy_condition_statement is:

  'NOT' <policy_condition_expr>

so for example we have:

  IF NOT sourceIPAddress = 199.10.20.1

Why is this statement so hard to check?

We think what you meant to imply is that negating a policy_condition_expr
makes it NP-complete in the general sense (though we are still confused
by your use of the phrase "simplest form"). We don't understand why this
is even harder, let alone NP-complete. Conflict resolution between two
policies is solved in linear time because:

 1) the structure of the conditions can be canonicalized 
    (at worst a  nLog(n) problem -- basically a sort)

 2) the conflict check is linear in that value intersection
    is a linear check

It is clear that to conflict check a single new policy against N
policies requires N pairwise resolutions.  However, since pairwise
resolution does not share N (and, generally, we would expect the number
of conditions to be relatively small AND a conflict occurs ONLY when
every condition conflicts) overall conflict resolution for a single new
policy is linear in the number of policies (NOT NP-complete).

You must be thinking of a harder problem; please enlighten us.

>2. Do we really need the full generality of an arbitrary relation (as
>defined by a relational operator in the policyConditionStatement) between
>policyConditionCategory and policyConditionValuie? Imagine what it will
>do to the consistency checking complexity.

[js] The term <rel_op> will more than likely be limited to IN, NOT IN, =,
!=, >, >=, <, and <=. What would you propose instead?

>The above two are not just important for consistency checking, but they
>also take heavy toll on policy enforcement implementation. 

[js] But they are needed to implement real-world conditions.

I think you are worried that a simple device might not be able to process
all of the PFDL (e.g., only be able to check for = and !=, and nothing
else). However, other devices exist that can process all of the PFDL (and
more).

The point, then, is that we should NOT arbitrarily limit the "complexity" (I
would prefer to call this expressiveness) based on the lowest common
denominator (e.g., the capabilities of the simplest device). We should have
a language that can implement policy in a natural form for the administrator.
It is then the job of some other entity (e.g., the Policy Server) to check
that the policy can be downloaded to and understood by a PEP. If the Policy
Server determines that a particular policy can not be understood by a device
(either before or after it downloads the policy to the device), then it is
the job of the Policy Server to either translate that policy to a form
suitable for the PEP or kick it back to the user. Constraining the language
in advance to ensure that this will never happen will leave us a language
that is not useful.

>I have a few more questions about the details in the draft, but the main
>points I would like debated are: 
>
>1. Are we really ready for the PFDL yet? Do we have a large set of
>"networking policy" examples that suggest the complexity of this
>specification? 

[js] Yes, it's in the charter. And networking policy examples abound in the
work of DiffServ and RAP, not to mention many other groups.

>2. Could we take the pragmatic approach of first hashing out a simple
>definition of policyConditions for IP traffic (possibly in terms of an LDAP
>schema, since we also need to address the policy rule storage issue), and
>then evolving the PFDL rather than
>the other way around? This way, we can at least start from the reasonably
>well understood requirements of policies for QoS, and security, for which I
>believe we can define policyConditions that do not require so much
>complexity.

[js] That's what we're doing, except we are explicitly NOT considering
security yet, since that further complicates things. In addition, if we
start by tying this to LDAP, we will have destroyed interoperability.
This is because we will end up developing a schema that works very well
for LDAP but is cumbersome at best to implement on other data stores.
Furthermore, LDAP has no way of representing relationships between
objects - it is simply a flat store that describes objects.

Therefore, the best way to proceed is to develop an information model
that is independent of any one particular repository implementation. The
information model will express structure (e.g., schema) as well as
relationships between objects and how objects interact.

Given such an information model, we can then produce an optimized mapping
to any number of data stores, including an LDAP directory.

I thought that this was clear in the BOF - if it wasn't, please tell me
and then this should be a formal agenda item for the WG.

So, in summary, I don't understand your concern expressed in 2 above
(your wish for a pragmatic approach); could you please elaborate?

>-Sanjay Kamat
>IBM Research