Executor.h

Go to the documentation of this file.

//===-- Executor.h ----------------------------------------------*- C++ -*-===//
//
//                     The KLEE Symbolic Virtual Machine
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Class to perform actual execution, hides implementation details from external
// interpreter.
//
//===----------------------------------------------------------------------===//
 
#ifndef KLEE_EXECUTOR_H
#define KLEE_EXECUTOR_H
 
#include "ExecutionState.h"
#include "UserSearcher.h"
 
#include "klee/ADT/RNG.h"
#include "klee/Core/BranchTypes.h"
#include "klee/Core/Interpreter.h"
#include "klee/Core/TerminationTypes.h"
#include "klee/Expr/ArrayCache.h"
#include "klee/Expr/ArrayExprOptimizer.h"
#include "klee/Module/Cell.h"
#include "klee/Module/KInstruction.h"
#include "klee/Module/KModule.h"
#include "klee/System/Time.h"
 
#include "llvm/ADT/Twine.h"
#include "llvm/Support/raw_ostream.h"
 
#include <map>
#include <memory>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
 
struct KTest;
 
namespace llvm {
  class BasicBlock;
  class BranchInst;
  class CallInst;
  class LandingPadInst;
  class Constant;
  class ConstantExpr;
  class Function;
  class GlobalValue;
  class Instruction;
  class LLVMContext;
  class DataLayout;
  class Twine;
  class Value;
}
 
namespace klee {  
  class Array;
  struct Cell;
  class ExecutionState;
  class ExternalDispatcher;
  class Expr;
  class InstructionInfoTable;
  struct KFunction;
  struct KInstruction;
  class KInstIterator;
  class KModule;
  class MemoryManager;
  class MemoryObject;
  class ObjectState;
  class PTree;
  class Searcher;
  class SeedInfo;
  class SpecialFunctionHandler;
  struct StackFrame;
  class StatsTracker;
  class TimingSolver;
  class TreeStreamWriter;
  class MergeHandler;
  class MergingSearcher;
  template<class T> class ref;
 
 
 
 
class Executor : public Interpreter {
  friend class OwningSearcher;
  friend class WeightedRandomSearcher;
  friend class SpecialFunctionHandler;
  friend class StatsTracker;
  friend class MergeHandler;
  friend klee::Searcher *klee::constructUserSearcher(Executor &executor);
 
public:
  typedef std::pair<ExecutionState*,ExecutionState*> StatePair;
 
  RNG theRNG;
 
private:
  std::unique_ptr<KModule> kmodule;
  InterpreterHandler *interpreterHandler;
  Searcher *searcher;
 
  ExternalDispatcher *externalDispatcher;
  TimingSolver *solver;
  MemoryManager *memory;
  std::set<ExecutionState*, ExecutionStateIDCompare> states;
  StatsTracker *statsTracker;
  TreeStreamWriter *pathWriter, *symPathWriter;
  SpecialFunctionHandler *specialFunctionHandler;
  TimerGroup timers;
  std::unique_ptr<PTree> processTree;
 
  std::vector<ExecutionState *> addedStates;
  std::vector<ExecutionState *> removedStates;
 
  std::map<ExecutionState*, std::vector<SeedInfo> > seedMap;
  
  std::map<const llvm::GlobalValue*, MemoryObject*> globalObjects;
 
  std::map<const llvm::GlobalValue*, ref<ConstantExpr> > globalAddresses;
 
  std::unordered_map<std::uint64_t, llvm::Function*> legalFunctions;
 
  const struct KTest *replayKTest;
 
  const std::vector<bool> *replayPath;
 
  unsigned replayPosition;
 
  const std::vector<struct KTest *> *usingSeeds;  
 
  bool atMemoryLimit;
 
  bool inhibitForking;
 
  bool haltExecution;  
 
  bool ivcEnabled;
 
  time::Span coreSolverTimeout;
 
  time::Span maxInstructionTime;
 
  ArrayCache arrayCache;
 
  std::unique_ptr<llvm::raw_ostream> debugInstFile;
 
  // @brief Buffer used by logBuffer
  std::string debugBufferString;
 
  // @brief buffer to store logs before flushing to file
  llvm::raw_string_ostream debugLogBuffer;
 
  ExprOptimizer optimizer;
 
  MergingSearcher *mergingSearcher = nullptr;
 
  std::vector<ref<Expr>> eh_typeids;
 
  ref<ConstantExpr> getEhTypeidFor(ref<Expr> type_info);
 
  llvm::Function* getTargetFunction(llvm::Value *calledVal,
                                    ExecutionState &state);
  
  void executeInstruction(ExecutionState &state, KInstruction *ki);
 
