[cap-talk] On revocation and the use of wrappers and In Defenseof Identities

[Jonathan S. Shapiro]

On Mon, 2007-01-15 at 06:09 +0100, Pierre THIERRY wrote:
> Scribit Marcus Brinkmann dies 07/12/2006 hora 17:35:
> > Two existing implementations:
> > 
> > 1) Make invocation constant in time and revocation linear in time with
> >    the depth of delegation.  This is what current L4 implementations
> >    do.  In this case, the revoker will be punished.  L4 does allow
> >    arbitrary nesting (even in the L4.sec designs) at the cost of
> >    making unmap() preemptible.
> > 
> > 2) Make invocation linear in time with the depth of delegation and
> >    revocation constant in time.  This is what EROS does.  In this
> >    case, the invoker will be punished.  EROS does not allow arbitrary
> >    nesting.
> 
> Maybe I'm missing something about that previous discussion on revokation
> and delegation: you discuss time linear with the depth of delegation,
> but isn't delegation a tree? Then shouldn't time be exponential with
> depth of delegation?

No, but I DID make some errors in my previous statement. Here is an
attempt to correct that:

FACTS (as I understand them):

L4.1:   Receiver of invocation can be determined in constant time.

L4.2:   Revocation of delegations is linear in the total number of
        delegations that have been performed below the point of
        revocation (because each delegation only needs to be revoked
        once).

L4.3:   All capability transfers are performed by map. Therefore all
        capability transfers are revocable delegations.

L4.4:   Capability transfer often has the same cost as revocation,
        because an occupied slot must be revoked before it can be
        overwritten.



EROS.1: Receiver of invocation can be determined in time that is
        linear in the number of revocable delegations of the
        capability being invoked.

EROS.2: Revocation of revocable delegations is constant time.

EROS.3: All capability transfers are performed by copy. Capability
        transfers are not revocable unless special actions are taken.

EROS.4: Capability transfer takes constant time.


OPINIONS:

1. Relative performance is NOT simple to compare. Every IPC transfers at
least one capability (the reply capability), and this will invariably go
into an occupied slot. Therefore, the cost of IPC is determined by

   L4.1   + L4.4   => linear in total number of delegations of
                      capability being overwritten

                      [times number of caps received, but this
                       is usually 1]

   EROS.1 + EROS.4 => linear in depth of delegations of invoked
                      cap

2. If we believe that most IPCs involve processes at the "leaves" of the
delegation tree (which does seem likely), the L4 design may be better.

3. The EROS design is not intended to be heavily used without trusted
mediators. A correctly implemented family of mediators can keep the
chain depth at one.


NOTE

Eric Northup has proposed an internal optimization in EROS that would
cache the traversal, yielding a typical case invocation in unit time but
a revocation delay that is linear in the depth of the delegation.
-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
+1 443 927 1719 x5100