The basic switch model. More...

#include <jumptable.hh>

Inheritance diagram for JumpBasic:

Public Member Functions
	JumpBasic (JumpTable *jt)
	Construct given a parent JumpTable.

const PathMeld &	getPathMeld (void) const
	Get the possible of paths to the switch.

const JumpValuesRange *	getValueRange (void) const
	Get the normalized value iterator.

virtual bool	isOverride (void) const
	Return true if this model was manually overridden.

virtual int4	getTableSize (void) const
	Return the number of entries in the address table.

virtual bool	recoverModel (Funcdata fd, PcodeOp indop, uint4 matchsize, uint4 maxtablesize)
	Attempt to recover details of the model, given a specific BRANCHIND. More...

virtual void	buildAddresses (Funcdata fd, PcodeOp indop, vector< Address > &addresstable, vector< LoadTable > *loadpoints) const
	Construct the explicit list of target addresses (the Address Table) from this model. More...

virtual void	findUnnormalized (uint4 maxaddsub, uint4 maxleftright, uint4 maxext)
	Recover the unnormalized switch variable. More...

virtual void	buildLabels (Funcdata fd, vector< Address > &addresstable, vector< uintb > &label, const JumpModel orig) const
	Recover case labels associated with the Address table. More...

virtual Varnode *	foldInNormalization (Funcdata fd, PcodeOp indop)
	Do normalization of the given switch specific to this model. More...

virtual bool	foldInGuards (Funcdata fd, JumpTable jump)
	Eliminate any guard code involved in computing the switch destination. More...

virtual bool	sanityCheck (Funcdata fd, PcodeOp indop, vector< Address > &addresstable)
	Perform a sanity check on recovered addresses. More...

virtual JumpModel *	clone (JumpTable *jt) const
	Clone this model.

virtual void	clear (void)
	Clear any non-permanent aspects of the model.

Public Member Functions inherited from JumpModel
	JumpModel (JumpTable *jt)
	Construct given a parent jump-table.

virtual	~JumpModel (void)
	Destructor.

virtual void	saveXml (ostream &s) const
	Save this model as an XML tag.

virtual void	restoreXml (const Element el, Architecture glb)
	Restore this model from an XML tag.

Protected Member Functions
void	findDeterminingVarnodes (PcodeOp *op, int4 slot)
	Calculate the initial set of Varnodes that might be switch variables. More...

void	analyzeGuards (BlockBasic *bl, int4 pathout)
	Analyze CBRANCHs leading up to the given basic-block as a potential switch guard. More...

void	calcRange (Varnode *vn, CircleRange &rng) const
	Calculate the range of values in the given Varnode that direct control-flow to the switch. More...

void	findSmallestNormal (uint4 matchsize)
	Find the putative switch variable with the smallest range of values reaching the switch. More...

void	findNormalized (Funcdata fd, BlockBasic rootbl, int4 pathout, uint4 matchsize, uint4 maxtablesize)
	Do all the work necessary to recover the normalized switch variable. More...

void	markFoldableGuards ()
	Mark the guard CBRANCHs that are truly part of the model. More...

void	markModel (bool val)
	Mark (or unmark) all PcodeOps involved in the model. More...

bool	flowsOnlyToModel (Varnode vn, PcodeOp trailOp)
	Check if the given Varnode flows to anything other than this model. More...

virtual bool	foldInOneGuard (Funcdata fd, GuardRecord &guard, JumpTable jump)
	Eliminate the given guard to this switch. More...

Static Protected Member Functions
static bool	isprune (Varnode *vn)
	Do we prune in here in our depth-first search for the normalized switch variable. More...

static bool	ispoint (Varnode *vn)
	Is it possible for the given Varnode to be a switch variable? More...

static int4	getStride (Varnode *vn)
	Get the step/stride associated with the Varnode. More...

static uintb	backup2Switch (Funcdata fd, uintb output, Varnode outvn, Varnode *invn)
	Back up the constant value in the output Varnode to the value in the input Varnode. More...

Protected Attributes
JumpValuesRange *	jrange
	Range of values for the (normalized) switch variable.

PathMeld	pathMeld
	Set of PcodeOps and Varnodes producing the final target addresses.

vector< GuardRecord >	selectguards
	Any guards associated with model.

int4	varnodeIndex
	Position of the normalized switch Varnode within PathMeld.

Varnode *	normalvn
	Normalized switch Varnode.

Varnode *	switchvn
	Unnormalized switch Varnode.

Protected Attributes inherited from JumpModel
JumpTable *	jumptable
	The jump-table that is building this model.

