Acess Control Lists and Capability Lists

Part of 22C:169, Computer Security Notes
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Access Control Lists

The original Multics protection mechanism was based on the idea of adding an access control list or ACL to each file, protecting the right to open that file. An access control list is a list of user, access-access rights pairs. Consider the access matrix:

Alice R/W R R -
Bob R R/W R
Carol R R R/W R
Dave R/W R/W R
aaa bbb ccc ddd

We can express the same access constraints given in the above matrix with the by attaching the following access control lists to the four files shown:

aaa -- Alice:R/W, Bob:R, Carol:R

bbb -- Alice:R, Bob:R/W, Carol:R, Dave:R/W

ccc -- Alice:R, Carol:R/W, Dave:R/W

ddd -- Bob:R, Carol:R, Dave:R

Note, with access control lists, that we only list users who have access to some file, omitting from the list those users who have no access. It should be immediately clear that access control lists have the potential to completely encode every aspect of the access matrix.

Sparse Matrices

In the field of numerical analysis, a matrix where most of the elements are zero is called a sparse matrix. Conventional (non-sparse) matrices can be efficiently stored as two-dimensional arrays, but in computations involving very large numbers of sparse matrices, memory can be used more efficiently by storing each matrix as a list of non-empty rows, where each row is stored as a list of nonzero elements.

It should be immediately clear that the access-control-list idea is really just a sparse-matrix representation for the access matrix. We only store an access control list for objects that someone has access to, and the only entries in the list are entries for current users.

Default Access Rights and Groups

Access control lists, in the basic form described above, are only efficient if the average file is accessible to only a few users, for example, if most files are private. The basic access control list idea was enhanced very early in the development of systems by adding a special entry for the default access rights. Typically, this was put at the very end. If we use the distinguished name Others for this, the above example can be reformulated as:

aaa -- Alice:R/W, Bob:R, Carol:R

bbb -- Bob:R/W, Dave:R/W, Others:R

ccc -- Alice:R, Carol:R/W, Dave:R/W

ddd -- Bob:R, Carol:R, Dave:R

The Others entry is at the end of the list so that a linear search will find individual ownership before it finds an entry that matches everyone. The basic model of the access control list had no such concept of ordering. The list was just a set of pairs.

Once the idea of creating a single "wild card" group was hit upon, it was natural to invent group memberships for users. This can shorten the access control lists, but there are two costs:

It is worth noting that the access rights system of Unix is a degenerate form of the access control list idea. Each Unix file has a 3-entry access control list, where the first entry lists just one user (the owner), while the second entry lists a group (the group), and the third entry is the wildcard (others).

Fully general access control lists have been added in various ways to various versions of Unix. Unfortunately, these have not been entirely compatable, but a standard is emerging. Typically, the shell command getfacl gets the access control list of a file and setfacl sets the access control list. The man page acl gives more details, including pointers to a variety of ACL manipulation routines.

Windows NT and .NET both use access control models that owe a considerable debt to the Multics ACL idea. Some security standards consider ACLs to be the minimum reasonable access rights enforcement mechanism.

Access Control Lists in Directory Systems

Access control lists on directories naturally control the right to add to or edit those directories. Access control lists in the context of directories can do much more. We can easily identify the following rights to a directory:

The final right above allows us to construct an access control list on a directory that prevent some users from accessing files even though those users are specifically given rights in the access control lists for those files. The key is that the user is blocked from reaching the file by a directory on the path to that file that the user cannot traverse. Generalizing on this, we come up with the following rights:

The above rights, although they apply to a directory, control access to files listed in that directory and not to the directory itself. If we build access control list systems that include these rights, then the rights a user has to a particular file depend on the intersecton of the sets of rights granted by the access control list on that file and the rights granted by each directory on the path to that file.

Access Control Lists in Dynamic Systems

Things get even worse if we consider dynamic access rights -- that is, tools to permit modification of the access rights. In systems based on access control lists, it is quite natural to include, in the access control list, the rights to modify that access control list. We could just have a single right, the right to edit the access control list, or we could subdivide this right:

At this point, it should be clear that access control lists are no-longer purely a simple sparse-matrix encoding of the access matrix.

Capability Lists

If we can represent the access matrix using access control lists, one per column of the matrix, we can also do the same thing using rows. Rows of the access matrix correspond to domains, but the dominant terminology used since the early 1970's describes each row of the access matrix as a capability list. Consider the same example acces matrix:

Alice R/W R R -
Bob R R/W R
Carol R R R/W R
Dave R/W R/W R
aaa bbb ccc ddd

The corresponding capabilty list representation of this access matrix is:

