Index: lib/Fuzzer/FuzzerInternal.h =================================================================== --- lib/Fuzzer/FuzzerInternal.h +++ lib/Fuzzer/FuzzerInternal.h @@ -112,12 +112,38 @@ int SignalToMainThread(); void SleepSeconds(int Seconds); + +struct PcCoverageMap { + static const size_t kPcMapSizeInBits = 65371; // Prime. + static const size_t kPcMapSizeInBitsAligned = 65536; // 2^16 + static const size_t kBitsInWord =(sizeof(uintptr_t) * 8); + static const size_t kPcMapSizeInWords = kPcMapSizeInBitsAligned / kBitsInWord; + + void Reset() { + memset(Map, 0, sizeof(Map)); + } + + size_t MergeInto(PcCoverageMap* Other) const { + uintptr_t Res = 0; + for (size_t i = 0; i < kPcMapSizeInWords; i++) + Res += __builtin_popcountl(Other->Map[i] |= Map[i]); + return Res; + } + + void Update(uintptr_t Addr) { + uintptr_t Idx = Addr % kPcMapSizeInBits; + uintptr_t WordIdx = Idx / kBitsInWord; + uintptr_t BitIdx = Idx % kBitsInWord; + Map[WordIdx] |= 1UL << BitIdx; + } + + uintptr_t Map[kPcMapSizeInWords] __attribute__((aligned(512))); +}; + // 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(); +size_t PcMapMergeInto(PcCoverageMap* Map); class Random { public: @@ -276,6 +302,7 @@ static Mutator Mutators[]; }; + class Fuzzer { public: struct FuzzingOptions { @@ -309,6 +336,38 @@ bool PrintFinalStats = false; bool DetectLeaks = true; }; + + struct CoverageStats { + CoverageStats() { Reset(); } + + void Reset() { + BlockCoverage = 0; + CallerCalleeCoverage = 0; + PcMapBits = 0; + CounterBitmapBits = 0; + CounterBitmap.clear(); + PCMap.Reset(); + } + + bool UpdateMax(const CoverageStats& Other); + std::string DebugString() const; + + size_t TotalBits() { // Slow. Call it only for printing stats. + size_t Res = 0; + for (auto x : CounterBitmap) + Res += __builtin_popcount(x); + return Res; + } + + size_t BlockCoverage; + size_t CallerCalleeCoverage; + + size_t CounterBitmapBits; + size_t PcMapBits; + PcCoverageMap PCMap; + std::vector CounterBitmap; + }; + Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options); void AddToCorpus(const Unit &U) { Corpus.push_back(U); @@ -378,10 +437,6 @@ // 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(); // Trace-based fuzzing: we run a unit with some kind of tracing @@ -410,16 +465,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 +475,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; + + CoverageStats MaxCoverage; }; }; // namespace fuzzer Index: lib/Fuzzer/FuzzerLoop.cpp =================================================================== --- lib/Fuzzer/FuzzerLoop.cpp +++ lib/Fuzzer/FuzzerLoop.cpp @@ -81,6 +81,32 @@ 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::CoverageStats* Stats) { + if (Options.UseCounters) { + size_t NumCounters = __sanitizer_get_number_of_counters(); + Stats->CounterBitmap.resize(NumCounters); + __sanitizer_update_counter_bitset_and_clear_counters(0); + } + } + + static void Record(const Fuzzer::FuzzingOptions& Options, Fuzzer::CoverageStats* Stats) { + Stats->BlockCoverage = __sanitizer_get_total_unique_coverage(); + if (Options.UseIndirCalls && __sanitizer_get_total_unique_caller_callee_pairs) + Stats->CallerCalleeCoverage = __sanitizer_get_total_unique_caller_callee_pairs(); + if (Options.UseCounters) + Stats->CounterBitmapBits += __sanitizer_update_counter_bitset_and_clear_counters(Stats->CounterBitmap.data()); + Stats->PcMapBits = PcMapMergeInto(&Stats->PCMap); + } +}; + Fuzzer::Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options) : CB(CB), MD(MD), Options(Options) { SetDeathCallback(); @@ -208,22 +234,22 @@ 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, + MaxCoverage.BlockCoverage, MaxCoverage.TotalBits(), + 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.TotalBits()) 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 +324,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; @@ -312,9 +338,14 @@ bool Fuzzer::RunOne(const uint8_t *Data, size_t Size) { TotalNumberOfRuns++; - PrepareCoverageBeforeRun(); + CoverageStats Stats; + + CoverageController::Prepare(Options, &Stats); ExecuteCallback(Data, Size); - bool Res = CheckCoverageAfterRun(); + CoverageController::Record(Options, &Stats); + + // Printf("Max=%s New=%s\n", MaxCoverage.DebugString().c_str(), Stats.DebugString().c_str()); + bool Res = MaxCoverage.UpdateMax(Stats); auto UnitStopTime = system_clock::now(); auto TimeOfUnit = @@ -378,6 +409,7 @@ assert(Res == 0); } +/* size_t Fuzzer::RecordBlockCoverage() { CHECK_WEAK_API_FUNCTION(__sanitizer_get_total_unique_coverage); uintptr_t PrevCoverage = LastRecordedBlockCoverage; @@ -396,43 +428,50 @@ return LastRecordedBlockCoverage; } +*/ -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(); -} +bool Fuzzer::CoverageStats::UpdateMax(const CoverageStats& Other) { + bool Res = false; + + if (Other.BlockCoverage > BlockCoverage) { + Res = true; + BlockCoverage = Other.BlockCoverage; + } + + if (Other.CallerCalleeCoverage > CallerCalleeCoverage) { + Res = true; + CallerCalleeCoverage = Other.CallerCalleeCoverage; + } + + if (CounterBitmap.size() != 0) { + 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 = Other.PCMap.MergeInto(&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::CoverageStats::DebugString() const { + std::string Result = std::string("CoverageStats{") + + "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 +678,8 @@ } void Fuzzer::ResetCoverage() { - CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage); - __sanitizer_reset_coverage(); - CounterBitmap.clear(); + CoverageController::Reset(); + MaxCoverage = CoverageStats(); } // Experimental search heuristic: drilling. Index: lib/Fuzzer/FuzzerMutate.cpp =================================================================== --- lib/Fuzzer/FuzzerMutate.cpp +++ lib/Fuzzer/FuzzerMutate.cpp @@ -119,6 +119,9 @@ if (D.empty()) return 0; DictionaryEntry &DE = D[Rand(D.size())]; const Word &W = DE.GetW(); + Printf("UseWord:"); + PrintASCII(W); + Printf(" (%zd)\n", D.size()); bool UsePositionHint = DE.HasPositionHint() && DE.GetPositionHint() + W.size() < Size && Rand.RandBool(); if (Rand.RandBool()) { // Insert W. Index: lib/Fuzzer/FuzzerTracePC.cpp =================================================================== --- lib/Fuzzer/FuzzerTracePC.cpp +++ lib/Fuzzer/FuzzerTracePC.cpp @@ -15,39 +15,26 @@ #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 CurrentMap.MergeInto(Map); } -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; }