Re: Factory Pitfall shapj@us.ibm.com
Fri, 25 Dec 1998 20:13:23 -0500

One of the debates that Jonathan Adams and I had in connection with the EROS space bank design was whether the space bank should support a call of the form "how much space is left?" We concluded reluctantly that it had to.

However, we also concluded that a *limited* space bank (i.e. one that restricts allocation) should report the delta between current allocation and the limit. This raises a more interesting question: if there is a tighter limit imposed from above, which delta should be reported? My feeling is that the limit reported should be the one between your allocation limit and the current allocation -- i.e. the answer tells you how much space you are authorized to allocate, not how much space you will actually be *able* to allocate. (NB this is not consistent with the current EROS space bank implementation).

A separate question, then, is what happens when you go to allocate an object that is within your limit but some higher limit has been exhausted in such a way as to prevent allocation. There are only two possible designs:

  1. Allocation will be indefinitely delayed -- there is a promptness issue here.
  2. Allocation will fail.

Ultimately, we concluded that there was a need for a space bank providing guaranteed allocation. This is desirable in any case -- some applications need to know that their storage is densely allocated on the disk, so we would like to actually reserve the space prior to allocation. It is then relatively straightforward to guarantee to each user a lower bound on available space and then arbitrage the rest. If you are really paranoid, you can hand such a bank to a confined program.

My feeling is that if some program is actually exhausting shared storage you are likely to notice and ask what in tarnation it is doing. From a practical perspective, then, reporting available space this way may mitigate the problem.

shap

Norman Hardy <norm@netcom.com> on 12/24/98 02:56:01 PM

To: Ben Laurie <ben@algroup.co.uk>
cc: e-lang@eros.cis.upenn.edu (bcc: Jonathan S Shapiro/Watson/IBM) Subject: Re: Factory Pitfall

At 10:43 AM +0000 12/24/98, Ben Laurie wrote:
>Norman Hardy wrote:
>>
>> There is an avoidable pitfall in Factory usage.
>> The requester passes in a spacebank and if
>> that space bank buys and sells material from a general pool
>> (which is the current normal practice) than an unconfined
>> accomplice can obsereve the waxing and wayning of storage
>> and thus receive signals from code within the confined
>> environment. Banks can be configured to limit this
>> effect to zero or near zero at fairly small storage cost.
>>
>> This "covert channel" was found by preliminary formal
>> security analysis.
>
>Hmmm ... do you think it is possible to avoid covert channels?
>
Yes. Depending on your perspective you can either eliminate them or reduce them to a few bits per day. There are trade-offs; reducing bandwidth may require wasting, or at least mis-allocating resources. This is similar to bogus traffic on an enciphered line to reduce traffic analysis. There is an interesting patent on this which I will look for.

See "Cached Banks" in <http://www.agorics.com/KeyKos/Gnosis/66.html> about scheme that was proposed for the 370 Keykos, and implemented, I think, in the C version of the bank.
One can create an official sub bank with preallocated space. Such a bank can be passed to the confined object which can only draw on that space and thus not export any signals. Variations on that might allow dynamic adjustment of that limit providing a trade-off between covery channel bandwidth and storage efficiency.

This is a bit like the covert channel of counting the cars in the Pentagon parking lot.

More later.

Norman Hardy <http://www.mediacity.com/~norm>