Re: Proposal: drop QPACK encoder stream framing

[Kazuho Oku <[e-mail]>]

2018-06-09 8:26 GMT+09:00 Alan Frindell <[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