Subject: [ogpx] type-system : guidance for binary serialization implementers

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

so this has stuck in my craw for a couple weeks, finally remembering
to post it to the list.

the JSON and XML serialization schemes use well known grammars that
have wide adoption. not so for the binary serialization. so if i
wanted to write an XML parser, i would have a lot of 3rd party
resources and discussion to guide me. specifically when it comes to
handling errors.

as i was writing my own implementation of the LLSD binary
serialization scheme, a couple issues came up.

i think we should *somewhere* address them. either as a section of the
type-system document, or as an informational RFC. i would like to have
clear guidance for how implementers would handle the following
exceptional events.

one of the things we were trying to do was make a type system and
serialization schemes that were resilient in the face of error. so i
think there's a strong preference that we recover as best we can from
an error instead of throwing up our hands and just saying "error!"

i would actually go and look at how LL implemented the binary
serialization (i'm sure it's in the viewer code somewhere) but i'm in
the middle of my gnu/bsd cool down period, and i don't want to reset
the timer. i think there may be other people in the same situation,
which is why we should have a document describing what we should do in
the face of parsing errors.

so... if someone out there who's more of a viewer person wants to look
at the linden implementation and describe it's behavior in a textual
format, and then someone wants to look at the opensim implementation
and describe it's behavior in a textual format, we could then document
how things work and avoid this situation for other people.

here's a list of encoding / decoding errors i think about, along with
suggestions for how to handle them.

1. the object count following the opening tag ('{' or '[') is less
than the actual number of objects in the collection. (that is, the
closing tag is not found after iterating through "object count" number
of elements, but is found later in the stream.)

the "simple" thing to do would be to simply say, "the array ends after
$(OBJECT_COUNT) number of elements, even if there's not a closing
tag."

the "smart" thing to do would be to look at the LLIDL definition of
the array you're parsing and try to come up with a "best fit" for
what's supposed to be there vs. what's actually there. in other words,
you look at the LLIDL and if it says you're supposed to have three
elements in the array and you have three elements in the array, then
you're done. or maybe you're supposed to have one additional element
in the array.

the "smart" thing to do could get quite complicated while the "simple"
thing is sure to introduce failures the "smart" thing could recover
from.

2. the object count following the opening tag ('{' or '[') is greater
than the actual number of objects in the collection. (that is, you get
a closing tag before "object count" number of elements)

the "simple" thing to do is to simply say, "a closing tag ends the collection"

combining this with the previous error case, we could say, "a
collection continues until the closing tag is reached or
$(OBJECT_COUNT) elements are found in the collection."

3. there is no closing tag. (that is, after "object count" number of
elements, you find a tag that is not a '}' or a ']'.)

this is more or less the same as error case number 1 above.

though i wonder if it makes sense to differentiate the two cases. if
we were, we would have to have the smarts enough to look forward in
the stream, count the number of opening tags, then count the number of
closing tags and see if they're unbalanced. ugh.

4. lack of 'k' elements in a map. (that is, you haven't reached the
"object count" number of elements and are expecting a 'k' but get
something else.)

my druthers would be to say, if you encounter a type that can be
converted to a string, you just do the conversion and use the result
as the key.

another way to handle it would be to ignore it.

5. you encounter a bare 'k'. (that is, you encounter a 'k' tag outside
the context of a map.)

i vote for "convert to string"

6. duplicate keys in a map. (actually this applies to all serializations)

i vote for "the last key in the map with the same name wins." that is,
if you have two or more keys with the same name, the one found
furthest in the stream is the one that's used.

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

---

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

> an error instead of throwing up our hands and just saying "error!"

One primary source of decoding errors (i.e. LLSD message that doesn't follow 
the spec) will be from attackers (DOS attacks, remote code execution).  There 
is a big difference between handling unknown tags (to support future 
extentions) vs. trying to recover from a bad LLSD message and passing it on.  
The spec should allow for future extentions to be ignored by old 
implementations, but bad LLSD messages shouldn't be ignored, it will just 
hide normal bugs and make it harder to create new implementations (since you 
will not get useful decoding errors).

> of elements, but is found later in the stream.)

If closing tags are kept in the spec, then just reject the LLSD message as 
malformed.  What would you do if the same LLSD message was serialized in the 
XML format and the ending </array> or </map> tags where missing?

If the object count doesn't match the number of objects before the closing tag 
is found, then the LLSD message should be rejected with some error sent back 
to the sender.

> a closing tag before "object count" number of elements)

Same as case 1, just reject the LLSD message.

> closing tags and see if they're unbalanced. ugh.

Doing this type of analysis would be fine for a verification tool, but not for 
a protocol decoder in a client/server program.  The more complex the decoder 
logic is the more likely it will have bugs that an attacker can exploit.

Also if the decoder should continue parsing the array/map until it finds the 
closing tag, then the "object count" is completely redundant and a waste of 
bandwidth.  Either drop the "object count" or the closing tags.

I would prefer the "object count" over the closing tags, also it would be nice 
if the "object count" was a "Base 128 Varint" instead of a fixed length 32bit 
integer:
http://code.google.com/apis/protocolbuffers/docs/encoding.html#varints

