the deadly hypercube of death, or: handling permissions

[Marcus Brinkmann]

Hi,

I was considering permissions lately, and have reached some
preliminary conclusions that I would like to share with you.

As a first approximation, permission bits are, semantically speaking,
a user-modificable part of the protected payload of an object (the
protected payload usually contains the object ID).  The user can
modify this part by clearing bits (setting them to zero), thereby
downgrading the permissions.

Currently, there is no support for that in Coyotos, although we
reserved a couple of bits for that purpose.  Neal and I wanted this to
be a kernel operation, because then you can downgrade a capability
without invoking it, thereby allowing downgrading capabilities of
unknown origin on behalf of somebody else (ie, the directory server
can downgrade capabilities before giving them to a client).

However, I am backing off.  The reason I am backing off is that this
is not a uniform solution.  For example, polycasting will _always_
involve a call to the server, and furthermore permission bits may have
different semantics than just "clear-only".  For example, some
combinations of permission bits may not be allowed or used to mean
something differently than expected.  Also, one may want to have a
"write protection bit" that can be arbitrarily switched on and off,
but which provides a form of protection against accidential writes.
In other words, some bits may be advisory from the client to the
server.

To allow the full spectrum of flexibility, we should design our system
to not rely on this minimal kernel feature we envisioned.  In the
specific example of the directory server, the same job could be done
by the powerbox, or by some proxy directory server.  How to do this is
part of the discussion of what "recovery boundaries" are etc.  Here, I
want to talk about permission bits only and assume that invoking the
server is OK.

To simplify the discussion, I will only talk about N permission bits,
which are independent of each other, and which can only be downgraded.
Now I will consider the effect of the presence of permission bits on
the object type hierarchy.  It seems to me that it is useful to have a
simple type system (single inheritance), and to use it consistently to
express the semantics of the objects involved.  We have previously
considered how to do this for polymorphic objects like DogCows (or
zipped tar files).  I will now apply the lessons from that to the case
of permission bits.

To give specific examples, I will talk about I/O objects, which have
the permission bits "readable" and "writable", and File objects, which
are derived from I/O objects, inherit their permission bits, but also
add another permission bit, executable.  This example is somewhat
artificial, but it allows me to give useful examples.

To handle permission bits within the object type system, I will
consider each combination of permission bits as a different object
type.  This means that for I/O objects, there exist four variations:
IO_none, IO_readable, IO_writable, IO_readwritable, in short: IO,
IO_R, IO_W, IO_RW.  For file objects, there exist 8 combinations.

This is how the inheritance tree looks like for the I/O objects:

           BASE
            |
            IO
           /  \
        IO_R  IO_W
           \  /
           IO_RW

Downgrading an object type to one with reduced permissions is then
simply an operation that walks up in the object hierarchy, toward the
root of the tree.

As we can see, this shape requires multiple inheritance.  Kathy Sierra
and Bert Bates call this shape in their Book "Head First Java" the
"Deadly Diamond of Death".  It is easy to show that the shape for N
orthogonal permission bits is an N-dimensional hypercube with directed
edges.

To reduce this graph to a graph using only single-inheritance, the
different IO object types can be made siblings of each other, ignoring
their interdependencies.  (There is some flexibility here in how the
tree is constructed.  However, they are all related by simple
equivalence relations, so I settled on the clearest representation).

           BASE
         / |   | \
        /  |   |  \
       /   |   |   \
     IO  IO_R IO_W  IO_RW

This means that we are loosing all information about which variant can
be used by downgrading.  The effect of a permission bit is now to
partition the object type hierarchy into 2^N equivalent sub-trees,
each of which represents one of the possible combinations of
permission bits.

Permissions can then not be downgraded within the type system anymore.
Instead, the "polycast" operation needs to be used to select a
different "facet" of the same object, namely one that has a different
set of permissions.  The actual check if the transition is allowed or
not must be done in the object implementation itself.  From a
perspective of type purity, that is unfortunate (and must be
considered a defect).  However, it is also the solution that provides
the most flexibility.

One can now easily extend this to inheritance and inheritance that
extends the object type by more permission bits:

           _______ B A S E _____
         _/           |         \_
        /             |           \
      IO             IO_R          ...etc...
     / \             / \
  FILE  FILE_X  FILE_R  FILE_RX

One interesting property of this tree is that for every such
"fan-out", we get back the "original object hierarchy" without
consideration of permission bits by taking the left-most child.  Of
course, if you have more than one derived type, you need to take the
left-most child of each of those.  Another property is that if you
take a leaf node and all its ancestors, you get a copy of the
"original object hierarchy" with each node substituted by its
permission-derived node that has the same permissions as the leaf-node
(or rather, the subset of permissions that are relevant to the type of
the object at that node).

In the actual implementation, CapIDL could be extended to allow to
"tag" each interface with a set of permissions (or combinations
thereof) that are valid (possible) for this type.  Then CapIDL can
automatically generate the above tree and assign each object type with
any valid permission combination a valid type identifier.  This can
then be used in the polycast operation.  Also, support functions that
allow the user and implementor of a capability to separate the
permission bits from the object type (identified by the object type
without any permissions) and reverse can be generated automatically.

At the server side, every capability that names a distinguished object
requires a different wrapper object (there are other equivalent
options, but for simplicity I assume the use of wrappers).  But the
same object accessed with different permissions also needs a different
wrapper object.  Again, support for this can be mostly automatic, if
the maximum number of bits needed to represent all valid permission
combinations is known (in the case of N independent permission bits,
this is of course N).

CapIDL could even generate automatic permission downgrade checking, if
it knows the semantic rules of their interrelationship.  A simple rule
would be to consider all permission bits to be independent.  However,
as there is a good motivation to make the actual number of possible
permission combinations as small as possible, and the server can
easily implement these checks themselves, and implementing them
explicitely allows for more flexibility in defining the semantics (for
example, requiring that X is only present if R is present as well), I
would argue for simplicity and flexibility and leave CapIDL ignorant
of semantics of permission bits.

Summary: I have shown how permission bits with arbitrary semantic
meaning can be integrated into an object type hierarchy that only
supports single-inheritance, using the polycast operation.  This can
be used to implement automatic support for permission bits into the
IDL subsystem.

Thanks,
Marcus