Coverage Report

Created: 2022-01-22 13:19

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/Taint.cpp
Line
Count
Source (jump to first uncovered line)
1
//=== Taint.cpp - Taint tracking and basic propagation rules. ------*- C++ -*-//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// Defines basic, non-domain-specific mechanisms for tracking tainted values.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "Taint.h"
14
#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
15
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
16
17
using namespace clang;
18
using namespace ento;
19
using namespace taint;
20
21
// Fully tainted symbols.
22
REGISTER_MAP_WITH_PROGRAMSTATE(TaintMap, SymbolRef, TaintTagType)
23
24
// Partially tainted symbols.
25
REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(TaintedSubRegions, const SubRegion *,
26
                                       TaintTagType)
27
REGISTER_MAP_WITH_PROGRAMSTATE(DerivedSymTaint, SymbolRef, TaintedSubRegions)
28
29
void taint::printTaint(ProgramStateRef State, raw_ostream &Out, const char *NL,
30
2
                       const char *Sep) {
31
2
  TaintMapTy TM = State->get<TaintMap>();
32
33
2
  if (!TM.isEmpty())
34
2
    Out << "Tainted symbols:" << NL;
35
36
2
  for (const auto &I : TM)
37
2
    Out << I.first << " : " << I.second << NL;
38
2
}
39
40
0
void dumpTaint(ProgramStateRef State) { printTaint(State, llvm::errs()); }
41
42
ProgramStateRef taint::addTaint(ProgramStateRef State, const Stmt *S,
43
                                const LocationContext *LCtx,
44
0
                                TaintTagType Kind) {
45
0
  return addTaint(State, State->getSVal(S, LCtx), Kind);
46
0
}
47
48
ProgramStateRef taint::addTaint(ProgramStateRef State, SVal V,
49
759
                                TaintTagType Kind) {
50
759
  SymbolRef Sym = V.getAsSymbol();
51
759
  if (Sym)
52
681
    return addTaint(State, Sym, Kind);
53
54
  // If the SVal represents a structure, try to mass-taint all values within the
55
  // structure. For now it only works efficiently on lazy compound values that
56
  // were conjured during a conservative evaluation of a function - either as
57
  // return values of functions that return structures or arrays by value, or as
58
  // values of structures or arrays passed into the function by reference,
59
  // directly or through pointer aliasing. Such lazy compound values are
60
  // characterized by having exactly one binding in their captured store within
61
  // their parent region, which is a conjured symbol default-bound to the base
62
  // region of the parent region.
63
78
  if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) {
64
50
    if (Optional<SVal> binding =
65
50
            State->getStateManager().getStoreManager().getDefaultBinding(
66
50
                *LCV)) {
67
50
      if (SymbolRef Sym = binding->getAsSymbol())
68
50
        return addPartialTaint(State, Sym, LCV->getRegion(), Kind);
69
50
    }
70
50
  }
71
72
28
  const MemRegion *R = V.getAsRegion();
73
28
  return addTaint(State, R, Kind);
