[cap-talk] Claim: correct generic wrapping is not possible in principle

[Jonathan S. Shapiro]

On Sun, 2006-12-31 at 19:58 -0800, Jed Donnelley wrote:

> A general solution seems simple to me - namely partial buffering
> of messages, both for data and for capabilities.  This immediately
> occurs to me because it was the approach used in NLTSS (though
> there only for data as capabilities were data).

I suspect that you are once again thinking first about the network case.
Yes?

In the local case:

   Partial buffering with dynamic bound leads to unpredictable blocking
   behavior and kernel resource exhaustion.

   Partial buffering with static bound gives nominally predictable
   behavior, but pragmatically unpredictable behavior as programmers
   come to rely on the fact that short message sends always go to
   available buffer space. In practice, programmers come to assume that
   short messages are non-blocking and this has been observed to lead to
   deadlock in real systems.

   ANY buffering costs a factor of four in communication performance.
   There's really good measurement on this available in the literature.

So yes. Partial static buffering is good, and in the local case the
empirically correct number of bytes and capabilities to buffer is zero.

> Perhaps I should also point out that for long delays or
> issues managing receive buffers, the buffer sizes can
> be reduced to zero so that the receiver can be notified
> when any data is available (when buffers can be allocated).

In the local case, the concerns with buffering mostly aren't on the
receiver side. They are on the sender side.

There is exhaustive discussion of the (local case) IPC buffering issue
in the OSDI/SOSP literature, and it's now universally agreed that
buffering in the local case is very bad from almost every conceivable
perspective.

In the network case, buffering is inevitable and the source of a bunch
of problems.

> > > but this is
> > > not the main source of my objection.
> > >
> > > Let is consider solutions to (a):
> > >
> > >   (i)   We might assume infinite storage that is trusted to be promptly
> > >         allocatable. A system embedding this assumption is intrinsically
> > >         incorrect, because it does not admit ANY guarantee of liveness.
> > >
> > >   (ii)  We might ask somebody for the protocol schema. Ultimately, the
> > >         only party who *really* knows the protocol is the implementing
> > >         server. Unfortunately, if the object we are wrapping is hostile
> > >         it will lie (either to us or to the hypothetical protocol
> > >         registry).
> > >
> > >   (iii) We might rely on a higher-level protocol (one that the service
> > >         also relies on). For example, we might design the transport
> > >         layer to disclose to us how many bytes we received as distinct
> > >         from how many bytes were transmitted, providing a basis to
> > >         allocate more receive buffer and ask for a message retransmit.
> > >
> > >         Note, however, that this approach is not fully transparent,
> > >         because it may involve an observable deviation from the protocol
> > >         of the real object.
> > >
> > >   (iv)  We might implement unbounded message transmit, allowing storage
> > >         allocation while transmitting but admitting allocation failure
> > >         as a reason for transmission failure.
> > >
> > >         Unfortunately, this does not work when a server replies to a
> > >         presumed-untrusted client. This is a long, complicated issue.
> > >         The paper:
> > >
> > >           Vulnerabilities in Synchronous IPC Designs
> > >           http://www.eros-os.org/papers/IPC-Assurance.ps
> > >
> > >         scratches the surface, but isn't comprehensive.
> > >
> > > If we do not know the protocol, we cannot anticipate the maximal size of
> > > incoming messages that will be forwarded.
> > >
> > > As you try to sort out solutions to all of this,
> 
> Sorry, but I really don't see the problem.  The above issues are common
> to many network services and have been managed just fine for many years.

No. Respectfully, they have not. They have been universally "managed
just fine" only in systems that accept one of the constraints above. In
practice, the overwhelming majority of network systems blindly assume
infinite resource without actually checking that assumption.

However, I was focusing on the local case.

> 
> > > be sure to consider how
> > > your solution might be exploited by hostile clients to implement denial
> > > of resource and/or denial of service attacks.
> 
> Denial of service attacks can be a problem in any network service.

I was not concerned about network services. I was concerned about the
*local* case.

> I agree with this as well.  These issues exist today and are dealt
> with in current servers.  What do these resource issues have to
> do with wrapping?  I don't see anything in the above that's
> specific to the wrapping problem.

A correct wrapper must not issue errors or observable differences in
behavior w.r.t. the things that it wraps. If it needs to allocate
storage, and consequently needs to demand a message re-send, it isn't
doing a faithful virtualization.

Jed: please read the paper I cited. I'm simply not going to replay the
entire paper here when I've already dealt with this in the literature
with considerable care.
-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
+1 443 927 1719 x5100