Description

Binary function detection.

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

Partitioner: The partitioner has two slightly conflated roles. Its primary role is to serve as a database that supports efficient queries for information that are needed during typical binary analysis. As such, it is able to describe functions, basic blocks, static data blocks, memory maps, control flow graphs, address usage maps, and more and has a fairly robust API. Its second role, less important from the view of the end user, is to accumulate the above information in a process known as partitioning.

Engine: The engine contains the higher-level functionality that drives the process by which information is added to the partitioner, i.e., partitioning. The engine is customized by class derivation, and the base class (Partitioner2::Engine) is abstract.

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

namespace	DataFlow
	Data-flow utilities.

namespace	GraphViz
	Support for generating and reading GraphViz output.

namespace	IndirectControlFlow
	Utilities for doing indirect control flow as part of partitioning.

namespace	Modules
	Miscellaneous supporting functions for disassembly.

namespace	ModulesElf
	Disassembly and partitioning utility functions for ELF.

namespace	ModulesJvm
	Disassembly and partitioning utility functions for JVM.

namespace	ModulesLinux
	Disassembly and partitioning utilities for Linux.

namespace	ModulesM68k
	Disassembly and partitioning utility functions for M68k.

namespace	ModulesMips
	Disassembly and partitioning utility functions for MIPS.

namespace	ModulesPe
	Disassembly and partitioning utilities for PE files.

namespace	ModulesPowerpc
	Disassembly and partitioning utilities for PowerPC.

namespace	ModulesX86
	Disassembly and partitioning utilities for Intel x86 and amd64.

namespace	Precision
	Level of precision for analysis.

namespace	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	EngineBinary
	Engine for specimens containing machine instructions. More...

class	EngineJvm
	Engine for Java Virtual Machine (JVM) specimens. More...

struct	EngineSettings
	Settings for controlling 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...

class	JumpTable
	Utilities for working with jump tables. More...

struct	JvmSettings
	Settings for controlling JVM partitioning behavior. More...

struct	LoaderSettings
	Settings for loading specimens. More...

class	MemoryTable
	Utilities for working with tables. 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.

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

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

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

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

using	EnginePtr = Sawyer::SharedPointer< Engine >
	Shared-ownership pointer for Engine.

using	EngineBinaryPtr = Sawyer::SharedPointer< EngineBinary >
	Shared-ownership pointer for EngineBinary.

using	EngineJvmPtr = Sawyer::SharedPointer< EngineJvm >
	Shared-ownership pointer for EngineJvm.

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

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

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

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

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

using	JumpTablePtr = std::shared_ptr< JumpTable >
	Shared-ownership pointer for JumpTable.

using	JumpTableConstPtr = std::shared_ptr< const JumpTable >
	Shared-ownership pointer for JumpTable.

using	MemoryTablePtr = std::shared_ptr< MemoryTable >
	Shared-ownership pointer for MemoryTable.

using	MemoryTableConstPtr = std::shared_ptr< const MemoryTable >
	Shared-ownership pointer for MemoryTable.

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

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

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

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

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

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

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

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


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.

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.

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

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.

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

boost::logic::tribool	hasAnyCalleeReturn (const PartitionerConstPtr &, const ControlFlowGraph::ConstVertexIterator &)
	May-return status for function callees.

bool	hasCallReturnEdges (const ControlFlowGraph::ConstVertexIterator &)
	Test whether vertex has at least one call-return edge.


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.

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.


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.

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.


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.

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.


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.

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.


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

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


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

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


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

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

Variables
Sawyer::Message::Facility	mlog

Typedef Documentation

◆ BasicBlockPtr

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

Shared-ownersip pointer for BasicBlock.

Definition at line 735 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ BasicBlockCallbackPtr

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

Shared ownership pointer.

Definition at line 740 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ BasicBlockSuccessors

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

All successors in no particular order.

Definition at line 743 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ ControlFlowGraph

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

Control flow graph.

