[E-Lang] Transposing the Access Matrix

[Mark S. Miller]

At 12:12 PM 9/13/00 , David A. Wagner wrote:
>... I must
>admit to some skepticism about whether it is really the mere fact of
>storing permissions with subjects (as opposed to [resources]) that is buying
>you so much here, as opposed to explicitness or other features of the
>system.)

[David, other than wording cleanups, this is essentially identical to my 
private reply.  --MarkM]

First of all, this notion that capabilities and acls are merely transposes 
of the access matrix is wrong.  It is one of "those things everyone knows 
that ain't so" that does a lot of damage.  If you transpose the access 
matrix (transform an ACL system to store permissions with subjects rather 
than resources), you get something like SPKI, which we classify as a 
semi-capability system.  Why?  Contrast the diagram on 
http://www.erights.org/elib/capability/ode/ode-pki.html with the full 
Granovetter diagram.  In a semi-capability system, Alice requires access to 
Carol in order to give Bob access to Carol.  In a capability system, Alice 
additionally requires access to Bob, while a semi-capability system does not 
require this.  This latter issue is not a transpose of anything in acls.

This is the difference that enables capability systems to confine authority. 
(Confining covert bits is another matter entirely.)  Jonathan Shapiro's 
thesis proves that acls can't confine, essentially because that have no 
analog of this issue.  In a capability system, only connectivity begets 
connectivity, so subgraphs, once disjoint, can never become connected.

But, believe it or not, that's not the big deal.  The big deal is 
designation, as shown by the confused deputy.  If permissions are with the 
subject, then the subject's means of designating the resource can be combined 
with the subject's authority to operate on the resource.  If the permissions 
are with the resource, then the subject needs some other means to designate 
what he's operating on.  When the subject attempts an operation -- in oo 
terms, sends a message -- the permissions at the resource must be able to deny 
or allow the message.  That means the message must carry more than its 
explicit arguments.  These implicit arguments are a real added complexity.

What are these implicit arguments anyway?  They must be adequate to enable 
the permissions to make a decision.  Sometimes, one says that it is the 
"identity" of the invoker, but that would be completely confused.  The 
invoker is a little subject-object, one among a zillion.  The acl could list 
the zillion separate subjects that it might allow to access it, but then 
we'd lose abstraction.  Subject A could not call library routine X to do its 
job for it unless the acl also listed X.  If it did, then subject B could 
call X as well and successfully access the resource.

To escape this dilemma, acl folks instead introduce the notion of 
"Principal", which is even more badly confused.  It raises the granularity 
of security designation from objects to *people* -- the acls' designation 
that it check the implicit arguments against.  This loss of resolution is 
fatal.  It assumes that if I run a program written by you, then the program 
embodies only my intentions, not yours.  

The opposite statement is more true, but in fact we need to understand the 
resulting object as a mixture of our intentions.  
http://www.erights.org/elib/capability/3parts.html You determine what the 
program tries to do, but, if we have a decent security architecture, I can 
use the principle of least authority to constrain what the program can do.  
ACLs don't lose this ability to constraint merely by the transpose.  But the 
transpose causes it to introduce the notion of Principal, and once you've 
done that, you can kiss the principle of least authority goodbye.

There's another difference between the Granovetter diagrams: symmetry.  In 
the SPKI diagram, we show Carol as a box labeled "Resource", while Alice and 
Bob are circles.  In the real Granovetter diagram, Carol is a circle too.  
As is familiar from oo programming, everything is an object, and each object 
is both a resource and a subject.  Without this symmetry, we return to the 
old world of procedures operating on data.  The move from procedures to 
objects was often understood as a move to a more social metaphor.  Only with 
this symmetry can the change of access of objects to each other over time be 
understood socially -- as Granovetter originally intended.

Which raises another difference between capabilities and acls.  Capabilities 
are a model of secure computation, while acls are just a security model.  
Good modern languages for symbolic computation, whether they think of 
themselves as being primary about lambda or about objects, but designed with 
no regard to security, are nevertheless usually close approximations to pure 
capability systems.  Capabilities express fundamental truths about the 
organization of abstraction and modularity, and these truths are useful, 
even from a software engineering only perspective, down to very fine grains 
of computation.  I do not know of a single instance where similar statements 
could be said for acls.  No one treats acls as a model of computation, or a 
means of abstraction and modularity.  No one has independently discovered 
and built an acl-like system for non-security reasons.

Back to social metaphors: The transition from feudalism to capitalism is 
often understood as a transition from systems of status to systems of 
property and contract.  Does Joe have certain rights because of the kind of 
person he is, or simply because he's acquired these rights piecemeal from 
others who had these rights?  The need for special action by a sysadmin in a 
acl system is too much like needing to be emancipated in order to acquire 
more rights.  Acls may support the representation of rights, but only 
capabilities are about the transfer of rights.

That covers the transition from status to property.  What about contract?  
Before contract, bundles of rights were given: physical objects, land, 
money.  With the rise of contract, these rights could be unbundled and 
separately transferred; and new rights could be designed by abstraction from 
old rights.  The CoveredCallOptionsMaker in the Ode is a nice crisp example 
of doing this by normal object abstraction.

Frankly I am baffled at how something so obviously wrong could have won out 
over something so obviously right.  I do know some of the history, but I'm 
still baffled.  Many of the players are smart people!


                                   Designation Revisited

I ran into Norm at a party recently, and he had a fascinating new insight 
that he's been shy about putting up.  So if it's silly, blame me for it, I 
probably got it wrong anyway.

Back with Newtonian physics, and even special relativity, one could 
successfully pretend that there is a global coordinate space.  Of course 
everyone understood that no one coordinate space was privileged, but you 
could still pick one and fit everything into it.  With General Relativity 
and curved space-time, this pleasant notion was shattered.  Space is just a 
stitching together of local geometric relationships into an overall curved 
fabric, but this curvature could not be described as curves in a higher 
dimensional classic uncurved space.  There is only the space itself.  There 
cannot be any comprehensive means of designating places in the space other 
than to use the space itself.

Similarly, Norm [as interpreted by me, perhaps badly] speculates that, not 
only have all non-capability attempts to create a global designation system 
for mutually suspicious distributed computation been flawed, but that they 
must be flawed.  There cannot be any comprehensive system of secure entity 
designation in such a world that doesn't follow capability logic.  Note that 
"public-key fingerprint designates private key holder" does work, and does 
follow capability logic.

There are no global names.  There is only the topology of the distributed 
reference graph, held together by capabilities.


         Cheers,
         --MarkM