[llvm-stress] Add a mutation fuzzing mode

[reames]

Summary

This change generalizes llvm-stress by adding a sub-command to mutate an input IR file. This involves splitting the existing functionality into a sub-command of it's own (though its still the default).

The main change for the existing behavior is the following:

1. An optional "generate" command is added. You can continue to not specify a sub-command, and we default to "generate" (i.e. legacy behavior.)
2. Several cl::opts which are specific to generate are moved under that sub-command. This is unfortunately, a breaking change. These options will no longer be accepted without an explicit sub-command being given, and the help text is moved under "llvm-stress help generate".

The newly added mode exposes the existing mutation logic used by our various libfuzzer based fuzzers. This allows the logic to be exercised, and used, when not linking against libfuzzer.

p.s. I know the command guide page needs rewritten. I figured I'd get initial feedback on the approach before doing so. That's definitely a blocker item for landing this.

[nikic]

Is there much overlap between llvm-stress generate and llvm-stress mutate? Maybe that should just be a separate llvm-mutate tool? (Just throwing this out there, not advocating for anything in particular...)

[Peter]

I have been working on FuzzMutate for half a year.
To FuzzMutate, generation and mutation is the same... generation is just initialize an empty module and them mutate.
So I don't think the function Generate() is necessary.
What you can do is initialize an empty Module("M", LLVMContext) and throw it to FuzzMutate.

Also, many features in Generate() have already been introduced into FuzzMutate.
IntroduceControlFlow is InsertCFGStrategy, works better if you add InsertPHIStrategy too.
FillFunction is InjectorStrategy
GenEmptyFunction is InsertFunctionCallStrategy, this strategy haven't been upstreamed yet. I am waiting for other diffs(https://reviews.llvm.org/D139894, :https://reviews.llvm.org/D139907) to be accepted before I send it for review.

I highly encourage you take look at IRMutator.h to see what strategies have been added.

[reames]

In D140239#4002162, @nikic wrote:

Is there much overlap between llvm-stress generate and llvm-stress mutate? Maybe that should just be a separate llvm-mutate tool? (Just throwing this out there, not advocating for anything in particular...)

I'm open to either option here.

My thinking went as follows:

1. They both related to generating test cases for fuzzing. (i.e the "stress" part of the name)
2. The generate mode is simply a mutator starting with an empty function. At the moment, the code is separate, but it might make sense to merge parts. (Or not, no concrete plans here.) From a usage perspective, a user might want to use both llvm-stress generate, and llvm-stress mutate (on an empty input) at some experimentally established frequency. (As right now, the two modes generate different patterns at different frequencies.)
3. As we adjust control knobs (i.e size, types, enable-disable flags), we're more likely to have a consistent interface if the tools in the same source.

[reames]

In D140239#4002213, @Peter wrote:

I highly encourage you take look at IRMutator.h to see what strategies have been added.

I have. That's what led to the motivation to expose this via a CLI tool. (i.e. this patch)

[Peter]

I think another interesting thing you can add is "How much do you want to mutate". mutateModule will only change the module once, i.e. insert one instruction, add one function(may be no one is using it), etc.

Can we add a command line arg --num-mutate= and default to, say 100, so we mutate the module 100 times before we return it.

Just a thought.

[reames]

In D140239#4002246, @Peter wrote:

I think another interesting thing you can all is "How much do you want to mutate". mutateModule will only change the module once, i.e. insert one instruction, add one function(may be no one is using it).

Can we add a command line arg --num-mutate= and default to, say 100, so we mutate the module 100 times before we return it.

Just a thought.

Good idea. If you don't mind I'll leave that to a follow up commit. I also want to add some command line control of which strategies to select from. Again, in a separate commit.

[reames]

In D140239#4002268, @reames wrote:

In D140239#4002246, @Peter wrote:

I think another interesting thing you can all is "How much do you want to mutate". mutateModule will only change the module once, i.e. insert one instruction, add one function(may be no one is using it).

Can we add a command line arg --num-mutate= and default to, say 100, so we mutate the module 100 times before we return it.

Just a thought.

Good idea. If you don't mind I'll leave that to a follow up commit. I also want to add some command line control of which strategies to select from. Again, in a separate commit.

