3.3 The Take-Grant Protection Model

Can the safety of a particular system, with specific rules, be established (or disproved)? The answer, not surprisingly, is yes. Such a system is the Take-Grant Protection Model.

The Take-Grant Protection Model represents a system as a directed graph. Vertices are either subjects (represented by ) or objects (represented by ). Vertices that may be either subjects or objects are represented by . Edges are labeled, and the label indicates the rights that the source vertex has over the destination vertex. Rights are elements of a predefined set R; R contains two distinguished rights: t (for take) and g (for grant).

As the protection state of the system changes, so does the graph. The protection state (and therefore the graph) changes according to four graph rewriting rules:

Take rule: Let x, y, and z be three distinct vertices in a protection graph G₀, and let x be a subject. Let there be an edge from x to z labeled g with t g, an edge from z to y labeled b, and a b. Then the take rule defines a new graph G₁ by adding an edge to the protection graph from x to y labeled a. Graphically,

The rule is written "x takes (a to y) from z."

Grant rule: Let x, y, and z be three distinct vertices in a protection graph G₀, and let z be a subject. Let there be an edge from z to x labeled g with g g, an edge from z to y labeled b, and a b. Then the grant rule defines a new graph G₁ by adding an edge to the protection graph from x to y labeled a. Graphically,

The rule is written "z grants (a to y) to x."

Create rule: Let x be any subject in a protection graph G₀ and let a R. Then create defines a new graph G₁ by adding a new vertex y to the graph and an edge from x to y labeled a. Graphically,

The rule is written "x creates (a to new vertex) y."

Remove rule: Let x and y be any distinct vertices in a protection graph G₁ such that x is a subject. Let there be an explicit edge from x to y labeled b, and let a b. Then remove defines a new graph G₁ by deleting the a labels from b. If b becomes empty as a result, the edge itself is deleted. Graphically,

The rule is written "x removes (a to) y."

Because these rules alter the state of the protection graph, they are called de jure ("by law" or "by right") rules.

We demonstrate that one configuration of a protection graph can be derived from another by applying the four rules above in succession. The symbol |– means that the graph following it is produced by the action of a graph rewriting rule on the graph preceding it; and the symbol |–^* represents a finite number of successive rule applications. Such a sequence of graph rewriting rules is called a witness. A witness is often demonstrated by listing the graph rewriting rules that make up the witness (usually with pictures).

3.3.1 Sharing of Rights

We first wish to determine if a given right a can be shared—that is, given a protection graph G₀, can a vertex x obtain a rights over another vertex y? More formally:

Definition 3–3. The predicate can•share(a, x, y, G₀) is true for a set of rights a and two vertices x and y if and only if there exists a sequence of protection graphs G₁, …, G_n such that G₀ |–^*G_n using only de jure rules and in G_n there is an edge from x to y labeled a.

To establish the conditions under which this predicate will hold, we must define a few terms.

Definition 3–4. A tg-path is a nonempty sequence v₀, …, v_n of distinct vertices such that for all i, 0 i < n, v_i is connected to v_i+1 by an edge (in either direction) with a label containing t or g.

Definition 3–5. Vertices are tg-connected if there is a tg-path between them.

We can now prove that any two subjects with a tg-path of length 1 can share rights. Four such paths are possible. The take and grant rules in the preceding section account for two of them. Lemmata 3–1 and 3–2 cover the other two cases.

Lemma 3–1.

Proof x creates (tg to new vertex) v.

z takes (g to v) from x.

z grants (a to y) to v.

x takes (a to y) from v.

This sequence of rule applications adds an edge labeled a from x to y. A similar proof establishes the following lemma.

Lemma 3–2.

Thus, the take and grant rules are symmetric if the vertices on the tg-path between x and y are subjects. This leads us to the following definition.

Definition 3–6. An island is a maximal tg-connected subject-only subgraph.

Because an island is a maximal tg-only subgraph, a straightforward inductive proof shows that any right possessed by any vertex in the island can be shared with any other vertex in the island.

