| 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 |
} |