Description

Binary function detection.

This namespace consists of two major parts and a number of smaller parts. The major parts are:

Partitioner: The partitioner is responsible for organizing instructions into basic blocks and basic blocks into functions. It has methods to discover new parts of the executable, and methods to control how those parts are organized into larger parts. It queries a memory map and an instruction provider and updates a global control flow graph (CFG) and address usage map (AUM). Its operations are quite low-level and its behavior is customized primarily by callbacks.

Engine: The engine contains the higher-level functionality that drives the partitioner. Where the partitioner knows how to make a basic block or a function, the engine know where to make a basic block or function. The engine is customized by subclassing it and overriding various methods.

Disassembly techniques fall into two broad categories: linear disassembly and recursive disassembly. Linear disassembly progresses by starting at some low address in the specimen address space, disassembling one instruction, and then moving on to the next (fallthrough) address and repeating. This approach is quite good at disassembling everything (especially for fixed length instructions) but makes no attempt to organize instructions according to flow of control. On the other hand, recursive disassembly uses a work list containing known instruction addresses, disassembles an instruction from the worklist, determines its control flow successors, and adds those addresses to the work list. As a side effect, it produces a control flow graph.

ROSE supports both linear and recursive disassembly. Linear disassembly is trivial to implement: simply walk the memory map from beginning to end calling an InstructionProvider at each address. Recursive disassembly is where the rubber meets the road, so to speak, and the quality of the disassembly is intimately tied to the quality of the control flow graph. ROSE supports pure control flow reasoning, and combines that with heuristics to discover (or prevent discovery) where the control flow reasoning is deficient. For example, a pure control flow approach will miss dead code, but heuristics might be able to find the dead code at which time the control flow approach can continue. The trick is finding the right set of heuristics for a particular situation – if to permissive, they'll find code where it doesn't exist and which might interfere with the control flow reasoning; to restrictive and they could easily miss large parts of a specimen. Heuristics are mostly implemented as optional parts of an engine, or callbacks registered with the partitioner.

Namespaces
	AllowParallelEdges
	Flag whether to allow parallel edges in a graph.

	DataFlow
	Data-flow utilities.

	GraphViz
	Support for generating and reading GraphViz output.

	Modules
	Miscellaneous supporting functions for disassembly.

	ModulesElf
	Disassembly and partitioning utility functions for ELF.

	ModulesJvm
	Disassembly and partitioning utility functions for JVM.

	ModulesLinux
	Disassembly and partitioning utilities for Linux.

	ModulesM68k
	Disassembly and partitioning utility functions for M68k.

	ModulesMips
	Disassembly and partitioning utility functions for MIPS.

	ModulesPe
	Disassembly and partitioning utilities for PE files.

	ModulesPowerpc
	Disassembly and partitioning utilities for PowerPC.

	ModulesX86
	Disassembly and partitioning utilities for Intel x86 and amd64.

	Precision
	Level of precision for analysis.

	Semantics
	Instruction semantics for the partitioner.

Classes
class	AddressConfiguration
	Configuration for individual addresses. More...

class	AddressIntervalParser
	Parse an address interval. More...

class	AddressUsageMap
	Address usage map. More...

class	AddressUser
	Address usage item. More...

class	AddressUsers
	List of virtual address users. More...

struct	AstConstructionSettings
	Settings that control building the AST. More...

struct	BasePartitionerSettings
	Settings that directly control a partitioner. More...

class	BasicBlock
	Basic block information. More...

class	BasicBlockCallback
	Base class for adjusting basic blocks during discovery. More...

class	BasicBlockConfiguration
	Configuration information for a basic block. More...

class	BasicBlockError

class	BasicBlockSemantics
	Information related to instruction semantics. More...

class	BasicBlockSuccessor
	Basic block successor. More...

class	CfgAdjustmentCallback
	Base class for CFG-adjustment callbacks. More...

class	CfgEdge
	Control flow graph edge. More...

class	CfgPath
	A path through a control flow graph. More...

class	CfgVertex
	Control flow graph vertex. More...

class	Configuration
	Holds configuration information. More...

class	DataBlock
	Data block information. More...

class	DataBlockConfiguration
	Configuration information for a data block. More...

class	DataBlockError

struct	DisassemblerSettings
	Settings that control the disassembler. More...

class	Engine
	Base class for engines driving the partitioner. More...

class	EngineJvm
	Class for the JVM engine driving the partitioner. More...

struct	EngineSettings
	Settings for controling the engine behavior. More...

class	Exception

class	FileError

class	Function
	Describes one function. More...

class	FunctionCallGraph
	Function call information. More...

class	FunctionConfiguration
	Configuration information for a function. More...

class	FunctionError

class	FunctionPaddingMatcher
	Base class for matching function padding. More...

class	FunctionPrologueMatcher
	Base class for matching function prologues. More...

class	Inliner
	Binary inliner. More...

class	InstructionMatcher
	Base class for matching an instruction pattern. More...

struct	LoaderSettings
	Settings for loading specimens. More...

class	Partitioner
	Partitions instructions into basic blocks and functions. More...

struct	PartitionerSettings
	Settings that control the engine partitioning. More...

class	PlaceholderError

class	Reference
	Reference to a function, basic block, instruction, or address. More...

struct	ThunkDetection
	Return type for thunk detectors. More...

class	ThunkPredicates
	List of thunk predicates. More...

class	Trigger
	Trigger based on number of times called. More...

Typedefs
using	BasicBlockPtr = Sawyer::SharedPointer< BasicBlock >
	Shared-ownersip pointer for BasicBlock. More...

using	BasicBlockCallbackPtr = Sawyer::SharedPointer< BasicBlockCallback >
	Shared ownership pointer. More...

using	BasicBlockSuccessors = std::vector< BasicBlockSuccessor >
	All successors in no particular order. More...

using	ControlFlowGraph = Sawyer::Container::Graph< CfgVertex, CfgEdge >
	Control flow graph. More...

using	DataBlockPtr = Sawyer::SharedPointer< DataBlock >
	Shared-ownership pointer for DataBlock. More...

using	FunctionPtr = Sawyer::SharedPointer< Function >
	Shared-ownership pointer for Function. More...

