1 #ifndef ROSE_BinaryAnalysis_FeasiblePath_H
2 #define ROSE_BinaryAnalysis_FeasiblePath_H
4 #include <BaseSemantics2.h>
5 #include <BinarySmtSolver.h>
6 #include <Partitioner2/CfgPath.h>
7 #include <Sawyer/Message.h>
8 #include <boost/filesystem/path.hpp>
10 namespace Rose {
11 namespace BinaryAnalysis {
16 class FeasiblePath {
18  // Types and public data members
20 public:
27  };
30  enum IoMode { READ, WRITE };
33  enum MayOrMust { MAY, MUST };
36  struct Settings {
37  // Path feasibility
38  SearchMode searchMode;
41  size_t maxPathLength;
42  size_t maxCallDepth;
44  std::vector<SymbolicExpr::Ptr> postConditions;
45  std::vector<rose_addr_t> summarizeFunctions;
47  std::string solverName;
50  // Null dereferences
51  struct NullDeref {
52  bool check;
54  bool constOnly;
56  NullDeref()
57  : check(false), mode(MUST), constOnly(false) {}
58  } nullDeref;
62  : searchMode(SEARCH_SINGLE_DFS), vertexVisitLimit((size_t)-1), maxPathLength((size_t)-1), maxCallDepth((size_t)-1),
63  maxRecursionDepth((size_t)-1), nonAddressIsFeasible(true), solverName("best"),
64  memoryParadigm(LIST_BASED_MEMORY) {}
65  };
80  struct VarDetail {
81  std::string registerName;
82  std::string firstAccessMode;
86  size_t memSize;
87  size_t memByteNumber;
90  VarDetail(): firstAccessInsn(NULL), memSize(0), memByteNumber(0) {}
91  std::string toString() const;
92  };
97  class PathProcessor {
98  public:
99  enum Action {
102  };
104  virtual ~PathProcessor() {}
107  virtual Action found(const FeasiblePath &analyzer, const Partitioner2::CfgPath &path,
108  const std::vector<SymbolicExpr::Ptr> &pathConditions,
110  const SmtSolverPtr &solver) = 0;
124  };
130  rose_addr_t address;
131  int64_t stackDelta;
132  std::string name;
135  FunctionSummary(): stackDelta(SgAsmInstruction::INVALID_STACK_DELTA) {}
138  FunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgFuncVertex, uint64_t stackDelta);
139  };
148  public:
151  protected:
152  FunctionSummarizer() {}
153  public:
155  virtual void init(const FeasiblePath &analysis, FunctionSummary &summary /*in,out*/,
156  const Partitioner2::Function::Ptr &function,
157  Partitioner2::ControlFlowGraph::ConstVertexIterator cfgCallTarget) = 0;
163  virtual bool process(const FeasiblePath &analysis, const FunctionSummary &summary,
171  returnValue(const FeasiblePath &analysis, const FunctionSummary &summary,
173  };
176  // Private data members
178 private:
179  const Partitioner2::Partitioner *partitioner_; // binary analysis context
180  RegisterDictionary *registers_; // registers augmented with "path" pseudo-register
181  RegisterDescriptor REG_RETURN_; // FIXME[Robb P Matzke 2016-10-11]: see source
182  Settings settings_;
183  FunctionSummaries functionSummaries_;
184  Partitioner2::CfgVertexMap vmap_; // relates CFG vertices to path vertices
185  Partitioner2::ControlFlowGraph paths_; // all possible paths, feasible or otherwise
186  Partitioner2::CfgConstVertexSet pathsBeginVertices_;// vertices of paths_ where searching starts
187  Partitioner2::CfgConstVertexSet pathsEndVertices_; // vertices of paths_ where searching stops
188  Partitioner2::CfgConstEdgeSet cfgAvoidEdges_; // CFG edges to avoid
189  Partitioner2::CfgConstVertexSet cfgEndAvoidVertices_;// CFG end-of-path and other avoidance vertices
190  FunctionSummarizer::Ptr functionSummarizer_; // user-defined function for handling function summaries
194  // Construction, destruction
196 public:
199  : registers_(NULL) {}
201  virtual ~FeasiblePath() {}
204  void reset() {
205  partitioner_ = NULL;
206  registers_ = NULL;
207  REG_PATH = REG_RETURN_ = RegisterDescriptor();
208  functionSummaries_.clear();
209  vmap_.clear();
210  paths_.clear();
211  pathsBeginVertices_.clear();
212  pathsEndVertices_.clear();
213  cfgAvoidEdges_.clear();
214  cfgEndAvoidVertices_.clear();
215  }
218  static void initDiagnostics();
222  // Settings affecting behavior
224 public:
228  const Settings& settings() const { return settings_; }
229  Settings& settings() { return settings_; }
230  void settings(const Settings &s) { settings_ = s; }
234  // Overridable processing functions
237 public:
244  buildVirtualCpu(const Partitioner2::Partitioner&, PathProcessor*);
252  virtual void
254  const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsBeginVertex);
260  virtual void
262  const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex);
267  virtual void
268  processIndeterminateBlock(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex,
270  size_t pathInsnIndex);
275  virtual void
276  processFunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
278  size_t pathInsnIndex);
283  virtual void
285  const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
286  size_t &pathInsnIndex /*in,out*/);
289  virtual bool
290  shouldSummarizeCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex,
292  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);
295  virtual bool
296  shouldInline(const Partitioner2::CfgPath &path, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);
306  FunctionSummarizer::Ptr functionSummarizer() const { return functionSummarizer_; }
307  void functionSummarizer(const FunctionSummarizer::Ptr &f) { functionSummarizer_ = f; }
310  // Utilities
313 public:
315  Partitioner2::ControlFlowGraph::ConstVertexIterator
316  pathToCfg(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex) const;
326  bool isFunctionCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator&) const;
329  void printPathVertex(std::ostream &out, const Partitioner2::ControlFlowGraph::Vertex &pathVertex,
330  size_t &insnIdx /*in,out*/) const;
335  void printPath(std::ostream &out, const Partitioner2::CfgPath&) const;
342  virtual boost::tribool
344  const std::vector<SymbolicExpr::Ptr> &postConditions, PathProcessor *pathProcessor,
345  std::vector<SymbolicExpr::Ptr> &pathConditions /*in,out*/,
350  // Functions for describing the search space
352 public:
360  void
362  const Partitioner2::CfgConstVertexSet &cfgBeginVertices,
363  const Partitioner2::CfgConstVertexSet &cfgEndVertices,
366  void
367  setSearchBoundary(const Partitioner2::Partitioner &partitioner,
368  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgBeginVertex,
369  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgEndVertex,
375  // Functions for searching for paths
378 public:
383  void depthFirstSearch(PathProcessor &pathProcessor);
387  // Functions for getting the results
389 public:
394  const Partitioner2::Partitioner& partitioner() const;
399  const FunctionSummaries& functionSummaries() const {
400  return functionSummaries_;
401  }
407  const FunctionSummary& functionSummary(rose_addr_t entryVa) const;
410  const VarDetail& varDetail(const InstructionSemantics2::BaseSemantics::StatePtr &state, const std::string &varName) const;
414  // Private supporting functions
416 private:
417  static rose_addr_t virtualAddress(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex);
419  void insertCallSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsCallSite,
421  const Partitioner2::ControlFlowGraph::ConstEdgeIterator &cfgCallEdge);
423  boost::filesystem::path emitPathGraph(size_t callId, size_t graphId); // emit paths graph to "rose-debug" directory
424 };
426 } // namespace
427 } // namespace
429 #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.
MayOrMust mode
Check for addrs that may or must be null.
size_t vertexVisitLimit
Max times to visit a particular vertex in one path.
virtual InstructionSemantics2::SymbolicSemantics::SValuePtr returnValue(const FeasiblePath &analysis, const FunctionSummary &summary, const InstructionSemantics2::SymbolicSemantics::RiscOperatorsPtr &ops)=0
Return value for function.
rose_addr_t address
Address of summarized function.
SemanticMemoryParadigm memoryParadigm
Type of memory state when there's a choice to be made.
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
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to symbolic RISC operations.
Constructs a new feasible path analyzer.
virtual bool process(const FeasiblePath &analysis, const FunctionSummary &summary, const InstructionSemantics2::SymbolicSemantics::RiscOperatorsPtr &ops)=0
Invoked when the analysis traverses the summary.
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.
virtual void nullDeref(IoMode ioMode, const InstructionSemantics2::BaseSemantics::SValuePtr &addr, SgAsmInstruction *)
Function invoked whenever a null pointer dereference is detected.
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.
size_t maxCallDepth
Max length of path in terms of function calls.
struct Rose::BinaryAnalysis::FeasiblePath::Settings::NullDeref nullDeref
Settings for null-dereference analysis.
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.
bool constOnly
If true, check only constants or sets of constants.
Base class for callbacks for function summaries.
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.
Construct empty function summary.
bool nonAddressIsFeasible
Indeterminate/undiscovered vertices are feasible?
virtual Action found(const FeasiblePath &analyzer, const Partitioner2::CfgPath &path, const std::vector< SymbolicExpr::Ptr > &pathConditions, const InstructionSemantics2::BaseSemantics::DispatcherPtr &, const SmtSolverPtr &solver)=0
Function invoked whenever a complete path is found.
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.
FunctionSummarizer::Ptr functionSummarizer() const
Property: Function summary handling.
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.
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.
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:1984
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.
Base class for reference counted objects.
Definition: SharedObject.h:22
Sawyer::SharedPointer< FunctionSummarizer > Ptr
Reference counting pointer.
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.
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:292
virtual InstructionSemantics2::BaseSemantics::DispatcherPtr buildVirtualCpu(const Partitioner2::Partitioner &, PathProcessor *)
Create the virtual CPU.
std::string solverName
Type of SMT solver.
void functionSummarizer(const FunctionSummarizer::Ptr &f)
Property: Function summary handling.
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.
bool check
If true, look for null dereferences along the paths.
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.
Organization of semantic memory.
virtual void init(const FeasiblePath &analysis, FunctionSummary &summary, const Partitioner2::Function::Ptr &function, Partitioner2::ControlFlowGraph::ConstVertexIterator cfgCallTarget)=0
Invoked when a new summary is created.