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     Mutators.push_back(&MutationDispatcher::Mutate_ChangeASCIIInteger);
  33   }
  34   void AddWordToDictionary(const uint8_t *Word, size_t Size) {
  35     if (Dictionary.empty()) {
  36       Mutators.push_back(&MutationDispatcher::Mutate_AddWordFromDictionary);
  37     }
  38     Dictionary.push_back(Unit(Word, Word + Size));
  39   }
  40 };
  41
  42
  43 static char FlipRandomBit(char X, FuzzerRandomBase &Rand) {
  44   int Bit = Rand(8);
  45   char Mask = 1 << Bit;
  46   char R;
  47   if (X & (1 << Bit))
  48     R = X & ~Mask;
  49   else
  50     R = X | Mask;
  51   assert(R != X);
  52   return R;
  53 }
  54
  55 static char RandCh(FuzzerRandomBase &Rand) {
  56   if (Rand.RandBool()) return Rand(256);
  57   const char *Special = "!*'();:@&=+$,/?%#[]123ABCxyz-`~.";
  58   return Special[Rand(sizeof(Special) - 1)];
  59 }
  60
  61 size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
  62                                                size_t MaxSize) {
  63   assert(Size);
  64   size_t ShuffleAmount = Rand(std::min(Size, (size_t)8)) + 1;  // [1,8] and <= Size.
  65   size_t ShuffleStart = Rand(Size - ShuffleAmount);
  66   assert(ShuffleStart + ShuffleAmount <= Size);
  67   std::random_shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount,
  68                       Rand);
  69   return Size;
  70 }
  71
  72 size_t MutationDispatcher::Mutate_EraseByte(uint8_t *Data, size_t Size,
  73                                             size_t MaxSize) {
  74   assert(Size);
  75   if (Size == 1) return 0;
  76   size_t Idx = Rand(Size);
  77   // Erase Data[Idx].
  78   memmove(Data + Idx, Data + Idx + 1, Size - Idx - 1);
  79   return Size - 1;
  80 }
  81
  82 size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
  83                                              size_t MaxSize) {
  84   if (Size == MaxSize) return 0;
  85   size_t Idx = Rand(Size + 1);
  86   // Insert new value at Data[Idx].
  87   memmove(Data + Idx + 1, Data + Idx, Size - Idx);
  88   Data[Idx] = RandCh(Rand);
  89   return Size + 1;
  90 }
  91
  92 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
  93                                              size_t MaxSize) {
  94   size_t Idx = Rand(Size);
  95   Data[Idx] = RandCh(Rand);
  96   return Size;
  97 }
  98
  99 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
 100                                             size_t MaxSize) {
 101   size_t Idx = Rand(Size);
 102   Data[Idx] = FlipRandomBit(Data[Idx], Rand);
 103   return Size;
 104 }
 105
 106 size_t MutationDispatcher::Mutate_AddWordFromDictionary(uint8_t *Data,
 107                                                         size_t Size,
 108                                                         size_t MaxSize) {
 109   auto &D = MDImpl->Dictionary;
 110   assert(!D.empty());
 111   if (D.empty()) return 0;
 112   const Unit &Word = D[Rand(D.size())];
 113   if (Size + Word.size() > MaxSize) return 0;
 114   size_t Idx = Rand(Size + 1);
 115   memmove(Data + Idx + Word.size(), Data + Idx, Size - Idx);
 116   memcpy(Data + Idx, Word.data(), Word.size());
 117   return Size + Word.size();
 118 }
 119
 120 size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
 121                                                      size_t MaxSize) {
 122   size_t B = Rand(Size);
 123   while (B < Size && !isdigit(Data[B])) B++;
 124   if (B == Size) return 0;
 125   size_t E = B;
 126   while (E < Size && isdigit(Data[E])) E++;
 127   assert(B < E);
 128   // now we have digits in [B, E).
 129   // strtol and friends don't accept non-zero-teminated data, parse it manually.
 130   uint64_t Val = Data[B] - '0';
 131   for (size_t i = B + 1; i < E; i++)
 132     Val = Val * 10 + Data[i] - '0';
 133
 134   // Mutate the integer value.
 135   switch(Rand(5)) {
 136     case 0: Val++; break;
 137     case 1: Val--; break;
 138     case 2: Val /= 2; break;
 139     case 3: Val *= 2; break;
 140     case 4: Val = Rand(Val * Val); break;
 141     default: assert(0);
 142   }
 143   // Just replace the bytes with the new ones, don't bother moving bytes.
 144   for (size_t i = B; i < E; i++) {
 145     size_t Idx = E + B - i - 1;
 146     assert(Idx >= B && Idx < E);
 147     Data[Idx] = (Val % 10) + '0';
 148     Val /= 10;
 149   }
 150   return Size;
 151 }
 152
 153 // Mutates Data in place, returns new size.
 154 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
 155   assert(MaxSize > 0);
 156   assert(Size <= MaxSize);
 157   if (Size == 0) {
 158     for (size_t i = 0; i < MaxSize; i++)
 159       Data[i] = RandCh(Rand);
 160     return MaxSize;
 161   }
 162   assert(Size > 0);
 163   // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
 164   // in which case they will return 0.
 165   // Try several times before returning un-mutated data.
 166   for (int Iter = 0; Iter < 10; Iter++) {
 167     size_t MutatorIdx = Rand(MDImpl->Mutators.size());
 168     size_t NewSize =
 169         (this->*(MDImpl->Mutators[MutatorIdx]))(Data, Size, MaxSize);
 170     if (NewSize) return NewSize;
 171   }
 172   return Size;
 173 }
 174
 175 void MutationDispatcher::AddWordToDictionary(const uint8_t *Word, size_t Size) {
 176   MDImpl->AddWordToDictionary(Word, Size);
 177 }
 178
 179 MutationDispatcher::MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) {
 180   MDImpl = new Impl;
 181 }
 182
 183 MutationDispatcher::~MutationDispatcher() { delete MDImpl; }
 184
 185 }  // namespace fuzzer