OASIS eXtensible Access Control Markup Language (XACML) TC

All,

I promised to send a variant of the deny overrides
policy combining algorithm which does not have the "surprising"
behavior which Olav Bandmann discovered. Here it is:

Decision soundDenyOverridesPolicyCombiningAlgorithm(Policy policy[])
{
    Boolean atLeastOnePermit = false;
    Boolean atLeastOneIndeterminate = false;
    for( i=0 ; i < lengthOf(policy) ; i++ )
    {
        Decision decision = evaluate(policy[i]);
        if (decision == Deny)
        {
            return Deny;
        }
        if (decision == Permit)
        {
            atLeastOnePermit = true;
            continue;
        }
        if (decision == NotApplicable)
        {
            continue;
        }
        if (decision == Indeterminate)
        {
            atLeastOneIndeterminate = true;
            continue;
        }
    }
    if (atLeastOneIndeterminate)
    {
        return Indeterminate;
    }
    if (atLeastOnePermit)
    {
        return Permit;
    }
    return NotApplicable;
}

The intuition here is that if we get a deny, then it doesn't matter what
anything
else evaluated to. In case there was at least on indeterminate, then we have
to return indeterminate since the result could have been a deny or a permit.
If there has been no deny or no indeterminate, then we can be sure that
the result is permit if there was a permit.

Olav has also found surprises in the permit overrides
algorithm. The algorithm is currently:

Decision permitOverridesPolicyCombiningAlgorithm(Policy policy[])
{
    Boolean atLeastOneError = false;
    Boolean atLeastOneDeny  = false;
    for( i=0 ; i < lengthOf(policy) ; i++ )
    {
        Decision decision = evaluate(policy[i]);
        if (decision == Deny)
        {
            atLeastOneDeny = true;
            continue;
        }
        if (decision == Permit)
        {
            return Permit;
        }
        if (decision == NotApplicable)
        {
            continue;
        }
        if (decision == Indeterminate)
        {
            atLeastOneError = true;
            continue;
        }
    }
    if (atLeastOneDeny)
    {
        return Deny;
    }
    if (atLeastOneError)
    {
        return Indeterminate;
    }
    return NotApplicable;
}

The order of the last two if statements is "wrong". If there has been an
indeterimnate,
the results should be indeterminate since the policy could have been either
permit or deny. Only if there is neither permit nor indeterminate can we
return deny
for sure.

Here is an example of a "weird" situation which can happen because of this:

    PS1
    /\
   /  \
  P2  PS3
      /
     / 
    P4

Policy set 1 has a permit overrides combining algorithm. Policy 2
evalutes to deny.
Its internals do not matter. PS3 contains one policy P4 and uses a
only-one-applicable
combining algorithm. P4 gives permit.

This means that PS3 gives permit, and PS1 combines the permit and deny
into a permit.
The overall result is a permit.

Now, add policy 5, which also evaluates to permit:

    PS1
    /\
   /  \
  P2  PS3
      /\
     /  \
    P4  P5

This causes PS3 to become indeterminate, which in turn causes PS1 to
become deny.

So, here is the "weirdness": the overall result was Permit, we added one
more Permit
into it, and this additional permit made the end result into a deny.

Of course, since combining algorithms in general can do anything, this is
not "wrong" in the strict sense. It is according to spec.

However, is this the best spec for the standard algorithms? That they
may invert
decisions is a bit surprising and makes analysis of a complex system/policy
difficult.

There is no real advantage with this behavior, and it could cause accidents
for people not aware of it. And those who want a system with some kind
of certified assurance level will find that it his harder to analyse the
system.

Best regards,
Erik

I've diff'd the first algorithm against the standard deny-overrides 
below for easier comparison.  I agree that the proposed variants are 
better, although I see the use of "onlyOneApplicable" as an equal 
problem in the example you give.  Presumably in that case, besides the 
PEP getting a response of "Indeterminate", the PAP should get an error 
saying "onlyOneApplicable" had failed - this is a failure of policy 
design.  With distributed, dynamic policies, it is not always possible 
to detect this situation ahead of time statically unfortunately.

Anne

Erik Rissanen wrote On 02/16/07 11:37,:
> I promised to send a variant of the deny overrides
> policy combining algorithm which does not have the "surprising"
> behavior which Olav Bandmann discovered. Here it is:
> 
> Decision soundDenyOverridesPolicyCombiningAlgorithm(Policy policy[])
> {
>     Boolean atLeastOnePermit = false;
>     Boolean atLeastOneIndeterminate = false;
>     for( i=0 ; i < lengthOf(policy) ; i++ )
>     {
>         Decision decision = evaluate(policy[i]);
>         if (decision == Deny)
>         {
>             return Deny;
>         }
>         if (decision == Permit)
>         {
>             atLeastOnePermit = true;
>             continue;
>         }
>         if (decision == NotApplicable)
>         {
>             continue;
>         }
>         if (decision == Indeterminate)
>         {

STD:          return Deny;

>             atLeastOneIndeterminate = true;
>             continue;
>         }
>     }
>     if (atLeastOneIndeterminate)
>     {
>         return Indeterminate;
>     }
>     if (atLeastOnePermit)
>     {
>         return Permit;
>     }
>     return NotApplicable;
> }
> 
> The intuition here is that if we get a deny, then it doesn't matter what
> anything
> else evaluated to. In case there was at least on indeterminate, then we have
> to return indeterminate since the result could have been a deny or a permit.
> If there has been no deny or no indeterminate, then we can be sure that
> the result is permit if there was a permit.
-- 
Anne H. Anderson             Email: Anne.Anderson@Sun.COM
Sun Microsystems Laboratories
1 Network Drive,UBUR02-311     Tel: 781/442-0928
Burlington, MA 01803-0902 USA  Fax: 781/442-1692

