Computer Security: Art and Science

3.9 Exercises

1:
The proof of Theorem 3�1 states the following: Suppose two subjects s₁ and s₂ are created and the rights in A[s₁, o₁] and A[s₂, o₂] are tested. The same test for A[s₁, o₁] and A[s₁, o₂] = A[s₁, o₂] A[s₂, o₂] will produce the same result. Justify this statement. Would it be true if one could test for the absence of rights as well as for the presence of rights?
2:
Devise an algorithm that determines whether or not a system is safe by enumerating all possible states. Is this problem NP-complete? Justify your answer.
3:
Prove Theorem 3�3. (Hint: Use a diagonalization argument to test each system as the set of protection systems is enumerated. Whenever a protection system leaks a right, add it to the list of unsafe protection systems.)
4:
Prove or disprove: The claim of Lemma 3�1 holds when x is an object.
5:
Prove or give a counterexample:

The predicate can•share(a, x, y, G₀) is true if and only if there is an edge from x to y in G₀ labeled a, or if the following hold simultaneously.

There is a vertex s G₀ with an s-to-y edge labeled a.
There is a subject vertex x' such that x' = x or x' initially spans to x.
There is a subject vertex s' such that s' = s or s' terminally spans to s.
There is a sequence of subjects x₁, …, x_n with x₁ = x', x_n = s', and x_i and x_i₊₁ (1 i < n) being connected by an edge labeled t, an edge labeled g, or a bridge.
6:
The Take-Grant Protection Model provides two rights, take and grant, that enable the transfer of other rights. SPM's demand right, in many ways analogous to take, was shown to be unnecessary. Could take similarly be dropped from the Take-Grant Protection Model?
7:
The discussion of acyclic creates imposes constraints on the types of created subjects but not on the types of created objects. Why not?
8:
Prove that if a graph for cc is constructed and has no loops, the system is attenuating.
9:
Consider the construction of the three-parent joint creation operation from the two-parent joint creation operation. In [21], cr_C(s, c) = c/R₃ and link₂(S, A₃) = A₃/t dom(S). Why is this not sufficient to derive the three-parent joint creation operation from the two-parent joint creation operation?
10:
The simulation of three-parent creation by two-parent creation using the Ammann, Lipton, and Sandhu scheme mimics the simulation using SPM. Present a simpler, more direct simulation using the Ammann, Lipton, and Sandhu scheme that requires only five operations.

Top

1:	The proof of Theorem 3�1 states the following: Suppose two subjects s₁ and s₂ are created and the rights in A[s₁, o₁] and A[s₂, o₂] are tested. The same test for A[s₁, o₁] and A[s₁, o₂] = A[s₁, o₂] A[s₂, o₂] will produce the same result. Justify this statement. Would it be true if one could test for the absence of rights as well as for the presence of rights?
2:	Devise an algorithm that determines whether or not a system is safe by enumerating all possible states. Is this problem NP-complete? Justify your answer.
3:	Prove Theorem 3�3. (Hint: Use a diagonalization argument to test each system as the set of protection systems is enumerated. Whenever a protection system leaks a right, add it to the list of unsafe protection systems.)
4:	Prove or disprove: The claim of Lemma 3�1 holds when x is an object.
5:	Prove or give a counterexample: The predicate can•share(a, x, y, G₀) is true if and only if there is an edge from x to y in G₀ labeled a, or if the following hold simultaneously. There is a vertex s G₀ with an s-to-y edge labeled a. There is a subject vertex x' such that x' = x or x' initially spans to x. There is a subject vertex s' such that s' = s or s' terminally spans to s. There is a sequence of subjects x₁, …, x_n with x₁ = x', x_n = s', and x_i and x_i₊₁ (1 i < n) being connected by an edge labeled t, an edge labeled g, or a bridge.
6:	The Take-Grant Protection Model provides two rights, take and grant, that enable the transfer of other rights. SPM's demand right, in many ways analogous to take, was shown to be unnecessary. Could take similarly be dropped from the Take-Grant Protection Model?
7:	The discussion of acyclic creates imposes constraints on the types of created subjects but not on the types of created objects. Why not?
8:	Prove that if a graph for cc is constructed and has no loops, the system is attenuating.
9:	Consider the construction of the three-parent joint creation operation from the two-parent joint creation operation. In [21], cr_C(s, c) = c/R₃ and link₂(S, A₃) = A₃/t dom(S). Why is this not sufficient to derive the three-parent joint creation operation from the two-parent joint creation operation?
10:	The simulation of three-parent creation by two-parent creation using the Ammann, Lipton, and Sandhu scheme mimics the simulation using SPM. Present a simpler, more direct simulation using the Ammann, Lipton, and Sandhu scheme that requires only five operations.