decompiler  1.0.0
Classes | Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
ghidra::ValueSetSolver Class Reference

Class that determines a ValueSet for each Varnode in a data-flow system. More...

#include <rangeutil.hh>

Classes

class  ValueSetEdge
 An iterator over out-bound edges for a single ValueSet node in a data-flow system. More...
 

Public Member Functions

void establishValueSets (const vector< Varnode *> &sinks, const vector< PcodeOp *> &reads, Varnode *stackReg, bool indirectAsCopy)
 Build value sets for a data-flow system. More...
 
int4 getNumIterations (void) const
 Get the current number of iterations.
 
void solve (int4 max, Widener &widener)
 Iterate the ValueSet system until it stabilizes. More...
 
list< ValueSet >::const_iterator beginValueSets (void) const
 Start of all ValueSets in the system.
 
list< ValueSet >::const_iterator endValueSets (void) const
 End of all ValueSets in the system.
 
map< SeqNum, ValueSetRead >::const_iterator beginValueSetReads (void) const
 Start of ValueSetReads.
 
map< SeqNum, ValueSetRead >::const_iterator endValueSetReads (void) const
 End of ValueSetReads.
 
const ValueSetReadgetValueSetRead (const SeqNum &seq)
 Get ValueSetRead by SeqNum.
 

Private Member Functions

void newValueSet (Varnode *vn, int4 tCode)
 Allocate storage for a new ValueSet. More...
 
void partitionSurround (Partition &part)
 Create a full partition component. More...
 
void component (ValueSet *vertex, Partition &part)
 Generate a partition component given its head. More...
 
int4 visit (ValueSet *vertex, Partition &part)
 Recursively walk the data-flow graph finding partitions. More...
 
void establishTopologicalOrder (void)
 Find the optimal order for iterating through the ValueSets. More...
 
void generateTrueEquation (Varnode *vn, PcodeOp *op, int4 slot, int4 type, const CircleRange &range)
 Generate an equation given a true constraint and the input/output Varnodes it affects. More...
 
void generateFalseEquation (Varnode *vn, PcodeOp *op, int4 slot, int4 type, const CircleRange &range)
 Generate the complementary equation given a true constraint and the input/output Varnodes it affects. More...
 
void applyConstraints (Varnode *vn, int4 type, const CircleRange &range, PcodeOp *cbranch)
 Look for PcodeOps where the given constraint range applies and instantiate an equation. More...
 
void constraintsFromPath (int4 type, CircleRange &lift, Varnode *startVn, Varnode *endVn, PcodeOp *cbranch)
 Generate constraints given a Varnode path. More...
 
void constraintsFromCBranch (PcodeOp *cbranch)
 Generate constraints arising from the given branch. More...
 
void generateConstraints (const vector< Varnode *> &worklist, const vector< PcodeOp *> &reads)
 Generate constraints given a system of Varnodes. More...
 
bool checkRelativeConstant (Varnode *vn, int4 &typeCode, uintb &value) const
 Check if the given Varnode is a relative constant. More...
 
void generateRelativeConstraint (PcodeOp *compOp, PcodeOp *cbranch)
 Try to find a relative constraint. More...
 

Static Private Member Functions

static void partitionPrepend (ValueSet *vertex, Partition &part)
 Prepend a vertex to a partition. More...
 
static void partitionPrepend (const Partition &head, Partition &part)
 Prepend full Partition to given Partition. More...
 

Private Attributes

list< ValueSetvalueNodes
 Storage for all the current value sets.
 
map< SeqNum, ValueSetReadreadNodes
 Additional, after iteration, add-on value sets.
 
Partition orderPartition
 Value sets in iteration order.
 
list< PartitionrecordStorage
 Storage for the Partitions establishing components.
 
vector< ValueSet * > rootNodes
 Values treated as inputs.
 
vector< ValueSet * > nodeStack
 Stack used to generate the topological ordering.
 
int4 depthFirstIndex
 (Global) depth first numbering for topological ordering
 
int4 numIterations
 Count of individual ValueSet iterations.
 
int4 maxIterations
 Maximum number of iterations before forcing termination.
 

Detailed Description

Class that determines a ValueSet for each Varnode in a data-flow system.

This class uses value set analysis to calculate (an overestimation of) the range of values that can reach each Varnode. The system is formed by providing a set of Varnodes for which the range is desired (the sinks) via establishValueSets(). This creates a system of Varnodes (within the single function) that can flow to the sinks. Running the method solve() does the analysis, and the caller can examine the results by examining the ValueSet attached to any of the Varnodes in the system (via Varnode::getValueSet()). The ValueSetSolver::solve() starts with minimal value sets and does iteration steps by pushing them through the PcodeOps until stability is reached. A Widener object is passed to solve() which selects the specific strategy for accelerating convergence.

