Analyze data-flow to resolve which field of a union data-type is being accessed. More...

#include <unionresolve.hh>

Classes
class	Trial
	A trial data-type fitted to a specific place in the data-flow. More...

class	VisitMark
	A mark accumulated when a given Varnode is visited with a specific field index. More...

Public Member Functions
	ScoreUnionFields (TypeFactory &tgrp, Datatype parentType, PcodeOp op, int4 slot)
	Score a given data-type involving a union against data-flow. More...

	ScoreUnionFields (TypeFactory &tgrp, TypeUnion unionType, int4 offset, PcodeOp op)
	Score a union data-type against data-flow, where there is a SUBPIECE. More...

	ScoreUnionFields (TypeFactory &tgrp, TypeUnion unionType, int4 offset, PcodeOp op, int4 slot)
	Score a union data-type against data-flow, where there is an implied truncation. More...

const ResolvedUnion &	getResult (void) const
	Get the resulting best field resolution.

Private Member Functions
bool	testArrayArithmetic (PcodeOp *op, int4 inslot)
	Check if given PcodeOp is operating on array with union elements. More...

bool	testSimpleCases (PcodeOp op, int4 inslot, Datatype parent)
	Preliminary checks before doing full scoring. More...

int4	scoreLockedType (Datatype ct, Datatype lockType)
	Score trial data-type against a locked data-type. More...

int4	scoreParameter (Datatype ct, const PcodeOp callOp, int4 paramSlot)
	Score trial data-type against a parameter. More...

int4	scoreReturnType (Datatype ct, const PcodeOp callOp)
	Score trial data-type against return data-type of function. More...

Datatype *	derefPointer (Datatype ct, Varnode vn, int4 &score)
	Score trial data-type as a pointer to LOAD/STORE. More...

void	newTrialsDown (Varnode vn, Datatype ct, int4 scoreIndex, bool isArray)
	Create new trials based an reads of given Varnode. More...

void	newTrials (PcodeOp op, int4 slot, Datatype ct, int4 scoreIndex, bool isArray)
	Create new trials based on given input slot. More...

void	scoreTrialDown (const Trial &trial, bool lastLevel)
	Try to fit the given trial following data-flow down. More...

void	scoreTrialUp (const Trial &trial, bool lastLevel)
	Try to fit the given trial following data-flow up.

Datatype *	scoreTruncation (Datatype ct, Varnode vn, int4 offset, int4 scoreIndex)
	Score a truncation in the data-flow. More...

void	scoreConstantFit (const Trial &trial)
	Score trial data-type against a constant. More...

void	runOneLevel (bool lastPass)
	Score all the current trials. More...

void	computeBestIndex (void)
	Assuming scoring is complete, compute the best index.

void	run (void)
	Calculate best fitting field. More...

Private Attributes
TypeFactory &	typegrp
	The factory containing data-types.

vector< int4 >	scores
	Score for each field, indexed by fieldNum + 1 (whole union is index=0)

vector< Datatype * >	fields
	Field corresponding to each score.

set< VisitMark >	visited
	Places that have already been visited.

list< Trial >	trialCurrent
	Current trials being pushed.

list< Trial >	trialNext
	Next set of trials.

ResolvedUnion	result
	The best result.

int4	trialCount
	Number of trials evaluated so far.

Static Private Attributes
static const int4	maxPasses = 6
	Maximum number of levels to score through.

static const int4	threshold = 256
	Threshold of trials over which to cancel additional passes.

static const int4	maxTrials = 1024
	Maximum number of trials to evaluate.

Detailed Description

Analyze data-flow to resolve which field of a union data-type is being accessed.

A Varnode with a data-type that is either a union, a pointer to union, or a part of a union, can be accessed in multiple ways. Each individual read (or write) of the Varnode may be accessing either a specific field of the union or accessing the union as a whole. The particular access may not be explicitly known but can sometimes be inferred from data-flow near the Varnode. This class scores all the possible fields of a data-type involving a union for a specific Varnode.

Because the answer may be different for different accesses, the Varnode must be specified as an access edge, a PcodeOp and a slot. A slot >= 0 indicates the index of a Varnode that is being read by the PcodeOp, a slot == -1 indicates the output Varnode being written by the PcodeOp.

The result of scoring is returned as a ResolvedUnion record.

Constructor & Destructor Documentation