Transferring rights between islands requires that a subject in one island be able to take the right from a vertex in the other island or that a subject be able to grant the right to an intermediate object from which another subject in the second island may take the right. This observation, coupled with the symmetry of take and grant, leads to a characterization of paths between islands along which rights can be transferred. To express it succinctly, we use the following notation. With each tg-path, associate one or more words over the alphabet in the obvious way. If the {,,,} path has length 0, then the associated word is the null word n. notation t* means zero or more occurrences of the character t, so, for example, t*g represents the sequence g, tg, ttg, ....

Definition 3–7. A bridge is a tg-path with endpoints v₀ and v_n both subjects and the path's associated word in {,,,}.

The endpoints of a bridge are both subjects, so the right can be transferred from one endpoint of the bridge to the other.

Given this definition, and that every subject vertex is contained in an island (consisting of only that subject vertex, perhaps), we have established conditions under which rights can be shared between subjects in a protection graph.

Theorem 3–9. [641] The predicate subject•can•share(a, x, y, G₀) is true if and only if x and y are both subjects and there is an edge from x to y in G₀ labeled a, or if the following hold simultaneously:

1. There is a subject s G₀ with an s-to-y edge labeled a;

2. There exist islands I₁, …, I_n such that x is in I₁, s is in I_n, and there is a bridge from I_j to I_j+1 (1 j < n).

Objects complicate this result. Because subjects can act but objects cannot, the transfer may begin with a right possessed by an object and conclude with that right being given to another object. The following two definitions help.

Definition 3–8. A vertex x initially spans to y if x is a subject and there is a tg-path between x and y with an associated word in {} { n }.

In other words, x initially spans to y if x can grant a right it possesses to y.

Definition 3–9. A vertex x terminally spans to y if x is a subject and there is a tg-path between x and y with an associated word in {} { n }.

In other words, x terminally spans to y if x can take any right that y possesses. Note that these two definitions imply that t and g are not symmetric if either the source or destination vertex of the edge labeled t or g is an object.

We can now state and prove necessary and sufficient conditions for rights to be transferred from a vertex y to another vertex x.

Theorem 3–10. [527] The predicate can•share(a, x, y, G₀) is true if and only if there is an edge from x to y in G₀ labeled a, or if the following hold simultaneously:

1. There is a vertex s G₀ with an s-to-y edge labeled a.

2. There exists a subject vertex x' such that x' = x or x' initially spans to x.

3. There exists a subject vertex s' such that s' = s or s' terminally spans to s.

4. There exist islands I₁, …, I_n such that x' I₁, s' I_n, and there is a bridge from I_j to I_j+1 (1 j < n).

The idea behind this theorem is simple. Because s' terminally spans to s, s' can acquire a rights to y. Given the definition of island, all subjects in I_n can acquire those rights. They can be passed along the bridge to a subject in I_n–1, which means that any subject in I_n–1 can acquire those same rights. This continues until x' I₁ acquires those rights. Then, as x' initially spans to x, x' can pass the rights to x. Exercise 5 explores a possible alternative representation of this result.

Corollary 3–1. [527] There is an algorithm of complexity O(|V| + |E|) that tests the predicate can•share, where V is the set of vertices and E the set of edges, in G₀.

3.3.2 Interpretation of the Model

A model abstracts essential details from a situation to aid in its analysis. For example, the question: "Can my competitor access my files?" presumes a knowledge of the rules for sharing files on the computer system (or network). The model must correctly capture these rules to be applicable.

The beauty of the access control matrix model is its malleability; by choosing rights and rules appropriately, an analyst can use it to capture the essence of any situation. The Take-Grant Protection Model presents specific rules and distinguished rights and so can be applied only in specific situations.

The protection state of a system evolves as rules are applied to entities within the system. The question of what states can evolve is thus of interest, because that set of states defines what protection states the (real) system may assume. So, consider the set of states of a particular system that the Take-Grant Protection Model rules can generate. For simplicity, we consider those states arising from a single entity, which (by the Take-Grant rules above) must be a subject.

