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