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 18 using namespace clang; 19 using namespace ento; 20 using namespace taint; 21 22 // Fully tainted symbols. 23 REGISTER_MAP_WITH_PROGRAMSTATE(TaintMap, SymbolRef, TaintTagType) 24 25 // Partially tainted symbols. 26 REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(TaintedSubRegions, const SubRegion *, 27 TaintTagType) 28 REGISTER_MAP_WITH_PROGRAMSTATE(DerivedSymTaint, SymbolRef, TaintedSubRegions) 29 30 void 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 41 void taint::dumpTaint(ProgramStateRef State) { 42 printTaint(State, llvm::errs()); 43 } 44 45 ProgramStateRef 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 51 ProgramStateRef 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 79 ProgramStateRef 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 86 ProgramStateRef 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 98 ProgramStateRef 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 107 ProgramStateRef 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 113 ProgramStateRef 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 124 ProgramStateRef 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 147 bool 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 153 bool 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 161 bool 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 181 bool 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 235 PathDiagnosticPieceRef 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