Explain how access control lists are used to represent access control matrices.

1. An access control matrix, and its access control list and capability list representations

There 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.

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:

AliceBobCarolDaveaaabbbcccddd

R/W	R	R	-
R	R/W	R
R	R	R/W	R
R/W	R/W	R

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.