A node for data-flow feature generation. More...

#include <signature.hh>

Collaboration diagram for ghidra::SignatureEntry:

Classes
struct	DFSNode
	A path node for doing depth first traversals of data-flow informed by SignatureEntry. More...

Public Member Functions
	SignatureEntry (Varnode *v, uint4 modifiers)
	Construct from a Varnode.

	SignatureEntry (int4 ind)
	Construct a virtual node.

bool	isTerminal (void) const
	Return true if this node has no inputs.

bool	isNotEmitted (void) const
	Return true if this is not emitted as a feature.

bool	isCommutative (void) const
	Return true if inputs to this are unordered.

bool	isStandaloneCopy (void) const
	Return true if this is a stand-alone COPY.

int4	numInputs (void) const
	Return the number incoming edges to this node.

SignatureEntry *	getIn (int4 i, const map< int4, SignatureEntry * > &sigMap) const
	Get the i-th incoming node.

void	calculateShadow (const map< int4, SignatureEntry * > &sigMap)
	Determine if this node shadows another.

void	localHash (uint4 modifiers)
	Compute an initial hash based on local properties of the Varnode.

void	flip (void)
	Store hash from previous iteration and prepare for next iteration.

void	hashIn (vector< SignatureEntry * > &neigh)
	Hash info from other nodes into this.

Varnode *	getVarnode (void) const
	Get the underlying Varnode which this overlays.

hashword	getHash (void) const
	Get the current hash value.

Static Public Member Functions
static SignatureEntry *	mapToEntry (const Varnode vn, const map< int4, SignatureEntry > &sigMap)
	Given a Varnode, find its SignatureEntry overlay.

static SignatureEntry *	mapToEntryCollapse (const Varnode vn, const map< int4, SignatureEntry > &sigMap)
	Given a Varnode, find its SignatureEntry overlay, collapsing shadows.

static void	removeNoise (map< int4, SignatureEntry * > &sigMap)
	Remove noise from the data-flow graph by collapsing Varnodes that are indirect copies of each other.

static hashword	hashSize (Varnode *vn, uint4 modifiers)
	Calculate a hash describing the size of a given Varnode.

Private Types
enum	SignatureFlags { SIG_NODE_TERMINAL = 0x1 , SIG_NODE_COMMUTATIVE = 0x2 , SIG_NODE_NOT_EMITTED = 0x4 , SIG_NODE_STANDALONE = 0x8 , VISITED = 0x10 , MARKER_ROOT = 0x20 }
	Varnode properties that need to be explicit during feature generation. More...

Private Member Functions
hashword	getOpHash (uint4 modifiers)
	Get a hash encoding the OpCode of the effective defining PcodeOp.

bool	isVisited (void) const
	Return true if this node has been visited before.

void	setVisited (void)
	Mark that this node has been visited.

int4	markerSizeIn (void) const
	Get the number of input edges for this in the noise reduced form of the data-flow graph.

SignatureEntry *	getMarkerIn (int4 i, SignatureEntry vRoot, const map< int4, SignatureEntry > &sigMap) const
	Get a specific node coming into this in the noise reduced form of the data-flow graph.

void	standaloneCopyHash (uint4 modifiers)
	Calculate the hash for stand-alone COPY.

Static Private Member Functions
static bool	testStandaloneCopy (Varnode *vn)
	Determine if the given Varnode is a stand-alone COPY.

static void	noisePostOrder (const vector< SignatureEntry * > &rootlist, vector< SignatureEntry * > &postOrder, map< int4, SignatureEntry * > &sigMap)
	Do a post-ordering of the modified noise graph.

static void	noiseDominator (vector< SignatureEntry * > &postOrder, map< int4, SignatureEntry * > &sigMap)
	Construct the dominator tree for the modified noise graph.

Private Attributes
Varnode *	vn
	The root Varnode.

uint4	flags
	Feature generation properties of this Varnode.

hashword	hash [2]
	Current and previous hash.

const PcodeOp *	op
	The effective defining PcodeOp of this Varnode.

int4	startvn
	First incoming edge (via the effective PcodeOp)

int4	inSize
	Number of incoming edges.

int4	index
	Post-order index.

SignatureEntry *	shadow
	(If non-null) the Varnode being shadowed by this

Detailed Description

A node for data-flow feature generation.

A SignatureEntry is rooted at a specific Varnode in the data-flow of a function. During feature generation it iteratively hashes information about the Varnode and its nearest neighbors through the edges of the graph. Feature generation needs to explicitly label:

