ROSE  0.11.145.0
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
Rose::BinaryAnalysis::Partitioner2::Partitioner Class Reference

Description

Partitions instructions into basic blocks and functions.

A partitioner is responsible for driving a disassembler to obtain instructions, grouping those instructions into basic blocks, grouping the basic blocks into functions, and building an abstract syntax tree. The partitioner is the low-level part of the whole partitioning process (the Engine is the high-level part) and is customized by registering callbacks. The partitioner knows "how" to group small components (like instructions) into larger components (like basic blocks) whereas the engine knows "where" to look for things in the specimen address space.

The following objects are needed as input:

The following data structures are maintained consistently by the partitioner (described in detail later):

Basic Blocks

A basic block (BB) is a sequence of distinct instructions that are always executed linearly from beginning to end with no branching into or out of the middle of the BB. The semantics of a BB are the composition of the semantics of each instruction in the order they would be executed. The instructions of a BB are not required to be contiguous in memory, although they usually are.

A basic block has a starting address (equivalent to the starting address of its first instruction when its first instruction is known), and a size measured in instructions. A basic block's size in bytes is generally not useful since there is no requirement that the instructions be contiguous in memory. Basic blocks also store the results of various analyses that are run when the block is created.

Basic blocks can either be represented in a partitioner's CFG/AUM, or they can exist in a detached state. Basic blocks in a detached state can be modified directly via BasicBlock methods, but blocks that are attached to the CFG/AUM are frozen. Frozen blocks can still be modified in certain ways, but usually only by going through the Partitioner API that ensures that the CFG/AUM are kept up-to-date. The CFG/AUM will contain at most one basic block per basic block starting address.

If the first instruction of a basic block is unmapped or mapped without execute permission then the basic block is said to be non-existing and will have no instructions. Such blocks point to the special "nonexisting" CFG vertex when they are attached to the control flow graph. If a non-initial instruction of a basic block is unmapped or not executable then the prior instruction becomes the final instruction of the block and the block's successor will be a vertex for a non-existing basic block which in turn points to the special "nonexisting" CFG vertex. In other words, a basic block will either entirely exist or entirely not exist (there are no basic blocks containing instructions that just run off the end of memory).

If a basic block encounters an address which is mapped with execute permission and properly aligned but the instruction provider is unable to disassemble an instruction at that address, then the instruction provider must provide an "unknown" instruction. Since an "unknown" instruction always has indeterminate edges it becomes the final instruction of the basic block, and the CFG will contain an edge to the special "indeterminate" vertex. Blocks that have improper alignment are treated as if they started at an unmapped or non-executable address.

Data Blocks

A data block is an address and data type anywhere in memory. A data block can be attached to a CFG/AUM, or exist in a detached state. They are attached to the CFG/AUM by virtue of being owned by one or more basic blocks or functions that are attached to the CFG/AUM. Data blocks such as function alignment are typically attached to a function, while data blocks such as branch tables are typically attached to a basic block. A data block may be attached to more than one function and/or basic block, and the CFG/AUM is able to support multiple data blocks having the same address.

Functions

A function is a collection of one or more basic blocks related by control flow edges. One basic block is special in that it serves as the only entry point to this function for inter-function edges (usually function calls). Any edge that leaves the function must enter a different function's entry block. These two rules can be relaxed, but result in a control flow graph that is not proper for a function–most of ROSE's analyses work only on proper control flow graphs.

Functions can either be represented in a partitioner's CFG/AUM, or they can exist in a detached state. Functions in a detached state can have their basic block and data block ownership adjusted, otherwise the function exists in a frozen state to prevent the CFG/AUM from becoming out of date with respect to the function. Frozen functions can only be modified through the Partitioner API so that the CFG/AUM can be updated. When a function becomes detached from the CFG it thaws out again and can be modified. The CFG/AUM will contain at most one function per function starting address.

Control Flow Graph

At any point in time, the partitioner's control flow graph represents those basic blocks (and indirectly the instructions) that have been selected to appear in the final abstract syntax tree (AST). This is a subset of all basic blocks ever created, and a subset of the instructions known to the instruction provider. Note: a final pass during AST construction might join certain CFG vertices into a single SgAsmBlock under certain circumstances. The CFG is of type ControlFlowGraph, a subset of Sawyer::Container::Graph whose vertices and edges both carry information: the vertices are of type ControlFlowGraph::CfgVertex and the edges are of type ControlFlowGraph::CfgEdge.

Most CFG vertices represent basic blocks (vertex type V_BASIC_BLOCK) and either point to a non-null BasicBlock having at least one discovered instruction, or to a null basic block. A "placeholder" usually refers to a vertex with a null basic block pointer (but not necessarily), and "basic block" refers to a vertex with a non-null pointer. Therefore the set of placeholders is a superset of the set of basic blocks. A "pure placeholder" is a basic block vertex with a null pointer. Any of the V_BASIC_BLOCK vertices can also point to an optional function that owns the block.

Placeholders with null basic block pointers represent one of two situations: either the partitioner has not attempted to discover an instruction at the basic block starting address, or the partitioner has tried but failed due to the address being non-executable or not mapped. The two cases are distinguished from each other by whether the vertex's only outgoing edge points to the special "undiscovered" or "nonexisting" vertex. Pure placeholders always have exactly this one outgoing edge.

The CFG also has other special (non-basic block) vertices each represented by its own vertex type. Altogether, the special vertices, by their type, are:

CFG edges are also labeled with type information:

Address Usage Map

The address usage map (AUM) is similar to the control flow graph in that they both represent the same set of instructions, basic blocks, and functions. But where the CFG organizes them according to their control flow relationships, the AUM organizes them by the memory addresses they occupy. The partitioner ensures that both data structures are always synchronized with each other from the perspective of an outside viewer (including user callbacks).

The AUM can answer queries about what instructions, basic blocks, data blocks, or functions are contained within, begin within, span, or overlap an address or address interval. For small intervals the results can usually be obtained in logorithmic time, but querying large intervals can be slower.

Prioritizing Work

The partitioner itself does not prioritize work or perform work automatically–it must be told what to do, usually through an engine. However, the partitioner does have certain features that facilitate prioritization at higher layers. Namely, it has the CFG with special vertices, and AUM and a whole set of queries, an address map that can be traversed, and user-defined callbacks that are notified for certain CFG changes.

The base implementation of Engine uses these features to prioritize its work and can be consulted as an example.

Provisional Detection

(This section is a placeholder for an idea that is not yet implemented.)

Sometimes one wants to ask the question "does a recursive disassembly starting at some particular address look reasonable?" and avoid making any changes if it doesn't. This can be accomplished by creating a second "provisional" partitioner which is either in its initial empty state or a copy of the current partitioner, running the query, and examining the result. If the result looks reasonable, then the provisional partitioner can be assigned to the current partitioner.

When a partitioner is copied (by the copy constructor or by assignment) it makes a new copy of the CFG and the address mapping. The new copy points to the same instructions and basic blocks as the original, but since both of these items are constant (other than basic block analysis results) they are sharing read-only information.

The cost of copying the CFG is linear in the number of vertices and edges. The cost of copying the address map is linear in the number of instructions (or slightly more if instructions overlap).

A more efficient mechanism might be developed in the future.

Function Boundary Determination

(This section is a placeholder for future documentation).

Frequenctly Asked Questions

Q. Why is this class final?

A. This class represents the low-level operations for partitioning instructions and is responsible for ensuring that certain data structures such as the CFG and AUM are always consistent. The class is final to guarantee these invariants. Its behavior can only be modified by registering callbacks. High-level behavior is implemented above this class such as in module functions (various Module*.h files) or engines derived from the Engine class. Additional data can be attached to a partitioner via attributes (see Attribute).

Definition at line 293 of file Partitioner.h.

#include <Rose/BinaryAnalysis/Partitioner2/Partitioner.h>

Inheritance diagram for Rose::BinaryAnalysis::Partitioner2::Partitioner:
Inheritance graph
[legend]
Collaboration diagram for Rose::BinaryAnalysis::Partitioner2::Partitioner:
Collaboration graph
[legend]

Classes

struct  Thunk
 Represents information about a thunk. More...
 

Public Types

typedef Sawyer::Callbacks< CfgAdjustmentCallback::PtrCfgAdjustmentCallbacks
 See cfgAdjustmentCallbacks. More...
 
typedef Sawyer::Callbacks< BasicBlockCallbackPtrBasicBlockCallbacks
 See basicBlockCallbacks. More...
 
typedef std::vector< FunctionPrologueMatcherPtrFunctionPrologueMatchers
 See functionPrologueMatchers. More...
 
typedef std::vector< FunctionPaddingMatcherPtrFunctionPaddingMatchers
 See functionPaddingMatchers. More...
 
typedef Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
 Map address to name. More...
 
using Ptr = PartitionerPtr
 Shared-ownership pointer.
 
using ConstPtr = PartitionerConstPtr
 Shared-ownership pointer.
 
- Public Types inherited from Sawyer::Attribute::Storage<>
typedef SynchronizationTraits< Sawyer::SingleThreadedTagSync
 

Public Member Functions

void saveAsRbaFile (const boost::filesystem::path &name, SerialIo::Format fmt) const
 Save this partitioner as an RBA file. More...
 
 Partitioner (const Partitioner &)
 
Partitioneroperator= (const Partitioner &)
 
bool isDefaultConstructed () const
 Return true if this is a default constructed partitioner. More...
 
void clear ()
 Reset CFG/AUM to initial state. More...
 
MemoryMap::Ptr memoryMap () const
 Returns the memory map. More...
 
bool addressIsExecutable (rose_addr_t) const
 Returns true if address is executable. More...
 
void configureInsnUnparser (const Unparser::BasePtr &) const
 Configure the single-instruction unparser. More...
 
void configureInsnPlainUnparser (const Unparser::BasePtr &) const
 Configure plain single-instruction unparser. More...
 
std::string unparsePlain (SgAsmInstruction *) const
 Unparse an instruction in a plain way. More...
 
size_t nBytes () const
 Returns the number of bytes represented by the CFG. More...
 
const ControlFlowGraphcfg () const
 Returns the control flow graph. More...
 
const AddressUsageMapaum () const
 Returns the address usage map. More...
 
AddressUsageMap aum (const FunctionPtr &) const
 Returns the address usage map for a single function. More...
 
std::vector< AddressUserusers (rose_addr_t) const
 Entities that exist at a particular address. More...
 
std::set< rose_addr_t > ghostSuccessors () const
 Determine all ghost successors in the control flow graph. More...
 
size_t nInstructions () const
 Returns the number of instructions attached to the CFG/AUM. More...
 
ControlFlowGraph::ConstVertexIterator instructionVertex (rose_addr_t insnVa) const
 Returns the CFG vertex containing specified instruction. More...
 
std::vector< SgAsmInstruction * > instructionsOverlapping (const AddressInterval &) const
 Returns instructions that overlap with specified address interval. More...
 
std::vector< SgAsmInstruction * > instructionsSpanning (const AddressInterval &) const
 Returns instructions that span an entire address interval. More...
 
std::vector< SgAsmInstruction * > instructionsContainedIn (const AddressInterval &) const
 Returns instructions that are fully contained in an address interval. More...
 
AddressInterval instructionExtent (SgAsmInstruction *) const
 Returns the address interval for an instruction. More...
 
SgAsmInstructiondiscoverInstruction (rose_addr_t startVa) const
 Discover an instruction. More...
 
CrossReferences instructionCrossReferences (const AddressIntervalSet &restriction) const
 Cross references. More...
 
size_t nPlaceholders () const
 Returns the number of basic basic block placeholders in the CFG. More...
 
bool placeholderExists (rose_addr_t startVa) const
 Determines whether a basic block placeholder exists in the CFG. More...
 
ControlFlowGraph::VertexIterator insertPlaceholder (rose_addr_t startVa)
 Insert a basic-block placeholder. More...
 
void basicBlockDropSemantics () const
 Immediately drop semantic information for all attached basic blocks. More...
 
size_t nBasicBlocks () const
 Returns the number of basic blocks attached to the CFG/AUM. More...
 
std::vector< BasicBlockPtrbasicBlocks () const
 Returns all basic blocks attached to the CFG. More...
 
std::vector< BasicBlockPtrbasicBlocksOverlapping (const AddressInterval &) const
 Returns basic blocks that overlap with specified address interval. More...
 
std::vector< BasicBlockPtrbasicBlocksSpanning (const AddressInterval &) const
 Returns basic blocks that span an entire address interval. More...
 
std::vector< BasicBlockPtrbasicBlocksContainedIn (const AddressInterval &) const
 Returns basic blocks that are fully contained in an address interval. More...
 
BasicBlockPtr basicBlockContainingInstruction (rose_addr_t insnVa) const
 Returns the basic block that contains a specific instruction address. More...
 
AddressIntervalSet basicBlockInstructionExtent (const BasicBlockPtr &) const
 Returns the addresses used by basic block instructions. More...
 
AddressIntervalSet basicBlockDataExtent (const BasicBlockPtr &) const
 Returns the addresses used by basic block data. More...
 
ControlFlowGraph::VertexIterator truncateBasicBlock (const ControlFlowGraph::ConstVertexIterator &basicBlock, SgAsmInstruction *insn)
 Truncate an attached basic-block. More...
 
BasicBlockSuccessors basicBlockSuccessors (const BasicBlockPtr &, Precision::Level precision=Precision::HIGH) const
 Determine successors for a basic block. More...
 
std::vector< rose_addr_t > basicBlockConcreteSuccessors (const BasicBlockPtr &, bool *isComplete=NULL) const
 Determines concrete successors for a basic block. More...
 
std::set< rose_addr_t > basicBlockGhostSuccessors (const BasicBlockPtr &) const
 Determine ghost successors for a basic block. More...
 
bool basicBlockIsFunctionCall (const BasicBlockPtr &, Precision::Level precision=Precision::HIGH) const
 Determine if a basic block looks like a function call. More...
 
bool basicBlockIsFunctionReturn (const BasicBlockPtr &) const
 Determine if a basic block looks like a function return. More...
 
bool basicBlockPopsStack (const BasicBlockPtr &) const
 Determine if the basic block pops at least one byte from the stack. More...
 
void basicBlockMayReturnReset () const
 Clear all may-return properties. More...
 
size_t nDataBlocks () const
 Returns the number of data blocks attached to the CFG/AUM. More...
 
DataBlockPtr dataBlockExists (const DataBlockPtr &) const
 Determine if a data block or its equivalent is attached to the CFG/AUM. More...
 
DataBlockPtr findBestDataBlock (const AddressInterval &) const
 Find an existing data block. More...
 
DataBlockPtr attachDataBlock (const DataBlockPtr &)
 Attach a data block to the CFG/AUM. More...
 
void detachDataBlock (const DataBlockPtr &)
 Detaches a data block from the CFG/AUM. More...
 
DataBlockPtr attachDataBlockToFunction (const DataBlockPtr &, const FunctionPtr &)
 Attach a data block to an attached or detached function. More...
 
DataBlockPtr attachDataBlockToBasicBlock (const DataBlockPtr &, const BasicBlockPtr &)
 Attach a data block to a basic block. More...
 
std::vector< DataBlockPtrdataBlocksOverlapping (const AddressInterval &) const
 Returns data blocks that overlap with specified address interval. More...
 
std::vector< DataBlockPtrdataBlocksSpanning (const AddressInterval &) const
 Returns data blocks that span an entire address interval. More...
 
std::vector< DataBlockPtrdataBlocksContainedIn (const AddressInterval &) const
 Returns data blocks that are fully contained in an address interval. More...
 
AddressInterval dataBlockExtent (const DataBlockPtr &) const
 Returns the addresses used by a data block. More...
 
std::vector< DataBlockPtrdataBlocks () const
 Returns the list of all attached data blocks. More...
 
size_t nFunctions () const
 Returns the number of functions attached to the CFG/AUM. More...
 
std::vector< FunctionPtrfunctions () const
 All functions attached to the CFG/AUM. More...
 
std::vector< FunctionPtrfunctionsOverlapping (const AddressInterval &) const
 Returns functions that overlap with specified address interval. More...
 
std::vector< FunctionPtrfunctionsSpanning (const AddressInterval &) const
 Returns functions that span an entire address interval. More...
 
std::vector< FunctionPtrfunctionsContainedIn (const AddressInterval &) const
 Returns functions that are fully contained in an address interval. More...
 
FunctionPtr attachOrMergeFunction (const FunctionPtr &)
 Attaches or merges a function into the CFG/AUM. More...
 
void detachFunction (const FunctionPtr &)
 Detaches a function from the CFG/AUM. More...
 
std::vector< FunctionPtrdiscoverCalledFunctions () const
 Scans the CFG to find function calls. More...
 
std::vector< FunctionPtrdiscoverFunctionEntryVertices () const
 Scans the CFG to find function entry basic blocks. More...
 
Sawyer::Optional< ThunkfunctionIsThunk (const FunctionPtr &) const
 True if function is a thunk. More...
 
void discoverFunctionBasicBlocks (const FunctionPtr &function) const
 Adds basic blocks to a function. More...
 
std::set< rose_addr_t > functionGhostSuccessors (const FunctionPtr &) const
 Returns ghost successors for a single function. More...
 
FunctionCallGraph functionCallGraph (AllowParallelEdges::Type allowParallelEdges) const
 Returns a function call graph. More...
 
InstructionSemantics::BaseSemantics::SValuePtr functionStackDelta (const FunctionPtr &function) const
 Stack delta analysis for one function. More...
 
void allFunctionStackDelta () const
 Compute stack delta analysis for all functions. More...
 
Sawyer::Optional< bool > functionOptionalMayReturn (const FunctionPtr &function) const
 May-return analysis for one function. More...
 
void allFunctionMayReturn () const
 Compute may-return analysis for all functions. More...
 
bool functionIsNoop (const FunctionPtr &) const
 Function no-op analysis. More...
 
void allFunctionIsNoop () const
 Analyze all functions for whether they are effectivly no-ops. More...
 
std::set< rose_addr_t > functionDataFlowConstants (const FunctionPtr &) const
 Find constants in function using data-flow. More...
 
DataBlockPtr matchFunctionPadding (const FunctionPtr &)
 Finds function padding. More...
 
void dumpCfg (std::ostream &, const std::string &prefix="", bool showBlocks=true, bool computeProperties=true) const
 Output the control flow graph. More...
 
void cfgGraphViz (std::ostream &, const AddressInterval &restrict=AddressInterval::whole(), bool showNeighbors=true) const
 Output CFG as GraphViz. More...
 
void expandIndeterminateCalls ()
 Expands indeterminate function calls. More...
 
void updateProgress (const std::string &phase, double completion) const
 Update partitioner with a new progress report. More...
 
void showStatistics () const
 Print some partitioner performance statistics. More...
 
void checkConsistency () const
 
