From e2e54904b734dfb130584a030acd4b2c632402d6 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Fri, 23 Sep 2016 23:51:58 +0000 Subject: [PATCH] [libFuzzer] simplify HandleTrace again, start re-running interesting units and collecting their features. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@282316 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerInternal.h | 1 + lib/Fuzzer/FuzzerLoop.cpp | 19 ++++++++-- lib/Fuzzer/FuzzerTracePC.cpp | 41 +++++++++++++++++++--- lib/Fuzzer/FuzzerTracePC.h | 12 +++++++ lib/Fuzzer/FuzzerValueBitMap.h | 8 +++++ .../fuzzer-test-suite/re2-2014-12-09/build.sh | 3 +- 6 files changed, 75 insertions(+), 9 deletions(-) diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index 23cdc6a84cc..1188b052a1b 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -115,6 +115,7 @@ private: void ShuffleCorpus(UnitVector *V); void TryDetectingAMemoryLeak(const uint8_t *Data, size_t Size, bool DuringInitialCorpusExecution); + void AddToCorpusAndMaybeRerun(const Unit &U); bool UpdateMaxCoverage(); diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index 7182a693afa..4a9b5694956 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -374,6 +374,18 @@ void Fuzzer::SetMaxMutationLen(size_t MaxMutationLen) { this->MaxMutationLen = MaxMutationLen; } +void Fuzzer::AddToCorpusAndMaybeRerun(const Unit &U) { + 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(); + } +} + void Fuzzer::RereadOutputCorpus(size_t MaxSize) { if (Options.OutputCorpus.empty() || !Options.Reload) return; std::vector AdditionalCorpus; @@ -386,7 +398,7 @@ void Fuzzer::RereadOutputCorpus(size_t MaxSize) { X.resize(MaxSize); if (!Corpus.HasUnit(X)) { if (RunOne(X)) { - Corpus.AddToCorpus(X); + AddToCorpusAndMaybeRerun(X); PrintStats("RELOAD"); } } @@ -409,7 +421,7 @@ void Fuzzer::ShuffleAndMinimize(UnitVector *InitialCorpus) { for (const auto &U : *InitialCorpus) { bool NewCoverage = RunOne(U); if (!Options.PruneCorpus || NewCoverage) { - Corpus.AddToCorpus(U); + AddToCorpusAndMaybeRerun(U); if (Options.Verbosity >= 2) Printf("NEW0: %zd L %zd\n", MaxCoverage.BlockCoverage, U.size()); } @@ -471,6 +483,7 @@ void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) { UnitStartTime = system_clock::now(); ResetCounters(); // Reset coverage right before the callback. TPC.ResetMaps(); + TPC.ResetGuards(); int Res = CB(DataCopy, Size); UnitStopTime = system_clock::now(); (void)Res; @@ -547,12 +560,12 @@ void Fuzzer::PrintNewPCs() { void Fuzzer::ReportNewCoverage(InputInfo *II, const Unit &U) { II->NumSuccessfullMutations++; - Corpus.AddToCorpus(U); MD.RecordSuccessfulMutationSequence(); PrintStatusForNewUnit(U); WriteToOutputCorpus(U); NumberOfNewUnitsAdded++; PrintNewPCs(); + AddToCorpusAndMaybeRerun(U); } // Finds minimal number of units in 'Extra' that add coverage to 'Initial'. diff --git a/lib/Fuzzer/FuzzerTracePC.cpp b/lib/Fuzzer/FuzzerTracePC.cpp index 0df8aba18f6..393470770c9 100644 --- a/lib/Fuzzer/FuzzerTracePC.cpp +++ b/lib/Fuzzer/FuzzerTracePC.cpp @@ -23,18 +23,24 @@ TracePC TPC; void TracePC::HandleTrace(uintptr_t *Guard, uintptr_t PC) { uintptr_t Idx = *Guard; if (!Idx) return; - uint8_t Counter = Counters[Idx % kNumCounters]; + uint8_t *CounterPtr = &Counters[Idx % kNumCounters]; + uint8_t Counter = *CounterPtr; if (Counter == 0) { - AddNewPCID(Idx); if (!PCs[Idx]) { + AddNewPCID(Idx); TotalPCCoverage++; PCs[Idx] = PC; } } - if (Counter < 128) - Counters[Idx % kNumCounters] = Counter + 1; - if (Counter >= 128 || !UseCounters) + if (UseCounters) { + if (Counter < 128) + *CounterPtr = Counter + 1; + else + *Guard = 0; + } else { + *CounterPtr = 1; *Guard = 0; + } } void TracePC::HandleInit(uintptr_t *Start, uintptr_t *Stop) { @@ -96,6 +102,31 @@ 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/lib/Fuzzer/FuzzerTracePC.h b/lib/Fuzzer/FuzzerTracePC.h index bf890211791..facd98d5262 100644 --- a/lib/Fuzzer/FuzzerTracePC.h +++ b/lib/Fuzzer/FuzzerTracePC.h @@ -50,6 +50,9 @@ class TracePC { memset(Counters, 0, sizeof(Counters)); } + void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize); + void PrintFeatureSet(); + void ResetGuards(); void PrintModuleInfo(); @@ -84,6 +87,15 @@ 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; diff --git a/lib/Fuzzer/FuzzerValueBitMap.h b/lib/Fuzzer/FuzzerValueBitMap.h index fdc92189b47..bc191e49fae 100644 --- a/lib/Fuzzer/FuzzerValueBitMap.h +++ b/lib/Fuzzer/FuzzerValueBitMap.h @@ -23,6 +23,7 @@ struct ValueBitMap { static const size_t kBitsInWord = (sizeof(uintptr_t) * 8); static const size_t kMapSizeInWords = kMapSizeInBitsAligned / kBitsInWord; public: + static const size_t kNumberOfItems = kMapSizeInBits; // Clears all bits. void Reset() { memset(Map, 0, sizeof(Map)); } @@ -38,6 +39,13 @@ struct ValueBitMap { return New != Old; } + inline bool Get(uintptr_t Idx) { + assert(Idx < kMapSizeInBits); + uintptr_t WordIdx = Idx / kBitsInWord; + uintptr_t BitIdx = Idx % kBitsInWord; + return Map[WordIdx] & (1UL << BitIdx); + } + size_t GetNumBitsSinceLastMerge() const { return NumBits; } // Merges 'Other' into 'this', clears 'Other', updates NumBits, diff --git a/lib/Fuzzer/fuzzer-test-suite/re2-2014-12-09/build.sh b/lib/Fuzzer/fuzzer-test-suite/re2-2014-12-09/build.sh index 0b79aa55819..c2533bb0dc3 100755 --- a/lib/Fuzzer/fuzzer-test-suite/re2-2014-12-09/build.sh +++ b/lib/Fuzzer/fuzzer-test-suite/re2-2014-12-09/build.sh @@ -2,6 +2,7 @@ [ -e $(basename $0) ] && echo "PLEASE USE THIS SCRIPT FROM ANOTHER DIR" && exit 1 SCRIPT_DIR=$(dirname $0) +EXECUTABLE_NAME_BASE=$(basename $SCRIPT_DIR) LIBFUZZER_SRC=$(dirname $(dirname $SCRIPT_DIR)) FUZZ_CXXFLAGS="-O2 -g -fsanitize=address -fsanitize-coverage=trace-pc-guard,trace-cmp,trace-gep,trace-div" @@ -18,4 +19,4 @@ build_lib() { get build_lib $LIBFUZZER_SRC/build.sh -clang++ -g $SCRIPT_DIR/target.cc -I BUILD BUILD/obj/libre2.a libFuzzer.a $FUZZ_CXXFLAGS +clang++ -g $SCRIPT_DIR/target.cc -I BUILD BUILD/obj/libre2.a libFuzzer.a $FUZZ_CXXFLAGS -o $EXECUTABLE_NAME_BASE -- 2.11.0