[I did not give the complete diff in the first edition of this comment]

I've diff'd the first algorithm against the standard deny-overrides
below for easier comparison.  I agree that the proposed variants are
better, although I see the use of "onlyOneApplicable" as an equal
problem in the example you give.  Presumably in that case, besides the
PEP getting a response of "Indeterminate", the PAP should get an error
saying "onlyOneApplicable" had failed - this is a failure of policy
design.  With distributed, dynamic policies, it is not always possible
to detect this situation ahead of time statically unfortunately.

Anne

Erik Rissanen wrote On 02/16/07 11:37,:
> I promised to send a variant of the deny overrides
> policy combining algorithm which does not have the "surprising"
> behavior which Olav Bandmann discovered. Here it is:
> 
> Decision soundDenyOverridesPolicyCombiningAlgorithm(Policy policy[])
> {
>     Boolean atLeastOnePermit = false;
>     Boolean atLeastOneIndeterminate = false;
>     for( i=0 ; i < lengthOf(policy) ; i++ )
>     {
>         Decision decision = evaluate(policy[i]);
>         if (decision == Deny)
>         {
>             return Deny;
>         }
>         if (decision == Permit)
>         {
>             atLeastOnePermit = true;
>             continue;
>         }
>         if (decision == NotApplicable)
>         {
>             continue;
>         }
>         if (decision == Indeterminate)
>         {

STD:          return Deny;

>             atLeastOneIndeterminate = true;
>             continue;
>         }
>     }

STD: start omit

>     if (atLeastOneIndeterminate)
>     {
>         return Indeterminate;
>     }

STD: end omit

>     if (atLeastOnePermit)
>     {
>         return Permit;
>     }
>     return NotApplicable;
> }
> 
> The intuition here is that if we get a deny, then it doesn't matter what
> anything
> else evaluated to. In case there was at least on indeterminate, then we have
> to return indeterminate since the result could have been a deny or a permit.
> If there has been no deny or no indeterminate, then we can be sure that
> the result is permit if there was a permit.
-- 
Anne H. Anderson             Email: Anne.Anderson@Sun.COM
Sun Microsystems Laboratories
1 Network Drive,UBUR02-311     Tel: 781/442-0928
Burlington, MA 01803-0902 USA  Fax: 781/442-1692

Actually, the only-one-applicable does not have a problem in this sense.
It is ok for an algorithm to return an error, which only-one-applicable
is designed to do in this case. We cannot force the PDP to always make a
decision in case there are errors in policies. If someone forces that,
then he is essentially making assumptions about the indeterminate result
and treating it as equivalent to a valid decision.

The problem in this example is that the permit-overrides treats the
indeterminate as it was either deny or not applicable since it returns a
deny. The permit overrides algorithm should return an indeterminate if
it gets an indeterminate as input and there is no permit from any of the
other policies.

Erik


Anne Anderson - Sun Microsystems wrote:
> [I did not give the complete diff in the first edition of this comment]
>
> I've diff'd the first algorithm against the standard deny-overrides
> below for easier comparison.  I agree that the proposed variants are
> better, although I see the use of "onlyOneApplicable" as an equal
> problem in the example you give.  Presumably in that case, besides the
> PEP getting a response of "Indeterminate", the PAP should get an error
> saying "onlyOneApplicable" had failed - this is a failure of policy
> design.  With distributed, dynamic policies, it is not always possible
> to detect this situation ahead of time statically unfortunately.
>
> Anne
>
> Erik Rissanen wrote On 02/16/07 11:37,:
>> I promised to send a variant of the deny overrides
>> policy combining algorithm which does not have the "surprising"
>> behavior which Olav Bandmann discovered. Here it is:
>>
>> Decision soundDenyOverridesPolicyCombiningAlgorithm(Policy policy[])
>> {
>>     Boolean atLeastOnePermit = false;
>>     Boolean atLeastOneIndeterminate = false;
>>     for( i=0 ; i < lengthOf(policy) ; i++ )
>>     {
>>         Decision decision = evaluate(policy[i]);
>>         if (decision == Deny)
>>         {
>>             return Deny;
>>         }
>>         if (decision == Permit)
>>         {
>>             atLeastOnePermit = true;
>>             continue;
>>         }
>>         if (decision == NotApplicable)
>>         {
>>             continue;
>>         }
>>         if (decision == Indeterminate)
>>         {
>
> STD:          return Deny;
>
>>             atLeastOneIndeterminate = true;
>>             continue;
>>         }
>>     }
>
> STD: start omit
>
>>     if (atLeastOneIndeterminate)
>>     {
>>         return Indeterminate;
>>     }
>
> STD: end omit
>
>>     if (atLeastOnePermit)
>>     {
>>         return Permit;
>>     }
>>     return NotApplicable;
>> }
>>
>> The intuition here is that if we get a deny, then it doesn't matter what
>> anything
>> else evaluated to. In case there was at least on indeterminate, then
>> we have
>> to return indeterminate since the result could have been a deny or a
>> permit.
>> If there has been no deny or no indeterminate, then we can be sure that
>> the result is permit if there was a permit.