Add functions to encode/decode feature files

[aarongreen]

Summary

This change adds EncodeFeatures and DecodeFeatures to FuzzerFork. These are fairly vacuous in this change: features files are simply sorted lists of unsigned, 32 bit integers. The addition of these methods and their associated tests helps encapsulate the feature file format, allowing subsequent changes to it.

This is change 3 of (at least) 18 for cross-process fuzzing support

[charco]

compiler-rt/lib/fuzzer/FuzzerFork.cpp

199

What happens if the features here are not sorted?

compiler-rt/lib/fuzzer/FuzzerFork.h

19

empty line

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

1313

Why did you have to add this?

[aarongreen]

compiler-rt/lib/fuzzer/FuzzerFork.cpp

199

DecodeFeatures will return false, and the FeatureFile will be skipped. This shouldn't happen if EncodeFeatures was used to write the FeatureFile in the first place.

compiler-rt/lib/fuzzer/FuzzerFork.h

19

Intentional. Most of the header files have a blank lines separating the 'namespace' lines from other code, and clang-format allows it.

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

1313

In this change, the rationale is to ensure srand(0) is called and the tests using pseudorandom values are deterministic. Unit tests should *always* be deterministic!

Later, this is reused to instantiate the fuzzer::EF global in a way that prevents heap use-after-frees when running with --gtest_repeat=N for N > 1. The unit tests were broken when using this feature, but repeating tests was absolutely critical to hunting down flake in later changes adding the IPC layer.

[morehouse]

compiler-rt/lib/fuzzer/tests/FuzzerTestUtil.h

44

67

Nit: Let's use a single naming convention, either "Stop" or "End"

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

702

What does EXPECT_NO_FATAL_FAILURE do here? How is this line different from just CheckEncodedFeatures(...)?

[aarongreen]

Address morehouse's comments.

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

702

This is me juggling too many changes simultaneously. When the features files become DSO-relative, CheckEncodedFeatures gets a few ASSERT_...(...) statements. Until then, you are correct, these aren't needed.

[aarongreen]

Multiprocess fuzzing will not be supported by the libFuzzer maintainers. Fuchsia has implemented a new approach with their Component Fuzzing Framework (RFC-117).

compiler-rt/lib/fuzzer/FuzzerFork.h

 
 #include "FuzzerDefs.h"
 #include "FuzzerOptions.h"
 #include "FuzzerRandom.h"
 
 #include <string>
 
 namespace fuzzer {
+
 void FuzzWithFork(Random &Rand, const FuzzingOptions &Options,
                   const Vector<std::string> &Args,
                   const Vector<std::string> &CorpusDirs, int NumJobs);
+
+void EncodeFeatures(const Vector<uint32_t> &Features,
+                    Vector<uint32_t> *Encoded);
+bool DecodeFeatures(const Vector<uint32_t> &Encoded,
+                    Vector<uint32_t> *Features);
+
 } // namespace fuzzer
 
 #endif // LLVM_FUZZER_FORK_H

compiler-rt/lib/fuzzer/FuzzerFork.cpp