After writing this, I wondered how we'd been testing the new mutation strategies. The answer turned out to be, we weren't. This will give a means to write tests for individual mutations going forward as well.

[Peter]

In D140239#4002352, @reames wrote:

In D140239#4002268, @reames wrote:

In D140239#4002246, @Peter wrote:

I think another interesting thing you can all is "How much do you want to mutate". mutateModule will only change the module once, i.e. insert one instruction, add one function(may be no one is using it).

Can we add a command line arg --num-mutate= and default to, say 100, so we mutate the module 100 times before we return it.

Just a thought.

Good idea. If you don't mind I'll leave that to a follow up commit. I also want to add some command line control of which strategies to select from. Again, in a separate commit.

After writing this, I wondered how we'd been testing the new mutation strategies. The answer turned out to be, we weren't. This will give a means to write tests for individual mutations going forward as well.

Sorry I don't understand what do you mean by we are not testing mutation strategies.

If you mean unit testing, we actually have hand written modules and try it on strategies in llvm/unittests/FuzzMutate/StrategiesTest.cpp.
If you mean more large scale end-to-end testing, I have been using these strategies the whole winter so they should be good.

[reames]

In D140239#4002453, @Peter wrote:

In D140239#4002352, @reames wrote:

In D140239#4002268, @reames wrote:

In D140239#4002246, @Peter wrote:

I think another interesting thing you can all is "How much do you want to mutate". mutateModule will only change the module once, i.e. insert one instruction, add one function(may be no one is using it).

Can we add a command line arg --num-mutate= and default to, say 100, so we mutate the module 100 times before we return it.

Just a thought.

Good idea. If you don't mind I'll leave that to a follow up commit. I also want to add some command line control of which strategies to select from. Again, in a separate commit.

After writing this, I wondered how we'd been testing the new mutation strategies. The answer turned out to be, we weren't. This will give a means to write tests for individual mutations going forward as well.

Sorry I don't understand what do you mean by we are not testing mutation strategies.

If you mean unit testing, we actually have hand written modules and try it on strategies in llvm/unittests/FuzzMutate/StrategiesTest.cpp.
If you mean more large scale end-to-end testing, I have been using these strategies the whole winter so they should be good.

Oops, my apologies. I'd glanced at a recent commit and looked for changes in test/. I had not spotted the unit test. That's entirely my error.

[Peter]

In D140239#4002462, @reames wrote:

In D140239#4002453, @Peter wrote:

In D140239#4002352, @reames wrote:

In D140239#4002268, @reames wrote:

In D140239#4002246, @Peter wrote:

I think another interesting thing you can all is "How much do you want to mutate". mutateModule will only change the module once, i.e. insert one instruction, add one function(may be no one is using it).

Can we add a command line arg --num-mutate= and default to, say 100, so we mutate the module 100 times before we return it.

Just a thought.

Good idea. If you don't mind I'll leave that to a follow up commit. I also want to add some command line control of which strategies to select from. Again, in a separate commit.

After writing this, I wondered how we'd been testing the new mutation strategies. The answer turned out to be, we weren't. This will give a means to write tests for individual mutations going forward as well.

Sorry I don't understand what do you mean by we are not testing mutation strategies.

If you mean unit testing, we actually have hand written modules and try it on strategies in llvm/unittests/FuzzMutate/StrategiesTest.cpp.
If you mean more large scale end-to-end testing, I have been using these strategies the whole winter so they should be good.

Oops, my apologies. I'd glanced at a recent commit and looked for changes in test/. I had not spotted the unit test. That's entirely my error.

NP. I'd also start from test/. Its a myth to me why the framework author put them in unittest/ so I have to follow suit when writing new tests :)

[nikic]

In D140239#4002223, @reames wrote:

In D140239#4002162, @nikic wrote:

Is there much overlap between llvm-stress generate and llvm-stress mutate? Maybe that should just be a separate llvm-mutate tool? (Just throwing this out there, not advocating for anything in particular...)

I'm open to either option here.

My thinking went as follows:

