decompiler
1.0.0
|
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 ValueSetRead & | getValueSetRead (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< ValueSet > | valueNodes |
Storage for all the current value sets. | |
map< SeqNum, ValueSetRead > | readNodes |
Additional, after iteration, add-on value sets. | |
Partition | orderPartition |
Value sets in iteration order. | |
list< Partition > | recordStorage |
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. | |
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.
|
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.
vn | is the given Varnode |
type | is the constraint characteristic |
range | is the known constraint (assuming the true branch was taken) |
cbranch | is 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().
|
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.
vn | is the given Varnode |
typeCode | will hold the base register code (if found) |
value | will hold the additive value relative to the base register (if found) |
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.
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.
vertex | is the given ValueSet (attached to the head Varnode) |
part | will hold the constructed Partition |
References ghidra::ValueSet::count, and ghidra::ValueSetSolver::ValueSetEdge::getNext().
|
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.
cbranch | is 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().
|
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.
type | is the constraint characteristic |
lift | is the given range that will be lifted |
startVn | is the starting Varnode |
endVn | is the given ending Varnode in the system |
cbranch | is 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().
|
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.
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.
sinks | is the list terminating Varnodes |
reads | are 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) |
indirectAsCopy | is 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().
|
private |
Generate constraints given a system of Varnodes.
Given a complete data-flow system of Varnodes, look for any constraint:
worklist | is the set of Varnodes in the data-flow system (all marked) |
reads | is 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().
|
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.
vn | is the output Varnode the equation will be attached to |
op | is the specific PcodeOp |
slot | is the input slot of the constrained input Varnode |
type | is the type of values |
range | is the range of true values, which must be complemented |
References ghidra::ValueSet::addEquation(), ghidra::PcodeOp::getSeqNum(), ghidra::Varnode::getValueSet(), and ghidra::CircleRange::invert().
|
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.
compOp | is the comparison PcodeOp |
cbranch | is 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().
|
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.
vn | is the output Varnode the equation will be attached to |
op | is the specific PcodeOp |
slot | is the input slot of the constrained input Varnode |
type | is the type of values |
range | is the range of true values |
References ghidra::ValueSet::addEquation(), ghidra::PcodeOp::getSeqNum(), and ghidra::Varnode::getValueSet().
|
private |
|
inlinestaticprivate |
Prepend a vertex to a partition.
vertex | is the node that will be prepended |
part | is the Partition being modified |
References ghidra::ValueSet::next, ghidra::Partition::startNode, and ghidra::Partition::stopNode.
|
inlinestaticprivate |
Prepend full Partition to given Partition.
head | is the partition to be prepended |
part | is the given partition being modified (prepended to) |
References ghidra::ValueSet::next, ghidra::Partition::startNode, and ghidra::Partition::stopNode.
|
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.
part | is the partition to store |
References ghidra::ValueSet::partHead, and ghidra::Partition::startNode.
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.
max | is the maximum number of iterations to allow before forcing termination |
widener | is 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().
Recursively walk the data-flow graph finding partitions.
References ghidra::ValueSet::count, and ghidra::ValueSetSolver::ValueSetEdge::getNext().