Subject: Header compression: buffer management

From: RUELLAN Herve <[email-masked]>
Date: Thu, 21 Mar 2013 12:50:54 +0000

In HeaderDiff we chose to let the encoder decide how the buffer is managed (regarding additions and removals). These decisions are encoded on the wire and applied by the decoder on its own buffer. We think this choice has several advantages.

First, this allows to have a very simple and lightweight decoder: it only needs to decode the decisions made by the encoder and apply them. It has no need to effectively implements a LRU mechanism for its buffer. This is especially important for small devices with limited CPU.
In addition, we think it could be of interest for an intermediary, that could keep a partial buffer containing only the entries it is interested with, ignoring the other entries.

Second, this allows to adapt the buffer management to the context. While LRU is a good algorithm in the general case for deciding which entry to remove from the buffer, it may not be the best one for every specific case. More complex algorithms can probably be devised to improve the compaction (for example taking also into account the frequency of occurrence of headers), or simpler algorithms could be used to reduce the CPU cost to the detriment of compaction (this is important for small devices).
Adaptability is also important for the future of HTTP/2.0. If we do our job correctly, HTTP/2.0 will still be used in 10 or 20 years, but we have no idea how it will be used at that time. Making HTTP/2.0 adaptable to new usages is crucial to give it a long life expectancy.

For these reasons, we prefer to keep all the buffer management on the encoder side, allowing an implementer to choose its preferred approach.

Hervé.

---

From: Amos Jeffries <[email-masked]>
Date: Fri, 22 Mar 2013 04:11:44 +1300

> In HeaderDiff we chose to let the encoder decide how the buffer is managed (regarding additions and removals). These decisions are encoded on the wire and applied by the decoder on its own buffer.…

The encoder *will* at some point be a malicious attacker out to cause 
the decoder problems. Placing such an encoder in charge of buffer 
management at the decoder end of the wire is a sure-fire recipe for 
trouble. For anything like correct operation under such conditions it 
requires a pre-known buffer limit and enforcement of that limit at the 
decoder. Possibly with one size in the specs and a larger buffer size 
offered by the decoder for ongoing traffic (yes I can hear the cries 
about RTT lag already).

> In addition, we think it could be of interest for an intermediary, that could keep a partial buffer containing only the entries it is interested with, ignoring the other entries.

I notice that you are not making the same claim for encoder. All HTTP 
nodes will need both algorithms to follow the request+response model. 
How does the encoder+decoder as a pair stack up for size and complexity?

> For these reasons, we prefer to keep all the buffer management on the encoder side, allowing an implementer to choose its preferred approach.

Good reasons.

Amos

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Thu, 21 Mar 2013 16:49:35 +0000

In message <[email-masked]>, RUELL
AN Herve writes:

>In HeaderDiff we chose to let the encoder decide how the buffer is managed
>(regarding additions and removals). These decisions are encoded on the wire
> and applied by the decoder on its own buffer. We think this choice has
> several advantages.

Has this been analysed from a denial-of-service perspective ?

Anything in the protocol where the client can cause memory allocation
on the server/proxy/whatever, should be scrutinized in a DoS perspective.

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: James M Snell <[email-masked]>
Date: Thu, 21 Mar 2013 12:45:24 -0700

I've briefly looked at this and it definitely is a challenge.  With delta,
we at least have the benefit of allowing the decompressor to set an upper
bound on stored state size,  but even that can be problematic under heavy
load and does not completely resolve the issue.  For instance,  a malicious
client could potentially send hundreds of junk headers frames intentionally
designed to make the decompressor do significant extra work managing it's
internal buffers.  If the intermediary blindly passes such requests
through,  it will likely end up double buffering the junk data causing even
more issues.  It is obvious that fairly aggressive defensive techniques are
going to be required to watch for bad behavior and compensate. On the plus
side,  a delta decompressor could simply choose to throw up its hands and
give up doing any buffer management, simply passing values through...
Which,  of course just passes the problem on to someone else.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 21 Mar 2013 17:06:05 -0400

