ROSE  0.9.10.6
Classes | Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | List of all members
Rose::BinaryAnalysis::FeasiblePath Class Reference

Description

Feasible path analysis.

Determines whether CFG paths are feasible paths.

Definition at line 16 of file BinaryFeasiblePath.h.

#include <BinaryFeasiblePath.h>

Collaboration diagram for Rose::BinaryAnalysis::FeasiblePath:
Collaboration graph
[legend]

Classes

struct  FunctionSummary
 Information stored per V_USER_DEFINED path vertex. More...
 
class  PathProcessor
 Path searching functor. More...
 
struct  Settings
 Settings that control this analysis. More...
 
struct  VarDetail
 Information about a variable seen on a path. More...
 

Public Types

enum  SearchMode {
  SEARCH_SINGLE_DFS,
  SEARCH_SINGLE_BFS,
  SEARCH_MULTI
}
 
enum  SemanticMemoryParadigm {
  LIST_BASED_MEMORY,
  MAP_BASED_MEMORY
}
 Organization of semantic memory. More...
 
enum  IoMode {
  READ,
  WRITE
}
 Read or write operation. More...
 
enum  MayOrMust {
  MAY,
  MUST
}
 Types of comparisons. More...
 
typedef Sawyer::Container::Map< rose_addr_t, FunctionSummaryFunctionSummaries
 Summaries for multiple functions. More...
 

Public Member Functions

 FeasiblePath ()
 Constructs a new feasible path analyzer. More...
 
void reset ()
 Reset to initial state without changing settings. More...
 
virtual InstructionSemantics2::BaseSemantics::DispatcherPtr buildVirtualCpu (const Partitioner2::Partitioner &, PathProcessor *)
 Create the virtual CPU. More...
 
virtual void setInitialState (const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsBeginVertex)
 Initialize state for first vertex of path. More...
 
virtual void processBasicBlock (const Partitioner2::BasicBlock::Ptr &bblock, const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex)
 Process instructions for one basic block on the specified virtual CPU. More...
 
virtual void processIndeterminateBlock (const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex, const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex)
 Process an indeterminate block. More...
 
virtual void processFunctionSummary (const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex, const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex)
 Process a function summary vertex. More...
 
virtual void processVertex (const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t &pathInsnIndex)
 Process one vertex. More...
 
virtual bool shouldSummarizeCall (const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex, const Partitioner2::ControlFlowGraph &cfg, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget)
 Determines whether a function call should be summarized instead of inlined. More...
 
virtual bool shouldInline (const Partitioner2::CfgPath &path, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget)
 Determines whether a function call should be inlined. More...
 
Partitioner2::ControlFlowGraph::ConstVertexIterator pathToCfg (const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex) const
 Convert path vertex to a CFG vertex. More...
 
Partitioner2::CfgConstVertexSet cfgToPaths (const Partitioner2::CfgConstVertexSet &) const
 Convert CFG vertices to path vertices. More...
 
bool pathEndsWithFunctionCall (const Partitioner2::CfgPath &) const
 True if path ends with a function call. More...
 
bool isFunctionCall (const Partitioner2::ControlFlowGraph::ConstVertexIterator &) const
 True if vertex is a function call. More...
 
void printPathVertex (std::ostream &out, const Partitioner2::ControlFlowGraph::Vertex &pathVertex, size_t &insnIdx) const
 Print one vertex of a path for debugging. More...
 
void printPath (std::ostream &out, const Partitioner2::CfgPath &) const
 Print the path to the specified output stream. More...
 
virtual boost::tribool isPathFeasible (const Partitioner2::CfgPath &path, const SmtSolverPtr &, const std::vector< SymbolicExpr::Ptr > &postConditions, PathProcessor *pathProcessor, std::vector< SymbolicExpr::Ptr > &pathConditions, InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu)
 Determine whether a single path is feasible. More...
 
void depthFirstSearch (PathProcessor &pathProcessor)
 Find all feasible paths. More...
 
