ROSE  0.9.12.24
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.
213  void content(std::vector<uint8_t> binary_data);
214 };
215 
217 // Test cases
219 
221 typedef std::pair<std::string /*name*/, std::string /*value*/> EnvValue;
222 
226 class TestCase: public Sawyer::SharedObject, public Sawyer::SharedFromThis<TestCase> {
227 public:
230 
231 private:
232  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
233  std::string name_; // name for debugging
234  std::string executor_; // name of execution environment
235  Specimen::Ptr specimen_; // the thing to run
236 
237  std::vector<std::string> args_; // command line arguments
238  std::vector<EnvValue> env_; // environment variables
239  Sawyer::Optional<double> concrete_rank_; // rank after testing
240  bool concolically_tested; // true if test was run concolically
241 
242 protected:
243  TestCase() {}
244 
245 public:
247  static Ptr instance() {
248  return Ptr(new TestCase);
249  }
250 
252  static Ptr instance(const Specimen::Ptr &specimen);
253 
262  std::string name() const; // value return is intentional for thread safety
263  void name(const std::string&);
271  std::string printableName(const DatabasePtr &db = DatabasePtr());
272 
280  Specimen::Ptr specimen() const;
281  void specimen(const Specimen::Ptr&);
286  std::vector<std::string> args() const;
287  void args(std::vector<std::string> arguments);
292  std::vector<EnvValue> env() const;
293  void env(std::vector<EnvValue> envvars);
297  bool hasConcolicTest() const;
298 
300  void concolicTest(bool);
301 
303  bool hasConcreteTest() const;
304 
307 
310 
311  // We'll need to add additional information about how to run the specimen:
312  // 1. Command-line arguments (argc, argv)
313  // 2. Environment varaibles (envp)
314  // 3. Auxilliary vector (auxv)
315  // 4. System calls that provide input (e.g., virtual file system, network, etc.)
316  // Some of this information might need to be separated into subclasses that support different architectures since the
317  // info for testing a Linux ELF executable is different from a Windows PE executable, which is different from how one
318  // would run firmware.
319 };
320 
321 
323 // Concrete executors and their results
325 
326 extern const char* const tagConcreteExecutorResult;
327 extern const char* const tagLinuxExecutorResult;
328 
340 public:
343 
354  class Result {
355  private:
356  double rank_;
357 
358  public:
359  explicit Result(double rank): rank_(rank) {
360  ASSERT_forbid(rose_isnan(rank));
361  }
362 
363  Result() {} // required for serialization
364 
365  virtual ~Result() {}
366 
367  double rank() const { return rank_; }
368 
369  private:
370  friend class boost::serialization::access;
371 
372  template<class S>
373  void serialize(S &s, const unsigned /*version*/) {
374  s & BOOST_SERIALIZATION_NVP(rank_);
375  }
376  };
377 
378 protected:
379  // Allocating constructors should be implemente by the non-abstract subclasses.
380  ConcreteExecutor() {}
381 
382 public:
387  virtual
388  Result*
389  execute(const TestCase::Ptr&) = 0;
390 
413  void executionMonitor(const boost::filesystem::path& executorName)
414  {
415  execmon = executorName;
416  }
417 
418  boost::filesystem::path executionMonitor() const
419  {
420  return execmon;
421  }
424 private:
425  boost::filesystem::path execmon; // the execution monitor
426 };
427 
430 public:
433 
436 
439  protected:
441  std::string exitKind_;
442  std::string capturedOut_;
443  std::string capturedErr_;
445  private:
446  friend class boost::serialization::access;
447 
448  template<class S>
449  void serialize(S &s, const unsigned /*version*/) {
450  // was: s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(ConcreteExecutor::Result);
451  // nvp of a base class in a different namespace seems to produce
452  // invalid results.
453  s & boost::serialization::make_nvp( tagConcreteExecutorResult,
454  boost::serialization::base_object<ConcreteExecutor::Result>(*this)
455  );
456  s & BOOST_SERIALIZATION_NVP(exitStatus_);
457  s & BOOST_SERIALIZATION_NVP(exitKind_);
458  s & BOOST_SERIALIZATION_NVP(capturedOut_);
459  s & BOOST_SERIALIZATION_NVP(capturedErr_);
460  }
461 
462  public:
463  Result(double rank, int exitStatus);
464 
465  Result() {} // required for boost serialization
466 
474  int exitStatus() const { return exitStatus_; }
475  void exitStatus(int x);
481  std::string out() const { return capturedOut_; }
482  void out(const std::string& output) { capturedOut_ = output; }
483 
484  std::string err() const { return capturedErr_; }
485  void err(const std::string& output) { capturedErr_ = output; }
491  std::string exitKind() const { return exitKind_; }
492  /* @} */
493  };
494 
495 protected:
496  bool useAddressRandomization_; // enable/disable address space randomization in the OS
497 
498 protected:
499  LinuxExecutor()
500  : useAddressRandomization_(false) {}
501 
502 public:
504  static Ptr instance() {
505  return Ptr(new LinuxExecutor);
506  }
507 
514  bool useAddressRandomization() const { return useAddressRandomization_; }
515  void useAddressRandomization(bool b) { useAddressRandomization_ = b; }
518  virtual
519  Result* execute(const TestCase::Ptr&) ROSE_OVERRIDE;
520 };
521 
523 // Concolic (concrete + symbolic) executors
525 
526 } // namespace
527 } // namespace
528 } // namespace
529 
530 #include <Concolic/ConcolicExecutor.h>
531 
532 namespace Rose {
533 namespace BinaryAnalysis {
534 namespace Concolic {
535 
537 // Test suites
539 
552 class TestSuite: public Sawyer::SharedObject, public Sawyer::SharedFromThis<TestSuite> {
553 public:
556 
557 private:
558  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
559  std::string name_; // unique and non-empty within a database
560 
561 protected:
562  TestSuite() {}
563 
564 public:
566  static Ptr instance(const std::string &name = "");
567 
576  std::string name() const; // value return is intentional for thread safety
577  void name(const std::string&);
585  std::string printableName(const DatabasePtr &db = DatabasePtr());
586 };
587 
589 // Databases
591 
593 template <class Tag>
594 class ObjectId: public Sawyer::Optional<size_t> {
595 public:
596  typedef size_t Value;
598  typedef Tag Object;
600  ObjectId() {}
601 
602  explicit
603  ObjectId(const Value& v)
604  : Super(v) {}
605 
606  ObjectId(const ObjectId& rhs)
607  : Super(rhs) {}
608 
614  explicit ObjectId(const std::string &s) {
615  char *rest = NULL;
616  uint64_t id = rose_strtoull(s.c_str(), &rest, 0);
617  while (*rest && isspace(*rest)) ++rest;
618  if (*rest)
619  throw Exception("invalid syntax for object ID: \"" + StringUtility::cEscape(s) + "\"");
620  try {
621  *this = boost::numeric_cast<Value>(id);
622  } catch (const boost::bad_numeric_cast&) {
623  throw Exception("parsed object ID out of range: \"" + StringUtility::cEscape(s) + "\"");
624  }
625  }
626 
629  this->Super::operator=(lhs);
630  return *this;
631  }
632 
634  ObjectId<Tag>& operator=(const Value& v) {
635  this->Super::operator=(v);
636  return *this;
637  }
638 
640  template<class _Tag>
641  friend
642  bool operator<(const ObjectId<_Tag>& lhs, const ObjectId<_Tag>& rhs);
643 };
644 
646 template<class Tag>
647 inline
648 bool operator<(const ObjectId<Tag>& lhs, const ObjectId<Tag>& rhs)
649 {
650  if (!rhs) return false;
651  if (!lhs) return true;
652 
653  return lhs.get() < rhs.get();
654 }
655 
672 class Database: public Sawyer::SharedObject, boost::noncopyable {
673 public:
676 
677  typedef ::Rose::BinaryAnalysis::Concolic::TestSuiteId TestSuiteId;
678  typedef ::Rose::BinaryAnalysis::Concolic::SpecimenId SpecimenId;
679  typedef ::Rose::BinaryAnalysis::Concolic::TestCaseId TestCaseId;
680 
681 private:
682  SqlDatabase::ConnectionPtr dbconn_; // holds connection to database
683 
684  // The lock protects the following concurrent accesses
685  // - memoized data
686  // - testSuiteId_
687  //~ mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
688 
689  // Memoization of ID to object mappings
693 
694  TestSuiteId testSuiteId_; // database scope is restricted to this single test suite
695 
696 protected:
697  Database()
698  : dbconn_(), specimens_(), testCases_(), testSuites_(), testSuiteId_()
699  {}
700 
701 public:
705  static Ptr instance(const std::string &url);
706 
717  static Ptr create(const std::string &url);
718  static Ptr create(const std::string &url, const std::string &testSuiteName);
720  //------------------------------------------------------------------------------------------------------------------------
721  // Test suites
722  //------------------------------------------------------------------------------------------------------------------------
723 
728  std::vector<TestSuiteId> testSuites();
729 
737  TestSuite::Ptr testSuite();
738  TestSuiteId testSuite(const TestSuite::Ptr&);
741  //------------------------------------------------------------------------------------------------------------------------
742  // Specimens
743  //------------------------------------------------------------------------------------------------------------------------
744 
749  std::vector<SpecimenId> specimens();
750 
751  //------------------------------------------------------------------------------------------------------------------------
752  // Test cases
753  //------------------------------------------------------------------------------------------------------------------------
754 
759  std::vector<TestCaseId> testCases();
760 
761  //------------------------------------------------------------------------------------------------------------------------
762  // Overloaded methods for all objects.
763  //------------------------------------------------------------------------------------------------------------------------
764 
771  TestSuite::Ptr object(TestSuiteId, Update::Flag update = Update::YES);
772  TestCase::Ptr object(TestCaseId, Update::Flag update = Update::YES);
773  Specimen::Ptr object(SpecimenId, Update::Flag update = Update::YES);
780  Specimen::Ptr object_ns(SqlDatabase::TransactionPtr tx, SpecimenId id);
781 
790  TestSuiteId id(const TestSuite::Ptr&, Update::Flag update = Update::YES);
791  TestCaseId id(const TestCase::Ptr&, Update::Flag update = Update::YES);
792  SpecimenId id(const Specimen::Ptr&, Update::Flag update = Update::YES);
801  TestSuiteId id_ns(SqlDatabase::TransactionPtr, const TestSuite::Ptr&, Update::Flag update = Update::YES);
802  TestCaseId id_ns(SqlDatabase::TransactionPtr, const TestCase::Ptr&, Update::Flag update = Update::YES);
803  SpecimenId id_ns(SqlDatabase::TransactionPtr, const Specimen::Ptr&, Update::Flag update = Update::YES);
804 
811  TestSuite::Ptr findTestSuite(const std::string &nameOrId);
812 
817  std::vector<SpecimenId> findSpecimensByName(const std::string &name);
818 
819  //------------------------------------------------------------------------------------------------------------------------
820  // Cached info about disassembly. This is large data. Each specimen has zero or one associated RBA data blob.
821  //------------------------------------------------------------------------------------------------------------------------
822 
829  bool rbaExists(SpecimenId);
830 
839  void saveRbaFile(const boost::filesystem::path&, SpecimenId);
840 
848  void extractRbaFile(const boost::filesystem::path&, SpecimenId);
849 
855  void eraseRba(SpecimenId);
856 
861  void assocTestCaseWithTestSuite(TestCaseId testcase, TestSuiteId testsuite);
862 
867  std::vector<Database::TestCaseId> needConcreteTesting(size_t);
868 
873  std::vector<Database::TestCaseId> needConcolicTesting(size_t);
874 
882  void insertConcreteResults(const TestCase::Ptr &testCase, const ConcreteExecutor::Result& details);
883 
888  bool hasUntested() const;
889 };
890 
891 
893 // Execution manager
895 
900 class ExecutionManager: boost::noncopyable, public Sawyer::SharedObject {
901 public:
904 
905 private:
906  Database::Ptr database_;
907 
908 protected:
909  // Subclasses should implement allocating constructors
910  explicit ExecutionManager(const Database::Ptr &db)
911  : database_(db) {
912  ASSERT_not_null(db);
913  }
914 
915 public:
916  virtual ~ExecutionManager() {}
917 
921  Database::Ptr database() const;
922 
929  virtual std::vector<Database::TestCaseId> pendingConcreteResults(size_t n = (size_t)(-1));
930  Database::TestCaseId pendingConcreteResult() /*final*/;
938  virtual void insertConcreteResults(const TestCase::Ptr&, const ConcreteExecutor::Result &details);
939 
946  virtual std::vector<Database::TestCaseId> pendingConcolicResults(size_t n = (size_t)(-1));
947  Database::TestCaseId pendingConcolicResult() /*final*/;
955  virtual void insertConcolicResults(const TestCase::Ptr &original, const std::vector<TestCase::Ptr> &newCases);
956 
960  virtual bool isFinished() const;
961 
966  virtual void run() = 0;
967 };
968 
970 // Example execution manager
972 
978 public:
981 
982 protected:
983  explicit LinuxExitStatus(const Database::Ptr &db): ExecutionManager(db) {}
984 
985 public:
990  static Ptr create(const std::string databaseUrl, const boost::filesystem::path &executableName,
991  const std::vector<std::string> &arguments);
992 
998  static Ptr instance(const std::string& databaseUri, const std::string &testSuiteName = "");
999 
1000  virtual void run() ROSE_OVERRIDE;
1001 };
1002 
1005 void writeDBSchema(std::ostream& os);
1006 
1009 void writeSqlStmts(std::ostream& os);
1010 
1011 
1012 } // namespace
1013 } // namespace
1014 } // namespace
1015 
1016 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
1017 //~ BOOST_CLASS_EXPORT_GUID(LinuxExecutor::Result, "LinuxExecutor::Result")
1018 
1019 //~ BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::Concolic::ConcreteExecutor::Result)
1020 //~ BOOST_CLASS_EXPORT_KEY(Rose::BinaryAnalysis::Concolic::LinuxExecutor::Result)
1021 
1023  Rose::BinaryAnalysis::Concolic::tagConcreteExecutorResult
1024  )
1025 BOOST_CLASS_EXPORT_KEY2( Rose::BinaryAnalysis::Concolic::LinuxExecutor::Result,
1026  Rose::BinaryAnalysis::Concolic::tagLinuxExecutorResult
1027  )
1028 #endif /* ROSE_HAVE_BOOST_SERIALIZATION_LIB */
1029 
1030 #endif
int exitStatus_
Exit status as returned by waitpid[2].
virtual Result * execute(const TestCase::Ptr &) ROSE_OVERRIDE
Execute one test case synchronously.
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.
ObjectId< TestSuite > TestSuiteId
Database ID for test suite objects.
ID class for database 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.
ObjectId< Tag > & operator=(const Value &v)
Assignment overload to allow assignments of Value objects.
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.
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.
Sawyer::Optional< Value > Super
Supertype of this class.
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
const Value & get() const
Dereference to obtain value.
Definition: Optional.h:192
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.
ObjectId< Tag > & operator=(const ObjectId< Tag > &lhs)
Assignment operator to replace default generated one.
Base class for executing test cases concretely.