Varnodes that don't contribute meaningful information
Shadow Varnodes that are direct or indirect COPYs of other Varnodes
Stand-alone COPYs from a constant or input to a Varnode that is not directly read from again

Member Enumeration Documentation

◆ SignatureFlags

enum ghidra::SignatureEntry::SignatureFlags

private

Varnode properties that need to be explicit during feature generation.

Enumerator
SIG_NODE_TERMINAL	Varnode has no incoming edges.
SIG_NODE_COMMUTATIVE	No distinction between this Varnode's incoming edges.
SIG_NODE_NOT_EMITTED	Varnode is not emitted as a formal feature (it might be hashed with other features)
SIG_NODE_STANDALONE	Varnode is a stand-alone COPY.
VISITED	Mark for spanning tree construction.
MARKER_ROOT	Special root status in marker subgraph.

Constructor & Destructor Documentation

◆ SignatureEntry() [1/2]

ghidra::SignatureEntry::SignatureEntry	(	Varnode *	v,
		uint4	modifiers
	)

Construct from a Varnode.

Parameters

v	is the Varnode being overlayed
modifiers	are the settings being used for signature generation

References ghidra::PcodeOp::code(), ghidra::CPUI_CALL, ghidra::CPUI_CALLIND, ghidra::CPUI_CALLOTHER, ghidra::CPUI_COPY, ghidra::CPUI_CPOOLREF, ghidra::CPUI_INDIRECT, ghidra::CPUI_INT_LEFT, ghidra::CPUI_INT_RIGHT, ghidra::CPUI_INT_SRIGHT, ghidra::CPUI_LOAD, ghidra::CPUI_MULTIEQUAL, ghidra::CPUI_STORE, ghidra::CPUI_SUBPIECE, flags, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), index, inSize, ghidra::PcodeOp::isCommutative(), ghidra::Varnode::isConstant(), ghidra::PcodeOp::numInput(), op, shadow, SIG_NODE_COMMUTATIVE, SIG_NODE_STANDALONE, SIG_NODE_TERMINAL, startvn, testStandaloneCopy(), and vn.

◆ SignatureEntry() [2/2]

ghidra::SignatureEntry::SignatureEntry ( int4 ind )

Construct a virtual node.

Used for adding additional virtual nodes in a modified graph. There is no actual backing Varnode.

Parameters

ind	is the post-order index to associate with the virtual node

References flags, index, inSize, op, shadow, startvn, and vn.

Member Function Documentation

◆ calculateShadow()

void ghidra::SignatureEntry::calculateShadow ( const map< int4, SignatureEntry * > & sigMap )

Determine if this node shadows another.

A Varnode shadows another if it is defined by a COPY or INDIRECT op. In this case, the shadow field is filled in by following any chain of COPY and INDIRECT ops back to their input Varnode.

Parameters

sigMap is the map from Varnode to its SignatureEntry overlay

References ghidra::PcodeOp::code(), ghidra::CPUI_CAST, ghidra::CPUI_COPY, ghidra::CPUI_INDIRECT, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), mapToEntry(), op, shadow, and vn.

◆ getIn()

SignatureEntry * ghidra::SignatureEntry::getIn	(	int4	i,
		const map< int4, SignatureEntry * > &	sigMap
	)		const

inline

Get the i-th incoming node.

Parameters

i	is the index
sigMap	is the map from Varnode to its SignatureEntry overlay

Returns: the selected incoming SignatureEntry node

References ghidra::PcodeOp::getIn(), mapToEntryCollapse(), op, and startvn.

Referenced by ghidra::GraphSigManager::signatureIterate().

◆ getMarkerIn()

SignatureEntry * ghidra::SignatureEntry::getMarkerIn	(	int4	i,
		SignatureEntry *	vRoot,
		const map< int4, SignatureEntry * > &	sigMap
	)		const

inlineprivate

Get a specific node coming into this in the noise reduced form of the data-flow graph.

Parameters

i	is the index of the incoming node
vRoot	is the virtual root of the noise reduced form
sigMap	is the map from a Varnode to its SignatureEntry overlay

Returns: the incoming SignatureEntry

References flags, ghidra::PcodeOp::getIn(), mapToEntry(), MARKER_ROOT, op, and startvn.

Referenced by noiseDominator().

◆ getOpHash()

hashword ghidra::SignatureEntry::getOpHash ( uint4 modifiers )

private

Get a hash encoding the OpCode of the effective defining PcodeOp.

In most cases, the hash value is just the OpCode of the PcodeOp itself. CPOOLREF ops are distinguished by hashing in the CPoolRecord tag type.

Parameters

modifiers are the specific settings being used for signature generation