Detailed Description

The basic switch model.

This is the most common model:

A straight-line calculation from switch variable to BRANCHIND
The switch variable is bounded by one or more guards that branch around the BRANCHIND
The unnormalized switch variable is recovered from the normalized variable through some basic transforms

Member Function Documentation

void JumpBasic::analyzeGuards	(	BlockBasic *	bl,
		int4	pathout
	)

protected

Analyze CBRANCHs leading up to the given basic-block as a potential switch guard.

In general there is only one path to the switch, and the given basic-block will hold the BRANCHIND. In some models, there is more than one path to the switch block, and a path must be specified. In this case, the given basic-block will be a block that flows into the switch block, and the pathout parameter describes which path leads to the switch block.

For each CBRANCH, range restrictions on the various variables which allow control flow to pass through the CBRANCH to the switch are analyzed. A GuardRecord is created for each of these restrictions.

Parameters

bl	is the given basic-block
pathout	is an optional path from the basic-block to the switch or -1

References PcodeOp::code(), CPUI_BRANCHIND, CPUI_CBRANCH, Varnode::getDef(), FlowBlock::getFlipPath(), PcodeOp::getIn(), FlowBlock::getIn(), FlowBlock::getInRevIndex(), FlowBlock::getOut(), PcodeOp::isBooleanFlip(), CircleRange::isEmpty(), Varnode::isWritten(), BlockBasic::lastOp(), CircleRange::pullBack(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

uintb JumpBasic::backup2Switch	(	Funcdata *	fd,
		uintb	output,
		Varnode *	outvn,
		Varnode *	invn
	)

staticprotected

Back up the constant value in the output Varnode to the value in the input Varnode.

This does the work of going from a normalized switch value to the unnormalized value. PcodeOps between the output and input Varnodes must be reversible or an exception is thrown.

Parameters

fd	is the function containing the switch
output	is the constant value to back up
outvn	is the output Varnode of the data-flow
invn	is the input Varnode to back up to

Returns: the recovered value associated with the input Varnode

References PcodeOp::binary, Varnode::getAddr(), Funcdata::getArch(), Varnode::getDef(), PcodeOp::getEvalType(), PcodeOp::getIn(), PcodeOp::getOpcode(), PcodeOp::getOut(), Varnode::getSize(), MemoryBank::getValue(), Varnode::isConstant(), Architecture::loader, PcodeOp::numInput(), TypeOp::recoverInputBinary(), TypeOp::recoverInputUnary(), and PcodeOp::unary.

Referenced by JumpBasicOverride::buildLabels().

void JumpBasic::buildAddresses	(	Funcdata *	fd,
		PcodeOp *	indop,
		vector< Address > &	addresstable,
		vector< LoadTable > *	loadpoints
	)		const

virtual

Construct the explicit list of target addresses (the Address Table) from this model.

The addresses produced all come from the BRANCHIND and may not be deduped. Alternate guard destinations are not yet included.

Parameters

fd	is the function containing the switch
indop	is the root BRANCHIND of the switch
addresstable	will hold the list of Addresses
loadpoints	if non-null will hold LOAD table information used by the model

Implements JumpModel.

Reimplemented in JumpBasicOverride.

References AddrSpace::addressToByte(), EmulateFunction::collectLoadPoints(), EmulateFunction::emulatePath(), PcodeOp::getAddr(), Address::getSpace(), AddrSpace::getWordSize(), and EmulateFunction::setLoadCollect().

void JumpBasic::buildLabels	(	Funcdata *	fd,
		vector< Address > &	addresstable,
		vector< uintb > &	label,
		const JumpModel *	orig
	)		const

virtual

Recover case labels associated with the Address table.

The unnormalized switch variable must already be recovered. Values that the normalized switch value can hold or walked back to obtain the value that the unnormalized switch variable would hold. Labels are returned in the order provided by normalized switch variable iterator JumpValues.

Parameters

fd	is the function containing the switch
addresstable	is the address table (used to label code blocks with bad or missing labels)
label	will hold recovered labels in JumpValues order
orig	is the JumpModel to use for the JumpValues iterator

Implements JumpModel.

Reimplemented in JumpBasicOverride.

References JumpValuesRange::getValue(), JumpValuesRange::initializeForReading(), JumpValuesRange::isReversible(), JumpValuesRange::next(), and Funcdata::warning().

void JumpBasic::calcRange	(	Varnode *	vn,
		CircleRange &	rng
	)		const

protected

Calculate the range of values in the given Varnode that direct control-flow to the switch.

The Varnode is evaluated against each GuardRecord to determine if its range of values can be restricted. Multiple guards may provide different restrictions.

Parameters

vn	is the given Varnode
rng	will hold resulting range of values the Varnode can hold at the switch

References calc_mask(), PcodeOp::code(), coveringmask(), CPUI_INT_AND, Varnode::getDef(), PcodeOp::getIn(), CircleRange::getMask(), Varnode::getOffset(), GuardRecord::getRange(), CircleRange::getSize(), Varnode::getSize(), CircleRange::intersect(), PcodeOp::isBoolOutput(), Varnode::isConstant(), Varnode::isWritten(), GuardRecord::quasiCopy(), and GuardRecord::valueMatch().

void JumpBasic::findDeterminingVarnodes	(	PcodeOp *	op,
		int4	slot
	)

protected

Calculate the initial set of Varnodes that might be switch variables.

Paths that terminate at the given PcodeOp are calculated and organized in a PathMeld object that determines Varnodes that are common to all the paths.

Parameters

op	is the given PcodeOp
slot	is input slot to the PcodeOp all paths must terminate at

References Varnode::getDef(), PcodeOp::getIn(), Varnode::getOffset(), and Varnode::isConstant().

Referenced by JumpBasicOverride::recoverModel().

void JumpBasic::findNormalized	(	Funcdata *	fd,
		BlockBasic *	rootbl,
		int4	pathout,
		uint4	matchsize,
		uint4	maxtablesize
	)

protected

Do all the work necessary to recover the normalized switch variable.

The switch can be specified as the basic-block containing the BRANCHIND, or as a block that flows to the BRANCHIND block by following the specified path out.

Parameters

fd	is the function containing the switch
rootbl	is the basic-block
pathout	is the (optional) path to the BRANCHIND or -1
matchsize	is an (optional) size to expect for the normalized switch variable range
maxtablesize	is the maximum size expected for the normalized switch variable range

References Funcdata::getArch(), Varnode::getOffset(), Varnode::getSize(), Varnode::getSpace(), MemoryBank::getValue(), EmulatePcodeOp::glb, Varnode::isReadOnly(), and Architecture::loader.

void JumpBasic::findSmallestNormal ( uint4 matchsize )

protected

Find the putative switch variable with the smallest range of values reaching the switch.

The Varnode with the smallest range and closest to the BRANCHIND is assumed to be the normalized switch variable. If an expected range size is provided, it is used to prefer a particular Varnode as the switch variable. Whatever Varnode is selected, the JumpValue object is set up to iterator over its range.

Parameters

matchsize optionally gives an expected size of the range, or it can be 0

References CircleRange::getSize(), and CircleRange::setRange().

void JumpBasic::findUnnormalized	(	uint4	maxaddsub,
		uint4	maxleftright,
		uint4	maxext
	)

virtual

Recover the unnormalized switch variable.

The normalized switch variable must already be recovered. The amount of normalization between the two switch variables can be restricted.

Parameters

maxaddsub	is a restriction on arithmetic operations
maxleftright	is a restriction on shift operations
maxext	is a restriction on extension operations

Implements JumpModel.

Reimplemented in JumpBasic2.

References PcodeOp::code(), CPUI_INT_ADD, CPUI_INT_SEXT, CPUI_INT_SUB, CPUI_INT_ZEXT, PcodeOp::getIn(), Varnode::isConstant(), and PcodeOp::numInput().

Referenced by JumpBasic2::findUnnormalized().

bool JumpBasic::flowsOnlyToModel	(	Varnode *	vn,
		PcodeOp *	trailOp
	)

protected

Check if the given Varnode flows to anything other than this model.

The PcodeOps in this model must have been previously marked with markModel(). Run through the descendants of the given Varnode and look for this mark.

Parameters

vn	is the given Varnode
trailOp	is an optional known PcodeOp that leads to the model

Returns: true if the only flow is into this model

References Varnode::beginDescend(), Varnode::endDescend(), and PcodeOp::isMark().

bool JumpBasic::foldInGuards	(	Funcdata *	fd,
		JumpTable *	jump
	)

virtual

Eliminate any guard code involved in computing the switch destination.

We now think of the BRANCHIND as encompassing any guard function.

Parameters

fd	is the function containing the switch
jump	is the JumpTable owning this model.

Implements JumpModel.

Reimplemented in JumpBasicOverride.

References PcodeOp::isDead().

Varnode * JumpBasic::foldInNormalization	(	Funcdata *	fd,
		PcodeOp *	indop
	)

virtual

Do normalization of the given switch specific to this model.

The PcodeOp machinery is removed so it looks like the CPUI_BRANCHIND simply takes the switch variable as an input Varnode and automatically interprets its values to reach the correct destination.

Parameters

fd	is the function containing the switch
indop	is the given switch as a CPUI_BRANCHIND

Returns: the Varnode holding the final unnormalized switch variable

Implements JumpModel.

References Funcdata::opSetInput().

bool JumpBasic::foldInOneGuard	(	Funcdata *	fd,
		GuardRecord &	guard,
		JumpTable *	jump
	)

protectedvirtual

Eliminate the given guard to this switch.

We disarm the guard instructions by making the guard condition always false. If the simplification removes the unusable branches, we are left with only one path through the switch.

Parameters

fd	is the function containing the switch
guard	is a description of the particular guard mechanism
jump	is the JumpTable owning this model

Returns: true if a change was made to data-flow

Reimplemented in JumpBasic2.

References JumpTable::addBlockToSwitch(), GuardRecord::clear(), GuardRecord::getBranch(), FlowBlock::getFlipPath(), PcodeOp::getIn(), JumpTable::getIndirectOp(), FlowBlock::getOut(), PcodeOp::getParent(), GuardRecord::getPath(), Varnode::getSize(), PcodeOp::isBooleanFlip(), BlockBasic::lastOp(), Funcdata::newConstant(), BlockBasic::noInterveningStatement(), Funcdata::opSetInput(), Funcdata::pushBranch(), JumpTable::setDefaultBlock(), JumpTable::setLastAsMostCommon(), and FlowBlock::sizeOut().

int4 JumpBasic::getStride ( Varnode * vn )

staticprotected

Get the step/stride associated with the Varnode.

If the some of the least significant bits of the given Varnode are known to be zero, translate this into a stride for the jumptable range.

Parameters

vn	is the given Varnode

Returns: the calculated stride = 1,2,4,...

References Varnode::getNZMask().

bool JumpBasic::ispoint ( Varnode * vn )

staticprotected

Is it possible for the given Varnode to be a switch variable?

Parameters

vn	is the given Varnode to test

Returns: false if it is impossible for the Varnode to be the switch variable

References Varnode::isAnnotation(), Varnode::isConstant(), and Varnode::isReadOnly().

bool JumpBasic::isprune ( Varnode * vn )

staticprotected

Do we prune in here in our depth-first search for the normalized switch variable.

Parameters

vn	is the Varnode we are testing for pruning

Returns: true if the search should be pruned here

References Varnode::getDef(), PcodeOp::isCall(), PcodeOp::isMarker(), Varnode::isWritten(), and PcodeOp::numInput().

void JumpBasic::markFoldableGuards ( void )

protected

Mark the guard CBRANCHs that are truly part of the model.

These CBRANCHs will be removed from the active control-flow graph, their function folded into the action of the model, as represented by BRANCHIND.

References GuardRecord::quasiCopy().

void JumpBasic::markModel ( bool val )

protected

Mark (or unmark) all PcodeOps involved in the model.

Parameters

val	is true to set marks, false to clear marks

References PcodeOp::clearMark(), and PcodeOp::setMark().

bool JumpBasic::recoverModel	(	Funcdata *	fd,
		PcodeOp *	indop,
		uint4	matchsize,
		uint4	maxtablesize
	)

virtual

Attempt to recover details of the model, given a specific BRANCHIND.

This generally recovers the normalized switch variable and any guards.

Parameters

fd	is the function containing the switch
indop	is the given BRANCHIND
matchsize	is the expected number of address table entries to recover, or 0 for no expectation
maxtablesize	is maximum number of address table entries to allow in the model

Returns: true if details of the model were successfully recovered

Implements JumpModel.

Reimplemented in JumpBasicOverride, and JumpBasic2.

References PcodeOp::getParent().

bool JumpBasic::sanityCheck	(	Funcdata *	fd,
		PcodeOp *	indop,
		vector< Address > &	addresstable
	)

virtual

Perform a sanity check on recovered addresses.

Individual addresses are checked against the function or its program to determine if they are reasonable. This method can optionally remove addresses from the table. If it does so, the underlying model is changed to reflect the removal.

Parameters

fd	is the function containing the switch
indop	is the root BRANCHIND of the switch
addresstable	is the list of recovered Addresses, which may be modified

Returns: true if there are (at least some) reasonable addresses in the table

Implements JumpModel.

Reimplemented in JumpBasicOverride.

References Funcdata::getArch(), Address::getOffset(), Architecture::loader, and LoadImage::loadFill().

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

jumptable.hh
jumptable.cc

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation