ROSE  0.9.11.10
BinaryConcolic.h
1 #ifndef ROSE_BinaryAnalysis_Concolic_H
2 #define ROSE_BinaryAnalysis_Concolic_H
3 
4 // ROSE headers
5 #include <Diagnostics.h>
6 #include <rose_isnan.h>
7 #include <Partitioner2/BasicTypes.h>
8 #include <RoseException.h>
9 #include <SqlDatabase.h>
10 
11 
12 // Non-ROSE headers
13 #include <boost/filesystem.hpp>
14 #include <boost/serialization/access.hpp>
15 #include <boost/serialization/nvp.hpp>
16 #include <Sawyer/BiMap.h>
17 #include <Sawyer/SharedObject.h>
18 #include <Sawyer/SharedPointer.h>
19 #include <Sawyer/Synchronization.h>
20 #include <memory>
21 #include <stdexcept>
22 #include <string>
23 #include <vector>
24 
25 namespace Rose {
26 namespace BinaryAnalysis {
27 
50 namespace Concolic {
51 
53 // Flags and enums
55 
56 namespace Update {
57 enum Flag { NO, YES };
58 } // namespace
59 
61 // Exceptions, errors, etc.
63 
64 extern Sawyer::Message::Facility mlog;
65 
67 class Exception: public Rose::Exception {
68 public:
69  explicit Exception(const std::string &mesg): Rose::Exception(mesg) {}
70  ~Exception() throw () {}
71 };
72 
74 // Forward references
76 
77 class Specimen;
79 
80 class TestCase;
82 
83 class ConcreteExecutor;
85 
86 class LinuxExecutor;
88 
89 class ConcolicExecutor;
91 
92 class TestSuite;
94 
95 class Database;
97 
98 class ExecutionManager;
100 
101 class LinuxExitStatus;
103 
105 // Specimens
107 
113 public:
116 
117 private:
118  typedef std::vector<uint8_t> BinaryData;
119 
120  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
121  std::string name_; // name of specimen (e.g., for debugging)
122  BinaryData content_; // content of the binary executable file
123  mutable bool read_only_; // safe guards from writing content after it has been shared;
124  bool empty_; // indicates if this object is empty
125 
126 private:
127  friend class boost::serialization::access;
128 
129  template<class S>
130  void serialize(S &s, const unsigned /*version*/) {
131  s & BOOST_SERIALIZATION_NVP(name_);
132  s & BOOST_SERIALIZATION_NVP(content_);
133  s & BOOST_SERIALIZATION_NVP(empty_);
134  }
135 
136 protected:
137  Specimen()
138  : mutex_(), name_(), content_(), read_only_(false), empty_(false)
139  {}
140 
141 public:
144  static Ptr instance(const boost::filesystem::path &executableName);
145  static Ptr instance();
154  void open(const boost::filesystem::path &executableName);
155 
162  void close();
163 
169  bool isEmpty() const;
170 
179  std::string name() const; // value return is intentional for thread safety
180  void name(const std::string&);
189  const std::vector<uint8_t>& content() const;
190 
191  void content(std::vector<uint8_t> binary_data);
192 };
193 
195 // Test cases
197 
198 typedef std::pair<std::string, std::string> EnvValue;
199 
204 public:
207 
208 private:
209  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
210  std::string name_; // name for debugging
211  std::string executor_; // name of execution environment
212  Specimen::Ptr specimen_; // the thing to run
213 
214  std::vector<std::string> args_; // command line arguments
215  std::vector<EnvValue> env_; // environment variables
216  Sawyer::Optional<double> concrete_rank_; // rank after testing
217  bool concolically_tested; // true if test was run concolically
218 
219 protected:
220  TestCase() {}
221 
222 public:
224  static Ptr instance() {
225  return Ptr(new TestCase);
226  }
227 
229  static Ptr instance(const Specimen::Ptr &specimen);
230 
239  std::string name() const; // value return is intentional for thread safety
240  void name(const std::string&);
250  Specimen::Ptr specimen() const;
251  void specimen(const Specimen::Ptr&);
256  std::vector<std::string> args() const;
257  void args(std::vector<std::string> arguments);
262  std::vector<EnvValue> env() const;
263  void env(std::vector<EnvValue> envvars);
267  bool hasConcolicTest() const;
268 
270  void concolicTest(bool);
271 
273  bool hasConcreteTest() const;
274 
277 
280 
281  // We'll need to add additional information about how to run the specimen:
282  // 1. Command-line arguments (argc, argv)
283  // 2. Environment varaibles (envp)
284  // 3. Auxilliary vector (auxv)
285  // 4. System calls that provide input (e.g., virtual file system, network, etc.)
286  // Some of this information might need to be separated into subclasses that support different architectures since the
287  // info for testing a Linux ELF executable is different from a Windows PE executable, which is different from how one
288  // would run firmware.
289 };
290 
291 
293 // Concrete executors and their results
295 
307 public:
310 
321  class Result {
322  private:
323  double rank_;
324 
325  public:
326  explicit Result(double rank): rank_(rank) {
327  ASSERT_forbid(rose_isnan(rank));
328  }
329  virtual ~Result() {}
330 
331  double rank() const { return rank_; }
332 
333  private:
334  friend class boost::serialization::access;
335 
336  template<class S>
337  void serialize(S &s, const unsigned /*version*/) {
338  s & BOOST_SERIALIZATION_NVP(rank_);
339  }
340  };
341 
342 protected:
343  // Allocating constructors should be implemente by the non-abstract subclasses.
344  ConcreteExecutor() {}
345 
346 public:
351  virtual
352  Result*
353  execute(const TestCase::Ptr&) = 0;
354 };
355 
356 
359 public:
362 
365  protected:
368  private:
369  friend class boost::serialization::access;
370 
371  template<class S>
372  void serialize(S &s, const unsigned /*version*/) {
373  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(ConcreteExecutor::Result);
374  s & BOOST_SERIALIZATION_NVP(exitStatus_);
375  }
376 
377  public:
378  Result(int exitStatus);
379 
387  int exitStatus() const { return exitStatus_; }
388  void exitStatus(int x) { exitStatus_ = x; }
390  };
391 
392 protected:
393  bool useAddressRandomization_; // enable/disable address space randomization in the OS
394 
395 protected:
396  LinuxExecutor()
397  : useAddressRandomization_(false) {}
398 
399 public:
401  static Ptr instance() {
402  return Ptr(new LinuxExecutor);
403  }
404 
411  // TO BE REMOVED BY PETER: When you "exec" the specimen, you'll need to use setarch -R to turn off ASLR. There's probably
412  // an equivalent C library function, but I don't know what it is.
413  bool useAddressRandomization() const { return useAddressRandomization_; }
414  void useAddressRandomization(bool b) { useAddressRandomization_ = b; }
417  virtual
419  execute(const TestCase::Ptr&) ROSE_OVERRIDE;
420 };
421 
422 
424 // Concolic (concrete + symbolic) executors
426 
431 public:
434 
436  struct Settings {
437  Partitioner2::EngineSettings partitionerEngine;
441  };
442 
443 private:
444  Settings settings_;
445 
446 protected:
447  ConcolicExecutor() {}
448 
449 public:
451  static Ptr instance();
452 
461  const Settings& settings() const { return settings_; }
462  Settings& settings() { return settings_; }
468  std::vector<TestCase::Ptr> execute(const DatabasePtr&, const TestCase::Ptr&);
469 
470 private:
471  // Disassemble the specimen and cache the result in the database. If the specimen has previously been disassembled
472  // then reconstitute the analysis results from the database.
473  Partitioner2::Partitioner partition(const DatabasePtr&, const Specimen::Ptr&);
474 
475  // TODO: Lots of properties to control the finer aspects of executing a test case!
476 };
477 
478 
480 // Test suites
482 
492 public:
495 
496 private:
497  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members
498  std::string name_; // unique and non-empty within a database
499 
500 protected:
501  TestSuite() {}
502 
503 public:
505  static Ptr instance(const std::string &name = "");
506 
515  std::string name() const; // value return is intentional for thread safety
516  void name(const std::string&);
518 };
519 
521 // Databases
523 
537 template <class Tag>
539 {
541  typedef int Value;
542 
543  ObjectId() : Super() {}
544 
545  explicit
546  ObjectId(const Value& v)
547  : Super(v)
548  {}
549 
550  ObjectId(const ObjectId& rhs)
551  : Super(rhs)
552  {}
553 
555  {
556  this->Super::operator=(lhs);
557 
558  return *this;
559  }
560 
561  ObjectId<Tag>& operator=(const Value& v)
562  {
563  this->Super::operator=(v);
564 
565  return *this;
566  }
567 
568  template<class _Tag>
569  friend
570  bool operator<(const ObjectId<_Tag>& lhs, const ObjectId<_Tag>& rhs);
571 };
572 
573  template<class Tag>
574  inline
575  bool operator<(const ObjectId<Tag>& lhs, const ObjectId<Tag>& rhs)
576  {
577  static const int noid = -1;
578 
579  const int lhsid = lhs.orElse(noid);
580  const int rhsid = rhs.orElse(noid);
581 
582  return lhsid < rhsid;
583  }
584 
585 
586 typedef ObjectId<TestSuite> TestSuiteId;
587 typedef ObjectId<Specimen> SpecimenId;
588 typedef ObjectId<TestCase> TestCaseId;
589 
590 class Database: public Sawyer::SharedObject, boost::noncopyable {
591 public:
594 
595  typedef ::Rose::BinaryAnalysis::Concolic::TestSuiteId TestSuiteId;
596  typedef ::Rose::BinaryAnalysis::Concolic::SpecimenId SpecimenId;
597  typedef ::Rose::BinaryAnalysis::Concolic::TestCaseId TestCaseId;
598 
599 private:
600  SqlDatabase::ConnectionPtr dbconn_; // holds connection to database
601 
602  // The lock protects the following concurrent accesses
603  // - memoized data
604  // - testSuiteId_
605  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
606 
607  // Memoization of ID to object mappings
611 
612  TestSuiteId testSuiteId_; // database scope is restricted to this single test suite
613 
614 protected:
615  Database()
616  : dbconn_(), mutex_(), specimens_(), testCases_(), testSuites_(),
617  testSuiteId_()
618  {}
619 
620 public:
624  static Ptr instance(const std::string &url);
625 
634  static Ptr create(const std::string &url, const std::string &testSuiteName);
635 
636  //------------------------------------------------------------------------------------------------------------------------
637  // Test suites
638  //------------------------------------------------------------------------------------------------------------------------
639 
644  std::vector<TestSuiteId> testSuites();
645 
653  TestSuite::Ptr testSuite();
654  TestSuiteId testSuite(const TestSuite::Ptr&);
657  //------------------------------------------------------------------------------------------------------------------------
658  // Specimens
659  //------------------------------------------------------------------------------------------------------------------------
660 
665  std::vector<SpecimenId> specimens();
666 
667  //------------------------------------------------------------------------------------------------------------------------
668  // Test cases
669  //------------------------------------------------------------------------------------------------------------------------
670 
675  std::vector<TestCaseId> testCases();
676 
677  //------------------------------------------------------------------------------------------------------------------------
678  // Overloaded methods for all objects.
679  //------------------------------------------------------------------------------------------------------------------------
680 
687  TestSuite::Ptr object(TestSuiteId, Update::Flag update = Update::YES);
688  TestCase::Ptr object(TestCaseId, Update::Flag update = Update::YES);
689  Specimen::Ptr object(SpecimenId, Update::Flag update = Update::YES);
697  Specimen::Ptr object_ns(SqlDatabase::TransactionPtr tx, SpecimenId id);
698 
707  TestSuiteId id(const TestSuite::Ptr&, Update::Flag update = Update::YES);
708  TestCaseId id(const TestCase::Ptr&, Update::Flag update = Update::YES);
709  SpecimenId id(const Specimen::Ptr&, Update::Flag update = Update::YES);
718  TestSuiteId id_ns(SqlDatabase::TransactionPtr, const TestSuite::Ptr&);
719  TestCaseId id_ns(SqlDatabase::TransactionPtr, const TestCase::Ptr&);
720  SpecimenId id_ns(SqlDatabase::TransactionPtr, const Specimen::Ptr&);
721 
722 
723  //------------------------------------------------------------------------------------------------------------------------
724  // Cached info about disassembly. This is large data. Each specimen has zero or one associated RBA data blob.
725  //------------------------------------------------------------------------------------------------------------------------
726 
733  bool rbaExists(SpecimenId);
734 
743  void saveRbaFile(const boost::filesystem::path&, SpecimenId);
744 
752  void extractRbaFile(const boost::filesystem::path&, SpecimenId);
753 
759  void eraseRba(SpecimenId);
760 
765  void assocTestCaseWithTestSuite(TestCaseId testcase, TestSuiteId testsuite);
766 
771  std::vector<Database::TestCaseId> needConcreteTesting(size_t);
772 
777  std::vector<Database::TestCaseId> needConcolicTesting(size_t);
778 
783  void insertConcreteResults(const TestCase::Ptr &testCase, const ConcreteExecutor::Result& details);
784 
789  bool hasUntested() const;
790 };
791 
792 
794 // Execution manager
796 
801 class ExecutionManager: boost::noncopyable, public Sawyer::SharedObject {
802 public:
805 
806 private:
807  Database::Ptr database_;
808 
809 protected:
810  // Subclasses should implement allocating constructors
811  explicit ExecutionManager(const Database::Ptr &db)
812  : database_(db) {
813  ASSERT_not_null(db);
814  }
815 
816 public:
817  virtual ~ExecutionManager() {}
818 
822  Database::Ptr database() const;
823 
830  virtual std::vector<Database::TestCaseId> pendingConcreteResults(size_t n = (size_t)(-1));
831  Database::TestCaseId pendingConcreteResult() /*final*/;
839  virtual void insertConcreteResults(const TestCase::Ptr&, const ConcreteExecutor::Result &details);
840 
847  virtual std::vector<Database::TestCaseId> pendingConcolicResults(size_t n = (size_t)(-1));
848  Database::TestCaseId pendingConcolicResult() /*final*/;
856  virtual void insertConcolicResults(const TestCase::Ptr &original, const std::vector<TestCase::Ptr> &newCases);
857 
861  virtual bool isFinished() const;
862 
867  virtual void run() = 0;
868 };
869 
871 // Example execution manager
873 
879 public:
882 
883 protected:
884  explicit LinuxExitStatus(const Database::Ptr &db): ExecutionManager(db) {}
885 
886 public:
891  static Ptr create(const std::string databaseUrl, const boost::filesystem::path &executableName,
892  const std::vector<std::string> &arguments);
893 
899  static Ptr instance(const std::string& databaseUri, const std::string &testSuiteName = "");
900 
901  virtual void run() ROSE_OVERRIDE;
902 };
903 
908 std::vector<uint8_t> loadBinaryFile(const boost::filesystem::path& path);
909 
914 void storeBinaryFile(const std::vector<uint8_t>& data, const boost::filesystem::path& path);
915 
916 
917 } // namespace
918 } // namespace
919 } // namespace
920 #endif
int exitStatus_
Exit status as returned by waitpid[2].
SharedObject()
Default constructor.
Definition: SharedObject.h:70
Settings for controling the engine behavior.
Definition: BasicTypes.h:439
std::vector< std::string > args() const
Command line arguments.
SharedObject & operator=(const SharedObject &)
Assignment.
Definition: SharedObject.h:86
Collection of streams.
Definition: Message.h:1579
Settings that control the disassembler.
Definition: BasicTypes.h:248
bool useAddressRandomization() const
Property: Address space randomization.
Sawyer::Optional< double > concreteRank() const
returns the concrete rank.
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.
STL namespace.
void concolicTest(bool)
sets the status of the concolic test to true.
const Settings & settings() const
Property: Configuration settings.
static Ptr instance()
Allocating default constructor.
Main namespace for the ROSE library.
static Ptr instance()
Allocating constructor.
Settings for loading specimens.
Definition: BasicTypes.h:193
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.
Name space for the entire library.
Sawyer::SharedPointer< TestCase > Ptr
Reference counting pointer to a TestCase.
void useAddressRandomization(bool b)
Property: Address space randomization.
Base class for exceptions for concolic testing.
virtual ConcreteExecutor::Result * execute(const TestCase::Ptr &) ROSE_OVERRIDE
Execute one test case synchronously.
Sawyer::SharedPointer< ConcreteExecutor > Ptr
Reference counting pointer to a ConcreteExecutor.
Settings to control various aspects of an executor.
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.
Settings that control the engine partitioning.
Definition: BasicTypes.h:307
Information about how to run a specimen.
Settings & settings()
Property: Configuration settings.
Concolic teting of Linux executables.
int exitStatus() const
Property: Exit status of the executable.
void exitStatus(int x)
Property: Exit status 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.
Sawyer::SharedPointer< LinuxExecutor > Ptr
Reference counting pointer to a LinuxExecutor.
void close()
Close the executable file.
void storeBinaryFile(const std::vector< uint8_t > &data, const boost::filesystem::path &path)
Stores a binary file.
std::vector< uint8_t > loadBinaryFile(const boost::filesystem::path &path)
Loads a binary 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.
Sawyer::SharedPointer< ConcolicExecutor > Ptr
Reference counting pointer to ConcolicExecutor.
std::string name() const
Property: Test case name.
const Value & orElse(const Value &dflt) const
Obtain value or something else.
Definition: Optional.h:230
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:293
Base class for all ROSE exceptions.
Definition: RoseException.h:9
static Ptr instance()
Allocating constructor.
Base class for executing test cases concretely.