From 2c55613a08b1b66eb337fc5a84fd2d6b086bb8b4 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Fri, 30 Sep 2016 01:19:56 +0000 Subject: [PATCH] [libFuzzer] more the feature set to InputCorpus; on feature update, change the feature counter of the old best input llvm-svn: 282829 --- llvm/lib/Fuzzer/FuzzerCorpus.h | 77 ++++++++++++++++++++++++++++++++++++++- llvm/lib/Fuzzer/FuzzerLoop.cpp | 4 +- llvm/lib/Fuzzer/FuzzerTracePC.cpp | 25 ------------- llvm/lib/Fuzzer/FuzzerTracePC.h | 13 ++----- 4 files changed, 80 insertions(+), 39 deletions(-) diff --git a/llvm/lib/Fuzzer/FuzzerCorpus.h b/llvm/lib/Fuzzer/FuzzerCorpus.h index b9a0665..6438a60 100644 --- a/llvm/lib/Fuzzer/FuzzerCorpus.h +++ b/llvm/lib/Fuzzer/FuzzerCorpus.h @@ -17,21 +17,26 @@ #include "FuzzerDefs.h" #include "FuzzerRandom.h" +#include "FuzzerTracePC.h" namespace fuzzer { struct InputInfo { Unit U; // The actual input data. uint8_t Sha1[kSHA1NumBytes]; // Checksum. + // Number of features that this input has and no smaller input has. + size_t NumFeatures = 0; + size_t Tmp = 0; // Used by ValidateFeatureSet. // Stats. - uintptr_t NumExecutedMutations = 0; - uintptr_t NumSuccessfullMutations = 0; + size_t NumExecutedMutations = 0; + size_t NumSuccessfullMutations = 0; }; class InputCorpus { public: InputCorpus() { Inputs.reserve(1 << 14); // Avoid too many resizes. + memset(FeatureSet, 0, sizeof(FeatureSet)); } size_t size() const { return Inputs.size(); } bool empty() const { return Inputs.empty(); } @@ -44,6 +49,7 @@ class InputCorpus { InputInfo &II = Inputs.back(); II.U = U; memcpy(II.Sha1, Hash, kSHA1NumBytes); + UpdateFeatureSet(Inputs.size() - 1); UpdateCorpusDistribution(); } @@ -74,8 +80,68 @@ class InputCorpus { } } + void PrintFeatureSet() { + Printf("Features [id: cnt idx sz] "); + for (size_t i = 0; i < kFeatureSetSize; i++) { + auto &Fe = FeatureSet[i]; + if (!Fe.Count) continue; + Printf("[%zd: %zd %zd] ", i, Fe.SmallestElementIdx, + Fe.SmallestElementSize); + } + Printf("\n\t"); + for (size_t i = 0; i < Inputs.size(); i++) + if (size_t N = Inputs[i].NumFeatures) + Printf(" %zd=>%zd ", i, N); + Printf("\n"); + } + private: + static const bool FeatureDebug = false; + static const size_t kFeatureSetSize = TracePC::kFeatureSetSize; + + void ValidateFeatureSet() { + for (size_t Idx = 0; Idx < kFeatureSetSize; Idx++) { + Feature &Fe = FeatureSet[Idx]; + if(Fe.Count && Fe.SmallestElementSize) + Inputs[Fe.SmallestElementIdx].Tmp++; + } + for (auto &II: Inputs) { + assert(II.Tmp == II.NumFeatures); + II.Tmp = 0; + } + } + + void UpdateFeatureSet(size_t CurrentElementIdx) { + auto &II = Inputs[CurrentElementIdx]; + size_t Size = II.U.size(); + if (!Size) + return; + bool Updated = false; + for (size_t Idx = 0; Idx < kFeatureSetSize; Idx++) { + if (!TPC.HasFeature(Idx)) + continue; + Feature &Fe = FeatureSet[Idx]; + Fe.Count++; + if (!Fe.SmallestElementSize || + Fe.SmallestElementSize > Size) { + II.NumFeatures++; + if (Fe.SmallestElementSize > Size) { + auto &OlderII = Inputs[Fe.SmallestElementIdx]; + assert(OlderII.NumFeatures > 0); + OlderII.NumFeatures--; + if (!OlderII.NumFeatures && FeatureDebug) + Printf("EVICTED %zd\n", Fe.SmallestElementIdx); + } + Fe.SmallestElementIdx = CurrentElementIdx; + Fe.SmallestElementSize = Size; + Updated = true; + } + } + if (Updated && FeatureDebug) PrintFeatureSet(); + ValidateFeatureSet(); + } + // Updates the probability distribution for the units in the corpus. // Must be called whenever the corpus or unit weights are changed. void UpdateCorpusDistribution() { @@ -91,6 +157,13 @@ private: std::unordered_set Hashes; std::vector Inputs; + + struct Feature { + size_t Count; + size_t SmallestElementIdx; + size_t SmallestElementSize; + }; + Feature FeatureSet[kFeatureSetSize]; }; } // namespace fuzzer diff --git a/llvm/lib/Fuzzer/FuzzerLoop.cpp b/llvm/lib/Fuzzer/FuzzerLoop.cpp index 197b80e..8ef86f2 100644 --- a/llvm/lib/Fuzzer/FuzzerLoop.cpp +++ b/llvm/lib/Fuzzer/FuzzerLoop.cpp @@ -392,15 +392,13 @@ void Fuzzer::CheckExitOnSrcPos() { void Fuzzer::AddToCorpusAndMaybeRerun(const Unit &U) { CheckExitOnSrcPos(); - Corpus.AddToCorpus(U); if (TPC.GetTotalPCCoverage()) { TPC.ResetMaps(); TPC.ResetGuards(); ExecuteCallback(U.data(), U.size()); TPC.FinalizeTrace(); - TPC.UpdateFeatureSet(Corpus.size() - 1, U.size()); - // TPC.PrintFeatureSet(); } + Corpus.AddToCorpus(U); } void Fuzzer::RereadOutputCorpus(size_t MaxSize) { diff --git a/llvm/lib/Fuzzer/FuzzerTracePC.cpp b/llvm/lib/Fuzzer/FuzzerTracePC.cpp index 4414992..f97da96 100644 --- a/llvm/lib/Fuzzer/FuzzerTracePC.cpp +++ b/llvm/lib/Fuzzer/FuzzerTracePC.cpp @@ -109,31 +109,6 @@ void TracePC::PrintCoverage() { } } - -void TracePC::UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize) { - if (!CurrentElementSize) return; - for (size_t Idx = 0; Idx < kFeatureSetSize; Idx++) { - if (!CounterMap.Get(Idx)) continue; - Feature &Fe = FeatureSet[Idx]; - Fe.Count++; - if (!Fe.SmallestElementSize || Fe.SmallestElementSize > CurrentElementSize) { - Fe.SmallestElementIdx = CurrentElementIdx; - Fe.SmallestElementSize = CurrentElementSize; - } - } -} - -void TracePC::PrintFeatureSet() { - Printf("[id: cnt idx sz] "); - for (size_t i = 0; i < kFeatureSetSize; i++) { - auto &Fe = FeatureSet[i]; - if (!Fe.Count) continue; - Printf("[%zd: %zd %zd %zd] ", i, Fe.Count, Fe.SmallestElementIdx, - Fe.SmallestElementSize); - } - Printf("\n"); -} - } // namespace fuzzer extern "C" { diff --git a/llvm/lib/Fuzzer/FuzzerTracePC.h b/llvm/lib/Fuzzer/FuzzerTracePC.h index 3f4c783..1eb4a30 100644 --- a/llvm/lib/Fuzzer/FuzzerTracePC.h +++ b/llvm/lib/Fuzzer/FuzzerTracePC.h @@ -19,6 +19,8 @@ namespace fuzzer { class TracePC { public: + static const size_t kFeatureSetSize = ValueBitMap::kNumberOfItems; + void HandleTrace(uint32_t *guard, uintptr_t PC); void HandleInit(uint32_t *start, uint32_t *stop); void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee); @@ -58,6 +60,8 @@ class TracePC { void PrintCoverage(); + bool HasFeature(size_t Idx) { return CounterMap.Get(Idx); } + private: bool UseCounters = false; bool UseValueProfile = false; @@ -86,15 +90,6 @@ private: ValueBitMap CounterMap; ValueBitMap ValueProfileMap; - - struct Feature { - size_t Count; - size_t SmallestElementIdx; - size_t SmallestElementSize; - }; - - static const size_t kFeatureSetSize = ValueBitMap::kNumberOfItems; - Feature FeatureSet[kFeatureSetSize]; }; extern TracePC TPC; -- 2.7.4