APPLYING THE TAKE-GRANT PROTECTION

MODEL

Matt Bishop

Technical Report PCS-TR90-151



Applying the Take-Grant Protection Model

Matt Bishop

Department of Mathematics and Computer Science

Dartmouth College

Hanover, NH 03755

ABSTRACT

The Take-Grant Protection Model has in the past been used to model multilevel security hierarchies and simple protection systems. The models are extended to include theft of rights and sharing of information, and additional security policies are

examined. The analysis suggests that in some cases the basic rules of the TakeGrant Protection Model should be augmented to represent the policy properly;

when appropriate, such modifications are made and their effects with respect to the

policy and its Take-Grant representation are discussed.

Keywords: theoretical foundations, Take-Grant Protection Model, security policy,

isolation, multilevel security.

1. Introduction

The Take-Grant Protection Model [12][15] is one of a number of abstract formulations of

protection systems. Like other such models, it is primarily a theoretical tool used to analyze the

safety question; unlike other models, it presents a framework in which that question is answered

"yes," and enables the derivation of results indicating the conditions under which rights can be

transferred as well as the complexity of determining whether or not those conditions hold in a particular system. Because of these characteristics, if it could be used to analyze an abstract model of

an existing or proposed system, it would be possible either to prove in that model that rights could

be transferred, or that they could not be.

In this, it differs from other formal models of protection. The access control matrix model

[8][ 10][14] is a matrix-oriented description of the rights that subjects, or actors, have over objects,

or passive entities. It is a very general model that does not consu'ain in any way the set of commands that may be used to manipulate rights. As one would expect, answering the safety question

using such a system is quite complex, and for the most general case, it is undecidable. However, if

the commands are mono-conditional (or monooperational), the safety question can be answered.

The difference between this model and Take-Grant is that Take-Grant explicidy states four rules

Portions of this work were supported by a Burke Award fi'om Dartmouth College.

Page 1 of 26
controllingthe propagation of rights, and four rules and information, and so -- even though those

rules are not mono-operational -- the safety question can be answered.

The schonatic protection model [17] is another model of protection which, like the access

control matrix model, focuses on the issue of being able to answer the safety question and not determining necessary and sufficient conditions for sharing rights or information. Like the access

control matrix model, it presumes no rules for propagation of rights, and ignores completely the

questions of theft of rights and propagation of information.

Those questions have been studied extensively in the Take-Grant Protection Model. Work

by Snyder [20] on the transfer of rights without the cooperation of the owner of those rights extended the results about sharing to situations of theft; work by Snyder and Bishop [4] introduced

the notion of information flow and transfer into the model, and recent work by Bishop [3] presented

results about the theft of information. Bishop [2], Jones [11], Snyder [18], and Wu [21] have applied the model to some existing computer systems and simple security policies. The contribution

of this paper is the expansion of some of those representations to include theft of rights and the

sharing of information as well as representing some new policies. We begin by briefly reviewing

the Take-Grant Protection Model, and then derive a simplification of one of those results, which

will make analysis of the security policies in the following section much simpler. We analyze the

security policies of complete isolation, the owner having the ability to share rights nd information,

a multilevel security policy, and a tree-based hierarchical policy such as is found in many computer

systems. Finally, we conclude with some discussion and suggestions for future work.

2. The Basic Take-Grant Protection Model

We present this section as background into the model; the reader desiring a more complete

presentation should turn to the references. On the other hand, the reader familiar with the model is

encouraged to turn to the next section!

The Take-Grant Protection Model represents systems as graphs. The vertices are of two colors: subjects correspond to the active nodes such as processes, and objects correspond to the passive entities as files. (In modelling a system, representing an entity may not be straightforward; for

example, a segment of memory might be an object when not in use, but a subject when being executed. We treat this as a point of interpretation and hence beyond the scope of this paper.) Edges

connecting these nodes are labelled with sets of fights; these sets are subsets of a finite set of rights

which for this description we shall take to be R = { t, g, r, w}, where t represents the take right,

Page 2 of 26
g the gram right, r the read right, and w the write right. Application of the fights is modelled by

applying graph rewriting rules, which either change the protection state of the graph( de jure rules)

or provide a representation of how information flows throughout the system (de facto rules).

In protection graphs, the subjects are represented by • and objects by O. Vertices which

may be either subjects or objects are represented by ®. 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 a graph rewriting rule on the graph preceding it. The symbol I--* represents several rule applications. The term witness means a sequence of graph rewriting

rules which produce the predicate or condition being witnessed, and a wimess is often demonstrated by listing the graph rewriting rules that make up the wimess (usually with pictures).

The de jure rules manipulate edges (and vertices) in the graph. They are:

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 _, and a _ 13.

•Then the take rule defines a new graph G! by adding an edge to the protection graph from

x to z labelledoz.Graphically,

x y z

