1//===-- IRMutator.h - Mutation engine for fuzzing IR ------------*- C++ -*-===//
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// Provides the IRMutator class, which drives mutations on IR based on a
10// configurable set of strategies. Some common strategies are also included
11// here.
12//
13// Fuzzer-friendly (de)serialization functions are also provided, as these
14// are usually needed when mutating IR.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_FUZZMUTATE_IRMUTATOR_H
19#define LLVM_FUZZMUTATE_IRMUTATOR_H
20
21#include "llvm/FuzzMutate/OpDescriptor.h"
22#include "llvm/Support/ErrorHandling.h"
23#include <optional>
24
25namespace llvm {
26class BasicBlock;
27class Function;
28class Instruction;
29class Module;
30
31struct RandomIRBuilder;
32
33/// Base class for describing how to mutate a module. mutation functions for
34/// each IR unit forward to the contained unit.
35class IRMutationStrategy {
36public:
37 virtual ~IRMutationStrategy() = default;
38
39 /// Provide a weight to bias towards choosing this strategy for a mutation.
40 ///
41 /// The value of the weight is arbitrary, but a good default is "the number of
42 /// distinct ways in which this strategy can mutate a unit". This can also be
43 /// used to prefer strategies that shrink the overall size of the result when
44 /// we start getting close to \c MaxSize.
45 virtual uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
46 uint64_t CurrentWeight) = 0;
47
48 /// @{
49 /// Mutators for each IR unit. By default these forward to a contained
50 /// instance of the next smaller unit.
51 virtual void mutate(Module &M, RandomIRBuilder &IB);
52 virtual void mutate(Function &F, RandomIRBuilder &IB);
53 virtual void mutate(BasicBlock &BB, RandomIRBuilder &IB);
54 virtual void mutate(Instruction &I, RandomIRBuilder &IB) {
55 llvm_unreachable("Strategy does not implement any mutators");
56 }
57 /// @}
58};
59
60using TypeGetter = std::function<Type *(LLVMContext &)>;
61
62/// Entry point for configuring and running IR mutations.
63class IRMutator {
64 std::vector<TypeGetter> AllowedTypes;
65 std::vector<std::unique_ptr<IRMutationStrategy>> Strategies;
66
67public:
68 IRMutator(std::vector<TypeGetter> &&AllowedTypes,
69 std::vector<std::unique_ptr<IRMutationStrategy>> &&Strategies)
70 : AllowedTypes(std::move(AllowedTypes)),
71 Strategies(std::move(Strategies)) {}
72
73 /// Calculate the size of module as the number of objects in it, i.e.
74 /// instructions, basic blocks, functions, and aliases.
75 ///
76 /// \param M module
77 /// \return number of objects in module
78 static size_t getModuleSize(const Module &M);
79
80 /// Mutate given module. No change will be made if no strategy is selected.
81 ///
82 /// \param M module to mutate
83 /// \param Seed seed for random mutation
84 /// \param MaxSize max module size (see getModuleSize)
85 void mutateModule(Module &M, int Seed, size_t MaxSize);
86};
87
88/// Strategy that injects operations into the function.
89class InjectorIRStrategy : public IRMutationStrategy {
90 std::vector<fuzzerop::OpDescriptor> Operations;
91
92 std::optional<fuzzerop::OpDescriptor> chooseOperation(Value *Src,
93 RandomIRBuilder &IB);
94
95public:
96 InjectorIRStrategy() : Operations(getDefaultOps()) {}
97 InjectorIRStrategy(std::vector<fuzzerop::OpDescriptor> &&Operations)
98 : Operations(std::move(Operations)) {}
99 static std::vector<fuzzerop::OpDescriptor> getDefaultOps();
100
101 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
102 uint64_t CurrentWeight) override {
103 return Operations.size();
104 }
105
106 using IRMutationStrategy::mutate;
107 void mutate(Function &F, RandomIRBuilder &IB) override;
108 void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
109};
110
111/// Strategy that deletes instructions when the Module is too large.
112class InstDeleterIRStrategy : public IRMutationStrategy {
113public:
114 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
115 uint64_t CurrentWeight) override;
116
117 using IRMutationStrategy::mutate;
118 void mutate(Function &F, RandomIRBuilder &IB) override;
119 void mutate(Instruction &Inst, RandomIRBuilder &IB) override;
120};
121
122/// Strategy that modifies instruction attributes and operands.
123class InstModificationIRStrategy : public IRMutationStrategy {
124public:
125 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
126 uint64_t CurrentWeight) override {
127 return 4;
128 }
129
130 using IRMutationStrategy::mutate;
131 void mutate(Instruction &Inst, RandomIRBuilder &IB) override;
132};
133
134/// Strategy that generates new function calls and inserts function signatures
135/// to the modules. If any signatures are present in the module it will be
136/// called.
137class InsertFunctionStrategy : public IRMutationStrategy {
138public:
139 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
140 uint64_t CurrentWeight) override {
141 return 10;
142 }
143
144 using IRMutationStrategy::mutate;
145 void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
146};
147
148/// Strategy to split a random block and insert a random CFG in between.
149class InsertCFGStrategy : public IRMutationStrategy {
150private:
151 uint64_t MaxNumCases;
152 enum CFGToSink { Return, DirectSink, SinkOrSelfLoop, EndOfCFGToLink };
153
154public:
155 InsertCFGStrategy(uint64_t MNC = 8) : MaxNumCases(MNC){};
156 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
157 uint64_t CurrentWeight) override {
158 return 5;
159 }
160
161 void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
162
163private:
164 void connectBlocksToSink(ArrayRef<BasicBlock *> Blocks, BasicBlock *Sink,
165 RandomIRBuilder &IB);
166};
167
168/// Strategy to insert PHI Nodes at the head of each basic block.
169class InsertPHIStrategy : public IRMutationStrategy {
170public:
171 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
172 uint64_t CurrentWeight) override {
173 return 2;
174 }
175
176 void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
177};
178
179/// Strategy to select a random instruction and add a new sink (user) to it to
180/// increate data dependency.
181class SinkInstructionStrategy : public IRMutationStrategy {
182public:
183 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
184 uint64_t CurrentWeight) override {
185 return 2;
186 }
187
188 void mutate(Function &F, RandomIRBuilder &IB) override;
189 void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
190};
191
192/// Strategy to randomly select a block and shuffle the operations without
193/// affecting data dependency.
194class ShuffleBlockStrategy : public IRMutationStrategy {
195public:
196 uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
197 uint64_t CurrentWeight) override {
198 return 2;
199 }
200
201 void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
202};
203
204/// Fuzzer friendly interface for the llvm bitcode parser.
205///
206/// \param Data Bitcode we are going to parse
207/// \param Size Size of the 'Data' in bytes
208/// \return New module or nullptr in case of error
209std::unique_ptr<Module> parseModule(const uint8_t *Data, size_t Size,
210 LLVMContext &Context);
211
212/// Fuzzer friendly interface for the llvm bitcode printer.
213///
214/// \param M Module to print
215/// \param Dest Location to store serialized module
216/// \param MaxSize Size of the destination buffer
217/// \return Number of bytes that were written. When module size exceeds MaxSize
218/// returns 0 and leaves Dest unchanged.
219size_t writeModule(const Module &M, uint8_t *Dest, size_t MaxSize);
220
221/// Try to parse module and verify it. May output verification errors to the
222/// errs().
223/// \return New module or nullptr in case of error.
224std::unique_ptr<Module> parseAndVerify(const uint8_t *Data, size_t Size,
225 LLVMContext &Context);
226
227} // namespace llvm
228
229#endif // LLVM_FUZZMUTATE_IRMUTATOR_H
230

source code of llvm/include/llvm/FuzzMutate/IRMutator.h