using	Functions = Sawyer::Container::Map< rose_addr_t, FunctionPtr >
	Mapping from address to function. More...

using	FunctionPaddingMatcherPtr = Sawyer::SharedPointer< FunctionPaddingMatcher >
	Shared ownership pointer. More...

using	FunctionPrologueMatcherPtr = Sawyer::SharedPointer< FunctionPrologueMatcher >
	Shared ownership pointer. More...

using	FunctionSet = Sawyer::Container::Set< FunctionPtr >
	Set of functions. More...

using	PartitionerPtr = Sawyer::SharedPointer< Partitioner >
	Shared-ownership pointer for Partitioner. More...

using	PartitionerConstPtr = Sawyer::SharedPointer< const Partitioner >
	Shared-ownership pointer for Partitioner. More...

using	ReferenceSet = std::set< Reference >
	Set of references. More...

using	CrossReferences = Sawyer::Container::Map< Reference, ReferenceSet >
	Cross references. More...

using	ThunkPredicatesPtr = Sawyer::SharedPointer< ThunkPredicates >
	Shared-ownership pointer for ThunkPredicates. More...

typedef Sawyer::Container::HashMap< rose_addr_t, ControlFlowGraph::VertexIterator >	CfgVertexIndex
	Mapping from basic block starting address to CFG vertex. More...

typedef Sawyer::Container::GraphIteratorBiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator >	CfgVertexMap
	Map vertices from one CFG to another CFG and vice versa. More...

typedef ThunkDetection(*	ThunkPredicate) (const PartitionerConstPtr &, const std::vector< SgAsmInstruction * > &)
	Function signature for finding thunks. More...


typedef std::list< ControlFlowGraph::VertexIterator >	CfgVertexList
	List of CFG vertex pointers.

typedef std::list< ControlFlowGraph::ConstVertexIterator >	CfgConstVertexList
	List of CFG vertex pointers.


typedef std::list< ControlFlowGraph::EdgeIterator >	CfgEdgeList
	List of CFG edge pointers.

typedef std::list< ControlFlowGraph::ConstEdgeIterator >	CfgConstEdgeList
	List of CFG edge pointers.


typedef Sawyer::Container::GraphIteratorSet< ControlFlowGraph::VertexIterator >	CfgVertexSet
	Set of CFG vertex pointers.

typedef Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstVertexIterator >	CfgConstVertexSet
	Set of CFG vertex pointers.


typedef Sawyer::Container::GraphIteratorSet< ControlFlowGraph::EdgeIterator >	CfgEdgeSet
	Set of CFG edge pointers.

typedef Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstEdgeIterator >	CfgConstEdgeSet
	Set of CFG edge pointers.

Enumerations
enum	VertexType { V_BASIC_BLOCK, V_UNDISCOVERED, V_INDETERMINATE, V_NONEXISTING, V_USER_DEFINED }
	Partitioner control flow vertex types. More...

enum	EdgeType { E_NORMAL = 0x00000001, E_FUNCTION_CALL = 0x00000002, E_FUNCTION_RETURN = 0x00000004, E_CALL_RETURN = 0x00000008, E_FUNCTION_XFER = 0x00000010, E_USER_DEFINED = 0x00000020 }
	Partitioner control flow edge types. More...

enum	Confidence { ASSUMED, PROVED }
	How sure are we of something. More...

enum	SemanticMemoryParadigm { LIST_BASED_MEMORY, MAP_BASED_MEMORY }
	Organization of semantic memory. More...

enum	MemoryDataAdjustment { DATA_IS_CONSTANT, DATA_IS_INITIALIZED, DATA_NO_CHANGE }
	How the partitioner should globally treat memory. More...

enum	FunctionReturnAnalysis { MAYRETURN_DEFAULT_YES, MAYRETURN_DEFAULT_NO, MAYRETURN_ALWAYS_YES, MAYRETURN_ALWAYS_NO }
	Controls whether the function may-return analysis runs. More...

