Understanding An Access Control Matrix Setup Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

An obvious variant of the access control matrix is to store each column with the object it represents. Thus, each object has associated with it a set of pairs, with each pair containing a subject and a set of rights. The named subject can access the associated object using any of those rights. More formally:

Let S be the set of subjects, and R the set of rights, of a system. An access control list (ACL) l is a set of pairs l = { (s, r) : s included in S, r included in R }. Let acl be a functionthat determines the access control list l associated with a particular object o. The interpretation of the access control list acl(o) = { (si, ri) : 1 <= i <= n } is that subject si may access o using any right in ri.

One issue is the matter of default permission. If a subject is not named in the ACL, it has no rights over the associated object. On a system with many subjects, the ACL may be very large. If many subjects have the same right over the file, one could define a "wildcard" to match any unnamed subjects, and give them default rights.

EXAMPLE: UNICOS 7.0 ACLs have entries of the form (user, group, rights). If the user is in the named group, he or she has those rights over the object. For example, the triplet (holly, maceranch, r) gives user holly read (r) access over the object only when holly has maceranch as her group.

If either user or group is specified as "*", that character is taken to match all users or all groups. Thus, (holly, *, r) gives holly read permission over the object regardless of the group she is in; (*, maceranch, r) gives any user read permission over the object when that user is in the group maceranch.

abbreviations of access control lists

Some systems abbreviate access control lists. The basis for file access control in the UNIX operating system is of this variety. UNIX systems divide the set of users into three classes: the owner of the file, the group owner of the file, and all other users. Each class has a separate set of rights.

EXAMPLE: UNIX systems provide read (r), write (w), and execute (x) rights. When user bishop creates a file, assume that it is in the group vulner. Initially, bishop requests that he be able to read from and write to the file, that members of the group be allowed to read from the file, and that no one else have access to the file. Then the permissions would be rw for owner, r for group, and none for other.

UNIX permissions are represented as three triplets. The first is the owner rights; the second, group rights; and the third, other rights. Within each triplet, the first position is r if read access is allowed or if it is not; the second position is w if write access is allowed or if it is not; and the third position is x if execute access is allowed or if it is not. The permissions for bishop's file would be rwr.

An interesting question is how UNIX systems assign group ownership. Traditionally, UNIX systems assign the effective principal group ID of the creating process. But in some cases this is not appropriate. For instance, suppose the line printer program works by using group permissions; say its group is lpdaemon. Then, when a user copies a file into the spool directory, lpdaemon must own the spool file. The simplest way to enforce this requirement is to make the spool directory group owned by lpdaemon and to have the group ownership inherited by all files created in that directory. Some systemsnotably, Solaris and SunOS systemsaugment the semantics of file protection modes by setting the setgid bit on the directory when any files created in the directory are to inherit the group ownership of the containing directory.

Abbreviations of access control lists, such as those supported by the UNIX operating system, suffer from a loss of granularity. Suppose a UNIX system has five users. Anne wants to allow Beth to read her file, Caroline to write to it, Della to read and write to it, and Elizabeth to execute it. Because there are only three sets of permissions and five desired arrangements of rights (including Alice), three triplets are insufficient to allow all desired modes of access. Hence, Alice must compromise, and either give someone more rights than she desires or give someone fewer rights. Similarly, traditional UNIX access control does not allow one to say "everybody but user Fran"; to do this, one must create groups of all users except Fran. Such an arrangement is cumbersome, the more so because only a system administrator can create groups.

Many systems augment abbreviations of ACLs with full-blown ACLs. This scheme uses the abbreviations of ACLs as the default permission controls; the explicit ACL overrides the defaults as needed. The exact method varies.

