source/fuzz/shrinker.h

   1 // Copyright (c) 2019 Google LLC
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #ifndef SOURCE_FUZZ_SHRINKER_H_
  16 #define SOURCE_FUZZ_SHRINKER_H_
  17
  18 #include <memory>
  19 #include <vector>
  20
  21 #include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
  22 #include "spirv-tools/libspirv.hpp"
  23
  24 namespace spvtools {
  25 namespace fuzz {
  26
  27 // Shrinks a sequence of transformations that lead to an interesting SPIR-V
  28 // binary to yield a smaller sequence of transformations that still produce an
  29 // interesting binary.
  30 class Shrinker {
  31  public:
  32   // Possible statuses that can result from running the shrinker.
  33   enum class ShrinkerResultStatus {
  34     kComplete,
  35     kFailedToCreateSpirvToolsInterface,
  36     kInitialBinaryInvalid,
  37     kInitialBinaryNotInteresting,
  38     kReplayFailed,
  39     kStepLimitReached,
  40     kAddedFunctionReductionFailed,
  41   };
  42
  43   struct ShrinkerResult {
  44     ShrinkerResultStatus status;
  45     std::vector<uint32_t> transformed_binary;
  46     protobufs::TransformationSequence applied_transformations;
  47   };
  48
  49   // The type for a function that will take a binary, |binary|, and return true
  50   // if and only if the binary is deemed interesting. (The function also takes
  51   // an integer argument, |counter|, that will be incremented each time the
  52   // function is called; this is for debugging purposes).
  53   //
  54   // The notion of "interesting" depends on what properties of the binary or
  55   // tools that process the binary we are trying to maintain during shrinking.
  56   using InterestingnessFunction = std::function<bool(
  57       const std::vector<uint32_t>& binary, uint32_t counter)>;
  58
  59   Shrinker(spv_target_env target_env, MessageConsumer consumer,
  60            const std::vector<uint32_t>& binary_in,
  61            const protobufs::FactSequence& initial_facts,
  62            const protobufs::TransformationSequence& transformation_sequence_in,
  63            const InterestingnessFunction& interestingness_function,
  64            uint32_t step_limit, bool validate_during_replay,
  65            spv_validator_options validator_options);
  66
  67   // Disables copy/move constructor/assignment operations.
  68   Shrinker(const Shrinker&) = delete;
  69   Shrinker(Shrinker&&) = delete;
  70   Shrinker& operator=(const Shrinker&) = delete;
  71   Shrinker& operator=(Shrinker&&) = delete;
  72
  73   ~Shrinker();
  74
  75   // Requires that when |transformation_sequence_in_| is applied to |binary_in_|
  76   // with initial facts |initial_facts_|, the resulting binary is interesting
  77   // according to |interestingness_function_|.
  78   //
  79   // If shrinking succeeded -- possibly terminating early due to reaching the
  80   // shrinker's step limit -- an associated result status is returned together
  81   // with a subsequence of |transformation_sequence_in_| that, when applied
  82   // to |binary_in_| with initial facts |initial_facts_|, produces a binary
  83   // that is also interesting according to |interestingness_function_|; this
  84   // binary is also returned.
  85   //
  86   // If shrinking failed for some reason, an appropriate result status is
  87   // returned together with an empty binary and empty transformation sequence.
  88   ShrinkerResult Run();
  89
  90  private:
  91   // Returns the id bound for the given SPIR-V binary, which is assumed to be
  92   // valid.
  93   uint32_t GetIdBound(const std::vector<uint32_t>& binary) const;
  94
  95   // Target environment.
  96   const spv_target_env target_env_;
  97
  98   // Message consumer that will be invoked once for each message communicated
  99   // from the library.
 100   MessageConsumer consumer_;
 101
 102   // The binary to which transformations are to be applied.
 103   const std::vector<uint32_t>& binary_in_;
 104
 105   // Initial facts known to hold in advance of applying any transformations.
 106   const protobufs::FactSequence& initial_facts_;
 107
 108   // The series of transformations to be shrunk.
 109   const protobufs::TransformationSequence& transformation_sequence_in_;
 110
 111   // Function that decides whether a given module is interesting.
 112   const InterestingnessFunction& interestingness_function_;
 113
 114   // Step limit to decide when to terminate shrinking early.
 115   const uint32_t step_limit_;
 116
 117   // Determines whether to check for validity during the replaying of
 118   // transformations.
 119   const bool validate_during_replay_;
 120
 121   // Options to control validation.
 122   spv_validator_options validator_options_;
 123 };
 124
 125 }  // namespace fuzz
 126 }  // namespace spvtools
 127
 128 #endif  // SOURCE_FUZZ_SHRINKER_H_