1351280Sdim//=== Taint.cpp - Taint tracking and basic propagation rules. ------*- C++ -*-// 2351280Sdim// 3351280Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351280Sdim// See https://llvm.org/LICENSE.txt for license information. 5351280Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351280Sdim// 7351280Sdim//===----------------------------------------------------------------------===// 8351280Sdim// 9351280Sdim// Defines basic, non-domain-specific mechanisms for tracking tainted values. 10351280Sdim// 11351280Sdim//===----------------------------------------------------------------------===// 12351280Sdim 13351280Sdim#include "Taint.h" 14351280Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 15351280Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 16351280Sdim 17351280Sdimusing namespace clang; 18351280Sdimusing namespace ento; 19351280Sdimusing namespace taint; 20351280Sdim 21351280Sdim// Fully tainted symbols. 22351280SdimREGISTER_MAP_WITH_PROGRAMSTATE(TaintMap, SymbolRef, TaintTagType) 23351280Sdim 24351280Sdim// Partially tainted symbols. 25351280SdimREGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(TaintedSubRegions, const SubRegion *, 26351280Sdim TaintTagType) 27351280SdimREGISTER_MAP_WITH_PROGRAMSTATE(DerivedSymTaint, SymbolRef, TaintedSubRegions) 28351280Sdim 29351280Sdimvoid taint::printTaint(ProgramStateRef State, raw_ostream &Out, const char *NL, 30351280Sdim const char *Sep) { 31351280Sdim TaintMapTy TM = State->get<TaintMap>(); 32351280Sdim 33351280Sdim if (!TM.isEmpty()) 34351280Sdim Out << "Tainted symbols:" << NL; 35351280Sdim 36351280Sdim for (const auto &I : TM) 37351280Sdim Out << I.first << " : " << I.second << NL; 38351280Sdim} 39351280Sdim 40360784Sdimvoid dumpTaint(ProgramStateRef State) { printTaint(State, llvm::errs()); } 41351280Sdim 42351280SdimProgramStateRef taint::addTaint(ProgramStateRef State, const Stmt *S, 43351280Sdim const LocationContext *LCtx, 44351280Sdim TaintTagType Kind) { 45351280Sdim return addTaint(State, State->getSVal(S, LCtx), Kind); 46351280Sdim} 47351280Sdim 48351280SdimProgramStateRef taint::addTaint(ProgramStateRef State, SVal V, 49351280Sdim TaintTagType Kind) { 50351280Sdim SymbolRef Sym = V.getAsSymbol(); 51351280Sdim if (Sym) 52351280Sdim return addTaint(State, Sym, Kind); 53351280Sdim 54351280Sdim // If the SVal represents a structure, try to mass-taint all values within the 55351280Sdim // structure. For now it only works efficiently on lazy compound values that 56351280Sdim // were conjured during a conservative evaluation of a function - either as 57351280Sdim // return values of functions that return structures or arrays by value, or as 58351280Sdim // values of structures or arrays passed into the function by reference, 59351280Sdim // directly or through pointer aliasing. Such lazy compound values are 60351280Sdim // characterized by having exactly one binding in their captured store within 61351280Sdim // their parent region, which is a conjured symbol default-bound to the base 62351280Sdim // region of the parent region. 63351280Sdim if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) { 64351280Sdim if (Optional<SVal> binding = 65360784Sdim State->getStateManager().getStoreManager().getDefaultBinding( 66360784Sdim *LCV)) { 67351280Sdim if (SymbolRef Sym = binding->getAsSymbol()) 68351280Sdim return addPartialTaint(State, Sym, LCV->getRegion(), Kind); 69351280Sdim } 70351280Sdim } 71351280Sdim 72351280Sdim const MemRegion *R = V.getAsRegion(); 73351280Sdim return addTaint(State, R, Kind); 74351280Sdim} 75351280Sdim 76351280SdimProgramStateRef taint::addTaint(ProgramStateRef State, const MemRegion *R, 77351280Sdim TaintTagType Kind) { 78351280Sdim if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 79351280Sdim return addTaint(State, SR->getSymbol(), Kind); 80351280Sdim return State; 81351280Sdim} 82351280Sdim 83351280SdimProgramStateRef taint::addTaint(ProgramStateRef State, SymbolRef Sym, 84351280Sdim TaintTagType Kind) { 85351280Sdim // If this is a symbol cast, remove the cast before adding the taint. Taint 86351280Sdim // is cast agnostic. 87351280Sdim while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) 88351280Sdim Sym = SC->getOperand(); 89351280Sdim 90351280Sdim ProgramStateRef NewState = State->set<TaintMap>(Sym, Kind); 91351280Sdim assert(NewState); 92351280Sdim return NewState; 93351280Sdim} 94351280Sdim 95360784SdimProgramStateRef taint::removeTaint(ProgramStateRef State, SVal V) { 96360784Sdim SymbolRef Sym = V.getAsSymbol(); 97360784Sdim if (Sym) 98360784Sdim return removeTaint(State, Sym); 99360784Sdim 100360784Sdim const MemRegion *R = V.getAsRegion(); 101360784Sdim return removeTaint(State, R); 102360784Sdim} 103360784Sdim 104360784SdimProgramStateRef taint::removeTaint(ProgramStateRef State, const MemRegion *R) { 105360784Sdim if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 106360784Sdim return removeTaint(State, SR->getSymbol()); 107360784Sdim return State; 108360784Sdim} 109360784Sdim 110360784SdimProgramStateRef taint::removeTaint(ProgramStateRef State, SymbolRef Sym) { 111360784Sdim // If this is a symbol cast, remove the cast before adding the taint. Taint 112360784Sdim // is cast agnostic. 113360784Sdim while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) 114360784Sdim Sym = SC->getOperand(); 115360784Sdim 116360784Sdim ProgramStateRef NewState = State->remove<TaintMap>(Sym); 117360784Sdim assert(NewState); 118360784Sdim return NewState; 119360784Sdim} 120360784Sdim 121351280SdimProgramStateRef taint::addPartialTaint(ProgramStateRef State, 122351280Sdim SymbolRef ParentSym, 123351280Sdim const SubRegion *SubRegion, 124351280Sdim TaintTagType Kind) { 125351280Sdim // Ignore partial taint if the entire parent symbol is already tainted. 126351280Sdim if (const TaintTagType *T = State->get<TaintMap>(ParentSym)) 127351280Sdim if (*T == Kind) 128351280Sdim return State; 129351280Sdim 130351280Sdim // Partial taint applies if only a portion of the symbol is tainted. 131351280Sdim if (SubRegion == SubRegion->getBaseRegion()) 132351280Sdim return addTaint(State, ParentSym, Kind); 133351280Sdim 134351280Sdim const TaintedSubRegions *SavedRegs = State->get<DerivedSymTaint>(ParentSym); 135351280Sdim TaintedSubRegions::Factory &F = State->get_context<TaintedSubRegions>(); 136351280Sdim TaintedSubRegions Regs = SavedRegs ? *SavedRegs : F.getEmptyMap(); 137351280Sdim 138351280Sdim Regs = F.add(Regs, SubRegion, Kind); 139351280Sdim ProgramStateRef NewState = State->set<DerivedSymTaint>(ParentSym, Regs); 140351280Sdim assert(NewState); 141351280Sdim return NewState; 142351280Sdim} 143351280Sdim 144351280Sdimbool taint::isTainted(ProgramStateRef State, const Stmt *S, 145351280Sdim const LocationContext *LCtx, TaintTagType Kind) { 146351280Sdim SVal val = State->getSVal(S, LCtx); 147351280Sdim return isTainted(State, val, Kind); 148351280Sdim} 149351280Sdim 150351280Sdimbool taint::isTainted(ProgramStateRef State, SVal V, TaintTagType Kind) { 151351280Sdim if (const SymExpr *Sym = V.getAsSymExpr()) 152351280Sdim return isTainted(State, Sym, Kind); 153351280Sdim if (const MemRegion *Reg = V.getAsRegion()) 154351280Sdim return isTainted(State, Reg, Kind); 155351280Sdim return false; 156351280Sdim} 157351280Sdim 158351280Sdimbool taint::isTainted(ProgramStateRef State, const MemRegion *Reg, 159351280Sdim TaintTagType K) { 160351280Sdim if (!Reg) 161351280Sdim return false; 162351280Sdim 163351280Sdim // Element region (array element) is tainted if either the base or the offset 164351280Sdim // are tainted. 165351280Sdim if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 166351280Sdim return isTainted(State, ER->getSuperRegion(), K) || 167351280Sdim isTainted(State, ER->getIndex(), K); 168351280Sdim 169351280Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 170351280Sdim return isTainted(State, SR->getSymbol(), K); 171351280Sdim 172351280Sdim if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 173351280Sdim return isTainted(State, ER->getSuperRegion(), K); 174351280Sdim 175351280Sdim return false; 176351280Sdim} 177351280Sdim 178351280Sdimbool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) { 179351280Sdim if (!Sym) 180351280Sdim return false; 181351280Sdim 182351280Sdim // Traverse all the symbols this symbol depends on to see if any are tainted. 183351280Sdim for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), 184360784Sdim SE = Sym->symbol_end(); 185360784Sdim SI != SE; ++SI) { 186351280Sdim if (!isa<SymbolData>(*SI)) 187351280Sdim continue; 188351280Sdim 189351280Sdim if (const TaintTagType *Tag = State->get<TaintMap>(*SI)) { 190351280Sdim if (*Tag == Kind) 191351280Sdim return true; 192351280Sdim } 193351280Sdim 194351280Sdim if (const auto *SD = dyn_cast<SymbolDerived>(*SI)) { 195351280Sdim // If this is a SymbolDerived with a tainted parent, it's also tainted. 196351280Sdim if (isTainted(State, SD->getParentSymbol(), Kind)) 197351280Sdim return true; 198351280Sdim 199351280Sdim // If this is a SymbolDerived with the same parent symbol as another 200351280Sdim // tainted SymbolDerived and a region that's a sub-region of that tainted 201351280Sdim // symbol, it's also tainted. 202351280Sdim if (const TaintedSubRegions *Regs = 203351280Sdim State->get<DerivedSymTaint>(SD->getParentSymbol())) { 204351280Sdim const TypedValueRegion *R = SD->getRegion(); 205351280Sdim for (auto I : *Regs) { 206351280Sdim // FIXME: The logic to identify tainted regions could be more 207351280Sdim // complete. For example, this would not currently identify 208351280Sdim // overlapping fields in a union as tainted. To identify this we can 209351280Sdim // check for overlapping/nested byte offsets. 210351280Sdim if (Kind == I.second && R->isSubRegionOf(I.first)) 211351280Sdim return true; 212351280Sdim } 213351280Sdim } 214351280Sdim } 215351280Sdim 216351280Sdim // If memory region is tainted, data is also tainted. 217351280Sdim if (const auto *SRV = dyn_cast<SymbolRegionValue>(*SI)) { 218351280Sdim if (isTainted(State, SRV->getRegion(), Kind)) 219351280Sdim return true; 220351280Sdim } 221351280Sdim 222351280Sdim // If this is a SymbolCast from a tainted value, it's also tainted. 223351280Sdim if (const auto *SC = dyn_cast<SymbolCast>(*SI)) { 224351280Sdim if (isTainted(State, SC->getOperand(), Kind)) 225351280Sdim return true; 226351280Sdim } 227351280Sdim } 228351280Sdim 229351280Sdim return false; 230351280Sdim} 231351280Sdim 232360784SdimPathDiagnosticPieceRef TaintBugVisitor::VisitNode(const ExplodedNode *N, 233360784Sdim BugReporterContext &BRC, 234360784Sdim PathSensitiveBugReport &BR) { 235351280Sdim 236351280Sdim // Find the ExplodedNode where the taint was first introduced 237351280Sdim if (!isTainted(N->getState(), V) || 238351280Sdim isTainted(N->getFirstPred()->getState(), V)) 239351280Sdim return nullptr; 240351280Sdim 241360784Sdim const Stmt *S = N->getStmtForDiagnostics(); 242351280Sdim if (!S) 243351280Sdim return nullptr; 244351280Sdim 245351280Sdim const LocationContext *NCtx = N->getLocationContext(); 246351280Sdim PathDiagnosticLocation L = 247351280Sdim PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx); 248351280Sdim if (!L.isValid() || !L.asLocation().isValid()) 249351280Sdim return nullptr; 250351280Sdim 251351280Sdim return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here"); 252351280Sdim} 253