const Partitioner2::Partitionerpartitioner () const
 Property: Partitioner currently in use. More...
 
const FunctionSummariesfunctionSummaries () const
 Function summary information. More...
 
const FunctionSummaryfunctionSummary (rose_addr_t entryVa) const
 Function summary information. More...
 
const VarDetailvarDetail (const InstructionSemantics2::BaseSemantics::StatePtr &state, const std::string &varName) const
 Details about a variable. More...
 
const Settingssettings () const
 Property: Settings used by this analysis.
 
Settingssettings ()
 Property: Settings used by this analysis.
 
void settings (const Settings &s)
 Property: Settings used by this analysis.
 
void setSearchBoundary (const Partitioner2::Partitioner &partitioner, const Partitioner2::CfgConstVertexSet &cfgBeginVertices, const Partitioner2::CfgConstVertexSet &cfgEndVertices, const Partitioner2::CfgConstVertexSet &cfgAvoidVertices=Partitioner2::CfgConstVertexSet(), const Partitioner2::CfgConstEdgeSet &cfgAvoidEdges=Partitioner2::CfgConstEdgeSet())
 Specify search boundary. More...
 
void setSearchBoundary (const Partitioner2::Partitioner &partitioner, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgBeginVertex, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgEndVertex, const Partitioner2::CfgConstVertexSet &cfgAvoidVertices=Partitioner2::CfgConstVertexSet(), const Partitioner2::CfgConstEdgeSet &cfgAvoidEdges=Partitioner2::CfgConstEdgeSet())
 Specify search boundary. More...
 

Static Public Member Functions

static void initDiagnostics ()
 Initialize diagnostic output. More...
 

Public Attributes

RegisterDescriptor REG_PATH
 Descriptor of path pseudo-registers. More...
 

Static Public Attributes

static Sawyer::Message::Facility mlog
 Diagnostic output. More...
 

Member Typedef Documentation

Summaries for multiple functions.

Definition at line 142 of file BinaryFeasiblePath.h.

Member Enumeration Documentation

Organization of semantic memory.

Enumerator
LIST_BASED_MEMORY 

Precise but slow.

MAP_BASED_MEMORY 

Fast but not precise.

Definition at line 24 of file BinaryFeasiblePath.h.

Read or write operation.

Definition at line 30 of file BinaryFeasiblePath.h.

Types of comparisons.

Definition at line 33 of file BinaryFeasiblePath.h.

Constructor & Destructor Documentation

Rose::BinaryAnalysis::FeasiblePath::FeasiblePath ( )
inline

Constructs a new feasible path analyzer.

Definition at line 167 of file BinaryFeasiblePath.h.

Member Function Documentation

void Rose::BinaryAnalysis::FeasiblePath::reset ( )
inline
static void Rose::BinaryAnalysis::FeasiblePath::initDiagnostics ( )
static

Initialize diagnostic output.

This is called automatically when ROSE is initialized.

virtual InstructionSemantics2::BaseSemantics::DispatcherPtr Rose::BinaryAnalysis::FeasiblePath::buildVirtualCpu ( const Partitioner2::Partitioner ,
PathProcessor  
)
virtual

Create the virtual CPU.

Creates a new virtual CPU for each call. The first call also makes a copy of the register dictionary from the specified partitioner and augments it with a "path" pseudo-register that holds a symbolic expressions on which the current CFG path depends.

virtual void Rose::BinaryAnalysis::FeasiblePath::setInitialState ( const InstructionSemantics2::BaseSemantics::DispatcherPtr cpu,
const Partitioner2::ControlFlowGraph::ConstVertexIterator &  pathsBeginVertex 
)
virtual

Initialize state for first vertex of path.

Given the beginning of the path and the virtual CPU, initialize that state with whatever is suitable for the analysis. The default implementation sets the "path" pseudo-register to true (since the first vertex of the path is unconditionally feasible), sets the instruction pointer register to the first instruction, and initializes the stack pointer with the concrete stack pointer from settings (if any). On x86, the DF register is set.

