formalizing the chaining and reduction... v4

[Frank Siebenlist <franks@mcs.anl.gov>]

Assume n+1 subjects: Si with 0 <= i <= n

Arbitrarily, we designate two subjects to be special:
S0 is the resource owner
Sn is the original requester

Note that the assignment of the numbers 0 and n are arbitrary, but not the
identification of the resource owner and requester subjects themselves.

Each subject is also a PDP with its own set of policy rules:
n+1 PDPs: PDPi with 0 <= i <= n

Give a certain access request, i.e. "resource, action",
Let each subject-pdp evaluate a decision for any one of
the other subjects:
PDPi(Sj, resource, action) = Di,j
or
Di,j is decision D issued by Si's PDP about whether Sj is allowed "resource,action"


Given a fixed request ("resource, action"), we can construct a decision matrix
for Di,j with 0 <= i <= n and 1 <= j <= n

In general, this would look for "n" like:

D0,0   D0,1   D0,2   .... D0,n-1   D0,n
D1,0   D1,1   D1,2   .... D1,n-1   D1,n
....   ....   ....   .... ....     ....
Dn-2,0 Dn-2,1 Dn-2,2 .... Dn-2,n-1 Dn-2,n
Dn-1,0 Dn-1,1 Dn-1,2 .... Dn-1,n-1 Dn-1,n
Dn,0   Dn,1   Dn,2   .... Dn,n-1   Dn,n

Note that "0" is the resource owner and "n" is the requester.

Let's first eliminate the row Dn,* because we don't care what the
requester says about the other subjects:

D0,0   D0,1   D0,2   .... D0,n-1   D0,n
D1,0   D1,1   D1,2   .... D1,n-1   D1,n
....   ....   ....   .... ....     ....
Dn-2,0 Dn-2,1 Dn-2,2 .... Dn-2,n-1 Dn-2,n
Dn-1,0 Dn-1,1 Dn-1,2 .... Dn-1,n-1 Dn-1,n

Next, we don't care what the subject say about themselves:

----   D0,1   D0,2   .... D0,n-1   D0,n
D1,0   ----   D1,2   .... D1,n-1   D1,n
....   ....   ....   .... ....     ....
Dn-2,0 Dn-2,1 Dn-2,2 .... Dn-2,n-1 Dn-2,n
Dn-1,0 Dn-1,1 Dn-1,2 .... -----    Dn-1,n

Then we can eliminate what other subjects say about the resource owner,
because the resource owner doesn't care:

---- D0,1   D0,2   .... D0,n-1   D0,n
---- ----   D1,2   .... D1,n-1   D1,n
.... ....   ....   .... ....     ....
---- Dn-2,1 Dn-2,2 .... Dn-2,n-1 Dn-2,n
---- Dn-1,1 Dn-1,2 .... -----    Dn-1,n

This is the decision matrix that the Master-PDP can construct, and it's now up
to this Master-PDP to determine from the different decisions whether or not the
requester is allowed access.

Note that we can distinguish a number of "special" decisions, like
element D0,n which is the resource owners decision about the original requester,
or D*,n which are the decisions of all the subjects about the requester,
or D0,* which are the resource owner's decisions about all other subjects

Let decisions be P,D,N (Permit,Deny,NotApplicable)

For example for n=3 we have:

---- (D0,1)=P (D0,2)=N (D0,3)=N
---- -------- (D1,2)=N (D1,3)=P
---- (D2,1)=D -------- (D2,3)=N

One can see from this example that the resource owner does not have any policy
applicable to the requesters access request:(D0,3)=N
Furthermore, subject-1 is the only one that allows the requester access:(D1,3)=P
while the resource owner also allows subject-1 access:(D0,1)=P

Intuitively, we could deduce that if the resource owner allows Subject-1, and
Subject-1 allows the requester, then the resource owner will allow the requester
to access the resource... however, this really depends on the enforced
combinator and reduction rules from the Master-PDP's policy.

Now we have to introduce the reduction and combinator rules that the Master-PDP
can use...

The first rule is that the resource owner is the source of authority, which
means that the decision of a subject is irrelevant unless that subject is
somehow empowered directly or indirectly by the resource owner.

The second rule is that if one subject grants access rights to another subject,
then that other subject can delegate those access rights again to someone else.
In other words, the issuer of a Permit decision for a subject will honor the
Permit decision issued by that subject to another subject. This allows one to
reduce a chain of two decisions to a single decision where the "middleman" is
taken out: (Di,j)=P + (Dj,k)=P => (Di,k)=P

The third rule is that Permit-Overrides, which means that if multiple policy
decisions are issued by the same issuer-subject for an other access-subject,
then any Permit decision by that issuer will overrule any other decision by that
same issuer.
So, as soon a single Permit decision is determined, no other evaluation are
needed: (Di,j)=P + (Di,j)=? => (Di,j)=P

Note that only decisions made by the same issuing subject can be combined.

A "permit-decision-chain" is defined as a sequential-list of only
permit-decisions "(Di,j)=P + (Dj,k)=P + (Dk,l)=P + ..."
Note that the issuer-subject of the "next" decision equals the access-subject of
the "previous" one.

With "access rights equals delegation rights" and "permit-override"
combinator policies, any permit-decision-chain that start with the resource
owner as issuer-subject and ends with the requester as access-subject yields an
overall Permit decision.

In other words, the Master-PDP should search for permit-decision-chains that
start with the resource owner and end with the requester, and any such found
decisions chain will yield an overall Permit decision, while the inability to
find such a chain should yield an overall Deny decision.

This implies that any decision chain that is not a permit-decision-chain, or is
a permit-decision-chain that is not started with the owner and ended with the
requester, can be discarded.

This also implies that the Master-PDP can stop as soon as it found a single
permit-decision-chain that starts with the owner and ends with the requester,
which allows for different strategies to find such a chain, like a simple
exhaustive search through the permutation space, or an algorithm guided by
performance considerations.

For example, the Master-PDP's permit-decision-chain search algorithm could start
on the requester's end and try to work backwards to construct a
permit-decision-chain that begins with the resource owner:

   search for Permit decisions in column D*,n and start with D0,n
     if (D0,n)=P then overall decision is Permit
     else, for any k where (Dk,n)==P
       search for a Permit decision in column D*,k and start with D0,k
         if (D0,k)==P then overall decision is Permit
         else, for any l where (Dl,k)==P
           search for a Permit decision in column D*,l and start with D0,l
             if (D0,l)==P then overall decision is Permit
             ...
             until no more pdp-subjects left and the overall decision is Deny

(note that the algorithm should detect and avoid recursion in the decision
chain, and the iteration could be better expressed through recursive function...
exercise for the reader ;-) )

...

It may be good to expand on this for the authz processing doc...

Regards, Frank.

-- 
Frank Siebenlist               franks@mcs.anl.gov
The Globus Alliance - Argonne National Laboratory