Subject: [ogpx] type-system : eliminate closing tags for collections in binary serialization?

From: Meadhbh Hamrick <[email-masked]>
Date: Sun, 28 Mar 2010 10:34:17 -0700

so... just an idea...

the current type system draft, draft-hamrick-vwrap-type-system-00,
requires that maps or arrays that are serialized using the binary
serialization scheme have a closing tag in addition to an opening tag.
for example, to serialize the map:

{
  foo : string,
  bar : integer
}

you would use an opening tag of a left curly brace ('{') followed by a
32 bit count of the number of elements in the map, followed by the two
elements, followed by a closing tag of a right curly brace.

i have a vague concern that the closing tag is unneeded, may confuse
implementers and could lead to security concerns (at worst) or generic
errors (at best.) specifically, what happens when you don't have a
closing tag following the last element in the collection?

i don't think this is a "big deal," and we can certainly provide
guidance for implementers with properly worded statements about how we
think such situations should be handled.

and i think that making this change would require both opensim and LL
to modify their code, so i can totally understand if peeps would
rather keep the closing tag for collections.

but.. i think it would be a good idea to either a) eliminate the
closing tags or b) add some guidance to implementers about handling
encoding errors. i have a separate email coming up for guidance.

so, assuming we wanted to eliminate closing tags, we might want to
change section 4.3 to read thusly.

4.3. Binary Serialization

   The LLSD Binary Serialization is an encoding syntax appropriate for
   situations where high message entropy is required or limiting
   processing power for parsing messages is available.

   Encoding LLSD structured data using the binary serialization scheme
   involves generating tag, (optional) size values, and serialization of
   simple values.  Composite types are serialized by iterating across
   all members of the collection, serializing each simple or composite
   member in turn.  For each element in an
   LLSD structured data object, the following process is used to
   generate a binary output stream of serialized data:

   o  A one octet type tag is emitted to the output stream.  See the
      table below for tag octets.

   o  If the size of the element being serialized is variable (as it
      will be for strings, URIs, arrays and maps), the size or length of
      the element is output to the stream as a network-order 32 bit
      value.  Elements of types with fixed lengths such as undefined
      values, booleans, integers, reals, UUIDs and dates will not
      include size information in the output stream.

   o  Finally, the binary representation of the element is appended to
      the output stream.

   Undefined  Undefined values are serialized with a single exclamation
       point character ('!').  Undefined values append neither size
       information or data to the output stream.

   Boolean  True values are serialized with a single '1' character.
       False values are serialized with a single '0' character.
       Booleans append neither size information or data to the output
       stream.

   Integer  Integer values are serialized by emitting the 'i' character
       to the output stream followed by the four octets representing the
       integer's 32 bits in network order.

   Real  Real values are serialized by emitting the 'r' character to the
       output stream followed by the eight octets representing the real
       value's 64 bits in network order.

   String  String values are serialized by emitting the 's' character to
       the output stream followed by the string's length in octets
       represented as a network-order 32 bit integer, followed by the
       string's UTF-8 encoding.

   UUID  UUID values are serialized by emitting the 'u' character to the
       output stream followed by the sixteen octets representing the
       UUID's 128 bits, with the most significant byte coming first.

   Date  Date values are serialized by emitting the 'd' character to the
       output stream followed by the number of seconds since the start
       of the epoch, represented as a 64-bit real value.

   URI URI values are serialized by emitting the 'l' character to the
       output stream followed by the URI's length in octets represented
       as a network-order 32 bit integer, followed by the binary
       representation of the URI.

   Binary  Binary values are serialized by emitting the 'b' character to
       the output stream followed by the binary array's length in octets
       represented as a network-order 32 bit integer, followed by the
       octets of the binary array.

   Array  Arrays are serialized by emitting the left square bracket
       ('[') character, followed by the count of objects in the array
       represented as a network-order 32 bit integer, followed by each
       array element in order.  Note that compliant implementations MUST
       preserve the order of array elements.

   Map Maps are serialized by emitting the left curly brace ('{')
       character, followed by the count of objects in the map
       represented as a network-order 32 bit integer, followed by each
       key-value element.  Map keys are represented as strings except
       that they use the character 'k' instead of the character 's' as a
       tag.  Note that preserving the order of maps is not REQUIRED.

