[cap-talk] "ACLs don't" paper rejected from Oakland 09

[David Wagner]

Tyler Close  wrote:
> If it is true that it is hard to publish a paper that only evaluates
> existing mechanisms, rather than proposing new mechanisms, that would
> go a long way towards explaining why poor mechanisms survive and
> thrive for so long in this field once they take hold.

Interesting.  I'd never thought about it this way before, but I
suspect there may be a good bit of truth to that.

There are some cases where critiques get published.  If you manage to
break the security of a published scheme, it is often possible to publish
the break.  (There are some restrictions: if you send the break to the
same conference where the original paper appeared, within a reasonable
time period after it appeared, most conferences will more or less feel
an obligation to publish the break.  But if you send it anywhere else,
if the ideas found in the attack are not of independent interest, the
break paper might get rejected with a note to send it to the original
conference that was foolish enough to publish the broken scheme.)

If you find a show-stopping problem in an important scheme, in some
cases you may be able to publish that, especially if your analysis has
substantial technical depth, your analysis techniques are of independent
interest, or the scheme is of extraordinary importance.

What if you don't have a break and you don't have a show-stopper, but
you discovered some limitations that were not noticed or mentioned in
the original paper?  Maybe the authors mentioned some advantages and
disadvantages of their scheme, and you found another disadvantage or
pitfall they missed.  Now what?  Usually that just isn't enough to get a
publication out of your observation.  (What are you going to do, write a
2-page paper saying "the authors missed this downside of their scheme"?
Program committees are likely to say, that's not a substantial enough
contribution to merit contribution in a top conference.)

Sometimes such limitations/criticisms do get published, as part
of a larger paper that proposes a better scheme.  In other words,
sometimes what happens is an author notices a non-obvious shortcoming
of a previously published scheme, then comes up with a new scheme that
fixes this shortcoming, and writes a paper that both describes the
limitation of the prior scheme and the new scheme.  That's often enough
to get published, and that's easier for program committees to evaluate,
because they can evaluate whether this is enough of a step forward
over prior work, and whether the paper accomplishes what it sets out
to.

But I suspect that many times when such limitations are found, they're
never published.  They may get handed down by word of mouth among
researchers in the narrow specialty.

I remember several times when Berkeley grad students read a recently
published paper in a reading group, and came to me annoyed because
they discovered that the paper's scheme has some problems not described
in the paper.  They wanted to know what to do: who could they tell to
make sure the record gets corrected?  The answer is, often, nothing.
They didn't like that answer much, and I don't blame them, but that's
how it works.

Anyway, let's face it.  90% of everything is crap.  That applies to
research papers, too.  90% of published papers are flawed, or turn out
to be unimportant, or solve the wrong problem, or have shortcomings
that later get addressed by others, or are obsoleted by subsequent
advances in the field.  Of course it's hard to know that at the time,
but in retrospect, it's probably true.

> Once a mechanism
> has been published, it is effectively beyond reproach.

Well, I wouldn't go that far.

Just because something is published in the literature doesn't mean
it's right, let alone beyond reproach.  Crappy schemes are published
in the literature all the time -- and experienced researchers know it.
So I'd expect that knowlegeable folks should know that just because a
mechanism is published doesn't necessarily mean it's any good.

Basically, conferences publish what researchers think is interesting.
If you found a serious and subtle flaw in a very important and recent
scheme, and the flaw has important implications for the field, folks
are likely to think that's interesting and publishable.  But we could
go pick through the literature of three decades ago and find dozens
of examples of sloppy reasoning, stuff that in retrospect is wrong or
poorly justified, and so on.  That doesn't mean top conferences are
going to publish corrections to some paper from three decades ago.

> It certainly seems like this is the case with ACLs. For example, ACLs
> arrived along with the claim that the access matrix was the "one true
> model of access control", meaning ACLs and capabilities were
> semantically equivalent.

