[cap-talk] "Capability Myths Demolished" review

Ka-Ping Yee cap-talk@mail.eros-os.org
Fri, 21 Mar 2003 07:16:28 -0600 (CST)

Dear Author,

I regret to inform you that your paper

099 "Capability Myths Demolished"

was not accepted for the 2003 USENIX Security Symposium.

The selection of 21 papers from 125 submissions has been a challenging
and difficult task. The program committee members put in a significant
effort in order to provide useful feedback to the authors.  I've appended
the detailed comments for your paper.

I thank you for your interest in USENIX Security 2003 and hope that you will
be able to attend the conference this coming August in Washington, D.C.


Vern Paxson
Program Chair, 2003 USENIX Security Symposium


099 "Capability Myths Demolished"


Numbering sections would make it easier to comment on them.

"Designation and Authority": This is a pretty minor nitpick with ACLs, sure,
the capability has the permitted access info built into it, but if you need to
know this in an ACL-based system you can just ask for the info (in Unix terms,
"ls -l").  It seems like a non-issue.

"Granularity": Again, a valid point, but it seems to be just another minor
thing in the endless ACL-vs-capability debate.  I could counter this by saying
that having a subject disappear and take their capabilities with them is just
as problematic.

"Intermission": It hasn't really demonstrated this, merely shown that there
are some minor nitpicks with the model.

"Achieving Confinement": The claim from Wallach et al is true though, if it's
possible to arbitrarily communicate capabilities then confinement isn't
achieved.  Confinement requires that the "sharing of object references" is
itself controlled by capabilities, which often isn't possible.  The Wallach et
al text as quoted is correct, if you can't restrict the ability to pass on
capabilities, you can't achieve confinement, and as commonly used (object
handles, passwords, cookies), this restriction isn't present.

"Revocable Access": This is creating/using ACL-like restrictions to handle
problems with capabilities, e.g. Kargers use of cached ACL lookups as
capabilities and the CAP-III work mentioned in the paper, Li Gong's 1989 work
on per-object exception lists (referenced elsewhere in the paper), the use of
subject restriction lists in the BirliX work, etc.  Again, it's a (endlessly)
debatable point whether this still qualifies as a true capability system.

"An Argument against Confinement": Using capabilities to control the ability
to delegate capabilities is no different than using ACLs to control the
ability to delegate ACLs, which is common enough to be present in widely-used
mainstream OSes (Windows NT/Win2K/XP).  It's like the "Achieving confinement"
argument, it's fair enough to use as a theoretical argument but things don't
really work like that in practice.  In addition, this type of thing is fairly
well known and has been analysed in some detail, e.g. in Sandhu's typed access
matrix model.



Your paper provides a very interesting discussion and analysis of differences
between ACL and capability systems and the resulting consequences.

In the section on designation and authority, it might help to introduce
the confused deputy problem earlier.  Otherwise, the statement

  "They must also understand their relationship to the designated
  resource in order to determine what actions they should perform on
  the resource."

seems to be lacking some context.

Regarding the section on Unix file descriptors: Its possible to assume a
model in which no direct filesystem access exists and all file descriptors
are delegated via file descriptor passing.  In that case, Unix file
descriptors match Model 4.  However, Unix sockets are bi-directional.
So, you might have to restrict yourself to pipes, only.



From: Earl Boebert <boebert@mail.swcp.com>
Date: Sat, 1 Mar 2003 09:39:19 -0700

Hi. Thanks (I  guess) for bringing this to my attention.  First, my
response to the paper, which you may feel free to print with

The paper in question was, and remains, no more than an  offhand
remark. It arose from work that Dick Kain of the University of
Minnesota and I were  doing  in support of  a capability-based
architecture from SRI called PSOS.  An early version of that
architecture had the flaw in question (which,  I  learned later, had
been independently and previously  noted by Jerry Salzer.)  Kain and
I had come up with a hardware solution  which the Government sponsor
of the project chose not to release  for publication -- all the while
strongly encouraging us to support the conference.  So I wrote up the
problem statement, omitted the solution, and moved on.

The historical significance of the paper is that it prompted  the
writing of [1], which, curiously, the authors do not  reference.
That paper remains  the definitive description of work up to the date
of its publication, and completely obsoletes my little two-page

  As a footnote, Bill Young  of the University of Texas, Dick  Kain,
and I  decided shortly thereafter that a distributed protection state
was beyond the ability of the verification tools of the time to deal
with, and we dropped the PSOS-inspired capability architecture for a
more direct implementation of the Lampson  Access Matrix.  This
eventually  became  what is  now known  variously as Type Enforcement
or  Domain Type Enforcement.   This evolution is document in [2],
which  also contains a useful bibliography.

