Factory Pitfall

shapj@us.ibm.com 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

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

1. Allocation will be indefinitely delayed -- there is a promptness issue
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.


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>