Index: compiler-rt/lib/fuzzer/CMakeLists.txt =================================================================== --- compiler-rt/lib/fuzzer/CMakeLists.txt +++ compiler-rt/lib/fuzzer/CMakeLists.txt @@ -1,5 +1,4 @@ set(LIBFUZZER_SOURCES - FuzzerCrossOver.cpp FuzzerDataFlowTrace.cpp FuzzerDriver.cpp FuzzerExtFunctionsDlsym.cpp @@ -29,7 +28,6 @@ FuzzerCorpus.h FuzzerDataFlowTrace.h FuzzerDefs.h - FuzzerDictionary.h FuzzerExtFunctions.def FuzzerExtFunctions.h FuzzerFlags.def @@ -84,6 +82,32 @@ endif() endif() +macro(partially_link_libcxx name dir arch) + if(${arch} MATCHES "i386") + set(EMULATION_ARGUMENT "-m" "elf_i386") + else() + set(EMULATION_ARGUMENT "") + endif() + set(cxx_${arch}_merge_dir "${CMAKE_CURRENT_BINARY_DIR}/cxx_${arch}_merge.dir") + file(MAKE_DIRECTORY ${cxx_${arch}_merge_dir}) + add_custom_command(TARGET clang_rt.${name}-${arch} POST_BUILD + COMMAND ${CMAKE_LINKER} ${EMULATION_ARGUMENT} --whole-archive "$" --no-whole-archive ${dir}/lib/libc++.a -r -o ${name}.o + COMMAND ${CMAKE_OBJCOPY} --localize-hidden ${name}.o + COMMAND ${CMAKE_COMMAND} -E remove "$" + COMMAND ${CMAKE_AR} qcs "$" ${name}.o + WORKING_DIRECTORY ${cxx_${arch}_merge_dir} + ) +endmacro() + +add_subdirectory(mutagen) +foreach(X IN LISTS LIBFUZZER_MUTAGEN_SOURCES) + list(APPEND LIBFUZZER_SOURCES "mutagen/${X}") +endforeach() +foreach(X IN LISTS LIBFUZZER_MUTAGEN_HEADERS) + list(APPEND LIBFUZZER_HEADERS "mutagen/${X}") +endforeach() +include_directories(.) + add_compiler_rt_component(fuzzer) add_compiler_rt_object_libraries(RTfuzzer @@ -135,23 +159,6 @@ if(OS_NAME MATCHES "Linux|Fuchsia" AND COMPILER_RT_LIBCXX_PATH AND COMPILER_RT_LIBCXXABI_PATH) - macro(partially_link_libcxx name dir arch) - if(${arch} MATCHES "i386") - set(EMULATION_ARGUMENT "-m" "elf_i386") - else() - set(EMULATION_ARGUMENT "") - endif() - set(cxx_${arch}_merge_dir "${CMAKE_CURRENT_BINARY_DIR}/cxx_${arch}_merge.dir") - file(MAKE_DIRECTORY ${cxx_${arch}_merge_dir}) - add_custom_command(TARGET clang_rt.${name}-${arch} POST_BUILD - COMMAND ${CMAKE_LINKER} ${EMULATION_ARGUMENT} --whole-archive "$" --no-whole-archive ${dir}/lib/libc++.a -r -o ${name}.o - COMMAND ${CMAKE_OBJCOPY} --localize-hidden ${name}.o - COMMAND ${CMAKE_COMMAND} -E remove "$" - COMMAND ${CMAKE_AR} qcs "$" ${name}.o - WORKING_DIRECTORY ${cxx_${arch}_merge_dir} - ) - endmacro() - foreach(arch ${FUZZER_SUPPORTED_ARCH}) get_target_flags_for_arch(${arch} TARGET_CFLAGS) set(LIBCXX_${arch}_PREFIX ${CMAKE_CURRENT_BINARY_DIR}/libcxx_fuzzer_${arch}) Index: compiler-rt/lib/fuzzer/FuzzerDefs.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerDefs.h +++ compiler-rt/lib/fuzzer/FuzzerDefs.h @@ -15,21 +15,18 @@ #include #include #include +#include #include #include #include #include - namespace fuzzer { template T Min(T a, T b) { return a < b ? a : b; } template T Max(T a, T b) { return a > b ? a : b; } class Random; -class Dictionary; -class DictionaryEntry; -class MutationDispatcher; struct FuzzingOptions; class InputCorpus; struct InputInfo; @@ -60,6 +57,37 @@ typedef Vector Unit; typedef Vector UnitVector; + +// A simple POD sized array of bytes. +template class FixedWord { +public: + static const size_t kMaxSize = kMaxSizeT; + FixedWord() { memset(Data, 0, kMaxSize); } + FixedWord(const uint8_t *B, size_t S) { Set(B, S); } + + void Set(const uint8_t *B, size_t S) { + static_assert(kMaxSizeT <= std::numeric_limits::max(), + "FixedWord::kMaxSizeT cannot fit in a uint8_t."); + assert(S <= kMaxSize); + memcpy(Data, B, S); + Size = static_cast(S); + } + + bool operator==(const FixedWord &w) const { + return Size == w.Size && 0 == memcmp(Data, w.Data, Size); + } + + static size_t GetMaxSize() { return kMaxSize; } + const uint8_t *data() const { return Data; } + uint8_t size() const { return Size; } + +private: + uint8_t Size = 0; + uint8_t Data[kMaxSize]; +}; + +typedef FixedWord<64> Word; + typedef int (*UserCallback)(const uint8_t *Data, size_t Size); int FuzzerDriver(int *argc, char ***argv, UserCallback Callback); Index: compiler-rt/lib/fuzzer/FuzzerDictionary.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerDictionary.h +++ /dev/null @@ -1,120 +0,0 @@ -//===- FuzzerDictionary.h - Internal header for the Fuzzer ------*- C++ -* ===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// fuzzer::Dictionary -//===----------------------------------------------------------------------===// - -#ifndef LLVM_FUZZER_DICTIONARY_H -#define LLVM_FUZZER_DICTIONARY_H - -#include "FuzzerDefs.h" -#include "FuzzerIO.h" -#include "FuzzerUtil.h" -#include -#include - -namespace fuzzer { -// A simple POD sized array of bytes. -template class FixedWord { -public: - static const size_t kMaxSize = kMaxSizeT; - FixedWord() {} - FixedWord(const uint8_t *B, size_t S) { Set(B, S); } - - void Set(const uint8_t *B, size_t S) { - static_assert(kMaxSizeT <= std::numeric_limits::max(), - "FixedWord::kMaxSizeT cannot fit in a uint8_t."); - assert(S <= kMaxSize); - memcpy(Data, B, S); - Size = static_cast(S); - } - - bool operator==(const FixedWord &w) const { - return Size == w.Size && 0 == memcmp(Data, w.Data, Size); - } - - static size_t GetMaxSize() { return kMaxSize; } - const uint8_t *data() const { return Data; } - uint8_t size() const { return Size; } - -private: - uint8_t Size = 0; - uint8_t Data[kMaxSize]; -}; - -typedef FixedWord<64> Word; - -class DictionaryEntry { - public: - DictionaryEntry() {} - DictionaryEntry(Word W) : W(W) {} - DictionaryEntry(Word W, size_t PositionHint) : W(W), PositionHint(PositionHint) {} - const Word &GetW() const { return W; } - - bool HasPositionHint() const { return PositionHint != std::numeric_limits::max(); } - size_t GetPositionHint() const { - assert(HasPositionHint()); - return PositionHint; - } - void IncUseCount() { UseCount++; } - void IncSuccessCount() { SuccessCount++; } - size_t GetUseCount() const { return UseCount; } - size_t GetSuccessCount() const {return SuccessCount; } - - void Print(const char *PrintAfter = "\n") { - PrintASCII(W.data(), W.size()); - if (HasPositionHint()) - Printf("@%zd", GetPositionHint()); - Printf("%s", PrintAfter); - } - -private: - Word W; - size_t PositionHint = std::numeric_limits::max(); - size_t UseCount = 0; - size_t SuccessCount = 0; -}; - -class Dictionary { - public: - static const size_t kMaxDictSize = 1 << 14; - - bool ContainsWord(const Word &W) const { - return std::any_of(begin(), end(), [&](const DictionaryEntry &DE) { - return DE.GetW() == W; - }); - } - const DictionaryEntry *begin() const { return &DE[0]; } - const DictionaryEntry *end() const { return begin() + Size; } - DictionaryEntry & operator[] (size_t Idx) { - assert(Idx < Size); - return DE[Idx]; - } - void push_back(DictionaryEntry DE) { - if (Size < kMaxDictSize) - this->DE[Size++] = DE; - } - void clear() { Size = 0; } - bool empty() const { return Size == 0; } - size_t size() const { return Size; } - -private: - DictionaryEntry DE[kMaxDictSize]; - size_t Size = 0; -}; - -// Parses one dictionary entry. -// If successful, write the enty to Unit and returns true, -// otherwise returns false. -bool ParseOneDictionaryEntry(const std::string &Str, Unit *U); -// Parses the dictionary file, fills Units, returns true iff all lines -// were parsed successfully. -bool ParseDictionaryFile(const std::string &Text, Vector *Units); - -} // namespace fuzzer - -#endif // LLVM_FUZZER_DICTIONARY_H Index: compiler-rt/lib/fuzzer/FuzzerDriver.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerDriver.cpp +++ compiler-rt/lib/fuzzer/FuzzerDriver.cpp @@ -19,15 +19,16 @@ #include "FuzzerPlatform.h" #include "FuzzerRandom.h" #include "FuzzerTracePC.h" +#include "mutagen/MutagenDispatcher.h" #include #include #include #include #include +#include #include #include #include -#include // This function should be present in the libFuzzer so that the client // binary can test for its existence. @@ -803,8 +804,9 @@ ReadCorpora(*Inputs, {})); } - Random Rand(Seed); - auto *MD = new MutationDispatcher(Rand, Options); + LLVMMutagenConfiguration Config; + ConfigureMutagen(Seed, Options, &Config); + auto *MD = new MutationDispatcher(&Config); auto *Corpus = new InputCorpus(Options.OutputCorpus, Entropic); auto *F = new Fuzzer(Callback, *Corpus, *MD, Options); Index: compiler-rt/lib/fuzzer/FuzzerInternal.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerInternal.h +++ compiler-rt/lib/fuzzer/FuzzerInternal.h @@ -18,6 +18,7 @@ #include "FuzzerOptions.h" #include "FuzzerSHA1.h" #include "FuzzerValueBitMap.h" +#include "mutagen/MutagenDispatcher.h" #include #include #include @@ -26,8 +27,12 @@ #include namespace fuzzer { +namespace { using namespace std::chrono; +using mutagen::MutationDispatcher; + +} // namespace class Fuzzer { public: Index: compiler-rt/lib/fuzzer/FuzzerLoop.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerLoop.cpp +++ compiler-rt/lib/fuzzer/FuzzerLoop.cpp @@ -177,7 +177,7 @@ if (!CurrentUnitData) return; // Happens when running individual inputs. ScopedDisableMsanInterceptorChecks S; - MD.PrintMutationSequence(); + PrintMutationSequence(MD); Printf("; base unit: %s\n", Sha1ToString(BaseSha1).c_str()); size_t UnitSize = CurrentUnitSize; if (UnitSize <= kMaxUnitSizeToPrint) { @@ -539,8 +539,9 @@ TimeOfUnit, UniqFeatureSetTmp, DFT, II); WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1), NewII->UniqFeatureSet); + const auto &MS = MD.MutationSequence(); WriteEdgeToMutationGraphFile(Options.MutationGraphFile, NewII, II, - MD.MutationSequence()); + MS.GetString()); return true; } if (II && FoundUniqFeaturesOfII && @@ -652,7 +653,7 @@ PrintStats(Text, ""); if (Options.Verbosity) { Printf(" L: %zd/%zd ", U.size(), Corpus.MaxInputSize()); - MD.PrintMutationSequence(Options.Verbosity >= 2); + PrintMutationSequence(MD, Options.Verbosity >= 2); Printf("\n"); } } @@ -898,7 +899,7 @@ } PrintStats("DONE ", "\n"); - MD.PrintRecommendedDictionary(); + PrintRecommendedDictionary(MD); } void Fuzzer::MinimizeCrashLoop(const Unit &U) { Index: compiler-rt/lib/fuzzer/FuzzerMutate.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerMutate.h +++ compiler-rt/lib/fuzzer/FuzzerMutate.h @@ -11,145 +11,23 @@ #ifndef LLVM_FUZZER_MUTATE_H #define LLVM_FUZZER_MUTATE_H -#include "FuzzerDefs.h" -#include "FuzzerDictionary.h" #include "FuzzerOptions.h" -#include "FuzzerRandom.h" +#include "mutagen/Mutagen.h" +#include "mutagen/MutagenDispatcher.h" namespace fuzzer { +namespace { -class MutationDispatcher { -public: - MutationDispatcher(Random &Rand, const FuzzingOptions &Options); - ~MutationDispatcher() {} - /// Indicate that we are about to start a new sequence of mutations. - void StartMutationSequence(); - /// Print the current sequence of mutations. Only prints the full sequence - /// when Verbose is true. - void PrintMutationSequence(bool Verbose = true); - /// Return the current sequence of mutations. - std::string MutationSequence(); - /// Indicate that the current sequence of mutations was successful. - void RecordSuccessfulMutationSequence(); - /// Mutates data by invoking user-provided mutator. - size_t Mutate_Custom(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by invoking user-provided crossover. - size_t Mutate_CustomCrossOver(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by shuffling bytes. - size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by erasing bytes. - size_t Mutate_EraseBytes(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by inserting a byte. - size_t Mutate_InsertByte(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by inserting several repeated bytes. - size_t Mutate_InsertRepeatedBytes(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by changing one byte. - size_t Mutate_ChangeByte(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by changing one bit. - size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize); - /// Mutates data by copying/inserting a part of data into a different place. - size_t Mutate_CopyPart(uint8_t *Data, size_t Size, size_t MaxSize); +using mutagen::MutationDispatcher; - /// Mutates data by adding a word from the manual dictionary. - size_t Mutate_AddWordFromManualDictionary(uint8_t *Data, size_t Size, - size_t MaxSize); +} // namespace - /// Mutates data by adding a word from the TORC. - size_t Mutate_AddWordFromTORC(uint8_t *Data, size_t Size, size_t MaxSize); +void ConfigureMutagen(unsigned int Seed, const FuzzingOptions &Options, + LLVMMutagenConfiguration *OutConfig); - /// Mutates data by adding a word from the persistent automatic dictionary. - size_t Mutate_AddWordFromPersistentAutoDictionary(uint8_t *Data, size_t Size, - size_t MaxSize); +void PrintRecommendedDictionary(MutationDispatcher &MD); - /// Tries to find an ASCII integer in Data, changes it to another ASCII int. - size_t Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, size_t MaxSize); - /// Change a 1-, 2-, 4-, or 8-byte integer in interesting ways. - size_t Mutate_ChangeBinaryInteger(uint8_t *Data, size_t Size, size_t MaxSize); - - /// CrossOver Data with CrossOverWith. - size_t Mutate_CrossOver(uint8_t *Data, size_t Size, size_t MaxSize); - - /// Applies one of the configured mutations. - /// Returns the new size of data which could be up to MaxSize. - size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize); - - /// Applies one of the configured mutations to the bytes of Data - /// that have '1' in Mask. - /// Mask.size() should be >= Size. - size_t MutateWithMask(uint8_t *Data, size_t Size, size_t MaxSize, - const Vector &Mask); - - /// Applies one of the default mutations. Provided as a service - /// to mutation authors. - size_t DefaultMutate(uint8_t *Data, size_t Size, size_t MaxSize); - - /// Creates a cross-over of two pieces of Data, returns its size. - size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2, - size_t Size2, uint8_t *Out, size_t MaxOutSize); - - void AddWordToManualDictionary(const Word &W); - - void PrintRecommendedDictionary(); - - void SetCrossOverWith(const Unit *U) { CrossOverWith = U; } - - Random &GetRand() { return Rand; } - - private: - struct Mutator { - size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max); - const char *Name; - }; - - size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size, - size_t MaxSize); - size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize, - Vector &Mutators); - - size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To, - size_t ToSize, size_t MaxToSize); - size_t CopyPartOf(const uint8_t *From, size_t FromSize, uint8_t *To, - size_t ToSize); - size_t ApplyDictionaryEntry(uint8_t *Data, size_t Size, size_t MaxSize, - DictionaryEntry &DE); - - template - DictionaryEntry MakeDictionaryEntryFromCMP(T Arg1, T Arg2, - const uint8_t *Data, size_t Size); - DictionaryEntry MakeDictionaryEntryFromCMP(const Word &Arg1, const Word &Arg2, - const uint8_t *Data, size_t Size); - DictionaryEntry MakeDictionaryEntryFromCMP(const void *Arg1, const void *Arg2, - const void *Arg1Mutation, - const void *Arg2Mutation, - size_t ArgSize, - const uint8_t *Data, size_t Size); - - Random &Rand; - const FuzzingOptions Options; - - // Dictionary provided by the user via -dict=DICT_FILE. - Dictionary ManualDictionary; - // Persistent dictionary modified by the fuzzer, consists of - // entries that led to successful discoveries in the past mutations. - Dictionary PersistentAutoDictionary; - - Vector CurrentDictionaryEntrySequence; - - static const size_t kCmpDictionaryEntriesDequeSize = 16; - DictionaryEntry CmpDictionaryEntriesDeque[kCmpDictionaryEntriesDequeSize]; - size_t CmpDictionaryEntriesDequeIdx = 0; - - const Unit *CrossOverWith = nullptr; - Vector MutateInPlaceHere; - Vector MutateWithMaskTemp; - // CustomCrossOver needs its own buffer as a custom implementation may call - // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere. - Vector CustomCrossOverInPlaceHere; - - Vector Mutators; - Vector DefaultMutators; - Vector CurrentMutatorSequence; -}; +void PrintMutationSequence(MutationDispatcher &MD, bool Verbose = true); } // namespace fuzzer Index: compiler-rt/lib/fuzzer/FuzzerMutate.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerMutate.cpp +++ compiler-rt/lib/fuzzer/FuzzerMutate.cpp @@ -1,497 +1,76 @@ -//===- FuzzerMutate.cpp - Mutate a test input -----------------------------===// +//===- FuzzerMutate.cpp - Mutation utilities -----------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -// Mutate a test input. +// Mutate utilities. //===----------------------------------------------------------------------===// -#include "FuzzerDefs.h" +#include "FuzzerMutate.h" #include "FuzzerExtFunctions.h" #include "FuzzerIO.h" -#include "FuzzerMutate.h" -#include "FuzzerOptions.h" #include "FuzzerTracePC.h" +#include "FuzzerUtil.h" namespace fuzzer { +namespace { -const size_t Dictionary::kMaxDictSize; -static const size_t kMaxMutationsToPrint = 10; - -static void PrintASCII(const Word &W, const char *PrintAfter) { - PrintASCII(W.data(), W.size(), PrintAfter); -} - -MutationDispatcher::MutationDispatcher(Random &Rand, - const FuzzingOptions &Options) - : Rand(Rand), Options(Options) { - DefaultMutators.insert( - DefaultMutators.begin(), - { - {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"}, - {&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, - {&MutationDispatcher::Mutate_InsertRepeatedBytes, - "InsertRepeatedBytes"}, - {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, - {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, - {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, - {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, - {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"}, - {&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, - {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, - {&MutationDispatcher::Mutate_AddWordFromManualDictionary, - "ManualDict"}, - {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, - "PersAutoDict"}, - }); - if(Options.UseCmp) - DefaultMutators.push_back( - {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"}); - - if (EF->LLVMFuzzerCustomMutator) - Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); - else - Mutators = DefaultMutators; - - if (EF->LLVMFuzzerCustomCrossOver) - Mutators.push_back( - {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); -} - -static char RandCh(Random &Rand) { - if (Rand.RandBool()) - return static_cast(Rand(256)); - const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; - return Special[Rand(sizeof(Special) - 1)]; -} - -size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (EF->__msan_unpoison) - EF->__msan_unpoison(Data, Size); - if (EF->__msan_unpoison_param) - EF->__msan_unpoison_param(4); - return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, - Rand.Rand()); -} - -size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size == 0) - return 0; - if (!CrossOverWith) return 0; - const Unit &Other = *CrossOverWith; - if (Other.empty()) - return 0; - CustomCrossOverInPlaceHere.resize(MaxSize); - auto &U = CustomCrossOverInPlaceHere; - - if (EF->__msan_unpoison) { - EF->__msan_unpoison(Data, Size); - EF->__msan_unpoison(Other.data(), Other.size()); - EF->__msan_unpoison(U.data(), U.size()); - } - if (EF->__msan_unpoison_param) - EF->__msan_unpoison_param(7); - size_t NewSize = EF->LLVMFuzzerCustomCrossOver( - Data, Size, Other.data(), Other.size(), U.data(), U.size(), - Rand.Rand()); - - if (!NewSize) - return 0; - assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); - memcpy(Data, U.data(), NewSize); - return NewSize; -} - -size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size > MaxSize || Size == 0) return 0; - size_t ShuffleAmount = - Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. - size_t ShuffleStart = Rand(Size - ShuffleAmount); - assert(ShuffleStart + ShuffleAmount <= Size); - std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand); - return Size; -} - -size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size <= 1) return 0; - size_t N = Rand(Size / 2) + 1; - assert(N < Size); - size_t Idx = Rand(Size - N + 1); - // Erase Data[Idx:Idx+N]. - memmove(Data + Idx, Data + Idx + N, Size - Idx - N); - // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); - return Size - N; +void FromTORC4(size_t Idx, uint32_t *A, uint32_t *B) { + const auto &X = TPC.TORC4.Get(Idx); + *A = X.A; + *B = X.B; } -size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size >= MaxSize) return 0; - size_t Idx = Rand(Size + 1); - // Insert new value at Data[Idx]. - memmove(Data + Idx + 1, Data + Idx, Size - Idx); - Data[Idx] = RandCh(Rand); - return Size + 1; +void FromTORC8(size_t Idx, uint64_t *A, uint64_t *B) { + const auto &X = TPC.TORC8.Get(Idx); + *A = X.A; + *B = X.B; } -size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, - size_t Size, - size_t MaxSize) { - const size_t kMinBytesToInsert = 3; - if (Size + kMinBytesToInsert >= MaxSize) return 0; - size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); - size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; - assert(Size + N <= MaxSize && N); - size_t Idx = Rand(Size + 1); - // Insert new values at Data[Idx]. - memmove(Data + Idx + N, Data + Idx, Size - Idx); - // Give preference to 0x00 and 0xff. - uint8_t Byte = static_cast( - Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255)); - for (size_t i = 0; i < N; i++) - Data[Idx + i] = Byte; - return Size + N; +void FromTORCW(size_t Idx, const uint8_t **DataA, size_t *SizeA, + const uint8_t **DataB, size_t *SizeB) { + const auto &X = TPC.TORCW.Get(Idx); + *DataA = X.A.data(); + *SizeA = X.A.size(); + *DataB = X.B.data(); + *SizeB = X.B.size(); } -size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size > MaxSize) return 0; - size_t Idx = Rand(Size); - Data[Idx] = RandCh(Rand); - return Size; +void FromMMT(size_t Idx, const uint8_t **Data, size_t *Size) { + auto W = TPC.MMT.Get(Idx); + *Data = W.data(); + *Size = W.size(); } -size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size > MaxSize) return 0; - size_t Idx = Rand(Size); - Data[Idx] ^= 1 << Rand(8); - return Size; +void PrintASCII(const Word &W, const char *PrintAfter) { + fuzzer::PrintASCII(W.data(), W.size(), PrintAfter); } -size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, - size_t Size, - size_t MaxSize) { - return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); -} - -size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, - size_t MaxSize, - DictionaryEntry &DE) { - const Word &W = DE.GetW(); - bool UsePositionHint = DE.HasPositionHint() && - DE.GetPositionHint() + W.size() < Size && - Rand.RandBool(); - if (Rand.RandBool()) { // Insert W. - if (Size + W.size() > MaxSize) return 0; - size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); - memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); - memcpy(Data + Idx, W.data(), W.size()); - Size += W.size(); - } else { // Overwrite some bytes with W. - if (W.size() > Size) return 0; - size_t Idx = - UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size()); - memcpy(Data + Idx, W.data(), W.size()); - } - return Size; -} - -// Somewhere in the past we have observed a comparison instructions -// with arguments Arg1 Arg2. This function tries to guess a dictionary -// entry that will satisfy that comparison. -// It first tries to find one of the arguments (possibly swapped) in the -// input and if it succeeds it creates a DE with a position hint. -// Otherwise it creates a DE with one of the arguments w/o a position hint. -DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( - const void *Arg1, const void *Arg2, - const void *Arg1Mutation, const void *Arg2Mutation, - size_t ArgSize, const uint8_t *Data, - size_t Size) { - bool HandleFirst = Rand.RandBool(); - const void *ExistingBytes, *DesiredBytes; - Word W; - const uint8_t *End = Data + Size; - for (int Arg = 0; Arg < 2; Arg++) { - ExistingBytes = HandleFirst ? Arg1 : Arg2; - DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; - HandleFirst = !HandleFirst; - W.Set(reinterpret_cast(DesiredBytes), ArgSize); - const size_t kMaxNumPositions = 8; - size_t Positions[kMaxNumPositions]; - size_t NumPositions = 0; - for (const uint8_t *Cur = Data; - Cur < End && NumPositions < kMaxNumPositions; Cur++) { - Cur = - (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); - if (!Cur) break; - Positions[NumPositions++] = Cur - Data; - } - if (!NumPositions) continue; - return DictionaryEntry(W, Positions[Rand(NumPositions)]); - } - DictionaryEntry DE(W); - return DE; -} - - -template -DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( - T Arg1, T Arg2, const uint8_t *Data, size_t Size) { - if (Rand.RandBool()) Arg1 = Bswap(Arg1); - if (Rand.RandBool()) Arg2 = Bswap(Arg2); - T Arg1Mutation = static_cast(Arg1 + Rand(-1, 1)); - T Arg2Mutation = static_cast(Arg2 + Rand(-1, 1)); - return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, - sizeof(Arg1), Data, Size); -} +} // namespace -DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( - const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) { - return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(), - Arg2.data(), Arg1.size(), Data, Size); +void ConfigureMutagen(unsigned int Seed, const FuzzingOptions &Options, + LLVMMutagenConfiguration *OutConfig) { + OutConfig->Seed = Seed; + OutConfig->UseCmp = Options.UseCmp; + OutConfig->FromTORC4 = FromTORC4; + OutConfig->FromTORC8 = FromTORC8; + OutConfig->FromTORCW = FromTORCW; + OutConfig->UseMemmem = Options.UseMemmem; + OutConfig->FromMMT = FromMMT; + OutConfig->CustomMutator = EF->LLVMFuzzerCustomMutator; + OutConfig->CustomCrossOver = EF->LLVMFuzzerCustomCrossOver; + OutConfig->MSanUnpoison = EF->__msan_unpoison; + OutConfig->MSanUnpoisonParam = EF->__msan_unpoison_param; } -size_t MutationDispatcher::Mutate_AddWordFromTORC( - uint8_t *Data, size_t Size, size_t MaxSize) { - Word W; - DictionaryEntry DE; - switch (Rand(4)) { - case 0: { - auto X = TPC.TORC8.Get(Rand.Rand()); - DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); - } break; - case 1: { - auto X = TPC.TORC4.Get(Rand.Rand()); - if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool()) - DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size); - else - DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); - } break; - case 2: { - auto X = TPC.TORCW.Get(Rand.Rand()); - DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); - } break; - case 3: if (Options.UseMemmem) { - auto X = TPC.MMT.Get(Rand.Rand()); - DE = DictionaryEntry(X); - } break; - default: - assert(0); - } - if (!DE.GetW().size()) return 0; - Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); - if (!Size) return 0; - DictionaryEntry &DERef = - CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ % - kCmpDictionaryEntriesDequeSize]; - DERef = DE; - CurrentDictionaryEntrySequence.push_back(&DERef); - return Size; -} - -size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( - uint8_t *Data, size_t Size, size_t MaxSize) { - return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); -} - -size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, - size_t Size, size_t MaxSize) { - if (Size > MaxSize) return 0; - if (D.empty()) return 0; - DictionaryEntry &DE = D[Rand(D.size())]; - Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); - if (!Size) return 0; - DE.IncUseCount(); - CurrentDictionaryEntrySequence.push_back(&DE); - return Size; -} - -// Overwrites part of To[0,ToSize) with a part of From[0,FromSize). -// Returns ToSize. -size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, - uint8_t *To, size_t ToSize) { - // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). - size_t ToBeg = Rand(ToSize); - size_t CopySize = Rand(ToSize - ToBeg) + 1; - assert(ToBeg + CopySize <= ToSize); - CopySize = std::min(CopySize, FromSize); - size_t FromBeg = Rand(FromSize - CopySize + 1); - assert(FromBeg + CopySize <= FromSize); - memmove(To + ToBeg, From + FromBeg, CopySize); - return ToSize; -} - -// Inserts part of From[0,ToSize) into To. -// Returns new size of To on success or 0 on failure. -size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, - uint8_t *To, size_t ToSize, - size_t MaxToSize) { - if (ToSize >= MaxToSize) return 0; - size_t AvailableSpace = MaxToSize - ToSize; - size_t MaxCopySize = std::min(AvailableSpace, FromSize); - size_t CopySize = Rand(MaxCopySize) + 1; - size_t FromBeg = Rand(FromSize - CopySize + 1); - assert(FromBeg + CopySize <= FromSize); - size_t ToInsertPos = Rand(ToSize + 1); - assert(ToInsertPos + CopySize <= MaxToSize); - size_t TailSize = ToSize - ToInsertPos; - if (To == From) { - MutateInPlaceHere.resize(MaxToSize); - memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); - memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); - memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); - } else { - memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); - memmove(To + ToInsertPos, From + FromBeg, CopySize); - } - return ToSize + CopySize; -} - -size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size > MaxSize || Size == 0) return 0; - // If Size == MaxSize, `InsertPartOf(...)` will - // fail so there's no point using it in this case. - if (Size == MaxSize || Rand.RandBool()) - return CopyPartOf(Data, Size, Data, Size); - else - return InsertPartOf(Data, Size, Data, Size, MaxSize); -} - -size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size > MaxSize) return 0; - size_t B = Rand(Size); - while (B < Size && !isdigit(Data[B])) B++; - if (B == Size) return 0; - size_t E = B; - while (E < Size && isdigit(Data[E])) E++; - assert(B < E); - // now we have digits in [B, E). - // strtol and friends don't accept non-zero-teminated data, parse it manually. - uint64_t Val = Data[B] - '0'; - for (size_t i = B + 1; i < E; i++) - Val = Val * 10 + Data[i] - '0'; - - // Mutate the integer value. - switch(Rand(5)) { - case 0: Val++; break; - case 1: Val--; break; - case 2: Val /= 2; break; - case 3: Val *= 2; break; - case 4: Val = Rand(Val * Val); break; - default: assert(0); - } - // Just replace the bytes with the new ones, don't bother moving bytes. - for (size_t i = B; i < E; i++) { - size_t Idx = E + B - i - 1; - assert(Idx >= B && Idx < E); - Data[Idx] = (Val % 10) + '0'; - Val /= 10; - } - return Size; -} - -template -size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { - if (Size < sizeof(T)) return 0; - size_t Off = Rand(Size - sizeof(T) + 1); - assert(Off + sizeof(T) <= Size); - T Val; - if (Off < 64 && !Rand(4)) { - Val = static_cast(Size); - if (Rand.RandBool()) - Val = Bswap(Val); - } else { - memcpy(&Val, Data + Off, sizeof(Val)); - T Add = static_cast(Rand(21)); - Add -= 10; - if (Rand.RandBool()) - Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. - else - Val = Val + Add; // Add assuming current endiannes. - if (Add == 0 || Rand.RandBool()) // Maybe negate. - Val = -Val; - } - memcpy(Data + Off, &Val, sizeof(Val)); - return Size; -} - -size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, - size_t Size, - size_t MaxSize) { - if (Size > MaxSize) return 0; - switch (Rand(4)) { - case 3: return ChangeBinaryInteger(Data, Size, Rand); - case 2: return ChangeBinaryInteger(Data, Size, Rand); - case 1: return ChangeBinaryInteger(Data, Size, Rand); - case 0: return ChangeBinaryInteger(Data, Size, Rand); - default: assert(0); - } - return 0; -} - -size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, - size_t MaxSize) { - if (Size > MaxSize) return 0; - if (Size == 0) return 0; - if (!CrossOverWith) return 0; - const Unit &O = *CrossOverWith; - if (O.empty()) return 0; - size_t NewSize = 0; - switch(Rand(3)) { - case 0: - MutateInPlaceHere.resize(MaxSize); - NewSize = CrossOver(Data, Size, O.data(), O.size(), - MutateInPlaceHere.data(), MaxSize); - memcpy(Data, MutateInPlaceHere.data(), NewSize); - break; - case 1: - NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize); - if (!NewSize) - NewSize = CopyPartOf(O.data(), O.size(), Data, Size); - break; - case 2: - NewSize = CopyPartOf(O.data(), O.size(), Data, Size); - break; - default: assert(0); - } - assert(NewSize > 0 && "CrossOver returned empty unit"); - assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); - return NewSize; -} - -void MutationDispatcher::StartMutationSequence() { - CurrentMutatorSequence.clear(); - CurrentDictionaryEntrySequence.clear(); -} - -// Copy successful dictionary entries to PersistentAutoDictionary. -void MutationDispatcher::RecordSuccessfulMutationSequence() { - for (auto DE : CurrentDictionaryEntrySequence) { - // PersistentAutoDictionary.AddWithSuccessCountOne(DE); - DE->IncSuccessCount(); - assert(DE->GetW().size()); - // Linear search is fine here as this happens seldom. - if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) - PersistentAutoDictionary.push_back(*DE); - } -} - -void MutationDispatcher::PrintRecommendedDictionary() { - Vector V; - for (auto &DE : PersistentAutoDictionary) - if (!ManualDictionary.ContainsWord(DE.GetW())) - V.push_back(DE); - if (V.empty()) return; +void PrintRecommendedDictionary(MutationDispatcher &MD) { + auto RecommendedDictionary = MD.RecommendDictionary(); + if (RecommendedDictionary.empty()) + return; Printf("###### Recommended dictionary. ######\n"); - for (auto &DE: V) { + for (auto &DE : RecommendedDictionary) { assert(DE.GetW().size()); Printf("\""); PrintASCII(DE.GetW(), "\""); @@ -500,97 +79,12 @@ Printf("###### End of recommended dictionary. ######\n"); } -void MutationDispatcher::PrintMutationSequence(bool Verbose) { - Printf("MS: %zd ", CurrentMutatorSequence.size()); - size_t EntriesToPrint = - Verbose ? CurrentMutatorSequence.size() - : std::min(kMaxMutationsToPrint, CurrentMutatorSequence.size()); - for (size_t i = 0; i < EntriesToPrint; i++) - Printf("%s-", CurrentMutatorSequence[i].Name); - if (!CurrentDictionaryEntrySequence.empty()) { - Printf(" DE: "); - EntriesToPrint = Verbose ? CurrentDictionaryEntrySequence.size() - : std::min(kMaxMutationsToPrint, - CurrentDictionaryEntrySequence.size()); - for (size_t i = 0; i < EntriesToPrint; i++) { - Printf("\""); - PrintASCII(CurrentDictionaryEntrySequence[i]->GetW(), "\"-"); - } - } -} - -std::string MutationDispatcher::MutationSequence() { - std::string MS; - for (auto M : CurrentMutatorSequence) { - MS += M.Name; - MS += "-"; - } - return MS; -} - -size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { - return MutateImpl(Data, Size, MaxSize, Mutators); -} - -size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, - size_t MaxSize) { - return MutateImpl(Data, Size, MaxSize, DefaultMutators); -} - -// Mutates Data in place, returns new size. -size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, - size_t MaxSize, - Vector &Mutators) { - assert(MaxSize > 0); - // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), - // in which case they will return 0. - // Try several times before returning un-mutated data. - for (int Iter = 0; Iter < 100; Iter++) { - auto M = Mutators[Rand(Mutators.size())]; - size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); - if (NewSize && NewSize <= MaxSize) { - if (Options.OnlyASCII) - ToASCII(Data, NewSize); - CurrentMutatorSequence.push_back(M); - return NewSize; - } - } - *Data = ' '; - return 1; // Fallback, should not happen frequently. -} - -// Mask represents the set of Data bytes that are worth mutating. -size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size, - size_t MaxSize, - const Vector &Mask) { - size_t MaskedSize = std::min(Size, Mask.size()); - // * Copy the worthy bytes into a temporary array T - // * Mutate T - // * Copy T back. - // This is totally unoptimized. - auto &T = MutateWithMaskTemp; - if (T.size() < Size) - T.resize(Size); - size_t OneBits = 0; - for (size_t I = 0; I < MaskedSize; I++) - if (Mask[I]) - T[OneBits++] = Data[I]; - - if (!OneBits) return 0; - assert(!T.empty()); - size_t NewSize = Mutate(T.data(), OneBits, OneBits); - assert(NewSize <= OneBits); - (void)NewSize; - // Even if NewSize < OneBits we still use all OneBits bytes. - for (size_t I = 0, J = 0; I < MaskedSize; I++) - if (Mask[I]) - Data[I] = T[J++]; - return Size; -} - -void MutationDispatcher::AddWordToManualDictionary(const Word &W) { - ManualDictionary.push_back( - {W, std::numeric_limits::max()}); +void PrintMutationSequence(MutationDispatcher &MD, bool Verbose) { + const auto &MS = MD.MutationSequence(); + const auto &DS = MD.DictionaryEntrySequence(); + Printf("MS: %zd %s", MS.size(), MS.GetString(Verbose).c_str()); + if (!DS.empty()) + Printf(" DE: %s", DS.GetString(Verbose).c_str()); } } // namespace fuzzer Index: compiler-rt/lib/fuzzer/FuzzerRandom.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerRandom.h +++ compiler-rt/lib/fuzzer/FuzzerRandom.h @@ -11,6 +11,7 @@ #ifndef LLVM_FUZZER_RANDOM_H #define LLVM_FUZZER_RANDOM_H +#include #include namespace fuzzer { Index: compiler-rt/lib/fuzzer/FuzzerTracePC.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerTracePC.h +++ compiler-rt/lib/fuzzer/FuzzerTracePC.h @@ -12,7 +12,7 @@ #define LLVM_FUZZER_TRACE_PC #include "FuzzerDefs.h" -#include "FuzzerDictionary.h" +#include "FuzzerUtil.h" #include "FuzzerValueBitMap.h" #include @@ -40,7 +40,7 @@ Table[Idx].B = Arg2; } - Pair Get(size_t I) { return Table[I % kSize]; } + const Pair &Get(size_t I) { return Table[I % kSize]; } Pair Table[kSize]; }; Index: compiler-rt/lib/fuzzer/FuzzerTracePC.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerTracePC.cpp +++ compiler-rt/lib/fuzzer/FuzzerTracePC.cpp @@ -16,7 +16,6 @@ #include "FuzzerBuiltinsMsvc.h" #include "FuzzerCorpus.h" #include "FuzzerDefs.h" -#include "FuzzerDictionary.h" #include "FuzzerExtFunctions.h" #include "FuzzerIO.h" #include "FuzzerPlatform.h" Index: compiler-rt/lib/fuzzer/FuzzerUtil.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerUtil.h +++ compiler-rt/lib/fuzzer/FuzzerUtil.h @@ -47,6 +47,15 @@ unsigned NumberOfCpuCores(); +// Parses one dictionary entry. +// If successful, write the enty to Unit and returns true, +// otherwise returns false. +bool ParseOneDictionaryEntry(const std::string &Str, Unit *U); + +// Parses the dictionary file, fills Units, returns true iff all lines +// were parsed successfully. +bool ParseDictionaryFile(const std::string &Text, Vector *Units); + // Platform specific functions. void SetSignalHandler(const FuzzingOptions& Options); @@ -63,9 +72,6 @@ FILE *OpenProcessPipe(const char *Command, const char *Mode); int CloseProcessPipe(FILE *F); -const void *SearchMemory(const void *haystack, size_t haystacklen, - const void *needle, size_t needlelen); - std::string CloneArgsWithoutX(const Vector &Args, const char *X1, const char *X2); Index: compiler-rt/lib/fuzzer/FuzzerUtilFuchsia.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerUtilFuchsia.cpp +++ compiler-rt/lib/fuzzer/FuzzerUtilFuchsia.cpp @@ -528,11 +528,6 @@ return Ret == 0; } -const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt, - size_t PattLen) { - return memmem(Data, DataLen, Patt, PattLen); -} - // In fuchsia, accessing /dev/null is not supported. There's nothing // similar to a file that discards everything that is written to it. // The way of doing something similar in fuchsia is by using Index: compiler-rt/lib/fuzzer/FuzzerUtilPosix.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerUtilPosix.cpp +++ compiler-rt/lib/fuzzer/FuzzerUtilPosix.cpp @@ -170,11 +170,6 @@ return pclose(F); } -const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt, - size_t PattLen) { - return memmem(Data, DataLen, Patt, PattLen); -} - std::string DisassembleCmd(const std::string &FileName) { return "objdump -d " + FileName; } Index: compiler-rt/lib/fuzzer/FuzzerUtilWindows.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerUtilWindows.cpp +++ compiler-rt/lib/fuzzer/FuzzerUtilWindows.cpp @@ -182,27 +182,6 @@ return _pclose(Pipe) == 0; } -const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt, - size_t PattLen) { - // TODO: make this implementation more efficient. - const char *Cdata = (const char *)Data; - const char *Cpatt = (const char *)Patt; - - if (!Data || !Patt || DataLen == 0 || PattLen == 0 || DataLen < PattLen) - return NULL; - - if (PattLen == 1) - return memchr(Data, *Cpatt, DataLen); - - const char *End = Cdata + DataLen - PattLen + 1; - - for (const char *It = Cdata; It < End; ++It) - if (It[0] == Cpatt[0] && memcmp(It, Cpatt, PattLen) == 0) - return It; - - return NULL; -} - std::string DisassembleCmd(const std::string &FileName) { Vector command_vector; command_vector.push_back("dumpbin /summary > nul"); Index: compiler-rt/lib/fuzzer/build.sh =================================================================== --- compiler-rt/lib/fuzzer/build.sh +++ compiler-rt/lib/fuzzer/build.sh @@ -1,11 +1,11 @@ #!/bin/sh LIBFUZZER_SRC_DIR=$(dirname $0) +LIBMUTAGEN_SRC_DIR=$LIBFUZZER_SRC_DIR/mutagen CXX="${CXX:-clang}" -for f in $LIBFUZZER_SRC_DIR/*.cpp; do - $CXX -g -O2 -fno-omit-frame-pointer -std=c++11 $f -c & +for f in $LIBFUZZER_SRC_DIR/*.cpp $LIBMUTAGEN_SRC_DIR/*.cpp; do + $CXX -g -O2 -fno-omit-frame-pointer -std=c++11 $f -c -I$LIBFUZZER_SRC_DIR & done wait rm -f libFuzzer.a -ar ru libFuzzer.a Fuzzer*.o -rm -f Fuzzer*.o - +ar ru libFuzzer.a Fuzzer*.o Mutagen*.o +rm -f Fuzzer*.o Mutagen*.o Index: compiler-rt/lib/fuzzer/mutagen/CMakeLists.txt =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/CMakeLists.txt @@ -0,0 +1,59 @@ +set(MUTAGEN_SOURCES + Mutagen.cpp + MutagenCrossOver.cpp + MutagenDispatcher.cpp + MutagenUtilPosix.cpp + MutagenUtilWindows.cpp) + +set(MUTAGEN_HEADERS + Mutagen.h + MutagenDictionary.h + MutagenDispatcher.h + MutagenUtil.h) + +# Expose the files in this library to libFuzzer for optimized, direct inclusion. +set(LIBFUZZER_MUTAGEN_SOURCES ${MUTAGEN_SOURCES} PARENT_SCOPE) +set(LIBFUZZER_MUTAGEN_HEADERS ${MUTAGEN_HEADERS} PARENT_SCOPE) + +# Reuse the following variables from libFuzzer: +# FUZZER_SUPPORTED_ARCH +# FUZZER_SUPPORTED_OS +# LIBFUZZER_CFLAGS +# LIBFUZZER_DEPS +include_directories(..) + +add_compiler_rt_component(mutagen) + +add_compiler_rt_object_libraries(RTmutagen + OS ${FUZZER_SUPPORTED_OS} + ARCHS ${FUZZER_SUPPORTED_ARCH} + SOURCES ${MUTAGEN_SOURCES} + ADDITIONAL_HEADERS ${MUTAGEN_HEADERS} + CFLAGS ${LIBFUZZER_CFLAGS} + DEPS ${LIBFUZZER_DEPS}) + +add_compiler_rt_runtime(clang_rt.mutagen + STATIC + OS ${FUZZER_SUPPORTED_OS} + ARCHS ${FUZZER_SUPPORTED_ARCH} + OBJECT_LIBS RTmutagen + CFLAGS ${LIBFUZZER_CFLAGS} + PARENT_TARGET mutagen) + +if(OS_NAME MATCHES "Linux|Fuchsia" AND + COMPILER_RT_LIBCXX_PATH AND + COMPILER_RT_LIBCXXABI_PATH) + foreach(arch ${FUZZER_SUPPORTED_ARCH}) + get_target_flags_for_arch(${arch} TARGET_CFLAGS) + set(LIBCXX_${arch}_PREFIX ${CMAKE_CURRENT_BINARY_DIR}/libcxx_mutagen_${arch}) + add_custom_libcxx(libcxx_mutagen_${arch} ${LIBCXX_${arch}_PREFIX} + CFLAGS ${TARGET_CFLAGS} + CMAKE_ARGS -DCMAKE_CXX_COMPILER_WORKS=ON + -DCMAKE_POSITION_INDEPENDENT_CODE=ON + -DLIBCXXABI_ENABLE_EXCEPTIONS=OFF + -DLIBCXX_ABI_NAMESPACE=__Fuzzer) + target_compile_options(RTmutagen.${arch} PRIVATE -isystem ${LIBCXX_${arch}_PREFIX}/include/c++/v1) + add_dependencies(RTmutagen.${arch} libcxx_mutagen_${arch}-build) + partially_link_libcxx(mutagen ${LIBCXX_${arch}_PREFIX} ${arch}) + endforeach() +endif() Index: compiler-rt/lib/fuzzer/mutagen/Mutagen.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/Mutagen.h @@ -0,0 +1,119 @@ +//===- Mutagen.h - Interface header for the mutagen -------------*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Define the interface between libMutagen and its consumers. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_MUTAGEN_H +#define LLVM_FUZZER_MUTAGEN_H + +#include "FuzzerPlatform.h" +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif // __cplusplus + +#define MAX_WORD_SIZE 64 + +typedef struct { + // PRNG seed. + unsigned int Seed; + + // If non-zero, use CMP traces to guide mutations. Ignored if any of + // |FromTORC4|, |FromTORC8|, or |FromTORCW| are null. + int UseCmp; + void (*FromTORC4)(size_t Idx, uint32_t *Arg1, uint32_t *Arg2); + void (*FromTORC8)(size_t Idx, uint64_t *Arg1, uint64_t *Arg2); + void (*FromTORCW)(size_t Idx, const uint8_t **Data1, size_t *Size1, + const uint8_t **Data2, size_t *Size2); + + // If non-zero, use hints from intercepting memmem, strstr, etc. Ignored if + // |UseCmp| is zero or if |FromMMT| is null. + int UseMemmem; + void (*FromMMT)(size_t Idx, const uint8_t **Data, size_t *Size); + + // If non-zero, generate only ASCII (isprint+isspace) inputs. + int OnlyASCII; + + // Optional user-provided custom mutator. + size_t (*CustomMutator)(uint8_t *Data, size_t Size, size_t MaxSize, + unsigned int Seed); + + // Optional user-provided custom cross-over function. + size_t (*CustomCrossOver)(const uint8_t *Data1, size_t Size1, + const uint8_t *Data2, size_t Size2, uint8_t *Out, + size_t MaxOutSize, unsigned int Seed); + + // Optional MemorySanitizer callbacks. + void (*MSanUnpoison)(const volatile void *, size_t size); + void (*MSanUnpoisonParam)(size_t n); +} LLVMMutagenConfiguration; + +// Re-seeds the PRNG and sets mutator-related options. +ATTRIBUTE_INTERFACE void +LLVMMutagenConfigure(const LLVMMutagenConfiguration *config); + +// Writes the mutation sequence to |Out|, and returns the number of +// characters it wrote, or would have written given a large enough buffer, +// excluding the null terminator. Thus, a return value of |Max| or greater +// indicates the sequence was truncated (like snprintf). May truncate the +// sequence unless |Verbose| is non-zero. Sets |OutNumItems| to the number of +// items in the untruncated sequence. +ATTRIBUTE_INTERFACE size_t LLVMMutagenGetMutationSequence(int Verbose, + char *Out, size_t Max, + size_t *OutNumItems); + +// Writes the dictionary entry sequence to |Out|, and returns the number of +// characters it wrote, or would have written given a large enough buffer, +// excluding a null terminator. Thus, a return value of |Max| or greater +// indicates the sequence was truncated (like snprintf). May truncate the +// sequence unless |Verbose| is non-zero. Sets |OutNumItems| to the number of +// items in the untruncated sequence. +ATTRIBUTE_INTERFACE size_t LLVMMutagenGetDictionaryEntrySequence( + int Verbose, char *Out, size_t Max, size_t *OutNumItems); + +// Instructs the library to record the current mutation sequence as successful +// at increasing coverage. +ATTRIBUTE_INTERFACE void LLVMMutagenRecordSequence(); + +// Clears the mutation and dictionary entry sequences. +ATTRIBUTE_INTERFACE void LLVMMutagenResetSequence(); + +// Adds data used by various mutators to produce new inputs. +ATTRIBUTE_INTERFACE void LLVMMutagenSetCrossOverWith(const uint8_t *Data, + size_t Size); +ATTRIBUTE_INTERFACE void LLVMMutagenAddWordToDictionary(const uint8_t *Word, + size_t Size); + +// Mutates the contents of |Data| and returns the new size. +ATTRIBUTE_INTERFACE size_t LLVMMutagenMutate(uint8_t *Data, size_t Size, + size_t Max); + +// Like |LLVMMutagenMutate|, but never selects the custom mutators and is +// therefore suitable to be called from them. +ATTRIBUTE_INTERFACE size_t LLVMMutagenDefaultMutate(uint8_t *Data, size_t Size, + size_t Max); + +// Creates a recommended dictionary and returns its number of entries. The +// entries can be retrieved by subsequent calls to +// |LLVMMutagenRecommendDictionaryEntry|. +ATTRIBUTE_INTERFACE size_t LLVMMutagenRecommendDictionary(); + +// Returns the ASCII representation of the next recommended dictionary entry, +// or null if no entries remain (or |LLVMMutagenRecommendDictionary| wasn't +// called). If non-null, the return pointer is valid until the next call to this +// method, and if provided, |OutUseCount| is set to the entry's use count. +ATTRIBUTE_INTERFACE const char * +LLVMMutagenRecommendDictionaryEntry(size_t *OutUseCount); + +#ifdef __cplusplus +} // extern "C" +#endif // __cplusplus + +#endif // LLVM_FUZZER_MUTAGEN_H Index: compiler-rt/lib/fuzzer/mutagen/Mutagen.cpp =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/Mutagen.cpp @@ -0,0 +1,100 @@ +//===- Mutagen.cpp - Interface header for the mutagen -----------*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Define the interface between libMutagen and its consumers. +//===----------------------------------------------------------------------===// + +#include "Mutagen.h" +#include "FuzzerDefs.h" +#include "MutagenDispatcher.h" +#include +#include +#include + +namespace mutagen { +namespace { + +MutationDispatcher *MD = nullptr; + +} // namespace + +MutationDispatcher *GetMutationDispatcherForTest() { return MD; } + +} // namespace mutagen + +using fuzzer::Unit; +using mutagen::MD; +using mutagen::MutationDispatcher; +using mutagen::Word; + +extern "C" { + +ATTRIBUTE_INTERFACE void +LLVMMutagenConfigure(const LLVMMutagenConfiguration *Config) { + if (MD) + delete MD; + MD = new MutationDispatcher(Config); +} + +ATTRIBUTE_INTERFACE void LLVMMutagenResetSequence() { + MD->StartMutationSequence(); +} + +ATTRIBUTE_INTERFACE void LLVMMutagenSetCrossOverWith(const uint8_t *Data, + size_t Size) { + static Unit CrossOverWith; + Unit U(Data, Data + Size); + CrossOverWith = std::move(U); + MD->SetCrossOverWith(&CrossOverWith); +} + +ATTRIBUTE_INTERFACE size_t LLVMMutagenMutate(uint8_t *Data, size_t Size, + size_t Max) { + return MD->Mutate(Data, Size, Max); +} + +ATTRIBUTE_INTERFACE size_t LLVMMutagenDefaultMutate(uint8_t *Data, size_t Size, + size_t Max) { + return MD->DefaultMutate(Data, Size, Max); +} + +ATTRIBUTE_INTERFACE void LLVMMutagenRecordSequence() { + MD->RecordSuccessfulMutationSequence(); +} + +ATTRIBUTE_INTERFACE size_t LLVMMutagenGetMutationSequence(int Verbose, + char *Out, size_t Max, + size_t *OutNumItems) { + const auto &Seq = MD->MutationSequence(); + if (OutNumItems) + *OutNumItems = Seq.size(); + return snprintf(Out, Max, "%s", Seq.GetString(Verbose).c_str()); +} + +ATTRIBUTE_INTERFACE void LLVMMutagenAddWordToDictionary(const uint8_t *Data, + size_t Size) { + MD->AddWordToManualDictionary(Word(Data, std::min(Size, Word::GetMaxSize()))); +} + +ATTRIBUTE_INTERFACE size_t LLVMMutagenGetDictionaryEntrySequence( + int Verbose, char *Out, size_t Max, size_t *OutNumItems) { + const auto &Seq = MD->DictionaryEntrySequence(); + if (OutNumItems) + *OutNumItems = Seq.size(); + return snprintf(Out, Max, "%s", Seq.GetString(Verbose).c_str()); +} + +ATTRIBUTE_INTERFACE size_t LLVMMutagenRecommendDictionary() { + return MD->RecommendDictionary().size(); +} + +ATTRIBUTE_INTERFACE const char * +LLVMMutagenRecommendDictionaryEntry(size_t *OutUseCount) { + return MD->RecommendDictionaryEntry(OutUseCount); +} + +} // extern "C" Index: compiler-rt/lib/fuzzer/mutagen/MutagenCrossOver.cpp =================================================================== --- compiler-rt/lib/fuzzer/mutagen/MutagenCrossOver.cpp +++ compiler-rt/lib/fuzzer/mutagen/MutagenCrossOver.cpp @@ -1,4 +1,4 @@ -//===- FuzzerCrossOver.cpp - Cross over two test inputs -------------------===// +//===- MutagenCrossOver.cpp - Cross over two test inputs ------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -8,12 +8,11 @@ // Cross over test inputs. //===----------------------------------------------------------------------===// -#include "FuzzerDefs.h" -#include "FuzzerMutate.h" #include "FuzzerRandom.h" +#include "MutagenDispatcher.h" #include -namespace fuzzer { +namespace mutagen { // Cross Data1 and Data2, store the result (up to MaxOutSize bytes) in Out. size_t MutationDispatcher::CrossOver(const uint8_t *Data1, size_t Size1, @@ -40,12 +39,12 @@ (*InPos) += ExtraSize; } // Use the other input data on the next iteration. - InPos = CurrentlyUsingFirstData ? &Pos2 : &Pos1; + InPos = CurrentlyUsingFirstData ? &Pos2 : &Pos1; InSize = CurrentlyUsingFirstData ? Size2 : Size1; - Data = CurrentlyUsingFirstData ? Data2 : Data1; + Data = CurrentlyUsingFirstData ? Data2 : Data1; CurrentlyUsingFirstData = !CurrentlyUsingFirstData; } return OutPos; } -} // namespace fuzzer +} // namespace mutagen Index: compiler-rt/lib/fuzzer/mutagen/MutagenDictionary.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/MutagenDictionary.h @@ -0,0 +1,85 @@ +//===- MutagenDictionary.h - Internal header for the mutagen ----*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// mutagen::Dictionary +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_MUTAGEN_DICTIONARY_H +#define LLVM_FUZZER_MUTAGEN_DICTIONARY_H + +#include "FuzzerDefs.h" +#include +#include +#include +#include +#include + +namespace mutagen { +namespace { + +using fuzzer::Word; + +} // namespace + +class DictionaryEntry { +public: + DictionaryEntry() {} + DictionaryEntry(Word W) : W(W) {} + DictionaryEntry(Word W, size_t PositionHint) + : W(W), PositionHint(PositionHint) {} + const Word &GetW() const { return W; } + + bool HasPositionHint() const { + return PositionHint != std::numeric_limits::max(); + } + size_t GetPositionHint() const { + assert(HasPositionHint()); + return PositionHint; + } + void IncUseCount() { UseCount++; } + void IncSuccessCount() { SuccessCount++; } + size_t GetUseCount() const { return UseCount; } + size_t GetSuccessCount() const { return SuccessCount; } + +private: + Word W; + size_t PositionHint = std::numeric_limits::max(); + size_t UseCount = 0; + size_t SuccessCount = 0; +}; + +class Dictionary { +public: + static const size_t kMaxDictSize = 1 << 14; + + bool ContainsWord(const Word &W) const { + return std::any_of(begin(), end(), [&](const DictionaryEntry &DE) { + return DE.GetW() == W; + }); + } + const DictionaryEntry *begin() const { return &DE[0]; } + const DictionaryEntry *end() const { return begin() + Size; } + DictionaryEntry &operator[](size_t Idx) { + assert(Idx < Size); + return DE[Idx]; + } + void push_back(DictionaryEntry DE) { + if (Size < kMaxDictSize) + this->DE[Size++] = DE; + } + void clear() { Size = 0; } + bool empty() const { return Size == 0; } + size_t size() const { return Size; } + +private: + DictionaryEntry DE[kMaxDictSize]; + size_t Size = 0; +}; + +} // namespace mutagen + +#endif // LLVM_FUZZER_MUTAGEN_DICTIONARY_H Index: compiler-rt/lib/fuzzer/mutagen/MutagenDispatcher.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/MutagenDispatcher.h @@ -0,0 +1,190 @@ +//===- MutagenDispatcher.h - Internal header for the mutagen ----*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// mutagen::MutationDispatcher +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_MUTAGEN_DISPATCHER_H +#define LLVM_FUZZER_MUTAGEN_DISPATCHER_H + +#include "FuzzerRandom.h" +#include "Mutagen.h" +#include "MutagenDictionary.h" +#include "MutagenSequence.h" +#include +#include +#include + +namespace mutagen { +namespace { + +using fuzzer::Random; +using fuzzer::Unit; +using fuzzer::Vector; +using fuzzer::Word; + +} // namespace + +class MutationDispatcher final { +public: + struct Mutator { + size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max); + const char *Name; + }; + + explicit MutationDispatcher(const LLVMMutagenConfiguration *Config); + ~MutationDispatcher() = default; + + /// Indicate that we are about to start a new sequence of mutations. + void StartMutationSequence(); + /// Returns the current sequence of mutations. May truncate the sequence + /// unless Verbose is true. Sets |OutSize| to the length of the untrancated + /// sequence, if provided. + const Sequence &MutationSequence(); + /// Returns the current sequence of dictionary entries. May truncate the + /// sequence unless Verbose is true. Sets |OutSize| to the length of the + /// untrancated sequence, if provided. + const Sequence &DictionaryEntrySequence(); + /// Indicate that the current sequence of mutations was successful. + void RecordSuccessfulMutationSequence(); + /// Mutates data by invoking user-provided mutator. + size_t Mutate_Custom(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by invoking user-provided crossover. + size_t Mutate_CustomCrossOver(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by shuffling bytes. + size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by erasing bytes. + size_t Mutate_EraseBytes(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by inserting a byte. + size_t Mutate_InsertByte(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by inserting several repeated bytes. + size_t Mutate_InsertRepeatedBytes(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by changing one byte. + size_t Mutate_ChangeByte(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by changing one bit. + size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by copying/inserting a part of data into a different place. + size_t Mutate_CopyPart(uint8_t *Data, size_t Size, size_t MaxSize); + + /// Mutates data by adding a word from the manual dictionary. + size_t Mutate_AddWordFromManualDictionary(uint8_t *Data, size_t Size, + size_t MaxSize); + + /// Mutates data by adding a word from the TORC. + size_t Mutate_AddWordFromTORC(uint8_t *Data, size_t Size, size_t MaxSize); + + /// Mutates data by adding a word from the persistent automatic dictionary. + size_t Mutate_AddWordFromPersistentAutoDictionary(uint8_t *Data, size_t Size, + size_t MaxSize); + + /// Tries to find an ASCII integer in Data, changes it to another ASCII int. + size_t Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, size_t MaxSize); + /// Change a 1-, 2-, 4-, or 8-byte integer in interesting ways. + size_t Mutate_ChangeBinaryInteger(uint8_t *Data, size_t Size, size_t MaxSize); + + /// CrossOver Data with CrossOverWith. + size_t Mutate_CrossOver(uint8_t *Data, size_t Size, size_t MaxSize); + + size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size, + size_t MaxSize); + size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize, + Vector &Mutators); + + size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To, + size_t ToSize, size_t MaxToSize); + size_t CopyPartOf(const uint8_t *From, size_t FromSize, uint8_t *To, + size_t ToSize); + size_t ApplyDictionaryEntry(uint8_t *Data, size_t Size, size_t MaxSize, + DictionaryEntry &DE); + + template + DictionaryEntry MakeDictionaryEntryFromCMP(T Arg1, T Arg2, + const uint8_t *Data, size_t Size); + DictionaryEntry MakeDictionaryEntryFromCMP(const Word &Arg1, const Word &Arg2, + const uint8_t *Data, size_t Size); + DictionaryEntry MakeDictionaryEntryFromCMP(const void *Arg1, const void *Arg2, + const void *Arg1Mutation, + const void *Arg2Mutation, + size_t ArgSize, + const uint8_t *Data, size_t Size); + + /// Applies one of the configured mutations. + /// Returns the new size of data which could be up to MaxSize. + size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize); + + /// Applies one of the configured mutations to the bytes of Data + /// that have '1' in Mask. + /// Mask.size() should be >= Size. + size_t MutateWithMask(uint8_t *Data, size_t Size, size_t MaxSize, + const Vector &Mask); + + /// Applies one of the default mutations. Provided as a service + /// to mutation authors. + size_t DefaultMutate(uint8_t *Data, size_t Size, size_t MaxSize); + + /// Creates a cross-over of two pieces of Data, returns its size. + size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2, + size_t Size2, uint8_t *Out, size_t MaxOutSize); + + void AddWordToManualDictionary(const Word &W); + + // Creates a recommended dictionary and returns its number of entries. The + // entries can be retrieved by subsequent calls to + // |LLVMMutagenRecommendDictionaryEntry|. + const Dictionary &RecommendDictionary(); + + // Returns the ASCII representation of the next recommended dictionary entry, + // and sets |OutUseCount| to its use count. The return pointer is valid until + // the next call to this method. + const char *RecommendDictionaryEntry(size_t *OutUseCount); + + void SetCrossOverWith(const Unit *U) { CrossOverWith = U; } + + Random &GetRand() { return Rand; } + +private: + // Imports and validates the disptacher's configuration. + void SetConfig(const LLVMMutagenConfiguration *Config); + + Random Rand; + LLVMMutagenConfiguration Config; + + // Dictionary provided by the user via -dict=DICT_FILE. + Dictionary ManualDictionary; + // Persistent dictionary modified by the fuzzer, consists of + // entries that led to successful discoveries in the past mutations. + Dictionary PersistentAutoDictionary; + // Recommended dictionary buolt by |RecommendDictionary|. + Dictionary RecommendedDictionary; + size_t NextRecommendedDictionaryEntry = 0; + std::string DictionaryEntryWord; + + Sequence CurrentDictionaryEntrySequence; + + static const size_t kCmpDictionaryEntriesDequeSize = 16; + DictionaryEntry CmpDictionaryEntriesDeque[kCmpDictionaryEntriesDequeSize]; + size_t CmpDictionaryEntriesDequeIdx = 0; + + const Unit *CrossOverWith = nullptr; + Vector MutateInPlaceHere; + Vector MutateWithMaskTemp; + // CustomCrossOver needs its own buffer as a custom implementation may call + // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere. + Vector CustomCrossOverInPlaceHere; + + Vector Mutators; + Vector DefaultMutators; + Sequence CurrentMutatorSequence; +}; + +// Returns a pointer to the MutationDispatcher is use by MutagenInterface. +// This should only be used for testing. +MutationDispatcher *GetMutationDispatcherForTest(); + +} // namespace mutagen + +#endif // LLVM_FUZZER_MUTAGEN_DISPATCHER_H Index: compiler-rt/lib/fuzzer/mutagen/MutagenDispatcher.cpp =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/MutagenDispatcher.cpp @@ -0,0 +1,658 @@ +//===- MutagenDispatcher.cpp - Mutate a test input ------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Mutate a test input. +//===----------------------------------------------------------------------===// + +#include "MutagenDispatcher.h" +#include "FuzzerBuiltins.h" +#include "FuzzerPlatform.h" +#include "MutagenUtil.h" +#include +#include + +namespace mutagen { +namespace { + +using fuzzer::Bswap; + +std::string ToASCII(const uint8_t *Data, size_t Size) { + std::ostringstream OSS; + for (size_t i = 0; i < Size; i++) { + uint16_t Byte = Data[i]; + if (Byte == '\\') + OSS << "\\\\"; + else if (Byte == '"') + OSS << "\\\""; + else if (Byte >= 32 && Byte < 127) + OSS << static_cast(Byte); + else + OSS << "\\x" << std::hex << std::setw(2) << std::setfill('0') << Byte + << std::dec; + } + return OSS.str(); +} + +std::string ToASCII(const Word &W) { return ToASCII(W.data(), W.size()); } + +} // namespace + +void MutationDispatcher::SetConfig(const LLVMMutagenConfiguration *C) { + memcpy(&Config, C, sizeof(Config)); + if (!Config.FromTORC4 || !Config.FromTORC8 || !Config.FromTORCW) + Config.UseCmp = 0; + if (!Config.FromMMT) + Config.UseMemmem = 0; +} + +MutationDispatcher::MutationDispatcher(const LLVMMutagenConfiguration *config) + : Rand(config->Seed) { + SetConfig(config); + DefaultMutators.insert( + DefaultMutators.begin(), + { + {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"}, + {&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, + {&MutationDispatcher::Mutate_InsertRepeatedBytes, + "InsertRepeatedBytes"}, + {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, + {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, + {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, + {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, + {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"}, + {&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, + {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, + {&MutationDispatcher::Mutate_AddWordFromManualDictionary, + "ManualDict"}, + {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, + "PersAutoDict"}, + }); + if (Config.UseCmp) + DefaultMutators.push_back( + {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"}); + + if (Config.CustomMutator) + Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); + else + Mutators = DefaultMutators; + + if (Config.CustomCrossOver) + Mutators.push_back( + {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); +} + +static char RandCh(Random &Rand) { + if (Rand.RandBool()) + return static_cast(Rand(256)); + const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; + return Special[Rand(sizeof(Special) - 1)]; +} + +size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Config.MSanUnpoison) + Config.MSanUnpoison(Data, Size); + if (Config.MSanUnpoisonParam) + Config.MSanUnpoisonParam(4); + return Config.CustomMutator(Data, Size, MaxSize, Rand.Rand()); +} + +size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size == 0) + return 0; + if (!CrossOverWith) + return 0; + const Unit &Other = *CrossOverWith; + if (Other.empty()) + return 0; + CustomCrossOverInPlaceHere.resize(MaxSize); + auto &U = CustomCrossOverInPlaceHere; + + if (Config.MSanUnpoison) { + Config.MSanUnpoison(Data, Size); + Config.MSanUnpoison(Other.data(), Other.size()); + Config.MSanUnpoison(U.data(), U.size()); + } + if (Config.MSanUnpoisonParam) + Config.MSanUnpoisonParam(7); + size_t NewSize = + Config.CustomCrossOver(Data, Size, Other.data(), Other.size(), U.data(), + U.size(), Rand.Rand()); + + if (!NewSize) + return 0; + assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); + memcpy(Data, U.data(), NewSize); + return NewSize; +} + +size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size > MaxSize || Size == 0) + return 0; + size_t ShuffleAmount = + Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. + size_t ShuffleStart = Rand(Size - ShuffleAmount); + assert(ShuffleStart + ShuffleAmount <= Size); + std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand); + return Size; +} + +size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size <= 1) + return 0; + size_t N = Rand(Size / 2) + 1; + assert(N < Size); + size_t Idx = Rand(Size - N + 1); + // Erase Data[Idx:Idx+N]. + memmove(Data + Idx, Data + Idx + N, Size - Idx - N); + // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); + return Size - N; +} + +size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size >= MaxSize) + return 0; + size_t Idx = Rand(Size + 1); + // Insert new value at Data[Idx]. + memmove(Data + Idx + 1, Data + Idx, Size - Idx); + Data[Idx] = RandCh(Rand); + return Size + 1; +} + +size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, + size_t Size, + size_t MaxSize) { + const size_t kMinBytesToInsert = 3; + if (Size + kMinBytesToInsert >= MaxSize) + return 0; + size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); + size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; + assert(Size + N <= MaxSize && N); + size_t Idx = Rand(Size + 1); + // Insert new values at Data[Idx]. + memmove(Data + Idx + N, Data + Idx, Size - Idx); + // Give preference to 0x00 and 0xff. + uint8_t Byte = static_cast( + Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255)); + for (size_t i = 0; i < N; i++) + Data[Idx + i] = Byte; + return Size + N; +} + +size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size > MaxSize) + return 0; + size_t Idx = Rand(Size); + Data[Idx] = RandCh(Rand); + return Size; +} + +size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size > MaxSize) + return 0; + size_t Idx = Rand(Size); + Data[Idx] ^= 1 << Rand(8); + return Size; +} + +size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, + size_t Size, + size_t MaxSize) { + return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); +} + +size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, + size_t MaxSize, + DictionaryEntry &DE) { + const Word &W = DE.GetW(); + bool UsePositionHint = DE.HasPositionHint() && + DE.GetPositionHint() + W.size() < Size && + Rand.RandBool(); + if (Rand.RandBool()) { // Insert W. + if (Size + W.size() > MaxSize) + return 0; + size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); + memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); + memcpy(Data + Idx, W.data(), W.size()); + Size += W.size(); + } else { // Overwrite some bytes with W. + if (W.size() > Size) + return 0; + size_t Idx = + UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size()); + memcpy(Data + Idx, W.data(), W.size()); + } + return Size; +} + +// Somewhere in the past we have observed a comparison instructions +// with arguments Arg1 Arg2. This function tries to guess a dictionary +// entry that will satisfy that comparison. +// It first tries to find one of the arguments (possibly swapped) in the +// input and if it succeeds it creates a DE with a position hint. +// Otherwise it creates a DE with one of the arguments w/o a position hint. +DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( + const void *Arg1, const void *Arg2, const void *Arg1Mutation, + const void *Arg2Mutation, size_t ArgSize, const uint8_t *Data, + size_t Size) { + bool HandleFirst = Rand.RandBool(); + const void *ExistingBytes, *DesiredBytes; + Word W; + const uint8_t *End = Data + Size; + for (int Arg = 0; Arg < 2; Arg++) { + ExistingBytes = HandleFirst ? Arg1 : Arg2; + DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; + HandleFirst = !HandleFirst; + W.Set(reinterpret_cast(DesiredBytes), ArgSize); + const size_t kMaxNumPositions = 8; + size_t Positions[kMaxNumPositions]; + size_t NumPositions = 0; + for (const uint8_t *Cur = Data; + Cur < End && NumPositions < kMaxNumPositions; Cur++) { + Cur = + (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); + if (!Cur) + break; + Positions[NumPositions++] = Cur - Data; + } + if (!NumPositions) + continue; + return DictionaryEntry(W, Positions[Rand(NumPositions)]); + } + DictionaryEntry DE(W); + return DE; +} + +template +DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( + T Arg1, T Arg2, const uint8_t *Data, size_t Size) { + if (Rand.RandBool()) + Arg1 = Bswap(Arg1); + if (Rand.RandBool()) + Arg2 = Bswap(Arg2); + T Arg1Mutation = static_cast(Arg1 + Rand(-1, 1)); + T Arg2Mutation = static_cast(Arg2 + Rand(-1, 1)); + return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, + sizeof(Arg1), Data, Size); +} + +size_t MutationDispatcher::Mutate_AddWordFromTORC(uint8_t *Data, size_t Size, + size_t MaxSize) { + Word W; + DictionaryEntry DE; + switch (Rand(4)) { + case 0: { + uint64_t A, B; + Config.FromTORC8(Rand.Rand(), &A, &B); + DE = MakeDictionaryEntryFromCMP(A, B, Data, Size); + } break; + case 1: { + uint32_t A, B; + Config.FromTORC4(Rand.Rand(), &A, &B); + if ((A >> 16) == 0 && (B >> 16) == 0 && Rand.RandBool()) + DE = MakeDictionaryEntryFromCMP((uint16_t)A, (uint16_t)B, Data, Size); + else + DE = MakeDictionaryEntryFromCMP(A, B, Data, Size); + } break; + case 2: { + const uint8_t *DataA, *DataB; + size_t SizeA, SizeB; + Config.FromTORCW(Rand.Rand(), &DataA, &SizeA, &DataB, &SizeB); + DE = MakeDictionaryEntryFromCMP(DataA, DataB, DataA, DataB, SizeA, Data, + Size); + } break; + case 3: + if (Config.UseMemmem) { + const uint8_t *DataW; + size_t SizeW; + Config.FromMMT(Rand.Rand(), &DataW, &SizeW); + DE = DictionaryEntry(Word(DataW, SizeW)); + } + break; + default: + assert(0); + } + if (!DE.GetW().size()) + return 0; + Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); + if (!Size) + return 0; + DictionaryEntry &DERef = + CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ % + kCmpDictionaryEntriesDequeSize]; + DERef = DE; + CurrentDictionaryEntrySequence.push_back(&DERef); + return Size; +} + +size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( + uint8_t *Data, size_t Size, size_t MaxSize) { + return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); +} + +size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, + size_t Size, size_t MaxSize) { + if (Size > MaxSize) + return 0; + if (D.empty()) + return 0; + DictionaryEntry &DE = D[Rand(D.size())]; + Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); + if (!Size) + return 0; + DE.IncUseCount(); + CurrentDictionaryEntrySequence.push_back(&DE); + return Size; +} + +// Overwrites part of To[0,ToSize) with a part of From[0,FromSize). +// Returns ToSize. +size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, + uint8_t *To, size_t ToSize) { + // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). + size_t ToBeg = Rand(ToSize); + size_t CopySize = Rand(ToSize - ToBeg) + 1; + assert(ToBeg + CopySize <= ToSize); + CopySize = std::min(CopySize, FromSize); + size_t FromBeg = Rand(FromSize - CopySize + 1); + assert(FromBeg + CopySize <= FromSize); + memmove(To + ToBeg, From + FromBeg, CopySize); + return ToSize; +} + +// Inserts part of From[0,ToSize) into To. +// Returns new size of To on success or 0 on failure. +size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, + uint8_t *To, size_t ToSize, + size_t MaxToSize) { + if (ToSize >= MaxToSize) + return 0; + size_t AvailableSpace = MaxToSize - ToSize; + size_t MaxCopySize = std::min(AvailableSpace, FromSize); + size_t CopySize = Rand(MaxCopySize) + 1; + size_t FromBeg = Rand(FromSize - CopySize + 1); + assert(FromBeg + CopySize <= FromSize); + size_t ToInsertPos = Rand(ToSize + 1); + assert(ToInsertPos + CopySize <= MaxToSize); + size_t TailSize = ToSize - ToInsertPos; + if (To == From) { + MutateInPlaceHere.resize(MaxToSize); + memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); + memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); + memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); + } else { + memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); + memmove(To + ToInsertPos, From + FromBeg, CopySize); + } + return ToSize + CopySize; +} + +size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size > MaxSize || Size == 0) + return 0; + // If Size == MaxSize, `InsertPartOf(...)` will + // fail so there's no point using it in this case. + if (Size == MaxSize || Rand.RandBool()) + return CopyPartOf(Data, Size, Data, Size); + else + return InsertPartOf(Data, Size, Data, Size, MaxSize); +} + +size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size > MaxSize) + return 0; + size_t B = Rand(Size); + while (B < Size && !isdigit(Data[B])) + B++; + if (B == Size) + return 0; + size_t E = B; + while (E < Size && isdigit(Data[E])) + E++; + assert(B < E); + // now we have digits in [B, E). + // strtol and friends don't accept non-zero-teminated data, parse it manually. + uint64_t Val = Data[B] - '0'; + for (size_t i = B + 1; i < E; i++) + Val = Val * 10 + Data[i] - '0'; + + // Mutate the integer value. + switch (Rand(5)) { + case 0: + Val++; + break; + case 1: + Val--; + break; + case 2: + Val /= 2; + break; + case 3: + Val *= 2; + break; + case 4: + Val = Rand(Val * Val); + break; + default: + assert(0); + } + // Just replace the bytes with the new ones, don't bother moving bytes. + for (size_t i = B; i < E; i++) { + size_t Idx = E + B - i - 1; + assert(Idx >= B && Idx < E); + Data[Idx] = (Val % 10) + '0'; + Val /= 10; + } + return Size; +} + +template +size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { + if (Size < sizeof(T)) + return 0; + size_t Off = Rand(Size - sizeof(T) + 1); + assert(Off + sizeof(T) <= Size); + T Val; + if (Off < 64 && !Rand(4)) { + Val = static_cast(Size); + if (Rand.RandBool()) + Val = Bswap(Val); + } else { + memcpy(&Val, Data + Off, sizeof(Val)); + T Add = static_cast(Rand(21)); + Add -= 10; + if (Rand.RandBool()) + Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. + else + Val = Val + Add; // Add assuming current endiannes. + if (Add == 0 || Rand.RandBool()) // Maybe negate. + Val = -Val; + } + memcpy(Data + Off, &Val, sizeof(Val)); + return Size; +} + +size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, + size_t Size, + size_t MaxSize) { + if (Size > MaxSize) + return 0; + switch (Rand(4)) { + case 3: + return ChangeBinaryInteger(Data, Size, Rand); + case 2: + return ChangeBinaryInteger(Data, Size, Rand); + case 1: + return ChangeBinaryInteger(Data, Size, Rand); + case 0: + return ChangeBinaryInteger(Data, Size, Rand); + default: + assert(0); + } + return 0; +} + +size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, + size_t MaxSize) { + if (Size > MaxSize) + return 0; + if (Size == 0) + return 0; + if (!CrossOverWith) + return 0; + const Unit &O = *CrossOverWith; + if (O.empty()) + return 0; + size_t NewSize = 0; + switch (Rand(3)) { + case 0: + MutateInPlaceHere.resize(MaxSize); + NewSize = CrossOver(Data, Size, O.data(), O.size(), + MutateInPlaceHere.data(), MaxSize); + memcpy(Data, MutateInPlaceHere.data(), NewSize); + break; + case 1: + NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize); + if (!NewSize) + NewSize = CopyPartOf(O.data(), O.size(), Data, Size); + break; + case 2: + NewSize = CopyPartOf(O.data(), O.size(), Data, Size); + break; + default: + assert(0); + } + assert(NewSize > 0 && "CrossOver returned empty unit"); + assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); + return NewSize; +} + +void MutationDispatcher::StartMutationSequence() { + CurrentMutatorSequence.clear(); + CurrentDictionaryEntrySequence.clear(); +} + +// Copy successful dictionary entries to PersistentAutoDictionary. +void MutationDispatcher::RecordSuccessfulMutationSequence() { + for (auto *DE : CurrentDictionaryEntrySequence) { + // PersistentAutoDictionary.AddWithSuccessCountOne(DE); + DE->IncSuccessCount(); + assert(DE->GetW().size()); + // Linear search is fine here as this happens seldom. + if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) + PersistentAutoDictionary.push_back(*DE); + } +} + +const Dictionary &MutationDispatcher::RecommendDictionary() { + RecommendedDictionary.clear(); + for (auto &DE : PersistentAutoDictionary) + if (!ManualDictionary.ContainsWord(DE.GetW())) + RecommendedDictionary.push_back(DE); + NextRecommendedDictionaryEntry = 0; + return RecommendedDictionary; +} + +const char *MutationDispatcher::RecommendDictionaryEntry(size_t *UseCount) { + if (NextRecommendedDictionaryEntry >= RecommendedDictionary.size()) + return nullptr; + auto &DE = RecommendedDictionary[NextRecommendedDictionaryEntry++]; + assert(DE.GetW().size()); + DictionaryEntryWord = ToASCII(DE.GetW()); + if (UseCount) + *UseCount = DE.GetUseCount(); + return DictionaryEntryWord.c_str(); +} + +const Sequence & +MutationDispatcher::MutationSequence() { + CurrentMutatorSequence.SetString([](Mutator M) { return M.Name; }); + return CurrentMutatorSequence; +} + +const Sequence & +MutationDispatcher::DictionaryEntrySequence() { + CurrentDictionaryEntrySequence.SetString([](DictionaryEntry *DE) { + return std::string("\"") + ToASCII(DE->GetW()) + std::string("\""); + }); + return CurrentDictionaryEntrySequence; +} + +size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { + return MutateImpl(Data, Size, MaxSize, Mutators); +} + +size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, + size_t MaxSize) { + return MutateImpl(Data, Size, MaxSize, DefaultMutators); +} + +// Mutates Data in place, returns new size. +size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, + size_t MaxSize, + Vector &Mutators) { + assert(MaxSize > 0); + // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), + // in which case they will return 0. + // Try several times before returning un-mutated data. + for (int Iter = 0; Iter < 100; Iter++) { + auto M = Mutators[Rand(Mutators.size())]; + size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); + if (NewSize && NewSize <= MaxSize) { + if (Config.OnlyASCII) + ToASCII(Data, NewSize); + CurrentMutatorSequence.push_back(M); + return NewSize; + } + } + *Data = ' '; + return 1; // Fallback, should not happen frequently. +} + +// Mask represents the set of Data bytes that are worth mutating. +size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size, + size_t MaxSize, + const Vector &Mask) { + size_t MaskedSize = std::min(Size, Mask.size()); + // * Copy the worthy bytes into a temporary array T + // * Mutate T + // * Copy T back. + // This is totally unoptimized. + auto &T = MutateWithMaskTemp; + if (T.size() < Size) + T.resize(Size); + size_t OneBits = 0; + for (size_t I = 0; I < MaskedSize; I++) + if (Mask[I]) + T[OneBits++] = Data[I]; + + if (!OneBits) + return 0; + assert(!T.empty()); + size_t NewSize = Mutate(T.data(), OneBits, OneBits); + assert(NewSize <= OneBits); + (void)NewSize; + // Even if NewSize < OneBits we still use all OneBits bytes. + for (size_t I = 0, J = 0; I < MaskedSize; I++) + if (Mask[I]) + Data[I] = T[J++]; + return Size; +} + +void MutationDispatcher::AddWordToManualDictionary(const Word &W) { + ManualDictionary.push_back({W, std::numeric_limits::max()}); +} + +} // namespace mutagen Index: compiler-rt/lib/fuzzer/mutagen/MutagenSequence.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/MutagenSequence.h @@ -0,0 +1,101 @@ +//===- MutagenSequence.h - Internal header for the mutagen ------*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// mutagen::Sequence +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_MUTAGEN_SEQUENCE_H +#define LLVM_FUZZER_MUTAGEN_SEQUENCE_H + +#include "FuzzerDefs.h" +#include +#include + +namespace mutagen { +namespace { + +using fuzzer::Vector; + +} // namespace + +// The Sequence type bundles together a list of items, a string representation, +// and a position in that string suitable for truncating it when overly long, +// e.g. after the tenth item. +template class Sequence { +public: + constexpr static size_t kMaxBriefItems = 10; + + void clear() { + Items.clear(); + Size = 0; + Str.clear(); + Brief = 0; + } + + bool empty() const { return Size == 0; } + + size_t size() const { return Size; } + + void push_back(T t) { Items.push_back(t); } + + typename Vector::const_iterator begin() const { return Items.begin(); } + typename Vector::iterator begin() { return Items.begin(); } + + typename Vector::const_iterator end() const { return Items.end(); } + typename Vector::iterator end() { return Items.end(); } + + std::string GetString(bool Verbose = true) const { + return Verbose ? Str : Str.substr(0, Brief); + } + + // Constructs the string representation of the sequence, using a callback that + // converts items to strings. + template + // std::string ItemCallback(T Item); + void SetString(ItemCallback ConvertToASCII) { + // No change since last call. + if (Size == Items.size()) + return; + Size = Items.size(); + std::ostringstream OSS; + size_t i = 0; + for (; i < Size && i < kMaxBriefItems; i++) + OSS << ConvertToASCII(Items[i]) << "-"; + Brief = static_cast(OSS.tellp()); + for (; i < Size; i++) + OSS << ConvertToASCII(Items[i]) << "-"; + Str = OSS.str(); + } + +private: + Vector Items; + size_t Size = 0; + std::string Str; + size_t Brief = 0; +}; + +template +typename Vector::const_iterator begin(const Sequence &S) { + return S.begin(); +} + +template typename Vector::iterator begin(Sequence &S) { + return S.begin(); +} + +template +typename Vector::const_iterator end(const Sequence &S) { + return S.end(); +} + +template typename Vector::iterator end(Sequence &S) { + return S.end(); +} + +} // namespace mutagen + +#endif // LLVM_FUZZER_MUTAGEN_SEQUENCE_H Index: compiler-rt/lib/fuzzer/mutagen/MutagenUtil.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/MutagenUtil.h @@ -0,0 +1,24 @@ +//===- MutagenUtil.h - Internal header for the mutagen Utils ----*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Util functions. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_MUTAGEN_UTIL_H +#define LLVM_FUZZER_MUTAGEN_UTIL_H + +#include +#include + +namespace mutagen { + +const void *SearchMemory(const void *haystack, size_t haystacklen, + const void *needle, size_t needlelen); + +} // namespace mutagen + +#endif // LLVM_FUZZER_MUTAGEN_UTIL_H Index: compiler-rt/lib/fuzzer/mutagen/MutagenUtilPosix.cpp =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/MutagenUtilPosix.cpp @@ -0,0 +1,23 @@ +//===- MutagenUtilPosix.cpp - Misc utils for Posix. -----------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Misc utils implementation using Posix API. +//===----------------------------------------------------------------------===// +#include "FuzzerPlatform.h" +#if (LIBFUZZER_POSIX || LIBFUZZER_FUCHSIA) +#include + +namespace mutagen { + +const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt, + size_t PattLen) { + return memmem(Data, DataLen, Patt, PattLen); +} + +} // namespace mutagen + +#endif // (LIBFUZZER_POSIX || LIBFUZZER_FUCHSIA) Index: compiler-rt/lib/fuzzer/mutagen/MutagenUtilWindows.cpp =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/MutagenUtilWindows.cpp @@ -0,0 +1,41 @@ +//===- MutagenUtilWindows.cpp - Misc utils for Windows. -------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Misc utils implementation for Windows. +//===----------------------------------------------------------------------===// +#include "FuzzerPlatform.h" +#if LIBFUZZER_WINDOWS +#include +#include +#include + +namespace mutagen { + +const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt, + size_t PattLen) { + // TODO: make this implementation more efficient. + const char *Cdata = (const char *)Data; + const char *Cpatt = (const char *)Patt; + + if (!Data || !Patt || DataLen == 0 || PattLen == 0 || DataLen < PattLen) + return NULL; + + if (PattLen == 1) + return memchr(Data, *Cpatt, DataLen); + + const char *End = Cdata + DataLen - PattLen + 1; + + for (const char *It = Cdata; It < End; ++It) + if (It[0] == Cpatt[0] && memcmp(It, Cpatt, PattLen) == 0) + return It; + + return NULL; +} + +} // namespace mutagen + +#endif // LIBFUZZER_WINDOWS Index: compiler-rt/lib/fuzzer/mutagen/build.sh =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/mutagen/build.sh @@ -0,0 +1,12 @@ +#!/bin/sh +LIBMUTAGEN_SRC_DIR=$(dirname $0) +LIBFUZZER_SRC_DIR=$LIBMUTAGEN_SRC_DIR/.. +CXX="${CXX:-clang}" +for f in $LIBMUTAGEN_SRC_DIR/*.cpp; do + $CXX -g -O2 -fno-omit-frame-pointer -std=c++11 $f -c -I$LIBFUZZER_SRC_DIR & +done +wait +rm -f libMutagen.a +ar ru libMutagen.a Mutagen*.o +rm -f Mutagen*.o + Index: compiler-rt/lib/fuzzer/tests/CMakeLists.txt =================================================================== --- compiler-rt/lib/fuzzer/tests/CMakeLists.txt +++ compiler-rt/lib/fuzzer/tests/CMakeLists.txt @@ -17,6 +17,9 @@ add_custom_target(FuzzedDataProviderUnitTests) set_target_properties(FuzzedDataProviderUnitTests PROPERTIES FOLDER "Compiler-RT Tests") +add_custom_target(MutagenUnitTests) +set_target_properties(MutagenUnitTests PROPERTIES FOLDER "Compiler-RT Tests") + set(LIBFUZZER_UNITTEST_LINK_FLAGS ${COMPILER_RT_UNITTEST_LINK_FLAGS}) list(APPEND LIBFUZZER_UNITTEST_LINK_FLAGS --driver-mode=g++) @@ -46,19 +49,31 @@ set(arch ${COMPILER_RT_DEFAULT_TARGET_ARCH}) set(LIBFUZZER_TEST_RUNTIME RTFuzzerTest.${arch}) + set(LIBMUTAGEN_TEST_RUNTIME RTMutagenTest.${arch}) if(APPLE) set(LIBFUZZER_TEST_RUNTIME_OBJECTS $) + set(LIBMUTAGEN_TEST_RUNTIME_OBJECTS + $) else() set(LIBFUZZER_TEST_RUNTIME_OBJECTS $) + set(LIBMUTAGEN_TEST_RUNTIME_OBJECTS + $) endif() add_library(${LIBFUZZER_TEST_RUNTIME} STATIC - ${LIBFUZZER_TEST_RUNTIME_OBJECTS}) + ${LIBFUZZER_TEST_RUNTIME_OBJECTS} + ${LIBMUTAGEN_TEST_RUNTIME_OBJECTS}) set_target_properties(${LIBFUZZER_TEST_RUNTIME} PROPERTIES ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} FOLDER "Compiler-RT Runtime tests") + add_library(${LIBMUTAGEN_TEST_RUNTIME} STATIC + ${LIBMUTAGEN_TEST_RUNTIME_OBJECTS}) + set_target_properties(${LIBMUTAGEN_TEST_RUNTIME} PROPERTIES + ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} + FOLDER "Compiler-RT Runtime tests") + if(CMAKE_SYSTEM_NAME STREQUAL "Linux" AND COMPILER_RT_LIBCXX_PATH AND COMPILER_RT_LIBCXXABI_PATH) @@ -66,6 +81,8 @@ set(LIBFUZZER_TEST_RUNTIME_DEPS libcxx_fuzzer_${arch}-build ${libfuzzer_headers}) set(LIBFUZZER_TEST_RUNTIME_CFLAGS -isystem ${LIBCXX_${arch}_PREFIX}/include/c++/v1) set(LIBFUZZER_TEST_RUNTIME_LINK_FLAGS ${LIBCXX_${arch}_PREFIX}/lib/libc++.a) + file(GLOB libmutagen_headers ../mutagen/*.h) + set(LIBMUTAGEN_TEST_RUNTIME_DEPS libcxx_fuzzer_${arch}-build ${libmutagen_headers}) endif() set(FuzzerTestObjects) @@ -73,7 +90,7 @@ FuzzerUnitTests "Fuzzer-${arch}-Test" ${arch} SOURCES FuzzerUnittest.cpp ${COMPILER_RT_GTEST_SOURCE} RUNTIME ${LIBFUZZER_TEST_RUNTIME} - DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} + DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS} LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS}) set_target_properties(FuzzerUnitTests PROPERTIES @@ -88,4 +105,15 @@ LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS}) set_target_properties(FuzzedDataProviderUnitTests PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}) + + set(MutagenTestObjects) + generate_compiler_rt_tests(MutagenTestObjects + MutagenUnitTests "Mutagen-${arch}-Test" ${arch} + SOURCES MutagenUnittest.cpp ${COMPILER_RT_GTEST_SOURCE} + RUNTIME ${LIBFUZZER_TEST_RUNTIME} + DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} ${LIBMUTAGEN_TEST_RUNTIME_DEPS} + CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS} + LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS}) + set_target_properties(MutagenUnitTests PROPERTIES + RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}) endif() Index: compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp =================================================================== --- compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp +++ compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp @@ -10,7 +10,6 @@ #define GTEST_NO_LLVM_SUPPORT 1 #include "FuzzerCorpus.h" -#include "FuzzerDictionary.h" #include "FuzzerInternal.h" #include "FuzzerMerge.h" #include "FuzzerMutate.h" @@ -44,65 +43,6 @@ #endif } -TEST(Fuzzer, CrossOver) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - Unit A({0, 1, 2}), B({5, 6, 7}); - Unit C; - Unit Expected[] = { - { 0 }, - { 0, 1 }, - { 0, 5 }, - { 0, 1, 2 }, - { 0, 1, 5 }, - { 0, 5, 1 }, - { 0, 5, 6 }, - { 0, 1, 2, 5 }, - { 0, 1, 5, 2 }, - { 0, 1, 5, 6 }, - { 0, 5, 1, 2 }, - { 0, 5, 1, 6 }, - { 0, 5, 6, 1 }, - { 0, 5, 6, 7 }, - { 0, 1, 2, 5, 6 }, - { 0, 1, 5, 2, 6 }, - { 0, 1, 5, 6, 2 }, - { 0, 1, 5, 6, 7 }, - { 0, 5, 1, 2, 6 }, - { 0, 5, 1, 6, 2 }, - { 0, 5, 1, 6, 7 }, - { 0, 5, 6, 1, 2 }, - { 0, 5, 6, 1, 7 }, - { 0, 5, 6, 7, 1 }, - { 0, 1, 2, 5, 6, 7 }, - { 0, 1, 5, 2, 6, 7 }, - { 0, 1, 5, 6, 2, 7 }, - { 0, 1, 5, 6, 7, 2 }, - { 0, 5, 1, 2, 6, 7 }, - { 0, 5, 1, 6, 2, 7 }, - { 0, 5, 1, 6, 7, 2 }, - { 0, 5, 6, 1, 2, 7 }, - { 0, 5, 6, 1, 7, 2 }, - { 0, 5, 6, 7, 1, 2 } - }; - for (size_t Len = 1; Len < 8; Len++) { - Set FoundUnits, ExpectedUnitsWitThisLength; - for (int Iter = 0; Iter < 3000; Iter++) { - C.resize(Len); - size_t NewSize = MD->CrossOver(A.data(), A.size(), B.data(), B.size(), - C.data(), C.size()); - C.resize(NewSize); - FoundUnits.insert(C); - } - for (const Unit &U : Expected) - if (U.size() <= Len) - ExpectedUnitsWitThisLength.insert(U); - EXPECT_EQ(ExpectedUnitsWitThisLength, FoundUnits); - } -} - TEST(Fuzzer, Hash) { uint8_t A[] = {'a', 'b', 'c'}; fuzzer::Unit U(A, A + sizeof(A)); @@ -111,423 +51,6 @@ EXPECT_EQ("81fe8bfe87576c3ecb22426f8e57847382917acf", fuzzer::Hash(U)); } -typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size, - size_t MaxSize); - -void TestEraseBytes(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - uint8_t REM0[8] = {0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t REM1[8] = {0x00, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t REM2[8] = {0x00, 0x11, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t REM3[8] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x77}; - uint8_t REM4[8] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x66, 0x77}; - uint8_t REM5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x66, 0x77}; - uint8_t REM6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x77}; - uint8_t REM7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; - - uint8_t REM8[6] = {0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t REM9[6] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55}; - uint8_t REM10[6] = {0x00, 0x11, 0x22, 0x55, 0x66, 0x77}; - - uint8_t REM11[5] = {0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t REM12[5] = {0x00, 0x11, 0x22, 0x33, 0x44}; - uint8_t REM13[5] = {0x00, 0x44, 0x55, 0x66, 0x77}; - - - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - int FoundMask = 0; - for (int i = 0; i < NumIter; i++) { - uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - size_t NewSize = (*MD.*M)(T, sizeof(T), sizeof(T)); - if (NewSize == 7 && !memcmp(REM0, T, 7)) FoundMask |= 1 << 0; - if (NewSize == 7 && !memcmp(REM1, T, 7)) FoundMask |= 1 << 1; - if (NewSize == 7 && !memcmp(REM2, T, 7)) FoundMask |= 1 << 2; - if (NewSize == 7 && !memcmp(REM3, T, 7)) FoundMask |= 1 << 3; - if (NewSize == 7 && !memcmp(REM4, T, 7)) FoundMask |= 1 << 4; - if (NewSize == 7 && !memcmp(REM5, T, 7)) FoundMask |= 1 << 5; - if (NewSize == 7 && !memcmp(REM6, T, 7)) FoundMask |= 1 << 6; - if (NewSize == 7 && !memcmp(REM7, T, 7)) FoundMask |= 1 << 7; - - if (NewSize == 6 && !memcmp(REM8, T, 6)) FoundMask |= 1 << 8; - if (NewSize == 6 && !memcmp(REM9, T, 6)) FoundMask |= 1 << 9; - if (NewSize == 6 && !memcmp(REM10, T, 6)) FoundMask |= 1 << 10; - - if (NewSize == 5 && !memcmp(REM11, T, 5)) FoundMask |= 1 << 11; - if (NewSize == 5 && !memcmp(REM12, T, 5)) FoundMask |= 1 << 12; - if (NewSize == 5 && !memcmp(REM13, T, 5)) FoundMask |= 1 << 13; - } - EXPECT_EQ(FoundMask, (1 << 14) - 1); -} - -TEST(FuzzerMutate, EraseBytes1) { - TestEraseBytes(&MutationDispatcher::Mutate_EraseBytes, 200); -} -TEST(FuzzerMutate, EraseBytes2) { - TestEraseBytes(&MutationDispatcher::Mutate, 2000); -} - -void TestInsertByte(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - int FoundMask = 0; - uint8_t INS0[8] = {0xF1, 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; - uint8_t INS1[8] = {0x00, 0xF2, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; - uint8_t INS2[8] = {0x00, 0x11, 0xF3, 0x22, 0x33, 0x44, 0x55, 0x66}; - uint8_t INS3[8] = {0x00, 0x11, 0x22, 0xF4, 0x33, 0x44, 0x55, 0x66}; - uint8_t INS4[8] = {0x00, 0x11, 0x22, 0x33, 0xF5, 0x44, 0x55, 0x66}; - uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF6, 0x55, 0x66}; - uint8_t INS6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF7, 0x66}; - uint8_t INS7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF8}; - for (int i = 0; i < NumIter; i++) { - uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; - size_t NewSize = (*MD.*M)(T, 7, 8); - if (NewSize == 8 && !memcmp(INS0, T, 8)) FoundMask |= 1 << 0; - if (NewSize == 8 && !memcmp(INS1, T, 8)) FoundMask |= 1 << 1; - if (NewSize == 8 && !memcmp(INS2, T, 8)) FoundMask |= 1 << 2; - if (NewSize == 8 && !memcmp(INS3, T, 8)) FoundMask |= 1 << 3; - if (NewSize == 8 && !memcmp(INS4, T, 8)) FoundMask |= 1 << 4; - if (NewSize == 8 && !memcmp(INS5, T, 8)) FoundMask |= 1 << 5; - if (NewSize == 8 && !memcmp(INS6, T, 8)) FoundMask |= 1 << 6; - if (NewSize == 8 && !memcmp(INS7, T, 8)) FoundMask |= 1 << 7; - } - EXPECT_EQ(FoundMask, 255); -} - -TEST(FuzzerMutate, InsertByte1) { - TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15); -} -TEST(FuzzerMutate, InsertByte2) { - TestInsertByte(&MutationDispatcher::Mutate, 1 << 17); -} - -void TestInsertRepeatedBytes(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - int FoundMask = 0; - uint8_t INS0[7] = {0x00, 0x11, 0x22, 0x33, 'a', 'a', 'a'}; - uint8_t INS1[7] = {0x00, 0x11, 0x22, 'a', 'a', 'a', 0x33}; - uint8_t INS2[7] = {0x00, 0x11, 'a', 'a', 'a', 0x22, 0x33}; - uint8_t INS3[7] = {0x00, 'a', 'a', 'a', 0x11, 0x22, 0x33}; - uint8_t INS4[7] = {'a', 'a', 'a', 0x00, 0x11, 0x22, 0x33}; - - uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 'b', 'b', 'b', 'b'}; - uint8_t INS6[8] = {0x00, 0x11, 0x22, 'b', 'b', 'b', 'b', 0x33}; - uint8_t INS7[8] = {0x00, 0x11, 'b', 'b', 'b', 'b', 0x22, 0x33}; - uint8_t INS8[8] = {0x00, 'b', 'b', 'b', 'b', 0x11, 0x22, 0x33}; - uint8_t INS9[8] = {'b', 'b', 'b', 'b', 0x00, 0x11, 0x22, 0x33}; - - for (int i = 0; i < NumIter; i++) { - uint8_t T[8] = {0x00, 0x11, 0x22, 0x33}; - size_t NewSize = (*MD.*M)(T, 4, 8); - if (NewSize == 7 && !memcmp(INS0, T, 7)) FoundMask |= 1 << 0; - if (NewSize == 7 && !memcmp(INS1, T, 7)) FoundMask |= 1 << 1; - if (NewSize == 7 && !memcmp(INS2, T, 7)) FoundMask |= 1 << 2; - if (NewSize == 7 && !memcmp(INS3, T, 7)) FoundMask |= 1 << 3; - if (NewSize == 7 && !memcmp(INS4, T, 7)) FoundMask |= 1 << 4; - - if (NewSize == 8 && !memcmp(INS5, T, 8)) FoundMask |= 1 << 5; - if (NewSize == 8 && !memcmp(INS6, T, 8)) FoundMask |= 1 << 6; - if (NewSize == 8 && !memcmp(INS7, T, 8)) FoundMask |= 1 << 7; - if (NewSize == 8 && !memcmp(INS8, T, 8)) FoundMask |= 1 << 8; - if (NewSize == 8 && !memcmp(INS9, T, 8)) FoundMask |= 1 << 9; - - } - EXPECT_EQ(FoundMask, (1 << 10) - 1); -} - -TEST(FuzzerMutate, InsertRepeatedBytes1) { - TestInsertRepeatedBytes(&MutationDispatcher::Mutate_InsertRepeatedBytes, 10000); -} -TEST(FuzzerMutate, InsertRepeatedBytes2) { - TestInsertRepeatedBytes(&MutationDispatcher::Mutate, 300000); -} - -void TestChangeByte(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - int FoundMask = 0; - uint8_t CH0[8] = {0xF0, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH1[8] = {0x00, 0xF1, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH2[8] = {0x00, 0x11, 0xF2, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH3[8] = {0x00, 0x11, 0x22, 0xF3, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0xF4, 0x55, 0x66, 0x77}; - uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF5, 0x66, 0x77}; - uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF5, 0x77}; - uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7}; - for (int i = 0; i < NumIter; i++) { - uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - size_t NewSize = (*MD.*M)(T, 8, 9); - if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0; - if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1; - if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2; - if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3; - if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4; - if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5; - if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6; - if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7; - } - EXPECT_EQ(FoundMask, 255); -} - -TEST(FuzzerMutate, ChangeByte1) { - TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15); -} -TEST(FuzzerMutate, ChangeByte2) { - TestChangeByte(&MutationDispatcher::Mutate, 1 << 17); -} - -void TestChangeBit(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - int FoundMask = 0; - uint8_t CH0[8] = {0x01, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH1[8] = {0x00, 0x13, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH2[8] = {0x00, 0x11, 0x02, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH3[8] = {0x00, 0x11, 0x22, 0x37, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x54, 0x55, 0x66, 0x77}; - uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x54, 0x66, 0x77}; - uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x76, 0x77}; - uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7}; - for (int i = 0; i < NumIter; i++) { - uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - size_t NewSize = (*MD.*M)(T, 8, 9); - if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0; - if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1; - if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2; - if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3; - if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4; - if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5; - if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6; - if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7; - } - EXPECT_EQ(FoundMask, 255); -} - -TEST(FuzzerMutate, ChangeBit1) { - TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16); -} -TEST(FuzzerMutate, ChangeBit2) { - TestChangeBit(&MutationDispatcher::Mutate, 1 << 18); -} - -void TestShuffleBytes(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - int FoundMask = 0; - uint8_t CH0[7] = {0x00, 0x22, 0x11, 0x33, 0x44, 0x55, 0x66}; - uint8_t CH1[7] = {0x11, 0x00, 0x33, 0x22, 0x44, 0x55, 0x66}; - uint8_t CH2[7] = {0x00, 0x33, 0x11, 0x22, 0x44, 0x55, 0x66}; - uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x33}; - uint8_t CH4[7] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x44, 0x66}; - for (int i = 0; i < NumIter; i++) { - uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; - size_t NewSize = (*MD.*M)(T, 7, 7); - if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0; - if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1; - if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2; - if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3; - if (NewSize == 7 && !memcmp(CH4, T, 7)) FoundMask |= 1 << 4; - } - EXPECT_EQ(FoundMask, 31); -} - -TEST(FuzzerMutate, ShuffleBytes1) { - TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 17); -} -TEST(FuzzerMutate, ShuffleBytes2) { - TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 20); -} - -void TestCopyPart(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - int FoundMask = 0; - uint8_t CH0[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11}; - uint8_t CH1[7] = {0x55, 0x66, 0x22, 0x33, 0x44, 0x55, 0x66}; - uint8_t CH2[7] = {0x00, 0x55, 0x66, 0x33, 0x44, 0x55, 0x66}; - uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x66}; - uint8_t CH4[7] = {0x00, 0x11, 0x11, 0x22, 0x33, 0x55, 0x66}; - - for (int i = 0; i < NumIter; i++) { - uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; - size_t NewSize = (*MD.*M)(T, 7, 7); - if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0; - if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1; - if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2; - if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3; - if (NewSize == 7 && !memcmp(CH4, T, 7)) FoundMask |= 1 << 4; - } - - uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22}; - uint8_t CH6[8] = {0x22, 0x33, 0x44, 0x00, 0x11, 0x22, 0x33, 0x44}; - uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x33, 0x44}; - uint8_t CH8[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x22, 0x33, 0x44}; - uint8_t CH9[8] = {0x00, 0x11, 0x22, 0x22, 0x33, 0x44, 0x33, 0x44}; - - for (int i = 0; i < NumIter; i++) { - uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - size_t NewSize = (*MD.*M)(T, 5, 8); - if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5; - if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6; - if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7; - if (NewSize == 8 && !memcmp(CH8, T, 8)) FoundMask |= 1 << 8; - if (NewSize == 8 && !memcmp(CH9, T, 8)) FoundMask |= 1 << 9; - } - - EXPECT_EQ(FoundMask, 1023); -} - -TEST(FuzzerMutate, CopyPart1) { - TestCopyPart(&MutationDispatcher::Mutate_CopyPart, 1 << 10); -} -TEST(FuzzerMutate, CopyPart2) { - TestCopyPart(&MutationDispatcher::Mutate, 1 << 13); -} -TEST(FuzzerMutate, CopyPartNoInsertAtMaxSize) { - // This (non exhaustively) tests if `Mutate_CopyPart` tries to perform an - // insert on an input of size `MaxSize`. Performing an insert in this case - // will lead to the mutation failing. - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - uint8_t Data[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22}; - size_t MaxSize = sizeof(Data); - for (int count = 0; count < (1 << 18); ++count) { - size_t NewSize = MD->Mutate_CopyPart(Data, MaxSize, MaxSize); - ASSERT_EQ(NewSize, MaxSize); - } -} - -void TestAddWordFromDictionary(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - uint8_t Word1[4] = {0xAA, 0xBB, 0xCC, 0xDD}; - uint8_t Word2[3] = {0xFF, 0xEE, 0xEF}; - MD->AddWordToManualDictionary(Word(Word1, sizeof(Word1))); - MD->AddWordToManualDictionary(Word(Word2, sizeof(Word2))); - int FoundMask = 0; - uint8_t CH0[7] = {0x00, 0x11, 0x22, 0xAA, 0xBB, 0xCC, 0xDD}; - uint8_t CH1[7] = {0x00, 0x11, 0xAA, 0xBB, 0xCC, 0xDD, 0x22}; - uint8_t CH2[7] = {0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0x11, 0x22}; - uint8_t CH3[7] = {0xAA, 0xBB, 0xCC, 0xDD, 0x00, 0x11, 0x22}; - uint8_t CH4[6] = {0x00, 0x11, 0x22, 0xFF, 0xEE, 0xEF}; - uint8_t CH5[6] = {0x00, 0x11, 0xFF, 0xEE, 0xEF, 0x22}; - uint8_t CH6[6] = {0x00, 0xFF, 0xEE, 0xEF, 0x11, 0x22}; - uint8_t CH7[6] = {0xFF, 0xEE, 0xEF, 0x00, 0x11, 0x22}; - for (int i = 0; i < NumIter; i++) { - uint8_t T[7] = {0x00, 0x11, 0x22}; - size_t NewSize = (*MD.*M)(T, 3, 7); - if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0; - if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1; - if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2; - if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3; - if (NewSize == 6 && !memcmp(CH4, T, 6)) FoundMask |= 1 << 4; - if (NewSize == 6 && !memcmp(CH5, T, 6)) FoundMask |= 1 << 5; - if (NewSize == 6 && !memcmp(CH6, T, 6)) FoundMask |= 1 << 6; - if (NewSize == 6 && !memcmp(CH7, T, 6)) FoundMask |= 1 << 7; - } - EXPECT_EQ(FoundMask, 255); -} - -TEST(FuzzerMutate, AddWordFromDictionary1) { - TestAddWordFromDictionary( - &MutationDispatcher::Mutate_AddWordFromManualDictionary, 1 << 15); -} - -TEST(FuzzerMutate, AddWordFromDictionary2) { - TestAddWordFromDictionary(&MutationDispatcher::Mutate, 1 << 15); -} - -void TestChangeASCIIInteger(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - - uint8_t CH0[8] = {'1', '2', '3', '4', '5', '6', '7', '7'}; - uint8_t CH1[8] = {'1', '2', '3', '4', '5', '6', '7', '9'}; - uint8_t CH2[8] = {'2', '4', '6', '9', '1', '3', '5', '6'}; - uint8_t CH3[8] = {'0', '6', '1', '7', '2', '8', '3', '9'}; - int FoundMask = 0; - for (int i = 0; i < NumIter; i++) { - uint8_t T[8] = {'1', '2', '3', '4', '5', '6', '7', '8'}; - size_t NewSize = (*MD.*M)(T, 8, 8); - /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0; - else if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1; - else if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2; - else if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3; - else if (NewSize == 8) FoundMask |= 1 << 4; - } - EXPECT_EQ(FoundMask, 31); -} - -TEST(FuzzerMutate, ChangeASCIIInteger1) { - TestChangeASCIIInteger(&MutationDispatcher::Mutate_ChangeASCIIInteger, - 1 << 15); -} - -TEST(FuzzerMutate, ChangeASCIIInteger2) { - TestChangeASCIIInteger(&MutationDispatcher::Mutate, 1 << 15); -} - -void TestChangeBinaryInteger(Mutator M, int NumIter) { - std::unique_ptr t(new ExternalFunctions()); - fuzzer::EF = t.get(); - Random Rand(0); - std::unique_ptr MD(new MutationDispatcher(Rand, {})); - - uint8_t CH0[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x79}; - uint8_t CH1[8] = {0x00, 0x11, 0x22, 0x31, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH2[8] = {0xff, 0x10, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH3[8] = {0x00, 0x11, 0x2a, 0x33, 0x44, 0x55, 0x66, 0x77}; - uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x4f, 0x66, 0x77}; - uint8_t CH5[8] = {0xff, 0xee, 0xdd, 0xcc, 0xbb, 0xaa, 0x99, 0x88}; - uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x00, 0x00, 0x00, 0x08, 0x77}; // Size - uint8_t CH7[8] = {0x00, 0x08, 0x00, 0x33, 0x44, 0x55, 0x66, 0x77}; // Sw(Size) - - int FoundMask = 0; - for (int i = 0; i < NumIter; i++) { - uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; - size_t NewSize = (*MD.*M)(T, 8, 8); - /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0; - else if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1; - else if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2; - else if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3; - else if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4; - else if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5; - else if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6; - else if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7; - } - EXPECT_EQ(FoundMask, 255); -} - -TEST(FuzzerMutate, ChangeBinaryInteger1) { - TestChangeBinaryInteger(&MutationDispatcher::Mutate_ChangeBinaryInteger, - 1 << 12); -} - -TEST(FuzzerMutate, ChangeBinaryInteger2) { - TestChangeBinaryInteger(&MutationDispatcher::Mutate, 1 << 15); -} - - TEST(FuzzerDictionary, ParseOneDictionaryEntry) { Unit U; EXPECT_FALSE(ParseOneDictionaryEntry("", &U)); Index: compiler-rt/lib/fuzzer/tests/MutagenUnittest.cpp =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/tests/MutagenUnittest.cpp @@ -0,0 +1,982 @@ +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception + +#include "mutagen/Mutagen.h" +#include "mutagen/MutagenDispatcher.h" +#include "mutagen/MutagenSequence.h" +#include "mutagen/MutagenUtil.h" +#include "gtest/gtest.h" +#include + +// Avoid using fuzzer::ExternalFunctions, since it may not be linked against +// the test binary. +#if defined(__has_feature) +#if __has_feature(memory_sanitizer) +#define HAS_MSAN 1 +#include +#else +#define HAS_MSAN 0 +#endif // __has_feature(memory_sanitizer) +#else +#define HAS_MSAN 0 +#endif // defined(__has_feature) + +namespace mutagen { +namespace { + +using fuzzer::Set; + +std::unique_ptr CreateMutationDispatcher() { + LLVMMutagenConfiguration Config; + memset(&Config, 0, sizeof(Config)); + return std::unique_ptr(new MutationDispatcher(&Config)); +} + +typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size, + size_t MaxSize); + +TEST(MutationDispatcher, CrossOver) { + auto MD = CreateMutationDispatcher(); + Unit A({0, 1, 2}), B({5, 6, 7}); + Unit C; + Unit Expected[] = {{0}, + {0, 1}, + {0, 5}, + {0, 1, 2}, + {0, 1, 5}, + {0, 5, 1}, + {0, 5, 6}, + {0, 1, 2, 5}, + {0, 1, 5, 2}, + {0, 1, 5, 6}, + {0, 5, 1, 2}, + {0, 5, 1, 6}, + {0, 5, 6, 1}, + {0, 5, 6, 7}, + {0, 1, 2, 5, 6}, + {0, 1, 5, 2, 6}, + {0, 1, 5, 6, 2}, + {0, 1, 5, 6, 7}, + {0, 5, 1, 2, 6}, + {0, 5, 1, 6, 2}, + {0, 5, 1, 6, 7}, + {0, 5, 6, 1, 2}, + {0, 5, 6, 1, 7}, + {0, 5, 6, 7, 1}, + {0, 1, 2, 5, 6, 7}, + {0, 1, 5, 2, 6, 7}, + {0, 1, 5, 6, 2, 7}, + {0, 1, 5, 6, 7, 2}, + {0, 5, 1, 2, 6, 7}, + {0, 5, 1, 6, 2, 7}, + {0, 5, 1, 6, 7, 2}, + {0, 5, 6, 1, 2, 7}, + {0, 5, 6, 1, 7, 2}, + {0, 5, 6, 7, 1, 2}}; + for (size_t Len = 1; Len < 8; Len++) { + Set FoundUnits, ExpectedUnitsWitThisLength; + for (int Iter = 0; Iter < 3000; Iter++) { + C.resize(Len); + size_t NewSize = MD->CrossOver(A.data(), A.size(), B.data(), B.size(), + C.data(), C.size()); + C.resize(NewSize); + FoundUnits.insert(C); + } + for (const Unit &U : Expected) + if (U.size() <= Len) + ExpectedUnitsWitThisLength.insert(U); + EXPECT_EQ(ExpectedUnitsWitThisLength, FoundUnits); + } +} + +void TestEraseBytes(Mutator M, int NumIter) { + uint8_t REM0[8] = {0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t REM1[8] = {0x00, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t REM2[8] = {0x00, 0x11, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t REM3[8] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x77}; + uint8_t REM4[8] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x66, 0x77}; + uint8_t REM5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x66, 0x77}; + uint8_t REM6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x77}; + uint8_t REM7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; + + uint8_t REM8[6] = {0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t REM9[6] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55}; + uint8_t REM10[6] = {0x00, 0x11, 0x22, 0x55, 0x66, 0x77}; + + uint8_t REM11[5] = {0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t REM12[5] = {0x00, 0x11, 0x22, 0x33, 0x44}; + uint8_t REM13[5] = {0x00, 0x44, 0x55, 0x66, 0x77}; + + auto MD = CreateMutationDispatcher(); + int FoundMask = 0; + for (int i = 0; i < NumIter; i++) { + uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + size_t NewSize = (*MD.*M)(T, sizeof(T), sizeof(T)); + if (NewSize == 7 && !memcmp(REM0, T, 7)) + FoundMask |= 1 << 0; + if (NewSize == 7 && !memcmp(REM1, T, 7)) + FoundMask |= 1 << 1; + if (NewSize == 7 && !memcmp(REM2, T, 7)) + FoundMask |= 1 << 2; + if (NewSize == 7 && !memcmp(REM3, T, 7)) + FoundMask |= 1 << 3; + if (NewSize == 7 && !memcmp(REM4, T, 7)) + FoundMask |= 1 << 4; + if (NewSize == 7 && !memcmp(REM5, T, 7)) + FoundMask |= 1 << 5; + if (NewSize == 7 && !memcmp(REM6, T, 7)) + FoundMask |= 1 << 6; + if (NewSize == 7 && !memcmp(REM7, T, 7)) + FoundMask |= 1 << 7; + + if (NewSize == 6 && !memcmp(REM8, T, 6)) + FoundMask |= 1 << 8; + if (NewSize == 6 && !memcmp(REM9, T, 6)) + FoundMask |= 1 << 9; + if (NewSize == 6 && !memcmp(REM10, T, 6)) + FoundMask |= 1 << 10; + + if (NewSize == 5 && !memcmp(REM11, T, 5)) + FoundMask |= 1 << 11; + if (NewSize == 5 && !memcmp(REM12, T, 5)) + FoundMask |= 1 << 12; + if (NewSize == 5 && !memcmp(REM13, T, 5)) + FoundMask |= 1 << 13; + } + EXPECT_EQ(FoundMask, (1 << 14) - 1); +} + +TEST(MutationDispatcher, EraseBytes1) { + TestEraseBytes(&MutationDispatcher::Mutate_EraseBytes, 200); +} +TEST(MutationDispatcher, EraseBytes2) { + TestEraseBytes(&MutationDispatcher::Mutate, 2000); +} + +void TestInsertByte(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + int FoundMask = 0; + uint8_t INS0[8] = {0xF1, 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; + uint8_t INS1[8] = {0x00, 0xF2, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; + uint8_t INS2[8] = {0x00, 0x11, 0xF3, 0x22, 0x33, 0x44, 0x55, 0x66}; + uint8_t INS3[8] = {0x00, 0x11, 0x22, 0xF4, 0x33, 0x44, 0x55, 0x66}; + uint8_t INS4[8] = {0x00, 0x11, 0x22, 0x33, 0xF5, 0x44, 0x55, 0x66}; + uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF6, 0x55, 0x66}; + uint8_t INS6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF7, 0x66}; + uint8_t INS7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF8}; + for (int i = 0; i < NumIter; i++) { + uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; + size_t NewSize = (*MD.*M)(T, 7, 8); + if (NewSize == 8 && !memcmp(INS0, T, 8)) + FoundMask |= 1 << 0; + if (NewSize == 8 && !memcmp(INS1, T, 8)) + FoundMask |= 1 << 1; + if (NewSize == 8 && !memcmp(INS2, T, 8)) + FoundMask |= 1 << 2; + if (NewSize == 8 && !memcmp(INS3, T, 8)) + FoundMask |= 1 << 3; + if (NewSize == 8 && !memcmp(INS4, T, 8)) + FoundMask |= 1 << 4; + if (NewSize == 8 && !memcmp(INS5, T, 8)) + FoundMask |= 1 << 5; + if (NewSize == 8 && !memcmp(INS6, T, 8)) + FoundMask |= 1 << 6; + if (NewSize == 8 && !memcmp(INS7, T, 8)) + FoundMask |= 1 << 7; + } + EXPECT_EQ(FoundMask, 255); +} + +TEST(MutationDispatcher, InsertByte1) { + TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15); +} +TEST(MutationDispatcher, InsertByte2) { + TestInsertByte(&MutationDispatcher::Mutate, 1 << 17); +} + +void TestInsertRepeatedBytes(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + int FoundMask = 0; + uint8_t INS0[7] = {0x00, 0x11, 0x22, 0x33, 'a', 'a', 'a'}; + uint8_t INS1[7] = {0x00, 0x11, 0x22, 'a', 'a', 'a', 0x33}; + uint8_t INS2[7] = {0x00, 0x11, 'a', 'a', 'a', 0x22, 0x33}; + uint8_t INS3[7] = {0x00, 'a', 'a', 'a', 0x11, 0x22, 0x33}; + uint8_t INS4[7] = {'a', 'a', 'a', 0x00, 0x11, 0x22, 0x33}; + + uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 'b', 'b', 'b', 'b'}; + uint8_t INS6[8] = {0x00, 0x11, 0x22, 'b', 'b', 'b', 'b', 0x33}; + uint8_t INS7[8] = {0x00, 0x11, 'b', 'b', 'b', 'b', 0x22, 0x33}; + uint8_t INS8[8] = {0x00, 'b', 'b', 'b', 'b', 0x11, 0x22, 0x33}; + uint8_t INS9[8] = {'b', 'b', 'b', 'b', 0x00, 0x11, 0x22, 0x33}; + + for (int i = 0; i < NumIter; i++) { + uint8_t T[8] = {0x00, 0x11, 0x22, 0x33}; + size_t NewSize = (*MD.*M)(T, 4, 8); + if (NewSize == 7 && !memcmp(INS0, T, 7)) + FoundMask |= 1 << 0; + if (NewSize == 7 && !memcmp(INS1, T, 7)) + FoundMask |= 1 << 1; + if (NewSize == 7 && !memcmp(INS2, T, 7)) + FoundMask |= 1 << 2; + if (NewSize == 7 && !memcmp(INS3, T, 7)) + FoundMask |= 1 << 3; + if (NewSize == 7 && !memcmp(INS4, T, 7)) + FoundMask |= 1 << 4; + + if (NewSize == 8 && !memcmp(INS5, T, 8)) + FoundMask |= 1 << 5; + if (NewSize == 8 && !memcmp(INS6, T, 8)) + FoundMask |= 1 << 6; + if (NewSize == 8 && !memcmp(INS7, T, 8)) + FoundMask |= 1 << 7; + if (NewSize == 8 && !memcmp(INS8, T, 8)) + FoundMask |= 1 << 8; + if (NewSize == 8 && !memcmp(INS9, T, 8)) + FoundMask |= 1 << 9; + } + EXPECT_EQ(FoundMask, (1 << 10) - 1); +} + +TEST(MutationDispatcher, InsertRepeatedBytes1) { + TestInsertRepeatedBytes(&MutationDispatcher::Mutate_InsertRepeatedBytes, + 10000); +} +TEST(MutationDispatcher, InsertRepeatedBytes2) { + TestInsertRepeatedBytes(&MutationDispatcher::Mutate, 300000); +} + +void TestChangeByte(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + int FoundMask = 0; + uint8_t CH0[8] = {0xF0, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH1[8] = {0x00, 0xF1, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH2[8] = {0x00, 0x11, 0xF2, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH3[8] = {0x00, 0x11, 0x22, 0xF3, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0xF4, 0x55, 0x66, 0x77}; + uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF5, 0x66, 0x77}; + uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF5, 0x77}; + uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7}; + for (int i = 0; i < NumIter; i++) { + uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + size_t NewSize = (*MD.*M)(T, 8, 9); + if (NewSize == 8 && !memcmp(CH0, T, 8)) + FoundMask |= 1 << 0; + if (NewSize == 8 && !memcmp(CH1, T, 8)) + FoundMask |= 1 << 1; + if (NewSize == 8 && !memcmp(CH2, T, 8)) + FoundMask |= 1 << 2; + if (NewSize == 8 && !memcmp(CH3, T, 8)) + FoundMask |= 1 << 3; + if (NewSize == 8 && !memcmp(CH4, T, 8)) + FoundMask |= 1 << 4; + if (NewSize == 8 && !memcmp(CH5, T, 8)) + FoundMask |= 1 << 5; + if (NewSize == 8 && !memcmp(CH6, T, 8)) + FoundMask |= 1 << 6; + if (NewSize == 8 && !memcmp(CH7, T, 8)) + FoundMask |= 1 << 7; + } + EXPECT_EQ(FoundMask, 255); +} + +TEST(MutationDispatcher, ChangeByte1) { + TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15); +} +TEST(MutationDispatcher, ChangeByte2) { + TestChangeByte(&MutationDispatcher::Mutate, 1 << 17); +} + +void TestChangeBit(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + int FoundMask = 0; + uint8_t CH0[8] = {0x01, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH1[8] = {0x00, 0x13, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH2[8] = {0x00, 0x11, 0x02, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH3[8] = {0x00, 0x11, 0x22, 0x37, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x54, 0x55, 0x66, 0x77}; + uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x54, 0x66, 0x77}; + uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x76, 0x77}; + uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7}; + for (int i = 0; i < NumIter; i++) { + uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + size_t NewSize = (*MD.*M)(T, 8, 9); + if (NewSize == 8 && !memcmp(CH0, T, 8)) + FoundMask |= 1 << 0; + if (NewSize == 8 && !memcmp(CH1, T, 8)) + FoundMask |= 1 << 1; + if (NewSize == 8 && !memcmp(CH2, T, 8)) + FoundMask |= 1 << 2; + if (NewSize == 8 && !memcmp(CH3, T, 8)) + FoundMask |= 1 << 3; + if (NewSize == 8 && !memcmp(CH4, T, 8)) + FoundMask |= 1 << 4; + if (NewSize == 8 && !memcmp(CH5, T, 8)) + FoundMask |= 1 << 5; + if (NewSize == 8 && !memcmp(CH6, T, 8)) + FoundMask |= 1 << 6; + if (NewSize == 8 && !memcmp(CH7, T, 8)) + FoundMask |= 1 << 7; + } + EXPECT_EQ(FoundMask, 255); +} + +TEST(MutationDispatcher, ChangeBit1) { + TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16); +} +TEST(MutationDispatcher, ChangeBit2) { + TestChangeBit(&MutationDispatcher::Mutate, 1 << 18); +} + +void TestShuffleBytes(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + int FoundMask = 0; + uint8_t CH0[7] = {0x00, 0x22, 0x11, 0x33, 0x44, 0x55, 0x66}; + uint8_t CH1[7] = {0x11, 0x00, 0x33, 0x22, 0x44, 0x55, 0x66}; + uint8_t CH2[7] = {0x00, 0x33, 0x11, 0x22, 0x44, 0x55, 0x66}; + uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x33}; + uint8_t CH4[7] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x44, 0x66}; + for (int i = 0; i < NumIter; i++) { + uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; + size_t NewSize = (*MD.*M)(T, 7, 7); + if (NewSize == 7 && !memcmp(CH0, T, 7)) + FoundMask |= 1 << 0; + if (NewSize == 7 && !memcmp(CH1, T, 7)) + FoundMask |= 1 << 1; + if (NewSize == 7 && !memcmp(CH2, T, 7)) + FoundMask |= 1 << 2; + if (NewSize == 7 && !memcmp(CH3, T, 7)) + FoundMask |= 1 << 3; + if (NewSize == 7 && !memcmp(CH4, T, 7)) + FoundMask |= 1 << 4; + } + EXPECT_EQ(FoundMask, 31); +} + +TEST(MutationDispatcher, ShuffleBytes1) { + TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 17); +} +TEST(MutationDispatcher, ShuffleBytes2) { + TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 20); +} + +void TestCopyPart(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + int FoundMask = 0; + uint8_t CH0[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11}; + uint8_t CH1[7] = {0x55, 0x66, 0x22, 0x33, 0x44, 0x55, 0x66}; + uint8_t CH2[7] = {0x00, 0x55, 0x66, 0x33, 0x44, 0x55, 0x66}; + uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x66}; + uint8_t CH4[7] = {0x00, 0x11, 0x11, 0x22, 0x33, 0x55, 0x66}; + + for (int i = 0; i < NumIter; i++) { + uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66}; + size_t NewSize = (*MD.*M)(T, 7, 7); + if (NewSize == 7 && !memcmp(CH0, T, 7)) + FoundMask |= 1 << 0; + if (NewSize == 7 && !memcmp(CH1, T, 7)) + FoundMask |= 1 << 1; + if (NewSize == 7 && !memcmp(CH2, T, 7)) + FoundMask |= 1 << 2; + if (NewSize == 7 && !memcmp(CH3, T, 7)) + FoundMask |= 1 << 3; + if (NewSize == 7 && !memcmp(CH4, T, 7)) + FoundMask |= 1 << 4; + } + + uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22}; + uint8_t CH6[8] = {0x22, 0x33, 0x44, 0x00, 0x11, 0x22, 0x33, 0x44}; + uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x33, 0x44}; + uint8_t CH8[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x22, 0x33, 0x44}; + uint8_t CH9[8] = {0x00, 0x11, 0x22, 0x22, 0x33, 0x44, 0x33, 0x44}; + + for (int i = 0; i < NumIter; i++) { + uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + size_t NewSize = (*MD.*M)(T, 5, 8); + if (NewSize == 8 && !memcmp(CH5, T, 8)) + FoundMask |= 1 << 5; + if (NewSize == 8 && !memcmp(CH6, T, 8)) + FoundMask |= 1 << 6; + if (NewSize == 8 && !memcmp(CH7, T, 8)) + FoundMask |= 1 << 7; + if (NewSize == 8 && !memcmp(CH8, T, 8)) + FoundMask |= 1 << 8; + if (NewSize == 8 && !memcmp(CH9, T, 8)) + FoundMask |= 1 << 9; + } + + EXPECT_EQ(FoundMask, 1023); +} + +TEST(MutationDispatcher, CopyPart1) { + TestCopyPart(&MutationDispatcher::Mutate_CopyPart, 1 << 10); +} +TEST(MutationDispatcher, CopyPart2) { + TestCopyPart(&MutationDispatcher::Mutate, 1 << 13); +} +TEST(MutationDispatcher, CopyPartNoInsertAtMaxSize) { + // This (non exhaustively) tests if `Mutate_CopyPart` tries to perform an + // insert on an input of size `MaxSize`. Performing an insert in this case + // will lead to the mutation failing. + auto MD = CreateMutationDispatcher(); + uint8_t Data[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22}; + size_t MaxSize = sizeof(Data); + for (int count = 0; count < (1 << 18); ++count) { + size_t NewSize = MD->Mutate_CopyPart(Data, MaxSize, MaxSize); + ASSERT_EQ(NewSize, MaxSize); + } +} + +void TestAddWordFromDictionary(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + uint8_t Word1[4] = {0xAA, 0xBB, 0xCC, 0xDD}; + uint8_t Word2[3] = {0xFF, 0xEE, 0xEF}; + MD->AddWordToManualDictionary(Word(Word1, sizeof(Word1))); + MD->AddWordToManualDictionary(Word(Word2, sizeof(Word2))); + int FoundMask = 0; + uint8_t CH0[7] = {0x00, 0x11, 0x22, 0xAA, 0xBB, 0xCC, 0xDD}; + uint8_t CH1[7] = {0x00, 0x11, 0xAA, 0xBB, 0xCC, 0xDD, 0x22}; + uint8_t CH2[7] = {0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0x11, 0x22}; + uint8_t CH3[7] = {0xAA, 0xBB, 0xCC, 0xDD, 0x00, 0x11, 0x22}; + uint8_t CH4[6] = {0x00, 0x11, 0x22, 0xFF, 0xEE, 0xEF}; + uint8_t CH5[6] = {0x00, 0x11, 0xFF, 0xEE, 0xEF, 0x22}; + uint8_t CH6[6] = {0x00, 0xFF, 0xEE, 0xEF, 0x11, 0x22}; + uint8_t CH7[6] = {0xFF, 0xEE, 0xEF, 0x00, 0x11, 0x22}; + for (int i = 0; i < NumIter; i++) { + uint8_t T[7] = {0x00, 0x11, 0x22}; + size_t NewSize = (*MD.*M)(T, 3, 7); + if (NewSize == 7 && !memcmp(CH0, T, 7)) + FoundMask |= 1 << 0; + if (NewSize == 7 && !memcmp(CH1, T, 7)) + FoundMask |= 1 << 1; + if (NewSize == 7 && !memcmp(CH2, T, 7)) + FoundMask |= 1 << 2; + if (NewSize == 7 && !memcmp(CH3, T, 7)) + FoundMask |= 1 << 3; + if (NewSize == 6 && !memcmp(CH4, T, 6)) + FoundMask |= 1 << 4; + if (NewSize == 6 && !memcmp(CH5, T, 6)) + FoundMask |= 1 << 5; + if (NewSize == 6 && !memcmp(CH6, T, 6)) + FoundMask |= 1 << 6; + if (NewSize == 6 && !memcmp(CH7, T, 6)) + FoundMask |= 1 << 7; + } + EXPECT_EQ(FoundMask, 255); +} + +TEST(MutationDispatcher, AddWordFromDictionary1) { + TestAddWordFromDictionary( + &MutationDispatcher::Mutate_AddWordFromManualDictionary, 1 << 15); +} + +TEST(MutationDispatcher, AddWordFromDictionary2) { + TestAddWordFromDictionary(&MutationDispatcher::Mutate, 1 << 15); +} + +void TestChangeASCIIInteger(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + + uint8_t CH0[8] = {'1', '2', '3', '4', '5', '6', '7', '7'}; + uint8_t CH1[8] = {'1', '2', '3', '4', '5', '6', '7', '9'}; + uint8_t CH2[8] = {'2', '4', '6', '9', '1', '3', '5', '6'}; + uint8_t CH3[8] = {'0', '6', '1', '7', '2', '8', '3', '9'}; + int FoundMask = 0; + for (int i = 0; i < NumIter; i++) { + uint8_t T[8] = {'1', '2', '3', '4', '5', '6', '7', '8'}; + size_t NewSize = (*MD.*M)(T, 8, 8); + /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) + FoundMask |= 1 << 0; + else if (NewSize == 8 && !memcmp(CH1, T, 8)) + FoundMask |= 1 << 1; + else if (NewSize == 8 && !memcmp(CH2, T, 8)) + FoundMask |= 1 << 2; + else if (NewSize == 8 && !memcmp(CH3, T, 8)) + FoundMask |= 1 << 3; + else if (NewSize == 8) + FoundMask |= 1 << 4; + } + EXPECT_EQ(FoundMask, 31); +} + +TEST(MutationDispatcher, ChangeASCIIInteger1) { + TestChangeASCIIInteger(&MutationDispatcher::Mutate_ChangeASCIIInteger, + 1 << 15); +} + +TEST(MutationDispatcher, ChangeASCIIInteger2) { + TestChangeASCIIInteger(&MutationDispatcher::Mutate, 1 << 15); +} + +void TestChangeBinaryInteger(Mutator M, int NumIter) { + auto MD = CreateMutationDispatcher(); + + uint8_t CH0[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x79}; + uint8_t CH1[8] = {0x00, 0x11, 0x22, 0x31, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH2[8] = {0xff, 0x10, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH3[8] = {0x00, 0x11, 0x2a, 0x33, 0x44, 0x55, 0x66, 0x77}; + uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x4f, 0x66, 0x77}; + uint8_t CH5[8] = {0xff, 0xee, 0xdd, 0xcc, 0xbb, 0xaa, 0x99, 0x88}; + uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x00, 0x00, 0x00, 0x08, 0x77}; // Size + uint8_t CH7[8] = {0x00, 0x08, 0x00, 0x33, 0x44, 0x55, 0x66, 0x77}; // Sw(Size) + + int FoundMask = 0; + for (int i = 0; i < NumIter; i++) { + uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77}; + size_t NewSize = (*MD.*M)(T, 8, 8); + /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) + FoundMask |= 1 << 0; + else if (NewSize == 8 && !memcmp(CH1, T, 8)) + FoundMask |= 1 << 1; + else if (NewSize == 8 && !memcmp(CH2, T, 8)) + FoundMask |= 1 << 2; + else if (NewSize == 8 && !memcmp(CH3, T, 8)) + FoundMask |= 1 << 3; + else if (NewSize == 8 && !memcmp(CH4, T, 8)) + FoundMask |= 1 << 4; + else if (NewSize == 8 && !memcmp(CH5, T, 8)) + FoundMask |= 1 << 5; + else if (NewSize == 8 && !memcmp(CH6, T, 8)) + FoundMask |= 1 << 6; + else if (NewSize == 8 && !memcmp(CH7, T, 8)) + FoundMask |= 1 << 7; + } + EXPECT_EQ(FoundMask, 255); +} + +TEST(MutationDispatcher, ChangeBinaryInteger1) { + TestChangeBinaryInteger(&MutationDispatcher::Mutate_ChangeBinaryInteger, + 1 << 12); +} + +TEST(MutationDispatcher, ChangeBinaryInteger2) { + TestChangeBinaryInteger(&MutationDispatcher::Mutate, 1 << 15); +} + +// Test fixture for MutagenInterface unit tests. +static const char *kWord1 = "word1"; +static const char *kWord2 = "word2"; + +class MutagenInterface : public ::testing::Test { +protected: + void SetUp() override { + Current = this; + memset(&Config, 0, sizeof(Config)); + + Config.Seed = 1; + + Config.UseCmp = 1; + Config.FromTORC4 = [](size_t Idx, uint32_t *Arg1, uint32_t *Arg2) { + ++(Current->FromTORC4Calls); + *Arg1 = 0x0401; + *Arg2 = 0x0402; + }; + Config.FromTORC8 = [](size_t Idx, uint64_t *Arg1, uint64_t *Arg2) { + ++(Current->FromTORC8Calls); + *Arg1 = 0x0801; + *Arg2 = 0x0802; + }; + Config.FromTORCW = [](size_t Idx, const uint8_t **Data1, size_t *Size1, + const uint8_t **Data2, size_t *Size2) { + ++(Current->FromTORCWCalls); + *Data1 = reinterpret_cast(kWord1); + *Size1 = strlen(kWord1); + *Data2 = reinterpret_cast(kWord2); + *Size2 = strlen(kWord2); + }; + + Config.UseMemmem = 0; + Config.FromMMT = [](size_t Idx, const uint8_t **Data, size_t *Size) { + ++(Current->FromMMTCalls); + *Data = reinterpret_cast(kWord1); + *Size = strlen(kWord1); + }; + + Config.OnlyASCII = 0; + + Config.CustomMutator = [](uint8_t *Data, size_t Size, size_t MaxSize, + unsigned int Seed) { + ++(Current->CustomMutatorCalls); + return LLVMMutagenDefaultMutate(Data, Size, MaxSize); + }; + + Config.CustomCrossOver = + [](const uint8_t *Data1, size_t Size1, const uint8_t *Data2, + size_t Size2, uint8_t *Out, size_t MaxOutSize, unsigned int Seed) { + ++(Current->CustomCrossOverCalls); + auto *MD = GetMutationDispatcherForTest(); + return MD->CrossOver(Data1, Size1, Data2, Size2, Out, MaxOutSize); + }; + +#if HAS_MSAN + Config.MSanUnpoison = __msan_unpoison; + Config.MSanUnpoisonParam = __msan_unpoison_param; +#endif // HAS_MSAN + + U = Unit({1, 2, 3, 4}); + U.reserve(8); + } + + void TearDown() override { + Current = nullptr; + memset(&Config, 0, sizeof(Config)); + LLVMMutagenConfigure(&Config); + } + + LLVMMutagenConfiguration Config; + Unit U; + + size_t FromTORC4Calls = 0; + size_t FromTORC8Calls = 0; + size_t FromTORCWCalls = 0; + size_t FromMMTCalls = 0; + size_t CustomMutatorCalls = 0; + size_t CustomCrossOverCalls = 0; + +private: + static MutagenInterface *Current; +}; + +MutagenInterface *MutagenInterface::Current = nullptr; + +// Unit tests for MutagenInterface. + +TEST_F(MutagenInterface, Configure) { + Config.OnlyASCII = 1; + LLVMMutagenConfigure(&Config); + auto *MD = GetMutationDispatcherForTest(); + ASSERT_NE(MD, nullptr); + + Random Rand1(Config.Seed); + Random &Rand2 = MD->GetRand(); + for (size_t i = 0; i < 10; ++i) + EXPECT_EQ(Rand1(), Rand2()); + + Config.Seed = static_cast( + std::chrono::system_clock::now().time_since_epoch().count()); + Config.OnlyASCII = 0; + LLVMMutagenConfigure(&Config); + MD = GetMutationDispatcherForTest(); + ASSERT_NE(MD, nullptr); + + Random Rand3(Config.Seed); + Random &Rand4 = MD->GetRand(); + for (size_t i = 0; i < 10; ++i) + EXPECT_EQ(Rand3(), Rand4()); +} + +TEST_F(MutagenInterface, UseTORCs) { + // If !UseCmp, none of the TORC/MMT callbacks are called, regardless of + // UseMemmem. + Config.UseCmp = 0; + Config.UseMemmem = 1; + LLVMMutagenConfigure(&Config); + for (size_t i = 0; i < 200; ++i) + LLVMMutagenMutate(U.data(), U.size(), U.capacity()); + EXPECT_EQ(FromTORC4Calls, 0U); + EXPECT_EQ(FromTORC8Calls, 0U); + EXPECT_EQ(FromTORCWCalls, 0U); + EXPECT_EQ(FromMMTCalls, 0U); + + // If UseCmp, but !UseMemmem, only the TORC callbacks are invoked. + Config.UseCmp = 1; + Config.UseMemmem = 0; + LLVMMutagenConfigure(&Config); + for (size_t i = 0; i < 200; ++i) + LLVMMutagenMutate(U.data(), U.size(), U.capacity()); + EXPECT_NE(FromTORC4Calls, 0U); + EXPECT_NE(FromTORC8Calls, 0U); + EXPECT_NE(FromTORCWCalls, 0U); + EXPECT_EQ(FromMMTCalls, 0U); + + // If UseCmp and UseMemmem, all the TORC/MMT callbacks are invoked. + Config.UseCmp = 1; + Config.UseMemmem = 1; + LLVMMutagenConfigure(&Config); + for (size_t i = 0; i < 200; ++i) + LLVMMutagenMutate(U.data(), U.size(), U.capacity()); + EXPECT_NE(FromTORC4Calls, 0U); + EXPECT_NE(FromTORC8Calls, 0U); + EXPECT_NE(FromTORCWCalls, 0U); + EXPECT_NE(FromMMTCalls, 0U); +} + +TEST_F(MutagenInterface, CustomCallbacks) { + // DefaultMutate never selects custom callbacks. + LLVMMutagenConfigure(&Config); + for (size_t i = 0; i < 200; ++i) + LLVMMutagenDefaultMutate(U.data(), U.size(), U.capacity()); + + // Valid. + auto *MD = GetMutationDispatcherForTest(); + EXPECT_EQ(CustomMutatorCalls, 0U); + MD->Mutate_Custom(U.data(), U.size(), U.capacity()); + EXPECT_EQ(CustomMutatorCalls, 1U); + + // Null cross-over input disables CustomCrossOver. + LLVMMutagenSetCrossOverWith(nullptr, 0); + MD->Mutate_CustomCrossOver(U.data(), U.size(), U.capacity()); + EXPECT_EQ(CustomCrossOverCalls, 0U); + + // Zero-length cross-over input disables CustomCrossOver. + Unit CrossOverWith = {4, 3, 2, 1}; + LLVMMutagenSetCrossOverWith(CrossOverWith.data(), 0); + MD->Mutate_CustomCrossOver(U.data(), U.size(), U.capacity()); + EXPECT_EQ(CustomCrossOverCalls, 0U); + + // Valid. + LLVMMutagenSetCrossOverWith(CrossOverWith.data(), CrossOverWith.size()); + MD->Mutate_CustomCrossOver(U.data(), U.size(), U.capacity()); + EXPECT_EQ(CustomCrossOverCalls, 1U); + + // Can mutate without custom callbacks. + Config.CustomMutator = nullptr; + Config.CustomCrossOver = nullptr; + LLVMMutagenConfigure(&Config); + for (size_t i = 0; i < 200; ++i) + LLVMMutagenMutate(U.data(), U.size(), U.capacity()); +} + +TEST_F(MutagenInterface, MutationSequence) { + LLVMMutagenConfigure(&Config); + char Buf[1024]; + size_t NumItems; + + Set Names = { + "ShuffleBytes", "EraseBytes", "InsertBytes", "InsertRepeatedBytes", + "ChangeByte", "ChangeBit", "CopyPart", "ChangeASCIIInt", + "ChangeBinInt", + }; + std::string Name; + std::istringstream ISS; + + // Empty sequences + auto Size = LLVMMutagenGetMutationSequence(true, Buf, sizeof(Buf), &NumItems); + EXPECT_STREQ(Buf, ""); + EXPECT_EQ(Size, 0U); + EXPECT_EQ(NumItems, 0U); + + while (true) { + // Can get size without output parameters. + Size = LLVMMutagenGetMutationSequence(true, nullptr, 0, &NumItems); + if (NumItems > Sequence::kMaxBriefItems) + break; + // !Verbose has no effect for <= 10 items. + EXPECT_EQ(LLVMMutagenGetMutationSequence(false, nullptr, 0, nullptr), Size); + EXPECT_GT(LLVMMutagenDefaultMutate(U.data(), U.size(), U.capacity()), 0U); + } + + // All items are valid. + LLVMMutagenGetMutationSequence(true, Buf, sizeof(Buf), nullptr); + ISS.str(Buf); + size_t N = 0; + while (std::getline(ISS, Name, '-')) { + EXPECT_GT(Names.count(Name), 0U); + ++N; + } + EXPECT_EQ(N, NumItems); + + // !Verbose truncates, but items are still valid. + EXPECT_LT(LLVMMutagenGetMutationSequence(false, Buf, sizeof(Buf), nullptr), + Size); + ISS.str(Buf); + N = 0; + while (std::getline(ISS, Name, '-')) { + EXPECT_GT(Names.count(Name), 0U); + ++N; + } + EXPECT_LT(N, NumItems); + + // Truncated sequence is a prefix of its untruncated equivalent. + std::string Truncated(Buf); + LLVMMutagenGetMutationSequence(true, Buf, sizeof(Buf), &NumItems); + Buf[Truncated.size()] = '\0'; + EXPECT_STREQ(Truncated.c_str(), Buf); + + // Stops at the end of |Buf|, and null terminates. + EXPECT_EQ(LLVMMutagenGetMutationSequence(true, Buf, Size - 1, nullptr), Size); + EXPECT_EQ(strlen(Buf), Size - 2); + + // Clear the sequence. + LLVMMutagenResetSequence(); + EXPECT_EQ(LLVMMutagenGetMutationSequence(true, nullptr, 0, nullptr), 0U); +} + +static uint8_t FromASCIINybble(char C) { + if ('0' <= C && C <= '9') + return static_cast(C - '0'); + if ('A' <= C && C <= 'F') + return static_cast(C - 'A' + 10); + assert('a' <= C && C <= 'f'); + return static_cast(C - 'a' + 10); +} + +static Word FromASCII(const char *DE) { + Unit Tmp; + bool Escape = false; + size_t Hex = 0; + uint8_t Nybble = 0; + for (char C = *DE++; C; C = *DE++) { + if (Hex == 2) { + Nybble = FromASCIINybble(C); + --Hex; + } else if (Hex == 1) { + Tmp.push_back(static_cast(Nybble << 4) | FromASCIINybble(C)); + --Hex; + } else if (Escape) { + switch (C) { + case '\\': + case '"': + Tmp.push_back(static_cast(C)); + break; + case 'x': + Hex = 2; + break; + default: + assert(false && "FromASCII failure."); + } + Escape = false; + } else if (C == '\\') { + Escape = true; + } else { + Tmp.push_back(static_cast(C)); + } + } + return Word(Tmp.data(), Tmp.size()); +} + +TEST_F(MutagenInterface, Dictionaries) { + LLVMMutagenConfigure(&Config); + size_t NumItems; + char Buf[1024]; + std::istringstream ISS; + std::string Str; + + // Empty sequences + auto Size = + LLVMMutagenGetDictionaryEntrySequence(true, Buf, sizeof(Buf), &NumItems); + EXPECT_STREQ(Buf, ""); + EXPECT_EQ(Size, 0U); + EXPECT_EQ(NumItems, 0U); + + auto *MD = GetMutationDispatcherForTest(); + while (true) { + // Can get size without output parameters. + Size = LLVMMutagenGetDictionaryEntrySequence(true, nullptr, 0, &NumItems); + if (NumItems > Sequence::kMaxBriefItems) + break; + // !Verbose has no effect for <= 10 items. + EXPECT_EQ(LLVMMutagenGetDictionaryEntrySequence(false, nullptr, 0, nullptr), + Size); + MD->Mutate_AddWordFromTORC(U.data(), U.size(), U.capacity()); + } + + // All items are valid. + LLVMMutagenGetDictionaryEntrySequence(true, Buf, sizeof(Buf), nullptr); + ISS.str(Buf); + size_t N = 0; + while (std::getline(ISS, Str, '-')) { + ASSERT_FALSE(Str.empty()); + EXPECT_EQ(Str[0], '"'); + EXPECT_EQ(Str[Str.size() - 1], '"'); + ++N; + } + EXPECT_EQ(N, NumItems); + + // !Verbose truncates, but items are still valid. + EXPECT_LT( + LLVMMutagenGetDictionaryEntrySequence(false, Buf, sizeof(Buf), nullptr), + Size); + ISS.str(Buf); + N = 0; + while (std::getline(ISS, Str, '-')) { + ASSERT_FALSE(Str.empty()); + EXPECT_EQ(Str[0], '"'); + EXPECT_EQ(Str[Str.size() - 1], '"'); + ++N; + } + EXPECT_LT(N, NumItems); + + // Truncated sequence is a prefix of its untruncated equivalent. + std::string Truncated(Buf); + LLVMMutagenGetDictionaryEntrySequence(true, Buf, sizeof(Buf), &NumItems); + Buf[Truncated.size()] = '\0'; + EXPECT_STREQ(Truncated.c_str(), Buf); + + // Stops at the end of |Buf|, and null terminates. + EXPECT_EQ(LLVMMutagenGetDictionaryEntrySequence(true, Buf, Size - 1, nullptr), + Size); + EXPECT_EQ(strlen(Buf), Size - 2); + + // Clear the sequence. + LLVMMutagenResetSequence(); + EXPECT_EQ(LLVMMutagenGetDictionaryEntrySequence(true, nullptr, 0, nullptr), + 0U); + + // Retuns null if no recommendations. + size_t UseCount = 0; + EXPECT_EQ(LLVMMutagenRecommendDictionaryEntry(&UseCount), nullptr); + EXPECT_EQ(LLVMMutagenRecommendDictionary(), 0U); + EXPECT_EQ(LLVMMutagenRecommendDictionaryEntry(&UseCount), nullptr); + + // Record sequences. + for (size_t i = 0; i < 5; ++i) { + for (size_t i = 0; i < 5; ++i) { + MD->Mutate_AddWordFromTORC(U.data(), U.size(), U.capacity()); + } + LLVMMutagenRecordSequence(); + } + + size_t NumDEs = LLVMMutagenRecommendDictionary(); + EXPECT_NE(NumDEs, 0U); + for (size_t i = 0; i < NumDEs; ++i) { + auto *DE = LLVMMutagenRecommendDictionaryEntry(&UseCount); + EXPECT_NE(DE, nullptr); + EXPECT_EQ(UseCount, 0U); + } + + // Increment the use counts of entries. + for (size_t i = 0; i < 100; ++i) + MD->Mutate_AddWordFromPersistentAutoDictionary(U.data(), U.size(), + U.capacity()); + NumDEs = LLVMMutagenRecommendDictionary(); + EXPECT_NE(NumDEs, 0U); + for (size_t i = 0; i < NumDEs; ++i) { + auto *DE = LLVMMutagenRecommendDictionaryEntry(&UseCount); + EXPECT_NE(DE, nullptr); + EXPECT_NE(UseCount, 0U); + } + + // Add the first few words manually to exclude them from recommendations. + Vector ManualAdditions; + NumDEs = LLVMMutagenRecommendDictionary(); + ASSERT_GT(NumDEs, 3U); + for (size_t i = 0; i < 3; ++i) { + auto *DE = LLVMMutagenRecommendDictionaryEntry(nullptr); + auto W = FromASCII(DE); + LLVMMutagenAddWordToDictionary(W.data(), W.size()); + ManualAdditions.push_back(W); + } + N = NumDEs; + + // Get the recommended dictionary without the manual additions. + NumDEs = LLVMMutagenRecommendDictionary(); + EXPECT_EQ(NumDEs, N - 3); + for (size_t i = 0; i < NumDEs; ++i) { + auto *DE = LLVMMutagenRecommendDictionaryEntry(nullptr); + ASSERT_NE(DE, nullptr); + Word W1(reinterpret_cast(DE), strlen(DE)); + for (const auto &W2 : ManualAdditions) + EXPECT_FALSE(W1 == W2); + } +} + +} // namespace +} // namespace mutagen + +#undef HAS_MSAN + +int main(int argc, char **argv) { + testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} Index: compiler-rt/test/fuzzer/CMakeLists.txt =================================================================== --- compiler-rt/test/fuzzer/CMakeLists.txt +++ compiler-rt/test/fuzzer/CMakeLists.txt @@ -20,6 +20,7 @@ if(COMPILER_RT_INCLUDE_TESTS) list(APPEND LIBFUZZER_TEST_DEPS FuzzerUnitTests) list(APPEND LIBFUZZER_TEST_DEPS FuzzedDataProviderUnitTests) + list(APPEND LIBFUZZER_TEST_DEPS MutagenUnitTests) endif() add_custom_target(check-fuzzer)