SEGTrace.h

/*
 * SEGTrace.h
 *
 *  Created on: 2016.11.4
 *      Author: andyzhou
 */
 
#ifndef INCLUDE_IR_SEG_SEGTRACE_H_
#define INCLUDE_IR_SEG_SEGTRACE_H_
 
#include "rapidjson/document.h"
 
#include "IR/LLVMValueTrace.h"
#include "IR/SEG/SymbolicExprGraphBuilder.h"
#include "IR/Trace.h"
 
using namespace llvm;
 
class SEGRegionNode;
 
class SEGTrace : public Trace<const SEGObject *> {
  friend class TraceSerializer;
 
public:
  enum TraceKind {
    TK_ValueFlow,
    TK_ResourceLeak,
    TK_TypeState,
  };
 
  virtual TraceKind getKind() const { return TK_ValueFlow; }
 
public:
  typedef uint64_t StepType;
  const static StepType STY_VALUE = 0x1;
  const static StepType STY_USE_SITE = 0x2;
 
  const StepType DEFAULT_STEP_TYPE = STY_VALUE | STY_USE_SITE;
 
private:
  kvec<StepType> STys;
 
  // Additional conditions such as for NPD trace, we have ptr==null, and some
  // path choices are also modelled here
  kvec<SEGRegionNode *> AdditionalConds;
 
protected:
  // Guess the source node index of the last effect value flow of the bug trace
  // if exist The sink of the last effect value flow is usually the key index
  // This can be used to override "getLEVFSrcIdx" function
  //
  // In Basic IR, a value can be accessed from the value cached in register or
  // by a load instruction accessing the main memory By setting isConsiderLoad =
  // true, we consider load instruction as a source of the last effective value
  // flow, or otherwise, we go past the load instruction and directly find the
  // store instruction
  int guessLEVFSrcIdx(bool IsConsiderLoad) const;
 
public:
  SEGTrace();
 
  SEGTrace(const SEGTrace &T);
 
  SEGTrace(const kvec<const SEGObject *> &Trace);
 
  SEGTrace(const SEGObject *Obj);
 
  SEGTrace(const SEGObject *Obj1, const SEGObject *Obj2);
 
  // Construct SEG trace from Value Trace
  SEGTrace(const LLVMValueTrace *ValueTrace, SEGMapBase *SEGs);
 
  SEGTrace &operator=(const SEGTrace &T);
 
  // Reset the trace with LLVM Value Trace
  virtual void resetWithLLVMValueTrace(const LLVMValueTrace *ValueTrace,
                                       SEGMapBase *SEGs);
 
  virtual ~SEGTrace();
 
  // Get the real start idx of the trace that matters
  // For some bug types, the first several steps shall be some preparation nodes
  // Usually, returns 0, needing override when a class of trace has special
  // needs that the first few steps are not considered
  virtual int getValidStartIdx() const;
 
  // Get the key step index in the trace where vulnerability occurs
  // SOURCE_SINK/SIMPLE_VALUE_FLOW/NON_VALUE_FLOW : return the last step
  // SOURCE_NO_SINK : return the first step indicating the source
  virtual int getKeyIdx() const;
 
  // Get the source node index of the last effect value flow of the bug trace if
  // exist The sink of the last effect value flow is usually the key index
  //
  // By default, this function returns as follows :
  // SOURCE_SINK/SIMPLE_VALUE_FLOW :
  //      guessLEVFSrcIdx(isConsiderLoad), which tries to guess the last value
  //      flow to the key step returned by getKeyIdx()
  // SOURCE_NO_SINK/NON_VALUE_FLOW
  //      the last step of the trace, meaning that a bug report does not have
  //      such last effect value flow
  //
  // Please extend SEGTrace by overriding this function to support special last
  // effect value flow source computation for e.g. domination checking
  // guessLEVFSrcIdx() can be used to guess the last effect value flow index for
  // common traces like NPD Trace, which can be used for the overriding of this
  // function
  //
  // In Basic IR, a value can be accessed from the value cached in register or
  // by a load instruction accessing the main memory By setting isConsiderLoad =
  // true, we consider load instruction as a source of the last effective value
  // flow, or otherwise, we go past the load instruction and directly find the
  // store instruction
  virtual int getLEVFSrcIdx(bool isConsiderLoad = false) const;
 
  // get the trace step type for the given StepIdx
  StepType getStepType(int StepIdx) const;
 
  // get the trace step type for the given StepIdx to STy
  void setStepType(int StepIdx, StepType STy);
 
  // Get the number of additional conditions for the trace
  int getNumAdditionalConds() const;
 
  // Get the additional condition with index idx ranges in [0,
  // getNumAdditionalConds)
  SEGRegionNode *getAdditionalCond(int idx) const;
 
  // Add an additional condition modelled using SEG region node
  void addAdditionalCond(SEGRegionNode *cond);
 
  // Clear all the additional conditions
  void clearAdditionalCond();
 
  template <typename Predicate>
  std::pair<const SEGObject *, int> find(int StartIndex, Predicate P) const {
    for (int I = StartIndex, E = get_length(); I < E; ++I) {
      auto *O = at(I);
      if (P(O)) {
        return std::move(std::make_pair(O, I));
      }
    }
 
    return std::move(std::make_pair(nullptr, get_length()));
  }
 
  template <typename Predicate>
  std::pair<const SEGObject *, size_t> rfind(size_t StartIndex,
                                             Predicate P) const {
    size_t Size = get_length();
    if (StartIndex >= Size)
      return std::move(std::make_pair(nullptr, Size));
 
    for (size_t I = StartIndex;; --I) {
      auto *O = at(I);
      if (P(O)) {
        return std::move(std::make_pair(O, I));
      }
 
      if (I == 0)
        break;
    }
 
    return std::move(std::make_pair(nullptr, Size));
  }
 
  virtual void print(raw_ostream &O);
};
 
#endif /* INCLUDE_IR_SEG_SEGTRACE_H_ */