Outline for January 18, 2012

Reading: §3.3

1. Sharing
   1. Definition: can•share(α, x, y, G₀) iff there exists a sequence of protection graphs G₀, . . ., G_n such that 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(α, x, y, G₀) iff there is an edge from x to y labeled α in G₀, or all of the following hold:
      1. there is a vertex y′ with an edge from y′ to y labeled α;
      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.
2. Model Interpretation
   1. ACM very general, broadly applicable; Take-Grant more specific, can model fewer situations
   2. Theorem: G₀ protection graph with exactly one subject, no edges; R set of rights. Then G₀, . . ., G_n iff G₀ is a finite directed graph containing subjects and objects only, with edges labeled from nonempty subsets of R, and with at least one subject with no incoming edges
   3. Example: shared buffer managed by trusted third party
3. Stealing
   1. Definition: can•steal(α, x, y, G₀) iff there is no edge from x to y labeled α in G₀, and there exists a sequence of protection graphs G₀, . . ., G_n such that G₀ |−^*G_n in which:
      1. G_n has an edge from x to y labeled α
      2. There is a sequence of rule applications ρ₁, . . ., ρ_n such that G_i−1 |−G_i; and
      3. For all vertices v, w ∈ G_i−1, if there is an edge from v to y in G₀ labeled α, then ρ_, is not of the form “v grants (α to y) to w”
   2. Example
4. Conspiracy
   1. Access set
   2. Deletion set
   3. Conspiracy graph
   4. I, T sets
   5. Theorem: can•steal(α, x, y, G₀) iff there is a path from some h(p) ∈ I(x) to some h(q) ∈ T(y)

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