Struct cwe_checker_lib::analysis::pointer_inference::State

pub struct State {
    pub memory: AbstractObjectList,
    pub stack_id: AbstractIdentifier,
    /* private fields */
}

Contains all information known about the state of a program at a specific point of time.

Fields

memory: AbstractObjectList

The list of all known memory objects.

stack_id: AbstractIdentifier

The abstract identifier of the current stack frame. It points to the base of the stack frame, i.e. only negative offsets point into the current stack frame.

Implementations

impl State

pub fn get_register(&self, variable: &Variable) -> Data

Get the value of a register or Top() if no value is known.

pub fn set_register(&mut self, variable: &Variable, value: Data)

Set the value of a register.

pub fn handle_register_assign( &mut self, target: &Variable, expression: &Expression )

Evaluate expression on the given state and write the result to the target register.

pub fn store_value( &mut self, address: &Data, value: &Data, global_memory: &RuntimeMemoryImage ) -> Result<(), Error>

Store value at the given address.

pub fn write_to_address( &mut self, address: &Expression, value: &Data, global_memory: &RuntimeMemoryImage ) -> Result<(), Error>

Write a value to the address one gets when evaluating the address expression.

pub fn handle_store( &mut self, address: &Expression, value: &Expression, global_memory: &RuntimeMemoryImage ) -> Result<(), Error>

Evaluate the store instruction, given by its address and value expressions, and modify the state accordingly.

pub fn load_value( &self, address: &Expression, size: ByteSize, global_memory: &RuntimeMemoryImage ) -> Result<Data, Error>

Evaluate the given address expression and return the data read from that address on success.

pub fn load_value_from_address( &self, address: &Data, size: ByteSize, global_memory: &RuntimeMemoryImage ) -> Result<Data, Error>

Load the value at the given address from the state and return the data read on success. If the address contains more than one possible pointer target the results are merged for all possible pointer targets.

pub fn handle_load( &mut self, var: &Variable, address: &Expression, global_memory: &RuntimeMemoryImage ) -> Result<(), Error>

Handle a load instruction by assigning the value loaded from the address given by the address expression to var.

pub fn eval(&self, expression: &Expression) -> Data

Evaluate the value of an expression in the current state.

pub fn eval_parameter_arg( &self, parameter: &Arg, global_memory: &RuntimeMemoryImage ) -> Result<Data, Error>

Evaluate the value of a parameter of an extern symbol for the given state.

pub fn eval_abstract_location( &self, location: &AbstractLocation, global_memory: &RuntimeMemoryImage ) -> Data

Evaluate the value of the given abstract location on the current state. If the actual value cannot be determined (e.g. if an intermediate pointer returns Top) then a Top value is returned.

pub fn check_def_for_null_dereferences( &mut self, def: &Term<Def> ) -> Result<bool, Error>

Check whether the given def could result in a memory access through a NULL pointer.

If no NULL pointer dereference is detected then Ok(false) is returned. If a NULL pointer dereference is detected, try to specialize the state so that address_expr cannot result in a NULL pointer anymore. If that succeeds, Ok(true) is returned. If that would result in an unsatisfiable state, an error is returned.

impl State

pub fn add_directly_reachable_ids_to_id_set( &self, ids: BTreeSet<AbstractIdentifier> ) -> BTreeSet<AbstractIdentifier>

Search (recursively) through all memory objects referenced by the given IDs and add all IDs reachable through concrete pointers contained in them to the set of IDs.

This uses an underapproximation of the referenced IDs of a memory object, i.e. IDs may be missing if the analysis lost track of the corresponding pointer.

pub fn add_recursively_referenced_ids_to_id_set( &self, ids: BTreeSet<AbstractIdentifier> ) -> BTreeSet<AbstractIdentifier>

Search (recursively) through all memory objects referenced by the given IDs and add all IDs contained in them to the set of IDs.

This uses an overapproximation of the referenced IDs of a memory object, i.e. for a memory object it may add IDs as possible references where the corresponding reference is not longer present in the memory object.

pub fn add_param_object_from_callee( &mut self, param_object: AbstractObject, param_value_at_call: &Data ) -> Result<(), Error>

Add the given param_object from the callee state to self (where self represents the state after returning from the callee).

param_value_at_call is the value that the parameter had at the callsite. It is assumed that all IDs contained in the param_object are already replaced with values relative to the caller.

If the param_object corresponds to a unique object in self then the contents of that object are overwritten with those of param_object. Else the contents are only merged with all possible caller objects, since the exact object that corresponds to the callee object is unknown.

pub fn get_id_to_unified_ids_replacement_map( &self, location_to_data_map: &BTreeMap<AbstractIdentifier, Data> ) -> BTreeMap<AbstractIdentifier, Data>

Create an ID renaming map that maps IDs in self to the values representing them after unifying and renaming non-parameter objects in self in preparation of returning to a caller.

pub fn replace_ids_to_non_parameter_objects( &mut self, location_to_data_map: &BTreeMap<AbstractIdentifier, Data> )

Replace all IDs pointing to non-parameter objects.

• IDs contained in the values of the location to data map are replaced by the corresponding key (with adjusted offset). But the Top flag is also set, because the pointers may point to other objects.
• All other non-parameter IDs are replaced with Top.

pub fn insert_pointers_to_unified_objects( &mut self, location_to_data_map: &BTreeMap<AbstractIdentifier, Data>, call_tid: &Tid )

Explicitly insert pointers to unified objects at the locations specified by their abstract location.

Note that these are the only locations where we (by definition) know that the pointer is unique, i.e. we do not have to set a Top flag. However, we still have to add targets to parameter objects, absolute values or the Top flag to the pointer if the original pointer value contained them, because these targets were not merged to the unified object.

