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