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

Jed at Webstart donnelley1 at webstart.com
Mon Nov 27 16:46:32 CST 2006

At 04:11 AM 11/27/2006, Marcus Brinkmann wrote:
>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.

As I've oft repeated on this list I'm an advocate of the "network down"
approach to creating greater market share for object/capabilities.  At the
network level (e.g. YURLs and CapWiki, wideword, etc.) I believe the design
options, protocols, etc. are quite apparent and the trade-offs between
protocol options are fairly easy to access.  The one microkernel system
that I designed, NLTSS:


basically made all processes appear as if they were on a network, so the
design issues were the same (e.g.:


).  That system failed to deal with confinement adequately.  Dealing with
confinement generally for systems connected to the Internet I think is
a bit of an issue - seeming to fall on the shoulders of whatever manages
the domains of processes/active objects.  That might get back into the
realm of microkernel designs, but one would hope that however the
microkernel is designed it can at least limit communication to that
specifically granted by object/capabilities (POLA) - as NLTSS did not.

>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.

I believe to satisfy the TCSEC sorts of concerns it would suffice to
have delegation between people tracked/audited.  This can happen
of course only if people want it to happen, but it can be set up
so that it is simple and natural to do and that it is recommended
policy.  It's been noted again and again on this list how it's
possible to set up revocable capabilities, membranes, etc. on top
of a simple base capability communication mechanism.  If such
tracked delegation is used relatively rarely (relative to all process
to process delegations) then I don't believe it need substantially
effect system overhead.

>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 ;)

The later is what I was suggesting above.  Since I have implemented
a comparable scheme, I know that it can be as simple as 'mere' book keeping,
though of course it need not be.  In our system an application wishing to
create a revocable capability (similar to delegation) would make such a
request of the server.  The server would add a book keeping entry and
return a new capability with the same permission (but that can be revoked
through the book keeping entry, can have it's access audited, etc.).
In our system the revocable capability went back to the requesting
process that had the base capability.  To effectively place responsibility
a delegated capability must be communicated directly to the
subject (person, process acting on their behalf) - the delegate.
That's the part of this procedure/protocol I would like to see discussed
more if there is sufficient merit.

>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 that case I argue that the design is flawed - though perhaps we aren't
using common terminology.  Clearly the server can "revoke" any capability
that it serves simply by noting in whatever table structure it uses to
define the meaning of the capability that the capability is no longer

>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).

You haven't touched on any issues above that give me concern.
I'll leave it to others to see if they notice any potential problems there.

>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'm getting the sense that you are dealing with the 'lost object'
problem.  Namely an effort to notice if all the references to
an object have been removed - so that the object itself can
be destroyed.  While I consider this an interesting problem
(we dealt with it using an accounting mechanism - pay for it
and it stays even if there are no references, stop paying for
it and it is destroyed even if there are outstanding references)
I believe it is a distinct problem/issue.  For the purposes of
lost object tracking the base capability and the revocable
capability are distinct (if for no other reason than to recover
the revocation state if the revocable capability no longer has
any references).  Revoking a capability effectively destroys
the resource that it's capabilities point to - rather than
what would happen if a reference to a capability (revocable
or not) is removed.

>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.

This is one reason why I believe in the "network first" approach.
Performance issues at the network level are generally dwarfed by
network latency (typically many milliseconds) so they usually
aren't as much of a concern.  Of course if a protocol requires
multiple round trip times then performance can again become
a problem.  This is indeed an issue with the sorts of implementations
that I imagine, but I don't believe the problems are serious.  Certainly
nothing like the layered redirections in CapDesk - if I'm remembering
Alan Karp's comment on that system correctly.

I also believe that the "world at large" doesn't give a hoot for
object/capability operating systems at this point.  They have no
market share.  If systems like Polaris and/or Plash end up being
layered on current market leading systems (Windows and Unix)
and introduce noticeable overhead then there may certainly
be some issues there.  Yet another reason why I'm most
hopeful about the network first approach.

--Jed http://www.webstart.com/jed/ 

More information about the cap-talk mailing list