Subject: Re: HPACK problems (was http/2 & hpack protocol review)

From: Cory Benfield <[email-masked]>
Date: Tue, 6 May 2014 10:14:06 +0100

On 5 May 2014 16:26, James M Snell <[email-masked]> wrote:
> FWIW, I am strongly -1 on the use of hpack in http/2. I believe that
> there are (and have proposed/argued for) much less complicated
> alternatives.
>
> - James

I agree with James and Keith's anonymous reviewer's doubts about
HPACK. Hyper's HPACK code has been a source of pain since I first
wrote it. The spec varies wildly between mind-bogglingly specific
(using 32 octets per-header-table entry as overhead because that's the
size of two 64-bit pointers and two 64-bit integers) and
under-specified.

As an example of the under-specification, consider that the reference
set and header sets are defined as unordered but do not say whether
they may contain duplicate elements. My assumption was that they could
not and so I could assume all implementations will join multiple
values with null bytes, but that assumption has not been made
elsewhere (nghttp2 certainly doesn't). Essentially, the word 'set' is
being used here without clarity about what exactly is meant. Is a
'set' simply an unordered collection? Or is it subject to stronger
constraints (more in line with the computer-science definition of a
set)? I guarantee that I won't be the first person to read the word
'set' and jump to my chosen language's set data structure.

These interop bugs with HPACK are ridiculously difficult to catch. I
didn't find any during live testing or in use, I only found some when
I used the excellent hpack-test-case[1] project to write 500-odd
integration tests. Even this didn't catch everything: my interop
problems with nghttp2 were only found when I submitted hyper's output
to the project, fully four months after I introduced the bug.

Finally, I'm utterly unconvinced that HPACK solves the problem it was
intended to solve: compression-based attacks on TLS-encrypted
sessions. I am not a cryptographer, but I'm quite prepared to believe
that we'll see successful attacks on HPACK in the future.

It could be that I'm simply less competent than everyone else on this
list and no-one else has had the trouble with HPACK that I've had. But
I'm also not a total moron, and the pain I had with HPACK suggests
it's a potential pain-point for a lot of others as well.

-- Cory

[1] https://github.com/http2jp/hpack-test-case

---

From: Daniel Stenberg <[email-masked]>
Date: Tue, 6 May 2014 12:00:35 +0200 (CEST)

On Tue, 6 May 2014, Cory Benfield wrote:

> As an example of the under-specification, consider that the reference set 
> and header sets are defined as unordered but do not say whether they may 
> contain duplicate elements. My assumption was that they could not and so I 
> could assume all implementations will join multiple values with null bytes, 
> but that assumption has not been made elsewhere (nghttp2 certainly doesn't).

Perhaps you can suggest an updated wording for the spec that makes it clearer?

I (and others) have used nghttp2 quite a lot for interop lately so I want to 
be sure that what it does is what the spec says so that we don't interop 
against something not actually compliant!

> These interop bugs with HPACK are ridiculously difficult to catch.

Any more than other compression or encryption interop bugs (I'm just 
suggesting that the area of compression/checksumming/encryption makes annoying 
interop debugging)? If so, what is it that makes HPACK more difficult than 
others?

-- 

  / daniel.haxx.se

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Tue, 6 May 2014 19:30:33 +0900

On Tue, May 6, 2014 at 7:00 PM, Daniel Stenberg <[email-masked]> wrote:

> I (and others) have used nghttp2 quite a lot for interop lately so I want
> to be sure that what it does is what the spec says so that we don't interop
​The reference set actually does not contain duplicates because its element
is a reference to the header table entry.
On the other hand, the header table may have duplicates.  This is​ covered
by the spec:

>From 3.1.2 <http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07#section-3.1.2>.
 Header Table:

   There is typically no need for the header table to contain duplicate
   entries.  However, duplicate entries MUST NOT be treated as an error
   by a decoder.

The current HTTP/2 draft-12 says that header fields sharing same name can
be concatenated with "0x0" but it was introduced some where in -6 to -9 and
it is only required if ordering of those header fields are significant.

>From 8.1.3.3.  Header Field Ordering:

   Header fields containing multiple values MUST be concatenated into a
   single value unless the ordering of that header field is known to be
   insignificant.

This means that we must expect duplicated header fields and multiple header
fields sharing same name in header set as input to HPACK.

Best regards,

Tatsuhiro Tsujikawa

> suggesting that the area of compression/checksumming/encryption makes
> annoying interop debugging)? If so, what is it that makes HPACK more
> difficult than others?
>
> --
>
>  / daniel.haxx.se
>
>

---

From: Cory Benfield <[email-masked]>
Date: Tue, 6 May 2014 11:32:54 +0100

> against something not actually compliant!

I use nghttp2 as well, which is how I found this ambiguity. I
deliberately didn't suggest any new wording because I'm not actually
sure what the correct logic should be! From a personal perspective I'd
be tempted to mandate that header sets and reference sets not have
duplicate elements in them. However, to make that work while still
emitting the same header more than once (technically allowed but
totally insane) you'd need to mandate joining those duplicate header
values together with null bytes. It also has slightly worse
compression efficiency, I suspect, though I've not sat down and
profiled it.

> annoying interop debugging)? If so, what is it that makes HPACK more

