1 #ifndef ROSE_BinaryAnalysis_FeasiblePath_H
2 #define ROSE_BinaryAnalysis_FeasiblePath_H
4 #include <BaseSemantics2.h>
5 #include <BinarySmtSolver.h>
6 #include <BinarySymbolicExprParser.h>
7 #include <Partitioner2/CfgPath.h>
8 #include <Sawyer/CommandLine.h>
9 #include <Sawyer/Message.h>
10 #include <boost/filesystem/path.hpp>
12 namespace Rose {
13 namespace BinaryAnalysis {
18 class FeasiblePath {
20  // Types and public data members
22 public:
29  };
32  enum IoMode { READ, WRITE };
35  enum MayOrMust { MAY, MUST };
38  struct Settings {
39  // Path feasibility
40  SearchMode searchMode;
43  size_t maxPathLength;
44  size_t maxCallDepth;
46  std::vector<SymbolicExpr::Ptr> postConditions;
47  std::vector<std::string> postConditionStrings;
48  std::vector<rose_addr_t> summarizeFunctions;
50  std::string solverName;
53  // Null dereferences
54  struct NullDeref {
55  bool check;
57  bool constOnly;
59  NullDeref()
60  : check(false), mode(MUST), constOnly(false) {}
61  } nullDeref;
65  : searchMode(SEARCH_SINGLE_DFS), vertexVisitLimit((size_t)-1), maxPathLength((size_t)-1), maxCallDepth((size_t)-1),
66  maxRecursionDepth((size_t)-1), nonAddressIsFeasible(true), solverName("best"),
67  memoryParadigm(LIST_BASED_MEMORY) {}
68  };
83  struct VarDetail {
84  std::string registerName;
85  std::string firstAccessMode;
89  size_t memSize;
90  size_t memByteNumber;
93  VarDetail(): firstAccessInsn(NULL), memSize(0), memByteNumber(0) {}
94  std::string toString() const;
95  };
104  public:
105  enum Action {
108  };
110  virtual ~PathProcessor() {}
113  virtual Action found(const FeasiblePath &analyzer, const Partitioner2::CfgPath &path,
114  const std::vector<SymbolicExpr::Ptr> &pathConditions,
116  const SmtSolverPtr &solver) { return CONTINUE; };
135  virtual void memoryIo(const FeasiblePath &analyzer, IoMode ioMode,
139  };
145  rose_addr_t address;
146  int64_t stackDelta;
147  std::string name;
150  FunctionSummary(): stackDelta(SgAsmInstruction::INVALID_STACK_DELTA) {}
153  FunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgFuncVertex, uint64_t stackDelta);
154  };
163  public:
166  protected:
167  FunctionSummarizer() {}
168  public:
170  virtual void init(const FeasiblePath &analysis, FunctionSummary &summary /*in,out*/,
171  const Partitioner2::Function::Ptr &function,
172  Partitioner2::ControlFlowGraph::ConstVertexIterator cfgCallTarget) = 0;
178  virtual bool process(const FeasiblePath &analysis, const FunctionSummary &summary,
186  returnValue(const FeasiblePath &analysis, const FunctionSummary &summary,
188  };
191  // Private data members
193 private:
194  const Partitioner2::Partitioner *partitioner_; // binary analysis context
195  RegisterDictionary *registers_; // registers augmented with "path" pseudo-register
196  RegisterDescriptor REG_RETURN_; // FIXME[Robb P Matzke 2016-10-11]: see source
197  Settings settings_;
198  FunctionSummaries functionSummaries_;
199  Partitioner2::CfgVertexMap vmap_; // relates CFG vertices to path vertices
200  Partitioner2::ControlFlowGraph paths_; // all possible paths, feasible or otherwise
201  Partitioner2::CfgConstVertexSet pathsBeginVertices_;// vertices of paths_ where searching starts
202  Partitioner2::CfgConstVertexSet pathsEndVertices_; // vertices of paths_ where searching stops
203  Partitioner2::CfgConstEdgeSet cfgAvoidEdges_; // CFG edges to avoid
204  Partitioner2::CfgConstVertexSet cfgEndAvoidVertices_;// CFG end-of-path and other avoidance vertices
205  FunctionSummarizer::Ptr functionSummarizer_; // user-defined function for handling function summaries
209  // Construction, destruction
211 public:
214  : registers_(NULL) {}
216  virtual ~FeasiblePath() {}
219  void reset() {
220  partitioner_ = NULL;
221  registers_ = NULL;
222  REG_PATH = REG_RETURN_ = RegisterDescriptor();
223  functionSummaries_.clear();
224  vmap_.clear();
225  paths_.clear();
226  pathsBeginVertices_.clear();
227  pathsEndVertices_.clear();
228  cfgAvoidEdges_.clear();
229  cfgEndAvoidVertices_.clear();
230  }
233  static void initDiagnostics();
237  // Settings affecting behavior
239 public:
243  const Settings& settings() const { return settings_; }
244  Settings& settings() { return settings_; }
245  void settings(const Settings &s) { settings_ = s; }
256  // Overridable processing functions
258 public:
265  buildVirtualCpu(const Partitioner2::Partitioner&, PathProcessor*);
273  virtual void
275  const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsBeginVertex);
281  virtual void
283  const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex);
288  virtual void
289  processIndeterminateBlock(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex,
291  size_t pathInsnIndex);
296  virtual void
297  processFunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
299  size_t pathInsnIndex);
304  virtual void
306  const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
307  size_t &pathInsnIndex /*in,out*/);
310  virtual bool
311  shouldSummarizeCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex,
313  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);
316  virtual bool
317  shouldInline(const Partitioner2::CfgPath &path, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);
327  FunctionSummarizer::Ptr functionSummarizer() const { return functionSummarizer_; }
328  void functionSummarizer(const FunctionSummarizer::Ptr &f) { functionSummarizer_ = f; }
331  // Utilities
334 public:
336  Partitioner2::ControlFlowGraph::ConstVertexIterator
337  pathToCfg(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex) const;
347  bool isFunctionCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator&) const;
350  void printPathVertex(std::ostream &out, const Partitioner2::ControlFlowGraph::Vertex &pathVertex,
351  size_t &insnIdx /*in,out*/) const;
356  void printPath(std::ostream &out, const Partitioner2::CfgPath&) const;
363  virtual boost::tribool
365  std::vector<SymbolicExpr::Ptr> postConditions, const SymbolicExprParser::RegisterSubstituter::Ptr&,
366  PathProcessor *pathProcessor, std::vector<SymbolicExpr::Ptr> &pathConditions /*in,out*/,
371  // Functions for describing the search space
373 public:
381  void
383  const Partitioner2::CfgConstVertexSet &cfgBeginVertices,
384  const Partitioner2::CfgConstVertexSet &cfgEndVertices,
387  void
388  setSearchBoundary(const Partitioner2::Partitioner &partitioner,
389  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgBeginVertex,
390  const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgEndVertex,
396  // Functions for searching for paths
399 public:
404  void depthFirstSearch(PathProcessor &pathProcessor);
408  // Functions for getting the results
410 public:
415  const Partitioner2::Partitioner& partitioner() const;
420  const FunctionSummaries& functionSummaries() const {
421  return functionSummaries_;
422  }
428  const FunctionSummary& functionSummary(rose_addr_t entryVa) const;
431  const VarDetail& varDetail(const InstructionSemantics2::BaseSemantics::StatePtr &state, const std::string &varName) const;
434  const VarDetails& varDetails(const InstructionSemantics2::BaseSemantics::StatePtr &state) const;
438  // Private supporting functions
440 private:
441  static rose_addr_t virtualAddress(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex);
443  void insertCallSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsCallSite,
445  const Partitioner2::ControlFlowGraph::ConstEdgeIterator &cfgCallEdge);
447  boost::filesystem::path emitPathGraph(size_t callId, size_t graphId); // emit paths graph to "rose-debug" directory
448 };
450 } // namespace
451 } // namespace
453 #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.
Sawyer::Container::Map< std::string, FeasiblePath::VarDetail > VarDetails
Variable detail by name.
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.
virtual Action found(const FeasiblePath &analyzer, const Partitioner2::CfgPath &path, const std::vector< SymbolicExpr::Ptr > &pathConditions, const InstructionSemantics2::BaseSemantics::DispatcherPtr &, const SmtSolverPtr &solver)
Function invoked whenever a complete path is found.
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.
A collection of related switch declarations.
const VarDetails & varDetails(const InstructionSemantics2::BaseSemantics::StatePtr &state) const
Details about all variables by name.
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.
virtual boost::tribool isPathFeasible(const Partitioner2::CfgPath &path, const SmtSolverPtr &, std::vector< SymbolicExpr::Ptr > postConditions, const SymbolicExprParser::RegisterSubstituter::Ptr &, PathProcessor *pathProcessor, std::vector< SymbolicExpr::Ptr > &pathConditions, InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu)
Determine whether a single path is feasible.
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.
virtual void memoryIo(const FeasiblePath &analyzer, IoMode ioMode, const InstructionSemantics2::BaseSemantics::SValuePtr &addr, const InstructionSemantics2::BaseSemantics::SValuePtr &value, const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &ops)
Function invoked every time a memory reference occurs.
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.
std::vector< std::string > postConditionStrings
Additional post conditions as strings to be parsed.
Construct empty function summary.
bool nonAddressIsFeasible
Indeterminate/undiscovered vertices are feasible?
size_t maxRecursionDepth
Max path length in terms of recursive function calls.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
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.
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
static Sawyer::CommandLine::SwitchGroup commandLineSwitches(Settings &settings)
Describe command-line switches.
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:293
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.
Container associating values with keys.
Definition: Sawyer/Map.h:66
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.