**Reading:** §3.1–3.3

- 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

- Take-Grant
- 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}) iff there exists a sequence of protection graphs*G*_{0}, . . .,*G*such that 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: can•share(α,

A PDF version is available here.

ECS 235B, Foundations of Computer and Information Security Winter Quarter 2012 |