4 ms·

There was this recent security presentation about formal language-theoretic reasons why message-length prefixes are a bad idea. http://www.cs.dartmouth.edu/~ser

There was this recent security presentation about formal language-theoretic reasons why message-length prefixes are a bad idea. http://www.cs.dartmouth.edu/~sergey/langsec/ http://www.cs.dartmouth.edu/~sergey/langsec/ The problem was that it causes unnecessary complexity in validation and parsing, as <length-of-message><message>... describes a context-sensitive grammar, while a more XML-, JSON-like syntax with delimiters <delim><message></delim>... is context-free. The complexity of proper CSG validation can be exploited for resource-depletion/DOS attacks, while not validating the syntax of a message leaves part of the program that uses the data in these messages with potentially invalid data, putting it into an inconsistent state, possibly leading to DOS or worse exploits. At least that's what I got from their presentation, which was very interesting BTW, especially the part about "weird machines"--that's basically the inconsistent state, the emergent machine that is made out of all the things an attacker can make a system do by exploiting it. It was also extremely geeky. It just left me wondering: if I understood this right, every protocol that uses message-length prefixes is at least vulnerable to resource-depletion attacks, and there's no way of solving this short of proving P=NP. But that's quite a lot of protocols! Why isn't the Internet burning down as we speak?

m_eiman 14y ago
if ( msg.total_length > MAX_ALLOWED_SIZE ) { reset_parser(); }? Should take care of any resource depletion issues, and do it way faster than eating data waiting for an end of field marker would.
- mcherm 14y ago
  But it produces a protocol which is incapable of handling messages greater than a certain length. The marketplace is littered with such protocols, but they're all useless since they can no longer even transmit a single wordprocessing document now that a page of text takes up megabytes of overhead.
  - m_eiman 14y ago
    It's not every protocol that must handle arbitrary messages, that doesn't make them useless. Having a 9600 baud half duplex connection for messaging that requires low latency is quite different from 1Gbps Ethernet, and that makes every byte count.
kryptiskt 14y ago
But in any normal design you never put the message length into the same parser, you use it to read the message, and the parser is fed the message when you have received that many bytes. For the reader a message consists of <length>+<blob>+<length>+<blob>+ etc. It can be in two states, having enough data, so pass the blob on to the parser (and it doesn't have to validate that the blob is length bytes, we know that already); or awaiting more data (you can attack that by dribbling data slowly, but you can do that with any protocol). EDIT: Ok, I used a flat structure there, it would be different in a recursive structure with length on every element. But a top level reader that reads <length> bytes of the outer wrapper and doesn't muck about with the innards is still a sensible thing.
- tripzilch 14y ago
  First of, this isn't about deeply nested structures, the flat example demonstrates the problem perfectly fine :) > But in any normal design you never put the message length into the same parser, you use it to read the message, and the parser is fed the message when you have received that many bytes. Won't work, this is a fundamental problem in computing science. Splitting the parser into a pre-parser and a post-parser isn't going to help solve the fundamental problem, because the combination of two parsers is still a parser. One of the problems is, you cannot distinguish <blob> bytes from <length> bytes. If the data stream gets out of sync with the parser state (hiccup, dropped packet), you have a very non-trivial problem on your hands. A context-free grammer however, is free of context (ohh!) and can therefore resync in time proportional to how deep it's nested. Speaking of nesting, that's another bit where I expect CSGs to become incredibly hairy: Of course you can use a hybrid approach: length-prefixed messages for the "outer stream", and a context-free XML/JSON/Lisp style format (delimiters on both sides[0]) for recursive structures. But why would you do that? If you wanted to save bytes by avoiding the delimiters on the very outer structures, there's a lot more of them to be saved if you apply the same "optimization" to any inner recursive structures. If you don't know what I'm talking about, think about how a tree-like recursive datastructure is represented in the memory of a C program. Yes pointers. Alternatively you could length-prefix them like before, C programs don't do that because you need to scan through everything and it's less efficient. Regardless, both approaches are context-sensitive and good luck on distinguishing malformed data from correct ones. Now, this whole "formal languages and automatons" is a very complex subject matter[1], so while it may seem that the whole argument hinges on dropping a packet and desyncing the parser[2], I got the feeling from that talk that there are other (similarly fundamental) problems, but this particular one I understood and can make a compelling argument for :) [0] afaik you might actually get away with a delimiter on just one side, but that makes it harder to parse because you need strict precedence rules to resolve ambiguities (e.g. 2+34+182+1+1+74321+0) [1] it was considered one of the hardest courses during my CS college years (the other one being on "formal proofs of program correctness"), for various reasons I retook this course 4 times (underestimating its difficulty at first being one of those reasons), but when I finally did pass, I did so with a score of 9 out of 10, I'm kinda proud of that :P But the real* benefit of studying 4 times for the same difficult course is that you never really forget it (some parallels there with that post about "spaced repetition learning" last week). [2] another thing they recommended that makes a lot of sense, but again is a parsing complexity (security) vs bandwidth efficiency trade-off: to make the delimiters (say, parentheses) to be out-of-band characters. so they're not allowed in binary blobs. this saves you from all sorts of escaping exploits (think XSS), makes resyncing more efficient and parsing a lot easier. of course it's really hard to step out of the "we really need all 8 bits in a byte"-paradigm, or how else can you design data formats with out-of-band characters? I don't know, and the talk I watched didn't give a solution either, just that it would be a good idea (to which I agree).
