Subject: PFDL draft

From: [email-masked]
Date: Tue, 24 Nov 1998 19:27:15 -0500

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.

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.

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

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? 
   
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.

-Sanjay Kamat
IBM Research

---

From: [email-masked]
Date: Wed, 25 Nov 1998 08:35:52 -0800

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

Sanjay,

comments inline.

regards,
John and Stephen

>Message originally sent by Sanjay Kamat <[email-masked]>

[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.

>   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?

>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.

>   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.

>   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?

---

From: [email-masked]
Date: Wed, 25 Nov 1998 12:24:50 -0500

The following is being forwarded to the policy mailing list.
Message originally sent by Michael Richardson <[email-masked]>
---------------------------------------------------------------------------

-----BEGIN PGP SIGNED MESSAGE-----

  [Sanjay, if I attribute anything to you incorrectly, sorry... ]

>>>>> "Sanjay" == Sanjay Kamat <[email-masked]> writes:
    Sanjay> so for example we have:

    Sanjay> IF NOT sourceIPAddress = 199.10.20.1

    Sanjay> Why is this statement so hard to check?

  I have some issues if the policy is going to say things like that.
  I will retain them until I see a real example that I can understand, 
including where this check is supposed to be done, and by whom.

    Sanjay> NP-complete. Conflict resolution between two policies is solved
    Sanjay> in linear time because:

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

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

  If we are worried about how hard it is to check policies, and you give me
something linear in the number of policies, I'm already worried.

    Sanjay> The point, then, is that we should NOT arbitrarily limit the
    Sanjay> "complexity" (I would prefer to call this expressiveness) based
    Sanjay> on the lowest common denominator (e.g., the capabilities of the
    Sanjay> simplest device). We should have a language that can implement
    Sanjay> policy in a natural form for the administrator. It is then the
    Sanjay> job of some other entity (e.g., the Policy Server) to check that
    Sanjay> the policy can be downloaded to and understood by a PEP. If the

  I suggest that anything that uses nested conditionals is not understandable 
to the administrator.
 
    Sanjay> Policy Server determines that a particular policy can not be
    Sanjay> understood by a device (either before or after it downloads the
    Sanjay> policy to the device), then it is the job of the Policy Server to
    Sanjay> either translate that policy to a form suitable for the PEP or
    Sanjay> kick it back to the user.  Constraining the language in advance
    Sanjay> to ensure that this will never happen will leave us a language
    Sanjay> that is not useful.

  I further suggest that anything that uses nested conditionals is not easily
optomizable by any program into something that can be used to program a
wire-rate PEP. You need higher level constructs, and you need them to be
declarative.
  
    >> I have a few more questions about the details in the draft, but the
    >> main
    Sanjay> points I would
    >> like debated are:
    >> 
    >> 1. Are we really ready for the PFDL yet? Do we have a large set of
    Sanjay> "networking policy"
    >> examples that suggest the complexity of this specification?

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

  Then, they need to be specified as examples, and either a draft, or at
minimum, a well written message to the list, needs to 

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

  Okay, I fail to understand how the PFDL has anything to do with what you
just said.

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

  Do it with examples. All constructs should be justify their existance via
some concrete, real life example. Only once we understand all of this do
we define anything as abstract as a BNF.

   :!mcr!:            |  Solidum Systems Corporation, http://www.solidum.com
   Michael Richardson |For a better connected world,where data flows faster<tm>
 Personal: <A HREF="http://www.sandelman.ottawa.on.ca/People/Michael_Richardson/Bio.html">[email-masked]</A>. PGP key available.
 Corporate: <A HREF="mailto:[email-masked]">[email-masked]</A>.

---

From: [email-masked]
Date: Wed, 25 Nov 1998 10:34:28 -0800

Michael,

the attributions that you make to Sanjay came from my response to Sanjay.
Comments on your responses inline. Do I need to resend my original response
to Sanjay to the list again? I'm concerned that you think that the excerpts
below are from Sanjay...

regards,
John

>Message originally sent by Michael Richardson <[email-masked]>

[js] If you're going to bring up the issue, which you did, it seems like
you might as well voice your concerns now.

>something linear in the number of policies, I'm already worried.

[js] This is somewhat out of context. I was responding to Sanjay's assertion
that the problem in its simplest form was NP-complete.

But on another subject, how can policy conflict resolution NOT be at least
this complicated?

>  I suggest that anything that uses nested conditionals is not
understandable 

[js] But the question is: Should the language be designed in such a way as to
prevent that? I think not.
 
>wire-rate PEP. You need higher level constructs, and you need them to be

[js] This is certainly true for wire-rate policing, but the PFDL is intended
for more than that. Several implementations suggest first defining policies
in a console and then validating those policies in some device (e.g., a
Policy Server) BEFORE they are sent to the PEP.

Therefore, the PFDL should enable *reasonably* detailed policies to be
specified so that they can be checked for conflict and/or translated to a
form (e.g., a set of ACLs) that can be implemented by the PEP.

[js] You're taking this out of context. Sanjay originally said:

>>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...

and the above response, from me, was in response to that approach. The is a
means to express the information model.

>we define anything as abstract as a BNF.

[js] I disagree - I think defining the language in cooperation with a
framework aids the understanding of both.
> Personal: <A
HREF="http://www.sandelman.ottawa.on.ca/People/Michael_Richardson/Bio.html">
[email-masked]</A>. PGP key available.
>-----BEGIN PGP SIGNATURE-----
>Version: 2.6.3ia
>Charset: noconv
>Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface
>
>iQCVAwUBNlw9VW5vCG0TOZrRAQG3kAQAs7ZfjrIFe3Y/WQzgz0gaMgjK4Vx54Kyb
>fwuJ3VCJO8Q0QodqvCAIt7QDUmQQqHp76ZUxEpJ4eZDa+Es/2+N5TScvCqvMwtlm
>nlrc2DfQX40SbGf/0y9khdy0HfOgkXlF9ck4eiQxrPS5AQ8KF6kSK1VbNWz7RjNp
>Bf1I+39OjB8=
>=IpWT
>-----END PGP SIGNATURE-----
>
>