Infer and propagate data-types. More...

#include <coreaction.hh>

Inheritance diagram for ActionInferTypes:

Public Member Functions
	ActionInferTypes (const string &g)
	Constructor.

virtual void	reset (Funcdata &data)
	Reset the Action for a new function. More...

virtual Action *	clone (const ActionGroupList &grouplist) const
	Clone the Action. More...

virtual int4	apply (Funcdata &data)
	Make a single attempt to apply this Action. More...

Public Member Functions inherited from Action
	Action (uint4 f, const string &nm, const string &g)
	Base constructor for an Action. More...

virtual	~Action (void)
	Destructor.

virtual void	printStatistics (ostream &s) const
	Dump statistics to stream. More...

int4	perform (Funcdata &data)
	Perform this action (if necessary) More...

bool	setBreakPoint (uint4 tp, const string &specify)
	Set a breakpoint on this action. More...

virtual void	clearBreakPoints (void)
	Clear all breakpoints set on this Action.

bool	setWarning (bool val, const string &specify)
	Set a warning on this action. More...

bool	disableRule (const string &specify)
	Disable a specific Rule within this. More...

bool	enableRule (const string &specify)
	Enable a specific Rule within this. More...

const string &	getName (void) const
	Get the Action's name.

const string &	getGroup (void) const
	Get the Action's group.

uint4	getStatus (void) const
	Get the current status of this Action.

uint4	getNumTests (void)
	Get the number of times apply() was invoked.

uint4	getNumApply (void)

virtual void	resetStats (void)
	Reset all the counts to zero. More...

virtual int4	print (ostream &s, int4 num, int4 depth) const
	Print a description of this Action to stream. More...

virtual void	printState (ostream &s) const
	Print status to stream. More...

virtual void	saveXml (ostream &s) const
	Save specifics of this action to stream.

virtual void	restoreXml (const Element el, Funcdata fd)
	Load specifics of action from XML.

virtual Action *	getSubAction (const string &specify)
	Retrieve a specific sub-action by name. More...

virtual Rule *	getSubRule (const string &specify)
	Retrieve a specific sub-rule by name. More...

Static Private Member Functions
static void	buildLocaltypes (Funcdata &data)
	Assign initial data-type based on local info. More...

static bool	writeBack (Funcdata &data)
	Commit the final propagated data-types to Varnodes. More...

static int4	propagateAddPointer (PcodeOp *op, int4 slot)
	Test if edge is pointer plus a constant. More...

static Datatype *	propagateAddIn2Out (TypeFactory typegrp, PcodeOp op, int4 inslot)
	Propagate a pointer data-type through an ADD operation. More...

static bool	propagateGoodEdge (PcodeOp op, int4 inslot, int4 outslot, Varnode invn)
	Determine if propagation should happen along the given edge. More...

static bool	propagateTypeEdge (TypeFactory typegrp, PcodeOp op, int4 inslot, int4 outslot)
	Attempt to propagate a data-type across a single PcodeOp edge. More...

static void	propagateOneType (TypeFactory typegrp, Varnode vn)
	Propagate a data-type starting from one Varnode across the function. More...

static void	propagateRef (Funcdata &data, Varnode *vn, const Address &addr)
	Try to propagate a pointer data-type to known aliases. More...

static void	propagateSpacebaseRef (Funcdata &data, Varnode *spcvn)
	Search for pointers and propagate its data-type to known aliases. More...

static PcodeOp *	canonicalReturnOp (Funcdata &data)

static void	propagateAcrossReturns (Funcdata &data)
	Give data-types a chance to propagate between CPUI_RETURN operations. More...

Private Attributes
int4	localcount
	Number of passes performed for this function.

Additional Inherited Members
Public Types inherited from Action
enum	ruleflags { rule_repeatapply = 4, rule_onceperfunc = 8, rule_oneactperfunc = 16, rule_debug = 32, rule_warnings_on = 64, rule_warnings_given = 128 }
	Boolean behavior properties governing this particular Action. More...

