Outline for May 5, 1997
- Greetings and Felicitations
- 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, ..., ok)
if r1 in
A[s1, o1] and
A[s2, o2] and
- Example 1: creating a file
create object f;
enter Own into A[p, f]
enter Read into A[p, f]
enter Write into A[p, f]
- Example 2: granting one process read rights to a file
command grant_read(p, q, f)
if Own in A[p, 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 genericv 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.
Notes by John Black:
You can get this document in
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 5/12/97