ROSE  0.9.9.109
Namespaces | Classes | Typedefs | Enumerations | Functions | Variables
Rose::BinaryAnalysis::Partitioner2 Namespace Reference

Description

Binary function detection.

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

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

 DataFlow
 Data-flow utilities.
 
 GraphViz
 Support for generating and reading GraphViz output.
 

Classes

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  BasicBlockConfig
 Configuration information for a basic block. More...
 
class  BasicBlockError
 
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  DataBlockConfig
 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...
 
struct  EngineSettings
 Settings for controling the engine behavior. More...
 
class  Exception
 
class  Function
 Describes one function. More...
 
class  FunctionCallGraph
 Function call information. More...
 
class  FunctionConfig
 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  OwnedDataBlock
 Shared reference to data block. 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...
 
class  Trigger
 Trigger based on number of times called. More...
 

Typedefs

typedef Sawyer::SharedPointer< FunctionFunctionPtr
 Shared-ownership pointer for function. More...
 
typedef Sawyer::SharedPointer< BasicBlockBasicBlockPtr
 
typedef Sawyer::SharedPointer< DataBlockDataBlockPtr
 
typedef Sawyer::Container::Graph< CfgVertex, CfgEdgeControlFlowGraph
 Control flow graph. More...
 
typedef Sawyer::Container::Map< rose_addr_t, ControlFlowGraph::VertexIterator > CfgVertexIndex
 Mapping from basic block starting address to CFG vertex. More...
 
typedef Sawyer::Container::BiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIteratorCfgVertexMap
 Map vertices from one CFG to another CFG and vice versa. More...
 
typedef Sawyer::Container::Map< rose_addr_t, Function::PtrFunctions
 
typedef Sawyer::Container::Set< Function::PtrFunctionSet
 
typedef std::set< ReferenceReferenceSet
 Set of references. More...
 
typedef Sawyer::Container::Map< Reference, ReferenceSetCrossReferences
 Cross references. More...
 
typedef std::list< ControlFlowGraph::VertexIterator > CfgVertexList
 List of CFG vertex pointers.
 
typedef std::list< ControlFlowGraph::ConstVertexIteratorCfgConstVertexList
 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 std::set< ControlFlowGraph::VertexIterator > CfgVertexSet
 Set of CFG vertex pointers.
 
typedef std::set< ControlFlowGraph::ConstVertexIteratorCfgConstVertexSet
 Set of CFG vertex pointers.
 
typedef std::set< ControlFlowGraph::EdgeIterator > CfgEdgeSet
 Set of CFG edge pointers.
 
typedef std::set< 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,
  E_FUNCTION_CALL,
  E_FUNCTION_RETURN,
  E_CALL_RETURN,
  E_FUNCTION_XFER,
  E_USER_DEFINED
}
 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

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...
 
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 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 &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
 Compute all paths across function calls and returns. More...
 
std::ostream & operator<< (std::ostream &out, const CfgPath &path)
 
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...
 
CfgConstEdgeSet findCallReturnEdges (const ControlFlowGraph::ConstVertexIterator &callSite)
 Return outgoing call-return edges. More...
 
CfgConstVertexSet findFunctionReturns (const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex)
 Find 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 initDiagnostics ()
 
bool sortBasicBlocksByAddress (const BasicBlock::Ptr &, const BasicBlock::Ptr &)
 
bool sortDataBlocks (const DataBlock::Ptr &, const DataBlock::Ptr &)
 
bool sortFunctionsByAddress (const Function::Ptr &, const Function::Ptr &)
 
bool sortFunctionNodesByAddress (const SgAsmFunction *, const SgAsmFunction *)
 
bool sortByExpression (const BasicBlock::Successor &, const BasicBlock::Successor &)
 
bool sortVerticesByAddress (const ControlFlowGraph::ConstVertexIterator &, const ControlFlowGraph::ConstVertexIterator &)
 
bool sortEdgesBySrc (const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
 
bool sortEdgesByDst (const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
 
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 >
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 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 &)
 
std::ostream & operator<< (std::ostream &, const ControlFlowGraph::Vertex &)
 
std::ostream & operator<< (std::ostream &, const ControlFlowGraph::Edge &)
 
AddressIntervalParser::Ptr addressIntervalParser (AddressInterval &storage)
 
AddressIntervalParser::Ptr addressIntervalParser (std::vector< AddressInterval > &storage)
 
AddressIntervalParser::Ptr addressIntervalParser ()
 
size_t serialNumber ()
 Return the next serial number. More...
 
bool insertCalleePaths (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=NULL)
 Inline a function at the specified call site. More...
 
bool insertCalleePaths (ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite, const ControlFlowGraph &cfg, const ControlFlowGraph::ConstEdgeIterator &cfgCallEdge, const CfgConstVertexSet &cfgAvoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &cfgAvoidEdges=CfgConstEdgeSet(), std::vector< ControlFlowGraph::ConstVertexIterator > *newEdges=NULL)
 Inline a function at the specified call site. 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

Shared-ownership pointer for function.

See Shared ownership.

Definition at line 372 of file BasicTypes.h.

Control flow graph.

Definition at line 189 of file ControlFlowGraph.h.

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

Mapping from basic block starting address to CFG vertex.

Definition at line 192 of file ControlFlowGraph.h.

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

Definition at line 223 of file ControlFlowGraph.h.

Set of references.

Definition at line 151 of file Reference.h.

Cross references.

Definition at line 154 of file Reference.h.

Enumeration Type Documentation

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 19 of file BasicTypes.h.

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. The 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 30 of file BasicTypes.h.

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 54 of file BasicTypes.h.

Organization of semantic memory.

Enumerator
LIST_BASED_MEMORY 

Precise but slow.

MAP_BASED_MEMORY 

Fast but not precise.

Definition at line 60 of file BasicTypes.h.

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 155 of file BasicTypes.h.

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 225 of file BasicTypes.h.

Function Documentation

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 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 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 the beginVertex.

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 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 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::insertCalleePaths ( 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 = NULL 
)

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 versions of this function: one takes a specific function call edge and inlines only that single call. The other takes a call site vertex and inlines all functions called at that vertex.

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::insertCalleePaths ( ControlFlowGraph paths,
const ControlFlowGraph::ConstVertexIterator pathsCallSite,
const ControlFlowGraph cfg,
const ControlFlowGraph::ConstEdgeIterator &  cfgCallEdge,
const CfgConstVertexSet cfgAvoidVertices = CfgConstVertexSet(),
const CfgConstEdgeSet cfgAvoidEdges = CfgConstEdgeSet(),
std::vector< ControlFlowGraph::ConstVertexIterator > *  newEdges = NULL 
)

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 versions of this function: one takes a specific function call edge and inlines only that single call. The other takes a call site vertex and inlines all functions called at that vertex.

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.

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 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.

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

Find function return vertices.

Returns the list of vertices with outgoing E_FUNCTION_RETURN edges.

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

Erase multiple edges.

Erases each edge in the toErase set.

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.

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

Return the next serial number.