Member Function Documentation

◆ applyConstraints()

void ghidra::ValueSetSolver::applyConstraints ( Varnode vn,
int4  type,
const CircleRange range,
PcodeOp cbranch 
)
private

Look for PcodeOps where the given constraint range applies and instantiate an equation.

If a read of the given Varnode is in a basic block dominated by the condition producing the constraint, then either the constraint or its complement applies to the PcodeOp reading the Varnode. An equation holding the constraint is added to the ValueSet of the Varnode output of the PcodeOp.

Parameters
vnis the given Varnode
typeis the constraint characteristic
rangeis the known constraint (assuming the true branch was taken)
cbranchis conditional branch creating the constraint

References ghidra::ValueSet::addLandmark(), ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::endDescend(), ghidra::FlowBlock::getFalseOut(), ghidra::FlowBlock::getImmedDom(), ghidra::FlowBlock::getIn(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ghidra::PcodeOp::getSlot(), ghidra::FlowBlock::getTrueOut(), ghidra::Varnode::getValueSet(), ghidra::PcodeOp::isBooleanFlip(), ghidra::PcodeOp::isMark(), ghidra::Varnode::isMark(), ghidra::Varnode::isWritten(), ghidra::ValueSet::opCode, and ghidra::FlowBlock::restrictedByConditional().

◆ checkRelativeConstant()

bool ghidra::ValueSetSolver::checkRelativeConstant ( Varnode vn,
int4 &  typeCode,
uintb &  value 
) const
private

Check if the given Varnode is a relative constant.

Verify that the given Varnode is produced by a straight line sequence of COPYs, INT_ADDs with a constant, from the base register marked as relative for our system.

Parameters
vnis the given Varnode
typeCodewill hold the base register code (if found)
valuewill hold the additive value relative to the base register (if found)
Returns
true if the Varnode is a relative constant

References ghidra::calc_mask(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INDIRECT, ghidra::CPUI_INT_ADD, ghidra::CPUI_PTRSUB, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Varnode::getValueSet(), ghidra::Varnode::isConstant(), ghidra::Varnode::isMark(), ghidra::Varnode::isWritten(), and ghidra::ValueSet::typeCode.

◆ component()

void ghidra::ValueSetSolver::component ( ValueSet vertex,
Partition part 
)
private

Generate a partition component given its head.

Knowing that the given Varnode is the head of a partition, generate the partition recursively and generate the formal Partition object.

Parameters
vertexis the given ValueSet (attached to the head Varnode)
partwill hold the constructed Partition

References ghidra::ValueSet::count, and ghidra::ValueSetSolver::ValueSetEdge::getNext().

◆ constraintsFromCBranch()

void ghidra::ValueSetSolver::constraintsFromCBranch ( PcodeOp cbranch)
private

Generate constraints arising from the given branch.

Lift the set of values on the condition for the given CBRANCH to any Varnode in the system, and label (the reads) of any such Varnode with the constraint. If the values cannot be lifted or no Varnode in the system is found, no constraints are generated.

Parameters
cbranchis the given condition branch

References ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::isCall(), ghidra::Varnode::isConstant(), ghidra::Varnode::isMark(), ghidra::PcodeOp::isMarker(), ghidra::Varnode::isWritten(), and ghidra::PcodeOp::numInput().

◆ constraintsFromPath()

void ghidra::ValueSetSolver::constraintsFromPath ( int4  type,
CircleRange lift,
Varnode startVn,
Varnode endVn,
PcodeOp cbranch 
)
private

Generate constraints given a Varnode path.

Knowing that there is a lifting path from the given starting Varnode to an ending Varnode in the system, go ahead and lift the given range to a final constraint on the ending Varnode. Then look for reads of the Varnode where the constraint applies.

Parameters
typeis the constraint characteristic
liftis the given range that will be lifted
startVnis the starting Varnode
endVnis the given ending Varnode in the system
cbranchis the PcodeOp causing the control-flow split

References ghidra::Varnode::getDef(), ghidra::PcodeOp::isCall(), ghidra::Varnode::isMark(), ghidra::PcodeOp::isMarker(), ghidra::Varnode::isWritten(), and ghidra::CircleRange::pullBack().

◆ establishTopologicalOrder()

void ghidra::ValueSetSolver::establishTopologicalOrder ( void  )
private

Find the optimal order for iterating through the ValueSets.

Establish the recursive node ordering for iteratively solving the value set system.

This algorithm is based on "Efficient chaotic iteration strategies with widenings" by Francois Bourdoncle. The Varnodes in the system are ordered and a set of nested Partition components are generated. Iterating the ValueSets proceeds in this order, looping through the components recursively until a fixed point is reached. This implementation assumes all Varnodes in the system are distinguished by Varnode::isMark() returning true.

References ghidra::ValueSet::vn.

◆ establishValueSets()

void ghidra::ValueSetSolver::establishValueSets ( const vector< Varnode *> &  sinks,
const vector< PcodeOp *> &  reads,
Varnode stackReg,
bool  indirectAsCopy 
)

Build value sets for a data-flow system.

Given a set of sinks, find all the Varnodes that flow directly into them and set up their initial ValueSet objects.

Parameters
sinksis the list terminating Varnodes
readsare add-on PcodeOps where we would like to know input ValueSets at the point of read
stackReg(if non-NULL) gives the stack pointer (for keeping track of relative offsets)
indirectAsCopyis true if solver should treat CPUI_INDIRECT as CPUI_COPY operations

References ghidra::PcodeOp::code(), ghidra::CPUI_CALL, ghidra::CPUI_CALLIND, ghidra::CPUI_CALLOTHER, ghidra::CPUI_CPOOLREF, ghidra::CPUI_FLOAT_ABS, ghidra::CPUI_FLOAT_ADD, ghidra::CPUI_FLOAT_CEIL, ghidra::CPUI_FLOAT_DIV, ghidra::CPUI_FLOAT_FLOAT2FLOAT, ghidra::CPUI_FLOAT_FLOOR, ghidra::CPUI_FLOAT_INT2FLOAT, ghidra::CPUI_FLOAT_MULT, ghidra::CPUI_FLOAT_NEG, ghidra::CPUI_FLOAT_ROUND, ghidra::CPUI_FLOAT_SQRT, ghidra::CPUI_FLOAT_SUB, ghidra::CPUI_FLOAT_TRUNC, ghidra::CPUI_INDIRECT, ghidra::CPUI_LOAD, ghidra::CPUI_NEW, ghidra::CPUI_SEGMENTOP, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getSeqNum(), ghidra::Varnode::getValueSet(), ghidra::Varnode::isAnnotation(), ghidra::Varnode::isConstant(), ghidra::PcodeOp::isIndirectStore(), ghidra::Varnode::isMark(), ghidra::Varnode::isSpacebase(), ghidra::Varnode::isWritten(), ghidra::Varnode::loneDescend(), ghidra::PcodeOp::numInput(), ghidra::ValueSet::setFull(), ghidra::PcodeOp::setMark(), and ghidra::Varnode::setMark().

Referenced by ghidra::Heritage::analyzeNewLoadGuards(), and ghidra::IfcAnalyzeRange::execute().

◆ generateConstraints()

void ghidra::ValueSetSolver::generateConstraints ( const vector< Varnode *> &  worklist,
const vector< PcodeOp *> &  reads 
)
private

Generate constraints given a system of Varnodes.

Given a complete data-flow system of Varnodes, look for any constraint:

  • For a particular Varnode
  • A limited set of values
  • Due to its involvement in a branch condition
  • Which applies at a particular read of the Varnode
Parameters
worklistis the set of Varnodes in the data-flow system (all marked)
readsis the additional set of PcodeOps that read a Varnode from the system

References ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, ghidra::CPUI_MULTIEQUAL, ghidra::FlowBlock::getImmedDom(), ghidra::FlowBlock::getIn(), ghidra::PcodeOp::getParent(), ghidra::FlowBlock::isMark(), ghidra::BlockBasic::lastOp(), ghidra::FlowBlock::setMark(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ generateFalseEquation()

void ghidra::ValueSetSolver::generateFalseEquation ( Varnode vn,
PcodeOp op,
int4  slot,
int4  type,
const CircleRange range 
)
private

Generate the complementary equation given a true constraint and the input/output Varnodes it affects.

The equation is expressed as: only false values can reach the indicated input to a specific PcodeOp. The equation is attached to the output of the PcodeOp.

Parameters
vnis the output Varnode the equation will be attached to
opis the specific PcodeOp
slotis the input slot of the constrained input Varnode
typeis the type of values
rangeis the range of true values, which must be complemented

References ghidra::ValueSet::addEquation(), ghidra::PcodeOp::getSeqNum(), ghidra::Varnode::getValueSet(), and ghidra::CircleRange::invert().

◆ generateRelativeConstraint()

void ghidra::ValueSetSolver::generateRelativeConstraint ( PcodeOp compOp,
PcodeOp cbranch 
)
private

Try to find a relative constraint.

Given a binary PcodeOp producing a conditional branch, check if it can be interpreted as a constraint relative to (the) base register specified for this system. If it can be, a relative Equation is generated, which will apply to relative ValueSets.

Parameters
compOpis the comparison PcodeOp
cbranchis the conditional branch

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INT_ADD, ghidra::CPUI_INT_EQUAL, ghidra::CPUI_INT_LESS, ghidra::CPUI_INT_LESSEQUAL, ghidra::CPUI_INT_NOTEQUAL, ghidra::CPUI_INT_SLESS, ghidra::CPUI_INT_SLESSEQUAL, ghidra::CPUI_PTRSUB, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getSize(), ghidra::Varnode::isConstant(), ghidra::Varnode::isMark(), ghidra::Varnode::isWritten(), and ghidra::CircleRange::pullBackBinary().

◆ generateTrueEquation()

void ghidra::ValueSetSolver::generateTrueEquation ( Varnode vn,
PcodeOp op,
int4  slot,
int4  type,
const CircleRange range 
)
private

Generate an equation given a true constraint and the input/output Varnodes it affects.

The equation is expressed as: only true values can reach the indicated input to a specific PcodeOp. The equation is attached to the output of the PcodeOp.

Parameters
vnis the output Varnode the equation will be attached to
opis the specific PcodeOp
slotis the input slot of the constrained input Varnode
typeis the type of values
rangeis the range of true values

References ghidra::ValueSet::addEquation(), ghidra::PcodeOp::getSeqNum(), and ghidra::Varnode::getValueSet().

◆ newValueSet()

void ghidra::ValueSetSolver::newValueSet ( Varnode vn,
int4  tCode 
)
private

Allocate storage for a new ValueSet.

The new ValueSet is attached to the given Varnode

Parameters
vnis the given Varnode
tCodeis the type to associate with the Varnode

◆ partitionPrepend() [1/2]

void ghidra::ValueSetSolver::partitionPrepend ( ValueSet vertex,
Partition part 
)
inlinestaticprivate

Prepend a vertex to a partition.

Parameters
vertexis the node that will be prepended
partis the Partition being modified

References ghidra::ValueSet::next, ghidra::Partition::startNode, and ghidra::Partition::stopNode.

◆ partitionPrepend() [2/2]

void ghidra::ValueSetSolver::partitionPrepend ( const Partition head,
Partition part 
)
inlinestaticprivate

Prepend full Partition to given Partition.

Parameters
headis the partition to be prepended
partis the given partition being modified (prepended to)

References ghidra::ValueSet::next, ghidra::Partition::startNode, and ghidra::Partition::stopNode.

◆ partitionSurround()

void ghidra::ValueSetSolver::partitionSurround ( Partition part)
private

Create a full partition component.

This method saves a Partition to permanent storage. It marks the starting node of the partition and sets up for the iterating algorithm.

Parameters
partis the partition to store

References ghidra::ValueSet::partHead, and ghidra::Partition::startNode.

◆ solve()

void ghidra::ValueSetSolver::solve ( int4  max,
Widener widener 
)

Iterate the ValueSet system until it stabilizes.

The ValueSets are recalculated in the established topological ordering, with looping at various levels until a fixed point is reached.

Parameters
maxis the maximum number of iterations to allow before forcing termination
wideneris the Widening strategy to use to accelerate stabilization

References ghidra::Widener::determineIterationReset(), ghidra::Partition::isDirty, ghidra::ValueSet::iterate(), ghidra::ValueSet::next, ghidra::ValueSet::partHead, and ghidra::ValueSet::printRaw().

Referenced by ghidra::Heritage::analyzeNewLoadGuards(), and ghidra::IfcAnalyzeRange::execute().

◆ visit()

int4 ghidra::ValueSetSolver::visit ( ValueSet vertex,
Partition part 
)
private

Recursively walk the data-flow graph finding partitions.

Parameters
vertexis the current Varnode being walked
partis the current Partition being constructed
Returns
the index of calculated head ValueSet for the current Parition

References ghidra::ValueSet::count, and ghidra::ValueSetSolver::ValueSetEdge::getNext().


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