| // Copyright (c) 2020 Google LLC |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "source/fuzz/fuzzer_pass_add_function_calls.h" |
| |
| #include "source/fuzz/call_graph.h" |
| #include "source/fuzz/fuzzer_util.h" |
| #include "source/fuzz/transformation_add_global_variable.h" |
| #include "source/fuzz/transformation_add_local_variable.h" |
| #include "source/fuzz/transformation_function_call.h" |
| |
| namespace spvtools { |
| namespace fuzz { |
| |
| FuzzerPassAddFunctionCalls::FuzzerPassAddFunctionCalls( |
| opt::IRContext* ir_context, FactManager* fact_manager, |
| FuzzerContext* fuzzer_context, |
| protobufs::TransformationSequence* transformations) |
| : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {} |
| |
| FuzzerPassAddFunctionCalls::~FuzzerPassAddFunctionCalls() = default; |
| |
| void FuzzerPassAddFunctionCalls::Apply() { |
| MaybeAddTransformationBeforeEachInstruction( |
| [this](opt::Function* function, opt::BasicBlock* block, |
| opt::BasicBlock::iterator inst_it, |
| const protobufs::InstructionDescriptor& instruction_descriptor) |
| -> void { |
| // Check whether it is legitimate to insert a function call before the |
| // instruction. |
| if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(SpvOpFunctionCall, |
| inst_it)) { |
| return; |
| } |
| |
| // Randomly decide whether to try inserting a function call here. |
| if (!GetFuzzerContext()->ChoosePercentage( |
| GetFuzzerContext()->GetChanceOfCallingFunction())) { |
| return; |
| } |
| |
| // Compute the module's call graph - we don't cache it since it may |
| // change each time we apply a transformation. If this proves to be |
| // a bottleneck the call graph data structure could be made updatable. |
| CallGraph call_graph(GetIRContext()); |
| |
| // Gather all the non-entry point functions different from this |
| // function. It is important to ignore entry points as a function |
| // cannot be an entry point and the target of an OpFunctionCall |
| // instruction. We ignore this function to avoid direct recursion. |
| std::vector<opt::Function*> candidate_functions; |
| for (auto& other_function : *GetIRContext()->module()) { |
| if (&other_function != function && |
| !TransformationFunctionCall::FunctionIsEntryPoint( |
| GetIRContext(), other_function.result_id())) { |
| candidate_functions.push_back(&other_function); |
| } |
| } |
| |
| // Choose a function to call, at random, by considering candidate |
| // functions until a suitable one is found. |
| opt::Function* chosen_function = nullptr; |
| while (!candidate_functions.empty()) { |
| opt::Function* candidate_function = |
| GetFuzzerContext()->RemoveAtRandomIndex(&candidate_functions); |
| if (!GetFactManager()->BlockIsDead(block->id()) && |
| !GetFactManager()->FunctionIsLivesafe( |
| candidate_function->result_id())) { |
| // Unless in a dead block, only livesafe functions can be invoked |
| continue; |
| } |
| if (call_graph.GetIndirectCallees(candidate_function->result_id()) |
| .count(function->result_id())) { |
| // Calling this function could lead to indirect recursion |
| continue; |
| } |
| chosen_function = candidate_function; |
| break; |
| } |
| |
| if (!chosen_function) { |
| // No suitable function was found to call. (This can happen, for |
| // instance, if the current function is the only function in the |
| // module.) |
| return; |
| } |
| |
| ApplyTransformation(TransformationFunctionCall( |
| GetFuzzerContext()->GetFreshId(), chosen_function->result_id(), |
| ChooseFunctionCallArguments(*chosen_function, function, block, |
| inst_it), |
| instruction_descriptor)); |
| }); |
| } |
| |
| std::map<uint32_t, std::vector<opt::Instruction*>> |
| FuzzerPassAddFunctionCalls::GetAvailableInstructionsSuitableForActualParameters( |
| opt::Function* function, opt::BasicBlock* block, |
| const opt::BasicBlock::iterator& inst_it) { |
| // Find all instructions in scope that could potentially be used as actual |
| // parameters. Weed out unsuitable pointer arguments immediately. |
| std::vector<opt::Instruction*> potentially_suitable_instructions = |
| FindAvailableInstructions( |
| function, block, inst_it, |
| [this, block](opt::IRContext* context, |
| opt::Instruction* inst) -> bool { |
| if (!inst->HasResultId() || !inst->type_id()) { |
| // An instruction needs a result id and type in order |
| // to be suitable as an actual parameter. |
| return false; |
| } |
| if (context->get_def_use_mgr()->GetDef(inst->type_id())->opcode() == |
| SpvOpTypePointer) { |
| switch (inst->opcode()) { |
| case SpvOpFunctionParameter: |
| case SpvOpVariable: |
| // Function parameters and variables are the only |
| // kinds of pointer that can be used as actual |
| // parameters. |
| break; |
| default: |
| return false; |
| } |
| if (!GetFactManager()->BlockIsDead(block->id()) && |
| !GetFactManager()->PointeeValueIsIrrelevant( |
| inst->result_id())) { |
| // We can only pass a pointer as an actual parameter |
| // if the pointee value for the pointer is irrelevant, |
| // or if the block from which we would make the |
| // function call is dead. |
| return false; |
| } |
| } |
| return true; |
| }); |
| |
| // Group all the instructions that are potentially viable as function actual |
| // parameters by their result types. |
| std::map<uint32_t, std::vector<opt::Instruction*>> result; |
| for (auto inst : potentially_suitable_instructions) { |
| if (result.count(inst->type_id()) == 0) { |
| // This is the first instruction of this type we have seen, so populate |
| // the map with an entry. |
| result.insert({inst->type_id(), {}}); |
| } |
| // Add the instruction to the sequence of instructions already associated |
| // with this type. |
| result.at(inst->type_id()).push_back(inst); |
| } |
| return result; |
| } |
| |
| std::vector<uint32_t> FuzzerPassAddFunctionCalls::ChooseFunctionCallArguments( |
| const opt::Function& callee, opt::Function* caller_function, |
| opt::BasicBlock* caller_block, |
| const opt::BasicBlock::iterator& caller_inst_it) { |
| auto type_to_available_instructions = |
| GetAvailableInstructionsSuitableForActualParameters( |
| caller_function, caller_block, caller_inst_it); |
| |
| opt::Instruction* function_type = GetIRContext()->get_def_use_mgr()->GetDef( |
| callee.DefInst().GetSingleWordInOperand(1)); |
| assert(function_type->opcode() == SpvOpTypeFunction && |
| "The function type does not have the expected opcode."); |
| std::vector<uint32_t> result; |
| for (uint32_t arg_index = 1; arg_index < function_type->NumInOperands(); |
| arg_index++) { |
| auto arg_type_id = |
| GetIRContext() |
| ->get_def_use_mgr() |
| ->GetDef(function_type->GetSingleWordInOperand(arg_index)) |
| ->result_id(); |
| if (type_to_available_instructions.count(arg_type_id)) { |
| std::vector<opt::Instruction*>& candidate_arguments = |
| type_to_available_instructions.at(arg_type_id); |
| // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3177) The value |
| // selected here is arbitrary. We should consider adding this |
| // information as a fact so that the passed parameter could be |
| // transformed/changed. |
| result.push_back(candidate_arguments[GetFuzzerContext()->RandomIndex( |
| candidate_arguments)] |
| ->result_id()); |
| } else { |
| // We don't have a suitable id in scope to pass, so we must make |
| // something up. |
| auto type_instruction = |
| GetIRContext()->get_def_use_mgr()->GetDef(arg_type_id); |
| |
| if (type_instruction->opcode() == SpvOpTypePointer) { |
| // In the case of a pointer, we make a new variable, at function |
| // or global scope depending on the storage class of the |
| // pointer. |
| |
| // Get a fresh id for the new variable. |
| uint32_t fresh_variable_id = GetFuzzerContext()->GetFreshId(); |
| |
| // The id of this variable is what we pass as the parameter to |
| // the call. |
| result.push_back(fresh_variable_id); |
| |
| // Now bring the variable into existence. |
| if (type_instruction->GetSingleWordInOperand(0) == |
| SpvStorageClassFunction) { |
| // Add a new zero-initialized local variable to the current |
| // function, noting that its pointee value is irrelevant. |
| ApplyTransformation(TransformationAddLocalVariable( |
| fresh_variable_id, arg_type_id, caller_function->result_id(), |
| FindOrCreateZeroConstant( |
| type_instruction->GetSingleWordInOperand(1)), |
| true)); |
| } else { |
| assert(type_instruction->GetSingleWordInOperand(0) == |
| SpvStorageClassPrivate && |
| "Only Function and Private storage classes are " |
| "supported at present."); |
| // Add a new zero-initialized global variable to the module, |
| // noting that its pointee value is irrelevant. |
| ApplyTransformation(TransformationAddGlobalVariable( |
| fresh_variable_id, arg_type_id, |
| FindOrCreateZeroConstant( |
| type_instruction->GetSingleWordInOperand(1)), |
| true)); |
| } |
| } else { |
| // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3177): We use |
| // constant zero for the parameter, but could consider adding a fact |
| // to allow further passes to obfuscate it. |
| result.push_back(FindOrCreateZeroConstant(arg_type_id)); |
| } |
| } |
| } |
| return result; |
| } |
| |
| } // namespace fuzz |
| } // namespace spvtools |