Index: compiler-rt/lib/fuzzer/FuzzerFork.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerFork.h +++ compiler-rt/lib/fuzzer/FuzzerFork.h @@ -16,9 +16,16 @@ #include namespace fuzzer { + void FuzzWithFork(Random &Rand, const FuzzingOptions &Options, const Vector &Args, const Vector &CorpusDirs, int NumJobs); + +void EncodeFeatures(const Vector &Features, + Vector *Encoded); +bool DecodeFeatures(const Vector &Encoded, + Vector *Features); + } // namespace fuzzer #endif // LLVM_FUZZER_FORK_H Index: compiler-rt/lib/fuzzer/FuzzerFork.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerFork.cpp +++ compiler-rt/lib/fuzzer/FuzzerFork.cpp @@ -193,14 +193,13 @@ FeatureFile.replace(0, Job->CorpusDir.size(), Job->FeaturesDir); auto FeatureBytes = FileToVector(FeatureFile, 0, false); assert((FeatureBytes.size() % sizeof(uint32_t)) == 0); - Vector NewFeatures(FeatureBytes.size() / sizeof(uint32_t)); - memcpy(NewFeatures.data(), FeatureBytes.data(), FeatureBytes.size()); - for (auto Ft : NewFeatures) { - if (!Features.count(Ft)) { + Vector Encoded(FeatureBytes.size() / sizeof(uint32_t)); + memcpy(Encoded.data(), FeatureBytes.data(), FeatureBytes.size()); + Vector NewFeatures; + if (DecodeFeatures(Encoded, &NewFeatures)) + if (!std::includes(Features.begin(), Features.end(), + NewFeatures.begin(), NewFeatures.end())) MergeCandidates.push_back(F); - break; - } - } } // if (!FilesToAdd.empty() || Job->ExitCode != 0) Printf("#%zd: cov: %zd ft: %zd corp: %zd exec/s %zd " @@ -415,4 +414,23 @@ exit(ExitCode); } +void EncodeFeatures(const Vector &Features, + Vector *Encoded) { + assert(Encoded); + Encoded->clear(); + Encoded->resize(Features.size()); + std::partial_sort_copy(Features.begin(), Features.end(), Encoded->begin(), + Encoded->end()); +} + +bool DecodeFeatures(const Vector &Encoded, + Vector *Features) { + assert(Features); + if (!std::is_sorted(Encoded.begin(), Encoded.end())) + return false; + Features->clear(); + Features->insert(Features->end(), Encoded.begin(), Encoded.end()); + return true; +} + } // namespace fuzzer Index: compiler-rt/lib/fuzzer/FuzzerLoop.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerLoop.cpp +++ compiler-rt/lib/fuzzer/FuzzerLoop.cpp @@ -9,6 +9,7 @@ //===----------------------------------------------------------------------===// #include "FuzzerCorpus.h" +#include "FuzzerFork.h" #include "FuzzerIO.h" #include "FuzzerInternal.h" #include "FuzzerMutate.h" @@ -452,9 +453,12 @@ static void WriteFeatureSetToFile(const std::string &FeaturesDir, const std::string &FileName, const Vector &FeatureSet) { - if (FeaturesDir.empty() || FeatureSet.empty()) return; - WriteToFile(reinterpret_cast(FeatureSet.data()), - FeatureSet.size() * sizeof(FeatureSet[0]), + if (FeaturesDir.empty() || FeatureSet.empty()) + return; + Vector Encoded; + EncodeFeatures(FeatureSet, &Encoded); + WriteToFile(reinterpret_cast(Encoded.data()), + Encoded.size() * sizeof(Encoded[0]), DirPlusFile(FeaturesDir, FileName)); } Index: compiler-rt/lib/fuzzer/tests/CMakeLists.txt =================================================================== --- compiler-rt/lib/fuzzer/tests/CMakeLists.txt +++ compiler-rt/lib/fuzzer/tests/CMakeLists.txt @@ -73,7 +73,7 @@ FuzzerUnitTests "Fuzzer-${arch}-Test" ${arch} SOURCES FuzzerUnittest.cpp ${COMPILER_RT_GTEST_SOURCE} RUNTIME ${LIBFUZZER_TEST_RUNTIME} - DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} + DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} FuzzerTestUtil.h CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS} LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS}) set_target_properties(FuzzerUnitTests PROPERTIES Index: compiler-rt/lib/fuzzer/tests/FuzzerTestUtil.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/tests/FuzzerTestUtil.h @@ -0,0 +1,75 @@ +//===- FuzzerTestUtil.h -----------------------------------------*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Test support shared between unit tests. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_TEST_UTIL_H +#define LLVM_FUZZER_TEST_UTIL_H + +#include "FuzzerTracePC.h" +#include "gtest/gtest.h" +#include +#include +#include +#include +#include + +namespace fuzzer { + +// Helper environment to ensure that: +// * The PRNG is seeded deterministically. +class TestEnvironment : public testing::Environment { +public: + void SetUp() override { srand(0); } +}; + +// Test utilities for picking repeatable psuedorandom numbers. +template +typename std::enable_if::value, T>::type Pick() { + return static_cast(rand() & std::numeric_limits::max()); +} + +template +typename std::enable_if::value, T>::type Pick() { + auto AbsVal = static_cast(rand()) / static_cast(RAND_MAX); + return rand() % 2 ? -AbsVal : AbsVal; +} + +// Helper struct for creating coverage data for unit tests. Note that once +// memory is added to the fuzzer::TracePC singleton, that object will assume it +// is valid for its lifetime, i.e. the remainder of the process. This can cause +// issues if unit tests are repeated, i.e. -gtest_repeat=. Avoid this by +// declaring the FakeModule static within the test that adds it to the coverage. +template struct FakeModule final { +public: + uint8_t Counters[N]; + uintptr_t PCs[N * 2]; + const size_t NumPCs = N; + + FakeModule() { + memset(Counters, 0, sizeof(Counters)); + auto *TE = GetPCTableEntries(); + uintptr_t PC = Pick() & ((1ULL << 48) - 1); + for (size_t i = 0; i < N; ++i) { + TE[i].PC = PC; + TE[i].PCFlags = i == 0 || (rand() % 16) == 0; + PC += Pick(); + } + } + + uint8_t *CountersEnd() { return Counters + N; } + uintptr_t *PCsEnd() { return PCs + (N * 2); } + + TracePC::PCTableEntry *GetPCTableEntries() { + return reinterpret_cast(PCs); + } +}; + +} // namespace fuzzer + +#endif // LLVM_FUZZER_TEST_UTIL_H Index: compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp =================================================================== --- compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp +++ compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp @@ -11,11 +11,13 @@ #include "FuzzerCorpus.h" #include "FuzzerDictionary.h" +#include "FuzzerFork.h" #include "FuzzerInternal.h" #include "FuzzerMerge.h" #include "FuzzerMutate.h" #include "FuzzerRandom.h" #include "FuzzerTracePC.h" +#include "tests/FuzzerTestUtil.h" #include "gtest/gtest.h" #include #include @@ -636,6 +638,99 @@ EQ(A, __VA_ARGS__); \ } +template +void CheckEncodedFeatures(FakeModule &M, bool UseCounters) { + // Ensure the module has been added to the TracePC + auto *B = reinterpret_cast(M.PCs); + uintptr_t Idx = 0; + while (true) { + auto *TE = TPC.PCTableEntryByIdx(Idx); + if (!TE) { + TPC.HandlePCsInit(M.PCs, M.PCsEnd()); + TPC.HandleInline8bitCountersInit(M.Counters, M.CountersEnd()); + break; + } + if (TE == B) + break; + ++Idx; + } + + // Generate the sequence of relative encoded features for the given module. + Vector Expected; + auto FirstFeature = Idx * 8; + for (size_t i = 0; i < M.NumPCs; ++i) { + if (M.Counters[i]) { + if (UseCounters) { + Expected.push_back(FirstFeature + i * 8 + + CounterToFeature(M.Counters[i])); + } else { + Expected.push_back(FirstFeature + i); + } + } + ++Idx; + } + + // Now get the actual encoded features, and look for the expected ones. + Vector Features, Actual; + TPC.CollectFeatures( + [&](size_t F) { Features.push_back(static_cast(F)); }); + + EncodeFeatures(Features, &Actual); + auto I = std::search(Actual.begin(), Actual.end(), Expected.begin(), + Expected.end()); + EXPECT_NE(I, Actual.end()); +} + +TEST(FuzzerFork, EncodeFeatures) { + TPC.SetUseCounters(0); + TPC.SetUseValueProfileMask(0); + TPC.RecordInitialStack(); + TPC.ResetMaps(); + + // Add a module. It will be added to TPC, so make it static to allow the test + // to be run multiple times. + static FakeModule<4> M1; + M1.Counters[0] = 3; + M1.Counters[1] = 2; + M1.Counters[2] = 1; + M1.Counters[3] = 0; // Not encoded. + CheckEncodedFeatures(M1, /* UseCounters */ false); + + // Add a second module. This time, use counters. + TPC.SetUseCounters(1); + static FakeModule<9> M2; + M2.Counters[0] = 0; // Not encoded. + M2.Counters[1] = 1; + M2.Counters[2] = 2; + M2.Counters[3] = 3; + M2.Counters[4] = 4; + M2.Counters[5] = 8; + M2.Counters[6] = 16; + M2.Counters[7] = 32; + M2.Counters[8] = 128; + CheckEncodedFeatures(M2, /* UseCounters */ true); +} + +TEST(FuzzerFork, DecodeFeatures) { + Vector A; + + // Empty input + EXPECT_TRUE(DecodeFeatures({}, &A)); + TRACED_EQ(A, {}); + + // Not sorted + EXPECT_FALSE(DecodeFeatures({3, 2}, &A)); + TRACED_EQ(A, {}); + + // Valid + EXPECT_TRUE(DecodeFeatures({2, 3}, &A)); + TRACED_EQ(A, {2, 3}); + + // Multiple valid modules. + EXPECT_TRUE(DecodeFeatures({2, 3, 4, 5, 6}, &A)); + TRACED_EQ(A, {2, 3, 4, 5, 6}); +} + TEST(Merger, Parse) { Merger M; @@ -1215,5 +1310,6 @@ int main(int argc, char **argv) { testing::InitGoogleTest(&argc, argv); + testing::AddGlobalTestEnvironment(new fuzzer::TestEnvironment()); return RUN_ALL_TESTS(); }