[cap-talk] Wikipedia: Object-capability model

[Jed Donnelley]

At 05:07 PM 1/5/2007, Mark Miller wrote:
>...
>I think we should indeed create a separate page for the "object
>capability model" as you originally proposed. There are many ways in
>which this model is more specific than the general category of even
>those cap systems we consider sensible. For example, purely
>crypto-based distributed cap systems (which is the only possible kind
>of cap system without a central point of failure among mutually
>suspicious machines on open networks) are not obj-cap systems.

I just want to point out that distributed capability systems need not
be crypto-based.  For example, the Distributed Capability Computing
System:

http://www.webstart.com/jed/papers/DCCS/

didn't use encryption anywhere.  It was based, somewhat amusingly,
on an ACL sort of mechanism.  Just to make sure people understand
this sort of alternative, I'll describe it briefly.

Every component Capability Computing System (CCS) in the DCCS
was assumed to have a network service process (server) whose
job it was to "remote" local capabilities and to emulate remote
capabilities (using the transparent wrapping that we've been
discussing a bit lately).  Any "remote" capability was represented
by an extended type capability pointing to this network server.

When a remoted capability was invoked, the emulating network
server processed the call by sending a message through the
network to the network server on the system where the "real"
capability was supported.  Of course data and potentially
capabilities may go across with such a message and may
come back in reply.  I won't go into that detail (pretty simply
actually) here.  However, one might ask:

1.  How does the system making the request identify the capability
to invoke on the remote system? and

2.  How does the remote system know whether or not to
trust the requesting system?  After all, it's simply data
coming across in the protocol.

The answer to #1 is that the request simply names an
index into a c-list (referred to as the "Support list" in
this diagram:

http://www.webstart.com/jed/papers/DCCS/figure4.gif
<from: http://www.webstart.com/jed/papers/DCCS/>

  ) on the remote system.  Some data in the extended
capability being used for the emulation provides the
address of the remote system and the index into it's
Supported list.  The answer to #2 is that each network
server keeps track of which other system's network
servers (essentially by network address) have access to
each individual capability in it's support list.  If a network
server tries to remotely invoke a capability that it's not
listing as having access to, then it's invocation is denied.
Remote servers get added to such lists when "capabilities"
are passed (remoted) to them through the normal invocation
mechanism.  The DCCS also had a sort of garbage collection
mechanism.  A server get's removed from an ACL when it
indicates that it no longer has a need for remote support
(supposedly when all instances of the emulated capability
disappear from the system doing the remoting).

One might imagine these days that a network address would
be inadequate to base trust in.  Those were simpler days.
You could argue that encryption is necessary to protect
the communication between such network servers.  That's
easy to imagine and could prove useful.

However, the main thing I want to point out is that there
is no need for any sort of per object encryption or even
any sort of Swiss Number mechanism with an approach
like this.

I don't want to defend this approach.  Others may well
be more effective (the topic of my later "Managing Domains"
paper:

http://www.webstart.com/jed/papers/Managing-Domains/

which did include cryptographic techniques). I just want to
clarify that distributed capability systems with no single
points of failure can be implemented without any sort of
per object encryption.

>Also, as Fred's upcoming thesis will do a wonderful job of pointing
>out, the obj-cap *model* is distinct from many other models adequate
>to describe, for example, DVH, in that there are no differentiated
>"read", "write", etc kinds of permission built into the model. Rather,
>there is only one kind of permission: the permission to invoke. The
>distinctions represented in other models as kinds of permissions are
>instead represented in the obj-cap model as differences in the
>behavior of the invoked object. This results in a wonderful
>simplification for many kinds of analysis. In actual systems,
>funneling all exercise of rights through invocation results in the
>kinds of virtualizability that Jed especially has been championing of
>late. Even when this virtualizability is imperfect, as in E or the
>KeyKOS line, imperfect virtualizability is still a huge benefit.

