CS513 Homework 5

CS513 Homework 5: Information Flow

General Instructions. You are expected to work alone on this assignment.

Due November 9. Submit your solution on paper in class. No late assignments will be accepted.

To facilitate grading, format your solutions as follows.

Put your name and net id on each page of your solution.
Typeset your solution, using 10 point or larger font, and use 8.5 x 11 inch paper.
For problems 1 and 2, use at most one page (both sides, if necessary) for each problem. See problem 3 for its page limit.
Start each problem's solution on a separate side.

Solutions that do not satisfy the formatting guidelines will be returned, ungraded.

Problem 1: Arrays

Suppose we add heap allocated arrays (as in Java) to our language. So, we may have assignment statements of the following forms.

    a[i] = j;
       j = a[i];
       a = b;

In the final statement above, a and b are both arrays. The effect of the statement is to cause both a and b to refer to the same array on the heap; that is, the array is aliased by a and b. Thus, if "a = b; b[j] = i;" is executed, both a[j] and b[j] will be equal to i. Assume that all array indices are always within bounds.

Examine the following three statements, whose variables are subscripted by confidentiality labels. Explain which statements are secure, which are insecure, and why. Variables c, d, e, and f are arrays; m, n, o, and p are integers.
1. c_H[m_L] = n_L;
2. o_L = d_L[p_H];
3. e_L = f_H;
The rules below are proposed to check information flow for arrays. The first rule allows array element selection (e.g., a[i]) as part of expression E. Variables in expressions may be arrays or scalars. In the first rule, x may be either an array variable or a scalar variable, but it may not be an array element selection. In the second rule, a is an array. Do these rules enforce a secure information flow policy (that is, do they enforce noninterference)? Exhibit either a proof or a counterexample.

C ≤ x E ≤ x		C ≤ a E1 ≤ a E2 ≤ a

x = E sif pc = C		a[E1] = E2 sif pc = C

Problem 2: Measuring Information Flow

Let x, y, and z be integer variables in the range [0,15]. Let x and y be high confidentiality variables and z be low confidentiality. Consider this program:
```
y = rand(16); 
z = x ^ y;
```
Here, rand(N) returns a random integer r chosen uniformly such that 0 <= r < N, and x ^ y denotes the bitwise exclusive OR of x and y. Assume that before execution of this program, the attacker believes that all values of x are equally likely (this is the attacker's prebelief). Suppose that in a particular experiment E, the attacker observes that z equals 7 on output.
1. After running experiment E, what is the attacker's belief, expressed as a probability distribution, about the value of x? (This is the attacker's postbelief.) Hint: it may be helpful to consider first the case where the variables range only over [0,1].
2. Suppose that x is actually equal to 3. How much information, measured in bits, did the attacker gain from experiment E?
Consider the password checker:
```
if (g == p) { 
  a = 1; 
} else { 
  a = 0; 
}
```
Suppose that passwords are k bits, and that the attacker initially believes that all passwords are equally likely.
1. What is the maximum amount of information that the attacker can gain from any experiment in which he guesses incorrectly?
2. How large must passwords be, in bits, to ensure that the password checker leaks no more than 10^-4 bits of information when the attacker guesses incorrectly?

Problem 3: Covert Channels

Covert channels allow two processes to communicate even when the processes are prohibited from directly communicating. We mentioned two examples of covert channels in lecture: file locking and system load. Some covert channels, like system load, are not very reliable because the receiver does not necessarily receive exactly the same message the sender sent.

Implement one of these covert channels (or another of your design) in the language of your choice.
Experiment to determine the tradeoff between the bandwidth of your channel (the number of bits it can transmit per second) and the reliability of your channel (the percentage of bits that are received correctly). Present the results in one or more charts, and discuss any interesting features these charts reveal.
[Extra Credit] Design a defense that could be employed against your channel. Implement your defense, then repeat your experiments. Present and discuss your new results. Discuss the effectiveness of your defense and the impact it might have on users of the system.

Submit your source code and results on paper; you do not need to submit anything electronically. You may use up to two pages (both sides) for your results, plus an additional two pages (both sides) for the extra credit. There is no page limitation on your source code. Concentrate on being clear and convincing in your description of the channel, explanation of your methodology, and presentation and discussion of the results.