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
21 #include "source/fuzz/fuzzer_context.h"
22 #include "source/fuzz/fuzzer_pass_add_access_chains.h"
23 #include "source/fuzz/fuzzer_pass_add_bit_instruction_synonyms.h"
24 #include "source/fuzz/fuzzer_pass_add_composite_extract.h"
25 #include "source/fuzz/fuzzer_pass_add_composite_inserts.h"
26 #include "source/fuzz/fuzzer_pass_add_composite_types.h"
27 #include "source/fuzz/fuzzer_pass_add_copy_memory.h"
28 #include "source/fuzz/fuzzer_pass_add_dead_blocks.h"
29 #include "source/fuzz/fuzzer_pass_add_dead_breaks.h"
30 #include "source/fuzz/fuzzer_pass_add_dead_continues.h"
31 #include "source/fuzz/fuzzer_pass_add_equation_instructions.h"
32 #include "source/fuzz/fuzzer_pass_add_function_calls.h"
33 #include "source/fuzz/fuzzer_pass_add_global_variables.h"
34 #include "source/fuzz/fuzzer_pass_add_image_sample_unused_components.h"
35 #include "source/fuzz/fuzzer_pass_add_loads.h"
36 #include "source/fuzz/fuzzer_pass_add_local_variables.h"
37 #include "source/fuzz/fuzzer_pass_add_loop_preheaders.h"
38 #include "source/fuzz/fuzzer_pass_add_loops_to_create_int_constant_synonyms.h"
39 #include "source/fuzz/fuzzer_pass_add_no_contraction_decorations.h"
40 #include "source/fuzz/fuzzer_pass_add_opphi_synonyms.h"
41 #include "source/fuzz/fuzzer_pass_add_parameters.h"
42 #include "source/fuzz/fuzzer_pass_add_relaxed_decorations.h"
43 #include "source/fuzz/fuzzer_pass_add_stores.h"
44 #include "source/fuzz/fuzzer_pass_add_synonyms.h"
45 #include "source/fuzz/fuzzer_pass_add_vector_shuffle_instructions.h"
46 #include "source/fuzz/fuzzer_pass_adjust_branch_weights.h"
47 #include "source/fuzz/fuzzer_pass_adjust_function_controls.h"
48 #include "source/fuzz/fuzzer_pass_adjust_loop_controls.h"
49 #include "source/fuzz/fuzzer_pass_adjust_memory_operands_masks.h"
50 #include "source/fuzz/fuzzer_pass_adjust_selection_controls.h"
51 #include "source/fuzz/fuzzer_pass_apply_id_synonyms.h"
52 #include "source/fuzz/fuzzer_pass_construct_composites.h"
53 #include "source/fuzz/fuzzer_pass_copy_objects.h"
54 #include "source/fuzz/fuzzer_pass_donate_modules.h"
55 #include "source/fuzz/fuzzer_pass_duplicate_regions_with_selections.h"
56 #include "source/fuzz/fuzzer_pass_expand_vector_reductions.h"
57 #include "source/fuzz/fuzzer_pass_flatten_conditional_branches.h"
58 #include "source/fuzz/fuzzer_pass_inline_functions.h"
59 #include "source/fuzz/fuzzer_pass_interchange_signedness_of_integer_operands.h"
60 #include "source/fuzz/fuzzer_pass_interchange_zero_like_constants.h"
61 #include "source/fuzz/fuzzer_pass_invert_comparison_operators.h"
62 #include "source/fuzz/fuzzer_pass_make_vector_operations_dynamic.h"
63 #include "source/fuzz/fuzzer_pass_merge_blocks.h"
64 #include "source/fuzz/fuzzer_pass_merge_function_returns.h"
65 #include "source/fuzz/fuzzer_pass_mutate_pointers.h"
66 #include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
67 #include "source/fuzz/fuzzer_pass_outline_functions.h"
68 #include "source/fuzz/fuzzer_pass_permute_blocks.h"
69 #include "source/fuzz/fuzzer_pass_permute_function_parameters.h"
70 #include "source/fuzz/fuzzer_pass_permute_instructions.h"
71 #include "source/fuzz/fuzzer_pass_permute_phi_operands.h"
72 #include "source/fuzz/fuzzer_pass_propagate_instructions_down.h"
73 #include "source/fuzz/fuzzer_pass_propagate_instructions_up.h"
74 #include "source/fuzz/fuzzer_pass_push_ids_through_variables.h"
75 #include "source/fuzz/fuzzer_pass_replace_adds_subs_muls_with_carrying_extended.h"
76 #include "source/fuzz/fuzzer_pass_replace_branches_from_dead_blocks_with_exits.h"
77 #include "source/fuzz/fuzzer_pass_replace_copy_memories_with_loads_stores.h"
78 #include "source/fuzz/fuzzer_pass_replace_copy_objects_with_stores_loads.h"
79 #include "source/fuzz/fuzzer_pass_replace_irrelevant_ids.h"
80 #include "source/fuzz/fuzzer_pass_replace_linear_algebra_instructions.h"
81 #include "source/fuzz/fuzzer_pass_replace_loads_stores_with_copy_memories.h"
82 #include "source/fuzz/fuzzer_pass_replace_opphi_ids_from_dead_predecessors.h"
83 #include "source/fuzz/fuzzer_pass_replace_opselects_with_conditional_branches.h"
84 #include "source/fuzz/fuzzer_pass_replace_parameter_with_global.h"
85 #include "source/fuzz/fuzzer_pass_replace_params_with_struct.h"
86 #include "source/fuzz/fuzzer_pass_split_blocks.h"
87 #include "source/fuzz/fuzzer_pass_swap_commutable_operands.h"
88 #include "source/fuzz/fuzzer_pass_swap_conditional_branch_operands.h"
89 #include "source/fuzz/fuzzer_pass_toggle_access_chain_instruction.h"
90 #include "source/fuzz/fuzzer_pass_wrap_regions_in_selections.h"
91 #include "source/fuzz/pass_management/repeated_pass_manager.h"
92 #include "source/fuzz/pass_management/repeated_pass_recommender_standard.h"
93 #include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
94 #include "source/fuzz/transformation_context.h"
95 #include "source/opt/build_module.h"
96 #include "source/spirv_fuzzer_options.h"
97 #include "source/util/make_unique.h"
98
99 namespace spvtools {
100 namespace fuzz {
101
Fuzzer(std::unique_ptr<opt::IRContext> ir_context,std::unique_ptr<TransformationContext> transformation_context,std::unique_ptr<FuzzerContext> fuzzer_context,MessageConsumer consumer,const std::vector<fuzzerutil::ModuleSupplier> & donor_suppliers,bool enable_all_passes,RepeatedPassStrategy repeated_pass_strategy,bool validate_after_each_fuzzer_pass,spv_validator_options validator_options)102 Fuzzer::Fuzzer(std::unique_ptr<opt::IRContext> ir_context,
103 std::unique_ptr<TransformationContext> transformation_context,
104 std::unique_ptr<FuzzerContext> fuzzer_context,
105 MessageConsumer consumer,
106 const std::vector<fuzzerutil::ModuleSupplier>& donor_suppliers,
107 bool enable_all_passes,
108 RepeatedPassStrategy repeated_pass_strategy,
109 bool validate_after_each_fuzzer_pass,
110 spv_validator_options validator_options)
111 : consumer_(std::move(consumer)),
112 enable_all_passes_(enable_all_passes),
113 validate_after_each_fuzzer_pass_(validate_after_each_fuzzer_pass),
114 validator_options_(validator_options),
115 num_repeated_passes_applied_(0),
116 is_valid_(true),
117 ir_context_(std::move(ir_context)),
118 transformation_context_(std::move(transformation_context)),
119 fuzzer_context_(std::move(fuzzer_context)),
120 transformation_sequence_out_(),
121 pass_instances_(),
122 repeated_pass_recommender_(nullptr),
123 repeated_pass_manager_(nullptr),
124 final_passes_() {
125 assert(ir_context_ && "IRContext is not initialized");
126 assert(fuzzer_context_ && "FuzzerContext is not initialized");
127 assert(transformation_context_ && "TransformationContext is not initialized");
128 assert(fuzzerutil::IsValidAndWellFormed(ir_context_.get(), validator_options_,
129 consumer_) &&
130 "IRContext is invalid");
131
132 // The following passes are likely to be very useful: many other passes
133 // introduce synonyms, irrelevant ids and constants that these passes can work
134 // with. We thus enable them with high probability.
135 MaybeAddRepeatedPass<FuzzerPassObfuscateConstants>(90, &pass_instances_);
136 MaybeAddRepeatedPass<FuzzerPassApplyIdSynonyms>(90, &pass_instances_);
137 MaybeAddRepeatedPass<FuzzerPassReplaceIrrelevantIds>(90, &pass_instances_);
138
139 do {
140 // Each call to MaybeAddRepeatedPass randomly decides whether the given pass
141 // should be enabled, and adds an instance of the pass to |pass_instances|
142 // if it is enabled.
143 MaybeAddRepeatedPass<FuzzerPassAddAccessChains>(&pass_instances_);
144 MaybeAddRepeatedPass<FuzzerPassAddBitInstructionSynonyms>(&pass_instances_);
145 MaybeAddRepeatedPass<FuzzerPassAddCompositeExtract>(&pass_instances_);
146 MaybeAddRepeatedPass<FuzzerPassAddCompositeInserts>(&pass_instances_);
147 MaybeAddRepeatedPass<FuzzerPassAddCompositeTypes>(&pass_instances_);
148 MaybeAddRepeatedPass<FuzzerPassAddCopyMemory>(&pass_instances_);
149 MaybeAddRepeatedPass<FuzzerPassAddDeadBlocks>(&pass_instances_);
150 MaybeAddRepeatedPass<FuzzerPassAddDeadBreaks>(&pass_instances_);
151 MaybeAddRepeatedPass<FuzzerPassAddDeadContinues>(&pass_instances_);
152 MaybeAddRepeatedPass<FuzzerPassAddEquationInstructions>(&pass_instances_);
153 MaybeAddRepeatedPass<FuzzerPassAddFunctionCalls>(&pass_instances_);
154 MaybeAddRepeatedPass<FuzzerPassAddGlobalVariables>(&pass_instances_);
155 MaybeAddRepeatedPass<FuzzerPassAddImageSampleUnusedComponents>(
156 &pass_instances_);
157 MaybeAddRepeatedPass<FuzzerPassAddLoads>(&pass_instances_);
158 MaybeAddRepeatedPass<FuzzerPassAddLocalVariables>(&pass_instances_);
159 MaybeAddRepeatedPass<FuzzerPassAddLoopPreheaders>(&pass_instances_);
160 MaybeAddRepeatedPass<FuzzerPassAddLoopsToCreateIntConstantSynonyms>(
161 &pass_instances_);
162 MaybeAddRepeatedPass<FuzzerPassAddOpPhiSynonyms>(&pass_instances_);
163 MaybeAddRepeatedPass<FuzzerPassAddParameters>(&pass_instances_);
164 MaybeAddRepeatedPass<FuzzerPassAddRelaxedDecorations>(&pass_instances_);
165 MaybeAddRepeatedPass<FuzzerPassAddStores>(&pass_instances_);
166 MaybeAddRepeatedPass<FuzzerPassAddSynonyms>(&pass_instances_);
167 MaybeAddRepeatedPass<FuzzerPassAddVectorShuffleInstructions>(
168 &pass_instances_);
169 MaybeAddRepeatedPass<FuzzerPassConstructComposites>(&pass_instances_);
170 MaybeAddRepeatedPass<FuzzerPassCopyObjects>(&pass_instances_);
171 MaybeAddRepeatedPass<FuzzerPassDonateModules>(&pass_instances_,
172 donor_suppliers);
173 MaybeAddRepeatedPass<FuzzerPassDuplicateRegionsWithSelections>(
174 &pass_instances_);
175 MaybeAddRepeatedPass<FuzzerPassExpandVectorReductions>(&pass_instances_);
176 MaybeAddRepeatedPass<FuzzerPassFlattenConditionalBranches>(
177 &pass_instances_);
178 MaybeAddRepeatedPass<FuzzerPassInlineFunctions>(&pass_instances_);
179 MaybeAddRepeatedPass<FuzzerPassInvertComparisonOperators>(&pass_instances_);
180 MaybeAddRepeatedPass<FuzzerPassMakeVectorOperationsDynamic>(
181 &pass_instances_);
182 MaybeAddRepeatedPass<FuzzerPassMergeBlocks>(&pass_instances_);
183 MaybeAddRepeatedPass<FuzzerPassMergeFunctionReturns>(&pass_instances_);
184 MaybeAddRepeatedPass<FuzzerPassMutatePointers>(&pass_instances_);
185 MaybeAddRepeatedPass<FuzzerPassOutlineFunctions>(&pass_instances_);
186 MaybeAddRepeatedPass<FuzzerPassPermuteBlocks>(&pass_instances_);
187 MaybeAddRepeatedPass<FuzzerPassPermuteFunctionParameters>(&pass_instances_);
188 MaybeAddRepeatedPass<FuzzerPassPermuteInstructions>(&pass_instances_);
189 MaybeAddRepeatedPass<FuzzerPassPropagateInstructionsDown>(&pass_instances_);
190 MaybeAddRepeatedPass<FuzzerPassPropagateInstructionsUp>(&pass_instances_);
191 MaybeAddRepeatedPass<FuzzerPassPushIdsThroughVariables>(&pass_instances_);
192 MaybeAddRepeatedPass<FuzzerPassReplaceAddsSubsMulsWithCarryingExtended>(
193 &pass_instances_);
194 MaybeAddRepeatedPass<FuzzerPassReplaceBranchesFromDeadBlocksWithExits>(
195 &pass_instances_);
196 MaybeAddRepeatedPass<FuzzerPassReplaceCopyMemoriesWithLoadsStores>(
197 &pass_instances_);
198 MaybeAddRepeatedPass<FuzzerPassReplaceCopyObjectsWithStoresLoads>(
199 &pass_instances_);
200 MaybeAddRepeatedPass<FuzzerPassReplaceLoadsStoresWithCopyMemories>(
201 &pass_instances_);
202 MaybeAddRepeatedPass<FuzzerPassReplaceParameterWithGlobal>(
203 &pass_instances_);
204 MaybeAddRepeatedPass<FuzzerPassReplaceLinearAlgebraInstructions>(
205 &pass_instances_);
206 MaybeAddRepeatedPass<FuzzerPassReplaceOpPhiIdsFromDeadPredecessors>(
207 &pass_instances_);
208 MaybeAddRepeatedPass<FuzzerPassReplaceOpSelectsWithConditionalBranches>(
209 &pass_instances_);
210 MaybeAddRepeatedPass<FuzzerPassReplaceParamsWithStruct>(&pass_instances_);
211 MaybeAddRepeatedPass<FuzzerPassSplitBlocks>(&pass_instances_);
212 MaybeAddRepeatedPass<FuzzerPassSwapBranchConditionalOperands>(
213 &pass_instances_);
214 MaybeAddRepeatedPass<FuzzerPassWrapRegionsInSelections>(&pass_instances_);
215 // There is a theoretical possibility that no pass instances were created
216 // until now; loop again if so.
217 } while (pass_instances_.GetPasses().empty());
218
219 repeated_pass_recommender_ = MakeUnique<RepeatedPassRecommenderStandard>(
220 &pass_instances_, fuzzer_context_.get());
221 repeated_pass_manager_ = RepeatedPassManager::Create(
222 repeated_pass_strategy, fuzzer_context_.get(), &pass_instances_,
223 repeated_pass_recommender_.get());
224
225 MaybeAddFinalPass<FuzzerPassAdjustBranchWeights>(&final_passes_);
226 MaybeAddFinalPass<FuzzerPassAdjustFunctionControls>(&final_passes_);
227 MaybeAddFinalPass<FuzzerPassAdjustLoopControls>(&final_passes_);
228 MaybeAddFinalPass<FuzzerPassAdjustMemoryOperandsMasks>(&final_passes_);
229 MaybeAddFinalPass<FuzzerPassAdjustSelectionControls>(&final_passes_);
230 MaybeAddFinalPass<FuzzerPassAddNoContractionDecorations>(&final_passes_);
231 if (!fuzzer_context_->IsWgslCompatible()) {
232 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/4214):
233 // this is disabled temporarily due to some issues in the Tint compiler.
234 // Enable it back when the issues are resolved.
235 MaybeAddFinalPass<FuzzerPassInterchangeSignednessOfIntegerOperands>(
236 &final_passes_);
237 }
238 MaybeAddFinalPass<FuzzerPassInterchangeZeroLikeConstants>(&final_passes_);
239 MaybeAddFinalPass<FuzzerPassPermutePhiOperands>(&final_passes_);
240 MaybeAddFinalPass<FuzzerPassSwapCommutableOperands>(&final_passes_);
241 MaybeAddFinalPass<FuzzerPassToggleAccessChainInstruction>(&final_passes_);
242 }
243
244 Fuzzer::~Fuzzer() = default;
245
246 template <typename FuzzerPassT, typename... Args>
MaybeAddRepeatedPass(uint32_t percentage_chance_of_adding_pass,RepeatedPassInstances * pass_instances,Args &&...extra_args)247 void Fuzzer::MaybeAddRepeatedPass(uint32_t percentage_chance_of_adding_pass,
248 RepeatedPassInstances* pass_instances,
249 Args&&... extra_args) {
250 if (enable_all_passes_ ||
251 fuzzer_context_->ChoosePercentage(percentage_chance_of_adding_pass)) {
252 pass_instances->SetPass(MakeUnique<FuzzerPassT>(
253 ir_context_.get(), transformation_context_.get(), fuzzer_context_.get(),
254 &transformation_sequence_out_, std::forward<Args>(extra_args)...));
255 }
256 }
257
258 template <typename FuzzerPassT, typename... Args>
MaybeAddFinalPass(std::vector<std::unique_ptr<FuzzerPass>> * passes,Args &&...extra_args)259 void Fuzzer::MaybeAddFinalPass(std::vector<std::unique_ptr<FuzzerPass>>* passes,
260 Args&&... extra_args) {
261 if (enable_all_passes_ || fuzzer_context_->ChooseEven()) {
262 passes->push_back(MakeUnique<FuzzerPassT>(
263 ir_context_.get(), transformation_context_.get(), fuzzer_context_.get(),
264 &transformation_sequence_out_, std::forward<Args>(extra_args)...));
265 }
266 }
267
ApplyPassAndCheckValidity(FuzzerPass * pass) const268 bool Fuzzer::ApplyPassAndCheckValidity(FuzzerPass* pass) const {
269 pass->Apply();
270 return !validate_after_each_fuzzer_pass_ ||
271 fuzzerutil::IsValidAndWellFormed(ir_context_.get(), validator_options_,
272 consumer_);
273 }
274
GetIRContext()275 opt::IRContext* Fuzzer::GetIRContext() { return ir_context_.get(); }
276
GetTransformationSequence() const277 const protobufs::TransformationSequence& Fuzzer::GetTransformationSequence()
278 const {
279 return transformation_sequence_out_;
280 }
281
Run(uint32_t num_of_transformations_to_apply)282 Fuzzer::Result Fuzzer::Run(uint32_t num_of_transformations_to_apply) {
283 assert(is_valid_ && "The module was invalidated during the previous fuzzing");
284
285 const auto initial_num_of_transformations =
286 static_cast<uint32_t>(transformation_sequence_out_.transformation_size());
287
288 auto status = Status::kComplete;
289 do {
290 if (!ApplyPassAndCheckValidity(
291 repeated_pass_manager_->ChoosePass(transformation_sequence_out_))) {
292 status = Status::kFuzzerPassLedToInvalidModule;
293 break;
294 }
295
296 // Check that the module is small enough.
297 if (ir_context_->module()->id_bound() >=
298 fuzzer_context_->GetIdBoundLimit()) {
299 status = Status::kModuleTooBig;
300 break;
301 }
302
303 auto transformations_applied_so_far = static_cast<uint32_t>(
304 transformation_sequence_out_.transformation_size());
305 assert(transformations_applied_so_far >= initial_num_of_transformations &&
306 "Number of transformations cannot decrease");
307
308 // Check if we've already applied the maximum number of transformations.
309 if (transformations_applied_so_far >=
310 fuzzer_context_->GetTransformationLimit()) {
311 status = Status::kTransformationLimitReached;
312 break;
313 }
314
315 // Check that we've not got stuck (this can happen if the only available
316 // fuzzer passes are not able to apply any transformations, or can only
317 // apply very few transformations).
318 if (num_repeated_passes_applied_ >=
319 fuzzer_context_->GetTransformationLimit()) {
320 status = Status::kFuzzerStuck;
321 break;
322 }
323
324 // Check whether we've exceeded the number of transformations we can apply
325 // in a single call to this method.
326 if (num_of_transformations_to_apply != 0 &&
327 transformations_applied_so_far - initial_num_of_transformations >=
328 num_of_transformations_to_apply) {
329 status = Status::kComplete;
330 break;
331 }
332
333 } while (ShouldContinueRepeatedPasses(num_of_transformations_to_apply == 0));
334
335 if (status != Status::kFuzzerPassLedToInvalidModule) {
336 // We apply this transformations despite the fact that we might exceed
337 // |num_of_transformations_to_apply|. This is not a problem for us since
338 // these fuzzer passes are relatively simple yet might trigger some bugs.
339 for (auto& pass : final_passes_) {
340 if (!ApplyPassAndCheckValidity(pass.get())) {
341 status = Status::kFuzzerPassLedToInvalidModule;
342 break;
343 }
344 }
345 }
346
347 is_valid_ = status != Status::kFuzzerPassLedToInvalidModule;
348 return {status, static_cast<uint32_t>(
349 transformation_sequence_out_.transformation_size()) !=
350 initial_num_of_transformations};
351 }
352
ShouldContinueRepeatedPasses(bool continue_fuzzing_probabilistically)353 bool Fuzzer::ShouldContinueRepeatedPasses(
354 bool continue_fuzzing_probabilistically) {
355 if (continue_fuzzing_probabilistically) {
356 // If we have applied T transformations so far, and the limit on the number
357 // of transformations to apply is L (where T < L), the chance that we will
358 // continue fuzzing is:
359 //
360 // 1 - T/(2*L)
361 //
362 // That is, the chance of continuing decreases as more transformations are
363 // applied. Using 2*L instead of L increases the number of transformations
364 // that are applied on average.
365 auto transformations_applied_so_far = static_cast<uint32_t>(
366 transformation_sequence_out_.transformation_size());
367 auto chance_of_continuing = static_cast<uint32_t>(
368 100.0 *
369 (1.0 - (static_cast<double>(transformations_applied_so_far) /
370 (2.0 * static_cast<double>(
371 fuzzer_context_->GetTransformationLimit())))));
372 if (!fuzzer_context_->ChoosePercentage(chance_of_continuing)) {
373 // We have probabilistically decided to stop.
374 return false;
375 }
376 }
377 // Continue fuzzing!
378 num_repeated_passes_applied_++;
379 return true;
380 }
381
382 } // namespace fuzz
383 } // namespace spvtools
384