Theorem 3–11. [942] Let G₀ be a protection graph containing exactly one subject vertex and no edges, and let R be a set of rights. Then G₀ |–^* G if and only if G is a finite directed acyclic graph containing subjects and objects only, with edges labeled from nonempty subsets of R and with at least one subject having no incoming edges.

Proof (). By construction. Assume that G meets the requirements above. Let x₁, …, x_n be the set of subjects in G, and without loss of generality let x₁ have no incoming edges. Identify v with x₁. The graph G' can be constructed from v using the Take-Grant Protection Model rules, as follows:

1. Perform "v creates (a { g } to) new x_i" for all x_i, 2 i n, where a is the union of all labels on the edges going into x_i in G.

2. For all pairs of vertices x_i and x_j in G with x_i having a rights over x_j, perform "v grants (a to x_j) to x_i."

3. Let b be the set of rights labeling the edge from x_i and x_j in G (note that b may be empty). Perform "v removes ((a { g }) – b to) x_j."

The resulting graph G' is the desired graph G.

(). Let v be the initial subject, and let G₀ |–^* G. By inspection of the rules, G is finite, loop-free, and a directed graph; furthermore, it consists of subjects and objects only, and all edges are labeled with nonempty subsets of R.

Because no rule allows the deletion of vertices, v is in G. Because no rule allows an incoming edge to be added to a vertex without any incoming edges, and v has no incoming edges, it cannot be assigned any.

Corollary 3–2. [944] A k-component, n-edge protection graph can be constructed from t-rule applications, where 2(k – 1) + n t 2(k – 1) + 3n.

Using the Take-Grant Protection Model, Snyder [943] showed how some common protection problems could be solved. For example, suppose two processes p and q communicate through a shared buffer b controlled by a trusted entity s (for example, an operating system). The configuration in Figure 3-2a shows the initial protection state of the system. Because s is a trusted entity, the assumption that it has g rights over p and q is reasonable. To create b, and to allow p and q to communicate through it, s does the following:

This creates the configuration in Figure 3-2(b). The communication channel is two-way; if it is to be one-way, the sender would have write rights and the receiver would have read rights. This configuration also captures the ability of the trusted entity to monitor the communication channel or interfere with it (by altering or creating messages)—a point we will explore in later sections.

3.3.3 Theft in the Take-Grant Protection Model

The proof of the conditions necessary and sufficient for can•share requires that all subjects involved in the witness cooperate. This is unrealistic. If Professor Olson does not want any students to read her grade file, the notion of "sharing" fails to capture the unwillingness to grant access. This leads to a notion of stealing, in which no owner of any right over an object grants that right to another.

Definition 3–10. Let G₀ be a protection graph, let x and y be distinct vertices in G₀, and let a be a subset of a set of rights R. The predicate can•steal(a, x, y, G₀) is true when there is no edge from x to y labeled a in G₀ and there exists a sequence of protection graphs G₁, …, G_n for which the following hold simultaneously:

1. There is an edge from x to y labeled a in G_n.

2. There is a sequence of rule applications r₁, ..., r_n such that G_i–1 |– G_i using r_i.

3. For all vertices v and w in G_i–1, 1 i < n, if there is an edge from v to y in G₀ labeled a, then r_i is not of the form "v grants (a to y) to w."

This definition disallows owners of a rights to y from transferring those rights. It does not disallow those owners from transferring other rights. Consider Figure 3-3. The given witness exhibits can•steal(a, s, w, G₀). In step (1), the owner of a rights to w grants other rights (specifically, t rights to v) to a different subject, s. Without this step, the theft cannot occur. The definition only forbids grants of the rights to be stolen. Other rights may be granted. One justification for this formulation is the ability of attackers to trick others into surrendering rights. While the owner of the target right would be unlikely to grant that right, the owner might grant other rights. This models the Trojan horse (see Section 22.2), in which the owner of the rights is unaware she is giving them away.

