Outline for April 8, 2013
Reading: text §3.3
Due: Homework #1, due April 12, 2013
- Take-Grant Protection Model
- Islands (maximal subject-only tg-connected subgraphs)
- Terminal and initial spans
- Bridges (as a combination of terminal and initial spans)
- Sharing
- Definition: can•share(α, x, y, G_{0}) true iff there exists a sequence of protection graphs G_{0}, …, G_{n} such that G_{0} |–^{*} G_{n} using only take, grant, create, remove rules and in G_{n}, there is an edge from x to y labeled α
- Theorem: can•share(r, x, y, G_{0}) iff there is an edge from x to y labeled r in G_{0}$, or all of the following hold:
- there is a vertex y′ with an edge from y′ to y labeled r;
- there is a subject y′′ which terminally spans to y′, or y′′ = y′;
- there is a subject x′ which initially spans to x, or x′ = x; and
- there is a sequence of islands I_{1}, …, I_{n} connected by bridges for which x′ ∈ I_{1} and y′ ∈ I_{n}.
- Model Interpretation
- ACM very general, broadly applicable; Take-Grant more specific, can model fewer situations
- Theorem: G_{0} protection graph with exactly one subject, no edges; R set of rights. Then G_{0} |–^{*} G_{n} iff G_{0} 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
- Example: shared buffer managed by trusted third party
- Stealing
- Definition: can•steal(r, x, y, G_{0}) true iff there is no edge from x to y labeled r in G_{0}, and there exists a sequence of protection graphs G_{0}, …, G_{n} such that G_{0} |–^{*} G_{n} in which:
- G_{n} has an edge from x to y labeled r
- There is a sequence of rule applications ρ_{1}, …, ρ_{n} such that G_{i−1} |– G_{i}; and
- For all vertices v, w ∈ G_{i−1}, if there is an edge from v to y in G_{0} labeled r, then ρ_{i} is not of the form “v grants (r to y) to w”
- Example
- Theorem: can•steal(r, x, y, G_{0}) iff the following hold simultaneously:
- there is no edge from x to y labeled α in G_{0};
- there is a subject x′ such that x′ = x or x′ initially spans to x; and
- there is a vertex s with an edge labeled α to y in G_{0} and for which can•share(t, x, s, G_{0}) holds.
- Conspiracy
- Access set
- Deletion set
- Conspiracy graph
- I, T sets
- Theorem: can•share(α, x, y, G_{0}) iff there is a path from some h(p) ∈ I(x) to some h(q) ∈ T(y)