Outline for January 19, 1999
- Greetings and felicitations!
- lassen should be reachable from anywhere in the department. I'm
working on having it recognize the rest of the Internet!
- ACM and primitive operations
- Go over subjects, objects (includes subjects), and state (S,
O, A) where A is ACM
- Transitions modify ACM entries; primitive operations follow
- enter r into A[s,o]
- delete r from A[s,o]
- create subject s' (note A[s',x] =
A[x,s'] = ø for all x)
- create object o' (note A[x,o'] = ø
for all x)
- destroy subject s'
- destroy object o'
- command c(s1, ..., sk, o1, ...,
if r1 in A[s1, o1]
r2 in A[s2, o2] and
rm in A[sm, om]
- Example 1: creating a file
create object f;
Own into A[p, f]
Read into A[p, f]
Write into A[p, f]
- Example 2:granting one process read rights to a file
grant_read(p, q, f)
if Own in A[p, f]
enter Read into A[q, f]
- What is the safety question?
- An unauthorized state is one in which a generic right r could be
leaked into an entry in the ACM that did not previously contain r. An
initial state is safe for r if it cannot lead to a state in which
r could be leaked.
- Question: in a given arbitrary protection system, is safety decidable?
- Mono-operational protection systems: decidable
- Theorem: there is an algorithm that decides whether a given mono-operational
system and initial state is safe for a given generic right.
- Proof: finite number of command sequences; can eliminate delete,
Ignore more than one create as all others are
conditioned on access rights in the matrix. (One exception: no subjects;
then we need one create subject).
Bound: s number of subjects
(possibly one more than in original), o number of objects (same),
g number of generic rights; number of command sequences to inspect is
at most 2gso.
- General case: It is undecidable whether a given state of a given protection
system is safe for a given generic right.
- Represent TM as ACM; reduce halting problem to it
You can get this document in
Framemaker+SGML version 5.5,
PDF (for Acrobat 3.0 or later),
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 1/20/99