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