The basic switch model. More...

#include <jumptable.hh>

Inheritance diagram for ghidra::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 ghidra::JumpModel
	JumpModel (JumpTable *jt)
	Construct given a parent jump-table.

virtual	~JumpModel (void)
	Destructor.

virtual void	encode (Encoder &encoder) const
	Encode this model to a stream.

virtual void	decode (Decoder &decoder)
	Decode this model from a stream.

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...

bool	checkCommonCbranch (vector< Varnode > &varArray, BlockBasic bl)
	Check that all incoming blocks end with a CBRANCH. More...

void	checkUnrolledGuard (BlockBasic *bl, int4 maxpullback, bool usenzmask)
	Check for a guard that has been unrolled across multiple blocks. 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...

static uintb	getMaxValue (Varnode *vn)
	Get maximum value associated with the given 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 ghidra::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

◆ analyzeGuards()

void ghidra::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 ghidra::PcodeOp::code(), ghidra::CPUI_BRANCHIND, ghidra::CPUI_CBRANCH, ghidra::Varnode::getDef(), ghidra::FlowBlock::getFlipPath(), ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::FlowBlock::getOut(), ghidra::PcodeOp::isBooleanFlip(), ghidra::CircleRange::isEmpty(), ghidra::Varnode::isWritten(), ghidra::BlockBasic::lastOp(), ghidra::CircleRange::pullBack(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ backup2Switch()

uintb ghidra::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 ghidra::PcodeOp::binary, ghidra::Varnode::getAddr(), ghidra::Funcdata::getArch(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getEvalType(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOpcode(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::MemoryBank::getValue(), ghidra::Varnode::isConstant(), ghidra::Architecture::loader, ghidra::PcodeOp::numInput(), ghidra::TypeOp::recoverInputBinary(), ghidra::TypeOp::recoverInputUnary(), and ghidra::PcodeOp::unary.

Referenced by ghidra::JumpBasicOverride::buildLabels().

◆ buildAddresses()

void ghidra::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 ghidra::JumpModel.

Reimplemented in ghidra::JumpBasicOverride.

References ghidra::AddrSpace::addressToByte(), ghidra::EmulateFunction::collectLoadPoints(), ghidra::EmulateFunction::emulatePath(), ghidra::Architecture::funcptr_align, ghidra::PcodeOp::getAddr(), ghidra::Funcdata::getArch(), ghidra::Address::getSpace(), ghidra::AddrSpace::getWordSize(), and ghidra::EmulateFunction::setLoadCollect().

◆ buildLabels()

void ghidra::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 ghidra::JumpModel.

Reimplemented in ghidra::JumpBasicOverride.

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

◆ calcRange()

void ghidra::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 ghidra::Varnode::getDef(), ghidra::CircleRange::getMask(), ghidra::Varnode::getOffset(), ghidra::GuardRecord::getRange(), ghidra::CircleRange::getSize(), ghidra::Varnode::getSize(), ghidra::CircleRange::intersect(), ghidra::PcodeOp::isBoolOutput(), ghidra::Varnode::isConstant(), ghidra::Varnode::isWritten(), ghidra::GuardRecord::quasiCopy(), and ghidra::GuardRecord::valueMatch().

◆ checkCommonCbranch()

bool ghidra::JumpBasic::checkCommonCbranch	(	vector< Varnode *> &	varArray,
		BlockBasic *	bl
	)

protected

Check that all incoming blocks end with a CBRANCH.

All CBRANCHs in addition to flowing to the given block, must also flow to another common block, and each boolean value must select between the given block and the common block in the same way. If this flow exists, true is returned and the boolean Varnode inputs to each CBRANCH are passed back.

Parameters

varArray	will hold the input Varnodes being passed back
bl	is the given block

Returns: true if the common CBRANCH flow exists across all incoming blocks

References ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::PcodeOp::isBooleanFlip(), ghidra::BlockBasic::lastOp(), and ghidra::FlowBlock::sizeIn().

◆ checkUnrolledGuard()

void ghidra::JumpBasic::checkUnrolledGuard	(	BlockBasic *	bl,
		int4	maxpullback,
		bool	usenzmask
	)

protected

Check for a guard that has been unrolled across multiple blocks.

A guard calculation can be duplicated across multiple blocks that all branch to the basic block performing the final BRANCHIND. In this case, the switch variable is also duplicated across multiple Varnodes that are all inputs to a MULTIEQUAL whose output is used for the final BRANCHIND calculation. This method looks for this situation and creates a GuardRecord associated with this MULTIEQUAL output.

Parameters

bl	is the basic block on the path to the switch with multiple incoming flows
maxpullback	is the maximum number of times to pull back from the guard CBRANCH to the putative switch variable
usenzmask	is true if the NZMASK should be used as part of the pull-back operation

References ghidra::BlockBasic::findMultiequal(), ghidra::Varnode::getDef(), ghidra::FlowBlock::getFlipPath(), ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getSlot(), ghidra::PcodeOp::isBooleanFlip(), ghidra::CircleRange::isEmpty(), ghidra::Varnode::isWritten(), ghidra::EmulatePcodeOp::lastOp, ghidra::BlockBasic::liftVerifyUnroll(), and ghidra::CircleRange::pullBack().

◆ findDeterminingVarnodes()

void ghidra::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 ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), and ghidra::Varnode::isConstant().

Referenced by ghidra::JumpBasicOverride::recoverModel().

◆ findNormalized()

void ghidra::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 ghidra::Funcdata::getArch(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Varnode::getSpace(), ghidra::MemoryBank::getValue(), ghidra::EmulatePcodeOp::glb, ghidra::Varnode::isReadOnly(), and ghidra::Architecture::loader.

◆ findSmallestNormal()

void ghidra::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 ghidra::CircleRange::getSize(), and ghidra::CircleRange::setRange().

◆ findUnnormalized()

void ghidra::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 ghidra::JumpModel.

Reimplemented in ghidra::JumpBasic2.

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

Referenced by ghidra::JumpBasic2::findUnnormalized().

◆ flowsOnlyToModel()

bool ghidra::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 ghidra::Varnode::beginDescend(), ghidra::Varnode::endDescend(), and ghidra::PcodeOp::isMark().

◆ foldInGuards()

bool ghidra::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 ghidra::JumpModel.

Reimplemented in ghidra::JumpBasicOverride.

References ghidra::PcodeOp::isDead().

◆ foldInNormalization()

Varnode * ghidra::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 ghidra::JumpModel.

References ghidra::Funcdata::opSetInput().

◆ foldInOneGuard()

bool ghidra::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 ghidra::JumpBasic2.

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

◆ getMaxValue()

uintb ghidra::JumpBasic::getMaxValue ( Varnode * vn )

staticprotected

Get maximum value associated with the given Varnode.

If the Varnode has a restricted range due to masking via INT_AND, the maximum value of this range is returned. Otherwise, 0 is returned, indicating that the Varnode can take all possible values.

Parameters

vn	is the given Varnode

Returns: the maximum value or 0

References ghidra::calc_mask(), ghidra::PcodeOp::code(), ghidra::CPUI_INT_AND, ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Varnode::isConstant(), ghidra::Varnode::isWritten(), and ghidra::PcodeOp::numInput().

◆ getStride()

int4 ghidra::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 ghidra::Varnode::getNZMask().

◆ ispoint()

bool ghidra::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 ghidra::Varnode::isAnnotation(), ghidra::Varnode::isConstant(), and ghidra::Varnode::isReadOnly().

◆ isprune()

bool ghidra::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 ghidra::Varnode::getDef(), ghidra::PcodeOp::isCall(), ghidra::PcodeOp::isMarker(), ghidra::Varnode::isWritten(), and ghidra::PcodeOp::numInput().

◆ markFoldableGuards()

void ghidra::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 ghidra::GuardRecord::clear(), ghidra::GuardRecord::isUnrolled(), ghidra::GuardRecord::quasiCopy(), and ghidra::GuardRecord::valueMatch().

◆ markModel()

void ghidra::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 ghidra::PcodeOp::clearMark(), and ghidra::PcodeOp::setMark().

◆ recoverModel()

bool ghidra::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 ghidra::JumpModel.

Reimplemented in ghidra::JumpBasicOverride, and ghidra::JumpBasic2.

References ghidra::PcodeOp::getParent().

◆ sanityCheck()

bool ghidra::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 ghidra::JumpModel.

Reimplemented in ghidra::JumpBasicOverride.

References ghidra::Funcdata::getArch(), ghidra::Address::getOffset(), ghidra::Architecture::loader, and ghidra::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

◆ analyzeGuards()

◆ backup2Switch()

◆ buildAddresses()

◆ buildLabels()

◆ calcRange()

◆ checkCommonCbranch()

◆ checkUnrolledGuard()

◆ findDeterminingVarnodes()

◆ findNormalized()

◆ findSmallestNormal()

◆ findUnnormalized()

◆ flowsOnlyToModel()

◆ foldInGuards()

◆ foldInNormalization()

◆ foldInOneGuard()

◆ getMaxValue()

◆ getStride()

◆ ispoint()

◆ isprune()

◆ markFoldableGuards()

◆ markModel()

◆ recoverModel()

◆ sanityCheck()