SgAsmGenericSectionelfGot (SgAsmElfFileHeader *)
 Find the ELF global offset table and save its address. More...
 
Sawyer::Optional< rose_addr_t > elfGotVa () const
 Returns a previously cached ELF GOT address. More...
 
SmtSolverPtr smtSolver () const
 SMT solver. More...
 
InstructionSemantics::BaseSemantics::DispatcherPtr newDispatcher (const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &) const
 Obtain a new instruction semantics dispatcher. More...
 
Configurationconfiguration ()
 Property: Configuration information. More...
 
const Configurationconfiguration () const
 Property: Configuration information. More...
 
InstructionProviderinstructionProvider ()
 Returns the instruction provider. More...
 
const InstructionProviderinstructionProvider () const
 Returns the instruction provider. More...
 
SgAsmInterpretationinterpretation () const
 Property: Interpretation corresponding to the memory map.
 
void interpretation (SgAsmInterpretation *)
 Property: Interpretation corresponding to the memory map.
 
Unparser::BasePtr unparser () const
 Returns an unparser. More...
 
void unparser (const Unparser::BasePtr &)
 Returns an unparser. More...
 
Unparser::BasePtr insnUnparser () const
 Returns an unparser. More...
 
void insnUnparser (const Unparser::BasePtr &)
 Returns an unparser. More...
 
std::string unparse (SgAsmInstruction *) const
 Unparse some entity. More...
 
void unparse (std::ostream &, SgAsmInstruction *) const
 Unparse some entity. More...
 
void unparse (std::ostream &, const BasicBlockPtr &) const
 Unparse some entity. More...
 
void unparse (std::ostream &, const DataBlockPtr &) const
 Unparse some entity. More...
 
void unparse (std::ostream &, const FunctionPtr &) const
 Unparse some entity. More...
 
void unparse (std::ostream &) const
 Unparse some entity. More...
 
ControlFlowGraph::VertexIterator undiscoveredVertex ()
 Returns the special "undiscovered" vertex. More...
 
ControlFlowGraph::ConstVertexIterator undiscoveredVertex () const
 Returns the special "undiscovered" vertex. More...
 
ControlFlowGraph::VertexIterator indeterminateVertex ()
 Returns the special "indeterminate" vertex. More...
 
ControlFlowGraph::ConstVertexIterator indeterminateVertex () const
 Returns the special "indeterminate" vertex. More...
 
ControlFlowGraph::VertexIterator nonexistingVertex ()
 Returns the special "non-existing" vertex. More...
 
ControlFlowGraph::ConstVertexIterator nonexistingVertex () const
 Returns the special "non-existing" vertex. More...
 
bool isEdgeIntraProcedural (ControlFlowGraph::ConstEdgeIterator edge, const FunctionPtr &) const
 Determine if an edge is intra-procedural. More...
 
bool isEdgeIntraProcedural (const ControlFlowGraph::Edge &edge, const FunctionPtr &) const
 Determine if an edge is intra-procedural. More...
 
bool isEdgeIntraProcedural (ControlFlowGraph::ConstEdgeIterator edge) const
 Determine if an edge is intra-procedural. More...
 
bool isEdgeIntraProcedural (const ControlFlowGraph::Edge &edge) const
 Determine if an edge is intra-procedural. More...
 
bool isEdgeInterProcedural (ControlFlowGraph::ConstEdgeIterator edge) const
 Determine if an edge is inter-procedural. More...
 
bool isEdgeInterProcedural (ControlFlowGraph::ConstEdgeIterator edge, const FunctionPtr &sourceFunction) const
 Determine if an edge is inter-procedural. More...
 
bool isEdgeInterProcedural (ControlFlowGraph::ConstEdgeIterator edge, const FunctionPtr &sourceFunction, const FunctionPtr &targetFunction) const
 Determine if an edge is inter-procedural. More...
 
bool isEdgeInterProcedural (const ControlFlowGraph::Edge &edge) const
 Determine if an edge is inter-procedural. More...
 
bool isEdgeInterProcedural (const ControlFlowGraph::Edge &edge, const FunctionPtr &sourceFunction) const
 Determine if an edge is inter-procedural. More...
 
bool isEdgeInterProcedural (const ControlFlowGraph::Edge &edge, const FunctionPtr &sourceFunction, const FunctionPtr &targetFunction) const
 Determine if an edge is inter-procedural. More...
 
AddressUser instructionExists (rose_addr_t startVa) const
 Determines whether an instruction is attached to the CFG/AUM. More...
 
AddressUser instructionExists (SgAsmInstruction *insn) const
 Determines whether an instruction is attached to the CFG/AUM. More...
 
ControlFlowGraph::VertexIterator findPlaceholder (rose_addr_t startVa)
 Find the CFG vertex for a basic block placeholder. More...
 
ControlFlowGraph::ConstVertexIterator findPlaceholder (rose_addr_t startVa) const
 Find the CFG vertex for a basic block placeholder. More...
 
BasicBlockPtr erasePlaceholder (const ControlFlowGraph::ConstVertexIterator &placeholder)
 Remove a basic block placeholder from the CFG/AUM. More...
 
BasicBlockPtr erasePlaceholder (rose_addr_t startVa)
 Remove a basic block placeholder from the CFG/AUM. More...
 
bool basicBlockSemanticsAutoDrop () const
 Property: Automatically drop semantics for attached basic blocks. More...
 
void basicBlockSemanticsAutoDrop (bool)
 Property: Automatically drop semantics for attached basic blocks. More...
 
BasicBlockPtr basicBlockExists (rose_addr_t startVa) const
 Determines whether a discovered basic block exists in the CFG/AUM. More...
 
BasicBlockPtr basicBlockExists (const BasicBlockPtr &) const
 Determines whether a discovered basic block exists in the CFG/AUM. More...
 
BasicBlockPtr detachBasicBlock (rose_addr_t startVa)
 Detach a basic block from the CFG/AUM. More...
 
BasicBlockPtr detachBasicBlock (const BasicBlockPtr &basicBlock)
 Detach a basic block from the CFG/AUM. More...
 
BasicBlockPtr detachBasicBlock (const ControlFlowGraph::ConstVertexIterator &placeholder)
 Detach a basic block from the CFG/AUM. More...
 
void attachBasicBlock (const BasicBlockPtr &)
 Attach a basic block to the CFG/AUM. More...
 
void attachBasicBlock (const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlockPtr &)
 Attach a basic block to the CFG/AUM. More...
 
BasicBlockPtr discoverBasicBlock (rose_addr_t startVa) const
 Discover instructions for a detached basic block. More...
 
BasicBlockPtr discoverBasicBlock (const ControlFlowGraph::ConstVertexIterator &placeholder) const
 Discover instructions for a detached basic block. More...
 
InstructionSemantics::BaseSemantics::SValuePtr basicBlockStackDeltaIn (const BasicBlockPtr &, const FunctionPtr &function) const
 Return the stack delta expression. More...
 
InstructionSemantics::BaseSemantics::SValuePtr basicBlockStackDeltaOut (const BasicBlockPtr &, const FunctionPtr &function) const
 Return the stack delta expression. More...
 
void forgetStackDeltas () const
 Clears all cached stack deltas. More...
 
void forgetStackDeltas (const FunctionPtr &) const
 Clears all cached stack deltas. More...
 
size_t stackDeltaInterproceduralLimit () const
 Property: max depth for inter-procedural stack delta analysis. More...
 
void stackDeltaInterproceduralLimit (size_t)
 Property: max depth for inter-procedural stack delta analysis. More...
 
Sawyer::Optional< bool > basicBlockOptionalMayReturn (const BasicBlockPtr &) const
 Determine if part of the CFG can pop the top stack frame. More...
 
Sawyer::Optional< bool > basicBlockOptionalMayReturn (const ControlFlowGraph::ConstVertexIterator &) const
 Determine if part of the CFG can pop the top stack frame. More...
 
FunctionPtr functionExists (rose_addr_t entryVa) const
 Determines whether a function exists in the CFG/AUM. More...
 
FunctionPtr functionExists (const BasicBlockPtr &entryBlock) const
 Determines whether a function exists in the CFG/AUM. More...
 
FunctionPtr functionExists (const FunctionPtr &function) const
 Determines whether a function exists in the CFG/AUM. More...
 
AddressIntervalSet functionExtent (const FunctionPtr &) const
 Returns the addresses used by a function. More...
 
void functionExtent (const FunctionPtr &function, AddressIntervalSet &retval) const
 Returns the addresses used by a function. More...
 
AddressIntervalSet functionBasicBlockExtent (const FunctionPtr &function) const
 Returns the addresses used by a function. More...
 
void functionBasicBlockExtent (const FunctionPtr &function, AddressIntervalSet &retval) const
 Returns the addresses used by a function. More...
 
AddressIntervalSet functionDataBlockExtent (const FunctionPtr &function) const
 Returns the addresses used by a function. More...
 
void functionDataBlockExtent (const FunctionPtr &function, AddressIntervalSet &retval) const
 Returns the addresses used by a function. More...
 
size_t attachFunction (const FunctionPtr &)
 Attaches a function to the CFG/AUM. More...
 
size_t attachFunctions (const Functions &)
 Attaches a function to the CFG/AUM. More...
 
size_t attachFunctionBasicBlocks (const Functions &)
 Create placeholders for function basic blocks. More...
 
size_t attachFunctionBasicBlocks (const FunctionPtr &)
 Create placeholders for function basic blocks. More...
 
std::vector< FunctionPtrfunctionsOwningBasicBlock (const ControlFlowGraph::Vertex &, bool doSort=true) const
 Finds functions that own the specified basic block. More...
 
std::vector< FunctionPtrfunctionsOwningBasicBlock (const ControlFlowGraph::ConstVertexIterator &, bool doSort=true) const
 Finds functions that own the specified basic block. More...
 
std::vector< FunctionPtrfunctionsOwningBasicBlock (rose_addr_t bblockVa, bool doSort=true) const
 Finds functions that own the specified basic block. More...
 
std::vector< FunctionPtrfunctionsOwningBasicBlock (const BasicBlockPtr &, bool doSort=true) const
 Finds functions that own the specified basic block. More...
 
template<class Container >
std::vector< FunctionPtrfunctionsOwningBasicBlocks (const Container &bblocks) const
 Finds functions that own the specified basic block. More...
 
const CallingConvention::AnalysisfunctionCallingConvention (const FunctionPtr &) const
 Calling convention analysis for one function. More...
 
const CallingConvention::AnalysisfunctionCallingConvention (const FunctionPtr &, const CallingConvention::Definition::Ptr &dflt) const
 Calling convention analysis for one function. More...
 
void allFunctionCallingConvention () const
 Compute calling conventions for all functions. More...
 
void allFunctionCallingConvention (const CallingConvention::Definition::Ptr &dflt) const
 Compute calling conventions for all functions. More...
 
CallingConvention::Dictionary functionCallingConventionDefinitions (const FunctionPtr &) const
 Return list of matching calling conventions. More...
 
CallingConvention::Dictionary functionCallingConventionDefinitions (const FunctionPtr &, const CallingConvention::Definition::Ptr &) const
 Return list of matching calling conventions. More...
 
void allFunctionCallingConventionDefinition () const
 Analyzes calling conventions and saves results. More...
 
void allFunctionCallingConventionDefinition (const CallingConvention::Definition::Ptr &) const
 Analyzes calling conventions and saves results. More...
 
void fixInterFunctionEdges ()
 Adjust inter-function edge types. More...
 
void fixInterFunctionEdge (const ControlFlowGraph::ConstEdgeIterator &)
 Adjust inter-function edge types. More...
 
void forgetFunctionIsNoop () const
 Clears cached function no-op analysis results. More...
 
void forgetFunctionIsNoop (const FunctionPtr &) const
 Clears cached function no-op analysis results. More...
 
CfgAdjustmentCallbackscfgAdjustmentCallbacks ()
 List of all callbacks invoked when the CFG is adjusted. More...
 
const CfgAdjustmentCallbackscfgAdjustmentCallbacks () const
 List of all callbacks invoked when the CFG is adjusted. More...
 
BasicBlockCallbacksbasicBlockCallbacks ()
 Callbacks for adjusting basic block during discovery. More...
 
const BasicBlockCallbacksbasicBlockCallbacks () const
 Callbacks for adjusting basic block during discovery. More...
 
FunctionPrologueMatchersfunctionPrologueMatchers ()
 Ordered list of function prologue matchers. More...
 
const FunctionPrologueMatchersfunctionPrologueMatchers () const
 Ordered list of function prologue matchers. More...
 
std::vector< FunctionPtrnextFunctionPrologue (rose_addr_t startVa)
 Finds the next function by searching for a function prologue. More...
 
std::vector< FunctionPtrnextFunctionPrologue (rose_addr_t startVa, rose_addr_t &lastSearchedVa)
 Finds the next function by searching for a function prologue. More...
 
FunctionPaddingMatchersfunctionPaddingMatchers ()
 Ordered list of function padding matchers. More...
 
const FunctionPaddingMatchersfunctionPaddingMatchers () const
 Ordered list of function padding matchers. More...
 
Progress::Ptr progress () const
 Property: How to report progress. More...
 
void progress (const Progress::Ptr &)
 Property: How to report progress. More...
 
const BasePartitionerSettingssettings () const
 Partitioner settings. More...
 
void settings (const BasePartitionerSettings &)
 Partitioner settings. More...
 
void enableSymbolicSemantics (bool=true)
 Use or not use symbolic semantics. More...
 
void disableSymbolicSemantics ()
 Use or not use symbolic semantics. More...
 
bool usingSymbolicSemantics () const
 Use or not use symbolic semantics. More...
 
void autoAddCallReturnEdges (bool)
 Property: Insert (or not) function call return edges. More...
 
bool autoAddCallReturnEdges () const
 Property: Insert (or not) function call return edges. More...
 
void assumeFunctionsReturn (bool)
 Property: Assume (or not) that function calls return. More...
 
bool assumeFunctionsReturn () const
 Property: Assume (or not) that function calls return. More...
 
void addressName (rose_addr_t, const std::string &)
 Property: Name for address. More...
 
const std::string & addressName (rose_addr_t) const
 Property: Name for address. More...
 
const AddressNameMapaddressNames () const
 Property: Name for address. More...
 
const SourceLocationssourceLocations () const
 Property: Source locations. More...
 
SourceLocationssourceLocations ()
 Property: Source locations. More...
 
void sourceLocations (const SourceLocations &)
 Property: Source locations. More...
 
bool checkingCallBranch () const
 Property: Whether to look for function calls used as branches. More...
 
void checkingCallBranch (bool)
 Property: Whether to look for function calls used as branches. More...
 
SemanticMemoryParadigm semanticMemoryParadigm () const
 Property: Whether to use map- or list-based memory states. More...
 
void semanticMemoryParadigm (SemanticMemoryParadigm)
 Property: Whether to use map- or list-based memory states. More...
 
InstructionSemantics::BaseSemantics::RiscOperatorsPtr newOperators () const
 Obtain new RiscOperators. More...
 
InstructionSemantics::BaseSemantics::RiscOperatorsPtr newOperators (SemanticMemoryParadigm) const
 Obtain new RiscOperators. More...
 
- Public Member Functions inherited from Sawyer::SharedObject
 SharedObject ()
 Default constructor. More...
 
 SharedObject (const SharedObject &)
 Copy constructor. More...
 
virtual ~SharedObject ()
 Virtual destructor. More...
 
SharedObjectoperator= (const SharedObject &)
 Assignment. More...
 
- Public Member Functions inherited from Sawyer::SharedFromThis< Partitioner >
SharedPointer< Partitioner > sharedFromThis ()
 Create a shared pointer from this. More...
 
SharedPointer< const Partitioner > sharedFromThis () const
 Create a shared pointer from this. More...
 
- Public Member Functions inherited from Sawyer::Attribute::Storage<>
 Storage ()
 Default constructor. More...
 
 Storage (const Storage &other)
 Copy constructor. More...
 
Storageoperator= (const Storage &other)
 Assignment operator. More...
 
bool attributeExists (Id id) const
 Check attribute existence. More...
 
void eraseAttribute (Id id)
 Erase an attribute. More...
 
void clearAttributes ()
 Erase all attributes. More...
 
void setAttribute (Id id, const T &value)
 Store an attribute. More...
 
bool setAttributeMaybe (Id id, const T &value)
 Store an attribute if not already present. More...
 
getAttribute (Id id) const
 Get an attribute that is known to exist. More...
 
attributeOrElse (Id id, const T &dflt) const
 Return an attribute or a specified value. More...
 
attributeOrDefault (Id id) const
 Return an attribute or a default-constructed value. More...
 
Sawyer::Optional< T > optionalAttribute (Id id) const
 Return the attribute as an optional value. More...
 
size_t nAttributes () const
 Number of attributes stored. More...
 
std::vector< IdattributeIds () const
 Returns ID numbers for all IDs stored in this container. More...
 

Static Public Member Functions

static Ptr instance ()
 Default allocating constructor. More...
 
static Ptr instance (const Disassembler::BasePtr &, const MemoryMap::Ptr &)
 Construct a partitioner. More...
 
static PartitionerPtr instanceFromRbaFile (const boost::filesystem::path &, SerialIo::Format=SerialIo::BINARY)
 Construct a partitioner by loading it and an AST from a file. More...
 
static std::string vertexNameEnd (const ControlFlowGraph::Vertex &)
 Name of last instruction in vertex. More...
 
static std::string basicBlockName (const BasicBlockPtr &)
 Name of a basic block. More...
 
static std::string dataBlockName (const DataBlockPtr &)
 Name of a data block. More...
 
static std::string functionName (const FunctionPtr &)
 Name of a function. More...
 
std::string vertexName (const ControlFlowGraph::ConstVertexIterator &) const
 Name of a vertex. More...
 
static std::string vertexName (const ControlFlowGraph::Vertex &)
 Name of a vertex. More...
 
std::string edgeNameSrc (const ControlFlowGraph::ConstEdgeIterator &) const
 Name of an incoming edge. More...
 
static std::string edgeNameSrc (const ControlFlowGraph::Edge &)
 Name of an incoming edge. More...
 
std::string edgeNameDst (const ControlFlowGraph::ConstEdgeIterator &) const
 Name of an outgoing edge. More...
 
static std::string edgeNameDst (const ControlFlowGraph::Edge &)
 Name of an outgoing edge. More...
 
std::string edgeName (const ControlFlowGraph::ConstEdgeIterator &) const
 Name of an edge. More...
 
static std::string edgeName (const ControlFlowGraph::Edge &)
 Name of an edge. More...
 

Member Typedef Documentation

See cfgAdjustmentCallbacks.

Definition at line 315 of file Partitioner.h.

See basicBlockCallbacks.

Definition at line 316 of file Partitioner.h.

See functionPrologueMatchers.

Definition at line 317 of file Partitioner.h.

See functionPaddingMatchers.

Definition at line 318 of file Partitioner.h.

