Introduce llvm-opt-fuzzer for fuzzing optimization passes

[igor-laevsky]

Summary

Hi,

Seeing recent advances in fuzzing technologies for llvm (libFuzzer, FuzzMutate, OSSFuzz)
it's become reasonably simple to extend this approach for the general optimization
passes.

In this review I would like to propose a generic fuzzing target intended for the
optimization passes and various combinations of them. This is very initial implementation
which I tried to keep simple. Most of it's code is inherited from the llvm-isel-fuzzer.

This tool is intended to be run by the OSSFuzz, so interface is rather primitive.
User is only required to specify target triple and optimization pipeline using
the new pass manager syntax.

In general our primary goal here is to continuously run OSSFuzz testing for some of the llvm passes
which are not widely used (i.e passes which are not part of the default clang pipeline, IRCE,
Loop Predication, RS4GC and so on).

However I expect it would be simpler to start with the more popular passes just
to have a chance to stabilize infrastructure and figure out good workflow for the discovered bugs.
So after this tool is integrated to the tree (if no one will have objections), next step would be
to start OSSFuzz project for the InstCombine, as being single most used pass.

[kcc]

Answering the questions from e-mail (not on the code review tool): OSS-Fuzz does not support run-time flags and we don't plan to -- it will complicate so many things on our side and it will also encourage heavy-weight fuzzers (like this one).
So, yes, if we want this on oss-fuzz, it should require no flags (same hack as llmv-isel-fuzzer--foo-bar is ok).

[igor-laevsky]

Thanks for the comments. I updated the patch to support embedded "instcombine" option.

[bogner]

Repeating my comments from email, as it looks like they got missed.

tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp

134–139 ↗

