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