As others have pointed out, one cannot simply trust the encoder to do the
right thing.
As a result, either some eviction policy needs to be used (e.g. LRU), or
agood, reliable, detection mechanism must be used which doesn't have
false-positives and which only disconnects malicious users.

I have doubts that one can correctly identify malicious endpoints, and so I
chose the eviction policy based route.

The choice of eviction policy ends up having a large effect on the amount
of overhead necessary for the compressor/decompressor. In the case of LRU,
it is feasible to write all bytes into a single buffer, trading off space
for speed.

 An LRU doesn't *require* this tradeoff, however-- one could trade space
for CPU and use a map or hashmap for entries, reducing lookup time from
O(n) to O(lg(n)) or O(1) (avg case).

LRU is also one of the simplest eviction policies possible...

Also... it is theoretically possible to manage entries in the buffer with
delta that *don't* appear in the currrent headers. I've just not written an
encoder which does so.You'd do this by inserting the key-value and
immediately declare that it isn't part of the current headers...
-=R

On Thu, Mar 21, 2013 at 3:45 PM, James M Snell <[email-masked]> wrote:

> I've briefly looked at this and it definitely is a challenge.  With
> delta,  we at least have the benefit of allowing the decompressor to set an
> upper bound on stored state size,  but even that can be problematic under
> heavy load and does not completely resolve the issue.  For instance,  a
> malicious client could potentially send hundreds of junk headers frames
> intentionally designed to make the decompressor do significant extra work
> managing it's internal buffers.  If the intermediary blindly passes such
> requests through,  it will likely end up double buffering the junk data
> causing even more issues.  It is obvious that fairly aggressive defensive
> techniques are going to be required to watch for bad behavior and
> compensate. On the plus side,  a delta decompressor could simply choose to
> throw up its hands and give up doing any buffer management, simply passing
> values through...  Which,  of course just passes the problem on to someone
> else.

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Fri, 22 Mar 2013 07:38:24 +0000

In message <CABP7RbdL=cV2qSMBA3Me65T8tGaU3p9F5Wc690Jqk7q8xk_=[email-masked]>
, James M Snell writes:

>internal buffers.

Any request-response protocol is more or less vulnerable in this respect.

There are basically two things you can do to mitigate:

1) Severely circumscribe the first request on a connection.  This vastly
   increases the attackers cost of attack and makes sure that the server
   can scrutinize the first request for signs of malicious behaviour.

2) Make sure that the first request becomes available progressively
   to enable similar heuristics on the fly.

I think #1 is far preferable to #2, as a matter of usability for
the people writing the non-client code, but if done right #2 is a
workable solution.

One way to implement #1 is to specify that the first request, however
encoded, compressed or serialized, cannot be bigger than N bytes
on the wire.  For instance setting N to 8192.

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Fri, 22 Mar 2013 07:42:08 +0000

In message <CAP+FsNdVz3xU=[email-masked]>

>chose the eviction policy based route.

We certainly cannot trust the encoder to clean up for us, and you
point about identification is true as well.

However, the point of a DoS mitigation by protocol design, is not to
make them impossible, because you can't.

A popular TV-host telling all his viewers to visit the website "RIGHT
NOW!" is an incredible effective DoS.

But what you do, and what we should do, is make them difficult and
expensive to automate:  The major cost of the first request should
be borne by the client.

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 22 Mar 2013 13:52:35 +0000

> -----Original Message-----
> From: Amos Jeffries [mailto:[email-masked]]
> Sent: jeudi 21 mars 2013 16:12
> To: [email-masked]
> Subject: Re: Header compression: buffer management
> 
> > In HeaderDiff we chose to let the encoder decide how the buffer is
> managed (regarding additions and removals). These decisions are encoded
> on the wire and applied by the decoder on its own buffer. We think this
> choice has several advantages.
> 
> The encoder *will* at some point be a malicious attacker out to cause the
> decoder problems. Placing such an encoder in charge of buffer management
> at the decoder end of the wire is a sure-fire recipe for trouble. For anything
> like correct operation under such conditions it requires a pre-known buffer
> limit and enforcement of that limit at the decoder. Possibly with one size in
> the specs and a larger buffer size offered by the decoder for ongoing traffic
> (yes I can hear the cries about RTT lag already).

