Home | History | Annotate | Download | only in fuzzing 
      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<size_t>(-std::log(base::RandDouble()) * mean, sanity_bound);
    111 }
    112 
    113 // static
    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
    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
    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
    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
    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