Ghidra Decompiler Analysis Engine
Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | List of all members
JumpBasic Class Reference

The basic switch model. More...

#include <jumptable.hh>

Inheritance diagram for JumpBasic:
Inheritance graph
[legend]
Collaboration diagram for JumpBasic:
Collaboration graph
[legend]

Public Member Functions

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 VarnodefoldInNormalization (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 JumpModelclone (JumpTable *jt) const
 Clone this model.
 
virtual void clear (void)
 

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

JumpValuesRangejrange
 Range of values for the (normalized) switch variable.
 
PathMeld pathMeld
 Set of PcodeOps and Varnodes producing the final target addresses.
 
vector< GuardRecordselectguards
 Any guards associated with model.
 
int4 varnodeIndex
 Position of the normalized switch Varnode within PathMeld.
 
Varnodenormalvn
 Normalized switch Varnode.
 
Varnodeswitchvn
 Unnormalized switch Varnode.
 
- Protected Attributes inherited from JumpModel
JumpTablejumptable
 The jump-table that is building this model.
 

Detailed Description

The basic switch model.

This is the most common model:

Member Function Documentation

◆ analyzeGuards()

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
blis the given basic-block
pathoutis an optional path from the basic-block to the switch or -1

◆ backup2Switch()

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
fdis the function containing the switch
outputis the constant value to back up
outvnis the output Varnode of the data-flow
invnis the input Varnode to back up to
Returns
the recovered value associated with the input Varnode

◆ buildAddresses()

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
fdis the function containing the switch
indopis the root BRANCHIND of the switch
addresstablewill hold the list of Addresses
loadpointsif non-null will hold LOAD table information used by the model

Implements JumpModel.

Reimplemented in JumpBasicOverride.

◆ buildLabels()

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
fdis the function containing the switch
addresstableis the address table (used to label code blocks with bad or missing labels)
labelwill hold recovered labels in JumpValues order
origis the JumpModel to use for the JumpValues iterator

Implements JumpModel.

Reimplemented in JumpBasicOverride.

◆ calcRange()

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
vnis the given Varnode
rngwill hold resulting range of values the Varnode can hold at the switch

◆ findDeterminingVarnodes()

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
opis the given PcodeOp
slotis input slot to the PcodeOp all paths must terminate at

◆ findNormalized()

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
fdis the function containing the switch
rootblis the basic-block
pathoutis the (optional) path to the BRANCHIND or -1
matchsizeis an (optional) size to expect for the normalized switch variable range
maxtablesizeis the maximum size expected for the normalized switch variable range

◆ findSmallestNormal()

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
matchsizeoptionally gives an expected size of the range, or it can be 0

◆ findUnnormalized()

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
maxaddsubis a restriction on arithmetic operations
maxleftrightis a restriction on shift operations
maxextis a restriction on extension operations

Implements JumpModel.

Reimplemented in JumpBasic2.

◆ flowsOnlyToModel()

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
vnis the given Varnode
trailOpis an optional known PcodeOp that leads to the model
Returns
true if the only flow is into this model

◆ foldInGuards()

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
fdis the function containing the switch
jumpis the JumpTable owning this model.

Implements JumpModel.

Reimplemented in JumpBasicOverride.

◆ foldInNormalization()

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
fdis the function containing the switch
indopis the given switch as a CPUI_BRANCHIND
Returns
the Varnode holding the final unnormalized switch variable

Implements JumpModel.

◆ foldInOneGuard()

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
fdis the function containing the switch
guardis a description of the particular guard mechanism
jumpis the JumpTable owning this model
Returns
true if a change was made to data-flow

◆ getStride()

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
vnis the given Varnode
Returns
the calculated stride = 1,2,4,...

◆ ispoint()

bool JumpBasic::ispoint ( Varnode vn)
staticprotected

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

Parameters
vnis the given Varnode to test
Returns
false if it is impossible for the Varnode to be the switch variable

◆ isprune()

bool JumpBasic::isprune ( Varnode vn)
staticprotected

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

Parameters
vnis the Varnode we are testing for pruning
Returns
true if the search should be pruned here

◆ markFoldableGuards()

void JumpBasic::markFoldableGuards ( )
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.

◆ markModel()

void JumpBasic::markModel ( bool  val)
protected

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

Parameters
valis true to set marks, false to clear marks

◆ recoverModel()

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
fdis the function containing the switch
indopis the given BRANCHIND
matchsizeis the expected number of address table entries to recover, or 0 for no expectation
maxtablesizeis 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.

◆ sanityCheck()

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
fdis the function containing the switch
indopis the root BRANCHIND of the switch
addresstableis 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.


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