A hash utility to uniquely identify a temporary Varnode in data-flow. More...

#include <dynamic.hh>

Public Member Functions
void	clear (void)
	Called for each additional hash (after the first)

void	calcHash (const Varnode *root, uint4 method)
	Calculate the hash for given Varnode and method. More...

void	uniqueHash (const Varnode root, Funcdata fd)
	Select a unique hash for the given Varnode. More...

Varnode *	findVarnode (Funcdata *fd, const Address &addr, uint8 h)
	Given an address and hash, find the unique matching Varnode. More...

uint8	getHash (void) const
	Get the (current) hash.

const Address &	getAddress (void) const
	Get the (current) address.

Static Public Member Functions
static void	gatherFirstLevelVars (vector< Varnode * > &varlist, Funcdata *fd, const Address &addr, uint8 h)
	Get the Varnodes immediately attached to PcodeOps at the given address. More...

static int4	getSlotFromHash (uint8 h)
	Retrieve the encoded slot from a hash. More...

static uint4	getMethodFromHash (uint8 h)
	Retrieve the encoded method from a hash. More...

static OpCode	getOpCodeFromHash (uint8 h)
	Retrieve the encoded op-code from a hash. More...

static uint4	getPositionFromHash (uint8 h)
	Retrieve the encoded position from a hash. More...

static uint4	getTotalFromHash (uint8 h)
	Retrieve the encoded collision total from a hash. More...

static bool	getIsNotAttached (uint8 h)
	Retrieve the attachment boolean from a hash. More...

static void	clearTotalPosition (uint8 &h)
	Clear the collision total and position fields within a hash. More...

Static Public Attributes
static uint4	transtable []
	Translation of op-codes to hash values.

Private Member Functions
void	buildVnUp (const Varnode *vn)
	Add in the edge between the given Varnode and its defining PcodeOp. More...

void	buildVnDown (const Varnode *vn)
	Add in edges between the given Varnode and any PcodeOp that reads it. More...

void	buildOpUp (const PcodeOp *op)
	Move input Varnodes for the given PcodeOp into staging. More...

void	buildOpDown (const PcodeOp *op)
	Move the output Varnode for the given PcodeOp into staging. More...

void	gatherUnmarkedVn (void)
	Move staged Varnodes into the sub-graph and mark them.

void	gatherUnmarkedOp (void)
	Mark any new PcodeOps in the sub-graph.

Private Attributes
uint4	vnproc
	Number of Varnodes processed in the markvn list so far.

uint4	opproc
	Number of PcodeOps processed in the markop list so far.

uint4	opedgeproc
	Number of edges processed in the opedge list.

vector< const PcodeOp * >	markop
	List of PcodeOps in the sub-graph being hashed.

vector< const Varnode * >	markvn
	List of Varnodes is the sub-graph being hashed.

vector< const Varnode * >	vnedge
	A staging area for Varnodes before formally adding to the sub-graph.

vector< ToOpEdge >	opedge
	The edges in the sub-graph.

Address	addrresult
	Address most closely associated with variable.

uint8	hash
	The calculated hash value.

Detailed Description

A hash utility to uniquely identify a temporary Varnode in data-flow.

Most Varnodes can be identified within the data-flow graph by their storage address and the address of the PcodeOp that defines them. For temporary registers, this does not work because the storage address is ephemeral. This class allows Varnodes like temporary registers (and constants) to be robustly identified by hashing details of the local data-flow.

This class, when presented a Varnode via calcHash(), calculates a hash (getHash()) and an address (getAddress()) of the PcodeOp most closely associated with the Varnode, either the defining op or the op directly reading the Varnode. There are actually four hash variants that can be calculated, labeled 0, 1, 2, or 3, which incrementally hash in a larger portion of data-flow. The method uniqueHash() selects the simplest variant that causes the hash to be unique for the Varnode, among all the Varnodes that share the same address.

The variant index is encoded in the hash, so the hash and the address are enough information to uniquely identify the Varnode. This is what is stored in the symbol table for a dynamic Symbol.

Member Function Documentation

◆ buildOpDown()

void DynamicHash::buildOpDown ( const PcodeOp * op )