-cheers
-meadhbh

--
meadhbh hamrick * it's pronounced "maeve"
@OhMeadhbh * http://meadhbh.org/ * [email-masked]

---

From: "Robert G. Jakabosky" <[email-masked]>
Date: Sun, 28 Mar 2010 20:29:58 -0800

I vote to remove the closing tags, since they are redundant.

If the closing tags are kept in the spec, then they should only be used for 
validation (i.e. the number of objects contained between the opening & 
closing tag MUST match the "object count").

Also I vote that the spec require malformed binary/JSON/XML LLSD messages to 
be rejected.  This is very important for security reasons and it will make it 
easier for new implementations to be made, since there will be less 
convertion/corner case rules.

On Sunday 28, Meadhbh Hamrick wrote:
> _______________________________________________
> ogpx mailing list (VWRAP working group)
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ogpx

-- 
Robert G. Jakabosky

---

From: Han Sontse <[email-masked]>
Date: Sun, 28 Mar 2010 22:17:57 -0700

My instinct is to have the closing tag AND the object count.
And apply the rule that count MUST equal the enclosed objects.

Having both is a basic sanity check on the content.

Robert's comments earlier about potential to exploit the
protocol are found first within the ambiguities of the specification.

Being a little pedantic in the object structure is good for 
security and consistency.   Some things should not be shortcut
to save a few transmitted symbols.   UDP wrappers are a good
example why it's a bad idea.

~HS~

---

From: Joshua Bell <[email-masked]>
Date: Sun, 28 Mar 2010 22:34:56 -0700

I actually like having the extra characters in there, but I'm not picky.

However, having just implemented a binary serializer, it occurred to me that
the 'k' indicator for map keys is also unnecessary baggage. If we are truly
trying to minimize byte count, that could go too.

Also, the I-D calls out that "characters" are emitted into the stream, which
implies an encoding. Although UTF-8 is dictated for strings (and map keys),
for clarity we might want to describe the octets e.g. "Undefined values are
serialized as a single 0x21 octet (ASCII '!')" and so forth

---

From: "Robert G. Jakabosky" <[email-masked]>
Date: Sun, 28 Mar 2010 23:28:22 -0800

> protocol are found first within the ambiguities of the specification.

The main reason for my first e-mail was about the security issues related to 
being too lenient with malformed LLSD messages.  I am not going to complain 
too much if the current binary format is kept as is, as long as the rules are 
tightend to remove those ambiguities from the spec.

I am not a big fan of the current LLSD binary format, but it is not the worst 
binary format that I have seen.  I just hope that it isn't going to be used 
for the high-frequency low-latency messages needed for scene updates, since 
the cpu/latency cost of doing lookups on the map keys will be to high.

> example why it's a bad idea.

The issue with the SecondLife UDP protocol is how it is used to transfer 
reliable non-realtime messages, also it doesn't have support for 
encrypting/authenticating high security messages (i.e. money transfers).  
Which is why atleast some of those messages have been moved over to the 
https "Event queue".

The message encoding format isn't that bad, I like that it doesn't use tags in 
the encoded messages.

Here is an example of a nice data serialization system that doesn't require 
type info or tags to be encoded with every message:
http://hadoop.apache.org/avro/docs/current/spec.html

Avro uses JSON schema's to define records, enums, arrays, maps, unions, and 
fixed (i.e. binary values).  To handle forward/backwards compatibility, they 
have a section in the spec on schema resolution.  Avro even has a RPC 
protocol that allows the client/server to verify that they are both using the 
same schema.

