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