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
The set of unsafe systems is recursively enumerable
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.