1 //=== Taint.cpp - Taint tracking and basic propagation rules. ------*- C++ -*-//
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
7 //===----------------------------------------------------------------------===//
9 // Defines basic, non-domain-specific mechanisms for tracking tainted values.
11 //===----------------------------------------------------------------------===//
14 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
15 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
17 using namespace clang;
19 using namespace taint;
21 // Fully tainted symbols.
22 REGISTER_MAP_WITH_PROGRAMSTATE(TaintMap, SymbolRef, TaintTagType)
24 // Partially tainted symbols.
25 REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(TaintedSubRegions, const SubRegion *,
27 REGISTER_MAP_WITH_PROGRAMSTATE(DerivedSymTaint, SymbolRef, TaintedSubRegions)
29 void taint::printTaint(ProgramStateRef State, raw_ostream &Out, const char *NL,
31 TaintMapTy TM = State->get<TaintMap>();
34 Out << "Tainted symbols:" << NL;
36 for (const auto &I : TM)
37 Out << I.first << " : " << I.second << NL;
40 void dumpTaint(ProgramStateRef State) { printTaint(State, llvm::errs()); }
42 ProgramStateRef taint::addTaint(ProgramStateRef State, const Stmt *S,
43 const LocationContext *LCtx,
45 return addTaint(State, State->getSVal(S, LCtx), Kind);
48 ProgramStateRef taint::addTaint(ProgramStateRef State, SVal V,
50 SymbolRef Sym = V.getAsSymbol();
52 return addTaint(State, Sym, Kind);
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(
67 if (SymbolRef Sym = binding->getAsSymbol())
68 return addPartialTaint(State, Sym, LCV->getRegion(), Kind);
72 const MemRegion *R = V.getAsRegion();
73 return addTaint(State, R, Kind);
76 ProgramStateRef taint::addTaint(ProgramStateRef State, const MemRegion *R,
78 if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
79 return addTaint(State, SR->getSymbol(), Kind);
83 ProgramStateRef taint::addTaint(ProgramStateRef State, SymbolRef Sym,
85 // If this is a symbol cast, remove the cast before adding the taint. Taint
87 while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
88 Sym = SC->getOperand();
90 ProgramStateRef NewState = State->set<TaintMap>(Sym, Kind);
95 ProgramStateRef taint::removeTaint(ProgramStateRef State, SVal V) {
96 SymbolRef Sym = V.getAsSymbol();
98 return removeTaint(State, Sym);
100 const MemRegion *R = V.getAsRegion();
101 return removeTaint(State, R);
104 ProgramStateRef taint::removeTaint(ProgramStateRef State, const MemRegion *R) {
105 if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
106 return removeTaint(State, SR->getSymbol());
110 ProgramStateRef taint::removeTaint(ProgramStateRef State, SymbolRef Sym) {
111 // If this is a symbol cast, remove the cast before adding the taint. Taint
113 while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
114 Sym = SC->getOperand();
116 ProgramStateRef NewState = State->remove<TaintMap>(Sym);
121 ProgramStateRef taint::addPartialTaint(ProgramStateRef State,
123 const SubRegion *SubRegion,
125 // Ignore partial taint if the entire parent symbol is already tainted.
126 if (const TaintTagType *T = State->get<TaintMap>(ParentSym))
130 // Partial taint applies if only a portion of the symbol is tainted.
131 if (SubRegion == SubRegion->getBaseRegion())
132 return addTaint(State, ParentSym, Kind);
134 const TaintedSubRegions *SavedRegs = State->get<DerivedSymTaint>(ParentSym);
135 TaintedSubRegions::Factory &F = State->get_context<TaintedSubRegions>();
136 TaintedSubRegions Regs = SavedRegs ? *SavedRegs : F.getEmptyMap();
138 Regs = F.add(Regs, SubRegion, Kind);
139 ProgramStateRef NewState = State->set<DerivedSymTaint>(ParentSym, Regs);
144 bool 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);
150 bool 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);
158 bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,
163 // Element region (array element) is tainted if either the base or the offset
165 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
166 return isTainted(State, ER->getSuperRegion(), K) ||
167 isTainted(State, ER->getIndex(), K);
169 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
170 return isTainted(State, SR->getSymbol(), K);
172 if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
173 return isTainted(State, ER->getSuperRegion(), K);
178 bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {
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();
186 if (!isa<SymbolData>(*SI))
189 if (const TaintTagType *Tag = State->get<TaintMap>(*SI)) {
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))
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))
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))
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))
232 PathDiagnosticPieceRef TaintBugVisitor::VisitNode(const ExplodedNode *N,
233 BugReporterContext &BRC,
234 PathSensitiveBugReport &BR) {
236 // Find the ExplodedNode where the taint was first introduced
237 if (!isTainted(N->getState(), V) ||
238 isTainted(N->getFirstPred()->getState(), V))
241 const Stmt *S = N->getStmtForDiagnostics();
245 const LocationContext *NCtx = N->getLocationContext();
246 PathDiagnosticLocation L =
247 PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx);
248 if (!L.isValid() || !L.asLocation().isValid())
251 return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here");