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