net/spdy/fuzzing/hpack_fuzz_util.cc

   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
  39 HpackFuzzUtil::GeneratorContext::GeneratorContext() {}
  40 HpackFuzzUtil::GeneratorContext::~GeneratorContext() {}
  41
  42 HpackFuzzUtil::Input::Input() : offset(0) {}
  43 HpackFuzzUtil::Input::~Input() {}
  44
  45 HpackFuzzUtil::FuzzerContext::FuzzerContext() {}
  46 HpackFuzzUtil::FuzzerContext::~FuzzerContext() {}
  47
  48 // static
  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
  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
 109 size_t HpackFuzzUtil::SampleExponential(size_t mean, size_t sanity_bound) {
 110   return std::min(static_cast<size_t>(-std::log(base::RandDouble()) * mean),
 111                   sanity_bound);
 112 }
 113
 114 // static
 115 bool HpackFuzzUtil::NextHeaderBlock(Input* input,
 116                                     StringPiece* out) {
 117   // ClusterFuzz may truncate input files if the fuzzer ran out of allocated
 118   // disk space. Be tolerant of these.
 119   CHECK_LE(input->offset, input->input.size());
 120   if (input->remaining() < sizeof(uint32)) {
 121     return false;
 122   }
 123
 124   size_t length = ntohl(*reinterpret_cast<const uint32*>(input->ptr()));
 125   input->offset += sizeof(uint32);
 126
 127   if (input->remaining() < length) {
 128     return false;
 129   }
 130   *out = StringPiece(input->ptr(), length);
 131   input->offset += length;
 132   return true;
 133 }
 134
 135 // static
 136 string HpackFuzzUtil::HeaderBlockPrefix(size_t block_size) {
 137   uint32 length = htonl(block_size);
 138   return string(reinterpret_cast<char*>(&length), sizeof(uint32));
 139 }
 140
 141 // static
 142 void HpackFuzzUtil::InitializeFuzzerContext(FuzzerContext* context) {
 143   context->first_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
 144   context->second_stage.reset(new HpackEncoder(ObtainHpackHuffmanTable()));
 145   context->third_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
 146 }
 147
 148 // static
 149 bool HpackFuzzUtil::RunHeaderBlockThroughFuzzerStages(FuzzerContext* context,
 150                                                       StringPiece input_block) {
 151   // First stage: Decode the input header block. This may fail on invalid input.
 152   if (!context->first_stage->HandleControlFrameHeadersData(
 153       1, input_block.data(), input_block.size())) {
 154     return false;
 155   }
 156   if (!context->first_stage->HandleControlFrameHeadersComplete(1)) {
 157     return false;
 158   }
 159   // Second stage: Re-encode the decoded header block. This must succeed.
 160   string second_stage_out;
 161   CHECK(context->second_stage->EncodeHeaderSet(
 162       context->first_stage->decoded_block(), &second_stage_out));
 163
 164   // Third stage: Expect a decoding of the re-encoded block to succeed, but
 165   // don't require it. It's possible for the stage-two encoder to produce an
 166   // output which violates decoder size tolerances.
 167   if (!context->third_stage->HandleControlFrameHeadersData(
 168           1, second_stage_out.data(), second_stage_out.length())) {
 169     return false;
 170   }
 171   if (!context->third_stage->HandleControlFrameHeadersComplete(1)) {
 172     return false;
 173   }
 174   return true;
 175 }
 176
 177 // static
 178 void HpackFuzzUtil::FlipBits(uint8* buffer, size_t buffer_length,
 179                              size_t flip_per_thousand) {
 180   uint64 buffer_bit_length = buffer_length * 8u;
 181   uint64 bits_to_flip = flip_per_thousand * (1 + buffer_bit_length / 1024);
 182
 183   // Iteratively identify & flip offsets in the buffer bit-sequence.
 184   for (uint64 i = 0; i != bits_to_flip; ++i) {
 185     uint64 bit_offset = base::RandUint64() % buffer_bit_length;
 186     buffer[bit_offset / 8u] ^= (1 << (bit_offset % 8u));
 187   }
 188 }
 189
 190 }  // namespace net