Outline for January 12, 2007

Greetings and Felicitations!

TakeGrant

Counterpoint to HRU result

Symmetry of take and grant rights

Islands (maximal subjectonly tgconnected subgraphs)

Bridges (as a combination of terminal and initial spans)

Sharing

Definition: can·share(r, 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 r

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′ is in I_{1} and y′ is in I_{n}.

Model Interpretation

ACM very general, broadly applicable; TakeGrant 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 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

Example: shared buffer managed by trusted third part

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 in 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
Here is a PDF version of this document.