A map from values to control-flow targets within a function. More...

#include <jumptable.hh>

Classes
struct	IndexPair
	An address table index and its corresponding out-edge. More...

Public Member Functions
	JumpTable (Architecture *g, Address ad=Address())
	Constructor. More...

	JumpTable (const JumpTable *op2)
	Copy constructor. More...

	~JumpTable (void)
	Destructor.

bool	isRecovered (void) const
	Return true if a model has been recovered.

bool	isLabelled (void) const
	Return true if case labels are computed.

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

bool	isPossibleMultistage (void) const
	Return true if this could be multi-staged.

int4	getStage (void) const
	Return what stage of recovery this jump-table is in.

int4	numEntries (void) const
	Return the size of the address table for this jump-table.

uintb	getSwitchVarConsume (void) const
	Get bits of switch variable consumed by this table.

int4	getDefaultBlock (void) const
	Get the out-edge corresponding to the default switch destination.

const Address &	getOpAddress (void) const
	Get the address of the BRANCHIND for the switch.

PcodeOp *	getIndirectOp (void) const
	Get the BRANCHIND PcodeOp.

void	setIndirectOp (PcodeOp *ind)
	Set the BRANCHIND PcodeOp.

void	setMaxTableSize (uint4 val)
	Set the maximum entries allowed in the address table.

void	setNormMax (uint4 maddsub, uint4 mleftright, uint4 mext)
	Set the switch variable normalization model restrictions.

void	setOverride (const vector< Address > &addrtable, const Address &naddr, uintb h, uintb sv)
	Force manual override information on this jump-table. More...

int4	numIndicesByBlock (const FlowBlock *bl) const
	Return the number of address table entries that target the given basic-block. More...

int4	getIndexByBlock (const FlowBlock *bl, int4 i) const
	Get the index of the i-th address table entry that corresponds to the given basic-block. More...

Address	getAddressByIndex (int4 i) const
	Get the i-th address table entry.

void	setLastAsMostCommon (void)
	Set the most common jump-table target to be the last address in the table.

void	setDefaultBlock (int4 bl)
	Set out-edge of the switch destination considered to be default.

void	setLoadCollect (bool val)
	Set whether LOAD records should be collected.

void	addBlockToSwitch (BlockBasic *bl, uintb lab)
	Force a given basic-block to be a switch destination. More...

void	switchOver (const FlowInfo &flow)
	Convert absolute addresses to block indices. More...

uintb	getLabelByIndex (int4 index) const
	Given a case index, get its label.

void	foldInNormalization (Funcdata *fd)
	Hide the normalization code for the switch. More...

bool	foldInGuards (Funcdata *fd)
	Hide any guard code for this switch.

void	recoverAddresses (Funcdata *fd)
	Recover the raw jump-table addresses (the address table) More...

void	recoverMultistage (Funcdata *fd)
	Recover jump-table addresses keeping track of a possible previous stage. More...

bool	recoverLabels (Funcdata *fd)
	Recover the case labels for this jump-table. More...

bool	checkForMultistage (Funcdata *fd)
	Check if this jump-table requires an additional recovery stage. More...

void	clear (void)
	Clear instance specific data for this jump-table. More...

void	saveXml (ostream &s) const
	Save this jump-table as a <jumptable> XML tag. More...

void	restoreXml (const Element *el)
	Recover this jump-table from a <jumptable> XML tag. More...

Private Member Functions
void	recoverModel (Funcdata *fd)
	Attempt recovery of the jump-table model. More...

void	trivialSwitchOver (void)
	Switch this table over to a trivial model. More...

void	sanityCheck (Funcdata *fd)
	Perform sanity check on recovered address targets. More...

int4	block2Position (const FlowBlock *bl) const
	Convert a basic-block to an out-edge index from the switch. More...

Static Private Member Functions
static bool	isReachable (PcodeOp *op)
	Check if the given PcodeOp still seems reachable in its function. More...

Private Attributes
Architecture *	glb
	Architecture under which this jump-table operates.

JumpModel *	jmodel
	Current model of how the jump table is implemented in code.