enum	statusflags { status_start =1, status_breakstarthit =2, status_repeat =4, status_mid =8, status_end =16, status_actionbreak =32 }
	Boolean properties describing the status of an action. More...

enum	breakflags { break_start = 1, tmpbreak_start = 2, break_action = 4, tmpbreak_action = 8 }
	Break points associated with an Action. More...

Protected Member Functions inherited from Action
void	issueWarning (Architecture *glb)
	Warn that this Action has applied. More...

bool	checkStartBreak (void)
	Check start breakpoint. More...

bool	checkActionBreak (void)
	Check action breakpoint. More...

void	turnOnWarnings (void)
	Enable warnings for this Action.

void	turnOffWarnings (void)
	Disable warnings for this Action.

Protected Attributes inherited from Action
int4	lcount
	Changes not including last call to apply()

int4	count
	Number of changes made by this action so far.

uint4	status
	Current status.

uint4	breakpoint
	Breakpoint properties.

uint4	flags
	Behavior properties.

uint4	count_tests
	Number of times apply() has been called.

uint4	count_apply
	Number of times apply() made changes.

string	name
	Name of the action.

string	basegroup
	Base group this action belongs to.

Detailed Description

Infer and propagate data-types.

Atomic data-types are ordered from most specified to least specified. This is extended rescursively to an ordering on composite data-types via Datatype::typeOrder(). A local data-type is calculated for each Varnode by looking at the data-types expected by the PcodeOps it is directly involved in (as input or output). Every Varnode has 1 chance to propagate its information throughout the graph along COPY,LOAD,STORE,ADD,MULTIEQUAL,and INDIRECT edges. The propagation is done with a depth first search along propagating edges. If the propagated data-type is the same, less than, or if the varnode had been propagated through already, that branch is trimmed. Every edge can theoretically get traversed once, i.e. the search allows the type to propagate through a looping edge, but immediately truncates. This is probably quadratic in the worst case, if each Varnode has a higher type and propagates it to the entire graph. But it is linear in practice, because there are generally only two or three levels of type, so only one or two Varnodes are likely to propagate widely within a component, and the others get truncated immediately. An initial sort on the data-type level of the Varnodes, so that the highest-level types are propagated first, would probably fix the worst-case, but this seems unnecessary. Complications: TYPE_SPACEBASE is a problem because we have to make sure that it doesn't propagate. Also, offsets off of pointers to TYPE_SPACEBASE look up the data-type in the local map. Then ActionRestructure uses data-type information recovered by this algorithm to reconstruct the local map. This causes a feedback loop which allows type information recovered about mapped Varnodes to be propagated to pointer Varnodes which point to the mapped object. Unfortunately under rare circumstances, this feedback-loop does not converge for some reason. Rather than hunt this down, I've put an arbitrary iteration limit on the data-type propagation algorithm, which reports a warning if the limit is reached and then aborts additional propagation so that decompiling can terminate.

Member Function Documentation

int4 ActionInferTypes::apply ( Funcdata & data )

virtual

Make a single attempt to apply this Action.

This is the main entry point for applying changes to a function that are specific to this Action. The method can inspect whatever it wants to decide if the Action does or does not apply. Changes are indicated by incrementing the count field.

Parameters

data	is the function to inspect/modify

Returns: 0 for a complete application, -1 for a partial completion (due to breakpoint)

Implements Action.

References ScopeLocal::applyTypeRecommendations(), Funcdata::beginLoc(), Funcdata::endLoc(), Funcdata::findSpacebaseInput(), Funcdata::getArch(), Funcdata::getScopeLocal(), ScopeLocal::getSpaceId(), Varnode::hasNoDescend(), Varnode::isAnnotation(), Funcdata::isTypeRecoveryOn(), Varnode::isWritten(), Architecture::types, and Funcdata::warningHeader().

void ActionInferTypes::buildLocaltypes ( Funcdata & data )

