**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?

- An unauthorized state is one in which a generic right
- 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)

- Sharing
- Definition:
*can•share*(α,**x**,**y**,*G*_{0}) true iff there exists a sequence of protection graphs*G*_{0}, …,*G*such that_{n}*G*_{0}|−^{*}*G*using only take, grant, create, remove rules and in_{n}*G*, there is an edge from_{n}**x**to**y**labeled α

- Definition:

You can also obtain a PDF version of this. | Version of April 4, 2013 at 11:10PM |