CS5430 Homework 2: Authorization
General Instructions.
You are expected to work alone on this assignment.
Due Monday Feb 21, 10am.
No late assignments will be accepted.
Submit your solution using CMS.
Prepare your solution as .doc, .docx, or .pdf, as follows:
-
Use 10 point or larger font.
-
Start each problem's solution on a new page.
-
Use at most 1 page per problem.
Problem 1:
We define a coarse-grained object to be an object
that is obtained by combining the state and operations from a collection
of (ordinary) fine-grained objects,
and we define a fine-grained principal to be a principal that
executes for a short period and accesses only a few fine-grained objects.
Discuss the extent to which
the authorization benefits of fine-grained objects
can be achieved for each of the following
strategies.
-
Only employ coarse-grained objects, where you may define as many
different kinds of privileges and operations as necessary.
-
Only employ fine-grained principals, where you may define as many
different kinds of privileges and operations as necessary.
Problem 2:
In class, we discussed schemes for associating a
separate capability with each
different memory segment but not with each individual word.
Why?
Problem 3:
Capability-based addressing associates each object name
with the starting virtual address of that object.
But multiple objects might all start at the same address---for example,
a byte, a word, and a doubleword.
Are any problems caused by such overlap?
Explain why not or propose a naming scheme that does not suffer from
these problems.
Problem 4:
An analogy is often made between capabilities and movie tickets.
Suppose subjects correspond to people and each subject has access to
-
a copy machine that can be used to make genuine copies of any movie ticket,
-
a delivery service whereby a movie ticket can be transferred to any other subject.
Moreover, suppose the movie ticket has written on it (using indelible ink and
unalterable writing) the
operations allowed by the holder when that subject is present
in movie theater (eg viewing movie, getting popcorn, sitting in good
seats or bad seats, etc).
What functionality do we expect and require of a capability system that
is not present in the movie-theater analogy.
Problem 5:
An access control matrix is one way to depict an
assignment of privileges to subjects.
A CS5430 student has proposed using a directed graph instead.
(Recall, a directed graph is defined by (i) a set of nodes and (ii) a set of triples
("edges") of the form
< n1, n2, lab > where n1 and n2 are nodes
and lab is a label.)
Specifically, the student proposes:
- Having each node of the graph correspond to a single subject and/or an object.
(Recall, subjects are also considered objects.)
- For a node nP corresponding to a subject P and a node nO corresponding
to an object O, having an edge in the graph from nP to nO with label priv
if and only if subject P has privilege priv for object O.
And just as the access control matrix representation has commands
to change the assignment of privileges, you can imagine corresponding commands
to effect that change by manipulating the directed graph representation.
Discuss the relative expressive power of these two alternatives for
representing access control policies.
Are there situations that can be represented in one but not the other?
If so, give one;
if not, give a proof that none will exist.
Extra Credit:
Suppose at most one privilege can be granted to any single principal for each
given object.
Under this restriction, is the ``privilege propagation'' problem still undecidable?