[cap-talk] Re: "capabilities" as data vs. as descriptors - OS
security discussion, restricted access processes, etc.
jed at nersc.gov
Thu Apr 29 22:24:49 EDT 2004
At 11:25 AM 4/27/2004, Jonathan S. Shapiro wrote:
>On Tue, 2004-04-27 at 13:56, Jed Donnelley wrote:
>> > > "Harrison, Ruzzo and Ullman proved in 1976 that access list systems cannot
>> > > prevent a program from disclosing information to anyone in the system...
>> > > I wonder what is going on. Why is an access list based system any
>> > > different from a capability based system (or a system like Unix or
>> > Windows)
>> > > in that regard?
>> >Briefly: because the rules that govern updates to the access graphs are
>> >not the same, and the rules in ACL systems don't work right.
>> Are we again talking about programs that are given a right (via an ACL)
>> being restricted from making that right available to other processes that
>> they are able to communicate with?
>The reason that the safety problem is decidable in the capability case
>is that the transmission of authority is governed by authority. That is,
>in order for A to send some capability X to B, A must already be in
>possession of a send capability to B. This is the result from the
>Jones, Lipton, Snyder work on capability safety.
>The reason that the safety problem is decidable and unsafe in ACL
>systems is that no such restriction on transmission exists. In an ACL
>system, A can transmit an authority to B **whether or not A holds an
>authorized communication channel to B**.
Good point (regardless of the term "safety"). ACL based systems really
seem to get messy (to me) because of their dependence on the notion
of "subject". When that subject is a human being then I throw up my
hands entirely. However, if a subject is a process then I certainly think
the notion (as I understand it above) of "safety" can be enforced in an
access list based system. Namely, the server of the resource (who
knows who has access) can simply deny any request to add a process
to an access list unless the requesting process is on the access list.
Not so? Am I missing something there?
>> However, perhaps we can agree that it is
>> important to at least have the ability to limit the rights that a program has
>> more tightly that to just give it all the rights that a human user has.
>We can certainly agree on this.
Good. The next step that I think we can probably agree on is that
programs should only have access to the resources they need to
do their work.
Then the only problem becomes how do accomplish the above. While
I'm a capability supporter from the get go (friends/colleagues used
to call me "Mr. Capability" ;-), I don't want to get on the wrong side of
others by emphasizing implementation aspects of things too early.
We have had systems that support seemingly effective restricted
access mechanisms (albeit not mainstream) for many years.
Academics may debate the relative merits of one system vs.
another. However, I haven't yet seen even an effort to develop
a user interface suitable for such systems. Do you feel that is
something that still needs to wait? Wait for what?
>> I believe that the most significant difficulty is not in the underlying
>> mechanisms to restrict access (though I believe the capability
>> mechanism has huge advantages in that regard), but more in the
>Jed: you seem to be talking in conflict with yourself. I agree that the
>interfaces are key, but I think that you have dismissed without
>appearing to consider my comments about supporting programmers.
This seems to me an important point on which I would like to clarify
Firstly, I would like to distinguish a class of programs - namely those
that initialize or otherwise communicate rights to other programs
at the level of process initiation. I believe that today this is, fortunately,
a rather limited set of programs/code. This is the area where I
believe focus should be, at least initially, directed.
For these programs we certainly do need some sorts of tools to allow
them to specify the rights granted to the programs they initialize and
to specify any rights that should be granted to programs that "request"
them. I prefer capability mechanisms for what I believe are good reasons,
but I'm willing to consider any, just to get the ball rolling. I think we
are long past the point where it's worthwhile debating such mechanisms
before working on the interface issues, since we have had MANY (!) systems
with all sorts of such mechanisms and none of them have made any significant
impact on the underlying problem (limiting program rights to principle
of least access).
If somebody wants to try to get started with an access list based system,
more power to them. I believe they will rather quickly find that mechanism
is an awkward one on which to base restricted access, but I'd rather see
that proceed and get started working on the interface issues than to
have yet another round of debate/implementation on more access control
mechanisms without any progress on the interfaces.
This special class of programs shares with all other programs the
desire to not have bugs (make mistakes, etc.). Of course I'm
sympathetic to this desire and wish to support programmers as
much as possible to this end. However, I see it as a distinct
goal. The goal of supporting programming practices to help keep
programmers from making mistakes. I admit there is some overlap
with domain protection. It's often possible to divide a program into
multiple pieces that can run in separate domains and provide an
equivalent functionality. Anything that makes it easier to do such
subdividing and make it efficient and effective I support. However,
I admit to being somewhat cynical about the efforts to help in this
regard. I've seen so many efforts in such a direction come and go
with what seems to me little progress. Still, there has been some
progress which is of course good.
In the area of restricting access rights to application processes
run by users there has been no (absolutely no) progress that I am
aware of essentially in the history of computing (I speak of course
of systems with visible market share). I see this situation as
appalling and hope to encourage/help something to be done about
it. This email thread is one effort in that direction.
>One key reason that getting the interfaces right is hard is that the
>designation of authority does not align with the incentives of the
>stakeholders. To say that in plain English:
> In capability systems, we observe that the *natural* thing for the
> programmer to do usually turns out to be the *right* thing to do.
At some level I agree with this. However, even in capability systems
I'm not aware of mechanisms that make it "natural" for people sitting
at workstations to initialize applications with just the rights they need
to perform the desired task. Are you?
You speak of the programmer. What about the programmer that wrote
the program that initializes such processes? Perhaps you can show
me an example from some capability systems where that (those)
programmers did the "right" thing in initializing such processes.
With such an example we might be able to use it as a model
for such mechanisms in more mainstream systems.
> In other protection systems that I am familiar with, doing the
> *right* thing is almost always the *unnatural* thing. It takes
> extra work.
>So when I talk about the value of descriptors as a means of enforcing
>programmer mindset, I'm talking about something that is exceedingly
>important in practical terms -- and something that empirically doesn't
>happen reliably in "capabilities as data" systems.
You really lost me there. I again see no difference between capabilities
as data and capabilities as descriptors with regard to the naturalness
of doing the "right" thing. From the viewpoint of the programmer they
seem identical to me. At some level the interfaces can be identical.
There may be some additional library support required for the capabilities
as data implementation, but I believe this is more than made up for
in the simplification of the kernel and in the simplification of the
network extension mechanisms - essentially empty in the capabilities
as data model where processors and their virtual instantiation as
processes are treated essentially identically.
>I think that you and I agree on our two main points:
> 1. We want to make it possible and natural for developers to get
> security "right" more often. Least privilege is a good starting
And I am focusing at this time on the mechanism whereby human
users (e.g. sitting at a workstation) start and manage application processes.
The area that I feel:
a. Must be improved/corrected to make any substantive progress in
restricting the rights that application programs have (which will can go
as far as possible in solving the classical Trojan horse problem - as
often seen in the issue of worrying about executable email attachments).
b. Has been almost completely neglected during the history of computing.
I would be very interested to hear of examples that others may know of
mechanisms for doing such restriction that others may know of.
> 2. We probably would agree that for most general-purpose applications,
> memory safe programming languages (Java, C#) are preferable to
> traditional systems languages like C.
Fine, fine. We may disagree on how much value is added by such
mechanisms, but I can accept that they add value.
>Or to say this another way:
> 1. Take steps not to have more authority than you need.
I might say not to grant more authority than is needed, but that
is a minor semantic distinction.
> 2. Take steps that reduce the likelihood that your program will
> get compromised, regardless of how much authority it holds.
Again perhaps this is semantic, but when you say "that your program
will get compromised" it sounds to me like you are protecting it from
external attack. Is that right? Attack from who or what? Do you mean
to protect it from other programs (processes) that it communicates
with? In that sense I am with you.
>The key point on which we disagree is the practical feasibility of doing
>this in any current popular system API.
You seem to be focusing on the programming interface while I am
focusing on the human interface. It's true that I do believe that most
aspects of the programming interface (API) for today's most popular
systems (Windows, Unix) can be made to work (awkwardly I admit)
so as to provide principal of least privilege access control. It's true
that mechanisms must be added/changed at least in the facilities
to initialize and manage processes.
However, I repeat that without a model for human interaction with
a system, even if it was the most lovely capability based API that
you can imagine there would be no substantive gain without providing
some user interface facility that can limit rights given initialized
>Can we provide some approximation to least privilege in a UNIX-like API?
>Yes, I believe that we can. I cannot do it within the constraints of
>POSIX, but I think I can do it within a sufficiently "POSIX like"
>environment that the result would be acceptable to current UNIX
>programmers and would have acceptable real porting costs (note that both
>of these metrics -- which are the only important metrics for developer
>acceptance in the real world -- are inherently subjective).
>But if I have to live within the current POSIX or Windows API, forget
I suggest getting off the API. I believe the API will work itself out.
Whether or not I hope we can agree that some user interfaces is
needed in any case. We have many examples of APIs in the various
capability system extant. What about user interfaces?
>> I believe, therefore, that anybody working on improving the security
>> of a system like Unix by adding mechanisms like access lists or
>> capabilities is deluding themselves if they think they are going to
>> accomplish anything substantive with that work without addressing
>> what I see as the more important interface issues.
>Perhaps, but anybody who isn't looking at introducing a fundamental
>protection mechanisms that can be aligned with the interface designs
>they need to create is equally delusional.
OK, so lets pick up on some user interfaces for systems with fundamental
protection mechanisms that you believe are appropriate.
>...> I find it difficult to imagine how it could be proven that all Access List
>> systems (in fact almost any access list system) are so insecure as to
>> not be able to allow a process with an access right (limited by ACL) to
>> choose to either share the right or not share the right with other
>> processes on the system.... I strongly suspect there is some misunderstanding about
>> assumptions here, but if that's the only way to get past them it might be
>> an amusing exercise.
>Actually, there is no misunderstanding of assumptions. The proof
>basically shows that an ACL system, as typically constructed, can
>violate safety in two steps.
>Could you design a hybrid to solve this problem?
Hybrid in what sense? An ACL system combined with a capability
>Yes. The point is that
>once you see the proof you can stop working on the simple ACL system and
>start working on the hybrid. Further, there is a tool (the method of
>proof) that will very quickly tell you that whether you are wasting your
>time on any given design. That is a useful thing to know in practical
Sounds like it could be useful - another point for picking up that paper.
>> Hmmm. Perhaps we should clarify the above point a bit. The notion of
>> "capabilities as data" still includes quite a variety of potential
>> e.g. as discussed in:
>> All include both information in the server of the resource as well
>> as information from the process requesting access. One extreme
>> is essentially an access list mechanism where the server remembers
>> which processes (this assumes that it can know where requests
>> come from) have the rights to which resources.
>The fatal problem with this is that the responsibility for filtering
>must not live in the server. Placing it in the server supports denial of
When you say "filtering" what are you referring to? Are you referring
to the right to communicate? Namely that no process should even
have the right to send a message to a server without some sort
of authorization (capability)? In that case it would seem we are
back to discussing denial of service. For you it seems important
that such filtering is done close to the process requesting the
communication. That is, if it is going to launch a denial of service
attack then it can't get out on something like the Internet to do so.
Even in a "system" that supports such restricted communication
I believe there is a need to provide essentially open services. How
do you imagine Web services will be provided in such a system?
>In the current internet architecture, there is no other choice by to
>place defense in the server. From this we can conclude that it is
>impossible to guard resource in an internet-connected application given
>the current design of the internet.
>I'm not saying you can ignore the issue. I'm saying that there are
>places in the local case system design where you require greater
>robustness than is feasible under the constraint space of the internet.
>> I believe the network environment is where the security problems relevant
>> to the present and future lie and that any effort to restrict the domain of
>> discourse to what you refer to as the "simpler (local)" case are no more
>> helpful than securing a system by disconnecting it from the network.
>On this point we will continue to disagree. Eventually we need to
>consider the internet case, but one does not successfully solve big
>problems by solving them all at once in their entirety. People have been
>taking your approach for 40 years,
I'm not sure what you mean by 'my approach.' Certainly I have been
involved in the development of at least two capability based systems.
Its true that in both case I worked on extending them into a network
>and they have made negative progress.
>Our approach is a bit slower, but it's letting us figure out which
>problems in the internet have to have to be solved to give us a long
Does your approach include a user interface? Perhaps we can
find some common ground by focusing on that aspect of the systems.
More information about the cap-talk