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 "FuzzerMutate.h" 13 #include "FuzzerCorpus.h" 14 #include "FuzzerDefs.h" 15 #include "FuzzerExtFunctions.h" 16 #include "FuzzerIO.h" 17 #include "FuzzerOptions.h" 18 19 namespace fuzzer { 20 21 const size_t Dictionary::kMaxDictSize; 22 23 static void PrintASCII(const Word &W, const char *PrintAfter) { 24 PrintASCII(W.data(), W.size(), PrintAfter); 25 } 26 27 MutationDispatcher::MutationDispatcher(Random &Rand, 28 const FuzzingOptions &Options) 29 : Rand(Rand), Options(Options) { 30 DefaultMutators.insert( 31 DefaultMutators.begin(), 32 { 33 {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"}, 34 {&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, 35 {&MutationDispatcher::Mutate_InsertRepeatedBytes, 36 "InsertRepeatedBytes"}, 37 {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, 38 {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, 39 {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, 40 {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, 41 {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"}, 42 {&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, 43 {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, 44 {&MutationDispatcher::Mutate_AddWordFromManualDictionary, 45 "ManualDict"}, 46 {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, 47 "PersAutoDict"}, 48 }); 49 if(Options.UseCmp) 50 DefaultMutators.push_back( 51 {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"}); 52 53 if (EF->LLVMFuzzerCustomMutator) 54 Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); 55 else 56 Mutators = DefaultMutators; 57 58 if (EF->LLVMFuzzerCustomCrossOver) 59 Mutators.push_back( 60 {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); 61 } 62 63 static char RandCh(Random &Rand) { 64 if (Rand.RandBool()) return Rand(256); 65 const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; 66 return Special[Rand(sizeof(Special) - 1)]; 67 } 68 69 size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, 70 size_t MaxSize) { 71 return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, Rand.Rand()); 72 } 73 74 size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, 75 size_t MaxSize) { 76 if (!Corpus || Corpus->size() < 2 || Size == 0) 77 return 0; 78 size_t Idx = Rand(Corpus->size()); 79 const Unit &Other = (*Corpus)[Idx]; 80 if (Other.empty()) 81 return 0; 82 CustomCrossOverInPlaceHere.resize(MaxSize); 83 auto &U = CustomCrossOverInPlaceHere; 84 size_t NewSize = EF->LLVMFuzzerCustomCrossOver( 85 Data, Size, Other.data(), Other.size(), U.data(), U.size(), Rand.Rand()); 86 if (!NewSize) 87 return 0; 88 assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); 89 memcpy(Data, U.data(), NewSize); 90 return NewSize; 91 } 92 93 size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, 94 size_t MaxSize) { 95 if (Size > MaxSize || Size == 0) return 0; 96 size_t ShuffleAmount = 97 Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. 98 size_t ShuffleStart = Rand(Size - ShuffleAmount); 99 assert(ShuffleStart + ShuffleAmount <= Size); 100 std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand); 101 return Size; 102 } 103 104 size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, 105 size_t MaxSize) { 106 if (Size <= 1) return 0; 107 size_t N = Rand(Size / 2) + 1; 108 assert(N < Size); 109 size_t Idx = Rand(Size - N + 1); 110 // Erase Data[Idx:Idx+N]. 111 memmove(Data + Idx, Data + Idx + N, Size - Idx - N); 112 // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); 113 return Size - N; 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_InsertRepeatedBytes(uint8_t *Data, 127 size_t Size, 128 size_t MaxSize) { 129 const size_t kMinBytesToInsert = 3; 130 if (Size + kMinBytesToInsert >= MaxSize) return 0; 131 size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); 132 size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; 133 assert(Size + N <= MaxSize && N); 134 size_t Idx = Rand(Size + 1); 135 // Insert new values at Data[Idx]. 136 memmove(Data + Idx + N, Data + Idx, Size - Idx); 137 // Give preference to 0x00 and 0xff. 138 uint8_t Byte = Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255); 139 for (size_t i = 0; i < N; i++) 140 Data[Idx + i] = Byte; 141 return Size + N; 142 } 143 144 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, 145 size_t MaxSize) { 146 if (Size > MaxSize) return 0; 147 size_t Idx = Rand(Size); 148 Data[Idx] = RandCh(Rand); 149 return Size; 150 } 151 152 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, 153 size_t MaxSize) { 154 if (Size > MaxSize) return 0; 155 size_t Idx = Rand(Size); 156 Data[Idx] ^= 1 << Rand(8); 157 return Size; 158 } 159 160 size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, 161 size_t Size, 162 size_t MaxSize) { 163 return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); 164 } 165 166 size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, 167 size_t MaxSize, 168 DictionaryEntry &DE) { 169 const Word &W = DE.GetW(); 170 bool UsePositionHint = DE.HasPositionHint() && 171 DE.GetPositionHint() + W.size() < Size && 172 Rand.RandBool(); 173 if (Rand.RandBool()) { // Insert W. 174 if (Size + W.size() > MaxSize) return 0; 175 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); 176 memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); 177 memcpy(Data + Idx, W.data(), W.size()); 178 Size += W.size(); 179 } else { // Overwrite some bytes with W. 180 if (W.size() > Size) return 0; 181 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size()); 182 memcpy(Data + Idx, W.data(), W.size()); 183 } 184 return Size; 185 } 186 187 // Somewhere in the past we have observed a comparison instructions 188 // with arguments Arg1 Arg2. This function tries to guess a dictionary 189 // entry that will satisfy that comparison. 190 // It first tries to find one of the arguments (possibly swapped) in the 191 // input and if it succeeds it creates a DE with a position hint. 192 // Otherwise it creates a DE with one of the arguments w/o a position hint. 193 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 194 const void *Arg1, const void *Arg2, 195 const void *Arg1Mutation, const void *Arg2Mutation, 196 size_t ArgSize, const uint8_t *Data, 197 size_t Size) { 198 ScopedDoingMyOwnMemOrStr scoped_doing_my_own_mem_os_str; 199 bool HandleFirst = Rand.RandBool(); 200 const void *ExistingBytes, *DesiredBytes; 201 Word W; 202 const uint8_t *End = Data + Size; 203 for (int Arg = 0; Arg < 2; Arg++) { 204 ExistingBytes = HandleFirst ? Arg1 : Arg2; 205 DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; 206 HandleFirst = !HandleFirst; 207 W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize); 208 const size_t kMaxNumPositions = 8; 209 size_t Positions[kMaxNumPositions]; 210 size_t NumPositions = 0; 211 for (const uint8_t *Cur = Data; 212 Cur < End && NumPositions < kMaxNumPositions; Cur++) { 213 Cur = 214 (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); 215 if (!Cur) break; 216 Positions[NumPositions++] = Cur - Data; 217 } 218 if (!NumPositions) continue; 219 return DictionaryEntry(W, Positions[Rand(NumPositions)]); 220 } 221 DictionaryEntry DE(W); 222 return DE; 223 } 224 225 226 template <class T> 227 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 228 T Arg1, T Arg2, const uint8_t *Data, size_t Size) { 229 if (Rand.RandBool()) Arg1 = Bswap(Arg1); 230 if (Rand.RandBool()) Arg2 = Bswap(Arg2); 231 T Arg1Mutation = Arg1 + Rand(-1, 1); 232 T Arg2Mutation = Arg2 + Rand(-1, 1); 233 return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, 234 sizeof(Arg1), Data, Size); 235 } 236 237 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 238 const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) { 239 return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(), 240 Arg2.data(), Arg1.size(), Data, Size); 241 } 242 243 size_t MutationDispatcher::Mutate_AddWordFromTORC( 244 uint8_t *Data, size_t Size, size_t MaxSize) { 245 Word W; 246 DictionaryEntry DE; 247 switch (Rand(4)) { 248 case 0: { 249 auto X = TPC.TORC8.Get(Rand.Rand()); 250 DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 251 } break; 252 case 1: { 253 auto X = TPC.TORC4.Get(Rand.Rand()); 254 if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool()) 255 DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size); 256 else 257 DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 258 } break; 259 case 2: { 260 auto X = TPC.TORCW.Get(Rand.Rand()); 261 DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 262 } break; 263 case 3: if (Options.UseMemmem) { 264 auto X = TPC.MMT.Get(Rand.Rand()); 265 DE = DictionaryEntry(X); 266 } break; 267 default: 268 assert(0); 269 } 270 if (!DE.GetW().size()) return 0; 271 Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 272 if (!Size) return 0; 273 DictionaryEntry &DERef = 274 CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ % 275 kCmpDictionaryEntriesDequeSize]; 276 DERef = DE; 277 CurrentDictionaryEntrySequence.push_back(&DERef); 278 return Size; 279 } 280 281 size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( 282 uint8_t *Data, size_t Size, size_t MaxSize) { 283 return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); 284 } 285 286 size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, 287 size_t Size, size_t MaxSize) { 288 if (Size > MaxSize) return 0; 289 if (D.empty()) return 0; 290 DictionaryEntry &DE = D[Rand(D.size())]; 291 Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 292 if (!Size) return 0; 293 DE.IncUseCount(); 294 CurrentDictionaryEntrySequence.push_back(&DE); 295 return Size; 296 } 297 298 // Overwrites part of To[0,ToSize) with a part of From[0,FromSize). 299 // Returns ToSize. 300 size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, 301 uint8_t *To, size_t ToSize) { 302 // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). 303 size_t ToBeg = Rand(ToSize); 304 size_t CopySize = Rand(ToSize - ToBeg) + 1; 305 assert(ToBeg + CopySize <= ToSize); 306 CopySize = std::min(CopySize, FromSize); 307 size_t FromBeg = Rand(FromSize - CopySize + 1); 308 assert(FromBeg + CopySize <= FromSize); 309 memmove(To + ToBeg, From + FromBeg, CopySize); 310 return ToSize; 311 } 312 313 // Inserts part of From[0,ToSize) into To. 314 // Returns new size of To on success or 0 on failure. 315 size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, 316 uint8_t *To, size_t ToSize, 317 size_t MaxToSize) { 318 if (ToSize >= MaxToSize) return 0; 319 size_t AvailableSpace = MaxToSize - ToSize; 320 size_t MaxCopySize = std::min(AvailableSpace, FromSize); 321 size_t CopySize = Rand(MaxCopySize) + 1; 322 size_t FromBeg = Rand(FromSize - CopySize + 1); 323 assert(FromBeg + CopySize <= FromSize); 324 size_t ToInsertPos = Rand(ToSize + 1); 325 assert(ToInsertPos + CopySize <= MaxToSize); 326 size_t TailSize = ToSize - ToInsertPos; 327 if (To == From) { 328 MutateInPlaceHere.resize(MaxToSize); 329 memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); 330 memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 331 memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); 332 } else { 333 memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 334 memmove(To + ToInsertPos, From + FromBeg, CopySize); 335 } 336 return ToSize + CopySize; 337 } 338 339 size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, 340 size_t MaxSize) { 341 if (Size > MaxSize || Size == 0) return 0; 342 if (Rand.RandBool()) 343 return CopyPartOf(Data, Size, Data, Size); 344 else 345 return InsertPartOf(Data, Size, Data, Size, MaxSize); 346 } 347 348 size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, 349 size_t MaxSize) { 350 if (Size > MaxSize) return 0; 351 size_t B = Rand(Size); 352 while (B < Size && !isdigit(Data[B])) B++; 353 if (B == Size) return 0; 354 size_t E = B; 355 while (E < Size && isdigit(Data[E])) E++; 356 assert(B < E); 357 // now we have digits in [B, E). 358 // strtol and friends don't accept non-zero-teminated data, parse it manually. 359 uint64_t Val = Data[B] - '0'; 360 for (size_t i = B + 1; i < E; i++) 361 Val = Val * 10 + Data[i] - '0'; 362 363 // Mutate the integer value. 364 switch(Rand(5)) { 365 case 0: Val++; break; 366 case 1: Val--; break; 367 case 2: Val /= 2; break; 368 case 3: Val *= 2; break; 369 case 4: Val = Rand(Val * Val); break; 370 default: assert(0); 371 } 372 // Just replace the bytes with the new ones, don't bother moving bytes. 373 for (size_t i = B; i < E; i++) { 374 size_t Idx = E + B - i - 1; 375 assert(Idx >= B && Idx < E); 376 Data[Idx] = (Val % 10) + '0'; 377 Val /= 10; 378 } 379 return Size; 380 } 381 382 template<class T> 383 size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { 384 if (Size < sizeof(T)) return 0; 385 size_t Off = Rand(Size - sizeof(T) + 1); 386 assert(Off + sizeof(T) <= Size); 387 T Val; 388 if (Off < 64 && !Rand(4)) { 389 Val = Size; 390 if (Rand.RandBool()) 391 Val = Bswap(Val); 392 } else { 393 memcpy(&Val, Data + Off, sizeof(Val)); 394 T Add = Rand(21); 395 Add -= 10; 396 if (Rand.RandBool()) 397 Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. 398 else 399 Val = Val + Add; // Add assuming current endiannes. 400 if (Add == 0 || Rand.RandBool()) // Maybe negate. 401 Val = -Val; 402 } 403 memcpy(Data + Off, &Val, sizeof(Val)); 404 return Size; 405 } 406 407 size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, 408 size_t Size, 409 size_t MaxSize) { 410 if (Size > MaxSize) return 0; 411 switch (Rand(4)) { 412 case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand); 413 case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand); 414 case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand); 415 case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand); 416 default: assert(0); 417 } 418 return 0; 419 } 420 421 size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, 422 size_t MaxSize) { 423 if (Size > MaxSize) return 0; 424 if (!Corpus || Corpus->size() < 2 || Size == 0) return 0; 425 size_t Idx = Rand(Corpus->size()); 426 const Unit &O = (*Corpus)[Idx]; 427 if (O.empty()) return 0; 428 MutateInPlaceHere.resize(MaxSize); 429 auto &U = MutateInPlaceHere; 430 size_t NewSize = 0; 431 switch(Rand(3)) { 432 case 0: 433 NewSize = CrossOver(Data, Size, O.data(), O.size(), U.data(), U.size()); 434 break; 435 case 1: 436 NewSize = InsertPartOf(O.data(), O.size(), U.data(), U.size(), MaxSize); 437 if (!NewSize) 438 NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size()); 439 break; 440 case 2: 441 NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size()); 442 break; 443 default: assert(0); 444 } 445 assert(NewSize > 0 && "CrossOver returned empty unit"); 446 assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); 447 memcpy(Data, U.data(), NewSize); 448 return NewSize; 449 } 450 451 void MutationDispatcher::StartMutationSequence() { 452 CurrentMutatorSequence.clear(); 453 CurrentDictionaryEntrySequence.clear(); 454 } 455 456 // Copy successful dictionary entries to PersistentAutoDictionary. 457 void MutationDispatcher::RecordSuccessfulMutationSequence() { 458 for (auto DE : CurrentDictionaryEntrySequence) { 459 // PersistentAutoDictionary.AddWithSuccessCountOne(DE); 460 DE->IncSuccessCount(); 461 assert(DE->GetW().size()); 462 // Linear search is fine here as this happens seldom. 463 if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) 464 PersistentAutoDictionary.push_back({DE->GetW(), 1}); 465 } 466 } 467 468 void MutationDispatcher::PrintRecommendedDictionary() { 469 Vector<DictionaryEntry> V; 470 for (auto &DE : PersistentAutoDictionary) 471 if (!ManualDictionary.ContainsWord(DE.GetW())) 472 V.push_back(DE); 473 if (V.empty()) return; 474 Printf("###### Recommended dictionary. ######\n"); 475 for (auto &DE: V) { 476 assert(DE.GetW().size()); 477 Printf("\""); 478 PrintASCII(DE.GetW(), "\""); 479 Printf(" # Uses: %zd\n", DE.GetUseCount()); 480 } 481 Printf("###### End of recommended dictionary. ######\n"); 482 } 483 484 void MutationDispatcher::PrintMutationSequence() { 485 Printf("MS: %zd ", CurrentMutatorSequence.size()); 486 for (auto M : CurrentMutatorSequence) 487 Printf("%s-", M.Name); 488 if (!CurrentDictionaryEntrySequence.empty()) { 489 Printf(" DE: "); 490 for (auto DE : CurrentDictionaryEntrySequence) { 491 Printf("\""); 492 PrintASCII(DE->GetW(), "\"-"); 493 } 494 } 495 } 496 497 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { 498 return MutateImpl(Data, Size, MaxSize, Mutators); 499 } 500 501 size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, 502 size_t MaxSize) { 503 return MutateImpl(Data, Size, MaxSize, DefaultMutators); 504 } 505 506 // Mutates Data in place, returns new size. 507 size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, 508 size_t MaxSize, 509 Vector<Mutator> &Mutators) { 510 assert(MaxSize > 0); 511 // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), 512 // in which case they will return 0. 513 // Try several times before returning un-mutated data. 514 for (int Iter = 0; Iter < 100; Iter++) { 515 auto M = Mutators[Rand(Mutators.size())]; 516 size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); 517 if (NewSize && NewSize <= MaxSize) { 518 if (Options.OnlyASCII) 519 ToASCII(Data, NewSize); 520 CurrentMutatorSequence.push_back(M); 521 return NewSize; 522 } 523 } 524 *Data = ' '; 525 return 1; // Fallback, should not happen frequently. 526 } 527 528 void MutationDispatcher::AddWordToManualDictionary(const Word &W) { 529 ManualDictionary.push_back( 530 {W, std::numeric_limits<size_t>::max()}); 531 } 532 533 } // namespace fuzzer 534