Take-Grant Systems
Lecture Material
found in
"Cryptography and Data Security", by Denning
compiled and presented by
Markus K. Gröner
Outline
This page was create as part of an assignment for the
CS5204 Operating Systems class
Spring Semester 1995 at Virginia Tech taught by
Dr. Dennis Kafura. Each student was
assigned with the task to recreate part of the lecture material as a WEB page. Most
of the text for this WEB page was taken directly from the Denning book [DENN82]. All
graphics were taken straight from this book as well, but redrawn to enhance visibility.
The Take-Grant System is a model that helps in determining the protection rights
(e.g., read or write) in a computer system. The Take-Grant system was introduced
by Jones, Lipton, and Snyder [JONE76] to show that it is possible to decide on the
safety of a computer system even when the number of subjects and objects are very
large, or unbound. This can be accomplished in linear time based on the initial
size of the system.
The take-grant system models a protection system which consists of a set of states
and state transitions. A directed graph shows the connections between the nodes of
this system. These nodes are representative of the subjects or objects of the model.
The directed edges between the nodes represent the rights that one node has over the
linked node.
Denotation:
(x,y) is the set of access rights on the edge from node x to node y.
If r is an element of (x,y), then node x has the right r for
node y.
Take Right:
The take right t on an edge is a special right. For a subject s to have the right
t on an object x, it means that subject s can take any rights that x
possesses.
Grant Right:
Similar to the take right, the grant right g on an edge is also a special right. For a
subject s to have the right g for a subject/object x, it means that subject
s can grant (share) any of the rights it possesses to subject/object x.
The figure below, taken from Denning [DENN82], is a graphical representation of a directory
structure. In this graph P1 and P2 represent subjects (possible users), and the
Ds and Fs represent objects, directories and files respectively. Read rights
have been changed to take rights for all levels except for the actually file level in
the directories. Write rights have equally been changed to grant rights.
It becomes clear from this graph that if a subject/object has read (take) capability on an object,
it can take on any of the capabilities that this object has. Similarly, if a subject/object has
write (grant) capabilities to an object, it can grant any of its capabilities to that object.
Rule 1 (Take):
Let s be a subject with t being an element of (s,x) and r
being an element of (x,y) for a right r and the nodes x, y.
To add r to (s,y) use: s take r for y from
x.
This is shown in the following picture where nodes x and y can be either
subjects or objects.
Rule 2 (Grant):
Let s be a subject with g being an element of (s,x) and r
being an element of (s,y) for a right r and the nodes x, y.
To add r to (x,y) use: s grant r for y to
x.
This is shown in the following picture where nodes x and y can be either
subjects or objects.
Rule 3 (Create):
If s is a subject and p is a set of rights, then the command:
s create p for new {subject or object} x
will add a new node x and sets (s,x) = p.
This is shown in the following picture where node x can be either a
subject or an object.
Rule 4 (Remove):
If s is a subject and x is a node, then the command:
s remove r for x will remove the right r from
(s,x).
This is shown in the following picture where node x can be either a
subject or an object.
Example 2
The figure below shows that through combinations of the above four rules, a new file can be added to the directory structure of Example 1 and Read/Write rights issued for the directory in which the file exists. The following four steps are necessary to add the file and grant rights:
- P1 create RW for new object F7
- P1 take t for D1 from D
- P1 take g for D11 from D1
- P1 grant RW for F7 to D11
The numbers in the list above correspond with the circled numbers depict in the graph as the arcs are created.
The four rules presented above allow for the granting and taking of rights by subjects/objects in the take-grant
system. This presents the question of safety and security. Is it possible for some individual to ultimately gain
rights to an object to which this individual should never have gained rights? Can the safety/protection of a system
be decided on?
Consider a graph G from the take-grant system. Can G be transformed into a graph G'
through a single command c, or a possible sequence of commands? Consider the following graph G. This graph has
a node S with right r for a node x. Now consider a new subject/object p. We would like to determine
if p can receive right r to x. Graph G is considered to be safe, if for any derivation of G
through the four commands, p cannot gain right r for node x.
The following proof uses the predicate can.share to decide if it is possible for node s to share its right r
for x with p. If this is the case then graph G is considered to be unsafe. There are two possible node
connections that have to be defined:
Nodes x and y are tg-connected if there is an undirected edge between the nodes labeled either t or
g.
Nodes x and y are directly tg-connected if there is a directed edge between the nodes labeled either t or
g.
The following sufficient condition for predicate can.share was proven by Jones, Lipton, and Snyder [JONE76]:
Theorem:
can.share(r,x,p. G) is true of p is a subject and
- There exists a subject s in G such that r is an element of (s,x) in G, and
- s and p are directly tg-connected.
The proof has to consider four cases:
Case 1.
In this case p can take the right r from s by the command:
p take r for x from s
Case 2.
Here s can grant p its right by the command:
s grant r for x to p
Case 3.
This third case is not immediately apparent since it is not possible for p to get the right with one command. But, with the help of s it is possible for p to get the right with only four commands. The series of figures shows how p gets the right:
This is the original state of the graph. 
p create tg for new object y 
p grant g for y to s 
s grant r for x to y 
p take r for x from y 
Case 4.
Just as with Case 3, p cannot get the right with a single command - four commands are needed. This last case shall remain unresolved as an exercise in preparation for the final. ;-)
Stealing Rights
The issue of sharing rights was easily solvable and decidable. This does not mean though that any system is
safe, just because it has been determined how rights can be shared. There also exists a possiblity for subjects
to steal rights from other subjects. It may not be easy for a single subject to steal rights, but with the help of other subjects, called conspirators, the subject may get rights that it shouldn't have. Even if a subject does not have rights to an object's information, with the help of a conspirator who has rights to this information it may be copied to the subject. These two possibilities to acquire information are coined de jure and de facto by Bishop and Snyder [BISH79]. Here de jure means that a subject actually gets the right to an object, and de facto means the subject does not necessarily get the rights but only the information of the object.
- [BISH79]
- Bishop, M. and Snyder, L., "The Transfer of Information and Authority in a Protection System,"Proc. 7th Symp. on Oper. Syst. Princ., ACM Oper. Syst. Rev., pp.45-54, Dec. 1979.
- [DENN82]
- Denning, Dorothy E., "Cryptography and Data Security," Addison-Wesley, Inc., Reading, Mass., pp. 248 - 257, 1982.
- [JONE76]
- Jones, A. K., Lipton, R. J., and Snyder, L., "A Linear Time Algorithm for Deciding
Security," Proc. 17th Annual Symp. on Found. of Comp. Sci., 1976.
Last Updated: Thursday, May 4, 1995