True, a malicious encoder could try to cause the decoder problems. But I think this is true for any encoder. Even HTTP/1.1 header format caused some vulnerabilities due to some whitespace handling.

Here, the decoder has only to check that the total buffer size is kept below the negotiated limit.

> > First, this allows to have a very simple and lightweight decoder: it only
> needs to decode the decisions made by the encoder and apply them. It has
> no need to effectively implements a LRU mechanism for its buffer. This is
> especially important for small devices with limited CPU.
> > In addition, we think it could be of interest for an intermediary, that could
> keep a partial buffer containing only the entries it is interested with, ignoring
> the other entries.
> 
> I notice that you are not making the same claim for encoder. All HTTP nodes
> will need both algorithms to follow the request+response model.

The case of the encoder is handled below. I started with the decoder because all HTTP nodes must implement a decoder able to handle any message sent to it. So the decoder will be roughly the same on a high-end workstation and on a low-power device.
Transmitting the buffer management information in the stream allows to have different implementations of the encoder, all compatible with any decoder. Therefore, an implementer can choose which kind of implementation he wants depending on its constraints (CPU, compaction ratio...). 

> > Second, this allows to adapt the buffer management to the context. While
> LRU is a good algorithm in the general case for deciding which entry to
> remove from the buffer, it may not be the best one for every specific case.
> More complex algorithms can probably be devised to improve the
> compaction (for example taking also into account the frequency of
> occurrence of headers), or simpler algorithms could be used to reduce the
> CPU cost to the detriment of compaction (this is important for small devices).
> > Adaptability is also important for the future of HTTP/2.0. If we do our job
> correctly, HTTP/2.0 will still be used in 10 or 20 years, but we have no idea
> how it will be used at that time. Making HTTP/2.0 adaptable to new usages is
> crucial to give it a long life expectancy.
> > For these reasons, we prefer to keep all the buffer management on the
> encoder side, allowing an implementer to choose its preferred approach.
> 
> Good reasons.
> 
> Amos

Hervé.

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 22 Mar 2013 14:08:47 +0000

For HeaderDiff, the encoder can transmit two buffer management commands:

-          Add a new header

-          Replace a previous header with a new one
A malicious encoder could try to make the buffer grow indefinitely. To prevent this, the decoder must check for each addition and replacement that the buffer size is kept below a predefined limit (either negotiated, or advertised).

Some other checks are needed (but this is true for any compression mechanism), for example limiting the length of a header name or of a header value, limiting the total size of a header set…

Keeping the buffer management as simpler as possible on the decoder side helps understanding its behavior and preventing attacks from malicious clients.

Hervé.

From: James M Snell [mailto:[email-masked]]
Sent: jeudi 21 mars 2013 20:45
To: Poul-Henning Kamp
Cc: RUELLAN Herve; [email-masked]
Subject: Re: Header compression: buffer management

I've briefly looked at this and it definitely is a challenge.  With delta,  we at least have the benefit of allowing the decompressor to set an upper bound on stored state size,  but even that can be problematic under heavy load and does not completely resolve the issue.  For instance,  a malicious client could potentially send hundreds of junk headers frames intentionally designed to make the decompressor do significant extra work managing it's internal buffers.  If the intermediary blindly passes such requests through,  it will likely end up double buffering the junk data causing even more issues.  It is obvious that fairly aggressive defensive techniques are going to be required to watch for bad behavior and compensate. On the plus side,  a delta decompressor could simply choose to throw up its hands and give up doing any buffer management, simply passing values through...  Which,  of course just passes the problem on to someone else.
On Mar 21, 2013 9:51 AM, "Poul-Henning Kamp" <[email-masked]<mailto:[email-masked]>> wrote:
In message <[email-masked]<mailto:[email-masked]>>, RUELL

--
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]<mailto:[email-masked]>         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.