JumpModel *	origmodel
	Initial jump table model, which may be incomplete.

vector< Address >	addresstable
	Raw addresses in the jump-table.

vector< IndexPair >	block2addr
	Map from basic-blocks to address table index.

vector< uintb >	label
	The case label for each explicit target.

vector< LoadTable >	loadpoints
	Any recovered in-memory data for the jump-table.

Address	opaddress
	Absolute address of the BRANCHIND jump.

PcodeOp *	indirect
	CPUI_BRANCHIND linked to this jump-table.

uintb	switchVarConsume
	Bits of the switch variable being consumed.

int4	defaultBlock
	The out-edge corresponding to the default switch destination (-1 = undefined)

int4	lastBlock
	Block out-edge corresponding to last entry in the address table.

uint4	maxtablesize
	Maximum table size we allow to be built (sanity check)

uint4	maxaddsub
	Maximum ADDs or SUBs to normalize.

uint4	maxleftright
	Maximum shifts to normalize.

uint4	maxext
	Maximum extensions to normalize.

int4	recoverystage
	0=no stages recovered, 1=additional stage needed, 2=complete

bool	collectloads
	Set to true if information about in-memory model data is/should be collected.

Detailed Description

A map from values to control-flow targets within a function.

A JumpTable is attached to a specific CPUI_BRANCHIND and encapsulates all the information necessary to model the indirect jump as a switch statement. It knows how to map from specific switch variable values to the destination case block and how to label the value.

Constructor & Destructor Documentation

JumpTable::JumpTable	(	Architecture *	g,
		Address	ad = `Address()`
	)

Constructor.

Parameters

g	is the Architecture the table exists within
ad	is the Address of the BRANCHIND this models

References collectloads, defaultBlock, glb, indirect, jmodel, lastBlock, maxaddsub, maxext, maxleftright, maxtablesize, origmodel, recoverystage, and switchVarConsume.

JumpTable::JumpTable ( const JumpTable * op2 )

Copy constructor.

This is a partial clone of another jump-table. Objects that are specific to the particular Funcdata instance must be recalculated.

Parameters

op2	is the jump-table to clone

References addresstable, JumpModel::clone(), collectloads, defaultBlock, glb, indirect, jmodel, lastBlock, loadpoints, maxaddsub, maxext, maxleftright, maxtablesize, opaddress, origmodel, recoverystage, and switchVarConsume.

Member Function Documentation

void JumpTable::addBlockToSwitch	(	BlockBasic *	bl,
		uintb	lab
	)

Force a given basic-block to be a switch destination.

This is used to add address targets from guard branches if they are not already in the address table. A specific case label for the block can also be provided. The new target is appended directly to the end of the table.

Parameters

bl	is the given basic-block
lab	is the case label for the block

References addresstable, block2addr, PcodeOp::getParent(), BlockBasic::getStart(), indirect, label, lastBlock, and FlowBlock::sizeOut().

Referenced by JumpBasic::foldInOneGuard().

int4 JumpTable::block2Position ( const FlowBlock * bl ) const

private

Convert a basic-block to an out-edge index from the switch.

Given a specific basic-block, figure out which edge out of the switch block hits it. This position is different from the index into the address table, the out edges are deduped and may include additional guard destinations. If no edge hits it, throw an exception.

Parameters

bl	is the specific basic-block

Returns: the position of the basic-block

References FlowBlock::getIn(), FlowBlock::getInRevIndex(), FlowBlock::getParent(), and FlowBlock::sizeIn().

Referenced by getIndexByBlock(), and numIndicesByBlock().

bool JumpTable::checkForMultistage ( Funcdata * fd )

Check if this jump-table requires an additional recovery stage.

Look for the override directive that indicates we need an additional recovery stage for this jump-table.

Parameters

fd	is the function containing the switch

Returns: true if an additional recovery stage is required.

References addresstable, PcodeOp::getAddr(), Funcdata::getOverride(), indirect, Override::queryMultistageJumptable(), and recoverystage.

Referenced by FlowInfo::checkMultistageJumptables().

