Information discovered about the program

Create empty discovery information.

Retrieves functions that are trusted entry points.

Maps code addresses to the associated symbol name if any.

Get information for specific functions

Return list of all functions discovered so far.

List of functions to explore next.

Construct an empty discovery state and populate it by exploring from a given set of function entry points

Expand an initial discovery state by exploring from a given set of function entry points.

Mark a escaped code pointer as a function entry.

Mark a list of addresses as function entries with the same reason.

This describes why we started exploring a given function.

Print exploration reason.

This describes why we are exploring a given block within a function.

This analyzes the function at a given address, possibly discovering new candidates.

This returns the updated state and the discovered control flow graph for this function.

Analyze addresses that we have marked as functions, but not yet analyzed to identify basic blocks, and discover new function candidates until we have analyzed all function entry points.

If an exploreFnPred function exists in the DiscoveryState, then do not analyze unexploredFunctions at addresses that do not satisfy this predicate.

Extend the analysis of a previously analyzed function with new information about the transfers for a block in that function. The assumption is that the block in question previously had an unknown transfer state condition, and that the new transfer addresses were discovered by other means (e.g. SMT analysis). The block in question's terminal statement will be replaced by an ITE (from IP -> new addresses) and the new addresses will be added to the frontier for additional discovery.

Run tfunction discovery to explore blocks.

Explore until we have found all functions we can.

This function is intended to make it easy to explore functions, and can be controlled via DiscoveryOptions.

Explore until we have found all functions we can.

This function is a version of completeDiscoveryState that uses the new incremental computation monad rather than IO.

Options controlling completeDiscoveryState.

Some default options

Events reported by discovery process.

Information discovered about a particular function

Address of function entry block.

Returns the "name" associated with a function.

This is either the symbol or the address.

A symbol associated with the definition.

A side mapping that records jump targets for ClassifyFailure block terminators that have been gleaned from an external source. When interpreting the function, this map can be used to complete the control flow of functions with ClassifyFailures.

Flags whether a function is labeled no return or not.

A contiguous region of instructions in memory.

Address of region

The size of the region of memory covered by this.

Reason that we marked this address as the start of a basic block.

Abstract state prior to the execution of this region.

The non-terminal statements in the block

The terminal statement in the block.

This term statement is used to describe higher level expressions of how block ending with a a FetchAndExecute statement should be interpreted.

This describes the layout of a jump table. Beware: on some architectures, after reading from the jump table, the resulting addresses must be aligned. See the IPAlignment class.

Return base address of table storing contents of jump table.

Returns the number of bytes in the layout

This is a good default set of block classifiers

Block classifiers determine how the code discovery engine interprets the final instruction in each block. The individual classifiers are also exported so that architecture backends (or even end users) can provide their own classifiers.

See Classifier for the primitives necessary to define new classifiers (e.g., classifiers that can produce architecture-specific terminators).

Note that classifiers are an instance of Alternative, so the order they are applied in matters. While several are non-overlapping, at least the order that the direct jump and tail call classifiers are applied in matters, as they look substantially the same to the analysis. Being too eager to flag jumps as tail calls classifies the jump targets as known function entry points, which can interfere with other classifiers later in the function.

The classifier for conditional and unconditional branches

Note that this classifier can convert a conditional branch to an unconditional branch if (and only if) the condition is syntactically true or false after constant propagation. It never attempts sophisticated path trimming.

Use the architecture-specific callback to check if last statement was a call.

Note that in some cases the call is known not to return, and thus this code will never jump to the return value; in that case, the noreturnCallClassifier should fire. As such, callClassifier should always be attempted *after* noreturnCallClassifier.

Check this block ends with a return as identified by the architecture-specific processing. Basic return identification can be performed by detecting when the Instruction Pointer (ip_reg) contains the ReturnAddr symbolic value (initially placed on the top of the stack or in the Link Register by the architecture-specific state initializer). However, some architectures perform expression evaluations on this value before loading the IP (e.g. ARM will clear the low bit in T32 mode or the low 2 bits in A32 mode), so the actual detection process is deferred to architecture-specific functionality.

Classifies jumps to concrete addresses as unconditional jumps. Note that this logic is substantially similar to the tailCallClassifier in cases where the function does not establish a stack frame (i.e., leaf functions).

Note that known call targets are not eligible to be intra-procedural jump targets (see classifyDirectJump). This means that we need to conservatively prefer to mis-classify terminators as jumps rather than tail calls. The downside of this choice is that code that could be considered a tail-called function may be duplicated in some cases (i.e., considered part of multiple functions).

The alternative interpretation (eagerly preferring tail calls) can cause a section of a function to be marked as a tail-called function, thereby blocking the directJumpClassifier or the branchClassifier from recognizing the "callee" as an intra-procedural jump. This results in classification failures that we don't have any mitigations for.

Attempt to recognize a call to a function that is known to not return. These are effectively tail calls, even if the compiler did not obviously generate a tail call instruction sequence.

This classifier is important because compilers often place garbage instructions (for alignment, or possibly the next function) after calls to no-return functions. Without knowledge of no-return functions, macaw would otherwise think that the callee could return to the garbage instructions, causing later classification failures.

This functionality depends on a set of known non-return functions are specified as an input to the code discovery process (see pctxKnownFnEntries).

Note that this classifier should always be run before the callClassifier.

Attempt to recognize tail call

The current heuristic is that the target looks like a call, except the stack height in the caller is 0.

Note that, in leaf functions (i.e., with no stack usage), tail calls and jumps look substantially similar. We typically apply the jump classifier first to prefer them, which means that we very rarely recognize tail calls in leaf functions.

A classifier that attempts to recognize PLT stubs

A classifier for jump tables

This classifier employs a number of heuristics, but is of course incomplete

Eliminate all dead statements in blocks

Number of bits in addreses for architecture.