Capabilities

Part of 22C:112, Operating Systems Notes
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Basic Definition

In the abstract, each user has particular access rights to each resource, so, for example, I have read-only rights to the file /usr/include/stdio.h and read-write rights to the memory segment holding the text editor I am using to edit this web page. The general concept of access rights applies across a huge range of resources. There are two common ways to link rights to users and resources:

At the level of abstraction presented above, any protection relationships that can be expressed using capability lists can also be expressed using access control lists, and visa versa.

Examples from the Real World

Systems like Unix (and Linux) as well as Windows mix the two protection models more or less at random. That is because these systems were developed without a coherent notion of resource protection. This, in turn, explains why modern commercial computer systems have such a mixed record when it cones to security. Both access control lists and capabilities have been grafted onto these systems as an afterthought, but design by afterthought rarely produces beauty. Certain part of typical modern systems tend to follow one or the other model.

Memory Management Units

Memory management units tend to use a capability list model of protection. For each user, there is a page-table listing the page frames available to that user. Each page-table entry typically has access rights associated with it. As a result, one user might have a read-only capability for some page frame, while another user might have a read-write capability for the same frame.

The page table is more than merely capability-based resource protection, because it is also the way the user program actually addresses its resources. This is called capability based addressing. The user never knows the actual physical memory address of any page frame, but only knows that it is the frame accessible using the capability in a particular page table entry.

Unix-like File Systems

The Unix file system stores the access rights for each file in the i-node for that file. Other attributes for files include the owner ID of the file and the group ID of the file. The access rights field in the i-node contains 3 sub fields, one giving the rights the owner has to that file, one giving the rights held by all members of the file's group, and one giving the rights held by everyone else. In effect, each Unix file has a three-entry access control list, with the two final entries containing wild cards of a sort. The rights on the i-node are checked when the user opens the file; once the file is open, different mechanisms come into play.

In fact, the Unix access rights model is a simplified version of the Multics file system. Multics allowed full fledged access control lists to be attached to any file, including a wild-card entry for "others" and entries for groups of users. Late in the history of Unix, general purpose access control lists were grafted onto the Unix file system, but these features are poorly utilized because they are afterthoughts.

The Problem with the Status Quo

Unix and similar systems have a variety of ad-hoc protection mechanisms, one for access to RAM, one for the right to open files, one for access to files that are already open, one for access to shared memory segments, and so on. With a different model for each resource class, nothing generalizes, and as a result, the size of the operating system grows and debugging of problems with access control becomes unlikely.

This has led to work on devising universal protection models. This work started in the 1960s, but became a major research focus in the 1970s. Sadly, market forces largely killed research in this area in the 1980s and 1990s. The market wanted Unix compatability or Windows compatability and strongly discouraged investment into alternative top-level models for system construction.

The systems developed in the 1970s exploring alternative protection models are extremely interesting today, in part because they offer potential paths out of the current network security crisis facing todays operating systems, since it seems, at this point, unlikely that any security add-ons can be used to patch today's commercial systems adequately to face the intense challenge of the modern Internet.

The Demos system is but one example of such systems. IBM's System 38, the Plessy System 250, the Cambridge University CAP system, and many others have explored the potential of capability-based addressing.