[cap-talk] Capabilities - the rub, an account

[Marcus Brinkmann]

On Sun, 2006-11-26 at 13:02 -0800, Jed at Webstart wrote:
> >I think that this makes sense, and it is one reason why I consider
> >revocable copies an essential feature in capability systems.
> >Unfortunately, building a system that has unlimited (by the system)
> >nesting of capability wrappers and no denial-of-service threat scenario
> >is a big challenge (see the current L4 redesign efforts with
> >user-managed kernel memory).
> 
> I don't think such an implementation is as difficult as it might seem,
> particularly if the protocol for communicating permission goes through
> the server of the 'object'.  In that case what you consider a "big challenge"
> I believe becomes rather simple book keeping.

We are not specific enough here to make meaningful predictions.  But
within traditional and recent microkernel system designs (the ones I
know something about), pushing permissions through intermediates may be
prohibitively expensive.

The experience from L4 and EROS seems to show that we can make IPC in a
microkernel system fast enough to afford a single RPC round trip for
each operation (2 IPC operations), but the clans-and-chief protection
model of L4 was already considered too expensive because it required 4
IPC operations for each RPC.  The redirector model in L4 X.2 costs only
3 IPC operations and is still considered inadequate.

Communicating permissions through a third party may involve up to 6 IPC
operations (without any nesting) and more if you need to check the IDs
of principals in the system with a central server.

Of course, there may be alternatives.  One may try to design a
microkernel system that efficiently supports an alternative set of
operations that is more adequate to build such systems.  Or one may try
to design the operating system in a way to make such operations rare.
The latter is what we (Hurd) are currently pursuing.  But that is
arguably more challenging than mere bookkeeping ;)

However, my argument above goes beyond mere performance considerations.
There is a deeper problem involving timing guarantees.  Take for example
the L4 kernel, which has a rather straightforward capability mapping
model (for memory in L4 X.2, for other stuff as well in the upcoming
L4.sec designs).  The map operation can be performed in constant time,
no matter at which point in the hierarchy (and this requires tricky data
structures).  The unmap operation however is bounded by the height of
the unmapped subtree only.  This means in practice that a server can
only revoke a resource given to a client in a time that is only bounded
by the accumulated resources of programs cooperating with the client.
In this picture, it is difficult to design the system in a way that
gives the server a guarantee about the time it takes to revoke the
resources.  This should at least give rise to concern.  Now, these L4
designs do not properly account kernel resources to tasks anyway, which
is a long outstanding defect that the L4 groups now try to correct, and
it turns out to be a very delicate and complicated problem (see Bernhard
Kauers Diplomarbeit on Kernel Memory Management).

I can think of ways to do away with this problem.  For example, the
server may not care if the user's own resources down the hierarchy are
not released properly.  However, the challenge is to come up with
something that is both reliable and efficient.  If you only care about
one, it's not particularly challenging.

I think that one of the big problems the capability people are facing is
that the world at large cares more about efficiency than reliability.
Thus, we ignore performance issues at our own peril.

Thanks,
Marcus