Subject: Re: [e-lang] Modelling Blindness

From: "Jonathan S. Shapiro" <shap@eros-os.org> · Date: Thu, 12 Dec 2002 13:32:37 -0500

On Thu, 2002-12-12 at 07:41, Tyler Close wrote:
> > On Wed, 2002-12-11 at 15:55, Tyler Close wrote:
> > > Can you suggest a textbook that defines this modeling jargon?
> 
> This would still be useful.

I agree, but I am unaware of a suitable textbook. This stuff is a bit
afield for me, and most of it isn't taught from textbooks in any case. 
David Wagner might have an idea. David? daw

> > It was flawed, and in consequence some of the people here have
> > spent a considerable amount of energy crapping on Butler.

Tyler: I wasn't thinking of you when I wrote that, and I'm sorry you
took it as personally directed.  Because of the character of the public
discussion it has become difficult for me to separate the public
comments being made from various private comments that have been made.
Even on the list itself, there has been discussion of how much damage
and widespread misunderstanding the protection paper has caused in the
security community. This alleged damage and widespread misunderstanding
appears to me largely unsubstantiated and contrafactual. To the extent
that it it true, it is true in about the same way that the Koran caused
the events of 9/11 -- i.e. not at all. It is largely the subsequent
interpretations and expansions on the work that are the source of the
problem.

Let us begin by putting this paper in context. 

The Protection paper was written in 1971. Butler was 28 years old.  He
had just arrived at Xerox Parc and was in the process of inventing a new
laboratory after 5 VERY tough years at Berkeley. Butler was promoted to
associate professor early after only 4 years. It is difficult to
describe how hard he had been working from 1967 to 1970, and I would
guess that some degree of burnout contributed to his willingness to
leave Berkeley for Parc. In the middle of all of this, he threw together
a workshop paper. Knowing something about workshops, and comparing this
paper to the quality of Butler's other writings, I venture to guess that
the paper was thrown together in 2-3 days based on ideas that had been
kicking around in Butler's head (and indeed elsewhere in the community). markm

It is in the nature of workshop papers that their purpose is to float
incompletely baked ideas.  It is to be expected that some or all of these
papers are flawed in some measure.

Being a widely known early capture of some ideas,  this paper came to be
cited as the basis for a bunch of ideas that were "in the ether" in the
community.

In short,  when you take this paper in context it shouldn't be *expected*
to live up to the hermeneutic analysis that various people here are
applying. Proceed instead from the assumption that the writing was
hastily done for the purpose of circulating or litmus testing an idea
and you have more of the flavor of the thing.

