Implement llvm-isel-fuzzer for fuzzing instruction selection

[bogner]

Summary

This implements a fuzzer tool for instruction selection, as described in my EuroLLVM 2017 talk.

The fuzzer must be given both libFuzzer args and llc-like args to configure the backend. For example, to fuzz AArch64 GlobalISel at -O0, you could invoke like so:

llvm-isel-fuzzer <corpus dirs> -ignore_remaining_args=1 \
                 -mtriple arm64-apple-ios -global-isel -O0

If you would like to seed the fuzzer with an initial corpus, simply provide a directory of valid LLVM bitcode (not textual IR) as one of the corpus dirs.

[kcc]

tools/llvm-isel-fuzzer/llvm-isel-fuzzer.cpp

111

You assume that libFuzzer will feed "\n" as a dummy input.
But this is not part of the contract.

117

currently the non-zero return value for LLVMFuzzerTestOneInput will call an error in libFuzzer.
Also, an ideal fuzz target must tolerate any kind of input, even if we never expect to see it.

[kcc]

tools/llvm-isel-fuzzer/llvm-isel-fuzzer.cpp

99

Will it be simpler and better to just assume that Size <= 1 is uninteresting and means a new module?

[bogner]

tools/llvm-isel-fuzzer/llvm-isel-fuzzer.cpp

99

Makes sense, I'll do that.

117

Calling an error is kind of the point here. We get here when the mutator can't do any work (due to MutateImpl giving up and returning ' ', which is also not part of the contract), but to return 0 would mean we just spin forever doing nothing rather than alert the user that there's a problem.

That said, this is much less of a problem now that the default max_len was bumped to 4096. When it was 64 you'd hit this very quickly if you forgot to override that. I'm fairly comfortable just returning zero here now, I think.

[kcc]

LGTM from fuzzing POV, let's see how this works.

