Outline for April 6, 2000
- 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
r2 in A[s2, o2] and
rm in A[sm, om]
- Example 1: creating a file
command create_file(p, f)
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]
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
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.
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 4/6/2000