Map address to name.

Definition at line 329 of file Partitioner.h.

Member Function Documentation

static Ptr Rose::BinaryAnalysis::Partitioner2::Partitioner::instance ( )
static

Default allocating constructor.

The default constructor does not produce a usable partitioner, but is convenient when one needs to pass a default partitioner by value or reference.

static Ptr Rose::BinaryAnalysis::Partitioner2::Partitioner::instance ( const Disassembler::BasePtr ,
const MemoryMap::Ptr  
)
static

Construct a partitioner.

The partitioner must be provided with a disassembler, which also determines the specimen's target architecture, and a memory map that represents a (partially) loaded instance of the specimen (i.e., a process).

static PartitionerPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::instanceFromRbaFile ( const boost::filesystem::path &  ,
SerialIo::Format  = SerialIo::BINARY 
)
static

Construct a partitioner by loading it and an AST from a file.

The specified RBA file is opened and read to create a new Partitioner object and associated AST. The partition function also understands how to open RBA files.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::saveAsRbaFile ( const boost::filesystem::path &  name,
SerialIo::Format  fmt 
) const

Save this partitioner as an RBA file.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isDefaultConstructed ( ) const

Return true if this is a default constructed partitioner.

Most methods won't work when applied to a default-constructed partitioner since it has no way to obtain instructions and it has an empty memory map.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::clear ( )

Reset CFG/AUM to initial state.

Configuration& Rose::BinaryAnalysis::Partitioner2::Partitioner::configuration ( )

Property: Configuration information.

The configuration holds information about functions and basic blocks which is used to provide default values and such.

Thread safety: Not thread safe.

const Configuration& Rose::BinaryAnalysis::Partitioner2::Partitioner::configuration ( ) const

Property: Configuration information.

The configuration holds information about functions and basic blocks which is used to provide default values and such.

Thread safety: Not thread safe.

InstructionProvider& Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionProvider ( )

Returns the instruction provider.

Thread safety: Not thread safe.

const InstructionProvider& Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionProvider ( ) const

Returns the instruction provider.

Thread safety: Not thread safe.

MemoryMap::Ptr Rose::BinaryAnalysis::Partitioner2::Partitioner::memoryMap ( ) const

Returns the memory map.

It is generally unwise to make extensive changes to a memory map after the partitioner has started using it, because that means that any instructions or data obtained earlier from the map might not be an accurate representation of memory anymore.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::addressIsExecutable ( rose_addr_t  ) const

Returns true if address is executable.

Thread safety: Not thread safe.

Unparser::BasePtr Rose::BinaryAnalysis::Partitioner2::Partitioner::unparser ( ) const

Returns an unparser.

This unparser is initiallly a copy of the one provided by the disassembler, but it can be reset to something else if desired. This is the unparser used by the unparse method for the partitioner as a whole, functions, basic blocks, and data blocks. Instructions use the insnUnparser instead.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::unparser ( const Unparser::BasePtr )

Returns an unparser.

This unparser is initiallly a copy of the one provided by the disassembler, but it can be reset to something else if desired. This is the unparser used by the unparse method for the partitioner as a whole, functions, basic blocks, and data blocks. Instructions use the insnUnparser instead.

Thread safety: Not thread safe.

Unparser::BasePtr Rose::BinaryAnalysis::Partitioner2::Partitioner::insnUnparser ( ) const

Returns an unparser.

This unparser is initially a copy of the one provided by the disassembler, and adjusted to be most useful for printing single instructions. By default, it prints the instruction address, mnemonic, and operands but not raw bytes, stack deltas, comments, or anything else.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::insnUnparser ( const Unparser::BasePtr )

Returns an unparser.

This unparser is initially a copy of the one provided by the disassembler, and adjusted to be most useful for printing single instructions. By default, it prints the instruction address, mnemonic, and operands but not raw bytes, stack deltas, comments, or anything else.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::configureInsnUnparser ( const Unparser::BasePtr ) const

Configure the single-instruction unparser.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::configureInsnPlainUnparser ( const Unparser::BasePtr ) const

Configure plain single-instruction unparser.

This configures an unparser for showing just the instruction mnemonic and operands.

std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::unparse ( SgAsmInstruction ) const

Unparse some entity.

Unparses an instruction, basic block, data block, function, or all functions using the unparser returned by unparser (except for instructions, which use the unparser returned by insnUnparser).

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::unparse ( std::ostream &  ,
SgAsmInstruction  
) const

Unparse some entity.

Unparses an instruction, basic block, data block, function, or all functions using the unparser returned by unparser (except for instructions, which use the unparser returned by insnUnparser).

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::unparse ( std::ostream &  ,
const BasicBlockPtr  
) const

Unparse some entity.

Unparses an instruction, basic block, data block, function, or all functions using the unparser returned by unparser (except for instructions, which use the unparser returned by insnUnparser).

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::unparse ( std::ostream &  ,
const DataBlockPtr  
) const

Unparse some entity.

Unparses an instruction, basic block, data block, function, or all functions using the unparser returned by unparser (except for instructions, which use the unparser returned by insnUnparser).

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::unparse ( std::ostream &  ,
const FunctionPtr  
) const

Unparse some entity.

Unparses an instruction, basic block, data block, function, or all functions using the unparser returned by unparser (except for instructions, which use the unparser returned by insnUnparser).

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::unparse ( std::ostream &  ) const

Unparse some entity.

Unparses an instruction, basic block, data block, function, or all functions using the unparser returned by unparser (except for instructions, which use the unparser returned by insnUnparser).

Thread safety: Not thread safe.

std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::unparsePlain ( SgAsmInstruction ) const

Unparse an instruction in a plain way.

This generates a string for the instruction that shows only the mnemonic and arguments.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::nBytes ( ) const

Returns the number of bytes represented by the CFG.

This is a constant time operation.

Thread safety: Not thread safe.

ControlFlowGraph::VertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::undiscoveredVertex ( )

Returns the special "undiscovered" vertex.

The incoming edges for this vertex originate from the basic block placeholder vertices.

Thread safety: Not thread safe.

ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::undiscoveredVertex ( ) const

Returns the special "undiscovered" vertex.

The incoming edges for this vertex originate from the basic block placeholder vertices.

Thread safety: Not thread safe.

ControlFlowGraph::VertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::indeterminateVertex ( )

Returns the special "indeterminate" vertex.

The incoming edges for this vertex originate from basic blocks whose successors are not all concrete values. Each such basic block has only one edge from that block to this vertex.

Indeterminate successors result from, among other things, indirect jump instructions, like x86 "JMP [EAX]".

Thread safety: Not thread safe.

ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::indeterminateVertex ( ) const

Returns the special "indeterminate" vertex.

The incoming edges for this vertex originate from basic blocks whose successors are not all concrete values. Each such basic block has only one edge from that block to this vertex.

Indeterminate successors result from, among other things, indirect jump instructions, like x86 "JMP [EAX]".

Thread safety: Not thread safe.

ControlFlowGraph::VertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::nonexistingVertex ( )

Returns the special "non-existing" vertex.

The incoming edges for this vertex originate from basic blocks that have no instructions but which aren't merely placeholders. Such basic blocks exist when an attempt is made to discover a basic block but its starting address is memory which is not mapped or memory which is mapped without execute permission.

Thread safety: Not thread safe.

ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::nonexistingVertex ( ) const

Returns the special "non-existing" vertex.

The incoming edges for this vertex originate from basic blocks that have no instructions but which aren't merely placeholders. Such basic blocks exist when an attempt is made to discover a basic block but its starting address is memory which is not mapped or memory which is mapped without execute permission.

Thread safety: Not thread safe.

const ControlFlowGraph& Rose::BinaryAnalysis::Partitioner2::Partitioner::cfg ( ) const

Returns the control flow graph.

Returns the global control flow graph. The CFG should not be modified by the caller except through the partitioner's own API.

Thread safety: Not thread safe.

const AddressUsageMap& Rose::BinaryAnalysis::Partitioner2::Partitioner::aum ( ) const

Returns the address usage map.

Returns the global address usage map. The AUM should not be modified by the caller except through the paritioner's own API.

Thread safety: Not thread safe.

AddressUsageMap Rose::BinaryAnalysis::Partitioner2::Partitioner::aum ( const FunctionPtr ) const

Returns the address usage map for a single function.

std::vector<AddressUser> Rose::BinaryAnalysis::Partitioner2::Partitioner::users ( rose_addr_t  ) const

Entities that exist at a particular address.

Returns a vector of AddressUser objects that describe instructions, basic blocks, data blocks, and functions that exist at the specified address.

std::set<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::Partitioner::ghostSuccessors ( ) const

Determine all ghost successors in the control flow graph.

The return value is a list of basic block ghost successors for which no basic block or basic block placeholder exists.

Thread safety: Not thread safe.

See also
basicBlockGhostSuccessors
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeIntraProcedural ( ControlFlowGraph::ConstEdgeIterator  edge,
const FunctionPtr  
) const

Determine if an edge is intra-procedural.

An intra-procedural edge is an edge whose source and target are owned by the same function and which is not part of a function call, function transfer, or function return. This function returns true if the edge is intra-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is not intra-procedural regardless of which functions own the source and target blocks.
  • If a function is specified and that function is listed as an owner of both the source and target blocks, then the edge is intra-procedural.
  • If no function is specified and neither the source nor the target block have any function owners then the edge is intra-procedural.
  • If no function is specified and there exists some function that is an owner of both the source and target blocks then the edge is intra-procedural.
  • Otherwise the edge is not intra-procedural.

When no function is specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeInterProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeIntraProcedural ( const ControlFlowGraph::Edge &  edge,
const FunctionPtr  
) const

Determine if an edge is intra-procedural.

An intra-procedural edge is an edge whose source and target are owned by the same function and which is not part of a function call, function transfer, or function return. This function returns true if the edge is intra-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is not intra-procedural regardless of which functions own the source and target blocks.
  • If a function is specified and that function is listed as an owner of both the source and target blocks, then the edge is intra-procedural.
  • If no function is specified and neither the source nor the target block have any function owners then the edge is intra-procedural.
  • If no function is specified and there exists some function that is an owner of both the source and target blocks then the edge is intra-procedural.
  • Otherwise the edge is not intra-procedural.

When no function is specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeInterProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeIntraProcedural ( ControlFlowGraph::ConstEdgeIterator  edge) const

Determine if an edge is intra-procedural.

An intra-procedural edge is an edge whose source and target are owned by the same function and which is not part of a function call, function transfer, or function return. This function returns true if the edge is intra-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is not intra-procedural regardless of which functions own the source and target blocks.
  • If a function is specified and that function is listed as an owner of both the source and target blocks, then the edge is intra-procedural.
  • If no function is specified and neither the source nor the target block have any function owners then the edge is intra-procedural.
  • If no function is specified and there exists some function that is an owner of both the source and target blocks then the edge is intra-procedural.
  • Otherwise the edge is not intra-procedural.

When no function is specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeInterProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeIntraProcedural ( const ControlFlowGraph::Edge &  edge) const

Determine if an edge is intra-procedural.

An intra-procedural edge is an edge whose source and target are owned by the same function and which is not part of a function call, function transfer, or function return. This function returns true if the edge is intra-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is not intra-procedural regardless of which functions own the source and target blocks.
  • If a function is specified and that function is listed as an owner of both the source and target blocks, then the edge is intra-procedural.
  • If no function is specified and neither the source nor the target block have any function owners then the edge is intra-procedural.
  • If no function is specified and there exists some function that is an owner of both the source and target blocks then the edge is intra-procedural.
  • Otherwise the edge is not intra-procedural.

When no function is specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeInterProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeInterProcedural ( ControlFlowGraph::ConstEdgeIterator  edge) const

Determine if an edge is inter-procedural.

An inter-procedural edge is an edge which is part of a function call, a function transfer, or a function return or an edge whose source and target blocks are owned by different functions. This function returns true if the edge is inter-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is inter-procedural regardless of which functions own the source and target blocks.
  • If two functions are specified and the source block is owned by the first function, the target block is owned by the second function, and the functions are different then the block is inter-procedural.
  • If only the source function is specified and the source block is owned by the source function and the target block is not owned by the source function then the edge is inter-procedural.
  • If only the target function is specified and the target block is owned by the target function and the source block is not owned by the target function then the edge is inter-procedural.
  • If no functions are specified and neither the source nor the target block have any function owners then the edge is inter-procedural.
  • If no functions are specified and the list of functions owning the source block is not equal to the list of functions owning the destination block then the block is inter-procedural.
  • Otherwise the edge is not inter-procedural.

When no functions are specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeIntraProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeInterProcedural ( ControlFlowGraph::ConstEdgeIterator  edge,
const FunctionPtr sourceFunction 
) const

Determine if an edge is inter-procedural.

An inter-procedural edge is an edge which is part of a function call, a function transfer, or a function return or an edge whose source and target blocks are owned by different functions. This function returns true if the edge is inter-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is inter-procedural regardless of which functions own the source and target blocks.
  • If two functions are specified and the source block is owned by the first function, the target block is owned by the second function, and the functions are different then the block is inter-procedural.
  • If only the source function is specified and the source block is owned by the source function and the target block is not owned by the source function then the edge is inter-procedural.
  • If only the target function is specified and the target block is owned by the target function and the source block is not owned by the target function then the edge is inter-procedural.
  • If no functions are specified and neither the source nor the target block have any function owners then the edge is inter-procedural.
  • If no functions are specified and the list of functions owning the source block is not equal to the list of functions owning the destination block then the block is inter-procedural.
  • Otherwise the edge is not inter-procedural.

When no functions are specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeIntraProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeInterProcedural ( ControlFlowGraph::ConstEdgeIterator  edge,
const FunctionPtr sourceFunction,
const FunctionPtr targetFunction 
) const

Determine if an edge is inter-procedural.

An inter-procedural edge is an edge which is part of a function call, a function transfer, or a function return or an edge whose source and target blocks are owned by different functions. This function returns true if the edge is inter-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is inter-procedural regardless of which functions own the source and target blocks.
  • If two functions are specified and the source block is owned by the first function, the target block is owned by the second function, and the functions are different then the block is inter-procedural.
  • If only the source function is specified and the source block is owned by the source function and the target block is not owned by the source function then the edge is inter-procedural.
  • If only the target function is specified and the target block is owned by the target function and the source block is not owned by the target function then the edge is inter-procedural.
  • If no functions are specified and neither the source nor the target block have any function owners then the edge is inter-procedural.
  • If no functions are specified and the list of functions owning the source block is not equal to the list of functions owning the destination block then the block is inter-procedural.
  • Otherwise the edge is not inter-procedural.

When no functions are specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeIntraProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeInterProcedural ( const ControlFlowGraph::Edge &  edge) const

Determine if an edge is inter-procedural.

An inter-procedural edge is an edge which is part of a function call, a function transfer, or a function return or an edge whose source and target blocks are owned by different functions. This function returns true if the edge is inter-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is inter-procedural regardless of which functions own the source and target blocks.
  • If two functions are specified and the source block is owned by the first function, the target block is owned by the second function, and the functions are different then the block is inter-procedural.
  • If only the source function is specified and the source block is owned by the source function and the target block is not owned by the source function then the edge is inter-procedural.
  • If only the target function is specified and the target block is owned by the target function and the source block is not owned by the target function then the edge is inter-procedural.
  • If no functions are specified and neither the source nor the target block have any function owners then the edge is inter-procedural.
  • If no functions are specified and the list of functions owning the source block is not equal to the list of functions owning the destination block then the block is inter-procedural.
  • Otherwise the edge is not inter-procedural.

When no functions are specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeIntraProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeInterProcedural ( const ControlFlowGraph::Edge &  edge,
const FunctionPtr sourceFunction 
) const

Determine if an edge is inter-procedural.

An inter-procedural edge is an edge which is part of a function call, a function transfer, or a function return or an edge whose source and target blocks are owned by different functions. This function returns true if the edge is inter-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is inter-procedural regardless of which functions own the source and target blocks.
  • If two functions are specified and the source block is owned by the first function, the target block is owned by the second function, and the functions are different then the block is inter-procedural.
  • If only the source function is specified and the source block is owned by the source function and the target block is not owned by the source function then the edge is inter-procedural.
  • If only the target function is specified and the target block is owned by the target function and the source block is not owned by the target function then the edge is inter-procedural.
  • If no functions are specified and neither the source nor the target block have any function owners then the edge is inter-procedural.
  • If no functions are specified and the list of functions owning the source block is not equal to the list of functions owning the destination block then the block is inter-procedural.
  • Otherwise the edge is not inter-procedural.

When no functions are specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeIntraProcedural.
bool Rose::BinaryAnalysis::Partitioner2::Partitioner::isEdgeInterProcedural ( const ControlFlowGraph::Edge &  edge,
const FunctionPtr sourceFunction,
const FunctionPtr targetFunction 
) const

Determine if an edge is inter-procedural.

An inter-procedural edge is an edge which is part of a function call, a function transfer, or a function return or an edge whose source and target blocks are owned by different functions. This function returns true if the edge is inter-procedural and false if not. The return value is calculated as follows:

  • An edge of type E_FUNCTION_CALL, E_FUNCTION_XFER, or E_FUNCTION_RETURN is inter-procedural regardless of which functions own the source and target blocks.
  • If two functions are specified and the source block is owned by the first function, the target block is owned by the second function, and the functions are different then the block is inter-procedural.
  • If only the source function is specified and the source block is owned by the source function and the target block is not owned by the source function then the edge is inter-procedural.
  • If only the target function is specified and the target block is owned by the target function and the source block is not owned by the target function then the edge is inter-procedural.
  • If no functions are specified and neither the source nor the target block have any function owners then the edge is inter-procedural.
  • If no functions are specified and the list of functions owning the source block is not equal to the list of functions owning the destination block then the block is inter-procedural.
  • Otherwise the edge is not inter-procedural.

When no functions are specified it can be ambiguous as to whether a branch is intra- or inter-procedural; a branch could be both intra- and inter-procedural.

Thread safety: Not thread safe.

See also
isEdgeIntraProcedural.
size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::nInstructions ( ) const

Returns the number of instructions attached to the CFG/AUM.

This statistic is computed in time linearly proportional to the number of basic blocks in the control flow graph.

Thread safety: Not thread safe.

AddressUser Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionExists ( rose_addr_t  startVa) const

Determines whether an instruction is attached to the CFG/AUM.

If the CFG/AUM represents an instruction that starts at the specified address, then this method returns the instruction/block pair, otherwise it returns an empty pair. The initial instruction for a basic block does not exist if the basic block is only represented by a placeholder in the CFG; such a basic block is said to be "undiscovered".

Thread safety: Not thread safe.

AddressUser Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionExists ( SgAsmInstruction insn) const

Determines whether an instruction is attached to the CFG/AUM.