◆ ScoreUnionFields() [1/3]

ghidra::ScoreUnionFields::ScoreUnionFields	(	TypeFactory &	tgrp,
		Datatype *	parentType,
		PcodeOp *	op,
		int4	slot
	)

Score a given data-type involving a union against data-flow.

The data-type must either be a union or a pointer to union. Set up the initial set of trials based on the given data-flow edge (PcodeOp and slot).

Parameters

tgrp	is the TypeFactory owning the data-types
parentType	is the given data-type to score
op	is PcodeOp of the given data-flow edge
slot	is slot of the given data-flow edge

References ghidra::ResolvedUnion::baseType, computeBestIndex(), fields, ghidra::Datatype::getDepend(), ghidra::PcodeOp::getIn(), ghidra::Datatype::getMetatype(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::Datatype::getSize(), ghidra::TypeFactory::getTypePointerStripArray(), ghidra::Datatype::numDepend(), result, run(), scores, testSimpleCases(), trialCurrent, ghidra::TYPE_ARRAY, ghidra::TYPE_PTR, typegrp, and visited.

◆ ScoreUnionFields() [2/3]

ghidra::ScoreUnionFields::ScoreUnionFields	(	TypeFactory &	tgrp,
		TypeUnion *	unionType,
		int4	offset,
		PcodeOp *	op
	)

Score a union data-type against data-flow, where there is a SUBPIECE.

A truncation is fit to each union field before doing the fit against data-flow. Only fields that match the offset and the truncation size (of the SUBPIECE) are scored further. If there is a good fit, the scoring for that field recurses into the given data-flow edge. This is only used where there is a SUBPIECE and the base scoring indicates the whole union is the best match for the input.

Parameters

tgrp	is the TypeFactory owning the data-types
unionType	is the data-type to score, which must be a TypeUnion
offset	is the given starting offset of the truncation
op	is the SUBPIECE op

References computeBestIndex(), fields, ghidra::TypeUnion::getField(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::Datatype::getSize(), newTrialsDown(), ghidra::TypeUnion::numDepend(), ghidra::TypeField::offset, run(), scores, trialCurrent, trialNext, and ghidra::TypeField::type.

◆ ScoreUnionFields() [3/3]

ghidra::ScoreUnionFields::ScoreUnionFields	(	TypeFactory &	tgrp,
		TypeUnion *	unionType,
		int4	offset,
		PcodeOp *	op,
		int4	slot
	)

Score a union data-type against data-flow, where there is an implied truncation.

A truncation is fit to each union field before doing the fit against data-flow, starting with the given PcodeOp and input slot.

Parameters

tgrp	is the TypeFactory owning the data-types
unionType	is the data-type to score, which must be a TypeUnion
offset	is the given starting offset of the truncation
op	is the PcodeOp initially reading/writing the union
slot	is the -1 if the op is writing, >= 0 if reading

References computeBestIndex(), fields, ghidra::TypeUnion::getField(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::TypeUnion::numDepend(), ghidra::TypeField::offset, run(), scores, scoreTruncation(), trialCurrent, ghidra::TypeField::type, and visited.

Member Function Documentation

◆ derefPointer()

Datatype * ghidra::ScoreUnionFields::derefPointer	(	Datatype *	ct,
		Varnode *	vn,
		int4 &	score
	)

private

Score trial data-type as a pointer to LOAD/STORE.

Test if the data-type is a pointer and if the pointed-to data-type is compatible with the size of the value being loaded or stored. A score is passed back for how closely the data-type fits this scenario, and if it does we return the data-type of the pointer value.

Parameters

ct	is the trial data-type
vn	is the Varnode holding the value being loaded or stored
score	is used to pass back the score

Returns: the data-type of the value or null

References ghidra::Datatype::getMetatype(), ghidra::Varnode::getSize(), ghidra::Datatype::getSize(), ghidra::Datatype::getSubType(), and ghidra::TYPE_PTR.

◆ newTrials()

void ghidra::ScoreUnionFields::newTrials	(	PcodeOp *	op,
		int4	slot,
		Datatype *	ct,
		int4	scoreIndex,
		bool	isArray
	)

private

Create new trials based on given input slot.

If the input slot is a Varnode that has already been visited, no new trial is created

Parameters

op	is the PcodeOp with the given slot
slot	is the index of the given input slot
ct	is the data-type to associate with the trial
scoreIndex	is the field index to score the trial against
isArray	is true if the data-type to fit is a pointer to an array

References ghidra::Varnode::beginDescend(), ghidra::Varnode::endDescend(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::getType(), and ghidra::Varnode::isTypeLock().

◆ newTrialsDown()

void ghidra::ScoreUnionFields::newTrialsDown	(	Varnode *	vn,
		Datatype *	ct,
		int4	scoreIndex,
		bool	isArray
	)

private

Create new trials based an reads of given Varnode.

If the Varnode has already been visited, no new trials are created

Parameters

vn	is the given Varnode
ct	is the data-type to associate with the trial
scoreIndex	is the field index to score the trial against
isArray	is true if the data-type to fit is a pointer to an array

References ghidra::Varnode::beginDescend(), ghidra::Varnode::endDescend(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::getType(), and ghidra::Varnode::isTypeLock().

Referenced by ScoreUnionFields().

◆ run()

void ghidra::ScoreUnionFields::run ( void )

private

Calculate best fitting field.

Try to fit each possible field over multiple levels of the data-flow. Return the index of the highest scoring field or -1 if the union data-type itself is the best fit.

Referenced by ScoreUnionFields().

◆ runOneLevel()

void ghidra::ScoreUnionFields::runOneLevel ( bool lastPass )

private

Score all the current trials.

Run through each trial in the current list and compute a score. If the trial recurses and this is not the final pass, build new trials for the recursion.

Parameters

lastPass is true if this is the last pass

◆ scoreConstantFit()

void ghidra::ScoreUnionFields::scoreConstantFit ( const Trial & trial )

private

Score trial data-type against a constant.

Assume the constant has no data-type of its own to match against. Evaluate if the constant looks like an integer or pointer etc. and score the trial data-type against that.

Parameters

trial is the trial of the constant Varnode

References ghidra::FloatFormat::extractExponentCode(), ghidra::ScoreUnionFields::Trial::fitType, ghidra::Datatype::getMetatype(), ghidra::Varnode::getOffset(), ghidra::AddrSpace::getPointerLowerBound(), ghidra::AddrSpace::getPointerUpperBound(), ghidra::Varnode::getSize(), ghidra::ScoreUnionFields::Trial::scoreIndex, ghidra::TYPE_BOOL, ghidra::TYPE_FLOAT, ghidra::TYPE_INT, ghidra::TYPE_PTR, ghidra::TYPE_UINT, and ghidra::ScoreUnionFields::Trial::vn.

◆ scoreLockedType()

int4 ghidra::ScoreUnionFields::scoreLockedType	(	Datatype *	ct,
		Datatype *	lockType
	)

private

Score trial data-type against a locked data-type.

A trial that encounters a locked data-type does not propagate through it but scores the trial data-type against the locked data-type.

Parameters

ct	is the trial data-type
lockType	is the locked data-type

Returns: the score

References ghidra::Datatype::getMetatype(), ghidra::Datatype::getSize(), ghidra::TYPE_ARRAY, ghidra::TYPE_CODE, ghidra::TYPE_INT, ghidra::TYPE_PTR, ghidra::TYPE_STRUCT, ghidra::TYPE_UINT, and ghidra::TYPE_UNION.

◆ scoreParameter()

int4 ghidra::ScoreUnionFields::scoreParameter	(	Datatype *	ct,
		const PcodeOp *	callOp,
		int4	paramSlot
	)

private

Score trial data-type against a parameter.

Look up the call-specs for the given CALL. If the inputs are locked, find the corresponding parameter and score the trial data-type against it.

Parameters

ct	is the trial data-type
callOp	is the CALL
paramSlot	is the input slot of the trial data-type

Returns: the score

References ghidra::Funcdata::getCallSpecs(), ghidra::BlockBasic::getFuncdata(), ghidra::Datatype::getMetatype(), ghidra::FuncProto::getParam(), ghidra::PcodeOp::getParent(), ghidra::ProtoParameter::getType(), ghidra::FuncProto::isInputLocked(), ghidra::FuncProto::numParams(), ghidra::TYPE_ARRAY, ghidra::TYPE_CODE, ghidra::TYPE_STRUCT, and ghidra::TYPE_UNION.

◆ scoreReturnType()

int4 ghidra::ScoreUnionFields::scoreReturnType	(	Datatype *	ct,
		const PcodeOp *	callOp
	)

private

Score trial data-type against return data-type of function.

Look up the call-specs for the given CALL. If the output is locked, score the trial data-type against it.

Parameters

ct	is the trial data-type
callOp	is the CALL

Returns: the score

References ghidra::Funcdata::getCallSpecs(), ghidra::BlockBasic::getFuncdata(), ghidra::Datatype::getMetatype(), ghidra::FuncProto::getOutputType(), ghidra::PcodeOp::getParent(), ghidra::FuncProto::isOutputLocked(), ghidra::TYPE_ARRAY, ghidra::TYPE_CODE, ghidra::TYPE_STRUCT, and ghidra::TYPE_UNION.

◆ scoreTrialDown()

void ghidra::ScoreUnionFields::scoreTrialDown	(	const Trial &	trial,
		bool	lastLevel
	)

private

Try to fit the given trial following data-flow down.

The trial's data-type is fitted to its PcodeOp as the incoming Varnode and a score is computed and added to the score for the trial's union field. The fitting may produce a new data-type which indicates scoring for the trial recurses into the output. This method builds trials for any new data-type unless lastLevel is true Varnode of its PcodeOp.

Parameters

trial	is the given trial
lastLevel	is true if the method should skip building new trials

◆ scoreTruncation()

Datatype * ghidra::ScoreUnionFields::scoreTruncation	(	Datatype *	ct,
		Varnode *	vn,
		int4	offset,
		int4	scoreIndex
	)

private

Score a truncation in the data-flow.

The truncation may be an explicit CPUI_SUBPIECE, or it may be implied. A score is computed for fitting a given data-type to the truncation, and a possible data-type to recurse is also computed.

Parameters

ct	is the given data-type to truncate
vn	is the Varnode the truncation will fit into
offset	is the number of bytes truncated off the start of the data-type
scoreIndex	is the field being scored

Returns: the data-type to recurse or null

References ghidra::TypeUnion::getField(), ghidra::Datatype::getMetatype(), ghidra::Varnode::getSize(), ghidra::Datatype::getSize(), ghidra::Datatype::getSubType(), ghidra::TypeUnion::numDepend(), ghidra::TypeField::offset, ghidra::TypeField::type, ghidra::TYPE_INT, ghidra::TYPE_UINT, and ghidra::TYPE_UNION.

Referenced by ScoreUnionFields().

◆ testArrayArithmetic()

bool ghidra::ScoreUnionFields::testArrayArithmetic	(	PcodeOp *	op,
		int4	inslot
	)

private

Check if given PcodeOp is operating on array with union elements.

If the op is adding a constant size or a multiple of a constant size to the given input slot, where the size is at least as large as the union, return true.

Parameters

op	is the given PcodeOp
inslot	is given input slot

Returns: true if op is doing array arithmetic with elements at least as large as the union

References ghidra::PcodeOp::code(), ghidra::CPUI_INT_ADD, ghidra::CPUI_INT_MULT, ghidra::CPUI_PTRADD, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::Varnode::isConstant(), and ghidra::Varnode::isWritten().

◆ testSimpleCases()

bool ghidra::ScoreUnionFields::testSimpleCases	(	PcodeOp *	op,
		int4	inslot,
		Datatype *	parent
	)

private

Preliminary checks before doing full scoring.

Identify cases where we know the union shouldn't be resolved to a field.

Parameters

op	is the PcodeOp manipulating the union variable
inslot	is -1 if the union is the output, >=0 if the union is an input to the op
parent	is the parent union or pointer to union

Returns: true if the union should not be resolved to a field

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::Datatype::getMetatype(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::isMarker(), ghidra::Varnode::isTypeLock(), and ghidra::TYPE_PTR.

Referenced by ScoreUnionFields().

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

unionresolve.hh
unionresolve.cc

Classes

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ScoreUnionFields() [1/3]

◆ ScoreUnionFields() [2/3]

◆ ScoreUnionFields() [3/3]

Member Function Documentation

◆ derefPointer()

◆ newTrials()

◆ newTrialsDown()

◆ run()

◆ runOneLevel()

◆ scoreConstantFit()

◆ scoreLockedType()

◆ scoreParameter()

◆ scoreReturnType()

◆ scoreTrialDown()

◆ scoreTruncation()

◆ testArrayArithmetic()

◆ testSimpleCases()