Re: Split Capabilities: Making Capabilities Scale Jonathan S. Shapiro (shap@eros-os.org)
Sat, 1 Jul 2000 07:42:14 -0400

I've held off on responding to this thread, partly because I wanted to let the idea sink in and partly because I'm packing a house at the moment, which has me a bit distracted. These comments span several of the emails that have gone back and forth.

First off: Hi, Alan. I'm very glad that you can now talk about e-speak. It looks like a strong piece of work.

> The problem is the number of capabilities I need to deal with. After all,
> my PC has over 60,000 files on it. In the most general case, I need a
> conventional capability for each operation, e.g., read, write, execute,
for
> each file. Some applications, SAP comes to mind, have hundreds or
thousands
> of methods, each of which I might want to control separately.

There are really two issues hiding in this statement: total capability count and manageability.

I think that the total count is not per-se a problem. To expand on your example, your file system on your PC currently *has* 60,000 capabilities, only they are called inodes or vfat entries. Encrypting these entries does not inherently alter any of the issues arising from the number of them you have. Distribution may, and I haven't thought that issue through.

The manageability argument is more compelling, but if we examine your file system we soon note that the file system itself doesn't treat its objects as a flat space. It has internal organization (directories) and deals with subsets of the larger capability pool. To the extent that directories in the file system grow too large, they become unmanageable by human users. This, however, is not a result of using capabilities. It is a result of having too many things to designate. Whether the designations are capabilities or filename paths, there are two many distinct names for the human to manage. I claim that this issue is fundamental: in any system having a large number of objects that must be designated individually for operational purposes the namespace management problem will arise.

Finally, I think that the "general case of one capability per method" claim is mistaken, though it's a natural mistake given the way that the literature has presented capabilities. Contrary to what the historical presentation has claimed, capabilities do not authorize operations in real systems. I think that the following is a better way to think about what is going on:

Each object has an interface containing all

of the methods that exist on that object. For each object, there are some number 

        of "thinnings" of that interface. For
        example, there may be a thinning for
        operations that can be performed under
        read-only authority.
    Each of these thinnings has a corresponding
        capability.

While shifting to this model doesn't change your claim in abstract, it does shift attention in a way that makes clearer why the abstract claim doesn't matter. Databases may have thousands of methods, but if they *were* individually controlled the database would have too many interfaces to be an engineerable software artifact, and the product would soon die for reasons having nothing to do with capabilities.

That is, either the number of capability variants per object is very small or the system design won't work for other reasons.

> Wildcards are often used to reduce the number of capabilities needed, but
> this approach is dangerous and not general enough. What happens if I put
a
> private file in a directory that has an outstanding wildcard capability
> granting read access to general users?

By wildcard, I assume that you mean wildcard on user identity. This implies a hybrid access control design. I'm not inherently opposed to hybrid systems, except insofar as bastardizing the protection model leads to the kinds of problems you identify (along with a host of others). Wildcards have been used in a few hybrid systems, but not in any capability system, because there is nothing to wildcard *on*.

The most thoroughly developed hybrid of this form is probably Karger's thesis (SCAP). Paul went to a hybrid model because neither he nor Boebert could see how to do multilevel security in an "unmodified" (Karger's term) capability system. It turns out that adding transparent indirection is all you really need, though a "weak" access right definitely helps. See the paper by Weber and Shapiro in the 2000 Symposium on Security and Privacy.

E is a "pure" capability model, and therefore has no wildcarding. So far, it does not appear to need any.

> We could also
> list all the relevant objects in the capability, but I don't think I want
to
> pass around a capability listing the 50,000 files on my system that you
can
> read.

You seem to be assuming that this is frequently necessary. In my experience it is not. These capabilities can almost invariably be stored in some "directory" object, and then a single capability to the directory object can be generated.

As an aside, I'ld argue that it is *rarely* the case that users may wish to share objects in bulk, and *never* the case that correctly designed programs should do so. Up to a point, the fact that capabilities means that they reinforce good design practices.

> The repository has an entry containing a number of fields for each
> registered resource. One of these fields is a list of pairs each
> consisting of a reference to an e-speak capability and the access
> rights granted when that capability is presented.

I think this is an interesting design. It's not appropriate in an operating system because of the number of dynamically allocated access records involved, but it has much to recommend it at the language level. A few questions:

If you pass an e-speak capability to me, and I pass it to Mary, how do you revoke mine without revoking hers? Injecting a wildcard filter can probably handle that, but now what about the case where you want to revoke capabilities that I hold except those held on my behalf by a particular trusted program?

How are access rights protected, given that they do not appear to be cryptographically secured? One of the important qualities of a vat is that if you compromise one vat you cannot compromise the next. I can imagine wire protocols that would achieve similar protections for e-speak, by shipping traditional capabilities over the wire, but all of the methods that I can see for doing so raise hairy consistency challenges in the context of object caching. In particular, one cannot guarantee that permission downgrade occurs promptly in the distributed case.

> In the case of multilevel security, I can cover
> all cases with only one e-speak capability per
> security level, and each user gets only one
> capability.

I think that this illustrates a flaw, and possibly a fatal flaw. If there is one fundamental advantage to true capabilities, it is that they make exactly this sort of aggregation hard. The aggregation you propose violates the principal of least privilege. Worse, it encourages the construction of programs that violate this principal routinely.

The reason this may be fatal is that one cannot assume that the programs are well behaved. Indeed, where security is taken seriously, we must assume that at some point somebody will slip us a trojan horse. In the design you propose, a single trojan horse can destroy everything I have access to *unless* I carefully restrict the capabilities that are handed to the trojan program, at which point we start to move to a design pattern in which I have to go to a lot of extra work to reconstruct traditional capabilities using the split capability mechanism.

> There's still a problem with the approach you describe. Namely, over time
> I'll accumulate a large number of capabilities. Either I'll have to
present
> them all on each request, in which case the permission checking will take
a
> long time, or I'll need a way to track which ones I need for each request.

First, let's be clear that "I" is a program, not a user. It is very easy for programs to track what capability goes to what. When was the last time a production version of a program you ran got its file descriptors confused?

Also, I'ld suggest that as a design pattern you want the program to present specifically the authorizing capability with each operation that it performs. This provides a form of scoping around the exercise of authority, and this scoping appears to be a very useful thing in reducing security-related errors.

> Besides, we can't really use that approach [the directory of capabilities
> approach] in e-speak because of the
> additional latency. The two step process you describe doubles the
latency.
> That's because in e-speak the holder of the strong capability is a
service,
> not an object.

In KeyKOS/EROS it's also a service, though it helps that the systems are not distributed.

Jonathan Shapiro