hpack_fuzz_util.cc revision cedac228d2dd51db4b79ea1e72c7f249408ee061
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