Returns: the PcodeOp hash value or 0 if there is no effective PcodeOp

References ghidra::PcodeOp::code(), ghidra::CPUI_CPOOLREF, ghidra::PcodeOp::getIn(), ghidra::PcodeOp::numInput(), and op.

Referenced by localHash().

◆ hashIn()

void ghidra::SignatureEntry::hashIn ( vector< SignatureEntry * > & neigh )

Hash info from other nodes into this.

The previous hash value for this node is mixed together with previous hash values from other given nodes. The result becomes the current hash value for this node.

Parameters

neigh is the list of given nodes to mix in

References hash, and isCommutative().

Referenced by ghidra::GraphSigManager::signatureIterate().

◆ hashSize()

hashword ghidra::SignatureEntry::hashSize	(	Varnode *	vn,
		uint4	modifiers
	)

inlinestatic

Calculate a hash describing the size of a given Varnode.

The hash is computed from the size of the Varnode in bytes, as an integer value. Depending on the signature settings, the hash incorporates the full value, or it may truncate a value greater than 4.

Parameters

vn	is the given Varnode
modifiers	are the settings being used for signature generation

Returns: the hash value

References ghidra::Varnode::getSize(), ghidra::GraphSigManager::SIG_COLLAPSE_SIZE, and vn.

Referenced by localHash(), and standaloneCopyHash().

◆ localHash()

void ghidra::SignatureEntry::localHash ( uint4 modifiers )

Compute an initial hash based on local properties of the Varnode.

The current hash value is set, incorporating:

the size of the Varnode
whether the Varnode is constant
whether the Varnode is an input
whether the Varnode is persistent
the OpCode of the effective defining PcodeOp

Parameters

modifiers are the settings being used for signature generation

References flags, ghidra::Varnode::getOffset(), getOpHash(), hash, hashSize(), ghidra::Varnode::isAnnotation(), ghidra::Varnode::isConstant(), ghidra::Varnode::isInput(), ghidra::Varnode::isPersist(), isStandaloneCopy(), ghidra::Varnode::isWritten(), shadow, ghidra::GraphSigManager::SIG_DONOTUSE_CONST, ghidra::GraphSigManager::SIG_DONOTUSE_PERSIST, SIG_NODE_NOT_EMITTED, SIG_NODE_TERMINAL, standaloneCopyHash(), and vn.

Referenced by ghidra::GraphSigManager::setCurrentFunction().

◆ mapToEntry()

SignatureEntry * ghidra::SignatureEntry::mapToEntry	(	const Varnode *	vn,
		const map< int4, SignatureEntry * > &	sigMap
	)

inlinestatic

Given a Varnode, find its SignatureEntry overlay.

Parameters

vn	is the given Varnode
sigMap	is the map from Varnode to SignatureEntry

Returns: the corresponding SignatureEntry

References ghidra::Varnode::getCreateIndex(), and vn.

Referenced by calculateShadow(), ghidra::GraphSigManager::collectBlockSigs(), getMarkerIn(), mapToEntryCollapse(), and noisePostOrder().

◆ mapToEntryCollapse()

SignatureEntry * ghidra::SignatureEntry::mapToEntryCollapse	(	const Varnode *	vn,
		const map< int4, SignatureEntry * > &	sigMap
	)

inlinestatic

Given a Varnode, find its SignatureEntry overlay, collapsing shadows.

If the corresponding SignatureEntry shadows another, the shadowed SignatureEntry is returned instead.

Parameters

vn	is the given Varnode
sigMap	is the map from Varnode to SignatureEntry

Returns: the corresponding SignatureEntry

References mapToEntry(), shadow, and vn.

Referenced by ghidra::GraphSigManager::collectBlockSigs(), and getIn().

◆ markerSizeIn()

int4 ghidra::SignatureEntry::markerSizeIn ( void ) const

inlineprivate

Get the number of input edges for this in the noise reduced form of the data-flow graph.

Returns: the number of input edges

References flags, MARKER_ROOT, and numInputs().

Referenced by noiseDominator().

◆ noiseDominator()

void ghidra::SignatureEntry::noiseDominator	(	vector< SignatureEntry * > &	postOrder,
		map< int4, SignatureEntry * > &	sigMap
	)

staticprivate

Construct the dominator tree for the modified noise graph.

The noise graph is formed from the original graph by removing all non-marker edges. Additionally a virtual root links all Varnodes that were inputs or had their defining op removed. After this routine completes, the shadow field of each node is filled in with its immediate dominator relative to the modified noise graph.

Parameters

postOrder	is the list of nodes in the noise graph in post-order
sigMap	is the map from Varnode to its SignatureEntry overlay

