Homework #3

UC Davis Students: Due May 19, 1997 at 11:59PM
NTU Students: Due May 26, 1997 at 11:59PM

1. (40 points) In the proof of the Harrison, Ruzzo, and Ullman theorem, we discussed the motion of the head of the tape to the left. Motion to the right would require us to take into account reaching the end of the tape. Please complete the proof presented in class by showing how the move (q, X) = (p, Y, R) can be represented as two commands, one covering the case where the head does not reach a new tape cell, and one where the head does reach a new tape cell.
2. (30 points) This question uses the Take-Grant model. Please give a sequence of rule applications showing how p can acquire the right r for x in the following protection graph, or prove that p cannot acquire those rights.
   
3. (40 points)A protected subsystem is a subject that is invoked by other subjects, and acts on their behalf. It is typically constrained, so that it can alter local variables and parameters, but nothing else (including other global information). Please extend the access control matrix model discussed in class to allow for the explicit existance of protected subsystems. To enter a protected subsystem S, use the primitive enter S with parameters (o₁, r₁), ..., (o_n, r_n), where o_i is an object that the subsystem can access and r_i the set of rights that the subsystem may use to access o_i; to exit the protected subsystem, use the primitive exit S with parameters (o₁, r₁), ..., (o_n, r_n). In your answer, define each of these operations in terms of the changes they induce on the access control matrix at the time of entry and of exit.
4. (20 points) Why is labelling (associating labels with objects and subjects) a security requirement? That is, why could a trusted computing base not simply maintain an access control table with entries for each subject and each object rather than having labels associated with each object?
5. (20 points) What restrictions are placed on two subjects (processes) that wish to send messages to, and receive messages from, each other:
   1. according to the Bell-LaPadula model?
   2. according to the Biba model?
6. (20 points)The *-property (no writes down) of the Bell-LaPadula model is designed to prevent subjects from leaking information to subjects at a lower security level. How could this rule be used to enforce integrity constraints (that is, prevent system programs from being altered maliciously)?

Extra Credit

7. What assumptions with respect to trust would an implementation of the Clark-Wilson model make? In particular, if you wanted to attack a system that implemented the Clark-Wilson model, what flaws would you hypothesize? Please discuss flaws related to the implementation and operation of system aspects related to the model only (that is, passwords being stored in the clear is not a relevant flaw).