pub fn generate_target_objects_for_new_locations( &self, location_to_data_map: &BTreeMap<AbstractIdentifier, Data> ) -> BTreeMap<AbstractIdentifier, AbstractObject>

Merge the target objects that are non-parameter objects for the given location to data mapping. Return the results as a location to memory object map.

This function is a step in the process of unifying callee-originating memory objects on a return instruction. The memory objects are also marked as unique, because they will represent a unique object in the caller.

pub fn filter_location_to_pointer_data_map( &self, location_to_data_map: &mut BTreeMap<AbstractIdentifier, Data> )

Filter out those locations from the location to pointer data map whose non-parameter object targets intersect with any of the other locations.

Note that this does not filter out locations whose targets contain the Top flag, despite the fact that these locations theoretically may point to the same non-parameter object. I.e. we trade soundness in the general case for exactness in the common case here.

pub fn map_abstract_locations_to_pointer_data( &self, call_tid: &Tid ) -> BTreeMap<AbstractIdentifier, Data>

Generate a map from abstract locations pointing to non-parameter memory objects to the data represented by the abstract location in the current state.

The abstract locations get different TIDs depending on the root of the location:

• If the root is a return register, then the TID is given by the provided call_tid.
• If the root is a parameter memory object, then the TID is given by appending the suffix _param to the call_tid. Since parameter and return register can overlap, the abstract IDs would overlap if one would use the same TID in both cases.

For return register based location this function also generates nested abstract locations.

This function assumes that State::minimize_before_return_instruction has been called on self beforehand.

impl State

pub fn specialize_by_expression_result( &mut self, expression: &Expression, result: Data ) -> Result<(), Error>

Try to restrict the input variables of expression on self so that expression only evaluates to values represented by the given result.

If expression cannot evaluate to any value represented by self, return an error.

This function may restrict to upper bounds of possible values if the restriction cannot be made exact, i.e. after calling this function the state may still contain values for which expression does not evaluate to values represented by result.

impl State

pub fn new( stack_register: &Variable, function_tid: Tid, global_addresses: BTreeSet<u64> ) -> State

Create a new state that contains one memory object corresponding to the stack and one memory object corresponding to global memory.

The stack offset will be set to zero.

pub fn from_fn_sig( fn_sig: &FunctionSignature, stack_register: &Variable, function_tid: Tid ) -> State

Create a new state from a function signature.

The created state contains one memory object for the stack frame of the function and one memory object for each parameter that is dereferenced by the function (according to the function signature).

pub fn set_mips_link_register( &mut self, callee_tid: &Tid, generic_pointer_size: ByteSize ) -> Result<(), Error>

Set the MIPS link register t9 to the address of the callee TID.

According to the System V ABI for MIPS the caller has to save the callee address in register t9 on a function call to position-independent code. In MIPS this value is used to compute the addresses of some global variables, since MIPS does not use program-counter-relative access instructions like other instruction set architectures do.

This function sets t9 to the correct value. Returns an error if the callee address could not be parsed (e.g. for UNKNOWN addresses).

pub fn minimize_before_return_instruction( &mut self, fn_sig: &FunctionSignature, cconv: &CallingConvention )

Remove all objects and registers from the state whose contents will not be used after returning to a caller.

All remaining memory objects after the minimization are reachable in the caller either via a parameter object that may have been mutated in the call or via a return register.

pub fn merge_mem_objects_with_unique_abstract_location( &mut self, call_tid: &Tid )

Try to determine unique pointer locations for non-parameter memory objects. When successful, merge all referenced non-parameter objects for that location and replace the pointer with a pointer to the merged object.

The merged objects get new abstract IDs generated from the call TID and their abstract location in the state.

This function leaves pointers to parameter objects as is, while pointers to non-parameter objects, that were not merged (e.g. due to pointers being not unique) are replaced with Top.

pub fn clear_non_callee_saved_register( &mut self, callee_saved_register: &[Variable] )

Clear all non-callee-saved registers from the state. This automatically also removes all virtual registers. The parameter is a list of callee-saved register names.

pub fn clear_stack_parameter( &mut self, extern_call: &ExternSymbol, global_memory: &RuntimeMemoryImage ) -> Result<(), Error>

Mark those parameter values of an extern function call, that are passed on the stack, as unknown data (since the function may modify them).

pub fn remove_unreferenced_objects(&mut self)

Remove all objects that cannot longer be reached by any known pointer. This does not remove objects, where some caller may still know a pointer to the object.

The function uses an underapproximation of all possible pointer targets contained in a memory object. This keeps the number of tracked objects reasonably small.

pub fn remove_non_callee_saved_register(&mut self, cconv: &CallingConvention)

Remove all knowledge about the contents of non-callee-saved registers from the state.

pub fn get_fn_tid(&self) -> &Tid

Get the Tid of the function that this state belongs to.

pub fn get_global_mem_id(&self) -> AbstractIdentifier

Get the abstract ID of the global memory object corresponding to this function.

impl State

pub fn to_json_compact(&self) -> Value

Get a more compact json-representation of the state. Intended for pretty printing, not useable for serialization/deserialization.

Trait Implementations

impl AbstractDomain for State

fn merge(&self, other: &Self) -> Self

Merge two states

fn is_top(&self) -> bool

A state has no Top element

fn merge_with(&mut self, other: &Self) -> &mut Self

Returns an upper bound (with respect to the partial order on the domain) for the two inputs self and other.

impl Clone for State

fn clone(&self) -> State

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for State

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for State

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for State

fn eq(&self, other: &State) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for State

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for State

impl StructuralEq for State

impl StructuralPartialEq for State