[prev in list] [next in list] [prev in thread] [next in thread] 

List:       cap-talk
Subject:    [cap-talk] Unstable output visibility (was: Waterken issues
From:       David-Sarah Hopwood <david-sarah () jacaranda ! org>
Date:       2011-02-06 5:36:09
Message-ID: 4D4E3349.3050807 () jacaranda ! org
[Download RAW message or body]

[Attachment #2 (multipart/signed)]


[cc:d to cap-talk from friam@googlegroups.com]

On 2011-02-06 01:00, Mark S. Miller wrote:
> On Sat, Feb 5, 2011 at 3:34 PM, David-Sarah Hopwood <
> david-sarah@jacaranda.org> wrote:
> 
>> On 2011-02-05 22:20, Tyler Close wrote:
>>> On Fri, Feb 4, 2011 at 5:14 PM, Bill Frantz <frantz@pwpconsult.com>
>> wrote:
>>>> It was also observed that if a Waterken server has a non-empty input
>>>> queue at the end of a turn, it can delay writing the checkpoint to disk
>>>> and returning the results until the end of the next turn at the cost of
>>>> response time for the first request. For a heavily loaded server this
>>>> technique may be a useful way of load shedding.
>>>
>>> That's interesting, I hadn't considered that. Potentially a very
>>> valuable optimization given the cost of a sync operation.
>>
>> The delay can be over multiple turns as long as the input queue continues
>> to be non-empty, and the checkpoint is written before returning any results.
>> I'd suggest limiting the maximum delay time, though.
>>
>> Especially if the results are large, it might be worthwhile to return them
>> up to, but not including a marker saying that they are complete, then
>> checkpoint, then send the marker. ("I'm not really telling you this...
>> checkpoint... ok, now I told you.") The recipient would not be allowed to
>> do anything that irreversibly depends on the results until it has seen the
>> marker, but is allowed to speculate based on them.

Note that the same potential optimization applies to sent messages:
("I'm not really sending this yet... checkpoint... ok, now I sent it.")
The hazard of revealing secret information described below seems to be
the same with either sent messages or with results, so I think there are
no security grounds to apply the optimization to one but not the other.
In more Actor-like models there is no distinction between sending a
message and sending a result to a customer, of course, although in
Waterken there is.

Oh, I notice that <http://www.eros-os.org/pipermail/e-lang/2001-December
/005931.html> has this optimization. (Is that 10 years ago? I feel old :-)

Note that you can send the data while not revealing it to the recipient,
by encrypting it (or maybe only encrypting representations of new
capabilities not previously known to the recipient), and then sending the
decryption key as the confirmation. This might make sense if the network
is slow but crypto is cheap. It doesn't allow the recipient to speculate,
though.

> There's an interesting hazard here that we may or may not decide to live
> with -- depending on the degree to which we're trying to mask failure under
> mutual suspicion.
> 
> Say the info that VatA is not really telling VatB includes a secret. Perhaps
> an authorizing secret or perhaps not. In either case, if VatA crashes and
> then proceeds fwd in a different manner, so that it does not chose to tell
> VatB what it previously almost told VatB, VatB still knows what it wasn't
> "really" told.

Yes. However, the original VatA had already decided to tell VatB the secret.
There can therefore only be a security problem if the resumed VatA relies on
VatB not knowing the secret, because the resumed VatA *didn't* tell it (as
opposed to *couldn't have* told it).

That isn't entirely implausible. For example, there are some cryptographic
protocols in which you randomly choose which of several secrets to reveal,
and then rely on the fact that you only revealed one of them. A simple
example is the Lamport signature scheme:
<http://en.wikipedia.org/wiki/Lamport_signature>
(My impression is that such protocols are more popular in the crypto
literature than in actual practice.)

I tried to find a clear statement in the Waterken documentation about
whether an application is permitted to rely on the changes to vat state
in a turn having been checkpointed before any output from that turn is
visible to other vats. The nearest thing I could find was this in section
2.2 of 'Introduction to Waterken Programming'
<http://www.hpl.hp.com/techreports/2010/HPL-2010-89.html>:

# If the state of objects is changed or a message is sent to a remote object
# during a turn, a checkpoint is taken automatically at the end of the turn
# as part of the process of returning the answer and sending new eventual
# messages that were initiated during the turn itself. As a consequence, the
# programmer never has to worry about where a might vat [sic] crash and
# doesn't need to know whether a particular message was sent, or whether it
# was received. ...

but I think that can be read either way.

I also tried to determine whether "output validity" as defined in
<http://www.hpl.hp.com/techreports/2010/HPL-2010-155.html> guarantees to
avoid this hazard. It seems to depend on whether we consider the contents
of messages and results observable to any potential attacker to be an
"output" of the system.

OTOH, the description of the "Ken" protocol described in that paper does
say that Ken does not make messages and results visible until after a
checkpoint:

# Outputs and messages sent by the processing function during a turn are
# buffered in the output queue until the end of the turn, when they are
# checkpointed to stable storage along with application state; only then
# are they transmitted/written and thus visible outside the process.

> This is similar to but not as bad as hangover inconsistency, which E does
> live with, but which Tyler has since convinced me was a mistake.

I also think it's a mistake, but I think so *because* we can do these
optimizations while still avoiding it :-)

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com


["signature.asc" (application/pgp-signature)]

_______________________________________________
cap-talk mailing list
cap-talk@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/cap-talk


[prev in list] [next in list] [prev in thread] [next in thread]