// Copyright (c) 2020 Can Boluk and contributors of the VTIL Project // All rights reserved. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are met: // // 1. Redistributions of source code must retain the above copyright notice, // this list of conditions and the following disclaimer. // 2. Redistributions in binary form must reproduce the above copyright // notice, this list of conditions and the following disclaimer in the // documentation and/or other materials provided with the distribution. // 3. Neither the name of VTIL Project nor the names of its contributors // may be used to endorse or promote products derived from this software // without specific prior written permission. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE // POSSIBILITY OF SUCH DAMAGE. // #include "pass_validation.hpp" namespace vtil::optimizer::validation { // Helper routine used to compare routine behaviour against expected behaviour. // bool verify_symbolic( const routine* rtn, const std::vector& parameters, const std::vector& action_log ) { auto action_it = action_log.begin(); auto action_end = action_log.end(); // Create the symbolic virtual machine. // lambda_vm vm = {}; // Use relaxed aliasing. // vm.memory_state.relaxed_aliasing = true; // Write default register state. // for ( auto& [k, v] : default_register_state ) vm.write_register( k, v ); // Write the parameters. // const call_convention& call_conv = rtn->routine_convention; auto rit = call_conv.param_registers.begin(); for ( auto [value, id] : zip( parameters, iindices ) ) { // If we did not reach the end of registers yet: // if ( rit != call_conv.param_registers.end() ) { vm.write_register( *rit++, value ); } // Otherwise, write into the stack. // else { // Calculate the surplus index. // size_t idx = id - call_conv.param_registers.size(); // Calculate the address on stack and write into it. // vm.write_memory_v( vm.read_register( REG_SP ) + ( idx * 8 ) + call_conv.shadow_space + 8, value ); } } // Write the return address, any random will work so let's // use a pointer off of our own stack. // const uint64_t return_address = ( uint64_t ) &vm; vm.write_memory_v( vm.read_register( REG_SP ), return_address ); // Declare current iterator. // il_const_iterator it = rtn->entry_point->begin(); // Instrument the virtual execution to verify actions: // bool success = true; vm.hooks.execute = [ & ] ( const instruction& ins ) { // If failed already, exit. // if ( !success ) return vm_exit_reason::unknown_instruction; // If hint is hit, skip. // if ( *ins.base == ins::vpinr ) return vm_exit_reason::none; if ( *ins.base == ins::vpinw ) return vm_exit_reason::none; // If a virtual branch is hit, exit the virtual machine so we can handle it. // if ( ins.base->is_branching_virt() ) return vm_exit_reason::unknown_instruction; // If branching to real location: // if ( ins.base->is_branching_real() ) { // If external call: // if ( ins.base == &ins::vxcall ) { // If was not expected, fail and exit the virtual machine. // if ( action_it == action_end || !std::get_if( &*action_it ) ) { logger::warning( "[Block: %llx] Unexpected call.", it.block->entry_vip ); success = false; return vm_exit_reason::unknown_instruction; } // Pop it off the stack. // const external_call& call = std::get( *action_it ); ++action_it; // Validate target. // auto target_call = ins.operands[ 0 ].is_immediate() ? symbolic::expression::reference{ ins.operands[ 0 ].imm().u64 } : vm.read_register( ins.operands[ 0 ].reg() ); if ( target_call->value.get() != call.address ) { logger::warning( "[Block: %llx] Unexpected callee, expected 0x%llx, got [%s].", it.block->entry_vip, call.address, *target_call ); success = false; return vm_exit_reason::unknown_instruction; } // Validate parameters. // const call_convention& call_conv = rtn->get_cconv( ins.vip ); auto pit = call_conv.param_registers.begin(); for ( auto [value, id] : zip( call.parameters, iindices ) ) { symbolic::expression::reference exp; // If we did not reach the end of registers yet: // if ( pit != call_conv.param_registers.end() ) { // Read from the register and increment iterator. // exp = vm.read_register( *pit ); pit++; } else { // Calculate the surplus index. // size_t idx = id - call_conv.param_registers.size(); // Calculate the address on stack and read from it. // exp = vm.read_memory( vm.read_register( REG_SP ) + ( idx * 8 ) + call_conv.shadow_space + 8, 8 ); } // Fail if value does not match. // if ( exp->value.get() != value ) { logger::warning( "[Block: %llx] Parameter %d does not match, expected 0x%llx, got [%s].", it.block->entry_vip, id, value, exp ); success = false; return vm_exit_reason::unknown_instruction; } } // Write the simulated return value. // for ( auto [value, target] : zip( call.fake_result, call_conv.retval_registers ) ) vm.write_register( target, value ); } // If we're exiting the virtual machine: // else if ( ins.base == &ins::vexit ) { // If was not expected, fail and exit the virtual machine. // if ( action_it == action_end || !std::get_if( &*action_it ) ) { logger::warning( "[Block: %llx] Unexpected exit.", it.block->entry_vip ); success = false; return vm_exit_reason::unknown_instruction; } // Pop it off the stack. // vm_exit exit = std::get( *action_it ); ++action_it; // Validate return address. // auto sreturn_address = ins.operands[ 0 ].is_immediate() ? symbolic::expression::reference{ ins.operands[ 0 ].imm().u64 } : vm.read_register( ins.operands[ 0 ].reg() ); if ( sreturn_address->value.get() != return_address ) { logger::warning( "[Block: %llx] Unexpected return address, expected 0x%llx, got [%s].", it.block->entry_vip, return_address, *sreturn_address ); success = false; return vm_exit_reason::unknown_instruction; } // Validate the register state / return value. // for ( auto& [reg, value] : exit.register_state ) { auto exp = vm.read_register( reg ); if ( exp->value.get() != value ) { logger::warning( "[Block: %llx] Return state %s does not match, expected 0x%llx, got [%s].", it.block->entry_vip, reg, value, exp ); success = false; return vm_exit_reason::unknown_instruction; } } } return vm_exit_reason::none; } // If none matches, redirect to original handler. // return vm.symbolic_vm::execute( ins ); }; vm.hooks.read_memory = [ & ] ( const symbolic::expression::reference& pointer, size_t sz ) { // If action log has a matching read memory on top of the stack: // if ( action_it != action_end && std::get_if( &*action_it ) ) { auto& mem = std::get( *action_it ); if ( pointer->value.get() == mem.address ) { // Write fake value to the state and pop the stack. // symbolic::expression value = { mem.fake_value, mem.size }; vm.symbolic_vm::write_memory_v( pointer, value ); ++action_it; } } return vm.symbolic_vm::read_memory( pointer, sz ); }; vm.hooks.write_memory = [ & ] ( const symbolic::expression::reference& pointer, deferred_value value, bitcnt_t size ) { // If action log has a matching write memory on top of the stack: // if ( action_it != action_end && std::get_if( &*action_it ) ) { auto& mem = std::get( *action_it ); if ( pointer->value.get() == mem.address ) { // Pop the stack and validate the value. // if ( value.get()->value.get() != mem.value ) { logger::warning( "[Block: %llx] Unexpected memory write into 0x%llx, expected 0x%llx, got [%s].", it.block->entry_vip, mem.address, mem.value, value.get() ); success = false; } ++action_it; } } return vm.symbolic_vm::write_memory( pointer, value, size ); }; // Begin the loop: // while ( true ) { // Run until it VM exits. // auto [lim, rsn] = vm.run( it ); // If failed, return. // if ( !success ) return false; // If we've reached the end of the virtual machine: // if ( lim.is_end() ) { // If we have a single continue destination (VXCALL), fix iterator and the stack, continue. // size_t num_continue_dst = lim.block->next.size(); if ( num_continue_dst == 1 ) { it = lim.block->next[ 0 ]->begin(); vm.write_register( REG_SP, vm.read_register( REG_SP ) + lim.block->sp_offset ); continue; } // If we've reached the end of the routine (VEXIT), signal success if all actions are complete, or fail. // else if ( num_continue_dst == 0 ) { return action_it == action_end; } unreachable(); } // If unhandled instruction is branching into virtual location: // if ( lim->base->is_branching_virt() ) { // Determine the destination. // operand dst = {}; if ( lim->base == &ins::js ) dst = *vm.read_register( lim->operands[ 0 ].reg() )->get() ? lim->operands[ 1 ] : lim->operands[ 2 ]; else if ( lim->base == &ins::jmp ) dst = lim->operands[ 0 ]; // If operand is an immediate, use as is: // basic_block* blk = nullptr; if ( dst.is_immediate() ) blk = rtn->find_block( dst.imm().u64 ); // Otherwise read VM context. // else if ( auto jmp_dst = vm.read_register( dst.reg() )->get() ) blk = rtn->find_block( *jmp_dst ); // If no valid destination, fail. // if ( !blk ) { logger::warning( "[Block: %llx] Invalid virtual jump [%s].", it.block->entry_vip, dst.is_immediate() ? dst.to_string() : vm.read_register( dst.reg() )->to_string() ); return false; } // Fix iterator and the stack, continue. // it = blk->begin(); vm.write_register( REG_SP, vm.read_register( REG_SP ) + lim.block->sp_offset ); continue; } logger::warning( "[Block: %llx] Failing execution at: %s.", it.block->entry_vip, lim->to_string() ); return false; } } };