Hi Erik, On 2/02/2015 6:57 PM, Erik Rissanen wrote: Hi Steven, Not sure if I understood you correctly, but the current working draft administrative policy evaluation is not path dependent. The only information which participates in the evaluation of an administrative request is the access situation, the issuer of the policy "asking for support" and the policy "providing support". No information of any other policy participates, so it's not path dependent. It was not my intention to give the impression that there were path dependencies in the way the reduction graph is formed. I don't believe there are any. MaxDelegationDepth creates path dependencies, of a sort, when it comes to searching for paths in the reduction graph that has already been formed. Sure, a naive recursive search of the graph has a worst case running time of n!, but that's just a sub-optimal implementation. The very least you can calculate all edges by going through all pairs (n^2) and then you can use some standard graph search algorithm to find your paths. It is many years ago from my computer science courses, so I don't recall the details, and won't bother to look into it now, but I would think that given the graph, you can find the path in n*log(n). I suppose you are thinking of Dijkstra's algorithm for finding the shortest path between two nodes in a graph. It has complexity E + N * log(N), where E is the number of edges. In a sparse graph the N * log(N) part dominates, but if the graph is fully connected then E is of order N * N. However, Dijkstra's algorithm doesn't solve the problem at hand because it doesn't account for the constraints on sub-path length imposed by MaxDelegationDepth. Back when I was implementing the path searching I didn't find a published algorithm that could deal with MaxDelegationDepth so it was a case of rolling my own. The profile is completely silent on the question of suitable algorithms, optimal or otherwise, for path searching in the reduction graph, which I found unhelpful. In the absence of MaxDelegationDepth, I can see how I can use Dijkstra's algorithm to find whether there is a PP-only path, or failing that, a PP and PI path, in only one run of the algorithm. Taking into account MaxDelegationDepth, I can see how to modify Dijkstra's algorithm to find a PP-only path that satisfies MaxDelegationDepth or a PP and PI path that satisfies MaxDelegationDepth, but they have to be done in separate runs (would the modification be obvious to all implementors?). I'm not at all certain there is a way to modify Dijkstra's algorithm to correctly find a satisfactory PP-only path or PP and PI path in only one run. I haven't looked closely because I came to regard searching for a path starting from the node of the access policy (like the profile says) as sub-optimal in the bigger picture. The problem with searching from the node of the access policy is that there seem to be no useful intermediate results that can be cached to speed up later searches in the same reduction graph. I started looking at working outwards from the nodes of the trusted policies instead and came up with propagating the effective MDD as a solution. It does have useful intermediate results that can be cached to speed up later checks in the same reduction graph. The breadth-first propagation of the effective MDD isn't Dijkstra's algorithm because it calculates different quantities and answers a different question, but it follows the same pattern, so I expect it would actually have the same complexity: E + N * log(N). I previously did a simple analysis for the worst case of a fully connected graph and came up with order N * N, which is the same as Dijkstra's algorithm in that case. I build the reduction graph incrementally and propagate the effective MDD as required as new bits are added to the graph. If instead I built the complete reduction graph in the first instance then I could adapt the breadth-first effective MDD propagation algorithm to find, for *every* node corresponding to an access policy, whether it has a PP-only or PP and PI path to a trusted node in just one run of the algorithm. Using a modified form of Dijkstra's algorithm would require one or two runs for *each* node corresponding to an access policy, hence that approach is sub-optimal. Regards, Steven Best regards, Erik On 2015-02-02 05:38, Steven Legg wrote: 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