10SN/A//===- FuzzerMutate.cpp - Mutate a test input -----------------------------===// 212260Sssadetsky// 30SN/A// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40SN/A// See https://llvm.org/LICENSE.txt for license information. 50SN/A// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60SN/A// 72362SN/A//===----------------------------------------------------------------------===// 80SN/A// Mutate a test input. 92362SN/A//===----------------------------------------------------------------------===// 100SN/A 110SN/A#include "FuzzerDefs.h" 120SN/A#include "FuzzerExtFunctions.h" 130SN/A#include "FuzzerIO.h" 140SN/A#include "FuzzerMutate.h" 150SN/A#include "FuzzerOptions.h" 160SN/A#include "FuzzerTracePC.h" 170SN/A 180SN/Anamespace fuzzer { 190SN/A 200SN/Aconst size_t Dictionary::kMaxDictSize; 212362SN/Astatic const size_t kMaxMutationsToPrint = 10; 222362SN/A 232362SN/Astatic void PrintASCII(const Word &W, const char *PrintAfter) { 240SN/A PrintASCII(W.data(), W.size(), PrintAfter); 250SN/A} 260SN/A 270SN/AMutationDispatcher::MutationDispatcher(Random &Rand, 281736SN/A const FuzzingOptions &Options) 291736SN/A : Rand(Rand), Options(Options) { 3015001Shschreiber DefaultMutators.insert( 310SN/A DefaultMutators.begin(), 320SN/A { 330SN/A {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"}, 340SN/A {&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, 350SN/A {&MutationDispatcher::Mutate_InsertRepeatedBytes, 361083SN/A "InsertRepeatedBytes"}, 370SN/A {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, 381736SN/A {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, 391083SN/A {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, 4011280Salexsch {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, 411083SN/A {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"}, 420SN/A {&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, 430SN/A {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, 449952SN/A {&MutationDispatcher::Mutate_AddWordFromManualDictionary, 450SN/A "ManualDict"}, 460SN/A {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, 470SN/A "PersAutoDict"}, 480SN/A }); 490SN/A if(Options.UseCmp) 500SN/A DefaultMutators.push_back( 510SN/A {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"}); 520SN/A 530SN/A if (EF->LLVMFuzzerCustomMutator) 540SN/A Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); 5510234SN/A else 560SN/A Mutators = DefaultMutators; 570SN/A 580SN/A if (EF->LLVMFuzzerCustomCrossOver) 599654SN/A Mutators.push_back( 600SN/A {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); 610SN/A} 620SN/A 631453SN/Astatic char RandCh(Random &Rand) { 641453SN/A if (Rand.RandBool()) 651453SN/A return static_cast<char>(Rand(256)); 661453SN/A const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; 671453SN/A return Special[Rand(sizeof(Special) - 1)]; 680SN/A} 690SN/A 701453SN/Asize_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, 711453SN/A size_t MaxSize) { 720SN/A if (EF->__msan_unpoison) 730SN/A EF->__msan_unpoison(Data, Size); 740SN/A if (EF->__msan_unpoison_param) 750SN/A EF->__msan_unpoison_param(4); 760SN/A return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, 770SN/A Rand.Rand<unsigned int>()); 780SN/A} 790SN/A 800SN/Asize_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, 810SN/A size_t MaxSize) { 821909SN/A if (Size == 0) 831909SN/A return 0; 841909SN/A if (!CrossOverWith) return 0; 851909SN/A const Unit &Other = *CrossOverWith; 861909SN/A if (Other.empty()) 871909SN/A return 0; 880SN/A CustomCrossOverInPlaceHere.resize(MaxSize); 890SN/A auto &U = CustomCrossOverInPlaceHere; 901453SN/A 911453SN/A if (EF->__msan_unpoison) { 920SN/A EF->__msan_unpoison(Data, Size); 930SN/A EF->__msan_unpoison(Other.data(), Other.size()); 940SN/A EF->__msan_unpoison(U.data(), U.size()); 950SN/A } 9612260Sssadetsky if (EF->__msan_unpoison_param) 970SN/A EF->__msan_unpoison_param(7); 980SN/A size_t NewSize = EF->LLVMFuzzerCustomCrossOver( 990SN/A Data, Size, Other.data(), Other.size(), U.data(), U.size(), 1000SN/A Rand.Rand<unsigned int>()); 1010SN/A 1020SN/A if (!NewSize) 1030SN/A return 0; 1040SN/A assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); 1050SN/A memcpy(Data, U.data(), NewSize); 1061736SN/A return NewSize; 1071736SN/A} 1081736SN/A 1091736SN/Asize_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, 1101736SN/A size_t MaxSize) { 1111736SN/A if (Size > MaxSize || Size == 0) return 0; 1121736SN/A size_t ShuffleAmount = 1131736SN/A Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. 1141736SN/A size_t ShuffleStart = Rand(Size - ShuffleAmount); 1151736SN/A assert(ShuffleStart + ShuffleAmount <= Size); 1161736SN/A std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand); 1171736SN/A return Size; 1181736SN/A} 1191736SN/A 12015001Shschreibersize_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, 12115001Shschreiber size_t MaxSize) { 12215001Shschreiber if (Size <= 1) return 0; 12315001Shschreiber size_t N = Rand(Size / 2) + 1; 12415001Shschreiber assert(N < Size); 12515001Shschreiber size_t Idx = Rand(Size - N + 1); 12615001Shschreiber // Erase Data[Idx:Idx+N]. 12715001Shschreiber memmove(Data + Idx, Data + Idx + N, Size - Idx - N); 1281736SN/A // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); 12915001Shschreiber return Size - N; 13015001Shschreiber} 13115001Shschreiber 13215001Shschreibersize_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, 1331736SN/A size_t MaxSize) { 13415001Shschreiber if (Size >= MaxSize) return 0; 1351736SN/A size_t Idx = Rand(Size + 1); 1361736SN/A // Insert new value at Data[Idx]. 1370SN/A memmove(Data + Idx + 1, Data + Idx, Size - Idx); 1380SN/A Data[Idx] = RandCh(Rand); 1390SN/A return Size + 1; 1400SN/A} 1410SN/A 1420SN/Asize_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, 1430SN/A size_t Size, 1440SN/A size_t MaxSize) { 1450SN/A const size_t kMinBytesToInsert = 3; 1460SN/A if (Size + kMinBytesToInsert >= MaxSize) return 0; 1470SN/A size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); 14810308SN/A size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; 14910308SN/A assert(Size + N <= MaxSize && N); 1500SN/A size_t Idx = Rand(Size + 1); 1511453SN/A // Insert new values at Data[Idx]. 1521453SN/A memmove(Data + Idx + N, Data + Idx, Size - Idx); 1531453SN/A // Give preference to 0x00 and 0xff. 1540SN/A uint8_t Byte = static_cast<uint8_t>( 1550SN/A Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255)); 1560SN/A for (size_t i = 0; i < N; i++) 1570SN/A Data[Idx + i] = Byte; 1580SN/A return Size + N; 1590SN/A} 1600SN/A 1610SN/Asize_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, 1620SN/A size_t MaxSize) { 16310308SN/A if (Size > MaxSize) return 0; 16410308SN/A size_t Idx = Rand(Size); 1650SN/A Data[Idx] = RandCh(Rand); 1661453SN/A return Size; 1671453SN/A} 1681453SN/A 1690SN/Asize_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, 1700SN/A size_t MaxSize) { 1710SN/A if (Size > MaxSize) return 0; 1720SN/A size_t Idx = Rand(Size); 1730SN/A Data[Idx] ^= 1 << Rand(8); 1740SN/A return Size; 1750SN/A} 1760SN/A 1770SN/Asize_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, 1780SN/A size_t Size, 1790SN/A size_t MaxSize) { 1800SN/A return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); 18110308SN/A} 18210308SN/A 1831453SN/Asize_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, 1841453SN/A size_t MaxSize, 1850SN/A DictionaryEntry &DE) { 1861453SN/A const Word &W = DE.GetW(); 1870SN/A bool UsePositionHint = DE.HasPositionHint() && 1880SN/A DE.GetPositionHint() + W.size() < Size && 1890SN/A Rand.RandBool(); 1900SN/A if (Rand.RandBool()) { // Insert W. 1910SN/A if (Size + W.size() > MaxSize) return 0; 1920SN/A size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); 1930SN/A memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); 1940SN/A memcpy(Data + Idx, W.data(), W.size()); 1950SN/A Size += W.size(); 19610308SN/A } else { // Overwrite some bytes with W. 19710308SN/A if (W.size() > Size) return 0; 1980SN/A size_t Idx = 1991453SN/A UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size()); 2001453SN/A memcpy(Data + Idx, W.data(), W.size()); 2011453SN/A } 2020SN/A return Size; 2030SN/A} 2040SN/A 2050SN/A// Somewhere in the past we have observed a comparison instructions 2060SN/A// with arguments Arg1 Arg2. This function tries to guess a dictionary 2070SN/A// entry that will satisfy that comparison. 2080SN/A// It first tries to find one of the arguments (possibly swapped) in the 2090SN/A// input and if it succeeds it creates a DE with a position hint. 2100SN/A// Otherwise it creates a DE with one of the arguments w/o a position hint. 2110SN/ADictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 2120SN/A const void *Arg1, const void *Arg2, 2130SN/A const void *Arg1Mutation, const void *Arg2Mutation, 2140SN/A size_t ArgSize, const uint8_t *Data, 2150SN/A size_t Size) { 2160SN/A bool HandleFirst = Rand.RandBool(); 2170SN/A const void *ExistingBytes, *DesiredBytes; 2180SN/A Word W; 2190SN/A const uint8_t *End = Data + Size; 2200SN/A for (int Arg = 0; Arg < 2; Arg++) { 22110308SN/A ExistingBytes = HandleFirst ? Arg1 : Arg2; 22210308SN/A DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; 2231453SN/A HandleFirst = !HandleFirst; 2241453SN/A W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize); 2250SN/A const size_t kMaxNumPositions = 8; 2261453SN/A size_t Positions[kMaxNumPositions]; 2270SN/A size_t NumPositions = 0; 2280SN/A for (const uint8_t *Cur = Data; 2290SN/A Cur < End && NumPositions < kMaxNumPositions; Cur++) { 2300SN/A Cur = 2310SN/A (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); 2320SN/A if (!Cur) break; 2330SN/A Positions[NumPositions++] = Cur - Data; 2340SN/A } 2350SN/A if (!NumPositions) continue; 23613629Savstepan return DictionaryEntry(W, Positions[Rand(NumPositions)]); 2370SN/A } 23813629Savstepan DictionaryEntry DE(W); 2390SN/A return DE; 24013629Savstepan} 2410SN/A 24213629Savstepan 2430SN/Atemplate <class T> 2440SN/ADictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 24513629Savstepan T Arg1, T Arg2, const uint8_t *Data, size_t Size) { 2460SN/A if (Rand.RandBool()) Arg1 = Bswap(Arg1); 2470SN/A if (Rand.RandBool()) Arg2 = Bswap(Arg2); 2480SN/A T Arg1Mutation = static_cast<T>(Arg1 + Rand(-1, 1)); 2491736SN/A T Arg2Mutation = static_cast<T>(Arg2 + Rand(-1, 1)); 25013629Savstepan return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, 2511736SN/A sizeof(Arg1), Data, Size); 2520SN/A} 25313629Savstepan 2540SN/ADictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( 2550SN/A const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) { 2560SN/A return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(), 2570SN/A Arg2.data(), Arg1.size(), Data, Size); 2580SN/A} 2590SN/A 2600SN/Asize_t MutationDispatcher::Mutate_AddWordFromTORC( 2610SN/A uint8_t *Data, size_t Size, size_t MaxSize) { 2620SN/A Word W; 26311280Salexsch DictionaryEntry DE; 2640SN/A switch (Rand(4)) { 2650SN/A case 0: { 2660SN/A auto X = TPC.TORC8.Get(Rand.Rand<size_t>()); 2670SN/A DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 2680SN/A } break; 2690SN/A case 1: { 2700SN/A auto X = TPC.TORC4.Get(Rand.Rand<size_t>()); 2710SN/A if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool()) 2720SN/A DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size); 2730SN/A else 27411280Salexsch DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 2750SN/A } break; 2760SN/A case 2: { 2770SN/A auto X = TPC.TORCW.Get(Rand.Rand<size_t>()); 27811280Salexsch DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); 2790SN/A } break; 2800SN/A case 3: if (Options.UseMemmem) { 2810SN/A auto X = TPC.MMT.Get(Rand.Rand<size_t>()); 2820SN/A DE = DictionaryEntry(X); 2830SN/A } break; 2840SN/A default: 2850SN/A assert(0); 2860SN/A } 2870SN/A if (!DE.GetW().size()) return 0; 2880SN/A Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 28911290Salexsch if (!Size) return 0; 2900SN/A DictionaryEntry &DERef = 2910SN/A CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ % 2920SN/A kCmpDictionaryEntriesDequeSize]; 2931905SN/A DERef = DE; 2940SN/A CurrentDictionaryEntrySequence.push_back(&DERef); 2950SN/A return Size; 2960SN/A} 29711290Salexsch 298344SN/Asize_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( 299344SN/A uint8_t *Data, size_t Size, size_t MaxSize) { 300344SN/A return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); 301344SN/A} 302344SN/A 3030SN/Asize_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, 3040SN/A size_t Size, size_t MaxSize) { 3050SN/A if (Size > MaxSize) return 0; 3060SN/A if (D.empty()) return 0; 30711280Salexsch DictionaryEntry &DE = D[Rand(D.size())]; 3080SN/A Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); 3090SN/A if (!Size) return 0; 3100SN/A DE.IncUseCount(); 3110SN/A CurrentDictionaryEntrySequence.push_back(&DE); 3120SN/A return Size; 3130SN/A} 3140SN/A 3150SN/A// Overwrites part of To[0,ToSize) with a part of From[0,FromSize). 3160SN/A// Returns ToSize. 3170SN/Asize_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, 3180SN/A uint8_t *To, size_t ToSize) { 3190SN/A // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). 3200SN/A size_t ToBeg = Rand(ToSize); 3210SN/A size_t CopySize = Rand(ToSize - ToBeg) + 1; 3220SN/A assert(ToBeg + CopySize <= ToSize); 3230SN/A CopySize = std::min(CopySize, FromSize); 3240SN/A size_t FromBeg = Rand(FromSize - CopySize + 1); 3250SN/A assert(FromBeg + CopySize <= FromSize); 3260SN/A memmove(To + ToBeg, From + FromBeg, CopySize); 3270SN/A return ToSize; 3281453SN/A} 3291453SN/A 3301453SN/A// Inserts part of From[0,ToSize) into To. 3310SN/A// Returns new size of To on success or 0 on failure. 3320SN/Asize_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, 3330SN/A uint8_t *To, size_t ToSize, 3340SN/A size_t MaxToSize) { 3350SN/A if (ToSize >= MaxToSize) return 0; 3360SN/A size_t AvailableSpace = MaxToSize - ToSize; 3370SN/A size_t MaxCopySize = std::min(AvailableSpace, FromSize); 3380SN/A size_t CopySize = Rand(MaxCopySize) + 1; 3390SN/A size_t FromBeg = Rand(FromSize - CopySize + 1); 3400SN/A assert(FromBeg + CopySize <= FromSize); 3410SN/A size_t ToInsertPos = Rand(ToSize + 1); 3420SN/A assert(ToInsertPos + CopySize <= MaxToSize); 3430SN/A size_t TailSize = ToSize - ToInsertPos; 34411280Salexsch if (To == From) { 3450SN/A MutateInPlaceHere.resize(MaxToSize); 3461736SN/A memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); 3471736SN/A memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 3481736SN/A memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); 3491736SN/A } else { 3501736SN/A memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); 3511736SN/A memmove(To + ToInsertPos, From + FromBeg, CopySize); 3521736SN/A } 3531736SN/A return ToSize + CopySize; 3541736SN/A} 3551736SN/A 3561736SN/Asize_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, 3571736SN/A size_t MaxSize) { 3581736SN/A if (Size > MaxSize || Size == 0) return 0; 3591736SN/A // If Size == MaxSize, `InsertPartOf(...)` will 3600SN/A // fail so there's no point using it in this case. 3611736SN/A if (Size == MaxSize || Rand.RandBool()) 3621736SN/A return CopyPartOf(Data, Size, Data, Size); 3630SN/A else 3640SN/A return InsertPartOf(Data, Size, Data, Size, MaxSize); 3650SN/A} 3660SN/A 3670SN/Asize_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, 3680SN/A size_t MaxSize) { 3690SN/A if (Size > MaxSize) return 0; 3700SN/A size_t B = Rand(Size); 3710SN/A while (B < Size && !isdigit(Data[B])) B++; 3720SN/A if (B == Size) return 0; 3730SN/A size_t E = B; 3740SN/A while (E < Size && isdigit(Data[E])) E++; 3750SN/A assert(B < E); 3760SN/A // now we have digits in [B, E). 377231SN/A // strtol and friends don't accept non-zero-teminated data, parse it manually. 378231SN/A uint64_t Val = Data[B] - '0'; 3790SN/A for (size_t i = B + 1; i < E; i++) 380231SN/A Val = Val * 10 + Data[i] - '0'; 3810SN/A 382231SN/A // Mutate the integer value. 3830SN/A switch(Rand(5)) { 3840SN/A case 0: Val++; break; 3850SN/A case 1: Val--; break; 3860SN/A case 2: Val /= 2; break; 3870SN/A case 3: Val *= 2; break; 3880SN/A case 4: Val = Rand(Val * Val); break; 3890SN/A default: assert(0); 39011280Salexsch } 39111280Salexsch // Just replace the bytes with the new ones, don't bother moving bytes. 39211280Salexsch for (size_t i = B; i < E; i++) { 39311280Salexsch size_t Idx = E + B - i - 1; 39411280Salexsch assert(Idx >= B && Idx < E); 39511280Salexsch Data[Idx] = (Val % 10) + '0'; 39611280Salexsch Val /= 10; 39711280Salexsch } 39811280Salexsch return Size; 39911280Salexsch} 40011280Salexsch 40111280Salexschtemplate<class T> 40211280Salexschsize_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { 40311280Salexsch if (Size < sizeof(T)) return 0; 40411280Salexsch size_t Off = Rand(Size - sizeof(T) + 1); 40511280Salexsch assert(Off + sizeof(T) <= Size); 40611280Salexsch T Val; 40711280Salexsch if (Off < 64 && !Rand(4)) { 40811280Salexsch Val = static_cast<T>(Size); 40911280Salexsch if (Rand.RandBool()) 41011280Salexsch Val = Bswap(Val); 41111280Salexsch } else { 41211280Salexsch memcpy(&Val, Data + Off, sizeof(Val)); 41311280Salexsch T Add = static_cast<T>(Rand(21)); 41411280Salexsch Add -= 10; 41511280Salexsch if (Rand.RandBool()) 41611280Salexsch Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. 41711280Salexsch else 41811280Salexsch Val = Val + Add; // Add assuming current endiannes. 41911280Salexsch if (Add == 0 || Rand.RandBool()) // Maybe negate. 42011280Salexsch Val = -Val; 42111280Salexsch } 42211280Salexsch memcpy(Data + Off, &Val, sizeof(Val)); 42311280Salexsch return Size; 42411280Salexsch} 4250SN/A 42613629Savstepansize_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, 4270SN/A size_t Size, 4280SN/A size_t MaxSize) { 4291560SN/A if (Size > MaxSize) return 0; 4300SN/A switch (Rand(4)) { 4310SN/A case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand); 4320SN/A case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand); 4331560SN/A case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand); 4341560SN/A case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand); 4351560SN/A default: assert(0); 4361560SN/A } 4371560SN/A return 0; 4381560SN/A} 4390SN/A 4400SN/Asize_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, 4410SN/A size_t MaxSize) { 4420SN/A if (Size > MaxSize) return 0; 4430SN/A if (Size == 0) return 0; 4440SN/A if (!CrossOverWith) return 0; 4450SN/A const Unit &O = *CrossOverWith; 4460SN/A if (O.empty()) return 0; 4470SN/A size_t NewSize = 0; 4480SN/A switch(Rand(3)) { 4490SN/A case 0: 4500SN/A MutateInPlaceHere.resize(MaxSize); 4510SN/A NewSize = CrossOver(Data, Size, O.data(), O.size(), 4520SN/A MutateInPlaceHere.data(), MaxSize); 4530SN/A memcpy(Data, MutateInPlaceHere.data(), NewSize); 4540SN/A break; 4550SN/A case 1: 4560SN/A NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize); 4570SN/A if (!NewSize) 4580SN/A NewSize = CopyPartOf(O.data(), O.size(), Data, Size); 4592332SN/A break; 4602332SN/A case 2: 4612332SN/A NewSize = CopyPartOf(O.data(), O.size(), Data, Size); 4622332SN/A break; 4632332SN/A default: assert(0); 4642332SN/A } 4652332SN/A assert(NewSize > 0 && "CrossOver returned empty unit"); 4662332SN/A assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); 4670SN/A return NewSize; 4680SN/A} 4690SN/A 4700SN/Avoid MutationDispatcher::StartMutationSequence() { 47110217SN/A CurrentMutatorSequence.clear(); 4720SN/A CurrentDictionaryEntrySequence.clear(); 4730SN/A} 4740SN/A 4750SN/A// Copy successful dictionary entries to PersistentAutoDictionary. 4760SN/Avoid MutationDispatcher::RecordSuccessfulMutationSequence() { 4770SN/A for (auto DE : CurrentDictionaryEntrySequence) { 47810217SN/A // PersistentAutoDictionary.AddWithSuccessCountOne(DE); 4790SN/A DE->IncSuccessCount(); 4800SN/A assert(DE->GetW().size()); 4810SN/A // Linear search is fine here as this happens seldom. 4820SN/A if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) 4830SN/A PersistentAutoDictionary.push_back(*DE); 4840SN/A } 4850SN/A} 4860SN/A 4870SN/Avoid MutationDispatcher::PrintRecommendedDictionary() { 4880SN/A std::vector<DictionaryEntry> V; 4890SN/A for (auto &DE : PersistentAutoDictionary) 4900SN/A if (!ManualDictionary.ContainsWord(DE.GetW())) 4910SN/A V.push_back(DE); 4920SN/A if (V.empty()) return; 4930SN/A Printf("###### Recommended dictionary. ######\n"); 4940SN/A for (auto &DE: V) { 4950SN/A assert(DE.GetW().size()); 4960SN/A Printf("\""); 4970SN/A PrintASCII(DE.GetW(), "\""); 4980SN/A Printf(" # Uses: %zd\n", DE.GetUseCount()); 4990SN/A } 5000SN/A Printf("###### End of recommended dictionary. ######\n"); 5010SN/A} 5020SN/A 5030SN/Avoid MutationDispatcher::PrintMutationSequence(bool Verbose) { 5040SN/A Printf("MS: %zd ", CurrentMutatorSequence.size()); 5050SN/A size_t EntriesToPrint = 5060SN/A Verbose ? CurrentMutatorSequence.size() 5070SN/A : std::min(kMaxMutationsToPrint, CurrentMutatorSequence.size()); 508344SN/A for (size_t i = 0; i < EntriesToPrint; i++) 5090SN/A Printf("%s-", CurrentMutatorSequence[i].Name); 5100SN/A if (!CurrentDictionaryEntrySequence.empty()) { 5110SN/A Printf(" DE: "); 5120SN/A EntriesToPrint = Verbose ? CurrentDictionaryEntrySequence.size() 5130SN/A : std::min(kMaxMutationsToPrint, 5140SN/A CurrentDictionaryEntrySequence.size()); 5150SN/A for (size_t i = 0; i < EntriesToPrint; i++) { 5160SN/A Printf("\""); 5171083SN/A PrintASCII(CurrentDictionaryEntrySequence[i]->GetW(), "\"-"); 5181083SN/A } 5191083SN/A } 5201083SN/A} 5211083SN/A 5221083SN/Astd::string MutationDispatcher::MutationSequence() { 5231083SN/A std::string MS; 5241083SN/A for (const auto &M : CurrentMutatorSequence) { 5251083SN/A MS += M.Name; 5261083SN/A MS += "-"; 52711779Sserb } 5281083SN/A return MS; 5291083SN/A} 53011779Sserb 53111779Sserbsize_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { 53211779Sserb return MutateImpl(Data, Size, MaxSize, Mutators); 53311779Sserb} 53411779Sserb 53514222Sprrsize_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, 53614222Sprr size_t MaxSize) { 53714222Sprr return MutateImpl(Data, Size, MaxSize, DefaultMutators); 53811779Sserb} 53911779Sserb 5401083SN/A// Mutates Data in place, returns new size. 5411083SN/Asize_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, 5421083SN/A size_t MaxSize, 5431083SN/A std::vector<Mutator> &Mutators) { 5441083SN/A assert(MaxSize > 0); 5451083SN/A // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), 5461083SN/A // in which case they will return 0. 5471083SN/A // Try several times before returning un-mutated data. 5481083SN/A for (int Iter = 0; Iter < 100; Iter++) { 5491083SN/A auto M = Mutators[Rand(Mutators.size())]; 5501083SN/A size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); 5511083SN/A if (NewSize && NewSize <= MaxSize) { 5521083SN/A if (Options.OnlyASCII) 5531083SN/A ToASCII(Data, NewSize); 55411779Sserb CurrentMutatorSequence.push_back(M); 55511779Sserb return NewSize; 55612334Sserb } 55712334Sserb } 55812334Sserb *Data = ' '; 55912334Sserb return 1; // Fallback, should not happen frequently. 56014222Sprr} 56114222Sprr 56214222Sprr// Mask represents the set of Data bytes that are worth mutating. 56311779Sserbsize_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size, 56411779Sserb size_t MaxSize, 56511779Sserb const std::vector<uint8_t> &Mask) { 5661083SN/A size_t MaskedSize = std::min(Size, Mask.size()); 5671083SN/A // * Copy the worthy bytes into a temporary array T 5681083SN/A // * Mutate T 5691453SN/A // * Copy T back. 5701453SN/A // This is totally unoptimized. 5711453SN/A auto &T = MutateWithMaskTemp; 5721453SN/A if (T.size() < Size) 5731453SN/A T.resize(Size); 5741453SN/A size_t OneBits = 0; 5751560SN/A for (size_t I = 0; I < MaskedSize; I++) 5761453SN/A if (Mask[I]) 5771453SN/A T[OneBits++] = Data[I]; 5781453SN/A 5791453SN/A if (!OneBits) return 0; 5801453SN/A assert(!T.empty()); 5811453SN/A size_t NewSize = Mutate(T.data(), OneBits, OneBits); 5821231SN/A assert(NewSize <= OneBits); 5831453SN/A (void)NewSize; 5841453SN/A // Even if NewSize < OneBits we still use all OneBits bytes. 5851453SN/A for (size_t I = 0, J = 0; I < MaskedSize; I++) 5861560SN/A if (Mask[I]) 5871560SN/A Data[I] = T[J++]; 5881560SN/A return Size; 5891560SN/A} 5901560SN/A 5911560SN/Avoid MutationDispatcher::AddWordToManualDictionary(const Word &W) { 5921560SN/A ManualDictionary.push_back( 5931453SN/A {W, std::numeric_limits<size_t>::max()}); 5941453SN/A} 5951453SN/A 5961453SN/A} // namespace fuzzer 5971453SN/A