Add fuzzer::DSORelativeValues

[aarongreen]

Summary

This changes intoduces fuzzer::DSORelativeValues, which can be used to represent features and PC indices independent of the DSO load order. This is required for cross-process fuzzing that involves multiple loaders.

In this change, DSORelativeValues are only invoked by the unit tests. Subsequent changes will integrate with areas where coverage is compared across multiple invocations of the fuzzer.

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

[morehouse]

compiler-rt/lib/fuzzer/FuzzerDSORelative.h

54

[aarongreen]

Renamed DSO -> Module to be more in keeping with LLVM. Fixed a bug in calculating features that caused tests to fail when run with sanitizer instrumentation.

[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/CMakeLists.txt

 set(LIBFUZZER_SOURCES
   FuzzerCrossOver.cpp
   FuzzerDataFlowTrace.cpp
   FuzzerDriver.cpp
+  FuzzerDSORelative.cpp
   FuzzerExtFunctionsDlsym.cpp
   FuzzerExtFunctionsWeak.cpp
   FuzzerExtFunctionsWindows.cpp
   FuzzerExtraCounters.cpp
   FuzzerFork.cpp
   FuzzerIO.cpp
   FuzzerIOPosix.cpp
   FuzzerIOWindows.cpp

 set(LIBFUZZER_HEADERS
   FuzzerBuiltins.h
   FuzzerBuiltinsMsvc.h
   FuzzerCommand.h
   FuzzerCorpus.h
   FuzzerDataFlowTrace.h
   FuzzerDefs.h
   FuzzerDictionary.h
+  FuzzerDSORelative.h
   FuzzerExtFunctions.def
   FuzzerExtFunctions.h
   FuzzerFlags.def
   FuzzerFork.h
   FuzzerIO.h
   FuzzerInterface.h
   FuzzerInternal.h
   FuzzerMerge.h

compiler-rt/lib/fuzzer/FuzzerDSORelative.h

+//===- FuzzerDSORelative.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
+//
+//===----------------------------------------------------------------------===//
+// Load-order-agnostic features and PCs
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_DSO_RELATIVE_H
+#define LLVM_FUZZER_DSO_RELATIVE_H
+
+#include "FuzzerDefs.h"
+
+#include <map>
+
+namespace fuzzer {
+
+// This class represents an aggregation of sets of values associated with a DSO.
+// It provides methods for adding/removing additional DSOs and/or values.
+class DSORelativeValues final {
+public:
+  bool operator==(const DSORelativeValues &Other) const {
+    return ValuesMap == Other.ValuesMap;
+  }
+  const Set<uint32_t> *get(uint64_t Hash) const;
+  void clear() { ValuesMap.clear(); }
+
+  size_t NumDSOs() const { return ValuesMap.size(); }
+  size_t NumValuesForDSO(uint64_t Hash) const;
+  size_t NumValues() const;
+  size_t size() const { return NumValues(); }
+  bool empty() const { return ValuesMap.empty(); }
+
+  // If `OtherValues` is not empty, adds them to the set of values associated
+  // with `Hash`. If `NewValues` is provided, its contents are **replaced** with
+  // the values added. Returns true if any values were added, false otherwise.
+  bool Merge(uint64_t Hash, const Set<uint32_t> &OtherValues,
+             Set<uint32_t> *NewValues = nullptr);
+
+  // If `Other` is not empty, adds its values to this objects's. If `New` is
+  // provided, its **accumulates** the values added, i.e. `New` is NOT cleared
+  // first. Returns true if any values were added, false otherwise.
+  bool Merge(const DSORelativeValues &Other, DSORelativeValues *New = nullptr);
+
+  // Remove all values in this object with `Hash` that are in `OtherValues`.
+  void Deduplicate(uint64_t Hash, const Set<uint32_t> &OtherValues);
+
+  // Remove all values in this object that are also in `Other`.
+  void Deduplicate(const DSORelativeValues &Other);
+
+  // Returns true if all `OtherValues` are in this object with the given `Hash`;
+  // false otherwise.
+  bool Includes(uint64_t Hash, const Set<uint32_t> &OtherValues);
+
+  // Returns true if all values in `Other` are in this object; false otherwise.
+  bool Includes(const DSORelativeValues &Other);
+
+  template <typename Callback>
+  // void Callback(uint64_t Hash, uint32_t Value)
+  void ForEachValue(Callback CB) const {
+    for (auto &HashAndValues : ValuesMap)
+      for (auto Value : HashAndValues.second)
+        CB(HashAndValues.first, Value);
+  }
+
+private:
+  std::map<uint64_t, Set<uint32_t>> ValuesMap;
+};
+
+} // namespace fuzzer
+
+#endif // LLVM_FUZZER_DSO_RELATIVE_H

compiler-rt/lib/fuzzer/FuzzerDSORelative.cpp

+//===- FuzzerDSORelative.cpp ------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+// Load-order-agnostic features and PCs
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerDSORelative.h"
+#include <algorithm>
+
+namespace fuzzer {
+
+const Set<uint32_t> *DSORelativeValues::get(uint64_t Hash) const {
+  const auto &I = ValuesMap.find(Hash);
+  return I == ValuesMap.end() ? nullptr : &I->second;
+}
+
+size_t DSORelativeValues::NumValuesForDSO(uint64_t Hash) const {
+  auto I = ValuesMap.find(Hash);
+  return I == ValuesMap.end() ? 0 : I->second.size();
+}
+
+size_t DSORelativeValues::NumValues() const {
+  size_t Result = 0;
+  for (const auto &HashAndValues : ValuesMap)
+    Result += HashAndValues.second.size();
+  return Result;
+}
+
+bool DSORelativeValues::Merge(uint64_t Hash, const Set<uint32_t> &OtherValues,
+                              Set<uint32_t> *NewValues) {
+  if (OtherValues.empty())
+    return false;
+  auto &Values = ValuesMap[Hash];
+  Set<uint32_t> Tmp;
+  std::set_difference(OtherValues.begin(), OtherValues.end(), Values.begin(),
+                      Values.end(), std::inserter(Tmp, Tmp.begin()));
+  if (Tmp.empty())
+    return false;
+  Values.insert(Tmp.begin(), Tmp.end());
+  if (NewValues)
+    NewValues->swap(Tmp);
+  return true;
+}
+
+bool DSORelativeValues::Merge(const DSORelativeValues &Other,
+                              DSORelativeValues *New) {
+  bool FoundNew = false;
+  Set<uint32_t> Tmp;
+  Set<uint32_t> *NewValues = New ? &Tmp : nullptr;
+  for (auto &HashAndValues : Other.ValuesMap) {
+    if (Merge(HashAndValues.first, HashAndValues.second, NewValues)) {
+      FoundNew = true;
+      if (New)
+        New->Merge(HashAndValues.first, Tmp);
+    }
+  }
+  return FoundNew;
+}
+
+void DSORelativeValues::Deduplicate(uint64_t Hash,
+                                    const Set<uint32_t> &OtherValues) {
+  if (OtherValues.empty())
+    return;
+  auto I = ValuesMap.find(Hash);
+  if (I == ValuesMap.end())
+    return;
+  auto &Values = I->second;
+  Set<uint32_t> Tmp;
+  std::set_difference(Values.begin(), Values.end(), OtherValues.begin(),
+                      OtherValues.end(), std::inserter(Tmp, Tmp.begin()));
+  if (Tmp.empty())
+    ValuesMap.erase(Hash);
+  else
+    Values.swap(Tmp);
+}
+
+void DSORelativeValues::Deduplicate(const DSORelativeValues &Other) {
+  for (auto &HashAndValues : Other.ValuesMap)
+    Deduplicate(HashAndValues.first, HashAndValues.second);
+}
+
+bool DSORelativeValues::Includes(uint64_t Hash,
+                                 const Set<uint32_t> &OtherValues) {
+  if (OtherValues.empty())
+    return true;
+  const auto &I = ValuesMap.find(Hash);
+  if (I == ValuesMap.end())
+    return false;
+  auto &Values = I->second;
+  return std::includes(Values.begin(), Values.end(), OtherValues.begin(),
+                       OtherValues.end());
+}
+
+bool DSORelativeValues::Includes(const DSORelativeValues &Other) {
+  bool Result = true;
+  for (auto &HashAndValues : Other.ValuesMap)
+    Result &= Includes(HashAndValues.first, HashAndValues.second);
+  return Result;
+}
+
+} // namespace fuzzer

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 "FuzzerDSORelative.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"

 template <typename T> void EQ(const Vector<T> &A, const Vector<T> &B) {
   EXPECT_EQ(A, B);
 }
 
 template <typename T> void EQ(const Set<T> &A, const Vector<T> &B) {
   EXPECT_EQ(A, Set<T>(B.begin(), B.end()));
 }
 
+template <typename T> void EQ(const Set<T> *A, const Vector<T> &B) {
+  ASSERT_NE(A, nullptr);
+  EQ(*A, B);
+}
+
 void EQ(const Vector<MergeFileInfo> &A, const Vector<std::string> &B) {
   Set<std::string> a;
   for (const auto &File : A)
     a.insert(File.Name);
   Set<std::string> b(B.begin(), B.end());
   EXPECT_EQ(a, b);
 }
 
 #define TRACED_EQ(A, ...)                                                      \
   {                                                                            \
     SCOPED_TRACE(#A);                                                          \
     EQ(A, __VA_ARGS__);                                                        \
   }
 
+TEST(DSORelativeValues, Merge) {
+  DSORelativeValues A, B, New;
+  Set<uint32_t> NewValues;
+
+  auto ClearAll = [&]() {
+    A.clear();
+    B.clear();
+    New.clear();
+    NewValues.clear();
+  };
+
+  // Empty vector merged into empty object
+  ClearAll();
+  EXPECT_FALSE(A.Merge(0, {}));
+  EXPECT_EQ(A.size(), 0U);
+  EXPECT_EQ(A.get(0), nullptr);
+
+  // Empty object merged into empty object
+  ClearAll();
+  EXPECT_FALSE(A.Merge(B));
+  EXPECT_EQ(A.size(), 0U);
+
+  // Non-empty vector merged into empty object
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}));
+  EXPECT_EQ(A.size(), 3U);
+  TRACED_EQ(A.get(0), {1, 2, 3});
+
+  // Empty vector merged into non-empty object
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}));
+  EXPECT_FALSE(A.Merge(1, {}, &NewValues));
+  EXPECT_EQ(A.size(), 3U);
+  EXPECT_EQ(A.get(1), nullptr);
+  EXPECT_EQ(NewValues.size(), 0U);
+
+  // Empty object into non-empty object.
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}));
+  EXPECT_FALSE(A.Merge(B, &New));
+  EXPECT_EQ(A.size(), 3U);
+  EXPECT_EQ(New.size(), 0U);
+
+  // Non-empty object into empty object.
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}));
+  EXPECT_TRUE(B.Merge(A, &New));
+  EXPECT_EQ(B.size(), 3U);
+  TRACED_EQ(B.get(0), {1, 2, 3});
+  TRACED_EQ(New.get(0), {1, 2, 3});
+
+  // Multiple merges reset individual vectors.
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}, &NewValues));
+  TRACED_EQ(NewValues, {1, 2, 3});
+  EXPECT_TRUE(A.Merge(1, {4, 5, 6}, &NewValues));
+  TRACED_EQ(NewValues, {4, 5, 6});
+
+  // Multiple merges accumulate new values from object.
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}));
+  EXPECT_TRUE(B.Merge(A, &New));
+  A.clear();
+  EXPECT_TRUE(A.Merge(1, {4, 5, 6}));
+  EXPECT_TRUE(B.Merge(A, &New));
+  TRACED_EQ(New.get(0), {1, 2, 3});
+  TRACED_EQ(New.get(1), {4, 5, 6});
+
+  // Object is non-empty, but hashes do not match
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}));
+  EXPECT_TRUE(A.Merge(1, {4, 5, 6}, &NewValues));
+  EXPECT_EQ(A.size(), 6U);
+  TRACED_EQ(A.get(1), {4, 5, 6});
+  TRACED_EQ(NewValues, {4, 5, 6});
+
+  // Object is non-empty and hashes match, but values do not overlap
+  ClearAll();
+  EXPECT_TRUE(A.Merge(1, {4, 5, 6}));
+  EXPECT_TRUE(A.Merge(1, {7, 8, 9}, &NewValues));
+  EXPECT_EQ(A.size(), 6U);
+  TRACED_EQ(A.get(1), {4, 5, 6, 7, 8, 9});
+  TRACED_EQ(NewValues, {7, 8, 9});
+
+  // Object is non-empty, hashes match, and values fully overlap
+  ClearAll();
+  EXPECT_TRUE(A.Merge(1, {4, 5, 6, 7, 8, 9}));
+  EXPECT_FALSE(A.Merge(1, {4, 6, 8}, &NewValues));
+  EXPECT_EQ(A.size(), 6U);
+  TRACED_EQ(A.get(1), {4, 5, 6, 7, 8, 9});
+  EXPECT_EQ(NewValues.size(), 0U);
+
+  // Object is non-empty, hashes match, and values partially overlap
+  ClearAll();
+  EXPECT_TRUE(A.Merge(1, {4, 5, 6, 7, 8, 9}));
+  EXPECT_TRUE(A.Merge(1, {5, 10, 15}, &NewValues));
+  EXPECT_EQ(A.size(), 8U);
+  TRACED_EQ(A.get(1), {4, 5, 6, 7, 8, 9, 10, 15});
+  TRACED_EQ(NewValues, {10, 15});
+
+  // Non-empty object into non-empty object, with full, partial, and no overlaps
+  ClearAll();
+  EXPECT_TRUE(A.Merge(0, {1, 2, 3}));
+  EXPECT_TRUE(A.Merge(1, {4, 5, 6, 7, 8, 9, 10, 15}));
+  EXPECT_TRUE(B.Merge(0, {1, 2, 3}));
+  EXPECT_TRUE(B.Merge(1, {11, 12, 13, 14, 15}));
+  EXPECT_TRUE(B.Merge(2, {16, 17, 18}));
+  EXPECT_TRUE(A.Merge(B, &New));
+  EXPECT_EQ(A.size(), 18U);
+
+  TRACED_EQ(A.get(0), {1, 2, 3});
+  TRACED_EQ(A.get(1), {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
+  TRACED_EQ(A.get(2), {16, 17, 18});
+
+  EXPECT_EQ(New.get(0), nullptr);
+  TRACED_EQ(New.get(1), {11, 12, 13, 14});
+  TRACED_EQ(New.get(2), {16, 17, 18});
+}
+
+TEST(DSORelativeValues, Deduplicate) {
+  DSORelativeValues A, B;
+
+  // Remove empty vector from empty object
+  A.Deduplicate(0, {});
+  EXPECT_EQ(A.size(), 0U);
+
+  // Remove empty object from empty object
+  A.Deduplicate(B);
+  EXPECT_EQ(A.size(), 0U);
+
+  // Remove empty vector from non-empty object
+  A.Merge(0, {1, 2, 3, 4, 5});
+  A.Deduplicate(0, {});
+  EXPECT_EQ(A.size(), 5U);
+  TRACED_EQ(A.get(0), {1, 2, 3, 4, 5});
+
+  // Remove empty object from non-empty object
+  A.Deduplicate(B);
+  EXPECT_EQ(A.size(), 5U);
+  TRACED_EQ(A.get(0), {1, 2, 3, 4, 5});
+
+  // Remove vector without matching hash
+  A.Deduplicate(1, {1, 2, 3, 4, 5});
+  EXPECT_EQ(A.size(), 5U);
+  TRACED_EQ(A.get(0), {1, 2, 3, 4, 5});
+  EXPECT_EQ(A.get(1), nullptr);
+
+  // Remove object without matching hash
+  B.Merge(1, {1, 2, 3, 4, 5});
+  A.Deduplicate(B);
+  EXPECT_EQ(A.size(), 5U);
+  TRACED_EQ(A.get(0), {1, 2, 3, 4, 5});
+  EXPECT_EQ(A.get(1), nullptr);
+
+  // Remove partial vector with matching hash
+  A.Deduplicate(0, {2, 4});
+  EXPECT_EQ(A.size(), 3U);
+  TRACED_EQ(A.get(0), {1, 3, 5});
+
+  // Remove matching vector with matching hash
+  A.Deduplicate(0, {1, 3, 5});
+  EXPECT_EQ(A.size(), 0U);
+  EXPECT_EQ(A.get(0), nullptr);
+
+  // Remove object with full, partial and no matching values for hashes
+  A.clear();
+  A.Merge(0, {1, 2, 3});
+  A.Merge(1, {4, 5, 6});
+  A.Merge(2, {7, 8, 9});
+  A.Merge(3, {10, 11, 12});
+  B.clear();
+  B.Merge(0, {1, 2, 3});
+  B.Merge(1, {4, 6, 8});
+  B.Merge(2, {5, 10, 15});
+  B.Merge(4, {10, 11, 12});
+  A.Deduplicate(B);
+  EXPECT_EQ(A.size(), 7U);
+  EXPECT_EQ(A.get(0), nullptr);
+
+  TRACED_EQ(A.get(1), {5});
+  TRACED_EQ(A.get(2), {7, 8, 9});
+  TRACED_EQ(A.get(3), {10, 11, 12});
+  EXPECT_EQ(A.get(4), nullptr);
+}
+
+TEST(DSORelativeValues, Includes) {
+  DSORelativeValues A, B;
+
+  // Empty vector, object are trivially true.
+  EXPECT_TRUE(A.Includes(0, {}));
+  EXPECT_TRUE(A.Includes(B));
+
+  // Mismatched hash
+  A.Merge(0, {1, 2, 3});
+  EXPECT_FALSE(A.Includes(1, {1, 2, 3}));
+
+  // Exact match
+  EXPECT_TRUE(A.Includes(0, {1, 2, 3}));
+
+  // Subset
+  EXPECT_TRUE(A.Includes(0, {2, 3}));
+
+  // Object with extra hash
+  B.Merge(0, {1, 2, 3});
+  B.Merge(1, {4});
+  EXPECT_FALSE(A.Includes(B));
+
+  // Object with extra value
+  A.Merge(1, {4});
+  B.Merge(0, {4});
+  EXPECT_FALSE(A.Includes(B));
+
+  // Strict subset
+  A.Merge(0, {4, 5});
+  A.Merge(2, {6, 7});
+  EXPECT_TRUE(A.Includes(B));
+
+  // Same object
+  B.Merge(A);
+  EXPECT_TRUE(A.Includes(B));
+}
+
 void CollectEncodedFeatures(Vector<uint32_t> *Encoded) {
   Vector<uint32_t> Features;
   TPC.CollectFeatures(
       [&](size_t F) { Features.push_back(static_cast<uint32_t>(F)); });
   EncodeFeatures(Features, Encoded);
 }
 
 template <size_t N>