If the CFG/AUM represents an instruction that starts at the specified address, then this method returns the instruction/block pair, otherwise it returns an empty pair. The initial instruction for a basic block does not exist if the basic block is only represented by a placeholder in the CFG; such a basic block is said to be "undiscovered".

Thread safety: Not thread safe.

ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionVertex ( rose_addr_t  insnVa) const

Returns the CFG vertex containing specified instruction.

Returns the control flow graph vertex that contains the specified instruction. If the instruction does not exist in the CFG then the end vertex is returned.

Thread safety: Not thread safe.

std::vector<SgAsmInstruction*> Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionsOverlapping ( const AddressInterval ) const

Returns instructions that overlap with specified address interval.

Returns a sorted list of distinct instructions that are attached to the CFG/AUM and which overlap at least one byte in the specified address interval. An instruction overlaps the interval if any of its bytes are within the interval.

The returned list of instructions are sorted by their starting address.

Thread safety: Not thread safe.

std::vector<SgAsmInstruction*> Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionsSpanning ( const AddressInterval ) const

Returns instructions that span an entire address interval.

Returns a sorted list of distinct instructions that are attached to the CFG/AUM and which span the entire specified interval. An instruction spans the interval if the set of addresses for all its bytes are a superset of the interval.

The returned list of instructions are sorted by their starting address.

Thread safety: Not thread safe.

std::vector<SgAsmInstruction*> Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionsContainedIn ( const AddressInterval ) const

Returns instructions that are fully contained in an address interval.

Returns a sorted list of distinct instructions that are attached to the CFG/AUM and which are fully contained within the specified interval. In order to be fully contained in the interval, the set of addresses of the bytes in the instruction must be a subset of the specified interval.

The returned list of instructions are sorted by their starting address.

Thread safety: Not thread safe.

AddressInterval Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionExtent ( SgAsmInstruction ) const

Returns the address interval for an instruction.

Returns the minimal interval describing from where the instruction was disassembled. An instruction always exists in a contiguous region of memory, therefore the return value is a single interval rather than a set of intervals. If a null pointer is specified then an empty interval is returned.

Thread safety: Not thread safe.

SgAsmInstruction* Rose::BinaryAnalysis::Partitioner2::Partitioner::discoverInstruction ( rose_addr_t  startVa) const

Discover an instruction.

Returns (and caches) the instruction at the specified address by invoking an InstructionProvider. Unlike instructionExists, the address does not need to be known by the CFG/AUM.

If the startVa is not mapped with execute permission or is improperly aligned for the architecture then a null pointer is returned. If an instruction cannot be disassembled at the address (e.g., bad byte code or not implemented) then a special 1-byte "unknown" instruction is returned; such instructions have indeterminate control flow successors and no semantics. If an instruction was previously returned for this address (including the "unknown" instruction) then that same instruction will be returned this time.

Thread safety: Not thread safe.

CrossReferences Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionCrossReferences ( const AddressIntervalSet restriction) const

Cross references.

Scans all attached instructions looking for constants mentioned in the instructions and builds a mapping from those constants back to the instructions. Only constants present in the restriction set are considered.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::nPlaceholders ( ) const

Returns the number of basic basic block placeholders in the CFG.

A placeholder optionally points to a basic block, and this method returns the number of placeholders in the CFG regardless of whether they point to a discovered basic block. Note that vertices that are mere placeholders and don't point to a discovered basic block are not represented in the AUM since a placeholder has no instructions.

This is a constant-time operation.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::placeholderExists ( rose_addr_t  startVa) const

Determines whether a basic block placeholder exists in the CFG.

Returns true if the CFG contains a placeholder at the specified address, and false if no such placeholder exists. The placeholder may or may not point to a discovered basic block.

Thread safety: Not thread safe.

See also
findPlaceholder
ControlFlowGraph::VertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::findPlaceholder ( rose_addr_t  startVa)

Find the CFG vertex for a basic block placeholder.

If the CFG contains a basic block placeholder at the specified address then that CFG vertex is returned, otherwise the end vertex (partitioner.cfg().vertices().end()) is returned.

Thread safety: Not thread safe.

See also
placeholderExists
ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::findPlaceholder ( rose_addr_t  startVa) const

Find the CFG vertex for a basic block placeholder.

If the CFG contains a basic block placeholder at the specified address then that CFG vertex is returned, otherwise the end vertex (partitioner.cfg().vertices().end()) is returned.

Thread safety: Not thread safe.

See also
placeholderExists
ControlFlowGraph::VertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::insertPlaceholder ( rose_addr_t  startVa)

Insert a basic-block placeholder.

Inserts a basic block placeholder into the CFG if it does not already exist.

If a new placeholder is inserted, then it represents the starting address of a not-yet-discovered basic block (as far as the CFG/AUM is concerned), and will contain a single incident edge which goes to the special "undiscovered" vertex. The new placeholder does not point to a basic block yet.

If the specified address is the starting address of an instruction that's already attached to the CFG/AUM (but not the start of a basic block) then the existing basic block that owns that instruction is truncated (see truncateBasicBlock), thereby inserting a new placeholder.

This method returns a pointer to either the existing placeholder (which may already point to an attached basic block) or the new placeholder.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::erasePlaceholder ( const ControlFlowGraph::ConstVertexIterator &  placeholder)

Remove a basic block placeholder from the CFG/AUM.

The specified placeholder (basic block starting address) is removed from the CFG along with its outgoing edges. If the placeholder pointed to a basic block then the basic block is detached from the CFG as if detachBasicBlock had been called. It is an error to attempt to remove a placeholder that has incoming edges that are not self edges (doing so will detach the basic block from the CFG/AUM before throwing an exception).

If the placeholder pointed to a discovered basic block then that basic block is returned, otherwise the null pointer is returned.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::erasePlaceholder ( rose_addr_t  startVa)

Remove a basic block placeholder from the CFG/AUM.

The specified placeholder (basic block starting address) is removed from the CFG along with its outgoing edges. If the placeholder pointed to a basic block then the basic block is detached from the CFG as if detachBasicBlock had been called. It is an error to attempt to remove a placeholder that has incoming edges that are not self edges (doing so will detach the basic block from the CFG/AUM before throwing an exception).

If the placeholder pointed to a discovered basic block then that basic block is returned, otherwise the null pointer is returned.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockSemanticsAutoDrop ( ) const

Property: Automatically drop semantics for attached basic blocks.

Basic blocks normally cache their semantic state as they're being discovered so that the state does not need to be recomputed from the beginning of the block each time a new instruction is appended. However, caching this information can consume a large number of symbolic expression nodes which are seldom needed once the basic block is fully discovered. Therefore, setting this property to true will cause a basic block's semantic information to be forgotten as soon as the basic block is attached to the CFG.

Thread safety: Not thread safe.

See also
basicBlockDropSemantics
void Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockSemanticsAutoDrop ( bool  )

Property: Automatically drop semantics for attached basic blocks.

Basic blocks normally cache their semantic state as they're being discovered so that the state does not need to be recomputed from the beginning of the block each time a new instruction is appended. However, caching this information can consume a large number of symbolic expression nodes which are seldom needed once the basic block is fully discovered. Therefore, setting this property to true will cause a basic block's semantic information to be forgotten as soon as the basic block is attached to the CFG.

Thread safety: Not thread safe.

See also
basicBlockDropSemantics
void Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockDropSemantics ( ) const

Immediately drop semantic information for all attached basic blocks.

Semantic information for all attached basic blocks is immediately forgotten by calling BasicBlock::dropSemantics. It can be recomputed later if necessary.

Thread safety: Not thread safe.

See also
basicBlockSemanticsAutoDrop
size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::nBasicBlocks ( ) const

Returns the number of basic blocks attached to the CFG/AUM.

This method returns the number of CFG vertices that are more than mere placeholders in that they point to an actual, discovered basic block.

This operation is linear in the number of vertices in the CFG. Consider using nPlaceholders instead.

Thread safety: Not thread safe.

std::vector<BasicBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlocks ( ) const

Returns all basic blocks attached to the CFG.

The returned list contains distinct basic blocks sorted by their starting address.

Thread safety: Not thread safe.

See also
basicBlocksOverlapping, basicBlocksSpanning, basicBlocksContainedIn
BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockExists ( rose_addr_t  startVa) const

Determines whether a discovered basic block exists in the CFG/AUM.

If the CFG/AUM contains a basic block that starts at the specified address then a pointer to that basic block is returned, otherwise a null pointer is returned. A null pointer is returned if the CFG contains only a placeholder vertex for a basic block at the specified address.

If a basic block pointer is specified instead of an address, the return value will be the same pointer if the specified basic block is attached to the CFG/AUM, otherwise the null pointer is returned. It is not sufficient for the CFG/AUM to contain a basic block at the same starting address – it must be the same actual basic block object. If you're only looking for a similar (i.e., starting at the same address) basic block then use the version that takes an address:

BasicBlock::Ptr original = ...;
BasicBlock::Ptr similar = basicBlockExists(original->address());

Thread safety: Not thread safe.

See also
placeholderExists
BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockExists ( const BasicBlockPtr ) const

Determines whether a discovered basic block exists in the CFG/AUM.

If the CFG/AUM contains a basic block that starts at the specified address then a pointer to that basic block is returned, otherwise a null pointer is returned. A null pointer is returned if the CFG contains only a placeholder vertex for a basic block at the specified address.

If a basic block pointer is specified instead of an address, the return value will be the same pointer if the specified basic block is attached to the CFG/AUM, otherwise the null pointer is returned. It is not sufficient for the CFG/AUM to contain a basic block at the same starting address – it must be the same actual basic block object. If you're only looking for a similar (i.e., starting at the same address) basic block then use the version that takes an address:

BasicBlock::Ptr original = ...;
BasicBlock::Ptr similar = basicBlockExists(original->address());

Thread safety: Not thread safe.

See also
placeholderExists
std::vector<BasicBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlocksOverlapping ( const AddressInterval ) const

Returns basic blocks that overlap with specified address interval.

Returns a sorted list of distinct basic blocks that are attached to the CFG/AUM and which overlap at least one byte in the specified address interval. By "overlap" we mean that the basic block has at least one instruction that overlaps with the specified interval. An instruction overlaps the interval if any of its bytes are within the interval.

The returned list of basic blocks are sorted by their starting address.

Thread safety: Not thread safe.

std::vector<BasicBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlocksSpanning ( const AddressInterval ) const

Returns basic blocks that span an entire address interval.

Returns a sorted list of distinct basic blocks that are attached to the CFG/AUM and which span the entire specified interval. In order for a basic block to span an interval its set of instructions must span the interval. In other words, the union of the addresses of the bytes contained in all the basic block's instructions is a superset of the specified interval.

The returned list of basic blocks are sorted by their starting address.

Thread safety: Not thread safe.

std::vector<BasicBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlocksContainedIn ( const AddressInterval ) const

Returns basic blocks that are fully contained in an address interval.

Returns a sorted list of distinct basic blocks that are attached to the CFG/AUM and which are fully contained within the specified interval. In order to be fully contained in the interval, the union of the addresses of the bytes in the basic block's instructions must be a subset of the specified interval.

The returned list of basic blocks are sorted by their starting address.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockContainingInstruction ( rose_addr_t  insnVa) const

Returns the basic block that contains a specific instruction address.

Returns the basic block that contains an instruction that starts at the specified address, or null if no such instruction or basic block exists in the CFG/AUM.

Thread safety: Not thread safe.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockInstructionExtent ( const BasicBlockPtr ) const

Returns the addresses used by basic block instructions.

Returns an interval set which is the union of the addresses of the bytes in the basic block's instructions. Most basic blocks are contiguous in memory and can be represented by a single address interval, but this is not a requirement in ROSE. ROSE only requires that the global control flow graph has edges that enter at only the initial instruction of the basic block and exit only from its final instruction. The instructions need not be contiguous or non-overlapping.

Thread safety: Not thread safe.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockDataExtent ( const BasicBlockPtr ) const

Returns the addresses used by basic block data.

Returns an interval set which is the union of the extents for each data block referenced by this basic block.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::detachBasicBlock ( rose_addr_t  startVa)

Detach a basic block from the CFG/AUM.

The specified basic block is detached from the CFG/AUM, leaving only a placeholder in its place. The original outgoing edges in the CFG are replaced by a single edge from the placeholder to the special "undiscovered" vertex. The instructions that had been attached to the CFG/AUM on behalf of the basic block are also detached from the CFG/AUM.

Any data blocks owned by this attached basic block will have their ownership counts decremented, and those data blocks whose attached owner counts reach zero are detached from the CFG/AUM.

This function does not modify the basic block itself; it only detaches it from the CFG/AUM. A basic block that is attached to the CFG/AUM is in a frozen state and cannot be modified directly, so one use of this function is to allow the user to modify a basic block and then re-attach it to the CFG/AUM. Detaching an already-detached basic block is a no-op.

This method returns a pointer to the basic block so it can be manipulated by the user after it is detached. If the user specified a basic block pointer to start with, then the return value is this same pointer; this function does nothing if the basic block was already detached. If the basic block was specified by its starting address and the CFG/AUM has no record of such a block then a null pointer is returned.

In order to completely remove a basic block, including its placeholder, use eraseBasicBlock.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::detachBasicBlock ( const BasicBlockPtr basicBlock)

Detach a basic block from the CFG/AUM.

The specified basic block is detached from the CFG/AUM, leaving only a placeholder in its place. The original outgoing edges in the CFG are replaced by a single edge from the placeholder to the special "undiscovered" vertex. The instructions that had been attached to the CFG/AUM on behalf of the basic block are also detached from the CFG/AUM.

Any data blocks owned by this attached basic block will have their ownership counts decremented, and those data blocks whose attached owner counts reach zero are detached from the CFG/AUM.

This function does not modify the basic block itself; it only detaches it from the CFG/AUM. A basic block that is attached to the CFG/AUM is in a frozen state and cannot be modified directly, so one use of this function is to allow the user to modify a basic block and then re-attach it to the CFG/AUM. Detaching an already-detached basic block is a no-op.

This method returns a pointer to the basic block so it can be manipulated by the user after it is detached. If the user specified a basic block pointer to start with, then the return value is this same pointer; this function does nothing if the basic block was already detached. If the basic block was specified by its starting address and the CFG/AUM has no record of such a block then a null pointer is returned.

In order to completely remove a basic block, including its placeholder, use eraseBasicBlock.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::detachBasicBlock ( const ControlFlowGraph::ConstVertexIterator &  placeholder)

Detach a basic block from the CFG/AUM.

The specified basic block is detached from the CFG/AUM, leaving only a placeholder in its place. The original outgoing edges in the CFG are replaced by a single edge from the placeholder to the special "undiscovered" vertex. The instructions that had been attached to the CFG/AUM on behalf of the basic block are also detached from the CFG/AUM.

Any data blocks owned by this attached basic block will have their ownership counts decremented, and those data blocks whose attached owner counts reach zero are detached from the CFG/AUM.

This function does not modify the basic block itself; it only detaches it from the CFG/AUM. A basic block that is attached to the CFG/AUM is in a frozen state and cannot be modified directly, so one use of this function is to allow the user to modify a basic block and then re-attach it to the CFG/AUM. Detaching an already-detached basic block is a no-op.

This method returns a pointer to the basic block so it can be manipulated by the user after it is detached. If the user specified a basic block pointer to start with, then the return value is this same pointer; this function does nothing if the basic block was already detached. If the basic block was specified by its starting address and the CFG/AUM has no record of such a block then a null pointer is returned.

In order to completely remove a basic block, including its placeholder, use eraseBasicBlock.

Thread safety: Not thread safe.

ControlFlowGraph::VertexIterator Rose::BinaryAnalysis::Partitioner2::Partitioner::truncateBasicBlock ( const ControlFlowGraph::ConstVertexIterator &  basicBlock,
SgAsmInstruction insn 
)

Truncate an attached basic-block.

The specified block is modified so that its final instruction is the instruction immediately prior to the specified instruction, a new placeholder vertex is created with the address of the specified instruction, and an edge is created from the truncated block to the new placeholder. All other outgoing edges of the truncated block are erased.

The specified block must exist and the instruction must not be the first instruction of the basic block. If the basic block contains the specified instruction then the block is split and a pointer to the new block returned. Otherwise a CFG vertex end iterator is returned.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::attachBasicBlock ( const BasicBlockPtr )

Attach a basic block to the CFG/AUM.

The specified basic block is inserted into the CFG/AUM. If the CFG already has a placeholder for the block then the specified block is stored at that placeholder, otherwise a new placeholder is created first. A basic block cannot be attached if the CFG/AUM already knows about a different basic block at the same address. Attempting to attach a block which is already attached is allowed, and is a no-op. It is an error to specify a null pointer for the basic block.

If the basic block owns any data blocks, those data blocks are also attached to the partitioner.

The basic block's cached successors are consulted when creating the new edges in the CFG. The block's successor types are used as-is except for the following modifications:

  • If the basic block is a function call and none of the successors are labeled as function calls (E_FUNCTION_CALL) then all normal successors (E_NORMAL) create function call edges in the CFG.
  • If the basic block is a function call and it has no call-return successor (E_CALL_RETURN) and this partitioner's autoAddCallReturnEdges property is true then a may-return analysis is performed on each callee and a call-return edge is added if any callee could return. If the analysis is indeterminate then an edge is added if this partitioner's assumeCallsReturn property is true.
  • If the basic block is a function return and has no function return successor (E_FUNCTION_RETURN, which normally is a symbolic address) then all normal successors (E_NORMAL) create function return edges in the CFG.

New placeholder vertices will be created automatically for new CFG edges that don't target an existing vertex.

A placeholder can be specified for better efficiency, in which case the placeholder must have the same address as the basic block.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::attachBasicBlock ( const ControlFlowGraph::ConstVertexIterator &  placeholder,
const BasicBlockPtr  
)

Attach a basic block to the CFG/AUM.

The specified basic block is inserted into the CFG/AUM. If the CFG already has a placeholder for the block then the specified block is stored at that placeholder, otherwise a new placeholder is created first. A basic block cannot be attached if the CFG/AUM already knows about a different basic block at the same address. Attempting to attach a block which is already attached is allowed, and is a no-op. It is an error to specify a null pointer for the basic block.

If the basic block owns any data blocks, those data blocks are also attached to the partitioner.

The basic block's cached successors are consulted when creating the new edges in the CFG. The block's successor types are used as-is except for the following modifications:

  • If the basic block is a function call and none of the successors are labeled as function calls (E_FUNCTION_CALL) then all normal successors (E_NORMAL) create function call edges in the CFG.
  • If the basic block is a function call and it has no call-return successor (E_CALL_RETURN) and this partitioner's autoAddCallReturnEdges property is true then a may-return analysis is performed on each callee and a call-return edge is added if any callee could return. If the analysis is indeterminate then an edge is added if this partitioner's assumeCallsReturn property is true.
  • If the basic block is a function return and has no function return successor (E_FUNCTION_RETURN, which normally is a symbolic address) then all normal successors (E_NORMAL) create function return edges in the CFG.

