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