Confusing The Deputy (was: Split Capabilities: Making Capabilities Scale)

[Mark S. Miller]

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:

* If object A attempts to perform operation X, then object A must wish to 
   succeed at performing operation X.

* If object A holds adequate permissions to perform operation X, then it is 
    allowed to perform operation X.

* If it wishes to perform operation X and it is allowed to perform operation 
    X, then the security system should allow its attempt to perform operation X 
    to succeed.

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