void JumpTable::clear ( void )

Clear instance specific data for this jump-table.

Clear out any data that is specific to a Funcdata instance. The address table is not cleared if it was recovered, and override information is left intact. Right now this is only getting called, when the jumptable is an override in order to clear out derived data.

References block2addr, JumpModel::clear(), indirect, JumpModel::isOverride(), jmodel, label, lastBlock, loadpoints, origmodel, recoverystage, and switchVarConsume.

Referenced by Funcdata::clearJumpTables().

void JumpTable::foldInNormalization ( Funcdata * fd )

Hide the normalization code for the switch.

Eliminate any code involved in actually computing the destination address so it looks like the CPUI_BRANCHIND operation does it all internally.

Parameters

fd	is the function containing this switch

References calc_mask(), PcodeOp::code(), CPUI_INT_SEXT, JumpModel::foldInNormalization(), Varnode::getDef(), PcodeOp::getIn(), Varnode::getNZMask(), Varnode::getSize(), indirect, Varnode::isWritten(), jmodel, minimalmask(), and switchVarConsume.

Referenced by ActionSwitchNorm::apply().

int4 JumpTable::getIndexByBlock	(	const FlowBlock *	bl,
		int4	i
	)		const

Get the index of the i-th address table entry that corresponds to the given basic-block.

An exception is thrown if no address table entry targets the block.

Parameters

bl	is the given basic-block
i	requests a specific position within the duplicate entries

Returns: the address table index

References block2addr, block2Position(), JumpTable::IndexPair::blockPosition, and JumpTable::IndexPair::compareByPosition().

Referenced by BlockSwitch::getLabel().

bool JumpTable::isReachable ( PcodeOp * op )

staticprivate

Check if the given PcodeOp still seems reachable in its function.

We are not doing a complete check, we are looking for a guard that has collapsed to "if (false)"

Parameters

op	is the given PcodeOp to check

Returns: true is the PcodeOp is reachable

