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) {
41 printTaint(State, llvm::errs());
44 ProgramStateRef taint::addTaint(ProgramStateRef State, const Stmt *S,
45 const LocationContext *LCtx,
47 return addTaint(State, State->getSVal(S, LCtx), Kind);
50 ProgramStateRef taint::addTaint(ProgramStateRef State, SVal V,
52 SymbolRef Sym = V.getAsSymbol();
54 return addTaint(State, Sym, Kind);
56 // If the SVal represents a structure, try to mass-taint all values within the
57 // structure. For now it only works efficiently on lazy compound values that
58 // were conjured during a conservative evaluation of a function - either as
59 // return values of functions that return structures or arrays by value, or as
60 // values of structures or arrays passed into the function by reference,
61 // directly or through pointer aliasing. Such lazy compound values are
62 // characterized by having exactly one binding in their captured store within
63 // their parent region, which is a conjured symbol default-bound to the base
64 // region of the parent region.
65 if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) {
66 if (Optional<SVal> binding =
67 State->getStateManager().getStoreManager()
68 .getDefaultBinding(*LCV)) {
69 if (SymbolRef Sym = binding->getAsSymbol())
70 return addPartialTaint(State, Sym, LCV->getRegion(), Kind);
74 const MemRegion *R = V.getAsRegion();
75 return addTaint(State, R, Kind);
78 ProgramStateRef taint::addTaint(ProgramStateRef State, const MemRegion *R,
80 if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
81 return addTaint(State, SR->getSymbol(), Kind);
85 ProgramStateRef taint::addTaint(ProgramStateRef State, SymbolRef Sym,
87 // If this is a symbol cast, remove the cast before adding the taint. Taint
89 while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
90 Sym = SC->getOperand();
92 ProgramStateRef NewState = State->set<TaintMap>(Sym, Kind);
97 ProgramStateRef taint::addPartialTaint(ProgramStateRef State,
99 const SubRegion *SubRegion,
101 // Ignore partial taint if the entire parent symbol is already tainted.
102 if (const TaintTagType *T = State->get<TaintMap>(ParentSym))
106 // Partial taint applies if only a portion of the symbol is tainted.
107 if (SubRegion == SubRegion->getBaseRegion())
108 return addTaint(State, ParentSym, Kind);
110 const TaintedSubRegions *SavedRegs = State->get<DerivedSymTaint>(ParentSym);
111 TaintedSubRegions::Factory &F = State->get_context<TaintedSubRegions>();
112 TaintedSubRegions Regs = SavedRegs ? *SavedRegs : F.getEmptyMap();
114 Regs = F.add(Regs, SubRegion, Kind);
115 ProgramStateRef NewState = State->set<DerivedSymTaint>(ParentSym, Regs);
120 bool taint::isTainted(ProgramStateRef State, const Stmt *S,
121 const LocationContext *LCtx, TaintTagType Kind) {
122 SVal val = State->getSVal(S, LCtx);
123 return isTainted(State, val, Kind);
126 bool taint::isTainted(ProgramStateRef State, SVal V, TaintTagType Kind) {
127 if (const SymExpr *Sym = V.getAsSymExpr())
128 return isTainted(State, Sym, Kind);
129 if (const MemRegion *Reg = V.getAsRegion())
130 return isTainted(State, Reg, Kind);
134 bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,
139 // Element region (array element) is tainted if either the base or the offset
141 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
142 return isTainted(State, ER->getSuperRegion(), K) ||
143 isTainted(State, ER->getIndex(), K);
145 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
146 return isTainted(State, SR->getSymbol(), K);
148 if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
149 return isTainted(State, ER->getSuperRegion(), K);
154 bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {
158 // Traverse all the symbols this symbol depends on to see if any are tainted.
159 for (SymExpr::symbol_iterator SI = Sym->symbol_begin(),
160 SE = Sym->symbol_end(); SI != SE; ++SI) {
161 if (!isa<SymbolData>(*SI))
164 if (const TaintTagType *Tag = State->get<TaintMap>(*SI)) {
169 if (const auto *SD = dyn_cast<SymbolDerived>(*SI)) {
170 // If this is a SymbolDerived with a tainted parent, it's also tainted.
171 if (isTainted(State, SD->getParentSymbol(), Kind))
174 // If this is a SymbolDerived with the same parent symbol as another
175 // tainted SymbolDerived and a region that's a sub-region of that tainted
176 // symbol, it's also tainted.
177 if (const TaintedSubRegions *Regs =
178 State->get<DerivedSymTaint>(SD->getParentSymbol())) {
179 const TypedValueRegion *R = SD->getRegion();
180 for (auto I : *Regs) {
181 // FIXME: The logic to identify tainted regions could be more
182 // complete. For example, this would not currently identify
183 // overlapping fields in a union as tainted. To identify this we can
184 // check for overlapping/nested byte offsets.
185 if (Kind == I.second && R->isSubRegionOf(I.first))
191 // If memory region is tainted, data is also tainted.
192 if (const auto *SRV = dyn_cast<SymbolRegionValue>(*SI)) {
193 if (isTainted(State, SRV->getRegion(), Kind))
197 // If this is a SymbolCast from a tainted value, it's also tainted.
198 if (const auto *SC = dyn_cast<SymbolCast>(*SI)) {
199 if (isTainted(State, SC->getOperand(), Kind))
207 PathDiagnosticPieceRef TaintBugVisitor::VisitNode(const ExplodedNode *N,
208 BugReporterContext &BRC,
209 PathSensitiveBugReport &BR) {
211 // Find the ExplodedNode where the taint was first introduced
212 if (!isTainted(N->getState(), V) ||
213 isTainted(N->getFirstPred()->getState(), V))
216 const Stmt *S = N->getStmtForDiagnostics();
220 const LocationContext *NCtx = N->getLocationContext();
221 PathDiagnosticLocation L =
222 PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx);
223 if (!L.isValid() || !L.asLocation().isValid())
226 return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here");