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 d(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 (o1, r1), ä, (on, rn), where oi is an object that the subsystem can 
access and ri the set of rights that the subsystem may use to access oi ; to exit the protected sub-
system, use the primitive exit S with parameters (o1, r1), ä, (on, rn). 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:

a.	according to the Bell-LaPadula model?

b.	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).