Re: Proposal: drop QPACK encoder stream framing

[Alan Frindell <[e-mail]>]

The fact that you now need an algorithm that tells you how to correctly/safely deserialize a single instruction is pretty much the point I was making.  This is more complex than just having a byte on the wire tell you how many bytes are required.  But I feel there’s clear consensus here to discard the length prefix.

-Alan

From: Mike Bishop <[e-mail]>
Date: Sunday, June 10, 2018 at 4:16 PM
To: Kazuho Oku <[e-mail]>, Alan Frindell <[e-mail]>
Cc: QUIC WG <[e-mail]>, Martin Thomson <[e-mail]>
Subject: RE: Proposal: drop QPACK encoder stream framing


And they probably should, since they can't sensibly do anything without a full instruction.  So an implementation would need to do the following steps:

  *   Check the first byte; at this point, you either know the string’s exact length, or you know it’s longer than 32 bytes
     *   If longer, wait until you’ve gotten at least 32 more bytes, and you’re guaranteed to have the remainder of the number; find the actual length
     *   Wait until you have the actual length plus one byte
  *   Use the length of the encoded string to locate the first byte of the value length; you either find the full length, or you know it’s at least 128 bytes long
     *   If longer, wait until you’ve gotten at least 128 more bytes; you’re guaranteed to have the actual number in there
     *   Wait until you have the actual length (remainder of the instruction)
  *   Decode the instruction



So you’re potentially waiting for more bytes up to four times per instruction (though the odds that a non-malicious sender would hit all four are low), and a naïve implementation might well re-parse the instruction from the beginning after each wait completes.  Implicit in this is the assumption that a 32 byte long integer will always be unacceptably long, and if after the wait you can’t move to the next field successfully, you’ll fail the instruction.



An implementation can always determine how many bytes it needs to wait for to make progress, without accidentally waiting past the end of the instruction and creating a deadlock if that’s a tail.  I think this example has convinced me that the length prefix is unnecessary.  (It does make me wonder whether it would have made more sense to put both lengths at the beginning of the instruction, followed by the values.)



-----Original Message-----
From: QUIC <[e-mail]> On Behalf Of Kazuho Oku
Sent: Saturday, June 9, 2018 3:57 PM
To: Alan Frindell <[e-mail]>
Cc: QUIC WG <[e-mail]>; Martin Thomson <[e-mail]>
Subject: Re: Proposal: drop QPACK encoder stream framing



2018-06-09 8:26 GMT+09:00 Alan Frindell <[e-mail]<mailto:[e-mail]>>:

>     Because I think reparsing is the best strategy here, let me argue that

>     the worst case is not O(N^2).

>

>     Of course, in theory it is O(N^2), because there is no upper bound for

>     the integer representation. But the reality is that implementations

>     are required to have an upper bound. I'd assume that they would

>     typically only permit values that fit in a 32-bit (u)int (16-bit is

>     another option for some).

>

> The O(N^2) work I was thinking of was something like this:

>

> The encoder sends a very long Huffman encoded header name followed by a long value, but they send the value one byte at a time.  If the decoder naively reparses the entire Insert instruction every time a byte arrives, it will end up Huffman decoding the header name on every new byte of the value.  The name can be skipped over to re-parse the value length, and verify if the full value is present.  However, even skipping over it may be a linear operation in a zero-copy implementation that maintains a linked list of data buffers.



Thank you for the clarification. That sounds like an interesting attack vector that we need to be aware of.



OTOH, I am not sure if we need to consider the possibility of streaming Huffman decoding in this discussion, considering the fact that the compressed strings remain length-prefixed.



Even if we remove the framing of the QCACK instructions, implementations will continue to have the freedom to buffer a complete Huffman-encoded string (the length of the string being identified by the length octets.



> -Alan

>

>







--

Kazuho Oku