EXAMPLE: IBM's version of the UNIX operating system, called AIX, uses an ACL (called "extended permissions") to augment the traditional UNIX abbreviations of ACL (called "base permissions"). Unlike traditional ACLs, the AIX ACL allows one to specify permissions to be added or deleted from the user's set. Like UNICOS, AIX bases matches on group and user identity. The specific algorithm (using AIX's terminology, in which "base permissions" are the UNIX abbreviations of ACLs and "extended permissions" are unabbreviated ACL entries) is as follows.

Determine what set S of permissions the user has from the base permissions.

If extended permissions are disabled, stop. The set S is the user's set of permissions.

Get the next entry in the extended permissions. If there are no more, stop. The set S is the user's set of permissions.

If the entry has the same user and group as the process requesting access, determine if the entry denies access. If so, stop. Access is denied.

Modify S as dictated by the permissions in the entry.

Go to 3.

As a specific example, consider the following representation of an AIX system's access control permissions for the file xyzzy.


base permissions

owner(bishop): rw-

group(sys): r--

others: ---

extended permissions enabled

specify rw- u:holly

permit -w- u:heidi, g=sys

permit rw- u:matt

deny -w- u:holly, g=faculty

In the extended permissions lines, the first field determines what the line means ("specify" to override the base permissions, "permit" to add rights, and "deny" to delete rights); the second field states the rights involved, using the traditional UNIX triplet; and the third field defines the user ("u:") and group ("g:") involved.

In this example, holly can read xyzzy because the first and fourth lines in the extended permissions section override the base permission denial of access to others (the class of which holly is a member). If holly is working in the faculty group, she cannot write to xyzzy (the last line) but can read it (first line). The user heidi, working in group sys, can read and write to the file (the group line in the base permissions gives heidi read permission; the first permit line in the extended permissions section gives her write permission). In this way, the extended permissions augment the base permissions.

creation and maintenance of access control lists

Specific implementations of ACLs differ in details. Some of the issues are as follows.

Which subjects can modify an object's ACL?

If there is a privileged user (such as root in the UNIX system or administrator in Windows NT), do the ACLs apply to that user?

Does the ACL support groups or wildcards (that is, can users be grouped into sets based on a system notion of "group" or on pattern matching)?

How are contradictory access control permissions handled? If one entry grants read privileges only and another grants write privileges only, which right does the subject have over the object?

If a default setting is allowed, do the ACL permissions modify it, or is the default used only when the subject is not explicitly mentioned in the ACL?

Because these isues are critical to the correct use of ACLs on a system, we will explore them in more detail.

which subjects can modify an object's acl?

When an ACL is created, rights are instantiated. Chief among these rights is the one we will call own. Possessors of the own right can modify the ACL.

Creating an object also creates its ACL, with some initial value (possibly empty, but more usually the creator is initially given all rights, including own, over the new object). By convention, the subject with own rights is allowed to modify the ACL. However, some systems allow anyone with access to manipulate the rights.

EXAMPLE: The relational database System R contains sets of n-tuples making up the records, and each element of each n-tuple has attributes. These n-tuples are stored as tables, with the records as the rows and the attributes as the columns. Each table defines a relation.

The rights for manipulating a table (relation) include read (for reading rows, querying using the relation, or defining views), update (for writing to a table), insert (for adding rows), delete (for deleting rows), and drop (for deleting tables). Each right has a modifier, called the grant option, which if set allows the possessor to give the right to another. Any user with access to a table can give rights to any other user, provided the right has the grant option. Hence, possession of access (and a grant option associated with each right), not ownership, controls the transfer of rights.

do the acls apply to a privileged user?

Many systems have users with extra privileges. The two best known are the root super-user on UNIX systems and the administrator user on Windows NT and 2000 systems. Typically, ACLs (or their degenerate forms) are applied in a limited fashion to such users.

EXAMPLE: Solaris UNIX systems use both the abbreviations of ACLs standard to UNIX systems and a full-blown ACL. The abbreviations of ACLs are ignored when root is the subject, but the full ACLs apply even to root.

does the acl support groups and wildcards?

In its classic form, ACLs do not support groups or wildcards. In practice, systems support one or the other (or both) to limit the size of the ACL and to make manipulation of the lists easier. A group can either refine the characteristics of the processes to be allowed access or be a synonym for a set of users (the members of the group).

EXAMPLE: In the AIX example above, recall that the extended permission lines (corresponding to the full ACL) were

extended permissions enabled

specify rw- u:holly

permit -w- u:heidi, g=sys

permit rw- u:matt

deny -w- u:holly, g=faculty

Initially, the group sys had read permission only on the file. The second line adds write permission for processes with UID heidi and GID sys. The first line gives processes with UID holly read and write access, except when the GID of the process is faculty, in which case the process cannot write to the object (see the fourth line).

EXAMPLE: The UNICOS operating system provides ACLs similar to those of AIX, but allows wildcards. For example,

holly : maceranch : r

means that a process with UID holly and GID maceranch can read the object with which the ACL is associated. The ACL entry

holly : * : r

means that a process with UID holly can access the object regardless of the group that the process is in. And the entry

* : maceranch : r

means that any process with GID maceranch can read the object.


A conflict arises when two access control list entries in the same ACL give different permissions to the subject. The system can allow access if any entry would give access, deny access if any entry would deny access, or apply the first entry that matches the subject.

EXAMPLE: If any entry in an AIX ACL denies access, the subject is denied access regardless of the location of that entry. Otherwise, if any entry has granted access, the subject is granted access. This is an example of denial taking precedence.

EXAMPLE: Cisco routers apply the first access control list entry that matches the incoming packet. If none applies, the incoming packet is discarded. This is an example of the second approach, with a default rule of deny.

acls and default permissions

When ACLs and abbreviations of access control lists or default access rights coexist (as on many UNIX systems), there are two ways to determine access rights. The first is to apply the appropriate ACL entry, if one exists, and to apply the default permissions or abbreviations of access control lists otherwise. The second way is to augment the default permissions or abbreviations of access control lists with those in the appropriate ACL entry.

EXAMPLE: The AIX extended permissions fall into the second category, because they modify the base permissions.

EXAMPLE: If a packet entering a Cisco router is destined for a host on a network behind the router, but the router has no access list entry that allows the packet to be forwarded, the packet is discarded. This is an example of the first method, because the default permission is deny.

revocation of rights

Revocation, or the prevention of a subject's accessing an object, requires that the subject's rights be deleted from the object's ACL.

Preventing a subject from accessing an object is simple. The entry for the subject is deleted from the object's ACL. If only specific rights are to be deleted, they are removed from the relevant subject's entry in the ACL.

If ownership does not control the giving of rights, revocation is more complex.

EXAMPLE: Return to System R. Suppose Anna has given Peter update rights over a relation T but now wishes to revoke them. System R holds that after the revoking, the protection state of the system should be as it was before Anna gave Peter any rights. Specifically, if Peter gave Mary update rights, when Anna revokes Peter's update rights, Mary's update rights should be revoked unless someone other than Peter has also given her update rights.

To implement this, System R defines a relation called Sysauth. The attributes of this relation are (User, Table, Grantor, Read, Insert, Delete, Drop, Update). The values of the attributes corresponding to the rights are timestamps indicating when the right was given (except for Update, which we will deal with later). For example, if Anna gave Peter read rights over the relation Reports at time 10, and Peter gave them to Mary at time 20, the table would be as follows.

User Table Grantor Read









If Anna revokes Peter's read rights, and Mary obtained her read rights from Peter after Anna gave them to Peter, her read rights would also be revoked. However, suppose that Michelle had also given Mary read rights over Reports. Then deleting the last row in the table leaves an entry for Marynamely, the one from Michelle:

User Table Grantor Read









So Mary can still read Reports.

The update right has a value of All, Some, or None. These values refer to the set of rows that can be changed. If the value is Some, a second relation called Syscolauth records the columns that the subject can update. This table also records times, and revocation proceeds as for the other columns.

example: windows nt access control lists

Windows NT provides access control lists for those files on NTFS partitions. Windows NT allows a user or group to read, write, execute, delete, change the permissions of, or take ownership of a file or directory. These rights are grouped into commonly assigned sets called generic rights. The generic rights for files are as follows.

no access, whereby the subject cannot access the file

read, whereby the subject can read or execute the file

change, whereby the subject can read, execute, write, or delete the file

full control, whereby the subject has all rights to the file

In addition, the generic right special access allows the assignment of any of the six permissions.

Windows NT directories also have their own notion of generic rights.

no access, whereby the subject cannot access the directory

read, whereby the subject can read or execute files within the directory

list, whereby the subject can list the contents of the directory and may change to a subdirectory within that directory

add, whereby the subject may create files or subdirectories in the directory

add and read, which combines the generic rights add and read

change, whereby the subject can create, read, execute, or write files within the directory and can delete subdirectories

full control, whereby the subject has all rights over the files and subdirectories in the directory

As before, the generic special access right allows assignment of other combinations of permissions.

When a user accesses a file, Windows NT first examines the file's ACL. If the user is not present in the ACL, and is not a member of any group listed in the ACL, access is denied. Otherwise, if any ACL entry denies the user access, Windows NT denies the access (this is an explicit denial, which is calculated first). If access is not explicitly denied, and the user is named in the ACL (as either a user or a member of a group), the user has the union of the set of rights from each ACL entry in which the user is named.

As an example, suppose Paul, Quentin, and Regina are users of a Windows NT system. Paul and Quentin are in the group students. Quentin and Regina are in the group staff. The directory e:\stuff has its access control list set to (staff, add), (Quentin, change), (students, no access). Under this list, the first entry enables Regina to create subdirectories or files in e:\stuff. The third entry disallows all members of the group students from accessing the directory. The second entry would allow Quentin to delete subdirectories, except that Quentin is in the students group, and in Windows NT an explicit deny (as given in the third entry) overrides any grants of permission. Hence, Quentin cannot access the directory.

Now, let Regina create a subdirectory plugh in e:\stuff. She then disallows Paul's access, but wants to allow Quentin to have change access. She does the following.

Create e:\stuff \ plugh; its ACL is (staff, add), (Quentin, change), (students, no access).

Delete the last entry in ACL; from the second entry, this gives Quentin change access.

Add the entry (Paul, no access) to the ACL.

The last step is superfluous, because Windows NT denies access by default, but it is safer to add it anyway, lest the group students be given rights. If that should happen, Paul would get those rights unless the (Paul, no access) entry were present.