I am not saying that VWRAP needs to switch from LLSD/LLIDL to Avro.  It is 
just a good idea to look at how other similar serialization systems have 
designed there binary protocols.

-- 
Robert G. Jakabosky

---

From: Dahlia Trimble <[email-masked]>
Date: Mon, 29 Mar 2010 01:08:19 -0700

I've used binary LLSD for scene update messages in a prototype viewer and
protocol for OpenSim, and I haven't found deserialization overhead to be an
issue. When you do things like sort 10000 scene nodes by distance from the
camera a couple times a second while you're also constructing 100+
procedural objects and hashing hundreds of material descriptions,
deserializing a few messages is insignificant. I suspect there's probably
other delay causing problems with LLSD in general, or possibly related to
the transport mechanism, but I haven't seen any specifically with binary
serialization/deserialization. Note: this was using the libomv
implementation.

On Mon, Mar 29, 2010 at 12:28 AM, Robert G. Jakabosky <[email-masked]
> wrote:

---

From: Joshua Bell <[email-masked]>
Date: Mon, 29 Mar 2010 08:39:15 -0700

FYI, I've rather experimentally created a ticket in the VWRAP trac for this:

http://trac.tools.ietf.org/wg/vwrap/trac/ticket/1

<http://trac.tools.ietf.org/wg/vwrap/trac/ticket/1>A list of active tickets
and links to RSS feeds (etc) can be found at:

http://trac.tools.ietf.org/wg/vwrap/trac/report/1

---

From: Meadhbh Hamrick <[email-masked]>
Date: Mon, 29 Mar 2010 08:54:20 -0700

this was supposed to go to the list as well.

---------- Forwarded message ----------
From: Meadhbh Hamrick <[email-masked]>
Date: Mon, Mar 29, 2010 at 8:53 AM
Subject: Re: [ogpx] type-system : eliminate closing tags for
collections in binary serialization?
To: Joshua Bell <[email-masked]>

thx josh.

and thx to peeps commenting on this thread. i had an intuitive sense
that such constructions could potentially lead to vulnerabilities.
seems like i'm not alone in that concern.

i was also thinking that we should be as resilient as possible in the
encoding, though there are some good arguments for barfing if you find
a poorly formed binary serialization.

what i had been thinking was you should try to recover as much
information from a poorly formed message. but i'm thinking this is an
error. messages _should_ be considered atomic. for instance:

<llsd>
 <map>
   <key>action</key>
   <string>launch</string>
   <key>object</key>
   <string>high yield thermonuclear devices</string>
   <key>only-if</key
   <string>nuclear_launch_detected() == true</string>
 </map>
</llsd>

the intent of this highly contrived message is to launch a retaliatory
strike should a missile launch be detected. but there's an error in
the serialization of the third key; the closing element is incomplete.
if we did as i had suggested, and attempted to recover as much data as
possible from a message, we might have inadvertently launched the high
yield thermonuclear devices.

so yeah. let's barf if we get an improperly serialized message.

this should probably go for all serializations as robert suggests.

-cheers
-meadhbh

On Mon, Mar 29, 2010 at 8:39 AM, Joshua Bell <[email-masked]> wrote:
> A list of active tickets and links to RSS feeds (etc) can be found at:

---

From: Joshua Bell <[email-masked]>
Date: Tue, 30 Mar 2010 11:12:36 -0700

On Sun, Mar 28, 2010 at 10:34 PM, Joshua Bell <[email-masked]> wrote:

> However, having just implemented a binary serializer, it occurred to me
> that the 'k' indicator for map keys is also unnecessary baggage. If we are
> truly trying to minimize byte count, that could go too.
>
>
To clarify the above:

Map keys are always strings, and keys occur in predictable locations in a
stream based on context. Therefore, strictly speaking, *no* tag is
necessary; a binary LLSD parser would always know when to begin parsing a
key, and could start immediately with reading the four-octet length.

(But I'm not advocating for the removal of unnecessary bytes.)