ROSE  0.10.7.0
BinaryConcolic.h
1 #ifndef ROSE_BinaryAnalysis_Concolic_H
2 #define ROSE_BinaryAnalysis_Concolic_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_CONCOLIC_TESTING
5 
6 // Which database implementation should be used
7 // Version 1 was implemented as part of ROSE in 2019 and supports only SQLite
8 // Version 2 is from Sawyer and supports SQLite and PostgreSQL
9 #ifndef ROSE_CONCOLIC_DB_VERSION
10 #define ROSE_CONCOLIC_DB_VERSION 2
11 #endif
12 
13 // ROSE headers
14 #include <Diagnostics.h>
15 #include <Partitioner2/BasicTypes.h>
16 #include <rose_isnan.h>
17 #include <rose_strtoull.h>
18 #include <RoseException.h>
19 #if ROSE_CONCOLIC_DB_VERSION == 1
20  #include <SqlDatabase.h>
21 #else
22  #include <Sawyer/Database.h>
23 #endif
24 
25 // Non-ROSE headers
26 #include <boost/filesystem.hpp>
27 
28 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
29 #include <boost/serialization/export.hpp>
30 #include <boost/serialization/access.hpp>
31 #include <boost/serialization/nvp.hpp>
32 #include <boost/serialization/base_object.hpp>
33 #include <boost/archive/text_iarchive.hpp>
34 #include <boost/archive/text_oarchive.hpp>
35 #include <boost/archive/xml_iarchive.hpp>
36 #include <boost/archive/xml_oarchive.hpp>
37 #endif /* ROSE_HAVE_BOOST_SERIALIZATION_LIB */
38 
39 #include <boost/numeric/conversion/cast.hpp>
40 #include <memory>
41 #include <Sawyer/BiMap.h>
42 #include <Sawyer/SharedObject.h>
43 #include <Sawyer/SharedPointer.h>
44 #include <Sawyer/Synchronization.h>
45 #include <stdexcept>
46 #include <string>
47 #include <vector>
48 
49 namespace Rose {
50 namespace BinaryAnalysis {
51 
74 namespace Concolic {
75 
77 // Flags and enums
79 
80 namespace Update {
81 enum Flag { NO, YES };
82 } // namespace
83 
85 // Exceptions, errors, etc.
87 
89 extern Sawyer::Message::Facility mlog;
90 
91 // Internal: called by Rose::Diagnostics::initialize
92 void initDiagnostics();
93 
95 class Exception: public Rose::Exception {
96 public:
97  explicit Exception(const std::string &mesg): Rose::Exception(mesg) {}
98  ~Exception() throw () {}
99 };
100 
102 // Forward references
104 
105 class Specimen;
106 typedef Sawyer::SharedPointer<Specimen> SpecimenPtr;
107 
108 class TestCase;
109 typedef Sawyer::SharedPointer<TestCase> TestCasePtr;
110 
111 class ConcreteExecutor;
112 typedef Sawyer::SharedPointer<ConcreteExecutor> ConcreteExecutorPtr;
113 
114 class LinuxExecutor;
115 typedef Sawyer::SharedPointer<LinuxExecutor> LinuxExecutorPtr;
116 
117 class ConcolicExecutor;
118 typedef Sawyer::SharedPointer<ConcolicExecutor> ConcolicExecutorPtr;
119 
120 class TestSuite;
121 typedef Sawyer::SharedPointer<TestSuite> TestSuitePtr;
122 
123 class Database;
124 typedef Sawyer::SharedPointer<Database> DatabasePtr;
125 
126 class ExecutionManager;
127 typedef Sawyer::SharedPointer<ExecutionManager> ExecutionManagerPtr;
128 
129 class LinuxExitStatus;
130 typedef Sawyer::SharedPointer<LinuxExitStatus> LinuxExitStatusPtr;
131 
133 // Specimens
135 
140 class Specimen: public Sawyer::SharedObject, public Sawyer::SharedFromThis<Specimen> {
141 public:
144 
146  typedef std::vector<uint8_t> BinaryData;
147 
148 private:
149  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
150  std::string name_; // name of specimen (e.g., for debugging)
151  BinaryData content_; // content of the binary executable file
152  mutable bool read_only_; // safe guards from writing content after it has been shared;
153  bool empty_; // indicates if this object is empty
154 
155 private:
156  friend class boost::serialization::access;
157 
158  template<class S>
159  void serialize(S &s, const unsigned /*version*/) {
160  s & BOOST_SERIALIZATION_NVP(name_);
161  s & BOOST_SERIALIZATION_NVP(content_);
162  s & BOOST_SERIALIZATION_NVP(empty_);
163  }
164 
165 protected:
166  Specimen()
167  : read_only_(false), empty_(false)
168  {}
169 
170 public:
173  static Ptr instance(const boost::filesystem::path &executableName);
174  static Ptr instance();
183  void open(const boost::filesystem::path &executableName);
184 
191  void close();
192 
198  bool isEmpty() const;
199 
208  std::string name() const; // value return is intentional for thread safety
209  void name(const std::string&);
217  std::string printableName(const DatabasePtr &db = DatabasePtr());
218 
225  const std::vector<uint8_t>& content() const;
226 
227  // FIXME[Robb Matzke 2019-08-12]: content is read-only, created by constructor. Therefore this member shouldn't be defined,
228  // or at least should be private.
231  void content(std::vector<uint8_t> binary_data);
232 };
233 
235 // Test cases
237 
239 typedef std::pair<std::string /*name*/, std::string /*value*/> EnvValue;
240 
244 class TestCase: public Sawyer::SharedObject, public Sawyer::SharedFromThis<TestCase> {
245 public:
248 
249 private:
250  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
251  std::string name_; // name for debugging
252  std::string executor_; // name of execution environment
253  Specimen::Ptr specimen_; // the thing to run
254  std::vector<std::string> args_; // command line arguments
255  std::vector<EnvValue> env_; // environment variables
256  Sawyer::Optional<size_t> concolicResult_; // non-empty if concolically tested
257  Sawyer::Optional<double> concreteRank_; // rank after testing
258 
259 protected:
260  TestCase() {}
261 
262 public:
264  static Ptr instance() {
265  return Ptr(new TestCase);
266  }
267 
269  static Ptr instance(const Specimen::Ptr &specimen);
270 
279  std::string name() const; // value return is intentional for thread safety
280  void name(const std::string&);
288  std::string printableName(const DatabasePtr &db = DatabasePtr());
289 
297  Specimen::Ptr specimen() const;
298  void specimen(const Specimen::Ptr&);
306  std::vector<std::string> args() const;
307  void args(std::vector<std::string> arguments);
312  std::vector<EnvValue> env() const;
313  void env(std::vector<EnvValue> envvars);
321  Sawyer::Optional<size_t> concolicResult() const {
322  return concolicResult_;
323  }
324  void concolicResult(const Sawyer::Optional<size_t> &x) {
325  concolicResult_ = x;
326  }
330  bool hasConcolicTest() const;
331 
335  Sawyer::Optional<double> concreteRank() const;
336  void concreteRank(Sawyer::Optional<double> val);
340  bool hasConcreteTest() const;
341 
345  const std::string& executor() const {
346  return executor_;
347  }
348  void executor(const std::string &x) {
349  executor_ = x;
350  }
353  // We'll need to add additional information about how to run the specimen:
354  // 3. Auxilliary vector (auxv)
355  // 4. System calls that provide input (e.g., virtual file system, network, etc.)
356  // Some of this information might need to be separated into subclasses that support different architectures since the
357  // info for testing a Linux ELF executable is different from a Windows PE executable, which is different from how one
358  // would run firmware.
359 };
360 
361 
363 // Concrete executors and their results
365 
366 extern const char* const tagConcreteExecutorResult;
367 extern const char* const tagLinuxExecutorResult;
368 
379 class ConcreteExecutor: public Sawyer::SharedObject {
380 public:
383 
394  class Result {
395  private:
396  double rank_;
397 
398  public:
399  explicit Result(double rank): rank_(rank) {
400  ASSERT_forbid(rose_isnan(rank));
401  }
402 
403  Result() {} // required for serialization
404 
405  virtual ~Result() {}
406 
407  double rank() const { return rank_; }
408 
409  private:
410  friend class boost::serialization::access;
411 
412  template<class S>
413  void serialize(S &s, const unsigned /*version*/) {
414  s & BOOST_SERIALIZATION_NVP(rank_);
415  }
416  };
417 
418 protected:
419  // Allocating constructors should be implemente by the non-abstract subclasses.
420  ConcreteExecutor() {}
421 
422 public:
427  virtual
428  Result*
429  execute(const TestCase::Ptr&) = 0;
430 
453  void executionMonitor(const boost::filesystem::path& executorName)
454  {
455  execmon = executorName;
456  }
457 
458  boost::filesystem::path executionMonitor() const
459  {
460  return execmon;
461  }
464 private:
465  boost::filesystem::path execmon; // the execution monitor
466 };
467 
469 class LinuxExecutor: public ConcreteExecutor {
470 public:
473 
475  typedef Sawyer::Optional<unsigned long> Persona;
476 
478  class Result: public ConcreteExecutor::Result {
479  protected:
480  int exitStatus_;
481  std::string exitKind_;
482  std::string capturedOut_;
483  std::string capturedErr_;
485  private:
486  friend class boost::serialization::access;
487 
488  template<class S>
489  void serialize(S &s, const unsigned /*version*/) {
490  // was: s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(ConcreteExecutor::Result);
491  // nvp of a base class in a different namespace seems to produce
492  // invalid results.
493  s & boost::serialization::make_nvp( tagConcreteExecutorResult,
494  boost::serialization::base_object<ConcreteExecutor::Result>(*this)
495  );
496  s & BOOST_SERIALIZATION_NVP(exitStatus_);
497  s & BOOST_SERIALIZATION_NVP(exitKind_);
498  s & BOOST_SERIALIZATION_NVP(capturedOut_);
499  s & BOOST_SERIALIZATION_NVP(capturedErr_);
500  }
501 
502  public:
503  Result(double rank, int exitStatus);
504 
505  Result() {} // required for boost serialization
506 
514  int exitStatus() const { return exitStatus_; }
515  void exitStatus(int x);
521  std::string out() const { return capturedOut_; }
522  void out(const std::string& output) { capturedOut_ = output; }
523 
524  std::string err() const { return capturedErr_; }
525  void err(const std::string& output) { capturedErr_ = output; }
531  std::string exitKind() const { return exitKind_; }
532  /* @} */
533  };
534 
535 protected:
536  bool useAddressRandomization_; // enable/disable address space randomization in the OS
537 
538 protected:
539  LinuxExecutor()
540  : useAddressRandomization_(false) {}
541 
542 public:
544  static Ptr instance() {
545  return Ptr(new LinuxExecutor);
546  }
547 
554  bool useAddressRandomization() const { return useAddressRandomization_; }
555  void useAddressRandomization(bool b) { useAddressRandomization_ = b; }
558  virtual
559  Result* execute(const TestCase::Ptr&) ROSE_OVERRIDE;
560 };
561 
563 // Concolic (concrete + symbolic) executors
565 
566 } // namespace
567 } // namespace
568 } // namespace
569 
570 #include <Concolic/ConcolicExecutor.h>
571 
572 namespace Rose {
573 namespace BinaryAnalysis {
574 namespace Concolic {
575 
577 // Test suites
579 
592 class TestSuite: public Sawyer::SharedObject, public Sawyer::SharedFromThis<TestSuite> {
593 public:
596 
597 private:
598  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
599  std::string name_; // unique and non-empty within a database
600 
601 protected:
602  TestSuite() {}
603 
604 public:
606  static Ptr instance(const std::string &name = "");
607 
616  std::string name() const; // value return is intentional for thread safety
617  void name(const std::string&);
625  std::string printableName(const DatabasePtr &db = DatabasePtr());
626 };
627 
629 // Databases
631 
633 template <class Tag>
634 class ObjectId: public Sawyer::Optional<size_t> {
635 public:
636  typedef size_t Value;
637  typedef Sawyer::Optional<Value> Super;
638  typedef Tag Object;
640  ObjectId() {}
641 
642  explicit
643  ObjectId(const Value& v)
644  : Super(v) {}
645 
646  ObjectId(const ObjectId& rhs)
647  : Super(rhs) {}
648 
649  explicit ObjectId(const Sawyer::Optional<size_t> &id)
650  : Super(id) {}
651 
657  explicit ObjectId(const std::string &s) {
658  char *rest = NULL;
659  uint64_t id = rose_strtoull(s.c_str(), &rest, 0);
660  while (*rest && isspace(*rest)) ++rest;
661  if (*rest)
662  throw Exception("invalid syntax for object ID: \"" + StringUtility::cEscape(s) + "\"");
663  try {
664  *this = boost::numeric_cast<Value>(id);
665  } catch (const boost::bad_numeric_cast&) {
666  throw Exception("parsed object ID out of range: \"" + StringUtility::cEscape(s) + "\"");
667  }
668  }
669 
671  ObjectId<Tag>& operator=(const ObjectId<Tag>& lhs) {
672  this->Super::operator=(lhs);
673  return *this;
674  }
675 
677  ObjectId<Tag>& operator=(const Value& v) {
678  this->Super::operator=(v);
679  return *this;
680  }
681 
683  template<class _Tag>
684  friend
685  bool operator<(const ObjectId<_Tag>& lhs, const ObjectId<_Tag>& rhs);
686 };
687 
689 template<class Tag>
690 inline
691 bool operator<(const ObjectId<Tag>& lhs, const ObjectId<Tag>& rhs)
692 {
693  if (!rhs) return false;
694  if (!lhs) return true;
695 
696  return lhs.get() < rhs.get();
697 }
698 
699 typedef ObjectId<TestSuite> TestSuiteId;
700 typedef ObjectId<Specimen> SpecimenId;
701 typedef ObjectId<TestCase> TestCaseId;
715 class Database: public Sawyer::SharedObject, public Sawyer::SharedFromThis<Database>, boost::noncopyable {
716 public:
719 
720  typedef ::Rose::BinaryAnalysis::Concolic::TestSuiteId TestSuiteId;
721  typedef ::Rose::BinaryAnalysis::Concolic::SpecimenId SpecimenId;
722  typedef ::Rose::BinaryAnalysis::Concolic::TestCaseId TestCaseId;
723 
724 private:
725 #if ROSE_CONCOLIC_DB_VERSION == 1
726  SqlDatabase::ConnectionPtr dbconn_; // connection to database
727 #else
728  Sawyer::Database::Connection connection_;
729 #endif
730 
731  // Memoization of ID to object mappings
735 
736  TestSuiteId testSuiteId_; // database scope is restricted to this single test suite
737 
738 protected:
739  Database() {}
740 
741 public:
748  static Ptr instance(const std::string &url);
749 
751 #if ROSE_CONCOLIC_DB_VERSION == 1
752  SqlDatabase::ConnectionPtr connection() {
753  return dbconn_;
754  }
755 #else
756  Sawyer::Database::Connection connection() {
757  return connection_;
758  }
759 #endif
760 
771  static Ptr create(const std::string &url);
772  static Ptr create(const std::string &url, const std::string &testSuiteName);
774  //------------------------------------------------------------------------------------------------------------------------
775  // Test suites
776  //------------------------------------------------------------------------------------------------------------------------
777 
782  std::vector<TestSuiteId> testSuites();
783 
791  TestSuite::Ptr testSuite();
792  TestSuiteId testSuite(const TestSuite::Ptr&);
795  //------------------------------------------------------------------------------------------------------------------------
796  // Specimens
797  //------------------------------------------------------------------------------------------------------------------------
798 
803  std::vector<SpecimenId> specimens();
804 
805  //------------------------------------------------------------------------------------------------------------------------
806  // Test cases
807  //------------------------------------------------------------------------------------------------------------------------
808 
813  std::vector<TestCaseId> testCases();
814 
815  //------------------------------------------------------------------------------------------------------------------------
816  // Overloaded methods for all objects.
817  //------------------------------------------------------------------------------------------------------------------------
818 
825  TestSuite::Ptr object(TestSuiteId, Update::Flag update = Update::YES);
826  TestCase::Ptr object(TestCaseId, Update::Flag update = Update::YES);
827  Specimen::Ptr object(SpecimenId, Update::Flag update = Update::YES);
830 #if ROSE_CONCOLIC_DB_VERSION == 1
831 
835  Specimen::Ptr object_ns(SqlDatabase::TransactionPtr tx, SpecimenId id);
836 #endif
837 
846  TestSuiteId id(const TestSuite::Ptr&, Update::Flag update = Update::YES);
847  TestCaseId id(const TestCase::Ptr&, Update::Flag update = Update::YES);
848  SpecimenId id(const Specimen::Ptr&, Update::Flag update = Update::YES);
855  template<class ObjectPointer>
856  void save(const ObjectPointer &obj) {
857  id(obj);
858  }
859 
860 #if ROSE_CONCOLIC_DB_VERSION == 1
861 
867  TestSuiteId id_ns(SqlDatabase::TransactionPtr, const TestSuite::Ptr&, Update::Flag update = Update::YES);
868  TestCaseId id_ns(SqlDatabase::TransactionPtr, const TestCase::Ptr&, Update::Flag update = Update::YES);
869  SpecimenId id_ns(SqlDatabase::TransactionPtr, const Specimen::Ptr&, Update::Flag update = Update::YES);
870 #endif
871 
878  TestSuite::Ptr findTestSuite(const std::string &nameOrId);
879 
884  std::vector<SpecimenId> findSpecimensByName(const std::string &name);
885 
886  //------------------------------------------------------------------------------------------------------------------------
887  // Cached info about disassembly. This is large data. Each specimen has zero or one associated RBA data blob.
888  //------------------------------------------------------------------------------------------------------------------------
889 
896  bool rbaExists(SpecimenId);
897 
906  void saveRbaFile(const boost::filesystem::path&, SpecimenId);
907 
916  void extractRbaFile(const boost::filesystem::path&, SpecimenId);
917 
923  void eraseRba(SpecimenId);
924 
933  void assocTestCaseWithTestSuite(TestCaseId, TestSuiteId);
934 
939  std::vector<TestCaseId> needConcreteTesting(size_t n = UNLIMITED);
940 
945  std::vector<TestCaseId> needConcolicTesting(size_t n = UNLIMITED);
946 
954  void insertConcreteResults(const TestCase::Ptr &testCase, const ConcreteExecutor::Result& details);
955 
960  bool hasUntested();
961 
962 private:
963 #if ROSE_CONCOLIC_DB_VERSION == 2
964  static Ptr create(const std::string &url, const Sawyer::Optional<std::string> &testSuiteName);
965 #endif
966 };
967 
968 
970 // Execution manager
972 
977 class ExecutionManager: boost::noncopyable, public Sawyer::SharedObject {
978 public:
981 
982 private:
983  Database::Ptr database_;
984 
985 protected:
986  // Subclasses should implement allocating constructors
987  explicit ExecutionManager(const Database::Ptr &db)
988  : database_(db) {
989  ASSERT_not_null(db);
990  }
991 
992 public:
993  virtual ~ExecutionManager() {}
994 
998  Database::Ptr database() const;
999 
1006  virtual std::vector<Database::TestCaseId> pendingConcreteResults(size_t n = UNLIMITED);
1007  Database::TestCaseId pendingConcreteResult() /*final*/;
1015  virtual void insertConcreteResults(const TestCase::Ptr&, const ConcreteExecutor::Result &details);
1016 
1023  virtual std::vector<Database::TestCaseId> pendingConcolicResults(size_t n = UNLIMITED);
1024  Database::TestCaseId pendingConcolicResult() /*final*/;
1032  virtual void insertConcolicResults(const TestCase::Ptr &original, const std::vector<TestCase::Ptr> &newCases);
1033 
1037  virtual bool isFinished() const;
1038 
1043  virtual void run() = 0;
1044 };
1045 
1047 // Example execution manager
1049 
1054 class LinuxExitStatus: public ExecutionManager {
1055 public:
1058 
1059 protected:
1060  explicit LinuxExitStatus(const Database::Ptr &db): ExecutionManager(db) {}
1061 
1062 public:
1067  static Ptr create(const std::string databaseUrl, const boost::filesystem::path &executableName,
1068  const std::vector<std::string> &arguments);
1069 
1075  static Ptr instance(const std::string& databaseUri, const std::string &testSuiteName = "");
1076 
1077  virtual void run() ROSE_OVERRIDE;
1078 };
1079 
1082 void writeDBSchema(std::ostream& os);
1083 
1086 void writeSqlStmts(std::ostream& os);
1087 
1088 
1089 } // namespace
1090 } // namespace
1091 } // namespace
1092 
1093 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
1094 //~ BOOST_CLASS_EXPORT_GUID(LinuxExecutor::Result, "LinuxExecutor::Result")
1095 
1096 //~ BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::Concolic::ConcreteExecutor::Result)
1097 //~ BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::Concolic::LinuxExecutor::Result)
1098 
1099 BOOST_CLASS_EXPORT_KEY2( Rose::BinaryAnalysis::Concolic::ConcreteExecutor::Result,
1100  Rose::BinaryAnalysis::Concolic::tagConcreteExecutorResult
1101  )
1102 BOOST_CLASS_EXPORT_KEY2( Rose::BinaryAnalysis::Concolic::LinuxExecutor::Result,
1103  Rose::BinaryAnalysis::Concolic::tagLinuxExecutorResult
1104  )
1105 #endif /* ROSE_HAVE_BOOST_SERIALIZATION_LIB */
1106 
1107 #endif
1108 #endif
Sawyer::SharedPointer< Node > Ptr
Shared-ownership pointer to an expression Node.
const size_t UNLIMITED(-1)
Effictively unlimited size.
Allow parallel edges, so each edge has a unit count.
Definition: BasicTypes.h:39
Collection of streams.
Definition: Message.h:1600
boost::shared_ptr< Transaction > TransactionPtr
Shared-ownership pointer to a transaction.
Definition: SqlDatabase.h:147
Enum type for allowing parallel edges.
Definition: BasicTypes.h:38
STL namespace.
Main namespace for the ROSE library.
ROSE_UTIL_API std::string cEscape(const std::string &, char context= '"')
Escapes characters that are special to C/C++.
One-to-one mapping between source and target values.
Definition: BiMap.h:26
Reference-counting intrusive smart pointer.
Definition: SharedPointer.h:68
Flag
Flag to pass as type stringification style.
Creates SharedPointer from this.
boost::shared_ptr< Connection > ConnectionPtr
Shared-ownership pointer to a database connection.
Definition: SqlDatabase.h:137
Base class for reference counted objects.
Definition: SharedObject.h:64
Base class for all ROSE exceptions.
Definition: RoseException.h:9