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