35 for(
const auto &field_pair : fields)
40 field_pair.second.id() == ID_typecast &&
43 const auto zero_value =
51 exprt init_expr = field_pair.second;
52 const auto init_value =
59 log.
debug() <<
"Shadow memory: initialize field "
61 <<
" with initial value " <<
format(field_pair.second)
70 const typet &field_type)
85 return addresses.back().shadow;
94 arguments.size() == 3,
CPROVER_PREFIX "set_field requires 3 arguments");
97 exprt expr = arguments[0];
100 expr_type.
id() == ID_pointer,
101 "shadow memory requires a pointer expression",
104 exprt value = arguments[2];
108 id2string(field_name) +
" should exist");
120 log.
warning() <<
"Shadow memory: cannot set shadow memory of NULL"
126 const exprt &rhs = value;
128 std::optional<exprt> maybe_lhs =
132 if(maybe_lhs.has_value())
136 log.
warning() <<
"Shadow memory: mux size set_field: " << mux_size
141 log.
debug() <<
"Shadow memory: mux size set_field: " << mux_size
148 if(lhs.
type().
id() == ID_empty)
151 s <<
"Shadow memory: cannot set shadow memory via type void* for "
153 <<
". Insert a cast to the type that you want to access.";
161 const exprt casted_rhs =
166 const auto per_byte_rhs =
197 arguments.size() == 2,
CPROVER_PREFIX "get_field requires 2 arguments");
200 exprt expr = arguments[0];
203 expr_type.
id() == ID_pointer,
204 "shadow memory requires a pointer expression");
209 id2string(field_name) +
" should exist");
219 std::vector<std::pair<exprt, exprt>> rhs_conds_values;
229 rhs_conds_values.emplace_back(
234 for(
const auto &matched_object : value_set)
237 if(matched_object.id() != ID_object_descriptor)
239 log.
warning() <<
"Shadow memory: value set contains unknown for "
248 log.
warning() <<
"Shadow memory: value set contains integer_address for "
255 if(matched_object.type().get_bool(ID_C_is_failed_symbol))
257 log.
warning() <<
"Shadow memory: value set contains failed symbol for "
262 bool exact_match =
false;
270 field_init_expr.
type(),
279 rhs_conds_values.clear();
282 rhs_conds_values.insert(
283 rhs_conds_values.end(),
284 per_matched_object_conds_values.begin(),
285 per_matched_object_conds_values.end());
293 if(!rhs_conds_values.empty())
299 const size_t mux_size = rhs_conds_values.size() - 1;
303 log.
warning() <<
"Shadow memory: mux size get_field: " << mux_size
308 log.
debug() <<
"Shadow memory: mux size get_field: " << mux_size
363 (
id2string(symbol.
name).find(
"::return_value") == std::string::npos &&
367 if(
id2string(symbol.
name).find(
"__cs_") != std::string::npos)
395 log.
debug() <<
"Shadow memory: global memory "
413 symbol_name.find(
"::return_value") == std::string::npos)
416 symbol_name.find(
"malloc::") != std::string::npos &&
417 (symbol_name.find(
"malloc_size") != std::string::npos ||
418 symbol_name.find(
"malloc_res") != std::string::npos ||
419 symbol_name.find(
"record_malloc") != std::string::npos ||
420 symbol_name.find(
"record_may_leak") != std::string::npos))
425 symbol_name.find(
"__builtin_alloca::") != std::string::npos &&
426 (symbol_name.find(
"alloca_size") != std::string::npos ||
427 symbol_name.find(
"record_malloc") != std::string::npos ||
428 symbol_name.find(
"record_alloca") != std::string::npos ||
429 symbol_name.find(
"res") != std::string::npos))
433 if(symbol_name.find(
"__cs_") != std::string::npos)
438 log.
debug() <<
"Shadow memory: local memory "
451 log.
debug() <<
"Shadow memory: dynamic memory of type "
467 const auto &goto_program = goto_function.second.body;
470 if(!target->is_function_call())
474 const exprt &
function = code_function_call.function();
476 if(
function.
id() != ID_symbol)
503 return field_definitions;
513 code_function_call.
arguments().size() == 2,
516 " requires 2 arguments");
522 log.
debug() <<
"Shadow memory: declare " << (is_global ?
"global " :
"local ")
523 <<
"field " <<
id2string(field_name) <<
" of type "
528 "A shadow memory field must be of a bitvector type.");
533 "A shadow memory field must not be larger than 8 bits.");
537 fields[field_name] = expr;
Pre-defined bitvector types.
const bitvector_typet & to_bitvector_type(const typet &type)
Cast a typet to a bitvector_typet.
Abstract interface to eager or lazy GOTO models.
virtual const goto_functionst & get_goto_functions() const =0
Accessor to get a raw goto_functionst.
std::size_t get_width() const
goto_instruction_codet representation of a function call statement.
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
bool starts_with(const char *s) const
equivalent of as_string().starts_with(s)
Base class for all expressions.
std::vector< exprt > operandst
const source_locationt & source_location() const
bool is_zero() const
Return whether the expression is a constant representing 0.
typet & type()
Return the type of the expression.
function_mapt function_map
value_sett value_set
Uses level 1 names, and is used to do dereferencing.
Central data structure: state.
shadow_memory_statet shadow_memory
symbol_tablet symbol_table
contains symbols that are minted during symbolic execution, such as dynamically created objects etc.
symex_targett::sourcet source
const irep_idt & id() const
Class that provides messages with a built-in verbosity 'level'.
mstreamt & warning() const
const typet & follow(const typet &) const
Resolve type symbol to the type it points to.
bool lookup(const irep_idt &name, const symbolt *&symbol) const override
See documentation for namespace_baset::lookup().
The null pointer constant.
The shadow memory field definitions.
field_definitiont global_fields
Field definitions for global-scope fields.
field_definitiont local_fields
Field definitions for local-scope fields.
std::map< irep_idt, exprt > field_definitiont
A field definition mapping a field name to its initial value.
shadow_memory_field_definitionst fields
The available shadow memory field definitions.
std::map< irep_idt, std::vector< shadowed_addresst > > address_fields
const symbol_exprt & add_field(goto_symex_statet &state, const exprt &expr, const irep_idt &field_name, const typet &field_type)
Registers a shadow memory field for the given original memory.
void symex_get_field(goto_symex_statet &state, const exprt &lhs, const exprt::operandst &arguments)
Symbolically executes a __CPROVER_get_field call.
static void convert_field_declaration(const code_function_callt &code_function_call, shadow_memory_field_definitionst::field_definitiont &fields, bool is_global, message_handlert &message_handler)
Converts a field declaration.
void symex_field_dynamic_init(goto_symex_statet &state, const exprt &expr, const side_effect_exprt &code)
Initialize global-scope shadow memory for dynamically allocated memory.
void symex_field_static_init(goto_symex_statet &state, const ssa_exprt &lhs)
Initialize global-scope shadow memory for global/static variables.
const std::function< void(goto_symex_statet &, const exprt &, const exprt)> symex_assign
void symex_field_static_init_string_constant(goto_symex_statet &state, const ssa_exprt &expr, const exprt &rhs)
Initialize global-scope shadow memory for string constants.
static shadow_memory_field_definitionst gather_field_declarations(const abstract_goto_modelt &goto_model, message_handlert &message_handler)
Gathers the available shadow memory field definitions (__CPROVER_field_decl calls) from the goto mode...
void symex_field_local_init(goto_symex_statet &state, const ssa_exprt &expr)
Initialize local-scope shadow memory for local variables and parameters.
void initialize_shadow_memory(goto_symex_statet &state, exprt expr, const shadow_memory_field_definitionst::field_definitiont &fields)
Allocates and initializes a shadow memory field for the given original memory.
void symex_set_field(goto_symex_statet &state, const exprt::operandst &arguments)
Symbolically executes a __CPROVER_set_field call.
An expression containing a side effect.
Expression providing an SSA-renamed symbol of expressions.
const exprt & get_original_expr() const
void value(const irep_idt &)
Expression to hold a symbol (variable)
const irep_idt & get_identifier() const
class symbol_exprt symbol_expr() const
Produces a symbol_exprt for a symbol.
typet type
Type of symbol.
irep_idt name
The unique identifier.
The Boolean constant true.
static exprt conditional_cast(const exprt &expr, const typet &type)
The type of an expression, extends irept.
Thrown when we encounter an instruction, parameters to an instruction etc.
std::vector< exprt > get_value_set(exprt expr, const namespacet &ns) const
Gets values pointed to by expr, including following dereference operators (i.e.
std::optional< exprt > zero_initializer(const typet &type, const source_locationt &source_location, const namespacet &ns)
Create the equivalent of zero for type type.
std::optional< exprt > expr_initializer(const typet &type, const source_locationt &source_location, const namespacet &ns, const exprt &init_byte_expr)
Create a value for type type, with all subtype bytes initialized to the given value.
Expression Initialization.
symbolt & get_fresh_aux_symbol(const typet &type, const std::string &name_prefix, const std::string &basename_prefix, const source_locationt &source_location, const irep_idt &symbol_mode, const namespacet &ns, symbol_table_baset &symbol_table)
Installs a fresh-named symbol with respect to the given namespace ns with the requested name pattern ...
Fresh auxiliary symbol creation.
const code_function_callt & to_code_function_call(const goto_instruction_codet &code)
#define forall_goto_program_instructions(it, program)
const std::string & id2string(const irep_idt &d)
std::string from_expr(const namespacet &ns, const irep_idt &identifier, const exprt &expr)
std::string from_type(const namespacet &ns, const irep_idt &identifier, const typet &type)
API to expression classes for Pointers.
const pointer_typet & to_pointer_type(const typet &type)
Cast a typet to a pointer_typet.
const object_descriptor_exprt & to_object_descriptor_expr(const exprt &expr)
Cast an exprt to an object_descriptor_exprt.
const address_of_exprt & to_address_of_expr(const exprt &expr)
Cast an exprt to an address_of_exprt.
Symex Shadow Memory Instrumentation.
#define SHADOW_MEMORY_GLOBAL_SCOPE
#define SHADOW_MEMORY_LOCAL_SCOPE
#define SHADOW_MEMORY_PREFIX
#define SHADOW_MEMORY_FIELD_DECL
exprt build_if_else_expr(const std::vector< std::pair< exprt, exprt >> &conds_values)
Build an if-then-else chain from a vector containing pairs of expressions.
void replace_invalid_object_by_null(exprt &expr)
Replace an invalid object by a null pointer.
void shadow_memory_log_value_set_match(const namespacet &ns, const messaget &log, const exprt &address, const exprt &expr)
Logs a successful match between an address and a value within the value set.
exprt deref_expr(const exprt &expr)
Wraps a given expression into a dereference_exprt unless it is an address_of_exprt in which case it j...
bool contains_null_or_invalid(const std::vector< exprt > &value_set, const exprt &address)
Given a pointer expression check to see if it can be a null pointer or an invalid object within value...
bool check_value_set_contains_only_null_ptr(const namespacet &ns, const messaget &log, const std::vector< exprt > &value_set, const exprt &expr)
Checks if value_set contains only a NULL pointer expression of the same type of expr.
void shadow_memory_log_set_field(const namespacet &ns, const messaget &log, const irep_idt &field_name, const exprt &expr, const exprt &value)
Logs setting a value to a given shadow field.
const typet & get_field_init_type(const irep_idt &field_name, const goto_symex_statet &state)
Retrieves the type of the shadow memory by returning the type of the shadow memory initializer value.
const exprt & get_field_init_expr(const irep_idt &field_name, const goto_symex_statet &state)
Retrieve the expression that a field was initialised with within a given symex state.
std::vector< std::pair< exprt, exprt > > get_shadow_dereference_candidates(const namespacet &ns, const messaget &log, const exprt &matched_object, const std::vector< shadow_memory_statet::shadowed_addresst > &addresses, const typet &field_type, const exprt &expr, const typet &lhs_type, bool &exact_match)
Get a list of (condition, value) pairs for a certain pointer from the shadow memory,...
void shadow_memory_log_get_field(const namespacet &ns, const messaget &log, const irep_idt &field_name, const exprt &expr)
Logs getting a value corresponding to a shadow memory field.
irep_idt extract_field_name(const exprt &string_expr)
Extracts the field name identifier from a string expression, e.g.
void shadow_memory_log_value_set(const namespacet &ns, const messaget &log, const std::vector< exprt > &value_set)
Logs the retrieval of the value associated with a given shadow memory field.
void clean_pointer_expr(exprt &expr, const typet &type)
Clean the given pointer expression so that it has the right shape for being used for identifying shad...
void shadow_memory_log_text_and_expr(const namespacet &ns, const messaget &log, const char *text, const exprt &expr)
Generic logging function that will log depending on the configured verbosity.
std::optional< exprt > get_shadow_memory(const exprt &expr, const std::vector< exprt > &value_set, const std::vector< shadow_memory_statet::shadowed_addresst > &addresses, const namespacet &ns, const messaget &log, size_t &mux_size)
Get shadow memory values for a given expression within a specified value set.
Symex Shadow Memory Instrumentation Utilities.
#define CHECK_RETURN(CONDITION)
#define DATA_INVARIANT(CONDITION, REASON)
This condition should be used to document that assumptions that are made on goto_functions,...
#define DATA_INVARIANT_WITH_DIAGNOSTICS(CONDITION, REASON,...)
ssa_exprt remove_level_2(ssa_exprt ssa)
#define INITIALIZE_FUNCTION
const symbol_exprt & to_symbol_expr(const exprt &expr)
Cast an exprt to a symbol_exprt.
const typecast_exprt & to_typecast_expr(const exprt &expr)
Cast an exprt to a typecast_exprt.
const index_exprt & to_index_expr(const exprt &expr)
Cast an exprt to an index_exprt.
bool can_cast_type< bitvector_typet >(const typet &type)
Check whether a reference to a typet is a bitvector_typet.
const string_constantt & to_string_constant(const exprt &expr)
goto_programt::const_targett pc