1326943Sdim//===- FuzzerMutate.cpp - Mutate a test input -----------------------------===// 2326943Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6326943Sdim// 7326943Sdim//===----------------------------------------------------------------------===// 8326943Sdim// Mutate a test input. 9326943Sdim//===----------------------------------------------------------------------===// 10326943Sdim 11326943Sdim#include "FuzzerDefs.h" 12326943Sdim#include "FuzzerExtFunctions.h" 13326943Sdim#include "FuzzerIO.h" 14353358Sdim#include "FuzzerMutate.h" 15326943Sdim#include "FuzzerOptions.h" 16353358Sdim#include "FuzzerTracePC.h" 17326943Sdim 18326943Sdimnamespace fuzzer { 19326943Sdim 20326943Sdimconst size_t Dictionary::kMaxDictSize; 21326943Sdim 22326943Sdimstatic void PrintASCII(const Word &W, const char *PrintAfter) { 23326943Sdim PrintASCII(W.data(), W.size(), PrintAfter); 24326943Sdim} 25326943Sdim 26326943SdimMutationDispatcher::MutationDispatcher(Random &Rand, 27326943Sdim const FuzzingOptions &Options) 28326943Sdim : Rand(Rand), Options(Options) { 29326943Sdim DefaultMutators.insert( 30326943Sdim DefaultMutators.begin(), 31326943Sdim { 32344779Sdim {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"}, 33344779Sdim {&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, 34326943Sdim {&MutationDispatcher::Mutate_InsertRepeatedBytes, 35344779Sdim "InsertRepeatedBytes"}, 36344779Sdim {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, 37344779Sdim {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, 38344779Sdim {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, 39344779Sdim {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, 40344779Sdim {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"}, 41344779Sdim {&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, 42344779Sdim {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, 43326943Sdim {&MutationDispatcher::Mutate_AddWordFromManualDictionary, 44344779Sdim "ManualDict"}, 45326943Sdim {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, 46344779Sdim "PersAutoDict"}, 47326943Sdim }); 48326943Sdim if(Options.UseCmp) 49326943Sdim DefaultMutators.push_back( 50344779Sdim {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"}); 51326943Sdim 52326943Sdim if (EF->LLVMFuzzerCustomMutator) 53344779Sdim Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); 54326943Sdim else 55326943Sdim Mutators = DefaultMutators; 56326943Sdim 57326943Sdim if (EF->LLVMFuzzerCustomCrossOver) 58326943Sdim Mutators.push_back( 59344779Sdim {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); 60326943Sdim} 61326943Sdim 62326943Sdimstatic char RandCh(Random &Rand) { 63326943Sdim if (Rand.RandBool()) return Rand(256); 64336817Sdim const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; 65326943Sdim return Special[Rand(sizeof(Special) - 1)]; 66326943Sdim} 67326943Sdim 68326943Sdimsize_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, 69326943Sdim size_t MaxSize) { 70326943Sdim return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, Rand.Rand()); 71326943Sdim} 72326943Sdim 73326943Sdimsize_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, 74326943Sdim size_t MaxSize) { 75353358Sdim if (Size == 0) 76326943Sdim return 0; 77353358Sdim if (!CrossOverWith) return 0; 78353358Sdim const Unit &Other = *CrossOverWith; 79326943Sdim if (Other.empty()) 80326943Sdim return 0; 81326943Sdim CustomCrossOverInPlaceHere.resize(MaxSize); 82326943Sdim auto &U = CustomCrossOverInPlaceHere; 83326943Sdim size_t NewSize = EF->LLVMFuzzerCustomCrossOver( 84326943Sdim Data, Size, Other.data(), Other.size(), U.data(), U.size(), Rand.Rand()); 85326943Sdim if (!NewSize) 86326943Sdim return 0; 87326943Sdim assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); 88326943Sdim memcpy(Data, U.data(), NewSize); 89326943Sdim return NewSize; 90326943Sdim} 91326943Sdim 92326943Sdimsize_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, 93326943Sdim size_t MaxSize) { 94326943Sdim if (Size > MaxSize || Size == 0) return 0; 95326943Sdim size_t ShuffleAmount = 96326943Sdim Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. 97326943Sdim size_t ShuffleStart = Rand(Size - ShuffleAmount); 98326943Sdim assert(ShuffleStart + ShuffleAmount <= Size); 99326943Sdim std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand); 100326943Sdim return Size; 101326943Sdim} 102326943Sdim 103326943Sdimsize_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, 104326943Sdim size_t MaxSize) { 105326943Sdim if (Size <= 1) return 0; 106326943Sdim size_t N = Rand(Size / 2) + 1; 107326943Sdim assert(N < Size); 108326943Sdim size_t Idx = Rand(Size - N + 1); 109326943Sdim // Erase Data[Idx:Idx+N]. 110326943Sdim memmove(Data + Idx, Data + Idx + N, Size - Idx - N); 111326943Sdim // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); 112326943Sdim return Size - N; 113326943Sdim} 114326943Sdim 115326943Sdimsize_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, 116326943Sdim size_t MaxSize) { 117326943Sdim if (Size >= MaxSize) return 0; 118326943Sdim size_t Idx = Rand(Size + 1); 119326943Sdim // Insert new value at Data[Idx]. 120326943Sdim memmove(Data + Idx + 1, Data + Idx, Size - Idx); 121326943Sdim Data[Idx] = RandCh(Rand); 122326943Sdim return Size + 1; 123326943Sdim} 124326943Sdim 125326943Sdimsize_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, 126326943Sdim size_t Size, 127326943Sdim size_t MaxSize) { 128326943Sdim const size_t kMinBytesToInsert = 3; 129326943Sdim if (Size + kMinBytesToInsert >= MaxSize) return 0; 130326943Sdim size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); 131326943Sdim size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; 132326943Sdim assert(Size + N <= MaxSize && N); 133326943Sdim size_t Idx = Rand(Size + 1); 134326943Sdim // Insert new values at Data[Idx]. 135326943Sdim memmove(Data + Idx + N, Data + Idx, Size - Idx); 136326943Sdim // Give preference to 0x00 and 0xff. 137326943Sdim uint8_t Byte = Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255); 138326943Sdim for (size_t i = 0; i < N; i++) 139326943Sdim Data[Idx + i] = Byte; 140326943Sdim return Size + N; 141326943Sdim} 142326943Sdim 143326943Sdimsize_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, 144326943Sdim size_t MaxSize) { 145326943Sdim if (Size > MaxSize) return 0; 146326943Sdim size_t Idx = Rand(Size); 147326943Sdim Data[Idx] = RandCh(Rand); 148326943Sdim return Size; 149326943Sdim} 150326943Sdim 151326943Sdimsize_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, 152326943Sdim size_t MaxSize) { 153326943Sdim if (Size > MaxSize) return 0; 154326943Sdim size_t Idx = Rand(Size); 155326943Sdim Data[Idx] ^= 1 << Rand(8); 156326943Sdim return Size; 157326943Sdim} 158326943Sdim 159326943Sdimsize_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, 160326943Sdim size_t Size, 161326943Sdim size_t MaxSize) { 162326943Sdim return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); 163326943Sdim} 164326943Sdim 165326943Sdimsize_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, 166326943Sdim size_t MaxSize, 167326943Sdim DictionaryEntry &DE) { 168326943Sdim const Word &W = DE.GetW(); 169326943Sdim bool UsePositionHint = DE.HasPositionHint() && 170326943Sdim DE.GetPositionHint() + W.size() < Size && 171326943Sdim Rand.RandBool(); 172326943Sdim if (Rand.RandBool()) { // Insert W. 173326943Sdim if (Size + W.size() > MaxSize) return 0; 174326943Sdim size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); 175326943Sdim memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); 176326943Sdim memcpy(Data + Idx, W.data(), W.size()); 177326943Sdim Size += W.size(); 178326943Sdim } else { // Overwrite some bytes with W. 179326943Sdim if (W.size() > Size) return 0; 180326943Sdim size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size()); 181326943Sdim memcpy(Data + Idx, W.data(), W.size()); 182326943Sdim } 183326943Sdim return Size; 184326943Sdim} 185326943Sdim 186326943Sdim// Somewhere in the past we have observed a comparison instructions 187326943Sdim// with arguments Arg1 Arg2. This function tries to guess a dictionary 188326943Sdim// entry that will satisfy that comparison. 189326943Sdim// It first tries to find one of the arguments (possibly swapped) in the 190326943Sdim// input and if it succeeds it creates a DE with a position hint. 191326943Sdim// Otherwise it creates a DE with one of the arguments w/o a position hint. 192326943SdimDictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 193326943Sdim const void *Arg1, const void *Arg2, 194326943Sdim const void *Arg1Mutation, const void *Arg2Mutation, 195326943Sdim size_t ArgSize, const uint8_t *Data, 196326943Sdim size_t Size) { 197326943Sdim bool HandleFirst = Rand.RandBool(); 198326943Sdim const void *ExistingBytes, *DesiredBytes; 199326943Sdim Word W; 200326943Sdim const uint8_t *End = Data + Size; 201326943Sdim for (int Arg = 0; Arg < 2; Arg++) { 202326943Sdim ExistingBytes = HandleFirst ? Arg1 : Arg2; 203326943Sdim DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; 204326943Sdim HandleFirst = !HandleFirst; 205326943Sdim W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize); 206326943Sdim const size_t kMaxNumPositions = 8; 207326943Sdim size_t Positions[kMaxNumPositions]; 208326943Sdim size_t NumPositions = 0; 209326943Sdim for (const uint8_t *Cur = Data; 210326943Sdim Cur < End && NumPositions < kMaxNumPositions; Cur++) { 211326943Sdim Cur = 212326943Sdim (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); 213326943Sdim if (!Cur) break; 214326943Sdim Positions[NumPositions++] = Cur - Data; 215326943Sdim } 216326943Sdim if (!NumPositions) continue; 217326943Sdim return DictionaryEntry(W, Positions[Rand(NumPositions)]); 218326943Sdim } 219326943Sdim DictionaryEntry DE(W); 220326943Sdim return DE; 221326943Sdim} 222326943Sdim 223326943Sdim 224326943Sdimtemplate <class T> 225326943SdimDictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 226326943Sdim T Arg1, T Arg2, const uint8_t *Data, size_t Size) { 227326943Sdim if (Rand.RandBool()) Arg1 = Bswap(Arg1); 228326943Sdim if (Rand.RandBool()) Arg2 = Bswap(Arg2); 229326943Sdim T Arg1Mutation = Arg1 + Rand(-1, 1); 230326943Sdim T Arg2Mutation = Arg2 + Rand(-1, 1); 231326943Sdim return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, 232326943Sdim sizeof(Arg1), Data, Size); 233326943Sdim} 234326943Sdim 235326943SdimDictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 236326943Sdim const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) { 237326943Sdim return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(), 238326943Sdim Arg2.data(), Arg1.size(), Data, Size); 239326943Sdim} 240326943Sdim 241326943Sdimsize_t MutationDispatcher::Mutate_AddWordFromTORC( 242326943Sdim uint8_t *Data, size_t Size, size_t MaxSize) { 243326943Sdim Word W; 244326943Sdim DictionaryEntry DE; 245326943Sdim switch (Rand(4)) { 246326943Sdim case 0: { 247326943Sdim auto X = TPC.TORC8.Get(Rand.Rand()); 248326943Sdim DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 249326943Sdim } break; 250326943Sdim case 1: { 251326943Sdim auto X = TPC.TORC4.Get(Rand.Rand()); 252326943Sdim if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool()) 253326943Sdim DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size); 254326943Sdim else 255326943Sdim DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 256326943Sdim } break; 257326943Sdim case 2: { 258326943Sdim auto X = TPC.TORCW.Get(Rand.Rand()); 259326943Sdim DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 260326943Sdim } break; 261326943Sdim case 3: if (Options.UseMemmem) { 262326943Sdim auto X = TPC.MMT.Get(Rand.Rand()); 263326943Sdim DE = DictionaryEntry(X); 264326943Sdim } break; 265326943Sdim default: 266326943Sdim assert(0); 267326943Sdim } 268326943Sdim if (!DE.GetW().size()) return 0; 269326943Sdim Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 270326943Sdim if (!Size) return 0; 271326943Sdim DictionaryEntry &DERef = 272326943Sdim CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ % 273326943Sdim kCmpDictionaryEntriesDequeSize]; 274326943Sdim DERef = DE; 275326943Sdim CurrentDictionaryEntrySequence.push_back(&DERef); 276326943Sdim return Size; 277326943Sdim} 278326943Sdim 279326943Sdimsize_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( 280326943Sdim uint8_t *Data, size_t Size, size_t MaxSize) { 281326943Sdim return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); 282326943Sdim} 283326943Sdim 284326943Sdimsize_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, 285326943Sdim size_t Size, size_t MaxSize) { 286326943Sdim if (Size > MaxSize) return 0; 287326943Sdim if (D.empty()) return 0; 288326943Sdim DictionaryEntry &DE = D[Rand(D.size())]; 289326943Sdim Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 290326943Sdim if (!Size) return 0; 291326943Sdim DE.IncUseCount(); 292326943Sdim CurrentDictionaryEntrySequence.push_back(&DE); 293326943Sdim return Size; 294326943Sdim} 295326943Sdim 296326943Sdim// Overwrites part of To[0,ToSize) with a part of From[0,FromSize). 297326943Sdim// Returns ToSize. 298326943Sdimsize_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, 299326943Sdim uint8_t *To, size_t ToSize) { 300326943Sdim // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). 301326943Sdim size_t ToBeg = Rand(ToSize); 302326943Sdim size_t CopySize = Rand(ToSize - ToBeg) + 1; 303326943Sdim assert(ToBeg + CopySize <= ToSize); 304326943Sdim CopySize = std::min(CopySize, FromSize); 305326943Sdim size_t FromBeg = Rand(FromSize - CopySize + 1); 306326943Sdim assert(FromBeg + CopySize <= FromSize); 307326943Sdim memmove(To + ToBeg, From + FromBeg, CopySize); 308326943Sdim return ToSize; 309326943Sdim} 310326943Sdim 311326943Sdim// Inserts part of From[0,ToSize) into To. 312326943Sdim// Returns new size of To on success or 0 on failure. 313326943Sdimsize_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, 314326943Sdim uint8_t *To, size_t ToSize, 315326943Sdim size_t MaxToSize) { 316326943Sdim if (ToSize >= MaxToSize) return 0; 317326943Sdim size_t AvailableSpace = MaxToSize - ToSize; 318326943Sdim size_t MaxCopySize = std::min(AvailableSpace, FromSize); 319326943Sdim size_t CopySize = Rand(MaxCopySize) + 1; 320326943Sdim size_t FromBeg = Rand(FromSize - CopySize + 1); 321326943Sdim assert(FromBeg + CopySize <= FromSize); 322326943Sdim size_t ToInsertPos = Rand(ToSize + 1); 323326943Sdim assert(ToInsertPos + CopySize <= MaxToSize); 324326943Sdim size_t TailSize = ToSize - ToInsertPos; 325326943Sdim if (To == From) { 326326943Sdim MutateInPlaceHere.resize(MaxToSize); 327326943Sdim memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); 328326943Sdim memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 329326943Sdim memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); 330326943Sdim } else { 331326943Sdim memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 332326943Sdim memmove(To + ToInsertPos, From + FromBeg, CopySize); 333326943Sdim } 334326943Sdim return ToSize + CopySize; 335326943Sdim} 336326943Sdim 337326943Sdimsize_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, 338326943Sdim size_t MaxSize) { 339326943Sdim if (Size > MaxSize || Size == 0) return 0; 340336817Sdim // If Size == MaxSize, `InsertPartOf(...)` will 341336817Sdim // fail so there's no point using it in this case. 342336817Sdim if (Size == MaxSize || Rand.RandBool()) 343326943Sdim return CopyPartOf(Data, Size, Data, Size); 344326943Sdim else 345326943Sdim return InsertPartOf(Data, Size, Data, Size, MaxSize); 346326943Sdim} 347326943Sdim 348326943Sdimsize_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, 349326943Sdim size_t MaxSize) { 350326943Sdim if (Size > MaxSize) return 0; 351326943Sdim size_t B = Rand(Size); 352326943Sdim while (B < Size && !isdigit(Data[B])) B++; 353326943Sdim if (B == Size) return 0; 354326943Sdim size_t E = B; 355326943Sdim while (E < Size && isdigit(Data[E])) E++; 356326943Sdim assert(B < E); 357326943Sdim // now we have digits in [B, E). 358326943Sdim // strtol and friends don't accept non-zero-teminated data, parse it manually. 359326943Sdim uint64_t Val = Data[B] - '0'; 360326943Sdim for (size_t i = B + 1; i < E; i++) 361326943Sdim Val = Val * 10 + Data[i] - '0'; 362326943Sdim 363326943Sdim // Mutate the integer value. 364326943Sdim switch(Rand(5)) { 365326943Sdim case 0: Val++; break; 366326943Sdim case 1: Val--; break; 367326943Sdim case 2: Val /= 2; break; 368326943Sdim case 3: Val *= 2; break; 369326943Sdim case 4: Val = Rand(Val * Val); break; 370326943Sdim default: assert(0); 371326943Sdim } 372326943Sdim // Just replace the bytes with the new ones, don't bother moving bytes. 373326943Sdim for (size_t i = B; i < E; i++) { 374326943Sdim size_t Idx = E + B - i - 1; 375326943Sdim assert(Idx >= B && Idx < E); 376326943Sdim Data[Idx] = (Val % 10) + '0'; 377326943Sdim Val /= 10; 378326943Sdim } 379326943Sdim return Size; 380326943Sdim} 381326943Sdim 382326943Sdimtemplate<class T> 383326943Sdimsize_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { 384326943Sdim if (Size < sizeof(T)) return 0; 385326943Sdim size_t Off = Rand(Size - sizeof(T) + 1); 386326943Sdim assert(Off + sizeof(T) <= Size); 387326943Sdim T Val; 388326943Sdim if (Off < 64 && !Rand(4)) { 389326943Sdim Val = Size; 390326943Sdim if (Rand.RandBool()) 391326943Sdim Val = Bswap(Val); 392326943Sdim } else { 393326943Sdim memcpy(&Val, Data + Off, sizeof(Val)); 394326943Sdim T Add = Rand(21); 395326943Sdim Add -= 10; 396326943Sdim if (Rand.RandBool()) 397326943Sdim Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. 398326943Sdim else 399326943Sdim Val = Val + Add; // Add assuming current endiannes. 400326943Sdim if (Add == 0 || Rand.RandBool()) // Maybe negate. 401326943Sdim Val = -Val; 402326943Sdim } 403326943Sdim memcpy(Data + Off, &Val, sizeof(Val)); 404326943Sdim return Size; 405326943Sdim} 406326943Sdim 407326943Sdimsize_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, 408326943Sdim size_t Size, 409326943Sdim size_t MaxSize) { 410326943Sdim if (Size > MaxSize) return 0; 411326943Sdim switch (Rand(4)) { 412326943Sdim case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand); 413326943Sdim case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand); 414326943Sdim case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand); 415326943Sdim case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand); 416326943Sdim default: assert(0); 417326943Sdim } 418326943Sdim return 0; 419326943Sdim} 420326943Sdim 421326943Sdimsize_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, 422326943Sdim size_t MaxSize) { 423326943Sdim if (Size > MaxSize) return 0; 424353358Sdim if (Size == 0) return 0; 425353358Sdim if (!CrossOverWith) return 0; 426353358Sdim const Unit &O = *CrossOverWith; 427326943Sdim if (O.empty()) return 0; 428326943Sdim MutateInPlaceHere.resize(MaxSize); 429326943Sdim auto &U = MutateInPlaceHere; 430326943Sdim size_t NewSize = 0; 431326943Sdim switch(Rand(3)) { 432326943Sdim case 0: 433326943Sdim NewSize = CrossOver(Data, Size, O.data(), O.size(), U.data(), U.size()); 434326943Sdim break; 435326943Sdim case 1: 436326943Sdim NewSize = InsertPartOf(O.data(), O.size(), U.data(), U.size(), MaxSize); 437326943Sdim if (!NewSize) 438326943Sdim NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size()); 439326943Sdim break; 440326943Sdim case 2: 441326943Sdim NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size()); 442326943Sdim break; 443326943Sdim default: assert(0); 444326943Sdim } 445326943Sdim assert(NewSize > 0 && "CrossOver returned empty unit"); 446326943Sdim assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); 447326943Sdim memcpy(Data, U.data(), NewSize); 448326943Sdim return NewSize; 449326943Sdim} 450326943Sdim 451326943Sdimvoid MutationDispatcher::StartMutationSequence() { 452326943Sdim CurrentMutatorSequence.clear(); 453326943Sdim CurrentDictionaryEntrySequence.clear(); 454326943Sdim} 455326943Sdim 456326943Sdim// Copy successful dictionary entries to PersistentAutoDictionary. 457326943Sdimvoid MutationDispatcher::RecordSuccessfulMutationSequence() { 458326943Sdim for (auto DE : CurrentDictionaryEntrySequence) { 459326943Sdim // PersistentAutoDictionary.AddWithSuccessCountOne(DE); 460326943Sdim DE->IncSuccessCount(); 461326943Sdim assert(DE->GetW().size()); 462326943Sdim // Linear search is fine here as this happens seldom. 463326943Sdim if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) 464326943Sdim PersistentAutoDictionary.push_back({DE->GetW(), 1}); 465326943Sdim } 466326943Sdim} 467326943Sdim 468326943Sdimvoid MutationDispatcher::PrintRecommendedDictionary() { 469326943Sdim Vector<DictionaryEntry> V; 470326943Sdim for (auto &DE : PersistentAutoDictionary) 471326943Sdim if (!ManualDictionary.ContainsWord(DE.GetW())) 472326943Sdim V.push_back(DE); 473326943Sdim if (V.empty()) return; 474326943Sdim Printf("###### Recommended dictionary. ######\n"); 475326943Sdim for (auto &DE: V) { 476326943Sdim assert(DE.GetW().size()); 477326943Sdim Printf("\""); 478326943Sdim PrintASCII(DE.GetW(), "\""); 479326943Sdim Printf(" # Uses: %zd\n", DE.GetUseCount()); 480326943Sdim } 481326943Sdim Printf("###### End of recommended dictionary. ######\n"); 482326943Sdim} 483326943Sdim 484326943Sdimvoid MutationDispatcher::PrintMutationSequence() { 485326943Sdim Printf("MS: %zd ", CurrentMutatorSequence.size()); 486344779Sdim for (auto M : CurrentMutatorSequence) 487344779Sdim Printf("%s-", M.Name); 488326943Sdim if (!CurrentDictionaryEntrySequence.empty()) { 489326943Sdim Printf(" DE: "); 490326943Sdim for (auto DE : CurrentDictionaryEntrySequence) { 491326943Sdim Printf("\""); 492326943Sdim PrintASCII(DE->GetW(), "\"-"); 493326943Sdim } 494326943Sdim } 495326943Sdim} 496326943Sdim 497326943Sdimsize_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { 498326943Sdim return MutateImpl(Data, Size, MaxSize, Mutators); 499326943Sdim} 500326943Sdim 501326943Sdimsize_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, 502326943Sdim size_t MaxSize) { 503326943Sdim return MutateImpl(Data, Size, MaxSize, DefaultMutators); 504326943Sdim} 505326943Sdim 506326943Sdim// Mutates Data in place, returns new size. 507326943Sdimsize_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, 508326943Sdim size_t MaxSize, 509326943Sdim Vector<Mutator> &Mutators) { 510326943Sdim assert(MaxSize > 0); 511326943Sdim // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), 512326943Sdim // in which case they will return 0. 513326943Sdim // Try several times before returning un-mutated data. 514326943Sdim for (int Iter = 0; Iter < 100; Iter++) { 515344779Sdim auto M = Mutators[Rand(Mutators.size())]; 516344779Sdim size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); 517326943Sdim if (NewSize && NewSize <= MaxSize) { 518326943Sdim if (Options.OnlyASCII) 519326943Sdim ToASCII(Data, NewSize); 520326943Sdim CurrentMutatorSequence.push_back(M); 521326943Sdim return NewSize; 522326943Sdim } 523326943Sdim } 524326943Sdim *Data = ' '; 525326943Sdim return 1; // Fallback, should not happen frequently. 526326943Sdim} 527326943Sdim 528336817Sdim// Mask represents the set of Data bytes that are worth mutating. 529336817Sdimsize_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size, 530336817Sdim size_t MaxSize, 531336817Sdim const Vector<uint8_t> &Mask) { 532353358Sdim size_t MaskedSize = std::min(Size, Mask.size()); 533336817Sdim // * Copy the worthy bytes into a temporary array T 534336817Sdim // * Mutate T 535336817Sdim // * Copy T back. 536336817Sdim // This is totally unoptimized. 537336817Sdim auto &T = MutateWithMaskTemp; 538336817Sdim if (T.size() < Size) 539336817Sdim T.resize(Size); 540336817Sdim size_t OneBits = 0; 541353358Sdim for (size_t I = 0; I < MaskedSize; I++) 542336817Sdim if (Mask[I]) 543336817Sdim T[OneBits++] = Data[I]; 544336817Sdim 545353358Sdim if (!OneBits) return 0; 546336817Sdim assert(!T.empty()); 547336817Sdim size_t NewSize = Mutate(T.data(), OneBits, OneBits); 548336817Sdim assert(NewSize <= OneBits); 549336817Sdim (void)NewSize; 550336817Sdim // Even if NewSize < OneBits we still use all OneBits bytes. 551353358Sdim for (size_t I = 0, J = 0; I < MaskedSize; I++) 552336817Sdim if (Mask[I]) 553336817Sdim Data[I] = T[J++]; 554336817Sdim return Size; 555336817Sdim} 556336817Sdim 557326943Sdimvoid MutationDispatcher::AddWordToManualDictionary(const Word &W) { 558326943Sdim ManualDictionary.push_back( 559326943Sdim {W, std::numeric_limits<size_t>::max()}); 560326943Sdim} 561326943Sdim 562326943Sdim} // namespace fuzzer 563