Speed up sanitizing headers received from HTTP proxies.

Speed up sanitizing headers received from HTTP proxies.

The old code repeatedly re-parsed headers for each header
to be retained, which is a very CPU intensive operation.
In practice, this shouldn't have mattered much. At worst, a
malicious proxy or MitM could DoS the CPU.

This code removes all the redundant parsing, and just removes
all the old headers in a single pass, at the cost of a bit more
code, and worse performance in the average case.  In the extreme
case the fuzzer detected, the new code is about 1,000 times
faster.

BUG=666878
Review-Url: https://codereview.chromium.org/2643023003
Cr-Commit-Position: refs/heads/master@{#445432}
Committed: https://chromium.googlesource.com/chromium/src/+/69b49a8ebcb7b1efddf89262b0ca36a300d756a5

[mmenke, 2017-01-19 18:41:55]

The CQ bit was checked by mmenke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-01-19 18:42:16]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[mmenke, 2017-01-19 18:48:06]

The CQ bit was checked by mmenke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-01-19 18:48:33]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[mmenke, 2017-01-19 18:51:55]

mmenke@chromium.org changed reviewers:
+ juliatuttle@chromium.org

[mmenke, 2017-01-19 18:51:55]

This fixes a rather silly issue, but at least it should make the fuzzers happy. 
And I guess it is technically a DoS attack on the browser, though those are
generally not considered huge issues.

https://codereview.chromium.org/2643023003/diff/20001/net/http/proxy_client_s...
File net/http/proxy_client_socket.cc (right):

https://codereview.chromium.org/2643023003/diff/20001/net/http/proxy_client_s...
net/http/proxy_client_socket.cc:98: &header_value)) {
I went with this approach instead of adding a "RemoveAllHeadersExcept" to
HttpResponseHeaders because HttpResponseHeaders::MergeWithHeaders is pretty
ugly, and I didn't want to make code that did the same thing (Though,
admittedly, I could have just copied the approach here to a new
RemoveAllHeadersExcept method).

[commit-bot: I haz the power, 2017-01-19 19:13:12]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-01-19 19:13:13]

Dry run: Try jobs failed on following builders:
  ios-simulator on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)

[mmenke, 2017-01-19 21:34:48]

Oops, looks like I broke something.  :(

[mmenke, 2017-01-19 21:49:52]

The CQ bit was checked by mmenke@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-01-19 21:50:43]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[mmenke, 2017-01-19 22:25:15]

On 2017/01/19 21:34:48, mmenke wrote:
> Oops, looks like I broke something.  :(

And fixed.

Julia:  PTAL when you get a chance, though no rush on this one.

[Julia Tuttle, 2017-01-19 22:26:40]

lgtm with a nit you can ignore if you want.

https://codereview.chromium.org/2643023003/diff/40001/net/http/proxy_client_s...
File net/http/proxy_client_socket.cc (right):

https://codereview.chromium.org/2643023003/diff/40001/net/http/proxy_client_s...
net/http/proxy_client_socket.cc:99: for (const char* header : kHeadersToKeep) {
Might be faster to just unconditionally remove the headers to keep after adding
all the current headers?

[commit-bot: I haz the power, 2017-01-20 00:26:30]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-01-20 00:26:31]

Dry run: This issue passed the CQ dry run.

[mmenke, 2017-01-23 17:28:15]

Thanks!

https://codereview.chromium.org/2643023003/diff/40001/net/http/proxy_client_s...
File net/http/proxy_client_socket.cc (right):

https://codereview.chromium.org/2643023003/diff/40001/net/http/proxy_client_s...
net/http/proxy_client_socket.cc:99: for (const char* header : kHeadersToKeep) {
On 2017/01/19 22:26:40, Julia Tuttle wrote:
> Might be faster to just unconditionally remove the headers to keep after
adding
> all the current headers?

The problem with that is the same reason adding header lines one-at-a-time is
slow.  Each time we add/remove a header/all instances of a header, we re-parse
the headers from scratch, which is slow.

i.e., the new bad case would be:

a:a
b:a
c:a
d:a
....

Each remove call would require a few more bytes than each add call requires now,
but we'd still have O(n^2) time for an O(n log n) length input (log n is because
keys have to grow in length to be unique).

This approach instead only parses the output string once, so I think should be
more robust against bad inputs.

[mmenke, 2017-01-23 17:28:44]

The CQ bit was checked by mmenke@chromium.org

[commit-bot: I haz the power, 2017-01-23 17:29:15]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-01-23 18:26:52]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-01-23 18:26:53]

Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[mmenke, 2017-01-23 18:28:26]

The CQ bit was checked by mmenke@chromium.org

[commit-bot: I haz the power, 2017-01-23 18:29:07]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-01-23 19:35:01]

CQ is committing da patch.

Bot data: {"patchset_id": 40001, "attempt_start_ts": 1485196106515470,
"parent_rev": "6778224312b46da67f47c84ec801d5849d078453", "commit_rev":
"69b49a8ebcb7b1efddf89262b0ca36a300d756a5"}

[commit-bot: I haz the power, 2017-01-23 19:35:38]

Description was changed from

==========
Speed up sanitizing headers received from HTTP proxies.

The old code repeatedly re-parsed headers for each header
to be retained, which is a very CPU intensive operation.
In practice, this shouldn't have mattered much. At worst, a
malicious proxy or MitM could DoS the CPU.

This code removes all the redundant parsing, and just removes
all the old headers in a single pass, at the cost of a bit more
code, and worse performance in the average case.  In the extreme
case the fuzzer detected, the new code is about 1,000 times
faster.

BUG=666878
==========

to

==========
Speed up sanitizing headers received from HTTP proxies.

The old code repeatedly re-parsed headers for each header
to be retained, which is a very CPU intensive operation.
In practice, this shouldn't have mattered much. At worst, a
malicious proxy or MitM could DoS the CPU.

This code removes all the redundant parsing, and just removes
all the old headers in a single pass, at the cost of a bit more
code, and worse performance in the average case.  In the extreme
case the fuzzer detected, the new code is about 1,000 times
faster.

BUG=666878

Review-Url: https://codereview.chromium.org/2643023003
Cr-Commit-Position: refs/heads/master@{#445432}
Committed:
https://chromium.googlesource.com/chromium/src/+/69b49a8ebcb7b1efddf89262b0ca...
==========

[commit-bot: I haz the power, 2017-01-23 19:35:44]

Committed patchset #3 (id:40001) as
https://chromium.googlesource.com/chromium/src/+/69b49a8ebcb7b1efddf89262b0ca...