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.
REGISTER_MAP_WITH_PROGRAMSTATE(TaintMap,SymbolRef,TaintTagType)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 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
dumpTaint(ProgramStateRef State)40 void dumpTaint(ProgramStateRef State) {
41 printTaint(State, llvm::errs());
42 }
43
addTaint(ProgramStateRef State,const Stmt * S,const LocationContext * LCtx,TaintTagType Kind)44 ProgramStateRef taint::addTaint(ProgramStateRef State, const Stmt *S,
45 const LocationContext *LCtx,
46 TaintTagType Kind) {
47 return addTaint(State, State->getSVal(S, LCtx), Kind);
48 }
49
addTaint(ProgramStateRef State,SVal V,TaintTagType Kind)50 ProgramStateRef taint::addTaint(ProgramStateRef State, SVal V,
51 TaintTagType Kind) {
52 SymbolRef Sym = V.getAsSymbol();
53 if (Sym)
54 return addTaint(State, Sym, Kind);
55
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);
71 }
72 }
73
74 const MemRegion *R = V.getAsRegion();
75 return addTaint(State, R, Kind);
76 }
77
addTaint(ProgramStateRef State,const MemRegion * R,TaintTagType Kind)78 ProgramStateRef taint::addTaint(ProgramStateRef State, const MemRegion *R,
79 TaintTagType Kind) {
80 if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
81 return addTaint(State, SR->getSymbol(), Kind);
82 return State;
83 }
84
addTaint(ProgramStateRef State,SymbolRef Sym,TaintTagType Kind)85 ProgramStateRef taint::addTaint(ProgramStateRef State, SymbolRef Sym,
86 TaintTagType Kind) {
87 // If this is a symbol cast, remove the cast before adding the taint. Taint
88 // is cast agnostic.
89 while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
90 Sym = SC->getOperand();
91
92 ProgramStateRef NewState = State->set<TaintMap>(Sym, Kind);
93 assert(NewState);
94 return NewState;
95 }
96
addPartialTaint(ProgramStateRef State,SymbolRef ParentSym,const SubRegion * SubRegion,TaintTagType Kind)97 ProgramStateRef taint::addPartialTaint(ProgramStateRef State,
98 SymbolRef ParentSym,
99 const SubRegion *SubRegion,
100 TaintTagType Kind) {
101 // Ignore partial taint if the entire parent symbol is already tainted.
102 if (const TaintTagType *T = State->get<TaintMap>(ParentSym))
103 if (*T == Kind)
104 return State;
105
106 // Partial taint applies if only a portion of the symbol is tainted.
107 if (SubRegion == SubRegion->getBaseRegion())
108 return addTaint(State, ParentSym, Kind);
109
110 const TaintedSubRegions *SavedRegs = State->get<DerivedSymTaint>(ParentSym);
111 TaintedSubRegions::Factory &F = State->get_context<TaintedSubRegions>();
112 TaintedSubRegions Regs = SavedRegs ? *SavedRegs : F.getEmptyMap();
113
114 Regs = F.add(Regs, SubRegion, Kind);
115 ProgramStateRef NewState = State->set<DerivedSymTaint>(ParentSym, Regs);
116 assert(NewState);
117 return NewState;
118 }
119
isTainted(ProgramStateRef State,const Stmt * S,const LocationContext * LCtx,TaintTagType Kind)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);
124 }
125
isTainted(ProgramStateRef State,SVal V,TaintTagType 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);
131 return false;
132 }
133
isTainted(ProgramStateRef State,const MemRegion * Reg,TaintTagType K)134 bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,
135 TaintTagType K) {
136 if (!Reg)
137 return false;
138
139 // Element region (array element) is tainted if either the base or the offset
140 // are tainted.
141 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
142 return isTainted(State, ER->getSuperRegion(), K) ||
143 isTainted(State, ER->getIndex(), K);
144
145 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
146 return isTainted(State, SR->getSymbol(), K);
147
148 if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
149 return isTainted(State, ER->getSuperRegion(), K);
150
151 return false;
152 }
153
isTainted(ProgramStateRef State,SymbolRef Sym,TaintTagType Kind)154 bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {
155 if (!Sym)
156 return false;
157
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))
162 continue;
163
164 if (const TaintTagType *Tag = State->get<TaintMap>(*SI)) {
165 if (*Tag == Kind)
166 return true;
167 }
168
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))
172 return true;
173
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))
186 return true;
187 }
188 }
189 }
190
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))
194 return true;
195 }
196
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))
200 return true;
201 }
202 }
203
204 return false;
205 }
206
207 std::shared_ptr<PathDiagnosticPiece>
VisitNode(const ExplodedNode * N,BugReporterContext & BRC,BugReport & BR)208 TaintBugVisitor::VisitNode(const ExplodedNode *N, BugReporterContext &BRC,
209 BugReport &BR) {
210
211 // Find the ExplodedNode where the taint was first introduced
212 if (!isTainted(N->getState(), V) ||
213 isTainted(N->getFirstPred()->getState(), V))
214 return nullptr;
215
216 const Stmt *S = PathDiagnosticLocation::getStmt(N);
217 if (!S)
218 return nullptr;
219
220 const LocationContext *NCtx = N->getLocationContext();
221 PathDiagnosticLocation L =
222 PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx);
223 if (!L.isValid() || !L.asLocation().isValid())
224 return nullptr;
225
226 return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here");
227 }
228