Index: lib/Fuzzer/FuzzerInternal.h =================================================================== --- lib/Fuzzer/FuzzerInternal.h +++ lib/Fuzzer/FuzzerInternal.h @@ -25,6 +25,7 @@ #include #include "FuzzerInterface.h" +#include "FuzzerTracePC.h" namespace fuzzer { using namespace std::chrono; @@ -112,13 +113,6 @@ int SignalToMainThread(); void SleepSeconds(int Seconds); -// Clears the current PC Map. -void PcMapResetCurrent(); -// Merges the current PC Map into the combined one, and clears the former. -void PcMapMergeCurrentToCombined(); -// Returns the size of the combined PC Map. -size_t PcMapCombinedSize(); - class Random { public: Random(unsigned int seed) : R(seed) {} @@ -309,6 +303,38 @@ bool PrintFinalStats = false; bool DetectLeaks = true; }; + + // Aggregates all available coverage measurements. + struct Coverage { + Coverage() { Reset(); } + + void Reset() { + BlockCoverage = 0; + CallerCalleeCoverage = 0; + PcMapBits = 0; + CounterBitmapBits = 0; + PcBufferLen = 0; + CounterBitmap.clear(); + PCMap.Reset(); + } + + // Merges coverage data from the other and returns true if new coverage + // was merged in. + bool MergeFrom(const Coverage &Other); + std::string DebugString() const; + + size_t BlockCoverage; + size_t CallerCalleeCoverage; + + size_t PcBufferLen; + // Precalculated number of bits in CounterBitmap. + size_t CounterBitmapBits; + std::vector CounterBitmap; + // Precalculated number of bits in PCMap. + size_t PcMapBits; + PcCoverageMap PCMap; + }; + Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options); void AddToCorpus(const Unit &U) { Corpus.push_back(U); @@ -378,11 +404,8 @@ // Must be called whenever the corpus or unit weights are changed. void UpdateCorpusDistribution(); - size_t RecordBlockCoverage(); - size_t RecordCallerCalleeCoverage(); - void PrepareCoverageBeforeRun(); - bool CheckCoverageAfterRun(); void ResetCoverage(); + bool UpdateMaxCoverage(const Coverage &C); // Trace-based fuzzing: we run a unit with some kind of tracing // enabled and record potentially useful mutations. Then @@ -410,16 +433,6 @@ std::vector Corpus; std::unordered_set UnitHashesAddedToCorpus; - - // For UseCounters - std::vector CounterBitmap; - size_t TotalBits() { // Slow. Call it only for printing stats. - size_t Res = 0; - for (auto x : CounterBitmap) - Res += __builtin_popcount(x); - return Res; - } - std::vector MutateInPlaceHere; std::piecewise_constant_distribution CorpusDistribution; @@ -430,10 +443,8 @@ system_clock::time_point UnitStartTime; long TimeOfLongestUnitInSeconds = 0; long EpochOfLastReadOfOutputCorpus = 0; - size_t LastRecordedBlockCoverage = 0; - size_t LastRecordedPcMapSize = 0; - size_t LastRecordedCallerCalleeCoverage = 0; - size_t LastCoveragePcBufferLen = 0; + + Coverage MaxCoverage; }; }; // namespace fuzzer Index: lib/Fuzzer/FuzzerLoop.cpp =================================================================== --- lib/Fuzzer/FuzzerLoop.cpp +++ lib/Fuzzer/FuzzerLoop.cpp @@ -81,6 +81,39 @@ return F->GetMD().Mutate(Data, Size, MaxSize); } +struct CoverageController { + static void Reset() { + CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage); + __sanitizer_reset_coverage(); + PcMapResetCurrent(); + } + + static void Prepare(const Fuzzer::FuzzingOptions &Options, + Fuzzer::Coverage *C) { + if (Options.UseCounters) { + size_t NumCounters = __sanitizer_get_number_of_counters(); + C->CounterBitmap.resize(NumCounters); + __sanitizer_update_counter_bitset_and_clear_counters(0); + } + } + + static void Record(const Fuzzer::FuzzingOptions &Options, + Fuzzer::Coverage *C) { + C->BlockCoverage = __sanitizer_get_total_unique_coverage(); + if (Options.UseIndirCalls && + __sanitizer_get_total_unique_caller_callee_pairs) + C->CallerCalleeCoverage = + __sanitizer_get_total_unique_caller_callee_pairs(); + if (Options.UseCounters) + C->CounterBitmapBits += + __sanitizer_update_counter_bitset_and_clear_counters( + C->CounterBitmap.data()); + C->PcMapBits = PcMapMergeInto(&C->PCMap); + uintptr_t *CoverageBuf; + C->PcBufferLen = __sanitizer_get_coverage_pc_buffer(&CoverageBuf); + } +}; + Fuzzer::Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options) : CB(CB), MD(MD), Options(Options) { SetDeathCallback(); @@ -208,22 +241,21 @@ Printf("runs,block_cov,bits,cc_cov,corpus,execs_per_sec,tbms,reason\n"); } Printf("%zd,%zd,%zd,%zd,%zd,%zd,%s\n", TotalNumberOfRuns, - LastRecordedBlockCoverage, TotalBits(), - LastRecordedCallerCalleeCoverage, Corpus.size(), ExecPerSec, - Where); + MaxCoverage.BlockCoverage, MaxCoverage.CounterBitmapBits, + MaxCoverage.CallerCalleeCoverage, Corpus.size(), ExecPerSec, Where); } if (!Options.Verbosity) return; Printf("#%zd\t%s", TotalNumberOfRuns, Where); - if (LastRecordedBlockCoverage) - Printf(" cov: %zd", LastRecordedBlockCoverage); - if (LastRecordedPcMapSize) - Printf(" path: %zd", LastRecordedPcMapSize); - if (auto TB = TotalBits()) + if (MaxCoverage.BlockCoverage) + Printf(" cov: %zd", MaxCoverage.BlockCoverage); + if (MaxCoverage.PcMapBits) + Printf(" path: %zd", MaxCoverage.PcMapBits); + if (auto TB = MaxCoverage.CounterBitmapBits) Printf(" bits: %zd", TB); - if (LastRecordedCallerCalleeCoverage) - Printf(" indir: %zd", LastRecordedCallerCalleeCoverage); + if (MaxCoverage.CallerCalleeCoverage) + Printf(" indir: %zd", MaxCoverage.CallerCalleeCoverage); Printf(" units: %zd exec/s: %zd", Corpus.size(), ExecPerSec); Printf("%s", End); } @@ -298,7 +330,7 @@ if (RunOne(U)) { NewCorpus.push_back(U); if (Options.Verbosity >= 2) - Printf("NEW0: %zd L %zd\n", LastRecordedBlockCoverage, U.size()); + Printf("NEW0: %zd L %zd\n", MaxCoverage.BlockCoverage, U.size()); } } Corpus = NewCorpus; @@ -309,12 +341,30 @@ CheckForMemoryLeaks(); } +bool Fuzzer::UpdateMaxCoverage(const Fuzzer::Coverage &C) { + uintptr_t PrevBufferLen = MaxCoverage.PcBufferLen; + bool Res = MaxCoverage.MergeFrom(C); + + if (Options.PrintNewCovPcs && PrevBufferLen != MaxCoverage.PcBufferLen) { + uintptr_t *CoverageBuf; + __sanitizer_get_coverage_pc_buffer(&CoverageBuf); + assert(CoverageBuf); + for (size_t I = PrevBufferLen; I < MaxCoverage.PcBufferLen; ++I) { + Printf("%p\n", CoverageBuf[I]); + } + } + + return Res; +} + bool Fuzzer::RunOne(const uint8_t *Data, size_t Size) { TotalNumberOfRuns++; - PrepareCoverageBeforeRun(); + Coverage C; + CoverageController::Prepare(Options, &C); ExecuteCallback(Data, Size); - bool Res = CheckCoverageAfterRun(); + CoverageController::Record(Options, &C); + bool Res = UpdateMaxCoverage(C); auto UnitStopTime = system_clock::now(); auto TimeOfUnit = @@ -378,61 +428,57 @@ assert(Res == 0); } -size_t Fuzzer::RecordBlockCoverage() { - CHECK_WEAK_API_FUNCTION(__sanitizer_get_total_unique_coverage); - uintptr_t PrevCoverage = LastRecordedBlockCoverage; - LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage(); +bool Fuzzer::Coverage::MergeFrom(const Coverage &Other) { + bool Res = false; - if (PrevCoverage == LastRecordedBlockCoverage || !Options.PrintNewCovPcs) - return LastRecordedBlockCoverage; + if (Other.BlockCoverage > BlockCoverage) { + Res = true; + BlockCoverage = Other.BlockCoverage; + } - uintptr_t PrevBufferLen = LastCoveragePcBufferLen; - uintptr_t *CoverageBuf; - LastCoveragePcBufferLen = __sanitizer_get_coverage_pc_buffer(&CoverageBuf); - assert(CoverageBuf); - for (size_t i = PrevBufferLen; i < LastCoveragePcBufferLen; ++i) { - Printf("%p\n", CoverageBuf[i]); + if (Other.CallerCalleeCoverage > CallerCalleeCoverage) { + Res = true; + CallerCalleeCoverage = Other.CallerCalleeCoverage; } - return LastRecordedBlockCoverage; -} + if (Other.PcBufferLen > PcBufferLen) { + Res = true; + PcBufferLen = Other.PcBufferLen; + } -size_t Fuzzer::RecordCallerCalleeCoverage() { - if (!Options.UseIndirCalls) - return 0; - if (!__sanitizer_get_total_unique_caller_callee_pairs) - return 0; - return LastRecordedCallerCalleeCoverage = - __sanitizer_get_total_unique_caller_callee_pairs(); -} + if (Other.CounterBitmap.size() != 0) { + if (CounterBitmap.size() == 0) + CounterBitmap.resize(Other.CounterBitmap.size()); + assert(CounterBitmap.size() == Other.CounterBitmap.size()); + size_t NewCounterBitmapBits = 0; + + for (size_t I = 0; I < CounterBitmap.size(); ++I) { + NewCounterBitmapBits += + __builtin_popcount(CounterBitmap[I] |= Other.CounterBitmap[I]); + } -void Fuzzer::PrepareCoverageBeforeRun() { - if (Options.UseCounters) { - size_t NumCounters = __sanitizer_get_number_of_counters(); - CounterBitmap.resize(NumCounters); - __sanitizer_update_counter_bitset_and_clear_counters(0); + if (NewCounterBitmapBits != CounterBitmapBits) { + Res = true; + CounterBitmapBits = NewCounterBitmapBits; + } + } + + size_t NewPcMapBits = PCMap.MergeFrom(Other.PCMap); + if (NewPcMapBits > PcMapBits) { + Res = true; + PcMapBits = NewPcMapBits; } - RecordBlockCoverage(); - RecordCallerCalleeCoverage(); -} - -bool Fuzzer::CheckCoverageAfterRun() { - size_t OldCoverage = LastRecordedBlockCoverage; - size_t NewCoverage = RecordBlockCoverage(); - size_t OldCallerCalleeCoverage = LastRecordedCallerCalleeCoverage; - size_t NewCallerCalleeCoverage = RecordCallerCalleeCoverage(); - size_t NumNewBits = 0; - size_t OldPcMapSize = LastRecordedPcMapSize; - PcMapMergeCurrentToCombined(); - size_t NewPcMapSize = PcMapCombinedSize(); - LastRecordedPcMapSize = NewPcMapSize; - if (NewPcMapSize > OldPcMapSize) - return true; - if (Options.UseCounters) - NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters( - CounterBitmap.data()); - return NewCoverage > OldCoverage || - NewCallerCalleeCoverage > OldCallerCalleeCoverage || NumNewBits; + + return Res; +} + +std::string Fuzzer::Coverage::DebugString() const { + std::string Result = std::string("Coverage{") + "BlockCoverage=" + + std::to_string(BlockCoverage) + + " CallerCalleeCoverage=" + + std::to_string(CallerCalleeCoverage) + " PcMapSize=" + + std::to_string(PcMapBits) + "}"; + return Result; } void Fuzzer::WriteToOutputCorpus(const Unit &U) { @@ -639,9 +685,8 @@ } void Fuzzer::ResetCoverage() { - CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage); - __sanitizer_reset_coverage(); - CounterBitmap.clear(); + CoverageController::Reset(); + MaxCoverage.Reset(); } // Experimental search heuristic: drilling. Index: lib/Fuzzer/FuzzerTracePC.h =================================================================== --- /dev/null +++ lib/Fuzzer/FuzzerTracePC.h @@ -0,0 +1,47 @@ +//===- FuzzerTracePC.h - INTERNAL - Path tracer i-face. --------*- C++ -* ===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// Define the main class fuzzer::Fuzzer and most functions. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_TRACE_PC_H +#define LLVM_FUZZER_TRACE_PC_H + +namespace fuzzer { +struct PcCoverageMap { + static const size_t kMapSizeInBits = 65371; // Prime. + static const size_t kMapSizeInBitsAligned = 65536; // 2^16 + static const size_t kBitsInWord = (sizeof(uintptr_t) * 8); + static const size_t kMapSizeInWords = kMapSizeInBitsAligned / kBitsInWord; + + void Reset() { memset(Map, 0, sizeof(Map)); } + + size_t MergeFrom(const PcCoverageMap &Other) { + uintptr_t Res = 0; + for (size_t i = 0; i < kMapSizeInWords; i++) + Res += __builtin_popcountl(Map[i] |= Other.Map[i]); + return Res; + } + + inline void Update(uintptr_t Addr) { + uintptr_t Idx = Addr % kMapSizeInBits; + uintptr_t WordIdx = Idx / kBitsInWord; + uintptr_t BitIdx = Idx % kBitsInWord; + Map[WordIdx] |= 1UL << BitIdx; + } + + uintptr_t Map[kMapSizeInWords] __attribute__((aligned(512))); +}; + +// Clears the current PC Map. +void PcMapResetCurrent(); +// Merges the current PC Map into the combined one, and clears the former. +size_t PcMapMergeInto(PcCoverageMap *Map); +} + +#endif Index: lib/Fuzzer/FuzzerTracePC.cpp =================================================================== --- lib/Fuzzer/FuzzerTracePC.cpp +++ lib/Fuzzer/FuzzerTracePC.cpp @@ -15,39 +15,27 @@ #include "FuzzerInternal.h" namespace fuzzer { -static const size_t kMapSizeInBits = 65371; // Prime. -static const size_t kMapSizeInBitsAligned = 65536; // 2^16 -static const size_t kBitsInWord =(sizeof(uintptr_t) * 8); -static const size_t kMapSizeInWords = kMapSizeInBitsAligned / kBitsInWord; -static uintptr_t CurrentMap[kMapSizeInWords] __attribute__((aligned(512))); -static uintptr_t CombinedMap[kMapSizeInWords] __attribute__((aligned(512))); -static size_t CombinedMapSize; + +static PcCoverageMap CurrentMap; static thread_local uintptr_t Prev; void PcMapResetCurrent() { if (Prev) { Prev = 0; - memset(CurrentMap, 0, sizeof(CurrentMap)); + CurrentMap.Reset(); } } -void PcMapMergeCurrentToCombined() { - if (!Prev) return; - uintptr_t Res = 0; - for (size_t i = 0; i < kMapSizeInWords; i++) - Res += __builtin_popcountl(CombinedMap[i] |= CurrentMap[i]); - CombinedMapSize = Res; +size_t PcMapMergeInto(PcCoverageMap *Map) { + if (!Prev) + return 0; + return Map->MergeFrom(CurrentMap); } -size_t PcMapCombinedSize() { return CombinedMapSize; } - static void HandlePC(uint32_t PC) { // We take 12 bits of PC and mix it with the previous PCs. uintptr_t Next = (Prev << 5) ^ (PC & 4095); - uintptr_t Idx = Next % kMapSizeInBits; - uintptr_t WordIdx = Idx / kBitsInWord; - uintptr_t BitIdx = Idx % kBitsInWord; - CurrentMap[WordIdx] |= 1UL << BitIdx; + CurrentMap.Update(Next); Prev = Next; }