THE SHARING OF RIGHTS AND INFORMATION 

IN A CAPABILITY-BASED PROTECTION SYSTEM 

/;r ML-5 

f&f&wJ7 

dc, 9 "0 

Matt Bishop /J -ij?L? r, 

Technical Report PCS-TR88-136 
I 

The Sharing of Rights and Information 

in a Capability-Based Protection System 

Matt Bishop 

Department of Mathematics and Computer Science 

Dartmouth College 

Hanover, NH 03755 

ABSTRACT 

This paper examines the question of sharing of rights and information in 

the Take-Grant Protection Model by concentrating on the similarities 

between the two; in order to do this, we state and prove new theorems 

for each that specifically show the similarities. The proof for one of the 

original theorems is also provided. These statements of necessary and 

sufficient conditions are contrasted to illustrate the proposition that 

transferring rights and transferring information are fundamentally the 

same, as one would expect in a capability-based system. We then discuss directions for future research in light of these results. 

1. Introduction 

Capability-based protection systems control access to objects by means of a ticket 

or capability. This piece of information, typically an ordered pair consisting of an 

address and a set of rights, grants to the holder unconditional access to the object at 

the given address in the manner indicated by the set of rights. If the ticket is copied 

to another process, that process has access to the object commensurate with the associated ticket. For this reason, capabilities are normally made inaccessible to ordinary 

processes. 

In addition to being a grant of rights, a capability is also information. When an 

This work was supported by grant NAG 2480 from the National Aeronautics and Space Adminisuation (NASA) to Dartmouth College, and a Burke Award from Dartmouth College. 
-2- 

object possesses a capability, it knows the location (address) of some other object and 

how it may access that other object (set of rights). No action of any kind is necessary 

to implement the use of a capability; the possessor need not be checked against an 

access control list, or provide a special key; just knowing what the ticket contains 

means the object has those rights to that object. In essence, then, a capability is permissions encoded as information. 

In this paper we explore how the transfer of rights and the transfer of information 

