1 //===- FuzzerMutate.cpp - Mutate a test input -----------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // Mutate a test input. 9 //===----------------------------------------------------------------------===// 10 11 #include "FuzzerDefs.h" 12 #include "FuzzerExtFunctions.h" 13 #include "FuzzerIO.h" 14 #include "FuzzerMutate.h" 15 #include "FuzzerOptions.h" 16 #include "FuzzerTracePC.h" 17 18 namespace fuzzer { 19 20 const size_t Dictionary::kMaxDictSize; 21 static const size_t kMaxMutationsToPrint = 10; 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()) 65 return static_cast<char>(Rand(256)); 66 const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; 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 if (EF->__msan_unpoison) 73 EF->__msan_unpoison(Data, Size); 74 if (EF->__msan_unpoison_param) 75 EF->__msan_unpoison_param(4); 76 return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, 77 Rand.Rand<unsigned int>()); 78 } 79 80 size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, 81 size_t MaxSize) { 82 if (Size == 0) 83 return 0; 84 if (!CrossOverWith) return 0; 85 const Unit &Other = *CrossOverWith; 86 if (Other.empty()) 87 return 0; 88 CustomCrossOverInPlaceHere.resize(MaxSize); 89 auto &U = CustomCrossOverInPlaceHere; 90 91 if (EF->__msan_unpoison) { 92 EF->__msan_unpoison(Data, Size); 93 EF->__msan_unpoison(Other.data(), Other.size()); 94 EF->__msan_unpoison(U.data(), U.size()); 95 } 96 if (EF->__msan_unpoison_param) 97 EF->__msan_unpoison_param(7); 98 size_t NewSize = EF->LLVMFuzzerCustomCrossOver( 99 Data, Size, Other.data(), Other.size(), U.data(), U.size(), 100 Rand.Rand<unsigned int>()); 101 102 if (!NewSize) 103 return 0; 104 assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); 105 memcpy(Data, U.data(), NewSize); 106 return NewSize; 107 } 108 109 size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, 110 size_t MaxSize) { 111 if (Size > MaxSize || Size == 0) return 0; 112 size_t ShuffleAmount = 113 Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. 114 size_t ShuffleStart = Rand(Size - ShuffleAmount); 115 assert(ShuffleStart + ShuffleAmount <= Size); 116 std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand); 117 return Size; 118 } 119 120 size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, 121 size_t MaxSize) { 122 if (Size <= 1) return 0; 123 size_t N = Rand(Size / 2) + 1; 124 assert(N < Size); 125 size_t Idx = Rand(Size - N + 1); 126 // Erase Data[Idx:Idx+N]. 127 memmove(Data + Idx, Data + Idx + N, Size - Idx - N); 128 // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); 129 return Size - N; 130 } 131 132 size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, 133 size_t MaxSize) { 134 if (Size >= MaxSize) return 0; 135 size_t Idx = Rand(Size + 1); 136 // Insert new value at Data[Idx]. 137 memmove(Data + Idx + 1, Data + Idx, Size - Idx); 138 Data[Idx] = RandCh(Rand); 139 return Size + 1; 140 } 141 142 size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, 143 size_t Size, 144 size_t MaxSize) { 145 const size_t kMinBytesToInsert = 3; 146 if (Size + kMinBytesToInsert >= MaxSize) return 0; 147 size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); 148 size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; 149 assert(Size + N <= MaxSize && N); 150 size_t Idx = Rand(Size + 1); 151 // Insert new values at Data[Idx]. 152 memmove(Data + Idx + N, Data + Idx, Size - Idx); 153 // Give preference to 0x00 and 0xff. 154 uint8_t Byte = static_cast<uint8_t>( 155 Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255)); 156 for (size_t i = 0; i < N; i++) 157 Data[Idx + i] = Byte; 158 return Size + N; 159 } 160 161 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, 162 size_t MaxSize) { 163 if (Size > MaxSize) return 0; 164 size_t Idx = Rand(Size); 165 Data[Idx] = RandCh(Rand); 166 return Size; 167 } 168 169 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, 170 size_t MaxSize) { 171 if (Size > MaxSize) return 0; 172 size_t Idx = Rand(Size); 173 Data[Idx] ^= 1 << Rand(8); 174 return Size; 175 } 176 177 size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, 178 size_t Size, 179 size_t MaxSize) { 180 return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); 181 } 182 183 size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, 184 size_t MaxSize, 185 DictionaryEntry &DE) { 186 const Word &W = DE.GetW(); 187 bool UsePositionHint = DE.HasPositionHint() && 188 DE.GetPositionHint() + W.size() < Size && 189 Rand.RandBool(); 190 if (Rand.RandBool()) { // Insert W. 191 if (Size + W.size() > MaxSize) return 0; 192 size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); 193 memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); 194 memcpy(Data + Idx, W.data(), W.size()); 195 Size += W.size(); 196 } else { // Overwrite some bytes with W. 197 if (W.size() > Size) return 0; 198 size_t Idx = 199 UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size()); 200 memcpy(Data + Idx, W.data(), W.size()); 201 } 202 return Size; 203 } 204 205 // Somewhere in the past we have observed a comparison instructions 206 // with arguments Arg1 Arg2. This function tries to guess a dictionary 207 // entry that will satisfy that comparison. 208 // It first tries to find one of the arguments (possibly swapped) in the 209 // input and if it succeeds it creates a DE with a position hint. 210 // Otherwise it creates a DE with one of the arguments w/o a position hint. 211 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 212 const void *Arg1, const void *Arg2, 213 const void *Arg1Mutation, const void *Arg2Mutation, 214 size_t ArgSize, const uint8_t *Data, 215 size_t Size) { 216 bool HandleFirst = Rand.RandBool(); 217 const void *ExistingBytes, *DesiredBytes; 218 Word W; 219 const uint8_t *End = Data + Size; 220 for (int Arg = 0; Arg < 2; Arg++) { 221 ExistingBytes = HandleFirst ? Arg1 : Arg2; 222 DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; 223 HandleFirst = !HandleFirst; 224 W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize); 225 const size_t kMaxNumPositions = 8; 226 size_t Positions[kMaxNumPositions]; 227 size_t NumPositions = 0; 228 for (const uint8_t *Cur = Data; 229 Cur < End && NumPositions < kMaxNumPositions; Cur++) { 230 Cur = 231 (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); 232 if (!Cur) break; 233 Positions[NumPositions++] = Cur - Data; 234 } 235 if (!NumPositions) continue; 236 return DictionaryEntry(W, Positions[Rand(NumPositions)]); 237 } 238 DictionaryEntry DE(W); 239 return DE; 240 } 241 242 243 template <class T> 244 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 245 T Arg1, T Arg2, const uint8_t *Data, size_t Size) { 246 if (Rand.RandBool()) Arg1 = Bswap(Arg1); 247 if (Rand.RandBool()) Arg2 = Bswap(Arg2); 248 T Arg1Mutation = static_cast<T>(Arg1 + Rand(-1, 1)); 249 T Arg2Mutation = static_cast<T>(Arg2 + Rand(-1, 1)); 250 return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, 251 sizeof(Arg1), Data, Size); 252 } 253 254 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 255 const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) { 256 return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(), 257 Arg2.data(), Arg1.size(), Data, Size); 258 } 259 260 size_t MutationDispatcher::Mutate_AddWordFromTORC( 261 uint8_t *Data, size_t Size, size_t MaxSize) { 262 Word W; 263 DictionaryEntry DE; 264 switch (Rand(4)) { 265 case 0: { 266 auto X = TPC.TORC8.Get(Rand.Rand<size_t>()); 267 DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 268 } break; 269 case 1: { 270 auto X = TPC.TORC4.Get(Rand.Rand<size_t>()); 271 if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool()) 272 DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size); 273 else 274 DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 275 } break; 276 case 2: { 277 auto X = TPC.TORCW.Get(Rand.Rand<size_t>()); 278 DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 279 } break; 280 case 3: if (Options.UseMemmem) { 281 auto X = TPC.MMT.Get(Rand.Rand<size_t>()); 282 DE = DictionaryEntry(X); 283 } break; 284 default: 285 assert(0); 286 } 287 if (!DE.GetW().size()) return 0; 288 Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 289 if (!Size) return 0; 290 DictionaryEntry &DERef = 291 CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ % 292 kCmpDictionaryEntriesDequeSize]; 293 DERef = DE; 294 CurrentDictionaryEntrySequence.push_back(&DERef); 295 return Size; 296 } 297 298 size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( 299 uint8_t *Data, size_t Size, size_t MaxSize) { 300 return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); 301 } 302 303 size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, 304 size_t Size, size_t MaxSize) { 305 if (Size > MaxSize) return 0; 306 if (D.empty()) return 0; 307 DictionaryEntry &DE = D[Rand(D.size())]; 308 Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 309 if (!Size) return 0; 310 DE.IncUseCount(); 311 CurrentDictionaryEntrySequence.push_back(&DE); 312 return Size; 313 } 314 315 // Overwrites part of To[0,ToSize) with a part of From[0,FromSize). 316 // Returns ToSize. 317 size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, 318 uint8_t *To, size_t ToSize) { 319 // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). 320 size_t ToBeg = Rand(ToSize); 321 size_t CopySize = Rand(ToSize - ToBeg) + 1; 322 assert(ToBeg + CopySize <= ToSize); 323 CopySize = std::min(CopySize, FromSize); 324 size_t FromBeg = Rand(FromSize - CopySize + 1); 325 assert(FromBeg + CopySize <= FromSize); 326 memmove(To + ToBeg, From + FromBeg, CopySize); 327 return ToSize; 328 } 329 330 // Inserts part of From[0,ToSize) into To. 331 // Returns new size of To on success or 0 on failure. 332 size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, 333 uint8_t *To, size_t ToSize, 334 size_t MaxToSize) { 335 if (ToSize >= MaxToSize) return 0; 336 size_t AvailableSpace = MaxToSize - ToSize; 337 size_t MaxCopySize = std::min(AvailableSpace, FromSize); 338 size_t CopySize = Rand(MaxCopySize) + 1; 339 size_t FromBeg = Rand(FromSize - CopySize + 1); 340 assert(FromBeg + CopySize <= FromSize); 341 size_t ToInsertPos = Rand(ToSize + 1); 342 assert(ToInsertPos + CopySize <= MaxToSize); 343 size_t TailSize = ToSize - ToInsertPos; 344 if (To == From) { 345 MutateInPlaceHere.resize(MaxToSize); 346 memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); 347 memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 348 memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); 349 } else { 350 memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 351 memmove(To + ToInsertPos, From + FromBeg, CopySize); 352 } 353 return ToSize + CopySize; 354 } 355 356 size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, 357 size_t MaxSize) { 358 if (Size > MaxSize || Size == 0) return 0; 359 // If Size == MaxSize, `InsertPartOf(...)` will 360 // fail so there's no point using it in this case. 361 if (Size == MaxSize || Rand.RandBool()) 362 return CopyPartOf(Data, Size, Data, Size); 363 else 364 return InsertPartOf(Data, Size, Data, Size, MaxSize); 365 } 366 367 size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, 368 size_t MaxSize) { 369 if (Size > MaxSize) return 0; 370 size_t B = Rand(Size); 371 while (B < Size && !isdigit(Data[B])) B++; 372 if (B == Size) return 0; 373 size_t E = B; 374 while (E < Size && isdigit(Data[E])) E++; 375 assert(B < E); 376 // now we have digits in [B, E). 377 // strtol and friends don't accept non-zero-teminated data, parse it manually. 378 uint64_t Val = Data[B] - '0'; 379 for (size_t i = B + 1; i < E; i++) 380 Val = Val * 10 + Data[i] - '0'; 381 382 // Mutate the integer value. 383 switch(Rand(5)) { 384 case 0: Val++; break; 385 case 1: Val--; break; 386 case 2: Val /= 2; break; 387 case 3: Val *= 2; break; 388 case 4: Val = Rand(Val * Val); break; 389 default: assert(0); 390 } 391 // Just replace the bytes with the new ones, don't bother moving bytes. 392 for (size_t i = B; i < E; i++) { 393 size_t Idx = E + B - i - 1; 394 assert(Idx >= B && Idx < E); 395 Data[Idx] = (Val % 10) + '0'; 396 Val /= 10; 397 } 398 return Size; 399 } 400 401 template<class T> 402 size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { 403 if (Size < sizeof(T)) return 0; 404 size_t Off = Rand(Size - sizeof(T) + 1); 405 assert(Off + sizeof(T) <= Size); 406 T Val; 407 if (Off < 64 && !Rand(4)) { 408 Val = static_cast<T>(Size); 409 if (Rand.RandBool()) 410 Val = Bswap(Val); 411 } else { 412 memcpy(&Val, Data + Off, sizeof(Val)); 413 T Add = static_cast<T>(Rand(21)); 414 Add -= 10; 415 if (Rand.RandBool()) 416 Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. 417 else 418 Val = Val + Add; // Add assuming current endiannes. 419 if (Add == 0 || Rand.RandBool()) // Maybe negate. 420 Val = -Val; 421 } 422 memcpy(Data + Off, &Val, sizeof(Val)); 423 return Size; 424 } 425 426 size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, 427 size_t Size, 428 size_t MaxSize) { 429 if (Size > MaxSize) return 0; 430 switch (Rand(4)) { 431 case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand); 432 case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand); 433 case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand); 434 case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand); 435 default: assert(0); 436 } 437 return 0; 438 } 439 440 size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, 441 size_t MaxSize) { 442 if (Size > MaxSize) return 0; 443 if (Size == 0) return 0; 444 if (!CrossOverWith) return 0; 445 const Unit &O = *CrossOverWith; 446 if (O.empty()) return 0; 447 size_t NewSize = 0; 448 switch(Rand(3)) { 449 case 0: 450 MutateInPlaceHere.resize(MaxSize); 451 NewSize = CrossOver(Data, Size, O.data(), O.size(), 452 MutateInPlaceHere.data(), MaxSize); 453 memcpy(Data, MutateInPlaceHere.data(), NewSize); 454 break; 455 case 1: 456 NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize); 457 if (!NewSize) 458 NewSize = CopyPartOf(O.data(), O.size(), Data, Size); 459 break; 460 case 2: 461 NewSize = CopyPartOf(O.data(), O.size(), Data, Size); 462 break; 463 default: assert(0); 464 } 465 assert(NewSize > 0 && "CrossOver returned empty unit"); 466 assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); 467 return NewSize; 468 } 469 470 void MutationDispatcher::StartMutationSequence() { 471 CurrentMutatorSequence.clear(); 472 CurrentDictionaryEntrySequence.clear(); 473 } 474 475 // Copy successful dictionary entries to PersistentAutoDictionary. 476 void MutationDispatcher::RecordSuccessfulMutationSequence() { 477 for (auto DE : CurrentDictionaryEntrySequence) { 478 // PersistentAutoDictionary.AddWithSuccessCountOne(DE); 479 DE->IncSuccessCount(); 480 assert(DE->GetW().size()); 481 // Linear search is fine here as this happens seldom. 482 if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) 483 PersistentAutoDictionary.push_back(*DE); 484 } 485 } 486 487 void MutationDispatcher::PrintRecommendedDictionary() { 488 std::vector<DictionaryEntry> V; 489 for (auto &DE : PersistentAutoDictionary) 490 if (!ManualDictionary.ContainsWord(DE.GetW())) 491 V.push_back(DE); 492 if (V.empty()) return; 493 Printf("###### Recommended dictionary. ######\n"); 494 for (auto &DE: V) { 495 assert(DE.GetW().size()); 496 Printf("\""); 497 PrintASCII(DE.GetW(), "\""); 498 Printf(" # Uses: %zd\n", DE.GetUseCount()); 499 } 500 Printf("###### End of recommended dictionary. ######\n"); 501 } 502 503 void MutationDispatcher::PrintMutationSequence(bool Verbose) { 504 Printf("MS: %zd ", CurrentMutatorSequence.size()); 505 size_t EntriesToPrint = 506 Verbose ? CurrentMutatorSequence.size() 507 : std::min(kMaxMutationsToPrint, CurrentMutatorSequence.size()); 508 for (size_t i = 0; i < EntriesToPrint; i++) 509 Printf("%s-", CurrentMutatorSequence[i].Name); 510 if (!CurrentDictionaryEntrySequence.empty()) { 511 Printf(" DE: "); 512 EntriesToPrint = Verbose ? CurrentDictionaryEntrySequence.size() 513 : std::min(kMaxMutationsToPrint, 514 CurrentDictionaryEntrySequence.size()); 515 for (size_t i = 0; i < EntriesToPrint; i++) { 516 Printf("\""); 517 PrintASCII(CurrentDictionaryEntrySequence[i]->GetW(), "\"-"); 518 } 519 } 520 } 521 522 std::string MutationDispatcher::MutationSequence() { 523 std::string MS; 524 for (const auto &M : CurrentMutatorSequence) { 525 MS += M.Name; 526 MS += "-"; 527 } 528 return MS; 529 } 530 531 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { 532 return MutateImpl(Data, Size, MaxSize, Mutators); 533 } 534 535 size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, 536 size_t MaxSize) { 537 return MutateImpl(Data, Size, MaxSize, DefaultMutators); 538 } 539 540 // Mutates Data in place, returns new size. 541 size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, 542 size_t MaxSize, 543 std::vector<Mutator> &Mutators) { 544 assert(MaxSize > 0); 545 // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), 546 // in which case they will return 0. 547 // Try several times before returning un-mutated data. 548 for (int Iter = 0; Iter < 100; Iter++) { 549 auto M = Mutators[Rand(Mutators.size())]; 550 size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); 551 if (NewSize && NewSize <= MaxSize) { 552 if (Options.OnlyASCII) 553 ToASCII(Data, NewSize); 554 CurrentMutatorSequence.push_back(M); 555 return NewSize; 556 } 557 } 558 *Data = ' '; 559 return 1; // Fallback, should not happen frequently. 560 } 561 562 // Mask represents the set of Data bytes that are worth mutating. 563 size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size, 564 size_t MaxSize, 565 const std::vector<uint8_t> &Mask) { 566 size_t MaskedSize = std::min(Size, Mask.size()); 567 // * Copy the worthy bytes into a temporary array T 568 // * Mutate T 569 // * Copy T back. 570 // This is totally unoptimized. 571 auto &T = MutateWithMaskTemp; 572 if (T.size() < Size) 573 T.resize(Size); 574 size_t OneBits = 0; 575 for (size_t I = 0; I < MaskedSize; I++) 576 if (Mask[I]) 577 T[OneBits++] = Data[I]; 578 579 if (!OneBits) return 0; 580 assert(!T.empty()); 581 size_t NewSize = Mutate(T.data(), OneBits, OneBits); 582 assert(NewSize <= OneBits); 583 (void)NewSize; 584 // Even if NewSize < OneBits we still use all OneBits bytes. 585 for (size_t I = 0, J = 0; I < MaskedSize; I++) 586 if (Mask[I]) 587 Data[I] = T[J++]; 588 return Size; 589 } 590 591 void MutationDispatcher::AddWordToManualDictionary(const Word &W) { 592 ManualDictionary.push_back( 593 {W, std::numeric_limits<size_t>::max()}); 594 } 595 596 } // namespace fuzzer 597