> converted to a string, you just do the conversion and use the result

Then why not just allow any type that can be converted to a string be used as 
a key in the maps?  How would you handle this for the XML encoding formats?

> another way to handle it would be to ignore it.

It should be a malformed error (with details about why it is malformed for 
easier debugging).

> i vote for "convert to string"

This would just hide errors caused by a bad implementation of the LLSD binary 
encoder.  If you find a 'k' tag outside a map, then there might be some 
bigger problem.  Maybe the last map had more objects then the "object count" 
said.

> furthest in the stream is the one that's used.

This issue is not unique to the binary format, both the XML & JSON formats 
will have this issue too.  The JSON specs RFC4627 section 2.2 says that the 
names of object members SHOULD be unique, but it doesn't say how duplicate 
names are to be handled.

Section "2.2.2.  Map" of the LLSD draft says "Within a given Map value, each 
key must be unique, each with one value. ....".

Either that should be changed to a "each key MUST be unique", in which case 
duplicate keys would generate a malformed error with the whole LLSD message 
being rejected, or it should be changed to a "MUST"/"REQUIRED" rule on how to 
handle duplicates.

Having strict rules in the spec on how to handle malformed LLSD message is 
important, since a security hole can exist if two LLSD implementations 
interpret/decode the same LLSD message differently.  There has been a similar 
issue with HTTP proxies (sneaking a second HTTP request passed the proxy to a 
backend HTTP server).

Lets say you have a proxy/authenticator in front of a set of backend servers 
that will consume LLSD messages:

"VWRAP client(attacker)" -> "public frontend proxy/authenticator" -> "private 
backend server"

The "public frontend" proxy server would decode the LLSD message to apply some 
routing or authentication rules (i.e. check user id & credentials) before 
passing the original (not a re-encoded message) LLSD message to a "private 
backend" server for handling.  The attacker could trick the frontend server 
into routing a LLSD message with any user id they want to the backend server.  
This could easily happend if the proxy server was written/made by a different 
company (i.e. Cisco VWRAP load balancer), then the backend server and the two 
implementations of LLSD used different rules for how to handle duplicate keys 
("user id" or "credential" keys).  The same thing can happen if one of the 
two implementations ignore incorrect "object counts" or missing closing tags.

I will be commenting more on the other "type-system" e-mails soon.

P.S. will this mailling list change it's name to "vwrap" soon?  I know the 
vwrap jabber.ietf.org channel has already been created.

-- 
Robert G. Jakabosky

---

From: Dahlia Trimble <[email-masked]>
Date: Sun, 28 Mar 2010 21:04:19 -0700

OpenSim in general uses the serializer and deserializer classes in
libOpenmetaverse (1). There may be a few lingering places in the code base
where they are hard coded with other methods, but I suspect they would be
converted to using the libOpenmetaverse implementation rather than be
modified to conform to any spec modifications.

1. http://www.openmetaverse.org/projects/libopenmetaverse

<http://www.openmetaverse.org/projects/libopenmetaverse>
On Sun, Mar 28, 2010 at 10:34 AM, Meadhbh Hamrick <[email-masked]>wrote:

> _______________________________________________
> ogpx mailing list (VWRAP working group)
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ogpx
>

---

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

Here is a link to the LLSD binary implementation from libopenmetaverse:
http://openmetaverse.org/viewvc/index.cgi/omf/libopenmetaverse/trunk/OpenMetaverse.StructuredData/LLSD/BinaryLLSD.cs?revision=2507&view=markup

The code is BSD licensed so I don't think there is a problem with people on 
this list reading it.

It handles missing closing tags or wrong "object counts" by throwing an 
exception, which would cause it to reject malformed LLSD messages.  I think 
this is the best way to handle any malformed LLSD message, weather it is in 
binary/JSON/XML format.

Also it doesn't check for duplicate map keys.  Only the last key/value pair 
with the same key would be kept.  We will have to decide if duplicate keys 
are allowed by the spec.

-- 
Robert G. Jakabosky

---

From: Meadhbh Hamrick <[email-masked]>
Date: Sun, 28 Mar 2010 21:19:44 -0700

well.. john hurliman's been pretty supportive of VWRAP generally.
(thanks, john!) so it's not outside the realm of possibility that
libOMV would get modified to be compliant with the VWRAP specs.

---

From: "Hurliman, John" <[email-masked]>
Date: Mon, 29 Mar 2010 12:11:00 -0600

I plan on updating the library when we can settle down on an LLSD spec that looks like it will be set in stone. Given the years of implementation experience and minimal disagreement on LLSD serialization details I don't think that's an unreasonable goal.

John

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Meadhbh Hamrick
> Sent: Sunday, March 28, 2010 9:20 PM
> To: Dahlia Trimble
> Cc: ogpx
> Subject: Re: [ogpx] type-system : guidance for binary serialization
> implementers
> 
> > On Sun, Mar 28, 2010 at 10:34 AM, Meadhbh Hamrick
> <[email-masked]>
> > wrote:
> >>