[analyzer] Fix taint propagation by remembering to the location context

[steakhal]

Summary

Fixes the issue D118987 by mapping the propagation to the callsite's
LocationContext.
This way we can keep track of the in-flight propagations.

Note that empty propagation sets won't be inserted.

[Szelethus]

Sounds about right! Just a nit, otherwise LGTM.

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

441

Are there any comfortable ways of making this non-global?
https://llvm.org/docs/CodingStandards.html#do-not-use-static-constructors

Also, I wonder how efficient immutable data structures are against something like std::vector, when the element type is small and the number of elements are expected to be very low. Just a thought, I don't have particularly strong views on this.

[steakhal]

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

441

Thanks for catching it.
I grepped for a similar code and it seems like there is the REGISTER_SET_FACTORY_WITH_PROGRAMSTATE for exactly this.
Now I know about this :)

[steakhal]

using REGISTER_SET_FACTORY_WITH_PROGRAMSTATE

[steakhal]

upload the right diff

[NoQ]

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

441

ImmutableList is another good candidate. I prefer these data structures to be immutable because that's a much stronger guarantee that they won't actually ever be updated while stored in the state.

clang/test/Analysis/taint-checker-callback-order-has-definition.c

3

This test will be annoying to update when more debug prints are added. It might be better to test this through debug.TaintTest or a new ExprInspection function.

[NoQ]

Looks correct, thanks for fixing this!

[Szelethus]

LGTM!

[Szelethus]

Can we reopen this if the code is not upstream at this time?

[steakhal]

I'll re-land the whole stack tomorrow, by adding the asserts requirement for the tests to make the tests pass on all bots.

[steakhal]

Committed as a848a5cf2f2f2f8a621bdc5a12e0fe49dc743176.

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

 #include <utility>
 
 #define DEBUG_TYPE "taint-checker"
 
 using namespace clang;
 using namespace ento;
 using namespace taint;
 
+using llvm::ImmutableSet;
+
 namespace {
 
 class GenericTaintChecker;
 
 /// Check for CWE-134: Uncontrolled Format String.
 constexpr llvm::StringLiteral MsgUncontrolledFormatString =
     "Untrusted data is used as a format string "
     "(CWE-134: Uncontrolled Format String)";

 };
 } // namespace yaml
 } // namespace llvm
 
 /// A set which is used to pass information from call pre-visit instruction
 /// to the call post-visit. The values are signed integers, which are either
 /// ReturnValueIndex, or indexes of the pointer/reference argument, which
 /// points to data, which should be tainted on return.
