Outline for January 12, 2007

1. Greetings and Felicitations!
2. 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)
3. Sharing
   1. Definition: can·share(r, 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 r
   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′ is in I₁ and y′ is in I_n.
4. 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 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 part
5. Stealing
   1. Definition: can·steal(r, x, y, G₀) true iff there is no edge from x to y labeled r 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 r
      2. There is a sequence of rule applications ρ₁, ..., ρ_n such that G_i-1 |- G_i; and
      3. For all vertices v, w in G_i-1, if there is an edge from v to y in G₀ labeled r, then ρ_i is not of the form "v grants (r to y) to w"
   2. Example