ROSE  0.9.11.125
BinaryConcolic.h
1 #ifndef ROSE_BinaryAnalysis_Concolic_H
2 #define ROSE_BinaryAnalysis_Concolic_H
3 
4 // ROSE headers
5 #include <Diagnostics.h>
6 #include <Partitioner2/BasicTypes.h>
7 #include <rose_isnan.h>
8 #include <rose_strtoull.h>
9 #include <RoseException.h>
10 #include <SqlDatabase.h>
11 
12 // Non-ROSE headers
13 #include <boost/filesystem.hpp>
14 
15 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
16 #include <boost/serialization/export.hpp>
17 #include <boost/serialization/access.hpp>
18 #include <boost/serialization/nvp.hpp>
19 #include <boost/serialization/base_object.hpp>
20 #include <boost/archive/text_iarchive.hpp>
21 #include <boost/archive/text_oarchive.hpp>
22 #include <boost/archive/xml_iarchive.hpp>
23 #include <boost/archive/xml_oarchive.hpp>
24 #endif /* ROSE_HAVE_BOOST_SERIALIZATION_LIB */
25 
26 #include <boost/numeric/conversion/cast.hpp>
27 #include <memory>
28 #include <Sawyer/BiMap.h>
29 #include <Sawyer/SharedObject.h>
30 #include <Sawyer/SharedPointer.h>
31 #include <Sawyer/Synchronization.h>
32 #include <stdexcept>
33 #include <string>
34 #include <vector>
35 
36 namespace Rose {
37 namespace BinaryAnalysis {
38 
61 namespace Concolic {
62 
64 // Flags and enums
66 
67 namespace Update {
68 enum Flag { NO, YES };
69 } // namespace
70 
72 // Exceptions, errors, etc.
74 
75 extern Sawyer::Message::Facility mlog;
76 
78 class Exception: public Rose::Exception {
79 public:
80  explicit Exception(const std::string &mesg): Rose::Exception(mesg) {}
81  ~Exception() throw () {}
82 };
83 
85 // Forward references
87 
88 class Specimen;
90 
91 class TestCase;
93 
94 class ConcreteExecutor;
96 
97 class LinuxExecutor;
99 
100 class ConcolicExecutor;
102 
103 class TestSuite;
105 
106 class Database;
108 
109 class ExecutionManager;
111 
112 class LinuxExitStatus;
114 
116 // Specimens
118 
123 class Specimen: public Sawyer::SharedObject, public Sawyer::SharedFromThis<Specimen> {
124 public:
127 
128 private:
129  typedef std::vector<uint8_t> BinaryData;
130 
131  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
132  std::string name_; // name of specimen (e.g., for debugging)
133  BinaryData content_; // content of the binary executable file
134  mutable bool read_only_; // safe guards from writing content after it has been shared;
135  bool empty_; // indicates if this object is empty
136 
137 private:
138  friend class boost::serialization::access;
139 
140  template<class S>
141  void serialize(S &s, const unsigned /*version*/) {
142  s & BOOST_SERIALIZATION_NVP(name_);
143  s & BOOST_SERIALIZATION_NVP(content_);
144  s & BOOST_SERIALIZATION_NVP(empty_);
145  }
146 
147 protected:
148  Specimen()
149  : mutex_(), name_(), content_(), read_only_(false), empty_(false)
150  {}
151 
152 public:
155  static Ptr instance(const boost::filesystem::path &executableName);
156  static Ptr instance();
165  void open(const boost::filesystem::path &executableName);
166 
173  void close();
174 
180  bool isEmpty() const;
181 
190  std::string name() const; // value return is intentional for thread safety
191  void name(const std::string&);
199  std::string printableName(const DatabasePtr &db = DatabasePtr());
200 
207  const std::vector<uint8_t>& content() const;
208 
209  // FIXME[Robb Matzke 2019-08-12]: content is read-only, created by constructor. Therefore this member shouldn't be defined,
210  // or at least should be private.
211  void content(std::vector<uint8_t> binary_data);
212 };
213 
215 // Test cases
217 
219 typedef std::pair<std::string /*name*/, std::string /*value*/> EnvValue;
220 
224 class TestCase: public Sawyer::SharedObject, public Sawyer::SharedFromThis<TestCase> {
225 public:
228 
229 private:
230  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
231  std::string name_; // name for debugging
232  std::string executor_; // name of execution environment
233  Specimen::Ptr specimen_; // the thing to run
234 
235  std::vector<std::string> args_; // command line arguments
236  std::vector<EnvValue> env_; // environment variables
237  Sawyer::Optional<double> concrete_rank_; // rank after testing
238  bool concolically_tested; // true if test was run concolically
239 
240 protected:
241  TestCase() {}
242 
243 public:
245  static Ptr instance() {
246  return Ptr(new TestCase);
247  }
248 
250  static Ptr instance(const Specimen::Ptr &specimen);
251 
260  std::string name() const; // value return is intentional for thread safety
261  void name(const std::string&);
269  std::string printableName(const DatabasePtr &db = DatabasePtr());
270 
278  Specimen::Ptr specimen() const;
279  void specimen(const Specimen::Ptr&);
284  std::vector<std::string> args() const;
285  void args(std::vector<std::string> arguments);
290  std::vector<EnvValue> env() const;
291  void env(std::vector<EnvValue> envvars);
295  bool hasConcolicTest() const;
296 
298  void concolicTest(bool);
299 
301  bool hasConcreteTest() const;
302 
305 
308 
309  // We'll need to add additional information about how to run the specimen:
310  // 1. Command-line arguments (argc, argv)
311  // 2. Environment varaibles (envp)
312  // 3. Auxilliary vector (auxv)
313  // 4. System calls that provide input (e.g., virtual file system, network, etc.)
314  // Some of this information might need to be separated into subclasses that support different architectures since the
315  // info for testing a Linux ELF executable is different from a Windows PE executable, which is different from how one
316  // would run firmware.
317 };
318 
319 
321 // Concrete executors and their results
323 
324 static const char* const tagConcreteExecutorResult = "ConcreteExecutorResult";
325 static const char* const tagLinuxExecutorResult = "LinuxExecutorResult";
326 
338 public:
341 
352  class Result {
353  private:
354  double rank_;
355 
356  public:
357  explicit Result(double rank): rank_(rank) {
358  ASSERT_forbid(rose_isnan(rank));
359  }
360 
361  Result() {} // required for serialization
362 
363  virtual ~Result() {}
364 
365  double rank() const { return rank_; }
366 
367  private:
368  friend class boost::serialization::access;
369 
370  template<class S>
371  void serialize(S &s, const unsigned /*version*/) {
372  s & BOOST_SERIALIZATION_NVP(rank_);
373  }
374  };
375 
376 protected:
377  // Allocating constructors should be implemente by the non-abstract subclasses.
378  ConcreteExecutor() {}
379 
380 public:
385  virtual
386  Result*
387  execute(const TestCase::Ptr&) = 0;
388 
411  void executionMonitor(const boost::filesystem::path& executorName)
412  {
413  execmon = executorName;
414  }
415 
416  boost::filesystem::path executionMonitor() const
417  {
418  return execmon;
419  }
422 private:
423  boost::filesystem::path execmon; // the execution monitor
424 };
425 
428 public:
431 
434 
437  protected:
439  std::string exitKind_;
440  std::string capturedOut_;
441  std::string capturedErr_;
443  private:
444  friend class boost::serialization::access;
445 
446  template<class S>
447  void serialize(S &s, const unsigned /*version*/) {
448  // was: s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(ConcreteExecutor::Result);
449  // nvp of a base class in a different namespace seems to produce
450  // invalid results.
451  s & boost::serialization::make_nvp( tagConcreteExecutorResult,
452  boost::serialization::base_object<ConcreteExecutor::Result>(*this)
453  );
454  s & BOOST_SERIALIZATION_NVP(exitStatus_);
455  s & BOOST_SERIALIZATION_NVP(exitKind_);
456  s & BOOST_SERIALIZATION_NVP(capturedOut_);
457  s & BOOST_SERIALIZATION_NVP(capturedErr_);
458  }
459 
460  public:
461  Result(double rank, int exitStatus);
462 
463  Result() {} // required for boost serialization
464 
472  int exitStatus() const { return exitStatus_; }
473  void exitStatus(int x);
479  std::string out() const { return capturedOut_; }
480  void out(const std::string& output) { capturedOut_ = output; }
481 
482  std::string err() const { return capturedErr_; }
483  void err(const std::string& output) { capturedErr_ = output; }
489  std::string exitKind() const { return exitKind_; }
490  /* @} */
491  };
492 
493 protected:
494  bool useAddressRandomization_; // enable/disable address space randomization in the OS
495 
496 protected:
497  LinuxExecutor()
498  : useAddressRandomization_(false) {}
499 
500 public:
502  static Ptr instance() {
503  return Ptr(new LinuxExecutor);
504  }
505 
512  bool useAddressRandomization() const { return useAddressRandomization_; }
513  void useAddressRandomization(bool b) { useAddressRandomization_ = b; }
516  virtual
518  execute(const TestCase::Ptr&) ROSE_OVERRIDE;
519 };
520 
522 // Concolic (concrete + symbolic) executors
524 
525 } // namespace
526 } // namespace
527 } // namespace
528 
529 #include <Concolic/ConcolicExecutor.h>
530 
531 namespace Rose {
532 namespace BinaryAnalysis {
533 namespace Concolic {
534 
536 // Test suites
538 
551 class TestSuite: public Sawyer::SharedObject, public Sawyer::SharedFromThis<TestSuite> {
552 public:
555 
556 private:
557  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
558  std::string name_; // unique and non-empty within a database
559 
560 protected:
561  TestSuite() {}
562 
563 public:
565  static Ptr instance(const std::string &name = "");
566 
575  std::string name() const; // value return is intentional for thread safety
576  void name(const std::string&);
584  std::string printableName(const DatabasePtr &db = DatabasePtr());
585 };
586 
588 // Databases
590 
591 // FIXME[Robb Matzke 2019-07-03]: All public classes and all their public members should be documented with doxygen comments.
592 template <class Tag>
593 class ObjectId: public Sawyer::Optional<int> {
594 public:
596  typedef int Value; // FIXME[Robb Matzke 2019-07-03]: negative values are allowed?!
597  typedef Tag Object;
599  ObjectId() {}
600 
601  explicit
602  ObjectId(const Value& v)
603  : Super(v) {}
604 
605  ObjectId(const ObjectId& rhs)
606  : Super(rhs) {}
607 
613  explicit ObjectId(const std::string &s) {
614  char *rest = NULL;
615  uint64_t id = rose_strtoull(s.c_str(), &rest, 0);
616  while (*rest && isspace(*rest)) ++rest;
617  if (*rest)
618  throw Exception("invalid syntax for object ID: \"" + StringUtility::cEscape(s) + "\"");
619  try {
620  *this = boost::numeric_cast<Value>(id);
621  } catch (const boost::bad_numeric_cast&) {
622  throw Exception("parsed object ID out of range: \"" + StringUtility::cEscape(s) + "\"");
623  }
624  }
625 
626  ObjectId<Tag>& operator=(const ObjectId<Tag>& lhs) {
627  this->Super::operator=(lhs);
628  return *this;
629  }
630 
631  ObjectId<Tag>& operator=(const Value& v) {
632  this->Super::operator=(v);
633  return *this;
634  }
635 
636  template<class _Tag>
637  friend
638  bool operator<(const ObjectId<_Tag>& lhs, const ObjectId<_Tag>& rhs);
639 };
640 
641 template<class Tag>
642 inline
643 bool operator<(const ObjectId<Tag>& lhs, const ObjectId<Tag>& rhs)
644 {
645  static const int noid = -1;
646 
647  const int lhsid = lhs.orElse(noid);
648  const int rhsid = rhs.orElse(noid);
649 
650  return lhsid < rhsid;
651 }
652 
669 class Database: public Sawyer::SharedObject, boost::noncopyable {
670 public:
673 
674  typedef ::Rose::BinaryAnalysis::Concolic::TestSuiteId TestSuiteId;
675  typedef ::Rose::BinaryAnalysis::Concolic::SpecimenId SpecimenId;
676  typedef ::Rose::BinaryAnalysis::Concolic::TestCaseId TestCaseId;
677 
678 private:
679  SqlDatabase::ConnectionPtr dbconn_; // holds connection to database
680 
681  // The lock protects the following concurrent accesses
682  // - memoized data
683  // - testSuiteId_
684  //~ mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
685 
686  // Memoization of ID to object mappings
690 
691  TestSuiteId testSuiteId_; // database scope is restricted to this single test suite
692 
693 protected:
694  Database()
695  : dbconn_(), specimens_(), testCases_(), testSuites_(), testSuiteId_()
696  {}
697 
698 public:
702  static Ptr instance(const std::string &url);
703 
714  static Ptr create(const std::string &url);
715  static Ptr create(const std::string &url, const std::string &testSuiteName);
717  //------------------------------------------------------------------------------------------------------------------------
718  // Test suites
719  //------------------------------------------------------------------------------------------------------------------------
720 
725  std::vector<TestSuiteId> testSuites();
726 
734  TestSuite::Ptr testSuite();
735  TestSuiteId testSuite(const TestSuite::Ptr&);
738  //------------------------------------------------------------------------------------------------------------------------
739  // Specimens
740  //------------------------------------------------------------------------------------------------------------------------
741 
746  std::vector<SpecimenId> specimens();
747 
748  //------------------------------------------------------------------------------------------------------------------------
749  // Test cases
750  //------------------------------------------------------------------------------------------------------------------------
751 
756  std::vector<TestCaseId> testCases();
757 
758  //------------------------------------------------------------------------------------------------------------------------
759  // Overloaded methods for all objects.
760  //------------------------------------------------------------------------------------------------------------------------
761 
768  TestSuite::Ptr object(TestSuiteId, Update::Flag update = Update::YES);
769  TestCase::Ptr object(TestCaseId, Update::Flag update = Update::YES);
770  Specimen::Ptr object(SpecimenId, Update::Flag update = Update::YES);
777  Specimen::Ptr object_ns(SqlDatabase::TransactionPtr tx, SpecimenId id);
778 
787  TestSuiteId id(const TestSuite::Ptr&, Update::Flag update = Update::YES);
788  TestCaseId id(const TestCase::Ptr&, Update::Flag update = Update::YES);
789  SpecimenId id(const Specimen::Ptr&, Update::Flag update = Update::YES);
798  TestSuiteId id_ns(SqlDatabase::TransactionPtr, const TestSuite::Ptr&, Update::Flag update = Update::YES);
799  TestCaseId id_ns(SqlDatabase::TransactionPtr, const TestCase::Ptr&, Update::Flag update = Update::YES);
800  SpecimenId id_ns(SqlDatabase::TransactionPtr, const Specimen::Ptr&, Update::Flag update = Update::YES);
801 
808  TestSuite::Ptr findTestSuite(const std::string &nameOrId);
809 
814  std::vector<SpecimenId> findSpecimensByName(const std::string &name);
815 
816  //------------------------------------------------------------------------------------------------------------------------
817  // Cached info about disassembly. This is large data. Each specimen has zero or one associated RBA data blob.
818  //------------------------------------------------------------------------------------------------------------------------
819 
826  bool rbaExists(SpecimenId);
827 
836  void saveRbaFile(const boost::filesystem::path&, SpecimenId);
837 
845  void extractRbaFile(const boost::filesystem::path&, SpecimenId);
846 
852  void eraseRba(SpecimenId);
853 
858  void assocTestCaseWithTestSuite(TestCaseId testcase, TestSuiteId testsuite);
859 
864  std::vector<Database::TestCaseId> needConcreteTesting(size_t);
865 
870  std::vector<Database::TestCaseId> needConcolicTesting(size_t);
871 
876  void insertConcreteResults(const TestCase::Ptr &testCase, const ConcreteExecutor::Result& details);
877 
882  bool hasUntested() const;
883 };
884 
885 
887 // Execution manager
889 
894 class ExecutionManager: boost::noncopyable, public Sawyer::SharedObject {
895 public:
898 
899 private:
900  Database::Ptr database_;
901 
902 protected:
903  // Subclasses should implement allocating constructors
904  explicit ExecutionManager(const Database::Ptr &db)
905  : database_(db) {
906  ASSERT_not_null(db);
907  }
908 
909 public:
910  virtual ~ExecutionManager() {}
911 
915  Database::Ptr database() const;
916 
923  virtual std::vector<Database::TestCaseId> pendingConcreteResults(size_t n = (size_t)(-1));
924  Database::TestCaseId pendingConcreteResult() /*final*/;
932  virtual void insertConcreteResults(const TestCase::Ptr&, const ConcreteExecutor::Result &details);
933 
940  virtual std::vector<Database::TestCaseId> pendingConcolicResults(size_t n = (size_t)(-1));
941  Database::TestCaseId pendingConcolicResult() /*final*/;
949  virtual void insertConcolicResults(const TestCase::Ptr &original, const std::vector<TestCase::Ptr> &newCases);
950 
954  virtual bool isFinished() const;
955 
960  virtual void run() = 0;
961 };
962 
964 // Example execution manager
966 
972 public:
975 
976 protected:
977  explicit LinuxExitStatus(const Database::Ptr &db): ExecutionManager(db) {}
978 
979 public:
984  static Ptr create(const std::string databaseUrl, const boost::filesystem::path &executableName,
985  const std::vector<std::string> &arguments);
986 
992  static Ptr instance(const std::string& databaseUri, const std::string &testSuiteName = "");
993 
994  virtual void run() ROSE_OVERRIDE;
995 };
996 
999 void writeDBSchema(std::ostream& os);
1000 
1003 void writeSqlStmts(std::ostream& os);
1004 
1005 
1006 } // namespace
1007 } // namespace
1008 } // namespace
1009 
1010 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
1011 //~ BOOST_CLASS_EXPORT_GUID(LinuxExecutor::Result, "LinuxExecutor::Result")
1012 
1013 //~ BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::Concolic::ConcreteExecutor::Result)
1014 //~ BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::Concolic::LinuxExecutor::Result)
1015 
1017  Rose::BinaryAnalysis::Concolic::tagConcreteExecutorResult
1018  )
1019 BOOST_CLASS_EXPORT_KEY2( Rose::BinaryAnalysis::Concolic::LinuxExecutor::Result,
1020  Rose::BinaryAnalysis::Concolic::tagLinuxExecutorResult
1021  )
1022 #endif /* ROSE_HAVE_BOOST_SERIALIZATION_LIB */
1023 
1024 #endif
int exitStatus_
Exit status as returned by waitpid[2].
std::string out() const
Property: Output to STDOUT and STDERR of the executable.
Tag Object
Type of object to which this ID refers.
ObjectId< TestCase > TestCaseId
Database ID for test case objects.
void executionMonitor(const boost::filesystem::path &executorName)
Sets an execution monitor for a test run.
std::vector< std::string > args() const
Command line arguments.
void writeDBSchema(std::ostream &os)
prints all SQL schema statements on os.
SharedObject & operator=(const SharedObject &)
Assignment.
Definition: SharedObject.h:86
ObjectId< TestSuite > TestSuiteId
Database ID for test suite objects.
bool useAddressRandomization() const
Property: Address space randomization.
Sawyer::Optional< double > concreteRank() const
returns the concrete rank.
std::string capturedOut_
Output written to STDOUT.
Sawyer::SharedPointer< Database > Ptr
Reference counting pointer to Database.
boost::shared_ptr< Transaction > TransactionPtr
Shared-ownership pointer to a transaction.
Definition: SqlDatabase.h:147
Sawyer::SharedPointer< ExecutionManager > Ptr
Reference counting pointer to an ExecutionManager.
std::string exitKind_
Textual representation how the Result exited.
STL namespace.
void concolicTest(bool)
sets the status of the concolic test to true.
std::string capturedErr_
Output written to STDERR.
static Ptr instance()
Allocating default constructor.
Main namespace for the ROSE library.
static Ptr instance()
Allocating constructor.
One-to-one mapping between source and target values.
Definition: BiMap.h:26
void open(const boost::filesystem::path &executableName)
Open an executable file.
std::string name() const
Property: Specimen name.
Sawyer::SharedPointer< TestSuite > Ptr
Reference counting pointer to TestSuite.
Sawyer::SharedPointer< TestCase > Ptr
Reference counting pointer to a TestCase.
void useAddressRandomization(bool b)
Property: Address space randomization.
ROSE_UTIL_API std::string cEscape(const std::string &)
Escapes characters that are special to C/C++.
Base class for exceptions for concolic testing.
virtual ConcreteExecutor::Result * execute(const TestCase::Ptr &) ROSE_OVERRIDE
Execute one test case synchronously.
Sawyer::Optional< unsigned long > Persona
Holds an optional personality-value (i.g., indicating if address randomization should be turned off)...
void writeSqlStmts(std::ostream &os)
prints all SQL statements on os.
Sawyer::SharedPointer< ConcreteExecutor > Ptr
Reference counting pointer to a ConcreteExecutor.
Base class for user-defined Linux concrete execution results.
bool hasConcreteTest() const
returns if the test has been run concretely.
std::vector< EnvValue > env() const
Environment variables.
Specimen::Ptr specimen() const
Property: Specimen.
Information about how to run a specimen.
Creates SharedPointer from this.
Concolic teting of Linux executables.
void err(const std::string &output)
Property: Output to STDOUT and STDERR of the executable.
int exitStatus() const
Property: Exit status of the executable.
void out(const std::string &output)
Property: Output to STDOUT and STDERR of the executable.
Concrete executor for Linux ELF executables.
Base class for user-defined concrete execution results.
Sawyer::SharedPointer< Specimen > Ptr
Referenc-counting pointer to a Specimen.
bool isEmpty() const
Test whether this object is empty.
boost::filesystem::path executionMonitor() const
Sets an execution monitor for a test run.
Sawyer::SharedPointer< LinuxExecutor > Ptr
Reference counting pointer to a LinuxExecutor.
std::string printableName(const DatabasePtr &db=DatabasePtr())
Returns printable name of test case for diagnostic output.
void close()
Close the executable file.
bool hasConcolicTest() const
returns if the test has been run concollically.
boost::shared_ptr< Connection > ConnectionPtr
Shared-ownership pointer to a database connection.
Definition: SqlDatabase.h:137
const std::vector< uint8_t > & content() const
Property: Specimen content.
virtual Result * execute(const TestCase::Ptr &)=0
Execute one test case synchronously.
Base class for managing an entire concolic testing run.
Base class for reference counted objects.
Definition: SharedObject.h:64
Sawyer::SharedPointer< LinuxExitStatus > Ptr
Reference counting pointer to LinuxExitStatus.
std::string err() const
Property: Output to STDOUT and STDERR of the executable.
std::string exitKind() const
Property: textual representation of how a test exited.
std::string name() const
Property: Test case name.
Base class for all ROSE exceptions.
Definition: RoseException.h:9
ObjectId< Specimen > SpecimenId
Database ID for specimen objects.
std::pair< std::string, std::string > EnvValue
Environment variable and its value.
ObjectId(const std::string &s)
Construct by parsing a string.
std::string printableName(const DatabasePtr &db=DatabasePtr())
Returns printable name of specimen for diagnostic output.
static Ptr instance()
Allocating constructor.
Base class for executing test cases concretely.