Making the target of the theft a subject complicates this situation. According to Definition 3–10, the target may give away any rights as well. In this case, the owner is acting as a moderator between the target and the source and must restrain the transfer of the right through it. This models the case of mandatory access controls.

Theorem 3–12. [944] The predicate can•steal(a, x, y, G₀) is true if and only if the following hold simultaneously:

1. There is no edge from x to y labeled a in G₀.

2. There exists a subject vertex x' such that x' = x or x' initially spans to x.

3. There exists a vertex s with an edge labeled a to y in G₀ and for which can•share(t, x, s, G₀) holds.

Proof (). Assume that the three conditions above hold. If x is a subject, then x need merely obtain t rights to s and then use the take rule to obtain a rights to y. By definition, this satisfies can•steal(a, x, y, G₀).

Suppose x is an object. Then Theorem 3–10, can•share(t, x, s, G₀), implies that there exists a subject vertex x' that tg-initially spans to x and for which the predicate can•share(t, x', s, G₀) is true. Without loss of generality, assume that the tg-initial span is of length 1 and that x' has t rights over s in G₀. If x' does not have an edge labeled a to y in G₀, then x' takes a rights to y and grants those rights to x, satisfying the definition. If x' has an edge labeled a to y in G₀, then x' will create a "surrogate" to which it can give take rights to s:

1. x' creates (g to new subject) x".

2. x' grants (t to s) to x".

3. x' grants (g to x) to x".

Now x" has t rights over s and g rights over x, so the rule applications

1. x" takes (a to y) from s.

2. x" grants (a to y) to x.

satisfy the definition. Hence, can•steal(a, x, y, G₀) holds if the three conditions in the theorem hold.

(): Assume that can•steal(a, x, y, G₀) holds. Then condition (a) of the theorem holds directly from Definition 3–10.

Condition (a) of Definition 3–10 implies can•share(a, x, y, G₀). From condition (b) of Theorem 3–10, we immediately obtain condition (b) of this theorem.

Condition (a) of Theorem 3–10 ensures that the vertex s in condition (c) of this theorem exists.

We must show that can•share(t, x, s, G₀) holds. Let r be a sequence of rule applications. Consider the minimal length sequence of rule applications deriving G_n from G₀. Let i be the least index such that G_i–1 |–_ri G_i and such that there is an edge labeled a from some vertex p to y in G_i but not in G_i–1. Then G_i is the first graph in which an edge labeled a to y is added.

Obviously, r_i is not a remove rule. It cannot be a create rule, because y already existed. By condition (c) of Definition 3–10, and the choice of i ensuring that all vertices with a rights to y in G_i are also in G₀, r_i cannot be a grant rule. Hence, r_i must be a take rule of the form

for some vertex s in G₀. From this, can•share(t, p, s, G₀) holds. By condition (c) of Theorem 3–10, there is a subject s' such that s' = s or s' terminally spans to s, and by condition (d), there exists a sequence of islands I₁, …, I_n such that x' I₁ and s' I_n.

