15c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Copyright 2014 The Chromium Authors. All rights reserved.
25c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Use of this source code is governed by a BSD-style license that can be
35c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// found in the LICENSE file.
45c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
55c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include "net/spdy/fuzzing/hpack_fuzz_util.h"
65c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
75c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include <algorithm>
85c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include <cmath>
95c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
105c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include "base/rand_util.h"
115c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include "base/sys_byteorder.h"
125c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include "net/spdy/hpack_constants.h"
135c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
145c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liunamespace net {
155c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
165c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liunamespace {
175c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
185c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Sampled exponential distribution parameters:
195c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Number of headers in each header set.
205c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kHeaderCountMean = 7;
215c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kHeaderCountMax = 50;
225c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Selected index within list of headers.
235c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kHeaderIndexMean = 20;
245c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kHeaderIndexMax = 200;
255c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Approximate distribution of header name lengths.
265c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kNameLengthMean = 5;
275c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kNameLengthMax = 30;
285c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Approximate distribution of header value lengths.
295c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kValueLengthMean = 15;
305c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuconst size_t kValueLengthMax = 75;
315c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
325c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}  //  namespace
335c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
345c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuusing base::StringPiece;
355c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuusing base::RandBytesAsString;
365c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuusing std::map;
375c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuusing std::string;
385c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
395c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo LiuHpackFuzzUtil::GeneratorContext::GeneratorContext() {}
405c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo LiuHpackFuzzUtil::GeneratorContext::~GeneratorContext() {}
415c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
425c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo LiuHpackFuzzUtil::Input::Input() : offset(0) {}
435c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo LiuHpackFuzzUtil::Input::~Input() {}
445c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
455c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo LiuHpackFuzzUtil::FuzzerContext::FuzzerContext() {}
465c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo LiuHpackFuzzUtil::FuzzerContext::~FuzzerContext() {}
475c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
485c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
495c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuvoid HpackFuzzUtil::InitializeGeneratorContext(GeneratorContext* context) {
505c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  // Seed the generator with common header fixtures.
515c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back(":authority");
525c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back(":path");
535c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back(":status");
545c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back("cookie");
555c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back("content-type");
565c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back("cache-control");
575c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back("date");
585c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back("user-agent");
595c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->names.push_back("via");
605c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
615c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("/");
625c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("/index.html");
635c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("200");
645c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("404");
655c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("");
665c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("baz=bing; foo=bar; garbage");
675c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("baz=bing; fizzle=fazzle; garbage");
685c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("rudolph=the-red-nosed-reindeer");
695c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("had=a;very_shiny=nose");
705c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("and\0if\0you\0ever\1saw\0it;");
715c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->values.push_back("u; would=even;say-it\xffglows");
725c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
735c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
745c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
755c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liumap<string, string> HpackFuzzUtil::NextGeneratedHeaderSet(
765c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    GeneratorContext* context) {
775c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  map<string, string> headers;
785c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
795c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  size_t header_count = 1 + SampleExponential(kHeaderCountMean,
805c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                                              kHeaderCountMax);
815c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  for (size_t j = 0; j != header_count; ++j) {
825c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    size_t name_index = SampleExponential(kHeaderIndexMean,
835c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                                          kHeaderIndexMax);
845c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    size_t value_index = SampleExponential(kHeaderIndexMean,
855c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                                           kHeaderIndexMax);
865c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    string name, value;
875c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    if (name_index >= context->names.size()) {
885c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      context->names.push_back(
895c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu          RandBytesAsString(1 + SampleExponential(kNameLengthMean,
905c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                                                  kNameLengthMax)));
915c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      name = context->names.back();
925c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    } else {
935c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      name = context->names[name_index];
945c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    }
955c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    if (value_index >= context->values.size()) {
965c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      context->values.push_back(
975c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu          RandBytesAsString(1 + SampleExponential(kValueLengthMean,
985c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                                                  kValueLengthMax)));
995c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      value = context->values.back();
1005c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    } else {
1015c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      value = context->values[value_index];
1025c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    }
1035c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    headers[name] = value;
1045c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  }
1055c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  return headers;
1065c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
1075c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1085c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
1095c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liusize_t HpackFuzzUtil::SampleExponential(size_t mean, size_t sanity_bound) {
1105c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  return std::min<size_t>(-std::log(base::RandDouble()) * mean, sanity_bound);
1115c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
1125c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1135c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
1145c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liubool HpackFuzzUtil::NextHeaderBlock(Input* input,
1155c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                                    StringPiece* out) {
116cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  // ClusterFuzz may truncate input files if the fuzzer ran out of allocated
117cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  // disk space. Be tolerant of these.
1185c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  CHECK_LE(input->offset, input->input.size());
119cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  if (input->remaining() < sizeof(uint32)) {
1205c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    return false;
1215c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  }
1225c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1235c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  size_t length = ntohl(*reinterpret_cast<const uint32*>(input->ptr()));
1245c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  input->offset += sizeof(uint32);
1255c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
126cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  if (input->remaining() < length) {
127cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)    return false;
128cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  }
1295c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  *out = StringPiece(input->ptr(), length);
1305c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  input->offset += length;
1315c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  return true;
1325c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
1335c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1345c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
1355c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liustring HpackFuzzUtil::HeaderBlockPrefix(size_t block_size) {
1365c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  uint32 length = htonl(block_size);
1375c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  return string(reinterpret_cast<char*>(&length), sizeof(uint32));
1385c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
1395c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1405c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
1415c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuvoid HpackFuzzUtil::InitializeFuzzerContext(FuzzerContext* context) {
1425c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->first_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
1435c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->second_stage.reset(new HpackEncoder(ObtainHpackHuffmanTable()));
1445c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  context->third_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
1455c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
1465c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1475c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
1485c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liubool HpackFuzzUtil::RunHeaderBlockThroughFuzzerStages(FuzzerContext* context,
1495c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                                                      StringPiece input_block) {
1505c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  // First stage: Decode the input header block. This may fail on invalid input.
1515c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  if (!context->first_stage->HandleControlFrameHeadersData(
1525c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      1, input_block.data(), input_block.size())) {
1535c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    return false;
1545c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  }
1555c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  if (!context->first_stage->HandleControlFrameHeadersComplete(1)) {
1565c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    return false;
1575c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  }
1585c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  // Second stage: Re-encode the decoded header block. This must succeed.
1595c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  string second_stage_out;
1605c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  CHECK(context->second_stage->EncodeHeaderSet(
1615c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu      context->first_stage->decoded_block(), &second_stage_out));
1625c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
163cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  // Third stage: Expect a decoding of the re-encoded block to succeed, but
164cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  // don't require it. It's possible for the stage-two encoder to produce an
165cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  // output which violates decoder size tolerances.
166cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  if (!context->third_stage->HandleControlFrameHeadersData(
167cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)          1, second_stage_out.data(), second_stage_out.length())) {
168cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)    return false;
169cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  }
170cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  if (!context->third_stage->HandleControlFrameHeadersComplete(1)) {
171cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)    return false;
172cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)  }
1735c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  return true;
1745c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
1755c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1765c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// static
1775c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liuvoid HpackFuzzUtil::FlipBits(uint8* buffer, size_t buffer_length,
1785c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu                             size_t flip_per_thousand) {
1795c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  uint64 buffer_bit_length = buffer_length * 8u;
1805c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  uint64 bits_to_flip = flip_per_thousand * (1 + buffer_bit_length / 1024);
1815c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1825c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  // Iteratively identify & flip offsets in the buffer bit-sequence.
1835c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  for (uint64 i = 0; i != bits_to_flip; ++i) {
1845c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    uint64 bit_offset = base::RandUint64() % buffer_bit_length;
1855c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu    buffer[bit_offset / 8u] ^= (1 << (bit_offset % 8u));
1865c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu  }
1875c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}
1885c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu
1895c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}  // namespace net
190