Re: the deadly hypercube of death, or: handling permissions

[Marcus Brinkmann]

At Thu, 27 Apr 2006 09:29:25 +0200,
Ludovic Courtès <address@hidden> wrote:
> One consequence is that permission bits can be thought of as reserved,
> implementation-specific bits and thus, they no longer need to be made
> part of the "type" system, i.e., they don't need to be interpreted by
> the type system --- and indeed, "permission" has nothing to do with
> "type", and IMO mixing them is what's harmful to "type purity".

I am not su sure that they don't have anything to do with "type".
Take a pipe for example.  It provides a read end and a write end, and
both can be considered to be quite distinct types, and in fact
different objects that just share some common state, namely the data
buffer.  It's less obvious for other objects, though.  However, in
general there is some state or interface associated with a permission
that is not accessible without it (otherwise, why have permissions at
all?), and without being compromised by reading much literature on
languages and typing, :), it seems to me that if this does not mean
that absence or presence of permission bits indicate a type change,
then what does?

> So you end up with the "real", regular object hierarchy where single
> inheritance should suffice for most purposes.
> 
> > 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.
> 
> I'm not sure "permissions" and "downgrading" are concepts that could easily
> be described within the interface description, and then interpreted
> automatically.  One reason to this is that there can be various kinds of
> relationships among permissions: "depend-on" relations, "conflict-with"
> relations (maybe), and perhaps others.

If you start with multiple-inheritance and N independent bits, you get
the N-dimensional hypercube that has 2^N states (vertices) and
2^N*(N-1) transitions (edges).  Conflicts are relatively easy to deal
with, you just remove all the vertices (and associated edges) that
contain conflicting bits at the same time (that's an N-2 dimensional
sub-hypercube for two conflicting bits).  To take the pipe example,
you just remove the RW state and are left with "none", "R" and "W".
Depend on relationships are also relatively easy: You can just drop
the depending bit when the dependend on bit is cleared.  All
transitions that violate that are removed (and any components that are
not reachable anymore after the removal).

You have to do something really funny to not be able to represent the
permission transitions with a static graph.  For example, if you make
the allowed transitions dependent on the state of the object, you
introduce a dynamic parameter that would be difficult to represent in
the type system, especially if the state is internal.  Also, if you
make the allowed transition dependent on capability arguments provided
to an interface method, ie a lock+key mechanism.  Or right
amplification.  It's a good idea to stay away from this stuff, though.

Thanks,
Marcus