[analyzer] NFC: Replace Taint API with a usual inter-checker communication API?

[NoQ]

Summary

Given how much effort @boga95 is spending on the taint checker, i decided to undig my effort to remove the whole taint API business from the ProgramState class and instead implement it as our usual, modern inter-checker communication API.

Modern as in "putting all such stuff into the ProgramState class clearly doesn't scale, but we still didn't come up with anything better, so let's just put it in the header and see if a better design suddenly emerges in the future after we do it a few hundred times". In other words, this was the plan that is part of the even-more-long-term plan of completely deprecating the void*-based Generic Data Map in favor of something that the analyzer core could introspect and help checkers keep track of, which would reduce boilerplate and make developing checkers easier.

The patch is rebased on top of the current master, but most likely conflicts with @boga95's latest patches. I'm sorry i didn't do this quickly enough, but better late than never, i suppose. I do not insist on this design, but i believe it looks much cleaner.

[NoQ]

(whoops sry nvm typo in reviewer list)

[Charusso]

I like the idea to put connecting stuff together in the same file to create more understandable code. LGTM.

clang/lib/StaticAnalyzer/Checkers/Taint.h

8

Outdated header-blurb.

81

We left the ProgramState::dump()' context so what about just dump()`?

[boga95]

Thanks, it will make my changes more cleaner.

[NoQ]

Address comments. Fix printing taint in state dumps.

clang/lib/StaticAnalyzer/Checkers/Taint.h

8

Whooooooooooops! Thanks!!

81

I'm doing using namespace taint; everywhere, so that'd make the code look like dump(State) which would look quite ambiguous to a human. Additionally, this function only needs to be called once, so it's not a problem if it's a bit long.

Also, wait, i didn't really call it even once. I.e., i forgot to implement GenericTaintChecker::printState() to print taint (now that it's not state-specific, there must be a checker responsible for this, and i'm casting my vote for GenericTaintChecker out of 1 potential candidates). Let me fix it.

[NoQ]

Add a test for taint dumps.

[Szelethus]

"putting all such stuff into the ProgramState class clearly doesn't scale, but we still didn't come up with anything better, so let's just put it in the header and see if a better design suddenly emerges in the future after we do it a few hundred times"

Now that we have a maintainer who will dedicate a lot of effort into taint analysis, that might just happen :) For the time being though, I agree, this is much cleaner.

It would be great to land this as soon as you're comfortable with it, in order not to block @boga95's work.

[Szelethus]

Also, you might as well clang-format the new files, since we already messed with git blame.

[NoQ]

Cleaned up formatting a bit.

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

public:
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {}
 
   std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *Succ,
                                                  BugReporterContext &BRC,
                                                  BugReport &BR) override;
 };
 
-/// The bug visitor prints a diagnostic message at the location where a given
-/// variable was tainted.
-class TaintBugVisitor final : public BugReporterVisitor {
-private:
-  const SVal V;
-
-public:
-  TaintBugVisitor(const SVal V) : V(V) {}
-  void Profile(llvm::FoldingSetNodeID &ID) const override { ID.Add(V); }
-
-  std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
-                                                 BugReporterContext &BRC,
-                                                 BugReport &BR) override;
-};
 
 /// The bug visitor will walk all the nodes in a path and collect all the
 /// constraints. When it reaches the root node, will create a refutation
 /// manager and check if the constraints are satisfiable
 class FalsePositiveRefutationBRVisitor final : public BugReporterVisitor {
 private:
   /// Holds the constraints in a given path
   ConstraintRangeTy Constraints;

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h

 
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableMap.h"
 #include "llvm/Support/Allocator.h"
 #include <utility>
 
 namespace llvm {
 class APSInt;
 }
 
 namespace clang {
 class ASTContext;
 
 namespace ento {
 
 class AnalysisManager;
 class CallEvent;
 class CallEventManager;
 
 typedef std::unique_ptr<ConstraintManager>(*ConstraintManagerCreator)(
     ProgramStateManager &, SubEngine *);
 typedef std::unique_ptr<StoreManager>(*StoreManagerCreator)(
     ProgramStateManager &);
-typedef llvm::ImmutableMap<const SubRegion*, TaintTagType> TaintedSubRegions;
 
 //===----------------------------------------------------------------------===//
 // ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState.
 //===----------------------------------------------------------------------===//
 
 template <typename T> struct ProgramStatePartialTrait;
 
 template <typename T> struct ProgramStateTrait {
public:
   /// MemRegions range using the provided SymbolVisitor.
   bool scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable,
                             SymbolVisitor &visitor) const;
 
   template <typename CB> CB scanReachableSymbols(SVal val) const;
   template <typename CB> CB
   scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable) const;
 
-  /// Create a new state in which the statement is marked as tainted.
-  LLVM_NODISCARD ProgramStateRef
-  addTaint(const Stmt *S, const LocationContext *LCtx,
-           TaintTagType Kind = TaintTagGeneric) const;
-
-  /// Create a new state in which the value is marked as tainted.
-  LLVM_NODISCARD ProgramStateRef
-  addTaint(SVal V, TaintTagType Kind = TaintTagGeneric) const;
-
-  /// Create a new state in which the symbol is marked as tainted.
-  LLVM_NODISCARD ProgramStateRef addTaint(SymbolRef S,
-                               TaintTagType Kind = TaintTagGeneric) const;
-
-  /// Create a new state in which the region symbol is marked as tainted.
-  LLVM_NODISCARD ProgramStateRef
-  addTaint(const MemRegion *R, TaintTagType Kind = TaintTagGeneric) const;
-
-  /// Create a new state in a which a sub-region of a given symbol is tainted.
-  /// This might be necessary when referring to regions that can not have an
-  /// individual symbol, e.g. if they are represented by the default binding of
-  /// a LazyCompoundVal.
-  LLVM_NODISCARD ProgramStateRef
-  addPartialTaint(SymbolRef ParentSym, const SubRegion *SubRegion,
-                  TaintTagType Kind = TaintTagGeneric) const;
-
-  /// Check if the statement is tainted in the current state.
-  bool isTainted(const Stmt *S, const LocationContext *LCtx,
-                 TaintTagType Kind = TaintTagGeneric) const;
-  bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const;
-  bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const;
-  bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const;
-
   //==---------------------------------------------------------------------==//
   // Accessing the Generic Data Map (GDM).
   //==---------------------------------------------------------------------==//
 
   void *const* FindGDM(void *K) const;
 
   template <typename T>
   LLVM_NODISCARD ProgramStateRef
bool contains(typename ProgramStateTrait<T>::key_type key) const {
     return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key);
   }
 
   // Pretty-printing.
   void print(raw_ostream &Out, const char *nl = "\n", const char *sep = "",
              const LocationContext *CurrentLC = nullptr) const;
   void printDOT(raw_ostream &Out,
                 const LocationContext *CurrentLC = nullptr) const;
-  void printTaint(raw_ostream &Out, const char *nl = "\n") const;
 
   void dump() const;
-  void dumpTaint() const;
 
 private:
   friend void ProgramStateRetain(const ProgramState *state);
   friend void ProgramStateRelease(const ProgramState *state);
 
   /// \sa invalidateValues()
   /// \sa invalidateRegions()
   ProgramStateRef
private:
   /// Eng - The SubEngine that owns this state manager.
   SubEngine *Eng; /* Can be null. */
 
   EnvironmentManager                   EnvMgr;
   std::unique_ptr<StoreManager>        StoreMgr;
   std::unique_ptr<ConstraintManager>   ConstraintMgr;
 
   ProgramState::GenericDataMap::Factory     GDMFactory;
-  TaintedSubRegions::Factory TSRFactory;
 
   typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy;
   GDMContextsTy GDMContexts;
 
   /// StateSet - FoldingSet containing all the states created for analyzing
   ///  a particular function.  This is used to unique states.
   llvm::FoldingSet<ProgramState> StateSet;
 

clang/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h

-//===- TaintManager.h - Managing taint --------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-//  This file provides APIs for adding, removing, querying symbol taint.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_TAINTMANAGER_H
-#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_TAINTMANAGER_H
-
-#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h"
-#include "llvm/ADT/ImmutableMap.h"
-
-namespace clang {
-namespace ento {
-
-/// The GDM component containing the tainted root symbols. We lazily infer the
-/// taint of the dependent symbols. Currently, this is a map from a symbol to
-/// tag kind. TODO: Should support multiple tag kinds.
-// FIXME: This does not use the nice trait macros because it must be accessible
-// from multiple translation units.
-struct TaintMap {};
-
-using TaintMapImpl = llvm::ImmutableMap<SymbolRef, TaintTagType>;
-
-template<> struct ProgramStateTrait<TaintMap>
-    :  public ProgramStatePartialTrait<TaintMapImpl> {
-  static void *GDMIndex();
-};
-
-/// The GDM component mapping derived symbols' parent symbols to their
-/// underlying regions. This is used to efficiently check whether a symbol is
-/// tainted when it represents a sub-region of a tainted symbol.
-struct DerivedSymTaint {};
-
-using DerivedSymTaintImpl = llvm::ImmutableMap<SymbolRef, TaintedSubRegions>;
-
-template<> struct ProgramStateTrait<DerivedSymTaint>
-    :  public ProgramStatePartialTrait<DerivedSymTaintImpl> {
-  static void *GDMIndex();
-};
-
-class TaintManager {
-  TaintManager() = default;
-};
-
-} // namespace ento
-} // namespace clang
-
-#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_TAINTMANAGER_H

clang/include/clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h

-//===- TaintTag.h - Path-sensitive "State" for tracking values --*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// Defines a set of taint tags. Several tags are used to differentiate kinds
-// of taint.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_TAINTTAG_H
-#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_TAINTTAG_H
-
-namespace clang {
-namespace ento {
-
-/// The type of taint, which helps to differentiate between different types of
-/// taint.
-using TaintTagType = unsigned;
-
-static const TaintTagType TaintTagGeneric = 0;
-
-} // namespace ento
-} // namespace clang
-
-#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_TAINTTAG_H

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

 //== ArrayBoundCheckerV2.cpp ------------------------------------*- C++ -*--==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines ArrayBoundCheckerV2, which is a path-sensitive check
 // which looks for an out-of-bound array element access.
 //
 //===----------------------------------------------------------------------===//
 
+#include "Taint.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/AST/CharUnits.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 class ArrayBoundCheckerV2 :
     public Checker<check::Location> {
   mutable std::unique_ptr<BuiltinBug> BT;
 
   enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted };
 
do {
 
     ProgramStateRef state_exceedsUpperBound, state_withinUpperBound;
     std::tie(state_exceedsUpperBound, state_withinUpperBound) =
       state->assume(*upperboundToCheck);
 
     // If we are under constrained and the index variables are tainted, report.
     if (state_exceedsUpperBound && state_withinUpperBound) {
       SVal ByteOffset = rawOffset.getByteOffset();
-      if (state->isTainted(ByteOffset)) {
+      if (isTainted(state, ByteOffset)) {
         reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted,
                   llvm::make_unique<TaintBugVisitor>(ByteOffset));
         return;
       }
     } else if (state_exceedsUpperBound) {
       // If we are constrained enough to definitely exceed the upper bound,
       // report.
       assert(!state_withinUpperBound);

clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   RetainCountChecker/RetainCountDiagnostics.cpp
   ReturnPointerRangeChecker.cpp
   ReturnUndefChecker.cpp
   RunLoopAutoreleaseLeakChecker.cpp
   SimpleStreamChecker.cpp
   StackAddrEscapeChecker.cpp
   StdLibraryFunctionsChecker.cpp
   StreamChecker.cpp
+  Taint.cpp
   TaintTesterChecker.cpp
   TestAfterDivZeroChecker.cpp
   TraversalChecker.cpp
   TrustNonnullChecker.cpp
   UndefBranchChecker.cpp
   UndefCapturedBlockVarChecker.cpp
   UndefResultChecker.cpp
   UndefinedArraySubscriptChecker.cpp

clang/lib/StaticAnalyzer/Checkers/DivZeroChecker.cpp

 //== DivZeroChecker.cpp - Division by zero checker --------------*- C++ -*--==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This defines DivZeroChecker, a builtin check in ExprEngine that performs
 // checks for division by zeros.
 //
 //===----------------------------------------------------------------------===//
 
+#include "Taint.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 class DivZeroChecker : public Checker< check::PreStmt<BinaryOperator> > {
   mutable std::unique_ptr<BuiltinBug> BT;
   void reportBug(const char *Msg, ProgramStateRef StateZero, CheckerContext &C,
                  std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const;
 
 public:
void DivZeroChecker::checkPreStmt(const BinaryOperator *B,
   std::tie(stateNotZero, stateZero) = CM.assumeDual(C.getState(), *DV);
 
   if (!stateNotZero) {
     assert(stateZero);
     reportBug("Division by zero", stateZero, C);
     return;
   }
 
-  bool TaintedD = C.getState()->isTainted(*DV);
+  bool TaintedD = isTainted(C.getState(), *DV);
   if ((stateNotZero && stateZero && TaintedD)) {
     reportBug("Division by a tainted value, possibly zero", stateZero, C,
-              llvm::make_unique<TaintBugVisitor>(*DV));
+              llvm::make_unique<taint::TaintBugVisitor>(*DV));
     return;
   }
 
   // If we get here, then the denom should not be zero. We abandon the implicit
   // zero denom case for now.
   C.addTransition(stateNotZero);
 }
 
 void ento::registerDivZeroChecker(CheckerManager &mgr) {
   mgr.registerChecker<DivZeroChecker>();
 }
 
 bool ento::shouldRegisterDivZeroChecker(const LangOptions &LO) {
   return true;
 }

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

 //== GenericTaintChecker.cpp ----------------------------------- -*- C++ -*--=//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This checker defines the attack surface for generic taint propagation.
 //
 // The taint information produced by it might be useful to other checkers. For
 // example, checkers should report errors which involve tainted data more
 // aggressively, even if the involved symbols are under constrained.
 //
 //===----------------------------------------------------------------------===//
+
+#include "Taint.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/AST/Attr.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include <climits>
 #include <initializer_list>
 #include <utility>
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 class GenericTaintChecker
     : public Checker<check::PostStmt<CallExpr>, check::PreStmt<CallExpr>> {
 public:
   static void *getTag() {
     static int Tag;
     return &Tag;
struct TaintPropagationRule {
     }
 
     bool isDestinationArgument(unsigned ArgNum) const {
       return (llvm::find(DstArgs, ArgNum) != DstArgs.end());
     }
 
     static bool isTaintedOrPointsToTainted(const Expr *E, ProgramStateRef State,
                                            CheckerContext &C) {
-      if (State->isTainted(E, C.getLocationContext()) || isStdin(E, C))
+      if (isTainted(State, E, C.getLocationContext()) || isStdin(E, C))
         return true;
 
       if (!E->getType().getTypePtr()->isPointerType())
         return false;
 
       Optional<SVal> V = getPointedToSVal(C, E);
-      return (V && State->isTainted(*V));
+      return (V && isTainted(State, *V));
     }
 
     /// Pre-process a function which propagates taint according to the
     /// taint rule.
     ProgramStateRef process(const CallExpr *CE, CheckerContext &C) const;
 
     // Functions for custom taintedness propagation.
     static bool postSocket(bool IsTainted, const CallExpr *CE,
bool GenericTaintChecker::propagateFromPre(const CallExpr *CE,
   // stored in the state as TaintArgsOnPostVisit set.
   TaintArgsOnPostVisitTy TaintArgs = State->get<TaintArgsOnPostVisit>();
   if (TaintArgs.isEmpty())
     return false;
 
   for (unsigned ArgNum : TaintArgs) {
     // Special handling for the tainted return value.
     if (ArgNum == ReturnValueIndex) {
-      State = State->addTaint(CE, C.getLocationContext());
+      State = addTaint(State, CE, C.getLocationContext());
       continue;
     }
 
     // The arguments are pointer arguments. The data they are pointing at is
     // tainted after the call.
     if (CE->getNumArgs() < (ArgNum + 1))
       return false;
     const Expr *Arg = CE->getArg(ArgNum);
     Optional<SVal> V = getPointedToSVal(C, Arg);
     if (V)
-      State = State->addTaint(*V);
+      State = addTaint(State, *V);
   }
 
   // Clear up the taint info from the state.
   State = State->remove<TaintArgsOnPostVisit>();
 
   if (State != C.getState()) {
     C.addTransition(State);
     return true;
bool GenericTaintChecker::generateReportIfTainted(const Expr *E,
                                                   const char Msg[],
                                                   CheckerContext &C) const {
   assert(E);
 
   // Check for taint.
   ProgramStateRef State = C.getState();
   Optional<SVal> PointedToSVal = getPointedToSVal(C, E);
   SVal TaintedSVal;
-  if (PointedToSVal && State->isTainted(*PointedToSVal))
+  if (PointedToSVal && isTainted(State, *PointedToSVal))
     TaintedSVal = *PointedToSVal;
-  else if (State->isTainted(E, C.getLocationContext()))
+  else if (isTainted(State, E, C.getLocationContext()))
     TaintedSVal = C.getSVal(E);
   else
     return false;
 
   // Generate diagnostic.
   if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
     initBugType();
     auto report = llvm::make_unique<BugReport>(*BT, Msg, N);

clang/lib/StaticAnalyzer/Checkers/Taint.h

+//=== Taint.h - Taint tracking and basic propagation rules. --------*- C++ -*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines basic, non-domain-specific mechanisms for tracking tainted values.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_TAINT_H
+#define LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_TAINT_H
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h"
+
+namespace clang {
+namespace ento {
+namespace taint {
+
+/// The type of taint, which helps to differentiate between different types of
+/// taint.
+using TaintTagType = unsigned;
+
+static constexpr TaintTagType TaintTagGeneric = 0;
+
+/// Create a new state in which the value of the statement is marked as tainted.
+LLVM_NODISCARD ProgramStateRef
+addTaint(ProgramStateRef State, const Stmt *S, const LocationContext *LCtx,
+         TaintTagType Kind = TaintTagGeneric);
+
+/// Create a new state in which the value is marked as tainted.
+LLVM_NODISCARD ProgramStateRef
+addTaint(ProgramStateRef State, SVal V,
+         TaintTagType Kind = TaintTagGeneric);
+
+/// Create a new state in which the symbol is marked as tainted.
+LLVM_NODISCARD ProgramStateRef
+addTaint(ProgramStateRef State, SymbolRef Sym,
+         TaintTagType Kind = TaintTagGeneric);
+
+/// Create a new state in which the pointer represented by the region
+/// is marked as tainted.
+LLVM_NODISCARD ProgramStateRef
+addTaint(ProgramStateRef State, const MemRegion *R,
+         TaintTagType Kind = TaintTagGeneric);
+
+/// Create a new state in a which a sub-region of a given symbol is tainted.
+/// This might be necessary when referring to regions that can not have an
+/// individual symbol, e.g. if they are represented by the default binding of
+/// a LazyCompoundVal.
+LLVM_NODISCARD ProgramStateRef
+addPartialTaint(ProgramStateRef State,
+                SymbolRef ParentSym, const SubRegion *SubRegion,
+                TaintTagType Kind = TaintTagGeneric);
+
+/// Check if the statement has a tainted value in the given state.
+bool isTainted(ProgramStateRef State, const Stmt *S,
+               const LocationContext *LCtx,
+               TaintTagType Kind = TaintTagGeneric);
+
+/// Check if the value is tainted in the given state.
+bool isTainted(ProgramStateRef State, SVal V,
+               TaintTagType Kind = TaintTagGeneric);
+
+/// Check if the symbol is tainted in the given state.
+bool isTainted(ProgramStateRef State, SymbolRef Sym,
+               TaintTagType Kind = TaintTagGeneric);
+
+/// Check if the pointer represented by the region is tainted in the given
+/// state.
+bool isTainted(ProgramStateRef State, const MemRegion *Reg,
+               TaintTagType Kind = TaintTagGeneric);
+
+void printTaint(ProgramStateRef State, raw_ostream &Out, const char *nl = "\n",
+                const char *sep = "");
+
+void dumpTaint(ProgramStateRef State);
+
+/// The bug visitor prints a diagnostic message at the location where a given
+/// variable was tainted.
+class TaintBugVisitor final : public BugReporterVisitor {
+private:
+  const SVal V;
+
+public:
+  TaintBugVisitor(const SVal V) : V(V) {}
+  void Profile(llvm::FoldingSetNodeID &ID) const override { ID.Add(V); }
+
+  std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
+                                                 BugReporterContext &BRC,
+                                                 BugReport &BR) override;
+};
+
+} // namespace taint
+} // namespace ento
+} // namespace clang
+
+#endif
+

clang/lib/StaticAnalyzer/Checkers/Taint.cpp

+//=== Taint.cpp - Taint tracking and basic propagation rules. ------*- C++ -*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines basic, non-domain-specific mechanisms for tracking tainted values.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
+#include "Taint.h"
+
+using namespace clang;
+using namespace ento;
+using namespace taint;
+
+// Fully tainted symbols.
+REGISTER_MAP_WITH_PROGRAMSTATE(TaintMap, SymbolRef, TaintTagType)
+
+// Partially tainted symbols.
+REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(TaintedSubRegions,
+                                       const SubRegion *, TaintTagType);
+REGISTER_MAP_WITH_PROGRAMSTATE(DerivedSymTaint, SymbolRef, TaintedSubRegions)
+
+void taint::printTaint(ProgramStateRef State, raw_ostream &Out, const char *NL,
+                       const char *Sep) {
+  TaintMapTy TM = State->get<TaintMap>();
+
+  if (!TM.isEmpty())
+    Out <<"Tainted symbols:" << NL;
+
+  for (const auto &I : TM)
+    Out << I.first << " : " << I.second << NL;
+}
+
+void dumpTaint(ProgramStateRef State) {
+  printTaint(State, llvm::errs());
+}
+
+ProgramStateRef taint::addTaint(ProgramStateRef State, const Stmt *S,
+                                const LocationContext *LCtx,
+                                TaintTagType Kind) {
+  return addTaint(State, State->getSVal(S, LCtx), Kind);
+}
+
+ProgramStateRef taint::addTaint(ProgramStateRef State, SVal V,
+                                TaintTagType Kind) {
+  SymbolRef Sym = V.getAsSymbol();
+  if (Sym)
+    return addTaint(State, Sym, Kind);
+
+  // If the SVal represents a structure, try to mass-taint all values within the
+  // structure. For now it only works efficiently on lazy compound values that
+  // were conjured during a conservative evaluation of a function - either as
+  // return values of functions that return structures or arrays by value, or as
+  // values of structures or arrays passed into the function by reference,
+  // directly or through pointer aliasing. Such lazy compound values are
+  // characterized by having exactly one binding in their captured store within
+  // their parent region, which is a conjured symbol default-bound to the base
+  // region of the parent region.
+  if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) {
+    if (Optional<SVal> binding =
+            State->getStateManager().getStoreManager()
+                                    .getDefaultBinding(*LCV)) {
+      if (SymbolRef Sym = binding->getAsSymbol())
+        return addPartialTaint(State, Sym, LCV->getRegion(), Kind);
+    }
+  }
+
+  const MemRegion *R = V.getAsRegion();
+  return addTaint(State, R, Kind);
+}
+
+ProgramStateRef taint::addTaint(ProgramStateRef State, const MemRegion *R,
+                                TaintTagType Kind) {
+  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
+    return addTaint(State, SR->getSymbol(), Kind);
+  return State;
+}
+
+ProgramStateRef taint::addTaint(ProgramStateRef State, SymbolRef Sym,
+                                TaintTagType Kind) {
+  // If this is a symbol cast, remove the cast before adding the taint. Taint
+  // is cast agnostic.
+  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
+    Sym = SC->getOperand();
+
+  ProgramStateRef NewState = State->set<TaintMap>(Sym, Kind);
+  assert(NewState);
+  return NewState;
+}
+
+ProgramStateRef taint::addPartialTaint(ProgramStateRef State,
+                                       SymbolRef ParentSym,
+                                       const SubRegion *SubRegion,
+                                       TaintTagType Kind) {
+  // Ignore partial taint if the entire parent symbol is already tainted.
+  if (const TaintTagType *T = State->get<TaintMap>(ParentSym))
+    if (*T == Kind)
+      return State;
+
+  // Partial taint applies if only a portion of the symbol is tainted.
+  if (SubRegion == SubRegion->getBaseRegion())
+    return addTaint(State, ParentSym, Kind);
+
+  const TaintedSubRegions *SavedRegs = State->get<DerivedSymTaint>(ParentSym);
+  TaintedSubRegions::Factory &F = State->get_context<TaintedSubRegions>();
+  TaintedSubRegions Regs = SavedRegs ? *SavedRegs : F.getEmptyMap();
+
+  Regs = F.add(Regs, SubRegion, Kind);
+  ProgramStateRef NewState = State->set<DerivedSymTaint>(ParentSym, Regs);
+  assert(NewState);
+  return NewState;
+}
+
+bool taint::isTainted(ProgramStateRef State, const Stmt *S,
+                      const LocationContext *LCtx, TaintTagType Kind) {
+  SVal val = State->getSVal(S, LCtx);
+  return isTainted(State, val, Kind);
+}
+
+bool taint::isTainted(ProgramStateRef State, SVal V, TaintTagType Kind) {
+  if (const SymExpr *Sym = V.getAsSymExpr())
+    return isTainted(State, Sym, Kind);
+  if (const MemRegion *Reg = V.getAsRegion())
+    return isTainted(State, Reg, Kind);
+  return false;
+}
+
+bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,
+                      TaintTagType K) {
+  if (!Reg)
+    return false;
+
+  // Element region (array element) is tainted if either the base or the offset
+  // are tainted.
+  if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
+    return isTainted(State, ER->getSuperRegion(), K) ||
+           isTainted(State, ER->getIndex(), K);
+
+  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
+    return isTainted(State, SR->getSymbol(), K);
+
+  if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
+    return isTainted(State, ER->getSuperRegion(), K);
+
+  return false;
+}
+
+bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {
+  if (!Sym)
+    return false;
+
+  // Traverse all the symbols this symbol depends on to see if any are tainted.
+  for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end();
+       SI != SE; ++SI) {
+    if (!isa<SymbolData>(*SI))
+      continue;
+
+    if (const TaintTagType *Tag = State->get<TaintMap>(*SI)) {
+      if (*Tag == Kind)
+        return true;
+    }
+
+    if (const auto *SD = dyn_cast<SymbolDerived>(*SI)) {
+      // If this is a SymbolDerived with a tainted parent, it's also tainted.
+      if (isTainted(State, SD->getParentSymbol(), Kind))
+        return true;
+
+      // If this is a SymbolDerived with the same parent symbol as another
+      // tainted SymbolDerived and a region that's a sub-region of that tainted
+      // symbol, it's also tainted.
+      if (const TaintedSubRegions *Regs =
+              State->get<DerivedSymTaint>(SD->getParentSymbol())) {
+        const TypedValueRegion *R = SD->getRegion();
+        for (auto I : *Regs) {
+          // FIXME: The logic to identify tainted regions could be more
+          // complete. For example, this would not currently identify
+          // overlapping fields in a union as tainted. To identify this we can
+          // check for overlapping/nested byte offsets.
+          if (Kind == I.second && R->isSubRegionOf(I.first))
+            return true;
+        }
+      }
+    }
+
+    // If memory region is tainted, data is also tainted.
+    if (const auto *SRV = dyn_cast<SymbolRegionValue>(*SI)) {
+      if (isTainted(State, SRV->getRegion(), Kind))
+        return true;
+    }
+
+    // If this is a SymbolCast from a tainted value, it's also tainted.
+    if (const auto *SC = dyn_cast<SymbolCast>(*SI)) {
+      if (isTainted(State, SC->getOperand(), Kind))
+        return true;
+    }
+  }
+
+  return false;
+}
+
+std::shared_ptr<PathDiagnosticPiece>
+TaintBugVisitor::VisitNode(const ExplodedNode *N, BugReporterContext &BRC,
+                           BugReport &BR) {
+
+  // Find the ExplodedNode where the taint was first introduced
+  if (!isTainted(N->getState(), V) ||
+      isTainted(N->getFirstPred()->getState(), V))
+    return nullptr;
+
+  const Stmt *S = PathDiagnosticLocation::getStmt(N);
+  if (!S)
+    return nullptr;
+
+  const LocationContext *NCtx = N->getLocationContext();
+  PathDiagnosticLocation L =
+      PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx);
+  if (!L.isValid() || !L.asLocation().isValid())
+    return nullptr;
+
+  return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here");
+}

clang/lib/StaticAnalyzer/Checkers/TaintTesterChecker.cpp

 //== TaintTesterChecker.cpp ----------------------------------- -*- C++ -*--=//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This checker can be used for testing how taint data is propagated.
 //
 //===----------------------------------------------------------------------===//
+
+#include "Taint.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 class TaintTesterChecker : public Checker< check::PostStmt<Expr> > {
 
   mutable std::unique_ptr<BugType> BT;
   void initBugType() const;
 
   /// Given a pointer argument, get the symbol of the value it contains

 }
 
 void TaintTesterChecker::checkPostStmt(const Expr *E,
                                        CheckerContext &C) const {
   ProgramStateRef State = C.getState();
   if (!State)
     return;
 
-  if (State->isTainted(E, C.getLocationContext())) {
+  if (isTainted(State, E, C.getLocationContext())) {
     if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
       initBugType();
       auto report = llvm::make_unique<BugReport>(*BT, "tainted",N);
       report->addRange(E->getSourceRange());
       C.emitReport(std::move(report));
     }
   }
 }
 
 void ento::registerTaintTesterChecker(CheckerManager &mgr) {
   mgr.registerChecker<TaintTesterChecker>();
 }
 
 bool ento::shouldRegisterTaintTesterChecker(const LangOptions &LO) {
   return true;
 }

clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp

 //=== VLASizeChecker.cpp - Undefined dereference checker --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This defines VLASizeChecker, a builtin check in ExprEngine that
 // performs checks for declaration of VLA of undefined or zero size.
 // In addition, VLASizeChecker is responsible for defining the extent
 // of the MemRegion that represents a VLA.
 //
 //===----------------------------------------------------------------------===//
 
+#include "Taint.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/AST/CharUnits.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 class VLASizeChecker : public Checker< check::PreStmt<DeclStmt> > {
   mutable std::unique_ptr<BugType> BT;
   enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative };
 
   void reportBug(VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
                  CheckerContext &C,
void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
   }
 
   // See if the size value is known. It can't be undefined because we would have
   // warned about that already.
   if (sizeV.isUnknown())
     return;
 
   // Check if the size is tainted.
-  if (state->isTainted(sizeV)) {
+  if (isTainted(state, sizeV)) {
     reportBug(VLA_Tainted, SE, nullptr, C,
               llvm::make_unique<TaintBugVisitor>(sizeV));
     return;
   }
 
   // Check if the size is zero.
   DefinedSVal sizeD = sizeV.castAs<DefinedSVal>();
 

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

Out << "Assuming " << Met->getParamDecl(0)->getName() <<
     ((Param == This) ? " == " : " != ") << "*this";
 
   auto Piece = std::make_shared<PathDiagnosticEventPiece>(L, Out.str());
   Piece->addRange(Met->getSourceRange());
 
   return std::move(Piece);
 }
 
-std::shared_ptr<PathDiagnosticPiece>
-TaintBugVisitor::VisitNode(const ExplodedNode *N,
-                           BugReporterContext &BRC, BugReport &) {
-
-  // Find the ExplodedNode where the taint was first introduced
-  if (!N->getState()->isTainted(V) || N->getFirstPred()->getState()->isTainted(V))
-    return nullptr;
-
-  const Stmt *S = PathDiagnosticLocation::getStmt(N);
-  if (!S)
-    return nullptr;
-
-  const LocationContext *NCtx = N->getLocationContext();
-  PathDiagnosticLocation L =
-      PathDiagnosticLocation::createBegin(S, BRC.getSourceManager(), NCtx);
-  if (!L.isValid() || !L.asLocation().isValid())
-    return nullptr;
-
-  return std::make_shared<PathDiagnosticEventPiece>(L, "Taint originated here");
-}
 
 FalsePositiveRefutationBRVisitor::FalsePositiveRefutationBRVisitor()
     : Constraints(ConstraintRangeTy::Factory().getEmptyMap()) {}
 
 void FalsePositiveRefutationBRVisitor::finalizeVisitor(
     BugReporterContext &BRC, const ExplodedNode *EndPathNode, BugReport &BR) {
   // Collect new constraints
   VisitNode(EndPathNode, BRC, BR);

clang/lib/StaticAnalyzer/Core/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCore
   SimpleConstraintManager.cpp
   SimpleSValBuilder.cpp
   SMTConstraintManager.cpp
   Store.cpp
   SubEngine.cpp
   SValBuilder.cpp
   SVals.cpp
   SymbolManager.cpp
-  TaintManager.cpp
   WorkList.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangAnalysis
   clangBasic
   clangCrossTU
   clangLex
   clangRewrite
   )
 

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace clang { namespace  ento {
 /// Increments the number of times this state is referenced.
void ProgramState::print(raw_ostream &Out,
   Env.print(Out, NL, Sep, Context, LC);
 
   // Print out the constraints.
   Mgr.getConstraintManager().print(this, Out, NL, Sep);
 
   // Print out the tracked dynamic types.
   printDynamicTypeInfo(this, Out, NL, Sep);
 
-  // Print out tainted symbols.
-  printTaint(Out, NL);
-
   // Print checker-specific data.
   Mgr.getOwningEngine().printState(Out, this, NL, Sep, LC);
 }
 
 void ProgramState::printDOT(raw_ostream &Out,
                             const LocationContext *LC) const {
   print(Out, "\\l", "\\|", LC);
 }
 
 LLVM_DUMP_METHOD void ProgramState::dump() const {
   print(llvm::errs());
 }
 
-void ProgramState::printTaint(raw_ostream &Out,
-                              const char *NL) const {
-  TaintMapImpl TM = get<TaintMap>();
-
-  if (!TM.isEmpty())
-    Out <<"Tainted symbols:" << NL;
-
-  for (TaintMapImpl::iterator I = TM.begin(), E = TM.end(); I != E; ++I) {
-    Out << I->first << " : " << I->second << NL;
-  }
-}
-
-void ProgramState::dumpTaint() const {
-  printTaint(llvm::errs());
-}
-
 AnalysisManager& ProgramState::getAnalysisManager() const {
   return stateMgr->getOwningEngine().getAnalysisManager();
 }
 
 //===----------------------------------------------------------------------===//
 // Generic Data Map.
 //===----------------------------------------------------------------------===//
 
bool ProgramState::scanReachableSymbols(
     SymbolVisitor &visitor) const {
   ScanReachableSymbols S(this, visitor);
   for (const MemRegion *R : Reachable) {
     if (!S.scan(R))
       return false;
   }
   return true;
 }
-
-ProgramStateRef ProgramState::addTaint(const Stmt *S,
-                                           const LocationContext *LCtx,
-                                           TaintTagType Kind) const {
-  if (const Expr *E = dyn_cast_or_null<Expr>(S))
-    S = E->IgnoreParens();
-
-  return addTaint(getSVal(S, LCtx), Kind);
-}
-
-ProgramStateRef ProgramState::addTaint(SVal V,
-                                       TaintTagType Kind) const {
-  SymbolRef Sym = V.getAsSymbol();
-  if (Sym)
-    return addTaint(Sym, Kind);
-
-  // If the SVal represents a structure, try to mass-taint all values within the
-  // structure. For now it only works efficiently on lazy compound values that
-  // were conjured during a conservative evaluation of a function - either as
-  // return values of functions that return structures or arrays by value, or as
-  // values of structures or arrays passed into the function by reference,
-  // directly or through pointer aliasing. Such lazy compound values are
-  // characterized by having exactly one binding in their captured store within
-  // their parent region, which is a conjured symbol default-bound to the base
-  // region of the parent region.
-  if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) {
-    if (Optional<SVal> binding = getStateManager().StoreMgr->getDefaultBinding(*LCV)) {
-      if (SymbolRef Sym = binding->getAsSymbol())
-        return addPartialTaint(Sym, LCV->getRegion(), Kind);
-    }
-  }
-
-  const MemRegion *R = V.getAsRegion();
-  return addTaint(R, Kind);
-}
-
-ProgramStateRef ProgramState::addTaint(const MemRegion *R,
-                                           TaintTagType Kind) const {
-  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
-    return addTaint(SR->getSymbol(), Kind);
-  return this;
-}
-
-ProgramStateRef ProgramState::addTaint(SymbolRef Sym,
-                                           TaintTagType Kind) const {
-  // If this is a symbol cast, remove the cast before adding the taint. Taint
-  // is cast agnostic.
-  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
-    Sym = SC->getOperand();
-
-  ProgramStateRef NewState = set<TaintMap>(Sym, Kind);
-  assert(NewState);
-  return NewState;
-}
-
-ProgramStateRef ProgramState::addPartialTaint(SymbolRef ParentSym,
-                                              const SubRegion *SubRegion,
-                                              TaintTagType Kind) const {
-  // Ignore partial taint if the entire parent symbol is already tainted.
-  if (contains<TaintMap>(ParentSym) && *get<TaintMap>(ParentSym) == Kind)
-    return this;
-
-  // Partial taint applies if only a portion of the symbol is tainted.
-  if (SubRegion == SubRegion->getBaseRegion())
-    return addTaint(ParentSym, Kind);
-
-  const TaintedSubRegions *SavedRegs = get<DerivedSymTaint>(ParentSym);
-  TaintedSubRegions Regs =
-      SavedRegs ? *SavedRegs : stateMgr->TSRFactory.getEmptyMap();
-
-  Regs = stateMgr->TSRFactory.add(Regs, SubRegion, Kind);
-  ProgramStateRef NewState = set<DerivedSymTaint>(ParentSym, Regs);
-  assert(NewState);
-  return NewState;
-}
-
-bool ProgramState::isTainted(const Stmt *S, const LocationContext *LCtx,
-                             TaintTagType Kind) const {
-  if (const Expr *E = dyn_cast_or_null<Expr>(S))
-    S = E->IgnoreParens();
-
-  SVal val = getSVal(S, LCtx);
-  return isTainted(val, Kind);
-}
-
-bool ProgramState::isTainted(SVal V, TaintTagType Kind) const {
-  if (const SymExpr *Sym = V.getAsSymExpr())
-    return isTainted(Sym, Kind);
-  if (const MemRegion *Reg = V.getAsRegion())
-    return isTainted(Reg, Kind);
-  return false;
-}
-
-bool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const {
-  if (!Reg)
-    return false;
-
-  // Element region (array element) is tainted if either the base or the offset
-  // are tainted.
-  if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
-    return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K);
-
-  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
-    return isTainted(SR->getSymbol(), K);
-
-  if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
-    return isTainted(ER->getSuperRegion(), K);
-
-  return false;
-}
-
-bool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const {
-  if (!Sym)
-    return false;
-
-  // Traverse all the symbols this symbol depends on to see if any are tainted.
-  for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end();
-       SI != SE; ++SI) {
-    if (!isa<SymbolData>(*SI))
-      continue;
-
-    if (const TaintTagType *Tag = get<TaintMap>(*SI)) {
-      if (*Tag == Kind)
-        return true;
-    }
-
-    if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) {
-      // If this is a SymbolDerived with a tainted parent, it's also tainted.
-      if (isTainted(SD->getParentSymbol(), Kind))
-        return true;
-
-      // If this is a SymbolDerived with the same parent symbol as another
-      // tainted SymbolDerived and a region that's a sub-region of that tainted
-      // symbol, it's also tainted.
-      if (const TaintedSubRegions *Regs =
-              get<DerivedSymTaint>(SD->getParentSymbol())) {
-        const TypedValueRegion *R = SD->getRegion();
-        for (auto I : *Regs) {
-          // FIXME: The logic to identify tainted regions could be more
-          // complete. For example, this would not currently identify
-          // overlapping fields in a union as tainted. To identify this we can
-          // check for overlapping/nested byte offsets.
-          if (Kind == I.second && R->isSubRegionOf(I.first))
-            return true;
-        }
-      }
-    }
-
-    // If memory region is tainted, data is also tainted.
-    if (const SymbolRegionValue *SRV = dyn_cast<SymbolRegionValue>(*SI)) {
-      if (isTainted(SRV->getRegion(), Kind))
-        return true;
-    }
-
-    // If this is a SymbolCast from a tainted value, it's also tainted.
-    if (const SymbolCast *SC = dyn_cast<SymbolCast>(*SI)) {
-      if (isTainted(SC->getOperand(), Kind))
-        return true;
-    }
-  }
-
-  return false;
-}

clang/lib/StaticAnalyzer/Core/TaintManager.cpp

-//== TaintManager.cpp ------------------------------------------ -*- C++ -*--=//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h"
-
-using namespace clang;
-using namespace ento;
-
-void *ProgramStateTrait<TaintMap>::GDMIndex() {
-  static int index = 0;
-  return &index;
-}
-
-void *ProgramStateTrait<DerivedSymTaint>::GDMIndex() {
-  static int index;
-  return &index;
-}