74
78
}
75
76
ProgramStateRef taint::addTaint(ProgramStateRef State, const MemRegion *R,
77
28
                                TaintTagType Kind) {
78
28
  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
79
0
    return addTaint(State, SR->getSymbol(), Kind);
80
28
  return State;
81
28
}
82
83
ProgramStateRef taint::addTaint(ProgramStateRef State, SymbolRef Sym,
84
701
                                TaintTagType Kind) {
85
  // If this is a symbol cast, remove the cast before adding the taint. Taint
86
  // is cast agnostic.
87
701
  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
88
0
    Sym = SC->getOperand();
89
90
701
  ProgramStateRef NewState = State->set<TaintMap>(Sym, Kind);
91
701
  assert(NewState);
92
0
  return NewState;
93
701
}
94
95
10
ProgramStateRef taint::removeTaint(ProgramStateRef State, SVal V) {
96
10
  SymbolRef Sym = V.getAsSymbol();
97
10
  if (Sym)
98
5
    return removeTaint(State, Sym);
99
100
5
  const MemRegion *R = V.getAsRegion();
101
5
  return removeTaint(State, R);
102
10
}
103
104
5
ProgramStateRef taint::removeTaint(ProgramStateRef State, const MemRegion *R) {
105
5
  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
106
0
    return removeTaint(State, SR->getSymbol());
107
5
  return State;
108
5
}
109
110
5
ProgramStateRef taint::removeTaint(ProgramStateRef State, SymbolRef Sym) {
111
  // If this is a symbol cast, remove the cast before adding the taint. Taint
112
  // is cast agnostic.
113
5
  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
114
0
    Sym = SC->getOperand();
115
116
5
  ProgramStateRef NewState = State->remove<TaintMap>(Sym);
117
5
  assert(NewState);
118
0
  return NewState;
119
5
}
120
121
ProgramStateRef taint::addPartialTaint(ProgramStateRef State,
122
                                       SymbolRef ParentSym,
123
                                       const SubRegion *SubRegion,
124
50
                                       TaintTagType Kind) {
125
  // Ignore partial taint if the entire parent symbol is already tainted.
126
50
  if (const TaintTagType *T = State->get<TaintMap>(ParentSym))
127
0
    if (*T == Kind)
128
0
      return State;
129
130
  // Partial taint applies if only a portion of the symbol is tainted.
131
50
  if (SubRegion == SubRegion->getBaseRegion())
132
20
    return addTaint(State, ParentSym, Kind);
133
134
30
  const TaintedSubRegions *SavedRegs = State->get<DerivedSymTaint>(ParentSym);
135
30
  TaintedSubRegions::Factory &F = State->get_context<TaintedSubRegions>();
136
30
  TaintedSubRegions Regs = SavedRegs ? 
*SavedRegs0
: F.getEmptyMap();
137
138
30
  Regs = F.add(Regs, SubRegion, Kind);
139
30
  ProgramStateRef NewState = State->set<DerivedSymTaint>(ParentSym, Regs);
140
30
  assert(NewState);
141
0
  return NewState;
142
50
}
143
144
bool taint::isTainted(ProgramStateRef State, const Stmt *S,
145
1.05k
                      const LocationContext *LCtx, TaintTagType Kind) {
146
1.05k
  SVal val = State->getSVal(S, LCtx);
147
1.05k
  return isTainted(State, val, Kind);
148
1.05k
}
149
150
22.7k
bool taint::isTainted(ProgramStateRef State, SVal V, TaintTagType Kind) {
151
22.7k
  if (SymbolRef Sym = V.getAsSymbol())
152
18.9k
    return isTainted(State, Sym, Kind);
153
3.79k
  if (const MemRegion *Reg = V.getAsRegion())
154
498
    return isTainted(State, Reg, Kind);
155
3.29k
  return false;
156
3.79k
}
157
158
bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,
159
7.75k
                      TaintTagType K) {
160
7.75k
  if (!Reg)
161
0
    return false;
162
163
  // Element region (array element) is tainted if either the base or the offset
164
  // are tainted.
165
7.75k
  if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
166
2.79k
    return isTainted(State, ER->getSuperRegion(), K) ||
167
2.79k
           
isTainted(State, ER->getIndex(), K)2.38k
;
168
169
4.96k
  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
170
2.54k
    return isTainted(State, SR->getSymbol(), K);
171
172
2.42k
  if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
173
1.21k
    return isTainted(State, ER->getSuperRegion(), K);
174
175
1.20k
  return false;
176
2.42k
}
177
178
28.2k
bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {
179
28.2k
  if (!Sym)
180
0
    return false;
181
182
  // Traverse all the symbols this symbol depends on to see if any are tainted.
183
28.2k
  for (SymExpr::symbol_iterator SI = Sym->symbol_begin(),
184
28.2k
                                SE = Sym->symbol_end();
185
89.8k
       SI != SE; 
++SI61.6k
) {
186
71.2k
    if (!isa<SymbolData>(*SI))
187
28.5k
      continue;
188
189
42.7k
    if (const TaintTagType *Tag = State->get<TaintMap>(*SI)) {
190
8.25k
      if (*Tag == Kind)
191
8.25k
        return true;
192
8.25k
    }
193
194
34.4k
    if (const auto *SD = dyn_cast<SymbolDerived>(*SI)) {
195
      // If this is a SymbolDerived with a tainted parent, it's also tainted.
196
6.67k
      if (isTainted(State, SD->getParentSymbol(), Kind))
197
630
        return true;
198
199
      // If this is a SymbolDerived with the same parent symbol as another
200
      // tainted SymbolDerived and a region that's a sub-region of that tainted
201
      // symbol, it's also tainted.
202
6.04k
      if (const TaintedSubRegions *Regs =
203
6.04k
              State->get<DerivedSymTaint>(SD->getParentSymbol())) {
204
340
        const TypedValueRegion *R = SD->getRegion();
205
340
        for (auto I : *Regs) {
206
          // FIXME: The logic to identify tainted regions could be more
207
          // complete. For example, this would not currently identify
208
          // overlapping fields in a union as tainted. To identify this we can
209
          // check for overlapping/nested byte offsets.
210
340
          if (Kind == I.second && R->isSubRegionOf(I.first))
211
255
            return true;
212
340
        }
213
340
      }
214
6.04k
    }
215
216
    // If memory region is tainted, data is also tainted.
217
33.5k
    if (const auto *SRV = dyn_cast<SymbolRegionValue>(*SI)) {
218
3.24k
      if (isTainted(State, SRV->getRegion(), Kind))
219
416
        return true;
220
3.24k
    }
221
222
    // If this is a SymbolCast from a tainted value, it's also tainted.
223
33.1k
    if (const auto *SC = dyn_cast<SymbolCast>(*SI)) {
224
0
      if (isTainted(State, SC->getOperand(), Kind))
225
0
        return true;
226
0
    }
227
33.1k
  }
228
229
18.6k
  return false;
230
28.2k
}
231
232
PathDiagnosticPieceRef TaintBugVisitor::VisitNode(const ExplodedNode *N,
233
                                                  BugReporterContext &BRC,
234
13.3k
                                                  PathSensitiveBugReport &BR) {
235
236
  // Find the ExplodedNode where the taint was first introduced
237
13.3k
  if (!isTainted(N->getState(), V) ||
238
13.3k
      
isTainted(N->getFirstPred()->getState(), V)3.90k
)
239
13.2k
    return nullptr;
240
241
160
  const Stmt *S = N->getStmtForDiagnostics();
242
160
  if (!S)
243
0
    return nullptr;
244
245
160
  const LocationContext *NCtx = N->getLocationContext();
246
160
  PathDiagnosticLocation L =
247
160
      PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx);
248
160
  if (!L.isValid() || !L.asLocation().isValid())
249
0
    return nullptr;
250
251
160
  return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here");
252
160
}