void RunOneMergeJob(FuzzJob *Job) {
     // Choose only those inputs that have new features.
     GetSizedFilesFromDir(Job->CorpusDir, &TempFiles);
     std::sort(TempFiles.begin(), TempFiles.end());
     for (auto &F : TempFiles) {
       auto FeatureFile = F.File;
       FeatureFile.replace(0, Job->CorpusDir.size(), Job->FeaturesDir);
       auto FeatureBytes = FileToVector(FeatureFile, 0, false);
       assert((FeatureBytes.size() % sizeof(uint32_t)) == 0);
-      Vector<uint32_t> NewFeatures(FeatureBytes.size() / sizeof(uint32_t));
-      memcpy(NewFeatures.data(), FeatureBytes.data(), FeatureBytes.size());
-      for (auto Ft : NewFeatures) {
-        if (!Features.count(Ft)) {
+      Vector<uint32_t> Encoded(FeatureBytes.size() / sizeof(uint32_t));
+      memcpy(Encoded.data(), FeatureBytes.data(), FeatureBytes.size());
+      Vector<uint32_t> 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 "
            "oom/timeout/crash: %zd/%zd/%zd time: %zds job: %zd dft_time: %d\n",
            NumRuns, Cov.size(), Features.size(), Files.size(),
            Stats.average_exec_per_sec, NumOOMs, NumTimeouts, NumCrashes,
            secondsSinceProcessStartUp(), Job->JobId, Job->DftTimeInSeconds);
 
void FuzzWithFork(Random &Rand, const FuzzingOptions &Options,
   RmDirRecursive(Env.TempDir);
 
   // Use the exit code from the last child process.
   Printf("INFO: exiting: %d time: %zds\n", ExitCode,
          Env.secondsSinceProcessStartUp());
   exit(ExitCode);
 }
 
+void EncodeFeatures(const Vector<uint32_t> &Features,
+                    Vector<uint32_t> *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<uint32_t> &Encoded,
+                    Vector<uint32_t> *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

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

 //===- FuzzerLoop.cpp - Fuzzer's main loop --------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 // Fuzzer's main loop.
 //===----------------------------------------------------------------------===//
 
 #include "FuzzerCorpus.h"
+#include "FuzzerFork.h"
 #include "FuzzerIO.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMutate.h"
 #include "FuzzerPlatform.h"
 #include "FuzzerRandom.h"
 #include "FuzzerTracePC.h"
 #include <algorithm>
 #include <cstring>
if (TimeOfUnit > Threshhold && TimeOfUnit >= Options.ReportSlowUnits) {
     Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds);
     WriteUnitToFileWithPrefix({Data, Data + Size}, "slow-unit-");
   }
 }
 
 static void WriteFeatureSetToFile(const std::string &FeaturesDir,
                                   const std::string &FileName,
                                   const Vector<uint32_t> &FeatureSet) {
-  if (FeaturesDir.empty() || FeatureSet.empty()) return;
-  WriteToFile(reinterpret_cast<const uint8_t *>(FeatureSet.data()),
-              FeatureSet.size() * sizeof(FeatureSet[0]),
+  if (FeaturesDir.empty() || FeatureSet.empty())
+    return;
+  Vector<uint32_t> Encoded;
+  EncodeFeatures(FeatureSet, &Encoded);
+  WriteToFile(reinterpret_cast<const uint8_t *>(Encoded.data()),
+              Encoded.size() * sizeof(Encoded[0]),
               DirPlusFile(FeaturesDir, FileName));
 }
 
 static void RenameFeatureSetFile(const std::string &FeaturesDir,
                                  const std::string &OldFile,
                                  const std::string &NewFile) {
   if (FeaturesDir.empty()) return;
   RenameFile(DirPlusFile(FeaturesDir, OldFile),

compiler-rt/lib/fuzzer/tests/CMakeLists.txt

if(CMAKE_SYSTEM_NAME STREQUAL "Linux" AND
     set(LIBFUZZER_TEST_RUNTIME_LINK_FLAGS ${LIBCXX_${arch}_PREFIX}/lib/libc++.a)
   endif()
 
   set(FuzzerTestObjects)
   generate_compiler_rt_tests(FuzzerTestObjects
     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
     RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
 
   set(FuzzedDataProviderTestObjects)
   generate_compiler_rt_tests(FuzzedDataProviderTestObjects
     FuzzedDataProviderUnitTests "FuzzerUtils-${arch}-Test" ${arch}
     SOURCES FuzzedDataProviderUnittest.cpp ${COMPILER_RT_GTEST_SOURCE}
     DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} ${COMPILER_RT_SOURCE_DIR}/include/fuzzer/FuzzedDataProvider.h
     CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS}
     LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS})
   set_target_properties(FuzzedDataProviderUnitTests PROPERTIES
     RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
 endif()

compiler-rt/lib/fuzzer/tests/FuzzerTestUtil.h

+//===- 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 <cstddef>
+#include <cstdint>
+#include <initializer_list>
+#include <memory>
+#include <vector>
+
+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 T>
+typename std::enable_if<std::is_integral<T>::value, T>::type Pick() {
+  return static_cast<T>(rand() & std::numeric_limits<T>::max());
+}
+
+template <typename T>
+typename std::enable_if<std::is_floating_point<T>::value, T>::type Pick() {
+  auto AbsVal = static_cast<T>(rand()) / static_cast<T>(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=<n>. Avoid this by
+// declaring the FakeModule static within the test that adds it to the coverage.
+template <size_t N> 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<uintptr_t>() & ((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<uint16_t>();
+    }
+  }
+
+  uint8_t *CountersEnd() { return Counters + N; }
+  uintptr_t *PCsEnd() { return PCs + (N * 2); }
+
+  TracePC::PCTableEntry *GetPCTableEntries() {
+    return reinterpret_cast<TracePC::PCTableEntry *>(PCs);
+  }
+};
+
+} // namespace fuzzer
+
+#endif // LLVM_FUZZER_TEST_UTIL_H

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

 // 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
 
 // Avoid ODR violations (LibFuzzer is built without ASan and this test is built
 // with ASan) involving C++ standard library types when using libcxx.
 #define _LIBCPP_HAS_NO_ASAN
 
 // Do not attempt to use LLVM ostream etc from gtest.
 #define GTEST_NO_LLVM_SUPPORT 1
 
 #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 <memory>
 #include <set>
 #include <sstream>
 
 using namespace fuzzer;
 
 // For now, have LLVMFuzzerTestOneInput just to make it link.

 }
 
 #define TRACED_EQ(A, ...)                                                      \
   {                                                                            \
     SCOPED_TRACE(#A);                                                          \
     EQ(A, __VA_ARGS__);                                                        \
   }
 
+template <size_t N>
+void CheckEncodedFeatures(FakeModule<N> &M, bool UseCounters) {
+  // Ensure the module has been added to the TracePC
+  auto *B = reinterpret_cast<const TracePC::PCTableEntry *>(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<uint32_t> 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<uint32_t> Features, Actual;
+  TPC.CollectFeatures(
+      [&](size_t F) { Features.push_back(static_cast<uint32_t>(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<uint32_t> 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;
 
   const char *kInvalidInputs[] = {
       // Bad file numbers
       "",
       "x",
       "0\n0",
TEST(Entropic, ComputeEnergy) {
   II->FeatureFreqs.push_back(std::pair<uint32_t, uint16_t>(42, 6));
   II->NumExecutedMutations = 20;
   II->UpdateEnergy(10, false, std::chrono::microseconds(0));
   EXPECT_LT(SubAndSquare(II->Energy, 1.792831), Precision);
 }
 
 int main(int argc, char **argv) {
   testing::InitGoogleTest(&argc, argv);
+  testing::AddGlobalTestEnvironment(new fuzzer::TestEnvironment());
   return RUN_ALL_TESTS();
 }