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 <sstream>
20
21 #include "fuzzer_pass_adjust_memory_operands_masks.h"
22 #include "source/fuzz/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_composite_types.h"
26 #include "source/fuzz/fuzzer_pass_add_dead_blocks.h"
27 #include "source/fuzz/fuzzer_pass_add_dead_breaks.h"
28 #include "source/fuzz/fuzzer_pass_add_dead_continues.h"
29 #include "source/fuzz/fuzzer_pass_add_function_calls.h"
30 #include "source/fuzz/fuzzer_pass_add_global_variables.h"
31 #include "source/fuzz/fuzzer_pass_add_loads.h"
32 #include "source/fuzz/fuzzer_pass_add_local_variables.h"
33 #include "source/fuzz/fuzzer_pass_add_no_contraction_decorations.h"
34 #include "source/fuzz/fuzzer_pass_add_stores.h"
35 #include "source/fuzz/fuzzer_pass_add_useful_constructs.h"
36 #include "source/fuzz/fuzzer_pass_adjust_function_controls.h"
37 #include "source/fuzz/fuzzer_pass_adjust_loop_controls.h"
38 #include "source/fuzz/fuzzer_pass_adjust_selection_controls.h"
39 #include "source/fuzz/fuzzer_pass_apply_id_synonyms.h"
40 #include "source/fuzz/fuzzer_pass_construct_composites.h"
41 #include "source/fuzz/fuzzer_pass_copy_objects.h"
42 #include "source/fuzz/fuzzer_pass_donate_modules.h"
43 #include "source/fuzz/fuzzer_pass_merge_blocks.h"
44 #include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
45 #include "source/fuzz/fuzzer_pass_outline_functions.h"
46 #include "source/fuzz/fuzzer_pass_permute_blocks.h"
47 #include "source/fuzz/fuzzer_pass_split_blocks.h"
48 #include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
49 #include "source/fuzz/pseudo_random_generator.h"
50 #include "source/opt/build_module.h"
51 #include "source/spirv_fuzzer_options.h"
52 #include "source/util/make_unique.h"
53
54 namespace spvtools {
55 namespace fuzz {
56
57 namespace {
58 const uint32_t kIdBoundGap = 100;
59
60 const uint32_t kTransformationLimit = 500;
61
62 const uint32_t kChanceOfApplyingAnotherPass = 85;
63
64 // A convenience method to add a fuzzer pass to |passes| with probability 0.5.
65 // All fuzzer passes take |ir_context|, |fact_manager|, |fuzzer_context| and
66 // |transformation_sequence_out| as parameters. Extra arguments can be provided
67 // via |extra_args|.
68 template <typename T, typename... Args>
MaybeAddPass(std::vector<std::unique_ptr<FuzzerPass>> * passes,opt::IRContext * ir_context,FactManager * fact_manager,FuzzerContext * fuzzer_context,protobufs::TransformationSequence * transformation_sequence_out,Args &&...extra_args)69 void MaybeAddPass(
70 std::vector<std::unique_ptr<FuzzerPass>>* passes,
71 opt::IRContext* ir_context, FactManager* fact_manager,
72 FuzzerContext* fuzzer_context,
73 protobufs::TransformationSequence* transformation_sequence_out,
74 Args&&... extra_args) {
75 if (fuzzer_context->ChooseEven()) {
76 passes->push_back(MakeUnique<T>(ir_context, fact_manager, fuzzer_context,
77 transformation_sequence_out,
78 std::forward<Args>(extra_args)...));
79 }
80 }
81
82 } // namespace
83
84 struct Fuzzer::Impl {
Implspvtools::fuzz::Fuzzer::Impl85 explicit Impl(spv_target_env env, uint32_t random_seed,
86 bool validate_after_each_pass)
87 : target_env(env),
88 seed(random_seed),
89 validate_after_each_fuzzer_pass(validate_after_each_pass) {}
90
91 bool ApplyPassAndCheckValidity(FuzzerPass* pass,
92 const opt::IRContext& ir_context,
93 const spvtools::SpirvTools& tools) const;
94
95 const spv_target_env target_env; // Target environment.
96 const uint32_t seed; // Seed for random number generator.
97 bool validate_after_each_fuzzer_pass; // Determines whether the validator
98 // should be invoked after every fuzzer pass.
99 MessageConsumer consumer; // Message consumer.
100 };
101
Fuzzer(spv_target_env env,uint32_t seed,bool validate_after_each_fuzzer_pass)102 Fuzzer::Fuzzer(spv_target_env env, uint32_t seed,
103 bool validate_after_each_fuzzer_pass)
104 : impl_(MakeUnique<Impl>(env, seed, validate_after_each_fuzzer_pass)) {}
105
106 Fuzzer::~Fuzzer() = default;
107
SetMessageConsumer(MessageConsumer c)108 void Fuzzer::SetMessageConsumer(MessageConsumer c) {
109 impl_->consumer = std::move(c);
110 }
111
ApplyPassAndCheckValidity(FuzzerPass * pass,const opt::IRContext & ir_context,const spvtools::SpirvTools & tools) const112 bool Fuzzer::Impl::ApplyPassAndCheckValidity(
113 FuzzerPass* pass, const opt::IRContext& ir_context,
114 const spvtools::SpirvTools& tools) const {
115 pass->Apply();
116 if (validate_after_each_fuzzer_pass) {
117 std::vector<uint32_t> binary_to_validate;
118 ir_context.module()->ToBinary(&binary_to_validate, false);
119 if (!tools.Validate(&binary_to_validate[0], binary_to_validate.size())) {
120 consumer(SPV_MSG_INFO, nullptr, {},
121 "Binary became invalid during fuzzing (set a breakpoint to "
122 "inspect); stopping.");
123 return false;
124 }
125 }
126 return true;
127 }
128
Run(const std::vector<uint32_t> & binary_in,const protobufs::FactSequence & initial_facts,const std::vector<fuzzerutil::ModuleSupplier> & donor_suppliers,std::vector<uint32_t> * binary_out,protobufs::TransformationSequence * transformation_sequence_out) const129 Fuzzer::FuzzerResultStatus Fuzzer::Run(
130 const std::vector<uint32_t>& binary_in,
131 const protobufs::FactSequence& initial_facts,
132 const std::vector<fuzzerutil::ModuleSupplier>& donor_suppliers,
133 std::vector<uint32_t>* binary_out,
134 protobufs::TransformationSequence* transformation_sequence_out) const {
135 // Check compatibility between the library version being linked with and the
136 // header files being used.
137 GOOGLE_PROTOBUF_VERIFY_VERSION;
138
139 spvtools::SpirvTools tools(impl_->target_env);
140 tools.SetMessageConsumer(impl_->consumer);
141 if (!tools.IsValid()) {
142 impl_->consumer(SPV_MSG_ERROR, nullptr, {},
143 "Failed to create SPIRV-Tools interface; stopping.");
144 return Fuzzer::FuzzerResultStatus::kFailedToCreateSpirvToolsInterface;
145 }
146
147 // Initial binary should be valid.
148 if (!tools.Validate(&binary_in[0], binary_in.size())) {
149 impl_->consumer(SPV_MSG_ERROR, nullptr, {},
150 "Initial binary is invalid; stopping.");
151 return Fuzzer::FuzzerResultStatus::kInitialBinaryInvalid;
152 }
153
154 // Build the module from the input binary.
155 std::unique_ptr<opt::IRContext> ir_context = BuildModule(
156 impl_->target_env, impl_->consumer, binary_in.data(), binary_in.size());
157 assert(ir_context);
158
159 // Make a PRNG from the seed passed to the fuzzer on creation.
160 PseudoRandomGenerator random_generator(impl_->seed);
161
162 // The fuzzer will introduce new ids into the module. The module's id bound
163 // gives the smallest id that can be used for this purpose. We add an offset
164 // to this so that there is a sizeable gap between the ids used in the
165 // original module and the ids used for fuzzing, as a readability aid.
166 //
167 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2541) consider the
168 // case where the maximum id bound is reached.
169 auto minimum_fresh_id = ir_context->module()->id_bound() + kIdBoundGap;
170 FuzzerContext fuzzer_context(&random_generator, minimum_fresh_id);
171
172 FactManager fact_manager;
173 fact_manager.AddFacts(impl_->consumer, initial_facts, ir_context.get());
174
175 // Add some essential ingredients to the module if they are not already
176 // present, such as boolean constants.
177 FuzzerPassAddUsefulConstructs add_useful_constructs(
178 ir_context.get(), &fact_manager, &fuzzer_context,
179 transformation_sequence_out);
180 if (!impl_->ApplyPassAndCheckValidity(&add_useful_constructs, *ir_context,
181 tools)) {
182 return Fuzzer::FuzzerResultStatus::kFuzzerPassLedToInvalidModule;
183 }
184
185 // Apply some semantics-preserving passes.
186 std::vector<std::unique_ptr<FuzzerPass>> passes;
187 while (passes.empty()) {
188 MaybeAddPass<FuzzerPassAddAccessChains>(&passes, ir_context.get(),
189 &fact_manager, &fuzzer_context,
190 transformation_sequence_out);
191 MaybeAddPass<FuzzerPassAddCompositeTypes>(&passes, ir_context.get(),
192 &fact_manager, &fuzzer_context,
193 transformation_sequence_out);
194 MaybeAddPass<FuzzerPassAddDeadBlocks>(&passes, ir_context.get(),
195 &fact_manager, &fuzzer_context,
196 transformation_sequence_out);
197 MaybeAddPass<FuzzerPassAddDeadBreaks>(&passes, ir_context.get(),
198 &fact_manager, &fuzzer_context,
199 transformation_sequence_out);
200 MaybeAddPass<FuzzerPassAddDeadContinues>(&passes, ir_context.get(),
201 &fact_manager, &fuzzer_context,
202 transformation_sequence_out);
203 MaybeAddPass<FuzzerPassAddFunctionCalls>(&passes, ir_context.get(),
204 &fact_manager, &fuzzer_context,
205 transformation_sequence_out);
206 MaybeAddPass<FuzzerPassAddGlobalVariables>(&passes, ir_context.get(),
207 &fact_manager, &fuzzer_context,
208 transformation_sequence_out);
209 MaybeAddPass<FuzzerPassAddLoads>(&passes, ir_context.get(), &fact_manager,
210 &fuzzer_context,
211 transformation_sequence_out);
212 MaybeAddPass<FuzzerPassAddLocalVariables>(&passes, ir_context.get(),
213 &fact_manager, &fuzzer_context,
214 transformation_sequence_out);
215 MaybeAddPass<FuzzerPassAddStores>(&passes, ir_context.get(), &fact_manager,
216 &fuzzer_context,
217 transformation_sequence_out);
218 MaybeAddPass<FuzzerPassApplyIdSynonyms>(&passes, ir_context.get(),
219 &fact_manager, &fuzzer_context,
220 transformation_sequence_out);
221 MaybeAddPass<FuzzerPassConstructComposites>(&passes, ir_context.get(),
222 &fact_manager, &fuzzer_context,
223 transformation_sequence_out);
224 MaybeAddPass<FuzzerPassCopyObjects>(&passes, ir_context.get(),
225 &fact_manager, &fuzzer_context,
226 transformation_sequence_out);
227 MaybeAddPass<FuzzerPassDonateModules>(
228 &passes, ir_context.get(), &fact_manager, &fuzzer_context,
229 transformation_sequence_out, donor_suppliers);
230 MaybeAddPass<FuzzerPassMergeBlocks>(&passes, ir_context.get(),
231 &fact_manager, &fuzzer_context,
232 transformation_sequence_out);
233 MaybeAddPass<FuzzerPassObfuscateConstants>(&passes, ir_context.get(),
234 &fact_manager, &fuzzer_context,
235 transformation_sequence_out);
236 MaybeAddPass<FuzzerPassOutlineFunctions>(&passes, ir_context.get(),
237 &fact_manager, &fuzzer_context,
238 transformation_sequence_out);
239 MaybeAddPass<FuzzerPassPermuteBlocks>(&passes, ir_context.get(),
240 &fact_manager, &fuzzer_context,
241 transformation_sequence_out);
242 MaybeAddPass<FuzzerPassSplitBlocks>(&passes, ir_context.get(),
243 &fact_manager, &fuzzer_context,
244 transformation_sequence_out);
245 }
246
247 bool is_first = true;
248 while (static_cast<uint32_t>(
249 transformation_sequence_out->transformation_size()) <
250 kTransformationLimit &&
251 (is_first ||
252 fuzzer_context.ChoosePercentage(kChanceOfApplyingAnotherPass))) {
253 is_first = false;
254 if (!impl_->ApplyPassAndCheckValidity(
255 passes[fuzzer_context.RandomIndex(passes)].get(), *ir_context,
256 tools)) {
257 return Fuzzer::FuzzerResultStatus::kFuzzerPassLedToInvalidModule;
258 }
259 }
260
261 // Now apply some passes that it does not make sense to apply repeatedly,
262 // as they do not unlock other passes.
263 std::vector<std::unique_ptr<FuzzerPass>> final_passes;
264 MaybeAddPass<FuzzerPassAdjustFunctionControls>(
265 &final_passes, ir_context.get(), &fact_manager, &fuzzer_context,
266 transformation_sequence_out);
267 MaybeAddPass<FuzzerPassAdjustLoopControls>(&final_passes, ir_context.get(),
268 &fact_manager, &fuzzer_context,
269 transformation_sequence_out);
270 MaybeAddPass<FuzzerPassAdjustMemoryOperandsMasks>(
271 &final_passes, ir_context.get(), &fact_manager, &fuzzer_context,
272 transformation_sequence_out);
273 MaybeAddPass<FuzzerPassAdjustSelectionControls>(
274 &final_passes, ir_context.get(), &fact_manager, &fuzzer_context,
275 transformation_sequence_out);
276 MaybeAddPass<FuzzerPassAddNoContractionDecorations>(
277 &final_passes, ir_context.get(), &fact_manager, &fuzzer_context,
278 transformation_sequence_out);
279 for (auto& pass : final_passes) {
280 if (!impl_->ApplyPassAndCheckValidity(pass.get(), *ir_context, tools)) {
281 return Fuzzer::FuzzerResultStatus::kFuzzerPassLedToInvalidModule;
282 }
283 }
284
285 // Encode the module as a binary.
286 ir_context->module()->ToBinary(binary_out, false);
287
288 return Fuzzer::FuzzerResultStatus::kComplete;
289 }
290
291 } // namespace fuzz
292 } // namespace spvtools
293