OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

 


Help: OASIS Mailing Lists Help | MarkMail Help

xacml message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]


Subject: Re: [xacml] Reactivating the Admin & Delegation discussion



Hi Hal and Erik,

On 28/01/2015 2:00 PM, Hal Lockhart wrote:
No the issue was my confusion. I thought the mere fact that when looking for an Admin policy to authorize some untrusted policy you have to check every Admin policy was sufficient to produce NP-completeness. In other words I confused "every possible policy" with "every possible delegation path." The history you mention corresponds to my memory, so I am relieved that my recollection to the effect that we had eliminated the problem is correct.

I don't completely see why the initial graph algorithm is required to properly resolve Indeterminate results, but I need to study it a bit more.

WRT to optimizations, I believe that it may be a big win to check every Admin policy against the situation initially. (Of course only once we have seen an Applicable Untrusted Policy and know Reduction will be required.)

On the understanding that this is a special form of policy evaluation that
treats the attributes in the delegate and delegation-info categories as
wildcards. The administrative requests generated during reduction will
have the same values for the attributes that originate from the access
request, but will have different values for the attributes in the delegate
and delegation-info categories. We would want to find all the administrative
policies that are satisfied by the situation for at least one possible
delegate and delegation-info combination without having to enumerate every
possible delegate and delegation-info combination. I can think of three
approaches for doing this, one of which is partial evaluation.

Since there are only two forms for the delegation-info category, depending
on whether we are reducing "Permit" or "Deny", a potential optimization would
be to do two checks, one for "Permit" reduction and one for "Deny" reduction.
Then only the attributes in the delegate category are wildcards.

This would not be so much to eliminate redundant computation, but simply to shrink the pool of candidate Admin policies to be considered.

Another useful optimization comes from the observation that two sibling
untrusted policies that have identical issuers will generate identical
administrative requests and therefore be authorized by exactly the same
administrative policies. If the reduction graph already has a node for an
identical issuer then the outgoing arcs of that node can be copied instead
of evaluating the administrative request.

I realize that the effectiveness of this is dependent on the policy structure. It is somewhat presumptuous to predict the policy structure when no one other than Frank Siebenlist wants to use this Profile, but let's look at a couple of usecases.

First, consider the bread and butter case of a large organization consisting of multiple sub groups each with their own servers and their own administrators of those servers. They would create Admin policies which would allow each admin to create policies for access to their own servers and no others. In this case I would expect that for each decision only a small subset of the Admin policies would be applicable, based on the location of the resource.

Now consider a dynamic policy scheme where Admin and/or Access policies are created on the fly. It is hard to predict how such schemes in would be set up in practice, but I have a suspicion that policies would be narrowly tailored to provide very specific access. In this case again I speculate that only a small percentage of Admin policies would be applicable to any particular decision.

Of course the spec does not have to describe optimization algorithms, only say they are allowed if they give the same result, but I mention it because like the graph search, it moves us away from the idea of using the existing (Access) policy evaluation logic without modification.

I will study the Indeterminate issue next. Otherwise I agree with your other comments.

Hal

More comments below.


-----Original Message-----
From: Erik Rissanen [mailto:erik@axiomatics.com]
Sent: Friday, January 23, 2015 10:54 AM
To: xacml@lists.oasis-open.org
Subject: Re: [xacml] Reactivating the Admin & Delegation discussion

Hi Hal,

I'm not sure how you define your "intuitive sense", but I don't see
that these criteria in this email would necessary lead to NP-
completeness.

The algorithm becomes NP-complete when the decision of whether a policy
A supports a policy B depends not only on these two policies, but also
on which other policies may be in the delegation chain.

In our early drafts we had a mechanism by which a policy could restrict
which kind of further delegation would be authorized. So, a policy A
could say that it supports policy B, but could also put restrictions on
what kind of policies policy B in turn could support. This leads to a
path dependency, so that the whole path from the root of trust to the
access policy has to be verified before the support is known to hold at
each step through the whole path. Because of this, we potentially have
to look at every possible ordered chain among the admin policies when
looking for a valid delegation. The number of ordered chains among the
admin policies grow exponentially, something like n!.

To fix this issue, we removed the possibility of these constraints on
further delegation. We said instead that a policy A supports policy B
if the issuer of policy B matches the constraints in policy A (using an
administrative request) on issuers. Further we included the access
situation in the administrative request to ensure that the access
request being granted is within the boundaries of the delegation from A
to B.

With this new model the support relation is not path dependent and we
can establish for each ordered policy pair whether one policy supports
another.

The complexity of the method of searching the reduction graph for paths
from the node for the access policy being reduced to the node of a trusted
policy should also be considered. A search that starts at the node for
the access policy and recursively tries each possible outgoing arc until it
finds the node of a trusted policy will also have worst case performance of
order N! . The cost of taking a step in the reduction graph is much smaller
than the cost of evaluating a policy, but even that small cost could become
significant for large enough N.

We can't cache the result of searching from any intermediate node for use
in the same or a later graph search because that result is dependent on the
path taken to get to the intermediate node in the first place. The nodes on
that initial path must be excluded from consideration in continuing the
search from the intermediate node, to avoid following cycles, and the
initial path will be different each time the intermediate node is visited.

