Conceptually, a capability is like the row of an access control matrix. Each subject has associated with it a set of pairs, with each pair containing an object and a set of rights. The subject associated with this list can access the named object in any of the ways indicated by the named rights. More formally:

Let O be the set of objects, and R the set of rights, of a system. A capability list c is a set of pairs c = { (o, r) : o included in O, r included in R }. Let cap be a function that determines the capability list c associated with a particular subject s. The interpretation of the capability list cap(s) = { (oi, ri) : 1 <= i <= n } is that subject s may access oi using any right in ri.

We abbreviate "capability list" as C-List.

Capabilities encapsulate object identity. When a process presents a capability on behalf of a user, the operating system examines the capability to determine both the object and the access to which the process is entitled. This reflects how capabiliies for memory management work; the location of the object in memory is encapsulated in the capability. Without a capability, the process cannot name the object in a way that will give it the desired access.

The "codewords" of Iliffe are similar to capabilities. "capabilities" are a way to control access to objects in memory or secondary storage. Fabry generalized this idea to implement capability-based addressing.

The architecture of capabilities is more interesting than that of access control lists. The access control list and the process identity are under the control of the operating system. In the absence of flaws, user processes can change them only by invoking the operating system services. However, a process must identify a capability in order to use it, so the process must have some control over the capabilities. If the process can forge a capability and then use it, access controls fail.

Implementation of Capabilities

Three mechanisms are used to protect capabilities: tags, protected memory, and cryptography.

A tagged architecture has a set of bits associated with each hardware word. The tag has two states: set and unset. If the tag is set, an ordinary process can read but not modify the word. If the tag is unset, an ordinary process can read and modify the word. Further, an ordinary process cannot change the state of the tag; the processor must be in a privileged mode to do so.

More common is to use the protection bits associated with paging or segmentation. All capabilities are stored in a page (segment) that the process can read but not alter. This requires no special-purpose hardware other than that used by the memory management scheme. But the process must reference capabilities indirectly, usually through pointers, rather than directly.

A third alternative is to use cryptography. The goal of tags and memory protection is to prevent the capabilities from being altered. This is akin to integrity checking. Cryptographic checksums are another mechanism for checking the integrity of information. Each capability has a cryptographic checksum associated with it, and the checksum is digitally enciphered using a cryptosystem whose key is known to the operating system.

When the process presents a capability to the operating system, the system first recomputes the cryptographic checksum associated with the capability. It then either enciphers the checksum using the cryptographic key and compares it with the one stored in the capability, or deciphers the checksum provided with the capability and compares it with the computed checksum. If they match, the capability is unaltered. If not, the capability is rejected.

Copying and Amplifying Capabilities

The ability to copy capabilities implies the ability to give rights. To prevent processes from indiscriminately giving away rights, a copy flag is associated with capabilities. A process cannot copy a capability to another process unless the copy flag is set. If the process does copy the capability, the copy flag may be turned off (at the discretion of either the process or the kernel).

Amplification is the increasing of privileges. The idea of modular programming, and especially of abstract data types, requires that the rights a process has over an object be amplified.

To understand why, consider the following abstract data type for a counter.

module counter;
 procedure entry increment(var ctr: integer);
 begin
 ctr := ctr + 1;
 end;
 function entry getval(ctr: integer);
 begin
 getval := ctr;
 end;
 procedure entry clear(var ctr: integer);
 begin
 ctr := 0;
 end;
 end.

Suppose x is declared to be a counter. The rules of abstract data types allow that object to be accessed only by the counter module. So, initially the capability for x would contain the right to invoke the counter module only. But when the object is passed to the counter module, the process must now be able to read and write to that object. Hence, the capability must be amplified temporarily while the module counter is active.

Revocation of Rights

In a capability system, revoking access to an object requires that all the capabilities granting access to that object be revoked. Conceptually, each process could be checked, and the capabilities deleted. The cost of such an operation would be unacceptable, however, so alternative methods are used.

The simplest mechanism is indirection. Define one or more global object tables. In this scheme, each object has a corresponding entry in a table. Capabilities do not name the object directly; they name the entry in the table corresponding to the object.

This scheme has several advantages. First, to revoke capabilities, the entry in the global object table is invalidated. Then any references will obtain an invalid table entry and will be rejected. Second, if only some of the capabilities are to be revoked, the object can have multiple entries, each corresponding to a different set of rights or a different group of users.

An alternative revocation mechanism uses abstract data type managers. Included with each abstract data type is a revocation procedure. When access is to be revoked, the type manager simpy disallows further accesses by the subject whose rights are being revoked. This does not affect alternative methods of accessing the objects underlying the abstract data types. For example, access to a file may be revoked, but this technique would not block access to the underlying segments through an alternative type manager. The SCP3 system used this technique.

Comparison with Access Control Lists

Two questions underlie the use of access controls:

In theory, either access control lists or capabilities can answer these questions. For the first question, capabilities are the simplest; just list the elements of the subject's associated C-List. For the second question, ACLs are the simplest; just list the elements of the object's access control list. In an ACL-based system, answering the first question requires all objects to be scanned. The system extracts all ACL entries associated with the subject in question. In a capability-based system, answering the second question requires all subjects to be scanned. The system extracts all capabilities associated with the object in question.

Karger and Herbert speculate that the practical difference in answering the second question is the reason more systems use access control lists than capabilities. This question is asked more often than the first. As the focus of incident response shifts from "who accessed the object" to include "what else did that subject access," capability-based systems may become more common.