References PcodeOp::code(), CPUI_CBRANCH, PcodeOp::getIn(), FlowBlock::getIn(), Varnode::getOffset(), FlowBlock::getOut(), PcodeOp::getParent(), PcodeOp::isBooleanFlip(), Varnode::isConstant(), BlockBasic::lastOp(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

int4 JumpTable::numIndicesByBlock ( const FlowBlock * bl ) const

Return the number of address table entries that target the given basic-block.

Parameters

bl	is the given basic-block

Returns: the count of entries

References block2addr, block2Position(), and JumpTable::IndexPair::compareByPosition().

Referenced by BlockSwitch::getNumLabels().

void JumpTable::recoverAddresses ( Funcdata * fd )

Recover the raw jump-table addresses (the address table)

The addresses that the raw BRANCHIND op might branch to itself are recovered, not including other targets of the final model, like guard addresses. The normalized switch variable and the guards are identified in the process however.

Generally this method is run during flow analysis when we only have partial information about the function (and possibly the switch itself). The Funcdata instance is a partial clone of the function and is different from the final instance that will hold the fully recovered jump-table. The final instance inherits the addresses recovered here, but recoverModel() will need to be run on it separately.

A sanity check is also run, which might truncate the original set of addresses.

Parameters

fd	is the function containing the switch

References addresstable, JumpModel::buildAddresses(), collectloads, JumpModel::getTableSize(), indirect, jmodel, loadpoints, opaddress, recoverModel(), and sanityCheck().

Referenced by recoverMultistage(), and Funcdata::stageJumpTable().

bool JumpTable::recoverLabels ( Funcdata * fd )

Recover the case labels for this jump-table.

This is run assuming the address table has already been recovered, via recoverAddresses() in another Funcdata instance. So recoverModel() needs to be rerun on the instance passed in here.

The unnormalized switch variable is recovered, and for each possible address table entry, the variable value that produces it is calculated and stored as the formal case label for the associated code block.

Parameters

fd	is the (final instance of the) function containing the switch

Returns: true if it looks like a multi-stage restart is needed.

References addresstable, JumpModel::buildAddresses(), JumpModel::buildLabels(), JumpModel::findUnnormalized(), JumpModel::getTableSize(), indirect, JumpModel::isOverride(), isRecovered(), jmodel, label, maxaddsub, maxext, maxleftright, maxtablesize, opaddress, origmodel, JumpModel::recoverModel(), recoverModel(), trivialSwitchOver(), and Funcdata::warning().

Referenced by ActionSwitchNorm::apply().

void JumpTable::recoverModel ( Funcdata * fd )

private

Attempt recovery of the jump-table model.

Try to recover each model in turn, until we find one that matches the specific BRANCHIND.

Parameters

fd	is the function containing the switch

References PcodeOp::code(), CPUI_CALLOTHER, Varnode::getDef(), JumpBasic::getPathMeld(), Varnode::isWritten(), JumpBasic::JumpBasic(), and Funcdata::size.

Referenced by recoverAddresses(), and recoverLabels().

void JumpTable::recoverMultistage ( Funcdata * fd )

Recover jump-table addresses keeping track of a possible previous stage.

Do a normal recoverAddresses, but save off the old JumpModel, and if we fail recovery, put back the old model.

Parameters

fd	is the function containing the switch

References addresstable, PcodeOp::getAddr(), indirect, jmodel, loadpoints, origmodel, recoverAddresses(), recoverystage, and Funcdata::warning().

Referenced by Funcdata::stageJumpTable().

void JumpTable::restoreXml ( const Element * el )

Recover this jump-table from a <jumptable> XML tag.

Restore the addresses, case labels, and any override information from the tag. Other parts of the model and jump-table will still need to be recovered.

Parameters

el	is the root <jumptable> tag to restore from

References addresstable, Element::getAttributeName(), Element::getAttributeValue(), Element::getChildren(), Element::getName(), Element::getNumAttributes(), glb, jmodel, label, loadpoints, opaddress, Address::restoreXml(), and JumpModel::restoreXml().

Referenced by Funcdata::restoreXmlJumpTable().

void JumpTable::sanityCheck ( Funcdata * fd )

private

Perform sanity check on recovered address targets.

Check that the BRANCHIND is still reachable, if not throw JumptableNotReachableError. Check pathological cases when there is only one address in the table, if we find this, throw the JumptableThunkError. Let the model run its sanity check. Print a warning if the sanity check truncates the original address table.

Parameters

fd	is the function containing the switch

References Address::getOffset(), and Funcdata::warning().

Referenced by recoverAddresses().

void JumpTable::saveXml ( ostream & s ) const

Save this jump-table as a <jumptable> XML tag.

The recovered addresses and case labels are saved to the XML stream. If override information is present, this is also incorporated into the tag.

Parameters

s	is the stream to write to

References a_v_u(), addresstable, JumpModel::isOverride(), isRecovered(), jmodel, label, loadpoints, opaddress, Address::saveXml(), JumpModel::saveXml(), and AddrSpace::saveXmlAttributes().

void JumpTable::setOverride	(	const vector< Address > &	addrtable,
		const Address &	naddr,
		uintb	h,
		uintb	sv
	)

Force manual override information on this jump-table.

The model is switched over to JumpBasicOverride, which is initialized with an externally provided list of addresses. The addresses are forced as the output addresses the BRANCHIND for this jump-table. If a non-zero hash and an address is provided, this identifies a specific Varnode to use as the normalized switch variable. A potential starting value for normalized switch variable range is provided.

Parameters

addrtable	is the manually provided list of addresses to put in the address table
naddr	is the address where the normalized switch variable is defined
h	is a hash identifying the normalized switch variable (or 0)
sv	is the starting value for the range of possible normalized switch variable values (usually 0)

References jmodel.

void JumpTable::switchOver ( const FlowInfo & flow )

Convert absolute addresses to block indices.

Convert addresses in this table to actual targeted basic-blocks.

This constructs a map from each out-edge from the basic-block containing the BRANCHIND to addresses in the table targetting that out-block. The most common address table entry is also calculated here.

Parameters