Definition at line 751 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ DataBlockPtr

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

Shared-ownership pointer for DataBlock.

Definition at line 756 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ EnginePtr

using Rose::BinaryAnalysis::Partitioner2::EnginePtr = typedef Sawyer::SharedPointer<Engine>

Shared-ownership pointer for Engine.

Definition at line 761 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ EngineBinaryPtr

using Rose::BinaryAnalysis::Partitioner2::EngineBinaryPtr = typedef Sawyer::SharedPointer<EngineBinary>

Shared-ownership pointer for EngineBinary.

Definition at line 764 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ EngineJvmPtr

using Rose::BinaryAnalysis::Partitioner2::EngineJvmPtr = typedef Sawyer::SharedPointer<EngineJvm>

Shared-ownership pointer for EngineJvm.

Definition at line 767 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ FunctionPtr

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

Shared-ownership pointer for Function.

Shared-ownership pointer for function.

Definition at line 772 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ Functions

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

Mapping from address to function.

Definition at line 774 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ FunctionPaddingMatcherPtr

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

Shared ownership pointer.

Definition at line 779 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ FunctionPrologueMatcherPtr

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

Shared ownership pointer.

Definition at line 782 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ FunctionSet

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

Set of functions.

Definition at line 784 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ JumpTablePtr

using Rose::BinaryAnalysis::Partitioner2::JumpTablePtr = typedef std::shared_ptr<JumpTable>

Shared-ownership pointer for JumpTable.

Definition at line 789 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ JumpTableConstPtr

using Rose::BinaryAnalysis::Partitioner2::JumpTableConstPtr = typedef std::shared_ptr<const JumpTable>

Shared-ownership pointer for JumpTable.

Definition at line 790 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ MemoryTablePtr

using Rose::BinaryAnalysis::Partitioner2::MemoryTablePtr = typedef std::shared_ptr<MemoryTable>

Shared-ownership pointer for MemoryTable.

Definition at line 793 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ MemoryTableConstPtr

using Rose::BinaryAnalysis::Partitioner2::MemoryTableConstPtr = typedef std::shared_ptr<const MemoryTable>

Shared-ownership pointer for MemoryTable.

Definition at line 794 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ PartitionerPtr

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

Shared-ownership pointer for Partitioner.

Definition at line 797 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ PartitionerConstPtr

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

Shared-ownership pointer for Partitioner.

Definition at line 798 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ ReferenceSet

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

Set of references.

Definition at line 803 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ CrossReferences

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

Cross references.

Definition at line 804 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ ThunkPredicatesPtr

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

Shared-ownership pointer for ThunkPredicates.

Definition at line 807 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ CfgVertexIndex

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

Mapping from basic block starting address to CFG vertex.

Definition at line 198 of file ControlFlowGraph.h.

◆ CfgVertexList

typedef std::list<ControlFlowGraph::VertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgVertexList

List of CFG vertex pointers.

Definition at line 203 of file ControlFlowGraph.h.

◆ CfgConstVertexList

typedef std::list<ControlFlowGraph::ConstVertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgConstVertexList

List of CFG vertex pointers.

Definition at line 204 of file ControlFlowGraph.h.

◆ CfgEdgeList

typedef std::list<ControlFlowGraph::EdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgEdgeList

List of CFG edge pointers.

Definition at line 210 of file ControlFlowGraph.h.

◆ CfgConstEdgeList

typedef std::list<ControlFlowGraph::ConstEdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgConstEdgeList

List of CFG edge pointers.

Definition at line 211 of file ControlFlowGraph.h.

◆ CfgVertexSet

typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::VertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgVertexSet

Set of CFG vertex pointers.

Definition at line 217 of file ControlFlowGraph.h.

◆ CfgConstVertexSet

typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::ConstVertexIterator> Rose::BinaryAnalysis::Partitioner2::CfgConstVertexSet

Set of CFG vertex pointers.

Definition at line 218 of file ControlFlowGraph.h.