virtual void Rose::BinaryAnalysis::FeasiblePath::processBasicBlock ( const Partitioner2::BasicBlock::Ptr bblock,
const InstructionSemantics2::BaseSemantics::DispatcherPtr cpu,
size_t  pathInsnIndex 
)
virtual

Process instructions for one basic block on the specified virtual CPU.

This is a state transfer function, updating the virtual machine state by processing the instructions of the specified basic block.

virtual void Rose::BinaryAnalysis::FeasiblePath::processIndeterminateBlock ( const Partitioner2::ControlFlowGraph::ConstVertexIterator &  vertex,
const InstructionSemantics2::BaseSemantics::DispatcherPtr cpu,
size_t  pathInsnIndex 
)
virtual

Process an indeterminate block.

This is a state transfer function, representing flow of control through an unknown address.

virtual void Rose::BinaryAnalysis::FeasiblePath::processFunctionSummary ( const Partitioner2::ControlFlowGraph::ConstVertexIterator &  pathsVertex,
const InstructionSemantics2::BaseSemantics::DispatcherPtr cpu,
size_t  pathInsnIndex 
)
virtual

Process a function summary vertex.

This is a state transfer function, representing flow of control across a summarized function.

virtual void Rose::BinaryAnalysis::FeasiblePath::processVertex ( const InstructionSemantics2::BaseSemantics::DispatcherPtr cpu,
const Partitioner2::ControlFlowGraph::ConstVertexIterator &  pathsVertex,
size_t &  pathInsnIndex 
)
virtual

Process one vertex.

This is the general state transfer function, representing flow of control through any type of vertex.

virtual bool Rose::BinaryAnalysis::FeasiblePath::shouldSummarizeCall ( const Partitioner2::ControlFlowGraph::ConstVertexIterator &  pathVertex,
const Partitioner2::ControlFlowGraph cfg,
const Partitioner2::ControlFlowGraph::ConstVertexIterator &  cfgCallTarget 
)
virtual

Determines whether a function call should be summarized instead of inlined.

virtual bool Rose::BinaryAnalysis::FeasiblePath::shouldInline ( const Partitioner2::CfgPath path,
const Partitioner2::ControlFlowGraph::ConstVertexIterator &  cfgCallTarget 
)
virtual

Determines whether a function call should be inlined.

Partitioner2::ControlFlowGraph::ConstVertexIterator Rose::BinaryAnalysis::FeasiblePath::pathToCfg ( const Partitioner2::ControlFlowGraph::ConstVertexIterator &  pathVertex) const

Convert path vertex to a CFG vertex.

Partitioner2::CfgConstVertexSet Rose::BinaryAnalysis::FeasiblePath::cfgToPaths ( const Partitioner2::CfgConstVertexSet ) const

Convert CFG vertices to path vertices.

bool Rose::BinaryAnalysis::FeasiblePath::pathEndsWithFunctionCall ( const Partitioner2::CfgPath ) const

True if path ends with a function call.

bool Rose::BinaryAnalysis::FeasiblePath::isFunctionCall ( const Partitioner2::ControlFlowGraph::ConstVertexIterator &  ) const

True if vertex is a function call.

void Rose::BinaryAnalysis::FeasiblePath::printPathVertex ( std::ostream &  out,
const Partitioner2::ControlFlowGraph::Vertex &  pathVertex,
size_t &  insnIdx 
) const

Print one vertex of a path for debugging.

void Rose::BinaryAnalysis::FeasiblePath::printPath ( std::ostream &  out,
const Partitioner2::CfgPath  
) const

Print the path to the specified output stream.

This is intended mainly for debugging.