cnvogel 14y ago
Also in applications where bit-errors (or disconnections) are to be expected, the <length><data_of_length_length> ... approach makes it hard to re-synchronize after errors. (think of a serial cable that might be dis/reconnected, or radio-frequency links.) A more robust encoding reserves some bit-pattern as a <start-of-message> marker, and escapes regular appearance of this marker in the payload with some special sequence. (see, for example, http://en.wikipedia.org/wiki/High-Level_Data_Link_Control http://en.wikipedia.org/wiki/High-Level_Data_Link_Control ). When you start putting (for example) single "blink"-messages in distinct payloads in such a framing container, then the <length-of-message> byte of blink becomes redundant, of course.
- randersson 14y ago
  We discussed length preambles vs markers when we designed the FAST protocol 8 years ago. That time we made length preambles optional (there are two "modes"). The nature of the FAST encoding made it impractical to use markers even though it would have been entirely possible. This time around we decided to use length preambles. Blink focuses on encoding short messages, so streaming works well with preamble. We expect bit-level errors, disconnects etc. to be handled by a lower layer. Rolf

m_eiman 14y ago

if ( msg.total_length > MAX_ALLOWED_SIZE ) { reset_parser(); }? Should take care of any resource depletion issues, and do it way faster than eating data waiting for an end of field marker would.

mcherm 14y ago
But it produces a protocol which is incapable of handling messages greater than a certain length. The marketplace is littered with such protocols, but they're all useless since they can no longer even transmit a single wordprocessing document now that a page of text takes up megabytes of overhead.
- m_eiman 14y ago
  It's not every protocol that must handle arbitrary messages, that doesn't make them useless. Having a 9600 baud half duplex connection for messaging that requires low latency is quite different from 1Gbps Ethernet, and that makes every byte count.

kryptiskt 14y ago

But in any normal design you never put the message length into the same parser, you use it to read the message, and the parser is fed the message when you have received that many bytes. For the reader a message consists of <length>+<blob>+<length>+<blob>+ etc. It can be in two states, having enough data, so pass the blob on to the parser (and it doesn't have to validate that the blob is length bytes, we know that already); or awaiting more data (you can attack that by dribbling data slowly, but you can do that with any protocol). EDIT: Ok, I used a flat structure there, it would be different in a recursive structure with length on every element. But a top level reader that reads <length> bytes of the outer wrapper and doesn't muck about with the innards is still a sensible thing.

tripzilch 14y ago
First of, this isn't about deeply nested structures, the flat example demonstrates the problem perfectly fine :) > But in any normal design you never put the message length into the same parser, you use it to read the message, and the parser is fed the message when you have received that many bytes. Won't work, this is a fundamental problem in computing science. Splitting the parser into a pre-parser and a post-parser isn't going to help solve the fundamental problem, because the combination of two parsers is still a parser. One of the problems is, you cannot distinguish <blob> bytes from <length> bytes. If the data stream gets out of sync with the parser state (hiccup, dropped packet), you have a very non-trivial problem on your hands. A context-free grammer however, is free of context (ohh!) and can therefore resync in time proportional to how deep it's nested. Speaking of nesting, that's another bit where I expect CSGs to become incredibly hairy: Of course you can use a hybrid approach: length-prefixed messages for the "outer stream", and a context-free XML/JSON/Lisp style format (delimiters on both sides[0]) for recursive structures. But why would you do that? If you wanted to save bytes by avoiding the delimiters on the very outer structures, there's a lot more of them to be saved if you apply the same "optimization" to any inner recursive structures. If you don't know what I'm talking about, think about how a tree-like recursive datastructure is represented in the memory of a C program. Yes pointers. Alternatively you could length-prefix them like before, C programs don't do that because you need to scan through everything and it's less efficient. Regardless, both approaches are context-sensitive and good luck on distinguishing malformed data from correct ones. Now, this whole "formal languages and automatons" is a very complex subject matter[1], so while it may seem that the whole argument hinges on dropping a packet and desyncing the parser[2], I got the feeling from that talk that there are other (similarly fundamental) problems, but this particular one I understood and can make a compelling argument for :) [0] afaik you might actually get away with a delimiter on just one side, but that makes it harder to parse because you need strict precedence rules to resolve ambiguities (e.g. 2+34+182+1+1+74321+0) [1] it was considered one of the hardest courses during my CS college years (the other one being on "formal proofs of program correctness"), for various reasons I retook this course 4 times (underestimating its difficulty at first being one of those reasons), but when I finally did pass, I did so with a score of 9 out of 10, I'm kinda proud of that :P But the real* benefit of studying 4 times for the same difficult course is that you never really forget it (some parallels there with that post about "spaced repetition learning" last week). [2] another thing they recommended that makes a lot of sense, but again is a parsing complexity (security) vs bandwidth efficiency trade-off: to make the delimiters (say, parentheses) to be out-of-band characters. so they're not allowed in binary blobs. this saves you from all sorts of escaping exploits (think XSS), makes resyncing more efficient and parsing a lot easier. of course it's really hard to step out of the "we really need all 8 bits in a byte"-paradigm, or how else can you design data formats with out-of-band characters? I don't know, and the talk I watched didn't give a solution either, just that it would be a good idea (to which I agree).

cnvogel 14y ago

Also in applications where bit-errors (or disconnections) are to be expected, the <length><data_of_length_length> ... approach makes it hard to re-synchronize after errors. (think of a serial cable that might be dis/reconnected, or radio-frequency links.) A more robust encoding reserves some bit-pattern as a <start-of-message> marker, and escapes regular appearance of this marker in the payload with some special sequence. (see, for example, http://en.wikipedia.org/wiki/High-Level_Data_Link_Control http://en.wikipedia.org/wiki/High-Level_Data_Link_Control ). When you start putting (for example) single "blink"-messages in distinct payloads in such a framing container, then the <length-of-message> byte of blink becomes redundant, of course.

randersson 14y ago
We discussed length preambles vs markers when we designed the FAST protocol 8 years ago. That time we made length preambles optional (there are two "modes"). The nature of the FAST encoding made it impractical to use markers even though it would have been entirely possible. This time around we decided to use length preambles. Blink focuses on encoding short messages, so streaming works well with preamble. We expect bit-level errors, disconnects etc. to be handled by a lower layer. Rolf