Dynamic Protection Mechanisms

Dynamic Protection

An access matrix describes the instantaneous state of a protected system. Consider the following access matrix:

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

In the simplest terms, we can imagine three obvious kinds of changes:

• The addition or deletion of users. We could delete Dave from or add Ellen to the system, an operation reflected in the matrix by deletion or addition of a row.

• The addition or deletion of resources. We could delete the resource ddd or add a new resource eee. Here we are adding or deleting columns from the matrix.

• Alteration of the access rights of some user for some resource, changing the contents of one intersection in the matrix.

There are more subtle operations that we might ask for but that few systems permit:

• Adding a new class of resources. This involves identifying, for that class, a new set of access rights, corresponding to the methods of that class. Obviously, classes must be added before resources of that class are added.

• Deleting class of resources. If any resources of that class exist, they probably need to be deleted first unless they will be deleted as a consequence of deleting their class.

In the abstract, these operations can themselves be considered to involve the manipulation of resources. We can therefore talk about granting a user the right to create or delete users, the right to create or delete resources, etc. How we protect these operations is a serious question.

Consider programming languages, where we can think in very fine grained terms of one domain per activation of a block in the program. When a block invokes another block, for example, by calling a method of an object or by the flow of control entering a nested block, a new domain is created, corresponding to one activation of the new block. As each declaration in the new block is elaborated, resources are created in the new domain. When the block is exited, the domain for the activation of the block is deleted.

Direct and Indirect Domains

If we allow access rights in the access matrix that permit editing of the matrix, we must distinguish two kinds of domain:

• The direct domain of a user, that is, the set of rights that user currently has to objects, as recorded in the access matrix.

• The indirect domain of a user, that is, the set of rights that user could concievably gain to objects by exercising other rights that object may have.

In general, the indirect domain of users may be very difficult to compute. What we want is access control systems that are sufficiently flexible that routine creation and deletion of users and resources is possible yet where no user, other than, perhaps the super-user or system administrator has the ability to gain access to all resources.

The classic problem with protection mechanisms is that some seemingly necessary and useful operation is added, only to discover later that adding this operation caused every user's indirect domain to encompass the entire system.

Dynamic Protection in Classic Unix

In Unix, only the system administrator (also known as the superuser or just root) can create or delete new file-system domains, that is, new User IDs.

In Unix, all users may create new resources, that is, files and directories, and they may include them in any directory so long as the user has write access to that directory. Users may place hard links to any file in any directory that user may write.

In Unix, newly created files and directories have the owner and group set to the current effective user ID and Group ID of the user who created them, unless the directory in which the file was created had the set-user-ID or set-group-ID bits set. In those special cases, the new file has the user ID or group ID of the directory it was created in.

In Unix, file and directory owners (that is, users with an effective user ID matching the file owner) may issue chmod shell commands or kernel calls to change the access rights to a file, and may issue chown or chgrp shell commands or kernel calls to change the onwership and group of the file. The owner of the file may change the group arbitrarily to any group of which that owner is a member, while only the system administrator may change the ownership.

Deletion of files in Unix happens when the file becomes inaccessible, as a result of deletion of the last link to the file. Users may delete (remove) links in any directory they are able to write by using the rm command or the unlink kernel call.

In the original version of Unix, only the superuser could remove directories. This is done by using unlink to delete the self and uplinks from the target directory and then using unlink one final time to remove the link to the directory. Only the superuser was allowed to delete links to a directory. The rmdir utility in old Unix systems ran using the setuid mechanism with root ownership so it could do this. Later versions of Unix included an rmdir kernel call that any user could call instead of using system("rmdir f").

Note that Unix has a deeper level, where each running process has its own domain for protecting access to memory resources. At this level, domains are created by the fork system call. A domain may self-delete by using the exit system call.

The kill shell command and the signal kernel calls may be used to kill any process with a real or effective user ID matching that of the current user. The super user may kill or send signals to any process.

Unix provides one particularly interesting operation, chroot, that changes the root of the file system to a particular subtree of the file system. If a process creates a subtree of the file system containing only the files a particular program should be able to access, the program can be launched (by exec) after doing a chroot to that subtree, thereby preventing it from even being to name files that it should not be able to access.

Unfortunately, Unix does not contain standard tools for creating temporary user IDs that can be used to run untrusted software, so that the untrusted software would run with a never-before-used ID, and when finished, have a guarantee that that ID would not be used again. Several research implementatons of this idea have been proposed. Along with chroot, this would allow creation of truly airtight "sandboxes" arould untrusted programs.

Dynamic Protection with Access Control Lists

With access control lists, the notion of file ownership can be simplified compared to the Unix model. The primary value of ownership in Unix, aside from selecting a particular set of access rights, is that it confers the right to use chmod and similar operations to alter the access rights to the file.

In system based on access control lists, we typically generalize on this by making the right to edit the access control list of a file into an access right for that file. As a result, ownership of a file becomes a transferrable right.

Typically, restrictions are placed on a user's right to add access rights to a file. If I have the right to add rights, but I only have read-only rights to the file, I can only give away read-only rights to other users and I cannot add back the right to write to my own files once I mark them read-only. (I can, however, create a new read-write file, copy the read only file into that, and then give away the read-write file.)

Dynamic Protection with Capability Lists

With capability lists, the typical dynamic protection operations involve restricting capabilities (that is, removing access rights from them) and creating new objects, typically with all rights present, in the current domain.

Further dynamism results if capability lists are themselves objects, so that a user's domain, as represented by that user's capability list, sits at the root of a tree, dag or arbitrary graph of other capability lists, some of which may themselves be domains.

In a system where capability lists are objects, users may typically copy capabilties from any capability list they can read, and copy them to any capability list they can write. Sometimes, the copy and restrict operations are combined.

A typical capability-based system will include a way to launch a process with some particular capability list as its domain. Typically, the caller first creates a new capability list, copies capabilities for the necessary resources into that new list, and then launches the new process in that new domain.

Amplification

Access rights amplification allows a thread of control to gain access to resources that it could not normally access. The setuid mechanism of Unix is an example of an amplification mechanism. All general purpose protection mechanisms must include some kind of amplification mechanism, whereby a program running in a very restricted domain gains access to objects not accessible from that domain, typically as part of a gate-crossing operation.

In the case of setuid, the exec operation becomes a gate-crossing mechanism to launch code from one domain that was written to operate in another domain.

In pure capabilty-list based systems, the typical gate crossing mechanism involves access rights to a domain that will launch a specific application in that domain when exercised. Typically, this involves something like a call access right. In effect, the domain becomes an object, with the capabilities in that domain being the private components of the object. The call access right, then, corresponds to calling a method of the domain. A variety of implementations of this have been proposed over the years.

References

The classic article that launched the ideas in this section is:

"Dynamic protection structures", by Butler Lampson, Proc. AFIPS Conf. 35 (1969), pp 27-38.
http://research.microsoft.com/Lampson/06-DynamicProtect/06-DynamicProtectAbstract.html