Re: [Fresco-devel] [ReFresco 03] Proposed network architecture overview

On Sat, Jan 31, 2004 at 12:59:26AM +0100, Tobias Hunger wrote:
> > Messages also contain a second cap, to which any return values or
> > errors are to be reported.  If a program does not wish to receive any
> > response, this cap should be set to all zeroes; this is a special
> > address whose object is the equivalent of /dev/null -- it will eat any
> > messages sent to it and never do anything with them.
> 
> Isen't that very wasteful? I think we can expect those one-way messages
> to be rather small in the typical case.
> 
> Lets assume I want to send a integer (4 Bytes) to some object. That's
> 4 bytes of data, 16 Bytes to encode the recipient plus 16 zeros (=36
> bytes). If we had one byte as a message-identifier we could reduce that
> to 1 byte "one way message", 16 bytes recipient and 4 bytes data (21
> Bytes, a 40% reduction). We might need to a flag to mark fragmented
> packages or similar things, too.
> 
> Of course this spoils the elegant design;-)

Current packet layout in my prototype is as follows:
   1 octet: packet type identifier
      (Currently this is one of MESSAGE, MESSAGE_FRAGMENT,
       MESSAGE_FRAGMENT_END)
   4 octets: packet length
   <more data as depending on packet type, but basically just the to:
   cap, the reply-to: cap, and then data; fragments have an additional
   "fragment stream" field used for reassembly>

So there is a byte used for marking fragments, but it's not so useful
to overload it; having types MESSAGE_WITH_REPLY and
MESSAGE_WITHOUT_REPLY etc. would be silly.  Easy enough to add a
"feature" bitfield or something, though.

I can see the point of adding this.  But I want to see numbers for
real protocol use before deciding if we care.  In the local case (very
common!), bandwidth is near infinite, and saving a few bytes is not
going to make any difference.  In the remote case, it's not
unreasonable to assume on-the-wire compression, and 16 contiguous zero
bytes are going to compress pretty well.  So basically, for now I want
to keep simplicity, and it's easy to add this as a special case
optimization later when we have more data to fine tune things with.

> > This is the only
> > mechanism for matching requests with replies; we don't have sequence
> > numbers or anything like that, because replies need to not be
> > forgeable; only the object to whom we send the request should have the
> > capability to reply to it.
> 
> I still fail to see why we don't need sequence numbers. Is the cap thrown
> away after receiving a single message? What else stops me from resending
> a reply at a later time or sending several replies? If one cap requests
> some information from two others, how does it figure out which reply 
> came from where? Or can there be only one "open" request at any given
> time??

I suspect that often a cap will be thrown away after receiving a
single message, yes.  I know, I know, this sounds horribly wasteful.
But it's not like caps are in short supply; there are a lot of
bitstrings out there :-).  (If caps were in short supply, is
wouldn't just be an engineering annoyance, it would be an immediate
security hole.  So I don't feel bad about depending on their
plentitude.)  Besides which, it's the right way to do things.

I want to send out a message, and get back a response.  A
security-relevant question is, who do I want to get a response from?
It isn't good if just anyone can reply to my message; it doesn't
matter how much I trust the recipient if I can never tell whether I'm
talking to them or not.  Essentially, I want to give the recipient,
and only the recipient a new ability they didn't have before: to
respond to the particular message I just sent.  In a capability
system, this is exactly what we call "granting a capability".  So I
create a new cap and send it to them.  This has lots of advantages in
terms of simplicity and reasoning about the system; the ability to
reply follows exactly the same security model as everything else,
there's no special case.  E.g., the recipient automatically has the
option of delegating their response to someone else; they just pass
along the cap.

Besides which, let's think about what happens if we add sequence
numbers.  I'll assume that this means that instead of passing a cap
for replies to come to, we're either identifying the request using a
pair (connection, sequence number) or a pair (cap, sequence number).
Let's call this pair (C, S), I don't care which version we use.

Scenario 1: Say I send two messages:
      Me -> Message1(C, S_1) -> Alice
      Me -> Message2(C, S_2) -> Bob
      Alice -> Reply1(C, S_1) -> Me
      Bob -> Reply1(C, S_1) -> Me
All is well.

Scenario 2: I send a message to Alice:
      Me -> Message1(C, S_1) -> Alice
But Alice isn't interested in dealing with it (perhaps Alice is a
fulfilled promise), so she forwards it on to Carl:
      Alice -> Message1(C, S_1) -> Carl
Who replies:
      Carl -> Reply1(C, S_1) -> Me
All is well.

Scenario 3: I send two messages:
      Me -> Message1(C, S_1) -> Alice
      Me -> Message2(C, S_2) -> Mallory
Mallory has a guess that I've been talking to Alice, and doesn't like
the response Alice is going to give.  So Mallory uses his (legitimate)
knowledge of S_2 to guess S_1, and sends back a mock reply to Alice's
message, before Alice can:
      Mallory -> Reply1(C, S_1) -> Me
As far as I can tell, this is just like Scenario 2, and I trust
Mallory's malicious packet.  I lose.

Conclusion: S_1 and S_2 need to be chosen such that knowing S_2
doesn't help you in guessing S_1.  Obviously we can't use "sequence
numbers" literally; it would work to instead choose S_1 and S_2
randomly, if they're chosen from a large enough space.  4 bytes might
be enough, since there probably aren't many requests outstanding from
a single client at once.  But now you've reinvented caps, just a
parallel, incompatible system of them.  This means special cases
everywhere, etc.  (Think about when Alice wants to delegate to Carl.
She may not want to simply pass the message on directly; perhaps Alice
wants to know about errors encountered in reaching Carl, and insulate
me from them.  So Alice passes my cap in to Carl as a method argument
and sticks some cap of her own in the magic reply-to field.  But if
reply-to caps are different from other caps, then this requires a way
to marshal the special reply-to caps.)

You ask, "If one cap requests data from two others, how does it figure
out which reply came from where?".  This is somewhat confused; caps
don't make requests, connections make requests.  (Just like in normal
single process OO programming, where objects don't make method calls,
flows of control make method calls.)  If one bit of code needs the
replies from two messages, it should create two caps and use those.

I think I'll steal this reply and stick it in a rationale ReFresco
:-).

-- Nathaniel

-- 
Eternity is very long, especially towards the end.
  -- Woody Allen