Outline for April 3, 2003

1. Principle of Complete Mediation
   1. All accesses must be checked
   2. Forces system-wide view of controls
   3. Sources of requests must be identified correatly
   4. Source of problems: caching (because it may not reflect the state of the system correctly); examples are race conditions, DNS poisoning
2. Principle of Open Design
   1. Designs are open so everyone can examine them and know the limits of the security provided
   2. Does not apply to cryptographic keys
   3. Acceptance of reality: they can get this info anyway
3. Principle of Separation of Privilege
   1. Require multiple conditions to be satisfied before granting permission/access/etc.
   2. Advantage: 2 accidents/errors/etc. must happen together to trigger failure
4. Principle of Least Common Mechanism
   1. Minimize sharing
   2. New service: in kernel or as a library routine? Latter is better, as each user gets their own copy
5. Principle of Psychological Acceptability
   1. Willingness to use the mechanisms
   2. Understanding model
   3. Matching user's goal
6. ACM and primitive operations
   1. Go over subjects, objects (includes subjects), and state (S, O, A) where A is ACM
   2. Transitions modify ACM entries; primitive operations follow
   3. enter r into A[s,o]
   4. delete r from A[s,o]
   5. create subject s' (note A[s',x] = A[x,s'] = NULLSET for all x)
   6. create object o' (note A[x,o'] = NULLSET for all x)
   7. destroy subject s'
   8. destroy object o'
7. Commands
   1. command c(s₁, ..., s_k, o₁, ..., o_k)
      if r₁ in A[s₁, o₁] and
          r₂ in A[s₂, o₂] and
          ...
          r_m in A[s_m, o_m]
      then
          op₁;
          op₂;
          ...;
          op_n;
      end.
   2. 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]
      end.
   3. Example 2:granting one process read rights to a file
      command grant_read(p, q, f)
      if Own in A[p, f]
      then
          enter Read into A[q, f]
      end.
8. What is the safety question?
   1. 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.
   2. Question: in a given arbitrary protection system, is safety decidable?
   3. Mono-operational protection systems: decidable
   4. 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, destroy.
      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 2^{g(s+1)(o+1) + 1}.
9. 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