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
17using namespace clang;
18using namespace ento;
19using namespace taint;
20
21// Fully tainted symbols.
22REGISTER_MAP_WITH_PROGRAMSTATE(TaintMap, SymbolRef, TaintTagType)
23
24// Partially tainted symbols.
25REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(TaintedSubRegions, const SubRegion *,
26                                       TaintTagType)
27REGISTER_MAP_WITH_PROGRAMSTATE(DerivedSymTaint, SymbolRef, TaintedSubRegions)
28
29void taint::printTaint(ProgramStateRef State, raw_ostream &Out, const char *NL,
30                       const char *Sep) {
31  TaintMapTy TM = State->get<TaintMap>();
32
33  if (!TM.isEmpty())
34    Out << "Tainted symbols:" << NL;
35
36  for (const auto &I : TM)
37    Out << I.first << " : " << I.second << NL;
38}
39
40void dumpTaint(ProgramStateRef State) { printTaint(State, llvm::errs()); }
41
42ProgramStateRef taint::addTaint(ProgramStateRef State, const Stmt *S,
43                                const LocationContext *LCtx,
44                                TaintTagType Kind) {
45  return addTaint(State, State->getSVal(S, LCtx), Kind);
46}
47
48ProgramStateRef taint::addTaint(ProgramStateRef State, SVal V,
49                                TaintTagType Kind) {
50  SymbolRef Sym = V.getAsSymbol();
51  if (Sym)
52    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  if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) {
64    if (Optional<SVal> binding =
65            State->getStateManager().getStoreManager().getDefaultBinding(
66                *LCV)) {
67      if (SymbolRef Sym = binding->getAsSymbol())
68        return addPartialTaint(State, Sym, LCV->getRegion(), Kind);
69    }
70  }
71
72  const MemRegion *R = V.getAsRegion();
73  return addTaint(State, R, Kind);
74}
75
76ProgramStateRef taint::addTaint(ProgramStateRef State, const MemRegion *R,
77                                TaintTagType Kind) {
78  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
79    return addTaint(State, SR->getSymbol(), Kind);
80  return State;
81}
82
83ProgramStateRef taint::addTaint(ProgramStateRef State, SymbolRef Sym,
84                                TaintTagType Kind) {
85  // If this is a symbol cast, remove the cast before adding the taint. Taint
86  // is cast agnostic.
87  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
88    Sym = SC->getOperand();
89
90  ProgramStateRef NewState = State->set<TaintMap>(Sym, Kind);
91  assert(NewState);
92  return NewState;
93}
94
95ProgramStateRef taint::removeTaint(ProgramStateRef State, SVal V) {
96  SymbolRef Sym = V.getAsSymbol();
97  if (Sym)
98    return removeTaint(State, Sym);
99
100  const MemRegion *R = V.getAsRegion();
101  return removeTaint(State, R);
102}
103
104ProgramStateRef taint::removeTaint(ProgramStateRef State, const MemRegion *R) {
105  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
106    return removeTaint(State, SR->getSymbol());
107  return State;
108}
109
110ProgramStateRef 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  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
114    Sym = SC->getOperand();
115
116  ProgramStateRef NewState = State->remove<TaintMap>(Sym);
117  assert(NewState);
118  return NewState;
119}
120
121ProgramStateRef taint::addPartialTaint(ProgramStateRef State,
122                                       SymbolRef ParentSym,
123                                       const SubRegion *SubRegion,
124                                       TaintTagType Kind) {
125  // Ignore partial taint if the entire parent symbol is already tainted.
126  if (const TaintTagType *T = State->get<TaintMap>(ParentSym))
127    if (*T == Kind)
128      return State;
129
130  // Partial taint applies if only a portion of the symbol is tainted.
131  if (SubRegion == SubRegion->getBaseRegion())
132    return addTaint(State, ParentSym, Kind);
133
134  const TaintedSubRegions *SavedRegs = State->get<DerivedSymTaint>(ParentSym);
135  TaintedSubRegions::Factory &F = State->get_context<TaintedSubRegions>();
136  TaintedSubRegions Regs = SavedRegs ? *SavedRegs : F.getEmptyMap();
137
138  Regs = F.add(Regs, SubRegion, Kind);
139  ProgramStateRef NewState = State->set<DerivedSymTaint>(ParentSym, Regs);
140  assert(NewState);
141  return NewState;
142}
143
144bool taint::isTainted(ProgramStateRef State, const Stmt *S,
145                      const LocationContext *LCtx, TaintTagType Kind) {
146  SVal val = State->getSVal(S, LCtx);
147  return isTainted(State, val, Kind);
148}
149
150bool taint::isTainted(ProgramStateRef State, SVal V, TaintTagType Kind) {
151  if (const SymExpr *Sym = V.getAsSymExpr())
152    return isTainted(State, Sym, Kind);
153  if (const MemRegion *Reg = V.getAsRegion())
154    return isTainted(State, Reg, Kind);
155  return false;
156}
157
158bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,
159                      TaintTagType K) {
160  if (!Reg)
161    return false;
162
163  // Element region (array element) is tainted if either the base or the offset
164  // are tainted.
165  if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
166    return isTainted(State, ER->getSuperRegion(), K) ||
167           isTainted(State, ER->getIndex(), K);
168
169  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
170    return isTainted(State, SR->getSymbol(), K);
171
172  if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
173    return isTainted(State, ER->getSuperRegion(), K);
174
175  return false;
176}
177
178bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {
179  if (!Sym)
180    return false;
181
182  // Traverse all the symbols this symbol depends on to see if any are tainted.
183  for (SymExpr::symbol_iterator SI = Sym->symbol_begin(),
184                                SE = Sym->symbol_end();
185       SI != SE; ++SI) {
186    if (!isa<SymbolData>(*SI))
187      continue;
188
189    if (const TaintTagType *Tag = State->get<TaintMap>(*SI)) {
190      if (*Tag == Kind)
191        return true;
192    }
193
194    if (const auto *SD = dyn_cast<SymbolDerived>(*SI)) {
195      // If this is a SymbolDerived with a tainted parent, it's also tainted.
196      if (isTainted(State, SD->getParentSymbol(), Kind))
197        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      if (const TaintedSubRegions *Regs =
203              State->get<DerivedSymTaint>(SD->getParentSymbol())) {
204        const TypedValueRegion *R = SD->getRegion();
205        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          if (Kind == I.second && R->isSubRegionOf(I.first))
211            return true;
212        }
213      }
214    }
215
216    // If memory region is tainted, data is also tainted.
217    if (const auto *SRV = dyn_cast<SymbolRegionValue>(*SI)) {
218      if (isTainted(State, SRV->getRegion(), Kind))
219        return true;
220    }
221
222    // If this is a SymbolCast from a tainted value, it's also tainted.
223    if (const auto *SC = dyn_cast<SymbolCast>(*SI)) {
224      if (isTainted(State, SC->getOperand(), Kind))
225        return true;
226    }
227  }
228
229  return false;
230}
231
232PathDiagnosticPieceRef TaintBugVisitor::VisitNode(const ExplodedNode *N,
233                                                  BugReporterContext &BRC,
234                                                  PathSensitiveBugReport &BR) {
235
236  // Find the ExplodedNode where the taint was first introduced
237  if (!isTainted(N->getState(), V) ||
238      isTainted(N->getFirstPred()->getState(), V))
239    return nullptr;
240
241  const Stmt *S = N->getStmtForDiagnostics();
242  if (!S)
243    return nullptr;
244
245  const LocationContext *NCtx = N->getLocationContext();
246  PathDiagnosticLocation L =
247      PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx);
248  if (!L.isValid() || !L.asLocation().isValid())
249    return nullptr;
250
251  return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here");
252}
253