Capabilities and Covert Channels

A covert channel allows one program to gain information from another without using the system mechanisms designed to convey information. Butler Lampson introduces and illustrates many covert channels in his Confinement Problem paper. That paper spoke mainly of pairs of programs cooperating as sender and receiver. We include here programs that inadvertently send as alleged here.

Mark Miller suggested the following as an intractable confinement problem: The confined program, wishing nonetheless to transmit, first allocates an array rather larger than real memory. The program then examines the bits that it wishes to transmit and for each bit does if(bit) {touch each page in the array} else {compute for several seconds}. Standard coding tricks ensure sufficiently short strings of 0’s and 1’s. The covert observer notes the paging and computing availability and applies standard noisy channel error correction.

My counter to this strategy solves this problem, within limits, as well as another recently noted covert “pitfall”. The requestor, as he invokes some factory for a new instance, supplies a bank with preallocated storage. The preallocated storage will be much less than the amount of real RAM. Only the requestor learns when the allocation is exhausted as the confined object demands storage for his array. The requestor may then choose whether to kill the confined object or resort to tactics such as delaying by a noisy amount of time before furnishing more storage. The confined object is unaware of these events and is thus unable to compensate for the delays. (Keykos does not currently provide such a space bank variation. To do so would slightly expand everyone’s TCB.)

An alternative solution also supports hard real time. Paging and checkpoints as performed by the current Keykos kernel interferes with hard real time processing. Part of the solution to this is introduction of capabilities to occupy RAM. There are several designs that have been considered and some sound reasonable. This bollixes the pretty rule that only the kernel is aware of the difference between RAM and disk. On the other hand real time application design must distinguish these, while most programs need not. A compiler in such a system is entirely unconcerned with such issues, as in current Keykos. With RAM occupancy capabilities, the confined application does not even know how many page touches are required to cause a fault. The same trick can be used by the requestor by modulating the meter. The storage and CPU signals escape confinement but are delivered to the requestor.

This is not a crisp solution to the problem but the confinement mechanisms sound easier then the transmission mechanisms. I think that the battle leans heavily towards the confiner. See this for a more principled approach.

In short do not despair of confining a whale if you need only confine a minnow. Significant computer and intellectual resources, and perhaps guile, will be required to confine a whale. Perhaps information theory is necessary to confine whales efficiently. They can bang the wall harder!

Light Pink Book, and its kin
A patent 5,574,912 on a scheduler to avoid covert channels.
A known and tolerated covert channel to arrange for payment.
A detailed analysis of Covert Channels by the military community.