Index: compiler-rt/lib/fuzzer/CMakeLists.txt =================================================================== --- compiler-rt/lib/fuzzer/CMakeLists.txt +++ compiler-rt/lib/fuzzer/CMakeLists.txt @@ -2,6 +2,7 @@ FuzzerCrossOver.cpp FuzzerDataFlowTrace.cpp FuzzerDriver.cpp + FuzzerDSORelative.cpp FuzzerExtFunctionsDlsym.cpp FuzzerExtFunctionsWeak.cpp FuzzerExtFunctionsWindows.cpp @@ -30,6 +31,7 @@ FuzzerDataFlowTrace.h FuzzerDefs.h FuzzerDictionary.h + FuzzerDSORelative.h FuzzerExtFunctions.def FuzzerExtFunctions.h FuzzerFlags.def Index: compiler-rt/lib/fuzzer/FuzzerDSORelative.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/FuzzerDSORelative.h @@ -0,0 +1,74 @@ +//===- 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 + +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 *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 &OtherValues, + Set *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 &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 &OtherValues); + + // Returns true if all values in `Other` are in this object; false otherwise. + bool Includes(const DSORelativeValues &Other); + + template + // 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> ValuesMap; +}; + +} // namespace fuzzer + +#endif // LLVM_FUZZER_DSO_RELATIVE_H Index: compiler-rt/lib/fuzzer/FuzzerDSORelative.cpp =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/FuzzerDSORelative.cpp @@ -0,0 +1,104 @@ +//===- 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" + +namespace fuzzer { + +const Set *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 &OtherValues, + Set *NewValues) { + if (OtherValues.empty()) + return false; + auto &Values = ValuesMap[Hash]; + Set 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 Tmp; + Set *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 &OtherValues) { + if (OtherValues.empty()) + return; + auto I = ValuesMap.find(Hash); + if (I == ValuesMap.end()) + return; + auto &Values = I->second; + Set 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 &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 Index: compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp =================================================================== --- compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp +++ compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp @@ -10,6 +10,7 @@ #define GTEST_NO_LLVM_SUPPORT 1 #include "FuzzerCorpus.h" +#include "FuzzerDSORelative.h" #include "FuzzerDictionary.h" #include "FuzzerFork.h" #include "FuzzerInternal.h" @@ -624,6 +625,11 @@ EXPECT_EQ(A, Set(B.begin(), B.end())); } +template void EQ(const Set *A, const Vector &B) { + ASSERT_NE(A, nullptr); + EQ(*A, B); +} + void EQ(const Vector &A, const Vector &B) { Set a; for (const auto &File : A) @@ -638,6 +644,228 @@ EQ(A, __VA_ARGS__); \ } +TEST(DSORelativeValues, Merge) { + DSORelativeValues A, B, New; + Set 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 *Encoded) { Vector Features; TPC.CollectFeatures(