A basic jump-table model incorporating manual override information. More...

#include <jumptable.hh>

Inheritance diagram for JumpBasicOverride:

Public Member Functions
	JumpBasicOverride (JumpTable *jt)
	Constructor. More...

void	setAddresses (const vector< Address > &adtable)
	Manually set the address table for this model. More...

void	setNorm (const Address &addr, uintb h)
	Set the normalized switch variable.

void	setStartingValue (uintb val)
	Set the starting value for the normalized range.

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	buildLabels (Funcdata fd, vector< Address > &addresstable, vector< uintb > &label, const JumpModel orig) const
	Recover case labels associated with the Address table. 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.

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.

Public Member Functions inherited from JumpBasic
	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 void	findUnnormalized (uint4 maxaddsub, uint4 maxleftright, uint4 maxext)
	Recover the unnormalized switch variable. More...

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

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

virtual	~JumpModel (void)
	Destructor.

Private Member Functions
int4	findStartOp (Varnode *vn)
	Return the PcodeOp (within the PathMeld set) that takes the given Varnode as input. More...

int4	trialNorm (Funcdata fd, Varnode trialvn, uint4 tolerance)
	Test a given Varnode as a potential normalized switch variable. More...

void	setupTrivial (void)
	Convert this to a trivial model. More...

Varnode *	findLikelyNorm (void)
	Find a potential normalized switch variable. More...

void	clearCopySpecific (void)
	Clear varnodes and ops that are specific to one instance of a function.

Private Attributes
set< Address >	adset
	Absolute address table (manually specified)

vector< uintb >	values
	Normalized switch variable values associated with addresses.

vector< Address >	addrtable
	Address associated with each value.

uintb	startingvalue
	Possible start for guessing values that match addresses.

Address	normaddress
	Dynamic info for recovering normalized switch variable.

uint8	hash
	if (hash==0) there is no normalized switch (use trivial model)

bool	istrivial
	true if we use a trivial value model

Additional Inherited Members
Protected Member Functions inherited from JumpBasic
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 inherited from JumpBasic
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 inherited from JumpBasic
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

A basic jump-table model incorporating manual override information.

The list of potential target addresses produced by the BRANCHIND is not recovered by this model, but must provided explicitly via setAddresses(). The model tries to repurpose some of the analysis that JumpBasic does to recover the switch variable. But it will revert to the trivial model if it can't find a suitable switch variable.

Constructor & Destructor Documentation

JumpBasicOverride::JumpBasicOverride ( JumpTable * jt )

Constructor.

Parameters

jt	is the parent JumpTable

References hash, istrivial, and startingvalue.

Referenced by clone().

Member Function Documentation

void JumpBasicOverride::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

Reimplemented from JumpBasic.

References addrtable.

void JumpBasicOverride::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

Reimplemented from JumpBasic.

References JumpBasic::backup2Switch(), JumpBasic::normalvn, JumpBasic::switchvn, values, and Funcdata::warning().

Varnode * JumpBasicOverride::findLikelyNorm ( void )

private

Find a potential normalized switch variable.

This method is called if the normalized switch variable is not explicitly provided. It looks for the normalized Varnode in the most common jump-table constructions, otherwise it returns null.

Returns: the potential normalized switch variable or null

References PcodeOp::code(), CPUI_INT_ADD, CPUI_INT_MULT, CPUI_LOAD, PathMeld::getOp(), PathMeld::getOpParent(), PathMeld::numOps(), and JumpBasic::pathMeld.

Referenced by recoverModel().

int4 JumpBasicOverride::findStartOp ( Varnode * vn )

private

Return the PcodeOp (within the PathMeld set) that takes the given Varnode as input.

If there no PcodeOp in the set reading the Varnode, null is returned

Parameters

vn	is the given Varnode

Returns: the PcodeOp or null

References Varnode::beginDescend(), Varnode::endDescend(), PathMeld::getOp(), PcodeOp::isMark(), PathMeld::numOps(), and JumpBasic::pathMeld.

Referenced by trialNorm().

virtual bool JumpBasicOverride::foldInGuards	(	Funcdata *	fd,
		JumpTable *	jump
	)

inlinevirtual

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.

Reimplemented from JumpBasic.

bool JumpBasicOverride::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

Reimplemented from JumpBasic.

References clearCopySpecific(), JumpBasic::findDeterminingVarnodes(), findLikelyNorm(), DynamicHash::findVarnode(), hash, istrivial, normaddress, JumpBasic::normalvn, setupTrivial(), trialNorm(), values, and JumpBasic::varnodeIndex.

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

inlinevirtual

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

Reimplemented from JumpBasic.

void JumpBasicOverride::setAddresses ( const vector< Address > & adtable )

Manually set the address table for this model.

Parameters

adtable is the list of externally provided addresses, which will be deduped

References adset.

void JumpBasicOverride::setupTrivial ( void )

private

Convert this to a trivial model.

Since we have an absolute set of addresses, if all else fails we can use the indirect variable as the normalized switch and the addresses as the values, similar to JumpModelTrivial

References addrtable, adset, PathMeld::getVarnode(), istrivial, JumpBasic::normalvn, JumpBasic::pathMeld, values, and JumpBasic::varnodeIndex.

Referenced by recoverModel().

int4 JumpBasicOverride::trialNorm	(	Funcdata *	fd,
		Varnode *	trialvn,
		uint4	tolerance
	)

private

Test a given Varnode as a potential normalized switch variable.

This method tries to figure out the set of values for the Varnode that produce the manually provided set of addresses. Starting with startingvalue and simply incrementing by one to obtain new values, the path from the potential variable to the BRANCHIND is emulated to produce addresses in the manual set. Duplicates and misses are allowed. Once we see all addresses in the manual set, the method returns the index of the starting op, otherwise -1 is returned.

Parameters

fd	is the function containing the switch
trialvn	is the given trial normalized switch variable
tolerance	is the number of misses that will be tolerated

Returns: the index of the starting PcodeOp within the PathMeld or -1

References AddrSpace::addressToByte(), addrtable, adset, EmulateFunction::emulatePath(), findStartOp(), PcodeOp::getAddr(), PathMeld::getOp(), Address::getSpace(), AddrSpace::getWordSize(), JumpBasic::pathMeld, startingvalue, and values.

Referenced by recoverModel().

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

jumptable.hh
jumptable.cc

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation