May 07, 2004

"How is a capability different to an object?"

A discussion on cap-talk on the definition of capabilities seems to have erupted... Here is one capabilty fan's interpretation of what a capability is, and how it relates to objects, in the sense of Java and other OO languages.

-------- Original Message --------
Subject: "How is a capability different to an object?"
Date: 6 May 2004 20:45:04

You asked me that after MarkM's talk at FC'99, and I didn't know.

Nowadays, I would say this:

Think of a graph with circles connected by arrows. (I really like thinking in these terms. If you don't like thinking in terms of graphs, this probably isn't the best explanation for you.)

Now, let any "thing" in the system under consideration, whether that thing be a person, computer, process, chunk of data, computational object, etc. be one of those circles.

Now say that there are only three ways that one circle can get an arrow pointing to another circle:

  1. The first circle creates the second circle (e.g., a process spawns another process, a Java object constructs another Java object, etc.). In this case, the second circle begins life with only a single incoming arrow, coming from the first circle.

  2. There was a third circle who already had an arrow pointing to the first circle and an arrow pointing to the second circle. This third circle gives to the first circle an arrow which points to the second circle. This is the event captured in the famous Granovetter Diagram [1].

  3. A link between two objects comes in from outside of this world. Please ignore this case for now, and revisit it after you understand what capabilities are.

Okay, now suppose you want to do some access control. You're writing a program, or a policy, or something that wants to specify who can touch what. To be concrete, let's say that you want to specify whether Alice can or cannot read a certain file. If you were never going to change your mind, and if you were not going to allow other people to make their own access control decisions while interoperating with yours, then this would be easy -- just write down "Alice, File, Yes", or "Alice, File, No". That is the basis of the Access Control List approach to access control.

The Object Capabilities approach to access control is to draw a graph with a circle labelled "Alice" and an arrow pointing to a circle labelled "File". Or leave the arrow off if you don't want to grant Alice that access.

Okay, now where are we? Well, the three rules (ignoring the 3rd) above tell you how the access control state can evolve over time. The basic ACL approach that we sketched above doesn't include this notion of evolving over time, so assuming that your access control decisions evolve over time, we would have to add it.

[End of General Definition]

Okay, now I wrote this in as general a manner as I could because I know that your interests include things outside of a specific thing like "this one virtual machine running on my computer". However, to make the notion of capabilities concrete, suppose you have a Java Virtual Machine, and the circles are Java objects and the arrows are Java references. Now suppose one of the objects is under the control of Alice and can be used by her to read files. Another object represents a file.

There, now you are using capabilities for access control in that JVM.

I'll stop for now!


[1] "Alice captured in the instant of giving Bob an arrow to Carol." Making this image required high speed photography by professional National Geographic photographers.

Posted by iang at May 7, 2004 07:03 PM | TrackBack

What I read above is that Java objects are capabilities. At least, in the sense that all three rules apply to Java objects - create, transfer, divine intervention.

Yet, there is obviously something in Java that doesn't make them capabilities, else they would be used all the time. In one post in the recent cap-talk thread Mark Miller said that Java's statics were an issue. Is that all it is or is there more?

(This is certainly an interesting line of thought, along the line of David Hopwood's "definition by comparison." I'd still like to identify a single stand alone definition.)

Posted by: Iang at May 9, 2004 06:20 AM

Whoa! Look at my note again, and this time exclude the paragraph that says "For a concrete example, consider a Java VM.".

Now what you are looking at is a *general* definition. Anything which follows those rules and which you use for access control is an object-capability system. Anything which doesn't follow those rules isn't a object-capability system.

Now the question of how is a capability different to a Java object remains unanswered (in this blog entry). There is a Wiki entry about it:

Honestly, I'm not too clear on how important are these differences between Java and Capability-Oriented-Programming. Historically, Electric Communities tried to convince Sun to close the gap back in early Java days, and failed (possibly because closing that gap would imply breaking backwards compatibility with previous versions of Java), and then Electric Communities tried to make Java libraries and idioms that closed the gap, and then Electric Communities made E.

As an aside, I think this pattern of taking libraries and idioms in Language L and then inventing Language L++ that integrates those libraries and idioms is a good way for programming languages to evolve.

Posted by: Zooko at May 9, 2004 09:17 AM

"As an aside, I think this pattern of taking libraries and idioms in Language L and then inventing Language L++ that integrates those libraries and idioms is a good way for programming languages to evolve."

The problem is that capability security in a language is determined at least as much by what the language and its library leave out, as by what they support.

Besides statics (and minor problems due to being able to synchronize on any object), the most important problem with Java is that the native methods in the Java API provide considerable "ambient authority". The language does not need many changes, but commonly used parts of the API would have to be changed in ways that would break almost all non-trivial Java applications.

Posted by: David Hopwood at May 9, 2004 10:15 AM