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

[Marcus Brinkmann]

At Thu, 07 Dec 2006 09:41:08 -0500,
"Jonathan S. Shapiro" <shap at eros-os.com> wrote:
> 
> On Thu, 2006-12-07 at 14:57 +0100, Marcus Brinkmann wrote:
> > > The server can always refuse if a given capability has been delegated
> > > too many times.
> > 
> > As Neal said.  Or: "What's too many?" [1]
> 
> I appreciate the humor, but there is a serious problem here in the OS
> context. If wrapping or delegation involves building a data structure,
> my bet is that data structure will grow linearly in the number of
> delegations.

I can accept that assumption.

> In order for the OS to have bounded-time operations, it MUST set a bound
> on the number of steps it will take in any given operation.

Sure, that's an obvious truism.  But an operation can also be
preemptible, in which case it does not need to be bounded in time (at
least from the kernel's perspective).  Yes, this causes other
problems.  But it can be a viable design alternative.

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.

EROS does not need preemptible operations, but it puts a hard limit at
the depth of delegation possible.  L4 is highly optimized for the
common case, but punishes the wrong party: The revoker does not
control subsequent delegations, thus it should not be punished by
them.

There is a third alternative: If one favors flexibility and security,
one would want to make revocation constant in time like EROS, but
allow arbitrary nesting like L4.  The consequence would be a hefty
performance and code complexity penalty because invocation would need
to be preemptible.  However, it seems to me that this third
alternative may be a safer approach than what L4 is doing.

I do not know about a system that follows this approach, thus I can
not say if it is "viable" or not.  It sounds interesting to me in any
case.

> Brinkmann and Walfield's "Critique of the Hurd" complains that EROS
> imposes such a limit (He states it incorrectly at 4.  The actual number
> is 20)

As for the critique, see Neal's reply.  Thanks for giving the actual
number, I keep forgetting it, although I think I remember that it was
supposed to be much smaller in Coyotos.  If I mentioned a 4 somewhere,
it may have been some left-over bits of information from our Coyotos
discussions.

> but fails to contemplate the consequences of his preferred
> alternative (unstated, but presumed to be "no traversal limit").
>
> The absence of a limit entails loss of bounded-time atomicity and
> potential infinite loops in the forwarding structures that the
> kernel cannot effectively guard against.

That may be true for EROS/Coyotos.  Unless I am missing something
fundamental, it does not necessarily needs to be true for other
systems as well.

> RANT
> 
> Nobody likes having the bound, but I confess I get annoyed by that
> particular critique. It comes up surprisingly often, but I have *never*
> observed the critic to either consider the alternative or propose a
> viable replacement mechanism.
>
> I'm not annoyed at Neal or Marcus. I just get tired of hearing one-sided
> reasoning on this issue.
> 
> END RANT

I don't criticize the bound in the context of the EROS/Coyotos
operating system.  It does what it does in an appropriate manner.
There is not much to be gained from simply removing (or increasing)
the bound in EROS and keeping the rest of the system as it is.  My
criticism of the bound stems from a desire to explore other system
designs which use revocable delegation without interposition as the
only delegation mechanism.  For these, other system mechanisms are
required.  Can such a system be viable?  Nobody has built (or
published) such a system yet, so we can't know for sure.

However, I am aware of at least one potentially viable replacement
mechanism, and that is the L4 mapping model.  It is an open question
if the L4 group can feasibly address the resource accounting problem,
but the L4.sec designs are interesting.  I have some doubts if the L4
unmap operation is really guaranteed to succeed at all in finite time
(I don't know any of the many implementations in sufficient detail),
but that may be because of aggressive optimization that can be
sacrificed (by corresponding checks in the map operation), or it may
be one of those warts that every system seems unavoidably to end up
with.

Design and Implementation of the Recursive Virtual Address Space Model for Small Scale Multiprocessor Systems
http://i30www.ira.uka.de/teaching/theses/l4ka/index.php?lid=en&year=2002&docid=814
L4.sec implementation:
http://www.tud-os.org/papers_ps/kauer-diplom.pdf

In fact, this was discussed before in some detail:
http://lists.gnu.org/archive/html/l4-hurd/2005-10/msg00419.html

Thanks,
Marcus