If s is an object (and thus s' s), consider two cases. If s' and p are in the same island, then take p = s'. If they are in different islands, the derivation cannot be of minimal length; choose s' in the same island to exhibit a shorter one. From this, the conditions of Theorem 3–10 have been met, and can•share(t, x, s, G₀) holds.

If s is a subject (s' = s), then p I_n, and we must show that p G₀ for Theorem 3–10 to hold. If p G₀, then there is a subject q in one of the islands such that can•share(t, q, s, G₀) holds. (To see this, note that s G₀ and that none of the de jure rules add new labels to incoming edges on existing vertices.) Because s is an owner of a rights to y in G₀, we must derive a witness for this sharing in which s does not grant (a to q). If s and q are distinct, replace each rule application of the form

s grants (a to y) to q

with the sequence

p takes (a to y) from s

p takes (g to q) from s

p grants (a to y) to q

thereby transferring the right (a to y) to q without s granting. If s = q, then the first rule application in this sequence suffices.

Hence, there exists a witness to can•share(t, q, s, G₀) in which s does not grant (a to y). This completes the proof.

3.3.4 Conspiracy

The notion of theft introduced the issue of cooperation: which subjects are actors in a transfer of rights, and which are not? This raises the issue of the number of actors necessary to transfer a right. More formally, what is the minimum number of actors required to witness a given predicate can•share(a, x, y, G₀)?

Consider a subject vertex y. Then y can share rights from any vertex to which it terminally spans and can pass those rights to any vertex to which it initially spans.

Definition 3–11. The access set A(y) with focus y is the set of vertices y, all vertices x to which y initially spans, and all vertices x' to which y terminally spans.

Of course, a focus must be a subject.

Consider two access sets with different foci y and y' that have a vertex z in common. If z A(y) because y initially spans to z, and z A(y') because y' initially spans to z, by the definition of initial span, no rights can be transferred between y and y' through z. A similar result holds if both y and y' terminally span to z. However, if one focus initially spans to z and the other terminally spans to z, rights can be transferred through z. Because we care about the transfer of rights, we identify a set of vertices that can be removed from the graph without affecting transfers:

Definition 3–12. The deletion set d(y, y') contains all vertices z in the set A(y) A(y') for which (a) y initially spans to z and y' terminally spans to z, (b) y terminally spans to z and y' initially spans to z, (c) z = y, and (d) z = y'.

Given the deletion set, we construct an undirected graph, called the conspiracy graph and represented by H, from G₀:

The conspiracy graph represents the paths along which subjects can transfer rights. The paths are unidirectional because the rights can be transmitted in either direction. Furthermore, each vertex in H represents an access set focus in G₀.

EXAMPLE: In Figure 3-4, the access sets are A(x) = { x, a } A(e) = { e, d, i, j } A(b) = { b, a } A(y) = { y } A(c) = { c, b, d } A(f) = { f, y } A(d) = { d } A(h) = { h, f, i } Figure 3-4. (a) A Take-Grant protection graph. (b) The corresponding conspiracy graph. The vertex z is not in A(e) because the path from e to z is neither a terminal nor an initial span. For the same reason, the vertex y is not in A(h). Using these sets gives the following nonempty deletion sets: d(x, b) = { a } d(c, d) = { d } d(y, f) = { y } d(b, c) = { b } d(c, e) = { d } d(h, f) = { f }   d(d, e) = { d }   Although A(e) A(h) = { i }, the vertex i is in A(e) because e initially spans to i, and i is in A(h) because h initially spans to i. Hence, d(e, h) = Ø and there is no edge between h(e) and h(h) in G0.

The conspiracy graph exhibits the paths along which rights can be transmitted. Let the set I(p) contain the vertex h(p) and the set of all vertices h(p') such that p' initially spans to p; let the set T(q) contain the vertex h(q) and the set of all vertices h(q') such that q' terminally spans to q. Then:

Theorem 3–13. [944] can•share(a, x, y, G₀) is true if and only if there is a path from some h(p) I(x) to some h(q) T(y).

Furthermore:

Theorem 3–14. [944] Let L be the number of vertices on a shortest path between h(p) and h(q), with p and q as in Theorem 3–13. Then L conspirators are necessary and sufficient to produce a witness to can•share(a, x, y, G₀).

EXAMPLE: In Figure 3-4, the shortest path between h(e) and h(x) has four vertices (h(x), h(b), h(c), and h(e)), so four conspirators are necessary and sufficient to witness can•share(r, x, y, G0). Such a witness is e grants (r to y) to d. c takes (r to y) from d. c grants (r to y) to b. b grants (r to y) to a. x takes (r to y) from a. and the conspirators are e, c, b, and x. To see that this is minimal, note that both x and b must act to transfer the right through a, e must act to transfer the right to another vertex, and in order to pass the right from d to b, c must act.

3.3.5 Summary

The Take-Grant Protection Model is a counterpoint to the Harrison-Ruzzo-Ullman (HRU) result. It demonstrates that, for a specific system, the safety question is not only decidable but decidable in linear time with respect to the size of the graph. It also explores ancillary issues such as theft and conspiracy.