From a1e5f35b029913c6226795f4c421693cfc68629e Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Sat, 19 Dec 2015 02:49:09 +0000 Subject: [PATCH] [libFuzzer] make CrossOver just one of the other mutations git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@256081 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerInterface.h | 9 ++++++ lib/Fuzzer/FuzzerInternal.h | 3 +- lib/Fuzzer/FuzzerLoop.cpp | 47 ++++++++++++------------------ lib/Fuzzer/FuzzerMutate.cpp | 23 +++++++++++++++ lib/Fuzzer/test/FuzzerUnittest.cpp | 2 +- lib/Fuzzer/test/fuzzer.test | 12 ++++---- 6 files changed, 58 insertions(+), 38 deletions(-) diff --git a/lib/Fuzzer/FuzzerInterface.h b/lib/Fuzzer/FuzzerInterface.h index 329e3a9b1e6..65f1707ba92 100644 --- a/lib/Fuzzer/FuzzerInterface.h +++ b/lib/Fuzzer/FuzzerInterface.h @@ -22,6 +22,7 @@ #include namespace fuzzer { +typedef std::vector Unit; /// Returns an int 0. Values other than zero are reserved for future. typedef int (*UserCallback)(const uint8_t *Data, size_t Size); @@ -89,8 +90,12 @@ class MutationDispatcher { size_t Mutate_AddWordFromDictionary(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); + /// CrossOver Data with some other element of the corpus. + size_t Mutate_CrossOver(uint8_t *Data, size_t Size, size_t MaxSize); + /// Applies one of the above 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); @@ -100,6 +105,7 @@ class MutationDispatcher { size_t Size2, uint8_t *Out, size_t MaxOutSize); void AddWordToDictionary(const uint8_t *Word, size_t Size); + void SetCorpus(const std::vector *Corpus); private: FuzzerRandomBase &Rand; @@ -144,6 +150,9 @@ class UserSuppliedFuzzer { virtual int TargetFunction(const uint8_t *Data, size_t Size) = 0; virtual void StartMutationSequence() { MD.StartMutationSequence(); } virtual void PrintMutationSequence() { MD.PrintMutationSequence(); } + virtual void SetCorpus(const std::vector *Corpus) { + MD.SetCorpus(Corpus); + } /// Mutates 'Size' bytes of data in 'Data' inplace into up to 'MaxSize' bytes, /// returns the new size of the data, which should be positive. virtual size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index bc6bec7473d..e96a4bc35fe 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -24,7 +24,6 @@ #include "FuzzerInterface.h" namespace fuzzer { -typedef std::vector Unit; using namespace std::chrono; std::string FileToString(const std::string &Path); @@ -132,7 +131,7 @@ class Fuzzer { private: void AlarmCallback(); - void MutateAndTestOne(Unit *U); + void MutateAndTestOne(); void ReportNewCoverage(const Unit &U); bool RunOne(const Unit &U); void RunOneAndUpdateCorpus(Unit &U); diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index b1ce294b972..7ea82f4f15d 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -367,29 +367,34 @@ void Fuzzer::Merge(const std::vector &Corpora) { Printf("Merge: written %zd out of %zd units\n", NumMerged, NumTried); } -void Fuzzer::MutateAndTestOne(Unit *U) { +void Fuzzer::MutateAndTestOne() { + auto &U = CurrentUnit; + USF.StartMutationSequence(); + + U = ChooseUnitToMutate(); + for (int i = 0; i < Options.MutateDepth; i++) { StartTraceRecording(); - size_t Size = U->size(); - U->resize(Options.MaxLen); - size_t NewSize = USF.Mutate(U->data(), Size, U->size()); + size_t Size = U.size(); + U.resize(Options.MaxLen); + size_t NewSize = USF.Mutate(U.data(), Size, U.size()); assert(NewSize > 0 && "Mutator returned empty unit"); assert(NewSize <= (size_t)Options.MaxLen && "Mutator return overisized unit"); - U->resize(NewSize); - RunOneAndUpdateCorpus(*U); + U.resize(NewSize); + RunOneAndUpdateCorpus(U); size_t NumTraceBasedMutations = StopTraceRecording(); size_t TBMWidth = std::min((size_t)Options.TBMWidth, NumTraceBasedMutations); size_t TBMDepth = std::min((size_t)Options.TBMDepth, NumTraceBasedMutations); - Unit BackUp = *U; + Unit BackUp = U; for (size_t w = 0; w < TBMWidth; w++) { - *U = BackUp; + U = BackUp; for (size_t d = 0; d < TBMDepth; d++) { TotalNumberOfExecutedTraceBasedMutations++; - ApplyTraceBasedMutation(USF.GetRand()(NumTraceBasedMutations), U); - RunOneAndUpdateCorpus(*U); + ApplyTraceBasedMutation(USF.GetRand()(NumTraceBasedMutations), &U); + RunOneAndUpdateCorpus(U); } } } @@ -465,8 +470,9 @@ void Fuzzer::Drill() { void Fuzzer::Loop() { system_clock::time_point LastCorpusReload = system_clock::now(); + if (Options.DoCrossOver) + USF.SetCorpus(&Corpus); while (true) { - size_t J1 = ChooseUnitIdxToMutate();; SyncCorpus(); auto Now = system_clock::now(); if (duration_cast(Now - LastCorpusReload).count()) { @@ -479,25 +485,8 @@ void Fuzzer::Loop() { secondsSinceProcessStartUp() > static_cast(Options.MaxTotalTimeSec)) break; - USF.StartMutationSequence(); - CurrentUnit = Corpus[J1]; - // Optionally, cross with another unit. - if (Options.DoCrossOver && USF.GetRand().RandBool()) { - size_t J2 = ChooseUnitIdxToMutate(); - if (!Corpus[J1].empty() && !Corpus[J2].empty()) { - assert(!Corpus[J2].empty()); - CurrentUnit.resize(Options.MaxLen); - size_t NewSize = USF.CrossOver( - Corpus[J1].data(), Corpus[J1].size(), Corpus[J2].data(), - Corpus[J2].size(), CurrentUnit.data(), CurrentUnit.size()); - assert(NewSize > 0 && "CrossOver returned empty unit"); - assert(NewSize <= (size_t)Options.MaxLen && - "CrossOver returned overisized unit"); - CurrentUnit.resize(NewSize); - } - } // Perform several mutations and runs. - MutateAndTestOne(&CurrentUnit); + MutateAndTestOne(); } PrintStats("DONE ", "\n"); diff --git a/lib/Fuzzer/FuzzerMutate.cpp b/lib/Fuzzer/FuzzerMutate.cpp index 471ae6ce197..c3fa37a435d 100644 --- a/lib/Fuzzer/FuzzerMutate.cpp +++ b/lib/Fuzzer/FuzzerMutate.cpp @@ -26,6 +26,7 @@ struct MutationDispatcher::Impl { std::vector Dictionary; std::vector Mutators; std::vector CurrentMutatorSequence; + const std::vector *Corpus = nullptr; void Add(Mutator M) { Mutators.push_back(M); } Impl() { @@ -35,6 +36,7 @@ struct MutationDispatcher::Impl { Add({&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}); Add({&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}); Add({&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}); + Add({&MutationDispatcher::Mutate_CrossOver, "CrossOver"}); } void AddWordToDictionary(const uint8_t *Word, size_t Size) { if (Dictionary.empty()) { @@ -42,6 +44,7 @@ struct MutationDispatcher::Impl { } Dictionary.push_back(Unit(Word, Word + Size)); } + void SetCorpus(const std::vector *Corpus) { this->Corpus = Corpus; } }; static char FlipRandomBit(char X, FuzzerRandomBase &Rand) { @@ -154,6 +157,22 @@ size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, return Size; } +size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, + size_t MaxSize) { + auto Corpus = MDImpl->Corpus; + if (!Corpus || Corpus->size() < 2 || Size == 0) return 0; + size_t Idx = Rand(Corpus->size()); + const Unit &Other = (*Corpus)[Idx]; + if (Other.empty()) return 0; + Unit U(MaxSize); + size_t NewSize = + CrossOver(Data, Size, Other.data(), Other.size(), U.data(), U.size()); + assert(NewSize > 0 && "CrossOver returned empty unit"); + assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); + memcpy(Data, U.data(), NewSize); + return NewSize; +} + void MutationDispatcher::StartMutationSequence() { MDImpl->CurrentMutatorSequence.clear(); } @@ -189,6 +208,10 @@ size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { return Size; } +void MutationDispatcher::SetCorpus(const std::vector *Corpus) { + MDImpl->SetCorpus(Corpus); +} + void MutationDispatcher::AddWordToDictionary(const uint8_t *Word, size_t Size) { MDImpl->AddWordToDictionary(Word, Size); } diff --git a/lib/Fuzzer/test/FuzzerUnittest.cpp b/lib/Fuzzer/test/FuzzerUnittest.cpp index b92e61877c6..8c0012708af 100644 --- a/lib/Fuzzer/test/FuzzerUnittest.cpp +++ b/lib/Fuzzer/test/FuzzerUnittest.cpp @@ -239,7 +239,7 @@ TEST(FuzzerMutate, ShuffleBytes1) { TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 15); } TEST(FuzzerMutate, ShuffleBytes2) { - TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 16); + TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 19); } void TestAddWordFromDictionary(Mutator M, int NumIter) { diff --git a/lib/Fuzzer/test/fuzzer.test b/lib/Fuzzer/test/fuzzer.test index 6515628d108..206b99e5b9f 100644 --- a/lib/Fuzzer/test/fuzzer.test +++ b/lib/Fuzzer/test/fuzzer.test @@ -41,10 +41,10 @@ RUN: rm -rf FourIndependentBranchesTestCORPUS RUN: not LLVMFuzzer-CounterTest -use_counters=1 -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s -RUN: not LLVMFuzzer-CallerCalleeTest -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s -RUN: LLVMFuzzer-CallerCalleeTest -use_indir_calls=0 -max_len=6 -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 +RUN: not LLVMFuzzer-CallerCalleeTest -cross_over=0 -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s +RUN: LLVMFuzzer-CallerCalleeTest -use_indir_calls=0 -cross_over=0 -max_len=6 -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: not LLVMFuzzer-SimpleCmpTest -use_traces=1 -seed=1 -runs=1000000 -timeout=5 2>&1 | FileCheck %s +RUN: not LLVMFuzzer-SimpleCmpTest -use_traces=1 -seed=1 -runs=1000001 -timeout=5 2>&1 | FileCheck %s RUN: not LLVMFuzzer-UserSuppliedFuzzerTest -seed=1 -timeout=15 2>&1 | FileCheck %s @@ -55,13 +55,13 @@ Done1000000: Done 1000000 runs in RUN: not LLVMFuzzer-StrncmpTest -use_traces=1 -seed=1 -runs=100000 2>&1 | FileCheck %s RUN: LLVMFuzzer-StrncmpTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: not LLVMFuzzer-StrcmpTest -use_traces=1 -seed=1 -runs=100000 2>&1 | FileCheck %s +RUN: not LLVMFuzzer-StrcmpTest -use_traces=1 -seed=1 -runs=200000 2>&1 | FileCheck %s RUN: LLVMFuzzer-StrcmpTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: not LLVMFuzzer-SwitchTest -use_traces=1 -seed=1 -runs=1000000 2>&1 | FileCheck %s +RUN: not LLVMFuzzer-SwitchTest -use_traces=1 -seed=1 -runs=1000002 2>&1 | FileCheck %s RUN: LLVMFuzzer-SwitchTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: not LLVMFuzzer-SimpleDictionaryTest -dict=%S/dict1.txt -seed=1 -runs=1000000 2>&1 | FileCheck %s +RUN: not LLVMFuzzer-SimpleDictionaryTest -dict=%S/dict1.txt -seed=1 -runs=1000003 2>&1 | FileCheck %s RUN: LLVMFuzzer-SimpleDictionaryTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 RUN: not LLVMFuzzer-SimpleHashTest -use_traces=1 -seed=1 -runs=100000 2>&1 | FileCheck %s -- 2.34.1