4 ms·

Well said. Also, binary protocol could easily be added on top of HTTP, a kind of "smart-gzip" which would encode (known) HTTP to binary codes. That could make p

by amenod 11y ago

Well said. Also, binary protocol could easily be added on top of HTTP, a kind of "smart-gzip" which would encode (known) HTTP to binary codes. That could make parsing faster while keeping the evolvability of the protocol intact.

chubot 11y ago
Actually, that's exactly what HTTP 2.0 is :) They're keeping the exact same message semantics, while changing the encoding to binary and also changing the network transfer part. I'd be a little concerned about fixing it in place, but it's perhaps possible that HTTP is done evolving, and this will be a win. HTTP has gotten so much usage far beyond its original intent. As an aside, I chafe against the implicit assumption in your message that binary is more space-efficient than text. :) Compressed text and binary formats are the same size (e.g. JSON vs protocol buffers), and compression is almost free these days in terms of CPU. And sometimes uncompressed text is SMALLER than binary, i.e. in the case of encoding numbers. Many data sets have lots of zeros and small numbers, and it takes 1-3 bytes to encode a zero in text ("0", "0,", "0.0") while it takes 4-8 bytes to encode in most binary formats. A CSV file vs. a memory dump of the same numbers can show this. Numbers encoded as ASCII is a built-in "varint" format, which shouldn't be underestimated.
- MichaelGG 11y ago
  General use compression algorithms suck at both ratio and speed when it comes to compressing integers. ASCII numbers are strictly inferior to even varint (base128) encoding. And varint is junk (in bulk) compared to int formats like PFor or Simple16 etc. You're arguing that a format with fixed width is worse. Sure. So what about fixed width text protocols? Nothing stops the spec writers from requiring leading zeros. Just like nothing stops binary protocols from using varint. The reason you want fixed width, though, is because it's so easy and fast to deal with. It's a no-op. TCP/IP is so easy because you just deref the message as a struct.
  - chubot 11y ago
    OK but I also think you're conflating two issues: text vs. binary on the one hand, and delimiter vs length-prefixed on the other. I like DJB's netstring scheme, which is an ASCII length-prefixed encoding: 3:foo, 10:0123456789, Text formats usually have delimiters (like HTTP headers), and binary formats usually have length prefixes, but technically they're orthogonal. I've never seen a fixed-width text format for numbers in practice.
    - noblethrasher 11y ago
      It's somewhat orthogonal to your point, but delimiters are theoretically more secure: Language Theoretic Security (langsec)[1][2] observes that any program that accepts input is an implementation of a recognizer for some formal language. The problem, with respect to network security, is: 1. The formal language is usually informally specified, which leads to... 2. The parsers for these languages are implemented in an ad-hoc fashion, with the logic scattered throughout the codebase. The remedy is to: 1. Formally specify the language, and limit it's power to regular expression, or, at worse, deterministic context-free (this is basically a recapitulation of the principle of least privilege) 2. Use explicit state machines for the parsing logic. The problem with binary protocols is that they tend to rely on length field, which automatically makes the formal language at least context-sensitive. This is a no-no from the langsec point of view because it's much harder to secure such protocols, because they tend to accidentally give rise to hidden Turing Machines that a hackers can then program against). Conversely, delimiters are necessary in order to limit your grammar to regular. [1] http://langsec.org/ http://langsec.org/ [2] https://www.youtube.com/watch?v=UzjfeFJJseU https://www.youtube.com/watch?v=UzjfeFJJseU
      - chubot 11y ago
        I'm familar with all this langsec stuff. I think it's interesting, but I'm not convinced about the delimiter argument. I actually watched one of those talks and I remember an audience member argued in favor of length prefixes too. I think this is mostly confusing tokenization and parsing. Regular languages and context free grammars basically define predicates on infinite streams of tokens (match or no match). In practice, the tokens are variable length, like HTTP headers. And if you care about resource exhaustion attacks, which you do in practice, then you need some kind of length limit. Even if you're using delimiters instead of length prefixes, you need this. Do you want to accept a 10 GB HTTP header value? Well the minute you do that, your recognizer is no longer context-free or regular, and you cannot solve the halting problem, etc. I think they bring up Mongrel as an example of a principled parser. But AFAIK it still has semantic actions for capture -- the whole point of Ragel is that you can embed semantic actions, like Yacc. Once you have semantics actions, you're writing in a Turing complete language, so you have all the same problems. The problems are only mitigated, not theoretically eliminated. I think there is a pretty large gulf in computational power between "weird machine, input data is a full-fledged programming language" and length prefixes and length limits. I bet you can define some formalism with length prefixes or length limits and prove things about them too. They are only speaking to one aspect of security, in any case. I looked at their Hammer parser combinator project recently too. That seems to have failed or languished, I think because parser combinators aren't good at expressing real world message formats. For one, a lot of servers are async, and a lot of parser generators assume that they pull their input rather than having it pushed upon them in async fashion. Another is that I would think using parser combinators probably doesn't lead to good memory allocation patterns. So basically I think the langsec stuff is interesting but doesn't entirely line up with reality. Though if they continue to pursue it, I think it will bear some fruits. I'm not ready to accept protocol design suggestions from them until they have tested their ideas in practice more. The Hammer thing was a good idea, but as far as I can tell it was mostly a negative result in terms of testing theory against practice.