(X

x y z

grant:

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

Let x, y, and z be three distinct vertices in a protection graph G 0, and let x be a subject. Let

there be an edge from x to y labelled ¥ with g ¢ ¥, an edge from x to z labelled _, and ct _ 13.

Then the grant rule defines a new graph G 1 by adding an edge to the protection graph from

x toz labelled¢x.Graphically,

Y x z

(X

Y x z

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

Page 3 of 26
create: Let x be any subject in a protection graph G Oand let a _ R. Create defines a new graph G 1

by adding a new vertex y to the graph and an edge from x to y labelled a. Graphically,

X X Z

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

remove: Let x and y be any distinct vertices in a protection graph G 1 such that x is a subject. Let

there be an explicit edge from x to y labelled [1, and let a _ R. Then remove defines a new

graph Gl by deleting the a labels from [3. If It becomes empty as a result, the edge itself is

deleted. Graphically,

X Z X Z

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

The edges which appear in the above graph 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 t or g is between two subjects. Specifically, with the cooperation of both

subjects, rights can be transmitted backwards along the edges. The following two lemmata [12]

demonstrate this:

/.,emma 1.

t Ct

y x z

CZ

Y X Z

_ 2.

y x z

Y X Z

As a result, when considering the transfer of authority between cooperating subjects, neither direction nor label of the edge is important, so long as the label is in the set { t, g }.

Definition. A tg-path is a nonempty sequence v0, .... v n of distinct vertices such that for all i,

0 < i < n, v i is connected to vi+ 1 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.

Page 4 of 26
Definition. Vertices are tg-connected ff there is a tg-path between them.

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

Any fight 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 subjects which possess common fights. With each tgpath, associate one or more words over the alphabet {_, i, _, _] in the obvious way. If the path has

length O, then the associated word is the null word v.

Definition. A vertex v 0 initia//y spans to v n if v 0 is a subject and there is a tg-path between v 0 and

v n with associated word in {_*_} u {v].

Definition.A vertex v0 terminallyspans to vn ifv0 isa subjectand thereisa tg-pathbetween v0

and vn with associated word in { _* }.

Definition. A bridge is a tg-path with v0 and v n both subjects and the path's associated word in

}.

The following predicate formally defines the notion of tranxferring authority.

Definition. The predicate can.share(o, x, y, G 0) is u'ue for a set of fights ot and two vertices x and

y if and only if there exist protection graphs G 1, ..., G n such that G Ob-*G n using only de jure rules,

and in G n there is an edge from x to y labelled o.

In short, if x can acquire ot rights over y, then can.share(_ x, y, G 0) is true. The theorem

which establishes necessary and sufficient conditions for this predicate to hold is [ 15]:

Theorem 3. The predicate can.share(o_ x, y, GO) is true if and only if there is an edge from x to y

in G Olabelled o_, or if the following hold simultaneously:

(3.1) thereisavertexs_ G0 with an s-to-y edge labeLled _

(3.2) there exists a subject vertex x" such that x" = x or x" initially spans to x;

(3.3) thereexistsa subjectvertexs"such thats"= s or s"terminallyspans tos;and

(3.4) thereexistislandsIi,...,In such thatp" isinIl,s"isinIn,and thereisa bridge from

ljtoij+l (l <j<n).

Finally, if the right can be transferred without any vertex which has that right applying a

rule, the fight is said to be stolen. Formally:

Definition. The predicate canosteal(_ x, y, G 0) is true if and only if there is no edge labelled o_from

x to y in G 0' there exist protection graphs G 1, ..., G a such that G O b-*G a using only de jure rules,

Page 5 of 26
in G n there is an edge from • to y labelled a, and ff there is an edge labelled a from s to q in G 0'

then no rule has the form "s grants (a to q) to z" for any z E Gj (1 <j < n).

Essentially, this says that can.steal is u'ue if can.share is true, the thief did not have the

right initially, and no owner of the right in the initial graph gave it away. It can be shown [17]:

Theorem 4. The predicate can.steal(a, x, y, G 0) is true if and only if all of the following hold:

(4.1) there is no edge labelled a from x to y in G0;

(4.2) there exists a subject vertex x" such that x" = • or x" initially spans to x;

(4.3) there is a vertex s with an edge from s to y labelled a in GO;

(4.4) can,share(t, x', s, G 0) is true.

The de facto rules differ from the de jure rules in that they do not alter the authorities in the

graph; they merely record patterns of information flow, so we cannot use an explicit edge to show

the result of the application. Sdll, some indication of the paths along which information can be

passed is necessary so 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 de jure rules, since the de jure rules can only affect authorities recorded in the protection

system, and implicit edges do not represent such authority.

The following set of de facto rules was introduced in [4] to model the transfer of information:

post: Let x, y, and z be three distinct vertices in a protection graph GO, and let • and z be subjects.

Let there be an (implicit or explicit) edge from • to y labelled a with r ¢ (x and an edge

from z to y labelled [_, where w _ [3. Then the post rule defines a new graph G 1 with an

implicit edge from • to z labelled r. Graphically,

r

.o°..... ........... _-*.o....,

W wwme'' "*_l

O r_---_ _ ['- 6_

• y z

• y z

The rule is written "z posts to • through y," and is so named because it is reminiscent of y

being a mailbox to which z posts a letter that • reads.

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 • labelled a with w ¢ a and an (implicit or explicit) edge from

Page 6 of 26
y to z labelled[3,wherer e

edge from x to z labelled r. Graphically,

_. Then the pass rule defines a new graph G 1 with an implicit

r

114/ r t/ '_

x y z

x y z

The rule is written "y passes from z to x," and is so named because y acquires the information from z and passes it on to x.

spy: Let x, y, and z be three distinct vertices in a protection graph G 0' and let x and y be subjects.

Let there be an (implicit or explicit) edge from x to y labelled ¢t with r ¢ 0t and an (implicit

or explicit) edge from y to z labelled [3, where r _ 13.Then the spy rule defines a new graph

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

r

°..°...---_......

,,_,.-'° "'*..,°

-- r =_.,.-- r _ I-- _Lr_r_ "'" '"t

x y z

x y z

The rule is written "x spies on z using y," and is so named because x is "looking over the

shoulder" of y to monitor z.

find: Let x, y, and z be three distinct vertices in a protection graph G 0, and let y and z be subjects.

Let there be an edge from y to x labelled ¢¢ with w E C¢and an edge from z to y labelled [_,

where w _ 15. Then the spy rule defines a new graph G 1 with an implicit edge from x to z

labelled r. Graphically,

r

®=w e Ix y z x y z

The rule is written "x finds from z through y," and is named because x is completely passive; z and y give it information, which x then "finds."

Note that these rules add implicit and not explicit edges. Further, as these rules model information flow, they can also be used when any edge labelled r is implicit.

Definition. An rwtg-path is a nonempty sequence v O, .... v a of distinct vertices such that for all i,

0 < i < n, v i is connected to vi+ 1 by an edge (in either direction) with a label containing t, g, r or w.

Page 7 of 26
With each rwtg-path, associate one or more words over the alphabet { _, i, _, g, _, r, _, w}

inthe obvious way.

De:nition.A vertexv0 rw-initiallyspans to vn ifv0 isa subjectand thereisan twig-path between

v0 and vn with associatedword in {_*_} u {v}.

De]inition.A vertexv0 rw-term/na//yspans tovn ifv0 isa subjectand thereisan rwtg-pathbetween

v0 and vn with associatedword in {}*_}.

De)_nition.A connection isan rwtg-path with v0 and vn both subjectsand the path's associated

word in C = {}*_, _i*, }*i'_i*}.

De3_nition.The predicatecansknow(x, y,GO) istrueifand only ifthereexistsa sequence of protectiongraphs G 0,...,G n such thatG O _-*G n,and inG n thereisan edge from x to y labelledr or

an edge from y tox labelledw, and iftheedge isexplicit,itssource isa subject.

In short,ifx can obtainan implicitor explicitedge labelledr toy,then cansknow(x, y,GO)

istrue.The theorem establishingnecessaryand sufficientconditionsforcansknow to hold is[4]:

Theorem 5. The predicatecansknow(x, y,GO) istrueifand only ifthereexistsa sequence of subjectsu!....,u n in G O (n > I)such thatthe following conditionshold:

(5.1) u I = x or u! rw-initiallyspans tox;

(5.2) u n = y or u n rw-terminallyspans toy;

(5.3) for alli,I < i< n, thereisan twig-path between ui and ui+I with associatedword

inBuC.

We definean information analog tothe can.stealpredicatein which verticeswith r rights

over the targetdo not grantthoserightstoothersnor participatein transfersof information.

Dej_nition.The predicatecanssnoop(x, y,GO) istrueifand only ifcanssteal(r,x, y,GO) istrueor

thereisa sequence of graphs and ruleapplicationsG O $--*G n forwhich allof thefollowing hold:

(a) thereisno explicitedge from x toy labelledr inGO;

(b) thereisan implicitedge from x toy labelledr in Gn; and

(c) neithery nor any vertexdirectlyconnected toy isan actorin a grantruleor a de facto

ruleresultinginan (explicitor implicit)read edge with y as itstarget.

Necessary and sufficientconditionsforthispredicateto hold are [3]:

Page 8 of 26
Theorem 6. For distinct vertices x and y in a protection graph G O with explicit edges only, the predicate canosnoop(x, y, G 0) is gue if and only if canosteal(r, x, y, GO) is true or all of the following

conditions hold:

(6.1) there is no edge from x to y labelled r in GO;

(6.2) there is a subject vertex x" such that x" = x or x" rw-initially spans to x in GO;

(6.3) there is a subject vertex y" such that y" _ y, there is no edge labelled r from y" to y

in G 0, and y" rw-terminally spans to y in GO; and

(6.4) can*/mow(x', y', G 0) is true.

We now consider an alternate formulation of can*share that will aid us in applying the

Take-Grant Protection Model to various security policies.

3. Alternate Characterizations of canoshare and canoknow

The simplicity of the statement for necessary and sufficient conditions for canaknow leads

one to wonder why equally straightforward conditions cannot be found for canoshare. A moment's

reflection will lead to the following:

/.emma 7. The predicate canoshare(_ x, y, G 0) is true if and only if there is a vertex s¢ G Owith an

edge to y labelled ¢z, and a sequence of subjects u I, .... u a such that all of the following hold simultaneously:

(7.1) u I = x or u 1 initially spans to x;

(7.2) u a = s or un terminally spans to s; and

(7.3) there is a tg-path between u i and ui+ 1 for all i such that 1 _<i < n.

Proof: (=¢) Assume canoshare(a, x, y, GO) is true. By (3.1), there is a vertex s _ G o with an edge

to y labelled ¢z; by (3.2), there is a vertex u 1 satisfying (7.1), and by (3.3) there is a vertex u n satisfying (7.2).

Consider now condition (3.4). Let bj and ej be the endpoints in lj of the bridges connecting

islands lj. 1 withljandlj with lj+l, respectively. From theorem 1, we have x'fb I and y"=e n. Now,

let bj = zjl, ..., zfl_ = ej be any path contained entirely in lj. Then the members of the set

{ z/l l <_j¢Zn, l <-i<-kj }

are the vertices ui, 1 _<i <_n, and (7.3) holds.

Page 9 of 26
(¢=) Now assumethat there is a vertex s e G O with an edge to y labelled a, and a sequence of

subjects ul,...,um such that (7.1)-(7.3) hold. Then (3.1) holds by assumption, (3.2) by choosing x"

= u 1, and (3.3) holds by choosing s" = un.

Finally, note that vertices in the same island have a bridge of length 1 between them, so if

u i and ui+ 1 are directly connected, they belong to the same island, and ffnot (i.e., there are objects

on the bridge connecting them), then they belong to different islands. In either case, let the set of

islands in G O be { Ii }; then the set of islands in (3.4) is merely the set

{ ljl 3 at least one k with ut elj }

This proves condition (3.4), and the lemma. •

Intuitively, the lemma holds because the islands are simply those parts of the tg-path between u I and un which consist of directly connected subjects. The advantage of this formulation is

that one need not define the "islands" of the original theorem, and can instead consider simply tgpaths irrespective of maximal subject-only groupings just as in the test for cansknow one need only

consider rwtg paths and rw-terminal and rw-initial spans. So there is now a pleasing symmetry between the necessary and sufficient conditions for sharing rights and sharing information. Of course,

Corollary 8. Truth or falsity of the predicate cansshare can be determined in time linear in the size

of the graph.

Given the symmetry between lemma 7 and the theorem for cansknow, one would expect

the latter could be reformulated along the lines of the theorem for cansshare:

Lemma 9. Let x and y be vertices in a protection graph G 0. Then cansknow(x, y, GO) is true if and

only if canoshare(r, x, y, GO) is true or all of the following conditions hold:

(9.1) there is a subject x" such that x" = x or x" rw-initially spans to x;

(9.2) there is a subject y" such that y" = y or y" rw-terminally spans to y;

(9.3) there is a sequence of islands lj, 1 <_j <_n, such that there is a bridge or connection from

ljtolj+l, 1 <j< n, and x" E I 1 and y" E I n.

Proof: The proof is similar to that of lemma 7 and is left to the reader.

4. Modelling Specific Security Policies

We now consider some security policies and how they might be modelled using the Takegrant Protection Model. Each of these policies is realistic in the sense that an existing computer

system uses them or they have been described in the literature as appropriate under certain condiPage 10 of 26
tions for anoperationalsystem.We first express the policy in mrms of the predicates canoshare,

canesteal, caneknow and canesnoop, and then ask whether the policy can be modelled using the

rules of the Take-Grant Protection Model. If it cannot, we describe any necessary modifications to

the rules and the effect of those modifications on the predicates.

We shall explore the representation using two criteria. Let H be the set of protection graphs

satisfying the security policy (we shall use subscripts to distinguish between Hs representing different policies). We shall require that the set of rules used to model the policy be sound with respect

to H:

Definition. A set of graph rewriting rules P is sound with respect to a set of protection graphs H if

applying any finite sequence of elements of P to any element h _ H produces a graph h" ¢H.

In addition, we shall examine the completeness of the rule set with respect to H and the set

of original rules 0 = { take, grant, create, remove }:

Definition. Let h, h" _ H, and h _* h" using the rules in O. Then if for some P _ O, h i--* h" using

only elements of P, the subset P is complete.

Note that "subset" here includes restricting the rewriting rule in some way, such as not allowing creates to add take edges.

4.1. Complete Isolation of Each Process

The policy of total isolation of each process prevents breaches of security and solves the

confinement problem by preventing any transfer of information or rights among subjects [ 13].

To prevent any information or rights transfer (illicit or otherwise) it suffices to make all four

predicates always be false. Hence for this policy, H l is the set of graphs with elements satisfying

-,canoshare(_x,y,h) ^ --,canOsteal( _x,y,h ) ^ -,canoknow( x,y,h ) ^ -_anoknow( x,y,h )

for all protection graphs h G H l, all pairs of vertices x and y in h, and all subsets of rights ot _ R.

To characterize this requirement in terms of the rules, note that by theorems 5 and 7, it suffices to prevent any bridges or connections between any two subjects to enforce this condition; in

that case, both conditions (5.3) and (7.3) can never hold. Because the x and y referred to in the theorems may be subjects, it is not possible to prevent conditions (5.1), (5.2), (7.1), and (7.2) apriori

from occurring; hence the above constraint is also necessary. Thus, H l may be characterized in

terms of Take-Grant rights by:

Page 11 of 26
Requirement. To enforce complete isolation of subjects, no bridges or connections may exist between any two subjects in the protection graph.

Determining whether or not a protection graph meets this requirement is easy: just look for

bridges or connections between subjects. So:

Lernma 10. Testing a graph for violation of the restriction may be done in time linear in the number

of edges of the graph.

Also, when a new de jure rule is applied, we can test for violation of the restriction just by

looking at the paths affected by the rule application; in the worst case, this requires checking every

edge in the graph. So:

Lemma 11. Determining whether or not an application of a de jure rule violates the restriction may

be done in time linear to the number of edges of the graph.

This does not require any changes to the take or grant rules, since in a graph in which creation is disallowed, bridges and connections may not be constructed unless they already exist.

However, it does require changing the create rule, since if one subject creates another, the parent

may give itself any rights in R to the child. Should one of these rights be take, grant, read, or write,

there will be a bridge, connection, or both between the parent and the child. Hence to make the rules

sound with respect to this set of protection graphs HI, the create rule must not allow any of those

rights to be in the set of rights the parent has over its child:

recreate (modified create): Let x be any subject in a protection graph h, and let (z _ R. The modified create rule recreate defines a new graph h" by adding a new vertex y to the graph and

an edge from x to y labelled ¢z" such that if y is a subject, (z" = a - { t, g, r, w }, and if y is

an object, (x" = (x.

To see the set PI - { take, grant, recreate, remove } is sound with respect to H l, simply note

bridges and connections cannot be added where they did not exist. This set of rules is not complete

with respect to O and H l, because using rules in O, one can derive a graph with two subjects that

are not connected to each other having read rights over a single object (see figure 1), but one cannot

obtain the same graph using the rules in PI because at no time can the read right be transferred from

one subject to another. These arguments can be made rigorous, and show:

I,emma 12. Pl is sound with respect to H 1, but not complete with respect to O and H 1.

As an aside, we note that if the policy is eased to allow sharing of rights between processes

with the same ancestors (which would be reflected by modifying the requirement and the definition

Page 12 of 26
x

_._ tr A m.,LA

W B_'_V

x y

x creates (tr to new subject) y

tr •

_ qW _ lp"

x Y z

x y z

y creates (r to new object) z

x takes (r to z) from y

x removes (tr to y)

x Y z

Figure 1. Example of lack of completeness of PI for a security policy of complete isolation.

of the set H l appropriately), the create rule need not be modified to produce a sound and complete

set of rules. The complexity of testing for violations of the restriction is still linear in the size of the

graph,

However, this security policy is so restrictive as to be uninteresting, banning (among other

things) any take, grant, read, or write edges, and most paths, between subjects. So let us turn to a

slightly less restrictive, and more interesting, policy.

4.2. Limited Sharing: Owner Controls Dissemination of Rights and Information

In some access control systems, the rights to manipulate files or data is under the control of

the owner of that data. For example, in the Unix@ operating system [16], the owner of a file controis who may access it. So this policy allows sharing of rights and information with consent of the

owners of that information.

We must at this point define ownership. Two definitions are possible; one, more common

in database work, holds that possession of a right is "ownership" of some kind. The second, more

common to operating systems, defines ownership as a separate right. We examine both here.

4.2.1. Ownership Conferred by Possession of a Right

This definition, used for example in System R [9],creates a system in which mere possession of a right enables a subject to propagate that right. Hence for this policy and definition, H 2 is

the set of graphs with elements satisfying

cane share( (z,x,y,h ) A --,cane steal( (x,x,y,h ) ^ cane know( x,y,h ) ^ --,canes noop( x,y,h )

Page 13 of 26
for all protection graphs h ¢ H 2, all pairs of vertices x and y in h, and all subsets of rights cc _ R.

The reasoning is that any two subjects must be able to share fights or information, but no set of

subjects can steal rights or information without the consent of the owner. To satisfy the first two

predicates, the owner must cooperate in any transfer of rights; to satisfy the latter two, the owner

must cooperate in any sharing of information. We also note that any pair of subjects can share rights

or information by the construction of this condition.

For canoshare(ot,x,y,h)to be n'uebut can*steal(cz,x,y,h)to be false,condition (4.4)must

be falsesincenegatingany of conditions(4.I)-(4.3)negateseitherofconditions(3.I)or (3.2),making can*share(ot,x,y,h)false.For (4.4)tobe false,by lemma 7 eithertheremust be no tg-pathsbetween any two subjectsor no takeedges incidentupon any subject.We note thattheformer again

renderscan*share(cz,x,yJOfalse,and thatthe latterenderscan*snoop(x,y,h)false(as allrw-terminal spans willhave length I,so condition (6.3)fails)without also negating caneknow(x,y,h).

Clearly,the lattercharacterizationof H 2 isbest:

Requirement. To implement the above policy,no take edges may be incidentupon any subject.

Obviously, testingfor thisconditionissimple,as istestingfor a violationwhen a de jure

ruleisapplied:

Lemma 13.Testinga graph fora violationof the restrictionmay be done intime linearinthe number of edges in thegraph. Further,determining whether or not an applicationof a de jure rule violatestherestrictionmay be done inconstanttime.

The obvious way topreventcreationof take edges istomake the appropriatemodification

totherecreateruledescribedin theprevious section(callthe new createrulencreate,and therule

setP21).The argument for soundness isalmost identicaltothe one forrecreate.And the argument

for completeness failsalso.To see why, noticethatthe grantrule does not add any edges to the

source of theedge labelledgrant.Hence, lemma 2 cannot hold (infact,theproof thatitistrueusing

the setO of originalTake-Grant ProtectionModel rulesrequirestheuse of a take rule).Now considera graph h inH 2.As thereare no take edges,the only takeedges thatcould be added using the

rulesinO would be to new vertices.Ifthoseverticesaresubjects,any subsequent manipulationof

those rightswould requirean applicationof lemma 2,which isfalsegiven the replacement of the

create rule by the ncreate rule. Hence:

Lemma 14. P21 is sound but not complete with respect to O and H 2.

Page 14 of 26
g 0t

Y X z

g x Ot

g

S

y nmcreates (g to new subject) s

y grants (g to s) to x

]-- gsy_ x grants (ct to z) to s

(Z

[_ s grants (_ to z) to y

Figure 2. Pr_f of lemma 2 using the rule set P_ = { take, grant, nmcreate, remove }.

A simple way to make the new rule set P21 complete as well as sound is to change ncreate

to require the creation of grant edges to every existing subject when a new subject is created:

nmcreate (new modified create): Let x be any subject in a protection graph h, and let ot _ R. The

modified create rule recreate defines a new graph h" by adding a new vertex y to the graph

and an edge from x to y labelled or" such that if y is a subject, ct" = ct - { t }, and if y is an

object, or" - ix. Also, if y is a subject, edges labeled { g } are added from y to each subject

vertex in h.

Using the rule set P22 = { take, grant, nmcreate, remove }, creating a new vertex would

add an incoming grant edge to the parent, in which case the proof of lemma 2 is straightforward

(see figure 2). Then the argument for completeness goes as before, except that as lemma 2 is true,

the transfer of any rights from a newly created subject to the parent using take can be emulated by

the child granting the parent the rights. If the child is an object, of course, the issue never arises

since the only way a right can be added to the child is by the parent granting the right, in which

case application of the take rule is redundant and can be eliminated. This can be made formal, and

shows:

Page 15 of 26
Lemma 15. P22 is both sound and complete with respect m O and H 2.

4.2.2. Ownership As a Right

Using this definition, ownership is itself a right and only the owner may distribute rights.

This version is similar to the propagation prevention mechanism such as HYDRA's environmental

rights mechanism [5],[11] and, at least in operating systems, is more common than an unconstrained ability to transmit rights.

First, note that the rules for the Take-Grant Protection Model fail to capture the system's

distinction between owning an object and owning a right to an object. The simplest incorporation

of this distinction is a modification of the grant rule.Define a new ownership right o. Then:

mgrant (modifted grant rule): Let x, 3,, and z be three distinct vertices in a protection graph G 0,

and let x be a subject. Let there be an edge from x to y labelled ¥ with g _ y, an edge from

x to z labelled _l with o G 13,and 0t c [3 with o _ ct. Then the modified grant rule mgrant

defines a new graph G 1 by adding an edge to the protection graph from x to z labelled tz.

In short, no fights to an object may be granted unless the grantor has an o right to the object.

Further, the o fight cannot be granted. Let P23 - { take, mgrant, nmcreate, remove }. Then:

Lemma 16. Given the set of rules P23, only the owner of a target can propagate a right to that target.

Now, the set of graphs under consideration is still H 2. But how does the change in the grant

rule affect the restriction necessary to ensure that owners can share information or rights, but that

those cannot be stolen or snooped? As both stealing and snooping may involve the propagation of

rights, if neither is possible, then limiting the propagation of rights further will not enable either.

In other words, the modified grant rule limits the spread of rights and so those predicates that are

false in the original model will be false in the modified model. So the requirement for the unconstrained case is at least sufficient.

To carry the analysis a bit deeper, a right can clearly be shared between the owner and any

other subject since, by the statement of the security policy, all subjects have grant rights over one

another. However, a simple construction will show that fights can be propagated between endpoints

of bridges as well, but no further. Hence given the modified grant rule, canoshare is true if and only

if the number of subjects in condition (7.3) is 2.

We note that the rule set P23 is sound since no take edges are added by any of the rules.

Completeness follows from the same argument as before. Hence:

Page 16 of 26
Lemma 17, P23 is both sound and complete with respect to O and H 2.

4.3. Multilevel Security Policy

Multilevel policies are quite common in exisdng systems (see for example [6],[ 16]). Here

we generalize the results in [2] and extend them to include caneshare, canesteal and canesnoop.

Our policy is a generalization of the Bell-LaPadula model [ 1] in which a set U of rights may not

extend from a lower to a higher level, and a set D of rights that may not extend from a higher to a

lower level.We shall assume that r ¢ U and w _ D so that the simple security and *-properties hold.

This policy associates with each subject and object a security level and a set of categories.

Informally, a subject can access an object (in any way other than by using the rights in D) if the

security level of that object is no greater than the level of the subject and the object's set of categories is a (possibly improper) subset of the subject's categories; similarly, the subject can access an

object (in any way other than by using the rights in U) if the security level of the object is no less

than that of the subject and the object's set of categories is a (possibly improper) subset of the subject's categories. Formally, define the functions s/(x) and cs(x) to be the security level and set of

categories of the vertex x, respectively; then x dominates y (written x > y) ff both sl(x) > sl(y) and

cs(y) _ cs(x), and x strictly dominates y (written x > y) if x > y and s/(x) _ sl(y) or cs(y) g cs(x).

(Following Gasser [7], we shall call the pair (s/(x), cs(x)) an access class.)

We consider two types of systems: those with mandatory access controls only, and those

with both mandatory and discretionary access controls.

4.3.1. Mandatory Access Controls Only

In a multilevel security policy with mandatory controls only, permission of the owner of

rights to an object need not be acquired to obtain access to that object; if access can be granted according to the multilevel rules, it will be. This security policy may then be summarized by requiring

the elements of H31 to satisfy:

[VSC.D, _U] x > y ¢* --,caneshare(8,x,y,h)^ --,caneshare(_,y,x,h)^ caneknow(x,yJz)

forallprotectiongraphs h ¢ 1-131,allpairsof verticesx and y in h,and allsubsetsof rightscx_ R.

This capturesthatifx strictlydominates y,x cannot x)to y and y cannot 8 tox (where _ and 8 are

subsetsof U and D, respectively)and thattheowner need not consent toany transfersof informationor rights(hence theomission of canesteal and canesnoop).

Page 17 of 26
We extend the characterization of a similar (straightforward Beil-LaPadula) model in [2] to

describe the class of protection graphs in//31. Each set of nodes in a single access class is represented as a protection level:

Definition. A protection level is a set of subjects in a protection graph G such that, for every pair

of vertices x and y in the set, caneshare(_x,y,G), caneshare(_y,x,G), caneknow(x,y,G) and

caneknow(y,x,G) are true.

This says that within a protection level (access class), all vertices can obtain any information or rights from any other vertex in that level.

De_nition. Two subject vertices x and y are said to be joined if caneknow(x,y,G) is u'ue, and

can*know(y,x,G), canashare(_,y,x,G), and can*share(8,x,y,G) are false.

It can be shown (along the lines of the proof of proposition 4.4 in [2]) that this relation defines a partial ordering; so, if the members of one access class dominate another, the members of

the protection level representing the first access class are joined to the second, and we say the first

protection level is higher than the second (or, the second is lower than the first). Intuitively, what

the two definitions say is that within a protection level, any amount of sharing of information or

rights is fine, but between protection levels, information may flow upward, and any sharing of

rights that does not involve adding edges labelled with rights in U going from a lower protection

level to a higher one, or edges labelled with rights in D going from a lower protection level to a

higher.

Given this representation, it can be shown that [2]:

Requirement. To enforce a multilevel security policy of the sort described here, there can be no

bridges or connections between protection levels.

In essence, this forbids any transfer of information or rights between protection levels,

which certainly satisfies the policy. It is also straightforward to prove:

Lemma 18. Testing a graph for a violation of the restriction may be done in time linear in the number of edges in the graph. Further, determining whether or not an application of a de jure rule violates the restriction may be done in constant time.

This representation is probably overly restrictive because it limits the sharing of rights other

than those in U and D, and since the multilevel policy deals only with those rights, any representation should deal only with them. In [2], three modifications to the rules in O are considered; we

generalize the most interesting here:

Page 18 of 26
mistake (multilevel secure 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 7 with t ¢ 7, art edge

from y to z labelled 13, and a c 13.Then the multilevel secure take rule mistake defines a

new graph G 1 by adding an edge to the protection graph from x to z labelled a" such that

if x > y, a'ffia- D and ff y > x, a'fa- U.

mlsgrant (multilevel secure grant): Let x, y, and z be three distinct vertices in a protection graph

G O, and let x be a subject. Let there be an edge from x to y labelled y with g _ y, an edge

from x to z labelled 13,and a c [3. Then the multilevel secure grant rule misgrant defines a

new graph G 1 by adding an edge to the protection graph from x to z labelled a" such that

ifx > y, a'=a-D andif y> x,a'=a- U.

These rules simply modify the original take and grant rules to prevent adding edges with

rights in U from a vertex in a lower protection level to a higher one, or edges with rights in D from

a higher protection level to a lower one. If P31 is the set of rules obtained by replacing the take and

grant rules in O with the mistake and misgrant rules, it can be shown [2]:

Lemma 19. P31 is both sound and complete with respect to O and H31.

4.3.2. Mandatory and Discretionary Access Controls

In this case, first mandatory access controls determine if the desired access is allowed by

the system; if it is, then the discretionary access controls determine if access is allowed by the owner of the information. So, with this policy, in addition to the statement of mandatory access, a component for discretionary access must be included, and the elements in H32 must satisfy:

[[VS..D, _U] x > y ¢=_ _caneshare(5,x,y,h) ^ -.caneshare(_,y,x,h) ^ caneknow(x,y,h)] ^

--,cane steal( _ y,x,h ) ^ -,cane snoop( x,y,h )

for all protection graphs h E H32, all pairs of vertices x and y in h, and all subsets of rights a _ R.

In addition to the limits discussed in the mandatory-only case, this formula also captures that the

owner must consent to any transfers of information or rights by the inclusion of canesteal and

cane snoop.

We now redefine protection level and joined to disallow stealing and snooping in the obvious way. Then in addition to their being no bridges or connections between protection levels, there

can also be no take edges incident upon subjects by the reasoning in section 4.2.1. Hence:

Page 19 of 26
Requirement. To enforce a multilevel security policy involving both mandatory and discretionary

access controls, there must be no take edges incident upon subjects, nor any bridges or connections

between protection levels.

Clearly, violations can be tested in time linear in the number of edges of the graph, and

when a de jure rule is applied, examining the new edge will reveal violations. As before, this requirement, while effective, is quite restrictive.

Let us add the fight t to both sets U and D, and further alter the create rule to bar creation

of any edge labelled t and add grant edges to all subjects in the new vertex's protection level when

the new vertex is a subject. (This is in the spirit of the nmcreate rule in section 4.2.1. However, here

the "parents" are simply all vertices in the protection level.) Call the new create rule mlscreate.

Then let P32 = ( mlsgrant, mlscreate, remove } and remove the above requirement. What are the

effects? If a graph h is in H32, applying those rules will generate a new graph h" also in H32, because no stealing or snooping can be done (since the lack of take edges incident on subjects violates

both conditions (4.4) and (6.3), so by theorems 4 and 6, those predicates can never hold), and clearly no edges with labels in U can be added from a lower protection level to a higher, and no edges

with labels in D can be added from a higher protection level to a lower, so this set of rules is sound

with respect to H32. Next, notice that since no take edges are present, the take rule could never be

applied, and further if the ordinary create rule were used, the mlscreate rule could be simulated by

having the creator at once grant g fights over all vertices in the protection level to the newly created

subject. Hence P32 is complete. This can be formalized to show:

Lemma 20. P32 is both sound and complete with respect to O and H32.

4.4. Tree.Based Hierarchies

A tree hierarchy is a set of entities arranged in a tree structure. We shall use the term treebased hierarchy to refer to a structure derived from a tree hierarchy. An ancestor of vertex x is a

vertex which can acquire a right from x with or without x's cooperation. The level ofx is the length

of the shortest path to the root containing only the ancestors of x and x itself. Define a common

ancestor of vertices x and y to be the set of vertices which are ancestors to both x and y. We then

consider a security policy that allows vertex x to share rights or information with vertex y if and

only if a common ancestor allows the sharing. We specifically consider those hierarchies which are

initially trees, but may degenerate into directed graphs.

Page 20 of 26
This policy is a generalization of one discussed in [ 18]; protocols to implement it were discussed in [21], and similar, less general policies are the basis for many protection schema (for example, for the Unix® operating system, the tree level is 2, with the superuser being the root vertex

and all users being the nodes to which the root is ancestor). The focus of this discussion is more

fundamental: what is the specific policy being enforced, and how should the rules in O be modified

to prevent breaches of security7

Define anc(x 1, .... x a) to be the set of common ancestors of x 1, .... x a. Then for this policy,

H 4 is the set of graphs satisfying:

[canoshare(cz_x,yJO =_ [3 zG anc(x,y) [canoshare(_z,y,h ) ^ canoshare(g,z,x,h )]]] A

[can*know(x,y,h) =_ [3 z_ anc(x,y) [canoknow(z,y,h) ^ canoknow(x,z,h)]]] ^

[ V z_ anc(x) [-_canosnoop(x_z,h) A --,canOsteal(t,x,z,h)]]

for all protection graphs h _ H 4, all pairs of vertices x and y in h, and all subsets of rights cx _ R.

In intuitive terms, this says simply that no vertex may steal or snoop an ancestor, and that if two

vertices can share rights or information, one of their common ancestors must have assisted in that

sharing.

To characterize such a graph in Take-Grant terms, first note that while each ancestor may

have both take and grant authority over its descendents, no vertex may have take authority over any

ancestor. (Hence the definition of ancestor of a vertex x ay be characterized succinctly as the set of

vertices lying on any path from the root to x with associated word in _* .) We then note that

canosteal(cz,x,y,h) is true only if some vertex z has cz rights over y, and a common ancestor of x

and z participates in the theft, the former condition being required by condition (4.3), and the latter

following by the common ancestors being foci of access sets which connect that part of the conspiracy graph associated with h containing x with that part containing y [20]. Further, both those

conditions enable one to exhibit a witness to canOsteal(cz,x,y,h); hence,

Lemma 21. canosteal(_x,y,G) is u'ue if and only if there exists a vertex z with cz rights over y in

G, and a comn_n ancestor of x and z applies one (or more) rules instantiating the theft.

A similar result holds for canosnoop:

Lemma 22. canOsnoop(x,y,G) is true if and only if there exists a vertex z which rw-terminally spans

to y in G but does not have r rights over y in G, and a common ancestor of x and z applies one (or

more) rules instantiating the snooping.

Page 21 of 26
y • z y x z

y takes (g to z) from x

I-- _ y grants(tto x) toz

y x _,]z

t

Figure 3. Lack of soundness of O under a tree-based hierarchical security policy.

Unfortunately, a very quick construction shows that O is not sound with respect to H 4 (see

figure 3). Hence, to enforce soundness, the rules must be modified. The most obvious modification

followsfrom theprevious section;sinceinessence thisisa hierarchy,simply restrictthe applicat/onof the take and grantrulesso thatno takeedges may be added going up:

tbhtake(tree-basedhierarchicaltake): Let x, y,and z be threedistinctverticesin a protection

graph GO, and letx be a subject.Let therebe an edge from x toy labelledy with t ¢ y,an

edge from y to z labelled [$, and a c [$.The tree-based hierarchical take rule tbhtake defines

a new graph G 1 by adding an edge to the protection graph from x to z labelled a" such that

ify¢ anc(x, y),co"= a- { t }.

tbhgrant (tree-based hierarchical grant): Let x, y, and z be three distinct vertices in a protection

graph G 0, and let x be a subject. Let there be an edge from x to y labelled ¥ with g _ T, an

edge from x to z labelled [3, and a c 13.Then the tree-based hierarchical grant rule tbhgrant

defines a new graph G 1 by adding an edge to the protection graph from x to z labelled 0t"

such that, ify (_ anc(x, y), a" = a - { t }.

Now, as no take edges ever extend from a vertex to an ancestor, both snooping and thieving

are impossible unless an ancestor common to the source and target cooperates. Unfortunately, completeness no longer holds since take edges from a vertex to an ancestor can no longer be emulated

with the new rules, as lemma 2 fails for the reasons given in section 4.2.1. So to ensure completeness, a modified create rule similar to the nmcreate rule must be used:

tbhcreate (tree-based hierarchical create): Let x be any subject in a protection graph h, and let ot

R. The tree-based hierarchical create rule tbhcreate defines a new graph h" by adding a

new vertex y to the graph and an edge from x to y labelled 0t" such that, if y is a subject,

Page 22 of 26
then e_" = a - { t }, and if y is an object, (I" = 0.. Also, ff y is a subject, edges labele.d { g }

are added from y to each subject vertex in anc(y).

The proof of completeness now follows, so letting/'4 = { tbhtake, tbhgrant, tbhcreate, remove }:

Lera_a 23. P4 is both sound and complete with respect to O and H 4.

5.Conclusion

The ability to represent useful security policies shows that the Take-Grant Protection Model may prove to be not only a theoretical tool for studying some ramifications of the safety question,

but also a powerful, practical model that can be used to study abstract representations of real systems for safety (or methods that could be used to leak information or rights). This paper has provided sevecal such representations. Of course, other methods of abstraction could have been used.

As an example, the four basic rules (take, grant, create, remove) could have been bound together to form protocols, and subjects required to apply rules only by executing one (or more) of

those protocols. Rather than employ this strategy to ensure soundness, as Snyder [18] and Wu [21]

have done, we have considered modifications to the take-grant graph rewriting rules. This has two

effects.

A protocol strategy first implies that all subjects will use the primitive operations only

through the protocols, and that they can be trusted not to call on the primitive operations directly.

For example, in figure 3, Wu's protocols assume that no ancestor will grant take rights in the way

that was done there. Given such an assumption (that all subjects are, in that sense at least, honest),

a protocol strategy works well. However, it ignores the possibilities of theft and snooping. When

those arc considered, it becomes clear that the "protocols" must be the "primitive operations" to

ensure that the subjects only use them to alter the graph.

Secondly, the graph rewriting rules presented here are far more general than the protocols

used by Wu. As an example, in her analysis of the tree-based hierarchical security policy, there is

an implicit assumption that if a subject wants a right from another node which is not a descendent,

a common ancestor must initiate the u'ansfer. In this analysis, we make no such assumption; the

vertex may, in effect, "request" the ancestor transfer the right by initiating a transfer. However, to

complete the transfer, the ancestor must apply one (or more) rules. The difference is that between

initiation and cooperation.

Page 23 of 26
Much work remains before the Take-Grant Protection Model can be used in practise. For

example, many systems treat fights reflexively (that is, a subject can take or grant itself rights, as

well as read itself).The Take-Grant Protection Model does not. But, as Snyder has pointed out, reflexivity "probably is not fundamental to the Take-Grant Model in the first place," ([19], p. 179)

and it has some benefits when making an abstraction of an existing system. When one models a

"process," one may actually be modelling several entities: the process thread itself, the process

control block (if the process can read or alter it directly), those portions of memory in which variables are stored (for processes which do not read or write anything are useless, unless one is considering the problem of covert channels, a subject well beyond the scope of this paper), and files.

Each of these should be considered as separate entities, because each interacts with the execution

of the process in a different way; and the lack of reflexivity in Take-Grant encourages such a division. This suggests that in the application of a formal model like Take-Grant, irreflexivity may benefit the modelling process. Analysis of a reflexive Take-Grant Protection Model would help

determine if this intuition is correct, or when a reflexive system should be used.

We have modified many of the Take-Grant graph rewriting rules to capture compliance with

a security policy. Part of the reason for this was to ensure the theorems stating necessary and sufficient conditions for caneshare, caneknow, canesteal and canesnoop held. However, it might be

possible to produce "meta-theorems" which, for a given rule set, produce conditions under which

those four predicates hold. Such meta-theorems would almost be a necessity for any realistic use

of the Take-Grant Protection Model in systems analysis, since no two systems will have the sa_mc

rule sets. This issue requires much further work.

Finally, most computer systems have some concept of"group." Incorporating such a notion

into the Take-Grant Model would be invaluable towards its practical application.

6. Reference

[ 1] Bell, D. and LaPadula, L., "Secure Computer Systems: Mathematical Foundations and

Model," M74-244, The MITRE Corp., Bedford, MA (May 1973).

[2] Bishop, M., "Hierarchical Take-Grant Protection Systems," Proc. 8th Syrup. on Operating

Systems Principles (Dec. 1981) pp. 107-123

[3] Bishop, M., "Theft of Information in the Take-Grant Protection Model," Proceedings of the

Computer Security Foundations Workshop (June 1988) pp. 94-218.

Page 24 of 26
[41

[5]

[6]

[7]

[8]

[9]

[lO1

[11]

[12]

[131

[14]

[15]

[16]

[17]

[18]

Bishop,M. and Snydcr,L.,"The Transferof Informationand Authorityin a ProtectionSystera," Pro¢. 7th Syrup. on Operan'ng Systems Principles (Dee. 1979) pp. 45-54.

Cohen, E. and Jefferson, D., "Protection in the HYDRA operating system," Operating System Reviews 9(5) (1975), pp. 141-160.

Deparmmnt of Defense, Trusted Computer System Evaluation Criteria. DOD 5200.28-

STD (1985).

Gasser, M., Building a Secure Computer System, Van Nostrand Reinhold (1988).

Graham, G. and Denning, P., "Protection: Principles and Practices," Proc. AFIPS Spring

Joint Computer Conf. 40 (1972) pp. 417-429.

Griffiths, P. and Wade, B., "An Authorization Mechanism for a Relational Database System," Transactions on Database Systems 1(3) (Sep. 1976) pp. 242-255.

Harrison, M., Ruzzo, W., and Ullman, J., "Protection in Operating Systems," CACM 19(8)

(Aug. 1976), pp. 461-471.

Jones, A., "Protection Mechanism Models: Their Usefulness," in Foundations of Secure

Computing, Academic Press, New York City, NY (1978) pp. 237-254.

Jones, A., Lipton, R., and Snyder, L., "A Linear Tune Algorithm for Deciding Subject Security," Proc. 17th Annual Syrup. on the Foundations of Computer Science (Oct. 1976) pp.

33-41.

Lampson, B., "A Note on the Confinement Problem," CACM 16(10) (Oct. 1973) pp. 613-

615.

Lampson, B., "Protection," Fifth Princeton Conf. on Information and Systems Sciences

(Mar. 1971) pp. 437-443.

Lipton, R. and Snyder, L., "A Llinear Time Algorithm for Deciding Subject Security. J.

ACM. 24(3) (Jill. 1977) pp. 455-464.

Ritchi¢, D. and Thompson, K., "The Unix Time-Sharing System. CACM 17(7) (Jul. 1974)

pp. 388-402.

Sandhu, R., "The Schematic Protection Model: its Definition and Analysis for Acyclic Attenuating Schemes," J. ACM 35(2) (Apr. 1988) pp. 404-432.

Snyder, L., "On the Synthesis and Analysis of Protection Systems," Proc. Sixth Syrup. on

Operating Systems Principles (Nov. 1977) pp. 141-150.

Page 25 of 26
[19]

[201

[21]

Snyder, L., "Formal Models of Capability-Based Protection Systems," IEEE Transactions

on Computers C-30(3) (Mar. 1981) pp. 172-181.

Snyder, I.,., "Theft and Conspiracy in the Take-Grant Protection Model," JCSS 23(3) (Dee.

1981) pp. 333-347.

Wu, M., "Hierarchical Protection Systems," Proc. of the 1981 Syrup. on Privacy and Security (1981) pp. 113-123.

Page 26 of 26