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
14namespace net {
15
16namespace {
17
18// Sampled exponential distribution parameters:
19// Number of headers in each header set.
20const size_t kHeaderCountMean = 7;
21const size_t kHeaderCountMax = 50;
22// Selected index within list of headers.
23const size_t kHeaderIndexMean = 20;
24const size_t kHeaderIndexMax = 200;
25// Approximate distribution of header name lengths.
26const size_t kNameLengthMean = 5;
27const size_t kNameLengthMax = 30;
28// Approximate distribution of header value lengths.
29const size_t kValueLengthMean = 15;
30const size_t kValueLengthMax = 75;
31
32}  //  namespace
33
34using base::StringPiece;
35using base::RandBytesAsString;
36using std::map;
37using std::string;
38
39HpackFuzzUtil::GeneratorContext::GeneratorContext() {}
40HpackFuzzUtil::GeneratorContext::~GeneratorContext() {}
41
42HpackFuzzUtil::Input::Input() : offset(0) {}
43HpackFuzzUtil::Input::~Input() {}
44
45HpackFuzzUtil::FuzzerContext::FuzzerContext() {}
46HpackFuzzUtil::FuzzerContext::~FuzzerContext() {}
47
48// static
49void 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
75map<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
109size_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
114bool 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
135string 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
141void 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
148bool 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
177void 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