◆ CfgEdgeSet

typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::EdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgEdgeSet

Set of CFG edge pointers.

Definition at line 224 of file ControlFlowGraph.h.

◆ CfgConstEdgeSet

typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::ConstEdgeIterator> Rose::BinaryAnalysis::Partitioner2::CfgConstEdgeSet

Set of CFG edge pointers.

Definition at line 225 of file ControlFlowGraph.h.

◆ CfgVertexMap

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 230 of file ControlFlowGraph.h.

◆ ThunkPredicate

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 81 of file Thunk.h.

Enumeration Type Documentation

◆ VertexType

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 51 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ EdgeType

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 62 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ Confidence

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 86 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ SemanticMemoryParadigm

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 92 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ MemoryDataAdjustment

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 179 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

◆ FunctionReturnAnalysis

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 312 of file Rose/BinaryAnalysis/Partitioner2/BasicTypes.h.

Function Documentation

◆ findPathEdges() [1/2]

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.

◆ findPathEdges() [2/2]

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.

◆ findPathReachableEdges()

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.

◆ findPathUnreachableEdges()

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.

◆ eraseUnreachablePaths()

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.

◆ findPaths() [1/2]

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.

◆ findPaths() [2/2]

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.

◆ findFunctionPaths() [1/2]

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.

◆ findFunctionPaths() [2/2]

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.

◆ findInterFunctionPaths() [1/2]

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.

◆ findInterFunctionPaths() [2/2]

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.

◆ inlineMultipleCallees()

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.

◆ inlineOneCallee()

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.

◆ insertCfg()

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.

◆ findBackEdges()

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.

◆ findCallEdges()

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

Find function call edges.

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

◆ findCalledFunctions()

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.

◆ findCallReturnEdges() [1/2]

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.

◆ findCallReturnEdges() [2/2]

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.

◆ findFunctionReturns()

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.

◆ findFunctionReturnEdges() [1/2]

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.

◆ findFunctionReturnEdges() [2/2]

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.

◆ eraseEdges()

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.

◆ findDetachedVertices() [1/2]

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.

◆ findDetachedVertices() [2/2]

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.

◆ forwardMapped()

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.

◆ reverseMapped()

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.

◆ expandFunctionReturnEdges()

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.

◆ functionCfgByErasure()

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.

◆ functionCfgByReachability()

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.

◆ isX86JmpImmThunk()

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.

◆ isX86JmpMemThunk()

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.

◆ isX86LeaJmpThunk()

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.

◆ isX86MovJmpThunk()

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.

◆ isX86AddJmpThunk()

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.

◆ splitThunkFunctions()

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.

◆ lowerBound() [1/2]

template<class Container , class Value , class Comparator >

