ROSE  0.9.9.109
BinaryFeasiblePath.h
1 #ifndef ROSE_BinaryAnalysis_FeasiblePath_H
2 #define ROSE_BinaryAnalysis_FeasiblePath_H
3 
4 #include <BaseSemantics2.h>
5 #include <Partitioner2/CfgPath.h>
6 #include <Sawyer/Message.h>
7 #include <SMTSolver.h>
8 #include <boost/filesystem/path.hpp>
9 
10 namespace Rose {
11 namespace BinaryAnalysis {
12 
16 class FeasiblePath {
18  // Types and public data members
20 public:
21  enum SearchMode { SEARCH_SINGLE_DFS, SEARCH_SINGLE_BFS, SEARCH_MULTI };
22 
24  struct Settings {
25  SearchMode searchMode;
28  size_t maxPathLength;
29  size_t maxCallDepth;
31  std::vector<SymbolicExpr::Ptr> postConditions;
32  std::vector<rose_addr_t> summarizeFunctions;
37  : searchMode(SEARCH_SINGLE_DFS), vertexVisitLimit((size_t)-1), maxPathLength((size_t)-1), maxCallDepth((size_t)-1),
38  maxRecursionDepth((size_t)-1), nonAddressIsFeasible(true) {}
39  };
40 
43 
52 
54  struct VarDetail {
55  std::string registerName;
56  std::string firstAccessMode;
60  size_t memSize;
61  size_t memByteNumber;
64  VarDetail(): firstAccessInsn(NULL), memSize(0), memByteNumber(0) {}
65  std::string toString() const;
66  };
67 
71  class PathProcessor {
72  public:
73  enum Action {
76  };
77 
78  virtual ~PathProcessor() {}
79  virtual Action found(const FeasiblePath &analyzer, const Partitioner2::CfgPath &path,
80  const std::vector<SymbolicExpr::Ptr> &pathConditions,
82  SMTSolver &solver) = 0;
83  };
84 
88  struct FunctionSummary {
89  rose_addr_t address;
90  int64_t stackDelta;
91  std::string name;
94  FunctionSummary(): stackDelta(SgAsmInstruction::INVALID_STACK_DELTA) {}
95 
97  FunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgFuncVertex, uint64_t stackDelta);
98  };
99 
102 
103 
105  // Private data members
107 private:
108  const Partitioner2::Partitioner *partitioner_; // binary analysis context
109  RegisterDictionary *registers_; // registers augmented with "path" pseudo-register
110  RegisterDescriptor REG_RETURN_; // FIXME[Robb P Matzke 2016-10-11]: see source
111  Settings settings_;
112  FunctionSummaries functionSummaries_;
113  Partitioner2::CfgVertexMap vmap_; // relates CFG vertices to path vertices
114  Partitioner2::ControlFlowGraph paths_; // all possible paths, feasible or otherwise
115  Partitioner2::CfgConstVertexSet pathsBeginVertices_;// vertices of paths_ where searching starts
116  Partitioner2::CfgConstVertexSet pathsEndVertices_; // vertices of paths_ where searching stops
117  Partitioner2::CfgConstEdgeSet cfgAvoidEdges_; // CFG edges to avoid
118  Partitioner2::CfgConstVertexSet cfgEndAvoidVertices_;// CFG end-of-path and other avoidance vertices
119 
120 
122  // Construction, destruction
124 public:
127  : registers_(NULL) {}
128 
129  virtual ~FeasiblePath() {}
130 
132  void reset() {
133  partitioner_ = NULL;
134  registers_ = NULL;
135  REG_PATH = REG_RETURN_ = RegisterDescriptor();
136  functionSummaries_.clear();
137  vmap_.clear();
138  paths_.clear();
139  pathsBeginVertices_.clear();
140  pathsEndVertices_.clear();
141  cfgAvoidEdges_.clear();
142  cfgEndAvoidVertices_.clear();
143  }
144 
146  static void initDiagnostics();
147 
148 
150  // Settings affecting behavior
152 public:
156  const Settings& settings() const { return settings_; }
157  Settings& settings() { return settings_; }
158  void settings(const Settings &s) { settings_ = s; }
162  // Overridable processing functions
165 public:
173 
180  virtual void
182  const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsBeginVertex);
183 
188  virtual void
190  const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex);
191 
195  virtual void
196  processIndeterminateBlock(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex,
198  size_t pathInsnIndex);
199 
203  virtual void
204  processFunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
206  size_t pathInsnIndex);
207 
211  virtual void
213  const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
214  size_t &pathInsnIndex /*in,out*/);
215 
217  virtual bool
218  shouldSummarizeCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex,
220  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);
221 
223  virtual bool
224  shouldInline(const Partitioner2::CfgPath &path, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);
225 
226 
228  // Utilities
230 public:
232  Partitioner2::ControlFlowGraph::ConstVertexIterator
233  pathToCfg(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex) const;
234 
238 
241 
243  bool isFunctionCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator&) const;
244 
246  void printPathVertex(std::ostream &out, const Partitioner2::ControlFlowGraph::Vertex &pathVertex,
247  size_t &insnIdx /*in,out*/) const;
248 
252  void printPath(std::ostream &out, const Partitioner2::CfgPath&) const;
253 
259  virtual boost::tribool
260  isPathFeasible(const Partitioner2::CfgPath &path, SMTSolver&, const std::vector<SymbolicExpr::Ptr> &postConditions,
261  std::vector<SymbolicExpr::Ptr> &pathConditions /*in,out*/,
263 
264 
266  // Functions for describing the search space
268 public:
269 
276  void
278  const Partitioner2::CfgConstVertexSet &cfgBeginVertices,
279  const Partitioner2::CfgConstVertexSet &cfgEndVertices,
282  void
283  setSearchBoundary(const Partitioner2::Partitioner &partitioner,
284  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgBeginVertex,
285  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgEndVertex,
291  // Functions for searching for paths
294 public:
299  void depthFirstSearch(PathProcessor &pathProcessor);
300 
301 
303  // Functions for getting the results
305 public:
310  const Partitioner2::Partitioner& partitioner() const;
311 
315  const FunctionSummaries& functionSummaries() const {
316  return functionSummaries_;
317  }
318 
323  const FunctionSummary& functionSummary(rose_addr_t entryVa) const;
324 
326  const VarDetail& varDetail(const InstructionSemantics2::BaseSemantics::StatePtr &state, const std::string &varName) const;
327 
328 
330  // Private supporting functions
332 private:
333  static rose_addr_t virtualAddress(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex);
334 
335  void insertCallSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsCallSite,
337  const Partitioner2::ControlFlowGraph::ConstEdgeIterator &cfgCallEdge);
338 
339  boost::filesystem::path emitPathGraph(size_t callId, size_t graphId); // emit paths graph to "rose-debug" directory
340 };
341 
342 } // namespace
343 } // namespace
344 
345 #endif
std::string firstAccessMode
How was variable first accessed ("read" or "write").
std::vector< rose_addr_t > summarizeFunctions
Functions to always summarize.
Sawyer::Container::Map< rose_addr_t, FunctionSummary > FunctionSummaries
Summaries for multiple functions.
size_t vertexVisitLimit
Max times to visit a particular vertex in one path.
rose_addr_t address
Address of summarized function.
void printPathVertex(std::ostream &out, const Partitioner2::ControlFlowGraph::Vertex &pathVertex, size_t &insnIdx) const
Print one vertex of a path for debugging.
Information stored per V_USER_DEFINED path vertex.
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.
void depthFirstSearch(PathProcessor &pathProcessor)
Find all feasible paths.
virtual void processIndeterminateBlock(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex, const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex)
Process an indeterminate block.
Base class for machine instructions.
Sawyer::Optional< rose_addr_t > returnFrom
This variable is the return value from the specified function.
Collection of streams.
Definition: Message.h:1579
FeasiblePath()
Constructs a new feasible path analyzer.
void clear()
Erase all mappings.
Definition: BiMap.h:63
std::set< ControlFlowGraph::ConstVertexIterator > CfgConstVertexSet
Set of CFG vertex pointers.
virtual void processFunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex, const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex)
Process a function summary vertex.
RegisterDescriptor REG_PATH
Descriptor of path pseudo-registers.
std::string name
Name of summarized function.
Sawyer::Optional< size_t > firstAccessIdx
Instruction position in path where this var was first read.
Main namespace for the ROSE library.
Describes (part of) a physical CPU register.
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:616
size_t maxCallDepth
Max length of path in terms of function calls.
const FunctionSummaries & functionSummaries() const
Function summary information.
Partitioner2::CfgConstVertexSet cfgToPaths(const Partitioner2::CfgConstVertexSet &) const
Convert CFG vertices to path vertices.
virtual bool shouldInline(const Partitioner2::CfgPath &path, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget)
Determines whether a function call should be inlined.
void settings(const Settings &s)
Property: Settings used by this analysis.
boost::shared_ptr< class State > StatePtr
Shared-ownership pointer to a semantic state.
size_t maxPathLength
Limit path length in terms of number of instructions.
const VarDetail & varDetail(const InstructionSemantics2::BaseSemantics::StatePtr &state, const std::string &varName) const
Details about a variable.
boost::shared_ptr< class Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
FunctionSummary()
Construct empty function summary.
bool nonAddressIsFeasible
Indeterminate/undiscovered vertices are feasible?
size_t maxRecursionDepth
Max path length in terms of recursive function calls.
void reset()
Reset to initial state without changing settings.
A path through a control flow graph.
Definition: CfgPath.h:15
std::set< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
Information about a variable seen on a path.
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.
bool isFunctionCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator &) const
True if vertex is a function call.
Defines registers available for a particular architecture.
Definition: Registers.h:32
SearchMode searchMode
Method to use when searching for feasible paths.
void clear()
Remove all vertices and edges.
Definition: Graph.h:1990
bool pathEndsWithFunctionCall(const Partitioner2::CfgPath &) const
True if path ends with a function call.
void printPath(std::ostream &out, const Partitioner2::CfgPath &) const
Print the path to the specified output stream.
const Settings & settings() const
Property: Settings used by this analysis.
size_t memByteNumber
Byte number for memory access.
int64_t stackDelta
Stack delta for summarized function.
virtual boost::tribool isPathFeasible(const Partitioner2::CfgPath &path, SMTSolver &, const std::vector< SymbolicExpr::Ptr > &postConditions, std::vector< SymbolicExpr::Ptr > &pathConditions, InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu)
Determine whether a single path is feasible.
static Sawyer::Message::Facility mlog
Diagnostic output.
virtual void processVertex(const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t &pathInsnIndex)
Process one vertex.
virtual InstructionSemantics2::BaseSemantics::DispatcherPtr buildVirtualCpu(const Partitioner2::Partitioner &)
Create the virtual CPU.
Partitioner2::ControlFlowGraph::ConstVertexIterator pathToCfg(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex) const
Convert path vertex to a CFG vertex.
const FunctionSummary & functionSummary(rose_addr_t entryVa) const
Function summary information.
std::vector< SymbolicExpr::Ptr > postConditions
Additional constraints to be satisifed at the end of a path.
const Partitioner2::Partitioner & partitioner() const
Property: Partitioner currently in use.
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.
SymbolicExpr::Ptr memAddress
Address where variable is located.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:289
Settings & settings()
Property: Settings used by this analysis.
size_t memSize
Size of total memory access in bytes.
SgAsmInstruction * firstAccessInsn
Instruction address where this var was first read.
Settings that control this analysis.
static void initDiagnostics()
Initialize diagnostic output.
Interface to Satisfiability Modulo Theory (SMT) solvers.
Definition: SMTSolver.h:19
virtual void setInitialState(const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsBeginVertex)
Initialize state for first vertex of path.
Sawyer::Optional< rose_addr_t > initialStackPtr
Concrete value to use for stack pointer register initial value.