staticprivate

Assign initial data-type based on local info.

Collect local data-type information on each Varnode inferred from the PcodeOps that read and write to it.

Parameters

data	is the function being analyzed

References Funcdata::beginLoc(), Funcdata::endLoc(), Funcdata::getArch(), Varnode::getLocalType(), Varnode::hasNoDescend(), Varnode::isAnnotation(), Varnode::isWritten(), and Varnode::setTempType().

PcodeOp * ActionInferTypes::canonicalReturnOp ( Funcdata & data )

staticprivate

Return the CPUI_RETURN op with the most specialized data-type, which is not dead and is not a special halt.

Parameters

data	is the function

Returns: the representative CPUI_RETURN op or NULL

References Funcdata::beginOp(), CPUI_RETURN, Funcdata::endOp(), PcodeOp::getHaltType(), PcodeOp::getIn(), Varnode::getTempType(), PcodeOp::isDead(), PcodeOp::numInput(), and Datatype::typeOrder().

virtual Action* ActionInferTypes::clone ( const ActionGroupList & grouplist ) const

inlinevirtual

Clone the Action.

If this Action is a member of one of the groups in the grouplist, this returns a clone of the Action, otherwise NULL is returned.

Parameters

grouplist is the list of groups being cloned

Returns: the cloned Action or NULL

Implements Action.

References ActionStart::apply(), ActionGroupList::contains(), and Action::getGroup().

void ActionInferTypes::propagateAcrossReturns ( Funcdata & data )

staticprivate

Give data-types a chance to propagate between CPUI_RETURN operations.

Since a function is intended to return a single data-type, data-types effectively propagate between the input Varnodes to CPUI_RETURN ops, if there are more than one.

References Funcdata::beginOp(), CPUI_RETURN, Funcdata::endOp(), Funcdata::getArch(), TypeFactory::getArch(), PcodeOp::getHaltType(), PcodeOp::getIn(), Datatype::getMetatype(), Varnode::getNZMask(), Varnode::getSize(), Varnode::getTempType(), PcodeOp::isDead(), PcodeOp::numInput(), Varnode::setTempType(), TYPE_BOOL, and Architecture::types.

Datatype * ActionInferTypes::propagateAddIn2Out	(	TypeFactory *	typegrp,
		PcodeOp *	op,
		int4	inslot
	)

staticprivate

Propagate a pointer data-type through an ADD operation.

Assuming a pointer data-type from an ADD PcodeOp propagates from an input to its output, calculate the transformed data-type of the output Varnode, which will depend on details of the operation. If the edge doesn't make sense as "an ADD to a pointer", prevent the propagation by returning the output Varnode's current data-type.

Parameters

typegrp	is the TypeFactory for constructing the transformed Datatype
op	is the ADD operation
inslot	is the edge to propagate along

Returns: the transformed Datatype or the original output Datatype

References AddrSpace::addressToByte(), PcodeOp::code(), CPUI_PTRSUB, TypeFactory::downChain(), TypeFactory::getBase(), PcodeOp::getIn(), Datatype::getMetatype(), PcodeOp::getOut(), TypePointer::getPtrTo(), Datatype::getSize(), Varnode::getTempType(), TypeFactory::getTypePointer(), TypePointer::getWordSize(), Varnode::isSpacebase(), Datatype::isVariableLength(), TYPE_PTR, TYPE_SPACEBASE, and TYPE_UNKNOWN.

int4 ActionInferTypes::propagateAddPointer	(	PcodeOp *	op,
		int4	slot
	)

staticprivate

Test if edge is pointer plus a constant.

Determine if the given data-type edge looks like a pointer propagating through an "add a constant" operation. We assume the input Varnode has a pointer data-type.

Parameters

op	is the PcodeOp propagating the data-type
slot	is the input edge being propagated

Returns: the offset of the added constant or -1 if not a pointer add operation

