[FuzzMutate] Don't crash when we can't remove instruction from empty function

[igor-laevsky]

Summary

We don't need to crash when we decide to delete something from the empty function. It is possible that module has other non empty functions which we are going to choose on the next fuzzer iteration.

[bogner]

Looks good. I have a couple of comments about things we should think about, but I don't think they need to block us.

lib/FuzzMutate/IRMutator.cpp

150–151 ↗

(On Diff #124081)

This is reasonable and should fix the problem, but it would be kind of nice if we could also make it so the deleter strategy was never chosen in this case. That's pretty tricky with the current getWeight API (it doesn't really have enough information), but we should think about it for the future.

unittests/FuzzMutate/StrategiesTest.cpp

99–101 ↗

(On Diff #124081)

Thanks for adding the test! I'm not a huge fan of the probabilistic nature of it, but I can't think of a better way to do that without making either the sampler or the mutators quite a bit more complicated.

[igor-laevsky]

lib/FuzzMutate/IRMutator.cpp

150–151 ↗

(On Diff #124081)

I guess it boils down to the question of wether or not we want to guarantee "forward progress" of the mutator (i,e guarantee that at least some transformation is always performed). Initially I implemented more involved version of this change - if randomly chosen function appeared to be empty we would have picked the first non empty one and removed from it. Then if there would be no such function we would assert. However in the end I realised that forward progress guarantee is not that important considering the amount of tests OSSFuzz runs.

unittests/FuzzMutate/StrategiesTest.cpp

99–101 ↗

(On Diff #124081)

If it makes things slightly better - since seed is fixed this is deterministic with the given libc implementation. Hopefully there shouldn't be too much different implementations.

llvm/trunk/lib/FuzzMutate/IRMutator.cpp

 }
 
 void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
   auto RS = makeSampler<Instruction *>(IB.Rand);
   // Avoid terminators so we don't have to worry about keeping the CFG coherent.
   for (Instruction &Inst : instructions(F))
     if (!Inst.isTerminator())
       RS.sample(&Inst, /*Weight=*/1);
-  assert(!RS.isEmpty() && "No instructions to delete");
+  if (RS.isEmpty())
+    return;
+
   // Delete the instruction.
   mutate(*RS.getSelection(), IB);
   // Clean up any dead code that's left over after removing the instruction.
   eliminateDeadCode(F);
 }
 
 void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
   assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");

llvm/trunk/unittests/FuzzMutate/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
+  AsmParser
   Core
   FuzzMutate
   Support
   )
 
 add_llvm_unittest(FuzzMutateTests
   OperationsTest.cpp
   ReservoirSamplerTest.cpp
+  StrategiesTest.cpp
   )

llvm/trunk/unittests/FuzzMutate/StrategiesTest.cpp

+//===- InjectorIRStrategyTest.cpp - Tests for injector strategy -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/AsmParser/SlotMapping.h"
+#include "llvm/FuzzMutate/IRMutator.h"
+#include "llvm/FuzzMutate/Operations.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Support/SourceMgr.h"
+
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static constexpr int Seed = 5;
+
+namespace {
+
+std::unique_ptr<IRMutator> createInjectorMutator() {
+  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()));
+
+  return llvm::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
+}
+
+std::unique_ptr<IRMutator> createDeleterMutator() {
+  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<InstDeleterIRStrategy>());
+
+  return llvm::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
+}
+
+std::unique_ptr<Module> parseAssembly(
+    const char *Assembly, LLVMContext &Context) {
+
+  SMDiagnostic Error;
+  std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
+
+  std::string ErrMsg;
+  raw_string_ostream OS(ErrMsg);
+  Error.print("", OS);
+
+  assert(M && !verifyModule(*M, &errs()));
+  return M;
+}
+
+TEST(InjectorIRStrategyTest, EmptyModule) {
+  // Test that we can inject into empty module
+
+  LLVMContext Ctx;
+  auto M = llvm::make_unique<Module>("M", Ctx);
+  ASSERT_TRUE(M && !verifyModule(*M, &errs()));
+
+  auto Mutator = createInjectorMutator();
+  ASSERT_TRUE(Mutator);
+
+  Mutator->mutateModule(*M, Seed, 1, 1);
+  EXPECT_TRUE(!verifyModule(*M, &errs()));
+}
+
+TEST(InstDeleterIRStrategyTest, EmptyFunction) {
+  // Test that we don't crash even if we can't remove from one of the functions.
+
+  LLVMContext Ctx;
+  StringRef Source = ""
+      "define <8 x i32> @func1() {\n"
+        "ret <8 x i32> undef\n"
+      "}\n"
+      "\n"
+      "define i32 @func2() {\n"
+        "%A9 = alloca i32\n"
+        "%L6 = load i32, i32* %A9\n"
+        "ret i32 %L6\n"
+      "}\n";
+
+  auto Mutator = createDeleterMutator();
+  ASSERT_TRUE(Mutator);
+
+  // We need to choose 'func1' in order for the crash to appear.
+  // Loop 10 times and assume we are lucky.
+  for (int i = 0; i < 10; ++i) {
+    auto M = parseAssembly(Source.data(), Ctx);
+    ASSERT_TRUE(M && !verifyModule(*M, &errs()));
+
+    Mutator->mutateModule(*M, Seed, Source.size(), Source.size() + 100);
+    EXPECT_TRUE(!verifyModule(*M, &errs()));
+  }
+}
+
+}