Does anyone really care about this claim any more?  I'm skeptical.
I have a theory that if you pick a random security person who is not a
capabilities guy and ask them whether they care about this equivalence
claim, their most likely response will basically be a shrug.  So it feels
a bit weird: like capabilities folks are picking on this claim that no one
(apart from the capabilities folks) really care much about anymore anyway.

I've heard the argument that the reason why capabilities aren't used
more widely is a widespread belief that they're equivalent to ACLs.
I guess I don't buy that argument.

I suspect that the reasons why capability systems aren't used more
widely are more fundamental.  Let's say I go to some random system
builder and try to convince them to use capabilities, telling them
that this will make their final system more secure.  I suspect the
average system builder is likely to hammer me with with a bunch of
questions:
 How do you know it will make the system more secure?
 Can you quantify how much more secure it will be?
 How do you measure that?
 And, what's the cost?
 How much does this increase system development costs?
 What's the evidence for that?
 How much does it reduce flexibility or affect functionality?
 How do you know?
 What, you say this means that I have to rewrite my existing
 legacy code and start over from scratch?  Yeah, right, good
 luck, brother!
 And I have to learn a new paradigm that's different from what
 I'm used to?  Youch!
I'm exaggerating a bit, but personally I suspect that these are the
more typical barriers to broader deployment, not an equivalence claim.
Coming up with persuasive answers to these questions is really hard.

In particular, the requirement to rewrite existing code to use a
capabilities approach is a really hard one.  If you have to rewrite
everything in the capability style, you can run into the "boil the ocean"
problem.  I fear that capabilities may have a little bit of a reputation
of that.  In other words, the response might be "the approach you are
advocating might plausibly be nice if I could start over from scratch,
but that's not the situation I'm in right now".

To add to this, I'll draw an analogy to software engineering.
One oft-heard criticism of the field of software engineering is that
it is rife with "fads": new ideas for how to develop software that are
supposed to reduce the cost or increase the reliability of your software.
These ideas often sound great, and may come with lots of evangelizing, but
often there is not a lot of hard evidence for the claims.  The reason for
this shortage of hard evidence is that it's very hard to do a controlled
study, say, where you build a ten-million-dollar system two different
ways, one using some older methodology and one using a newer methodology.

I think capabilities advocates may face similar challenges.  It's
challenging to put together persuasive evidence that adopting the
capability mindset will increase the security of your system, without
impacting cost of development (or other considerations) too much.
We're making good progress -- we have a bunch of exciting demonstration
projects that demonstrate the concept, and we're building up a set of
case studies -- but it's still a tough one.

> Now, I would have thought that in order to
> make a claim that two algorithms are equivalent, you'd have to provide
> some proof that their outputs are also always equivalent. No such
> proof was ever attempted or demanded for the access matrix claim. As
> I've shown in "ACLs don't", the outputs are not equivalent and so the
> equivalence claim is ridiculous (AFAIK, no other paper has ever put
> these two things together). And I really mean 'ridiculous'. If one of
> the claims about a mechanism is so blatantly erroneous, and yet
> survives for so long, it is a strong indication that the mechanism
> itself, and its other claims, have never been subjected to serious
> evaluation.

I guess I don't buy this argument, in this strong form.  Are you
assuming that the average researcher who picks up a 30-year old paper
will take for granted every claim made in that paper, unless there
is some subsequent publication that convincingly disproves the claim?
That's not how it works.  Pick a random security paper from 30 years ago,
and I suspect you'll find all sorts of bogus stuff.  Nobody takes those
papers as the word of god -- at least I hope they don't!

I suspect the reason why many current systems are built using ACLs is
not because of a failure to publish a disproof of the equivalence claim.
I suspect that the reason why many new systems rolled out today use ACLs
is inertia: systems builders are familiar with the ACLs approach and feel
comfortable with it; legacy systems they need to integrate with use ACLs;
and users have become accustomed to ACL systems.  All of these factors
make it difficult to swim against the stream.

(Lawyers have a fancy name for this: "path-dependence".)

Change is hard.  It can be frustrating.