1 //===-- IRMutator.cpp -----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/FuzzMutate/IRMutator.h"
10 #include "llvm/ADT/Optional.h"
11 #include "llvm/Analysis/TargetLibraryInfo.h"
12 #include "llvm/Bitcode/BitcodeReader.h"
13 #include "llvm/Bitcode/BitcodeWriter.h"
14 #include "llvm/FuzzMutate/Operations.h"
15 #include "llvm/FuzzMutate/Random.h"
16 #include "llvm/FuzzMutate/RandomIRBuilder.h"
17 #include "llvm/IR/BasicBlock.h"
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/InstIterator.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/IR/Verifier.h"
23 #include "llvm/Support/MemoryBuffer.h"
24 #include "llvm/Support/SourceMgr.h"
25 #include "llvm/Transforms/Scalar/DCE.h"
26 
27 using namespace llvm;
28 
createEmptyFunction(Module & M)29 static void createEmptyFunction(Module &M) {
30   // TODO: Some arguments and a return value would probably be more interesting.
31   LLVMContext &Context = M.getContext();
32   Function *F = Function::Create(FunctionType::get(Type::getVoidTy(Context), {},
33                                                    /*isVarArg=*/false),
34                                  GlobalValue::ExternalLinkage, "f", &M);
35   BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
36   ReturnInst::Create(Context, BB);
37 }
38 
mutate(Module & M,RandomIRBuilder & IB)39 void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
40   auto RS = makeSampler<Function *>(IB.Rand);
41   for (Function &F : M)
42     if (!F.isDeclaration())
43       RS.sample(&F, /*Weight=*/1);
44 
45   if (RS.isEmpty())
46     createEmptyFunction(M);
47   else
48     mutate(*RS.getSelection(), IB);
49 }
50 
mutate(Function & F,RandomIRBuilder & IB)51 void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
52   mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
53 }
54 
mutate(BasicBlock & BB,RandomIRBuilder & IB)55 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
56   mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
57 }
58 
mutateModule(Module & M,int Seed,size_t CurSize,size_t MaxSize)59 void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize,
60                              size_t MaxSize) {
61   std::vector<Type *> Types;
62   for (const auto &Getter : AllowedTypes)
63     Types.push_back(Getter(M.getContext()));
64   RandomIRBuilder IB(Seed, Types);
65 
66   auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
67   for (const auto &Strategy : Strategies)
68     RS.sample(Strategy.get(),
69               Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
70   auto Strategy = RS.getSelection();
71 
72   Strategy->mutate(M, IB);
73 }
74 
eliminateDeadCode(Function & F)75 static void eliminateDeadCode(Function &F) {
76   FunctionPassManager FPM;
77   FPM.addPass(DCEPass());
78   FunctionAnalysisManager FAM;
79   FAM.registerPass([&] { return TargetLibraryAnalysis(); });
80   FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
81   FPM.run(F, FAM);
82 }
83 
mutate(Function & F,RandomIRBuilder & IB)84 void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
85   IRMutationStrategy::mutate(F, IB);
86   eliminateDeadCode(F);
87 }
88 
getDefaultOps()89 std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
90   std::vector<fuzzerop::OpDescriptor> Ops;
91   describeFuzzerIntOps(Ops);
92   describeFuzzerFloatOps(Ops);
93   describeFuzzerControlFlowOps(Ops);
94   describeFuzzerPointerOps(Ops);
95   describeFuzzerAggregateOps(Ops);
96   describeFuzzerVectorOps(Ops);
97   return Ops;
98 }
99 
100 Optional<fuzzerop::OpDescriptor>
chooseOperation(Value * Src,RandomIRBuilder & IB)101 InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) {
102   auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) {
103     return Op.SourcePreds[0].matches({}, Src);
104   };
105   auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred));
106   if (RS.isEmpty())
107     return None;
108   return *RS;
109 }
110 
mutate(BasicBlock & BB,RandomIRBuilder & IB)111 void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
112   SmallVector<Instruction *, 32> Insts;
113   for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
114     Insts.push_back(&*I);
115   if (Insts.size() < 1)
116     return;
117 
118   // Choose an insertion point for our new instruction.
119   size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1);
120 
121   auto InstsBefore = makeArrayRef(Insts).slice(0, IP);
122   auto InstsAfter = makeArrayRef(Insts).slice(IP);
123 
124   // Choose a source, which will be used to constrain the operation selection.
125   SmallVector<Value *, 2> Srcs;
126   Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore));
127 
128   // Choose an operation that's constrained to be valid for the type of the
129   // source, collect any other sources it needs, and then build it.
130   auto OpDesc = chooseOperation(Srcs[0], IB);
131   // Bail if no operation was found
132   if (!OpDesc)
133     return;
134 
135   for (const auto &Pred : makeArrayRef(OpDesc->SourcePreds).slice(1))
136     Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
137 
138   if (Value *Op = OpDesc->BuilderFunc(Srcs, Insts[IP])) {
139     // Find a sink and wire up the results of the operation.
140     IB.connectToSink(BB, InstsAfter, Op);
141   }
142 }
143 
getWeight(size_t CurrentSize,size_t MaxSize,uint64_t CurrentWeight)144 uint64_t InstDeleterIRStrategy::getWeight(size_t CurrentSize, size_t MaxSize,
145                                           uint64_t CurrentWeight) {
146   // If we have less than 200 bytes, panic and try to always delete.
147   if (CurrentSize > MaxSize - 200)
148     return CurrentWeight ? CurrentWeight * 100 : 1;
149   // Draw a line starting from when we only have 1k left and increasing linearly
150   // to double the current weight.
151   int64_t Line = (-2 * static_cast<int64_t>(CurrentWeight)) *
152                  (static_cast<int64_t>(MaxSize) -
153                   static_cast<int64_t>(CurrentSize) - 1000) /
154                  1000;
155   // Clamp negative weights to zero.
156   if (Line < 0)
157     return 0;
158   return Line;
159 }
160 
mutate(Function & F,RandomIRBuilder & IB)161 void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
162   auto RS = makeSampler<Instruction *>(IB.Rand);
163   for (Instruction &Inst : instructions(F)) {
164     // TODO: We can't handle these instructions.
165     if (Inst.isTerminator() || Inst.isEHPad() ||
166         Inst.isSwiftError() || isa<PHINode>(Inst))
167       continue;
168 
169     RS.sample(&Inst, /*Weight=*/1);
170   }
171   if (RS.isEmpty())
172     return;
173 
174   // Delete the instruction.
175   mutate(*RS.getSelection(), IB);
176   // Clean up any dead code that's left over after removing the instruction.
177   eliminateDeadCode(F);
178 }
179 
mutate(Instruction & Inst,RandomIRBuilder & IB)180 void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
181   assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
182 
183   if (Inst.getType()->isVoidTy()) {
184     // Instructions with void type (ie, store) have no uses to worry about. Just
185     // erase it and move on.
186     Inst.eraseFromParent();
187     return;
188   }
189 
190   // Otherwise we need to find some other value with the right type to keep the
191   // users happy.
192   auto Pred = fuzzerop::onlyType(Inst.getType());
193   auto RS = makeSampler<Value *>(IB.Rand);
194   SmallVector<Instruction *, 32> InstsBefore;
195   BasicBlock *BB = Inst.getParent();
196   for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
197        ++I) {
198     if (Pred.matches({}, &*I))
199       RS.sample(&*I, /*Weight=*/1);
200     InstsBefore.push_back(&*I);
201   }
202   if (!RS)
203     RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
204 
205   Inst.replaceAllUsesWith(RS.getSelection());
206   Inst.eraseFromParent();
207 }
208 
mutate(Instruction & Inst,RandomIRBuilder & IB)209 void InstModificationIRStrategy::mutate(Instruction &Inst,
210                                         RandomIRBuilder &IB) {
211   SmallVector<std::function<void()>, 8> Modifications;
212   CmpInst *CI = nullptr;
213   GetElementPtrInst *GEP = nullptr;
214   switch (Inst.getOpcode()) {
215   default:
216     break;
217   case Instruction::Add:
218   case Instruction::Mul:
219   case Instruction::Sub:
220   case Instruction::Shl:
221     Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(true); }),
222         Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(false); });
223     Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(true); });
224     Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(false); });
225 
226     break;
227   case Instruction::ICmp:
228     CI = cast<ICmpInst>(&Inst);
229     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_EQ); });
230     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_NE); });
231     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGT); });
232     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGE); });
233     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULT); });
234     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULE); });
235     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGT); });
236     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGE); });
237     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLT); });
238     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLE); });
239     break;
240   case Instruction::GetElementPtr:
241     GEP = cast<GetElementPtrInst>(&Inst);
242     Modifications.push_back([GEP]() { GEP->setIsInBounds(true); });
243     Modifications.push_back([GEP]() { GEP->setIsInBounds(false); });
244     break;
245   }
246 
247   auto RS = makeSampler(IB.Rand, Modifications);
248   if (RS)
249     RS.getSelection()();
250 }
251 
parseModule(const uint8_t * Data,size_t Size,LLVMContext & Context)252 std::unique_ptr<Module> llvm::parseModule(const uint8_t *Data, size_t Size,
253                                           LLVMContext &Context) {
254 
255   if (Size <= 1)
256     // We get bogus data given an empty corpus - just create a new module.
257     return std::make_unique<Module>("M", Context);
258 
259   auto Buffer = MemoryBuffer::getMemBuffer(
260       StringRef(reinterpret_cast<const char *>(Data), Size), "Fuzzer input",
261       /*RequiresNullTerminator=*/false);
262 
263   SMDiagnostic Err;
264   auto M = parseBitcodeFile(Buffer->getMemBufferRef(), Context);
265   if (Error E = M.takeError()) {
266     errs() << toString(std::move(E)) << "\n";
267     return nullptr;
268   }
269   return std::move(M.get());
270 }
271 
writeModule(const Module & M,uint8_t * Dest,size_t MaxSize)272 size_t llvm::writeModule(const Module &M, uint8_t *Dest, size_t MaxSize) {
273   std::string Buf;
274   {
275     raw_string_ostream OS(Buf);
276     WriteBitcodeToFile(M, OS);
277   }
278   if (Buf.size() > MaxSize)
279     return 0;
280   memcpy(Dest, Buf.data(), Buf.size());
281   return Buf.size();
282 }
283 
parseAndVerify(const uint8_t * Data,size_t Size,LLVMContext & Context)284 std::unique_ptr<Module> llvm::parseAndVerify(const uint8_t *Data, size_t Size,
285                                              LLVMContext &Context) {
286   auto M = parseModule(Data, Size, Context);
287   if (!M || verifyModule(*M, &errs()))
288     return nullptr;
289 
290   return M;
291 }
292