ROSE  0.11.145.0
Classes | Typedefs | Functions | Variables
Rose::BinaryAnalysis::Partitioner2::DataFlow Namespace Reference

Description

Data-flow utilities.

Classes

class  DfCfgVertex
 CFG vertex for data-flow analysis. More...
 
class  InterproceduralPredicate
 Predicate that decides when to use inter-procedural data-flow. More...
 
class  NotInterprocedural
 Predicate that always returns false, preventing interprocedural analysis. More...
 
class  TransferFunction
 Data-Flow transfer functor. More...
 

Typedefs

using DfCfg = Sawyer::Container::Graph< DfCfgVertex >
 Control flow graph used by data-flow analysis. More...
 
typedef Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction
 Data-flow merge function. More...
 
using Engine = Rose::BinaryAnalysis::DataFlow::Engine< DfCfg, InstructionSemantics::BaseSemantics::StatePtr, TransferFunction, MergeFunction >
 Data-Flow engine. More...
 

Functions

std::vector< SgAsmInstruction * > vertexUnpacker (const DfCfgVertex &)
 Unpacks a vertex into a list of instructions. More...
 
DfCfg buildDfCfg (const PartitionerConstPtr &, const ControlFlowGraph &, const ControlFlowGraph::ConstVertexIterator &startVertex, InterproceduralPredicate &predicate=NOT_INTERPROCEDURAL)
 build a cfg useful for data-flow analysis. More...
 
void dumpDfCfg (std::ostream &, const DfCfg &)
 Emit a data-flow CFG as a GraphViz file. More...
 
FunctionPtr bestSummaryFunction (const FunctionSet &functions)
 Choose best function for data-flow summary vertex. More...
 
template<class DfCfg >
Sawyer::Container::GraphTraits< DfCfg >::VertexIterator findReturnVertex (DfCfg &dfCfg)
 Find the return vertex. More...
 
