ROSE  0.11.54.0
Partitioner.h
1 #ifndef ROSE_BinaryAnalysis_Partitioner2_Partitioner_H
2 #define ROSE_BinaryAnalysis_Partitioner2_Partitioner_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/Partitioner2/AddressUsageMap.h>
7 #include <Rose/BinaryAnalysis/Partitioner2/BasicBlock.h>
8 #include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
9 #include <Rose/BinaryAnalysis/Partitioner2/Config.h>
10 #include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
11 #include <Rose/BinaryAnalysis/Partitioner2/DataBlock.h>
12 #include <Rose/BinaryAnalysis/Partitioner2/Function.h>
13 #include <Rose/BinaryAnalysis/Partitioner2/FunctionCallGraph.h>
14 #include <Rose/BinaryAnalysis/Partitioner2/InstructionProvider.h>
15 #include <Rose/BinaryAnalysis/Partitioner2/Modules.h>
16 #include <Rose/BinaryAnalysis/Partitioner2/Reference.h>
17 
18 #include <Sawyer/Attribute.h>
19 #include <Sawyer/Callbacks.h>
20 #include <Sawyer/IntervalSet.h>
21 #include <Sawyer/Map.h>
22 #include <Sawyer/Message.h>
23 #include <Sawyer/Optional.h>
24 #include <Sawyer/ProgressBar.h>
25 #include <Sawyer/SharedPointer.h>
26 
27 #include <Rose/BinaryAnalysis/SourceLocations.h>
28 #include <Rose/BinaryAnalysis/Unparser/Settings.h>
29 #include <Rose/Progress.h>
30 
31 #include <boost/filesystem.hpp>
32 #include <boost/move/utility_core.hpp>
33 #include <boost/serialization/access.hpp>
34 #include <boost/serialization/split_member.hpp>
35 #include <boost/serialization/version.hpp>
36 
37 #include <ostream>
38 #include <set>
39 #include <string>
40 #include <vector>
41 
42 // Derived classes needed for serialization
43 #include <Rose/BinaryAnalysis/YicesSolver.h>
44 #include <Rose/BinaryAnalysis/Z3Solver.h>
45 #include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherAarch32.h>
46 #include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherAarch64.h>
47 #include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherM68k.h>
48 #include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherPowerpc.h>
49 #include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherX86.h>
50 
51 // Define ROSE_PARTITIONER_MOVE if boost::move works. Mainly this is to work around a GCC bug that reports this error:
52 //
53 // prototype for
54 // 'Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)'
55 // does not match any in class 'Rose::BinaryAnalysis::Partitioner2::Partitioner'
56 //
57 // followed by saying that the exact same signature is one of the candidates:
58 //
59 // candidates are:
60 // Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)
61 //
62 // This is apparently GCC issue 49377 [https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49377] fixed in GCC-6.1.0.
63 #if __cplusplus >= 201103L
64  #define ROSE_PARTITIONER_MOVE
65 #elif defined(__GNUC__)
66  #if __GNUC__ > 5
67  #define ROSE_PARTITIONER_MOVE
68  #elif BOOST_VERSION >= 106900 // 1.68.0 might be okay too, but ROSE blacklists it for other reasons
69  #define ROSE_PARTITIONER_MOVE
70  #endif
71 #endif
72 
73 namespace Rose {
74 namespace BinaryAnalysis {
75 namespace Partitioner2 {
76 
290 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
291 #ifdef ROSE_PARTITIONER_MOVE
292  BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
293 #endif
294 
295 public:
298  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
299  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
302  struct Thunk {
304  rose_addr_t target;
305  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
306  };
307 
310 
311 private:
312  BasePartitionerSettings settings_; // settings adjustable from the command-line
313  Configuration config_; // configuration information about functions, blocks, etc.
314  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
315  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
316  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
317  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
318  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
319  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
320  Functions functions_; // List of all attached functions by entry address
321  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
322  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
323  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
324  AddressNameMap addressNames_; // Names for various addresses
325  SourceLocations sourceLocations_; // Mapping between source locations and addresses
326  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
327  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
328  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
329  Unparser::BasePtr insnPlainUnparser_; // For unparsing just instruction mnemonic and operands
330 
331  // Callback lists
332  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
333  BasicBlockCallbacks basicBlockCallbacks_;
334  FunctionPrologueMatchers functionPrologueMatchers_;
335  FunctionPaddingMatchers functionPaddingMatchers_;
336 
337  // Special CFG vertices.
338  ControlFlowGraph::VertexIterator undiscoveredVertex_;
339  ControlFlowGraph::VertexIterator indeterminateVertex_;
340  ControlFlowGraph::VertexIterator nonexistingVertex_;
341  static const size_t nSpecialVertices = 3;
342 
343  // Optional cached information
344  Sawyer::Optional<rose_addr_t> elfGotVa_; // address of ELF GOT, set by findElfGotVa
345 
346  // Protects the following data members
347  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
348  Progress::Ptr progress_; // Progress reporter to update, or null
349  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
350 
351 
352 
355  //
356  // Serialization
357  //
360 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
361 private:
362  friend class boost::serialization::access;
363 
364  template<class S>
365  void serializeCommon(S &s, const unsigned version) {
366  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
367  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
368 #ifdef ROSE_ENABLE_ASM_AARCH64
369  s.template register_type<InstructionSemantics2::DispatcherAarch64>();
370 #endif
371 #ifdef ROSE_ENABLE_ASM_AARCH32
372  s.template register_type<InstructionSemantics2::DispatcherAarch32>();
373 #endif
374  s.template register_type<InstructionSemantics2::DispatcherX86>();
375  s.template register_type<InstructionSemantics2::DispatcherM68k>();
376  s.template register_type<InstructionSemantics2::DispatcherPowerpc>();
377  s.template register_type<SymbolicExpr::Interior>();
378  s.template register_type<SymbolicExpr::Leaf>();
379  s.template register_type<YicesSolver>();
380  s.template register_type<Z3Solver>();
381  s.template register_type<Semantics::SValue>();
382  s.template register_type<Semantics::MemoryListState>();
383  s.template register_type<Semantics::MemoryMapState>();
384  s.template register_type<Semantics::RegisterState>();
385  s.template register_type<Semantics::State>();
386  s.template register_type<Semantics::RiscOperators>();
387  s & BOOST_SERIALIZATION_NVP(settings_);
388  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
389  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
390  s & BOOST_SERIALIZATION_NVP(memoryMap_);
391  s & BOOST_SERIALIZATION_NVP(cfg_);
392  // s & vertexIndex_; -- initialized by rebuildVertexIndices
393  s & BOOST_SERIALIZATION_NVP(aum_);
394  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
395  s & BOOST_SERIALIZATION_NVP(functions_);
396  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
397  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
398  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
399  s & BOOST_SERIALIZATION_NVP(addressNames_);
400  if (version >= 1)
401  s & BOOST_SERIALIZATION_NVP(sourceLocations_);
402  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
403  // s & unparser_; -- not saved; restored from disassembler
404  // s & cfgAdjustmentCallbacks_; -- not saved/restored
405  // s & basicBlockCallbacks_; -- not saved/restored
406  // s & functionPrologueMatchers_; -- not saved/restored
407  // s & functionPaddingMatchers_; -- not saved/restored
408  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
409  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
410  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
411  if (version >= 2)
412  s & BOOST_SERIALIZATION_NVP(elfGotVa_);
413  // s & progress_; -- not saved/restored
414  // s & cfgProgressTotal_; -- not saved/restored
415  }
416 
417  template<class S>
418  void save(S &s, const unsigned version) const {
419  const_cast<Partitioner*>(this)->serializeCommon(s, version);
420  }
421 
422  template<class S>
423  void load(S &s, const unsigned version) {
424  serializeCommon(s, version);
425  rebuildVertexIndices();
426  }
427 
428  BOOST_SERIALIZATION_SPLIT_MEMBER();
429 #endif
430 
431 
432 
435  //
436  // Constructors
437  //
440 public:
445  Partitioner();
446 
451  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
452 
453 #ifdef ROSE_PARTITIONER_MOVE
454 
455  Partitioner(BOOST_RV_REF(Partitioner));
456 
458  Partitioner& operator=(BOOST_RV_REF(Partitioner));
459 #else
460  // These are unsafe
461  Partitioner(const Partitioner&);
462  Partitioner& operator=(const Partitioner&);
463 #endif
464 
465  ~Partitioner();
466 
473  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
474 
476  void clear() /*final*/;
477 
485  Configuration& configuration() { return config_; }
486  const Configuration& configuration() const { return config_; }
494  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
495  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
507  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
513  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
514  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
515  }
516 
519  //
520  // Unparsing
521  //
524 
534  Unparser::BasePtr unparser() const /*final*/;
535  void unparser(const Unparser::BasePtr&) /*final*/;
547  Unparser::BasePtr insnUnparser() const /*final*/;
548  void insnUnparser(const Unparser::BasePtr&) /*final*/;
552  void configureInsnUnparser(const Unparser::BasePtr&) const /*final*/;
553 
557  void configureInsnPlainUnparser(const Unparser::BasePtr&) const /*final*/;
558 
567  std::string unparse(SgAsmInstruction*) const;
568  void unparse(std::ostream&, SgAsmInstruction*) const;
569  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
570  void unparse(std::ostream&, const DataBlock::Ptr&) const;
571  void unparse(std::ostream&, const Function::Ptr&) const;
572  void unparse(std::ostream&) const;
578  std::string unparsePlain(SgAsmInstruction*) const;
579 
582  //
583  // Partitioner CFG queries
584  //
587 public:
593  size_t nBytes() const /*final*/ { return aum_.size(); }
594 
602  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
603  return undiscoveredVertex_;
604  }
605  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
606  return undiscoveredVertex_;
607  }
620  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
621  return indeterminateVertex_;
622  }
623  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
624  return indeterminateVertex_;
625  }
637  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
638  return nonexistingVertex_;
639  }
640  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
641  return nonexistingVertex_;
642  }
651  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
652 
659  const AddressUsageMap& aum() const /*final*/ { return aum_; }
660 
662  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
663 
668  std::vector<AddressUser> users(rose_addr_t) const /*final*/;
669 
677  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
678 
707  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
708  const Function::Ptr &function = Function::Ptr()) const /*final*/;
709  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
710  const Function::Ptr &function = Function::Ptr()) const /*final*/;
747  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
748  const Function::Ptr &sourceFunction = Function::Ptr(),
749  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
750  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
751  const Function::Ptr &sourceFunction = Function::Ptr(),
752  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
757  //
760  // Partitioner instruction operations
761  //
764 public:
770  size_t nInstructions() const /*final*/;
771 
781  AddressUser instructionExists(rose_addr_t startVa) const /*final*/ {
782  return aum_.findInstruction(startVa);
783  }
785  return aum_.findInstruction(insn);
786  }
795  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
796 
805  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
806 
815  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
816 
826  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
827 
835  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
836 
849  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
850 
855  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
856 
857 
858 
861  //
862  // Partitioner basic block placeholder operations
863  //
866 public:
876  size_t nPlaceholders() const /*final*/;
877 
886  bool placeholderExists(rose_addr_t startVa) const /*final*/;
887 
898  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
899  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
900  return *found;
901  return cfg_.vertices().end();
902  }
903  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
904  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
905  return *found;
906  return cfg_.vertices().end();
907  }
926  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
927 
941  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
942  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
947  //
950  // Partitioner basic block operations
951  //
954 public:
968  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
980  void basicBlockDropSemantics() const /*final*/;
981 
990  size_t nBasicBlocks() const /*final*/;
991 
999  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
1000 
1022  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
1023  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
1035  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
1036 
1047  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1048 
1058  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1059 
1066  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1067 
1077  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1078 
1084  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1085 
1110  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1111  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1112  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1126  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1127  SgAsmInstruction *insn) /*final*/;
1128 
1161  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1162  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1250  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1251  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1268  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
1269  Precision::Level precision = Precision::HIGH) const /*final*/;
1270 
1279  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1280 
1299  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1300 
1310  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;
1311 
1322  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1323 
1328  bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;
1329 
1370  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1371  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1382  void forgetStackDeltas() const /*final*/;
1383  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1395  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1396  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1449  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1450 
1451  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1460  void basicBlockMayReturnReset() const /*final*/;
1461 
1462 private:
1463  // Per-vertex data used during may-return analysis
1464  struct MayReturnVertexInfo {
1465  enum State {INIT, CALCULATING, FINISHED};
1466  State state; // current state of vertex
1467  bool processedCallees; // have we processed BBs this vertex calls?
1468  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1469  boost::logic::tribool result; // final result (eventually cached in BB)
1470  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1471  };
1472 
1473  // Is edge significant for analysis? See .C file for full documentation.
1474  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1475  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1476 
1477  // Determine (and cache in vertexInfo) whether any callees return.
1478  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1479  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1480 
1481  // Maximum may-return result from significant successors including phantom call-return edge.
1482  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1483  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1484 
1485  // The guts of the may-return analysis
1486  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1487  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1488 
1489 
1490 
1493  //
1494  // Partitioner data block operations
1495  //
1498 public:
1504  size_t nDataBlocks() const /*final*/;
1505 
1512  DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1513 
1522  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1523 
1535  DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;
1536 
1543  void detachDataBlock(const DataBlock::Ptr&) /*final*/;
1544 
1554  DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;
1555 
1568  DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;
1569 
1579  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1580 
1590  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1591 
1601  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1602 
1609  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1610 
1616  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1617 
1618 
1619 
1622  //
1623  // Partitioner function operations
1624  //
1627 public:
1633  size_t nFunctions() const /*final*/ { return functions_.size(); }
1634 
1653  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1654  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1655  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1663  std::vector<Function::Ptr> functions() const /*final*/;
1664 
1674  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1675 
1686  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1687 
1697  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1698 
1715  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1716  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1717  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1718  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1719  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1720  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1742  size_t attachFunction(const Function::Ptr&) /*final*/;
1743  size_t attachFunctions(const Functions&) /*final*/;
1759  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1760 
1777  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1778  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1794  void detachFunction(const Function::Ptr&) /*final*/;
1795 
1830  std::vector<Function::Ptr>
1831  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1832 
1833  std::vector<Function::Ptr>
1834  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1835 
1836  std::vector<Function::Ptr>
1837  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1838 
1839  std::vector<Function::Ptr>
1840  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1841 
1842  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1843  std::vector<Function::Ptr>
1844  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1845  std::vector<Function::Ptr> retval;
1846  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1847  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1848  insertUnique(retval, function, sortFunctionsByAddress);
1849  }
1850  return retval;
1851  }
1863  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1864 
1876  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1877 
1887  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1888 
1899  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1900 
1907  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1908 
1916  FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;
1917 
1937  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1938 
1942  void allFunctionStackDelta() const /*final*/;
1943 
1950  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1951 
1955  void allFunctionMayReturn() const /*final*/;
1956 
1983  const CallingConvention::Analysis&
1984  functionCallingConvention(const Function::Ptr&,
1985  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1986  const /*final*/;
1987 
2000  void
2001  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2002  const /*final*/;
2003 
2029  CallingConvention::Dictionary
2030  functionCallingConventionDefinitions(const Function::Ptr&,
2031  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2032  const /*final*/;
2033 
2046  void
2047  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
2048  CallingConvention::Definition::Ptr()) const /*final*/;
2049 
2058  void fixInterFunctionEdges() /*final*/;
2059  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2079  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2080 
2086  void allFunctionIsNoop() const /*final*/;
2087 
2095  void forgetFunctionIsNoop() const /*final*/;
2096  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2103  std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;
2104 
2105 
2106 
2109  //
2110  // Callbacks
2111  //
2114 public:
2132  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2133  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2144  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2145  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2148 public:
2156  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2157  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2184  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2185  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa, rose_addr_t &lastSearchedVa /*out*/) /*final*/;
2188 public:
2194  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2195  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2205  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2206 
2207 
2208 
2211  //
2212  // Partitioner miscellaneous
2213  //
2216 public:
2228  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2229  bool computeProperties=true) const /*final*/;
2230 
2244  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2245  bool showNeighbors=true) const /*final*/;
2246 
2252  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2253  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2259  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2260 
2266  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2267  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2275  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2276  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2284  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2285  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2291  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2292 
2296  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2297 
2301  static std::string functionName(const Function::Ptr&) /*final*/;
2302 
2307  void expandIndeterminateCalls();
2308 
2326  Progress::Ptr progress() const /*final*/;
2327  void progress(const Progress::Ptr&) /*final*/;
2334  void updateProgress(const std::string &phase, double completion) const;
2335 
2337  void showStatistics() const;
2338 
2339  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2340  void checkConsistency() const;
2341 
2348 
2352  Sawyer::Optional<rose_addr_t> elfGotVa() const;
2353 
2354 
2355 
2358  //
2359  // Settings
2360  //
2363 public:
2364 
2372  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2373  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2384  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2385  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2386  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2410  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2411  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2428  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2429  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2441  void addressName(rose_addr_t, const std::string&) /*final*/;
2442  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2443  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2451  const SourceLocations& sourceLocations() const /*final*/ { return sourceLocations_; }
2452  SourceLocations& sourceLocations() /*final*/ { return sourceLocations_; }
2453  void sourceLocations(const SourceLocations &locs) { sourceLocations_ = locs; }
2463  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2464  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2469  //
2472  // Instruction semantics
2473  //
2476 public:
2486  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2487  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2496  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2497 
2508  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2509  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2519  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2520 
2521 
2522 
2525  //
2526  // Python API support functions
2527  //
2530 #ifdef ROSE_ENABLE_PYTHON_API
2531  void pythonUnparse() const;
2532 #endif
2533 
2534 
2535 
2538  //
2539  // Partitioner internal utilities
2540  //
2543 private:
2544  void init(Disassembler*, const MemoryMap::Ptr&);
2545  void init(const Partitioner&);
2546  void updateCfgProgress();
2547 
2548 private:
2549  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2550  // and destination CFGs are identical.
2551  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2552  ControlFlowGraph::ConstVertexIterator otherIter);
2553 
2554  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2555  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2556  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2557 
2558  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2559  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2560  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2561 
2562  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2563  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2564 
2565  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2566  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2567  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2568 
2569  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2570  // The call happens immediately after the CFG/AUM are updated.
2571  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2572 
2573  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2574  void rebuildVertexIndices();
2575 };
2576 
2577 } // namespace
2578 } // namespace
2579 } // namespace
2580 
2581 // Class versions must be at global scope
2582 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::Partitioner, 2);
2583 
2584 #endif
2585 #endif
Represents information about a thunk.
Definition: Partitioner.h:302
size_t size() const
Number of addresses represented by the map.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:297
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2157
Contiguous region of a file.
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2496
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:303
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2156
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2442
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2385
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2464
Represents the file header of an ELF binary container.
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:623
const SourceLocations & sourceLocations() const
Property: Source locations.
Definition: Partitioner.h:2451
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:486
Base class for machine instructions.
Bidirectional mapping between addresses and source locations.
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2195
AddressUser instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:784
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:651
Provides and caches instructions.
STL namespace.
ControlFlowGraph::VertexIterator indeterminateVertex()
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:620
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:494
void sourceLocations(const SourceLocations &locs)
Property: Source locations.
Definition: Partitioner.h:2453
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1442
Main namespace for the ROSE library.
Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
Map address to name.
Definition: Partitioner.h:309
A container holding a set of values.
Definition: IntervalSet.h:55
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2144
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:602
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2486
Name space for the entire library.
Definition: FeasiblePath.h:787
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:485
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2429
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:903
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:659
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2443
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: HashMap.h:434
Base classes for instruction semantics.
Definition: Dispatcher.h:18
void settings(const BasePartitionerSettings &s)
Partitioner settings.
Definition: Partitioner.h:2373
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2428
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:304
ControlFlowGraph::VertexIterator nonexistingVertex()
Returns the special "non-existing" vertex.
Definition: Partitioner.h:637
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:473
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2386
SemanticMemoryParadigm
Organization of semantic memory.
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2145
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:969
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:577
void stackDeltaInterproceduralLimit(size_t n)
Property: max depth for inter-procedural stack delta analysis.
Definition: Partitioner.h:1396
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:495
bool checkingCallBranch
Check for situations where CALL is used as a branch.
bool usingSemantics
Whether instruction semantics are used.
A general, thread-safe way to report progress made on some task.
void autoAddCallReturnEdges(bool b)
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2410
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
bool basicBlockSemanticsAutoDrop() const
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:968
bool basicBlockSemanticsAutoDrop
Conserve memory by dropping semantics for attached basic blocks.
ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:605
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:640
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:298
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2194
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2133
API and storage for attributes.
Definition: Attribute.h:208
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:507
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2463
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:513
Virtual base class for instruction disassemblers.
Definition: Disassembler.h:50
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:386
void enableSymbolicSemantics(bool b=true)
Use or not use symbolic semantics.
Definition: Partitioner.h:2384
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2411
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:296
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:299
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2487
std::shared_ptr< class SmtSolver > SmtSolverPtr
Reference-counting pointer for SMT solvers.
Definition: SmtSolver.h:25
Holds configuration information.
Definition: Config.h:281
SourceLocations & sourceLocations()
Property: Source locations.
Definition: Partitioner.h:2452