IntroductionEdit
Capabilities achieve their objective of improving system security by being used in place of forgeable references. A forgeable reference [for example, a path name] identifies an object, but does not specify which access rights are appropriate for that object and the user program which holds that reference. Consequently, any attempt to access the referenced object must be validated by the operating system, based on the ambient authority of the requesting program, typically via the use of an access control list [ACL]. Instead, in a system with capabilities, the mere fact that a user program possesses that capability entitles it to use the referenced object in accordance with the rights that are specified by that capability. In theory, a system with capabilities removes the need for any access control list or similar mechanism by giving all entities all and only the capabilities they will actually need.
A capability is typically implemented as a privileged data structure that consists of a section that specifies access rights, and a section that uniquely identifies the object to be accessed. The user does not access the data structure or object directly, but instead via a handle. In practice, it is used much like a file descriptor in a traditional operating system [a traditional handle], but to access every object on the system. Capabilities are typically stored by the operating system in a list, with some mechanism in place to prevent the program from directly modifying the contents of the capability [so as to forge access rights or change the object it points to]. Some systems have also been based on capability-based addressing [hardware support for capabilities], such as Plessey System 250.
Programs possessing capabilities can perform functions on them, such as passing them on to other programs, converting them to a less-privileged version, or deleting them. The operating system must ensure that only specific operations can occur to the capabilities in the system, in order to maintain the integrity of the security policy.
A capability is defined to be a protected object reference which, by virtue of its possession by a user process, grants that process the capability [hence the name] to interact with an object in certain ways. Those ways might include reading data associated with an object, modifying the object, executing the data in the object as a process, and other conceivable access rights. The capability logically consists of a reference that uniquely identifies a particular object and a set of one or more of these rights.
Suppose that, in a user process's memory space, there exists the following string:
/etc/passwdAlthough this identifies a unique object on the system, it does not specify access rights and hence is not a capability. Suppose there is instead the following pair of values:
/etc/passwd O_RDWRThis pair identifies an object along with a set of access rights. The pair, however, is still not a capability because the user process's possession of these values says nothing about whether that access would actually be legitimate.
Now suppose that the user program successfully executes the following statement:
int fd = open["/etc/passwd", O_RDWR];
The variable fd now contains the index of a file descriptor in the process's file descriptor table. This file descriptor is a capability. Its existence in the process's file descriptor table is sufficient to show that the process does indeed have legitimate access to the object. A key feature of this arrangement is that the file descriptor table is in kernel memory and cannot be directly manipulated by the user program.
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 aaabbbcccddd
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:
- First, it means that the algorithm for searching for a particular user's access rights to a particular file is no longer simple. Instead of searching for that user in the ACL, we must search for that user and all groups that user is a member of.
Second, it means that multiple ACL entries may refer to a particular user. A user might match the ACL under his or her own personal identity as well as under any of several groups that user belongs to. Do we give the user the union of all access rights from the different matches? Do we give the user the intersection of the access rights? Do we search from the start of the list and give the user the first rights that match?
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 Matrix and Capability List
BlogThere is often confusion about the relationship between access control matrix and capability list or access control list when in fact these can be captured in a single image for clarity and simplicity purposes. You can think of access control matrix as a security access table which combines ACL and user capability list to define who can access what and to which degree. In the ACM, columns define objects and assigned privileges or ACL, rows list users or subjects, and relationships between rows and columns define user capabilities or UCL.