New placeholder vertices will be created automatically for new CFG edges that don't target an existing vertex.

A placeholder can be specified for better efficiency, in which case the placeholder must have the same address as the basic block.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::discoverBasicBlock ( rose_addr_t  startVa) const

Discover instructions for a detached basic block.

Obtains a basic block and its instructions without modifying the control flow graph. If the basic block already exists in the CFG/AUM then that block is returned, otherwise a new block is created but not added to the CFG/AUM. A basic block is created by adding one instruction at a time until one of the following conditions is met (tested in this order):

  • An instruction could not be obtained from the instruction provider via discoverInstruction. The instruction provider should return null only if the address is not mapped with execute permission or is improperly aligned for the architecture. The basic block's final instruction is the previous instruction, if any. If the block is empty then it is said to be non-existing, and will have a special successor when added to the CFG.
  • The instruction is an "unknown" instruction. The instruction provider returns an unknown instruction if it isn't able to disassemble an instruction at the specified address but the address is mapped with execute permission and the address was properly aligned. The partitioner treats this "unknown" instruction as a valid instruction with indeterminate successors (see below) and no semantics.
  • Note: at this point the user-defined basic block successors callbacks are invoked. They can query characteristics of the basic block, adjust the basic block successor cache (see below) and other characteristics of the block, and write values into a results structure that is used by some of the subsequent block termination conditions.
  • The instruction has a concrete successor address that is an address of a non-initial instruction in this block. Basic blocks cannot have a non-initial instruction with more than one incoming edge, therefore we've already added too many instructions to this block. We could proceed two ways: (A) We could throw away this instruction with the back-edge successor and make the block terminate at the previous instruction. This causes the basic block to be as big as possible for as long as possible, which is a good thing if it is determined later that the instruction with the back-edge is not reachable anyway. (B) We could truncate the basic block at the back-edge target so that the instruction prior to that is the final instruction. This is good because it converges to a steady state faster, but could result in basic blocks that are smaller than optimal. (The current algorithm uses method A.)
  • The user-defined basic block callbacks indicated that the block should be terminated. If the callback set the terminate member of the results output argument to BasicBlockCallback::TERMINATE_NOW or BasicBlockCallback::TERMINATE_PRIOR, then the current instruction either becomes the final instruction of the basic block, or the prior instruction becomes the final instruction.
  • The instruction is the final instruction of the basic block according to configuration information for that block. The basic block is terminated at this instruction.
  • The instruction causes this basic block to look like a function call. This instruction becomes the final instruction of the basic block and when the block is inserted into the CFG/AUM the edge will be marked as a function call edge. Function call instructions typically have one successor (the target function, usually concrete, but sometimes indeterminate), but the partitioner may eventually insert a "return" edge into the CFG when this basic block is attached.
  • The instruction doesn't have exactly one successor. Basic blocks cannot have a non-final instruction that branches, so this instruction becomes the final instruction.
  • The instruction successor is not a constant. If the successor cannot be resolved to a constant then this instruction becomes the final instruction. If this basic block is eventually attached to the CFG/AUM then an edge to the special "indeterminate" vertex will be created.
  • The instruction successor is the starting address for the block on which we're working. A basic block's instructions are distinct by definition, so this instruction becomes the final instruction for the block.
  • The instruction successor is the starting address of a basic block already in the CFG. This is a common case and probably means that what we discovered earlier is correct.
  • The instruction successor is an instruction already in the CFG other than in the conflict block. A "conflict block" is the basic block, if any, that contains as a non-first instruction the first instruction of this block. If the first instruction of the block being discovered is an instruction in the middle of some other basic block in the CFG, then we allow this block to use some of the same instructions as in the conflict block and we do not terminate construction of this block at this time. Usually what happens is the block being discovered uses all the final instructions from the conflict block; an exception is when an opaque predicate in the conflicting block is no longer opaque in the new block. Eventually if the new block is attached to the CFG/AUM then the conflict block will be truncated. When there is no conflict block then this instruction becomes the final instruction of the basic block.

Calculation of control flow successors

The basic block has a list of successor addresses and control flow edge types, but these are not added to the partitioner's CFG until the basic block is attached. A basic block's successor list can come from three places:

  • A block's successor list is initialized according to the final instruction. This list can be based on instruction pattern or semantic information for the entire block up to that point.
  • Basic block callbacks are allowed to adjust or replace the block's successor list.
  • If the configuration file has a successor list then that list is used. The list only applies if the configuration for the basic block also specifies a final instruction address and that address matches the current final instruction of the basic block.

Thread safety: Not thread safe.

BasicBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::discoverBasicBlock ( const ControlFlowGraph::ConstVertexIterator &  placeholder) const

Discover instructions for a detached basic block.

Obtains a basic block and its instructions without modifying the control flow graph. If the basic block already exists in the CFG/AUM then that block is returned, otherwise a new block is created but not added to the CFG/AUM. A basic block is created by adding one instruction at a time until one of the following conditions is met (tested in this order):

  • An instruction could not be obtained from the instruction provider via discoverInstruction. The instruction provider should return null only if the address is not mapped with execute permission or is improperly aligned for the architecture. The basic block's final instruction is the previous instruction, if any. If the block is empty then it is said to be non-existing, and will have a special successor when added to the CFG.
  • The instruction is an "unknown" instruction. The instruction provider returns an unknown instruction if it isn't able to disassemble an instruction at the specified address but the address is mapped with execute permission and the address was properly aligned. The partitioner treats this "unknown" instruction as a valid instruction with indeterminate successors (see below) and no semantics.
  • Note: at this point the user-defined basic block successors callbacks are invoked. They can query characteristics of the basic block, adjust the basic block successor cache (see below) and other characteristics of the block, and write values into a results structure that is used by some of the subsequent block termination conditions.
  • The instruction has a concrete successor address that is an address of a non-initial instruction in this block. Basic blocks cannot have a non-initial instruction with more than one incoming edge, therefore we've already added too many instructions to this block. We could proceed two ways: (A) We could throw away this instruction with the back-edge successor and make the block terminate at the previous instruction. This causes the basic block to be as big as possible for as long as possible, which is a good thing if it is determined later that the instruction with the back-edge is not reachable anyway. (B) We could truncate the basic block at the back-edge target so that the instruction prior to that is the final instruction. This is good because it converges to a steady state faster, but could result in basic blocks that are smaller than optimal. (The current algorithm uses method A.)
  • The user-defined basic block callbacks indicated that the block should be terminated. If the callback set the terminate member of the results output argument to BasicBlockCallback::TERMINATE_NOW or BasicBlockCallback::TERMINATE_PRIOR, then the current instruction either becomes the final instruction of the basic block, or the prior instruction becomes the final instruction.
  • The instruction is the final instruction of the basic block according to configuration information for that block. The basic block is terminated at this instruction.
  • The instruction causes this basic block to look like a function call. This instruction becomes the final instruction of the basic block and when the block is inserted into the CFG/AUM the edge will be marked as a function call edge. Function call instructions typically have one successor (the target function, usually concrete, but sometimes indeterminate), but the partitioner may eventually insert a "return" edge into the CFG when this basic block is attached.
  • The instruction doesn't have exactly one successor. Basic blocks cannot have a non-final instruction that branches, so this instruction becomes the final instruction.
  • The instruction successor is not a constant. If the successor cannot be resolved to a constant then this instruction becomes the final instruction. If this basic block is eventually attached to the CFG/AUM then an edge to the special "indeterminate" vertex will be created.
  • The instruction successor is the starting address for the block on which we're working. A basic block's instructions are distinct by definition, so this instruction becomes the final instruction for the block.
  • The instruction successor is the starting address of a basic block already in the CFG. This is a common case and probably means that what we discovered earlier is correct.
  • The instruction successor is an instruction already in the CFG other than in the conflict block. A "conflict block" is the basic block, if any, that contains as a non-first instruction the first instruction of this block. If the first instruction of the block being discovered is an instruction in the middle of some other basic block in the CFG, then we allow this block to use some of the same instructions as in the conflict block and we do not terminate construction of this block at this time. Usually what happens is the block being discovered uses all the final instructions from the conflict block; an exception is when an opaque predicate in the conflicting block is no longer opaque in the new block. Eventually if the new block is attached to the CFG/AUM then the conflict block will be truncated. When there is no conflict block then this instruction becomes the final instruction of the basic block.

Calculation of control flow successors

The basic block has a list of successor addresses and control flow edge types, but these are not added to the partitioner's CFG until the basic block is attached. A basic block's successor list can come from three places:

  • A block's successor list is initialized according to the final instruction. This list can be based on instruction pattern or semantic information for the entire block up to that point.
  • Basic block callbacks are allowed to adjust or replace the block's successor list.
  • If the configuration file has a successor list then that list is used. The list only applies if the configuration for the basic block also specifies a final instruction address and that address matches the current final instruction of the basic block.

Thread safety: Not thread safe.

BasicBlockSuccessors Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockSuccessors ( const BasicBlockPtr ,
Precision::Level  precision = Precision::HIGH 
) const

Determine successors for a basic block.

Basic block successors are returned as a vector in no particular order. This method returns the most basic successors; for instance, function call instructions will have an edge for the called function but no edge for the return. The basic block holds a successor cache which is consulted/updated by this method.

If precision is Precision::HIGH, then use instruction semantics if they're available. Otherwise, use a more naive method that usually works fine for most architectures with code generated by mainstream compilers. Low precision is substantially faster than high precision.

The basic block need not be complete or attached to the CFG/AUM. A basic block that has no instructions has no successors.

Thread safety: Not thread safe.

std::vector<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockConcreteSuccessors ( const BasicBlockPtr ,
bool *  isComplete = NULL 
) const

Determines concrete successors for a basic block.

Returns a vector of distinct, concrete successor addresses. Semantics is identical to bblockSuccessors except non-concrete values are removed from the list. The optional isComplete argument is set to true or false depending on whether the set of returned concrete successors represents the complete set of successors (true) or some member in the complete set is not concrete (false).

Thread safety: Not thread safe.

std::set<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockGhostSuccessors ( const BasicBlockPtr ) const

Determine ghost successors for a basic block.

The ghost successors of a basic block are those addresses where control could have naively flowed had we looked only at individual instructions rather than entire basic blocks. When a whole basic block is examined, the predicate of a conditional branch instruction might be determined to be constant, in which case the branch becomes unconditional, and the non-taken side of the branch becomes a ghost successor. Ghost successors are addresses rather than basic blocks (although they can be easily turned into basic blocks if desired), and can originate from any instruction within a basic block.

The basic block need not be complete and need not be attached to a CFG/AUM, although the specified pointer must not be null. A basic block that has no instructions has no ghost successors. The true successors are not included in the list of ghost successors. The basic block holds a ghost successor cache which is consulted/updated by this method.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockIsFunctionCall ( const BasicBlockPtr ,
Precision::Level  precision = Precision::HIGH 
) const

Determine if a basic block looks like a function call.

If the basic block appears to be a function call by some analysis then this function returns true. The analysis may use instruction semantics to look at the stack, it may look at the kind of instructions in the block, it may look for patterns at the callee address if known, etc. The basic block caches the result of this analysis.

If the analysis cannot prove that the block is a function call, then returns false.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockIsFunctionReturn ( const BasicBlockPtr ) const

Determine if a basic block looks like a function return.

If the basic block appears by some analysis to be a return from a function call, then this function returns true. The anlaysis may use instruction semantics to look at the stack, it may look at the kind of instructions in the lbock, it may look for patterns, etc. The basic block caches the result of this analysis.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockPopsStack ( const BasicBlockPtr ) const

Determine if the basic block pops at least one byte from the stack.

Returns true if the basic block has a net effect of popping at least one byte from the stack compared to the original stack pointer. Returns false if the block does not pop or its behavior cannot be determined.

InstructionSemantics::BaseSemantics::SValuePtr Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockStackDeltaIn ( const BasicBlockPtr ,
const FunctionPtr function 
) const

Return the stack delta expression.

The stack delta is the value of the stack pointer register at the entrance to the specified block minus the stack delta at the entry point of the function. The function entry point stack delta is zero; the return address pushed onto the stack by the caller is attributed to the caller, and popping the return address during the callee's return is attributed to the callee. Thus, most functions that use a caller-cleans-up-args ABI will have a stack delta equal to the size of the return address, and that delta will be positive for stacks that grow down, and negative for stacks that grow up.

The resulting stack delta can be four different kinds of values:

  • Never-computed is indicated by the basic block not caching any value for the stack delta. This method will always attempt to compute a stack delta if none is cached in the basic block.
  • Error is indicated by a cached null expression. Errors are usually due to a reachable basic block that contains an instruction for which semantics are not known.
  • Constant offset, for which the toInteger predicate applied to the return value is true. I.e., the delta is a concrete value fits in a 64-bit signed integer.
  • Top, indicated by a non-null return value for which toInteger is false. This results when two or more paths through the control flow graph result in different constant offsets. It can also occur when the algebraic simplifications that are built into ROSE fail to simplify a constant expression.

Two stack deltas are computed for each basic block: the stack delta at the start of the block and the start delta at the end of the block, returned by the "in" and "out" variants of this method, respectively. Since basic blocks can be shared among multiple functions and have a different delta in each, a function context must be provided as an argument.

Since stack deltas use the control flow graph during the analysis, the specified basic block and function must be attached to the CFG/AUM before calling this method. Also, since predefined stack deltas are based on function names, function calls must be to basic blocks that are attached to a function. Note that currently (Dec 2014) PE thunks transfering to a non-linked dynamic function are given names by ModulesPe::nameImportThunks, which runs after all basic blocks and functions have been discovered and attached to the CFG/AUM.

Thread safety: Not thread safe.

See also
functionStackDelta and allFunctionStackDelta
InstructionSemantics::BaseSemantics::SValuePtr Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockStackDeltaOut ( const BasicBlockPtr ,
const FunctionPtr function 
) const

Return the stack delta expression.

The stack delta is the value of the stack pointer register at the entrance to the specified block minus the stack delta at the entry point of the function. The function entry point stack delta is zero; the return address pushed onto the stack by the caller is attributed to the caller, and popping the return address during the callee's return is attributed to the callee. Thus, most functions that use a caller-cleans-up-args ABI will have a stack delta equal to the size of the return address, and that delta will be positive for stacks that grow down, and negative for stacks that grow up.

The resulting stack delta can be four different kinds of values:

  • Never-computed is indicated by the basic block not caching any value for the stack delta. This method will always attempt to compute a stack delta if none is cached in the basic block.
  • Error is indicated by a cached null expression. Errors are usually due to a reachable basic block that contains an instruction for which semantics are not known.
  • Constant offset, for which the toInteger predicate applied to the return value is true. I.e., the delta is a concrete value fits in a 64-bit signed integer.
  • Top, indicated by a non-null return value for which toInteger is false. This results when two or more paths through the control flow graph result in different constant offsets. It can also occur when the algebraic simplifications that are built into ROSE fail to simplify a constant expression.

Two stack deltas are computed for each basic block: the stack delta at the start of the block and the start delta at the end of the block, returned by the "in" and "out" variants of this method, respectively. Since basic blocks can be shared among multiple functions and have a different delta in each, a function context must be provided as an argument.

Since stack deltas use the control flow graph during the analysis, the specified basic block and function must be attached to the CFG/AUM before calling this method. Also, since predefined stack deltas are based on function names, function calls must be to basic blocks that are attached to a function. Note that currently (Dec 2014) PE thunks transfering to a non-linked dynamic function are given names by ModulesPe::nameImportThunks, which runs after all basic blocks and functions have been discovered and attached to the CFG/AUM.

Thread safety: Not thread safe.

See also
functionStackDelta and allFunctionStackDelta
void Rose::BinaryAnalysis::Partitioner2::Partitioner::forgetStackDeltas ( ) const

Clears all cached stack deltas.

Causes all stack deltas for basic blocks and functions that are attached to the CFG/AUM to be forgotten. This is useful if one needs to recompute deltas in light of new information.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::forgetStackDeltas ( const FunctionPtr ) const

Clears all cached stack deltas.

Causes all stack deltas for basic blocks and functions that are attached to the CFG/AUM to be forgotten. This is useful if one needs to recompute deltas in light of new information.

Thread safety: Not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::stackDeltaInterproceduralLimit ( ) const

Property: max depth for inter-procedural stack delta analysis.

Stack delta analysis will be interprocedural when this property has a value greater than one. Interprocedural analysis is only used when a called function's stack delta is unknown. Large values for this property will likely be clipped by the actual dataflow implementation.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::stackDeltaInterproceduralLimit ( size_t  )

Property: max depth for inter-procedural stack delta analysis.

Stack delta analysis will be interprocedural when this property has a value greater than one. Interprocedural analysis is only used when a called function's stack delta is unknown. Large values for this property will likely be clipped by the actual dataflow implementation.

Thread safety: Not thread safe.

Sawyer::Optional<bool> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockOptionalMayReturn ( const BasicBlockPtr ) const

Determine if part of the CFG can pop the top stack frame.

This analysis enters the CFG at the specified basic block and follows certain edges looking for a basic block where basicBlockIsFunctionReturn returns true. The analysis caches results in the mayReturn property of the reachable basic blocks.

Since the analysis results might change if edges are inserted or erased even on distant basic blocks, the basicBlockMayReturnReset method can be used to "forget" the property for all basic blocks in the CFG/AUM.

A basic block's may-return property is computed as follows (the first applicable rule wins):

  • If the block is owned by a function and the function's name is present on a whitelist or blacklist then the block's may-return is positive if whitelisted or negative if blacklisted.
  • If the block is a non-existing placeholder (i.e. its address is not mapped with execute permission) then its may-return is positive or negative depending on the value of this partitioner's assumeFunctionsReturn property.
  • If the block is a function return then the block's may-return is positive.
  • If any significant successor (defined below) of the block has a positive may-return value then the block's may-return is also positive.
  • If any significant succesor has an indeterminate may-return value, then the block's may-return is also indeterminate.
  • The block's may-return is negative.

A successor vertex is significant if there exists a significant edge to that vertex using these rules (first rule that applies wins):

  • A self-edge is never signiciant. A self edge does not affect the outcome of the analysis, so they're excluded.
  • A function-call edge (E_FUNCTION_CALL) is never significant. Even if the called function may return, it doesn't affect whether the block in question may return.
  • A call-return edge (E_CALL_RETURN) is significant if at least one of its sibling function call edges (E_FUNCTION_CALL) points to a vertex with a positive may-return, or if any sibling function call edge points to a vertex with an indeterminate may-return.
  • The edge is significant. This includes edges to the indeterminate and undiscovered vertices, whose may-return is always indeterminate.

