ROSE  0.11.98.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/Z3Solver.h>
44 #include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherAarch32.h>
45 #include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherAarch64.h>
46 #include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherM68k.h>
47 #include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherPowerpc.h>
48 #include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherX86.h>
49 
50 // [Robb Matzke 2022-06-22]: deprecated. Needed because some user code doesn't include the old InstructionSemantics2 header
51 // files where this same thing is defined, yet they use InstructionSemantics2 because such things were once declared by this
52 // header file due to it originally including InstructionSemantics2 headers (which it no longer does).
53 namespace Rose { namespace BinaryAnalysis { namespace InstructionSemantics2 = InstructionSemantics; }}
54 
55 // Define ROSE_PARTITIONER_MOVE if boost::move works. Mainly this is to work around a GCC bug that reports this error:
56 //
57 // prototype for
58 // 'Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)'
59 // does not match any in class 'Rose::BinaryAnalysis::Partitioner2::Partitioner'
60 //
61 // followed by saying that the exact same signature is one of the candidates:
62 //
63 // candidates are:
64 // Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)
65 //
66 // This is apparently GCC issue 49377 [https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49377] fixed in GCC-6.1.0.
67 #if __cplusplus >= 201103L
68  #define ROSE_PARTITIONER_MOVE
69 #elif defined(__GNUC__)
70  #if __GNUC__ > 5
71  #define ROSE_PARTITIONER_MOVE
72  #elif BOOST_VERSION >= 106900 // 1.68.0 might be okay too, but ROSE blacklists it for other reasons
73  #define ROSE_PARTITIONER_MOVE
74  #endif
75 #endif
76 
77 namespace Rose {
78 namespace BinaryAnalysis {
79 namespace Partitioner2 {
80 
294 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
295 #ifdef ROSE_PARTITIONER_MOVE
296  BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
297 #endif
298 
299 public:
302  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
303  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
306  struct Thunk {
308  rose_addr_t target;
309  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
310  };
311 
314 
315 private:
316  BasePartitionerSettings settings_; // settings adjustable from the command-line
317  Configuration config_; // configuration information about functions, blocks, etc.
318  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
319  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
320  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
321  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
322  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
323  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
324  Functions functions_; // List of all attached functions by entry address
325  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
326  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
327  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
328  AddressNameMap addressNames_; // Names for various addresses
329  SourceLocations sourceLocations_; // Mapping between source locations and addresses
330  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
331  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
332  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
333  Unparser::BasePtr insnPlainUnparser_; // For unparsing just instruction mnemonic and operands
334 
335  // Callback lists
336  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
337  BasicBlockCallbacks basicBlockCallbacks_;
338  FunctionPrologueMatchers functionPrologueMatchers_;
339  FunctionPaddingMatchers functionPaddingMatchers_;
340 
341  // Special CFG vertices.
342  ControlFlowGraph::VertexIterator undiscoveredVertex_;
343  ControlFlowGraph::VertexIterator indeterminateVertex_;
344  ControlFlowGraph::VertexIterator nonexistingVertex_;
345  static const size_t nSpecialVertices = 3;
346 
347  // Optional cached information
348  Sawyer::Optional<rose_addr_t> elfGotVa_; // address of ELF GOT, set by findElfGotVa
349 
350  // Protects the following data members
351  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
352  Progress::Ptr progress_; // Progress reporter to update, or null
353  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
354 
355 
356 
359  //
360  // Serialization
361  //
364 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
365 private:
366  friend class boost::serialization::access;
367 
368  template<class S>
369  void serializeCommon(S &s, const unsigned version) {
370  s.template register_type<InstructionSemantics::SymbolicSemantics::SValue>();
371  s.template register_type<InstructionSemantics::SymbolicSemantics::RiscOperators>();
372 #ifdef ROSE_ENABLE_ASM_AARCH64
373  s.template register_type<InstructionSemantics::DispatcherAarch64>();
374 #endif
375 #ifdef ROSE_ENABLE_ASM_AARCH32
376  s.template register_type<InstructionSemantics::DispatcherAarch32>();
377 #endif
378  s.template register_type<InstructionSemantics::DispatcherX86>();
379  s.template register_type<InstructionSemantics::DispatcherM68k>();
380  s.template register_type<InstructionSemantics::DispatcherPowerpc>();
381  s.template register_type<SymbolicExpr::Interior>();
382  s.template register_type<SymbolicExpr::Leaf>();
383  s.template register_type<Z3Solver>();
384  s.template register_type<Semantics::SValue>();
385  s.template register_type<Semantics::MemoryListState>();
386  s.template register_type<Semantics::MemoryMapState>();
387  s.template register_type<Semantics::RegisterState>();
388  s.template register_type<Semantics::State>();
389  s.template register_type<Semantics::RiscOperators>();
390  s & BOOST_SERIALIZATION_NVP(settings_);
391  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
392  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
393  s & BOOST_SERIALIZATION_NVP(memoryMap_);
394  s & BOOST_SERIALIZATION_NVP(cfg_);
395  // s & vertexIndex_; -- initialized by rebuildVertexIndices
396  s & BOOST_SERIALIZATION_NVP(aum_);
397  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
398  s & BOOST_SERIALIZATION_NVP(functions_);
399  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
400  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
401  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
402  s & BOOST_SERIALIZATION_NVP(addressNames_);
403  if (version >= 1)
404  s & BOOST_SERIALIZATION_NVP(sourceLocations_);
405  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
406  // s & unparser_; -- not saved; restored from disassembler
407  // s & cfgAdjustmentCallbacks_; -- not saved/restored
408  // s & basicBlockCallbacks_; -- not saved/restored
409  // s & functionPrologueMatchers_; -- not saved/restored
410  // s & functionPaddingMatchers_; -- not saved/restored
411  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
412  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
413  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
414  if (version >= 2)
415  s & BOOST_SERIALIZATION_NVP(elfGotVa_);
416  // s & progress_; -- not saved/restored
417  // s & cfgProgressTotal_; -- not saved/restored
418  }
419 
420  template<class S>
421  void save(S &s, const unsigned version) const {
422  const_cast<Partitioner*>(this)->serializeCommon(s, version);
423  }
424 
425  template<class S>
426  void load(S &s, const unsigned version) {
427  serializeCommon(s, version);
428  rebuildVertexIndices();
429  }
430 
431  BOOST_SERIALIZATION_SPLIT_MEMBER();
432 #endif
433 
434 
435 
438  //
439  // Constructors
440  //
443 public:
448  Partitioner();
449 
454  Partitioner(const Disassembler::BasePtr &disassembler, const MemoryMap::Ptr &map);
455 
456 #ifdef ROSE_PARTITIONER_MOVE
457 
458  Partitioner(BOOST_RV_REF(Partitioner));
459 
461  Partitioner& operator=(BOOST_RV_REF(Partitioner));
462 #else
463  // These are unsafe
464  Partitioner(const Partitioner&);
465  Partitioner& operator=(const Partitioner&);
466 #endif
467 
468  ~Partitioner();
469 
476  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
477 
479  void clear() /*final*/;
480 
488  Configuration& configuration() { return config_; }
489  const Configuration& configuration() const { return config_; }
497  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
498  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
510  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
516  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
517  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
518  }
519 
522  //
523  // Unparsing
524  //
527 
537  Unparser::BasePtr unparser() const /*final*/;
538  void unparser(const Unparser::BasePtr&) /*final*/;
550  Unparser::BasePtr insnUnparser() const /*final*/;
551  void insnUnparser(const Unparser::BasePtr&) /*final*/;
555  void configureInsnUnparser(const Unparser::BasePtr&) const /*final*/;
556 
560  void configureInsnPlainUnparser(const Unparser::BasePtr&) const /*final*/;
561 
570  std::string unparse(SgAsmInstruction*) const;
571  void unparse(std::ostream&, SgAsmInstruction*) const;
572  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
573  void unparse(std::ostream&, const DataBlock::Ptr&) const;
574  void unparse(std::ostream&, const Function::Ptr&) const;
575  void unparse(std::ostream&) const;
581  std::string unparsePlain(SgAsmInstruction*) const;
582 
585  //
586  // Partitioner CFG queries
587  //
590 public:
596  size_t nBytes() const /*final*/ { return aum_.size(); }
597 
605  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
606  return undiscoveredVertex_;
607  }
608  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
609  return undiscoveredVertex_;
610  }
623  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
624  return indeterminateVertex_;
625  }
626  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
627  return indeterminateVertex_;
628  }
640  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
641  return nonexistingVertex_;
642  }
643  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
644  return nonexistingVertex_;
645  }
654  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
655 
662  const AddressUsageMap& aum() const /*final*/ { return aum_; }
663 
665  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
666 
671  std::vector<AddressUser> users(rose_addr_t) const /*final*/;
672 
680  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
681 
710  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
711  const Function::Ptr &function = Function::Ptr()) const /*final*/;
712  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
713  const Function::Ptr &function = Function::Ptr()) const /*final*/;
750  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
751  const Function::Ptr &sourceFunction = Function::Ptr(),
752  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
753  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
754  const Function::Ptr &sourceFunction = Function::Ptr(),
755  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
760  //
763  // Partitioner instruction operations
764  //
767 public:
773  size_t nInstructions() const /*final*/;
774 
784  AddressUser instructionExists(rose_addr_t startVa) const /*final*/ {
785  return aum_.findInstruction(startVa);
786  }
788  return aum_.findInstruction(insn);
789  }
798  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
799 
808  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
809 
818  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
819 
829  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
830 
838  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
839 
852  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
853 
858  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
859 
860 
861 
864  //
865  // Partitioner basic block placeholder operations
866  //
869 public:
879  size_t nPlaceholders() const /*final*/;
880 
889  bool placeholderExists(rose_addr_t startVa) const /*final*/;
890 
901  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
902  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
903  return *found;
904  return cfg_.vertices().end();
905  }
906  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
907  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
908  return *found;
909  return cfg_.vertices().end();
910  }
929  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
930 
944  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
945  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
950  //
953  // Partitioner basic block operations
954  //
957 public:
971  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
983  void basicBlockDropSemantics() const /*final*/;
984 
993  size_t nBasicBlocks() const /*final*/;
994 
1002  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
1003 
1025  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
1026  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
1038  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
1039 
1050  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1051 
1061  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1062 
1069  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1070 
1080  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1081 
1087  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1088 
1113  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1114  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1115  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1129  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1130  SgAsmInstruction *insn) /*final*/;
1131 
1164  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1165  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1253  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1254  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1271  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
1272  Precision::Level precision = Precision::HIGH) const /*final*/;
1273 
1282  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1283 
1302  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1303 
1313  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;
1314 
1325  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1326 
1331  bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;
1332 
1373  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1374  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1385  void forgetStackDeltas() const /*final*/;
1386  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1398  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1399  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1452  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1453 
1454  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1463  void basicBlockMayReturnReset() const /*final*/;
1464 
1465 private:
1466  // Per-vertex data used during may-return analysis
1467  struct MayReturnVertexInfo {
1468  enum State {INIT, CALCULATING, FINISHED};
1469  State state; // current state of vertex
1470  bool processedCallees; // have we processed BBs this vertex calls?
1471  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1472  boost::logic::tribool result; // final result (eventually cached in BB)
1473  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1474  };
1475 
1476  // Is edge significant for analysis? See .C file for full documentation.
1477  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1478  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1479 
1480  // Determine (and cache in vertexInfo) whether any callees return.
1481  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1482  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1483 
1484  // Maximum may-return result from significant successors including phantom call-return edge.
1485  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1486  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1487 
1488  // The guts of the may-return analysis
1489  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1490  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1491 
1492 
1493 
1496  //
1497  // Partitioner data block operations
1498  //
1501 public:
1507  size_t nDataBlocks() const /*final*/;
1508 
1515  DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1516 
1525  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1526 
1538  DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;
1539 
1546  void detachDataBlock(const DataBlock::Ptr&) /*final*/;
1547 
1557  DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;
1558 
1571  DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;
1572 
1582  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1583 
1593  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1594 
1604  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1605 
1612  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1613 
1619  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1620 
1621 
1622 
1625  //
1626  // Partitioner function operations
1627  //
1630 public:
1636  size_t nFunctions() const /*final*/ { return functions_.size(); }
1637 
1656  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1657  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1658  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1666  std::vector<Function::Ptr> functions() const /*final*/;
1667 
1677  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1678 
1689  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1690 
1700  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1701 
1718  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1719  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1720  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1721  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1722  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1723  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1745  size_t attachFunction(const Function::Ptr&) /*final*/;
1746  size_t attachFunctions(const Functions&) /*final*/;
1762  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1763 
1780  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1781  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1797  void detachFunction(const Function::Ptr&) /*final*/;
1798 
1833  std::vector<Function::Ptr>
1834  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1835 
1836  std::vector<Function::Ptr>
1837  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1838 
1839  std::vector<Function::Ptr>
1840  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1841 
1842  std::vector<Function::Ptr>
1843  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1844 
1845  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1846  std::vector<Function::Ptr>
1847  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1848  std::vector<Function::Ptr> retval;
1849  for (const typename Container::value_type& bblock: bblocks) {
1850  for (const Function::Ptr &function: functionsOwningBasicBlock(bblock, false))
1851  insertUnique(retval, function, sortFunctionsByAddress);
1852  }
1853  return retval;
1854  }
1866  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1867 
1879  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1880 
1890  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1891 
1902  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1903 
1910  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1911 
1919  FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;
1920 
1940  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1941 
1945  void allFunctionStackDelta() const /*final*/;
1946 
1953  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1954 
1958  void allFunctionMayReturn() const /*final*/;
1959 
1986  const CallingConvention::Analysis&
1987  functionCallingConvention(const Function::Ptr&,
1988  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1989  const /*final*/;
1990 
2003  void
2004  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2005  const /*final*/;
2006 
2032  CallingConvention::Dictionary
2033  functionCallingConventionDefinitions(const Function::Ptr&,
2034  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2035  const /*final*/;
2036 
2049  void
2050  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
2051  CallingConvention::Definition::Ptr()) const /*final*/;
2052 
2061  void fixInterFunctionEdges() /*final*/;
2062  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2082  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2083 
2089  void allFunctionIsNoop() const /*final*/;
2090 
2098  void forgetFunctionIsNoop() const /*final*/;
2099  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2106  std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;
2107 
2108 
2109 
2112  //
2113  // Callbacks
2114  //
2117 public:
2135  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2136  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2147  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2148  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2151 public:
2159  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2160  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2187  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2188  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa, rose_addr_t &lastSearchedVa /*out*/) /*final*/;
2191 public:
2197  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2198  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2208  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2209 
2210 
2211 
2214  //
2215  // Partitioner miscellaneous
2216  //
2219 public:
2231  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2232  bool computeProperties=true) const /*final*/;
2233 
2247  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2248  bool showNeighbors=true) const /*final*/;
2249 
2255  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2256  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2262  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2263 
2269  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2270  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2278  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2279  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2287  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2288  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2294  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2295 
2299  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2300 
2304  static std::string functionName(const Function::Ptr&) /*final*/;
2305 
2310  void expandIndeterminateCalls();
2311 
2329  Progress::Ptr progress() const /*final*/;
2330  void progress(const Progress::Ptr&) /*final*/;
2337  void updateProgress(const std::string &phase, double completion) const;
2338 
2340  void showStatistics() const;
2341 
2342  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2343  void checkConsistency() const;
2344 
2351 
2355  Sawyer::Optional<rose_addr_t> elfGotVa() const;
2356 
2357 
2358 
2361  //
2362  // Settings
2363  //
2366 public:
2367 
2375  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2376  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2387  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2388  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2389  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2413  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2414  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2431  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2432  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2444  void addressName(rose_addr_t, const std::string&) /*final*/;
2445  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2446  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2454  const SourceLocations& sourceLocations() const /*final*/ { return sourceLocations_; }
2455  SourceLocations& sourceLocations() /*final*/ { return sourceLocations_; }
2456  void sourceLocations(const SourceLocations &locs) { sourceLocations_ = locs; }
2466  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2467  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2472  //
2475  // Instruction semantics
2476  //
2479 public:
2489  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2490  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2499  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2500 
2511  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2512  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2522  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2523 
2524 
2525 
2528  //
2529  // Python API support functions
2530  //
2533 #ifdef ROSE_ENABLE_PYTHON_API
2534  void pythonUnparse() const;
2535 #endif
2536 
2537 
2538 
2541  //
2542  // Partitioner internal utilities
2543  //
2546 private:
2547  void init(const Disassembler::BasePtr&, const MemoryMap::Ptr&);
2548  void init(const Partitioner&);
2549  void updateCfgProgress();
2550 
2551 private:
2552  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2553  // and destination CFGs are identical.
2554  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2555  ControlFlowGraph::ConstVertexIterator otherIter);
2556 
2557  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2558  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2559  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2560 
2561  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2562  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2563  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2564 
2565  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2566  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2567 
2568  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2569  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2570  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2571 
2572  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2573  // The call happens immediately after the CFG/AUM are updated.
2574  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2575 
2576  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2577  void rebuildVertexIndices();
2578 };
2579 
2580 } // namespace
2581 } // namespace
2582 } // namespace
2583 
2584 // Class versions must be at global scope
2585 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::Partitioner, 2);
2586 
2587 #endif
2588 #endif
Base classes for instruction semantics.
Definition: Dispatcher.h:18
Represents information about a thunk.
Definition: Partitioner.h:306
size_t size() const
Number of addresses represented by the map.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:301
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2160
Contiguous region of a file.
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2499
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:307
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2159
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2445
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2388
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2467
Represents the file header of an ELF binary container.
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:626
const SourceLocations & sourceLocations() const
Property: Source locations.
Definition: Partitioner.h:2454
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:489
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
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:2198
AddressUser instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:787
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:654
Provides and caches instructions.
STL namespace.
ControlFlowGraph::VertexIterator indeterminateVertex()
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:623
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:497
void sourceLocations(const SourceLocations &locs)
Property: Source locations.
Definition: Partitioner.h:2456
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1460
Main namespace for the ROSE library.
Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
Map address to name.
Definition: Partitioner.h:313
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2147
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:605
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2489
Name space for the entire library.
Definition: FeasiblePath.h:773
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:488
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2432
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:906
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:662
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2446
MemoryMapPtr Ptr
Reference counting pointer.
Definition: MemoryMap.h:115
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: HashMap.h:442
void settings(const BasePartitionerSettings &s)
Partitioner settings.
Definition: Partitioner.h:2376
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2431
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:308
ControlFlowGraph::VertexIterator nonexistingVertex()
Returns the special "non-existing" vertex.
Definition: Partitioner.h:640
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:476
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2389
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2148
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:972
Binary analysis.
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:586
void stackDeltaInterproceduralLimit(size_t n)
Property: max depth for inter-procedural stack delta analysis.
Definition: Partitioner.h:1399
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:498
bool checkingCallBranch
Check for situations where CALL is used as a branch.
A general, thread-safe way to report progress made on some task.
Definition: Progress.h:165
void autoAddCallReturnEdges(bool b)
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2413
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:971
bool basicBlockSemanticsAutoDrop
Conserve memory by dropping semantics for attached basic blocks.
ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:608
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:643
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:302
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2197
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2136
API and storage for attributes.
Definition: Attribute.h:208
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:510
Sawyer::SharedPointer< Base > BasePtr
Reference counted pointer for disassemblers.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:294
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2466
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:516
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:395
void enableSymbolicSemantics(bool b=true)
Use or not use symbolic semantics.
Definition: Partitioner.h:2387
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2414
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:300
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:303
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2490
Holds configuration information.
Definition: Config.h:281
SourceLocations & sourceLocations()
Property: Source locations.
Definition: Partitioner.h:2455