Outline for April 5, 2013
Reading: § 3.1–3.2
Due: Homework #1, due April 12, 2013
- What is the safety question?
- An unauthorized state is one in which a generic right r could be leaked into an entry in the ACM that did not previously contain r. An initial state is safe for r if it cannot lead to a state in which r could be leaked.
- Question: in a given arbitrary protection system, is safety decidable?
- Mono-operational case: there is an algorithm that decides whether a given mono-operational system and initial state is safe for a given generic right.
- General case: It is undecidable whether a given state of a given protection system is safe for a given generic right.
- Approach: represent Turing machine tape as access control matrix, transitions as commands
- Reduce halting problem to it
- Related results
- The set of unsafe systems is recursively enumerable (exercise)
- For protection systems without the create primitives, the question of safety is complete in P-SPACE.
- Monotonicity: no delete or destroy primitive operations
- The safety question for biconditional monotonic protection systems is undecidable.
- The safety question for monoconditional monotonic protection systems is decidable.
- The safety question for monoconditional protection systems without the destroy primitive operation is decidable.
- Take-Grant Protection Model
- Counterpoint to HRU result
- Symmetry of take and grant rights
- Islands (maximal subject-only tg-connected subgraphs)
- Bridges (as a combination of terminal and initial spans)
- Definition: can•share(α, x, y, G0) true iff there exists a sequence of protection graphs G0, …, Gn such that G0 |−* Gn using only take, grant, create, remove rules and in Gn, there is an edge from x to y labeled α