Functions
CfgConstEdgeSet	findPathReachableEdges (const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
	Find edges that are reachable. More...

CfgConstEdgeSet	findPathUnreachableEdges (const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
	Find edges that are unreachable. More...

size_t	eraseUnreachablePaths (ControlFlowGraph &graph, CfgConstVertexSet &beginVertices, CfgConstVertexSet &endVertices, CfgVertexMap &vmap, CfgPath &path)
	Remove edges and vertices that cannot be on the paths. More...

void	findPaths (const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
	Compute all paths. More...

void	findPaths (const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
	Compute all paths. More...

std::ostream &	operator<< (std::ostream &out, const CfgPath &path)

bool	sortEdgesBySrc (const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
	Sort edges by source vertex address. More...

bool	sortEdgesByDst (const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
	Sort edges by target vertex address. More...

bool	sortEdgesById (const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
	Sort edges by edge ID number. More...

bool	sortVerticesByAddress (const ControlFlowGraph::ConstVertexIterator &, const ControlFlowGraph::ConstVertexIterator &)
	Sort vertices by address. More...

bool	sortVerticesById (const ControlFlowGraph::ConstVertexIterator &, const ControlFlowGraph::ConstVertexIterator &)
	Sort vertices by vertex ID number. More...

std::ostream &	operator<< (std::ostream &, const ControlFlowGraph::Vertex &)
	Print control flow graph vertex. More...

std::ostream &	operator<< (std::ostream &, const ControlFlowGraph::Edge &)
	Print control flow graph edge. More...

void	insertCfg (ControlFlowGraph &dst, const ControlFlowGraph &src, CfgVertexMap &vmap)
	Insert one control flow graph into another. More...

CfgConstEdgeSet	findBackEdges (const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin)
	Find back edges. More...

CfgConstEdgeSet	findCallEdges (const ControlFlowGraph::ConstVertexIterator &callSite)
	Find function call edges. More...

CfgConstVertexSet	findCalledFunctions (const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite)
	Find called functions. More...

CfgConstVertexSet	findFunctionReturns (const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex)
	Find all function return vertices. More...

void	eraseEdges (ControlFlowGraph &, const CfgConstEdgeSet &toErase)
	Erase multiple edges. More...

CfgConstVertexSet	findIncidentVertices (const CfgConstEdgeSet &)
	Vertices that are incident to specified edges. More...

CfgConstVertexSet	forwardMapped (const CfgConstVertexSet &, const CfgVertexMap &)
	Return corresponding iterators. More...

CfgConstVertexSet	reverseMapped (const CfgConstVertexSet &, const CfgVertexMap &)
	Return corresponding iterators. More...

void	expandFunctionReturnEdges (const PartitionerConstPtr &, ControlFlowGraph &cfg)
	Rewrite function return edges. More...

ControlFlowGraph	functionCfgByErasure (const ControlFlowGraph &gcfg, const FunctionPtr &function, ControlFlowGraph::VertexIterator &entry)
	Generate a function control flow graph. More...

ControlFlowGraph	functionCfgByReachability (const ControlFlowGraph &gcfg, const FunctionPtr &function, const ControlFlowGraph::ConstVertexIterator &gcfgEntry)
	Generate a function control flow graph. More...

ThunkDetection	isX86JmpImmThunk (const PartitionerConstPtr &, const std::vector< SgAsmInstruction * > &)
	Test whether x86 instructions begin with "jmp ADDRESS". More...

ThunkDetection	isX86JmpMemThunk (const PartitionerConstPtr &, const std::vector< SgAsmInstruction * > &)
	Test whether x86 instruction begin with "jmp [ADDRESS]". More...

ThunkDetection	isX86LeaJmpThunk (const PartitionerConstPtr &, const std::vector< SgAsmInstruction * > &)
	Test whether x86 instructions begin with an LEA JMP pair. More...

ThunkDetection	isX86MovJmpThunk (const PartitionerConstPtr &, const std::vector< SgAsmInstruction * > &)
	Test whether x86 instructions begin with "mov R, [ADDR]; jmp R". More...

ThunkDetection	isX86AddJmpThunk (const PartitionerConstPtr &, const std::vector< SgAsmInstruction * > &)
	Test whether x86 instructions begin with "add R, C; jmp ADDR". More...

void	splitThunkFunctions (const PartitionerPtr &, const ThunkPredicates::Ptr &)
	Split thunks off from start of functions. More...

void	initDiagnostics ()

bool	sortBasicBlocksByAddress (const BasicBlockPtr &, const BasicBlockPtr &)

bool	sortDataBlocks (const DataBlockPtr &, const DataBlockPtr &)

bool	sortFunctionsByAddress (const FunctionPtr &, const FunctionPtr &)

bool	sortFunctionNodesByAddress (const SgAsmFunction , const SgAsmFunction )

bool	sortByExpression (const BasicBlockSuccessor &, const BasicBlockSuccessor &)

bool	sortBlocksForAst (SgAsmBlock , SgAsmBlock )

bool	sortInstructionsByAddress (SgAsmInstruction , SgAsmInstruction )

template<class Container , class Value , class Comparator >
Container::const_iterator	lowerBound (const Container &container, const Value &item, Comparator cmp)

template<class Container , class Value , class Comparator >
Container::iterator	lowerBound (Container &container, const Value &item, Comparator cmp)

template<class Value , class Comparator >
bool	equalUnique (const Value &a, const Value &b, Comparator cmp)

template<class Container , class Value , class Comparator >
bool	insertUnique (Container &container, const Value &item, Comparator cmp)

template<class Container , class Value , class Comparator >
void	replaceOrInsert (Container &container, const Value &item, Comparator cmp)

template<class Container , class Value , class Comparator >
bool	eraseUnique (Container &container, const Value &item, Comparator cmp)

template<class Container , class Value , class Comparator >
bool	existsUnique (const Container &container, const Value &item, Comparator cmp)

template<class Container , class Value , class Comparator >
Sawyer::Optional< Value >	getUnique (const Container &container, const Value &item, Comparator cmp)

template<class Container , class Value , class Comparator >
Sawyer::Optional< Value >	getOrInsertUnique (Container &container, const Value &item, Comparator cmp)

template<class Container , class Comparator >
bool	isSupersetUnique (const Container &sup, const Container &sub, Comparator lessThan)

std::ostream &	operator<< (std::ostream &, const AddressUser &)

std::ostream &	operator<< (std::ostream &, const AddressUsers &)

std::ostream &	operator<< (std::ostream &, const AddressUsageMap &)

AddressIntervalParser::Ptr	addressIntervalParser (AddressInterval &storage)

AddressIntervalParser::Ptr	addressIntervalParser (std::vector< AddressInterval > &storage)

AddressIntervalParser::Ptr	addressIntervalParser (AddressIntervalSet &storage)

AddressIntervalParser::Ptr	addressIntervalParser ()

size_t	serialNumber ()
	Return the next serial number. More...


std::vector< bool >	findPathEdges (const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
	Finds edges that can be part of some path. More...

std::vector< bool >	findPathEdges (const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
	Finds edges that can be part of some path. More...


void	findFunctionPaths (const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
	Compute all paths within one function. More...

void	findFunctionPaths (const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
	Compute all paths within one function. More...


void	findInterFunctionPaths (const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
	Compute all paths across function calls and returns. More...

void	findInterFunctionPaths (const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
	Compute all paths across function calls and returns. More...


bool	inlineMultipleCallees (ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite, const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallSite, const CfgConstVertexSet &cfgAvoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &cfgAvoidEdges=CfgConstEdgeSet(), std::vector< ControlFlowGraph::ConstVertexIterator > *newEdges=nullptr)
	Inline a function at the specified call site. More...

bool	inlineOneCallee (ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite, const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallTarget, const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges, std::vector< ControlFlowGraph::ConstVertexIterator > *newVertices=nullptr)
	Inline a function at the specified call site. More...


CfgConstEdgeSet	findCallReturnEdges (const PartitionerConstPtr &, const ControlFlowGraph &)
	Return outgoing call-return edges. More...

CfgConstEdgeSet	findCallReturnEdges (const ControlFlowGraph::ConstVertexIterator &callSite)
	Return outgoing call-return edges. More...


Sawyer::Container::Map< FunctionPtr, CfgConstEdgeSet >	findFunctionReturnEdges (const PartitionerConstPtr &)
	Find function return edges organized by function. More...

Sawyer::Container::Map< FunctionPtr, CfgConstEdgeSet >	findFunctionReturnEdges (const PartitionerConstPtr &, const ControlFlowGraph &)
	Find function return edges organized by function. More...


CfgConstVertexSet	findDetachedVertices (const ControlFlowGraph &)
	Find vertices that have zero degree. More...

CfgConstVertexSet	findDetachedVertices (const CfgConstVertexSet &vertices)
	Find vertices that have zero degree. More...

Variables
Sawyer::Message::Facility	mlog

Typedef Documentation

using Rose::BinaryAnalysis::Partitioner2::BasicBlockPtr = typedef Sawyer::SharedPointer<BasicBlock>

Shared-ownersip pointer for BasicBlock.

Definition at line 810 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::BasicBlockCallbackPtr = typedef Sawyer::SharedPointer<BasicBlockCallback>

Shared ownership pointer.

Definition at line 815 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::BasicBlockSuccessors = typedef std::vector<BasicBlockSuccessor>

All successors in no particular order.

Definition at line 818 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::ControlFlowGraph = typedef Sawyer::Container::Graph<CfgVertex, CfgEdge>

Control flow graph.

Definition at line 826 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::DataBlockPtr = typedef Sawyer::SharedPointer<DataBlock>

Shared-ownership pointer for DataBlock.

Definition at line 831 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

typedef Sawyer::SharedPointer< class Function > Rose::BinaryAnalysis::Partitioner2::FunctionPtr

Shared-ownership pointer for Function.

Shared-ownership pointer for function.

Definition at line 838 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::Functions = typedef Sawyer::Container::Map<rose_addr_t, FunctionPtr>

Mapping from address to function.

Definition at line 840 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::FunctionPaddingMatcherPtr = typedef Sawyer::SharedPointer<FunctionPaddingMatcher>

Shared ownership pointer.

Definition at line 845 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::FunctionPrologueMatcherPtr = typedef Sawyer::SharedPointer<FunctionPrologueMatcher>

Shared ownership pointer.

Definition at line 848 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::FunctionSet = typedef Sawyer::Container::Set<FunctionPtr>

Set of functions.

Definition at line 850 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::PartitionerPtr = typedef Sawyer::SharedPointer<Partitioner>

Shared-ownership pointer for Partitioner.

Definition at line 855 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::PartitionerConstPtr = typedef Sawyer::SharedPointer<const Partitioner>

Shared-ownership pointer for Partitioner.

Definition at line 856 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::ReferenceSet = typedef std::set<Reference>

Set of references.

Definition at line 861 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::CrossReferences = typedef Sawyer::Container::Map<Reference, ReferenceSet>

Cross references.

Definition at line 862 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

using Rose::BinaryAnalysis::Partitioner2::ThunkPredicatesPtr = typedef Sawyer::SharedPointer<ThunkPredicates>

Shared-ownership pointer for ThunkPredicates.

Definition at line 865 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

typedef Sawyer::Container::HashMap<rose_addr_t, ControlFlowGraph::VertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgVertexIndex

Mapping from basic block starting address to CFG vertex.

Definition at line 207 of file ControlFlowGraph.h.

typedef Sawyer::Container::GraphIteratorBiMap<ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgVertexMap

Map vertices from one CFG to another CFG and vice versa.

Definition at line 239 of file ControlFlowGraph.h.

typedef ThunkDetection(* Rose::BinaryAnalysis::Partitioner2::ThunkPredicate) (const PartitionerConstPtr &, const std::vector< SgAsmInstruction * > &)

Function signature for finding thunks.

These functions take a partitioner and a sequence of one or more instructions disassembled from memory and determine if the sequence begins with instructions that look like a thunk of some sort. If they do, then the function returns the number of initial instructions that compose the thunk and the name of the pattern that matched, otherwise it returns zero and an empty string.

Definition at line 79 of file Thunk.h.

Enumeration Type Documentation

enum Rose::BinaryAnalysis::Partitioner2::VertexType

Partitioner control flow vertex types.

Enumerator
V_BASIC_BLOCK	A basic block or placeholder for a basic block.
V_UNDISCOVERED	The special "undiscovered" vertex.
V_INDETERMINATE	Special vertex destination for indeterminate edges.
V_NONEXISTING	Special vertex destination for non-existing basic blocks.
V_USER_DEFINED	User defined vertex. These vertices don't normally appear in the global control flow graph but might appear in other kinds of graphs that are closely related to a CFG, such as a paths graph.

Definition at line 78 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

enum Rose::BinaryAnalysis::Partitioner2::EdgeType

Partitioner control flow edge types.

Enumerator
E_NORMAL	Normal control flow edge, nothing special.
E_FUNCTION_CALL	Edge is a function call.
E_FUNCTION_RETURN	Edge is a function return. Such edges represent the actual return-to-caller and usually originate from a return instruction (e.g., x86 `RET`, m68k `RTS`, etc.).
E_CALL_RETURN	Edge is a function return from the call site. Such edges are from a caller basic block to (probably) the fall-through address of the call and don't actually exist directly in the specimen. They represent the fact that the called function eventually returns even if the instructions for the called function are not available to analyze.
E_FUNCTION_XFER	Edge is a function call transfer. A function call transfer is similar to E_FUNCTION_CALL except the entire call frame is transferred to the target function and this function is no longer considered part of the call stack; a return from the target function will skip over this function. Function call transfers most often occur as the edge leaving a thunk.
E_USER_DEFINED	User defined edge. These edges don't normally appear in the global control flow graph but might appear in other kinds of graphs that are closely related to a CFG, such as a paths graph.

Definition at line 89 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

enum Rose::BinaryAnalysis::Partitioner2::Confidence

How sure are we of something.

Enumerator
ASSUMED	The value is an assumption without any proof.
PROVED	The value was somehow proved.

Definition at line 113 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

enum Rose::BinaryAnalysis::Partitioner2::SemanticMemoryParadigm

Organization of semantic memory.

Enumerator
LIST_BASED_MEMORY	Precise but slow.
MAP_BASED_MEMORY	Fast but not precise.

Definition at line 119 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

enum Rose::BinaryAnalysis::Partitioner2::MemoryDataAdjustment

How the partitioner should globally treat memory.

Enumerator

DATA_IS_CONSTANT

Treat all memory as if it were constant.

This is accomplished by removing MemoryMap::READABLE from all segments.

DATA_IS_INITIALIZED

Treat all memory as if it were initialized.

This is a little weaker than MEMORY_IS_CONSTANT in that it allows the partitioner to read the value from memory as if it were constant, but also marks the value as being indeterminate. This is accomplished by adding MemoryMap::INITIALIZED to all segments.

DATA_NO_CHANGE

Do not make any global changes to the memory map.

Definition at line 212 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

enum Rose::BinaryAnalysis::Partitioner2::FunctionReturnAnalysis

Controls whether the function may-return analysis runs.

Enumerator
MAYRETURN_DEFAULT_YES	Assume a function returns if the may-return analysis cannot decide whether it may return.
MAYRETURN_DEFAULT_NO	Assume a function cannot return if the may-return analysis cannot decide whether it may return.
MAYRETURN_ALWAYS_YES	Assume that all functions return without ever running the may-return analysis.
MAYRETURN_ALWAYS_NO	Assume that a function cannot return without ever running the may-return analysis.

Definition at line 370 of file BinaryAnalysis/Partitioner2/BasicTypes.h.

Function Documentation

std::vector<bool> Rose::BinaryAnalysis::Partitioner2::findPathEdges	(	const ControlFlowGraph &	graph,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`,
		bool	avoidCallsAndReturns = `false`
	)

Finds edges that can be part of some path.

Returns a Boolean vector indicating whether an edge is significant. An edge is significant if it appears on some path that originates from some vertex in beginVertices and reaches some vertex in endVertices (if endVertices is supplied) but is not a member of avoidEdges and is not incident to any vertex in avoidVertices. An edge is not significant if it is a function call or function return and avoidCallsAndReturns is true.

std::vector<bool> Rose::BinaryAnalysis::Partitioner2::findPathEdges	(	const ControlFlowGraph &	graph,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	endVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`,
		bool	avoidCallsAndReturns = `false`
	)

Finds edges that can be part of some path.

Returns a Boolean vector indicating whether an edge is significant. An edge is significant if it appears on some path that originates from some vertex in beginVertices and reaches some vertex in endVertices (if endVertices is supplied) but is not a member of avoidEdges and is not incident to any vertex in avoidVertices. An edge is not significant if it is a function call or function return and avoidCallsAndReturns is true.

CfgConstEdgeSet Rose::BinaryAnalysis::Partitioner2::findPathReachableEdges	(	const ControlFlowGraph &	graph,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	endVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`,
		bool	avoidCallsAndReturns = `false`
	)

Find edges that are reachable.

Finds edges that are part of some path from any of the beginVertices to any of the endVertices. The paths that are considered must not traverse the avoidEdges or avoidVertices.

CfgConstEdgeSet Rose::BinaryAnalysis::Partitioner2::findPathUnreachableEdges	(	const ControlFlowGraph &	graph,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	endVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`,
		bool	avoidCallsAndReturns = `false`
	)

Find edges that are unreachable.

Finds edges that are not part of any path from any of the beginVertices to any of the endVertices. The paths that are considered must not traverse the avoidEdges or avoidVertices.

size_t Rose::BinaryAnalysis::Partitioner2::eraseUnreachablePaths	(	ControlFlowGraph &	graph,
		CfgConstVertexSet &	beginVertices,
		CfgConstVertexSet &	endVertices,
		CfgVertexMap &	vmap,
		CfgPath &	path
	)

Remove edges and vertices that cannot be on the paths.

Removes those edges that aren't reachable in both forward and reverse directions between the specified begin and end vertices. Specified vertices must belong to the graph. After edges are removed, dangling vertices are removed. Vertices and edges are removed from all arguments. Removal of edges from path causes the path to be truncated.

Returns the number of edges that were removed from the path.

void Rose::BinaryAnalysis::Partitioner2::findPaths	(	const ControlFlowGraph &	srcCfg,
		ControlFlowGraph &	paths,
		CfgVertexMap &	vmap,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	endVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`,
		bool	avoidCallsAndReturns = `false`
	)

Compute all paths.

Computes all paths from any beginVertices to any endVertices if that does not go through any avoidVertices or avoidEdges. The paths are returned as a paths graph (CFG) so that cycles can be represented. A paths graph can represent an exponential number of paths. The paths graph is formed by taking the global CFG and removing all avoidVertices and avoidEdges, any edge that cannot appear on a path from the beginVertex to any endVertices, and any vertex that has degree zero provided it is not one of the beginVertices.

If avoidCallsAndReturns is true then E_FUNCTION_CALL and E_FUNCTION_RETURN edges are not followed. Note that the normal partitioner CFG will have E_CALL_RETURN edges that essentially short circuit a call to a function that might return, and that E_FUNCTION_RETURN edges normally point to the indeterminate vertex rather than concrete return targets.

If the returned graph, paths, is empty then no paths were found. If the returned graph has a vertex but no edges then the vertex serves as both the begin and end of the path (i.e., a single path of unit length). The vmap is updated to indicate the mapping from srcCfg vertices in the corresponding vertices in the returned graph.

void Rose::BinaryAnalysis::Partitioner2::findPaths	(	const ControlFlowGraph &	srcCfg,
		ControlFlowGraph &	paths,
		CfgVertexMap &	vmap,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`,
		bool	avoidCallsAndReturns = `false`
	)

Compute all paths.

Compute all paths that originate from any beginVertices and do not go through any avoidVertices or avoidEdges. The paths are returned as a paths graph (CFG) so that cycles can be represented. A paths graph can represent an exponential number of paths. The paths graph is formed by taking the global CFG and removing all avoidVertices and avoidEdges, and any vertex that has degree zero provided it is not one of the beginVertices.

If avoidCallsAndReturns is true then E_FUNCTION_CALL and E_FUNCTION_RETURN edges are not followed. Note that the normal partitioner CFG will have E_CALL_RETURN edges that essentially short circuit a call to a function that might return, and that E_FUNCTION_RETURN edges normally point to the indeterminate vertex rather than concrete return targets.

If the returned graph, paths, is empty then no paths were found. If the returned graph has a vertex but no edges then the vertex serves as both the begin and end of the path (i.e., a single path of unit length). The vmap is updated to indicate the mapping from srcCfg vertices in the corresponding vertices in the returned graph.

void Rose::BinaryAnalysis::Partitioner2::findFunctionPaths	(	const ControlFlowGraph &	srcCfg,
		ControlFlowGraph &	paths,
		CfgVertexMap &	vmap,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`
	)

Compute all paths within one function.

This is a convenience method for findPaths in a mode that avoids function call and return edges.

void Rose::BinaryAnalysis::Partitioner2::findFunctionPaths	(	const ControlFlowGraph &	srcCfg,
		ControlFlowGraph &	paths,
		CfgVertexMap &	vmap,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	endVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`
	)

Compute all paths within one function.

This is a convenience method for findPaths in a mode that avoids function call and return edges.

void Rose::BinaryAnalysis::Partitioner2::findInterFunctionPaths	(	const ControlFlowGraph &	srcCfg,
		ControlFlowGraph &	paths,
		CfgVertexMap &	vmap,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`
	)

Compute all paths across function calls and returns.

This is a convenience method for findPaths in a mode that follows function call and return edges. Note that in the normal partitioner CFG function return edges point to the indeterminate vertex rather than back to the place the function was called. In order to get call-sensitive paths you'll have to do something else.

void Rose::BinaryAnalysis::Partitioner2::findInterFunctionPaths	(	const ControlFlowGraph &	srcCfg,
		ControlFlowGraph &	paths,
		CfgVertexMap &	vmap,
		const CfgConstVertexSet &	beginVertices,
		const CfgConstVertexSet &	endVertices,
		const CfgConstVertexSet &	avoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	avoidEdges = `CfgConstEdgeSet()`
	)

Compute all paths across function calls and returns.

This is a convenience method for findPaths in a mode that follows function call and return edges. Note that in the normal partitioner CFG function return edges point to the indeterminate vertex rather than back to the place the function was called. In order to get call-sensitive paths you'll have to do something else.

bool Rose::BinaryAnalysis::Partitioner2::inlineMultipleCallees	(	ControlFlowGraph &	paths,
		const ControlFlowGraph::ConstVertexIterator &	pathsCallSite,
		const ControlFlowGraph &	cfg,
		const ControlFlowGraph::ConstVertexIterator &	cfgCallSite,
		const CfgConstVertexSet &	cfgAvoidVertices = `CfgConstVertexSet()`,
		const CfgConstEdgeSet &	cfgAvoidEdges = `CfgConstEdgeSet()`,
		std::vector< ControlFlowGraph::ConstVertexIterator > *	newEdges = `nullptr`
	)

Inline a function at the specified call site.

The paths graph is modified in place by inserting an inlined copy of the function(s) called from the specified pathsCallSite vertex. The pathsCallSite only serves as the attachment point–it must have the E_CALL_RETURN edge(s) but does not need any E_FUNCTION_CALL edges. The cfgCallSite is the vertex in the cfg corresponding to the pathsCallSite in the paths graph and provides information about which functions are called.

There are two similar functions: one inlines all the functions called from a particular call site in the CFG, the other inlines one specific function specified by its entry vertex. In the latter case, the CFG doesn't actually need to have an edge to the called function.

Usually, cfgCallSite has one outgoing E_FUNCTION_CALL edge and pathsCallSite (and cfgCallSite) has one outgoing E_CALL_RETURN edge. If the pathsCallSite has no E_CALL_RETURN edge, or the called function has no return sites, this operation is a no-op. A call site may call multiple functions, in which case each is inserted, even if some E_FUNCTION_CALL edges point to the same function. A called function may return to multiple addresses, such as longjmp, in which case multiple E_CALL_RETURN edges may be present–all return sites are linked to all return targets by this operation.

The vertices and edges in the inlined version that correspond to the cfgAvoidEVertices and cfgAvoidEdges are not copied into the paths graph. If this results in the called function having no paths that can return, then that function is not inserted into paths.

The E_CALL_RETURN edges in paths are not erased by this operation, but are usually subsequently erased by the user since they are redundant after this insertion–they represent a short-circuit over the called function(s).

Returns true if some function was inserted, false if no changes were made to paths. If newVertices is non-null then all newly inserted vertices are also pushed onto the end of the vector.

bool Rose::BinaryAnalysis::Partitioner2::inlineOneCallee	(	ControlFlowGraph &	paths,
		const ControlFlowGraph::ConstVertexIterator &	pathsCallSite,
		const ControlFlowGraph &	cfg,
		const ControlFlowGraph::ConstVertexIterator &	cfgCallTarget,
		const CfgConstVertexSet &	cfgAvoidVertices,
		const CfgConstEdgeSet &	cfgAvoidEdges,
		std::vector< ControlFlowGraph::ConstVertexIterator > *	newVertices = `nullptr`
	)

Inline a function at the specified call site.

The paths graph is modified in place by inserting an inlined copy of the function(s) called from the specified pathsCallSite vertex. The pathsCallSite only serves as the attachment point–it must have the E_CALL_RETURN edge(s) but does not need any E_FUNCTION_CALL edges. The cfgCallSite is the vertex in the cfg corresponding to the pathsCallSite in the paths graph and provides information about which functions are called.

There are two similar functions: one inlines all the functions called from a particular call site in the CFG, the other inlines one specific function specified by its entry vertex. In the latter case, the CFG doesn't actually need to have an edge to the called function.

Usually, cfgCallSite has one outgoing E_FUNCTION_CALL edge and pathsCallSite (and cfgCallSite) has one outgoing E_CALL_RETURN edge. If the pathsCallSite has no E_CALL_RETURN edge, or the called function has no return sites, this operation is a no-op. A call site may call multiple functions, in which case each is inserted, even if some E_FUNCTION_CALL edges point to the same function. A called function may return to multiple addresses, such as longjmp, in which case multiple E_CALL_RETURN edges may be present–all return sites are linked to all return targets by this operation.

The vertices and edges in the inlined version that correspond to the cfgAvoidEVertices and cfgAvoidEdges are not copied into the paths graph. If this results in the called function having no paths that can return, then that function is not inserted into paths.

The E_CALL_RETURN edges in paths are not erased by this operation, but are usually subsequently erased by the user since they are redundant after this insertion–they represent a short-circuit over the called function(s).

Returns true if some function was inserted, false if no changes were made to paths. If newVertices is non-null then all newly inserted vertices are also pushed onto the end of the vector.

bool Rose::BinaryAnalysis::Partitioner2::sortEdgesBySrc	(	const ControlFlowGraph::ConstEdgeIterator &	,
		const ControlFlowGraph::ConstEdgeIterator &
	)

Sort edges by source vertex address.

bool Rose::BinaryAnalysis::Partitioner2::sortEdgesByDst	(	const ControlFlowGraph::ConstEdgeIterator &	,
		const ControlFlowGraph::ConstEdgeIterator &
	)

Sort edges by target vertex address.

bool Rose::BinaryAnalysis::Partitioner2::sortEdgesById	(	const ControlFlowGraph::ConstEdgeIterator &	,
		const ControlFlowGraph::ConstEdgeIterator &
	)

Sort edges by edge ID number.

bool Rose::BinaryAnalysis::Partitioner2::sortVerticesByAddress	(	const ControlFlowGraph::ConstVertexIterator &	,
		const ControlFlowGraph::ConstVertexIterator &
	)

Sort vertices by address.

bool Rose::BinaryAnalysis::Partitioner2::sortVerticesById	(	const ControlFlowGraph::ConstVertexIterator &	,
		const ControlFlowGraph::ConstVertexIterator &
	)

Sort vertices by vertex ID number.

std::ostream& Rose::BinaryAnalysis::Partitioner2::operator<<	(	std::ostream &	,
		const ControlFlowGraph::Vertex &
	)

Print control flow graph vertex.

std::ostream& Rose::BinaryAnalysis::Partitioner2::operator<<	(	std::ostream &	,
		const ControlFlowGraph::Edge &
	)

Print control flow graph edge.

void Rose::BinaryAnalysis::Partitioner2::insertCfg	(	ControlFlowGraph &	dst,
		const ControlFlowGraph &	src,
		CfgVertexMap &	vmap
	)

Insert one control flow graph into another.

The vmap is updated with the mapping of vertices from source to destination. Upon return, vmap[srcVertex] will point to the corresponding vertex in the destination graph.

CfgConstEdgeSet Rose::BinaryAnalysis::Partitioner2::findBackEdges	(	const ControlFlowGraph &	cfg,
		const ControlFlowGraph::ConstVertexIterator &	begin
	)

Find back edges.

Performs a depth-first forward traversal of the cfg beginning at the specified vertex. Any edge encountered which points back to some vertex in the current traversal path is added to the returned edge set.

CfgConstEdgeSet Rose::BinaryAnalysis::Partitioner2::findCallEdges ( const ControlFlowGraph::ConstVertexIterator & callSite )

Find function call edges.

Returns the list of function call edges for the specified vertex.

CfgConstVertexSet Rose::BinaryAnalysis::Partitioner2::findCalledFunctions	(	const ControlFlowGraph &	cfg,
		const ControlFlowGraph::ConstVertexIterator &	callSite
	)

Find called functions.

Given some vertex in a CFG, return the vertices representing the functions that are called.

CfgConstEdgeSet Rose::BinaryAnalysis::Partitioner2::findCallReturnEdges	(	const PartitionerConstPtr &	,
		const ControlFlowGraph &
	)

Return outgoing call-return edges.

A call-return edge represents a short-circuit control flow path across a function call, from the call site to the return target.

If a partitioner and control flow graph are specified, then this returns all edges of type E_CALL_RETURN. If a vertex is specified, then it returns only those call-return edges that emanate from said vertex.

CfgConstEdgeSet Rose::BinaryAnalysis::Partitioner2::findCallReturnEdges ( const ControlFlowGraph::ConstVertexIterator & callSite )

Return outgoing call-return edges.

A call-return edge represents a short-circuit control flow path across a function call, from the call site to the return target.

If a partitioner and control flow graph are specified, then this returns all edges of type E_CALL_RETURN. If a vertex is specified, then it returns only those call-return edges that emanate from said vertex.

CfgConstVertexSet Rose::BinaryAnalysis::Partitioner2::findFunctionReturns	(	const ControlFlowGraph &	cfg,
		const ControlFlowGraph::ConstVertexIterator &	beginVertex
	)

Find all function return vertices.

Returns the list of vertices with outgoing E_FUNCTION_RETURN edges.

Sawyer::Container::Map<FunctionPtr, CfgConstEdgeSet> Rose::BinaryAnalysis::Partitioner2::findFunctionReturnEdges ( const PartitionerConstPtr & )

Find function return edges organized by function.

Finds all control flow graph edges that are function return edges and organizes them according to the function from which they emanate. Note that since a basic block can be shared among several functions (usually just one though), an edge may appear multiple times in the returned map.

If a control flow graph is supplied, it must be compatible with the specified partitioner. If no control flow graph is specified then the partitioner's own CFG is used.

Sawyer::Container::Map<FunctionPtr, CfgConstEdgeSet> Rose::BinaryAnalysis::Partitioner2::findFunctionReturnEdges	(	const PartitionerConstPtr &	,
		const ControlFlowGraph &
	)

Find function return edges organized by function.

Finds all control flow graph edges that are function return edges and organizes them according to the function from which they emanate. Note that since a basic block can be shared among several functions (usually just one though), an edge may appear multiple times in the returned map.

If a control flow graph is supplied, it must be compatible with the specified partitioner. If no control flow graph is specified then the partitioner's own CFG is used.

void Rose::BinaryAnalysis::Partitioner2::eraseEdges	(	ControlFlowGraph &	,
		const CfgConstEdgeSet &	toErase
	)

Erase multiple edges.

Erases each edge in the toErase set. Upon return, the toErase set's values will all be invalid and should not be dereferenced.

CfgConstVertexSet Rose::BinaryAnalysis::Partitioner2::findIncidentVertices ( const CfgConstEdgeSet & )

Vertices that are incident to specified edges.

CfgConstVertexSet Rose::BinaryAnalysis::Partitioner2::findDetachedVertices ( const ControlFlowGraph & )

Find vertices that have zero degree.

Returns a set of vertices that have no incoming or outgoing edges. If vertices are specified, then limit the return value to the specified vertices; this mode of operation can be significantly faster than scanning the entire graph.

CfgConstVertexSet Rose::BinaryAnalysis::Partitioner2::findDetachedVertices ( const CfgConstVertexSet & vertices )

Find vertices that have zero degree.

Returns a set of vertices that have no incoming or outgoing edges. If vertices are specified, then limit the return value to the specified vertices; this mode of operation can be significantly faster than scanning the entire graph.

CfgConstVertexSet Rose::BinaryAnalysis::Partitioner2::forwardMapped	(	const CfgConstVertexSet &	,
		const CfgVertexMap &
	)

Return corresponding iterators.

Given a set of iterators and a vertex map, return the corresponding iterators by following the forward mapping. Any vertex in the argument that is not present in the mapping is silently ignored.

CfgConstVertexSet Rose::BinaryAnalysis::Partitioner2::reverseMapped	(	const CfgConstVertexSet &	,
		const CfgVertexMap &
	)

Return corresponding iterators.

Given a set of iterators and a vertex map, return the corresponding iterators by following the reverse mapping. Any vertex in the argument that is not present in the mapping is silently ignored.

void Rose::BinaryAnalysis::Partitioner2::expandFunctionReturnEdges	(	const PartitionerConstPtr &	,
		ControlFlowGraph &	cfg
	)

Rewrite function return edges.

Given a graph that has function return edges (E_FUNCTION_RETURN) that point to the indeterminate vertex, replace them with function return edges that point to the return sites. The return sites are the vertices pointed to by the call-return (E_CALL_RETURN) edges emanating from the call sites for said function. The graph is modified in place. The resulting graph will usually have more edges than the original graph.

ControlFlowGraph Rose::BinaryAnalysis::Partitioner2::functionCfgByErasure	(	const ControlFlowGraph &	gcfg,
		const FunctionPtr &	function,
		ControlFlowGraph::VertexIterator &	entry
	)

Generate a function control flow graph.

A function control flow graph is created by erasing all parts of the global control flow graph (gcfg) that aren't owned by the specified function. The resulting graph will contain an indeterminate vertex if the global CFG contains an indeterminate vertex and the function has any edges to the indeterminate vertex that are not E_FUNCTION_RETURN edges. In other words, the indeterminate vertex is excluded unless there are things like branches or calls whose target address is a register.

Upon return, the entry iterator points to the vertex of the return value that serves as the function's entry point.

Note that this method of creating a function control flow graph can be slow since it starts with a global control flow graph. It has one benefit over functionCfgByReachability though: it will find all vertices that belong to the function even if they're not reachable from the function's entry point, or even if they're only reachable by traversing through a non-owned vertex.

ControlFlowGraph Rose::BinaryAnalysis::Partitioner2::functionCfgByReachability	(	const ControlFlowGraph &	gcfg,
		const FunctionPtr &	function,
		const ControlFlowGraph::ConstVertexIterator &	gcfgEntry
	)

Generate a function control flow graph.

A function control flow graph is created by traversing the specified global control flow grap (gcfg) starting at the specified vertex (gcfgEntry). The traversal follows only vertices that are owned by the specified function, and the indeterminate vertex. The indeterminate vertex is only reachable through edges of types other than E_FUNCTION_RETURN.

The function control flow graph entry point corresponding to gcfgEntry is always vertex number zero in the return value. However, if gcfgEntry points to a vertex not owned by function, or gcfg is empty then the returned graph is also empty.

Note that this method of creating a function control graph can be much faster than functionCfgByErasure since it only traverses part of the global CFG, but the drawback is that the return value won't include vertices that are not reachable from the return value's entry vertex.

ThunkDetection Rose::BinaryAnalysis::Partitioner2::isX86JmpImmThunk	(	const PartitionerConstPtr &	,
		const std::vector< SgAsmInstruction * > &
	)

Test whether x86 instructions begin with "jmp ADDRESS".

Tries to match "jmp ADDRESS" where ADDRESS is a constant.

ThunkDetection Rose::BinaryAnalysis::Partitioner2::isX86JmpMemThunk	(	const PartitionerConstPtr &	,
		const std::vector< SgAsmInstruction * > &
	)

Test whether x86 instruction begin with "jmp [ADDRESS]".

Tries to match "jmp [ADDRESS]" where ADDRESS is a constant.

ThunkDetection Rose::BinaryAnalysis::Partitioner2::isX86LeaJmpThunk	(	const PartitionerConstPtr &	,
		const std::vector< SgAsmInstruction * > &
	)

Test whether x86 instructions begin with an LEA JMP pair.

Tries to match "lea ecx, [ebp + C]; jmp ADDR" where C and ADDR are constants.

ThunkDetection Rose::BinaryAnalysis::Partitioner2::isX86MovJmpThunk	(	const PartitionerConstPtr &	,
		const std::vector< SgAsmInstruction * > &
	)

Test whether x86 instructions begin with "mov R, [ADDR]; jmp R".

Tries to match "mov R, [ADDR]; jmp R" where R is a register and ADDR is a constant.

ThunkDetection Rose::BinaryAnalysis::Partitioner2::isX86AddJmpThunk	(	const PartitionerConstPtr &	,
		const std::vector< SgAsmInstruction * > &
	)

Test whether x86 instructions begin with "add R, C; jmp ADDR".

Tries to match "add R, C; jmp ADDR" where R is one of the cx registers and C and ADDR are constants.

void Rose::BinaryAnalysis::Partitioner2::splitThunkFunctions	(	const PartitionerPtr &	,
		const ThunkPredicates::Ptr &
	)

Split thunks off from start of functions.

Splits as many thunks as possible off the front of all functions currently attached to the partitioner's CFG.

size_t Rose::BinaryAnalysis::Partitioner2::serialNumber ( )

Return the next serial number.

Description

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Typedef Documentation

Enumeration Type Documentation

Function Documentation