Variables::StackVariables findStackVariables (const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
 Returns the list of all known stack variables. More...
 
Variables::StackVariables findLocalVariables (const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
 Returns the list of all known local variables. More...
 
Variables::StackVariables findFunctionArguments (const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
 Returns the list of all known function arguments. More...
 
std::vector< AbstractLocationfindGlobalVariables (const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes)
 Returns a list of global variables. More...
 

Variables

NotInterprocedural NOT_INTERPROCEDURAL
 

Typedef Documentation

Control flow graph used by data-flow analysis.

The CFG used for data-flow is slightly different than the global CFG maintained by the partitioner. The partitioner's global CFG is tuned for discovering basic blocks and deciding which basic blocks are owned by which functions, whereas a data-flow's CFG is tuned for performing data flow analysis. A data-flow CFG is usually constructed from the partitioner's global CFG, but differs in the following ways:

  • First, data-flow analysis is usually performed on a subset of the partitioner's global CFG. This function uses the startVertex to select some connected subgraph, such as a subgraph corresponding to a single function definition when given the entry block.
  • Function return blocks (e.g., RET instructions) are handled differently during data-flow. In the partitioner's global CFG each return block is marked as a function return and has single successor–the indeterminate vertex. In a data-flow CFG the return blocks are not handled specially, but rather all flow into a single special return vertex that has no instructions. This allows data to be merged from all the return points.
  • Function call sites are modified. In the partitioner global CFG a function call (e.g., CALL instruction) has an edge (or edges) going to the entry block of the called function(s) and a special call-return edge to the return site if there is one (usually the fall-through address). A data-flow analysis often needs to perform some special action for the call-return, thus a call-return edge in the global CFG gets transformed to an edge-vertex-edge sequence in the data-flow CFG where the middle vertex is a special CALLRET vertex with no instructions.

Definition at line 123 of file Partitioner2/DataFlow.h.

Data-flow merge function.

Computes the meet of two states, merging the source state into the destination state and returning true iff the destination state changed.

Definition at line 254 of file Partitioner2/DataFlow.h.

Data-Flow engine.

Definition at line 260 of file Partitioner2/DataFlow.h.

Function Documentation

std::vector<SgAsmInstruction*> Rose::BinaryAnalysis::Partitioner2::DataFlow::vertexUnpacker ( const DfCfgVertex )

Unpacks a vertex into a list of instructions.

DfCfg Rose::BinaryAnalysis::Partitioner2::DataFlow::buildDfCfg ( const PartitionerConstPtr ,
const ControlFlowGraph ,
const ControlFlowGraph::ConstVertexIterator &  startVertex,
InterproceduralPredicate predicate = NOT_INTERPROCEDURAL 
)

build a cfg useful for data-flow analysis.

The returned CFG will be constructed from the global CFG vertices that are reachable from startVertex such that the reached vertex belongs to the same function as startVertex.

See also
DfCfg
void Rose::BinaryAnalysis::Partitioner2::DataFlow::dumpDfCfg ( std::ostream &  ,
const DfCfg  
)

Emit a data-flow CFG as a GraphViz file.

FunctionPtr Rose::BinaryAnalysis::Partitioner2::DataFlow::bestSummaryFunction ( const FunctionSet functions)

Choose best function for data-flow summary vertex.

When replacing a function call edge with a function summary, we insert a data-flow vertex that points to a function. During the data-flow processing, the function's information summarizes the data-flow state changes that are necessary. If multiple functions own the target block of a function call edge then we need to choose the "best" function to use.

template<class DfCfg >
Sawyer::Container::GraphTraits<DfCfg>::VertexIterator Rose::BinaryAnalysis::Partitioner2::DataFlow::findReturnVertex ( DfCfg dfCfg)

Find the return vertex.

Finds the FUNCRET vertex. Function returns all flow into this special vertex, but if there are no function return blocks then this vertex also doesn't exist (in which case the end iterator is returned). Do not call this if there's a chance that the data-flow CFG has more than one FUNCRET vertex.

Definition at line 174 of file Partitioner2/DataFlow.h.

References Rose::BinaryAnalysis::Partitioner2::DataFlow::DfCfgVertex::FUNCRET, and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().

Variables::StackVariables Rose::BinaryAnalysis::Partitioner2::DataFlow::findStackVariables ( const FunctionPtr function,
const InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops,
const InstructionSemantics::BaseSemantics::SValuePtr initialStackPointer 
)

Returns the list of all known stack variables.

A stack variable is any memory location whose address is a constant offset from an initial stack pointer. That is, the address has the form (add SP0 CONSTANT) where SP0 is a variable supplied as an argument to this function. When CONSTANT is zero the expression is simplified to SP0, so that also is accepted. Although memory is byte addressable and values are stored as individual bytes in memory, this function attempts to sew related addresses back together again to produce variables that are multiple bytes. There are many ways to do this, all of which are heuristic.

The ops provides the operators for comparing stack pointers, and also provides the state which is examined to find the stack variables. The underlying memory state should be of type MemoryCellList or a subclass, or else no stack variables will be found.

Variables::StackVariables Rose::BinaryAnalysis::Partitioner2::DataFlow::findLocalVariables ( const FunctionPtr function,
const InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops,
const InstructionSemantics::BaseSemantics::SValuePtr initialStackPointer 
)

Returns the list of all known local variables.

A local variable is any stack variable whose starting address is less than the specified stack pointer. For the definition of stack variable, see findStackVariables.

Variables::StackVariables Rose::BinaryAnalysis::Partitioner2::DataFlow::findFunctionArguments ( const FunctionPtr function,
const InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops,
const InstructionSemantics::BaseSemantics::SValuePtr initialStackPointer 
)

Returns the list of all known function arguments.

A function argument is any stack variable whose starting address is greater than or equal to the specified stack pointer. For the definition of stack variable, see findStackVariables. On architectures that pass a return address on the top of the stack, that return address is considered to be the first argument of the function.

std::vector<AbstractLocation> Rose::BinaryAnalysis::Partitioner2::DataFlow::findGlobalVariables ( const InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops,
size_t  wordNBytes 
)

Returns a list of global variables.

The returned abstract locations all point to memory. The wordNBytes is the maximum size for any returned variable; larger units of memory written to by the same instruction will be broken into smaller variables.