next up previous
Next: Physical Analogy Up: Protection Previous: Bell LaPadula Model

Capability-Based Systems

The three appraches we have studied above, Unix, Multics, and Bell Lapadula, support access lists. We now study in detail systems that support capability lists (e.g: Hydra, CAP, iMAX for INTEL 432, IBM System 38, Amoeba). These systems, often called capability-based systems

provide a very flexible protection mechanism.

Each process is associated with a list of capabilities called a C-list. Each capability in that list indicates the type of the object (e.g: file, device, directory), a rights field, which is a bit map indicating which of the legal operations on this type of object are applicable, and an object field which is a pointer to the object itself (in Unix, the equivalent of an inode number). Thus the following is an example of a C-list:

l l l
l l l.
{\bf Type}	{\bf Rights}	{\bf Object}
File	R--	Pointer to File3
File	RWX	Pointer to File4
File	RW	Pointer to File5
Directory	--X	Pointer to Directory3

How does the system check that a process can perform an operation on an object? Here are some alternatives:

First, the process, when it performs an operation on an object, indicates both the object and the operation, and the system checks the C-list to see if the operation can take place. The disadvantage of this scheme, as we have seen earlier, is that on each operation on an object the kernel has to search through a possibly long list of capabilities.

Second, the list of capabilities of a process are stored in the process' address space, and thus can be named by the process. Now when a process asks the system to perform an operation on an object, it also presents the capability to the kernel, which can then check if the operation is valid. It does not have to search the C-list for the capability;

A problem with this approach is that,

it can manufacture capabilities and thus perform arbitrary operations on arbitrary objects.

A better approach, used in Hydra, is to use a combination of these two approaches. The C-list of the process is stored in the kernel address space. A process refers to a capability via the index of the capability in the C-list. (Just as a Unix process names a file via an index in the file table). Now, instead of capabilities, descriptors for them are stored in the process' address space. When a process needs to perform an operation on an object, it names the capability for it via the descriptor for the capability. Thus the system does not have to search the C-list. Moreover, a process cannot manufacture capabilities.

Another approach is to keep the C-list in the process' space, but encrypt each capability with a key unknown to the process.

Yet another approach is to define a a hardware that distinguishes between memory words that store capabilities and those that do not. The hardware can then enforce that capabilities are manipulated only in the kernel mode. Two methods are used to distinguish between words that contain capabilities and those that do not. In a tagged memory these two kinds of words are distinguished by a tag bit, while in a partitioned memory, they are distinguished by the segments in which they reside (thus the segment descriptor contains a bit that indicates whether it contains capabilities). The use of either tagged or partitioned memory architectures forces an inconvenient tradeoff. If the addressable unit is large, one can afford a tag bit in each unit. If the byte or the bit is the unit of addressing, it is out of the question to associate a tag bit with each unit. Partitioned memory avoids this kind of storage overhead. However the need to separate capabilities and non-capabilities requires the use of many more small segments than in non-capability systems. As a result, many more units have to be transferred between memory and disk, leading to I/O congestion. The CAP system uses partitioned memory whereas intel 432, IBM system 38 and other capability-based architectures used tagged memory.

User-Defined Types

In the other systems we have seen so far, the type of the protected object was defined by the kernel. As a result an `object-independent' set of access rights could be defined by the kernel, which supported the predefined operations applicable on these predefined types. Capability-based systems go a step further and allow definition of user-defined types, which have user-defined operations applicable on them. Objects of these types were associated with a set of type-independent rights called kernel rights, which are defined by the kernel for all objects (e.g: read, write) and a set of type-dependent rights called auxiliary rights, which control which of the user-defined operations can be invoked on the object. Thus a capability has fields for both these kinds of rights.

Here is an example to clarify the idea of user-defined types: Assume that a user would like to provide a new type that defines a bibliography database in which entries can be examined, modified, deleted, and inserted. Then he could define the database as a user-defined type:

{\bf protected\_type} Bibliography {
    contents: file;
    {\bf procedure} Examine (obj: capability) { ... };
    {\bf procedure} Insert (obj: capability) { ... };
    {\bf procedure} Delete (obj: capability) { ... };
    {\bf procedure} Modify (obj: capability) { ... };
The declaration specifies the name of the type to be protected, the structure of the internal representation of data part of this type, and the operations associated with this type. The operating system uses this declaration to register a new type in its database of user-defined types.

Now a process can ask the operating system to create a new object of this type. In response, the operating system allocates space for the field `contents', which is the internal representation of the object, creates a new capability

l l l
l l l.
{\bf Type}	{\bf Rights}	{\bf Object}
Bibliography	---|EIDM	Pointer to the Internal Repn
and returns the newly created capability to the caller. The process may then use this capability to perform any of the four operations on this object. Note that the capability does not contain the read (R) or (W) rights. As a result, a user of this capability cannot examine or modify directly the internal representation of the data of a protected object, and has to do so indirectly by invoking the type-specific operations.