The algorithm uses a combination of depth-first traversal and recursive calls. If any vertex's may-return is requested recursively while it is being computed, the recursive call returns an indeterminate may-return. Indeterminate results are indicated by returning nothing.

Thread safety: Not thread safe.

Sawyer::Optional<bool> Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockOptionalMayReturn ( const ControlFlowGraph::ConstVertexIterator &  ) const

Determine if part of the CFG can pop the top stack frame.

This analysis enters the CFG at the specified basic block and follows certain edges looking for a basic block where basicBlockIsFunctionReturn returns true. The analysis caches results in the mayReturn property of the reachable basic blocks.

Since the analysis results might change if edges are inserted or erased even on distant basic blocks, the basicBlockMayReturnReset method can be used to "forget" the property for all basic blocks in the CFG/AUM.

A basic block's may-return property is computed as follows (the first applicable rule wins):

  • If the block is owned by a function and the function's name is present on a whitelist or blacklist then the block's may-return is positive if whitelisted or negative if blacklisted.
  • If the block is a non-existing placeholder (i.e. its address is not mapped with execute permission) then its may-return is positive or negative depending on the value of this partitioner's assumeFunctionsReturn property.
  • If the block is a function return then the block's may-return is positive.
  • If any significant successor (defined below) of the block has a positive may-return value then the block's may-return is also positive.
  • If any significant succesor has an indeterminate may-return value, then the block's may-return is also indeterminate.
  • The block's may-return is negative.

A successor vertex is significant if there exists a significant edge to that vertex using these rules (first rule that applies wins):

  • A self-edge is never signiciant. A self edge does not affect the outcome of the analysis, so they're excluded.
  • A function-call edge (E_FUNCTION_CALL) is never significant. Even if the called function may return, it doesn't affect whether the block in question may return.
  • A call-return edge (E_CALL_RETURN) is significant if at least one of its sibling function call edges (E_FUNCTION_CALL) points to a vertex with a positive may-return, or if any sibling function call edge points to a vertex with an indeterminate may-return.
  • The edge is significant. This includes edges to the indeterminate and undiscovered vertices, whose may-return is always indeterminate.

The algorithm uses a combination of depth-first traversal and recursive calls. If any vertex's may-return is requested recursively while it is being computed, the recursive call returns an indeterminate may-return. Indeterminate results are indicated by returning nothing.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockMayReturnReset ( ) const

Clear all may-return properties.

This function is const because it doesn't modify the CFG/AUM; it only removes the may-return property from all the CFG/AUM basic blocks.

Thread safety: Not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::nDataBlocks ( ) const

Returns the number of data blocks attached to the CFG/AUM.

This is a relatively expensive operation compared to querying the number of basic blocks or functions.

Thread safety: Not thread safe.

DataBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::dataBlockExists ( const DataBlockPtr ) const

Determine if a data block or its equivalent is attached to the CFG/AUM.

If the AUM contains the specified data block or an equivalent data block, then return the non-null pointer for the data block that's already present in the AUM. Otherwise return a null pointer.

Thread safety: Not thread safe.

DataBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::findBestDataBlock ( const AddressInterval ) const

Find an existing data block.

Finds a data block that spans the specified address interval or which can be extended to span the address interval. The first choice is to return the smallest data block that spans the entire interval; second choice is the largest block that contains the first byte of the interval. If there is a tie in sizes then the block with the highest starting address wins. If no suitable data block can be found then the null pointer is returned.

Thread safety: Not thread safe.

DataBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::attachDataBlock ( const DataBlockPtr )

Attach a data block to the CFG/AUM.

Attaches the data block to the CFG/AUM if it is not already attached and there is no equivalent data block already attached. If no equivalent data block exists in the CFG/AUM then the specified block is attached and will have an ownership count of zero since none of its owners are attached (otherwise the data block or an equivalent block would also have been already attached). It is an error to supply a null pointer.

Returns the canonical data block, either one that already existed in the CFG/AUM or the specified data block which is now attached.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::detachDataBlock ( const DataBlockPtr )

Detaches a data block from the CFG/AUM.

The specified data block is detached from the CFG/AUM and thawed, and returned so it can be modified. It is an error to attempt to detach a data block which is owned by attached basic blocks or attached functions.

Thread safety: Not thread safe.

DataBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::attachDataBlockToFunction ( const DataBlockPtr ,
const FunctionPtr  
)

Attach a data block to an attached or detached function.

