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 17 namespace fuzzer { 18 19 const size_t Dictionary::kMaxDictSize; 20 21 MutationDispatcher::MutationDispatcher(Random &Rand, 22 const FuzzingOptions &Options) 23 : Rand(Rand), Options(Options) { 24 DefaultMutators.insert( 25 DefaultMutators.begin(), 26 { 27 {&MutationDispatcher::Mutate_EraseByte, "EraseByte"}, 28 {&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, 29 {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, 30 {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, 31 {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, 32 {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, 33 {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, 34 {&MutationDispatcher::Mutate_AddWordFromManualDictionary, 35 "AddFromManualDict"}, 36 {&MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary, 37 "AddFromTempAutoDict"}, 38 {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, 39 "AddFromPersAutoDict"}, 40 }); 41 42 if (EF->LLVMFuzzerCustomMutator) 43 Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); 44 else 45 Mutators = DefaultMutators; 46 47 if (EF->LLVMFuzzerCustomCrossOver) 48 Mutators.push_back( 49 {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); 50 } 51 52 static char FlipRandomBit(char X, Random &Rand) { 53 int Bit = Rand(8); 54 char Mask = 1 << Bit; 55 char R; 56 if (X & (1 << Bit)) 57 R = X & ~Mask; 58 else 59 R = X | Mask; 60 assert(R != X); 61 return R; 62 } 63 64 static char RandCh(Random &Rand) { 65 if (Rand.RandBool()) return Rand(256); 66 const char *Special = "!*'();:@&=+$,/?%#[]123ABCxyz-`~."; 67 return Special[Rand(sizeof(Special) - 1)]; 68 } 69 70 size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, 71 size_t MaxSize) { 72 return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, Rand.Rand()); 73 } 74 75 size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, 76 size_t MaxSize) { 77 if (!Corpus || Corpus->size() < 2 || Size == 0) 78 return 0; 79 size_t Idx = Rand(Corpus->size()); 80 const Unit &Other = (*Corpus)[Idx]; 81 if (Other.empty()) 82 return 0; 83 MutateInPlaceHere.resize(MaxSize); 84 auto &U = MutateInPlaceHere; 85 size_t NewSize = EF->LLVMFuzzerCustomCrossOver( 86 Data, Size, Other.data(), Other.size(), U.data(), U.size(), Rand.Rand()); 87 if (!NewSize) 88 return 0; 89 assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); 90 memcpy(Data, U.data(), NewSize); 91 return NewSize; 92 } 93 94 size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, 95 size_t MaxSize) { 96 assert(Size); 97 size_t ShuffleAmount = 98 Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. 99 size_t ShuffleStart = Rand(Size - ShuffleAmount); 100 assert(ShuffleStart + ShuffleAmount <= Size); 101 std::random_shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, 102 Rand); 103 return Size; 104 } 105 106 size_t MutationDispatcher::Mutate_EraseByte(uint8_t *Data, size_t Size, 107 size_t MaxSize) { 108 assert(Size); 109 if (Size == 1) return 0; 110 size_t Idx = Rand(Size); 111 // Erase Data[Idx]. 112 memmove(Data + Idx, Data + Idx + 1, Size - Idx - 1); 113 return Size - 1; 114 } 115 116 size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, 117 size_t MaxSize) { 118 if (Size == MaxSize) return 0; 119 size_t Idx = Rand(Size + 1); 120 // Insert new value at Data[Idx]. 121 memmove(Data + Idx + 1, Data + Idx, Size - Idx); 122 Data[Idx] = RandCh(Rand); 123 return Size + 1; 124 } 125 126 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, 127 size_t MaxSize) { 128 size_t Idx = Rand(Size); 129 Data[Idx] = RandCh(Rand); 130 return Size; 131 } 132 133 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, 134 size_t MaxSize) { 135 size_t Idx = Rand(Size); 136 Data[Idx] = FlipRandomBit(Data[Idx], Rand); 137 return Size; 138 } 139 140 size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, 141 size_t Size, 142 size_t MaxSize) { 143 return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); 144 } 145 146 size_t MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary( 147 uint8_t *Data, size_t Size, size_t MaxSize) { 148 return AddWordFromDictionary(TempAutoDictionary, Data, Size, MaxSize); 149 } 150 151 size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( 152 uint8_t *Data, size_t Size, size_t MaxSize) { 153 return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); 154 } 155 156 size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, 157 size_t Size, size_t MaxSize) { 158 if (D.empty()) return 0; 159 DictionaryEntry &DE = D[Rand(D.size())]; 160 const Word &W = DE.GetW(); 161 bool UsePositionHint = DE.HasPositionHint() && 162 DE.GetPositionHint() + W.size() < Size && Rand.RandBool(); 163 if (Rand.RandBool()) { // Insert W. 164 if (Size + W.size() > MaxSize) return 0; 165 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); 166 memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); 167 memcpy(Data + Idx, W.data(), W.size()); 168 Size += W.size(); 169 } else { // Overwrite some bytes with W. 170 if (W.size() > Size) return 0; 171 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size()); 172 memcpy(Data + Idx, W.data(), W.size()); 173 } 174 DE.IncUseCount(); 175 CurrentDictionaryEntrySequence.push_back(&DE); 176 return Size; 177 } 178 179 size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, 180 size_t MaxSize) { 181 size_t B = Rand(Size); 182 while (B < Size && !isdigit(Data[B])) B++; 183 if (B == Size) return 0; 184 size_t E = B; 185 while (E < Size && isdigit(Data[E])) E++; 186 assert(B < E); 187 // now we have digits in [B, E). 188 // strtol and friends don't accept non-zero-teminated data, parse it manually. 189 uint64_t Val = Data[B] - '0'; 190 for (size_t i = B + 1; i < E; i++) 191 Val = Val * 10 + Data[i] - '0'; 192 193 // Mutate the integer value. 194 switch(Rand(5)) { 195 case 0: Val++; break; 196 case 1: Val--; break; 197 case 2: Val /= 2; break; 198 case 3: Val *= 2; break; 199 case 4: Val = Rand(Val * Val); break; 200 default: assert(0); 201 } 202 // Just replace the bytes with the new ones, don't bother moving bytes. 203 for (size_t i = B; i < E; i++) { 204 size_t Idx = E + B - i - 1; 205 assert(Idx >= B && Idx < E); 206 Data[Idx] = (Val % 10) + '0'; 207 Val /= 10; 208 } 209 return Size; 210 } 211 212 size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, 213 size_t MaxSize) { 214 if (!Corpus || Corpus->size() < 2 || Size == 0) return 0; 215 size_t Idx = Rand(Corpus->size()); 216 const Unit &Other = (*Corpus)[Idx]; 217 if (Other.empty()) return 0; 218 MutateInPlaceHere.resize(MaxSize); 219 auto &U = MutateInPlaceHere; 220 size_t NewSize = 221 CrossOver(Data, Size, Other.data(), Other.size(), U.data(), U.size()); 222 assert(NewSize > 0 && "CrossOver returned empty unit"); 223 assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); 224 memcpy(Data, U.data(), NewSize); 225 return NewSize; 226 } 227 228 void MutationDispatcher::StartMutationSequence() { 229 CurrentMutatorSequence.clear(); 230 CurrentDictionaryEntrySequence.clear(); 231 } 232 233 // Copy successful dictionary entries to PersistentAutoDictionary. 234 void MutationDispatcher::RecordSuccessfulMutationSequence() { 235 for (auto DE : CurrentDictionaryEntrySequence) { 236 // PersistentAutoDictionary.AddWithSuccessCountOne(DE); 237 DE->IncSuccessCount(); 238 // Linear search is fine here as this happens seldom. 239 if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) 240 PersistentAutoDictionary.push_back({DE->GetW(), 1}); 241 } 242 } 243 244 void MutationDispatcher::PrintRecommendedDictionary() { 245 std::vector<DictionaryEntry> V; 246 for (auto &DE : PersistentAutoDictionary) 247 if (!ManualDictionary.ContainsWord(DE.GetW())) 248 V.push_back(DE); 249 if (V.empty()) return; 250 Printf("###### Recommended dictionary. ######\n"); 251 for (auto &DE: V) { 252 Printf("\""); 253 PrintASCII(DE.GetW(), "\""); 254 Printf(" # Uses: %zd\n", DE.GetUseCount()); 255 } 256 Printf("###### End of recommended dictionary. ######\n"); 257 } 258 259 void MutationDispatcher::PrintMutationSequence() { 260 Printf("MS: %zd ", CurrentMutatorSequence.size()); 261 for (auto M : CurrentMutatorSequence) 262 Printf("%s-", M.Name); 263 if (!CurrentDictionaryEntrySequence.empty()) { 264 Printf(" DE: "); 265 for (auto DE : CurrentDictionaryEntrySequence) { 266 Printf("\""); 267 PrintASCII(DE->GetW(), "\"-"); 268 } 269 } 270 } 271 272 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { 273 return MutateImpl(Data, Size, MaxSize, Mutators); 274 } 275 276 size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, 277 size_t MaxSize) { 278 return MutateImpl(Data, Size, MaxSize, DefaultMutators); 279 } 280 281 // Mutates Data in place, returns new size. 282 size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, 283 size_t MaxSize, 284 const std::vector<Mutator> &Mutators) { 285 assert(MaxSize > 0); 286 assert(Size <= MaxSize); 287 if (Size == 0) { 288 for (size_t i = 0; i < MaxSize; i++) 289 Data[i] = RandCh(Rand); 290 if (Options.OnlyASCII) 291 ToASCII(Data, MaxSize); 292 return MaxSize; 293 } 294 assert(Size > 0); 295 // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), 296 // in which case they will return 0. 297 // Try several times before returning un-mutated data. 298 for (int Iter = 0; Iter < 10; Iter++) { 299 auto M = Mutators[Rand(Mutators.size())]; 300 size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); 301 if (NewSize) { 302 if (Options.OnlyASCII) 303 ToASCII(Data, NewSize); 304 CurrentMutatorSequence.push_back(M); 305 return NewSize; 306 } 307 } 308 return Size; 309 } 310 311 void MutationDispatcher::AddWordToManualDictionary(const Word &W) { 312 ManualDictionary.push_back( 313 {W, std::numeric_limits<size_t>::max()}); 314 } 315 316 void MutationDispatcher::AddWordToAutoDictionary(const Word &W, 317 size_t PositionHint) { 318 static const size_t kMaxAutoDictSize = 1 << 14; 319 if (TempAutoDictionary.size() >= kMaxAutoDictSize) return; 320 TempAutoDictionary.push_back({W, PositionHint}); 321 } 322 323 void MutationDispatcher::ClearAutoDictionary() { 324 TempAutoDictionary.clear(); 325 } 326 327 } // namespace fuzzer 328