I've not written a complete compression implementation from scratch
for any other form of compression, so I'm not well-placed to compare.
However, the reason I've been able to do that is because all other
compression algorithms used in HTTP are mature standards, allowing me
to use someone else's implementation (and to assume that such an
implementation will actually be present by default). This eliminates a
whole class of interop bugs because I can delegate to a mature
codebase that almost certainly does things right (or at least less
wrong).

It might be that in actuality HPACK is as simple or simpler than other
compression algorithms to implement, but to me it feels incredibly
fiddly: there's quite a few moving pieces and inputs that come from
multiple places, so I need to keep track of what's doing what. I also
have to perform some calculations that look insane because the spec
mandates them (those  32 octets!).

---

From: Cory Benfield <[email-masked]>
Date: Tue, 6 May 2014 11:34:57 +0100

On 6 May 2014 11:30, Tatsuhiro Tsujikawa <[email-masked]> wrote:
> The reference set actually does not contain duplicates because its element
> On the other hand, the header table may have duplicates.  This is covered by
> the spec:
>
> [..snip..]
>

I'm happy with the header table itself having duplicates, I'm
concerned about the header _set_ (see what I mean about the ambiguity
of the spec?). The header table is a list of headers that we can
reference, but the header _set_ is defined as follows:

> Header Set: A header set is an unordered group of header fields that
> are encoded jointly.  A complete set of key-value pairs contained
> in a HTTP request or response is a header set.

Are we allowed duplicates in here? The spec doesn't seem to say
anything about them.

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Tue, 6 May 2014 19:52:08 +0900

> Are we allowed duplicates in here? The spec doesn't seem to say
​It is true that spec does not say anything about it.
I think this is an editorial issue and can be solved by proposing suggested
text with PR as Daniel said.
And now the problem is what is the expected behavior.
I think duplicates should be allowed because the algorithm in HPACK does
not break if we allow them.
I don't think the complexity of HPACK is much lowered if we get rid of
duplicates.

Best regards,
Tatsuhiro Tsujikawa

---

From: Cory Benfield <[email-masked]>
Date: Tue, 6 May 2014 12:04:01 +0100

On 6 May 2014 11:52, Tatsuhiro Tsujikawa <[email-masked]> wrote:
> I think duplicates should be allowed because the algorithm in HPACK does not
> break if we allow them.

Agreed: considering the HPACK spec in the abstract the simplest and
broadest change is to explicitly allow duplicates in the header set.
We'd need to decide how that affects the reference set (currently that
would add the same reference twice into the reference set, which is
again probably acceptable).

