ClearBlue
SEGTrace.h
1 /*
2  * SEGTrace.h
3  *
4  * Created on: 2016.11.4
5  * Author: andyzhou
6  */
7 
8 #ifndef INCLUDE_IR_SEG_SEGTRACE_H_
9 #define INCLUDE_IR_SEG_SEGTRACE_H_
10 
11 #include "rapidjson/document.h"
12 
13 #include "IR/LLVMValueTrace.h"
14 #include "IR/SEG/SymbolicExprGraphBuilder.h"
15 #include "IR/Trace.h"
16 
17 using namespace llvm;
18 
19 class SEGRegionNode;
20 
21 class SEGTrace : public Trace<const SEGObject *> {
22 public:
23  enum TraceKind {
24  TK_ValueFlow,
25  TK_ResourceLeak,
26  TK_TypeState,
27  };
28 
29  virtual TraceKind getKind() const { return TK_ValueFlow; }
30 
31 public:
32  typedef uint64_t StepType;
33  const static StepType STY_VALUE = 0x1;
34  const static StepType STY_USE_SITE = 0x2;
35 
36  const StepType DEFAULT_STEP_TYPE = STY_VALUE | STY_USE_SITE;
37 
38 private:
39  kvec<StepType> STys;
40 
41  // Additional conditions such as for NPD trace, we have ptr==null, and some
42  // path choices are also modelled here
43  kvec<SEGRegionNode *> AdditionalConds;
44 
45 protected:
46  // Guess the source node index of the last effect value flow of the bug trace
47  // if exist The sink of the last effect value flow is usually the key index
48  // This can be used to override "getLEVFSrcIdx" function
49  //
50  // In Basic IR, a value can be accessed from the value cached in register or
51  // by a load instruction accessing the main memory By setting isConsiderLoad =
52  // true, we consider load instruction as a source of the last effective value
53  // flow, or otherwise, we go past the load instruction and directly find the
54  // store instruction
55  int guessLEVFSrcIdx(bool IsConsiderLoad) const;
56 
57 public:
58  SEGTrace();
59 
60  SEGTrace(const SEGTrace &T);
61 
62  SEGTrace(const kvec<const SEGObject *> &Trace);
63 
65  SEGTrace(const SEGObject *Obj);
66 
67  SEGTrace(const SEGObject *Obj1, const SEGObject *Obj2);
68 
69  // Construct SEG trace from Value Trace
70  SEGTrace(const LLVMValueTrace *ValueTrace, SEGMapBase *SEGs);
71 
72  SEGTrace &operator=(const SEGTrace &T);
73 
74  // Reset the trace with LLVM Value Trace
75  virtual void resetWithLLVMValueTrace(const LLVMValueTrace *ValueTrace,
76  SEGMapBase *SEGs);
77 
78  virtual ~SEGTrace();
79 
80  // Get the real start idx of the trace that matters
81  // For some bug types, the first several steps shall be some preparation nodes
82  // Usually, returns 0, needing override when a class of trace has special
83  // needs that the first few steps are not considered
84  virtual int getValidStartIdx() const;
85 
86  // Get the key step index in the trace where vulnerability occurs
87  // SOURCE_SINK/SIMPLE_VALUE_FLOW/NON_VALUE_FLOW : return the last step
88  // SOURCE_NO_SINK : return the first step indicating the source
89  virtual int getKeyIdx() const;
90 
91  // Get the source node index of the last effect value flow of the bug trace if
92  // exist The sink of the last effect value flow is usually the key index
93  //
94  // By default, this function returns as follows :
95  // SOURCE_SINK/SIMPLE_VALUE_FLOW :
96  // guessLEVFSrcIdx(isConsiderLoad), which tries to guess the last value
97  // flow to the key step returned by getKeyIdx()
98  // SOURCE_NO_SINK/NON_VALUE_FLOW
99  // the last step of the trace, meaning that a bug report does not have
100  // such last effect value flow
101  //
102  // Please extend SEGTrace by overriding this function to support special last
103  // effect value flow source computation for e.g. domination checking
104  // guessLEVFSrcIdx() can be used to guess the last effect value flow index for
105  // common traces like NPD Trace, which can be used for the overriding of this
106  // function
107  //
108  // In Basic IR, a value can be accessed from the value cached in register or
109  // by a load instruction accessing the main memory By setting isConsiderLoad =
110  // true, we consider load instruction as a source of the last effective value
111  // flow, or otherwise, we go past the load instruction and directly find the
112  // store instruction
113  virtual int getLEVFSrcIdx(bool isConsiderLoad = false) const;
114 
115  // get the trace step type for the given StepIdx
116  StepType getStepType(int StepIdx) const;
117 
118  // get the trace step type for the given StepIdx to STy
119  void setStepType(int StepIdx, StepType STy);
120 
121  // Get the number of additional conditions for the trace
122  int getNumAdditionalConds() const;
123 
124  // Get the additional condition with index idx ranges in [0,
125  // getNumAdditionalConds)
126  SEGRegionNode *getAdditionalCond(int idx) const;
127 
128  // Add an additional condition modelled using SEG region node
129  void addAdditionalCond(SEGRegionNode *cond);
130 
131  // Clear all the additional conditions
132  void clearAdditionalCond();
133 
137  template <typename Predicate>
138  std::pair<const SEGObject *, int> find(int StartIndex, Predicate P) const {
139  for (int I = StartIndex, E = get_length(); I < E; ++I) {
140  auto *O = at(I);
141  if (P(O)) {
142  return std::move(std::make_pair(O, I));
143  }
144  }
145 
146  return std::move(std::make_pair(nullptr, get_length()));
147  }
148 
149  template <typename Predicate>
150  std::pair<const SEGObject *, size_t> rfind(size_t StartIndex,
151  Predicate P) const {
152  size_t Size = get_length();
153  if (StartIndex >= Size)
154  return std::move(std::make_pair(nullptr, Size));
155 
156  for (size_t I = StartIndex;; --I) {
157  auto *O = at(I);
158  if (P(O)) {
159  return std::move(std::make_pair(O, I));
160  }
161 
162  if (I == 0)
163  break;
164  }
165 
166  return std::move(std::make_pair(nullptr, Size));
167  }
168 
169  virtual void print(raw_ostream &O);
170 };
171 
172 #endif /* INCLUDE_IR_SEG_SEGTRACE_H_ */
SEGMapBase
Definition: SEGMapBase.h:22
SEGObject
Definition: SymbolicExprGraph.h:76
SEGRegionNode
Definition: SEGRegionNode.h:34
SEGTrace::find
std::pair< const SEGObject *, int > find(int StartIndex, Predicate P) const
Definition: SEGTrace.h:138
SEGTrace
Definition: SEGTrace.h:21