In light of this,  watching 10 or 15 people on this list deconstruct the
paper sentence by sentence feels to me a bit like watching a gang
mugging a child. It has become distasteful to me (though not through any
fault of Tyler's).

The paper itself discusses protection and access control.  It discusses
*most* (not all) existing systems, and by "the properties of most
existing systems" I have always taken Butler to mean "the properties of
most existing systems then widely used". I do not see this paper
attempting to be universal at all, though the writing is sloppy (which
one should expect in a workshop paper). However, this is my *reading* of
the paper; other interpretations are possible.

Beginning on Page 4 the paper shifts focus. Once again the writing is a
bit weak and could have emphasized the shift better.  Just after the
heading "Objects and access matrices" begins a paragraph that reads:

  In order to provide facilities for controlling
  programs **from the outside**. 

In shifting to this discussion the paper begins to focus on access
models.  In the context of protection **from the outside** the issue of
designation is not only moot -- it would be inappropriate to include it.
Norm articulated this very well in

http://www.eros-os.org/pipermail/e-lang/2002-December/007967.html 

The single weakest point in the paper is the presentation of access
model rules beginning on page 5.  In this section Butler simply fumbled
the writing in a way that is consistent with hastily written workshop
papers. He is clearly describing a *particular* access model that is of
interest to him, but this is not really made clear. When I first read
the paper years ago, I took it that he was describing the particular
rights transfer model enforced by "most existing systems". That is, I
took this specific example to be set forward for the purpose of
understanding and illustrating the *weakness* of existing protection
models.

The discussion on page 7 of implementation techniques is talking about
ways of storing the table.  The text describes the *representation* of
capabilities accurately. Further, it refers to a "table" of capabilities
which can clearly be seen as a C-list. The use of the term "set" in the
last line of page 7 is simply sloppy writing -- it occurs in context of
three preceding paragraphs where an array-based (i.e. designated)
implementation is clearly assumed.

> > The basic Lampson access matrix based formalism *does* support
> > confinement, though other parts of the paper were unfortunately stated
> > in ways that you and Alan Karp have already enumerated.
> 
> The main Lampson model, presented in the "Protection" paper,
> explicitly *does not* support confinement. See rules b and c.

What I meant to say is that the access matrix is a perfectly fine way to
talk about the state graph and its evolution.  The particular operations
described on page 6 clearly cannot enforce confinement or much of
anything else.

> In the text, Lampson suggests a possible technique for preventing
> "de jure" transfer of authority. The technique adds an 'augment'
> authority to the model.

The "do not copy" bit was a mistake that Norm has adequately addressed
elsewhere. 

> Nowhere does Lampson address "de facto" transfer of authority. The
> use of a "copy flag" in the model suggests that Lampson had not
> even considered the issue.

It is true that the paper does not address de facto transfer.  This issue
would not be considered in the literature until 8 years later:

@INPROCEEDINGS{Bishop:transfer,
author="Matt Bishop", 
title="The Transfer of Information and Authority in a Protection
                  System",
booktitle="Proc. 7th ACM Symposium on Operating Systems Principles",
journal="Operating Systems Review",
month=dec,
year=1979,
pages="45--54",
note="Published as \emph{Operating System Review}, Vol 13, No 4",
}

Lampson's paper was written in a context where read-only memory
protections weren't yet generally available (see bottom p.7).  Covert
channels were way beyond the focal problems of the time.

> I see nothing in the paper to suggest
> that the access matrix model claims to be able to prevent
> communication between a conspiring domain and object. If you wish
> to refute this, please quote from the paper.

The access matrix model is simply a way of writing down a graph that
captures the instantaneous access rights of a system.  In and of itself
it does not address the question you raise. It is possible to reason
about the evolution of such a graph by describing a specific set of
transformations on this table and considering their implications, much
as Butler does in the paper.

The access matrix model neither prevents nor permits conspiracy.  It is
merely a tool for expressing and reasoning about the information flow
consequences of the operational semantics of a particular system.

There is no one set of "operations" that are part of the access matrix
model.  Rather, the access matrix model says "if you think about the
graph this way and write down the particular rules of your system you
can reason about them and maybe learn something."

> > I caution, however, that you seem to still be insisting on conflating
> > some things and that this is getting in your way.
> 
> One of the purposes of this email thread is to find any holes or
> inadequacies in the argument I have presented. I am not aware of
> any that you have presented evidence for. Perhaps I have missed
> them. Please be very explicit in pointing out mistakes. Quote me,
> state your argument and back it up.

I don't have time to do extended hermeneutics on the last month of
exchanges.  I was reacting to your apparent complaint that the access
matrix model was somehow flawed because it did not address the issue of
confused deputies. For reasons that have now been amply discussed
(though I will expand on one point below) it is not appropriate that
this model should do so. The inability of this model to deal with
designation is not a flaw in the model. Rather, the problem you are
trying to explore is outside the scope of the problems for which the
model was designed.

> Lampson is the one aiming for a universal verification model. This
> is our main issue with his paper.

I don't read it that way,  and the opening of the section on page 5 makes
it clear that Lampson didn't intend to overreach in the way you
describe.

> Lampson tries to prove that
> there are nothing but implementation issues separating the
> capability model from the ACL model. The main point of my argument
> has been to show that Lampson was wrong about the generality of
> his model.

Lampson attempts to prove no such thing. Kindly point me to the place in
the text where any such "proof" is introduced.  The discussion on page 7
is a discussion about representation, not a discussion about protection
systems or their relative merits.

Indeed, there is nothing at all in the paper that could be remotely
characterized as a "proof". 

> > Showing that the deputy isn't confused is basically a value/control flow
> > analysis at the source code level.
> 
> I am not sure what you are saying here.
> 
> I would think that showing that the deputy isn't confused would be
> very simple. If designation and authorization are inseparable,
> then it is simply not possible for the deputy to be confused. Once
> you have defined what it means to be "confused", it is simple to
> show that a capability system does not allow "confusion". A
> possible definition for "confusion" is:
> 
> "A deputy is said to be 'confused' if processing of a request
> makes use of authority that the deputy did not intend to apply to
> the request."

That seems like a good informal definition. Formalizing it is quite
hard. The difficulty is that you need to define "intends".  You then need
to identify the initial name to which the incoming authority was bound
and perform an analysis tracing through the control flow and the value
flow showing all of the places where it ended up and demonstrating that
none of these are involved in an "unintended" invocation. This is beyond
the state of the art for programs of any large size, and generally has
to be done conservatively because of pointer dispatch and weak type
systems -- even in safe languages.

> In a capability system, it is only possible to form a request by
> selecting the permissions that the request should use. It is not
> possible to form a request without exactly specifying the
> permissions to be applied.  This eliminates the possibility of
> confusion.

That is greatly overstated. Designation provides the *possibility* of
non-confusion. Confusion results from misuse.  The ability to designate
does not preclude misuse. The inability to designate does not guarantee
misuse, though it renders misuse likely and verification of correct use
impossible. frantz

> Confusion is only a consequence of the fact that an ACL model
> manipulates permissions in aggregate rather than individually.

It's not clear here what you mean by "the ACL model".  I'm not aware of
any paper that has been written that purports to define this model,
unless it is the Harrison Ruzzo and Ullman paper:

@ARTICLE{Harrison:Protection,
author="Michael A. Harrison and Walter L.  Ruzzo and Jeffrey
                  D. Ullman",
title="Protection in Operating Systems",
journal="Communications of the ACM",
volume=19,
number=8,
pages="461--471",
month=aug,
year=1976}

The ACL *model* doesn't say anything at all about the interface through
which invocation is performed or the presence or absence of designation. 
The ACL *model* doesn't consider the actions of programs at all.

The point you are trying to make about the importance of designation is
important and sound,  but it hasn't got anything to do with the access
matrix or access models. Access models are built from an *external*
perspective. They deliberately seek to maximize the degree of mis-action
that a program might perform because the goal is to show that *hostile*
programs are contained. Designation occurs in the program source code.
Access models are designed to reason over the actions of all possible
programs. They therefore do not (and must not) consider the source code
of particular programs and therefore do not (and must not) consider the
impact of designation.

From a protection perspective,  designation becomes important only when a
specific program's behavior is critical to the enforcement of some
security policy. At that point we need to crack open the program and
analyze what it actually does. At that point designation becomes
critical.

> > I think much the same confusion is happening in the discussion here
> > about the Lampson paper. The Lampson model was not attempting to address
> > many of the issues that this group finds important.
> 
> The problem is that Lampson never restricts the applicability of
> his model...

I think there are multiple readings here, and that you are reading too
strictly.  You may not agree with me, but do you now understand why I am
not taking the strict reading you are taking?

Basically, I think you are reading far too much into the unintended
consequences of hasty writing. 

> I find it very ironic that, in "Protection", Lampson explicitly
> talks about the exact scenario that Norm used to demonstrate the
> Confused Deputy problem. See the second example b in the
> Introduction section. This should make it abundantly clear that
> Lampson thought he was addressing the issues that we find
> important.

Read the preceding paragraph again. Lampson is not taking a position.  He
is describing the lines of thought that were then prevalent in the
community in order to set his work in context. He is using these
examples as motivation for the need for protection models. He makes no
claim to resolve these problems. It would be another two years before
his "Note on the Confinement Problem" would even begin to try to make
the notion of service programs more precise.

> > This stuff is **bloody hard**.
> 
> Then there should be no shame when mistakes are pointed out.

That depends on how one points them out. Analysis and discussion is
appropriate. Anal-retentive hermeneutics crosses a line at some point. 
This is not divine writ we are discussing. No rational reader should
expect even a carefully reviewed journal paper to be perfect. The
standard being applied here is unreasonable for such a paper, and even
more so when applied to a workshop paper. In doing so, I believe it has
crossed the line of impropriety. To be clear, I am not pointing the
finger at Tyler. All of us have participated, and I think that we have
lost sight of the goal.

I want to suggest that we return the discussion to Tyler's original
objective.  Instead of figuring out what Butler said or didn't say or
meant to say, let us figure out what confusions have emerged from the
paper and then attempt to address those in an appropriate publication
(i.e. Oakland or JCS, not DocSEC).

shap 

_______________________________________________
e-lang mailing list
e-lang@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/e-lang