How is a type named? A type is itself considered a protected object, of the predefined type TYPE, and is named by a capability for it. It is associated with the operation create, which may be invoked to create an instance of the type. This capability is named in the modified type declaration: capToBibliography: protected_type Bibliography ...

is of the form

l l l
l l l.
{\bf Type}	{\bf Rights}	{\bf Object}
TYPE	---Create	Pointer to Defn of Bibliography
and can be used to create a new instance of the type: newBib := create (capToBibliography, arg1, arg2, ...)

If all types are objects, and each object has a type, then what is the type of TYPE? The type TYPETYPE? In that case what is the type of TYPETYPE? TYPETYPETYPE?... We can get rid of this infinite sequence by making TYPE a distinguished object that is an instance of itself. Like other instances of TYPE, TYPE is also a type, and is associated with the operation create which creates instances of TYPE. This operation is invoked implicitly by the declaration: capToBibliography: protected_type Bibliography ...

which gets translated into a call of the form capToBibliography := create (capToTYPE, a1, a2, ...)

where the arguments specify the name of the type, the internal representation, and the operations.

Transferring Capabilities

Suppose a process has created a new instance of the type `Bibliography': capToBib := create (capToBibliography, ..)

and would like to share this object with other processes. How does it do so? The answer depends on the way capabilities are represented:

It can simply pass the value of the variable capToBib to the other process via IPC. This approach would work in a system in which capToBib is an encrypted word, if the key used to encrypt capabilities is common to all processes.

It can make a special kernel call: send_capability (receiver, capToBib)

which sends the capability to to process pid, which receives it via the call: receive_capability (copyOfCap)

In tagged or partioned memory systems, the kernel would use hardware instructions available in kernel mode to create the new capability. If C-Lists are stored in kernel space, then the kernel would create a new index in the process table of `receiver'.

Selective Transfer of Access

It is often useful for a process to give to another process a subset of the access rights it has to an object. For instance a process p that creates a new instance of `Bibliography' via the call: capToBibliography: protected_type Bibliography ...

has the right to examine, insert, modify, and delete bibliography items. It may want to give other processes the right to only examine the items.

How is selective transfer of access achieved? One approach is to provide a kernel call Copy (origCap, newRights) : capability

that returns a copy of origCap that includes only those rights specified by newRights. Another approach is to make each procedure an object that can be executed, and require that a a process performing operation p on object O provide capabilities to both O and p. Thus a process, to invoke the Examine operation on instance O of `Bibliography', would execute the following statement: execute (capToExamine, Examine (capToO))

Hydra uses a combination of these two approaches. A process can execute operation p on object O only if it has a capability c1 that allows execution of p and a capability c2 that allows operation p on O.

Changing Domains of Protection

We saw earlier the need to change the set of access rights available to a process, often called its domain, as the set of objects it needs to access changes. Capability-based systems are particularly well-suited to support this feature. The example of Hydra shows how this may be done.

In Hydra, the domain of a process changes on each procedure call. Capabilities that are to be shared between the caller's domain and the callee's domain are passed as parameters. In addition the callee may have some static capabilities that are available on each invocation. As an example, consider the definition of the following procedure q: procedure q (a1: capability) { var c3: capability = create (...)) ....

Now assume that some process A with capabilities c1 and c2 makes the call: q (c1)

Then after the call, the domain of protection of the process includes the capabilities c1 and c3.

This feature can be used, for example, by a compiler to ensure that only the ReadSource procedure gets the capability to read a source file.


Assume that a process calls procedure: Examine (capToObject: capability)

passing it a capability to the object on which the operation is to be invoked. The procedure Examine, defined with the type declaration of `Bibliography', needs to read the internal representation of the object to perform its duty. Thus it needs the kernel `R' right on the object to do so. However, capToObject does not have this right,

visible from outside. Therefore, the procedure cannot perform the requested operation!

A solution, adopted in Hydra, is to associate each capability parameter of a procedure with a capability template of the following form:

l l l
l l l.
{\bf Type}	{\bf Check-Rights}	{\bf Rights}
Bibliography	---|E	R--|
When the procedure is called, the system checks if a capability argument has the same type as the type of the associated template, and has the rights specified in the check-rights field of the template. If both conditions are met, then the call is successful, and the system assigns to the corresponding capability parameter a new capability that is the same as the capability argument, except that rights are those specified in the template and not the argument. Thus if the capability argument corresponding to the above template was:
l l l
l l l.
{\bf Type}	{\bf Rights}	{\bf Object}
Bibliography	---E	Pointer to Object
then the corresponding parameter is assigned the capability:
l l l
l l l.
{\bf Type}	{\bf Rights}	{\bf Object}
Bibliography	R--	Pointer to Object
Thus the callee may have greater freedom to operate on an object than the caller. In particular, as illustrated by this example, the callee may be able to access the internal representation of an object while the caller cannot.

next up previous
Next: Physical Analogy Up: Protection Previous: Bell LaPadula Model

Prasun Dewan
Mon Nov 4 12:08:34 EST 1996