# Outline for April 8, 2013

Due: Homework #1, due April 12, 2013

1. Take-Grant Protection Model
1. Islands (maximal subject-only tg-connected subgraphs)
2. Terminal and initial spans
3. Bridges (as a combination of terminal and initial spans)
2. Sharing
1. Definition: can•share(α, x, y, G0) true iff there exists a sequence of protection graphs G0, …, Gn such that G0 |–* Gn using only take, grant, create, remove rules and in Gn, there is an edge from x to y labeled α
2. Theorem: can•share(r, x, y, G0) iff there is an edge from x to y labeled r in G0\$, 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 I1, …, In connected by bridges for which x′I1 and y′In.
3. Model Interpretation
1. ACM very general, broadly applicable; Take-Grant more specific, can model fewer situations
2. Theorem: G0 protection graph with exactly one subject, no edges; R set of rights. Then G0 |–* Gn iff G0 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
4. Stealing
1. Definition: can•steal(r, x, y, G0) true iff there is no edge from x to y labeled r in G0, and there exists a sequence of protection graphs G0, …, Gn such that G0 |–* Gn in which:
1. Gn has an edge from x to y labeled r
2. There is a sequence of rule applications ρ1, …, ρn such that Gi−1 |– Gi; and
3. For all vertices v, wGi−1, if there is an edge from v to y in G0 labeled r, then ρi is not of the form “v grants (r to y) to w
2. Example
3. Theorem: can•steal(r, x, y, G0) iff the following hold simultaneously:
1. there is no edge from x to y labeled α in G0;
2. there is a subject x′ such that x′ = x or x′ initially spans to x; and
3. there is a vertex s with an edge labeled α to y in G0 and for which can•share(t, x, s, G0) holds.
5. Conspiracy
1. Access set
2. Deletion set
3. Conspiracy graph
4. I, T sets
5. Theorem: can•share(α, x, y, G0) iff there is a path from some h(p) ∈ I(x) to some h(q) ∈ T(y)

 You can also obtain a PDF version of this. Version of April 9, 2013 at 8:42PM