[1] Kain, R.Y.  and Landwehr, C.L.,  "On Access Checking in
Capability-Based Systems."  Proc. IEEE  Symp. on Security and
Privacy, 1986.

[2] Boebert, W.E.  and Kain, R.Y., "A Further  Note on the
Confinement Problem."  Proc IEEE International Carnahan Conf. on
Security Technology,  1966


As far as rating the paper goes, I'm afraid I haven't thought about
capability architectures for  nigh onto 20 years :-) and so I'm not
really qualified to judge.  The absence of the Kain and  Landwehr
paper, any mention of PSOS,  or the primary sources such  as the
original  Farber paper would, however, make me  skeptical.

Hope this helps,




The authors seem to have taken great umbrage at the (alleged) misuse of
their darling security mechanism, and have seen fit to stand before the
armies of darkness, wielding a flaming sword, and declaring their defiance.

Chill out!  This paper makes great hay out of a relatively small topic.
Historically, it would seem that a lot of people didn't "get" the idea of
object encapsulation.  It's actually reasonably good to have all of this in
one place, although many of the quotes here seem taken out of context.  The
Wallach et al. quote, for example, was discussing a world where you can't
apriori declare that two applets aren't communicating with each other.  In
that context, what they said was perfectly fine.  I imagine we could dig
further into the other quoted papers and find similar nuanced discussions
that you've seen fit to "demolish."

Much as you seem to enjoy demolishing all these myths, perhaps you'll be
able to better convince people, saying the same things, but in a less harsh
manner.  Do you think the AS/400 bolted ACLs onto their capability system
because they didn't understand the theory behind what they were doing?  Try
reasonably explaining why people have done what they've done, and maybe
you'll have the classic paper people will want to read.



This paper attempts to debunk myths about capability systems.  Unfortunately,
it is written in the tone of a rant, rather than a scientific paper.  It
is also misleading, if not plain wrong, on several key points.

I am shocked to see the "Model is Not Dynamic" section without a citation
to Harrison, Ruzzo, and Ullman's seminal 1976 paper.  Their model is
dynamic; that's where the undecidability comes from.

Property A: "No Designation Without Authority" fails to hold for Unix --
either considering permission bits as limited ACLs, or modern Unixes that
support ACLs.  To wit, permissions are attached to (device #, inode #)
pairs -- not pathnames! These pairs represent ground truth as far as Unix
resources are concerned.  There is no form of open(2) that takes such a
pair and returns a file descriptor.

The authors claim to contradict their first quote from [3], but fail to
explain what is wrong with the (quite formal and rigorous) proof in [3].
It appears that in fact the difference comes from different definitions.
This is fine, but the paper would be much more useful if the authors had
put their system into the framework defined in [3] if they wish to make
direct comparisons.

Quoting from [24], the authors take the quote out of the context of the
paper (namely securing Java), and violate a stated assumption in the quote
itself! To wit, "'two programs which can communicate object references can
share their capabilities without system mediation.' ... However, it appears
to overlook the possibility that such an ability to communicate might be
unavailable or restricted."  What gives here?  Java didn't have the newly
hypothesized restrictions on communication channels, so this is an invalid

The second quote from [3] is missing the qualification given in Section 5
of that paper: "It is also possible to define other capability models in
our framework, although for simplicity we do not do so in this paper."  The
model presented in [3], which the present authors might wish to call
something else, most certainly does have significant issues with revocation.

A well thought out, calm, reasoned discussion about capability systems
could make for an interesting paper.  Unfortunately, this isn't it.



The subject area is an interesting one -- it is not precisely defined, a
point the paper clearly demonstrates. When we say cap and ACL are equivalent,
we are saying they are generally equivalent. If you refine the definition,
you can get differences and contradictions, right? Like a car and a truck
are equivalent as transport tools, but of course if you start to examine
doors and engines then you say they are not equivalent.

Different folks use different terminologies or use the same word to mean
slightly different things. So it does not add much value for the authors
of this paper to try to demolish past work, where each may have a wider
or narrower definition of the cap system being considered. If they want
to propose a new system of defining cap systems with a lot of new attribute,
it would be somewhat new, but then it may not be very relevant.

Overall, there seems to be some value in what the authors are thinking,
but presenting as new work to have crashed three myths seems a bit overblown.
However, it would be good if there is a way for the authors to voice some
of their points, which might stimulate discussion. What one should avoid
is to present what is said in this paper as the new truth. It is not, as
they cannot say they have a precise and object definition of real capability
systems should be.