Homework #4 Revision 1

Changes for Revision 1:
  • Fixed an error in the problem statement of question 2

Questions

1. (25 points) Revisit the example for x := y + z in Section 17.1.1. Assume that x does not exist in state s. Confirm that information flows from y and z to x by computing H(y_s | x_t), H(y_s), H(z_s | x_t), and H(z_s) and showing that H(y_ss | x_t) < H(y_s) and H(z_s | x_t) < H(z_s).

2. (25 points) The system plugh has users Skyler, Matt, and David. Skyler cannot access David’s files, and neither Skyler nor David can access Matt’s files. The system xyzzy has users Holly, Sage, and Heidi. Sage cannot access either Holly’s or Heidi’s files. The composition policy says that Matt and Holly can access one another’s files, and Skyler can access Sage’s files.
   1. Apply the Principle of Autonomy (any access allowed by either component must be allowed by their composition) to determine who can read whose files in the composition of xyzzy and plugh. Assume that any access not explicitly denied is allowed.
   2. Apply the Principle of Security (any access nor allowed by either component must not be allowed by their composition) to determine who can read whose files in the composition of xyzzy and plugh. Assume that any access not explicitly allowed is denied.

3. (20 points) Consider the rule of transitive confinement. Suppose a process needs to execute a subprocess in such a way that the child can access exactly two files, one only for reading and one only for writing.
   1. Could capabilities be used to implement this? If so, how? If not, why not?
   2. Could access control lists be used to implement this? If so, how? If not, why not?

4. (30 points) Section 18.3.2.3 derives a formula for I(A; X). Prove that this formula is a maximum with respect to p when (this is different than what is in the text).

Extra Credit

Remember that extra credit scores are not added to your homework score. They are recorded separately and used to determine whether to boost your grade if the score is on a borderline.

1. (20 points) Let L = (S_L, ≤_L) be a lattice. Define:
   1. S_IL = { [a, b] | a, b ∈ S_L ∧ a ≤_L b }
   2. ≤_IL = { ([a₁, b₁], [a₂, b₂]) | a₁ ≤_L a₂ ∧ b₁ ≤_{L b2 }}
   3. lub_IL([a₁, b₁], [a₂, b₂]) = (lub_L(a₁, a₂), lub_L(b₁, b₂))
   4. glb_IL([a₁, b₁], [a₂, b₂]) = (glb_L(a₁, a₂), glb_L(b₁, b₂))
   Prove that the structure IL = (S_IL, ≤_IL) is a lattice.

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 235B, Foundations of Computer and Information Security Version of May 26, 2026 at 1:07PM

You can also obtain a PDF version of this.