April 7, 2017 Outline

Reading: Chapters from revised text, §3.2–3.4; [TL13]

1. 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
2. Related results
   1. The set of unsafe systems is recursively enumerable
   2. Monotonicity: no delete or destroy primitive operations
   3. The safety question for biconditional monotonic protection systems is undecidable.
   4. The safety question for monoconditional monotonic protection systems is decidable.
   5. The safety question for monoconditional protection systems without the destroy primitive operation is decidable.
3. Take-Grant Protection Model
   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)
4. Sharing
   1. Definition: can•share(α, x, y, G₀) true iff there exists a sequence of protection graphs G₀, …, G__n such that G₀ ⊢^* G_n using only take, grant, create, remove rules and in G_n, there is an edge from x to y labeled α
   2. Theorem: can•share(r, x, y, G₀) iff there is an edge from x to y labeled r in G₀, or all of the following hold:
      1. there is a vertex y′ with an edge from y′ to y labeled r;
      2. there is a subject y′′ which terminally spans to y′, or y′′ = y′
      3. there is a subject x′ which initially spans to x, or x′ = x; and
      4. there is a sequence of islands I₁, …, I_n connected by bridges for which x′ ∈ I₁ and y′ ∈ I_n
5. Model Interpretation
   1. ACM very general, broadly applicable; Take-Grant more specific, can model fewer situations
   2. Example: shared buffer managed by trusted third party
6. Schematic Protection Model
   1. Protection type, ticket, function, link predicate, filter function
   2. Take-Grant as an instance of SPM