From c015c9fee1e0af4d3a1da2ff435b020ff107abd8 Mon Sep 17 00:00:00 2001
From: Bruce He <44327446+zm2he@users.noreply.github.com>
Date: Wed, 26 Jul 2023 21:09:22 +0000
Subject: Add a Fuzzer for Lattice and Transfer Function Properties (#5831)
This change adds a fuzzer which checks the following properties in
abstract interpretation static analyses.
- Transfer Function Monotonicity
- Lattice Element Reflexivity
- Lattice Element Transitivity
- Lattice Element Anti-Symmetry
This is done by randomly generating a module and using its functions as
transfer function inputs, along with randomly generated lattice elements
(states). Lattice element properties are fuzzed from the randomly
generated states also.
---
src/analysis/lattice.h | 12 +
src/tools/CMakeLists.txt | 1 +
src/tools/wasm-fuzz-lattices.cpp | 509 +++++++++++++++++++++++++++++++++++++++
3 files changed, 522 insertions(+)
create mode 100644 src/tools/wasm-fuzz-lattices.cpp
(limited to 'src')
diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
index 5ab92a320..a5c7047dd 100644
--- a/src/analysis/lattice.h
+++ b/src/analysis/lattice.h
@@ -11,6 +11,18 @@ namespace wasm::analysis {
enum LatticeComparison { NO_RELATION, EQUAL, LESS, GREATER };
+// If parameter "comparison" compares x and y, the function returns the opposite
+// direction comparison between y and x.
+inline LatticeComparison reverseComparison(LatticeComparison comparison) {
+ if (comparison == LatticeComparison::LESS) {
+ return LatticeComparison::GREATER;
+ } else if (comparison == LatticeComparison::GREATER) {
+ return LatticeComparison::LESS;
+ } else {
+ return comparison;
+ }
+}
+
template<typename Lattice>
constexpr bool has_getBottom =
std::is_invocable_r<typename Lattice::Element,
diff --git a/src/tools/CMakeLists.txt b/src/tools/CMakeLists.txt
index 3d12b4e34..c73797f54 100644
--- a/src/tools/CMakeLists.txt
+++ b/src/tools/CMakeLists.txt
@@ -19,6 +19,7 @@ if(NOT BUILD_EMSCRIPTEN_TOOLS_ONLY)
binaryen_add_executable(wasm-reduce wasm-reduce.cpp)
binaryen_add_executable(wasm-merge wasm-merge.cpp)
binaryen_add_executable(wasm-fuzz-types "${fuzzing_SOURCES};wasm-fuzz-types.cpp")
+ binaryen_add_executable(wasm-fuzz-lattices "${fuzzing_SOURCES};wasm-fuzz-lattices.cpp")
endif()
add_subdirectory(wasm-split)
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
new file mode 100644
index 000000000..c31d64290
--- /dev/null
+++ b/src/tools/wasm-fuzz-lattices.cpp
@@ -0,0 +1,509 @@
+/*
+ * Copyright 2023 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <optional>
+#include <random>
+#include <string>
+
+#include "analysis/lattice.h"
+#include "analysis/liveness-transfer-function.h"
+#include "analysis/reaching-definitions-transfer-function.h"
+
+#include "support/command-line.h"
+#include "tools/fuzzing.h"
+#include "tools/fuzzing/random.h"
+
+namespace wasm {
+using RandEngine = std::mt19937_64;
+using namespace analysis;
+
+// Helps printing error messages.
+std::string LatticeComparisonNames[4] = {
+ "No Relation", "Equal", "Less", "Greater"};
+std::string LatticeComparisonSymbols[4] = {"?", "=", "<", ">"};
+
+uint64_t getSeed() {
+ // Return a (truly) random 64-bit value.
+ std::random_device rand;
+ return std::uniform_int_distribution<uint64_t>{}(rand);
+}
+
+// Utility class which provides methods to check properties of the transfer
+// function and lattice of an analysis.
+template<typename Lattice, typename TransferFunction> struct AnalysisChecker {
+ Lattice& lattice;
+ TransferFunction& transferFunction;
+ std::string latticeName;
+ std::string transferFunctionName;
+ uint64_t latticeElementSeed;
+ Name funcName;
+
+ AnalysisChecker(Lattice& lattice,
+ TransferFunction& transferFunction,
+ std::string latticeName,
+ std::string transferFunctionName,
+ uint64_t latticeElementSeed,
+ Name funcName)
+ : lattice(lattice), transferFunction(transferFunction),
+ latticeName(latticeName), transferFunctionName(transferFunctionName),
+ latticeElementSeed(latticeElementSeed), funcName(funcName) {}
+
+ void printFailureInfo(std::ostream& os) {
+ os << "Error for " << transferFunctionName << " and " << latticeName
+ << " at lattice element seed " << latticeElementSeed << " and function "
+ << funcName << ".\n";
+ }
+
+ // Prints information about a particular test case consisting of a randomly
+ // generated function and triple of randomly generate lattice elements.
+ void printVerboseFunctionCase(std::ostream& os,
+ typename Lattice::Element& x,
+ typename Lattice::Element& y,
+ typename Lattice::Element& z) {
+ os << "Using lattice element seed " << latticeElementSeed << "\nGenerated "
+ << latticeName << " elements:\n";
+ x.print(os);
+ os << ",\n";
+ y.print(os);
+ os << ",\n";
+ z.print(os);
+ os << "\nfor " << funcName << " to test " << transferFunctionName
+ << ".\n\n";
+ }
+
+ // Checks reflexivity of a lattice element, i.e. x = x.
+ void checkReflexivity(typename Lattice::Element& element) {
+ LatticeComparison result = lattice.compare(element, element);
+ if (result != LatticeComparison::EQUAL) {
+ std::stringstream ss;
+ printFailureInfo(ss);
+ ss << "Element ";
+ element.print(ss);
+ ss << " is not reflexive.\n";
+ Fatal() << ss.str();
+ }
+ }
+
+ // Anti-Symmetry is defined as x <= y and y <= x imply x = y. Due to the
+ // fact that the compare(x, y) function of the lattice explicitly tells
+ // us if two lattice elements are <, =, or = instead of providing a
+ // <= comparison, it is not useful to check for anti-symmetry as it is defined
+ // in the fuzzer.
+ //
+ // Instead, we check for a related concept that x < y implies y > x, and
+ // vice versa in this checkAntiSymmetry function.
+ void checkAntiSymmetry(typename Lattice::Element& x,
+ typename Lattice::Element& y) {
+ LatticeComparison result = lattice.compare(x, y);
+ LatticeComparison reverseResult = lattice.compare(y, x);
+
+ if (reverseComparison(result) != reverseResult) {
+ std::stringstream ss;
+ printFailureInfo(ss);
+ x.print(ss);
+ ss << " " << LatticeComparisonNames[result] << " ";
+ y.print(ss);
+ ss << " but reverse direction comparison is "
+ << LatticeComparisonNames[reverseResult] << ".\n";
+ Fatal() << ss.str();
+ }
+ }
+
+private:
+ // Prints the error message when a triple of lattice elements violates
+ // transitivity.
+ void printTransitivityError(std::ostream& os,
+ typename Lattice::Element& a,
+ typename Lattice::Element& b,
+ typename Lattice::Element& c,
+ LatticeComparison ab,
+ LatticeComparison bc,
+ LatticeComparison ac) {
+ printFailureInfo(os);
+ os << "Elements a = ";
+ a.print(os);
+ os << ", b = ";
+ b.print(os);
+ os << ", and c = ";
+ c.print(os);
+ os << " are not transitive. a" << LatticeComparisonSymbols[ab] << "b and b"
+ << LatticeComparisonSymbols[bc] << "c, but a"
+ << LatticeComparisonSymbols[ac] << "c.\n";
+ }
+
+ // Returns true if given a-b and b-c comparisons, the a-c comparison violates
+ // transitivity.
+ bool violatesTransitivity(LatticeComparison ab,
+ LatticeComparison bc,
+ LatticeComparison ac) {
+ if (ab != LatticeComparison::NO_RELATION &&
+ (bc == LatticeComparison::EQUAL || bc == ab) && ab != ac) {
+ return true;
+ } else if (bc != LatticeComparison::NO_RELATION &&
+ (ab == LatticeComparison::EQUAL || ab == bc) && bc != ac) {
+ return true;
+ }
+ return false;
+ }
+
+public:
+ // Given three lattice elements x, y, and z, checks if transitivity holds
+ // between them.
+ void checkTransitivity(typename Lattice::Element& x,
+ typename Lattice::Element& y,
+ typename Lattice::Element& z) {
+ LatticeComparison xy = lattice.compare(x, y);
+ LatticeComparison yz = lattice.compare(y, z);
+ LatticeComparison xz = lattice.compare(x, z);
+
+ LatticeComparison yx = reverseComparison(xy);
+ LatticeComparison zy = reverseComparison(yz);
+
+ // Cover all permutations of x, y, and z.
+ if (violatesTransitivity(xy, yz, xz)) {
+ std::stringstream ss;
+ printTransitivityError(ss, x, y, z, xy, yz, xz);
+ Fatal() << ss.str();
+ } else if (violatesTransitivity(yx, xz, yz)) {
+ std::stringstream ss;
+ printTransitivityError(ss, y, x, z, yx, xz, yz);
+ Fatal() << ss.str();
+ } else if (violatesTransitivity(xz, zy, xy)) {
+ std::stringstream ss;
+ printTransitivityError(ss, x, z, y, xz, zy, xy);
+ Fatal() << ss.str();
+ }
+ }
+
+ // Given two input - output lattice pairs of a transfer function, checks if
+ // the transfer function is monotonic. If this is violated, then we print out
+ // the CFG block input which caused the transfer function to exhibit
+ // non-monotonic behavior.
+ void checkMonotonicity(const BasicBlock* cfgBlock,
+ typename Lattice::Element& first,
+ typename Lattice::Element& second,
+ typename Lattice::Element& firstResult,
+ typename Lattice::Element& secondResult) {
+ LatticeComparison beforeCmp = lattice.compare(first, second);
+ LatticeComparison afterCmp = lattice.compare(firstResult, secondResult);
+
+ // Cases in which monotonicity is preserved.
+ if (beforeCmp == LatticeComparison::NO_RELATION) {
+ // If there is no relation in the first place, we can't expect anything.
+ return;
+ } else if (beforeCmp == LatticeComparison::LESS &&
+ (afterCmp == LatticeComparison::LESS ||
+ afterCmp == LatticeComparison::EQUAL)) {
+ // x < y and f(x) <= f(y)
+ return;
+ } else if (beforeCmp == LatticeComparison::GREATER &&
+ (afterCmp == LatticeComparison::GREATER ||
+ afterCmp == LatticeComparison::EQUAL)) {
+ // x > y and f(x) >= f(y)
+ return;
+ } else if (beforeCmp == LatticeComparison::EQUAL &&
+ afterCmp == LatticeComparison::EQUAL) {
+ // x = y and f(x) = f(y)
+ return;
+ }
+
+ std::stringstream ss;
+ printFailureInfo(ss);
+
+ ss << "Elements ";
+ first.print(ss);
+ ss << " -> ";
+ firstResult.print(ss);
+ ss << " and ";
+ second.print(ss);
+ ss << " -> ";
+ secondResult.print(ss);
+ ss << "\n show that the transfer function is not monotone when given the "
+ "input:\n";
+ cfgBlock->print(ss);
+ ss << "\n";
+
+ Fatal() << ss.str();
+ }
+
+ // Checks lattice-only properties for a triple of lattices.
+ void checkLatticeElements(typename Lattice::Element x,
+ typename Lattice::Element y,
+ typename Lattice::Element z) {
+ checkReflexivity(x);
+ checkReflexivity(y);
+ checkReflexivity(z);
+ checkAntiSymmetry(x, y);
+ checkAntiSymmetry(x, z);
+ checkAntiSymmetry(y, z);
+ checkTransitivity(x, y, z);
+ }
+
+ // Checks transfer function relevant properties given a CFG and three input
+ // states. It does this by applying the transfer function on each CFG block
+ // using the same three input states each time and then checking properties on
+ // the inputs and outputs.
+ void checkTransferFunction(CFG& cfg,
+ typename Lattice::Element x,
+ typename Lattice::Element y,
+ typename Lattice::Element z) {
+ for (auto cfgIter = cfg.begin(); cfgIter != cfg.end(); ++cfgIter) {
+ // Apply transfer function on each lattice element.
+ typename Lattice::Element xResult = x;
+ transferFunction.transfer(&(*cfgIter), xResult);
+ typename Lattice::Element yResult = y;
+ transferFunction.transfer(&(*cfgIter), yResult);
+ typename Lattice::Element zResult = z;
+ transferFunction.transfer(&(*cfgIter), zResult);
+
+ // Check monotonicity for every pair of transfer function outputs.
+ checkMonotonicity(&(*cfgIter), x, y, xResult, yResult);
+ checkMonotonicity(&(*cfgIter), x, z, xResult, zResult);
+ checkMonotonicity(&(*cfgIter), y, z, yResult, zResult);
+ }
+ }
+};
+
+// Struct to set up and check liveness analysis lattice and transfer function.
+struct LivenessChecker {
+ LivenessTransferFunction transferFunction;
+ FiniteIntPowersetLattice lattice;
+ AnalysisChecker<FiniteIntPowersetLattice, LivenessTransferFunction> checker;
+ LivenessChecker(Function* func, uint64_t latticeElementSeed, Name funcName)
+ : lattice(func->getNumLocals()), checker(lattice,
+ transferFunction,
+ "FiniteIntPowersetLattice",
+ "LivenessTransferFunction",
+ latticeElementSeed,
+ funcName) {}
+
+ FiniteIntPowersetLattice::Element getRandomElement(Random& rand) {
+ FiniteIntPowersetLattice::Element result = lattice.getBottom();
+
+ // Uses rand to randomly select which members are to be included (i. e. flip
+ // bits in the bitvector).
+ for (size_t i = 0; i < lattice.getSetSize(); ++i) {
+ result.set(i, rand.oneIn(2));
+ }
+ return result;
+ }
+
+ // Runs all checks for liveness analysis.
+ void runChecks(CFG& cfg, Random& rand, bool verbose) {
+ FiniteIntPowersetLattice::Element x = getRandomElement(rand);
+ FiniteIntPowersetLattice::Element y = getRandomElement(rand);
+ FiniteIntPowersetLattice::Element z = getRandomElement(rand);
+
+ if (verbose) {
+ checker.printVerboseFunctionCase(std::cout, x, y, z);
+ }
+
+ checker.checkLatticeElements(x, y, z);
+ checker.checkTransferFunction(cfg, x, y, z);
+ }
+};
+
+// Struct to set up and check reaching definitions analysis lattice and transfer
+// function.
+struct ReachingDefinitionsChecker {
+ LocalGraph::GetSetses getSetses;
+ LocalGraph::Locations locations;
+ ReachingDefinitionsTransferFunction transferFunction;
+ AnalysisChecker<FinitePowersetLattice<LocalSet*>,
+ ReachingDefinitionsTransferFunction>
+ checker;
+ ReachingDefinitionsChecker(Function* func,
+ uint64_t latticeElementSeed,
+ Name funcName)
+ : transferFunction(func, getSetses, locations),
+ checker(transferFunction.lattice,
+ transferFunction,
+ "FinitePowersetLattice<LocalSet*>",
+ "ReachingDefinitionsTransferFunction",
+ latticeElementSeed,
+ funcName) {}
+
+ FinitePowersetLattice<LocalSet*>::Element getRandomElement(Random& rand) {
+ FinitePowersetLattice<LocalSet*>::Element result =
+ transferFunction.lattice.getBottom();
+
+ // Uses rand to randomly select which members are to be included (i. e. flip
+ // bits in the bitvector).
+ for (size_t i = 0; i < transferFunction.lattice.getSetSize(); ++i) {
+ result.set(i, rand.oneIn(2));
+ }
+ return result;
+ }
+
+ // Runs all checks for reaching definitions analysis.
+ void runChecks(CFG& cfg, Random& rand, bool verbose) {
+ FinitePowersetLattice<LocalSet*>::Element x = getRandomElement(rand);
+ FinitePowersetLattice<LocalSet*>::Element y = getRandomElement(rand);
+ FinitePowersetLattice<LocalSet*>::Element z = getRandomElement(rand);
+
+ if (verbose) {
+ checker.printVerboseFunctionCase(std::cout, x, y, z);
+ }
+
+ checker.checkLatticeElements(x, y, z);
+ checker.checkTransferFunction(cfg, x, y, z);
+ }
+};
+
+struct Fuzzer {
+ bool verbose;
+
+ Fuzzer(bool verbose) : verbose(verbose) {}
+
+ // Helper function to run per-function tests. latticeElementSeed is used to
+ // generate three lattice elements randomly. It is also used to select which
+ // analysis is to be tested for the function.
+ void runOnFunction(Function* func, uint64_t latticeElementSeed) {
+ RandEngine getFuncRand(latticeElementSeed);
+
+ // Fewer bytes are needed to generate three random lattices.
+ std::vector<char> funcBytes(128);
+ for (size_t i = 0; i < funcBytes.size(); i += sizeof(uint64_t)) {
+ *(uint64_t*)(funcBytes.data() + i) = getFuncRand();
+ }
+
+ Random rand(std::move(funcBytes));
+
+ CFG cfg = CFG::fromFunction(func);
+
+ switch (rand.upTo(2)) {
+ case 0: {
+ LivenessChecker livenessChecker(func, latticeElementSeed, func->name);
+ livenessChecker.runChecks(cfg, rand, verbose);
+ break;
+ }
+ default: {
+ ReachingDefinitionsChecker reachingDefinitionsChecker(
+ func, latticeElementSeed, func->name);
+ reachingDefinitionsChecker.runChecks(cfg, rand, verbose);
+ }
+ }
+ }
+
+ // Generates a module. The module is used as an input to fuzz transfer
+ // functions as well as randomly generated lattice element states. Lattice
+ // properties are also fuzzed from the randomly generated states.
+ void run(uint64_t seed,
+ uint64_t* latticeElementSeed = nullptr,
+ std::string* funcName = nullptr) {
+ RandEngine getRand(seed);
+ std::cout << "Running with seed " << seed << "\n";
+
+ // 4kb of random bytes should be enough for anyone!
+ std::vector<char> bytes(4096);
+ for (size_t i = 0; i < bytes.size(); i += sizeof(uint64_t)) {
+ *(uint64_t*)(bytes.data() + i) = getRand();
+ }
+
+ Module testModule;
+ TranslateToFuzzReader reader(testModule, std::move(bytes));
+ reader.build();
+
+ if (verbose) {
+ std::cout << "Generated test module: \n";
+ std::cout << testModule;
+ std::cout << "\n";
+ }
+
+ // If a specific function and lattice element seed is specified, only run
+ // that.
+ if (latticeElementSeed && funcName) {
+ runOnFunction(testModule.getFunction(*funcName), *latticeElementSeed);
+ return;
+ }
+
+ ModuleUtils::iterDefinedFunctions(testModule, [&](Function* func) {
+ uint64_t funcSeed = getRand();
+ runOnFunction(func, funcSeed);
+ });
+ }
+};
+
+} // namespace wasm
+
+int main(int argc, const char* argv[]) {
+ using namespace wasm;
+
+ const std::string WasmFuzzTypesOption = "wasm-fuzz-lattices options";
+
+ Options options("wasm-fuzz-lattices",
+ "Fuzz lattices for reflexivity, transitivity, and "
+ "anti-symmetry, and tranfer functions for monotonicity.");
+
+ std::optional<uint64_t> seed;
+ options.add("--seed",
+ "",
+ "Run a single workload generated by the given seed",
+ WasmFuzzTypesOption,
+ Options::Arguments::One,
+ [&](Options*, const std::string& arg) {
+ seed = uint64_t(std::stoull(arg));
+ });
+
+ std::optional<uint64_t> latticeElementSeed;
+ options.add("--lattice-element-seed",
+ "",
+ "Seed which generated the lattice elements to be checked.",
+ WasmFuzzTypesOption,
+ Options::Arguments::One,
+ [&](Options*, const std::string& arg) {
+ latticeElementSeed = uint64_t(std::stoull(arg));
+ });
+
+ std::optional<std::string> functionName;
+ options.add(
+ "--function-name",
+ "",
+ "Name of the function in the module generated by --seed to be checked.",
+ WasmFuzzTypesOption,
+ Options::Arguments::One,
+ [&](Options*, const std::string& arg) { functionName = arg; });
+
+ bool verbose = false;
+ options.add("--verbose",
+ "-v",
+ "Print extra information",
+ WasmFuzzTypesOption,
+ Options::Arguments::Zero,
+ [&](Options*, const std::string& arg) { verbose = true; });
+
+ options.parse(argc, argv);
+
+ Fuzzer fuzzer{verbose};
+ if (seed) {
+ if (latticeElementSeed && functionName) {
+ // Run test a single function and lattice element seed.
+ fuzzer.run(*seed, &(*latticeElementSeed), &(*functionName));
+ } else {
+ // Run just a single workload with the given seed.
+ fuzzer.run(*seed);
+ }
+ } else {
+ // Continuously run workloads with new randomly generated seeds.
+ size_t i = 0;
+ RandEngine nextSeed(getSeed());
+ while (true) {
+ std::cout << "Iteration " << ++i << "\n";
+ fuzzer.run(nextSeed());
+ }
+ }
+ return 0;
+}
--
cgit v1.2.3