Issues #71 and #76 (multi-categories)

[Erik Rissanen <erik@axiomatics.com>]

All,

During the call today Hal expressed an interest in pursuing issues #71 
and #76.

To keep up the momentum I am posting my thoughts on these issues.

To remind everybody, these issues are the issues about extending XACML 
to support multiple distinct categories of attributes, for example:

<Request>
  <Attributes Category="urn:...:intermediate-subject">
    ...
  </Attributes>
  <Attributes Category="urn:...:intermediate-subject">
    ...
  </Attributes>
  ...
</Request>

Note that both of the Attributes elements contain the same category. In 
XACML 2.0 a similar construct, that is, multiple <Subject> elements, 
would have been considered as a single <Subject> element with all the 
content of both of the elements. In XACML 3.0 this is not allowed, 
unless it is a multiple request, in which case the PDP will respond to 
whether these two intermediate subjects would get access individually.

It is proposed that multiple Attributes elements like this should be 
allowed and the expressiveness of XACML to be extended so that policies 
can be stated with expressions on "all" and "at least one" of them.

I am opposed to this since it introduces an enormous amount of 
complexity if done fully, but there are "half-way" solutions which I 
might find acceptable if others find this to be a major desirable feature.

I am using the new term "multi-categories" to make the presentation 
below less verbose.

First of all, lets note that if we allow multi-categories in requests, 
all policies must be prepared to handle them in one way or another.

The primary impact will be on the AttributeDesignator and 
AttributeSelector since they are the methods we have to refer to the 
request. I will consider only the AttributeDesignator. I believe that 
the AttributeSelector is completely analogous, but I haven't really 
given it any thought yet.

If the request may contain multi-categories, the AttributeDesignator 
will no longer return a bag of attributes, but instead a bag of bags of 
attributes. To keep things less confusing, I will call this new type of 
attribute designator "QAttributeDesignator". I am using this name as in 
"Quantifier" since the output of it will be used in quantified expressions.

The "use cases" I am considering here are:

1. How to write "old style" XACML policies.

2. How to do "All/At least one" in the target.

3. How to do "All/At least one" in the condition.

Begin with 1:

We can introduce a new function called "urn:...:bag-one-and-only" which 
returns a single bag of attributes from a bag of bags of attributes. If 
the bag contains multiple bags of attributes, it returns Indeterminate. 
So we can do like this:

<Apply FunctionId="urn:...:bag-one-and-only">
  <QAttributeDesignator .../>
</Apply>

This is essentially the same thing as the old attribute designator, so 
we might as well redefine the behaviour of the plain AttributeDesignator 
to be like this. This means that all "old" policies work as expected if 
they receive an "old" style request. In case of a request with 
multi-categories, an old style policy will (likely) become Indeterminate.

So far so good. The old stuff has not become any more complex, at least 
not for the policy author.

Now consider 2:

One way to do it is to introduce a quantified <Match>, which I will call 
<QMatch>. (Alternatively we could overload the regular match.) It could 
look like this:

<Target>
  <AnyOf>
    <AllOf>
       <QMatch Quantifier="All" FunctionId="...">
         <AttributeValue>...</AttributeValue>
         <QAttributeDesignator .../>
    </AllOf>
    ...
  </AnyOf>
  ...
</Target>

The "All" can instead be "AtLeastOne".

The meaning is that the function has to match an attribute in 
All/AtLeastOne of the bags from the QAttributeDesignator.

This is not too bad either. It does introduce additional concerns in the 
processing model, which complicates learning of XACML to new users, but 
perhaps that is manageable?

Finally, consider 3:

Now it starts to get hairy...

What we need is higher order functions which work on bags of bags of 
attributes. And since the condition is written by the policy author, the 
function which is applied by the higher order function is written by the 
policy author. In other words we need some form of lambda expressions 
which can be passed to quantified higher order functions.

Something like this:

<Condition>
  <Apply FunctionId="urn:...:quantified-condition">
    <AttributeValue>AtLeastOne</AttributeValue>
    <Lambda>
      <Apply FunctionId="urn:...:integer-equal">
        <AttributeValue>5</AttributeValue>
        <Apply FunctionId="urn:...:integer-one-and-only">
          <LambdaArg/>
        </Apply>
      </Apply>
    </Lambda>
    <QAttributeDesignator AttributeId="foo" Category="...:intermediate" 
.../>
  </Apply>
</Condition>

This expression returns true if at least one of the intermediates has 
the "foo" attribute with a value of 5. (Yes, this particular example 
could be done more easily with a quantified target, but I wanted to keep 
the example simple.)

The function quantified-lambda takes three arguments: a quantifier 
(All/AtLeastOne), a lambda expression and a bag of bags. What it does is 
that it takes the lambda expression and evaluates it for each bag in the 
bag of bags of attributes. The <LambdaArg/> element stands for the bag 
which the expression is applied to. In this case the bag is converted 
into a single integer, which is compared to the value "5". If at least 
one of the lambdas returns true, then the whole quantified-condition 
returns true.

There are variants of how it could be done. Instead of having the 
quantifier as a parameter, we could have two functions "all-condition" 
and "at-least-one-condition".

Alternatively we could have a "lambda-map" which maps the bag of bags 
into a bag which contains the outputs of the lambda for each of the bags 
of bags and then a regular bag function could be used to test whether 
they are all/at least one "true". I would actually prefer this since it 
is more general, for instance we could count the number of "true"s in 
the bag.

If we want to do even more, we could have lambdas which take two or more 
bags as inputs to do expressions such as "at least one of the resource 
owner subjects has to have approved all the intermediate subjects". I 
haven't thought about how to do something like that. In any case it 
would require some analysis to understand which forms of expressions we 
need to be general in any way or another.

Anyway, at this stage it is pretty complex, hard to comprehend and teach.

And analysis of policies is probably going to be an important concern. 
For audit for instance. One worry I have there is that I am not sure 
what drives the complexity of analysis of policies with respect to 
multi-categories. Would a policy syntax which allows only target 
matching of multi-categories be any simpler to analyse than the full 
condition variant? It could be the case that there is something 
inherently complex in the multi-categories request model itself.

Any opinions? Do we need/want this in XACML? At which level in that 
case? Target only or full condition?

Best regards,
Erik