  void run(ExecutionState &initialState);
 
  // Given a concrete object in our [klee's] address space, add it to 
  // objects checked code can reference.
  MemoryObject *addExternalObject(ExecutionState &state, void *addr, 
                                  unsigned size, bool isReadOnly);
 
  void initializeGlobalAlias(const llvm::Constant *c);
  void initializeGlobalObject(ExecutionState &state, ObjectState *os, 
                              const llvm::Constant *c,
                              unsigned offset);
  void initializeGlobals(ExecutionState &state);
  void allocateGlobalObjects(ExecutionState &state);
  void initializeGlobalAliases();
  void initializeGlobalObjects(ExecutionState &state);
 
  void stepInstruction(ExecutionState &state);
  void updateStates(ExecutionState *current);
  void transferToBasicBlock(llvm::BasicBlock *dst, 
                            llvm::BasicBlock *src,
                            ExecutionState &state);
 
  void callExternalFunction(ExecutionState &state,
                            KInstruction *target,
                            llvm::Function *function,
                            std::vector< ref<Expr> > &arguments);
 
  ObjectState *bindObjectInState(ExecutionState &state, const MemoryObject *mo,
                                 bool isLocal, const Array *array = 0);
 
  typedef std::vector< std::pair<std::pair<const MemoryObject*, const ObjectState*>, 
                                 ExecutionState*> > ExactResolutionList;
  void resolveExact(ExecutionState &state,
                    ref<Expr> p,
                    ExactResolutionList &results,
                    const std::string &name);
 
  void executeAlloc(ExecutionState &state,
                    ref<Expr> size,
                    bool isLocal,
                    KInstruction *target,
                    bool zeroMemory=false,
                    const ObjectState *reallocFrom=0,
                    size_t allocationAlignment=0);
 
  void executeFree(ExecutionState &state,
                   ref<Expr> address,
                   KInstruction *target = 0);
 
  MemoryObject *serializeLandingpad(ExecutionState &state,
                                    const llvm::LandingPadInst &lpi,
                                    bool &stateTerminated);
 
  void unwindToNextLandingpad(ExecutionState &state);
 
  void executeCall(ExecutionState &state, 
                   KInstruction *ki,
                   llvm::Function *f,
                   std::vector< ref<Expr> > &arguments);
                   
  // do address resolution / object binding / out of bounds checking
  // and perform the operation
  void executeMemoryOperation(ExecutionState &state,
                              bool isWrite,
                              ref<Expr> address,
                              ref<Expr> value /* undef if read */,
                              KInstruction *target /* undef if write */);
 
  void executeMakeSymbolic(ExecutionState &state, const MemoryObject *mo,
                           const std::string &name);
 
  void branch(ExecutionState &state, const std::vector<ref<Expr>> &conditions,
              std::vector<ExecutionState *> &result, BranchType reason);
 
  StatePair fork(ExecutionState &current, ref<Expr> condition, bool isInternal,
                 BranchType reason);
 
  // If the MaxStatic*Pct limits have been reached, concretize the condition and
  // return it. Otherwise, return the unmodified condition.
  ref<Expr> maxStaticPctChecks(ExecutionState &current, ref<Expr> condition);
 
  void addConstraint(ExecutionState &state, ref<Expr> condition);
 
  // Called on [for now] concrete reads, replaces constant with a symbolic
  // Used for testing.
  ref<Expr> replaceReadWithSymbolic(ExecutionState &state, ref<Expr> e);
 
  const Cell& eval(KInstruction *ki, unsigned index, 
                   ExecutionState &state) const;
 
  Cell& getArgumentCell(ExecutionState &state,
                        KFunction *kf,
                        unsigned index) {
    return state.stack.back().locals[kf->getArgRegister(index)];
  }
 
  Cell& getDestCell(ExecutionState &state,
                    KInstruction *target) {
    return state.stack.back().locals[target->dest];
  }
 
  void bindLocal(KInstruction *target, 
                 ExecutionState &state, 
                 ref<Expr> value);
  void bindArgument(KFunction *kf, 
                    unsigned index,
                    ExecutionState &state,
                    ref<Expr> value);
 
  ref<klee::ConstantExpr> evalConstantExpr(const llvm::ConstantExpr *c,
                                           const KInstruction *ki = NULL);
 
  ref<klee::ConstantExpr> evalConstant(const llvm::Constant *c,
                                       const KInstruction *ki = NULL);
 
  ref<Expr> toUnique(const ExecutionState &state, ref<Expr> &e);
 
  ref<klee::ConstantExpr> toConstant(ExecutionState &state, ref<Expr> e, 
                                     const char *purpose);
 
