Outline for May 19, 1997

1. Greetings and Felicitations
2. Discuss covert channels
   1. confinement problem
   2. storage channels
   3. timing channels
3. Non-deducibility and non-interference policies: can these be composed?
   1. Non-deducibility security: prevent one set of users from deducing information from another set of user's actions
   2. Non-interference security: prevent one set of users from being interfered with as a result of another set of user's actions
4. Machine model
   1. Set of users with security labels High, Low
   2. Set of possible sequences of inputs from users and outputs to users
   3. Trace: interleaving of input and output in a "meaningful" order (eg, temporal)
5. Non-deducibility secure
   1. Means: for every security label x and defined trace, there is a second trace that exhibits the same behavior that is visible to users with security labels <= x, but which has no inputs that are not <= x.
   2. Implies: higher inputs don't affect output from the point of view of lower subject
   3. If system is NDS, low users can't obtain new information if additional high users are allowed to provide inputs
   4. If system is NDS, and low users can determine specific sets of information based on their interpretation of observed behavior, then removal of the high users should not change the information obtainable by low users
   5. Example: high user inputs into system, low user given parity of number of inputs (both high and low). Assumption: low user cannot examine inputs or the information they contain (as must look like high user not even present). But can observe parity of number of inputs (say, by looking at final value of toggle). This gives a covert channel (high can send messages to low 1 bit at a time) and so is not NDS secure. Fix: introduce high-level outputs, add them into parity.
6. Question: if two NDS systems are composed, is the result NDS?
   1. System A: 2 input, output channels; rules follow:
      • HIGH USER INPUT: user gives both high, low inputs to left input channel of A; no-one else can cause such inputs;
      • SYSTEM-GENERATED OUTPUT: Random high and low outputs to external environment on right channel only; user can't affect it
      • ENVIRONMENT INPUT: Arbitrary inputs, high and low, on right; unaffected by other inputs, and no effect on output
      • LOW USER OUTPUT: Low level user can observe low-level inputs, outputs of A; can never see high inputs, outputs
      • STOP TERMINATION: System A reaches klow level output called STOP. Only 1 more piece of I/O.
        PARITY OUTPUT: On STOP, low output is number of high-level inputs and outputs.
   2. System A examples:
      • One low output (STOP), final low output EVEN (0 high inputs, outputs)
      • 1 low input, 1 high input, 2 low outputs (inc. STOP), final low output ODD
      • 2 high inputs, 1 low input, 1 low output (STOP), low final output EVEN
   3. System B: line System A, but all input into left; none on right, and otherwise right and left are exchanged (eg., B gets STOP input on left).
   4. Note: A, B are NDS as a high-level user can't pass info to low-level user; uncertainty of inuts from environment make this so
   5. Compose them. A on left, B on ight, left/right inputs/outputs hooked together in the obvious way. Assumptions:
      • A sends STOP to B; atomic in transit, ie, no subsequent output of B sent to A after STOP sent but before it is received
      • right channels of A hooked to left channels of B, ie, no stray inputs, outputs
   6. Problem: high user passes high inputs to left channel of A; low level user observes parity outputs of A and B. By symmetry, parity between A and B is ALWAYS 0 (as each input has a corresponding output incident on A or B, and vice versa). Hence if observed parity valuues for A and B are the same, even number of inputs to left channel of A; if parity values differ, the number of inputs is odd. Hence not NDS.
7. Non-Interference Security System Model
   1. { u₁, ..., u_n } users with security labels (HIGH or LOW)
   2. { w₁, ..., w_n } inputs from user i
   3. W is single stream input merged from all n inputs in { w₁, ..., w_n }
   4. { [w, 1], ..., [w, n] } n output sequences, where [w, i] is the output seen by user i with respect to the merged input stream w
   5. PG_j([w, i]) is output sequence resulting from input sequence w with all input from u_j removed
   6. System is NIS if for all users, the output sequence is the same as the output sequence purged of input from higher sources, i.e.,
      label(u_i) > label(u_j) => [w, j] = PG_i([w, j])