contrib/compiler-rt/lib/fuzzer/FuzzerMutate.h

   1 //===- FuzzerMutate.h - Internal header for the Fuzzer ----------*- C++ -* ===//
   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 // fuzzer::MutationDispatcher
  10 //===----------------------------------------------------------------------===//
  11
  12 #ifndef LLVM_FUZZER_MUTATE_H
  13 #define LLVM_FUZZER_MUTATE_H
  14
  15 #include "FuzzerDefs.h"
  16 #include "FuzzerDictionary.h"
  17 #include "FuzzerOptions.h"
  18 #include "FuzzerRandom.h"
  19
  20 namespace fuzzer {
  21
  22 class MutationDispatcher {
  23 public:
  24   MutationDispatcher(Random &Rand, const FuzzingOptions &Options);
  25   ~MutationDispatcher() {}
  26   /// Indicate that we are about to start a new sequence of mutations.
  27   void StartMutationSequence();
  28   /// Print the current sequence of mutations.
  29   void PrintMutationSequence();
  30   /// Indicate that the current sequence of mutations was successful.
  31   void RecordSuccessfulMutationSequence();
  32   /// Mutates data by invoking user-provided mutator.
  33   size_t Mutate_Custom(uint8_t *Data, size_t Size, size_t MaxSize);
  34   /// Mutates data by invoking user-provided crossover.
  35   size_t Mutate_CustomCrossOver(uint8_t *Data, size_t Size, size_t MaxSize);
  36   /// Mutates data by shuffling bytes.
  37   size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize);
  38   /// Mutates data by erasing bytes.
  39   size_t Mutate_EraseBytes(uint8_t *Data, size_t Size, size_t MaxSize);
  40   /// Mutates data by inserting a byte.
  41   size_t Mutate_InsertByte(uint8_t *Data, size_t Size, size_t MaxSize);
  42   /// Mutates data by inserting several repeated bytes.
  43   size_t Mutate_InsertRepeatedBytes(uint8_t *Data, size_t Size, size_t MaxSize);
  44   /// Mutates data by chanding one byte.
  45   size_t Mutate_ChangeByte(uint8_t *Data, size_t Size, size_t MaxSize);
  46   /// Mutates data by chanding one bit.
  47   size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize);
  48   /// Mutates data by copying/inserting a part of data into a different place.
  49   size_t Mutate_CopyPart(uint8_t *Data, size_t Size, size_t MaxSize);
  50
  51   /// Mutates data by adding a word from the manual dictionary.
  52   size_t Mutate_AddWordFromManualDictionary(uint8_t *Data, size_t Size,
  53                                             size_t MaxSize);
  54
  55   /// Mutates data by adding a word from the TORC.
  56   size_t Mutate_AddWordFromTORC(uint8_t *Data, size_t Size, size_t MaxSize);
  57
  58   /// Mutates data by adding a word from the persistent automatic dictionary.
  59   size_t Mutate_AddWordFromPersistentAutoDictionary(uint8_t *Data, size_t Size,
  60                                                     size_t MaxSize);
  61
  62   /// Tries to find an ASCII integer in Data, changes it to another ASCII int.
  63   size_t Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, size_t MaxSize);
  64   /// Change a 1-, 2-, 4-, or 8-byte integer in interesting ways.
  65   size_t Mutate_ChangeBinaryInteger(uint8_t *Data, size_t Size, size_t MaxSize);
  66
  67   /// CrossOver Data with some other element of the corpus.
  68   size_t Mutate_CrossOver(uint8_t *Data, size_t Size, size_t MaxSize);
  69
  70   /// Applies one of the configured mutations.
  71   /// Returns the new size of data which could be up to MaxSize.
  72   size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize);
  73
  74   /// Applies one of the configured mutations to the bytes of Data
  75   /// that have '1' in Mask.
  76   /// Mask.size() should be >= Size.
  77   size_t MutateWithMask(uint8_t *Data, size_t Size, size_t MaxSize,
  78                         const Vector<uint8_t> &Mask);
  79
  80   /// Applies one of the default mutations. Provided as a service
  81   /// to mutation authors.
  82   size_t DefaultMutate(uint8_t *Data, size_t Size, size_t MaxSize);
  83
  84   /// Creates a cross-over of two pieces of Data, returns its size.
  85   size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2,
  86                    size_t Size2, uint8_t *Out, size_t MaxOutSize);
  87
  88   void AddWordToManualDictionary(const Word &W);
  89
  90   void PrintRecommendedDictionary();
  91
  92   void SetCorpus(const InputCorpus *Corpus) { this->Corpus = Corpus; }
  93
  94   Random &GetRand() { return Rand; }
  95
  96   void PrintMutationStats();
  97
  98   void RecordUsefulMutations();
  99
 100  private:
 101   struct Mutator {
 102     size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
 103     const char *Name;
 104     uint64_t UsefulCount;
 105     uint64_t TotalCount;
 106   };
 107
 108   size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size,
 109                                size_t MaxSize);
 110   size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize,
 111                     Vector<Mutator> &Mutators);
 112
 113   size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
 114                       size_t ToSize, size_t MaxToSize);
 115   size_t CopyPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
 116                     size_t ToSize);
 117   size_t ApplyDictionaryEntry(uint8_t *Data, size_t Size, size_t MaxSize,
 118                               DictionaryEntry &DE);
 119
 120   template <class T>
 121   DictionaryEntry MakeDictionaryEntryFromCMP(T Arg1, T Arg2,
 122                                              const uint8_t *Data, size_t Size);
 123   DictionaryEntry MakeDictionaryEntryFromCMP(const Word &Arg1, const Word &Arg2,
 124                                              const uint8_t *Data, size_t Size);
 125   DictionaryEntry MakeDictionaryEntryFromCMP(const void *Arg1, const void *Arg2,
 126                                              const void *Arg1Mutation,
 127                                              const void *Arg2Mutation,
 128                                              size_t ArgSize,
 129                                              const uint8_t *Data, size_t Size);
 130
 131   Random &Rand;
 132   const FuzzingOptions Options;
 133
 134   // Dictionary provided by the user via -dict=DICT_FILE.
 135   Dictionary ManualDictionary;
 136   // Temporary dictionary modified by the fuzzer itself,
 137   // recreated periodically.
 138   Dictionary TempAutoDictionary;
 139   // Persistent dictionary modified by the fuzzer, consists of
 140   // entries that led to successful discoveries in the past mutations.
 141   Dictionary PersistentAutoDictionary;
 142
 143   Vector<DictionaryEntry *> CurrentDictionaryEntrySequence;
 144   Vector<Mutator *> CurrentMutatorSequence;
 145
 146   static const size_t kCmpDictionaryEntriesDequeSize = 16;
 147   DictionaryEntry CmpDictionaryEntriesDeque[kCmpDictionaryEntriesDequeSize];
 148   size_t CmpDictionaryEntriesDequeIdx = 0;
 149
 150   const InputCorpus *Corpus = nullptr;
 151   Vector<uint8_t> MutateInPlaceHere;
 152   Vector<uint8_t> MutateWithMaskTemp;
 153   // CustomCrossOver needs its own buffer as a custom implementation may call
 154   // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere.
 155   Vector<uint8_t> CustomCrossOverInPlaceHere;
 156
 157   Vector<Mutator> Mutators;
 158   Vector<Mutator> DefaultMutators;
 159 };
 160
 161 }  // namespace fuzzer
 162
 163 #endif  // LLVM_FUZZER_MUTATE_H