[e-lang] capability myths demolished!

Zooko e-lang@mail.eros-os.org
Wed, 27 Nov 2002 20:56:17 -0500


MarkM:

Thank you for working on this document.  I think it is very important at this 
stage in history that this paper be written.  Bravo!

This letter contains a specific suggestion, a categorization of different kinds 
of pro-capability arguments, plus a FREE bonus political rant.

I think that the document's explanation of why caps can enforce POLA is 
insufficient.

To me, the most important difference between ACLs and caps is that caps can 
implement Marc Stiegler's story (and demo) about downloading a text editor from 
a questionable source and giving it a test drive while not incurring any 
unnecessary risk.

This is POLA, but I do not think that the "nature" of the subjects (humans 
or computational objects) is the key difference.  As Hal Finney has pointed out, 
ACLs can use subjects that represent other things (programs, "nobody", roles).

I think that the essential question is "What authority is required in order to 
implement this story?".

I believe that ACLs can also implement the same text editor POLA story, but only 
by using the superuser/administrator account to create a new principal, and 
changing your UID to that principal before running the text editor.

So, my current understanding is that ACLs do not offer *dynamic*, *non-higher-
power-requiring* POLA.  (This is a bit of funny recursion.  ACLs can implement 
POLA, but only caps can implement POLA while using the least necessary 
authority.)

This is a purely technical difference: whether or not you can dynamically create 
a new protection domain without requiring superuser privileges.  [footnote1] 
I think advantages of capability systems over ACLs can be grouped into three 
categories:

1.  technical

1.a.  dynamic, non-higher-power-requiring POLA
1.b.  endogenous verification [Shapiro99]
1.c.  efficient revocation [Chander01] [footnote2]

2.  engineering

2.a.  unification of designation with authority (help the confused deputy)
2.b.  unification of access and authorization [footnote3]
2.c.  capabilities fit into the object oriented paradigm
2.d.  practical POLA (because of 1.a, 2.a, 2.b, 2.c, ...)
2.e.  practical confinement allowing untrusted code (because of 2.d)

3.  political

3.a.  not confining humans, not prohibiting delegation by humans
3.b.  limiting your vulnerability to humans vs. identifying and controlling them
3.c.  decentralization vs. centralization

I think that a lot of scientists out there would benefit from a closer look at 
the topics in category 1, without the potential distraction of topics from the 
other categories.

Of course, the reason *I* care so strongly about it lies in category 3.  I now 
believe that unless a practical POLA system can be deployed (that allows people 
to safely look at the dancing bears in their e-mail), that the world's computer 
security problems will instead be solved by making it so that code only executes 
after the operating system has checked in with central HQ to see if the 
registered author of the code is in good standing with all of the relevant 
authorities.

Regards,

Zooko

[footnote1]  Once you imagine extending an ACL system to allow such a thing, 
you quickly see that you need other extensions to the ACL system to accomodate 
this change.  It appears to me that after applying a couple such "obviously
needed" extensions to the ACL system you have something that is isomorphic to a 
capability system.

[footnote2]  Yes, I *know* that [Chander01] says, in English prose, that 
revocation is infeasible in caps.  But it also says, in a formal model, that 
"Removing" access to a resource can be implemented in the cap model in a 
constant number of steps with respect to the total number of principals, but 
removing access to a resource can only be implemented in the ACL model in a 
number of steps proportional to the total number of principals.  I have been 
confused about this for some time, but I now think that the authors believed in 
some of the myths when they began writing the paper, that their formal model 
helped them see through those myths, but that they accidentally left some prose 
myths in place when they published.

Just now when looking at it again, I finally understood an inconsistent 
sentence -- the first sentence of section 6.2.  It reads "The fact that the 
`Remove' action in [our ACL model] has no real counterpart in [our cap model] 
leads to the following results."  This is inconsistent because their ACL model 
doesn't have an action named "Remove", it has one named "Revoke".  I thought 
that this was a typo and they meant "The fact that the `Revoke' action in [our 
ACL model] has no real counterpart in [our cap model]...".  However I now see 
that they actually meant "The fact that the `Remove' action in [our cap model] 
has no real counterpart in [our ACL model]...".  This is a change which reverses 
the sense of the sentence to match the format result that they give: that their 
ACL model is weakly contained in their cap model, but not vice versa, which 
means that their cap model can do everything that their ACL model can do, but 
not vice versa.

I now suspect that the prose text quoted in "Capability Myths Demolished" might 
also be a left-over from an earlier version of their paper.

[footnote3] Hello!  I'm footnote 3 and I'm way down here.  The phrase "unifying 
access and authorization" has often confused me, although I think I've got it 
figured out now by reading "Capability Myths Demolished".  Perhaps a better 
phrase would be "bundling authorization with meaning".

[Shapiro99] Jonathan S. Shapiro, "EROS: A Capability System", Ph.D. thesis, 
University of Pennsylvania, 1999. Online at 
http://www.eros-os.org/papers/shap-thesis.ps.

[Chander01] Ajay Chander, Drew Dean, John Mitchell, "A State Transition Model of 
Trust Management and Access Control", 14th IEEE Computer Security Foundations 
Workshop, Online at citeseer:
http://citeseer.nj.nec.com/chander01statetransition.html