virtual boost::tribool Rose::BinaryAnalysis::FeasiblePath::isPathFeasible ( const Partitioner2::CfgPath path,
const SmtSolverPtr ,
const std::vector< SymbolicExpr::Ptr > &  postConditions,
PathProcessor pathProcessor,
std::vector< SymbolicExpr::Ptr > &  pathConditions,
InstructionSemantics2::BaseSemantics::DispatcherPtr cpu 
)
virtual

Determine whether a single path is feasible.

Returns true if the path is feasible, false if not feasible, or indeterminate if a conclusion cannot be reached. The postConditions are additional optional conditions that must be satisified at the end of the path. The entire set of conditions is returned via pathConditions argument, which can also initially contain preconditions.

void Rose::BinaryAnalysis::FeasiblePath::setSearchBoundary ( const Partitioner2::Partitioner partitioner,
const Partitioner2::CfgConstVertexSet cfgBeginVertices,
const Partitioner2::CfgConstVertexSet cfgEndVertices,
const Partitioner2::CfgConstVertexSet cfgAvoidVertices = Partitioner2::CfgConstVertexSet(),
const Partitioner2::CfgConstEdgeSet cfgAvoidEdges = Partitioner2::CfgConstEdgeSet() 
)

Specify search boundary.

This function initializes the analysis by specifying starting and ending CFG vertices and the vertices and edges that should be avoided.

void Rose::BinaryAnalysis::FeasiblePath::setSearchBoundary ( const Partitioner2::Partitioner partitioner,
const Partitioner2::ControlFlowGraph::ConstVertexIterator &  cfgBeginVertex,
const Partitioner2::ControlFlowGraph::ConstVertexIterator &  cfgEndVertex,
const Partitioner2::CfgConstVertexSet cfgAvoidVertices = Partitioner2::CfgConstVertexSet(),
const Partitioner2::CfgConstEdgeSet cfgAvoidEdges = Partitioner2::CfgConstEdgeSet() 
)

Specify search boundary.

This function initializes the analysis by specifying starting and ending CFG vertices and the vertices and edges that should be avoided.

void Rose::BinaryAnalysis::FeasiblePath::depthFirstSearch ( PathProcessor pathProcessor)

Find all feasible paths.

Searches for paths and calls the pathProcessor each time a feasible path is found. The space explored using a depth first search, and the search can be limited with various settings.

const Partitioner2::Partitioner& Rose::BinaryAnalysis::FeasiblePath::partitioner ( ) const

Property: Partitioner currently in use.

Returns a reference to the partitioner that is currently in use, set by setSearchBoundary. It is a fatal error to call this function if there is no partitioner.

const FunctionSummaries& Rose::BinaryAnalysis::FeasiblePath::functionSummaries ( ) const
inline

Function summary information.

This is a map of functions that have been summarized, indexed by function entry address.

Definition at line 357 of file BinaryFeasiblePath.h.

const FunctionSummary& Rose::BinaryAnalysis::FeasiblePath::functionSummary ( rose_addr_t  entryVa) const

Function summary information.

This is the summary information for a single function. If the specified function is not summarized then a default-constructed summary information object is returned.

const VarDetail& Rose::BinaryAnalysis::FeasiblePath::varDetail ( const InstructionSemantics2::BaseSemantics::StatePtr state,
const std::string &  varName 
) const

Details about a variable.

Member Data Documentation

Sawyer::Message::Facility Rose::BinaryAnalysis::FeasiblePath::mlog
static

Diagnostic output.

Definition at line 68 of file BinaryFeasiblePath.h.

RegisterDescriptor Rose::BinaryAnalysis::FeasiblePath::REG_PATH

Descriptor of path pseudo-registers.

This analysis adds a special register named "path" to the register dictionary. This register holds the expression that determines how to reach the end of the path from the beginning. The major and minor numbers are arbitrary, but chosen so that they hopefully don't conflict with any real registers, which tend to start counting at zero. Since we're using BaseSemantics::RegisterStateGeneric, we can use its flexibility to store extra "registers" without making any other changes to the architecture.

Definition at line 77 of file BinaryFeasiblePath.h.


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