//=== Taint.cpp - Taint tracking and basic propagation rules. ------*- 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 basic, non-domain-specific mechanisms for tracking tainted values.

//

//===----------------------------------------------------------------------===//

#include "clang/StaticAnalyzer/Checkers/Taint.h"

#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"

#include <optional>

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 taint::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 (std::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::removeTaint(ProgramStateRef State, SVal V) {

  SymbolRef Sym = V.getAsSymbol();

  if (Sym)

    return removeTaint(State, Sym);

  const MemRegion *R = V.getAsRegion();

  return removeTaint(State, R);

}

ProgramStateRef taint::removeTaint(ProgramStateRef State, const MemRegion *R) {

  if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))

    return removeTaint(State, SR->getSymbol());

  return State;

}

ProgramStateRef taint::removeTaint(ProgramStateRef State, SymbolRef Sym) {

  // 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->remove<TaintMap>(Sym);

  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 ? 
*SavedRegs0
 : 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) {

  return !getTaintedSymbolsImpl(State, S, LCtx, Kind, /*ReturnFirstOnly=*/true)

              .empty();

}

bool taint::isTainted(ProgramStateRef State, SVal V, TaintTagType Kind) {

  return !getTaintedSymbolsImpl(State, V, Kind, /*ReturnFirstOnly=*/true)

              .empty();

}

bool taint::isTainted(ProgramStateRef State, const MemRegion *Reg,

                      TaintTagType K) {

  return !getTaintedSymbolsImpl(State, Reg, K, /*ReturnFirstOnly=*/true)

              .empty();

}

bool taint::isTainted(ProgramStateRef State, SymbolRef Sym, TaintTagType Kind) {

  return !getTaintedSymbolsImpl(State, Sym, Kind, /*ReturnFirstOnly=*/true)

              .empty();

}

std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State,

                                                const Stmt *S,

                                                const LocationContext *LCtx,

                                                TaintTagType Kind) {

  return getTaintedSymbolsImpl(State, S, LCtx, Kind, /*ReturnFirstOnly=*/false);

}

std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State, SVal V,

                                                TaintTagType Kind) {

  return getTaintedSymbolsImpl(State, V, Kind, /*ReturnFirstOnly=*/false);

}

std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State,

                                                SymbolRef Sym,

                                                TaintTagType Kind) {

  return getTaintedSymbolsImpl(State, Sym, Kind, /*ReturnFirstOnly=*/false);

}

std::vector<SymbolRef> taint::getTaintedSymbols(ProgramStateRef State,

                                                const MemRegion *Reg,

                                                TaintTagType Kind) {

  return getTaintedSymbolsImpl(State, Reg, Kind, /*ReturnFirstOnly=*/false);

}

std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,

                                                    const Stmt *S,

                                                    const LocationContext *LCtx,

                                                    TaintTagType Kind,

                                                    bool returnFirstOnly) {

  SVal val = State->getSVal(S, LCtx);

  return getTaintedSymbolsImpl(State, val, Kind, returnFirstOnly);

}

std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,

                                                    SVal V, TaintTagType Kind,

                                                    bool returnFirstOnly) {

  if (SymbolRef Sym = V.getAsSymbol())

    return getTaintedSymbolsImpl(State, Sym, Kind, returnFirstOnly);

  if (const MemRegion *Reg = V.getAsRegion())

    return getTaintedSymbolsImpl(State, Reg, Kind, returnFirstOnly);

  return {};

}