1. They both related to generating test cases for fuzzing. (i.e the "stress" part of the name)
2. The generate mode is simply a mutator starting with an empty function. At the moment, the code is separate, but it might make sense to merge parts. (Or not, no concrete plans here.) From a usage perspective, a user might want to use both llvm-stress generate, and llvm-stress mutate (on an empty input) at some experimentally established frequency. (As right now, the two modes generate different patterns at different frequencies.)
3. As we adjust control knobs (i.e size, types, enable-disable flags), we're more likely to have a consistent interface if the tools in the same source.

I think my main concern would be that llvm-stress generate is *not* just the same as llvm-stress mutate with an empty module -- it uses a different generation method with very different characteristics, so this might be a bit confusing.

Don't feel strong about this though, and the code looks fine to me. Might make sense to add a test with a fixed seed just as a basic sanity check?

llvm/tools/llvm-stress/llvm-stress.cpp

812

Any particular reason why this does not include all strategies?

[bjope]

I do not plan to give any review feedback at the moment. I've only touched this for legacy PM deprecation and I don't know much about the implementation details.

We do use llvm-stress downstream in some testing. But as long as we just use "generate" it looks like everything will be fine.

@uabelho: This will impact the options we've added downstream slightly, as we need to put them in the "subopts::Generate" category. But afaict that will be quite trivial.

[bjope]

llvm/tools/llvm-stress/llvm-stress.cpp

68

Maybe enough to say "Randomly mutates IR provided on standard in".

(to get rid of the repeated use of "provided")

[Peter]

In D140239#4011809, @bjope wrote:

I do not plan to give any review feedback at the moment. I've only touched this for legacy PM deprecation and I don't know much about the implementation details.

We do use llvm-stress downstream in some testing. But as long as we just use "generate" it looks like everything will be fine.

@uabelho: This will impact the options we've added downstream slightly, as we need to put them in the "subopts::Generate" category. But afaict that will be quite trivial.

Since I'm developing FuzzMutate most of my time, I am interested how you use llvm-stress downstream? If you have anything particular you want to generate I may write a strategy here upstream.

llvm/tools/llvm-stress/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   Core
+  FuzzMutate
   Support
   )
 
 add_llvm_tool(llvm-stress
   llvm-stress.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-stress/llvm-stress.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/Verifier.h"
+#include "llvm/FuzzMutate/FuzzerCLI.h"
+#include "llvm/FuzzMutate/IRMutator.h"
+#include "llvm/FuzzMutate/Operations.h"
+#include "llvm/IRReader/IRReader.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <memory>
 #include <string>
 #include <system_error>
 #include <vector>
 
 namespace llvm {
 
 static cl::OptionCategory StressCategory("Stress Options");
 
+namespace subopts {
+static cl::SubCommand
+    Generate("generate",
+             "Generate a new random IR file (default if no subcommand provided)");
+static cl::SubCommand
+    Mutate("mutate",
+           "Randomly mutates user provided IR provided on standard in");
+} // namespace subopts
+
+
 static cl::opt<unsigned> SeedCL("seed", cl::desc("Seed used for randomness"),
-                                cl::init(0), cl::cat(StressCategory));
+                                cl::init(0), cl::cat(StressCategory),
+                                cl::sub(*cl::AllSubCommands));
 
 static cl::opt<unsigned> SizeCL(
     "size",
     cl::desc("The estimated size of the generated function (# of instrs)"),
-    cl::init(100), cl::cat(StressCategory));
+    cl::init(100), cl::cat(StressCategory), cl::sub(subopts::Generate));
 
 static cl::opt<std::string> OutputFilename("o",
                                            cl::desc("Override output filename"),
                                            cl::value_desc("filename"),
-                                           cl::cat(StressCategory));
+                                           cl::cat(StressCategory),
+                                           cl::sub(*cl::AllSubCommands));
 
 static cl::list<StringRef> AdditionalScalarTypes(
-    "types", cl::CommaSeparated,
+    "types", cl::CommaSeparated, cl::cat(StressCategory),
+    cl::sub(subopts::Generate),
     cl::desc("Additional IR scalar types "
              "(always includes i1, i8, i16, i32, i64, float and double)"));
 
 static cl::opt<bool> EnableScalableVectors(
     "enable-scalable-vectors",
     cl::desc("Generate IR involving scalable vector types"),
-    cl::init(false), cl::cat(StressCategory));
+    cl::init(false), cl::cat(StressCategory), cl::sub(subopts::Generate));
 
 
 namespace {
 
 /// A utility class to provide a pseudo-random number generator which is
 /// the same across all platforms. This is somewhat close to the libc
 /// implementation. Note: This is not a cryptographically secure pseudorandom
 /// number generator.
if (Curr != &F->getEntryBlock()) {
       BranchInst::Create(Curr, Next, Instr, Curr->getTerminator());
       Curr->getTerminator()->eraseFromParent();
     }
   }
 }
 
 } // end namespace llvm
 
