llvm/FuzzMutate/IRMutator.h

0001 //===-- IRMutator.h - Mutation engine for fuzzing IR ------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Provides the IRMutator class, which drives mutations on IR based on a
0010 // configurable set of strategies. Some common strategies are also included
0011 // here.
0012 //
0013 // Fuzzer-friendly (de)serialization functions are also provided, as these
0014 // are usually needed when mutating IR.
0015 //
0016 //===----------------------------------------------------------------------===//
0017
0018 #ifndef LLVM_FUZZMUTATE_IRMUTATOR_H
0019 #define LLVM_FUZZMUTATE_IRMUTATOR_H
0020
0021 #include "llvm/FuzzMutate/OpDescriptor.h"
0022 #include "llvm/Support/ErrorHandling.h"
0023 #include <optional>
0024
0025 namespace llvm {
0026 class BasicBlock;
0027 class Function;
0028 class Instruction;
0029 class Module;
0030
0031 struct RandomIRBuilder;
0032
0033 /// Base class for describing how to mutate a module. mutation functions for
0034 /// each IR unit forward to the contained unit.
0035 class IRMutationStrategy {
0036 public:
0037   virtual ~IRMutationStrategy() = default;
0038
0039   /// Provide a weight to bias towards choosing this strategy for a mutation.
0040   ///
0041   /// The value of the weight is arbitrary, but a good default is "the number of
0042   /// distinct ways in which this strategy can mutate a unit". This can also be
0043   /// used to prefer strategies that shrink the overall size of the result when
0044   /// we start getting close to \c MaxSize.
0045   virtual uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0046                              uint64_t CurrentWeight) = 0;
0047
0048   /// @{
0049   /// Mutators for each IR unit. By default these forward to a contained
0050   /// instance of the next smaller unit.
0051   virtual void mutate(Module &M, RandomIRBuilder &IB);
0052   virtual void mutate(Function &F, RandomIRBuilder &IB);
0053   virtual void mutate(BasicBlock &BB, RandomIRBuilder &IB);
0054   virtual void mutate(Instruction &I, RandomIRBuilder &IB) {
0055     llvm_unreachable("Strategy does not implement any mutators");
0056   }
0057   /// @}
0058 };
0059
0060 using TypeGetter = std::function<Type *(LLVMContext &)>;
0061
0062 /// Entry point for configuring and running IR mutations.
0063 class IRMutator {
0064   std::vector<TypeGetter> AllowedTypes;
0065   std::vector<std::unique_ptr<IRMutationStrategy>> Strategies;
0066
0067 public:
0068   IRMutator(std::vector<TypeGetter> &&AllowedTypes,
0069             std::vector<std::unique_ptr<IRMutationStrategy>> &&Strategies)
0070       : AllowedTypes(std::move(AllowedTypes)),
0071         Strategies(std::move(Strategies)) {}
0072
0073   /// Calculate the size of module as the number of objects in it, i.e.
0074   /// instructions, basic blocks, functions, and aliases.
0075   ///
0076   /// \param M module
0077   /// \return number of objects in module
0078   static size_t getModuleSize(const Module &M);
0079
0080   /// Mutate given module. No change will be made if no strategy is selected.
0081   ///
0082   /// \param M  module to mutate
0083   /// \param Seed seed for random mutation
0084   /// \param MaxSize max module size (see getModuleSize)
0085   void mutateModule(Module &M, int Seed, size_t MaxSize);
0086 };
0087
0088 /// Strategy that injects operations into the function.
0089 class InjectorIRStrategy : public IRMutationStrategy {
0090   std::vector<fuzzerop::OpDescriptor> Operations;
0091
0092   std::optional<fuzzerop::OpDescriptor> chooseOperation(Value *Src,
0093                                                         RandomIRBuilder &IB);
0094
0095 public:
0096   InjectorIRStrategy() : Operations(getDefaultOps()) {}
0097   InjectorIRStrategy(std::vector<fuzzerop::OpDescriptor> &&Operations)
0098       : Operations(std::move(Operations)) {}
0099   static std::vector<fuzzerop::OpDescriptor> getDefaultOps();
0100
0101   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0102                      uint64_t CurrentWeight) override {
0103     return Operations.size();
0104   }
0105
0106   using IRMutationStrategy::mutate;
0107   void mutate(Function &F, RandomIRBuilder &IB) override;
0108   void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
0109 };
0110
0111 /// Strategy that deletes instructions when the Module is too large.
0112 class InstDeleterIRStrategy : public IRMutationStrategy {
0113 public:
0114   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0115                      uint64_t CurrentWeight) override;
0116
0117   using IRMutationStrategy::mutate;
0118   void mutate(Function &F, RandomIRBuilder &IB) override;
0119   void mutate(Instruction &Inst, RandomIRBuilder &IB) override;
0120 };
0121
0122 /// Strategy that modifies instruction attributes and operands.
0123 class InstModificationIRStrategy : public IRMutationStrategy {
0124 public:
0125   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0126                      uint64_t CurrentWeight) override {
0127     return 4;
0128   }
0129
0130   using IRMutationStrategy::mutate;
0131   void mutate(Instruction &Inst, RandomIRBuilder &IB) override;
0132 };
0133
0134 /// Strategy that generates new function calls and inserts function signatures
0135 /// to the modules. If any signatures are present in the module it will be
0136 /// called.
0137 class InsertFunctionStrategy : public IRMutationStrategy {
0138 public:
0139   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0140                      uint64_t CurrentWeight) override {
0141     return 10;
0142   }
0143
0144   using IRMutationStrategy::mutate;
0145   void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
0146 };
0147
0148 /// Strategy to split a random block and insert a random CFG in between.
0149 class InsertCFGStrategy : public IRMutationStrategy {
0150 private:
0151   uint64_t MaxNumCases;
0152   enum CFGToSink { Return, DirectSink, SinkOrSelfLoop, EndOfCFGToLink };
0153
0154 public:
0155   InsertCFGStrategy(uint64_t MNC = 8) : MaxNumCases(MNC){};
0156   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0157                      uint64_t CurrentWeight) override {
0158     return 5;
0159   }
0160
0161   void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
0162
0163 private:
0164   void connectBlocksToSink(ArrayRef<BasicBlock *> Blocks, BasicBlock *Sink,
0165                            RandomIRBuilder &IB);
0166 };
0167
0168 /// Strategy to insert PHI Nodes at the head of each basic block.
0169 class InsertPHIStrategy : public IRMutationStrategy {
0170 public:
0171   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0172                      uint64_t CurrentWeight) override {
0173     return 2;
0174   }
0175
0176   void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
0177 };
0178
0179 /// Strategy to select a random instruction and add a new sink (user) to it to
0180 /// increate data dependency.
0181 class SinkInstructionStrategy : public IRMutationStrategy {
0182 public:
0183   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0184                      uint64_t CurrentWeight) override {
0185     return 2;
0186   }
0187
0188   void mutate(Function &F, RandomIRBuilder &IB) override;
0189   void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
0190 };
0191
0192 /// Strategy to randomly select a block and shuffle the operations without
0193 /// affecting data dependency.
0194 class ShuffleBlockStrategy : public IRMutationStrategy {
0195 public:
0196   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
0197                      uint64_t CurrentWeight) override {
0198     return 2;
0199   }
0200
0201   void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
0202 };
0203
0204 /// Fuzzer friendly interface for the llvm bitcode parser.
0205 ///
0206 /// \param Data Bitcode we are going to parse
0207 /// \param Size Size of the 'Data' in bytes
0208 /// \return New module or nullptr in case of error
0209 std::unique_ptr<Module> parseModule(const uint8_t *Data, size_t Size,
0210                                     LLVMContext &Context);
0211
0212 /// Fuzzer friendly interface for the llvm bitcode printer.
0213 ///
0214 /// \param M Module to print
0215 /// \param Dest Location to store serialized module
0216 /// \param MaxSize Size of the destination buffer
0217 /// \return Number of bytes that were written. When module size exceeds MaxSize
0218 ///         returns 0 and leaves Dest unchanged.
0219 size_t writeModule(const Module &M, uint8_t *Dest, size_t MaxSize);
0220
0221 /// Try to parse module and verify it. May output verification errors to the
0222 /// errs().
0223 /// \return New module or nullptr in case of error.
0224 std::unique_ptr<Module> parseAndVerify(const uint8_t *Data, size_t Size,
0225                                        LLVMContext &Context);
0226
0227 } // namespace llvm
0228
0229 #endif // LLVM_FUZZMUTATE_IRMUTATOR_H