are reflected in a capability-based protection model. We shall use the Take-Grant Protection Model, introduced in [5] and expanded upon in [1,2,6-81. because both sharing of rights and sharing of information in that model has been analyzed at some 

length. This model also has some interesting theoretical properties: specifically, 

whether or not a right (or information) can be transferred may be detennined in time 

linearly proportional to the size of the graph even if the number of objects which can 

be created is unbounded, This is a direct consequence of the graph rewriting rules, 

which will be explained in the second and fourth sections. These rules make the 

model mono-operational; indeed, for any such system, there is an algorithm that 

decides whether that system and a given initial state is safe for a generic right. (With 

the more general system, of course, the question is undecidable [4].) 

The next section discusses the sharing of rights; we present a framework for stating the standard theorem, and do so. We then state and prove a slightly different 

(albeit equivalent) theorem; this theorem parallels a result presented in a later section, 

after we have discussed the sharing of information in the model; in that section, 

another theorem presents necessary and sufficient conditions for information transfer to 
-3- 

occur. Following this, we state and prove a version of this theorem which parallels 

the standad thmm for sharing rights. We conclude by looking at the idea of 

“meta-theorems” and how the dual nature of rights in a capability system demonstrates their utility. 

2. Transfers of Authority 

Let a finite, directed graph called a protection graph represent a system to be 

modelled. A protection graph has two distinct kinds of vertices, called subjects and 

objects. Subjects are the active vertices, and (for example) can represent users; they 

can pass information and authority by invoking graph rewriting rules. Objects, on the 

other hand, are completely passive; they can (for example) represent files, and do nothing. 

In protection graphs, the subjects are represented by and objects by 0. Vertices which may be either subjects or objects are represented by Q Pictures are very 

often used to show the effects of applying a graph rewriting rule on the graph; the 

symbol I- is used to mean that the graph following it is produced by the action of the 

graph rewriting rule on the graph preceding it. The rewriting rule itself is often written after the derived graph. The symbol c* represents several rule applications. The 

term witness means a sequence of graph rewriting rules which produce the predicate or 

condition being witnessed, and a witness is often demonstrated by listing the graph 

rewriting rules that make up the witness (usually with pictures.) 

The edges of a protection graph are labelled with subsets of a finite set R of 

rights. Suppose that (r,w,t,g} E R, where r, w, t, and g represent read, write, take, 

and grant rights, respectively. When written as labels on a graph, the set braces are 
-4- 

normally omitted. 

The TakeGrant Model permits users with certain rights to transfer rights from 

one vertex to another. The rules governing the transfer of rights are called de jure 

rules and are as follows : 

take: Let x, y, and z be three distinct vertices in a protection graph Go, and let x be a 

subject. Let there be an edge from x to y labelled y with t E y, an edge from y 

to z labelled p, and a s p. Then the take rule defines a new graph Gi by adding 

an edge to the protection graph from x to z labelled a. Graphically, 

t, P, IX Y Z X Y z 

The rule is written: “x takes (a to z) from y.” 

grunt: Let x, y, and z be three distinct vertices in a protection graph Go, and let x be 

a subject. Let there be an edge from x to y labelled y with g E y, an edge from x 

to z labelled p, and a c p. Then the grunt rule defines a new graph GI by 

adding an edge to the protection graph from y to z labelled a. Graphically, 

X Y z X Y z 

The rule is written: “x grants (a to z) to y.” 

create: Let x be any subject in a protection graph Go and let a be a subset of R. 

Create defines a new graph GI by adding a new vertex y to the graph and an 

edge from x to y labelled a. Graphically, 
-5- 

.I-& 

X X Y 

The rule is written: “x creates (a to new vertex) y.” 

remove: Let x and y be any distinct vertices in a protection graph GI such that x is a 

subject. Let there be an explicit edge from x to y labelled p, and let a be any 

subset of R. Then remove defines a new graph GI by deleting the a labels from 

p. If p becomes empty as a result, the edge itself is deleted. Graphically, 

. P, IX Y X Y 

The rule is written: “x removes (a to) y.” 

The edges which appear in the above graphs are called explicit because they 

represent authority known to the protection system. 

Note that there is a duality between the take and grant rules when the edge 

labelled c or g is between two subjects. Specifically, with the cooperation of both subjects, rights can be transmitted backwards along the edges. The following two lemmas 

(from [5]) demonstrate this: 

Lemma 1: 

X Y Z X Y Z 

Lemma 2: 

- I8 .* a 

X Y Z X Y Z 
-6- 

As a result, when considering the transfer of authority between subjects, neither 

direction nor label of the edge is important, so long as the label is in the set (t,g ). 

The first question that comes to mind is under what conditions can rights be 

shared? To answer this question, we first need to examine some characteristics of 

take-grant graphs. 

Definition: A tg-path is a nonempty sequence YO, . . . ,vk of distinct vertices such that 

for all i, OIi<k, vi is connected to Vi+l by an edge (in either direction) with a label 

containing t or g. 

Note that the vertices in a tg-path may be either subjects or objects. 

Definition: Vertices are tg-connected if there is a tg-path between them. 

Definition: An island is a maximal tg-connected subject-only subgraph. 

Any right that one vertex in an island has can be obtained by any other vertex in 

that island. In other words, an island is a maximal set of subject-only vertices which 

possess common rights. 

-+tJ t With each tg-path, associate one or more words over the alphabet { t, t, g , g } 

in the obvious way. If the path has length 0, then the associated word is the null word 

V. 

Definition: A vertex vo initially spans to vk if vo is a subject and there is a tg-path 

between YO and vk with associated word in { t, g } u {v}. 

Definition: A vertex vo terminally spans to vk if vo is a subject and there is a tg-path between vo and vk with associated word in { ;* }. 

Definition: A bridge is a tg-path with vo and vk both subjects and the path’s associ- 

-+-+ 
-7- 

+ t -+* +t3 ated word in { t*, I*, t*gt*, t*gt* }. 

An initial span is a tg-path along which the first vertex in the path can transmit 

authority; a terminal span is a tg-path dong which the first vertex in the path can 

acquire authority. A bridge is an edge dong which a right can be passed, possibly by 

using lemma 1 and 2 as well as the de jure rules. As a note, a bridge is said to be 

directed away from vo. The following diagram illustrates these terms: 

P 

R 

U V W X Y 

islands: 

bridges: u,v,w and w,x,y 

initial span: 

terminal span: 

h={p ,u IJ2={w }J3={y 4’1 

p with associated word: v 

s’,s with associated word 7 

The following predicate formally defines the notion of trun.sjkrring authority: 

Definition: The predicate cun*share(a, x, y, Go) is true for a right a and two vertices 

x and y if and only if there exist protection graphs G 1, . . . , Gn such that GoC* Gn 

using only de jure rules, and in Gn there is an edge from x to y labelled a. 

In short, if x can acquire a rights to y, then cun*share(a, x, y, Go) is true. The 

theorem which establishes necessary and sufficient conditions for this predicate to hold 

Theorem 3: The predicate cun*share(a, x, y, Go) is true if and only if there is an 

edge from x to y in Go labelled a, or if the following hold simultaneously: 

(i) there is a vertex s E Go with an s-to-y edge labelled a; 

\ 
-8- 

(ii) there exists a subject vertex p ’ such that p ’=p or p ’ initially spans to x; 

(iii) there exists a subject vertex s’ such that S’S or s’ terminally spans to s; 

and 

(iv) there exist islands Ii, . . . ,Iv such that p’ is in 11, s’ is in Iv, and there is a 

bridge from Ij to Ij+l (lSj<v). 

This statement of the necessary and sufficient conditions can be much simpler, 

and that is the topic of the next section. 

3. Alternate Necessary and Sufficient Conditions for cun*shure 

For reasons that will become clear in the next section, we can state conditions 

necessary and sufficient for can.share to be true as follows: 

Theorem 4: The predicate can*shure(a, x, y, Go) is true if and only if there is a 

vertex s with an edge to y labelled a, and a sequence of subjects u 1, . . . , u m such 

that all of the following conditions hold simultaneously: 

(i) u 1 =x or u 1 initially spans to x; 

(ii) u m =s or u m terminally spans to S; and 

(iii) for all i (1 Si cm), there is a rg-path between u i and u i+l with an associated word in B . 

boot: (e) We prove this by induction on rn. 

BASIS: m=l. First, note that if ui=s, u1 has a rights toy; but if if uifs, then by 

applying the take rule (repeatedly if necessary), u 1 can acquire a rights to y. If u I =x , 

we are done. If not, by using the take rule (possibly repeatedly), u 1 can acquire grant 

rights to x, and can then use the grant rule to give x a rights over y. Since only the 
take and grant 

-9- 

kjwe) rules were used, cunwhare(a, x, y, Go) is true by definition. 

INDUCTIONHYPOTHESIS: For all mIk, if the three conditions in the theorem 

are true, then cun~share(a, x, y, Gn) is true. 

INDUCTION STEP: Let rn =k+l. By the induction hypothesis, clearly cun.shure(a, 

u 2, y, Gn) is true. It suffices to consider whether u i can get a rights to y. For if 

u 1 =x, we are done, and if not, then u 1 initially spans to x; so u 1 may use a (possibly 

null) series of take rules to acquire grunt rights over x, and then use the grant rule to 

pass its a rights to x. 

Consider now whether or not u 1 may acquire a rights to y. Note that u 1 and u2 

are distinct, else rn =k, not k+l. By condition (iii), the word associated with the tgpath between u 1 and u2 is in B. So let us consider those one at a time. In these 

cases, by the take tule and the definition of bridge, it is necessary to consider only 

those cases where bridges are of length 2 or less. 

Case 1. The associated word is 2 

In this case u 1 simply applies the take rule to acquire a rights to y. 

Case 2. The associated word is 2. 

The result is true by lemma 2; take x =u 1, y =u 2, and z =y in that lemma. 

Case 3. The associated word is 2 

The result is true by lemma 1; take x =u 2, y =u I, and z =y in that lemma. 

Case 4. The associated word is F. 

In this case u2 simply applies the grant rule to give a rights to y. 
- 10 - 

Case 5. The associated word is G. 

Let z be the intemediate vertex; note that it must be an object. Then u2 simply 

applies the grant rule to give a rights to z, and u 1 simply uses the take rule to acquire 

them. 

Case 6. The associated word is s. 

The following construction suffices. First, u 1 creates (tg to new) v: 

Then, u 1 grants (g to v) to z: 

Next, u2 takes (g to v) from z: 

After that, u2 grants (a to y) to v: 

Finally, u2 grants (a to y) to v: 
- 11 - 

a 

V 

In all cases, ui can acquire a rights to y using only the de jure rules; so by the 

definition of cun.share, cun.share(a, x, y, Gn) is true. This proves the induction step 

and hence the claim. 

(=.) Assume now cun~share(a, x, y, Gn) is true. By inspection of the de jure rules, 

none adds an incoming edge with right a to a vertex y unless there is already an edge 

with that right and with y as target; hence, there must exist a vertex s with an a edge 

to y in Go. 

Now consider the de jure rule applications pi, . . . , pn needed to produce a witness to the predicate in Gn. Without loss of generality, we may eliminate all instances 

of the remove rule, since that rule never adds edges, and without loss of generality we 

may reorder the rule applications so all create rules come at the beginning. We induct 

on the number n to prove the claim. 

BAS IS: If n = 1, then either the take or grant rule was used, since the create rule 

would not add a new edge to an existing vertex. The initiator must have been a subject by the nature of the rules. 

If the take rule was used, then, x initiated it and took from s a rights to y; in this 

case, if s is not a subject, choose rn = 1 and u 1 =x in the theorem. Conditions (i) and 

(ii) clearly hold, and condition (iii) trivially holds. On the other hand, if s is a subject, 

choose rn =2, u 1 =x , and u 2=y. Then all three conditions hold. 
- 12- 

Now suppose the grant rule was used. Then s initiated it and granted to x a 

rights to y. In this case, if x is not a subject, choose m = 1 and u 1 =s in the theorem. 

Conditions (i) and (ii) clearly hold, and condition (iii) trivially holds. On the other 

hand, if x is a subject, choose m=2, ui=x, and u2=y. Then all three conditions 

hold. 

In either case, candzure(a, x, y, Go)’s being true implies that all three conditions 

hold, as claimed. 

INDUCTIONHYPOTHESIS: For n=1,. . . ,k, if candure(a, x, y, Go) is true, 

then all three conditions hold. 

INDUCTION STEP: Let n =k+l and consider the rule pa. If it is a create rule, then 

there is an edge from x to y labelled a in Gn-1, since the create rule cannot add a new 

incoming edge to an existing vertex; in this case the induction hypothesis assures us 

that the three conditions hold. 

The proof that the claim holds for the take and the grant rules are very similar, so 

we present the one for take here. Suppose the rule pk+i is a take rule. For this rule to 

be applied to Gk, x must be a subject, the= must be an x-to-z edge labelled t, and a 

z-to-y edge labelled a for some vertex z in Gk. So can*share(t, x, z, Gk) and 

can~shre(a, z, y, Gk) both hold. 

If z exists in Go, it is clear that the predicates can&ure(t, x, z, Go) and 

can~share(a, z, y, Go) both hold. Condition (i) follows immediately from the first of 

these and the induction hypothesis, and condition (ii) from the second and the induction hypothesis. So, consider the first of those two predicates. By the induction 

hypothesis, there is a subject vertex z’ such that either z’=z or z’ terminally spans to 
- 13 - 

z (condition (ii).) By the second, there is a subject vertex z” such that either z”=z or 

z” initially spans to z (condition (i).) Note that by the definition of bridge, the path 

between z’ to z” is a bridge unless z’=z”. In either case, the union of the sets of 

uis of the two predicates provides the uis for canoshare(a, x, z, Go) between each is 

a tg-path with associated word in B . This proves condition (iii). 

If, on the other hand, z does not exist in Go (and therefore was created by one of 

the create rules), consider the graph Gc that exists after all create rules have been 

applied but before any other de jure rules have been used. The vertex z must lie in a 

subgraph connected to the original graph Go by one edge. Call the vertex lying on 

this edge and existing in Go, zo. Thus, there is a path between zo and z; moreover, 

by the nature of the create rule, this path is directed out of zo and towards z. Let 

zo, . . . , zrn =z be the vertices on the path. All but the last of them must be subjects 

(because each invokes the create rule to create the next one.) Further, the edge 

between z m-i and z must contain a t in its label, since no de jure rule adds an incoming edge with a right unless there is already an incoming edge with that right; so, if 

the edge in question did not have a t in its label, candmre(t, x, z, Gc) would be false. 

Also, since rights may only be transferred using the take and grant rules, the label of 

each edge in the path from zo to z must contain either a t or a g. By the induction 

hypothesis, then, can&ure(t, zo, z, Gc) is true. This means that either can.share(g, 

zo, x, Gc) is true or candzure(t, x, zo, Gc) is me. 

To show that can.share(a, 20, y, Go) is true consider a witness to can.share(a, 

z, y, Go). Append to that witness a take rule of the form “20 takes (a to y) from 2.’’ 

These rules produce a series of protection graphs generated by a sequence of de jure 
- 14- 

rule applications, and in the final one there is an edge labelled a from zo to y. But by 

definition, this means cun.share(a, 20, y, Go) is true. 

Now, if cuneshure(t, x, zo, Gc) is true, as zo exists in Go and can.shure(a, 20, y, 

Go) is me, we have already shown that all three conditions hold. A similar argument 

when cun.shure(g, 20, x, Gc) is true also shows that all three conditions hold. This 

proves the induction hypothesis for n =k + 1. 

Since the induction step is successful, the claim is proven. 0 

Return now to the picture discussed in the earlier section: 

P s‘ + 

U V W X Y 

In this picture, we can easily see that cun.share(a, p, q, Go) is true; take ui=p, 

u2=u, u3=w, u4=y, and u5=s’. Condition (i) holds as ui=p; condition (ii) holds 

as u5 terminally spans to s; and condition (iii) holds as all words associated with the 

paths betweenm the subjects are bridges. 

It should be clear why this theorem holds. Since an island is a set of subjects 

connected by edges labelled tuke and grunt, the vertices of the island involved in the 

sharing of the right are all connected by elements of B. Between each island is a 

bridge, and of come the associated words are in B. So the theorem in this section 

merely focuses attention on these vertices and ignores the others in the island. Similarly, the conditions in theorem 3 simply merge all subsequences of the uis that have 

no objects as part of the tg-path between them into an island. This reasoning can be 

made more formal to show: 
- 15 - 

Corollary 5: The conditions in theorem 3 hold if and only if the conditions in theorem 

4 hold. 

Of course, this theorem also preserves the following property: 

Corollary 6: Truth or falsity of the predicate cunwhure may be determined in linear 

time in the size of the initial graph. 

Let us now consider the transfer of information, and re-examine the proof of the 

predicate governing that type of transfer. or connection. 

4. Transfers of Information 

The de jure rules control the transfer of authority only; they say nothing about 

the transfer of information. The two are clearly different; for example, if a user is 

shown a document containing information which he does not have authority to read, 

the information has been transfered to the user. The de jure rules do not model cases 

like this. Instead, we use a different set of rules, called de facto rules, to derive paths 

along which information may flow. 

In order to describe transfers of information, we cannot use explicit edges, 

because no change in authority occurs. Still, some indication of the paths along which 

information can be passed is necessary. Hence, we use a dashed line, labelled by r, to 

represent the path of a potential de facto transfer. Such an edge is called an implicit 

edge. Notice that implicit edges cannot be manipulated by the de jure rules, since the 

de jure rules can affect only authorities recorded in the protection system, and implicit 

edges do not represent such authority. 

A protection graph records all authorities as explicit edges, so when a de jure rule 
- 16- 

is used to add a new edge, an actual transfer of authority has taken place. But when a 

de facto rule is used, a path along which information can be transferred is exhibited; 

the actual transfer may, or may not, have occurred. It is impossible to tell this from 

the graph, because the graph records authorities and not information. For the purposes 

of this model, however, we shall assume that if it is possible for information to be 

transferred from one vertex to another, such a transfer has in fact occurred. 

One set of proposed de facto rules was introduced in [l] to model the transfer of 

information. Although these are not the only rules possible, their effects have been 

explored, and so we shall use them. 

posr: Let x, y, and z be three distinct vertices in a protection graph Go and let x and z 

be subjects. Let there be an edge from x to y labelled a, where r E a, and an 

edge from z to y labelled p, where w E p. Then the post rule defines a new 

graph G 1 with an implicit edge from x to z labelled (r) . Graphically, 

VI-V .................. 

Y Y 

pass: Let x, y, and z be three distinct vertices in a protection graph Go, and let y be a 

subject. Let there be an edge from y to x labelled a, where w E a, and an edge 

from y to z labelled p, where r E p. Then the pass rule defines a new graph GI 

with an implicit edge from x to z labelled (r}. Graphically, 

V'";P" .................. 

., 

J Y 
- 17 - 

spy: Let x, y, and z be three distinct vertices in a protection graph Go, and let x and y 

be subjects. Let there be an edge from x to y labelled a, where r E a, and an 

edge from y to z labelled p, where r E p. Then the spy rule defines a new graph 

G 1 with an implicit edge from x to z labelled { r) . Graphically, 

Y Y 

find Let x, y, and z be three distinct vertices in a protection graph Go, and let y and z 

be subjects. Let there be an edge from y to x labelled a, where w E a, and an 

edge from z to y labelled p, where w E p. Then the find rule defines a new 

graph GI with an implicit edge from x to z labelled {r). Graphically, 

- 

Y Y 

Note that these rules add implicit and not explicit edges. Further, as these rules 

model information flow, they can be used when either (or both) of the edges between 

x and y, or y and z, are implicit. 

4.1. Information Flow in a Graph with Static Rights 

Now, consider the conditions necessary for a potential de facro transfer to exist in 

a graph. 

Definition: The predicate can.know.f(x, y, Go) is true if and only if there exists a 

sequence of graphs GI, . . . ,Gn (OSn), such that GiP Gi+l (Oli<n) by one of the 

de facto rules and in Gn either a x-to-y edge labelled r exists or a y-to-x edge labelled 
- 18 - 

w exists and if the edge is explicit, its source is a subject. 

Intuitively, cunoknow~f(x, y, Go) is true if and only if x has the authority to read 

y, y has the authority to write to x, or an implicit edge from x to y can be added by 

means of the de facto rules. Note the duality of read and write. If x can write to y, 

then y effectively can read x. All x has to do is write to y any information that y 

wants to see. This duality will play an important role in later results. 

Definition: An wputh is a nonempty sequence v 0, . . . , vk of distinct vertices such 

that for all i, OSick, vi is connected to vi+i by an edge (in either direction) with a 

label containing an r or a w. 

With each rw-path, associate one or more words over the alphabet { r', F, $, k 

in the obvious way; for instance, the protection graph 

has associated PfW and *%. If the path has length 0, then the associated word is 

the null word v. 

Definition: An rw-path vo, . . . ,vk, k21, is an admissible ru-path if aid only if it 

has an associated word a 142 * - ak in the regular language (Fb%)*, and if ai=? then 

Vi-1 is a subject and if ai& then Vi is a subject. 

Note that there cannot be two consecutive objects on an rw-admissible path. Given 

these definitions, 

Theorem 7: Let x and y be vertices in a protection graph Go. Then cun.know.f(x, y, 

Go) is true if and only if there is an admissible rw-path between x and y. 
- 19 - 

4.2. Information Flow in a Graph with Changing Rights 

These results can be extended to include both de jure and de facto rules. To do 

so, we must define terms combining characteristics of those used in both the de jure 

and de facto developments. 

Definition: The predicate caneknow(x, y, Go) is true if and only if there is a sequence 

of protection graphs GI, . . . ,Gn such that GoC* Gn and in Gn either a x-to-y edge 

labelled r exists, or a y-to-x edge labelled w exists and, if the edge is explicit, its 

source is a subject. 

This is merely caneknowefTX, y, Go) without the restriction on the types of rules 

used. 

Definition: An rwtg-path is a nonempty sequence vo, . . . ,vk of distinct vertices 

such that for all i , OIi <k, v i is connected to v i+l by an edge (in either direction) with 

a label containing a t, g, r, or a w. 

With each rwtg-path, associate one or more words over the alphabet 

4++ c { t, t, g, g, P, F: $, 6 } in the obvious way. 

Definition: The vertex vo nv-initially spurn to vk if vo is a subject and there is an 

rwtg-path between vo and v A with associated word in { i'. i3 }. 

Definition: A vertex vo rw-terminally spans to VA if vo is a subject and there is an 

rwtg-path between v 0 and v A with associated word in { i'.? }. 

Definition: A bridge is an rwtg-path with associated word in the regular language 

++- +t) B= { ?* uY* u t*gt* u t*gt* } 

(Note that this is the same as the definition given earlier in this section.) A connection 
I' - 20 - 

is an rwtg-path with associated word in the regular language 

C={7*7u#ij7* u7*m7* } 

We can characterize the set of graphs for which can.kmw is true: 

In order to appreciate these results, let us now look at some examples of the uses 

of the rules; these will be useful in deriving our later results. These two results are 

quite basic, and state that there is a bridge or connection between two subjects, either 

can (with the co-operation of the other) read information from the other. More formally: 

Lemma 8: If there is a bridge from x to y, then x can obtain an implicit read edge to 

Proof: By the take rule and the definition of bridge, it suffices to prove the Iemma for 

bridges of length 2 or less. Six cases arise. 

Case 1: First, y creates (M to new vertex) z: 

X Y X Y Z 

Ac 

Then, x takes (M to z) from y: 

IM 

Finally, x and y use the post rule: 
- 21 - 

Case 2: First, x creates (rw to new vertex) z: 

+bLaz/=b 

X Y Z X Y 

Then, x grants (m to z) to y: 

Finally, x and y use the post rule: 

Case 3: First, x creates (M to new vertex) v: 

Z Z 

Next, x grants (m to v) to z: 

Then y takes (M to v) from z: 
Then y takes (m to v) from z: 

- 22 - 

Case 4: 

see case 1 f 

X Y 

Case 5: 

&? see case 2 

X Y 

Case 6: 

In all cases, x gets implicit read rights over y, proving the claim. 0 

Lemma 9: Let x and y be subjects with a bridge or connection between them. Then 

at least one of the following is true: 

(i) an explicit read edge from x to y exists or may be added; 

(ii) an implicit read edge from x to y may be added; or 

(iii) an explicit write edge from y to x exists or may be added. 

Proof: If there is a bridge between x and y, case (i) holds by lemma 8. So, suppose 

there is a connection from x to y. If the associated word is in t*?, by using the take 

rule, x can obtain an explicit read edge to y, establishing case (i). If the associated 

-+ 
- 23 - 

word is in 6*, by using the take rule, y can obtain an explicit write edge to x, establishing case (iii). If the associated word is in i)SM*, x and y can each apply the take 

rule until x obtains a read edge to a vertex to which y has a write edge (or vice versa); 

then x and y can use the post rule to add an implicit read edge from x to y (case (ii).) 

0 

5. Statement and Proof of cumknow 

The following theorem was presented in [l]; the proof has been expanded upon 

here. 

Theorem 10: The predicate cun.know(x, y, Go) is true if and only if there is a 

sequence of subjects u 1, . . . , u m such that all of the following conditions hold simultaneously: 

(i) u 1 =x or u 1 rw-initially spans to x; 

(ii) u m =y or ~m rw-terminally spans to y; and 

(iii) for all i (1 Si ern), there is an rwtg-path between u i and u i+l with an associated word in B yC. 

proof: (e) Assume the three conditions hold. By lemma 9, if p and q are subjects 

joined by an mtg-path with associated word in BuC, then one can add an implicit 

read edge between them. Once this is done, there is an rw-admissible path from x to 

y; by theorem 7, this is a necessary and sufficient condition for can.know(x, y, Go) to 

be true. 

(+) Assume can.know(x, y, Gn) is true. If a witness can be found by applying de 

jure rules only, then can.share(r, x, y, Go) is true. Let v 1, . . . , v be the sequence 
of subjects in theorem 4 instanl 

- 24 - 

iting that predicate, and le s be the vertex with an r 

edge to q. Taking rn=n+l, ui=Vi for ISiSn, and Un+l=S (if s is a subject) or 

rn =n and u i =vi for 1 Si Sn (if s is an object), conditions (i), (ii), and (iii) follow 

immediate1 y. 

So suppose at least one de facto rule application had to be used. Since de jure 

rules do not manipulate implicit edges, we may without loss of generality reorder the 

rule applications so that all de jure rules precede all de facto rules. It follows by 

theorem 7 that there exists an rw-admissible path in the graph resulting from the application of the de jure rules but before any de facto rules are applied. Let 

x =v 0, . . . , v 1 = y be the vertices on that path. We now show by induction on the 

length I of the path that the desired conditions hold. 

BAS IS: Let I = 1. Then by the definition of an rw-admissible path, either x is a subject and rw-terminally spans to y, or y is a subject and rw-initially spans to x. In the 

first case, take n = 1 and x =u 1 in the claim to see that conditions (i) and (ii) are true 

and condition (iii) is trivially true; in the other case, take n = 1 and y =u 1 in the claim 

to see once again that conditions (i) and (ii) are true and condition (iii) is trivially true. 

INDUCTION HYPOTHESIS: For 1 =1, . . . ,k, if can.know(x, y, Go), then the three 

conditions hold. 

INDUCTION STEP: Let l=k+l and consider which de facto rule was applied to 

produce the witness. What follows assumes that the rule application pi wis a spy rule; 

the proofs for the other rules are similar. 

If z exists in Go, that the spy rule was used means there is an (implicit or explicit) edge from x to z, and an (implicit or explicit) edge from z to y. If the edge from x 
- 25 - 

to z is explicit, theorern 4 gives us condition (i) (take u i=x in that theorem.) If it is 

implicit, since z and y are distinct (by definition of the spy rule), we may apply the 

induction hypothesis to obtain condition (i). Similarly, regardless of whether the edge 

is implicit or explicit, either theorem 4 or the induction hypothesis gives us condition 

(ii). Finally, condition (iii) follows from either the induction hypothesis or theorem 4 

(remember, condition (iii) requires the edge labels to be in a subset of what condition 

(iii) requires) or both. 

Now suppose z does not exist in Go. Then by the nature of the create rule, z 

must be in a subgraph connected to the vertices in Go by a single edge; moreover, 

there is a path zo, . . . ,z~=z with edges from Zi to Zi+l, and for Oli<m, Zi is a 

subject. If the edge from x to z is explicit, this means that by theorem 4, as zo lies on 

all possible paths from x to z, one of can.share(g, zo, x, Go) and can.share(t, x, zo, 

Go) is true. In either case, as x and zo are subjects, by lemma 8, can.know(x, zo, Go) 

is true. On the other hand, if the edge from x to z is implicit, since z and y are distinct (by definition of the spy rule), we may apply the induction hypothesis to show 

can.know(x, zo, Go) is true. The three conditions follow immediately. 0 

An example will perhaps clarify what the theorem says. Consider the graph: 

X Y Z 

Take ui=p, u2=x, u3=z, and u4=s. s indeed rw-terminally spans to q, and 

between each pair of uis there is a bridge (between x and q, and between s and z) or 

connection (between x and z). In this case, therefore, can.know(p, q, Go) is true. In 
- 26 - 

fact, the following witnesses the predicate: 

(1) z takes (I to q) from s; 

(2) x grants (r to y) to p; 

(3) p and z use the post rule to add an implicit edge labelled I from p to z; 

(4) p and z use the spy rule to add an implicit edge labelled r from p to q. 

However, note that cun.share(r, p, q, Go) is false because the= is no bridge between 

x and z. 

6. An Alternate Statement of cunaknow 

Earlier, we gave a statement of the necessary and sufficient conditions for 

cunoshure to be true that is quite similar to the conditions for cun.know to be true. In 

this section, we prove a symmetric result, namely that the conditions for cun.know to 

be true may be stated in a form quite similar to the original statement of the theorem 

for cumknow. The theorem relies upon lemma 9, which states a set of conditions that 

must be met before caneknow is true. Hence, the theorem given next really only tries 

to establish when there will be a series of bridges or connections from a vertex q to 

another vertex p along which information can be sent. 

Theorem 11: Let p and q be vertices in a protection graph Go. Then can.know(p, q, 

Go) is true if, and only if, canoshare(r, p, q, Go) is true or all of the following conditions hold: 

(i) There is a subject p’ such that p’ = p or p’ is m-initially connected to p; 

(ii) There is a subject q’ such that q’ = q or q’ is m-terminally connected to q; 
- 27 - 

(iii) There is a sequence of islands {Ij I 1 Sj Sm} such that there is a bridge or 

COMWtiOn from Ij to Ij+1, 1Sj Sm, and p’ E II, and q’ E Im. 

Infoml argument: To prove the “if“ part, note that if cun.share(r, p, q, Go) is true 

then by definition cun.know is true. If not, condition (i) says that p’ can send any 

infoxmation it gets to p, and part (ii) says that q‘ can obtain any information it needs 

from q. Condition (iii) simply says that q’ can send the information to a vertex z 1 in 

Im-1, which can in turn send it to a vertex 2.2 in Im-2, and so on, until a vertex Zm-1 

in I1 gets the information. By the properties of an island, this means that p’ can get 

the information. Putting all this together, cun.know is true. 

Going the other way involves considering the rule applications needed to produce 

a witness. We can require all de facto rules to be applied last, and examine the conditions needed for them to be applied. For example, in the pass rule, there is a vertex y 

for which cun.share(w, y, p, Gn) and cun.share(r, y, p, Gn) are true. From the conditions required for both cun.share rules to hold, the three condition of the theorem 

must be true. (In the formal proof, we will show this for the post and spy rules; the 

formal proof for the pass and find rules are left as an exercise for the rezder.) And if 

no de facto rules are used to generate a witness to can.know, obviously can.share(r, p, 

q, Go) is true. 

Pro& (e) Consider condition (i). As p ’ is rw-initially connected to p, it either has or 

can obtain (through the take rule) a write edge to p. Similarly, by condition (i), if q’ 

is rw-terminally connected to q, it either has or can obtain (using the take rule) a read 

edge to q. Thus, it suffices to show cun.know(p’, q’, Go) is true by condition (iii); 

merely apply the spy rule (if q’#q), and then the post rule (if p’zp), to obtain 
- 28 - 

cun*know(p, q, Go). 

We show condition (iii) implies cun.know(p’, q‘, Go) by inducting on rn, the 

number of islands in that condition. 

BASIS: Let rn = 1. Then p’ and q’ are in the same island, whence by cases 1, 2, 4, 

and 5 of lemma 8, cun.know(p’, q’, Go) is true. 

INDUCTIONHYPOTHESIS: For rn = 1 , . . . , k, if condition (iii) holds, 

cun.know(p’, q’, Go) also holds. 

INDUCTION STEP: Let rn = k + 1. Let zk be the subject in Ik that bounds the 

bridge or connection between Ik and Ik+i; let z~+i be zk’s counterpart in k+i. By 

lemma 9, cun.know(zk+i, q’, Go) holds; by lemma 8, this means cun.krww(zk, q’, 

Go) holds; and by the induction hypothesis, cun.know(p’, zk, Go) holds; whence by 

the spy rule, cun.know(p’, q’, Go) is true. This proves the induction hypothesis, and 

hence the “if” part of the theorem. 

(*) Now assume cun.know(p, q, Go) is true, and consider a minimal set of rule applications pi needed to produce a witness. Without loss of generality, we may reorder 

the pi’s so that all de jure rule applications precede any de facto rule applications, 

since de facto rule applications do not change the state of the protection graph. If no 

de facto rules are applied, the witness will end with an explicit read edge from p to q, 

in which case cun.share(r, p, q, Go) holds; the three conditions then follow from 

theorem 3. So suppose that at least one de facto rule application is needed. 

Induct on the number rn of such de facto rule applications. 

BASIS: Let rn = 1. Each of the de facto rules must be considered. We will give the 

proof for the post rule; the other rules are treated similarly. 
- 29 - 

Consider the post rule. In order to apply this rule, there must be a vertex x SI :h 

that can*share(r, p, x, Go) and camshare(w, q, y, Go) are true. By theorem 3, this 

means that there is a sequence of islands 11 , . . . ,1j with p E 11, and a vertex a E 1, 

which terminally spans to another vertex a ’, which has a read edge to x: 

Similarly, there is a sequence of islands Ji , . . . , Jk, With q E Jk, and a vertex 

b E J1 which terminally spans to another vertex b‘, which has a write edge to x: 

bridge ... 0-0 

Jk-i Jk 

Now, combining these two facts, relabel the islands Ji , . . . , Jk as 

Ij+i , . . . ,Ij+k. Note that, as a terminal span has associated word in 3, we have a 

connection from a to b: 
- 30 - 

Qrwy-iO 

X JI = Ij+l Ij 

This is condition (iii). Taking p’ = p and q’ = q , conditions (i) and (ii) hold. 

INDUCTION HYPOTHESIS: Let rn = 1 , . . . , k. Then after n de facto rule applications, if cun~krww(p, q, Go) is true, conditions (i), (ii), and (iii) hold. 

INDUCTION STEP: Let n = k + 1, and assume the k+lst rule applied is a spy rule 

(proofs for the other three rules are similar.) 

As the spy rule is used, p is a subject, and there is a subject vertex x such that 

cun.know(p, x, Go) and cun*know(x, q, Go) are true. By the induction hypothesis, the 

first caneknow ensures that there is a subject p’ such that p ’ = p or p’ nu-initially 

spans to p, giving condition (i); the second cunekmw ensures that there is a subject q ’ 

such that q’ = q or q’ nu-terminally spans to q, giving condition (ii). By the induction hypothesis, condition (iii) is assumed to hold for both cun.know(p, x, Go) and 

cun.know(x, q, Go). So, let I1 , . . . , Ij and Ji , . . . , Jk be the sets of islands for 

can.know(p, x, Go) and cun.know(x, q, Go), respectively. Thus, the configuration is: 

I1 Ii 

0- connection *** 0 I connection 0- 

Jk 

connection .-. 0 

Ji 
- 31 - 

span between subjects is a connection. This establishes condition (iii), proving the 

induction hypothesis and the claim. 

Hence, theorem 11 has been proven. 

Let us return to the example of the previous section. 

Take p'=p, q'=s, Il={ p,x }, and12={ s,a }. As s indeed rw-terminally spans 

to q, and there is a connection between I1 and 12, can&zow(p, q, Go) is true, agreeing 

with our previous result. 

It should be clear that this theorem and the one presented in the previous section 

are equivalent. As cases 1, 2, 4, and 5 of lemma 8 show, if there is an edge between 

two subjects labelled t or g an implicit edge labelled r can be added between those 

vertices. Hence in addition to being a subgraph in which rights may be freely 

transferred, an island is also a subgraph in which information may be freely transferred 

assuming all subjects co-operate. (If not, other conditions apply; see [2].) Hence, the 

islands connected by bridges and connections ensures that provides a sequence of subjects connected by bridges and connections along which information can flow, as condition (v) requires. Hence the conditions in theorem 11 being true implies the conditions in theorem 10 are true. Similarly, the sequence of subjects in theorem 10 may 

be grouped into islands (if need be, the islands may contain only one vertex) to obtain 

the conditions €or theorem 11. This reasoning can be made more formal to show: 
- 32 - 

Corollary 12: The conditions in theorem 10 hold if and only if the conditions in 

theorem 11 hold. 

Of course, this theorem also preserves the following property: 

Corollary 13: Truth or falsity of the predicate cawknow may be determined in linear 

time in the size of the initial graph. or connection. 

7. Discussion and Future Directions 

One of the more strinking feature of these theorems is the similarity betweem 

theorems 3 and 11, and between theorems 4 and 10. Let us look at’the first two in 

some detail. 

Take the capability represented by the s-to-x edge in theorem 3 to be a piece of 

information. Then the only difference between the two theorems lies in the nature of 

the paths along which the information is transmitted; if the information is a capability, 

the class of paths is much smaller than if it were ordinary information. This makes 

sense, because one of the characteristics of capabilities is that “ ... no ordinary program 

can manufacture or modify the bit pattern with which a capability is represented” [3]. 

Capabilities are very special pieces of information, and cannot be handed around like 

the contents of a file. So, in the TakeGrant Protection Model, the de jure rules manipulate the flow of capability information, and the de facto rules implement the flow of 

all other types of information. 

This suggests two things. In [6], the notion of classifying subjects into groups 

was explored in the context of “groups of users.” One could extend the classification 

to quantities to be controlled, and provide several different sets of rules, each set 
- 33 - 

describing the flow of that quantity throughout the graph. One would then have to 

discuss the interactions of the different rules and the quantities as the rules were 

applied. Interestingly enough, only the flow of capabilities would change the explicit 

edges in the graph, since the graph is designed to abstract only the capabilities; in 

some instances, a new graph might have to be defined. (This has been done with the 

de facto rules and the implicit edges; when one deals with implicit edges, one uses a 

“pseudo-graph” with dashed arrows representing edges that “really aren’t there.”) 

Continuing on in our speculations, since the characterization of the transfer of 

capabilities and information is so similar, the idea of a “meta-theorem” that captures 

the generalized notion of “sharing” immediately suggests itself. This theorem, and a 

corresponding one for the predicates describing the theft of information and rights, 

would be broad enough to incorporate the extensions to the model that deal with information flow of all kinds, classes of information and subjects, and so forth. Such 

theorems would be a step forward in making Take-Grant type protection models practical and useful. 

References 

1. 

2. 

3. 

4. 

5. 

Bishop, M. and Snyder, L., “The Transfer of Information and Authority in a 

Protection System”, Proceedings of the Seventh Symposium on Operating System 

Principles, 45-54 (December 1979). 

Bishop,, M., Practical Take-Grant Systems: Do They Exist?, Ph. D. Thesis, 

Purdue University, May 1984. 

Fabry, R., “Capability-Based Addressing”, Communications of the ACM, 17, 7 

Harrison, M., Ruzzo, W. and Ullman, J., “Protection in Operating Systems”, 

Communications of the ACM, 19, 8 (August 1976) 461-471. 

Jones, A., Lipton, R. and Snyder, L., “A Linear Time Algorithm for Deciding 

Security’ ’, Proceedings of the Seventeenth Annual Symposium on Foundations of 

Computer Science, (1976). 

(July 1974) 403-4 12. 
- 34 - 

6. Lipton, R. and Snyder, L., “A Linear Time Algorithm for Deciding Subject 

7. Snyder, L., “Theft and Conspiracy in the Take-Grant Protection Model”, Journal 

8. Snyder, L., ‘‘Formal Models of Capability-Based Protection Systems”, IEEE 

Se~Urity”, Jo~rnaI of the ACM, 24, 3 (July 1977) 455-464. 

of Computer and System Sciences, 23, 3 (December 1981) 333-347. 

Transactions on Computers, C-30, 3 (March 1981) 172-181.