Outline for January 13, 2012

Reading: §3.1–3.3

  1. What is the safety question?
    1. 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.
    2. Question: in a given arbitrary protection system, is safety decidable?
  2. 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.
  3. General case: It is undecidable whether a given state of a given protection system is safe for a given generic right.
    1. Approach: represent Turing machine tape as access control matrix, transitions as commands
    2. Reduce halting problem to it
  4. Take-Grant
    1. Counterpoint to HRU result
    2. Symmetry of take and grant rights
    3. Islands (maximal subject-only tg-connected subgraphs)
    4. Bridges (as a combination of terminal and initial spans)
  5. Sharing
    1. Definition: can•share(α, x, y, G0) iff there exists a sequence of protection graphs G0, . . ., Gn such that that G0 |−*Gn using only take, grant, create, remove rules and in Gn, there is an edge from x to y labeled α
A PDF version is available here.
UC Davis sigil
ECS 235B, Foundations of Computer and Information Security
Winter Quarter 2012