Are you referring to imperfect virtualizability regarding what I consider
"out of band" functions like "EQ?" or "MyCap?" or is there some
other sort of imperfection to virtualizability running around that
I should know about?  If so then I'd like to put together a list
of these sorts of "imperfections" and what gives rise to them.

I find it interesting to consider "EQ?" and "MyCap?" in the
context of a remoting mechanism like the DCCS.  The DCCS
really amounts to a "membrane" implementation.  The capabilities
kept on one side of the membrane show up in the "Support list".
People sometimes worry about the perfection of membrane
implementations in the face of "EQ?" or "MyCap?".  What if
the "real" capability is compared with that coming out through
the membrane?  In a remoting mechanism like the DCCS such
a situation can't arise, because it isn't possible for a "real"
capability to get 'directly' across the network.  Of course one
could imagine two competing "remoting" mechanisms.  In that
case instances of the same capability on some system might
show up as different emulations (which can be seen as
distinct with "EQ?", though not with "MyCap?") on some
other system.

>So here's an interesting question: For the cap OSes in, for example,
>Henry Levy's book, how many of them had enough virtualizability to be
>well described (even approximately) by the obj-cap model? I don't know
>the answer. But even if the answer is all of them, I would still think
>we're better off making a separate page.

I'll be interested to better understand just what sort of a refinement
the "Object-capability" model is on a more generic "capability"
model.  I should say that for me any sort of capability model
that allows the sort of remoting and I noted in the DCCS (as
a "membrane") is sufficient for my needs.

Just to start my own list of non-virtualizable objects, I'll note
the "file" object in the RATS system (page 9 of:

http://www.webstart.com/jed/papers/RATS/RATS.pdf

) had an "Attach" invocation that attached a part of the
file to a part of the invoking processes memory space.
In fact this was the only way in RATS to access the data
in a file.

The extension mechanism in RATS properly had no
means to virtualize a file object because the emulating
process was unable to manipulate (prohibited from
manipulating) the memory space of the invoking
process.


Perhaps others can describe other objects that can't
be virtualized by the extension mechanisms available
in other systems?  I'd like to understand why there are
such non-virtualizable objects.  In particular if there seems
to be any essential component that drives the creation
of such non-virtualizable objects.

To complete my example, I don't believe there was any
essential reason for the RATS file object to be non-virtualizable
as it was.  It might have been a bit more complex to
create virtualizable file and process objects in RATS, but
it could have been done (I say glibly) and with comparable
performance (more hand waving), even with virtual memory
mapping.


One category of systems in which at least "remoting" seems
a given are the network capability systems like NLTSS,
Amoeba and the Monash systems, perhaps Trix if I believe
my recent reading on it, DEMOS, others.  In these systems
the base "invocation" operation is imagined to happen
in general remotely.  That being the case the ability to
"remote" an object is a forgone conclusion.  It also seems
that virtualizing is naturally possible in such systems.

However, I believe I understood that such systems don't meet
the "Object-capability" criteria.  Why not?  Is it something
about the ability to look at the bits of a capability (stronger
than even "EQ?") that disqualifies them?  I believe they meet
the functional need I have for virtualizability (e.g. for functions
like revocation, Responsible Delegation, remoting, etc.).
What inadequacies are necessarily in these systems
that exclude them from the "Object-capability" class?

Just to cut off one avenue of attack on such system that I
consider as not generally applicable to the class (network
capability systems), I believe such systems can support
confinement by having the kernel know enough about
capabilities to safely extract what amounts to a network
address and safely do a handshake with the remote end
(perhaps with a key pair).  The trade-offs between building
a distributed network system from component descriptor
type "Object-capability" systems (e.g. along the lines
of the DCCS) vs. building network capability systems
from the get go (with a network invocation mechanism
supported by the kernel) interest me.  Of course I've
worked on one of each, so I guess this isn't surprising.

Interesting discussion.

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