A better algorithm is to propagate the effective MaxDelegationDepth (MDD)
outwards from the nodes for the trusted policies towards the nodes for the
access policies. The effective MDD for a trusted node is the value of its
policy's MaxDelegationDepth attribute, taking absent to equal infinity.
The effective MDD is one less for each node adjacent to a trusted node
(infinity minus one is still infinity), but capped by the adjacent node's
policy's own MaxDelegationDepth attribute value. Each step taken in the
reduction graph reduces the effective MDD by one. In propagating the
effective MDD to an adjacent node, if the adjacent node already has an
equal or higher effective MDD then propagation along that path stops. This
neatly takes care of cycles during propagation since any node that has
already been visited in the same attempt necessarily has a higher effective
MDD. If the adjacent node has a lower effective MDD then that node's
effective MDD is set to the higher value (possibly capped) and propagation
continues. If at any time the node for the access policy gets given an
effective MDD that is greater than zero then there must be a path from that
node to the node of a trusted policy that satisfies the MaxDelegationDepth
attribute value of the policy of each node on the path. If the propagation
quiesces without that happening then the access policy isn't authorized.

Breadth-first propagation of the effective MDD has worst case performance
of order N * N. Depth-first propagation has worst case performance of
order N * N * N, so the choice is obvious.

It is also possible to determine, at the same time, whether there is a PP-only
(DP-only) or a PP and PI (DP and DI) path from a trusted policy node to the
access policy node.

This is quadratic in complexity, which is not really great
either. (Perhaps using some clever indexing scheme it would be possible
to find the matching pairs for a given policy faster than trying each
other policy, thus reducing the complexity to less than quadratic,

This is what the ViewDS PDP does (i.e., it has a clever indexing scheme).
I build the reduction graph incrementally starting from the access policies.
An index lookup using attributes from the administrative request gives me
the identifiers for administrative policies that are worth checking for
applicability to that administrative request (there may be some false
positives to weed out). Each applicable administrative policy goes into
the graph and, if untrusted, spawns another administrative request and
index lookup. When I hit an applicable trusted policy I propagate the
effective MDD and see if the effective MDD for the access policy's node
is greater than zero. If not, I keep going until I run out of administrative
policies worth checking. Either way, I keep the reduction graph built so
far because it is still a valid starting point for evaluating a sibling
access policy of the first access policy. I would normally expect to only
end up looking at a subset of the administrative policies; enough of the
ones that matter and few of the ones that don't.

though I doubt that it can be done, given the richness of XACML
evaluation of administrative requests. In any case, in the worst case
every policy could possibly support every other policy, so the number
of pairs which exist would be quadratic.)

Now, given the support relations between the policies, determining
whether an access request is valid, then becomes the graph search which
is described in the draft profile.

Regarding my previous email, I did not mean to say that any other
algorithm is going to be NP-complete. What I mean was that defining the
algorithm using a recursive search using administrative requests could
lead to such an algorithm if you make it path dependent. However, if
you know that it's not path dependent, then any policy which has
already been searched using recursion can simply be skipped in further
searching because it would be known that the result is the same.

Yes. The problem I found with evaluating administrative requests just like
access requests is that the result is path dependent. We have to ignore any
administrative policies that are in the chain of authorizations from the
untrusted access policy to the current untrusted administrative policy.
That chain can vary, and so the result can vary.


Another concern I had was that we had the different types of edges to
properly account for Indeterminate results. The concern here was that a
broken or malicious policy could cause Indeterminates on requests on
access situations which were intended to be in the scope of the
delegated authority.

To me it appears that what you would want to do is to keep the graph
algorithm as it is, with the types of edges and the concept of support
and administrative requests being the same. What you would do instead
is:

- Change which policies participate in the graph search. You would not
take only siblings, like today, but instead collect them from various
places to be defined.

- Replace the prefix scheme with something else for the purpose of
matching administrative requests. For instance, you could define a new
schema elements for an administrative requests and policies, and only
those would be used in combination. The administrative request would
contain the issuer and the access situation like today, but without
prefixing. The admin policy would use normal category identifiers in
its expressions.

Agreed, though a new schema element for administrative requests isn't
needed. Even if there is a desire for PEPs to issue administrative
requests (for testing, say), including the delegation-info category
would indicate that a request is meant to be processed as an
administrative request.

Regards,
Steven


Best regards,
Erik


On 2015-01-22 20:36, Hal Lockhart wrote:
To review: WD 31 & 32 of the A&D Profile resolved issues 95, 96, 98,
100 & 101.

This version (CSD04) is under public review until Feb 11. The
intention of the TC is to move this Profile to CS and no further. This
will allow people who have already implemented it to claim conformance,
but make it easier for people who don't see the need for it to skip it
and also to indicate that the TC believes the Profile could still be
improved.

I now turn to the remaining issues, including 94, 97 & 99. Speaking
as an individual, I generally agree with Steven on the following
points.

1. Policies should either be Access Policies or Admin Policies, but
never both.
2. The distinction between them should be made at the schema level.
(The prefixing scheme is broken.) This is best done by subclassing
PolicySetType and PolicyType.
3. Admin policies should be able to authorize polices not only in the
same PolicySet, but also in any enclosed Policy or PolicySet. In other
words, Admin policies may appear in the same PolicySet or any PolicySet
closer to the root than the Policies they authorized.

I also believe as a matter of logic and common sense.

4. No Admin Policy or PolicySet should be able to authorize itself.
5. No Admin Policy or PolicySet should appear more than once in a
valid authorization tree. In other words, there be no cycles in the
delegation chain.

Now the main concern I have is as follows. In a previous message Erik
seemed to suggest that any reduction algorithm which matches our
intuitive sense of how the A&D scheme should work will necessarily be
NP-complete. That is to say the work factor will increase exponentially
as a function of the number of Admin Policies.

As I understand it, this is simply a consequence of the fact that
since the delegation chain depends the situation of the original
request, the and the contents of each policy we are trying to
authorize, in principle, we need to check every Admin Policy at every
step in the reduction process. #4 above helps a little, but does not
change the shape of the curve.

Erik can you confirm that this is true?

If this is the case, I am inclined to do no more work on the Profile.
What do others think?

Hal

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


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




[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]