-REGISTER_SET_WITH_PROGRAMSTATE(TaintArgsOnPostVisit, ArgIdxTy)
+REGISTER_MAP_WITH_PROGRAMSTATE(TaintArgsOnPostVisit, const LocationContext *,
+                               ImmutableSet<ArgIdxTy>)
+REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ArgIdxFactory, ArgIdxTy)
 
 void GenericTaintRuleParser::validateArgVector(const std::string &Option,
                                                const ArgVecTy &Args) const {
   for (ArgIdxTy Arg : Args) {
     if (Arg < ReturnValueIndex) {
       Mgr.reportInvalidCheckerOptionValue(
           Mgr.getChecker<GenericTaintChecker>(), Option,
           "an argument number for propagation rules greater or equal to -1");
void GenericTaintChecker::checkPreCall(const CallEvent &Call,
   taintUnsafeSocketProtocol(Call, C);
 }
 
 void GenericTaintChecker::checkPostCall(const CallEvent &Call,
                                         CheckerContext &C) const {
   // Set the marked values as tainted. The return value only accessible from
   // checkPostStmt.
   ProgramStateRef State = C.getState();
+  const StackFrameContext *CurrentFrame = C.getStackFrame();
 
   // Depending on what was tainted at pre-visit, we determined a set of
   // arguments which should be tainted after the function returns. These are
   // stored in the state as TaintArgsOnPostVisit set.
-  TaintArgsOnPostVisitTy TaintArgs = State->get<TaintArgsOnPostVisit>();
-  if (TaintArgs.isEmpty())
+  TaintArgsOnPostVisitTy TaintArgsMap = State->get<TaintArgsOnPostVisit>();
+
+  const ImmutableSet<ArgIdxTy> *TaintArgs = TaintArgsMap.lookup(CurrentFrame);
+  if (!TaintArgs)
     return;
+  assert(!TaintArgs->isEmpty());
 
   LLVM_DEBUG(for (ArgIdxTy I
-                  : TaintArgs) {
+                  : *TaintArgs) {
     llvm::dbgs() << "PostCall<";
     Call.dump(llvm::dbgs());
     llvm::dbgs() << "> actually wants to taint arg index: " << I << '\n';
   });
 
-  for (ArgIdxTy ArgNum : TaintArgs) {
+  for (ArgIdxTy ArgNum : *TaintArgs) {
     // Special handling for the tainted return value.
     if (ArgNum == ReturnValueIndex) {
       State = addTaint(State, Call.getReturnValue());
       continue;
     }
 
     // The arguments are pointer arguments. The data they are pointing at is
     // tainted after the call.
     if (auto V = getPointeeOf(C, Call.getArgSVal(ArgNum)))
       State = addTaint(State, *V);
   }
 
   // Clear up the taint info from the state.
-  State = State->remove<TaintArgsOnPostVisit>();
+  State = State->remove<TaintArgsOnPostVisit>(CurrentFrame);
   C.addTransition(State);
 }
 
 void GenericTaintChecker::printState(raw_ostream &Out, ProgramStateRef State,
                                      const char *NL, const char *Sep) const {
   printTaint(State, Out, NL, Sep);
 }
 
const auto WouldEscape = [](SVal V, QualType Ty) -> bool {
     const bool IsNonConstRef = Ty->isReferenceType() && !Ty.isConstQualified();
     const bool IsNonConstPtr =
         Ty->isPointerType() && !Ty->getPointeeType().isConstQualified();
 
     return IsNonConstRef || IsNonConstPtr;
   };
 
   /// Propagate taint where it is necessary.
+  auto &F = State->getStateManager().get_context<ArgIdxFactory>();
+  ImmutableSet<ArgIdxTy> Result = F.getEmptySet();
   ForEachCallArg(
-      [this, &State, WouldEscape, &Call](ArgIdxTy I, const Expr *E, SVal V) {
+      [this, WouldEscape, &Call, &Result, &F](ArgIdxTy I, const Expr *E,
+                                              SVal V) {
         if (PropDstArgs.contains(I)) {
           LLVM_DEBUG(llvm::dbgs() << "PreCall<"; Call.dump(llvm::dbgs());
                      llvm::dbgs()
                      << "> prepares tainting arg index: " << I << '\n';);
-          State = State->add<TaintArgsOnPostVisit>(I);
+          Result = F.add(Result, I);
         }
 
         // TODO: We should traverse all reachable memory regions via the
         // escaping parameter. Instead of doing that we simply mark only the
         // referred memory region as tainted.
         if (WouldEscape(V, E->getType())) {
-          LLVM_DEBUG(if (!State->contains<TaintArgsOnPostVisit>(I)) {
+          LLVM_DEBUG(if (!Result.contains(I)) {
             llvm::dbgs() << "PreCall<";
             Call.dump(llvm::dbgs());
             llvm::dbgs() << "> prepares tainting arg index: " << I << '\n';
           });
-          State = State->add<TaintArgsOnPostVisit>(I);
+          Result = F.add(Result, I);
         }
       });
 
+  if (!Result.isEmpty())
+    State = State->set<TaintArgsOnPostVisit>(C.getStackFrame(), Result);
   C.addTransition(State);
 }
 
 bool GenericTaintRule::UntrustedEnv(CheckerContext &C) {
   return !C.getAnalysisManager()
               .getAnalyzerOptions()
               .ShouldAssumeControlledEnvironment;
 }
void GenericTaintChecker::taintUnsafeSocketProtocol(const CallEvent &Call,
   StringRef DomName = C.getMacroNameOrSpelling(DomLoc);
   // Allow internal communication protocols.
   bool SafeProtocol = DomName.equals("AF_SYSTEM") ||
                       DomName.equals("AF_LOCAL") || DomName.equals("AF_UNIX") ||
                       DomName.equals("AF_RESERVED_36");
   if (SafeProtocol)
     return;
 
-  C.addTransition(C.getState()->add<TaintArgsOnPostVisit>(ReturnValueIndex));
+  ProgramStateRef State = C.getState();
+  auto &F = State->getStateManager().get_context<ArgIdxFactory>();
+  ImmutableSet<ArgIdxTy> Result = F.add(F.getEmptySet(), ReturnValueIndex);
+  State = State->set<TaintArgsOnPostVisit>(C.getStackFrame(), Result);
+  C.addTransition(State);
 }
 
 /// Checker registration
 
 void ento::registerGenericTaintChecker(CheckerManager &Mgr) {
   Mgr.registerChecker<GenericTaintChecker>();
 }
 
 bool ento::shouldRegisterGenericTaintChecker(const CheckerManager &mgr) {
   return true;
 }

clang/test/Analysis/taint-checker-callback-order-has-definition.c

 // RUN: %clang_analyze_cc1 %s \
 // RUN:   -analyzer-checker=core,alpha.security.taint \
 // RUN:   -mllvm -debug-only=taint-checker \
 // RUN:   2>&1 | FileCheck %s
 
-// FIXME: We should not crash.
-// XFAIL: *
-
 struct _IO_FILE;
 typedef struct _IO_FILE FILE;
 FILE *fopen(const char *fname, const char *mode);
 
 void nested_call(void) {}
 
 char *fgets(char *s, int n, FILE *fp) {
   nested_call();   // no-crash: we should not try adding taint to a non-existent argument.
if (!fp)
     return;
 
   (void)fgets(buf, 42, fp); // Trigger taint propagation.
   // CHECK-NEXT: PreCall<fgets(buf, 42, fp)> prepares tainting arg index: -1
   // CHECK-NEXT: PreCall<fgets(buf, 42, fp)> prepares tainting arg index: 0
   // CHECK-NEXT: PreCall<fgets(buf, 42, fp)> prepares tainting arg index: 1
   // CHECK-NEXT: PreCall<fgets(buf, 42, fp)> prepares tainting arg index: 2
 
-  // FIXME: We should propagate taint from PreCall<fgets> -> PostCall<fgets>.
-  // CHECK-NEXT: PostCall<nested_call()> actually wants to taint arg index: -1
-  // CHECK-NEXT: PostCall<nested_call()> actually wants to taint arg index: 0
-  // CHECK-NEXT: PostCall<nested_call()> actually wants to taint arg index: 1
-  // CHECK-NEXT: PostCall<nested_call()> actually wants to taint arg index: 2
-
-  // FIXME: We should not crash.
-  // CHECK: PLEASE submit a bug report
+  // CHECK-NEXT: PostCall<fgets(buf, 42, fp)> actually wants to taint arg index: -1
+  // CHECK-NEXT: PostCall<fgets(buf, 42, fp)> actually wants to taint arg index: 0
+  // CHECK-NEXT: PostCall<fgets(buf, 42, fp)> actually wants to taint arg index: 1
+  // CHECK-NEXT: PostCall<fgets(buf, 42, fp)> actually wants to taint arg index: 2
 }