[cap-talk] Use-case: hybrid capability systems

[Jed Donnelley]

On 2/4/2008 11:24 AM, Jonathan S. Shapiro wrote:
> I have a use case that I do not know how to adequately solve in
> real-world terms in a pure capability system. Perhaps someone else will
> be able to propose one.
> 
> I want to preface this by saying that I do not have the statement of
> requirements adequately refined. In particular, I suspect that one
> result of the discussion will be significant revision to the threat
> model.
> 
> 
> Use-Case:
> 
> We have a group of people who are working collaboratively on a
> graph-structured data set. Ground rules for normal use are:
> 
>   1. All parties have co-equal access.
>   2. The legitimate activities of the parties involve frequent
>      transfer of capabilities within the group.
>   3. All parties are permitted to update the graph, by which I
>      mean that they are expected, in the normal course of their
>      efforts, to insert capabilities into the structure.
>   4. The collaborative nature of the effort makes it likely that
>      party A, who has legitimate access in their own right to some
>      capability C, will interact during decision making with party
>      B (also a member of the group), and in the course of that 
>      interaction the capability C will be duplicated back and forth
>      during the discussion. One result of this is that the capability
>      that ultimately gets inserted into the data structure is likely
>      to be C', where C' is the result of some number of exchanges
>      of the original capability C.
> 
> We assume that the parties A, B are not hostile (if they are, that is an
> auditing problem). Party B now leaves the project. We now wish to ensure
> that:
> 
>   R1. B's authority to mutate the data set is eliminated in the absence
>       of conspiracy with a continuing group member.
>   R2. B's authority to *access* the data set is similarly eliminated in
>       the absence of conspiracy with a continuing group member.
>   R3. No portion of the graph structure is damaged as a consequence of
>       the enforcement of R1, R2.
>   R4. The implementation mechanism used to enforce R1, R2 is scalable
>       and efficient under conditions of normal use (i.e. when group
>       membership is stable, under normal operating conditions).
>   R5. The elimination of a member of the group, and the subsequent
>       permission modifications necessary to enforce R1, R2 have an
>       efficient implementation.
> 
> Some constraints must be satisfied in any practical solution:
> 
>   C1. No solution requiring new storage to be allocated during every
>       communication between the authorized parties is practical.
> 
>   C2. No solution requiring a mediator is admissible. Rationale:
>       we cannot afford to more than double the cost of every object
>       invocation. Solutions that are able to perform a mediation check
>       and somehow cache the result in order to achieve reasonable
>       efficiency are acceptable.
> 
>   C3. While we assume that parties A and B are not hostile, we assume
>       pragmatically that they are unable to successfully remember all
>       of the places that they may have stored capabilities into the
>       data set.
> 
>   C4. We are not concerned with *copies* made by the parties -- only
>       with capabilities to the definitive data set.
> 
> 
> Anybody see a way to do this with a pure capability design?

Interesting.  Of course a scenario like above is exactly
where I've been shooting at with the Horton mechanisms.

The only point where Horton has problems with the above
are at C1 and possibly at C2 (though as you say, I
believe this performance issue can be optimized away).

The reason a Horton sort of approach fails C1 is that
it must keep track of the delegation path - e.g. to
protect from confused deputies if for no other reason,
but of course there are other reasons such as the
typical requirement for logging for auditing.

Hmmm.  I wonder if I was reading more into C1 than
you intended?  Might you be satisfied with a fixed
size storage allocation for a delegation path?  If
that's the case then it would seem that the issue
would be to see whether the issue of an exhausted
store for path delegation could be handled in an
acceptable manner.  One possibility that occurs
to me is to mark the last available space for a
delegation to indicate this "overflow" situation
and that the communicated capability should be
considered invalid as should any future delegations.
Invocations could of course return an appropriate
error indication (e.g. "invalid by delegation path
overflow").

I expect this approach would be safe from the viewpoints
of security, confused deputies, and the like.  It
seems to me it would fall into the category of
many other sorts of resource exhaustion (e.g.
full file system conditions), but I know you are
sensitive about such things Jonathan, so I don't
know if this C1 condition could be adequately met
with a Horton sort of implementation.

>  It's completely straightforward in a hybrid design.

Since I'm still not sure what is meant by a "hybrid"
design, I'm afraid I can't comment on the above.
I would be interested to hear at least the basic
idea behind the "hybrid design" that you consider
a "completely straight forward" solution to the
above.

Do you consider the Horton mechanism that I
suggest (I can of course give more details
if you like - e.g. see the Capability MLS
scheme message that you apparently only
read a part of:

http://www.eros-os.org/pipermail/cap-talk/2008-February/009758.html

) a "hybrid design"?  The approach to meeting
the above criteria would be similar, but with
a simpler PDP (IDs are either in the project
with access or out of the project with no
access).

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