Re: [xacml] Optimizing <Target> evaluation

[Erik Rissanen <erik@axiomatics.com>]

Just bumping up this to the next call again.

/Erik

Erik Rissanen wrote:
> All,
>
> This issue was deferred to the next call, so I am bumping up this 
> message so it's not forgotten.
>
> I would also like to explain more carefully why it is more consistent 
> to give priority of a non-matching target section before an 
> indeterminate in the target evaluation.
>
> An Indeterminate result is used when the value of an evaluation cannot 
> be determined. Consider the following example:
>
> <Target>
>  <AnyOf> ... this evaluated to "Match" ... </AnyOf>
>  <AnyOf> ... there is an error retrieving an attribute here -> 
> Indeterminate ... </AnyOf>
> </Target>
>
> In this case we don't know the value of the second <AnyOf>. If we 
> would have been able to resolve the attribute, the value could be 
> either Match or NoMatch. If we consider these two possibilities for 
> the whole target, we see that in the first case the whole target is a 
> Match and in the other case it's a NoMatch. This means that because of 
> the error in the section of the target, the value of the whole target 
> is uncertain, and we should therefore treat that whole target as 
> Indeterminate as well.
>
> Now, consider the following case:
>
> <Target>
>  <AnyOf> ... this evaluated to "NoMatch" ... </AnyOf>
>  <AnyOf> ... there is an error retrieving an attribute here -> 
> Indeterminate ... </AnyOf>
> </Target>
>
> Again, the section which failed could be either NoMatch or Match if it 
> would have been non-failing. But in this case the value of the whole 
> target would be NoMatch in either case, so it would be safe to return 
> a NoMatch for the whole target. However, currently the specification 
> says that the whole target should be Indeterminate. This is not 
> consistent with the meaning of Indeterminate as "the value of the 
> policy is uncertain". And it is also suboptimal from a performance 
> point of view.
>
> Regards,
> Erik
>
> BTW, it was by reasoning like this Olav Bandman at SICS discovered 
> similar inconsistencies in some of the combining algorithms, and he 
> was able to "exploit" them to make the PDP go from Permit to Deny, or 
> vice versa, by imagining that an attacker could force a failure in 
> attribute resolution. We discussed this some time ago, but there was 
> some resistance to fix this. I still think it would be better to 
> update the combining algorithms in 3.0 and "deprecate" the old 
> versions. I can imagine there are similar performance issues in the 
> combining algorithms as well, but I haven't looked into it yet.
>
>
> Erik Rissanen wrote:
>> All,
>>
>> I have been considering how to optimize evaluation of the <Target>, 
>> and I think the standard could be improved for 3.0.
>>
>> There are several levels in the target, and their behaviour has been 
>> inherited from the 2.0 specification. The levels of combining results 
>> in the target matching are <Target>, <AnyOf> and <AllOf>. The issue I 
>> am considering is the priority of an Indeterminate result in the 
>> combination at these levels.
>>
>> At the <Target> level if at least one of the children is 
>> Indeterminate, then the whole target is Indeterminate, regardless of 
>> the other values.
>>
>> At the <AnyOf> level if at least one of the children matches, then 
>> the whole <AnyOf> is a match, regardless there are any Indeterminate 
>> values in the other children.
>>
>> At the <AllOf> level if at least one of the children is "false", then 
>> the whole <AllOf> is a no match, regardless there are any 
>> Indeterminate values in the other children.
>>
>> At first, one can note that the treatment of Indeterminate is 
>> somewhat inconsistent. At the <Target> level Indeterminate has 
>> priority, while at the other levels it does not.
>>
>> I would think that it makes more sense that Indeterminate does not 
>> have priority since if we know that a section of the target does not 
>> match, then we know for sure that the policy does not apply, so it 
>> would be safe to ignore the indeterminate from the other parts of the 
>> target. Conversely, if all parts of the target match, except that 
>> there is also an indeterminate, then it makes sense that the 
>> indeterminiate result is propagated upwards since we cannot know 
>> whether the policy applies or not.
>>
>> There is also a performance optimization argument in favour of 
>> changing the <Target> behaviour. The current behaviour means that if 
>> the PDP finds a section in the target which does not match, it still 
>> has to evaluate the remaining sections to determine that there is no 
>> Indeterminate result. In most cases we would expect that 
>> Indeterminates are less common than non-matching targets, so we can 
>> expect better performance if the PDP would give priority to a 
>> non-matching target.
>>
>> I propose therefore that to improve consistency and performance, we 
>> change the <Target> matching specification in 3.0 so that a 
>> non-matching child in a <Target> has priority over an Indeterminate 
>> child.
>>
>> Best regards,
>> Erik
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe from this mail list, you must leave the OASIS TC that
>> generates this mail.  Follow this link to all your TCs in OASIS at:
>> https://www.oasis-open.org/apps/org/workgroup/portal/my_workgroups.php
>
>
> ---------------------------------------------------------------------
> To unsubscribe from this mail list, you must leave the OASIS TC that
> generates this mail.  Follow this link to all your TCs in OASIS at:
> https://www.oasis-open.org/apps/org/workgroup/portal/my_workgroups.php