Re: [xacml] A & D Profile: Revise reduction algorithm

[Erik Rissanen <erik@axiomatics.com>]

Hi Steven,

Regardin the NP-completeness, the proof used the intermediate conditions 
to create policy structures which correspond to the 3-SAT problem. I 
don't think that works without the intermediate conditions.

The key to avoiding the NP-completeness is to make sure that the value 
of an administrative policy is independent of the recursive call path 
which was used to reach it. If that is so, the value of the admin policy 
can be stored, and if it is encountered through another recursive call, 
we don't need to evaluate it.

Since conditions on intermediate delegates made this path dependent, 
there is is way out of the exponential complexity.

So I think the reason we switched to the graph had more to do with the 
reduction of indeterminates, represented by the many different kinds of 
edges in the graph, rather than the NP-completeness problem itself.

Best regards,
Erik


On 2014-10-02 09:18, Steven Legg wrote:
> Hi Erik,
>
> On 18/09/2014 11:34 PM, Erik Rissanen wrote:
> > Hi,
> >
> > I haven't spent much time on this, but a few comments come to my 
> > mind. I might have said these earlier already.
> >
> > Separating out admin policies means that it is no longer possible to 
> > nest a self contained policy set in a larger context, where the 
> > nested policy could contain admin policies, which are independent of 
> > other parts of the policy hierarchy.
>
> Most recently I proposed forming the reduction graph from the sibling 
> administrative policies
> of the access policy being reduced and the sibling administrative 
> policies of each policy set
> enclosing the access policy being reduced to allow for such 
> self-contained nesting while
> still getting most of the benefits of separating out the admin policies
> (https://www.oasis-open.org/apps/org/workgroup/xacml/email/archives/201408/msg00020.html). 
>
> The scope of any administrative policy would be restricted to the 
> policy set where it
> appears, such as a self-contained policy subset. Administrative 
> policies that apply in
> the wider context, including any subsets, would appear in the 
> outermost policy set. A single
> outermost policy set could contain all the access policy and 
> administrative policy.
>
> > Such hierarchies may be useful in very large deployments, where 
> different sub trees are managed by different entities, and the trees 
> should not interfere with each other. If there instead is an "admin 
> policy bucket" where everybody puts their admin policies, then 
> interference is possible.
> > Early drafts of the delegation profile used recursive evaluations 
> > instead of the delegation graph. We thought that we had good reasons 
> > back then to instead use a graph, so it might not be a good idea to 
> > switch back to recursive evaluations. I don't remember the details 
> > but some of the issues I think we solved were the proper treatment of 
> > Indeterminate results and there might be performance benefits for the 
> > graph too, but I haven't analyzed it in detail. I know that the very 
> > early drafts were NP-complete, but that was because of the 
> > possibility to define conditions on intermediate delegates.
>
> I think it is still NP-complete without conditions on intermediate 
> delegates.
> Another problem is what to do during recursive evaluation when one 
> encounters the
> administrative policy being reduced. Ignoring it or treating it as 
> NotApplicable
> are not necessarily appropriate for all conceivable combining 
> algorithms. The
> reduction graph avoids the situation.
>
> Regards,
> Steven
>
> > In any case, I don't feel very strongly about this since I don't see 
> > a market demand for it. :-)
> >
> > Best regards,
> > Erik
> >
> >
> > On 2014-09-04 21:25, Hal Lockhart wrote:
> > > I basically agree with Steven's proposal #2 in:
> > >
> > > https://lists.oasis-open.org/archives/xacml/201211/msg00016.html
> > >
> > > In summary, Administrative Policies could enable Access Policies in 
> > > the same PolicySet or in any lower (further from the root) Policy 
> > > sets. The reduction graph is not used, instead the regular algorithm 
> > > is used, which recursively finds Authorizing Admin policies until it 
> > > either hist a trusted policy or runs out of policies to try.
> > >
> > > I am not exactly sure what we end up keeping from Section 4 of the 
> > > Profile and what we need to discard of modify.
> > >
> > > I also want to add a non-normative section describing to a Policy 
> > > Author (as distinct from a PDP implementer) what the effects of 
> > > various Admin policy choices are. For example, it is currently not 
> > > easy to understand what the semantics of Permit and Deny are in an 
> > > Administrative Policy.
> > >
> > > It also occurred to me that when evaluating a decision against a 
> > > large collection of admin and access policies, it might to compute 
> > > the applicability of the situation (but not the delegate) of every 
> > > Admin policy we encounter. Then when we actually try to build the 
> > > delegation chains we would not spend any time on admin policies 
> > > which can never be applicable. I am not completely sure 1) under 
> > > what circumstances this would pay off, 2) whether this should be 
> > > mentioned as a possible optimization or 3) whether it works so well 
> > > it should be describes as the normative algorithm.
> > >
> > > Thoughts?
> > >
> > > 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