DynamicHash Class Reference

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 (const 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, const 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.

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

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

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

findVarnode()

Varnode * DynamicHash::findVarnode	(	const 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

gatherFirstLevelVars()

void DynamicHash::gatherFirstLevelVars ( vector< Varnode *> &  varlist, const 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

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

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

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

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

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

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

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)

---

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

• dynamic.hh
• dynamic.cc