Acess Control Theory

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

Users, Objects and Rights

In the abstract, any access control system can be viewed in the following terms.

In any system, resources have users. Some uses of resources are permitted, others are forbidden. Depending on the system, users may be people, processes, or other entities.

In any system, resources can be grouped together into objects. Depending on the system, objects may be concrete items such as files or memory pages, or they may be abstractions such as stacks, queues or database records.

The goal of any protection system is to ensure that a user never manipulates an object except in ways that conform to the access rights granted to that user by the system. Each class of objects is characterized by a set of applicable access rights. In Unix, for example, files may be readable, writable or executable. In the abstract, each access right can be thought of as permission to apply a particular method to an object.

The Access Matrix

In the abstract, at any instant, we can describe the protection state of a computer system in terms of the access matrix. If we limit ourselves to human users and files, we might draw an access matrix such as:

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

An access matrix always lists one user for each row and one resource for each column, giving the access rights of one user to one resource at the intersection of each row and column. This notation was invented by Butler Lampson in the early 1970s, althoug informal use of such tables in military security and similar contexts quite likely predates this by many decades. The above example access matrix shows the rights of four people, Alice, Bob, Carol and Dave to four files, aaa, bbb, ccc and ddd.

Notice that the access matrix contains no notion of ownership. Certainly, Alice might be considered the owner of file aaa because she is the only one able to modify it, but the above matrix suggests no obvious ownership for the other files.

The only way to encode ownership into the access matrix is to encode it in terms of the rights ownership grants. In the case of Unix, for example, ownership of a file grants the right to change the access rights of that file. Each such change is actually a change to the access matrix itself.

We can talk of access matrices in many contexts. For example, we can construct an access matrix where the objects are the identifiers in a program and the users are the various subroutines:

int a;
const int b = 5;
void c() {
        int d;
void e() {
        int f;
int main () {
c R/W R call R/W - - -
e R/W R call - call R/W -
main R/W R call - call - call
a b c d e f main

The above access matrix shows the "must be defined before use" rule, so, for example, the function c() cannot call e(). It also shows that the const variable cannot be written, and it shows the distinction between different classes of objects in that functions can neither be read nor written, but only called, while variables cannot be called.

In fact, this access matrix for the program above is grossly oversimplified. It is legal to take the address of a variable, while reading a function name automatically takes the address of that function. Furthermore, if a recursive call is made, there will be multiple instances of the local variables of the recursively called function, each of which is entitled to a separate column in the matrix.


In discussions of protection mechanisms, the term domain is commonly used. The domain of a user is the set of all objects that user is permitted to access, or more properly, the set of all access rights that user has to particular objects. Thus, we say that your domain contains read-only access to one file and read-write access to another.

We can speak of the immediate domain of a user as the set of operations on objects directly accessible to that user. In the context of an access matrix, the immediate domain of a user is simply one row of the matrix.

The terms domain, from protection theory, and scope from programming language semantics, are closely related.

Fine-grained versus Coarse-grained Security

If we speak of people as our actors, we are taking a very coarse grained approach to security. If we speak of individual functions as our users, we are taking a very fine grained approach. Clearly, coarse grained security allows us to create very simple models, while fine grained security allows us to gain very precise control at the expense of immensely complex security models.

Protection Mechanisms

Any real secure system must have some protection mechanism or mechanisms to enforce the access rights required by the system. In the case of Unix, we rely on the memory management unit to enforce access rights for memory segments, and we rely on the file system to enforce the access rights for files.

In general, enforcement mechanisms that are added as afterthoughts to the design of a system are very difficult to build. In fact, it is a reasonable generalization that enforcement mechanisms added as afterthoughts hardly ever work very well.

Most successful secure operating systems are built around their enforcement mechanism. To the extent that Unix is secure, for example, it is because the basic enforcement mechanisms of Unix were concieved at the very start of the development process and are central to all thinking about the system.

Unix is a Bad Example

Looking at the above discussion of the access matrix, it is clear that Unix is an odd example. Unix does not have a single enforcement mechanism, but rather, three entirely different mechanisms, one for memory pages, one for access to files that have already been opened, and one for controlling the right to open files.

The enforcement mechanism for memory pages lies in the MMU. The enforcement mechanism for open files lies in the table of open files associated with each Unix process. So far as open files and pages are concerned, access rights are fairly fine grained, with users being running processes. Unix then backs away from this for the right to open files, granting access in terms of abstract user IDs and groups of user IDs, using the short little lists of access rights attached to each file in order to grant or deny access.

This complexity is evidence that Unix was designed before general access control mechanisms or abstract protection models were fully understood by the computer science community. The understanding of these problems really began to flower only in the 1970s, after most of the key elements of the Unix design been fixed.

Sadly, in the 1980s, the early development of personal computing led to a strong deemphasis on all thinking about security, and PC operating systems developed in this era included very weak security mechanisms. This is because most thinking on the subject in that era focused on the fact that computers were personal. There was no need to protect them from their owners, and their owners could physically prevent anyone else from using their machines. This lack of thought led to explosive growth of viruses and other threats, but by the time this problem was recognized, many key decisions in PC operating systems had already been made.

Dynamic Protection Models

It is important to recognize that the Access Control Matrix is a static model. Any particular matrix represents a snapshot of the state of the protection system. All real systems include dynamic creation of new resources, dynamic creation (or addition) of new users, and dynamic changes of access rights.


As usual, Wikipedia has some good material: