clang/lib/StaticAnalyzer/Checkers/Taint.cpp

   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   return !getTaintedSymbolsImpl(State, S, LCtx, Kind, /*ReturnFirstOnly=*/true)
 150               .empty();
 151 }
 152
 153 bool taint::isTainted(ProgramStateRef State, SVal V, TaintTagType Kind) {
 154   return !getTaintedSymbolsImpl(State, V, Kind, /*ReturnFirstOnly=*/true)
 155               .empty();
 156 }
 157
 158 bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,
 159                       TaintTagType K) {
 160   return !getTaintedSymbolsImpl(State, Reg, K, /*ReturnFirstOnly=*/true)
 161               .empty();
 162 }
 163
 164 bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {
 165   return !getTaintedSymbolsImpl(State, Sym, Kind, /*ReturnFirstOnly=*/true)
 166               .empty();
 167 }
 168
 169 std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State,
 170                                                 const Stmt *S,
 171                                                 const LocationContext *LCtx,
 172                                                 TaintTagType Kind) {
 173   return getTaintedSymbolsImpl(State, S, LCtx, Kind, /*ReturnFirstOnly=*/false);
 174 }
 175
 176 std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State, SVal V,
 177                                                 TaintTagType Kind) {
 178   return getTaintedSymbolsImpl(State, V, Kind, /*ReturnFirstOnly=*/false);
 179 }
 180
 181 std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State,
 182                                                 SymbolRef Sym,
 183                                                 TaintTagType Kind) {
 184   return getTaintedSymbolsImpl(State, Sym, Kind, /*ReturnFirstOnly=*/false);
 185 }
 186
 187 std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State,
 188                                                 const MemRegion *Reg,
 189                                                 TaintTagType Kind) {
 190   return getTaintedSymbolsImpl(State, Reg, Kind, /*ReturnFirstOnly=*/false);
 191 }
 192
 193 std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,
 194                                                     const Stmt *S,
 195                                                     const LocationContext *LCtx,
 196                                                     TaintTagType Kind,
 197                                                     bool returnFirstOnly) {
 198   SVal val = State->getSVal(S, LCtx);
 199   return getTaintedSymbolsImpl(State, val, Kind, returnFirstOnly);
 200 }
 201
 202 std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,
 203                                                     SVal V, TaintTagType Kind,
 204                                                     bool returnFirstOnly) {
 205   if (SymbolRef Sym = V.getAsSymbol())
 206     return getTaintedSymbolsImpl(State, Sym, Kind, returnFirstOnly);
 207   if (const MemRegion *Reg = V.getAsRegion())
 208     return getTaintedSymbolsImpl(State, Reg, Kind, returnFirstOnly);
 209   return {};
 210 }
 211
 212 std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,
 213                                                     const MemRegion *Reg,
 214                                                     TaintTagType K,
 215                                                     bool returnFirstOnly) {
 216   std::vector<SymbolRef> TaintedSymbols;
 217   if (!Reg)
 218     return TaintedSymbols;
 219   // Element region (array element) is tainted if either the base or the offset
 220   // are tainted.
 221   if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) {
 222     std::vector<SymbolRef> TaintedIndex =
 223         getTaintedSymbolsImpl(State, ER->getIndex(), K, returnFirstOnly);
 224     llvm::append_range(TaintedSymbols, TaintedIndex);
 225     if (returnFirstOnly && !TaintedSymbols.empty())
 226       return TaintedSymbols; // return early if needed
 227     std::vector<SymbolRef> TaintedSuperRegion =
 228         getTaintedSymbolsImpl(State, ER->getSuperRegion(), K, returnFirstOnly);
 229     llvm::append_range(TaintedSymbols, TaintedSuperRegion);
 230     if (returnFirstOnly && !TaintedSymbols.empty())
 231       return TaintedSymbols; // return early if needed
 232   }
 233
 234   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) {
 235     std::vector<SymbolRef> TaintedRegions =
 236         getTaintedSymbolsImpl(State, SR->getSymbol(), K, returnFirstOnly);
 237     llvm::append_range(TaintedSymbols, TaintedRegions);
 238     if (returnFirstOnly && !TaintedSymbols.empty())
 239       return TaintedSymbols; // return early if needed
 240   }
 241
 242   if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) {
 243     std::vector<SymbolRef> TaintedSubRegions =
 244         getTaintedSymbolsImpl(State, ER->getSuperRegion(), K, returnFirstOnly);
 245     llvm::append_range(TaintedSymbols, TaintedSubRegions);
 246     if (returnFirstOnly && !TaintedSymbols.empty())
 247       return TaintedSymbols; // return early if needed
 248   }
 249
 250   return TaintedSymbols;
 251 }
 252
 253 std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,
 254                                                     SymbolRef Sym,
 255                                                     TaintTagType Kind,
 256                                                     bool returnFirstOnly) {
 257   std::vector<SymbolRef> TaintedSymbols;
 258   if (!Sym)
 259     return TaintedSymbols;
 260
 261   // Traverse all the symbols this symbol depends on to see if any are tainted.
 262   for (SymbolRef SubSym : Sym->symbols()) {
 263     if (!isa<SymbolData>(SubSym))
 264       continue;
 265
 266     if (const TaintTagType *Tag = State->get<TaintMap>(SubSym)) {
 267       if (*Tag == Kind) {
 268         TaintedSymbols.push_back(SubSym);
 269         if (returnFirstOnly)
 270           return TaintedSymbols; // return early if needed
 271       }
 272     }
 273
 274     if (const auto *SD = dyn_cast<SymbolDerived>(SubSym)) {
 275       // If this is a SymbolDerived with a tainted parent, it's also tainted.
 276       std::vector<SymbolRef> TaintedParents = getTaintedSymbolsImpl(
 277           State, SD->getParentSymbol(), Kind, returnFirstOnly);
 278       llvm::append_range(TaintedSymbols, TaintedParents);
 279       if (returnFirstOnly && !TaintedSymbols.empty())
 280         return TaintedSymbols; // return early if needed
 281
 282       // If this is a SymbolDerived with the same parent symbol as another
 283       // tainted SymbolDerived and a region that's a sub-region of that
 284       // tainted symbol, it's also tainted.
 285       if (const TaintedSubRegions *Regs =
 286               State->get<DerivedSymTaint>(SD->getParentSymbol())) {
 287         const TypedValueRegion *R = SD->getRegion();
 288         for (auto I : *Regs) {
 289           // FIXME: The logic to identify tainted regions could be more
 290           // complete. For example, this would not currently identify
 291           // overlapping fields in a union as tainted. To identify this we can
 292           // check for overlapping/nested byte offsets.
 293           if (Kind == I.second && R->isSubRegionOf(I.first)) {
 294             TaintedSymbols.push_back(SD->getParentSymbol());
 295             if (returnFirstOnly && !TaintedSymbols.empty())
 296               return TaintedSymbols; // return early if needed
 297           }
 298         }
 299       }
 300     }
 301
 302     // If memory region is tainted, data is also tainted.
 303     if (const auto *SRV = dyn_cast<SymbolRegionValue>(SubSym)) {
 304       std::vector<SymbolRef> TaintedRegions =
 305           getTaintedSymbolsImpl(State, SRV->getRegion(), Kind, returnFirstOnly);
 306       llvm::append_range(TaintedSymbols, TaintedRegions);
 307       if (returnFirstOnly && !TaintedSymbols.empty())
 308         return TaintedSymbols; // return early if needed
 309     }
 310
 311     // If this is a SymbolCast from a tainted value, it's also tainted.
 312     if (const auto *SC = dyn_cast<SymbolCast>(SubSym)) {
 313       std::vector<SymbolRef> TaintedCasts =
 314           getTaintedSymbolsImpl(State, SC->getOperand(), Kind, returnFirstOnly);
 315       llvm::append_range(TaintedSymbols, TaintedCasts);
 316       if (returnFirstOnly && !TaintedSymbols.empty())
 317         return TaintedSymbols; // return early if needed
 318     }
 319   }
 320   return TaintedSymbols;
 321 }