private

Move the output Varnode for the given PcodeOp into staging.

Parameters

op	is the given PcodeOp thats already in the sub-graph

References PcodeOp::getOut(), and vnedge.

Referenced by calcHash().

◆ buildOpUp()

void DynamicHash::buildOpUp ( const PcodeOp * op )

private

Move input Varnodes for the given PcodeOp into staging.

Parameters

op	is the given PcodeOp thats already in the sub-graph

References PcodeOp::getIn(), PcodeOp::numInput(), and vnedge.

Referenced by calcHash().

◆ buildVnDown()

void DynamicHash::buildVnDown ( const Varnode * vn )

private

Add in edges between the given Varnode and any PcodeOp that reads it.

When building edges, certain p-code ops (CAST) are effectively ignored so that we get the same hash whether or not these ops are present.

Parameters

vn	is the given Varnode

References Varnode::beginDescend(), PcodeOp::code(), Varnode::endDescend(), PcodeOp::getOut(), PcodeOp::getSlot(), Varnode::loneDescend(), opedge, and transtable.

Referenced by calcHash().

◆ buildVnUp()

void DynamicHash::buildVnUp ( const Varnode * vn )

private

Add in the edge between the given Varnode and its defining PcodeOp.

When building the edge, certain p-code ops (CAST) are effectively ignored so that we get the same hash whether or not these ops are present.

Parameters

vn	is the given Varnode

References PcodeOp::code(), Varnode::getDef(), PcodeOp::getIn(), Varnode::isWritten(), opedge, and transtable.

Referenced by calcHash().

◆ calcHash()

void DynamicHash::calcHash	(	const Varnode *	root,
		uint4	method
	)

Calculate the hash for given Varnode and method.

A sub-graph is formed extending from the given Varnode as the root. The method specifies how the sub-graph is extended. In particular:

Method 0 is extends to just immediate p-code ops reading or writing root
Method 1 extends to one more level of inputs from method 0.
Method 2 extends to one more level of outputs from method 0.
Method 3 extends to inputs and outputs

The resulting hash and address can be obtained after calling this method through getHash() and getAddress().

Parameters

root	is the given root Varnode
method	is the hashing method to use: 0, 1, 2, 3

References addrresult, buildOpDown(), buildOpUp(), buildVnDown(), buildVnUp(), PcodeOp::code(), crc_update(), gatherUnmarkedOp(), gatherUnmarkedVn(), SeqNum::getAddr(), PcodeOp::getIn(), Varnode::getOffset(), PcodeOp::getOut(), PcodeOp::getSeqNum(), Varnode::getSize(), hash, Varnode::isConstant(), markop, markvn, opedge, opedgeproc, opproc, vnedge, and vnproc.

Referenced by findVarnode(), and uniqueHash().

◆ clearTotalPosition()

void DynamicHash::clearTotalPosition ( uint8 & h )

static

Clear the collision total and position fields within a hash.

The position and total collisions fields are set by the uniqueness and need to be cleared when comparing raw hashes.

Parameters

h	is a reference to the hash to modify

Referenced by findVarnode().

◆ findVarnode()

Varnode * DynamicHash::findVarnode	(	Funcdata *	fd,
		const Address &	addr,
		uint8	h
	)

Given an address and hash, find the unique matching Varnode.

The method, number of collisions, and position are pulled out of the hash. Hashes for the method are performed at Varnodes linked to the given address, and the Varnode which matches the hash (and the position) is returned. If the number of collisions for the hash does not match, this method will not return a Varnode, even if the position looks valid.

Parameters

fd	is the function containing the data-flow
addr	is the given address
h	is the hash

Returns: the matching Varnode or NULL

References calcHash(), clear(), clearTotalPosition(), gatherFirstLevelVars(), getMethodFromHash(), getPositionFromHash(), getTotalFromHash(), and hash.

Referenced by ActionDynamicSymbols::apply(), and Funcdata::attemptDynamicMapping().

◆ gatherFirstLevelVars()

void DynamicHash::gatherFirstLevelVars	(	vector< Varnode * > &	varlist,
		Funcdata *	fd,
		const Address &	addr,
		uint8	h
	)

