Re: [xacml] Combining algorithms

[Erik Rissanen <erik@axiomatics.com>]

Hi Rich and All,

I don't feel very strongly on this issue, so either of these two 
alternatives is good for me:

Alternative A: Minimal change (my preference)

- Remove the bias in the existing policy combining algorithms
- Do not change algorithm identifiers

Alternative B: extended algorithms (I'm fine with this if others feel 
strongly for it)

- Say that the XACML 2.0 algorithms are deprecated (but available for 
compatibility reasons)
- Define new identifiers for 3.0
- Use the extended definitions which I posted earlier

Orthogonally, we may choose to define biased variants. My preference is 
that we do not define them, but I am not strongly opposed to it. If we 
do define them, I think the algorithms should be mandatory to promote 
interoperability. They are relatively simple to implement so they can be 
mandatory.

In summary: A is a small change, a bit easier to define and to 
understand for users, but not as elegant logically as B.

What does the rest of the TC think? Rich is in favor of the extended 
algorithms, so unless anybody else has an opinion, I'm ok to go with B.

Bert regards,
Erik


Rich.Levinson wrote:
> Hi Erik,
>
> I agree w your comment. If we were to have only non-biased extended 
> algorithms, Indeterminates could not be prevented from escaping. I 
> think the intent was clear even though the method I used was 
> incorrect.  I expect this was why I was suggesting having the bias as 
> a "switch" that could be turned on and off at top level, which I no 
> longer think is a good idea (at least not in an arbitrary manner), so 
> I also agree that if we want to be able to capture non-definitive 
> results (NotApplicable, Indeterminate) and turn them into definitive 
> results (Permit or Deny), then we need some kind of biased option.
>
> One note on your comparison of complexity, I don't think it is "apples 
> to apples" to compare the extended-combining to the policy-combining. 
> We really need to compare extended-combining to the rule-combining, 
> which is the more complex of the two.
>
> I agree that algorithmically, the extended algorithms "start to look" 
> kind of messy, but if one thinks of them from a "logical" perspective 
> it  might be easier to grasp.
>
> Possibly a fair analogy would be to a box of holiday lights (or 
> traffic lights), where there are collections of red and green lights 
> in each box. For Indeterminate we could consider the light to be 
> "burned out" and for NotApplicable we could consider the light to be 
> "not plugged in".  Red would be Deny and green Permit.
>
> Deny overrides would be equivalent to opening the box (which would 
> turn on the current) and:
>
>     * If any red light were lit, then you would be denied access.
>     * If no red lights were lit and only a green light was lit you'd
>       be granted access (unless ...).
>     * But in the 2nd case, if there was a red light that was burned
>       out and need to be replaced, then you would get indeterminate-d.
>       (which means there is a potential-deny, because if this light
>       was replaced with a good one it would either be not plugged in
>       or it would light up as red and you would be denied.)
>     * Also in the 2nd case, if there was a green light that was burned
>       out and needed to be replaced, then you would still be granted
>       access, because you could not have been denied access by a green
>       light whether it was lit, burned out, or not plugged in.
>     * Another case is if no light is lit and only a green light was
>       plugged in but it was burned out. In this case you would get an
>       indeterminate-p.
>
> The problem comes when you have two boxes like this side by side (for 
> example: Department A and Department B). With the base algorithms you 
> don't know whether an indeterminate from one of the boxes is a d or p 
> type, and you have to assume it is dp.
>
> When a customer realizes this simple fact, they are going to start to 
> ask, why, if they get a green light from one box and an indeterminate 
> from the 2nd box, and they know that the second box only has potential 
> green lights in it, that they cannot make the same conclusion as they 
> do within the box that if they have green light and no possible red 
> lights, why should they be denied access?
>
> I think if we agree that our combining algorithms are really 
> representing this situation with the boxes, then whatever small amount 
> of logical complexity for the programmer is overridden many times over 
> by the simplicity of conceptualization gained by the administrator.
>
> Now, conceptually, we can add "bias" to any box, by simply saying and 
> indeterminate-d from a deny-overrides box is a Deny, and an 
> indeterminate-p is a Permit. So, a biased deny-overrides is 
> effectively a "Permit unless explicitly or potentially Denied" box.
>
> Similary, a biased permit-overrides is equivalent to a "Deny unless 
> explicitly or potentially Permitted" box.
>
> I think with a contextual combining algorithm framework like this then 
> existing system administrators will find it much easier to adapt to 
> the xacml technology because it can be readily represented in terms 
> that they can clearly understand, and additional complexity can be 
> introduced to a well-understood foundation.
>
> Therefore, my preference is to have 4 combining algorithms:
>
>     * extended deny-overrides
>     * extended permit-overrides
>     * extended biased deny-overrides (permit unless explicitly denied)
>     * extended biased permit-overrides (deny unless explicitly permitted)
>
> One mode of operation might be to use the extended non-biased for all 
> things except if the administrators want definitive answers coming out 
> of the pdp, they can cap the whole thing with a single biased algorithm.
>
> Or, more likely, they would cap certain regions with biased-deny (for 
> example for internal protection of resources) or with biased-permit 
> (for example for public access to broad web-site except selected 
> possibly subscription-required areas).
>
>     Thanks,
>     Rich
>
>
> Erik Rissanen wrote:
>> Hi Rich,
>>
>> Good, I think we are making real progress on this issue.
>>
>> But I think you are mistaken about your second bullet point below. 
>> With an unbiased permit overrides policy combining algorithm, a deny 
>> would not override an indeterminate. So if you want a top level 
>> combining algorithm which would remove all indeterminates, then you 
>> need a biased combining algorithm. So we must choose between:
>>
>> - Rely on PEP bias only
>>
>> or
>>
>> - we define a set of biased combining algorithms as well.
>>
>> Without biased algorithms it would not be possible to prevent 
>> Indeterminates reaching the PEP.
>>
>> Regarding the algorithms for extended indeterminate, I do agree with 
>> Rich that they are more "logically consistent" and lead to somewhat 
>> more intuitive behavior, but they are more complex in their 
>> definition. For instance, the regular (unbiased) deny overrides 
>> policy combining algorithm has the following textual description:
>>
>> 1. If any policy evaluates to "Deny", the result is "Deny".
>> 2. Otherwise, if any policy evaluates to "Indeterminate", the result 
>> is "Indeterminate".
>> 3. Otherwise, if any policy evaluates to "Permit", the result is 
>> "Permit".
>> 4. Otherwise, the result is "NotApplicable".
>>
>> while the extended algorithm has this description:
>>
>> 1. If any decision is "Deny", the result is "Deny".
>> 2. Otherwise, if any decision is "Indeterminate{DP}", the result is 
>> "Indeterminate{DP}".
>> 3. Otherwise, if any decision is "Indeterminate{D}" and another 
>> decision is “Indeterminate{P} or Permit, the result is 
>> "Indeterminate{DP}".
>> 4. Otherwise, if any decision is "Indeterminate{D}", the result is 
>> "Indeterminate{D}".
>> 5. Otherwise, if any decision is "Permit", the result is "Permit".
>> 6. Otherwise, if any decision is "Indeterminate{P}", the result is 
>> "Indeterminate{P}".
>> 7. Otherwise, the result is "NotApplicable".
>>
>> The latter is a longer and more complex description, and I am much 
>> more confident that the former is correct than the latter.
>>
>> But I could live with either alternative. Does anyone else have an 
>> opinion?
>>
>> However, I do not want the extended algorithm to be an optional 
>> choice. I think we should choose either alternative, and that should 
>> be mandatory, and the only alternative. Having two different 
>> permit-override algorithms which are almost the same except for their 
>> treatment of errors would be confusing for users and represent 
>> implementation overhead.
>>
>> If we go with the extended variant, we should define new identifiers 
>> for them and leave the old ones only for backwards compatibility use.
>>
>> Best regards,
>> Erik
>>
>> Rich.Levinson wrote:
>>> Hi Erik,
>>>
>>> Nice job putting together the combining algorithm sections. I agree 
>>> with most everything you supplied although I have not yet looked at 
>>> all the explicit details of each algorithm, but for the sake of 
>>> discussion will assume that they are correct and just focus on the 
>>> details of the extended algorithms.
>>>
>>> First, the things I agree on are:
>>>
>>>     * Agree that we don't need to define biased algorithms. Might want
>>>       to comment on that and indicate that recommendation is to build
>>>       any bias directly into the policies, if needed.
>>>     * Might also want to mention that PEP bias is possible, but that
>>>       it can be removed by defining appropriate policies, especially
>>>       at top level. For example, if you want a Deny for all cases of
>>>       errors and indeterminate, a top level PolicySet w
>>>       permit-overrides can contain one policyset for all other
>>>       policies which collectively can return Permit, Deny,
>>>       Indeterminate, NotApplicable, plus a second policyset that has
>>>       an automatic Deny Rule if the first PolicySet did not return a
>>>       Permit.
>>>     * Agree on change deny-overrides policy combining to unbiased as
>>>       you have included.
>>>     * Agree on change permit-overrides policy combining to unbiased,
>>>       as well, also, it is symmetric w deny-overrides.
>>>
>>> On the extended algorithms, I think we have a disagreement as to the 
>>> potential value, and therefore I will try to point out the value 
>>> that I see there as the basis of why I think they should be included.
>>>
>>> I'd like to initially point out that what we are dealing with here 
>>> is a pre-existing condition in the current set of combining 
>>> algorithms that neither Erik nor I were a party to creating in the 
>>> first place. Erik's proposal is to "fix" some aspects of the 
>>> existing algorithms, and I agree that those fixes are improvements 
>>> to the current state. My proposal has been to revisit whether, in 
>>> fact, that separate policy and rule combining algorithms actually 
>>> add value or subtract value, when compared to a single combining 
>>> algorithm that applies to both policy(set)s and rules.
>>>
>>> First, I agree that the extended algorithms Erik has written appear 
>>> to be functionally equivalent to what I was recommending in the 
>>> earlier discussion on this topic:
>>> http://lists.oasis-open.org/archives/xacml/200810/msg00053.html
>>> (Note: I recommend changing the Indeterminate(DP) defn to be: "an 
>>> Indeterminate from a policy which could have evaluated to a Deny or 
>>> Permit." i.e. remove the "or rule" because a rule can either be a 
>>> "D" or a "P" but not both. This has no algorithmic impact but might 
>>> be conceptually useful when examining the algorithms, i.e. to know 
>>> DP applies to policies only. (In fact this brings out a key concept, 
>>> namely that policies, while inherently can be DP, depending on the 
>>> contained rules and their evaluations, can effectively be 
>>> constrained to only "D" or "P", which carries the character of the 
>>> collection of applicable rules that it contains.)
>>>
>>> In particular, the 3 flavors of Indeterminate preserve the results 
>>> as to whether there was a possible override or not, which is lost in 
>>> the current "base" permit/deny-overrides algorithms that simply 
>>> return Indeterminate in the case where there is a potentialDeny or 
>>> potentialPermit flagged and do not distinguish the cases where those 
>>> potentials are not present.
>>>
>>> In other words, it is obvious by inspection of the base 
>>> permit/deny-overrides algorithms, that Indeterminate in both 
>>> algorithms can be returned in 2 distinct cases, which causes you to 
>>> lose track of whether there was a potential deny in the 
>>> deny-overrides case or a potential permit in the permit-overrides case.
>>>
>>> In fact, one could take the point of view that we are effectively 
>>> introducing the complexity of having two classes of combining 
>>> algorithm (policy and rule) in order to remove information that we 
>>> are presupposing will be of no value to any customer. i.e. the 
>>> reason that the policy-combining algorithms are simpler than the 
>>> rule-combining is that potentially useful decision making 
>>> information is removed by the rule combining algorithms after using 
>>> only a portion of the information that they have gone to the trouble 
>>> to collect.
>>>
>>> The net result is that there is a non-uniformity of containers for 
>>> Rules that adds conceptual complexity to the strategy of building 
>>> PolicySets with no obvious added value, but with subtracted 
>>> decision-making information.
>>>
>>> For example, consider a deny-overrides Policy with 2 Permit Rules, 
>>> RP1 and RP2, and 1 Deny Rule, RD3. If the Deny Rule, RD3, is 
>>> NotApplicable and one Permit Rule, RP2 is Indeterminate then if the 
>>> remaining Rule, RP1, evaluates to Permit, then the Policy evaluates 
>>> to Permit.
>>>
>>> Now split the Rules into 2 Policies, one with a Permit, RP2, and 
>>> Deny, RD3, and the other with one Permit RP1, and put the Policies 
>>> in a deny-overrides PolicySet. If the Deny Rule, RD3, again is 
>>> NotApplicable and the companion Permit Rule, RP2, is again 
>>> Indeterminate then that Policy will return Indeterminate. If the 
>>> remaining Rule, RP1, in the other Policy, again evaluates to Permit, 
>>> then that Policy will evaluate to Permit. Now the PolicySet, which 
>>> contains the two Policies which together contain the same three 
>>> rules as the case above, and all the Rules evaluate the same as 
>>> above, then now this combined PolicySet evaluates to Indeterminate, 
>>> even though there was a valid Permit and no applicable Deny.
>>>
>>> Interesting, if you switch RP2 to be NotApplicable, and RD3 to be 
>>> Indeterminate, then both cases evaluate to Indeterminate.
>>>
>>> The point is that by introducing a distinction between rule and 
>>> policy combining we end up with a non-intuitive structure where 
>>> sometimes behavior is consistent and sometimes not depending on the 
>>> subtleties of the whether the container is a container of Rules 
>>> directly or a container of containers of Rules.
>>>
>>> Now my proposal is not to take away any of the above-mentioned 
>>> behavior from those who choose to use it, but to offer an 
>>> alternative behavior which is container-consistent, which will 
>>> enable one to focus on managing collections of Rules without 
>>> worrying about whether the structure of the containers might contain 
>>> unexpected side-effects such as described above.
>>>
>>> The extended algorithms provide this container uniformity, while at 
>>> the same time not introducing new complexity, but simply by avoiding 
>>> removing potentially useful decision making information. With the 
>>> combined algorithms, for example, a top level deny-overrides 
>>> PolicySet will always know when it receives an Indeterminate, 
>>> whether that Indeterminate was a potential deny or not.
>>>
>>> I believe the combination of retaining information that is lost from 
>>> the existing algorithms plus the conceptual improvement of having 
>>> uniform container algorithms is sufficient justification to include 
>>> these extended algorithms as valuable options that one can choose. 
>>> No one will have to use them under any circumstances, but I believe 
>>> that there are organizations that would value the conceptual 
>>> simplification that the extended algorithms offer from the 
>>> perspective of getting consistent behavior from the container 
>>> structures.
>>>
>>> Thanks,
>>> Rich
>>>
>>>
>>>
>>>
>>>
>>>
>>> Erik Rissanen wrote:
>>>> All,
>>>>
>>>> We still have the combining algorithms issue to consider. I have 
>>>> written some text to consider and tried to organize the decisions 
>>>> we need to make.
>>>>
>>>> First, do we want to fix the current deny/permit policy algorithms 
>>>> at all? I think we should since it is not good that the basic 
>>>> algorithms are biased. It can lead to strange effects in policies, 
>>>> like a policy can return Deny although there is no rule with 
>>>> Effect="Deny" in it.
>>>>
>>>> Assuming that we do want to fix the basic combining algorithms so 
>>>> that they are not biased, then there are two orthogonal decisions 
>>>> for us to make:
>>>>
>>>> 1. Do we want to define biased algorithms as well, or do we rely on 
>>>> the PEP bias alone?
>>>>
>>>> 2. Do we want to make use of an extended Indeterminate to allow 
>>>> more fine grained treatment of errors in the combining algorithms?
>>>>
>>>> See the attached documents for what the different algorithms look 
>>>> like.
>>>>
>>>> comb-algs.doc contains combining algorithms which makes the basic 
>>>> algorithms unbiased and introduces separate biased algorithms. The 
>>>> word diff is against the current 3.0 working draft 7.
>>>>
>>>> comb-algs-extended.doc shows algorithms which make use of an 
>>>> extended indeterminate. The diff is against the unbiased algorithms 
>>>> in comb-algs.doc. I have not "ported" the other algorithms to the 
>>>> extended Indeterminate yet or written biased variants. Also note 
>>>> that under the extended indeterminate the rule and policy combining 
>>>> algorithms become the same, so I joined up their descriptions.
>>>>
>>>> My preference is that
>>>>
>>>> - The basic combining algorithms are made unbiased. (I feel 
>>>> strongly about this, the rest I care less about.)
>>>>
>>>> - We do not introduce biased alternatives. (I am happy with the PEP 
>>>> bias.)
>>>>
>>>> - We do not introduce an extended indeterminate. (I think it 
>>>> complicates matters for fairly little value.)
>>>>
>>>> Best regards,
>>>> Erik
>>>> ------------------------------------------------------------------------ 
>>>>
>>>>
>>>> ---------------------------------------------------------------------
>>>> 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 
>>
>>