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