by amenod 11y ago

chubot 11y ago

Actually, that's exactly what HTTP 2.0 is :) They're keeping the exact same message semantics, while changing the encoding to binary and also changing the network transfer part. I'd be a little concerned about fixing it in place, but it's perhaps possible that HTTP is done evolving, and this will be a win. HTTP has gotten so much usage far beyond its original intent. As an aside, I chafe against the implicit assumption in your message that binary is more space-efficient than text. :) Compressed text and binary formats are the same size (e.g. JSON vs protocol buffers), and compression is almost free these days in terms of CPU. And sometimes uncompressed text is SMALLER than binary, i.e. in the case of encoding numbers. Many data sets have lots of zeros and small numbers, and it takes 1-3 bytes to encode a zero in text ("0", "0,", "0.0") while it takes 4-8 bytes to encode in most binary formats. A CSV file vs. a memory dump of the same numbers can show this. Numbers encoded as ASCII is a built-in "varint" format, which shouldn't be underestimated.

MichaelGG 11y ago
General use compression algorithms suck at both ratio and speed when it comes to compressing integers. ASCII numbers are strictly inferior to even varint (base128) encoding. And varint is junk (in bulk) compared to int formats like PFor or Simple16 etc. You're arguing that a format with fixed width is worse. Sure. So what about fixed width text protocols? Nothing stops the spec writers from requiring leading zeros. Just like nothing stops binary protocols from using varint. The reason you want fixed width, though, is because it's so easy and fast to deal with. It's a no-op. TCP/IP is so easy because you just deref the message as a struct.
- chubot 11y ago
  OK but I also think you're conflating two issues: text vs. binary on the one hand, and delimiter vs length-prefixed on the other. I like DJB's netstring scheme, which is an ASCII length-prefixed encoding: 3:foo, 10:0123456789, Text formats usually have delimiters (like HTTP headers), and binary formats usually have length prefixes, but technically they're orthogonal. I've never seen a fixed-width text format for numbers in practice.
  - noblethrasher 11y ago
    It's somewhat orthogonal to your point, but delimiters are theoretically more secure: Language Theoretic Security (langsec)[1][2] observes that any program that accepts input is an implementation of a recognizer for some formal language. The problem, with respect to network security, is: 1. The formal language is usually informally specified, which leads to... 2. The parsers for these languages are implemented in an ad-hoc fashion, with the logic scattered throughout the codebase. The remedy is to: 1. Formally specify the language, and limit it's power to regular expression, or, at worse, deterministic context-free (this is basically a recapitulation of the principle of least privilege) 2. Use explicit state machines for the parsing logic. The problem with binary protocols is that they tend to rely on length field, which automatically makes the formal language at least context-sensitive. This is a no-no from the langsec point of view because it's much harder to secure such protocols, because they tend to accidentally give rise to hidden Turing Machines that a hackers can then program against). Conversely, delimiters are necessary in order to limit your grammar to regular. [1] http://langsec.org/ http://langsec.org/ [2] https://www.youtube.com/watch?v=UzjfeFJJseU https://www.youtube.com/watch?v=UzjfeFJJseU
    - chubot 11y ago
      I'm familar with all this langsec stuff. I think it's interesting, but I'm not convinced about the delimiter argument. I actually watched one of those talks and I remember an audience member argued in favor of length prefixes too. I think this is mostly confusing tokenization and parsing. Regular languages and context free grammars basically define predicates on infinite streams of tokens (match or no match). In practice, the tokens are variable length, like HTTP headers. And if you care about resource exhaustion attacks, which you do in practice, then you need some kind of length limit. Even if you're using delimiters instead of length prefixes, you need this. Do you want to accept a 10 GB HTTP header value? Well the minute you do that, your recognizer is no longer context-free or regular, and you cannot solve the halting problem, etc. I think they bring up Mongrel as an example of a principled parser. But AFAIK it still has semantic actions for capture -- the whole point of Ragel is that you can embed semantic actions, like Yacc. Once you have semantics actions, you're writing in a Turing complete language, so you have all the same problems. The problems are only mitigated, not theoretically eliminated. I think there is a pretty large gulf in computational power between "weird machine, input data is a full-fledged programming language" and length prefixes and length limits. I bet you can define some formalism with length prefixes or length limits and prove things about them too. They are only speaking to one aspect of security, in any case. I looked at their Hammer parser combinator project recently too. That seems to have failed or languished, I think because parser combinators aren't good at expressing real world message formats. For one, a lot of servers are async, and a lot of parser generators assume that they pull their input rather than having it pushed upon them in async fashion. Another is that I would think using parser combinators probably doesn't lead to good memory allocation patterns. So basically I think the langsec stuff is interesting but doesn't entirely line up with reality. Though if they continue to pursue it, I think it will bear some fruits. I'm not ready to accept protocol design suggestions from them until they have tested their ideas in practice more. The Hammer thing was a good idea, but as far as I can tell it was mostly a negative result in terms of testing theory against practice.