-int main(int argc, char **argv) {
-  using namespace llvm;
 
-  InitLLVM X(argc, argv);
-  cl::HideUnrelatedOptions({&StressCategory, &getColorCategory()});
-  cl::ParseCommandLineOptions(argc, argv, "llvm codegen stress-tester\n");
-
-  LLVMContext Context;
-  auto M = std::make_unique<Module>("/tmp/autogen.bc", Context);
-  Function *F = GenEmptyFunction(M.get());
-
-  // Pick an initial seed value
-  Random R(SeedCL);
-  // Generate lots of random instructions inside a single basic block.
-  FillFunction(F, R);
-  // Break the basic block into many loops.
-  IntroduceControlFlow(F, R);
-
+static int WriteModule(Module &M) {
   // Figure out what stream we are supposed to write to...
   std::unique_ptr<ToolOutputFile> Out;
   // Default to standard output.
   if (OutputFilename.empty())
     OutputFilename = "-";
 
   std::error_code EC;
   Out.reset(new ToolOutputFile(OutputFilename, EC, sys::fs::OF_None));
   if (EC) {
     errs() << EC.message() << '\n';
     return 1;
   }
 
   // Check that the generated module is accepted by the verifier.
-  if (verifyModule(*M.get(), &Out->os()))
+  if (verifyModule(M, &Out->os()))
     report_fatal_error("Broken module found, compilation aborted!");
 
   // Output textual IR.
-  M->print(Out->os(), nullptr);
+  M.print(Out->os(), nullptr);
 
   Out->keep();
-
   return 0;
 }
+
+static int Generate() {
+  LLVMContext Context;
+  auto M = std::make_unique<Module>("/tmp/autogen.bc", Context);
+  Function *F = GenEmptyFunction(M.get());
+
+  // Pick an initial seed value
+  Random R(SeedCL);
+  // Generate lots of random instructions inside a single basic block.
+  FillFunction(F, R);
+  // Break the basic block into many loops.
+  IntroduceControlFlow(F, R);
+
+  return WriteModule(*M);
+}
+
+static int GetBitcodeSizeInBytes(Module &M) {
+  std::string Buf;
+  raw_string_ostream OS(Buf);
+  WriteBitcodeToFile(M, OS);
+  return Buf.size();
+}
+
+static int Mutate() {
+  // TODO: Refactor to share this with Generate command, and generalize option
+  // to apply here too.
+  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());
+  Strategies.emplace_back(new InstModificationIRStrategy());
+
+  std::unique_ptr<IRMutator> Mutator =
+    std::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
+
+  LLVMContext Context;
+  SMDiagnostic SM;
+  std::unique_ptr<Module> M = parseIRFile("-",  SM, Context);
+
+  if (verifyModule(*M, &errs())) {
+    errs() << "Input module does not verify\n";
+    return 1;
+  }
+
+  // TODO: If the input was bitcode already, there is a really
+  // inefficient size check.
+  const int CurSize = GetBitcodeSizeInBytes(*M);
+  const int MaxSize = 1024;
+  Mutator->mutateModule(*M, SeedCL, CurSize, MaxSize);
+
+  // Output textual IR.
+  return WriteModule(*M);
+}
+
+int main(int argc, char **argv) {
+  InitLLVM X(argc, argv);
+  cl::HideUnrelatedOptions({&StressCategory, &getColorCategory()});
+  cl::ParseCommandLineOptions(argc, argv, "llvm codegen stress-tester\n");
+
+  if (subopts::Mutate)
+    return Mutate();
+  return Generate();
+}