Confusing The Deputy (was: Split Capabilities: Making Mark S. Miller (markm@caplet.com)
Sat, 08 Jul 2000 16:50:31 -0700

At 05:52 PM 7/7/00 , Karp, Alan wrote:
> > We need to distinguish between 1) using capabilities in a
> > natural capability
> > style vs 2) using capabilities to wrap legacy non-capability-oriented
> > systems (like file systems) vs 3) the possible advantages of
> > proposed new
> > styles.
>
>I don't see the usefulness of the distinction.

At 09:16 AM 6/29/00 , Karp, Alan wrote:
>... In the case of Unix-style file access control, I
>only need 3 capabilities for the world, 3 for each group, and 3 for each
>user, and each user only gets 9 of them. In both cases, files can be added
>to the system at any time without the need to create new capabilities.

The usefulness of the distinction is that it allows us to partition the discussion of, for example, this file proposal into separate issues.

  1. Natural Capability Style. Were one building, from scratch in a capability system, a set of abstractions to provide file-system-like services, would one try to do something like world/group/user cross read/write/execute? Several of us, including myself, would argue that one would not. Unless you're arguing that one would, I'll postpone elaborating.
  2. Legacy. If one is trying to simulate legacy file system semantics on top of a capability system (ie, Linux on EROS), then either your's or Norm's proposals seem reasonable. I don't understand your objection to Norm's proposal that it is ACL oriented -- the problem statement is ACL oriented. OTOH, if one is trying to wrap the file system accessible to an unprivileged user process implementing a capability system (E, E-speak), then there's no need to model the legacy restriction semantics. These are already imposed on this process.
  3. New Style. Perhaps you feel there's something of value in a pattern *like* the Unix file permission arrangement? That even in the absence of legacy considerations, it is a useful example of the kind of thing one might want to do anyway? If so, this would be interesting. But a non-legacy motivating example would be nice.

>There's still a problem with the approach you describe. Namely, over time
>I'll accumulate a large number of capabilities. Either I'll have to present
>them all on each request, in which case the permission checking will take a
>long time, or I'll need a way to track which ones I need for each request.
>If capabilities expire, I'll have to provide a way to get rid of those that
>are out of date.
>
>Since e-speak capabilities are so lightweight, presenting them all on every
>request is not a problem.

I think we have a deep difference of assumptions and (dare I use the term) paradigms here. For us, the most important lesson about the coherence of the capability programming paradigm is the Confused Deputy problem http://www.cis.upenn.edu/~KeyKOS/ConfusedDeputy.html . Those who haven't grokked the Confused Deputy would understandably find the following chain of reasoning plausible:

We call systems built according to these assumptions "ambient authority systems", since the authority applied to an operation is "in the air" -- it is implicitly part of the invoker's context. (Netscape's "capabilities" [sic] are actually an ambient authority system. SPKI is somewhere between the two. And for split capabilities, it remains to be seen.)

The flaw is the first step. To understand the flaw, we must distinguish between two kinds of object. An authority-reducing object provides to its clients less authority than it has access to. Such objects are the decentralized embodiments of the multitude of micro-security-policies that pervade systems built according to the principle of least authority. Norm's Deputy is one of these.

For non-authority-reducing objects, the above chain of reasoning may well be true. Most programmers, not practicing the principle of least authority at fine grain, write most of their code in a non-authority-reducing manner. This is perhaps why ambient authority architectures seem so plausible.

For an authority-reducing object, when it attempts operation X, it may wish to succeed exactly when it should succeed according to the security policy it is trying to embody and enforce. It would supply narrow and well chosen authority in its attempt to perform the operation exactly so that the operation will be disallowed when it would wish the operation to be disallowed. Even though it may hold sufficient authority to allow the operation, if its narrowly chosen set of authorities by themselves are insufficient, then it wishes to be prevented from performing the operation.

And it's properly narrower even then that! An operation typically contains several arguments, each designating a different object. Each argument position corresponds to a different role in the attempted operation. An authority reducing object should provide narrowly chosen authority to go along with each role (argument position) in the operating it is attempting. (It is this last step which is beyond SPKI.) This seems like a lot of trouble, until we get to punch line of the Confused Deputy: 

              "A Capability Combines Designation With Authority"
                                    --Norm Hardy

Because of this bundling, an authority-reducing object can often succeed at these duties in a simple and natural fashion by simply providing a capability in each argument position.

So, going back to E-speak, it is impressive that you can so efficiently check an operation against a large number of capabilities that might authorize it. By why would you want to? For legacy support? Ok, I can see that. For enabling the conventional capability style to scale? In the conventional capability style, use of such a pattern would be a clear sign of a design error. To support a new pattern that the rest of us are missing? Perhaps. 

         Cheers,
         --MarkM