1 // Copyright (c) 2020 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/transformation_access_chain.h"
16
17 #include <vector>
18
19 #include "source/fuzz/fuzzer_util.h"
20 #include "source/fuzz/instruction_descriptor.h"
21
22 namespace spvtools {
23 namespace fuzz {
24
TransformationAccessChain(const spvtools::fuzz::protobufs::TransformationAccessChain & message)25 TransformationAccessChain::TransformationAccessChain(
26 const spvtools::fuzz::protobufs::TransformationAccessChain& message)
27 : message_(message) {}
28
TransformationAccessChain(uint32_t fresh_id,uint32_t pointer_id,const std::vector<uint32_t> & index_id,const protobufs::InstructionDescriptor & instruction_to_insert_before,const std::vector<std::pair<uint32_t,uint32_t>> & fresh_ids_for_clamping)29 TransformationAccessChain::TransformationAccessChain(
30 uint32_t fresh_id, uint32_t pointer_id,
31 const std::vector<uint32_t>& index_id,
32 const protobufs::InstructionDescriptor& instruction_to_insert_before,
33 const std::vector<std::pair<uint32_t, uint32_t>>& fresh_ids_for_clamping) {
34 message_.set_fresh_id(fresh_id);
35 message_.set_pointer_id(pointer_id);
36 for (auto id : index_id) {
37 message_.add_index_id(id);
38 }
39 *message_.mutable_instruction_to_insert_before() =
40 instruction_to_insert_before;
41 for (auto clamping_ids_pair : fresh_ids_for_clamping) {
42 protobufs::UInt32Pair pair;
43 pair.set_first(clamping_ids_pair.first);
44 pair.set_second(clamping_ids_pair.second);
45 *message_.add_fresh_ids_for_clamping() = pair;
46 }
47 }
48
IsApplicable(opt::IRContext * ir_context,const TransformationContext &) const49 bool TransformationAccessChain::IsApplicable(
50 opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
51 // Keep track of the fresh ids used to make sure that they are distinct.
52 std::set<uint32_t> fresh_ids_used;
53
54 // The result id must be fresh.
55 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
56 message_.fresh_id(), ir_context, &fresh_ids_used)) {
57 return false;
58 }
59 // The pointer id must exist and have a type.
60 auto pointer = ir_context->get_def_use_mgr()->GetDef(message_.pointer_id());
61 if (!pointer || !pointer->type_id()) {
62 return false;
63 }
64 // The type must indeed be a pointer.
65 auto pointer_type = ir_context->get_def_use_mgr()->GetDef(pointer->type_id());
66 if (pointer_type->opcode() != SpvOpTypePointer) {
67 return false;
68 }
69
70 // The described instruction to insert before must exist and be a suitable
71 // point where an OpAccessChain instruction could be inserted.
72 auto instruction_to_insert_before =
73 FindInstruction(message_.instruction_to_insert_before(), ir_context);
74 if (!instruction_to_insert_before) {
75 return false;
76 }
77 if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
78 SpvOpAccessChain, instruction_to_insert_before)) {
79 return false;
80 }
81
82 // Do not allow making an access chain from a null or undefined pointer, as
83 // we do not want to allow accessing such pointers. This might be acceptable
84 // in dead blocks, but we conservatively avoid it.
85 switch (pointer->opcode()) {
86 case SpvOpConstantNull:
87 case SpvOpUndef:
88 assert(
89 false &&
90 "Access chains should not be created from null/undefined pointers");
91 return false;
92 default:
93 break;
94 }
95
96 // The pointer on which the access chain is to be based needs to be available
97 // (according to dominance rules) at the insertion point.
98 if (!fuzzerutil::IdIsAvailableBeforeInstruction(
99 ir_context, instruction_to_insert_before, message_.pointer_id())) {
100 return false;
101 }
102
103 // We now need to use the given indices to walk the type structure of the
104 // base type of the pointer, making sure that (a) the indices correspond to
105 // integers, and (b) these integer values are in-bounds.
106
107 // Start from the base type of the pointer.
108 uint32_t subobject_type_id = pointer_type->GetSingleWordInOperand(1);
109
110 int id_pairs_used = 0;
111
112 // Consider the given index ids in turn.
113 for (auto index_id : message_.index_id()) {
114 // The index value will correspond to the value of the index if the object
115 // is a struct, otherwise the value 0 will be used.
116 uint32_t index_value;
117
118 // Check whether the object is a struct.
119 if (ir_context->get_def_use_mgr()->GetDef(subobject_type_id)->opcode() ==
120 SpvOpTypeStruct) {
121 // It is a struct: we need to retrieve the integer value.
122
123 bool successful;
124 std::tie(successful, index_value) =
125 GetIndexValue(ir_context, index_id, subobject_type_id);
126
127 if (!successful) {
128 return false;
129 }
130 } else {
131 // It is not a struct: the index will need clamping.
132
133 if (message_.fresh_ids_for_clamping().size() <= id_pairs_used) {
134 // We don't have enough ids
135 return false;
136 }
137
138 // Get two new ids to use and update the amount used.
139 protobufs::UInt32Pair fresh_ids =
140 message_.fresh_ids_for_clamping()[id_pairs_used++];
141
142 // Valid ids need to have been given
143 if (fresh_ids.first() == 0 || fresh_ids.second() == 0) {
144 return false;
145 }
146
147 // Check that the ids are actually fresh and not already used by this
148 // transformation.
149 if (!CheckIdIsFreshAndNotUsedByThisTransformation(
150 fresh_ids.first(), ir_context, &fresh_ids_used) ||
151 !CheckIdIsFreshAndNotUsedByThisTransformation(
152 fresh_ids.second(), ir_context, &fresh_ids_used)) {
153 return false;
154 }
155
156 if (!ValidIndexToComposite(ir_context, index_id, subobject_type_id)) {
157 return false;
158 }
159
160 // Perform the clamping using the fresh ids at our disposal.
161 auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
162
163 uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
164 *ir_context->get_def_use_mgr()->GetDef(subobject_type_id),
165 ir_context);
166
167 // The module must have an integer constant of value bound-1 of the same
168 // type as the index.
169 if (!fuzzerutil::MaybeGetIntegerConstantFromValueAndType(
170 ir_context, bound - 1, index_instruction->type_id())) {
171 return false;
172 }
173
174 // The module must have the definition of bool type to make a comparison.
175 if (!fuzzerutil::MaybeGetBoolType(ir_context)) {
176 return false;
177 }
178
179 // The index is not necessarily a constant, so we may not know its value.
180 // We can use index 0 because the components of a non-struct composite
181 // all have the same type, and index 0 is always in bounds.
182 index_value = 0;
183 }
184
185 // Try to walk down the type using this index. This will yield 0 if the
186 // type is not a composite or the index is out of bounds, and the id of
187 // the next type otherwise.
188 subobject_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
189 ir_context, subobject_type_id, index_value);
190 if (!subobject_type_id) {
191 // Either the type was not a composite (so that too many indices were
192 // provided), or the index was out of bounds.
193 return false;
194 }
195 }
196 // At this point, |subobject_type_id| is the type of the value targeted by
197 // the new access chain. The result type of the access chain should be a
198 // pointer to this type, with the same storage class as for the original
199 // pointer. Such a pointer type needs to exist in the module.
200 //
201 // We do not use the type manager to look up this type, due to problems
202 // associated with pointers to isomorphic structs being regarded as the same.
203 return fuzzerutil::MaybeGetPointerType(
204 ir_context, subobject_type_id,
205 static_cast<SpvStorageClass>(
206 pointer_type->GetSingleWordInOperand(0))) != 0;
207 }
208
Apply(opt::IRContext * ir_context,TransformationContext * transformation_context) const209 void TransformationAccessChain::Apply(
210 opt::IRContext* ir_context,
211 TransformationContext* transformation_context) const {
212 // The operands to the access chain are the pointer followed by the indices.
213 // The result type of the access chain is determined by where the indices
214 // lead. We thus push the pointer to a sequence of operands, and then follow
215 // the indices, pushing each to the operand list and tracking the type
216 // obtained by following it. Ultimately this yields the type of the
217 // component reached by following all the indices, and the result type is
218 // a pointer to this component type.
219 opt::Instruction::OperandList operands;
220
221 // Add the pointer id itself.
222 operands.push_back({SPV_OPERAND_TYPE_ID, {message_.pointer_id()}});
223
224 // Start walking the indices, starting with the pointer's base type.
225 auto pointer_type = ir_context->get_def_use_mgr()->GetDef(
226 ir_context->get_def_use_mgr()->GetDef(message_.pointer_id())->type_id());
227 uint32_t subobject_type_id = pointer_type->GetSingleWordInOperand(1);
228
229 uint32_t id_pairs_used = 0;
230
231 // Go through the index ids in turn.
232 for (auto index_id : message_.index_id()) {
233 uint32_t index_value;
234
235 // Actual id to be used in the instruction: the original id
236 // or the clamped one.
237 uint32_t new_index_id;
238
239 // Check whether the object is a struct.
240 if (ir_context->get_def_use_mgr()->GetDef(subobject_type_id)->opcode() ==
241 SpvOpTypeStruct) {
242 // It is a struct: we need to retrieve the integer value.
243
244 index_value =
245 GetIndexValue(ir_context, index_id, subobject_type_id).second;
246
247 new_index_id = index_id;
248
249 } else {
250 // It is not a struct: the index will need clamping.
251
252 // Get two new ids to use and update the amount used.
253 protobufs::UInt32Pair fresh_ids =
254 message_.fresh_ids_for_clamping()[id_pairs_used++];
255
256 // Perform the clamping using the fresh ids at our disposal.
257 // The module will not be changed if |add_clamping_instructions| is not
258 // set.
259 auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
260
261 uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
262 *ir_context->get_def_use_mgr()->GetDef(subobject_type_id),
263 ir_context);
264
265 auto bound_minus_one_id =
266 fuzzerutil::MaybeGetIntegerConstantFromValueAndType(
267 ir_context, bound - 1, index_instruction->type_id());
268
269 assert(bound_minus_one_id &&
270 "A constant of value bound - 1 and the same type as the index "
271 "must exist as a precondition.");
272
273 uint32_t bool_type_id = fuzzerutil::MaybeGetBoolType(ir_context);
274
275 assert(bool_type_id &&
276 "An OpTypeBool instruction must exist as a precondition.");
277
278 auto int_type_inst =
279 ir_context->get_def_use_mgr()->GetDef(index_instruction->type_id());
280
281 // Clamp the integer and add the corresponding instructions in the module
282 // if |add_clamping_instructions| is set.
283 auto instruction_to_insert_before =
284 FindInstruction(message_.instruction_to_insert_before(), ir_context);
285
286 // Compare the index with the bound via an instruction of the form:
287 // %fresh_ids.first = OpULessThanEqual %bool %int_id %bound_minus_one.
288 fuzzerutil::UpdateModuleIdBound(ir_context, fresh_ids.first());
289 instruction_to_insert_before->InsertBefore(MakeUnique<opt::Instruction>(
290 ir_context, SpvOpULessThanEqual, bool_type_id, fresh_ids.first(),
291 opt::Instruction::OperandList(
292 {{SPV_OPERAND_TYPE_ID, {index_instruction->result_id()}},
293 {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));
294
295 // Select the index if in-bounds, otherwise one less than the bound:
296 // %fresh_ids.second = OpSelect %int_type %fresh_ids.first %int_id
297 // %bound_minus_one
298 fuzzerutil::UpdateModuleIdBound(ir_context, fresh_ids.second());
299 instruction_to_insert_before->InsertBefore(MakeUnique<opt::Instruction>(
300 ir_context, SpvOpSelect, int_type_inst->result_id(),
301 fresh_ids.second(),
302 opt::Instruction::OperandList(
303 {{SPV_OPERAND_TYPE_ID, {fresh_ids.first()}},
304 {SPV_OPERAND_TYPE_ID, {index_instruction->result_id()}},
305 {SPV_OPERAND_TYPE_ID, {bound_minus_one_id}}})));
306
307 new_index_id = fresh_ids.second();
308
309 index_value = 0;
310 }
311
312 // Add the correct index id to the operands.
313 operands.push_back({SPV_OPERAND_TYPE_ID, {new_index_id}});
314
315 // Walk to the next type in the composite object using this index.
316 subobject_type_id = fuzzerutil::WalkOneCompositeTypeIndex(
317 ir_context, subobject_type_id, index_value);
318 }
319 // The access chain's result type is a pointer to the composite component
320 // that was reached after following all indices. The storage class is that
321 // of the original pointer.
322 uint32_t result_type = fuzzerutil::MaybeGetPointerType(
323 ir_context, subobject_type_id,
324 static_cast<SpvStorageClass>(pointer_type->GetSingleWordInOperand(0)));
325
326 // Add the access chain instruction to the module, and update the module's
327 // id bound.
328 fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
329 FindInstruction(message_.instruction_to_insert_before(), ir_context)
330 ->InsertBefore(MakeUnique<opt::Instruction>(
331 ir_context, SpvOpAccessChain, result_type, message_.fresh_id(),
332 operands));
333
334 // Conservatively invalidate all analyses.
335 ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
336
337 // If the base pointer's pointee value was irrelevant, the same is true of
338 // the pointee value of the result of this access chain.
339 if (transformation_context->GetFactManager()->PointeeValueIsIrrelevant(
340 message_.pointer_id())) {
341 transformation_context->GetFactManager()->AddFactValueOfPointeeIsIrrelevant(
342 message_.fresh_id());
343 }
344 }
345
ToMessage() const346 protobufs::Transformation TransformationAccessChain::ToMessage() const {
347 protobufs::Transformation result;
348 *result.mutable_access_chain() = message_;
349 return result;
350 }
351
GetIndexValue(opt::IRContext * ir_context,uint32_t index_id,uint32_t object_type_id) const352 std::pair<bool, uint32_t> TransformationAccessChain::GetIndexValue(
353 opt::IRContext* ir_context, uint32_t index_id,
354 uint32_t object_type_id) const {
355 if (!ValidIndexToComposite(ir_context, index_id, object_type_id)) {
356 return {false, 0};
357 }
358 auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
359
360 uint32_t bound = fuzzerutil::GetBoundForCompositeIndex(
361 *ir_context->get_def_use_mgr()->GetDef(object_type_id), ir_context);
362
363 // The index must be a constant
364 if (!spvOpcodeIsConstant(index_instruction->opcode())) {
365 return {false, 0};
366 }
367
368 // The index must be in bounds.
369 uint32_t value = index_instruction->GetSingleWordInOperand(0);
370
371 if (value >= bound) {
372 return {false, 0};
373 }
374
375 return {true, value};
376 }
377
ValidIndexToComposite(opt::IRContext * ir_context,uint32_t index_id,uint32_t object_type_id)378 bool TransformationAccessChain::ValidIndexToComposite(
379 opt::IRContext* ir_context, uint32_t index_id, uint32_t object_type_id) {
380 auto object_type_def = ir_context->get_def_use_mgr()->GetDef(object_type_id);
381 // The object being indexed must be a composite.
382 if (!spvOpcodeIsComposite(object_type_def->opcode())) {
383 return false;
384 }
385
386 // Get the defining instruction of the index.
387 auto index_instruction = ir_context->get_def_use_mgr()->GetDef(index_id);
388 if (!index_instruction) {
389 return false;
390 }
391
392 // The index type must be 32-bit integer.
393 auto index_type =
394 ir_context->get_def_use_mgr()->GetDef(index_instruction->type_id());
395 if (index_type->opcode() != SpvOpTypeInt ||
396 index_type->GetSingleWordInOperand(0) != 32) {
397 return false;
398 }
399
400 // If the object being traversed is a struct, the id must correspond to an
401 // in-bound constant.
402 if (object_type_def->opcode() == SpvOpTypeStruct) {
403 if (!spvOpcodeIsConstant(index_instruction->opcode())) {
404 return false;
405 }
406 }
407 return true;
408 }
409
GetFreshIds() const410 std::unordered_set<uint32_t> TransformationAccessChain::GetFreshIds() const {
411 std::unordered_set<uint32_t> result = {message_.fresh_id()};
412 for (auto& fresh_ids_for_clamping : message_.fresh_ids_for_clamping()) {
413 result.insert(fresh_ids_for_clamping.first());
414 result.insert(fresh_ids_for_clamping.second());
415 }
416 return result;
417 }
418
419 } // namespace fuzz
420 } // namespace spvtools
421