std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,

                                                    const MemRegion *Reg,

                                                    TaintTagType K,

                                                    bool returnFirstOnly) {

  std::vector<SymbolRef> TaintedSymbols;

  if (!Reg)

    return TaintedSymbols;

  // Element region (array element) is tainted if either the base or the offset

  // are tainted.

  if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) {

    std::vector<SymbolRef> TaintedIndex =

        getTaintedSymbolsImpl(State, ER->getIndex(), K, returnFirstOnly);

    llvm::append_range(TaintedSymbols, TaintedIndex);

    if (returnFirstOnly && 
!TaintedSymbols.empty()2.57k
)

      return TaintedSymbols; // return early if needed

    std::vector<SymbolRef> TaintedSuperRegion =

        getTaintedSymbolsImpl(State, ER->getSuperRegion(), K, returnFirstOnly);

    llvm::append_range(TaintedSymbols, TaintedSuperRegion);

    if (returnFirstOnly && 
!TaintedSymbols.empty()2.56k
)

      return TaintedSymbols; // return early if needed

  }

  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) {

    std::vector<SymbolRef> TaintedRegions =

        getTaintedSymbolsImpl(State, SR->getSymbol(), K, returnFirstOnly);

    llvm::append_range(TaintedSymbols, TaintedRegions);

    if (returnFirstOnly && 
!TaintedSymbols.empty()1.73k
)

      return TaintedSymbols; // return early if needed

  }

  if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) {

    std::vector<SymbolRef> TaintedSubRegions =

        getTaintedSymbolsImpl(State, ER->getSuperRegion(), K, returnFirstOnly);

    llvm::append_range(TaintedSymbols, TaintedSubRegions);

    if (returnFirstOnly && 
!TaintedSymbols.empty()35.0k
)

      return TaintedSymbols; // return early if needed

  }

  return TaintedSymbols;

}

std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State,

                                                    SymbolRef Sym,

                                                    TaintTagType Kind,

                                                    bool returnFirstOnly) {

  std::vector<SymbolRef> TaintedSymbols;

  if (!Sym)

    return TaintedSymbols;

  // Traverse all the symbols this symbol depends on to see if any are tainted.

  
for (SymbolRef SubSym : Sym->symbols())18.5k
 {

    if (!isa<SymbolData>(SubSym))

      continue;

    if (const TaintTagType *Tag = State->get<TaintMap>(SubSym)) {

      if (*Tag == Kind) {

        TaintedSymbols.push_back(SubSym);

        if (returnFirstOnly)

          return TaintedSymbols; // return early if needed

      }

    }

    if (const auto *SD = dyn_cast<SymbolDerived>(SubSym)) {

      // If this is a SymbolDerived with a tainted parent, it's also tainted.

      std::vector<SymbolRef> TaintedParents = getTaintedSymbolsImpl(

          State, SD->getParentSymbol(), Kind, returnFirstOnly);

      llvm::append_range(TaintedSymbols, TaintedParents);

      if (returnFirstOnly && 
!TaintedSymbols.empty()378
)

        return TaintedSymbols; // return early if needed

      // 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)) {

            TaintedSymbols.push_back(SD->getParentSymbol());

            if (returnFirstOnly && 
!TaintedSymbols.empty()20
)

              return TaintedSymbols; // return early if needed

          }

        }

      }

    }

    // If memory region is tainted, data is also tainted.

    if (const auto *SRV = dyn_cast<SymbolRegionValue>(SubSym)) {

      std::vector<SymbolRef> TaintedRegions =

          getTaintedSymbolsImpl(State, SRV->getRegion(), Kind, returnFirstOnly);

      llvm::append_range(TaintedSymbols, TaintedRegions);

      if (returnFirstOnly && 
!TaintedSymbols.empty()28.3k
)

        return TaintedSymbols; // return early if needed

    }

    // If this is a SymbolCast from a tainted value, it's also tainted.

    if (const auto *SC = dyn_cast<SymbolCast>(SubSym)) {

      std::vector<SymbolRef> TaintedCasts =

          getTaintedSymbolsImpl(State, SC->getOperand(), Kind, returnFirstOnly);

      llvm::append_range(TaintedSymbols, TaintedCasts);

      if (returnFirstOnly && !TaintedSymbols.empty())

        return TaintedSymbols; // return early if needed

    }

  }

  return TaintedSymbols;

}