Outline for April 11, 2000

  1. Greetings and felicitations!
    1. Homework
    2. Handouts
  2. General case: It is undecidable whether a given state of a given protection system is safe for a given generic right.
    1. Represent TM as ACM; reduce halting problem to it
  3. Take-Grant
    1. Introduce as counterpoint to HRU result
    2. Show bridges (as a combination of terminal and initial spans)
    3. Show islands (maximal subject-only tg-connected subgraphs)
    4. can·share(r, x, y, G0) iff there is an edge from x to y labelled r in G0, or all of the following hold:
      1. there is a vertex y'' with an edge from y' to y labelled r;
      2. there is a subject y' which terminally spans to y'', or y' = y'';
      3. there is a subject x' which initially spans to x, or x' = x; and
      4. there is a sequence of islands I1, ..., In connected by bridges for which x' is in I1 and y' is in In.
    5. Describe can·steal; don't state theorem
  4. Decidability vs. Undecidability
    1. Notion of type; subject, object types
    2. Attenuation
    3. If attenuating acyclic, it's decidable; so that is sufficient. Open question: is it necessary?

Send email to bishop@cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562

Page last modified on 4/12/2000