static

Get the Varnodes immediately attached to PcodeOps at the given address.

Varnodes can be either inputs or outputs to the PcodeOps. The op-code, slot, and attachment boolean encoded in the hash are used to further filter the PcodeOp and Varnode objects. Varnodes are passed back in sequence with a list container.

Parameters

varlist	is the container that will hold the matching Varnodes
fd	is the function holding the data-flow
addr	is the given address
h	is the given hash

References Funcdata::beginOp(), PcodeOp::code(), Funcdata::endOp(), Varnode::getDef(), PcodeOp::getIn(), getIsNotAttached(), getOpCodeFromHash(), PcodeOp::getOut(), getSlotFromHash(), Varnode::loneDescend(), and transtable.

Referenced by findVarnode(), and uniqueHash().

◆ getIsNotAttached()

bool DynamicHash::getIsNotAttached ( uint8 h )

static

Retrieve the attachment boolean from a hash.

The hash encodes whether or not the root was directly attached to its PcodeOp

Parameters

h	is the hash value

Returns: true if the root was not attached

Referenced by gatherFirstLevelVars().

◆ getMethodFromHash()

uint4 DynamicHash::getMethodFromHash ( uint8 h )

static

Retrieve the encoded method from a hash.

The hash encodes the method used to produce it.

Parameters

h	is the hash value

Returns: the method: 0, 1, 2, 3

Referenced by findVarnode().

◆ getOpCodeFromHash()

OpCode DynamicHash::getOpCodeFromHash ( uint8 h )

static

Retrieve the encoded op-code from a hash.

The hash encodes the op-code of the p-code op attached to the root Varnode

Parameters

h	is the hash value

Returns: the op-code

Referenced by gatherFirstLevelVars().

◆ getPositionFromHash()

uint4 DynamicHash::getPositionFromHash ( uint8 h )

static

Retrieve the encoded position from a hash.

The hash encodes the position of the root Varnode within the list of hash collisions

Parameters

h	is the hash value

Returns: the position of the root

Referenced by findVarnode().

◆ getSlotFromHash()

int4 DynamicHash::getSlotFromHash ( uint8 h )

static

Retrieve the encoded slot from a hash.

The hash encodes the input slot the root Varnode was attached to in its PcodeOp.

Parameters

h	is the hash value

Returns: the slot index or -1 if the Varnode was attached as output

Referenced by gatherFirstLevelVars().

◆ getTotalFromHash()

uint4 DynamicHash::getTotalFromHash ( uint8 h )

static

Retrieve the encoded collision total from a hash.

The hash encodes the total number of collisions for that hash

Parameters

h	is the hash value

Returns: the total number of collisions

Referenced by findVarnode().

◆ uniqueHash()

void DynamicHash::uniqueHash	(	const Varnode *	root,
		Funcdata *	fd
	)

Select a unique hash for the given Varnode.

Collect the set of Varnodes at the same address as the given Varnode. Starting with method 0, increment the method and calculate hashes of the Varnodes until the given Varnode has a unique hash within the set. The resulting hash and address can be obtained after calling this method through getHash() and getAddress().

In the rare situation that the last method still does not yield a unique hash, the hash encodes:

the smallest number of hash collisions
the method that produced the smallest number of hash collisions
the position of the root within the collision list

For most cases, this will still uniquely identify the root Varnode.

Parameters

root	is the given root Varnode
fd	is the function (holding the data-flow graph)

References addrresult, calcHash(), clear(), gatherFirstLevelVars(), and hash.

Referenced by Funcdata::buildDynamicSymbol().

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

dynamic.hh
dynamic.cc

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ buildOpDown()

◆ buildOpUp()

◆ buildVnDown()

◆ buildVnUp()

◆ calcHash()

◆ clearTotalPosition()

◆ findVarnode()

◆ gatherFirstLevelVars()

◆ getIsNotAttached()

◆ getMethodFromHash()

◆ getOpCodeFromHash()

◆ getPositionFromHash()

◆ getSlotFromHash()

◆ getTotalFromHash()

◆ uniqueHash()