source/fuzz/shrinker.cpp

// Copyright (c) 2019 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "source/fuzz/shrinker.h"

#include <sstream>

#include "source/fuzz/added_function_reducer.h"
#include "source/fuzz/pseudo_random_generator.h"
#include "source/fuzz/replayer.h"
#include "source/opt/build_module.h"
#include "source/opt/ir_context.h"
#include "source/spirv_fuzzer_options.h"
#include "source/util/make_unique.h"

namespace spvtools {
namespace fuzz {

namespace {

// A helper to get the size of a protobuf transformation sequence in a less
// verbose manner.
uint32_t NumRemainingTransformations(
    const protobufs::TransformationSequence& transformation_sequence) {
  return static_cast<uint32_t>(transformation_sequence.transformation_size());
}

// A helper to return a transformation sequence identical to |transformations|,
// except that a chunk of size |chunk_size| starting from |chunk_index| x
// |chunk_size| is removed (or as many transformations as available if the whole
// chunk is not).
protobufs::TransformationSequence RemoveChunk(
    const protobufs::TransformationSequence& transformations,
    uint32_t chunk_index, uint32_t chunk_size) {
  uint32_t lower = chunk_index * chunk_size;
  uint32_t upper = std::min((chunk_index + 1) * chunk_size,
                            NumRemainingTransformations(transformations));
  assert(lower < upper);
  assert(upper <= NumRemainingTransformations(transformations));
  protobufs::TransformationSequence result;
  for (uint32_t j = 0; j < NumRemainingTransformations(transformations); j++) {
    if (j >= lower && j < upper) {
      continue;
    }
    protobufs::Transformation transformation =
        transformations.transformation()[j];
    *result.mutable_transformation()->Add() = transformation;
  }
  return result;
}

}  // namespace

Shrinker::Shrinker(
    spv_target_env target_env, MessageConsumer consumer,
    const std::vector<uint32_t>& binary_in,
    const protobufs::FactSequence& initial_facts,
    const protobufs::TransformationSequence& transformation_sequence_in,
    const InterestingnessFunction& interestingness_function,
    uint32_t step_limit, bool validate_during_replay,
    spv_validator_options validator_options)
    : target_env_(target_env),
      consumer_(std::move(consumer)),
      binary_in_(binary_in),
      initial_facts_(initial_facts),
      transformation_sequence_in_(transformation_sequence_in),
      interestingness_function_(interestingness_function),
      step_limit_(step_limit),
      validate_during_replay_(validate_during_replay),
      validator_options_(validator_options) {}

Shrinker::~Shrinker() = default;

Shrinker::ShrinkerResult Shrinker::Run() {
  // Check compatibility between the library version being linked with and the
  // header files being used.
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  SpirvTools tools(target_env_);
  if (!tools.IsValid()) {
    consumer_(SPV_MSG_ERROR, nullptr, {},
              "Failed to create SPIRV-Tools interface; stopping.");
    return {Shrinker::ShrinkerResultStatus::kFailedToCreateSpirvToolsInterface,
            std::vector<uint32_t>(), protobufs::TransformationSequence()};
  }

  // Initial binary should be valid.
  if (!tools.Validate(&binary_in_[0], binary_in_.size(), validator_options_)) {
    consumer_(SPV_MSG_INFO, nullptr, {},
              "Initial binary is invalid; stopping.");
    return {Shrinker::ShrinkerResultStatus::kInitialBinaryInvalid,
            std::vector<uint32_t>(), protobufs::TransformationSequence()};
  }

  // Run a replay of the initial transformation sequence to check that it
  // succeeds.
  auto initial_replay_result =
      Replayer(target_env_, consumer_, binary_in_, initial_facts_,
               transformation_sequence_in_,
               static_cast<uint32_t>(
                   transformation_sequence_in_.transformation_size()),
               validate_during_replay_, validator_options_)
          .Run();
  if (initial_replay_result.status !=
      Replayer::ReplayerResultStatus::kComplete) {
    return {ShrinkerResultStatus::kReplayFailed, std::vector<uint32_t>(),
            protobufs::TransformationSequence()};
  }
  // Get the binary that results from running these transformations, and the
  // subsequence of the initial transformations that actually apply (in
  // principle this could be a strict subsequence).
  std::vector<uint32_t> current_best_binary;
  initial_replay_result.transformed_module->module()->ToBinary(
      &current_best_binary, false);
  protobufs::TransformationSequence current_best_transformations =
      std::move(initial_replay_result.applied_transformations);

  // Check that the binary produced by applying the initial transformations is
  // indeed interesting.
  if (!interestingness_function_(current_best_binary, 0)) {
    consumer_(SPV_MSG_INFO, nullptr, {},
              "Initial binary is not interesting; stopping.");
    return {ShrinkerResultStatus::kInitialBinaryNotInteresting,
            std::vector<uint32_t>(), protobufs::TransformationSequence()};
  }

  uint32_t attempt = 0;  // Keeps track of the number of shrink attempts that
                         // have been tried, whether successful or not.

  uint32_t chunk_size =
      std::max(1u, NumRemainingTransformations(current_best_transformations) /
                       2);  // The number of contiguous transformations that the
                            // shrinker will try to remove in one go; starts
                            // high and decreases during the shrinking process.

  // Keep shrinking until we:
  // - reach the step limit,
  // - run out of transformations to remove, or
  // - cannot make the chunk size any smaller.
  while (attempt < step_limit_ &&
         !current_best_transformations.transformation().empty() &&
         chunk_size > 0) {
    bool progress_this_round =
        false;  // Used to decide whether to make the chunk size with which we
                // remove transformations smaller.  If we managed to remove at
                // least one chunk of transformations at a particular chunk
                // size, we set this flag so that we do not yet decrease the
                // chunk size.

    assert(chunk_size <=
               NumRemainingTransformations(current_best_transformations) &&
           "Chunk size should never exceed the number of transformations that "
           "remain.");

    // The number of chunks is the ceiling of (#remaining_transformations /
    // chunk_size).
    const uint32_t num_chunks =
        (NumRemainingTransformations(current_best_transformations) +
         chunk_size - 1) /
        chunk_size;
    assert(num_chunks >= 1 && "There should be at least one chunk.");
    assert(num_chunks * chunk_size >=
               NumRemainingTransformations(current_best_transformations) &&
           "All transformations should be in some chunk.");

    // We go through the transformations in reverse, in chunks of size
    // |chunk_size|, using |chunk_index| to track which chunk to try removing
    // next.  The loop exits early if we reach the shrinking step limit.
    for (int chunk_index = num_chunks - 1;
         attempt < step_limit_ && chunk_index >= 0; chunk_index--) {
      // Remove a chunk of transformations according to the current index and
      // chunk size.
      auto transformations_with_chunk_removed =
          RemoveChunk(current_best_transformations,
                      static_cast<uint32_t>(chunk_index), chunk_size);

      // Replay the smaller sequence of transformations to get a next binary and
      // transformation sequence. Note that the transformations arising from
      // replay might be even smaller than the transformations with the chunk
      // removed, because removing those transformations might make further
      // transformations inapplicable.
      auto replay_result =
          Replayer(
              target_env_, consumer_, binary_in_, initial_facts_,
              transformations_with_chunk_removed,
              static_cast<uint32_t>(
                  transformations_with_chunk_removed.transformation_size()),
              validate_during_replay_, validator_options_)
              .Run();
      if (replay_result.status != Replayer::ReplayerResultStatus::kComplete) {
        // Replay should not fail; if it does, we need to abort shrinking.
        return {ShrinkerResultStatus::kReplayFailed, std::vector<uint32_t>(),
                protobufs::TransformationSequence()};
      }

      assert(
          NumRemainingTransformations(replay_result.applied_transformations) >=
              chunk_index * chunk_size &&
          "Removing this chunk of transformations should not have an effect "
          "on earlier chunks.");

      std::vector<uint32_t> transformed_binary;
      replay_result.transformed_module->module()->ToBinary(&transformed_binary,
                                                           false);
      if (interestingness_function_(transformed_binary, attempt)) {
        // If the binary arising from the smaller transformation sequence is
        // interesting, this becomes our current best binary and transformation
        // sequence.
        current_best_binary = std::move(transformed_binary);
        current_best_transformations =
            std::move(replay_result.applied_transformations);
        progress_this_round = true;
      }
      // Either way, this was a shrink attempt, so increment our count of shrink
      // attempts.
      attempt++;
    }
    if (!progress_this_round) {
      // If we didn't manage to remove any chunks at this chunk size, try a
      // smaller chunk size.
      chunk_size /= 2;
    }
    // Decrease the chunk size until it becomes no larger than the number of
    // remaining transformations.
    while (chunk_size >
           NumRemainingTransformations(current_best_transformations)) {
      chunk_size /= 2;
    }
  }

  // We now use spirv-reduce to minimise the functions associated with any
  // AddFunction transformations that remain.
  //
  // Consider every remaining transformation.
  for (uint32_t transformation_index = 0;
       attempt < step_limit_ &&
       transformation_index <
           static_cast<uint32_t>(
               current_best_transformations.transformation_size());
       transformation_index++) {
    // Skip all transformations apart from TransformationAddFunction.
    if (!current_best_transformations.transformation(transformation_index)
             .has_add_function()) {
      continue;
    }
    // Invoke spirv-reduce on the function encoded in this AddFunction
    // transformation.  The details of this are rather involved, and so are
    // encapsulated in a separate class.
    auto added_function_reducer_result =
        AddedFunctionReducer(target_env_, consumer_, binary_in_, initial_facts_,
                             current_best_transformations, transformation_index,
                             interestingness_function_, validate_during_replay_,
                             validator_options_, step_limit_, attempt)
            .Run();
    // Reducing the added function should succeed.  If it doesn't, we report
    // a shrinking error.
    if (added_function_reducer_result.status !=
        AddedFunctionReducer::AddedFunctionReducerResultStatus::kComplete) {
      return {ShrinkerResultStatus::kAddedFunctionReductionFailed,
              std::vector<uint32_t>(), protobufs::TransformationSequence()};
    }
    assert(current_best_transformations.transformation_size() ==
               added_function_reducer_result.applied_transformations
                   .transformation_size() &&
           "The number of transformations should not have changed.");
    current_best_binary =
        std::move(added_function_reducer_result.transformed_binary);
    current_best_transformations =
        std::move(added_function_reducer_result.applied_transformations);
    // The added function reducer reports how many reduction attempts
    // spirv-reduce took when reducing the function.  We regard each of these
    // as a shrinker attempt.
    attempt += added_function_reducer_result.num_reduction_attempts;
  }

  // Indicate whether shrinking completed or was truncated due to reaching the
  // step limit.
  //
  // Either way, the output from the shrinker is the best binary we saw, and the
  // transformations that led to it.
  assert(attempt <= step_limit_);
  if (attempt == step_limit_) {
    std::stringstream strstream;
    strstream << "Shrinking did not complete; step limit " << step_limit_
              << " was reached.";
    consumer_(SPV_MSG_WARNING, nullptr, {}, strstream.str().c_str());
    return {Shrinker::ShrinkerResultStatus::kStepLimitReached,
            std::move(current_best_binary),
            std::move(current_best_transformations)};
  }
  return {Shrinker::ShrinkerResultStatus::kComplete,
          std::move(current_best_binary),
          std::move(current_best_transformations)};
}

uint32_t Shrinker::GetIdBound(const std::vector<uint32_t>& binary) const {
  // Build the module from the input binary.
  std::unique_ptr<opt::IRContext> ir_context =
      BuildModule(target_env_, consumer_, binary.data(), binary.size());
  assert(ir_context && "Error building module.");
  return ir_context->module()->id_bound();
}

}  // namespace fuzz
}  // namespace spvtools