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 #include "source/fuzz/fuzzer.h"
16 
17 #include <cassert>
18 #include <memory>
19 #include <numeric>
20 #include <sstream>
21 
22 #include "source/fuzz/fact_manager/fact_manager.h"
23 #include "source/fuzz/fuzzer_context.h"
24 #include "source/fuzz/fuzzer_pass_add_access_chains.h"
25 #include "source/fuzz/fuzzer_pass_add_bit_instruction_synonyms.h"
26 #include "source/fuzz/fuzzer_pass_add_composite_extract.h"
27 #include "source/fuzz/fuzzer_pass_add_composite_inserts.h"
28 #include "source/fuzz/fuzzer_pass_add_composite_types.h"
29 #include "source/fuzz/fuzzer_pass_add_copy_memory.h"
30 #include "source/fuzz/fuzzer_pass_add_dead_blocks.h"
31 #include "source/fuzz/fuzzer_pass_add_dead_breaks.h"
32 #include "source/fuzz/fuzzer_pass_add_dead_continues.h"
33 #include "source/fuzz/fuzzer_pass_add_equation_instructions.h"
34 #include "source/fuzz/fuzzer_pass_add_function_calls.h"
35 #include "source/fuzz/fuzzer_pass_add_global_variables.h"
36 #include "source/fuzz/fuzzer_pass_add_image_sample_unused_components.h"
37 #include "source/fuzz/fuzzer_pass_add_loads.h"
38 #include "source/fuzz/fuzzer_pass_add_local_variables.h"
39 #include "source/fuzz/fuzzer_pass_add_loop_preheaders.h"
40 #include "source/fuzz/fuzzer_pass_add_loops_to_create_int_constant_synonyms.h"
41 #include "source/fuzz/fuzzer_pass_add_no_contraction_decorations.h"
42 #include "source/fuzz/fuzzer_pass_add_opphi_synonyms.h"
43 #include "source/fuzz/fuzzer_pass_add_parameters.h"
44 #include "source/fuzz/fuzzer_pass_add_relaxed_decorations.h"
45 #include "source/fuzz/fuzzer_pass_add_stores.h"
46 #include "source/fuzz/fuzzer_pass_add_synonyms.h"
47 #include "source/fuzz/fuzzer_pass_add_vector_shuffle_instructions.h"
48 #include "source/fuzz/fuzzer_pass_adjust_branch_weights.h"
49 #include "source/fuzz/fuzzer_pass_adjust_function_controls.h"
50 #include "source/fuzz/fuzzer_pass_adjust_loop_controls.h"
51 #include "source/fuzz/fuzzer_pass_adjust_memory_operands_masks.h"
52 #include "source/fuzz/fuzzer_pass_adjust_selection_controls.h"
53 #include "source/fuzz/fuzzer_pass_apply_id_synonyms.h"
54 #include "source/fuzz/fuzzer_pass_construct_composites.h"
55 #include "source/fuzz/fuzzer_pass_copy_objects.h"
56 #include "source/fuzz/fuzzer_pass_donate_modules.h"
57 #include "source/fuzz/fuzzer_pass_duplicate_regions_with_selections.h"
58 #include "source/fuzz/fuzzer_pass_expand_vector_reductions.h"
59 #include "source/fuzz/fuzzer_pass_flatten_conditional_branches.h"
60 #include "source/fuzz/fuzzer_pass_inline_functions.h"
61 #include "source/fuzz/fuzzer_pass_interchange_signedness_of_integer_operands.h"
62 #include "source/fuzz/fuzzer_pass_interchange_zero_like_constants.h"
63 #include "source/fuzz/fuzzer_pass_invert_comparison_operators.h"
64 #include "source/fuzz/fuzzer_pass_make_vector_operations_dynamic.h"
65 #include "source/fuzz/fuzzer_pass_merge_blocks.h"
66 #include "source/fuzz/fuzzer_pass_merge_function_returns.h"
67 #include "source/fuzz/fuzzer_pass_mutate_pointers.h"
68 #include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
69 #include "source/fuzz/fuzzer_pass_outline_functions.h"
70 #include "source/fuzz/fuzzer_pass_permute_blocks.h"
71 #include "source/fuzz/fuzzer_pass_permute_function_parameters.h"
72 #include "source/fuzz/fuzzer_pass_permute_instructions.h"
73 #include "source/fuzz/fuzzer_pass_permute_phi_operands.h"
74 #include "source/fuzz/fuzzer_pass_propagate_instructions_down.h"
75 #include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
76 #include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
77 #include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
78 #include "source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
79 #include "source/fuzz/fuzzer_pass_replace_copy_memories_with_loads_stores.h"
80 #include "source/fuzz/fuzzer_pass_replace_copy_objects_with_stores_loads.h"
81 #include "source/fuzz/fuzzer_pass_replace_irrelevant_ids.h"
82 #include "source/fuzz/fuzzer_pass_replace_linear_algebra_instructions.h"
83 #include "source/fuzz/fuzzer_pass_replace_loads_stores_with_copy_memories.h"
84 #include "source/fuzz/fuzzer_pass_replace_opphi_ids_from_dead_predecessors.h"
85 #include "source/fuzz/fuzzer_pass_replace_opselects_with_conditional_branches.h"
86 #include "source/fuzz/fuzzer_pass_replace_parameter_with_global.h"
87 #include "source/fuzz/fuzzer_pass_replace_params_with_struct.h"
88 #include "source/fuzz/fuzzer_pass_split_blocks.h"
89 #include "source/fuzz/fuzzer_pass_swap_commutable_operands.h"
90 #include "source/fuzz/fuzzer_pass_swap_conditional_branch_operands.h"
91 #include "source/fuzz/fuzzer_pass_toggle_access_chain_instruction.h"
92 #include "source/fuzz/fuzzer_pass_wrap_regions_in_selections.h"
93 #include "source/fuzz/pass_management/repeated_pass_manager.h"
94 #include "source/fuzz/pass_management/repeated_pass_manager_looped_with_recommendations.h"
95 #include "source/fuzz/pass_management/repeated_pass_manager_random_with_recommendations.h"
96 #include "source/fuzz/pass_management/repeated_pass_manager_simple.h"
97 #include "source/fuzz/pass_management/repeated_pass_recommender_standard.h"
98 #include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
99 #include "source/fuzz/transformation_context.h"
100 #include "source/opt/build_module.h"
101 #include "source/spirv_fuzzer_options.h"
102 #include "source/util/make_unique.h"
103 
104 namespace spvtools {
105 namespace fuzz {
106 
107 namespace {
108 const uint32_t kIdBoundGap = 100;
109 
110 }  // namespace
111 
Fuzzer(spv_target_env target_env,MessageConsumer consumer,const std::vector<uint32_t> & binary_in,const protobufs::FactSequence & initial_facts,const std::vector<fuzzerutil::ModuleSupplier> & donor_suppliers,std::unique_ptr<RandomGenerator> random_generator,bool enable_all_passes,RepeatedPassStrategy repeated_pass_strategy,bool validate_after_each_fuzzer_pass,spv_validator_options validator_options)112 Fuzzer::Fuzzer(spv_target_env target_env, MessageConsumer consumer,
113                const std::vector<uint32_t>& binary_in,
114                const protobufs::FactSequence& initial_facts,
115                const std::vector<fuzzerutil::ModuleSupplier>& donor_suppliers,
116                std::unique_ptr<RandomGenerator> random_generator,
117                bool enable_all_passes,
118                RepeatedPassStrategy repeated_pass_strategy,
119                bool validate_after_each_fuzzer_pass,
120                spv_validator_options validator_options)
121     : target_env_(target_env),
122       consumer_(std::move(consumer)),
123       binary_in_(binary_in),
124       initial_facts_(initial_facts),
125       donor_suppliers_(donor_suppliers),
126       random_generator_(std::move(random_generator)),
127       enable_all_passes_(enable_all_passes),
128       repeated_pass_strategy_(repeated_pass_strategy),
129       validate_after_each_fuzzer_pass_(validate_after_each_fuzzer_pass),
130       validator_options_(validator_options),
131       num_repeated_passes_applied_(0),
132       ir_context_(nullptr),
133       fuzzer_context_(nullptr),
134       transformation_context_(nullptr),
135       transformation_sequence_out_() {}
136 
137 Fuzzer::~Fuzzer() = default;
138 
139 template <typename FuzzerPassT, typename... Args>
MaybeAddRepeatedPass(uint32_t percentage_chance_of_adding_pass,RepeatedPassInstances * pass_instances,Args &&...extra_args)140 void Fuzzer::MaybeAddRepeatedPass(uint32_t percentage_chance_of_adding_pass,
141                                   RepeatedPassInstances* pass_instances,
142                                   Args&&... extra_args) {
143   if (enable_all_passes_ ||
144       fuzzer_context_->ChoosePercentage(percentage_chance_of_adding_pass)) {
145     pass_instances->SetPass(MakeUnique<FuzzerPassT>(
146         ir_context_.get(), transformation_context_.get(), fuzzer_context_.get(),
147         &transformation_sequence_out_, std::forward<Args>(extra_args)...));
148   }
149 }
150 
151 template <typename FuzzerPassT, typename... Args>
MaybeAddFinalPass(std::vector<std::unique_ptr<FuzzerPass>> * passes,Args &&...extra_args)152 void Fuzzer::MaybeAddFinalPass(std::vector<std::unique_ptr<FuzzerPass>>* passes,
153                                Args&&... extra_args) {
154   if (enable_all_passes_ || fuzzer_context_->ChooseEven()) {
155     passes->push_back(MakeUnique<FuzzerPassT>(
156         ir_context_.get(), transformation_context_.get(), fuzzer_context_.get(),
157         &transformation_sequence_out_, std::forward<Args>(extra_args)...));
158   }
159 }
160 
ApplyPassAndCheckValidity(FuzzerPass * pass) const161 bool Fuzzer::ApplyPassAndCheckValidity(FuzzerPass* pass) const {
162   pass->Apply();
163   return !validate_after_each_fuzzer_pass_ ||
164          fuzzerutil::IsValidAndWellFormed(ir_context_.get(), validator_options_,
165                                           consumer_);
166 }
167 
Run()168 Fuzzer::FuzzerResult Fuzzer::Run() {
169   // Check compatibility between the library version being linked with and the
170   // header files being used.
171   GOOGLE_PROTOBUF_VERIFY_VERSION;
172 
173   assert(ir_context_ == nullptr && fuzzer_context_ == nullptr &&
174          transformation_context_ == nullptr &&
175          transformation_sequence_out_.transformation_size() == 0 &&
176          "'Run' must not be invoked more than once.");
177 
178   spvtools::SpirvTools tools(target_env_);
179   tools.SetMessageConsumer(consumer_);
180   if (!tools.IsValid()) {
181     consumer_(SPV_MSG_ERROR, nullptr, {},
182               "Failed to create SPIRV-Tools interface; stopping.");
183     return {Fuzzer::FuzzerResultStatus::kFailedToCreateSpirvToolsInterface,
184             std::vector<uint32_t>(), protobufs::TransformationSequence()};
185   }
186 
187   // Initial binary should be valid.
188   if (!tools.Validate(&binary_in_[0], binary_in_.size(), validator_options_)) {
189     consumer_(SPV_MSG_ERROR, nullptr, {},
190               "Initial binary is invalid; stopping.");
191     return {Fuzzer::FuzzerResultStatus::kInitialBinaryInvalid,
192             std::vector<uint32_t>(), protobufs::TransformationSequence()};
193   }
194 
195   // Build the module from the input binary.
196   ir_context_ =
197       BuildModule(target_env_, consumer_, binary_in_.data(), binary_in_.size());
198   assert(ir_context_);
199 
200   // The fuzzer will introduce new ids into the module.  The module's id bound
201   // gives the smallest id that can be used for this purpose.  We add an offset
202   // to this so that there is a sizeable gap between the ids used in the
203   // original module and the ids used for fuzzing, as a readability aid.
204   //
205   // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2541) consider the
206   //  case where the maximum id bound is reached.
207   auto minimum_fresh_id = ir_context_->module()->id_bound() + kIdBoundGap;
208   fuzzer_context_ =
209       MakeUnique<FuzzerContext>(random_generator_.get(), minimum_fresh_id);
210 
211   transformation_context_ = MakeUnique<TransformationContext>(
212       MakeUnique<FactManager>(ir_context_.get()), validator_options_);
213   transformation_context_->GetFactManager()->AddInitialFacts(consumer_,
214                                                              initial_facts_);
215 
216   RepeatedPassInstances pass_instances{};
217 
218   // The following passes are likely to be very useful: many other passes
219   // introduce synonyms, irrelevant ids and constants that these passes can work
220   // with.  We thus enable them with high probability.
221   MaybeAddRepeatedPass<FuzzerPassObfuscateConstants>(90, &pass_instances);
222   MaybeAddRepeatedPass<FuzzerPassApplyIdSynonyms>(90, &pass_instances);
223   MaybeAddRepeatedPass<FuzzerPassReplaceIrrelevantIds>(90, &pass_instances);
224 
225   do {
226     // Each call to MaybeAddRepeatedPass randomly decides whether the given pass
227     // should be enabled, and adds an instance of the pass to |pass_instances|
228     // if it is enabled.
229     MaybeAddRepeatedPass<FuzzerPassAddAccessChains>(&pass_instances);
230     MaybeAddRepeatedPass<FuzzerPassAddBitInstructionSynonyms>(&pass_instances);
231     MaybeAddRepeatedPass<FuzzerPassAddCompositeExtract>(&pass_instances);
232     MaybeAddRepeatedPass<FuzzerPassAddCompositeInserts>(&pass_instances);
233     MaybeAddRepeatedPass<FuzzerPassAddCompositeTypes>(&pass_instances);
234     MaybeAddRepeatedPass<FuzzerPassAddCopyMemory>(&pass_instances);
235     MaybeAddRepeatedPass<FuzzerPassAddDeadBlocks>(&pass_instances);
236     MaybeAddRepeatedPass<FuzzerPassAddDeadBreaks>(&pass_instances);
237     MaybeAddRepeatedPass<FuzzerPassAddDeadContinues>(&pass_instances);
238     MaybeAddRepeatedPass<FuzzerPassAddEquationInstructions>(&pass_instances);
239     MaybeAddRepeatedPass<FuzzerPassAddFunctionCalls>(&pass_instances);
240     MaybeAddRepeatedPass<FuzzerPassAddGlobalVariables>(&pass_instances);
241     MaybeAddRepeatedPass<FuzzerPassAddImageSampleUnusedComponents>(
242         &pass_instances);
243     MaybeAddRepeatedPass<FuzzerPassAddLoads>(&pass_instances);
244     MaybeAddRepeatedPass<FuzzerPassAddLocalVariables>(&pass_instances);
245     MaybeAddRepeatedPass<FuzzerPassAddLoopPreheaders>(&pass_instances);
246     MaybeAddRepeatedPass<FuzzerPassAddLoopsToCreateIntConstantSynonyms>(
247         &pass_instances);
248     MaybeAddRepeatedPass<FuzzerPassAddOpPhiSynonyms>(&pass_instances);
249     MaybeAddRepeatedPass<FuzzerPassAddParameters>(&pass_instances);
250     MaybeAddRepeatedPass<FuzzerPassAddRelaxedDecorations>(&pass_instances);
251     MaybeAddRepeatedPass<FuzzerPassAddStores>(&pass_instances);
252     MaybeAddRepeatedPass<FuzzerPassAddSynonyms>(&pass_instances);
253     MaybeAddRepeatedPass<FuzzerPassAddVectorShuffleInstructions>(
254         &pass_instances);
255     MaybeAddRepeatedPass<FuzzerPassConstructComposites>(&pass_instances);
256     MaybeAddRepeatedPass<FuzzerPassCopyObjects>(&pass_instances);
257     MaybeAddRepeatedPass<FuzzerPassDonateModules>(&pass_instances,
258                                                   donor_suppliers_);
259     MaybeAddRepeatedPass<FuzzerPassDuplicateRegionsWithSelections>(
260         &pass_instances);
261     MaybeAddRepeatedPass<FuzzerPassExpandVectorReductions>(&pass_instances);
262     MaybeAddRepeatedPass<FuzzerPassFlattenConditionalBranches>(&pass_instances);
263     MaybeAddRepeatedPass<FuzzerPassInlineFunctions>(&pass_instances);
264     MaybeAddRepeatedPass<FuzzerPassInvertComparisonOperators>(&pass_instances);
265     MaybeAddRepeatedPass<FuzzerPassMakeVectorOperationsDynamic>(
266         &pass_instances);
267     MaybeAddRepeatedPass<FuzzerPassMergeBlocks>(&pass_instances);
268     MaybeAddRepeatedPass<FuzzerPassMergeFunctionReturns>(&pass_instances);
269     MaybeAddRepeatedPass<FuzzerPassMutatePointers>(&pass_instances);
270     MaybeAddRepeatedPass<FuzzerPassOutlineFunctions>(&pass_instances);
271     MaybeAddRepeatedPass<FuzzerPassPermuteBlocks>(&pass_instances);
272     MaybeAddRepeatedPass<FuzzerPassPermuteFunctionParameters>(&pass_instances);
273     MaybeAddRepeatedPass<FuzzerPassPermuteInstructions>(&pass_instances);
274     MaybeAddRepeatedPass<FuzzerPassPropagateInstructionsDown>(&pass_instances);
275     MaybeAddRepeatedPass<FuzzerPassPropagateInstructionsUp>(&pass_instances);
276     MaybeAddRepeatedPass<FuzzerPassPushIdsThroughVariables>(&pass_instances);
277     MaybeAddRepeatedPass<FuzzerPassReplaceAddsSubsMulsWithCarryingExtended>(
278         &pass_instances);
279     MaybeAddRepeatedPass<FuzzerPassReplaceBranchesFromDeadBlocksWithExits>(
280         &pass_instances);
281     MaybeAddRepeatedPass<FuzzerPassReplaceCopyMemoriesWithLoadsStores>(
282         &pass_instances);
283     MaybeAddRepeatedPass<FuzzerPassReplaceCopyObjectsWithStoresLoads>(
284         &pass_instances);
285     MaybeAddRepeatedPass<FuzzerPassReplaceLoadsStoresWithCopyMemories>(
286         &pass_instances);
287     MaybeAddRepeatedPass<FuzzerPassReplaceParameterWithGlobal>(&pass_instances);
288     MaybeAddRepeatedPass<FuzzerPassReplaceLinearAlgebraInstructions>(
289         &pass_instances);
290     MaybeAddRepeatedPass<FuzzerPassReplaceOpPhiIdsFromDeadPredecessors>(
291         &pass_instances);
292     MaybeAddRepeatedPass<FuzzerPassReplaceOpSelectsWithConditionalBranches>(
293         &pass_instances);
294     MaybeAddRepeatedPass<FuzzerPassReplaceParamsWithStruct>(&pass_instances);
295     MaybeAddRepeatedPass<FuzzerPassSplitBlocks>(&pass_instances);
296     MaybeAddRepeatedPass<FuzzerPassSwapBranchConditionalOperands>(
297         &pass_instances);
298     MaybeAddRepeatedPass<FuzzerPassWrapRegionsInSelections>(&pass_instances);
299     // There is a theoretical possibility that no pass instances were created
300     // until now; loop again if so.
301   } while (pass_instances.GetPasses().empty());
302 
303   RepeatedPassRecommenderStandard pass_recommender(&pass_instances,
304                                                    fuzzer_context_.get());
305 
306   std::unique_ptr<RepeatedPassManager> repeated_pass_manager = nullptr;
307   switch (repeated_pass_strategy_) {
308     case RepeatedPassStrategy::kSimple:
309       repeated_pass_manager = MakeUnique<RepeatedPassManagerSimple>(
310           fuzzer_context_.get(), &pass_instances);
311       break;
312     case RepeatedPassStrategy::kLoopedWithRecommendations:
313       repeated_pass_manager =
314           MakeUnique<RepeatedPassManagerLoopedWithRecommendations>(
315               fuzzer_context_.get(), &pass_instances, &pass_recommender);
316       break;
317     case RepeatedPassStrategy::kRandomWithRecommendations:
318       repeated_pass_manager =
319           MakeUnique<RepeatedPassManagerRandomWithRecommendations>(
320               fuzzer_context_.get(), &pass_instances, &pass_recommender);
321       break;
322   }
323 
324   do {
325     if (!ApplyPassAndCheckValidity(
326             repeated_pass_manager->ChoosePass(transformation_sequence_out_))) {
327       return {Fuzzer::FuzzerResultStatus::kFuzzerPassLedToInvalidModule,
328               std::vector<uint32_t>(), protobufs::TransformationSequence()};
329     }
330   } while (ShouldContinueFuzzing());
331 
332   // Now apply some passes that it does not make sense to apply repeatedly,
333   // as they do not unlock other passes.
334   std::vector<std::unique_ptr<FuzzerPass>> final_passes;
335   MaybeAddFinalPass<FuzzerPassAdjustBranchWeights>(&final_passes);
336   MaybeAddFinalPass<FuzzerPassAdjustFunctionControls>(&final_passes);
337   MaybeAddFinalPass<FuzzerPassAdjustLoopControls>(&final_passes);
338   MaybeAddFinalPass<FuzzerPassAdjustMemoryOperandsMasks>(&final_passes);
339   MaybeAddFinalPass<FuzzerPassAdjustSelectionControls>(&final_passes);
340   MaybeAddFinalPass<FuzzerPassAddNoContractionDecorations>(&final_passes);
341   MaybeAddFinalPass<FuzzerPassInterchangeSignednessOfIntegerOperands>(
342       &final_passes);
343   MaybeAddFinalPass<FuzzerPassInterchangeZeroLikeConstants>(&final_passes);
344   MaybeAddFinalPass<FuzzerPassPermutePhiOperands>(&final_passes);
345   MaybeAddFinalPass<FuzzerPassSwapCommutableOperands>(&final_passes);
346   MaybeAddFinalPass<FuzzerPassToggleAccessChainInstruction>(&final_passes);
347   for (auto& pass : final_passes) {
348     if (!ApplyPassAndCheckValidity(pass.get())) {
349       return {Fuzzer::FuzzerResultStatus::kFuzzerPassLedToInvalidModule,
350               std::vector<uint32_t>(), protobufs::TransformationSequence()};
351     }
352   }
353   // Encode the module as a binary.
354   std::vector<uint32_t> binary_out;
355   ir_context_->module()->ToBinary(&binary_out, false);
356 
357   return {Fuzzer::FuzzerResultStatus::kComplete, std::move(binary_out),
358           std::move(transformation_sequence_out_)};
359 }
360 
ShouldContinueFuzzing()361 bool Fuzzer::ShouldContinueFuzzing() {
362   // There's a risk that fuzzing could get stuck, if none of the enabled fuzzer
363   // passes are able to apply any transformations.  To guard against this we
364   // count the number of times some repeated pass has been applied and ensure
365   // that fuzzing stops if the number of repeated passes hits the limit on the
366   // number of transformations that can be applied.
367   assert(
368       num_repeated_passes_applied_ <=
369           fuzzer_context_->GetTransformationLimit() &&
370       "The number of repeated passes applied must not exceed its upper limit.");
371   if (ir_context_->module()->id_bound() >= fuzzer_context_->GetIdBoundLimit()) {
372     return false;
373   }
374   if (num_repeated_passes_applied_ ==
375       fuzzer_context_->GetTransformationLimit()) {
376     // Stop because fuzzing has got stuck.
377     return false;
378   }
379   auto transformations_applied_so_far =
380       static_cast<uint32_t>(transformation_sequence_out_.transformation_size());
381   if (transformations_applied_so_far >=
382       fuzzer_context_->GetTransformationLimit()) {
383     // Stop because we have reached the transformation limit.
384     return false;
385   }
386   // If we have applied T transformations so far, and the limit on the number of
387   // transformations to apply is L (where T < L), the chance that we will
388   // continue fuzzing is:
389   //
390   //     1 - T/(2*L)
391   //
392   // That is, the chance of continuing decreases as more transformations are
393   // applied.  Using 2*L instead of L increases the number of transformations
394   // that are applied on average.
395   auto chance_of_continuing = static_cast<uint32_t>(
396       100.0 * (1.0 - (static_cast<double>(transformations_applied_so_far) /
397                       (2.0 * static_cast<double>(
398                                  fuzzer_context_->GetTransformationLimit())))));
399   if (!fuzzer_context_->ChoosePercentage(chance_of_continuing)) {
400     // We have probabilistically decided to stop.
401     return false;
402   }
403   // Continue fuzzing!
404   num_repeated_passes_applied_++;
405   return true;
406 }
407 
408 }  // namespace fuzz
409 }  // namespace spvtools
410