Assignment 6, Solutions

Part of the homework for 22C:169, Spring 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Background: Consider the properties of a stack object s: The methods s.push(d) and d=s.pop() are available to anyone able to see the object s, but the actual representation used for the object is hidden, so users cannot directly manipulate the stack pointer(s) or determine if the stack is maintained as a list or some other data structure.
Now, consider representing a stack as the file fs, with two applications, push fs<data and pop fs>data that implement the abstraction.
A problem: What Unix-style ownership and access rights should be used for the stack object fs and the applications push and pop in order to enforce the access rules that stack users can only manipulate stacks by using the applications that implement the methods of the abstract stack class. You may need to invent some users or groups to solve this problem. If you do, document the purpose of each. Hint: You will probably need to use the SUID or SGID bits. (1 point)

Here, I use the invented user ID stackclass to solve the problem, but I could have used a group ID to do the same thing.
The object fs should be owned by the user stackclass with access rights -rw-------. That is, it is only readable and writable by its owner.
The stack operations push and pop should also be owned by the user stackclass with access rights ---s-----x. That is, the file may be executed by the public, but the SUID bit is set, so when they execute it, the user ID is set to the owner.
Background: Now, consider a file system based on access control lists. The access rights are R, W, X, S. R W and X are the usual read, write and execute access rights. When a user executes a program using the X right, the user's identity does not change. When a user executes a program using the S right, the user's identity changes to the identity of the program itself. No two programs have the same identity. Assume a user called u exists, the user of a stack object, as defined in the previous problem.
A problem: Give the access control lists for the file holding the stack object, fs and the files holding the push and pop applications, push and pop, so that the abstract rules for stacks are enforced. If you have to invent to invent additional applications to solve the problem, document what they do and give their access control lists. (1 point)

Stack objects such as fs have the access control list [push:RW,pop:RW]
The files containing the executable code for push and pop have the access control list [u:S]
Background: Now, consider a file system based on capability lists. Capability lists may grant access to files, or they may grant access to other capability lists. The access rights are R, W and X. R and W access rights allow a file to be read or written. Simple text and capabilities can both be passed as parameters. The X access right on a file permits it to be executed in the caller's environment. The X access right on a C-list permits the file named main in that C-list to be executed with that C-list as its environment. Assume a user called u exists, the user of a stack object.
A problem: Give the capability list of this user, along with any auxiliary C-lists needed. Use the name fs for the file holing the protected representation of the stack, accessible only to the code of the push and pop programs. Document the purposes of any auxiliary C-lists and any auxiliary applications needed to solve this problem. Hint: The solution is entirely different from the solution to parts a and b, but it bears a strong relationship to typical models of abstract programming language semantics for object-oriented languages. (1.5 points)

Here is one approach, there are others:
The user u has C-list [push:X,pop:X]
The C-lists push and pop each contain a main program that implements the required operation They have C-lists [main:X,fs:RW]
Background: Now, consider an extension to the above C-list system. The extension adds a new type of object, the sealed object, so we now have files, C-lists and sealed objects. There are two new operations, seal and unseal. Given a pair of capabilities c and k, seal(c,k) returns a capability for a sealed object s, where c is the capability being sealed and k is the key needed to unlock it. There is only one operation that applies to sealed objects, unseal(s,k). This is defined by the relationship unseal(seal(c,k),k')=c if and only if k and k' refer to the same object. If k and k' refer to different objects, the unseal operation fails and returns an invalid capability. This allows a completely different approach to implementing object-oriented abstraction. Assume a user called u exists, the user of a stack object.
A problem: Give the capability list of this user, along with any auxiliary C-lists needed. Use the name fs for the file holing the protected representation of the stack, accessible only to the code of the push and pop programs. Document the purpose and use of any auxiliary C-lists, auxiliary applications, or auxiliary objects you needed to solve this problem. (1.5 points)
First, sealedfs = seal( fs:RW, stackkey: )
The user u has the C-list [read:WX,write:WX,sealedfs:] That is, the user has no access rights to the sealed object. The only thing allowed on that capability is to unseal it, but the user does not have the key.
The C-lists push and pop each contain a main program that implements the required operation They have C-lists [main:X,stackkey:] That is, the programs can unlock any sealed stack objects they see.
Note that we must assume that users can pass capabilities as parameters when they execute programs. This is how u passes sealedfs: to the stack methods.