(On Diff #121446)

These don't change from input to input do they? We should probably set this up in the initialize function.

141–160 ↗

(On Diff #121446)

Similarly here - we probably don't need to reconfigure the pass pipeline every time.

[bogner]

Please add a note about this fuzzer in docs/FuzzingLLVM.rst

lib/FuzzMutate/FuzzerCLI.cpp

48–49 ↗

(On Diff #121446)

We should add a new/separate handleExecNameEncodedFEOpts or handleExecNameEncodedPassList instead of adding this to BE opts. This fuzzer shouldn't need the backend options AFAIK.

[igor-laevsky]

Justin, I must have missed your comments in the email. I added documentation and replied inline.

[igor-laevsky]

lib/FuzzMutate/FuzzerCLI.cpp

48–49 ↗

(On Diff #121446)

Yes, I agree. I think best option is to write parametrised version of the handleExecNameEncodedBEOpts which would receive the desired mapping between "exec" options and command line options. However I would prefer to do this in a separate change to not clobber this one with the refactoring.
Do you think we can leave this code as-is for the initial submission?

tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp

134–139 ↗

(On Diff #121446)

I don't think we can do this. This is freshly created module, so we need to set correct target parameters during each invocation.

141–160 ↗

(On Diff #121446)

That was what I did initially. However libFuzzer complained about "number of mallocs didn't match number of free's" and disabled "LeakDetection after each iteration".

I suspect that somewhere in the pass manager something accumulates some state on each run, maybe to cache analysis results or something in this way. I don't really have good knowledge of this area, but having pass manager initialization on each iteration seems like a bulletproof solution from this kind of problems.

[bogner]

lib/FuzzMutate/FuzzerCLI.cpp

48–49 ↗

(On Diff #121446)

If that's what we end up doing this function has the wrong name, since IR passes really aren't BE (ie backend) options. I'd originally been thinking that there wouldn't be any real overlap between the option sets that are allowed here, but I guess the -march handling might be useful for some of the IR passes.

I'd really rather we just make a second function for "pass" options for now on the assumption that we won't really need the complexity of a fully general solution to embedding options in the filename.

tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp

134–139 ↗

(On Diff #121446)

Good point, this bit is fine.

141–160 ↗

(On Diff #121446)

My main concern here is that we'd like to minimize the work we do here as much as possible so that TestOneInput is fast. This is fine for now and we can maybe try to improve it later.

[igor-laevsky]

Added separate function to parse exec encoded options. It's almost direct copy of the backend variant, but I hope to refactor it in a follow up changes.

[bogner]

lib/FuzzMutate/FuzzerCLI.cpp

80–84 ↗

(On Diff #122243)

Why not assume everything that isn't an arch is a pass name and pass them all as a comma separated list to -passes=?

[igor-laevsky]

lib/FuzzMutate/FuzzerCLI.cpp

80–84 ↗

(On Diff #122243)

Some passes contain dashes in their names, and this doesn't work well with the option parser. Also syntax of the new pass manager includes braces and I'm not sure how good they are going to work in the executable file name.

So instead I decided to treat each option as an a alias for the predefined pipeline configuration. So for example someday we may have "safepoints" option which will expand into pipeline where PlaceSafepoints is followed by the RS4GC pass.

[bogner]

LGTM. We can iterate on this further in tree.

lib/FuzzMutate/FuzzerCLI.cpp

80–84 ↗

(On Diff #122243)

Fair enough, this seems reasonable for now.

[kcc]

I've added llvm-opt-fuzzer--x86_64-instcombine to oss-fuzz.
What would be other option combinations (expressed as binary names) worth adding?

[igor-laevsky]

Hi Kostya,

Thanks for doing that! My original thought was to start instcombine runs with the IR corpus. In my local experiments I found that using simple corpus gathered from the llvm-lit tests proves to be way more productive than non corpus runs. I found zero issues in about 10 hour runs without the corpus and with the corpus there were couple of failures during the first two minutes. However I also observed couple of crashes in the FuzzMutate itself, which I planned to fix first.

So the short answer to your question - next step is to use reasonable corpus for the instcombine, but first to fix all the immediate issues.

[kcc]

First trophy:
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=4210
Looks real. Did you see it?

Thanks for doing that! My original thought was to start instcombine runs with the IR corpus. In my local experiments I found that using simple corpus gathered from the llvm-lit tests proves to be way more productive than non corpus runs.

No surprise here!

I found zero issues in about 10 hour runs without the corpus and with the corpus there were couple of failures during the first two minutes.

Nice!

However I also observed couple of crashes in the FuzzMutate itself, which I planned to fix first.

So the short answer to your question - next step is to use reasonable corpus for the instcombine, but first to fix all the immediate issues.

Good strategy.

Ideally, a fuzz target would have an optional extra build rule.
that will create ${FUZZ_TARGET_NAME}_seed_corpus.zip so that
in https://github.com/google/oss-fuzz/blob/master/projects/llvm/build.sh
we just copy all such files to $OUT

[igor-laevsky]

In D39555#924678, @kcc wrote:

First trophy:
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=4210
Looks real. Did you see it?

Wow, that's cool :) I haven't seen this failure, think it's a new one.

Ideally, a fuzz target would have an optional extra build rule.
that will create ${FUZZ_TARGET_NAME}_seed_corpus.zip so that
in https://github.com/google/oss-fuzz/blob/master/projects/llvm/build.sh
we just copy all such files to $OUT

Thanks, I was just wondering on how to better handle corpus creation.

llvm/trunk/docs/FuzzingLLVM.rst

 (``aarch64``, ``x86_64``), optimization levels (``O0``, ``O2``), or specific
 keywords, like ``gisel`` for enabling global instruction selection. In this
 mode, the same example could be run like so:
 
 .. code-block:: shell
 
    % bin/llvm-isel-fuzzer--aarch64-O0-gisel <corpus-dir>
 
+llvm-opt-fuzzer
+---------------
+
+A |LLVM IR fuzzer| aimed at finding bugs in optimization passes.
+
+It receives optimzation pipeline and runs it for each fuzzer input.
+
+Interface of this fuzzer almost directly mirrors ``llvm-isel-fuzzer``. Both
+``mtriple`` and ``passes`` arguments are required. Passes are specified in a
+format suitable for the new pass manager.
+
+.. code-block:: shell
+
+   % bin/llvm-opt-fuzzer <corpus-dir> -ignore_remaining_args=1 -mtriple x86_64 -passes instcombine
+
+Similarly to the ``llvm-isel-fuzzer`` arguments in some predefined configurations
+might be embedded directly into the binary file name:
+
+.. code-block:: shell
+
+   % bin/llvm-opt-fuzzer--x86_64-instcombine <corpus-dir>
+
 llvm-mc-assemble-fuzzer
 -----------------------
 
 A |generic fuzzer| that fuzzes the MC layer's assemblers by treating inputs as
 target specific assembly.
 
 Note that this fuzzer has an unusual command line interface which is not fully
 compatible with all of libFuzzer's features. Fuzzer arguments must be passed

llvm/trunk/include/llvm/FuzzMutate/FuzzerCLI.h

 /// name (argv[0]). For example, a name like llvm-foo-fuzzer--aarch64-gisel
 /// might set up an AArch64 triple and the Global ISel selector. This should be
 /// called *before* parseFuzzerCLOpts if calling both.
 ///
 /// This is meant to be used for environments like OSS-Fuzz that aren't capable
 /// of passing in command line arguments in the normal way.
 void handleExecNameEncodedBEOpts(StringRef ExecName);
 
+/// Handle optimizer options which are encoded in the executable name.
+/// Same semantics as in 'handleExecNameEncodedBEOpts'.
+void handleExecNameEncodedOptimizerOpts(StringRef ExecName);
+
 using FuzzerTestFun = int (*)(const uint8_t *Data, size_t Size);
 using FuzzerInitFun = int (*)(int *argc, char ***argv);
 
 /// Runs a fuzz target on the inputs specified on the command line.
 ///
 /// Useful for testing fuzz targets without linking to libFuzzer. Finds inputs
 /// in the argument list in a libFuzzer compatible way.
 int runFuzzerOnInputs(int ArgC, char *ArgV[], FuzzerTestFun TestOne,
                       FuzzerInitFun Init = [](int *, char ***) { return 0; });
 
 } // end llvm namespace
 
 #endif // LLVM_FUZZMUTATE_FUZZER_CLI_H

llvm/trunk/lib/FuzzMutate/FuzzerCLI.cpp

void llvm::handleExecNameEncodedBEOpts(StringRef ExecName) {
   std::vector<const char *> CLArgs;
   CLArgs.reserve(Args.size());
   for (std::string &S : Args)
     CLArgs.push_back(S.c_str());
 
   cl::ParseCommandLineOptions(CLArgs.size(), CLArgs.data());
 }
 
+void llvm::handleExecNameEncodedOptimizerOpts(StringRef ExecName) {
+  // TODO: Refactor parts common with the 'handleExecNameEncodedBEOpts'
+  std::vector<std::string> Args{ExecName};
+
+  auto NameAndArgs = ExecName.split("--");
+  if (NameAndArgs.second.empty())
+    return;
+
+  SmallVector<StringRef, 4> Opts;
+  NameAndArgs.second.split(Opts, '-');
+  for (StringRef Opt : Opts) {
+    if (Opt.startswith("instcombine")) {
+      Args.push_back("-passes=instcombine");
+    } else if (Triple(Opt).getArch()) {
+      Args.push_back("-mtriple=" + Opt.str());
+    } else {
+      errs() << ExecName << ": Unknown option: " << Opt << ".\n";
+      exit(1);
+    }
+  }
+
+  errs() << NameAndArgs.first << ": Injected args:";
+  for (int I = 1, E = Args.size(); I < E; ++I)
+    errs() << " " << Args[I];
+  errs() << "\n";
+
+  std::vector<const char *> CLArgs;
+  CLArgs.reserve(Args.size());
+  for (std::string &S : Args)
+    CLArgs.push_back(S.c_str());
+
+  cl::ParseCommandLineOptions(CLArgs.size(), CLArgs.data());
+}
+
 int llvm::runFuzzerOnInputs(int ArgC, char *ArgV[], FuzzerTestFun TestOne,
                             FuzzerInitFun Init) {
   errs() << "*** This tool was not linked to libFuzzer.\n"
          << "*** No fuzzing will be performed.\n";
   if (int RC = Init(&ArgC, &ArgV)) {
     errs() << "Initialization failed\n";
     return RC;
   }

llvm/trunk/tools/llvm-opt-fuzzer/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  ${LLVM_TARGETS_TO_BUILD}
+  Analysis
+  BitWriter
+  CodeGen
+  Core
+  Coroutines
+  IPO
+  IRReader
+  InstCombine
+  Instrumentation
+  FuzzMutate
+  MC
+  ObjCARCOpts
+  ScalarOpts
+  Support
+  Target
+  TransformUtils
+  Vectorize
+  Passes
+)
+
+add_llvm_fuzzer(llvm-opt-fuzzer llvm-opt-fuzzer.cpp
+  DUMMY_MAIN DummyOptFuzzer.cpp)

llvm/trunk/tools/llvm-opt-fuzzer/DummyOptFuzzer.cpp

+//===--- DummyOptFuzzer.cpp - Entry point to sanity check the fuzzer ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of main so we can build and test without linking libFuzzer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/FuzzMutate/FuzzerCLI.h"
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size);
+extern "C" int LLVMFuzzerInitialize(int *argc, char ***argv);
+int main(int argc, char *argv[]) {
+    return llvm::runFuzzerOnInputs(argc, argv, LLVMFuzzerTestOneInput,
+                                   LLVMFuzzerInitialize);
+}

llvm/trunk/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp

+//===--- llvm-opt-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 optimization passes using libFuzzer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Bitcode/BitcodeReader.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/CodeGen/CommandFlags.h"
+#include "llvm/FuzzMutate/FuzzerCLI.h"
+#include "llvm/FuzzMutate/IRMutator.h"
+#include "llvm/FuzzMutate/Operations.h"
+#include "llvm/FuzzMutate/Random.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Passes/PassBuilder.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+
+using namespace llvm;
+
+static cl::opt<std::string>
+    TargetTripleStr("mtriple", cl::desc("Override target triple for module"));
+
+// Passes to run for this fuzzer instance. Expects new pass manager syntax.
+static cl::opt<std::string> PassPipeline(
+    "passes",
+    cl::desc("A textual description of the pass pipeline for testing"));
+
+static std::unique_ptr<IRMutator> Mutator;
+static std::unique_ptr<TargetMachine> TM;
+
+// This function is mostly copied from the llvm-isel-fuzzer.
+// TODO: Move this into FuzzMutate library and reuse.
+static std::unique_ptr<Module> parseModule(const uint8_t *Data, size_t Size,
+                                           LLVMContext &Context) {
+
+  if (Size <= 1)
+    // We get bogus data given an empty corpus - just create a new module.
+    return llvm::make_unique<Module>("M", 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());
+}
+
+// This function is copied from the llvm-isel-fuzzer.
+// TODO: Move this into FuzzMutate library and reuse.
+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> createOptMutator() {
+  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.push_back(
+      llvm::make_unique<InjectorIRStrategy>(
+          InjectorIRStrategy::getDefaultOps()));
+  Strategies.push_back(
+      llvm::make_unique<InstDeleterIRStrategy>());
+
+  return llvm::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) {
+
+  assert(Mutator &&
+      "IR mutator should have been created during fuzzer initialization");
+
+  LLVMContext Context;
+  auto M = parseModule(Data, Size, Context);
+  if (!M || verifyModule(*M, &errs())) {
+    errs() << "error: mutator input module is broken!\n";
+    return 0;
+  }
+
+  Mutator->mutateModule(*M, Seed, Size, MaxSize);
+
+#ifndef NDEBUG
+  if (verifyModule(*M, &errs())) {
+    errs() << "mutation result doesn't pass verification\n";
+    M->dump();
+    abort();
+  }
+#endif
+
+  return writeModule(*M, Data, MaxSize);
+}
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  assert(TM && "Should have been created during fuzzer initialization");
+
+  if (Size <= 1)
+    // We get bogus data given an empty corpus - ignore it.
+    return 0;
+
+  // Parse module
+  //
+
+  LLVMContext Context;
+  auto M = parseModule(Data, Size, Context);
+  if (!M || verifyModule(*M, &errs())) {
+    errs() << "error: input module is broken!\n";
+    return 0;
+  }
+
+  // Set up target dependant options
+  //
+
+  M->setTargetTriple(TM->getTargetTriple().normalize());
+  M->setDataLayout(TM->createDataLayout());
+  setFunctionAttributes(TM->getTargetCPU(), TM->getTargetFeatureString(), *M);
+
+  // Create pass pipeline
+  //
+
+  PassBuilder PB(TM.get());
+
+  LoopAnalysisManager LAM;
+  FunctionAnalysisManager FAM;
+  CGSCCAnalysisManager CGAM;
+  ModulePassManager MPM;
+  ModuleAnalysisManager MAM;
+
+  FAM.registerPass([&] { return PB.buildDefaultAAPipeline(); });
+  PB.registerModuleAnalyses(MAM);
+  PB.registerCGSCCAnalyses(CGAM);
+  PB.registerFunctionAnalyses(FAM);
+  PB.registerLoopAnalyses(LAM);
+  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+
+  bool Ok = PB.parsePassPipeline(MPM, PassPipeline, false, false);
+  assert(Ok && "Should have been checked during fuzzer initialization");
+
+  // Run passes which we need to test
+  //
+
+  MPM.run(*M, MAM);
+
+  // Check that passes resulted in a correct code
+  if (verifyModule(*M, &errs())) {
+    errs() << "Transformation resulted in an invalid module\n";
+    abort();
+  }
+
+  return 0;
+}
+
+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;
+
+  // Make sure we print the summary and the current unit when LLVM errors out.
+  install_fatal_error_handler(handleLLVMFatalError, nullptr);
+
+  // Initialize llvm
+  //
+
+  InitializeAllTargets();
+  InitializeAllTargetMCs();
+
+  PassRegistry &Registry = *PassRegistry::getPassRegistry();
+  initializeCore(Registry);
+  initializeCoroutines(Registry);
+  initializeScalarOpts(Registry);
+  initializeObjCARCOpts(Registry);
+  initializeVectorization(Registry);
+  initializeIPO(Registry);
+  initializeAnalysis(Registry);
+  initializeTransformUtils(Registry);
+  initializeInstCombine(Registry);
+  initializeInstrumentation(Registry);
+  initializeTarget(Registry);
+
+  // Parse input options
+  //
+
+  handleExecNameEncodedOptimizerOpts(*argv[0]);
+  parseFuzzerCLOpts(*argc, *argv);
+
+  // Create TargetMachine
+  //
+
+  if (TargetTripleStr.empty()) {
+    errs() << *argv[0] << ": -mtriple must be specified\n";
+    exit(1);
+  }
+  Triple TargetTriple = Triple(Triple::normalize(TargetTripleStr));
+
+  std::string Error;
+  const Target *TheTarget =
+      TargetRegistry::lookupTarget(MArch, TargetTriple, Error);
+  if (!TheTarget) {
+    errs() << *argv[0] << ": " << Error;
+    exit(1);
+  }
+
+  TargetOptions Options = InitTargetOptionsFromCodeGenFlags();
+  TM.reset(TheTarget->createTargetMachine(
+      TargetTriple.getTriple(), getCPUStr(), getFeaturesStr(),
+     Options, getRelocModel(), getCodeModel(), CodeGenOpt::Default));
+  assert(TM && "Could not allocate target machine!");
+
+  // Check that pass pipeline is specified and correct
+  //
+
+  if (PassPipeline.empty()) {
+    errs() << *argv[0] << ": at least one pass should be specified\n";
+    exit(1);
+  }
+
+  PassBuilder PB(TM.get());
+  ModulePassManager MPM;
+  if (!PB.parsePassPipeline(MPM, PassPipeline, false, false)) {
+    errs() << *argv[0] << ": can't parse pass pipeline\n";
+    exit(1);
+  }
+
+  // Create mutator
+  //
+
+  Mutator = createOptMutator();
+
+  return 0;
+}