Looks like HostResolverImpl has some O(N^2) behavior. Specifically the std::find in RemoveRequest. That should be doable more efficiently.

https://chromium-review.googlesource.com/1020022

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/a5677198e579f2371ef510f4ee60ea7ca19122f0

commit a5677198e579f2371ef510f4ee60ea7ca19122f0
Author: David Benjamin <davidben@chromium.org>
Date: Mon Apr 23 23:25:42 2018

Fix quadratic behavior in HostResolverImpl.

Canceling a single request is currently linear in the number of
requests, making the overall behavior quadratic. Fix it to be linear, so
we scale well and avoid upsetting the fuzzer.

Bug:  834578 
Change-Id: Ieb17b106b0a8308b7b5a882fa1f61f899ee4dbcd
Reviewed-on: https://chromium-review.googlesource.com/1020022
Reviewed-by: Eric Roman <eroman@chromium.org>
Commit-Queue: David Benjamin <davidben@chromium.org>
Cr-Commit-Position: refs/heads/master@{#552891}
[modify] https://crrev.com/a5677198e579f2371ef510f4ee60ea7ca19122f0/net/dns/host_resolver_impl.cc

Should be fixed now.

ClusterFuzz has detected this issue as fixed in range 552882:552902.

Detailed report: https://clusterfuzz.com/testcase?key=5548637363634176

Fuzzer: libFuzzer_net_host_resolver_impl_fuzzer
Job Type: libfuzzer_chrome_ubsan
Platform Id: linux

Crash Type: Timeout (exceeds 25 secs)
Crash Address: 
Crash State:
  net_host_resolver_impl_fuzzer
  
Sanitizer: undefined (UBSAN)

Regressed: https://clusterfuzz.com/revisions?job=libfuzzer_chrome_ubsan&range=523274:523299
Fixed: https://clusterfuzz.com/revisions?job=libfuzzer_chrome_ubsan&range=552882:552902

Reproducer Testcase: https://clusterfuzz.com/download?testcase_id=5548637363634176

See https://chromium.googlesource.com/chromium/src/+/master/testing/libfuzzer/reference.md for more information.

If you suspect that the result above is incorrect, try re-doing that job on the test case report page.

ClusterFuzz testcase 5548637363634176 is verified as fixed, so closing issue as verified.

If this is incorrect, please add ClusterFuzz-Wrong label and re-open the issue.

Thanks, libFuzzer! Realistically, this would never have come up---limits and coallescing higher up the stack would prevent someone many times over from making 10,000 requests to the same hostname---but the fix was easy enough and actually used one less allocation than before. We've got a lot of this pattern where we're not using the right data structure.