References PcodeOp::code(), CPUI_INT_ADD, CPUI_INT_MULT, CPUI_PTRADD, CPUI_PTRSUB, Varnode::getDef(), PcodeOp::getIn(), Datatype::getMetatype(), Varnode::getOffset(), Varnode::getTempType(), Varnode::isConstant(), Varnode::isWritten(), and TYPE_PTR.

bool ActionInferTypes::propagateGoodEdge	(	PcodeOp *	op,
		int4	inslot,
		int4	outslot,
		Varnode *	invn
	)

staticprivate

Determine if propagation should happen along the given edge.

This enforces a series of rules about how a data-type can propagate between the input and output Varnodes of a single PcodeOp. An input to the edge may either an input or output to the PcodeOp. A slot value of -1 indicates the PcodeOp output, a non-negative value indicates a PcodeOp input index.

Parameters

op	is the PcodeOp to test propagation through
inslot	indicates the edge's input Varnode
outslot	indicates the edge's output Varnode
invn	is the input Varnode

Returns: false if edge cannot propagate type

References PcodeOp::code(), CPUI_COPY, CPUI_INDIRECT, CPUI_INT_ADD, CPUI_INT_AND, CPUI_INT_EQUAL, CPUI_INT_LESS, CPUI_INT_LESSEQUAL, CPUI_INT_NOTEQUAL, CPUI_INT_OR, CPUI_INT_XOR, CPUI_LOAD, CPUI_MULTIEQUAL, CPUI_NEW, CPUI_PTRADD, CPUI_PTRSUB, CPUI_SEGMENTOP, CPUI_STORE, PcodeOp::getIn(), Datatype::getMetatype(), Varnode::getTempType(), Varnode::isConstant(), PcodeOp::isIndirectCreation(), Datatype::isPowerOfTwo(), Varnode::isSpacebase(), TYPE_INT, TYPE_PTR, and TYPE_UINT.

void ActionInferTypes::propagateOneType	(	TypeFactory *	typegrp,
		Varnode *	vn
	)

staticprivate

Propagate a data-type starting from one Varnode across the function.

Given a starting Varnode, propagate its Datatype as far as possible through the data-flow graph, transforming the data-type through PcodeOps as necessary. The data-type is push through all possible propagating edges, but each Varnode is visited at most once. Propagation is trimmed along any particular path if the pushed data-type isn't more specific than the current data-type on a Varnode, under the data-type ordering.

Parameters

typegrp	is the TypeFactory for constructing transformed data-types
vn	is the Varnode holding the root data-type to push

References Varnode::clearMark(), PcodeOp::getIn(), PcodeOp::getOut(), PropagationState::inslot, PropagationState::op, Varnode::setMark(), PropagationState::slot, PropagationState::step(), PropagationState::valid(), and PropagationState::vn.

void ActionInferTypes::propagateRef	(	Funcdata &	data,
		Varnode *	vn,
		const Address &	addr
	)

staticprivate

Try to propagate a pointer data-type to known aliases.

Given a Varnode which is a likely pointer and an Address that is a known alias of the pointer, attempt to propagate the Varnode's data-type to Varnodes at that address.

Parameters

data	is the function being analyzed
vn	is the given Varnode
addr	is the aliased address

References Funcdata::beginLoc(), Funcdata::endLoc(), Funcdata::getArch(), Datatype::getMetatype(), Address::getOffset(), Varnode::getOffset(), Datatype::getSize(), Varnode::getSize(), Address::getSpace(), Datatype::getSubType(), Varnode::getTempType(), Varnode::hasNoDescend(), Varnode::isAnnotation(), Varnode::isWritten(), Varnode::setTempType(), TYPE_PTR, TYPE_SPACEBASE, TYPE_UNKNOWN, Datatype::typeOrder(), and Architecture::types.

void ActionInferTypes::propagateSpacebaseRef	(	Funcdata &	data,
		Varnode *	spcvn
	)

staticprivate

Search for pointers and propagate its data-type to known aliases.