References getMarkerIn(), index, markerSizeIn(), and shadow.

Referenced by removeNoise().

◆ noisePostOrder()

void ghidra::SignatureEntry::noisePostOrder	(	const vector< SignatureEntry * > &	rootlist,
		vector< SignatureEntry * > &	postOrder,
		map< int4, SignatureEntry * > &	sigMap
	)

staticprivate

Do a post-ordering of the modified noise graph.

The noise graph is formed from the original graph by removing all non-marker edges. Root Varnodes for the noise graph, which are either inputs or are defined by a non-marker operation in the original graph, must be provided. The SignatureEntry objects are passed back in post-order, and the post-order index is stored on each object.

Parameters

rootlist	contains the roots of the graph
postOrder	will hold the array of SignatureEntrys in post-order
sigMap	is the map from Varnode to its SignatureEntry overlay

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::Varnode::endDescend(), ghidra::PcodeOp::getOut(), index, ghidra::PcodeOp::isMarker(), isVisited(), mapToEntry(), op, setVisited(), and vn.

Referenced by removeNoise().

◆ removeNoise()

void ghidra::SignatureEntry::removeNoise ( map< int4, SignatureEntry * > & sigMap )

static

Remove noise from the data-flow graph by collapsing Varnodes that are indirect copies of each other.

Two Varnodes are indirect copies if the only paths from one to the other are made up of:

CPUI_COPY
CPUI_INDIRECT and
CPUI_MULTIEQUAL

This routine creates a noise (sub-)graph from the data-flow graph by removing all PcodeOp edges that are not one of these three. A virtual root is created for the noise graph connecting all the input Varnodes and Varnodes defined by one of the removed PcodeOps. The dominator tree is calculated for this rooted noise graph. Any Varnode whose immediate dominator is the virtual root is a shadow base and is not an indirect copy of any other Varnode. All other Varnodes are indirect copies of one of these shadow bases, which can be calculated from the dominator tree. Indirectly copied varnodes are collapsed into their shadow base and will have a non-zero shadow field pointing to this base.

Parameters

sigMap is the map from Varnode to its SignatureEntry overlay

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, flags, ghidra::Varnode::getDef(), ghidra::Varnode::isConstant(), ghidra::Varnode::isInput(), ghidra::PcodeOp::isMarker(), ghidra::Varnode::isWritten(), MARKER_ROOT, noiseDominator(), noisePostOrder(), op, shadow, and vn.

Referenced by ghidra::GraphSigManager::setCurrentFunction().

◆ standaloneCopyHash()

void ghidra::SignatureEntry::standaloneCopyHash ( uint4 modifiers )

private

Calculate the hash for stand-alone COPY.

A stand-alone COPY is incorporated as a feature differently from other Varnodes. This method computes its hash once up front, and it is not updated iteratively as with other SignatureEntry nodes.

Parameters

modifiers are the specific settings being used for signature generation

References ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), hash, hashSize(), ghidra::Varnode::isConstant(), ghidra::Varnode::isPersist(), ghidra::GraphSigManager::SIG_DONOTUSE_CONST, and vn.

Referenced by localHash().

◆ testStandaloneCopy()

bool ghidra::SignatureEntry::testStandaloneCopy ( Varnode * vn )

staticprivate

Determine if the given Varnode is a stand-alone COPY.

A Varnode is a stand-alone COPY if it is defined by a COPY or INDIRECT operation whose input Varnode is either a constant or an input. Additionally the Varnode must not be read directly by other operations in the function. There currently is a slight exception made for a persistent Varnode; it can be read through a single INDIRECT operation.

Parameters

vn	is the given Varnode to test

Returns: true if it is considered a stand-alone COPY

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INDIRECT, ghidra::Varnode::endDescend(), ghidra::Varnode::getAddr(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::Varnode::hasNoDescend(), ghidra::Varnode::isPersist(), ghidra::Varnode::isWritten(), op, and vn.

Referenced by SignatureEntry().

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

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

Classes

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ SignatureFlags

Constructor & Destructor Documentation

◆ SignatureEntry() [1/2]

◆ SignatureEntry() [2/2]

Member Function Documentation

◆ calculateShadow()

◆ getIn()

◆ getMarkerIn()

◆ getOpHash()

◆ hashIn()

◆ hashSize()

◆ localHash()

◆ mapToEntry()

◆ mapToEntryCollapse()

◆ markerSizeIn()

◆ noiseDominator()

◆ noisePostOrder()

◆ removeNoise()

◆ standaloneCopyHash()

◆ testStandaloneCopy()