A sequence of STORE operations writing characters through the same string pointer. More...

#include <constseq.hh>

Inheritance diagram for ghidra::HeapSequence:

Collaboration diagram for ghidra::HeapSequence:

Public Member Functions
	HeapSequence (Funcdata &fdata, Datatype ct, PcodeOp root)
	Constructor for the sequence of STORE ops.

bool	transform (void)
	Transform STOREs into a single memcpy user-op.

Public Member Functions inherited from ghidra::ArraySequence
	ArraySequence (Funcdata &fdata, Datatype ct, PcodeOp root)
	Constructor.

bool	isValid (void) const
	Return true if sequence is found.

Private Member Functions
void	findBasePointer (Varnode *initPtr)
	Find the base pointer for the sequence.

void	findDuplicateBases (vector< Varnode * > &duplist)
	Find any duplicates of basePointer.

void	findInitialStores (vector< PcodeOp * > &stores)

uint8	calcPtraddOffset (Varnode vn, vector< Varnode > &nonConst)
	Calculate the byte offset and any non-constant additive elements between the given Varnode and the basePointer.

bool	testValue (PcodeOp *op)
	Test if a STORE value has the matching form for the sequence.

bool	collectStoreOps (void)
	Collect ops STOREing into a memory region from the same root pointer.

PcodeOp *	buildStringCopy (void)
	Build the strncpy,wcsncpy, or memcpy function with string as input.

void	gatherIndirectPairs (vector< PcodeOp * > &indirects, vector< Varnode * > &pairs)
	Gather INDIRECT ops attached to the final sequence STOREs and their input/output Varnode pairs.

void	removeRecursive (PcodeOp op, vector< PcodeOp > &scratch)
	Remove the given PcodeOp and any other ops that uniquely produce its inputs.

void	removeStoreOps (PcodeOp *replaceOp)
	Remove all STORE ops from the basic block.

Static Private Member Functions
static uint8	calcAddElements (Varnode vn, vector< Varnode > &nonConst, int4 maxDepth)
	Recursively walk an ADD tree from a given root, collecting offsets and non-constant elements.

static bool	setsEqual (const vector< Varnode * > &op1, const vector< Varnode * > &op2)
	Determine if two sets of Varnodes are equal.

Private Attributes
Varnode *	basePointer
	Pointer that sequence is stored to.

uint8	baseOffset
	Offset relative to pointer to root STORE.

AddrSpace *	storeSpace
	Address space being STOREed to.

int4	ptrAddMult
	Required multiplier for PTRADD ops.

vector< Varnode * >	nonConstAdds
	non-constant Varnodes being added into pointer calculation

Additional Inherited Members
Static Public Attributes inherited from ghidra::ArraySequence
static const int4	MINIMUM_SEQUENCE_LENGTH = 4
	Minimum number of sequential characters to trigger replacement with CALLOTHER.

static const int4	MAXIMUM_SEQUENCE_LENGTH = 0x20000

Protected Member Functions inherited from ghidra::ArraySequence
bool	checkInterference (void)
	Find maximal set of ops containing the root with no interfering ops in between.

int4	formByteArray (int4 sz, int4 slot, uint8 rootOff, bool bigEndian)
	Put constant values from COPYs into a single byte array.

uint4	selectStringCopyFunction (int4 &index)
	Pick either strncpy, wcsncpy, or memcpy function used to copy string.

Static Protected Member Functions inherited from ghidra::ArraySequence
static bool	interfereBetween (PcodeOp startOp, PcodeOp endOp)
	Check for interfering ops between the two given ops.

Protected Attributes inherited from ghidra::ArraySequence
Funcdata &	data
	The function containing the sequence.

PcodeOp *	rootOp
	The root PcodeOp.

Datatype *	charType
	Element data-type.

BlockBasic *	block
	Basic block containing all the COPY/STORE ops.

int4	numElements
	Number of elements in the final sequence.

vector< WriteNode >	moveOps
	COPY/STORE into the array memory region.

vector< uint1 >	byteArray
	Constants collected in a single array.

Detailed Description

A sequence of STORE operations writing characters through the same string pointer.

Given an initial STORE, a class instance collects a maximal set of STORE ops that can be treated as writing a single string into memory. If the transform() method is called, an explicit string is constructed, and the STOREs are replaced with a strncpy or similar CALLOTHER that takes the string as its source input.

Constructor & Destructor Documentation

◆ HeapSequence()

ghidra::HeapSequence::HeapSequence	(	Funcdata &	fdata,
		Datatype *	ct,
		PcodeOp *	root
	)

Constructor for the sequence of STORE ops.

From a given STORE op, construct the sequence of STOREs off of the same root pointer. The STOREs must be in the same basic block. They can be out of order but must fill out a contiguous region of memory with a minimum number of character elements. The values being stored are accumulated in a byte array. The initial STORE must have the earliest offset in the sequence. If a sequence matching these conditions isn't found, the constructed object will be in an invalid state, and isInvalid() will return true.

Parameters

fdata	is the function containing the sequence
ct	is the character data-type being STOREd
root	is the given (putative) initial STORE in the sequence

References baseOffset, ghidra::AddrSpace::byteToAddressInt(), ghidra::ArraySequence::charType, ghidra::ArraySequence::checkInterference(), collectStoreOps(), findBasePointer(), ghidra::ArraySequence::formByteArray(), ghidra::Datatype::getAlignSize(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getSpaceFromConst(), ghidra::AddrSpace::getWordSize(), ghidra::AddrSpace::isBigEndian(), ghidra::ArraySequence::moveOps, ghidra::ArraySequence::numElements, ptrAddMult, ghidra::ArraySequence::rootOp, and storeSpace.

Member Function Documentation

◆ buildStringCopy()

PcodeOp * ghidra::HeapSequence::buildStringCopy ( void )

private

Build the strncpy,wcsncpy, or memcpy function with string as input.

A built-in user-op that copies string data is created. Its first (destination) parameter is the base pointer of the STOREs. with the base offset added to it. The second (source) parameter is an internal string constructed from the byteArray. The third parameter is the constant indicating the length of the string. The user-op is inserted just before the last PcodeOp moving a character into the memory region.

Returns: the constructed PcodeOp representing the memcpy

References baseOffset, basePointer, ghidra::ArraySequence::byteArray, ghidra::ArraySequence::charType, ghidra::CPUI_CALLOTHER, ghidra::CPUI_INT_ADD, ghidra::CPUI_PTRADD, ghidra::ArraySequence::data, ghidra::PcodeOp::getAddr(), ghidra::Datatype::getAlignSize(), ghidra::Funcdata::getArch(), ghidra::TypeFactory::getBase(), ghidra::PcodeOp::getIn(), ghidra::Funcdata::getInternalString(), ghidra::Datatype::getSize(), ghidra::Varnode::getSize(), ghidra::Varnode::getTypeReadFacing(), ghidra::PcodeOp::inputTypeLocal(), ghidra::ArraySequence::moveOps, ghidra::Funcdata::newConstant(), ghidra::Funcdata::newOp(), ghidra::Funcdata::newUniqueOut(), nonConstAdds, ghidra::ArraySequence::numElements, ghidra::Funcdata::opInsertBefore(), ghidra::Funcdata::opSetInput(), ghidra::Funcdata::opSetOpcode(), ghidra::UserOpManage::registerBuiltin(), ghidra::ArraySequence::rootOp, ghidra::ArraySequence::selectStringCopyFunction(), ghidra::TYPE_INT, ghidra::Architecture::types, ghidra::Varnode::updateType(), and ghidra::Architecture::userops.

Referenced by transform().

◆ calcAddElements()

uint8 ghidra::HeapSequence::calcAddElements	(	Varnode *	vn,
		vector< Varnode * > &	nonConst,
		int4	maxDepth
	)

staticprivate

Recursively walk an ADD tree from a given root, collecting offsets and non-constant elements.

The constant offsets are returned as a final summed offset. Any non-constant Varnodes encountered are passed back in a list. Recursion is depth limited.

Parameters

vn	is the given root of ADD tree
nonConst	will hold the list of non-constant Varnodes in the tree
maxDepth	is the maximum recursion depth

Returns: the sum of all constant offsets

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

Referenced by calcAddElements(), and calcPtraddOffset().

◆ calcPtraddOffset()

uint8 ghidra::HeapSequence::calcPtraddOffset	(	Varnode *	vn,
		vector< Varnode * > &	nonConst
	)

private

Calculate the byte offset and any non-constant additive elements between the given Varnode and the basePointer.

Walk backward from the given Varnode thru PTRADDs and COPYs, summing any offsets encountered. Any non-constant Varnodes encountered in the path, that are not themselves a pointer, are passed back in a list.

Parameters

vn	is the given Varnode to trace back to the basePointer
nonConst	will hold the list of non-constant Varnodes being passed back

Returns: the sum off constant offsets on the path in byte units

References ghidra::AddrSpace::addressToByteInt(), calcAddElements(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_PTRADD, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::AddrSpace::getWordSize(), ghidra::Varnode::isWritten(), ptrAddMult, and storeSpace.

Referenced by collectStoreOps().

◆ collectStoreOps()

bool ghidra::HeapSequence::collectStoreOps ( void )

private

Collect ops STOREing into a memory region from the same root pointer.

Walk forward from the base pointer to all STORE ops from that pointer, keeping track of the offset. The final set of STOREs will all be in the same basic block as the root STORE and have a greater than or equal offset. If the minimum sequence size is reached, true is returned.

Returns: true if the minimum number of STOREs is collected.

References baseOffset, ghidra::calc_mask(), calcPtraddOffset(), ghidra::ArraySequence::charType, findInitialStores(), ghidra::AddrSpace::getAddrSize(), ghidra::Datatype::getAlignSize(), ghidra::PcodeOp::getIn(), ghidra::ArraySequence::MAXIMUM_SEQUENCE_LENGTH, ghidra::ArraySequence::MINIMUM_SEQUENCE_LENGTH, ghidra::ArraySequence::moveOps, nonConstAdds, ghidra::ArraySequence::rootOp, setsEqual(), storeSpace, and testValue().

Referenced by HeapSequence().

◆ findBasePointer()

void ghidra::HeapSequence::findBasePointer ( Varnode * initPtr )

private

Find the base pointer for the sequence.

From a starting pointer, backtrack through PTRADDs and COPYs to a putative root Varnode pointer.

Parameters

initPtr is pointer Varnode into the root STORE

References basePointer, ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_PTRADD, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::Varnode::isWritten(), and ptrAddMult.

Referenced by HeapSequence().

◆ findDuplicateBases()

void ghidra::HeapSequence::findDuplicateBases ( vector< Varnode * > & duplist )

private

Find any duplicates of basePointer.

Back-track from basePointer through PTRSUBs, PTRADDs, and INT_ADDs to an earlier root, keeping track of any offsets. If an earlier root exists, trace forward, through ops trying to match the offsets. For trace of ops whose offsets match exactly, the resulting Varnode is added to the list of duplicates.

Parameters

duplist will hold the list of duplicate Varnodes (including basePointer)

References basePointer, ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_INT_ADD, ghidra::CPUI_PTRADD, ghidra::CPUI_PTRSUB, ghidra::Varnode::endDescend(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::PcodeOp::getOut(), ghidra::Varnode::isConstant(), and ghidra::Varnode::isWritten().

Referenced by findInitialStores().

◆ findInitialStores()

void ghidra::HeapSequence::findInitialStores ( vector< PcodeOp * > & stores )

private

Find STOREs with pointers derived from the basePointer and that are in the same basic block as the root STORE. The root STORE is not included in the resulting set.

Parameters

stores holds the collected STOREs

References ghidra::Varnode::beginDescend(), ghidra::ArraySequence::block, ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_PTRADD, ghidra::CPUI_STORE, ghidra::Varnode::endDescend(), findDuplicateBases(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ptrAddMult, and ghidra::ArraySequence::rootOp.

Referenced by collectStoreOps().

◆ gatherIndirectPairs()

void ghidra::HeapSequence::gatherIndirectPairs	(	vector< PcodeOp * > &	indirects,
		vector< Varnode * > &	pairs
	)

private

Gather INDIRECT ops attached to the final sequence STOREs and their input/output Varnode pairs.

There may be chained INDIRECTs for a single storage location as it crosses multiple STORE ops. Only the initial input and final output are gathered.

Parameters

indirects	will hold the INDIRECT ops attached to sequence STOREs
pairs	will hold Varnode pairs where the first in the pair is the input and the second is the output

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::ArraySequence::data, ghidra::Varnode::endDescend(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::isMark(), ghidra::Varnode::isWritten(), ghidra::ArraySequence::moveOps, ghidra::Funcdata::opUnsetOutput(), ghidra::PcodeOp::previousOp(), and ghidra::PcodeOp::setMark().

Referenced by removeStoreOps().

◆ removeRecursive()

void ghidra::HeapSequence::removeRecursive	(	PcodeOp *	op,
		vector< PcodeOp * > &	scratch
	)

private

Remove the given PcodeOp and any other ops that uniquely produce its inputs.

The given PcodeOp is always removed. PcodeOps are recursively removed, if the only data-flow path of their output is to the given op, and they are not a CALL or are otherwise special.

Parameters

op	is the given PcodeOp to remove
scratch	is scratch space for holding

References ghidra::ArraySequence::data, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::isAutoLive(), ghidra::PcodeOp::isCall(), ghidra::PcodeOp::isIndirectSource(), ghidra::Varnode::isWritten(), ghidra::Varnode::loneDescend(), ghidra::PcodeOp::numInput(), and ghidra::Funcdata::opDestroy().

Referenced by removeStoreOps().

◆ removeStoreOps()

void ghidra::HeapSequence::removeStoreOps ( PcodeOp * replaceOp )

private

Remove all STORE ops from the basic block.

If the STORE pointer no longer has any other uses, remove the PTRADD producing it, recursively, up to the base pointer. INDIRECT ops surrounding any STORE that is removed are replaced with INDIRECTs around the user-op replacing the STOREs.

Parameters

replaceOp is the user-op replacement for the STOREs

References ghidra::CPUI_INDIRECT, ghidra::ArraySequence::data, gatherIndirectPairs(), ghidra::PcodeOp::getAddr(), ghidra::ArraySequence::moveOps, ghidra::Funcdata::newOp(), ghidra::Funcdata::newVarnodeIop(), ghidra::Funcdata::opDestroy(), ghidra::Funcdata::opInsertBefore(), ghidra::Funcdata::opSetInput(), ghidra::Funcdata::opSetOpcode(), ghidra::Funcdata::opSetOutput(), and removeRecursive().

Referenced by transform().

◆ setsEqual()

bool ghidra::HeapSequence::setsEqual	(	const vector< Varnode * > &	op1,
		const vector< Varnode * > &	op2
	)

staticprivate

Determine if two sets of Varnodes are equal.

The sets are passed in as arrays that are assumed sorted. If the sets contain the exact same Varnodes, true is returned, false otherwise.

Parameters

op1	is the first set
op2	is the second set

Returns: true if and only if the sets are equal

Referenced by collectStoreOps().

◆ testValue()

bool ghidra::HeapSequence::testValue ( PcodeOp * op )

private

Test if a STORE value has the matching form for the sequence.

Parameters

op	is the STORE to test

Returns: true if the value being STOREd has the right size and type

References ghidra::ArraySequence::charType, ghidra::PcodeOp::getIn(), ghidra::Datatype::getSize(), ghidra::Varnode::getSize(), and ghidra::Varnode::isConstant().

Referenced by collectStoreOps().

◆ transform()

bool ghidra::HeapSequence::transform ( void )

Transform STOREs into a single memcpy user-op.

The user-op representing the string move is created and all the STORE ops are removed. If successful true is returned. The transform fails (only) if the accumulated bytes do not represent a legal unicode string.

Returns: true if STOREs are successfully converted to a user-op with a string representation

References buildStringCopy(), and removeStoreOps().

Referenced by ghidra::RuleStringStore::applyOp().

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

/builds/appsec/reveng-binrw/ghidraplusplus/src/dec/constseq.hh
/builds/appsec/reveng-binrw/ghidraplusplus/src/dec/constseq.cc

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ HeapSequence()

Member Function Documentation

◆ buildStringCopy()

◆ calcAddElements()

◆ calcPtraddOffset()

◆ collectStoreOps()

◆ findBasePointer()

◆ findDuplicateBases()

◆ findInitialStores()

◆ gatherIndirectPairs()

◆ removeRecursive()

◆ removeStoreOps()

◆ setsEqual()

◆ testValue()

◆ transform()