  void executeGetValue(ExecutionState &state, ref<Expr> e, KInstruction *target);
 
  std::string getAddressInfo(ExecutionState &state, ref<Expr> address) const;
 
  // Determines the \param lastInstruction of the \param state which is not KLEE
  // internal and returns its InstructionInfo
  const InstructionInfo & getLastNonKleeInternalInstruction(const ExecutionState &state,
      llvm::Instruction** lastInstruction);
 
  void terminateState(ExecutionState &state);
 
  void terminateStateOnExit(ExecutionState &state);
 
  void terminateStateEarly(ExecutionState &state, const llvm::Twine &message,
                           StateTerminationType terminationType);
 
  void terminateStateOnError(ExecutionState &state, const llvm::Twine &message,
                             StateTerminationType terminationType,
                             const llvm::Twine &longMessage = "",
                             const char *suffix = nullptr);
 
  void terminateStateOnExecError(ExecutionState &state,
                                 const llvm::Twine &message,
                                 const llvm::Twine &info = "");
 
  void terminateStateOnSolverError(ExecutionState &state,
                                   const llvm::Twine &message);
 
  void terminateStateOnUserError(ExecutionState &state,
                                 const llvm::Twine &message);
 
  void bindModuleConstants();
 
  template <typename SqType, typename TypeIt>
  void computeOffsetsSeqTy(KGEPInstruction *kgepi,
                           ref<ConstantExpr> &constantOffset, uint64_t index,
                           const TypeIt it);
 
  template <typename TypeIt>
  void computeOffsets(KGEPInstruction *kgepi, TypeIt ib, TypeIt ie);
 
  void bindInstructionConstants(KInstruction *KI);
 
  void doImpliedValueConcretization(ExecutionState &state,
                                    ref<Expr> e,
                                    ref<ConstantExpr> value);
 
  bool checkMemoryUsage();
 
  bool branchingPermitted(const ExecutionState &state) const;
 
  void printDebugInstructions(ExecutionState &state);
  void doDumpStates();
 
  void dumpStates();
  void dumpPTree();
 
public:
  Executor(llvm::LLVMContext &ctx, const InterpreterOptions &opts,
      InterpreterHandler *ie);
  virtual ~Executor();
 
  const InterpreterHandler& getHandler() {
    return *interpreterHandler;
  }
 
  void setPathWriter(TreeStreamWriter *tsw) override { pathWriter = tsw; }
 
  void setSymbolicPathWriter(TreeStreamWriter *tsw) override {
    symPathWriter = tsw;
  }
 
  void setReplayKTest(const struct KTest *out) override {
    assert(!replayPath && "cannot replay both buffer and path");
    replayKTest = out;
    replayPosition = 0;
  }
 
  void setReplayPath(const std::vector<bool> *path) override {
    assert(!replayKTest && "cannot replay both buffer and path");
    replayPath = path;
    replayPosition = 0;
  }
 
  llvm::Module *setModule(std::vector<std::unique_ptr<llvm::Module>> &modules,
                          const ModuleOptions &opts) override;
 
  void useSeeds(const std::vector<struct KTest *> *seeds) override {
    usingSeeds = seeds;
  }
 
  void runFunctionAsMain(llvm::Function *f, int argc, char **argv,
                         char **envp) override;
 
  /*** Runtime options ***/
 
  void setHaltExecution(bool value) override { haltExecution = value; }
 
  void setInhibitForking(bool value) override { inhibitForking = value; }
 
  void prepareForEarlyExit() override;
 
  /*** State accessor methods ***/
 
  unsigned getPathStreamID(const ExecutionState &state) override;
 
  unsigned getSymbolicPathStreamID(const ExecutionState &state) override;
 
  void getConstraintLog(const ExecutionState &state, std::string &res,
                        Interpreter::LogType logFormat =
                            Interpreter::STP) override;
 
  bool getSymbolicSolution(
      const ExecutionState &state,
      std::vector<std::pair<std::string, std::vector<unsigned char>>> &res)
      override;
 
  void getCoveredLines(const ExecutionState &state,
                       std::map<const std::string *, std::set<unsigned>> &res)
      override;
 
  Expr::Width getWidthForLLVMType(llvm::Type *type) const;
  size_t getAllocationAlignment(const llvm::Value *allocSite) const;
 
  int *getErrnoLocation(const ExecutionState &state) const;
 
  MergingSearcher *getMergingSearcher() const { return mergingSearcher; };
  void setMergingSearcher(MergingSearcher *ms) { mergingSearcher = ms; };
};
  
} // End klee namespace
 
#endif /* KLEE_EXECUTOR_H */