This routine looks for ADD operations off of a specific spacebase register that produce output Varnodes with a known data-type. The offset of the ADD is calculated into the corresponding address space, and an attempt is made to propagate the Varnodes data-type to other Varnodes in the address space at that offset.

Parameters

data	is the function being analyzed
spcvn	is the spacebase register

References Varnode::beginDescend(), PcodeOp::code(), CPUI_COPY, CPUI_INT_ADD, CPUI_PTRADD, CPUI_PTRSUB, Varnode::endDescend(), PcodeOp::getAddr(), TypeSpacebase::getAddress(), PcodeOp::getIn(), Datatype::getMetatype(), Varnode::getOffset(), PcodeOp::getOut(), Varnode::getSize(), Varnode::getType(), Varnode::isConstant(), TYPE_PTR, and TYPE_SPACEBASE.

bool ActionInferTypes::propagateTypeEdge	(	TypeFactory *	typegrp,
		PcodeOp *	op,
		int4	inslot,
		int4	outslot
	)

staticprivate

Attempt to propagate a data-type across a single PcodeOp edge.

Given an input Varnode and an output Varnode defining a directed edge through a PcodeOp, determine if and how the input data-type propagates to the output. Update the output Varnode's (temporary) data-type. An input to the edge may either an input or output to the PcodeOp. A slot value of -1 indicates the PcodeOp output, a non-negative value indicates a PcodeOp input index.

Parameters

typegrp	is the TypeFactory for building a possibly transformed data-type
op	is the PcodeOp through which the propagation edge flows
inslot	indicates the edge's input Varnode
outslot	indicates the edge's output Varnode

Returns: true if the data-type propagates

References PcodeOp::code(), CPUI_COPY, CPUI_CPOOLREF, CPUI_INDIRECT, CPUI_INT_ADD, CPUI_INT_AND, CPUI_INT_EQUAL, CPUI_INT_LESS, CPUI_INT_LESSEQUAL, CPUI_INT_NOTEQUAL, CPUI_INT_OR, CPUI_INT_XOR, CPUI_LOAD, CPUI_MULTIEQUAL, CPUI_NEW, CPUI_PTRADD, CPUI_PTRSUB, CPUI_SEGMENTOP, CPUI_STORE, Varnode::getAddr(), TypeFactory::getArch(), TypeFactory::getBase(), Varnode::getDef(), AddrSpaceManager::getDefaultDataSpace(), PcodeOp::getIn(), Datatype::getMetatype(), Varnode::getNZMask(), PcodeOp::getOut(), Datatype::getSize(), Varnode::getSize(), Address::getSpaceFromConst(), Varnode::getTempType(), TypeFactory::getTypePointer(), TypeFactory::getTypePointerNoDepth(), AddrSpace::getWordSize(), Varnode::isAnnotation(), Varnode::isConstant(), Varnode::isMark(), Varnode::isSpacebase(), Varnode::isTypeLock(), Datatype::isVariableLength(), Varnode::isWritten(), Varnode::setTempType(), TYPE_BOOL, TYPE_PTR, TYPE_UNKNOWN, and Datatype::typeOrder().

virtual void ActionInferTypes::reset ( Funcdata & data )

inlinevirtual

Reset the Action for a new function.

Parameters

data	is the new function this Action may affect

Reimplemented from Action.

bool ActionInferTypes::writeBack ( Funcdata & data )

staticprivate

Commit the final propagated data-types to Varnodes.

For each Varnode copy the temporary data-type to the permament field, taking into account previous locks.

Parameters

data	is the function being analyzed

Returns: true if any Varnode's data-type changed from the last round of propagation

References Funcdata::beginLoc(), Funcdata::endLoc(), Varnode::getTempType(), Varnode::hasNoDescend(), Varnode::isAnnotation(), Varnode::isWritten(), and Varnode::updateType().

The documentation for this class was generated from the following files:

coreaction.hh
coreaction.cc

Public Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation