lib/Fuzzer/FuzzerMutate.cpp

   1 //===- FuzzerMutate.cpp - Mutate a test input -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 // Mutate a test input.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include <cstring>
  13
  14 #include "FuzzerInternal.h"
  15
  16 #include <algorithm>
  17
  18 namespace fuzzer {
  19
  20 typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size,
  21                                               size_t Max);
  22
  23 struct MutationDispatcher::Impl {
  24   std::vector<Unit> Dictionary;
  25   std::vector<Mutator> Mutators;
  26   Impl() {
  27     Mutators.push_back(&MutationDispatcher::Mutate_EraseByte);
  28     Mutators.push_back(&MutationDispatcher::Mutate_InsertByte);
  29     Mutators.push_back(&MutationDispatcher::Mutate_ChangeByte);
  30     Mutators.push_back(&MutationDispatcher::Mutate_ChangeBit);
  31     Mutators.push_back(&MutationDispatcher::Mutate_ShuffleBytes);
  32   }
  33   void AddWordToDictionary(const uint8_t *Word, size_t Size) {
  34     if (Dictionary.empty()) {
  35       Mutators.push_back(&MutationDispatcher::Mutate_AddWordFromDictionary);
  36     }
  37     Dictionary.push_back(Unit(Word, Word + Size));
  38   }
  39 };
  40
  41
  42 static char FlipRandomBit(char X, FuzzerRandomBase &Rand) {
  43   int Bit = Rand(8);
  44   char Mask = 1 << Bit;
  45   char R;
  46   if (X & (1 << Bit))
  47     R = X & ~Mask;
  48   else
  49     R = X | Mask;
  50   assert(R != X);
  51   return R;
  52 }
  53
  54 static char RandCh(FuzzerRandomBase &Rand) {
  55   if (Rand.RandBool()) return Rand(256);
  56   const char *Special = "!*'();:@&=+$,/?%#[]123ABCxyz-`~.";
  57   return Special[Rand(sizeof(Special) - 1)];
  58 }
  59
  60 size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
  61                                                size_t MaxSize) {
  62   assert(Size);
  63   size_t ShuffleAmount = Rand(std::min(Size, 8UL)) + 1;  // [1,8] and <= Size.
  64   size_t ShuffleStart = Rand(Size - ShuffleAmount);
  65   assert(ShuffleStart + ShuffleAmount <= Size);
  66   std::random_shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount,
  67                       Rand);
  68   return Size;
  69 }
  70
  71 size_t MutationDispatcher::Mutate_EraseByte(uint8_t *Data, size_t Size,
  72                                             size_t MaxSize) {
  73   assert(Size);
  74   if (Size == 1) return 0;
  75   size_t Idx = Rand(Size);
  76   // Erase Data[Idx].
  77   memmove(Data + Idx, Data + Idx + 1, Size - Idx - 1);
  78   return Size - 1;
  79 }
  80
  81 size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
  82                                              size_t MaxSize) {
  83   if (Size == MaxSize) return 0;
  84   size_t Idx = Rand(Size + 1);
  85   // Insert new value at Data[Idx].
  86   memmove(Data + Idx + 1, Data + Idx, Size - Idx);
  87   Data[Idx] = RandCh(Rand);
  88   return Size + 1;
  89 }
  90
  91 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
  92                                              size_t MaxSize) {
  93   size_t Idx = Rand(Size);
  94   Data[Idx] = RandCh(Rand);
  95   return Size;
  96 }
  97
  98 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
  99                                             size_t MaxSize) {
 100   size_t Idx = Rand(Size);
 101   Data[Idx] = FlipRandomBit(Data[Idx], Rand);
 102   return Size;
 103 }
 104
 105 size_t MutationDispatcher::Mutate_AddWordFromDictionary(uint8_t *Data,
 106                                                         size_t Size,
 107                                                         size_t MaxSize) {
 108   auto &D = MDImpl->Dictionary;
 109   assert(!D.empty());
 110   if (D.empty()) return 0;
 111   const Unit &Word = D[Rand(D.size())];
 112   if (Size + Word.size() > MaxSize) return 0;
 113   size_t Idx = Rand(Size + 1);
 114   memmove(Data + Idx + Word.size(), Data + Idx, Size - Idx);
 115   memcpy(Data + Idx, Word.data(), Word.size());
 116   return Size + Word.size();
 117 }
 118
 119 // Mutates Data in place, returns new size.
 120 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
 121   assert(MaxSize > 0);
 122   assert(Size <= MaxSize);
 123   if (Size == 0) {
 124     for (size_t i = 0; i < MaxSize; i++)
 125       Data[i] = RandCh(Rand);
 126     return MaxSize;
 127   }
 128   assert(Size > 0);
 129   // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
 130   // in which case they will return 0.
 131   // Try several times before returning un-mutated data.
 132   for (int Iter = 0; Iter < 10; Iter++) {
 133     size_t MutatorIdx = Rand(MDImpl->Mutators.size());
 134     size_t NewSize =
 135         (this->*(MDImpl->Mutators[MutatorIdx]))(Data, Size, MaxSize);
 136     if (NewSize) return NewSize;
 137   }
 138   return Size;
 139 }
 140
 141 void MutationDispatcher::AddWordToDictionary(const uint8_t *Word, size_t Size) {
 142   MDImpl->AddWordToDictionary(Word, Size);
 143 }
 144
 145 MutationDispatcher::MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) {
 146   MDImpl = new Impl;
 147 }
 148
 149 MutationDispatcher::~MutationDispatcher() { delete MDImpl; }
 150
 151 }  // namespace fuzzer