ECE 424 / CS 463
Fall 2007
HW #1

Assigned 9/20, Due 10/2, Grace period until 10/4.

Homework is mostly ungraded, except to check for plausibility.

You may work in groups on this assignment, but you must write it up separately
and without the benefit of any notes, and at least one hour of non-security
related activities must elapse between your discussion and your writeup. (This
is the "Gilligan's Island" rule, as defined in
   http://www.everything2.com/index.pl?node_id=1234234   )

1. Section 14.10, Problem 1
2. Section 14.10, Problem 2
3. Section 14.10, Problem 3
4. Section 14.10, Problem 4
5. Section 3.9, Problem 1
6. Section 3.9, Problem 4
7. Theorems 3-1 and 3-2 lay the foundation of decidability in Access Control 
Matricies. In particular, the former proves that for mono-operational 
protection, safety is decidable, and the latter proves that for arbitrary ACM 
operations, safety is undecidable. This question further delinates the question
of decidability by restricting each command to have the form
    if (boolean condition)
        operation 1
        operation 2
        operation 3
In particular, we are looking at tri-operational commands with arbitrary
conditions (in other words, we do not restrict ourselves to monoconditional
commands).

Is safety decidable in this environment? If so, give an algorithm; if not, give
a proof.