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