However, considering the real-world for a moment: disallowing
duplicates allows for hugely efficient operations to build the header
set by using proper set data structures (present in every useful
language's standard libraries and functions except C). In fact,
logically in pseudocode decoding becomes:

- Initialize empty header set
- Decode each header and add it to the header set and the reference
set (or remove it, as instructed)
- Emit the union of the header set and the reference set

These operations are fairly cheap and conceptually very clear.

Don't mistake that for me being hugely attached to the 'header set as
actual set' notion. I'm quite happy to go with nghttp2 on this,
especially as rewriting hyper is probably easier than rewriting
nghttp2. Just thought I'd present the case for the alternative.

---

From: RUELLAN Herve <[email-masked]>
Date: Wed, 7 May 2014 09:35:29 +0000

Hi Cory,

Thanks for your questions and comments: they're helpful by pointing the parts of the spec that are not clear enough and will help us improve this spec.

See my answers below.

> -----Original Message-----
> From: Cory Benfield [mailto:[email-masked]]
> Sent: mardi 6 mai 2014 13:04
> To: Tatsuhiro Tsujikawa
> Cc: Daniel Stenberg; James M Snell; [email-masked]; [email-masked];
> [email-masked]
> Subject: Re: HPACK problems (was http/2 & hpack protocol review)
> 

The intent is to allow duplicates in the header set. In an ideal world, it would be an 'actual set', but unfortunately, in my experimentation for building a header compression mechanism, I found several occurrences of real-world message headers containing duplicates. To support these use cases, HPACK has to allow for duplicates in the header set. I'm going to update the definition to make things clear.

On the other hand, the reference set is an 'actual set': it contains references to entries of the header table, and must not contain the same reference multiple times. However, it may contain two references resolving as the same header field, it this header field is contained in several entries of the header table.

The trick to encode a duplicate header field, is to encode it first as a literal, adding it to the header table and to the reference set, then to encode it twice as an index, the first index removing it from the reference set, and the second index adding it again to the reference set and to the encoded collection of headers.

Hervé.

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 7 May 2014 16:05:31 +0200

I'm coming back to the HTTP/2 WG very late in the process, so firstly
apologies for not giving feedback earlier in the process.

The jetty team is just starting our HTTP/2 work and we too have big
reservations about hpack from both a complexity and poor layering point of
view.

In a multiplexed protocol like HTTP/2  individual streams are going to be
handed off to threads to be processed, potentially out of order.   However
HPACK enforces an ordering on the decoding of header frames.   Thus it
means that you cannot design your HTTP/2 implement with pure framing layer
with protocol handling layer on top, because header frames must be
processed in the order they were received - thus the header decoding has to
be performed by the thread that is doing the framing decoding.

Not only does this result in poor separation of concerns, but it does
significantly slow down a server due to parallel slowdown.    The CPU core
that decodes a frames contents is the best CPU core to process it as it has
its caches warmed up with all the data!  But with HTTP/2 this is extremely
difficult to achieve as we need to be able to handle streams out of order.
Thus we have a thread dispatch between the decoding of the header frames
and the handling of those headers - meaning there is a high probability
that another CPU core will handle the frame and be slowed down with cache
misses.  This is a real problem (see
https://webtide.intalio.com/2012/12/avoiding-parallel-slowdown-in-jetty-9/).

More over, the requirement to decode headers in order detracts
significantly from the concept of stream priority, as low priority frames
must be decoded (and the results put somewhere) before any subsequent high
priority frames.

It also requires that intermediaries always decode and re encode header
frames if they are aggregating streams.

There are also numerous strategy decisions that must be made by a HPACK
encoding, such as replacing or using the current set of headers, H code or
not etc.    These types of decisions are difficult to make and almost
surely will be made wrongly in many situations.

There is also some element double complexity in a system that strives to
save every bit for field, but then has an entire other layer that avoids
the need to send the field in the first place.

What I would like to see is a much simpler header compression algorithm
applied to HEADER/CONTINUATION frames that is not order dependent.

However, I would also support that header frames could be sent on stream 0
and that headers so received would be considered part of all streams.
Such headers would probably need to be versioned, so that out of order
processing can occur, but I think that would be a lot less complex than the
current proposal.   But if it also proves to be complex, then just simple
header compression would be OK.

regards

-- 
Greg Wilkins <[email-masked]>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 7 May 2014 11:05:38 -0700

On 7 May 2014 07:05, Greg Wilkins <[email-masked]> wrote:
> handed off to threads to be processed, potentially out of order.

Note that it is possible, though not easy to construct a system that
can perform the bulk (or maybe even all) of HPACK processing on
different threads.  I've been involved in a couple of offline
discussions about this.  To do this, you can flush the reference set
on each header block and then rely on having certain guarantees
regarding the header table (i.e., strict controls on modifications).
A worker thread that updates the header table can do so within certain
constraints, though this may result in a need to perform fixups for
references to the static table, depending the final order that header
fields are ultimately serialized.

The shared context here is obviously more problematic for decoding,
since you have no guarantees from your peer about what they are
willing to do.

Ultimately, this trades compression efficiency for other things.  In
this case, some of the compression efficiency is gained by relying on
having strict serialization.  I don't believe it to be possible to
have a simpler compression algorithm that achieves this level of
compression efficiency without an ordering requirement.  That would
also need to be sensitive to the security concerns we've been
skirting.  I am happy to be proven wrong in this regard, of course.

It might be that good performance will require at least one HTTP/2
connection per core (or thread) on your machine, such that you are
unable to completely saturate a single connection.  I think that the
operating assumption is that machines with the sorts of performance
requirements you are talking about here will be operating on more
connections than that.

--Martin

---

From: Cory Benfield <[email-masked]>
Date: Thu, 8 May 2014 16:24:57 +0100

On 7 May 2014 10:35, RUELLAN Herve <[email-masked]> wrote:
> The intent is to allow duplicates in the header set. In an ideal world, it would
> be an 'actual set', but unfortunately, in my experimentation for building a header
> compression mechanism, I found several occurrences of real-world message
> headers containing duplicates. To support these use cases, HPACK has to
> allow for duplicates in the header set. I'm going to update the definition to
> make things clear.
>
> On the other hand, the reference set is an 'actual set': it contains references
> to entries of the header table, and must not contain the same reference multiple
> times. However, it may contain two references resolving as the same header
> field, it this header field is contained in several entries of the header table.

Fair enough: these didn't map to my expectations when reading the
spec, but they're obviously both totally reasonable ways to define
these terms. There are several moving pieces here and a fair bit of
subtlety, but I'm sure I can come up with something acceptable. I'm
looking forward to an updated spec so I can rewrite my entire
implementation again. =)

> The trick to encode a duplicate header field, is to encode it first as a literal,
> adding it to the header table and to the reference set, then to encode it twice
> as an index, the first index removing it from the reference set, and the second
> index adding it again to the reference set and to the encoded collection of
> headers.

This seems like exactly the kind of behaviour that leads to someone
suggesting a performance optimisation., and I'd love to bikeshed this
for a moment if you'd allow me. Is there any reason that HPACK
couldn't mandate that duplicate headers be forbidden in the same
header set? We have the ability to join the duplicates together into a
single header (with their values joined by null bytes), so it's in
principle possible for HPACK encoders to make this transformation.

The only argument I can see is that 'streaming' HPACK encoders (those
that don't have the full set of headers available to them) aren't able
to spot this optimisation up-front, and so can't make it (and
therefore can't comply). I don't really feel like we need to
accommodate such encoders, for two reasons. Firstly, I'm pretty sure
that no service generates so many headers that a HPACK encoder
couldn't deal with them in one go. Secondly, the ability to emit
headers straight away is almost totally unhelpful given that, even for
the largest of header sets, it's unlikely that HPACK encoding would
take more than a few tens of milliseconds, well under a RTT.

I accept that I'm wearing blinders here, because I deal with users who
always know what headers they're going to apply, so please tell me
what I'm missing.