Container::const_iterator Rose::BinaryAnalysis::Partitioner2::lowerBound	(	const Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 47 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ lowerBound() [2/2]

template<class Container , class Value , class Comparator >

Container::iterator Rose::BinaryAnalysis::Partitioner2::lowerBound	(	Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 52 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ equalUnique()

template<class Value , class Comparator >

bool Rose::BinaryAnalysis::Partitioner2::equalUnique	(	const Value &	a,
		const Value &	b,
		Comparator	cmp
	)

Definition at line 59 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ insertUnique()

template<class Container , class Value , class Comparator >

bool Rose::BinaryAnalysis::Partitioner2::insertUnique	(	Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 66 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ replaceOrInsert()

template<class Container , class Value , class Comparator >

void Rose::BinaryAnalysis::Partitioner2::replaceOrInsert	(	Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 80 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ eraseUnique()

template<class Container , class Value , class Comparator >

bool Rose::BinaryAnalysis::Partitioner2::eraseUnique	(	Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 94 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ existsUnique()

template<class Container , class Value , class Comparator >

bool Rose::BinaryAnalysis::Partitioner2::existsUnique	(	const Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 107 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ getUnique()

template<class Container , class Value , class Comparator >

Sawyer::Optional< Value > Rose::BinaryAnalysis::Partitioner2::getUnique	(	const Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 120 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ getOrInsertUnique()

template<class Container , class Value , class Comparator >

Sawyer::Optional< Value > Rose::BinaryAnalysis::Partitioner2::getOrInsertUnique	(	Container &	container,
		const Value &	item,
		Comparator	cmp
	)

Definition at line 133 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ isSupersetUnique()

template<class Container , class Comparator >

bool Rose::BinaryAnalysis::Partitioner2::isSupersetUnique	(	const Container &	sup,
		const Container &	sub,
		Comparator	lessThan
	)

Definition at line 147 of file BinaryAnalysis/Partitioner2/Utility.h.

◆ hasAnyCalleeReturn()

boost::logic::tribool Rose::BinaryAnalysis::Partitioner2::hasAnyCalleeReturn	(	const PartitionerConstPtr &	,
		const ControlFlowGraph::ConstVertexIterator &
	)

May-return status for function callees.

Returns true if any callee may-return is positive; false if all callees are negative; indeterminate if any are indeterminate.

◆ hasCallReturnEdges()

bool Rose::BinaryAnalysis::Partitioner2::hasCallReturnEdges ( const ControlFlowGraph::ConstVertexIterator & )

Test whether vertex has at least one call-return edge.

Returns true if the specified vertex has at least one E_CALL_RETURN edge.

Description

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Typedef Documentation

◆ BasicBlockPtr

◆ BasicBlockCallbackPtr

◆ BasicBlockSuccessors

◆ ControlFlowGraph

◆ DataBlockPtr

◆ EnginePtr

◆ EngineBinaryPtr

◆ EngineJvmPtr

◆ FunctionPtr

◆ Functions

◆ FunctionPaddingMatcherPtr

◆ FunctionPrologueMatcherPtr

◆ FunctionSet

◆ JumpTablePtr

◆ JumpTableConstPtr

◆ MemoryTablePtr

◆ MemoryTableConstPtr

◆ PartitionerPtr

◆ PartitionerConstPtr

◆ ReferenceSet

◆ CrossReferences

◆ ThunkPredicatesPtr

◆ CfgVertexIndex

◆ CfgVertexList

◆ CfgConstVertexList

◆ CfgEdgeList

◆ CfgConstEdgeList

◆ CfgVertexSet

◆ CfgConstVertexSet

◆ CfgEdgeSet

◆ CfgConstEdgeSet

◆ CfgVertexMap

◆ ThunkPredicate

Enumeration Type Documentation

◆ VertexType

◆ EdgeType

◆ Confidence

◆ SemanticMemoryParadigm

◆ MemoryDataAdjustment

◆ FunctionReturnAnalysis

Function Documentation

◆ findPathEdges() [1/2]

◆ findPathEdges() [2/2]

◆ findPathReachableEdges()

◆ findPathUnreachableEdges()

◆ eraseUnreachablePaths()

◆ findPaths() [1/2]

◆ findPaths() [2/2]

◆ findFunctionPaths() [1/2]

◆ findFunctionPaths() [2/2]

◆ findInterFunctionPaths() [1/2]

◆ findInterFunctionPaths() [2/2]

◆ inlineMultipleCallees()

◆ inlineOneCallee()

◆ insertCfg()

◆ findBackEdges()

◆ findCallEdges()

◆ findCalledFunctions()

◆ findCallReturnEdges() [1/2]

◆ findCallReturnEdges() [2/2]

◆ findFunctionReturns()

◆ findFunctionReturnEdges() [1/2]

◆ findFunctionReturnEdges() [2/2]

◆ eraseEdges()

◆ findDetachedVertices() [1/2]

◆ findDetachedVertices() [2/2]

◆ forwardMapped()

◆ reverseMapped()

◆ expandFunctionReturnEdges()

◆ functionCfgByErasure()

◆ functionCfgByReachability()

◆ isX86JmpImmThunk()