Due November 9. Submit your solution on paper in class. No late assignments will be accepted.
To facilitate grading, format your solutions as follows.
Solutions that do not satisfy the formatting guidelines will be returned, ungraded.
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.
c_{H}[m_{L}] = n_{L};
o_{L} = d_{L}[p_{H}];
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 
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.
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].x
is actually equal to 3. How much information, measured in bits, did the attacker gain from
experiment E?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.
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.
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.