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.

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

void 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

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 ValueSet::addLandmark(), Varnode::beginDescend(), PcodeOp::code(), CPUI_MULTIEQUAL, Varnode::endDescend(), FlowBlock::getFalseOut(), FlowBlock::getImmedDom(), FlowBlock::getIn(), PcodeOp::getOut(), PcodeOp::getParent(), PcodeOp::getSlot(), FlowBlock::getTrueOut(), Varnode::getValueSet(), PcodeOp::isBooleanFlip(), PcodeOp::isMark(), Varnode::isMark(), Varnode::isWritten(), ValueSet::opCode, and FlowBlock::restrictedByConditional().

bool 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

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)

Returns: true if the Varnode is a relative constant

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

void 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

vertex	is the given ValueSet (attached to the head Varnode)
part	will hold the constructed Partition

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

void 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

cbranch is the given condition branch

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

void 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

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 Varnode::getDef(), PcodeOp::isCall(), Varnode::isMark(), PcodeOp::isMarker(), Varnode::isWritten(), and CircleRange::pullBack().

void 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 ValueSet::vn.

void 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

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

Referenced by Heritage::analyzeNewLoadGuards().

void 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

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 PcodeOp::code(), CPUI_CBRANCH, CPUI_MULTIEQUAL, FlowBlock::getImmedDom(), FlowBlock::getIn(), PcodeOp::getParent(), FlowBlock::isMark(), BlockBasic::lastOp(), FlowBlock::setMark(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

void 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

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 ValueSet::addEquation(), PcodeOp::getSeqNum(), Varnode::getValueSet(), and CircleRange::invert().

void 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

compOp	is the comparison PcodeOp
cbranch	is the conditional branch

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

void 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

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 ValueSet::addEquation(), PcodeOp::getSeqNum(), and Varnode::getValueSet().

void ValueSetSolver::newValueSet	(	Varnode *	vn,
		int4	tCode
	)

private

Allocate storage for a new ValueSet.

The new ValueSet is attached to the given Varnode

Parameters

vn	is the given Varnode
tCode	is the type to associate with the Varnode

void ValueSetSolver::partitionPrepend	(	ValueSet *	vertex,
		Partition &	part
	)

inlinestaticprivate

Prepend a vertex to a partition.

Parameters

vertex	is the node that will be prepended
part	is the Partition being modified

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

void ValueSetSolver::partitionPrepend	(	const Partition &	head,
		Partition &	part
	)

inlinestaticprivate

Prepend full Partition to given Partition.

Parameters

head	is the partition to be prepended
part	is the given partition being modified (prepended to)

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

void 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

part	is the partition to store

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

void 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

max	is the maximum number of iterations to allow before forcing termination
widener	is the Widening strategy to use to accelerate stabilization

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

Referenced by Heritage::analyzeNewLoadGuards().

int4 ValueSetSolver::visit	(	ValueSet *	vertex,
		Partition &	part
	)

private

Recursively walk the data-flow graph finding partitions.

Parameters

vertex	is the current Varnode being walked
part	is the current Partition being constructed

Returns: the index of calculated head ValueSet for the current Parition

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

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

rangeutil.hh
rangeutil.cc

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation