hpack_fuzz_util.cc 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
  1. // Copyright 2014 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "net/spdy/fuzzing/hpack_fuzz_util.h"
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <memory>
  8. #include "base/rand_util.h"
  9. #include "base/sys_byteorder.h"
  10. #include "net/third_party/quiche/src/quiche/spdy/core/hpack/hpack_constants.h"
  11. namespace spdy {
  12. namespace {
  13. // Sampled exponential distribution parameters:
  14. // Number of headers in each header set.
  15. const size_t kHeaderCountMean = 7;
  16. const size_t kHeaderCountMax = 50;
  17. // Selected index within list of headers.
  18. const size_t kHeaderIndexMean = 20;
  19. const size_t kHeaderIndexMax = 200;
  20. // Approximate distribution of header name lengths.
  21. const size_t kNameLengthMean = 5;
  22. const size_t kNameLengthMax = 30;
  23. // Approximate distribution of header value lengths.
  24. const size_t kValueLengthMean = 15;
  25. const size_t kValueLengthMax = 75;
  26. } // namespace
  27. using base::RandBytesAsString;
  28. using std::map;
  29. HpackFuzzUtil::GeneratorContext::GeneratorContext() = default;
  30. HpackFuzzUtil::GeneratorContext::~GeneratorContext() = default;
  31. HpackFuzzUtil::Input::Input() = default;
  32. HpackFuzzUtil::Input::~Input() = default;
  33. HpackFuzzUtil::FuzzerContext::FuzzerContext() = default;
  34. HpackFuzzUtil::FuzzerContext::~FuzzerContext() = default;
  35. // static
  36. void HpackFuzzUtil::InitializeGeneratorContext(GeneratorContext* context) {
  37. // Seed the generator with common header fixtures.
  38. context->names.push_back(":authority");
  39. context->names.push_back(":path");
  40. context->names.push_back(":status");
  41. context->names.push_back("cookie");
  42. context->names.push_back("content-type");
  43. context->names.push_back("cache-control");
  44. context->names.push_back("date");
  45. context->names.push_back("user-agent");
  46. context->names.push_back("via");
  47. context->values.push_back("/");
  48. context->values.push_back("/index.html");
  49. context->values.push_back("200");
  50. context->values.push_back("404");
  51. context->values.push_back("");
  52. context->values.push_back("baz=bing; foo=bar; garbage");
  53. context->values.push_back("baz=bing; fizzle=fazzle; garbage");
  54. context->values.push_back("rudolph=the-red-nosed-reindeer");
  55. context->values.push_back("had=a;very_shiny=nose");
  56. context->values.push_back("and\0if\0you\0ever\1saw\0it;");
  57. context->values.push_back("u; would=even;say-it\xffglows");
  58. }
  59. // static
  60. Http2HeaderBlock HpackFuzzUtil::NextGeneratedHeaderSet(
  61. GeneratorContext* context) {
  62. Http2HeaderBlock headers;
  63. size_t header_count =
  64. 1 + SampleExponential(kHeaderCountMean, kHeaderCountMax);
  65. for (size_t j = 0; j != header_count; ++j) {
  66. size_t name_index = SampleExponential(kHeaderIndexMean, kHeaderIndexMax);
  67. size_t value_index = SampleExponential(kHeaderIndexMean, kHeaderIndexMax);
  68. std::string name, value;
  69. if (name_index >= context->names.size()) {
  70. context->names.push_back(RandBytesAsString(
  71. 1 + SampleExponential(kNameLengthMean, kNameLengthMax)));
  72. name = context->names.back();
  73. } else {
  74. name = context->names[name_index];
  75. }
  76. if (value_index >= context->values.size()) {
  77. context->values.push_back(RandBytesAsString(
  78. 1 + SampleExponential(kValueLengthMean, kValueLengthMax)));
  79. value = context->values.back();
  80. } else {
  81. value = context->values[value_index];
  82. }
  83. headers[name] = value;
  84. }
  85. return headers;
  86. }
  87. // static
  88. size_t HpackFuzzUtil::SampleExponential(size_t mean, size_t sanity_bound) {
  89. return std::min(static_cast<size_t>(-std::log(base::RandDouble()) * mean),
  90. sanity_bound);
  91. }
  92. // static
  93. bool HpackFuzzUtil::NextHeaderBlock(Input* input, absl::string_view* out) {
  94. // ClusterFuzz may truncate input files if the fuzzer ran out of allocated
  95. // disk space. Be tolerant of these.
  96. CHECK_LE(input->offset, input->input.size());
  97. if (input->remaining() < sizeof(uint32_t)) {
  98. return false;
  99. }
  100. size_t length =
  101. base::NetToHost32(*reinterpret_cast<const uint32_t*>(input->ptr()));
  102. input->offset += sizeof(uint32_t);
  103. if (input->remaining() < length) {
  104. return false;
  105. }
  106. *out = absl::string_view(input->ptr(), length);
  107. input->offset += length;
  108. return true;
  109. }
  110. // static
  111. std::string HpackFuzzUtil::HeaderBlockPrefix(size_t block_size) {
  112. uint32_t length = base::HostToNet32(static_cast<uint32_t>(block_size));
  113. return std::string(reinterpret_cast<char*>(&length), sizeof(uint32_t));
  114. }
  115. // static
  116. void HpackFuzzUtil::InitializeFuzzerContext(FuzzerContext* context) {
  117. context->first_stage = std::make_unique<HpackDecoderAdapter>();
  118. context->second_stage = std::make_unique<HpackEncoder>();
  119. context->third_stage = std::make_unique<HpackDecoderAdapter>();
  120. }
  121. // static
  122. bool HpackFuzzUtil::RunHeaderBlockThroughFuzzerStages(
  123. FuzzerContext* context,
  124. absl::string_view input_block) {
  125. // First stage: Decode the input header block. This may fail on invalid input.
  126. if (!context->first_stage->HandleControlFrameHeadersData(
  127. input_block.data(), input_block.size())) {
  128. return false;
  129. }
  130. if (!context->first_stage->HandleControlFrameHeadersComplete()) {
  131. return false;
  132. }
  133. // Second stage: Re-encode the decoded header block. This must succeed.
  134. std::string second_stage_out = context->second_stage->EncodeHeaderBlock(
  135. context->first_stage->decoded_block());
  136. // Third stage: Expect a decoding of the re-encoded block to succeed, but
  137. // don't require it. It's possible for the stage-two encoder to produce an
  138. // output which violates decoder size tolerances.
  139. if (!context->third_stage->HandleControlFrameHeadersData(
  140. second_stage_out.data(), second_stage_out.length())) {
  141. return false;
  142. }
  143. if (!context->third_stage->HandleControlFrameHeadersComplete()) {
  144. return false;
  145. }
  146. return true;
  147. }
  148. // static
  149. void HpackFuzzUtil::FlipBits(uint8_t* buffer,
  150. size_t buffer_length,
  151. size_t flip_per_thousand) {
  152. uint64_t buffer_bit_length = buffer_length * 8u;
  153. uint64_t bits_to_flip = flip_per_thousand * (1 + buffer_bit_length / 1024);
  154. // Iteratively identify & flip offsets in the buffer bit-sequence.
  155. for (uint64_t i = 0; i != bits_to_flip; ++i) {
  156. uint64_t bit_offset = base::RandUint64() % buffer_bit_length;
  157. buffer[bit_offset / 8u] ^= (1 << (bit_offset % 8u));
  158. }
  159. }
  160. } // namespace spdy