Security considerations for the access-permitted function

[Erik Rissanen <erik@axiomatics.com>]

All,

As agreed I am moving the access-permitted function from the delegation 
profile into the core spec.

When I did so I did some thinking about the concerns I have about the 
function.

As a reminder: this is the function defined in the delegation profile 
which returns true if an access request specified in its arguments is 
permitted.

The way the function invokes the PDP as a brand new request going back 
to the top level in the policies means that it is very hard to 
understand its behavior or put bounds on the execution.

Currently the specification of the function contains the following text:

--8<--
The PDP SHALL detect any loop which may occur if successive evaluations 
invoke this function. If such a loop is detected, the initial invocation 
of this function evaluates to Indeterminate with a 
“urn:oasis:names:tc:xacml:1.0:status:processing-error” status code.
--8<--

This text is a bit ambiguous. Does it mean

- any invocation of the access-permitted function at all

- any invocation of the same instance of the access-permitted function 
(with an instance I mean the specific <Apply> element where the function 
is invoked)

- any invocation of the same instance with the same request content

- any invocation which leads to a loop which does not terminate?

Note that it could be conceivable that a policy author wishes that the 
same instance would be invoked multiple times, for instance: Alice is 
permitted because Bob is permitted because Carol is permitted. I cannot 
think of any algorithm for telling apart such a legitimate loop from a 
loop which will not terminate.

A simple algorithm for prevention of infinite loops is the limit the 
depth of recursive invocations. However this still leaves the feature 
open for serious performance issues. For instance, consider the 
following policy:

<Policy CombAlg="permit-overrides">
<Rule><Apply FunctionId="access-permitted"/></Rule>
... Repeat rule N times ...
</Policy>

Let's say that the PDP allows only a depth of X invocations. In that 
case this policy will result in N^X invocations of the PDP.

Let's say that N=20, which is not an inconceivable number. And let's say 
that X is 5. This leads to 3.2 million invocations!

If we can trust the policy administrators to a) be benevolent, b) 
competent, then this is not an issue.

b) might not be true in some cases

a) is not true when delegated policies are used.

Alternatively we could define the loop termination criteria to be based 
on the total number of invocations, rather than the depth of the 
invocations. This is perhaps the best alternative. Should we define a 
particular number on the bound in that case? And in the first place, do 
we want to mandate any particular loop detection mechanism?

So I think we need to clarify the security consideration text of the 
function, or redefine the function so it does not have these issues.

To start a concrete discussion, I propose the following text in the 
function definition section (replaces the above quoted text):

--8<--
The PDP SHALL detect any loop which may occur if successive evaluations 
invoke this function by counting the number of total invocations of any 
instance of this function. If the total number of invocations exceeds 
the bound for such invocations, the initial invocation of this function 
evaluates to Indeterminate with a 
“urn:oasis:names:tc:xacml:1.0:status:processing-error” status code.
--8<--

I propose the following text to be placed in the security considerations 
section and referenced from the function definition section.

--8<--
The urn:...:access-permitted function may lead to hard to predict 
behavior in the PDP. It is possible that the function is invoked during 
the recursive invocations of the PDP such that loops are formed. Such 
loops may in some cases lead to large numbers of requests to be 
generated before the PDP can detect the loop and abort evaluation. Such 
loops could cause a denial of service at the PDP, either because of a 
malicious policy or because of a mistake in a policy.
--8<--

Best regards,
Erik