Employ the "swarm testing" idea in spirv-fuzz (#2890)
This change to spirv-fuzz uses ideas from "Swarm Testing" (Groce et al. 2012), so that a random subset of fuzzer passes are enabled. These passes are then applied repeatedly in a randomized fashion, with the aggression with which they are applied being randomly chosen per pass.
There is plenty of scope for refining the probabilities introduce in this change; this is just meant to be a reasonable first effort.
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 3b03493..8e36a32 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -15,6 +15,7 @@
#include "source/fuzz/fuzzer.h"
#include <cassert>
+#include <memory>
#include <sstream>
#include "source/fuzz/fact_manager.h"
@@ -38,8 +39,25 @@
namespace {
const uint32_t kIdBoundGap = 100;
+
+const uint32_t kTransformationLimit = 500;
+
+const uint32_t kChanceOfApplyingAnotherPass = 85;
+
+template <typename T>
+void MaybeAddPass(
+ std::vector<std::unique_ptr<FuzzerPass>>* passes,
+ opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformation_sequence_out) {
+ if (fuzzer_context->ChooseEven()) {
+ passes->push_back(MakeUnique<T>(ir_context, fact_manager, fuzzer_context,
+ transformation_sequence_out));
+ }
}
+} // namespace
+
struct Fuzzer::Impl {
explicit Impl(spv_target_env env) : target_env(env) {}
@@ -109,29 +127,40 @@
.Apply();
// Apply some semantics-preserving passes.
- FuzzerPassCopyObjects(ir_context.get(), &fact_manager, &fuzzer_context,
- transformation_sequence_out)
- .Apply();
- FuzzerPassApplyIdSynonyms(ir_context.get(), &fact_manager, &fuzzer_context,
- transformation_sequence_out)
- .Apply();
- FuzzerPassSplitBlocks(ir_context.get(), &fact_manager, &fuzzer_context,
- transformation_sequence_out)
- .Apply();
- FuzzerPassAddDeadBreaks(ir_context.get(), &fact_manager, &fuzzer_context,
- transformation_sequence_out)
- .Apply();
- FuzzerPassAddDeadContinues(ir_context.get(), &fact_manager, &fuzzer_context,
- transformation_sequence_out)
- .Apply();
- FuzzerPassObfuscateConstants(ir_context.get(), &fact_manager, &fuzzer_context,
- transformation_sequence_out)
- .Apply();
+ std::vector<std::unique_ptr<FuzzerPass>> passes;
+ while (passes.empty()) {
+ MaybeAddPass<FuzzerPassAddDeadBreaks>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
+ MaybeAddPass<FuzzerPassAddDeadContinues>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
+ MaybeAddPass<FuzzerPassApplyIdSynonyms>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
+ MaybeAddPass<FuzzerPassCopyObjects>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
+ MaybeAddPass<FuzzerPassObfuscateConstants>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
+ MaybeAddPass<FuzzerPassPermuteBlocks>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
+ MaybeAddPass<FuzzerPassSplitBlocks>(&passes, ir_context.get(),
+ &fact_manager, &fuzzer_context,
+ transformation_sequence_out);
+ }
- // Finally, give the blocks in the module a good shake-up.
- FuzzerPassPermuteBlocks(ir_context.get(), &fact_manager, &fuzzer_context,
- transformation_sequence_out)
- .Apply();
+ bool is_first = true;
+ while (static_cast<uint32_t>(
+ transformation_sequence_out->transformation_size()) <
+ kTransformationLimit &&
+ (is_first ||
+ fuzzer_context.ChoosePercentage(kChanceOfApplyingAnotherPass))) {
+ is_first = false;
+ passes[fuzzer_context.RandomIndex(passes)]->Apply();
+ }
// Encode the module as a binary.
ir_context->module()->ToBinary(binary_out, false);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 8d097b0..69c6e56 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -20,17 +20,16 @@
namespace fuzz {
namespace {
-// Default probabilities for applying various transformations.
-// All values are percentages.
-// Keep them in alphabetical order.
+// Default <minimum, maximum> pairs of probabilities for applying various
+// transformations. All values are percentages. Keep them in alphabetical order.
-const uint32_t kDefaultChanceOfAddingDeadBreak = 20;
-const uint32_t kDefaultChanceOfAddingDeadContinue = 20;
-const uint32_t kDefaultChanceOfCopyingObject = 20;
-const uint32_t kDefaultChanceOfMovingBlockDown = 25;
-const uint32_t kDefaultChanceOfObfuscatingConstant = 20;
-const uint32_t kDefaultChanceOfReplacingIdWithSynonym = 20;
-const uint32_t kDefaultChanceOfSplittingBlock = 20;
+const std::pair<uint32_t, uint32_t> kChanceOfAddingDeadBreak = {5, 80};
+const std::pair<uint32_t, uint32_t> kChanceOfAddingDeadContinue = {5, 80};
+const std::pair<uint32_t, uint32_t> kChanceOfCopyingObject = {20, 50};
+const std::pair<uint32_t, uint32_t> kChanceOfMovingBlockDown = {20, 50};
+const std::pair<uint32_t, uint32_t> kChanceOfObfuscatingConstant = {10, 90};
+const std::pair<uint32_t, uint32_t> kChanceOfReplacingIdWithSynonym = {10, 90};
+const std::pair<uint32_t, uint32_t> kChanceOfSplittingBlock = {40, 95};
// Default functions for controlling how deep to go during recursive
// generation/transformation. Keep them in alphabetical order.
@@ -48,16 +47,21 @@
uint32_t min_fresh_id)
: random_generator_(random_generator),
next_fresh_id_(min_fresh_id),
- chance_of_adding_dead_break_(kDefaultChanceOfAddingDeadBreak),
- chance_of_adding_dead_continue_(kDefaultChanceOfAddingDeadContinue),
- chance_of_copying_object_(kDefaultChanceOfCopyingObject),
- chance_of_moving_block_down_(kDefaultChanceOfMovingBlockDown),
- chance_of_obfuscating_constant_(kDefaultChanceOfObfuscatingConstant),
- chance_of_replacing_id_with_synonym_(
- kDefaultChanceOfReplacingIdWithSynonym),
- chance_of_splitting_block_(kDefaultChanceOfSplittingBlock),
go_deeper_in_constant_obfuscation_(
- kDefaultGoDeeperInConstantObfuscation) {}
+ kDefaultGoDeeperInConstantObfuscation) {
+ chance_of_adding_dead_break_ =
+ ChooseBetweenMinAndMax(kChanceOfAddingDeadBreak);
+ chance_of_adding_dead_continue_ =
+ ChooseBetweenMinAndMax(kChanceOfAddingDeadContinue);
+ chance_of_copying_object_ = ChooseBetweenMinAndMax(kChanceOfCopyingObject);
+ chance_of_moving_block_down_ =
+ ChooseBetweenMinAndMax(kChanceOfMovingBlockDown);
+ chance_of_obfuscating_constant_ =
+ ChooseBetweenMinAndMax(kChanceOfObfuscatingConstant);
+ chance_of_replacing_id_with_synonym_ =
+ ChooseBetweenMinAndMax(kChanceOfReplacingIdWithSynonym);
+ chance_of_splitting_block_ = ChooseBetweenMinAndMax(kChanceOfSplittingBlock);
+}
FuzzerContext::~FuzzerContext() = default;
@@ -70,5 +74,12 @@
return random_generator_->RandomPercentage() < percentage_chance;
}
+uint32_t FuzzerContext::ChooseBetweenMinAndMax(
+ const std::pair<uint32_t, uint32_t>& min_max) {
+ assert(min_max.first <= min_max.second);
+ return min_max.first +
+ random_generator_->RandomUint32(min_max.second - min_max.first + 1);
+}
+
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 90d8756..a1ad66f 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -16,6 +16,7 @@
#define SOURCE_FUZZ_FUZZER_CONTEXT_H_
#include <functional>
+#include <utility>
#include "source/fuzz/random_generator.h"
#include "source/opt/function.h"
@@ -45,7 +46,7 @@
// method, and which must be non-empty. Typically 'HasSizeMethod' will be an
// std::vector.
template <typename HasSizeMethod>
- uint32_t RandomIndex(HasSizeMethod sequence) {
+ uint32_t RandomIndex(const HasSizeMethod& sequence) {
assert(sequence.size() > 0);
return random_generator_->RandomUint32(
static_cast<uint32_t>(sequence.size()));
@@ -97,6 +98,10 @@
// or mutating constructs recursively.
const std::function<bool(uint32_t, RandomGenerator*)>&
go_deeper_in_constant_obfuscation_;
+
+ // Requires |min_max.first| <= |min_max.second|, and returns a value in the
+ // range [ |min_max.first|, |min_max.second| ]
+ uint32_t ChooseBetweenMinAndMax(const std::pair<uint32_t, uint32_t>& min_max);
};
} // namespace fuzz
diff --git a/source/fuzz/transformation_move_block_down.cpp b/source/fuzz/transformation_move_block_down.cpp
index ebce185..205818b 100644
--- a/source/fuzz/transformation_move_block_down.cpp
+++ b/source/fuzz/transformation_move_block_down.cpp
@@ -84,13 +84,11 @@
"To be able to move a block down, it needs to have a "
"program-order successor.");
function.MoveBasicBlockToAfter(message_.block_id(), &*block_it);
- // It is prudent to invalidate analyses after changing block ordering in
- // case any of them depend on it, but the ones that definitely do not
- // depend on ordering can be preserved. These include the following,
- // which can likely be extended.
+ // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2889):
+ // revisit whether it would be OK to avoid invalidating the dominator
+ // analysis (and perhaps other analyses).
context->InvalidateAnalysesExceptFor(
- opt::IRContext::Analysis::kAnalysisDefUse |
- opt::IRContext::Analysis::kAnalysisDominatorAnalysis);
+ opt::IRContext::Analysis::kAnalysisDefUse);
return;
}
diff --git a/test/fuzz/fuzzer_replayer_test.cpp b/test/fuzz/fuzzer_replayer_test.cpp
index 3c36602..5fb71b0 100644
--- a/test/fuzz/fuzzer_replayer_test.cpp
+++ b/test/fuzz/fuzzer_replayer_test.cpp
@@ -54,7 +54,7 @@
std::vector<uint32_t> replayer_binary_out;
protobufs::TransformationSequence replayer_transformation_sequence_out;
- Replayer replayer(env, true);
+ Replayer replayer(env, false);
replayer.SetMessageConsumer(kSilentConsumer);
auto replayer_result_status = replayer.Run(
binary_in, initial_facts, fuzzer_transformation_sequence_out,
diff --git a/test/fuzz/fuzzer_shrinker_test.cpp b/test/fuzz/fuzzer_shrinker_test.cpp
index 933038d..84608f3 100644
--- a/test/fuzz/fuzzer_shrinker_test.cpp
+++ b/test/fuzz/fuzzer_shrinker_test.cpp
@@ -125,7 +125,7 @@
const std::vector<uint32_t>& expected_binary_out,
uint32_t expected_transformations_out_size, uint32_t step_limit) {
// Run the shrinker.
- Shrinker shrinker(target_env, step_limit, true);
+ Shrinker shrinker(target_env, step_limit, false);
shrinker.SetMessageConsumer(kSilentConsumer);
std::vector<uint32_t> binary_out;
diff --git a/test/fuzz/transformation_split_block_test.cpp b/test/fuzz/transformation_split_block_test.cpp
index d33ccba..dc6d4d0 100644
--- a/test/fuzz/transformation_split_block_test.cpp
+++ b/test/fuzz/transformation_split_block_test.cpp
@@ -687,12 +687,12 @@
%10 = OpVariable %7 Function
OpStore %8 %9
%11 = OpLoad %6 %8
- OpBranch %20
- %20 = OpLabel
- %21 = OpPhi %6 %11 %5
- OpStore %10 %21
- OpReturn
- OpFunctionEnd
+ OpBranch %20
+ %20 = OpLabel
+ %21 = OpPhi %6 %11 %5
+ OpStore %10 %21
+ OpReturn
+ OpFunctionEnd
)";
const auto env = SPV_ENV_UNIVERSAL_1_3;
@@ -732,14 +732,14 @@
%10 = OpVariable %7 Function
OpStore %8 %9
%11 = OpLoad %6 %8
- OpBranch %20
- %20 = OpLabel
- OpBranch %100
- %100 = OpLabel
- %21 = OpPhi %6 %11 %20
- OpStore %10 %21
- OpReturn
- OpFunctionEnd
+ OpBranch %20
+ %20 = OpLabel
+ OpBranch %100
+ %100 = OpLabel
+ %21 = OpPhi %6 %11 %20
+ OpStore %10 %21
+ OpReturn
+ OpFunctionEnd
)";
ASSERT_TRUE(IsEqual(env, after_split, context.get()));
}
