[cap-talk] Wall banging (was: Bellizzomi - Capabilities and Shapiro's focus, Coyotos, etc.)

David Wagner daw at cs.berkeley.edu
Wed Nov 29 14:36:07 CST 2006

Toby Murray writes:
>On Wed, 2006-11-29 at 10:31 -0600, Karp, Alan H wrote:
>> While you can't prevent wall banging, you can prevent wall listening by
>> removing all forms of indeterminacy, such as access to the system clock.
>> Any process that is deterministically replayable meets this criterion.
>Are there generally accepted definitions for "indeterminacy" and
>"deterministically replayable"? If so, how do these definitions relate
>to non-interference? At first glance, it would seem that they are
>intrinsically linked to me.

Deterministic: A computational process whose behavior and output is a
deterministic function of its inputs (and only the inputs explicitly
provided, and not any other implicit values).

Deterministically replayable: A computational process that makes a record
of every nondeterministic choice, sufficient so that given the (explicit)
inputs and the non-determinism log you can replay the process and get
the exact same behavior and output every time.  Note that deterministic
processes are automatically deterministically replayable (d.r.); they are the
trivial case where you never need to write anything to the log.

Transforming a program into d.r. form often makes implicit inputs
more obvious.  For instance, if your behavior or output depends upon
the time of day, random number sources, packets read from the input,
scheduling decisions made by the OS, etc., then the act of rendering
the program d.r. will usually make this fact apparent.

Deterministic processes are unable to listen to covert channels.  This is
useful, because one way to "deafen" a process so that it cannot listen
to wallbanging is to place it into deterministic form (if possible).
You can't, in general, say the same thing about d.r.  processes.
The behavior of d.r. processes can still depend implicitly on any number
of side sources of non-determinism (such as OS scheduling decisions), so
d.r. processes can still listen to covert channels.  However, transforming
a program into d.r. form may aid covert channel analysis by making it
easier to see what kinds of covert channels it might be able to listen to.

Non-interference is trickier.  I may write about this subject later,
when I have more time, if there is interest.  But roughly speaking, if
a LOW process is running on the same system as a HIGH process, and the
LOW process cannot listen to covert channels, then the combination of
the two processes forms a computational system that ought to satisfy the
non-interference property (I think).  Be warned, though: non-interference
is too weak of a notion; a system can satisfy non-interference but still
be subject to covert channels.  Hence the introduction of notions such
as probabilistic non-interference.

More information about the cap-talk mailing list