Causes the data block to be owned by the specified function. If the function is attached to this partitioner (i.e., appears in the control flow graph and address usage map) then the specified data block is also attached to this partitioner (if it wasn't already) and will appear in the address usage map.

Returns either the specified data block or an equivalent data block that's already owned by the function.

Thread safety: Not thread safe.

DataBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::attachDataBlockToBasicBlock ( const DataBlockPtr ,
const BasicBlockPtr  
)

Attach a data block to a basic block.

Causes the data block to be owned by the specified basic block. If the basic block is attached to this partitioner (i.e., appears in the control flow graph and address usage map) then the specified data block is also attached to this partitioner (if it wasn't already) and will appear in the address usage map.

If the basic block already owns a data block with the same starting address and size, then the specified data block is not attached to the basic block.

Returns either the specified data block or an equivalent data block that's already owned by the basic block.

Thread safety: Not thread safe.

std::vector<DataBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::dataBlocksOverlapping ( const AddressInterval ) const

Returns data blocks that overlap with specified address interval.

Returns a sorted list of distinct data blocks that are attached to the CFG/AUM and which overlap at least one byte in the specified address interval. All bytes represented by the data block are returned, even if they are unused or marked as padding in the data block type.

The returned list of data blocks are sorted by their starting address.

Thread safety: Not thread safe.

std::vector<DataBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::dataBlocksSpanning ( const AddressInterval ) const

Returns data blocks that span an entire address interval.

Returns a sorted list of distinct data blocks that are attached to the CFG/AUM and which span the entire specified interval. All bytes represented by the data block are returned, even if they are unused or marked as padding in the data block type.

The returned list of data blocks are sorted by their starting address.

Thread safety: Not thread safe.

std::vector<DataBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::dataBlocksContainedIn ( const AddressInterval ) const

Returns data blocks that are fully contained in an address interval.

Returns a sorted list of distinct data blocks that are attached to the CFG/AUM and which are fully contained within the specified interval. All bytes represented by the data block are returned, even if they are unused or marked as padding in the data block type.

The returned list of data blocks are sorted by their starting address.

Thread safety: Not thread safe.

AddressInterval Rose::BinaryAnalysis::Partitioner2::Partitioner::dataBlockExtent ( const DataBlockPtr ) const

Returns the addresses used by a data block.

Returns an address interval describing all addresses of the data block, even if they are unused or marked as padding in the data block type. Since all addresses are returned, the extent of a data block is always contiguous.

Thread safety: Not thread safe.

std::vector<DataBlockPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::dataBlocks ( ) const

Returns the list of all attached data blocks.

Returns a sorted list of distinct data blocks that are attached to the CFG/AUM.

Thread safety: Not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::nFunctions ( ) const

Returns the number of functions attached to the CFG/AUM.

This is a constant-time operation.

Thread safety: Not thread safe.

FunctionPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::functionExists ( rose_addr_t  entryVa) const

Determines whether a function exists in the CFG/AUM.

If the CFG/AUM knows about the specified function then this method returns a pointer to that function, otherwise it returns the null pointer.

The argument identifies the function for which to search:

  • The function's entry address.
  • The basic block that serves as the function's entry block.
  • A function pointer.

If the argument is a function pointer then this method checks that the specified function exists in the CFG/AUM and returns the argument if it exists, or else null if it doesn't exist. This test uses the function pointer directly, not the entry address – it returns non-null only if the argument is the actual function object stored in the CFG/AUM.

Thread safety: Not thread safe.

FunctionPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::functionExists ( const BasicBlockPtr entryBlock) const

Determines whether a function exists in the CFG/AUM.

If the CFG/AUM knows about the specified function then this method returns a pointer to that function, otherwise it returns the null pointer.

The argument identifies the function for which to search:

  • The function's entry address.
  • The basic block that serves as the function's entry block.
  • A function pointer.

If the argument is a function pointer then this method checks that the specified function exists in the CFG/AUM and returns the argument if it exists, or else null if it doesn't exist. This test uses the function pointer directly, not the entry address – it returns non-null only if the argument is the actual function object stored in the CFG/AUM.

Thread safety: Not thread safe.

FunctionPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::functionExists ( const FunctionPtr function) const

Determines whether a function exists in the CFG/AUM.

If the CFG/AUM knows about the specified function then this method returns a pointer to that function, otherwise it returns the null pointer.

The argument identifies the function for which to search:

  • The function's entry address.
  • The basic block that serves as the function's entry block.
  • A function pointer.

If the argument is a function pointer then this method checks that the specified function exists in the CFG/AUM and returns the argument if it exists, or else null if it doesn't exist. This test uses the function pointer directly, not the entry address – it returns non-null only if the argument is the actual function object stored in the CFG/AUM.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functions ( ) const

All functions attached to the CFG/AUM.

Returns a vector of distinct functions sorted by their entry address.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsOverlapping ( const AddressInterval ) const

Returns functions that overlap with specified address interval.

Returns a sorted list of distinct functions that are attached to the CFG/AUM and which overlap at least one byte in the specified address interval. By "overlap" we mean that the function owns at least one basic block or data block that overlaps with the interval.

The returned list of funtions are sorted by their entry address.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsSpanning ( const AddressInterval ) const

Returns functions that span an entire address interval.

Returns a sorted list of distinct functions that are attached to the CFG/AUM and which span the entire specified interval. In order for a function to span the interval its extent must be a superset of the interval. See functionExtent. In other words, the union of all the addresseses represented by the function's basic blocks and data blocks is a superset of the specified interval.

The returned list of functions are sorted by their starting address.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsContainedIn ( const AddressInterval ) const

Returns functions that are fully contained in an address interval.

Returns a sorted list of distinct functions that are attached to the CFG/AUM and which are fully contained within the specified interval. In order to be fully contained in the interval, the addresses represented by the function's basic blocks and data blocks must be a subset of the specified interval.

The returned list of functions are sorted by their starting address.

Thread safety: Not thread safe.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::Partitioner::functionExtent ( const FunctionPtr ) const

Returns the addresses used by a function.

Returns an interval set which is the union of the addresses of the function's basic blocks and/or data blocks. Most functions are contiguous in memory and can be represented by a single address interval, but this is not a requirement in ROSE.

The versions of these functions that take an AddressIntervalSet argument simply insert additional address intervals into that set without clearing it first.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::functionExtent ( const FunctionPtr function,
AddressIntervalSet retval 
) const

Returns the addresses used by a function.

Returns an interval set which is the union of the addresses of the function's basic blocks and/or data blocks. Most functions are contiguous in memory and can be represented by a single address interval, but this is not a requirement in ROSE.

The versions of these functions that take an AddressIntervalSet argument simply insert additional address intervals into that set without clearing it first.

Thread safety: Not thread safe.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::Partitioner::functionBasicBlockExtent ( const FunctionPtr function) const

Returns the addresses used by a function.

Returns an interval set which is the union of the addresses of the function's basic blocks and/or data blocks. Most functions are contiguous in memory and can be represented by a single address interval, but this is not a requirement in ROSE.

The versions of these functions that take an AddressIntervalSet argument simply insert additional address intervals into that set without clearing it first.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::functionBasicBlockExtent ( const FunctionPtr function,
AddressIntervalSet retval 
) const

Returns the addresses used by a function.

Returns an interval set which is the union of the addresses of the function's basic blocks and/or data blocks. Most functions are contiguous in memory and can be represented by a single address interval, but this is not a requirement in ROSE.

The versions of these functions that take an AddressIntervalSet argument simply insert additional address intervals into that set without clearing it first.

Thread safety: Not thread safe.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::Partitioner::functionDataBlockExtent ( const FunctionPtr function) const

Returns the addresses used by a function.

Returns an interval set which is the union of the addresses of the function's basic blocks and/or data blocks. Most functions are contiguous in memory and can be represented by a single address interval, but this is not a requirement in ROSE.

The versions of these functions that take an AddressIntervalSet argument simply insert additional address intervals into that set without clearing it first.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::functionDataBlockExtent ( const FunctionPtr function,
AddressIntervalSet retval 
) const

Returns the addresses used by a function.

Returns an interval set which is the union of the addresses of the function's basic blocks and/or data blocks. Most functions are contiguous in memory and can be represented by a single address interval, but this is not a requirement in ROSE.

The versions of these functions that take an AddressIntervalSet argument simply insert additional address intervals into that set without clearing it first.

Thread safety: Not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::attachFunction ( const FunctionPtr )

Attaches a function to the CFG/AUM.

The indicated function(s) is inserted into the control flow graph. Basic blocks (or at least placeholders) are inserted into the CFG for the function entry address and any basic block addresses the function might already contain. This method returns the number of new basic block placeholders that were created. If any data blocks are associated with the function then they are inserted into the AUM.

It is permissible to insert the same function multiple times at the same address (subsequent insertions are no-ops), but it is an error to insert a different function at the same address as an existing function. The CFG/AUM is capable of representing at most one function per function entry address.

All functions that are attached to the CFG/AUM are marked as frozen and the user is prevented from directly manipulating the function's basic block and data block ownership lists. The connectivity of frozen functions can only be changed by using the partitioner's API, not the function's API. This allows the partitioner to keep the CFG in a consistent state.

Thread safety: Not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::attachFunctions ( const Functions )

Attaches a function to the CFG/AUM.

The indicated function(s) is inserted into the control flow graph. Basic blocks (or at least placeholders) are inserted into the CFG for the function entry address and any basic block addresses the function might already contain. This method returns the number of new basic block placeholders that were created. If any data blocks are associated with the function then they are inserted into the AUM.

It is permissible to insert the same function multiple times at the same address (subsequent insertions are no-ops), but it is an error to insert a different function at the same address as an existing function. The CFG/AUM is capable of representing at most one function per function entry address.

All functions that are attached to the CFG/AUM are marked as frozen and the user is prevented from directly manipulating the function's basic block and data block ownership lists. The connectivity of frozen functions can only be changed by using the partitioner's API, not the function's API. This allows the partitioner to keep the CFG in a consistent state.

Thread safety: Not thread safe.

FunctionPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::attachOrMergeFunction ( const FunctionPtr )

Attaches or merges a function into the CFG/AUM.

If no other function exists at the specified function's entry address, then this method behaves identically to attachFunction. Otherwise, this method attempts to merge the specified function into an existing function. In any case, it returns a pointer to the function in the CFG/AUM (the existing one, or the new one). If the merge is not possible, then an exception is thrown.

One of the things that are merged are the basic blocks. If the function being attached is A and the partitioner already knows about B having the same entry address as A, then all basic blocks owned by A are now (also) owned by B. Some of those blocks happened to be owned by other functions also attached to the partitioner they continue to be owned also by those other functions. Data blocks are handled in a similar fashion.

Thread safety: Not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::attachFunctionBasicBlocks ( const Functions )

Create placeholders for function basic blocks.

Ensures that a basic block placeholder (or basic block) exists for each function entry address and each function basic block address. If a placeholder is absent then one is created by calling insertPlaceholder. The return value is the number of new placeholders created. A function that is attached to the CFG/AUM cannot have its basic block and data block membership lists manipulated directly by the user, but only through the Partitioner API.

If the function is attached to the CFG/AUM then additional actions occur: any placeholders (or basic blocks) owned by this function are verified to not be owned by some other function, and they are marked as owned by this function.

Thread safety: Not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::Partitioner::attachFunctionBasicBlocks ( const FunctionPtr )

Create placeholders for function basic blocks.

Ensures that a basic block placeholder (or basic block) exists for each function entry address and each function basic block address. If a placeholder is absent then one is created by calling insertPlaceholder. The return value is the number of new placeholders created. A function that is attached to the CFG/AUM cannot have its basic block and data block membership lists manipulated directly by the user, but only through the Partitioner API.

If the function is attached to the CFG/AUM then additional actions occur: any placeholders (or basic blocks) owned by this function are verified to not be owned by some other function, and they are marked as owned by this function.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::detachFunction ( const FunctionPtr )

Detaches a function from the CFG/AUM.

The indicated function is detached from the control flow graph. Although this function's basic blocks remain attached to the CFG/AUM, they are no longer considered to be owned by this function even though this function will continue to list the addresses of those blocks as its members. Any data blocks that were owned by only this function become detached from the CFG/AUM, but this function continues to point to them; other multiply-owned data blocks will remain attached to the CFG/AUM and will continue to be pointed to by this function, but the CFG/AUM will no longer list this function as one of their owners.

Detaching a function from the CFG/AUM does not change the function other than thawing it so it can be modified by the user directly through its API. Attempting to detach a function that is already detached has no effect.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsOwningBasicBlock ( const ControlFlowGraph::Vertex &  ,
bool  doSort = true 
) const

Finds functions that own the specified basic block.

Return the functions that own the specified basic block(s). The returned vector has distinct function pointers sorted by their entry addresses. Usually a basic block is owned by zero or one function. If a basic block cannot be found or if it has no owning functions then an empty vector is returned. The returned functions are all attached to the partitioner (that's how the partitioner knows about them); detached functions are not found.

Basic blocks can be specified in a number of ways:

  • As a CFG vertex. This is the fastest method since ownership information is stored directly in the CFG vertex. This is identical to calling CfgVertex::owningFunctions except the return value is a vector and the functions are sorted differently. The only expense is sorting the return value, which is usually a single function and therefore constant time (the following bullets also assume this is constant time).
  • As a starting address. If a basic block with the specified starting address exists in the CFG then its function owners are retrieved from the vertex. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a block pointer. The address of the block is used to find the CFG vertex from which ownership information is obtained. Basic block ownership is stored in the CFG, therefore if the provided basic block is not attached to the partitioner, the partitioner substitutes one that is attached. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a vector of any of the above. The returned vector is the union of the owning functions. Run time is O(N M) where N is the length of the vector and M is the time from above.

If doSort is clear then the result vector is not sorted, although it will still consist of unique function pointers. The return value from the variants that take more than one basic block is always sorted.

The returned function will be a function that is attached to the CFG/AUM; detached functions are never returned since the partitioner does not necessarily know about them.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsOwningBasicBlock ( const ControlFlowGraph::ConstVertexIterator &  ,
bool  doSort = true 
) const

Finds functions that own the specified basic block.

Return the functions that own the specified basic block(s). The returned vector has distinct function pointers sorted by their entry addresses. Usually a basic block is owned by zero or one function. If a basic block cannot be found or if it has no owning functions then an empty vector is returned. The returned functions are all attached to the partitioner (that's how the partitioner knows about them); detached functions are not found.

Basic blocks can be specified in a number of ways:

  • As a CFG vertex. This is the fastest method since ownership information is stored directly in the CFG vertex. This is identical to calling CfgVertex::owningFunctions except the return value is a vector and the functions are sorted differently. The only expense is sorting the return value, which is usually a single function and therefore constant time (the following bullets also assume this is constant time).
  • As a starting address. If a basic block with the specified starting address exists in the CFG then its function owners are retrieved from the vertex. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a block pointer. The address of the block is used to find the CFG vertex from which ownership information is obtained. Basic block ownership is stored in the CFG, therefore if the provided basic block is not attached to the partitioner, the partitioner substitutes one that is attached. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a vector of any of the above. The returned vector is the union of the owning functions. Run time is O(N M) where N is the length of the vector and M is the time from above.

If doSort is clear then the result vector is not sorted, although it will still consist of unique function pointers. The return value from the variants that take more than one basic block is always sorted.

The returned function will be a function that is attached to the CFG/AUM; detached functions are never returned since the partitioner does not necessarily know about them.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsOwningBasicBlock ( rose_addr_t  bblockVa,
bool  doSort = true 
) const

Finds functions that own the specified basic block.

Return the functions that own the specified basic block(s). The returned vector has distinct function pointers sorted by their entry addresses. Usually a basic block is owned by zero or one function. If a basic block cannot be found or if it has no owning functions then an empty vector is returned. The returned functions are all attached to the partitioner (that's how the partitioner knows about them); detached functions are not found.

Basic blocks can be specified in a number of ways:

  • As a CFG vertex. This is the fastest method since ownership information is stored directly in the CFG vertex. This is identical to calling CfgVertex::owningFunctions except the return value is a vector and the functions are sorted differently. The only expense is sorting the return value, which is usually a single function and therefore constant time (the following bullets also assume this is constant time).
  • As a starting address. If a basic block with the specified starting address exists in the CFG then its function owners are retrieved from the vertex. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a block pointer. The address of the block is used to find the CFG vertex from which ownership information is obtained. Basic block ownership is stored in the CFG, therefore if the provided basic block is not attached to the partitioner, the partitioner substitutes one that is attached. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a vector of any of the above. The returned vector is the union of the owning functions. Run time is O(N M) where N is the length of the vector and M is the time from above.

If doSort is clear then the result vector is not sorted, although it will still consist of unique function pointers. The return value from the variants that take more than one basic block is always sorted.

The returned function will be a function that is attached to the CFG/AUM; detached functions are never returned since the partitioner does not necessarily know about them.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsOwningBasicBlock ( const BasicBlockPtr ,
bool  doSort = true 
) const

Finds functions that own the specified basic block.

Return the functions that own the specified basic block(s). The returned vector has distinct function pointers sorted by their entry addresses. Usually a basic block is owned by zero or one function. If a basic block cannot be found or if it has no owning functions then an empty vector is returned. The returned functions are all attached to the partitioner (that's how the partitioner knows about them); detached functions are not found.

Basic blocks can be specified in a number of ways:

  • As a CFG vertex. This is the fastest method since ownership information is stored directly in the CFG vertex. This is identical to calling CfgVertex::owningFunctions except the return value is a vector and the functions are sorted differently. The only expense is sorting the return value, which is usually a single function and therefore constant time (the following bullets also assume this is constant time).
  • As a starting address. If a basic block with the specified starting address exists in the CFG then its function owners are retrieved from the vertex. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a block pointer. The address of the block is used to find the CFG vertex from which ownership information is obtained. Basic block ownership is stored in the CFG, therefore if the provided basic block is not attached to the partitioner, the partitioner substitutes one that is attached. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a vector of any of the above. The returned vector is the union of the owning functions. Run time is O(N M) where N is the length of the vector and M is the time from above.

If doSort is clear then the result vector is not sorted, although it will still consist of unique function pointers. The return value from the variants that take more than one basic block is always sorted.

The returned function will be a function that is attached to the CFG/AUM; detached functions are never returned since the partitioner does not necessarily know about them.

Thread safety: Not thread safe.

template<class Container >
std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionsOwningBasicBlocks ( const Container &  bblocks) const
inline

Finds functions that own the specified basic block.

Return the functions that own the specified basic block(s). The returned vector has distinct function pointers sorted by their entry addresses. Usually a basic block is owned by zero or one function. If a basic block cannot be found or if it has no owning functions then an empty vector is returned. The returned functions are all attached to the partitioner (that's how the partitioner knows about them); detached functions are not found.

Basic blocks can be specified in a number of ways:

  • As a CFG vertex. This is the fastest method since ownership information is stored directly in the CFG vertex. This is identical to calling CfgVertex::owningFunctions except the return value is a vector and the functions are sorted differently. The only expense is sorting the return value, which is usually a single function and therefore constant time (the following bullets also assume this is constant time).
  • As a starting address. If a basic block with the specified starting address exists in the CFG then its function owners are retrieved from the vertex. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a block pointer. The address of the block is used to find the CFG vertex from which ownership information is obtained. Basic block ownership is stored in the CFG, therefore if the provided basic block is not attached to the partitioner, the partitioner substitutes one that is attached. Runtime is O(log |V|) where |V| is the number of vertices in the CFG.
  • As a vector of any of the above. The returned vector is the union of the owning functions. Run time is O(N M) where N is the length of the vector and M is the time from above.

If doSort is clear then the result vector is not sorted, although it will still consist of unique function pointers. The return value from the variants that take more than one basic block is always sorted.

The returned function will be a function that is attached to the CFG/AUM; detached functions are never returned since the partitioner does not necessarily know about them.

Thread safety: Not thread safe.

Definition at line 1873 of file Partitioner.h.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::discoverCalledFunctions ( ) const

Scans the CFG to find function calls.

Scans the CFG without modifying it and looks for edges that are marked as being function calls. A function is created at each call if one doesn't already exist in the CFG/AUM, and the list of created functions is returned. None of the created functions are added to the CFG/AUM.

See also discoverFunctionEntryVertices which returns a superset of the functions returned by this method.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::discoverFunctionEntryVertices ( ) const

Scans the CFG to find function entry basic blocks.

Scans the CFG without modifying it in order to find vertices (basic blocks and basic block placeholders) that are the entry points of functions. A vertex is a function entry point if it has an incoming edge that is a function call or if it is the entry block of a function that already exists.

The returned function pointers are sorted by function entry address.

See also discoverFunctionCalls which returns a subset of the functions returned by this method.

Thread safety: Not thread safe.

Sawyer::Optional<Thunk> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionIsThunk ( const FunctionPtr ) const

True if function is a thunk.

If the function is non-null and a thunk then some information about the thunk is returned, otherwise nothing is returned. A function is a thunk if it has the SgAsmFunction::FUNC_THUNK bit set in its reason mask, and it has exactly one basic block, and the basic block has exactly one successor, and the successor is concrete.

As a side effect, the basic block's outgoing edge type is changed to E_FUNCTION_XFER.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::discoverFunctionBasicBlocks ( const FunctionPtr function) const

Adds basic blocks to a function.

Attempts to discover the basic blocks that should belong to the specified function. It does so by finding all CFG vertices that are reachable from the already-owned vertices without following edges that are marked as function calls, function transfers, or function returns and without following edges that lead to the entry point of another function.

The CFG is not modified by this method. The function is modified and must not exist in the CFG; the function must be in a thawed state.

Thread safety: Not thread safe.

std::set<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionGhostSuccessors ( const FunctionPtr ) const

Returns ghost successors for a single function.

Returns the set of basic block starting addresses that are naive successors for the basic blocks of a function but which are not actual control flow successors due to the presence of opaque predicates.

Thread safety: Not thread safe.

FunctionCallGraph Rose::BinaryAnalysis::Partitioner2::Partitioner::functionCallGraph ( AllowParallelEdges::Type  allowParallelEdges) const

Returns a function call graph.

If allowParallelEdges is true then the returned call graph will have one edge for each function call and each edge will have a count of one. Otherwise multiple calls between the same pair of functions are coalesced into single edges with non-unit counts in the call graph.

Thread safety: Not thread safe.

InstructionSemantics::BaseSemantics::SValuePtr Rose::BinaryAnalysis::Partitioner2::Partitioner::functionStackDelta ( const FunctionPtr function) const

Stack delta analysis for one function.

Computes stack deltas if possible at each basic block within the specified function. The algorithm starts at the function's entry block with an incoming stack delta of zero, and performs a dataflow anysis following a control flow graph that contains those vertices reachable from the entry block by following only intra-function edges. Each such vertex is given an incoming and outgoing stack delta.

If the function appears to make reasonable use of the stack then an overall stack delta is returned. This is the delta resulting from the final function return blocks. Otherwise a null expression is returned. The result is cached in the Function::stackDelta property.

Since this analysis is based on data flow, which is based on a control flow graph, the function must be attached to the CFG/AUM and all its basic blocks must also exist in the CFG/AUM. Also, the basicBlockStackDelta method must be non-null for each reachable block in the function.

If the configuration information specifies a stack delta for this function then that delta is used instead of performing any analysis.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::allFunctionStackDelta ( ) const

Compute stack delta analysis for all functions.

Thread safety: Not thread safe.

Sawyer::Optional<bool> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionOptionalMayReturn ( const FunctionPtr function) const

May-return analysis for one function.

Determines if a function can possibly return to its caller. This is a simple wrapper around basicBlockOptionalMayReturn invoked on the function's entry block. See that method for details.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::allFunctionMayReturn ( ) const

Compute may-return analysis for all functions.

Thread safety: Not thread safe.

const CallingConvention::Analysis& Rose::BinaryAnalysis::Partitioner2::Partitioner::functionCallingConvention ( const FunctionPtr ) const

Calling convention analysis for one function.

Analyses a function to determine characteristics of its calling convention, such as which registers are callee-saved, which registers and stack locations are input parameters, and which are output parameters. The calling convention analysis itself does not define the entire calling convention–instead, the analysis results must be matched against a dictionary of calling convention definitions. Each function has a callingConventionDefinition property that points to the best definition; if this method reanalyzes the calling convention then the definition is reset to the null pointer.

Since this analysis is based on data-flow, which is based on a control flow graph, the function must be attached to the CFG/AUM and all its basic blocks must also exist in the CFG/AUM.

Warning: If the specified function calls other functions for which a calling convention analysis has not been run the analysis of this function may be incorrect. This is because the analysis of this function must know which registers are clobbered by the call in order to produce accurate results. See also, allFunctionCallingConvention. If a default calling convention is supplied then it determines which registers are clobbered by a call to a function that hasn't been analyzed yet.

Calling convention analysis results are stored in the function object. If calling convention analysis has already been run for this function then the old results are returned. The old results can be cleared on a per-function basis with function->callingConventionAnalysis().clear().

See also, allFunctionCallingConvention, which computes calling convention characteristics for all functions at once, and functionCallingConventionDefinitions, which returns matching definitions.

Thread safety: Not thread safe.

const CallingConvention::Analysis& Rose::BinaryAnalysis::Partitioner2::Partitioner::functionCallingConvention ( const FunctionPtr ,
const CallingConvention::Definition::Ptr dflt 
) const

Calling convention analysis for one function.

Analyses a function to determine characteristics of its calling convention, such as which registers are callee-saved, which registers and stack locations are input parameters, and which are output parameters. The calling convention analysis itself does not define the entire calling convention–instead, the analysis results must be matched against a dictionary of calling convention definitions. Each function has a callingConventionDefinition property that points to the best definition; if this method reanalyzes the calling convention then the definition is reset to the null pointer.

Since this analysis is based on data-flow, which is based on a control flow graph, the function must be attached to the CFG/AUM and all its basic blocks must also exist in the CFG/AUM.

Warning: If the specified function calls other functions for which a calling convention analysis has not been run the analysis of this function may be incorrect. This is because the analysis of this function must know which registers are clobbered by the call in order to produce accurate results. See also, allFunctionCallingConvention. If a default calling convention is supplied then it determines which registers are clobbered by a call to a function that hasn't been analyzed yet.

Calling convention analysis results are stored in the function object. If calling convention analysis has already been run for this function then the old results are returned. The old results can be cleared on a per-function basis with function->callingConventionAnalysis().clear().

See also, allFunctionCallingConvention, which computes calling convention characteristics for all functions at once, and functionCallingConventionDefinitions, which returns matching definitions.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::allFunctionCallingConvention ( ) const

Compute calling conventions for all functions.

Analyzes calling conventions for all functions and caches results in the function objects. The analysis uses a depth first traversal of the call graph, invoking the analysis as the traversal unwinds. This increases the chance that the calling conventions of callees are known before their callers are analyzed. However, this analysis must break cycles in mutually recursive calls, and does so by using an optional default calling convention where the cycle is broken. This default is not inserted as a result–it only influences the data-flow portion of the analysis.

After this method runs, results can be queried per function with either Function::callingConventionAnalysis or functionCallingConvention.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::allFunctionCallingConvention ( const CallingConvention::Definition::Ptr dflt) const

Compute calling conventions for all functions.

Analyzes calling conventions for all functions and caches results in the function objects. The analysis uses a depth first traversal of the call graph, invoking the analysis as the traversal unwinds. This increases the chance that the calling conventions of callees are known before their callers are analyzed. However, this analysis must break cycles in mutually recursive calls, and does so by using an optional default calling convention where the cycle is broken. This default is not inserted as a result–it only influences the data-flow portion of the analysis.

After this method runs, results can be queried per function with either Function::callingConventionAnalysis or functionCallingConvention.

Thread safety: Not thread safe.

CallingConvention::Dictionary Rose::BinaryAnalysis::Partitioner2::Partitioner::functionCallingConventionDefinitions ( const FunctionPtr ) const

Return list of matching calling conventions.

Given a function, run a calling convention analysis (if necessary) and return the list of common architecture calling convention definitions that match the characteristics of the function. This method differs from functionCallingConvention in that the former returns an analysis object that holds the function characteristics, while this method then takes a list of common calling convention definitions (based on the architecture) and returns those definitions that are consistent with the function characteristics.

Since this analysis is based on data-flow, which is based on a control flow graph, the function must be attached to the CFG/AUM and all ts basic blocks must also exist in the CFG/AUM.

If the specified function calls other functions for which a calling convention analysis has not been run the analysis of this function may be incorrect. This is because the analysis of this function must know which registers are clobbered by the call in order to produce accurate results. See also, allFunctionCallingConvention. If a default calling convention is supplied then it determines which registers are clobbered by a call to a function that hasn't been analyzed yet.

If the calling convention analysis fails or no common architecture calling convention definition matches the characteristics of the function, then an empty list is returned. This method does not access the function's calling convention property – it recomputes the list of matching definitions from scratch.

Thread safety: Not thread safe.

See also, functionCallingConvention, which returns the calling convention characteristics of a function (rather than definitions), and allFunctionCallingConvention, which runs that analysis over all functions.

CallingConvention::Dictionary Rose::BinaryAnalysis::Partitioner2::Partitioner::functionCallingConventionDefinitions ( const FunctionPtr ,
const CallingConvention::Definition::Ptr  
) const

Return list of matching calling conventions.

Given a function, run a calling convention analysis (if necessary) and return the list of common architecture calling convention definitions that match the characteristics of the function. This method differs from functionCallingConvention in that the former returns an analysis object that holds the function characteristics, while this method then takes a list of common calling convention definitions (based on the architecture) and returns those definitions that are consistent with the function characteristics.

Since this analysis is based on data-flow, which is based on a control flow graph, the function must be attached to the CFG/AUM and all ts basic blocks must also exist in the CFG/AUM.

If the specified function calls other functions for which a calling convention analysis has not been run the analysis of this function may be incorrect. This is because the analysis of this function must know which registers are clobbered by the call in order to produce accurate results. See also, allFunctionCallingConvention. If a default calling convention is supplied then it determines which registers are clobbered by a call to a function that hasn't been analyzed yet.

If the calling convention analysis fails or no common architecture calling convention definition matches the characteristics of the function, then an empty list is returned. This method does not access the function's calling convention property – it recomputes the list of matching definitions from scratch.

Thread safety: Not thread safe.

See also, functionCallingConvention, which returns the calling convention characteristics of a function (rather than definitions), and allFunctionCallingConvention, which runs that analysis over all functions.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::allFunctionCallingConventionDefinition ( ) const

Analyzes calling conventions and saves results.

This method invokes allFunctionCallingConvention to analyze the behavior of every function, then finds the list of matching definitions for each function. A histogram of definitions is calculated and each function is re-examined. If any function matched more than one definition, then the most frequent of those definitions is chosen as that function's "best" calling convention definition and saved in the Function::callingConventionDefinition property.

If a default calling convention definition is provided, it gets passed to the allFunctionCallingConvention analysis. The default is also assigned as the Function::callingConventionDefinition property of any function for which calling convention analysis fails.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::allFunctionCallingConventionDefinition ( const CallingConvention::Definition::Ptr ) const

Analyzes calling conventions and saves results.

This method invokes allFunctionCallingConvention to analyze the behavior of every function, then finds the list of matching definitions for each function. A histogram of definitions is calculated and each function is re-examined. If any function matched more than one definition, then the most frequent of those definitions is chosen as that function's "best" calling convention definition and saved in the Function::callingConventionDefinition property.

If a default calling convention definition is provided, it gets passed to the allFunctionCallingConvention analysis. The default is also assigned as the Function::callingConventionDefinition property of any function for which calling convention analysis fails.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::fixInterFunctionEdges ( )

Adjust inter-function edge types.

For any CFG edge whose source and destination are two different functions but whose type is E_NORMAL, replace the edge with either a E_FUNCTION_CALL or E_FUNCTION_XFER edge as appropriate.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::fixInterFunctionEdge ( const ControlFlowGraph::ConstEdgeIterator &  )

Adjust inter-function edge types.

For any CFG edge whose source and destination are two different functions but whose type is E_NORMAL, replace the edge with either a E_FUNCTION_CALL or E_FUNCTION_XFER edge as appropriate.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::functionIsNoop ( const FunctionPtr ) const

Function no-op analysis.

Analyzes a function to determine whether the function is effectively no operation. Returns true if the function can be proven to be a no-op, false if the analysis can prove the function has an effect, and also false if the analysis cannot make a determination.

Since this analysis is based on data-flow, which is based on a control flow graph, the function must be attached to the CFG/AUM and all its basic blocks must also exist in the CFG/AUM.

The no-op analysis results are stored in the function object. If no-op analysis has already been run for this function then the old results are returned. The old results can be cleared on a per-function basis with function->isNoop().clear().

Thread safety: Not thread safe.

See also, allFunctionIsNoop, which analyzes all functions at once and which therefore may be faster than invoking the analysis one function at a time.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::allFunctionIsNoop ( ) const

Analyze all functions for whether they are effectivly no-ops.

Invokes the functionIsNoop analysis on each function, perhaps concurrently.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::forgetFunctionIsNoop ( ) const

Clears cached function no-op analysis results.

Clears the function no-op analysis results for the specified function or all functions.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::forgetFunctionIsNoop ( const FunctionPtr ) const

Clears cached function no-op analysis results.

Clears the function no-op analysis results for the specified function or all functions.

Thread safety: Not thread safe.

std::set<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::Partitioner::functionDataFlowConstants ( const FunctionPtr ) const

Find constants in function using data-flow.

This function runs a simple data-flow operation on the specified function and examines all states to obtain a set of constants.

CfgAdjustmentCallbacks& Rose::BinaryAnalysis::Partitioner2::Partitioner::cfgAdjustmentCallbacks ( )

List of all callbacks invoked when the CFG is adjusted.

Inserting a new callback goes something like this:

struct MyCallback: Partitioner::CfgAdjustmentCallback {
static Ptr instance() { return Ptr(new MyCallback); }
virtual bool operator()(bool chain, const AttachedBasicBlock &args) { ... }
virtual bool operator()(bool chain, const DetachedBasicBlock &args) { ... }
};
partitioner.cfgAdjustmentCallbacks().append(MyCallback::instance());

Thread safety: Not thread safe.

const CfgAdjustmentCallbacks& Rose::BinaryAnalysis::Partitioner2::Partitioner::cfgAdjustmentCallbacks ( ) const

List of all callbacks invoked when the CFG is adjusted.

Inserting a new callback goes something like this:

struct MyCallback: Partitioner::CfgAdjustmentCallback {
static Ptr instance() { return Ptr(new MyCallback); }
virtual bool operator()(bool chain, const AttachedBasicBlock &args) { ... }
virtual bool operator()(bool chain, const DetachedBasicBlock &args) { ... }
};
partitioner.cfgAdjustmentCallbacks().append(MyCallback::instance());

Thread safety: Not thread safe.

BasicBlockCallbacks& Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockCallbacks ( )

Callbacks for adjusting basic block during discovery.

Each time an instruction is appended to a basic block these callbacks are invoked to make adjustments to the block. See BasicBlockCallback and discoverBasicBlock for details.

Thread safety: Not thread safe.

const BasicBlockCallbacks& Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockCallbacks ( ) const

Callbacks for adjusting basic block during discovery.

Each time an instruction is appended to a basic block these callbacks are invoked to make adjustments to the block. See BasicBlockCallback and discoverBasicBlock for details.

Thread safety: Not thread safe.

FunctionPrologueMatchers& Rose::BinaryAnalysis::Partitioner2::Partitioner::functionPrologueMatchers ( )

Ordered list of function prologue matchers.

See also
nextFunctionPrologue

Thread safety: Not thread safe.

const FunctionPrologueMatchers& Rose::BinaryAnalysis::Partitioner2::Partitioner::functionPrologueMatchers ( ) const

Ordered list of function prologue matchers.

See also
nextFunctionPrologue

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::nextFunctionPrologue ( rose_addr_t  startVa)

Finds the next function by searching for a function prologue.

Scans executable memory starting at startVa and tries to match a function prologue pattern. The patterns are represented by matchers that have been inserted into the vector reference returned by functionPrologueMatchers. The first matcher that finds an instruction anchored at a supplied starting address wins. The starting address is incremented at each step so that it is always an address that is mapped with execute permission and is not an address that is the start of an instruction that's in the CFG.

If a matcher matches a function prologue then a detached function is created and returned. The starting address need not be the same as the anchor address for the match. For instance, a matcher might match one or more no-op instructions followed by the function prologue, in which case the address after the no-ops is the one used as the entry point of the returned function.

Some function prologue matchers can return multiple functions. For instance, a matcher for a thunk might return the thunk and the function to which it points. In any case, the first function is the primary one.

If no match is found then an empty vector is returned.

If The lastSearchedVa argument is provided, then it is set to the highest address at which a function prologue was searched.

Thread safety: Not thread safe.

std::vector<FunctionPtr> Rose::BinaryAnalysis::Partitioner2::Partitioner::nextFunctionPrologue ( rose_addr_t  startVa,
rose_addr_t &  lastSearchedVa 
)

Finds the next function by searching for a function prologue.

Scans executable memory starting at startVa and tries to match a function prologue pattern. The patterns are represented by matchers that have been inserted into the vector reference returned by functionPrologueMatchers. The first matcher that finds an instruction anchored at a supplied starting address wins. The starting address is incremented at each step so that it is always an address that is mapped with execute permission and is not an address that is the start of an instruction that's in the CFG.

If a matcher matches a function prologue then a detached function is created and returned. The starting address need not be the same as the anchor address for the match. For instance, a matcher might match one or more no-op instructions followed by the function prologue, in which case the address after the no-ops is the one used as the entry point of the returned function.

Some function prologue matchers can return multiple functions. For instance, a matcher for a thunk might return the thunk and the function to which it points. In any case, the first function is the primary one.

If no match is found then an empty vector is returned.

If The lastSearchedVa argument is provided, then it is set to the highest address at which a function prologue was searched.

Thread safety: Not thread safe.

FunctionPaddingMatchers& Rose::BinaryAnalysis::Partitioner2::Partitioner::functionPaddingMatchers ( )

Ordered list of function padding matchers.

Thread safety: Not thread safe.

const FunctionPaddingMatchers& Rose::BinaryAnalysis::Partitioner2::Partitioner::functionPaddingMatchers ( ) const

Ordered list of function padding matchers.

Thread safety: Not thread safe.

DataBlockPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::matchFunctionPadding ( const FunctionPtr )

Finds function padding.

Scans backward from the specified function's entry address by invoking each function padding matcher in the order returned by functionPaddingMatchers until one of them finds some padding. Once found, a data block is created and returned. If no padding is found then the null pointer is returned.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::dumpCfg ( std::ostream &  ,
const std::string &  prefix = "",
bool  showBlocks = true,
bool  computeProperties = true 
) const

Output the control flow graph.

Emits the control flow graph, basic blocks, and their instructions to the specified stream. The addresses are starting addresses, and the suffix "[P]" means the address is a basic block placeholder, and the suffix "[X]" means the basic block was discovered to be non-existing (i.e., no executable memory for the first instruction).

A prefix can be specified to be added to the beginning of each line of output. If showBlocks is set then the instructions are shown for each basic block. If computeProperties is set then various properties are computed and cached rather than only consulting the cache.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::cfgGraphViz ( std::ostream &  ,
const AddressInterval restrict = AddressInterval::whole(),
bool  showNeighbors = true 
) const

Output CFG as GraphViz.

This is a wrapper around the GraphViz class. It emits a graph with function subgraphs for the vertices that are selected by the restrict parameter.

If showNeighbors is false then only edges whose source and target are both selected vertices are shown, otherwise edges that go from a selected vertex to an unselected vertex are also emitted, with the target vertex having abbreviated information in the GraphViz output.

This is only a simple wrapper around GraphViz::dumpInterval. That API has many more options than are presented by this method.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::vertexName ( const ControlFlowGraph::Vertex &  )
static

Name of a vertex.

Thread safety: Not thread safe.

std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::vertexName ( const ControlFlowGraph::ConstVertexIterator &  ) const

Name of a vertex.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::vertexNameEnd ( const ControlFlowGraph::Vertex &  )
static

Name of last instruction in vertex.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::edgeNameSrc ( const ControlFlowGraph::Edge &  )
static

Name of an incoming edge.

Thread safety: Not thread safe.

std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::edgeNameSrc ( const ControlFlowGraph::ConstEdgeIterator &  ) const

Name of an incoming edge.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::edgeNameDst ( const ControlFlowGraph::Edge &  )
static

Name of an outgoing edge.

Thread safety: Not thread safe.

std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::edgeNameDst ( const ControlFlowGraph::ConstEdgeIterator &  ) const

Name of an outgoing edge.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::edgeName ( const ControlFlowGraph::Edge &  )
static

Name of an edge.

Thread safety: Not thread safe.

std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::edgeName ( const ControlFlowGraph::ConstEdgeIterator &  ) const

Name of an edge.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::basicBlockName ( const BasicBlockPtr )
static

Name of a basic block.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::dataBlockName ( const DataBlockPtr )
static

Name of a data block.

Thread safety: Not thread safe.

static std::string Rose::BinaryAnalysis::Partitioner2::Partitioner::functionName ( const FunctionPtr )
static

Name of a function.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::expandIndeterminateCalls ( )

Expands indeterminate function calls.

Modifies the control flow graph so that any function call to the indeterminate vertex is replaced by function calls to every possible function.

Progress::Ptr Rose::BinaryAnalysis::Partitioner2::Partitioner::progress ( ) const

Property: How to report progress.

Partitioning progress is reported in two ways:

  • Various diagnostic facilities use the MARCH stream to emit a progress report to the terminal. These streams can be enabled and disabled from the command-line or with function calls using the Sawyer::Message API.
  • The partitioner also has a progress property that can be queried in thread-safe manners that allows one thread to run partitioner algorithms and other threads to query the progress.

If a non-null progress object is specified, then the partitioner will make progress reports to that object as well as emitting a progress bar to the Partitioner2 diagnostic stream. The progress bar can be disabled independently of reporting to a progress object, but no progress is reported if the progress object is null.

Thread safety: Thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::progress ( const Progress::Ptr )

Property: How to report progress.

Partitioning progress is reported in two ways:

  • Various diagnostic facilities use the MARCH stream to emit a progress report to the terminal. These streams can be enabled and disabled from the command-line or with function calls using the Sawyer::Message API.
  • The partitioner also has a progress property that can be queried in thread-safe manners that allows one thread to run partitioner algorithms and other threads to query the progress.

If a non-null progress object is specified, then the partitioner will make progress reports to that object as well as emitting a progress bar to the Partitioner2 diagnostic stream. The progress bar can be disabled independently of reporting to a progress object, but no progress is reported if the progress object is null.

Thread safety: Thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::updateProgress ( const std::string &  phase,
double  completion 
) const

Update partitioner with a new progress report.

This method is const because it doesn't change the partitioner, it only forwards the phase and completion to whatever Progress object is associated with the partition, if any.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::showStatistics ( ) const

Print some partitioner performance statistics.

SgAsmGenericSection* Rose::BinaryAnalysis::Partitioner2::Partitioner::elfGot ( SgAsmElfFileHeader )

Find the ELF global offset table and save its address.

Returns the GOT section and caches the section's actual mapped address.

See also, elfGotVa.

Sawyer::Optional<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::Partitioner::elfGotVa ( ) const

Returns a previously cached ELF GOT address.

See also, elfGot.

const BasePartitionerSettings& Rose::BinaryAnalysis::Partitioner2::Partitioner::settings ( ) const

Partitioner settings.

These are settings that are typically controlled from the command-line.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::settings ( const BasePartitionerSettings )

Partitioner settings.

These are settings that are typically controlled from the command-line.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::enableSymbolicSemantics ( bool  = true)

Use or not use symbolic semantics.

When true, a symbolic semantics domain will be used to reason about certain code properties such as successors for a basic block. When false, more naive but faster methods are used.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::disableSymbolicSemantics ( )

Use or not use symbolic semantics.

When true, a symbolic semantics domain will be used to reason about certain code properties such as successors for a basic block. When false, more naive but faster methods are used.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::usingSymbolicSemantics ( ) const

Use or not use symbolic semantics.

When true, a symbolic semantics domain will be used to reason about certain code properties such as successors for a basic block. When false, more naive but faster methods are used.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::autoAddCallReturnEdges ( bool  )

Property: Insert (or not) function call return edges.

When true, attaching a function call basic block to the CFG will create a call-return edge (E_CALL_RETURN) in the CFG even if the basic block has no explicit call-return edge and an analysis indicates that the callee (or at least one callee if there are more than one) may return. Call-return edges are typically the edge from a CALL instruction to the instruction immediately following in the address space.

If true, then the decision to add a call-return edge is made at the time the function call site is attached to the basic block, but the may-return analysis for the callees might be indeterminate at that time (such as if the callee instructions have not been discovered). The assumeCallsReturn partitioner property can be used to guess whether indeterminate may-return analysis should be assumed as a positive or negative result.

Deciding whether to add a call-return edge at the time of the call-site insertion can result in two kinds of errors: an extra CFG edge where there shouldn't be one, or a missing CFG edge where there should be one. An alternative is to turn off the autoAddCallReturnEdges property and delay the decision to a time when more information is available. This is the approach taken by the default Engine – it maintains a list of basic blocks that need to be investigated at a later time to determine if a call-return edge should be inserted, and it delays the decision as long as possible.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::autoAddCallReturnEdges ( ) const

Property: Insert (or not) function call return edges.

When true, attaching a function call basic block to the CFG will create a call-return edge (E_CALL_RETURN) in the CFG even if the basic block has no explicit call-return edge and an analysis indicates that the callee (or at least one callee if there are more than one) may return. Call-return edges are typically the edge from a CALL instruction to the instruction immediately following in the address space.

If true, then the decision to add a call-return edge is made at the time the function call site is attached to the basic block, but the may-return analysis for the callees might be indeterminate at that time (such as if the callee instructions have not been discovered). The assumeCallsReturn partitioner property can be used to guess whether indeterminate may-return analysis should be assumed as a positive or negative result.

Deciding whether to add a call-return edge at the time of the call-site insertion can result in two kinds of errors: an extra CFG edge where there shouldn't be one, or a missing CFG edge where there should be one. An alternative is to turn off the autoAddCallReturnEdges property and delay the decision to a time when more information is available. This is the approach taken by the default Engine – it maintains a list of basic blocks that need to be investigated at a later time to determine if a call-return edge should be inserted, and it delays the decision as long as possible.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::assumeFunctionsReturn ( bool  )

Property: Assume (or not) that function calls return.

If the may-return analysis is indeterminate and the partitioner needs to make an immediate decision about whether a function might return to its caller then this property is used. This property also determines whether the may-return analysis uses a whitelist or blacklist.

If this property is true, then functions are assumed to return unless it can be proven that they cannot. A blacklist is one way to prove that a function does not return. On the other hand, if this property is false then functions are assumed to not return unless it can be proven that they can. A whitelist is one way to prove that a function can return.

Thread safety: Not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::assumeFunctionsReturn ( ) const

Property: Assume (or not) that function calls return.

If the may-return analysis is indeterminate and the partitioner needs to make an immediate decision about whether a function might return to its caller then this property is used. This property also determines whether the may-return analysis uses a whitelist or blacklist.

If this property is true, then functions are assumed to return unless it can be proven that they cannot. A blacklist is one way to prove that a function does not return. On the other hand, if this property is false then functions are assumed to not return unless it can be proven that they can. A whitelist is one way to prove that a function can return.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::addressName ( rose_addr_t  ,
const std::string &   
)

Property: Name for address.

The partitioner stores a mapping from addresses to user specified names and uses those names when no other names are specified. For instance, if a function that has no name is attached to the CFG/AUM and a name has been specified for its entry address, then the function is given that name.

Thread safety: Not thread safe.

const std::string& Rose::BinaryAnalysis::Partitioner2::Partitioner::addressName ( rose_addr_t  ) const

Property: Name for address.

The partitioner stores a mapping from addresses to user specified names and uses those names when no other names are specified. For instance, if a function that has no name is attached to the CFG/AUM and a name has been specified for its entry address, then the function is given that name.

Thread safety: Not thread safe.

const AddressNameMap& Rose::BinaryAnalysis::Partitioner2::Partitioner::addressNames ( ) const

Property: Name for address.

The partitioner stores a mapping from addresses to user specified names and uses those names when no other names are specified. For instance, if a function that has no name is attached to the CFG/AUM and a name has been specified for its entry address, then the function is given that name.

Thread safety: Not thread safe.

const SourceLocations& Rose::BinaryAnalysis::Partitioner2::Partitioner::sourceLocations ( ) const

Property: Source locations.

The partitioner stores a mapping from source locations to virtual addresses and vice versa.

SourceLocations& Rose::BinaryAnalysis::Partitioner2::Partitioner::sourceLocations ( )

Property: Source locations.

The partitioner stores a mapping from source locations to virtual addresses and vice versa.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::sourceLocations ( const SourceLocations )

Property: Source locations.

The partitioner stores a mapping from source locations to virtual addresses and vice versa.

bool Rose::BinaryAnalysis::Partitioner2::Partitioner::checkingCallBranch ( ) const

Property: Whether to look for function calls used as branches.

If this property is set, then function call instructions are not automatically assumed to be actual function calls.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::checkingCallBranch ( bool  )

Property: Whether to look for function calls used as branches.

If this property is set, then function call instructions are not automatically assumed to be actual function calls.

Thread safety: Not thread safe.

SemanticMemoryParadigm Rose::BinaryAnalysis::Partitioner2::Partitioner::semanticMemoryParadigm ( ) const

Property: Whether to use map- or list-based memory states.

The partitioner can use either list-based memory states or map-based memory states. The list-based states are more precise, but the map-based states are faster. This property determines which kind of state is created by the newOperators method.

Thread safety: Not thread safe.

void Rose::BinaryAnalysis::Partitioner2::Partitioner::semanticMemoryParadigm ( SemanticMemoryParadigm  )

Property: Whether to use map- or list-based memory states.

The partitioner can use either list-based memory states or map-based memory states. The list-based states are more precise, but the map-based states are faster. This property determines which kind of state is created by the newOperators method.

Thread safety: Not thread safe.

SmtSolverPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::smtSolver ( ) const

SMT solver.

Returns the SMT solver being used for instruction semantics. The partitioner owns the solver, so the caller should not delete it. Some configurations will not use a solver, in which case the null pointer is returned.

Thread safety: Not thread safe.

InstructionSemantics::BaseSemantics::RiscOperatorsPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::newOperators ( ) const

Obtain new RiscOperators.

Creates a new instruction semantics infrastructure with a fresh machine state. The partitioner supports two kinds of memory state representations: list-based and map-based (see semanticMemoryParadigm). If the memory paradigm is not specified then the partitioner's default paradigm is used. Returns a null pointer if the architecture does not support semantics.

Thread safety: Not thread safe.

InstructionSemantics::BaseSemantics::RiscOperatorsPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::newOperators ( SemanticMemoryParadigm  ) const

Obtain new RiscOperators.

Creates a new instruction semantics infrastructure with a fresh machine state. The partitioner supports two kinds of memory state representations: list-based and map-based (see semanticMemoryParadigm). If the memory paradigm is not specified then the partitioner's default paradigm is used. Returns a null pointer if the architecture does not support semantics.

Thread safety: Not thread safe.

InstructionSemantics::BaseSemantics::DispatcherPtr Rose::BinaryAnalysis::Partitioner2::Partitioner::newDispatcher ( const InstructionSemantics::BaseSemantics::RiscOperatorsPtr ) const

Obtain a new instruction semantics dispatcher.

Creates and returns a new dispatcher for the instruction semantics framework. The dispatcher will contain a copy of the RiscOperators argument initialized with a new memory/register state. Returns a null pointer if instruction semantics are not supported for the specimen's architecture.

Thread safety: Not thread safe.


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