Alice -- aaa:R/W, bbb:R, ccc:R

Bob -- aaa:R, bbb:R/W, ddd:R

Carol -- aaa:R, bbb:R, ccc:R/W, ddd:R

Dave -- bbb:R/W, ccc:R/W, ddd:R

Each pair consisting of an object name and the access rights to that object is called an access capability.

In their simplest form, capabilty lists are just a compact form of the access matrix, but just as was the case with access control lists, capability listxs depart from this simple interpretation as they are fully developed. The departure is quite different in form.

Capability lists as Directories

Capability lists resemble directories. You can easily think of Alice's list above, listing the files aaa, bbb and ccc, as her home directory, holding links to the files she may access, where each link is decorated with Alice's access rights for that file.

This leads us to a radically different kind of file system from the tree-structured model common on Unix and Windows systems. In the first place, the access rights a user has to a file are properties of the user's link to that file and not properties of the file itself.

In traversing a path to a file in a capability-list structured file system, all users begin at their home directories and no user has access to the root.

illustration of a C-list system

In the above system, Alice has a private file called "aaa". Only Alice knows this file exists. Bob has a file called "bbb" that is shared with Alice, although Alice calls that very same file "bobfile". Alice has read-only access to that file, while Bob has read-write access.

How did Alice come to share a file with Bob? In this case, there is a shared directory. Bob calls it "share" and has write access, so Bob could have created "bbb" and put a capability for it in the directory. Both Alice and Carol could have taken a copy of the capability from the directory. In this case, Alice did, but Carol did not.

Carol has recently taken a copy of "shared/ccc" and named it "ccc" in her directory. Presumably Bob put this file in "share/ccc", since he is the only one whou could write things to the shared directory.

In a pure capability-based file system, all users would typically have capabilities for the root of the shared file tree containing such things as the standard system executables. We could make things look like Unix if we interpret the file names starting with "/" as having an empty first component "", and asking that each user directory include a link from "" to the root of the shared file system.

The first computer system with a fully developed capability-based file system was the Cambridge Cap system. The Amoeba file system is another good example. Remarkably, the latter was written in such a way that most users could use it without knowing that they were not running under a Unix variant.

Capability Based Addressing

It is fairly easy to see that a page-table entry is a kind of capability. Each page-table entry consists of a frame number, identifying where the page is currently stored, and a set of access rights. As such, a page table can be considered to be a capabilty list.

Similarly, in the Unix table of open files, each entry contains the handle of an open file object and the access rights for that open file -- so that if two users have the same file open, they have the same open file object, but they may have different access rights. As a result, each entry can be thought of as a capability for an open file.

Both the page-table example and the open file example have something in common. The user addresses a page or an open file by number. As a result, instead of searching the capability list for a specific capability, by name, as in the directory example, the user merely indexes into the capability list to a particular entry and then directly uses the capability at that slot without the need to compare textual object names. We call this capability based addressing.

This leads to a retrospective criticism of Unix: Why does the Unix access control mechanism use two different kinds of capability lists plus the primitive access control list scheme for files? This seems overly complex.

In fact, the Multics system had only somewhat reduced complexity. In Multics, open files were included in the memory address space as segments (Multics had a 36 bit word, so segments were fairly large), but the right to open a file was controlled by an access control list. Thus, in a formal sense, Multics used capability-based addressing for memory, which included open files, and access control lists to control the right to open files.

This hybrid scheme makes some sense, but the complexity of systems resulting from this scheme has led many system developers to propose the use of pure capability-based addressing as a foundation on which entire operating systems are built. This has been done in many research systems, such as the Carnegie-Mellon Hydra system and the Cambridge CAP system. It has also been done commercially in the Plessy System 250 (a machine used almost entirely as an embedded control system for telephone exchanges), and in the IBM AS 400 (a machine most programmers think of as an entirely unexciting small business computer).

References

As usual, Wikipedia has some good material:

http://en.wikipedia.org/wiki/Access_Control_List.

http://en.wikipedia.org/wiki/Capability-based_Security"

http://en.wikipedia.org/wiki/Cambridge_CAP_computer

For documentation on the Amoeba system, see:

http://www.cs.vu.nl/pub/papers/amoeba/ieee90.ps.Z

http://www.cs.vu.nl/pub/papers/amoeba/INDEX -- the index to the Amoeba papaers archive, not hot-linked to the papers

-- the Amoeba papers archive http://www.cs.vu.nl/pub/papers/amoeba/

Capability based addressing is discussed in many places, among them:

http://portal.acm.org/citation.cfm?id=361070 -- the classic CACM paper on the subject

http://en.wikipedia.org/wiki/Capability-based_Security"