meaning of 'no change limits'

[Jonathan S. Shapiro]

> I suppose this a public operation versus private operation
> question, but in practice, given the two alternatives:
> 	1. emit "no change limit", reduce space allocation, use less space
> 	2. emit nothing, use less space
> ....

I'm not sure what you meant by 'emit'.  Oh.  Now I see.

Charlie Landau and I had a conversation about this last night by phone
and came to a resolution of sorts.  I'll first describe the problem
and then the solution and an interesting challenge.  Those of you from
the KeyKOS group who know the problem already may just want to skip
the problem description.

THE PROBLEM

Consider two subsystems, one confined, the other a collaborator, both
operating on behalf of the same user and therefore using space banks
descended from the user's bank:


			P = user's (parent) bank
                       / \
                      /   -------------
       +-----------  / ------+    +--  \  ------------------+
       | child bank  C0      |    |    C1  child bank       |
       | (unconfined subsys) |    |    (confined subsys)    |
       +---------------------+    +-------------------------+

The confined subsystem wishes to leak information to the unconfined
subsystem (the collaborator) so that the collaborator can transmit it
off the machine.

P is any common parent bank, no necessarily the user's master bank.

A problem arises if the following combination of events occurs:

	1. limit(P) <= limit(C0)    this is common
	2. limit(P) <= limit(C1)    this is common
        3. There exists an operation by which a caller can ask a bank
           how many pages are actually available for allocation right
           now (this exposes allocations on P to C0, C1, which is the
	   source of the channel).

The channel is intrinsic -- the same information can be discovered by
the simple expedient of trying to exhaust P's space, but in that case
somebody is rather likely to notice..  The third condition means that
I don't have to exhaust the parent bank's space to communicate.

THE RESOLUTION

Charlie Landau points out that since the window of vulnerability
cannot be closed, the delta in bandwidth is small, and the
functionality (knowing how much space is left) is extremely useful,
removing the query operation is the wrong thing to do and another
solution should be sought.

I'ld add that if the program is going to leak information anyway I'ld
rather it not disrupt the rest of my world by exhausting their space :-)

The correct solution is to implement space reserves.  Have a mechanism
by which a user can say "reserve X pages for this bank NOW (ahead of
time), and don't let it allocate past the hard ceiling.  This
basically puts an upward information flow wall  at the top of C0 and
C1.

CHALLENGE

I would be very interested if someone would attempt to write a
transmission program that would *use* this hole so we could endeavour
to measure the bandwidth.  It shouldn't be hard for someone who knows
about error correction in the face of noisy channels (there are third
parties allocating on the bank), but *I* don't have the know-how to do
it.

We're doing a familiarization handoff to Charlie Landau this
afternoon.  If you want to try to take on this challenge, please let
me know and I'll let you know where the handoff can be found.

Unless you are eager for problems, I don't recommend this handoff.
We'll have a much more stable one in a week or so.



shap