Do you want me to also review https://reviews.llvm.org/D36274?
(I can't promise a detailed one until after Aug 21)

[bogner]

r311964

[kcc]

I've run ./bin/llvm-isel-fuzzer -ignore_remaining_args=1 -mtriple x86_64-unknown-linux-gnu for a few minutes and I got this:

25482==ERROR: AddressSanitizer: use-after-poison on address 0x621001698040 at pc 0x00000086c29f bp 0x7ffe31189870 sp 0x7ffe31189868

READ of size 8 at 0x621001698040 thread T0

#0 0x86c29e in llvm::SDNode::use_empty() const /usr/local/google/home/kcc/llvm/include/llvm/CodeGen/SelectionDAGNodes.h:666:35
#1 0x39bea98 in (anonymous namespace)::DAGCombiner::useDivRem(llvm::SDNode*) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:2778:31
#2 0x393fb48 in (anonymous namespace)::DAGCombiner::visitSDIV(llvm::SDNode*) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:2912:26
#3 0x392b092 in (anonymous namespace)::DAGCombiner::visit(llvm::SDNode*) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1488:40
#4 0x3929270 in (anonymous namespace)::DAGCombiner::combine(llvm::SDNode*) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1579:16
#5 0x3927a83 in (anonymous namespace)::DAGCombiner::Run(llvm::CombineLevel) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1427:18
#6 0x39268f9 in llvm::SelectionDAG::Combine(llvm::CombineLevel, llvm::AAResults*, llvm::CodeGenOpt::Level) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:17450:36
#7 0x3c43f89 in llvm::SelectionDAGISel::CodeGenAndEmitDAG() /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:744:13
#8 0x3c43654 in llvm::SelectionDAGISel::SelectBasicBlock(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, true>, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, true>, bool&) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:665:3
#9 0x3c42a8d in llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1609:7
#10 0x3c3de2f in llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) /usr/local/google/home/kcc/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:466:3

Impressive.
Let's get it to oss-fuzz!
(But as we discussed, need to encode the options in the binary name somehow)

tools/llvm-isel-fuzzer/CMakeLists.txt

+if( LLVM_USE_SANITIZE_COVERAGE )
+  include_directories(BEFORE
+    ${CMAKE_CURRENT_SOURCE_DIR}/../../lib/Fuzzer)
+
+  set(LLVM_LINK_COMPONENTS
+      ${LLVM_TARGETS_TO_BUILD}
+      Analysis
+      AsmPrinter
+      CodeGen
+      Core
+      FuzzMutate
+      IRReader
+      MC
+      ScalarOpts
+      SelectionDAG
+      Support
+      Target
+  )
+  add_llvm_tool(llvm-isel-fuzzer
+                llvm-isel-fuzzer.cpp)
+  target_link_libraries(llvm-isel-fuzzer
+                        LLVMFuzzer)
+endif()

tools/llvm-isel-fuzzer/llvm-isel-fuzzer.cpp

+//===--- llvm-isel-fuzzer.cpp - Fuzzer for instruction selection ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Tool to fuzz instruction selection using libFuzzer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInterface.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Bitcode/BitcodeReader.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/CodeGen/CommandFlags.h"
+#include "llvm/FuzzMutate/IRMutator.h"
+#include "llvm/FuzzMutate/Operations.h"
+#include "llvm/FuzzMutate/Random.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Target/TargetMachine.h"
+#include <random>
+
+#define DEBUG_TYPE "isel-fuzzer"
+
+using namespace llvm;
+
+static cl::opt<char>
+OptLevel("O",
+         cl::desc("Optimization level. [-O0, -O1, -O2, or -O3] "
+                  "(default = '-O2')"),
+         cl::Prefix,
+         cl::ZeroOrMore,
+         cl::init(' '));
+
+static cl::opt<std::string>
+TargetTriple("mtriple", cl::desc("Override target triple for module"));
+
+static std::unique_ptr<TargetMachine> TM;
+static std::unique_ptr<IRMutator> Mutator;
+
+static std::unique_ptr<Module> parseModule(const uint8_t *Data, size_t Size,
+                                           LLVMContext &Context) {
+  auto Buffer = MemoryBuffer::getMemBuffer(
+      StringRef(reinterpret_cast<const char *>(Data), Size), "Fuzzer input",
+      /*RequiresNullTerminator=*/false);
+
+  SMDiagnostic Err;
+  auto M = parseBitcodeFile(Buffer->getMemBufferRef(), Context);
+  if (Error E = M.takeError()) {
+    errs() << toString(std::move(E)) << "\n";
+    return nullptr;
+  }
+  return std::move(M.get());
+}
+
+static size_t writeModule(const Module &M, uint8_t *Dest, size_t MaxSize) {
+  std::string Buf;
+  {
+    raw_string_ostream OS(Buf);
+    WriteBitcodeToFile(&M, OS);
+  }
+  if (Buf.size() > MaxSize)
+    return 0;
+  memcpy(Dest, Buf.data(), Buf.size());
+  return Buf.size();
+}
+
+std::unique_ptr<IRMutator> createISelMutator() {
+  std::vector<TypeGetter> Types{
+      Type::getInt1Ty,  Type::getInt8Ty,  Type::getInt16Ty, Type::getInt32Ty,
+      Type::getInt64Ty, Type::getFloatTy, Type::getDoubleTy};
+
+  std::vector<std::unique_ptr<IRMutationStrategy>> Strategies;
+  Strategies.emplace_back(
+      new InjectorIRStrategy(InjectorIRStrategy::getDefaultOps()));
+  Strategies.emplace_back(new InstDeleterIRStrategy());
+
+  return make_unique<IRMutator>(std::move(Types), std::move(Strategies));
+}
+
+extern "C" LLVM_ATTRIBUTE_USED size_t LLVMFuzzerCustomMutator(
+    uint8_t *Data, size_t Size, size_t MaxSize, unsigned int Seed) {
+  LLVMContext Context;
+  std::unique_ptr<Module> M;
+  if (Size == 0 || (Size == 1 && *Data == '\n'))
+    // We get bogus data given an empty corpus - just create a new module.
+    M.reset(new Module("M", Context));
+  else
+    M = parseModule(Data, Size, Context);
+
+  Mutator->mutateModule(*M, Seed, Size, MaxSize);
+
+  return writeModule(*M, Data, MaxSize);
+}
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  if (Size == 0 || (Size == 1 && *Data == '\n'))
+    // We get bogus data given an empty corpus - ignore it.
+    return 0;
+  if (Size == 1 && *Data == ' ') {
+    // Getting here is probably a bug. Best to provide a coherent error.
+    errs() << "Mutator failed to make progress.\n";
+    return 1;
+  }
+
+  LLVMContext Context;
+  auto M = parseModule(Data, Size, Context);
+  if (!M || verifyModule(*M, &errs())) {
+    errs() << "error: input module is broken!\n";
+    return 1;
+  }
+
+  // Set up the module to build for our target.
+  M->setTargetTriple(TM->getTargetTriple().normalize());
+  M->setDataLayout(TM->createDataLayout());
+
+  // Build up a PM to do instruction selection.
+  legacy::PassManager PM;
+  TargetLibraryInfoImpl TLII(TM->getTargetTriple());
+  PM.add(new TargetLibraryInfoWrapperPass(TLII));
+  raw_null_ostream OS;
+  TM->addPassesToEmitFile(PM, OS, TargetMachine::CGFT_Null);
+  PM.run(*M);
+
+  return 0;
+}
+
+/// Parse command line options, but ignore anything before '--'.
+static void parseCLOptsAfterDashDash(int argc, char *argv[]) {
+  std::vector<const char *> CLArgs;
+  CLArgs.push_back(argv[0]);
+
+  int I = 1;
+  while (I < argc)
+    if (StringRef(argv[I++]).equals("-ignore_remaining_args=1"))
+      break;
+  while (I < argc)
+    CLArgs.push_back(argv[I++]);
+
+  cl::ParseCommandLineOptions(CLArgs.size(), CLArgs.data());
+}
+
+static void handleLLVMFatalError(void *, const std::string &Message, bool) {
+  // TODO: Would it be better to call into the fuzzer internals directly?
+  dbgs() << "LLVM ERROR: " << Message << "\n"
+         << "Aborting to trigger fuzzer exit handling.\n";
+  abort();
+}
+
+extern "C" LLVM_ATTRIBUTE_USED int LLVMFuzzerInitialize(int *argc,
+                                                        char ***argv) {
+  EnableDebugBuffering = true;
+
+  InitializeAllTargets();
+  InitializeAllTargetMCs();
+  InitializeAllAsmPrinters();
+  InitializeAllAsmParsers();
+
+  parseCLOptsAfterDashDash(*argc, *argv);
+
+  if (TargetTriple.empty()) {
+    errs() << *argv[0] << ": -mtriple must be specified\n";
+    return 1;
+  }
+
+  Triple TheTriple = Triple(Triple::normalize(TargetTriple));
+
+  // Get the target specific parser.
+  std::string Error;
+  const Target *TheTarget =
+      TargetRegistry::lookupTarget(MArch, TheTriple, Error);
+  if (!TheTarget) {
+    errs() << argv[0] << ": " << Error;
+    return 1;
+  }
+
+  // Set up the pipeline like llc does.
+  std::string CPUStr = getCPUStr(), FeaturesStr = getFeaturesStr();
+
+  CodeGenOpt::Level OLvl = CodeGenOpt::Default;
+  switch (OptLevel) {
+  default:
+    errs() << argv[0] << ": invalid optimization level.\n";
+    return 1;
+  case ' ': break;
+  case '0': OLvl = CodeGenOpt::None; break;
+  case '1': OLvl = CodeGenOpt::Less; break;
+  case '2': OLvl = CodeGenOpt::Default; break;
+  case '3': OLvl = CodeGenOpt::Aggressive; break;
+  }
+
+  TargetOptions Options = InitTargetOptionsFromCodeGenFlags();
+  TM.reset(TheTarget->createTargetMachine(TheTriple.getTriple(), CPUStr,
+                                          FeaturesStr, Options, getRelocModel(),
+                                          CMModel, OLvl));
+  assert(TM && "Could not allocate target machine!");
+
+  // Make sure we print the summary and the current unit when LLVM errors out.
+  install_fatal_error_handler(handleLLVMFatalError, nullptr);
+
+  // Finally, create our mutator.
+  Mutator = createISelMutator();
+  return 0;
+}