Re: [xacml] Reactivating the Admin & Delegation discussion

[Erik Rissanen <erik@axiomatics.com>]

Hi Hal,

Regarding this kind of optimization, yes, I agree that any kind of 
optimization should be allowed as long as the result is the same as what 
is defined. Of course it is good for the TC to consider various kinds of 
optimizations to make sure that they are possible to implement.

For the optimization you mention specifically, that is one I already 
implemented in the Axiomatics product for the previous drafts of the 
delegation profile. However, I cannot comment on the nature of typical 
data and whether it pays off because apart from a couple of early 
research type customers, nobody ever wanted to use the delegation profile.

Best regards,
Erik


On 2015-01-28 04:00, 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.) This would not be so much to eliminate redundant computation, but simply to shrink the pool of candidate Admin policies to be considered.
>
> 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
>
> > -----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. 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,
> > 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.
> >
> > 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.
> >
> > 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