From e9b850b5c5fa772293b043769265b46c183ccddd Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Thu, 22 Sep 2016 01:34:58 +0000 Subject: [PATCH] [libFuzzer] add 'features' to the corpus elements, allow mutations with Size > MaxSize, fix sha1 in corpus stats; various refactorings git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@282129 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerCorpus.h | 22 ++++++++++++++-------- lib/Fuzzer/FuzzerDriver.cpp | 2 +- lib/Fuzzer/FuzzerInternal.h | 2 +- lib/Fuzzer/FuzzerLoop.cpp | 37 ++++++++++++++++++++++--------------- lib/Fuzzer/FuzzerMutate.cpp | 17 ++++++++++++----- lib/Fuzzer/FuzzerTracePC.cpp | 4 ++-- lib/Fuzzer/FuzzerTracePC.h | 24 +++++++++++++----------- lib/Fuzzer/test/FuzzerUnittest.cpp | 2 +- 8 files changed, 66 insertions(+), 44 deletions(-) diff --git a/lib/Fuzzer/FuzzerCorpus.h b/lib/Fuzzer/FuzzerCorpus.h index 5a8581f8200..d1a3efebe2d 100644 --- a/lib/Fuzzer/FuzzerCorpus.h +++ b/lib/Fuzzer/FuzzerCorpus.h @@ -26,6 +26,9 @@ struct InputInfo { // Stats. uintptr_t NumExecutedMutations = 0; uintptr_t NumSuccessfullMutations = 0; + + // A set of features (PCIDs, etc) that were first found with this unit. + std::vector Features; }; class InputCorpus { @@ -36,13 +39,15 @@ class InputCorpus { size_t size() const { return Inputs.size(); } bool empty() const { return Inputs.empty(); } const Unit &operator[] (size_t Idx) const { return Inputs[Idx].U; } - void AddToCorpus(const Unit &U) { - auto H = Hash(U); - if (!Hashes.insert(H).second) return; - InputInfo II; + void AddToCorpus(const Unit &U, uintptr_t *Features, size_t NumFeatures) { + uint8_t Hash[kSHA1NumBytes]; + ComputeSHA1(U.data(), U.size(), Hash); + if (!Hashes.insert(Sha1ToString(Hash)).second) return; + Inputs.push_back(InputInfo()); + InputInfo &II = Inputs.back(); II.U = U; - memcpy(II.Sha1, H.data(), kSHA1NumBytes); - Inputs.push_back(II); + II.Features.insert(II.Features.begin(), Features, Features + NumFeatures); + memcpy(II.Sha1, Hash, kSHA1NumBytes); UpdateCorpusDistribution(); } @@ -67,9 +72,10 @@ class InputCorpus { void PrintStats() { for (size_t i = 0; i < Inputs.size(); i++) { const auto &II = Inputs[i]; - Printf(" [%zd %s]\tsz: %zd\truns: %zd\tsucc: %zd\n", i, + Printf(" [%zd %s]\tsz: %zd\truns: %zd\tsucc: %zd\tfea: %zd\n", i, Sha1ToString(II.Sha1).c_str(), II.U.size(), - II.NumExecutedMutations, II.NumSuccessfullMutations); + II.NumExecutedMutations, II.NumSuccessfullMutations, + II.Features.size()); } } diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index 99cc3682464..f7896eb973f 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -346,7 +346,7 @@ int MinimizeCrashInputInternalStep(Fuzzer *F, InputCorpus *Corpus) { for (size_t I = 0; I < U.size(); I++) { std::copy(U.begin(), U.begin() + I, X.begin()); std::copy(U.begin() + I + 1, U.end(), X.begin() + I); - Corpus->AddToCorpus(X); + Corpus->AddToCorpus(X, nullptr, 0); } F->SetMaxLen(U.size() - 1); F->Loop(); diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index 3142aac1187..ccb583c1ad0 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -159,7 +159,7 @@ private: FuzzingOptions Options; system_clock::time_point ProcessStartTime = system_clock::now(); - system_clock::time_point UnitStartTime; + system_clock::time_point UnitStartTime, UnitStopTime; long TimeOfLongestUnitInSeconds = 0; long EpochOfLastReadOfOutputCorpus = 0; diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index 78063085726..0955254ca67 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -68,7 +68,7 @@ void Fuzzer::ResetCounters() { } if (EF->__sanitizer_get_coverage_pc_buffer_pos) PcBufferPos = EF->__sanitizer_get_coverage_pc_buffer_pos(); - TPC.GetNewPCsAndFlush(); + TPC.ResetNewPCIDs(); } void Fuzzer::PrepareCounters(Fuzzer::Coverage *C) { @@ -111,7 +111,6 @@ bool Fuzzer::RecordMaxCoverage(Fuzzer::Coverage *C) { Res = true; C->CounterBitmapBits += CounterDelta; } - } size_t NewVPMapBits = VPMapMergeFromCurrent(C->VPMap); @@ -369,7 +368,9 @@ void Fuzzer::RereadOutputCorpus(size_t MaxSize) { X.resize(MaxSize); if (!Corpus.HasUnit(X)) { if (RunOne(X)) { - Corpus.AddToCorpus(X); + uintptr_t *NewPCIDs; + size_t NumNewPCIDs = TPC.GetNewPCIDs(&NewPCIDs); + Corpus.AddToCorpus(X, NewPCIDs, NumNewPCIDs); PrintStats("RELOAD"); } } @@ -392,7 +393,9 @@ void Fuzzer::ShuffleAndMinimize(UnitVector *InitialCorpus) { for (const auto &U : *InitialCorpus) { bool NewCoverage = RunOne(U); if (!Options.PruneCorpus || NewCoverage) { - Corpus.AddToCorpus(U); + uintptr_t *NewPCIDs; + size_t NumNewPCIDs = TPC.GetNewPCIDs(&NewPCIDs); + Corpus.AddToCorpus(U, NewPCIDs, NumNewPCIDs); if (Options.Verbosity >= 2) Printf("NEW0: %zd L %zd\n", MaxCoverage.BlockCoverage, U.size()); } @@ -420,13 +423,12 @@ bool Fuzzer::RunOne(const uint8_t *Data, size_t Size) { ExecuteCallback(Data, Size); bool Res = UpdateMaxCoverage(); - auto UnitStopTime = system_clock::now(); auto TimeOfUnit = duration_cast(UnitStopTime - UnitStartTime).count(); if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && secondsSinceProcessStartUp() >= 2) PrintStats("pulse "); - if (TimeOfUnit > TimeOfLongestUnitInSeconds && + if (TimeOfUnit > TimeOfLongestUnitInSeconds * 1.1 && TimeOfUnit >= Options.ReportSlowUnits) { TimeOfLongestUnitInSeconds = TimeOfUnit; Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds); @@ -444,7 +446,6 @@ size_t Fuzzer::GetCurrentUnitInFuzzingThead(const uint8_t **Data) const { void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) { assert(InFuzzingThread()); LazyAllocateCurrentUnitData(); - UnitStartTime = system_clock::now(); // We copy the contents of Unit into a separate heap buffer // so that we reliably find buffer overflows in it. uint8_t *DataCopy = new uint8_t[Size]; @@ -454,12 +455,14 @@ void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) { AssignTaintLabels(DataCopy, Size); CurrentUnitSize = Size; AllocTracer.Start(); + UnitStartTime = system_clock::now(); ResetCounters(); // Reset coverage right before the callback. int Res = CB(DataCopy, Size); + UnitStopTime = system_clock::now(); (void)Res; + assert(Res == 0); HasMoreMallocsThanFrees = AllocTracer.Stop(); CurrentUnitSize = 0; - assert(Res == 0); delete[] DataCopy; } @@ -522,15 +525,17 @@ void Fuzzer::PrintNewPCs() { PrintOneNewPC(PcBuffer[I]); } } - uintptr_t *PCs; - if (size_t NumNewPCs = TPC.GetNewPCsAndFlush(&PCs)) - for (size_t i = 0; i < NumNewPCs; i++) - PrintOneNewPC(PCs[i]); + uintptr_t *PCIDs; + if (size_t NumNewPCIDs = TPC.GetNewPCIDs(&PCIDs)) + for (size_t i = 0; i < NumNewPCIDs; i++) + PrintOneNewPC(TPC.GetPCbyPCID(PCIDs[i])); } void Fuzzer::ReportNewCoverage(InputInfo *II, const Unit &U) { II->NumSuccessfullMutations++; - Corpus.AddToCorpus(U); + uintptr_t *NewPCIDs; + size_t NumNewPCIDs = TPC.GetNewPCIDs(&NewPCIDs); + Corpus.AddToCorpus(U, NewPCIDs, NumNewPCIDs); MD.RecordSuccessfulMutationSequence(); PrintStatusForNewUnit(U); WriteToOutputCorpus(U); @@ -651,13 +656,15 @@ void Fuzzer::MutateAndTestOne() { assert(Size <= Options.MaxLen && "Oversized Unit"); memcpy(CurrentUnitData, U.data(), Size); + size_t MaxLen = Options.MaxLen; + for (int i = 0; i < Options.MutateDepth; i++) { if (TotalNumberOfRuns >= Options.MaxNumberOfRuns) break; size_t NewSize = 0; - NewSize = MD.Mutate(CurrentUnitData, Size, Options.MaxLen); + NewSize = MD.Mutate(CurrentUnitData, Size, MaxLen); assert(NewSize > 0 && "Mutator returned empty unit"); - assert(NewSize <= Options.MaxLen && "Mutator return overisized unit"); + assert(NewSize <= MaxLen && "Mutator return overisized unit"); Size = NewSize; if (i == 0) StartTraceRecording(); diff --git a/lib/Fuzzer/FuzzerMutate.cpp b/lib/Fuzzer/FuzzerMutate.cpp index 69ef9640d77..e3b35d4de81 100644 --- a/lib/Fuzzer/FuzzerMutate.cpp +++ b/lib/Fuzzer/FuzzerMutate.cpp @@ -92,6 +92,7 @@ size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize) { + if (Size > MaxSize) return 0; assert(Size); size_t ShuffleAmount = Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. @@ -117,7 +118,7 @@ size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, size_t MaxSize) { - if (Size == MaxSize) return 0; + 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); @@ -145,6 +146,7 @@ size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, 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; @@ -152,6 +154,7 @@ size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t 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; @@ -175,6 +178,7 @@ size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( 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())]; const Word &W = DE.GetW(); @@ -239,6 +243,7 @@ size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, size_t MaxSize) { + if (Size > MaxSize) return 0; if (Rand.RandBool()) return CopyPartOf(Data, Size, Data, Size); else @@ -247,6 +252,7 @@ size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, 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; @@ -305,6 +311,7 @@ size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { 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); @@ -317,6 +324,7 @@ size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, size_t MaxSize) { + if (Size > MaxSize) return 0; if (!Corpus || Corpus->size() < 2 || Size == 0) return 0; size_t Idx = Rand(Corpus->size()); const Unit &O = (*Corpus)[Idx]; @@ -402,7 +410,6 @@ size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize, const std::vector &Mutators) { assert(MaxSize > 0); - assert(Size <= MaxSize); if (Size == 0) { for (size_t i = 0; i < MaxSize; i++) Data[i] = RandCh(Rand); @@ -414,17 +421,17 @@ size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, // 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 < 10; Iter++) { + for (int Iter = 0; Iter < 100; Iter++) { auto M = Mutators[Rand(Mutators.size())]; size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); - if (NewSize) { + if (NewSize && NewSize <= MaxSize) { if (Options.OnlyASCII) ToASCII(Data, NewSize); CurrentMutatorSequence.push_back(M); return NewSize; } } - return Size; + return std::min(Size, MaxSize); } void MutationDispatcher::AddWordToManualDictionary(const Word &W) { diff --git a/lib/Fuzzer/FuzzerTracePC.cpp b/lib/Fuzzer/FuzzerTracePC.cpp index 4d962d31e78..34fd5730dcc 100644 --- a/lib/Fuzzer/FuzzerTracePC.cpp +++ b/lib/Fuzzer/FuzzerTracePC.cpp @@ -31,7 +31,7 @@ void TracePC::HandleTrace(uintptr_t *Guard, uintptr_t PC) { PCs[Idx] = PC; if (TotalCoverageMap.AddValue(Idx)) { TotalCoverage++; - AddNewPC(PC); + AddNewPCID(Idx); } } if (Counter < 128) @@ -41,7 +41,7 @@ void TracePC::HandleTrace(uintptr_t *Guard, uintptr_t PC) { } else { *Guard = 0; TotalCoverage++; - AddNewPC(PC); + AddNewPCID(Idx); PCs[Idx] = PC; } } diff --git a/lib/Fuzzer/FuzzerTracePC.h b/lib/Fuzzer/FuzzerTracePC.h index 58497f1e9f5..e26a59f4427 100644 --- a/lib/Fuzzer/FuzzerTracePC.h +++ b/lib/Fuzzer/FuzzerTracePC.h @@ -27,18 +27,18 @@ class TracePC { size_t UpdateCounterMap(ValueBitMap *Map); void FinalizeTrace(); - size_t GetNewPCsAndFlush(uintptr_t **NewPCsPtr = nullptr) { - if (NewPCsPtr) - *NewPCsPtr = NewPCs; - size_t Res = NumNewPCs; - NumNewPCs = 0; - return Res; + size_t GetNewPCIDs(uintptr_t **NewPCIDsPtr) { + *NewPCIDsPtr = NewPCIDs; + return NumNewPCIDs; } + void ResetNewPCIDs() { NumNewPCIDs = 0; } + uintptr_t GetPCbyPCID(uintptr_t PCID) { return PCs[PCID]; } + void Reset() { TotalCoverage = 0; TotalCounterBits = 0; - NumNewPCs = 0; + NumNewPCIDs = 0; CounterMap.Reset(); TotalCoverageMap.Reset(); ResetGuards(); @@ -53,10 +53,12 @@ private: size_t TotalCoverage = 0; size_t TotalCounterBits = 0; - static const size_t kMaxNewPCs = 64; - uintptr_t NewPCs[kMaxNewPCs]; - size_t NumNewPCs = 0; - void AddNewPC(uintptr_t PC) { NewPCs[(NumNewPCs++) % kMaxNewPCs] = PC; } + static const size_t kMaxNewPCIDs = 64; + uintptr_t NewPCIDs[kMaxNewPCIDs]; + size_t NumNewPCIDs = 0; + void AddNewPCID(uintptr_t PCID) { + NewPCIDs[(NumNewPCIDs++) % kMaxNewPCIDs] = PCID; + } void ResetGuards(); diff --git a/lib/Fuzzer/test/FuzzerUnittest.cpp b/lib/Fuzzer/test/FuzzerUnittest.cpp index fdde1d3fbb9..f2ac0e5f458 100644 --- a/lib/Fuzzer/test/FuzzerUnittest.cpp +++ b/lib/Fuzzer/test/FuzzerUnittest.cpp @@ -583,7 +583,7 @@ TEST(Corpus, Distribution) { size_t N = 10; size_t TriesPerUnit = 1<<20; for (size_t i = 0; i < N; i++) - C.AddToCorpus(Unit{ static_cast(i) }); + C.AddToCorpus(Unit{ static_cast(i) }, nullptr, 0); std::vector Hist(N); for (size_t i = 0; i < N * TriesPerUnit; i++) { -- 2.11.0