From a theoretical point of view, we can talk about any kind of object being used by or protected from and any kind of user. In this context, it is worth asking if users are themselves a kind of object, but what matters is that users act on objects using operations, where the type of each object may determine the set of applicable operations. All of this terminology applies whether or not any kind of object-oriented language is in use!
Here, we are not concerned with the nature of objects, other than the fact that objects may be operated on by users using operations selected from a finite set. Files fit this model, with the operations read and write. Directories fit this model, with the operations make-directory-entry and delete-directory-entry. Memory pages or segments also fit this model, with the operations load and store.
We are also not concerned with the nature of users. From the the point of view of the theory, users may be humans, programs, processes or anything else that may envoke operations on objects.
For example purposes, it is useful to think of files as the objects and humans as the users, but it is equally useful to think of pages or segments as the objects and processes as the users.
The access matrix model is a universal model of the instantaneous state of a protected system. It shows, at one instant, all users, all objects, and the set of operations each user is allowed to apply to each object in the system. Pictorially, access matrices are generally presented as follows:
| Cake | Tea | Objects
------+------+-------|
Fred | Eat | Drink |
------+------+-------|
Lucy | Bake | Drink |
| | Brew |
--------------------- Allowed
Users Operations
The above example illustrates the (pathetically steriotypical) interaction of
two users, Fred and Lucy, centered around two objects, Cake and Tea.
The operations Eat and Bake apply to cake; Fred can Eat Cake, but not
Bake it, and Lucy can Bake Cake, but not Eat it (perhaps she is on a diet?).
The operations Drink and Brew apply to Tea. From the point of view of the
access matrix, neither the names of users, the names of objects,
nor the names of operations
have any meaning other than the explicit relations between users, objects
and operations detailed in the matrix.
Access matrices may be used to control access to any resource, by any kind of user. Their use is not limited to computers; for example, explicit access matrices using almost exactly the notation used here have been used in the Russian Gulag to control the access of prisoner/laborers to rooms in a prison/factory. (a student of mine from Russia found a piece of paper with such an access matrix on it when he was working in a building that had been used as a Gulag prison not long before his job took him there.)
The access matrix describes allowed actions, but it does not describe an enforcement mechanism. In the case of the Russian prison, the rules of the matrix were enforced by guards with guns.
On a computer, one could store the access matrix inside the operating system, and have the system check the matrix whenever a user tried to access a resource. The problem with this is that the matrix is usually quite sparse -- that is, on most systems, most matrix entries will say "no access".
In linear algebra, particularly in numerical linear algebra, the efficient computational treatment of very large sparse matrices (where most elements were zero) is an old and important problem. As a result, numerical analysts have had, since the early 1960's, a large 'toolkit' of methods for dealing with sparse matrices. Some of very early use of linked-lists in computer programming was done in this domain.
It is also important to note that the access matrix is a static description of who can do what operations on which resources. The model must be extended to describe how access rights are changed, and these extensions frequently differ markedly depending on how the access matrix is implemented.
The scope rules of today's object oriented languages are provide considerable access control, but with few exceptions, the control is provided on an all or nothing basis. Each object is either visible in some context or not, and if visible, all operations on the object are allowed. The class hierarchy can be used, clumsily, and only in some languages, to restrict the set of allowed operations on an object by hiding the object's actual class and forcing a user to use the object as if it was a member of an ancestral class with a more restricted operator set.
There are two practical ways to implement the access matrix, access control lists and capabilty lists. Each of these allows efficient storage of the information in the access matrix.
The access control list implementation of the access matrix given above is:
Access Control Lists
-------- --------
Objects | Cake | | Tea |
-------- --------
| |
-------- --------
Access | Fred | | Fred |
Control | Eat | | Drink |
Lists |--------| |--------|
| Lucy | | Lucy |
| Bake | | Drink |
-------- | Brew |
--------
An access control list or ACL is what results when the access
matrix is stored column-wise. An access control list is a column
of the matrix is stored with a protected object. Each entry in
an access control list specifies a user and the operations that
user may perform on that object.
One problem with access control lists is that they may be quite large. It is easy to imagine the access control lists for some widely used files occupying more storage than the data in the file. The usual solution to this is to introduce named sets of users -- for example, the user name OTHERS to specify the rights given to all users not explicitly mentioned in the list.
Under the classic MULTICS system, which was also used by the PRIMOS operating system, each file has an ACL, with access such as the following:
The traverse right is used in the context of hierarchical directory structures. A user who has no right to read or write a directory can mention that directory in the path name of a file as long as the user has traverse rights to that directory -- the user is just passing through, but may not open the directory to list its contents.
The right to edit an access control list illustrates one approach to allowing the contents of the access control matrix to be modified. In a sense, all users with the right to edit the access control list of an object can be thought of as co-owners of the object. If one user (the legitimate owner of an object) grants the right to edit that object's ACL to another user, it is like granting the other user a power of attorny over the object.
Under UNIX, each file has an ACL, but the ACL is strictly limited in structure. Each UNIX ACL has 3 fixed entries:
The simple to implement ACL scheme of UNIX is an example of this. Unlike the MULTICS ACL, it is not general, but it meets the needs of most users of small computer systems. As a result, every UNIX ACL fits exactly in 9 bits of the I-node of the file it describes!
MULTICS was intended to meet the needs of a general information utility, and as such, it had to deal with the problems of large numbers of users, including users from competing organizations. The generality of the MULTICS access control list is well justified by this environment, and the success of PRIMOS in meeting the needs of Compuserve or The Source (two large computer utilities of the late 1980's and early 1990's) amply illustrates the appropriateness of the MULTICS design.
When UNIX systems are extended beyond single departments, the short ACL of UNIX becomes a problem. Distributed versions of UNIX such as the Appolo Domain operating system (a system that was later folded into HP's HPUX system) were forced to add general ACL's back onto the UNIX file model in order to meet the demands of the large user base that such a system can serve.
As mentioned above, capability lists are the alternative to access control lists. The capability list implementation of the sample access matrix given above is as follows:
------ --------------------
| Fred |-| Tea | Cake |
------ | Drink | Eat |
--------------------
------ --------------------
| Lucy |-| Tea | Cake |
------ | Drink | Bake |
| Brew | |
--------------------
Users C-lists
A Capability List is the dual (in the topological sense) of an
access control list. Instead of storing one column of the access
matrix with a protected object, a row of the access matrix is stored
with the user.
A capability list entry, known as a capability, consists of the name of an object and the rights one user has to that object.
This does not change the rights a user has to a resource, and it does not change the set of policies that can be implemented, but it does change the economics of certain operations.
With a capability-list based protection mechanism, it is clear that users should not be granted the right arbitrarily edit their own capability lists! Instead, it is common to consider the capability list itself to be an object to which rights can be granted. Thus, Fred in the above example might have the right to edit Lucy's capability list (this would clearly be a continuation of the essentially sexist nature of this painfully steriotypical example). Typically, users might have the right to move capabilities from any list they can read to any list they can write, but users would not be able to modify a capability, except by removing access rights from it.
The most important application of capability lists in modern computer systems is to addressing. With capability-based addressing, each address is formed from two parts, as follows:
ADDRESS
__________________
|_______|__________|
| |
| Index into an addressed object
|
Index into a capability list
used to select an object
Capability based addressing, as such, was invented for the Chicago
Magic Number computer, a paper machine that was described by people at
the University of Chicago in the late 1960's. Capability lists
were invented by people involved with the MULTICS project, although
MULTICS was not itself a purely capability based machine.
Capability based addressing solves some interesting problems. For example, on UNIX, users can frequently name files that they may not access, and users may find themself in the odd situation where they own a file (and pay for the storage it occupies) yet they can't address it because they have no rights to the directory where that file is listed.
Capability based addressing solves this problem by associating the right to access an object with the ability to name it. User's names of objects are always relative to some capability list, and any global absolute name for an object is hidden inside the capabilty and is never visible to the user.
The most common use of capability based addressing is in paged or segmented virtual memory address translation. Each entry in a page table clearly indicates both the object to which that entry grants access and the access rights granted, and the page table associated with each user is the page table for that user.
VIRTUAL ADDRESS
__________________
|_______|__________|
| |
| Word in page
|
Index into the process's C-list for pages
the objects referenced by capabilities are pages
Note that it is difficult to imagine an efficient implementation of paged
virtual address translation using one access control list per page. This
would require either an associative memory or a search of some kind with
each memory reference. In contract, a simple table lookup suffices to
check the access rights in a conventional (capability list based) virtual
address translation system.
Paged address translation was, of course, invented 5 years before the concept of capabilities, so it is not wrong to say that capability-based addressing was used close to a decade before it was invented. The important thing to understand here is that almost a decade passed between the invention of the paged MMU and the understanding of the truly general nature of the protection mechanism it implements.
Another common example of the use of a capability list is in accessing open files. Even when access control lists are used to control the right to open a file, once the file is open, it is common to simply enter the file description into a list of open files attached to a process. Files in this list are referenced not by name, but by their position in the list, and the entries in this list indicate not only what file is involved but how it was opened -- that is, what access rights apply. Clearly, the list of open files is a capability list.
lseek( f, pos )
read( f, buffer, len )
f -- index into the open file C-list of the process!
These two examples illustrate a problem with the way capabilities
are used in modern systems. Instead of a single capability list
per user, where that list describes all the resources the user is
allowed to access, we tend to give users a collection of lists,
one list for each type of resource. This is awkward.
Some systems have been built that solve this problem, notably the IBM AS/400 (and System 38). Another commercial system in this class is the Plessy System 250 (built in the 1970's and used only as a control computer for telephone exchanges) and Intel's iAPX 432 (in the early 1980's, a commercial failure). Experimental systems that have solved this problem include the Cambridge CAP system and the Carnegie-Mellon Hydra and C.mmp systems.
It is worth noting that, on Multics, when a file is opened, the sectors of that file become visible as a segment in the virtual address space of the process that requested the open operation. Thus, for Multics, there is no distinction between the capability list describing the segments a process may access and the capability list describing the open files the process may access.
The domain of a process is the set of all objects that process may manipulate. In a pure capability based system,
Domain = C-list = row of access matrix
In the abstract, therefore, domain switching involves a change of the
current working C-list.
Domain switching is very important! It is very common, and systems
must control it.
For example, when a trap occurs, the system typically changes from a user domain to the system kernel's domain, and on return from trap, the system switches back to the user's domain.
The entire reason for introducing two states in order to build a simple protected system is to create two domains, a system domain, that includes all objects, and a user domain, that includes only some objects.
One of the most complex domain switching mechanisms was introduced on the Multics system. On this system, each process has a level or ring number between 0 and 15. Ring 0 is the innermost or highest protection level, and ring 15 is the outermost or lowest level. In addition, each segment has a level or ring number, and when a process attempts a memory access, the hardware checks the process level against the level of the accessed segment.
Each level in Multics was called a ring, and the designers of Multics pictured the system as a set of concentric rings, where each ring was viewed as being guarded by a firewall that protected everything in that ring from abuse by code running outside that ring. The concentric ring structure, in diagrams, resembled the cross-section of an onion, so Multics was described as being based on the Onion model (reminiscent on a brief scene in Shrek).
A Multics memory access is illlegal if the process is running at a level lower than (in a ring outside) that of the segment being accessed.
The Multics hierarchy of domains is a generalization of the two domain model of the primitive systems discussed previously. Multics allowed the operating system itself to be subdivided, so that only the process manager operated at the highest level, level 0. The virtual memory manager was at level 1, accounting was at a more restricted level, things like line-printer spoolers were even more restricted, leaving a variety of levels were available to users.
A user might run undebugged code at level 15, so that bugs in the code wouldn't damage other parts of the user's program.
To further complicate the Multics model, some pages can be marked as gateways. A procedure call to address zero in a gateway page is the only legal memory reference from a process running at a numerically higher level.
A call through a gateway causes the current level of the process to be pushed on the stack along with the return address. The called procedure then runs at the level of the segment containing it, and the level is reset to the original level when the procedure returns.
A MULTICS gateway is the generalization of a trap in a two-level security system. In addition to allowing system calls to run at the system level, it allows users to divide their code into more secure and less secure segments.
For example, consider a system where Joe, one of the users, owns a private database (say Chem Abstracts), and wishes to sell access to that database on a per-use basis. This means that Joe can't allow direct access to the database, he only wants other users to access it through his access code (which produces an appropriate billing record every time someone calls it).
Joe would simply arrange for his access code to run at a low numbered level (also called an inner ring), and he would require that users wishing to run his code do so from a higher numbered level (or outer ring), crossing a gateway as they call his code.
The above kind of consideration was a natural outcome of thinking about a computer utility -- the motivation behind MULTICS.
Note, however, that the strictly hierarchic scheme of MULTICS does not solve some problems. For example, it fails to solve the problems of two mutually suspicious users. Either one or the other must be given greater access rights if code from both users must share an address space.
While the MULTICS system solved a great number of problems in resource protection, it was not perfect! The MULTICS combination of access control lists for files, capability based addressing of segments (open files), and gate crossing to move from user to subsystem to system was remarkably flexible, but it was not universal.
MULTICS solved the basic problems of resource sharing -- preventing unauthorized access and controlled sharing of resources, but it failed to solve a problem known as the mutual suspicion problem:
Suppose there are two users who must share information but neither user trusts the other. For example, suppose user A writes a proprietary database management system which user B wishes to use to manage confidential data. User A wants an assurance that user B will not pirate the database management system, so user A demands that B's access to the system be through protected gateways. User B wants an assurance that user A will not use the database management system to access or manipulate any of user B's data that is not in the system. Thus, user B demands that the database management system access user B's data through protected gateways.
The MULTICS system creates a hierarchy. A protection gateway between system components A and B can protect A from B or it can protect B from A, but not both.
The mutual syspicion problem is easily illustrated in the context of programming languages, and the solutions used in programming languages are a useful model for the problem as seen from the operating system perspective:
Consider the classic data abstraction problem, as illustrated by the problem of implementing a stack. Every programmer knows that there are two natural implementations of a stack, the linked list and the array implementation.
____ ____ ____
|Top | |\\\\| |Top | ____
|____|-- |free| |____|---->| A |
| |\\\\| |____|--
->| A | ____ |
|____| | B |<-
| B | |____|--
|____| ____ |
| C | | C |<-
|____| |____|----//
As a programmer, it is useful to hide the implementation from the user, and
to protect the user from the implementation. We do this using, for example,
the abstract data type facilities of a programming language:
Consider an Ada package implementation of a stack abstract data type:
package STACK -- the interface
entry PUSH -- public "methods"
entry POP -- of the abstraction
end
package body STACK -- the implementation
entry PUSH -- details private
implementation -- and entirely hidden
entry POP -- from users
implementation
end
some user code
We rely on the scope rules of the language to ensure that the implementation
is unable to interfere with the user of the abstraction and that the
user is unable to interfere with the implementation.
Within the package body, the user code is outside the current scope, so the implementation of PUSH and POP cannot manipulate any of the user's variables. Within the user code, the package body is outside the current scope, so the user cannot manipulate the implementation of the stack. The public interface to the stack is shared -- that is, it is within the scope of both user and package body, so it is possible to call the PUSH and POP procedures from the user program.
The call to an entry of the package is an example of switching protection domains -- gate crossing -- in a manner that solves the mutual suspicion problem.
The caller of an entry to the stack package has very limited rights to the stack object, the right to call Push or Pop with that object. As this object is passed to Push or Pop, the rights associated with the object are amplified, so that the code of the stack object has complete access to the representation of the object. This informal usage leads us to say that any general purpose solution to the mutual suspicion problem will involve an amplification mechanism.
Solutions to the mutual suspicion problem at the programming language level generally impose only minimal run-time costs, if any. Scope rules are largely enforced by the compile-time semantics of the programming language, with very lightweight run-time implementations, so the run-time cost of using a language that offers strong support for data abstraction is minimal.
However, not all abstraction problems can be solved at compile-time. An open file is an example of an abstraction that must be implemented by run-time mechanisms, both because we expect operating systems to support different languages with differing levels of support for data abstraction, and because we dynamically bind files to programs -- it is common to find devices and device drivers that were manufactured and written after the program that uses them was compiled -- for example, when you buy a new disk and a new operating system that is compatable with a software package you've used for years. Protection of such an abstraction by programming language semantics is a difficult problem, at best! The world of Java applets takes this requirement for dynamic binding and dynamic resource protection to an extreme.
Fortunately, there are general purpose solutions to the mutual suspicion problem that have been known for years. Unfortunately, few of these are supported by modern operating systems, so most of the protected abstractions with which operating systems must deal are protected by special purpose mechanisms.
The UNIX setuid mechanism provides an example of a domain switching access-rights amplification mechanism that solved the mutual suspicion problem and achieved significant market penetration. Under UNIX, there is one bit associated with each executable file indicating what user ID that file is to be run under. Recall that the user ID is needed to determine what files a running program may open.
Under UNIX, the default user ID used when a new program is executed (by the exec system call) is the user ID of the program that requested the exec. If the setuid bit on an executable file is set, however, executing that file will cause it to run under the user ID of the file's owner.
The Setuid bit completely solves the mutual suspicion problem; It was patented by Ken Thompson, the originator of UNIX.
To illustrate this, consider the following scenario: Joe has a program that Fred needs to run, but Fred doesn't trust Joe and Joe doesn't trust Fred. If Joe releases the program so Fred has execute-only access to the code and the setuid bit is turned on, then Fred cannot steal Joe's secrets by examining the code, and when Fred runs the program, the program cannot access any data that Joe could not access directly.
Furthermore, if the program requires data from some file of Fred's, Fred can preven Joe from directly reading that file while still allowing the program to access the file by opening the file prior to executing the program and then letting the program read the file as, for example, standard input.
The result is that the only files of Fred that Joe's program can damage are the ones Fred left open when he called the program (of course, it can also access any of Fred's data that is publically accessible). Even though Fred ran it, Joe's program runs under Joe's user ID and has free access Joe's data.
The UNIX setuid bit is considered dangerous, and it is. Users who need to solve the mutual suspicion problem must use it, but they should not do so until they understand exactly what they are doing. Careless use of this bit has created serious problems in the past, including major security holes in the Emacs text editor.
Unfortunately, all recent implementations of UNIX have actually defeated some of the functionality of setuid by distinguishing between a user's effective user ID (the ID used for opening files) and the user's real user ID. This distinction is useful, since the real user is the one who should be billed for CPU time, but then, probably without fully understanding the consequences, the setuid() system service was extended to allow a user process to set its effective user ID to its real user id, thus defeating the solution to the mutual suspicion problem.
The Cambridge CAP system, designed by Wilkes and Needham and described in a book by the same name, is one of the best available examples of a system using capability based addressing that includes an amplification mechanism that solves the mutual suspeicion problem. This system was designed during the outburst of creative operating system design in the mid 1970's, before the UNIX model and the demand for UNIX compatability put an end to a large body of operating systems research.
In the CAP system, each protection domain was represented by a capability list, and all addressing, whether addressing of code, data or other resources, was accomplished through this capability list. Physically, the machine was a standard minicomputer with a very nonstandard memory management unit. The memory management unit directly interpreted not only memory references to segments, but it also implemented capability manipulation operations.
In the CAP system, there were three object types relevant to this discussion, data segments containing data, C-lists containing capabilities, and sealed objects containing protected implementations of data abstractions. The following access rights relevant to this discussion were associated with each capability:
When a process had a capability for a C-list that allowed read or write access to the capabilities in it, the process could move capabilities from the C-list to its own address space; this allowed a process to follow chains of capabilities from one C-list to another.
When a process had a capability for a C-list with only enter rights, it could not inspect the capabilities in that list, but it could transfer control from its own domain to that new domain. Parameter passing mechanisms were provided allowing a process to pass data and capabilities to the new domain as it transferred control, and when control entered a new domain, the program counter was appropriately set to the first executable instruction in that domain. This was the fundamental gate-crossing mechanism in the CAP system, and it was equally applicable to crossing between user and system domains or between one user's domain and another.
The most interesting feature of the CAP system was the sealed object. Sealed objects were created by the seal operation as follows:
sealed_object = seal( capability, key )Once a sealed object was created, it could not be manipulated. Capabilities for that object could, however, be stored by the program that created it. Given the correct key, any program could unseal a sealed object:
capability = unseal( sealed_object, key )On unsealing a sealed object, the capability that was sealed inside the object is returned. The unseal operation is the amplification operation.
The central use of sealed objects is to hide and protect the implementations of abstract data types. Thus, the file manager would export the data structures representing open files as sealed objects. If a user wanted to read or write an open file, the user would pass the open file to the read or write routine, and that routine would unseal the object to gain access to the data needed to actually perform the transfer. The key used to seal and unseal file objects would be held by the open routine and shared with the read and write routine, but this key would never be passed to users.
Keys for sealing objects in the CAP system were capabilities -- any capability could be used as a key, but the useful keys were those capabilities that were held closely within the implementation of an abstract data type.