[analyzer] Add failing test case demonstrating buggy taint propagation

[steakhal]

Summary

Recently we uncovered a serious bug in the GenericTaintChecker.
It was already flawed before D116025, but that was the patch that turned this silent bug into a crash.

It happens if the GenericTaintChecker has a rule for a function, which also has a definition.

char *fgets(char *s, int n, FILE *fp) {
  nested_call();   // no parameters!
  return (char *)0;
}

// Within some function:
fgets(..., tainted_fd);

When the engine inlines the definition and finds a function call within that, the PostCall event for the call will get triggered sooner than the PostCall for the original function.
This mismatch violates the assumption of the GenericTaintChecker which wants to propagate taint information from the PreCall event to the PostCall event, where it can actually bind taint to the return value of the same call.

Let's get back to the example and go through step-by-step.
The GenericTaintChecker will see the PreCall<fgets(..., tainted_fd)> event, so it would 'remember' that it needs to taint the return value and the buffer, from the PostCall handler, where it has access to the return value symbol.
However, the engine will inline fgets and the nested_call() gets evaluated subsequently, which produces an unimportant PreCall<nested_call()>, then a PostCall<nested_call()> event, which is observed by the GenericTaintChecker, which will unconditionally mark tainted the 'remembered' arg indexes, trying to access a non-existing argument, resulting in a crash.
If it doesn't crash, it will behave completely unintuitively, by marking completely unrelated memory regions tainted, which is even worse.

The resulting assertion is something like this:

Expr.h: const Expr *CallExpr::getArg(unsigned int) const: Assertion `Arg < getNumArgs() && "Arg access out of range!"' failed.

The gist of the backtrace:

CallExpr::getArg(unsigned int) const
SimpleFunctionCall::getArgExpr(unsigned int)
CallEvent::getArgSVal(unsigned int) const
GenericTaintChecker::checkPostCall(const CallEvent &, CheckerContext &) const

Prior to D116025, there was a check for the argument count before it applied taint, however, it still suffered from the same underlying issue/bug regarding propagation.

This path does not intend to fix the bug, rather start a discussion on how to fix this.

---

Let me elaborate on how I see this problem.

This pre-call, post-call juggling is just a workaround.
The engine should by itself propagate taint where necessary right where it invalidates regions.
For the tracked values, which potentially escape, we need to erase the information we know about them; and this is exactly what is done by invalidation.
However, in the case of taint, we basically want to approximate from the opposite side of the spectrum.
We want to preserve taint in most cases, rather than cleansing them.

Now, we basically sanitize all escaping tainted regions implicitly, since invalidation binds a fresh conjured symbol for the given region, and that has not been associated with taint.

IMO this is a bad default behavior, we should be more aggressive about preserving taint if not further spreading taint to the reachable regions.

We have a couple of options for dealing with it (let's call it tainting policy):

1. Taint only the parameters which were tainted prior to the call.
2. Taint the return value of the call, since it likely depends on the tainted input - if any arguments were tainted.
3. Taint all escaped regions - (maybe transitively using the cluster algorithm) - if any arguments were tainted.
4. Not taint anything - this is what we do right now :D

The ExprEngine should not deal with taint on its own. It should be done by a checker, such as the GenericTaintChecker.
However, the Pre-PostCall checker callbacks are not designed for this. RegionChanges would be a much better fit for modeling taint propagation.
What we would need in the RegionChanges callback is the State prior invalidation, the State after the invalidation, and a CheckerContext in which the checker can create transitions, where it would place NoteTags for the modeled taint propagations and report errors if a taint sink rule gets violated.
In this callback, we could query from the prior State, if the given value was tainted; then act and taint if necessary according to the checker's tainting policy.

By using RegionChanges for this, we would 'fix' the mentioned propagation bug 'by-design'.
WDYT?

[martong]

Thanks Balázs for investigating this issue!

The way we reach the crash is not immediate from the summary you gave, however, the test cases extend the summary well.

Focusing on the crash, I think it might be solved by including the function's name (or even better, the CallDescription itself) in the key of TaintArgsOnPostVisit.

The engine should by itself propagate taint where necessary right where it invalidates regions.
For the tracked values, which potentially escape, we need to erase the information we know about them; and this is exactly what is done by invalidation.
However, in the case of taint, we basically want to approximate from the opposite side of the spectrum.
We want to preserve taint in most cases, rather than cleansing them.
...
What we would need in the RegionChanges callback is the State prior invalidation, the State after the invalidation, and a CheckerContext in which the checker can create transitions, where it would place NoteTags for the modeled taint propagations and report errors if a taint sink rule gets violated.
In this callback, we could query from the prior State, if the given value was tainted; then act and taint if necessary according to the checker's tainting policy.

I agree and fully support this.

We have a couple of options for dealing with it (let's call it tainting policy):

1. Taint only the parameters which were tainted prior to the call.
2. Taint the return value of the call, since it likely depends on the tainted input - if any arguments were tainted.
3. Taint all escaped regions - (maybe transitively using the cluster algorithm) - if any arguments were tainted.
4. Not taint anything - this is what we do right now :D

I think this should be configurable via an -analyzer-config option, but with a good default, which should be (1. and 2. together).

Before jumping into the heavy long-term work, Do you think, changing the key of TaintArgsOnPostVisit could solve the crash in the short-term?

[martong]

Focusing on the crash, I think it might be solved by including the function's name (or even better, the CallDescription itself) in the key of TaintArgsOnPostVisit.

Maybe even a LocationContext would be needed in the key?

[steakhal]

In D118987#3296841, @martong wrote:

The way we reach the crash is not immediate from the summary you gave, however, the test cases extend the summary well.

Yea, I'll update the summary. Include an example from the tests and a stack trace of the crash.

Before jumping into the heavy long-term work, Do you think, changing the key of TaintArgsOnPostVisit could solve the crash in the short-term?

We could map a location context to the TaintArgsOnPostVisit arg index set, and that would solve the issue. But it would make the situation worse in terms of readability.
So, even though we can hotfix it, we should definitely do something about it.

[NoQ]

I agree with @martong, LocationContext is the correct key here. The pair (Call expression, Location context) uniquely identifies the call as that call is being evaluated. This is exactly how expression evaluations are identified in the Environment.

An alternative would be to turn TaintArgsOnPostVisit into a stack (implemented as ImmutableList) but location contexts are already a stack designed specifically for that purpose.

[steakhal]

Please consider accepting this revision to land the child patches fixing both of the described bugs.

[Szelethus]

Sorry for the slack, I assumed this was accepted already. Thanks!

[steakhal]

It seems like the clang-ve-ninja doesn't really want to accept any patches from me :D
I hope it's not personal. Let's be friends bot, please.

Link to the breakage: https://lab.llvm.org/buildbot/#/builders/91/builds/3818

I'm inviting @simoll for resolving this, and the underlying issue to prevent future breakages and reverts.

[jrtc27]

In D118987#3319697, @steakhal wrote:

It seems like the clang-ve-ninja doesn't really want to accept any patches from me :D
I hope it's not personal. Let's be friends bot, please.

Link to the breakage: https://lab.llvm.org/buildbot/#/builders/91/builds/3818

I'm inviting @simoll for resolving this, and the underlying issue to prevent future breakages and reverts.

As stated in https://discourse.llvm.org/t/the-angry-clang-ve-ninja-build-bot/60330/4, it's because the clang-ve-ninja bot does a build without assertions enabled, so you need REQUIRES: asserts or to write the test in a way that avoids the need for -debug-only.

[steakhal]

In D118987#3332940, @jrtc27 wrote:

In D118987#3319697, @steakhal wrote:

It seems like the clang-ve-ninja doesn't really want to accept any patches from me :D
I hope it's not personal. Let's be friends bot, please.

Link to the breakage: https://lab.llvm.org/buildbot/#/builders/91/builds/3818

I'm inviting @simoll for resolving this, and the underlying issue to prevent future breakages and reverts.

As stated in https://discourse.llvm.org/t/the-angry-clang-ve-ninja-build-bot/60330/4, it's because the clang-ve-ninja bot does a build without assertions enabled, so you need REQUIRES: asserts or to write the test in a way that avoids the need for -debug-only.

It seems like it worked! Thanks again.

[steakhal]

Committed as fa0a80e017ebd58a71bdb4e4493bb022f80fe791.

[MaskRay]

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

782

There was a -Wunused-lambda-capture in -DLLVM_ENABLE_ASSERTIONS=off builds. Fixed by 7fd60ee6e0a87957a718297a4a42d9881fc561e3

[steakhal]

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

782

Ah, thanks!

clang/lib/StaticAnalyzer/Checkers/GenericTaintChecker.cpp

 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "llvm/Support/YAMLTraits.h"
 
 #include <limits>
 #include <memory>
 #include <utility>
 
+#define DEBUG_TYPE "taint-checker"
+
 using namespace clang;
 using namespace ento;
 using namespace taint;
 
 namespace {
 
 class GenericTaintChecker;
 
void GenericTaintChecker::checkPostCall(const CallEvent &Call,
 
   // 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())
     return;
 
+  LLVM_DEBUG(for (ArgIdxTy I
+                  : TaintArgs) {
+    llvm::dbgs() << "PostCall<";
+    Call.dump(llvm::dbgs());
+    llvm::dbgs() << "> actually wants to taint arg index: " << I << '\n';
+  });
+
   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
const auto WouldEscape = [](SVal V, QualType Ty) -> bool {
     const bool IsNonConstPtr =
         Ty->isPointerType() && !Ty->getPointeeType().isConstQualified();
 
     return IsNonConstRef || IsNonConstPtr;
   };
 
   /// Propagate taint where it is necessary.
   ForEachCallArg(
-      [this, &State, WouldEscape](ArgIdxTy I, const Expr *E, SVal V) {
-        if (PropDstArgs.contains(I))
+      [this, &State, WouldEscape, &Call](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);
+        }
 
         // 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()))
+        if (WouldEscape(V, E->getType())) {
+          LLVM_DEBUG(if (!State->contains<TaintArgsOnPostVisit>(I)) {
+            llvm::dbgs() << "PreCall<";
+            Call.dump(llvm::dbgs());
+            llvm::dbgs() << "> prepares tainting arg index: " << I << '\n';
+          });
           State = State->add<TaintArgsOnPostVisit>(I);
+        }
       });
 
   C.addTransition(State);
 }
 
 bool GenericTaintRule::UntrustedEnv(CheckerContext &C) {
   return !C.getAnalysisManager()
               .getAnalyzerOptions()

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.
+  return (char *)0;
+}
+
+void top(const char *fname, char *buf) {
+  FILE *fp = fopen(fname, "r");
+  // CHECK:      PreCall<fopen(fname, "r")> prepares tainting arg index: -1
+  // CHECK-NEXT: PostCall<fopen(fname, "r")> actually wants to taint arg index: -1
+
+  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
+}

clang/test/Analysis/taint-checker-callback-order-without-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
+
+struct _IO_FILE;
+typedef struct _IO_FILE FILE;
+FILE *fopen(const char *fname, const char *mode);
+
+char *fgets(char *s, int n, FILE *fp); // no-definition
+
+void top(const char *fname, char *buf) {
+  FILE *fp = fopen(fname, "r"); // Introduce taint.
+  // CHECK:      PreCall<fopen(fname, "r")> prepares tainting arg index: -1
+  // CHECK-NEXT: PostCall<fopen(fname, "r")> actually wants to taint arg index: -1
+
+  if (!fp)
+    return;
+
+  (void)fgets(buf, 42, fp); // Trigger taint propagation.
+
+  // FIXME: Why is the arg index 1 prepared for taint?
+  // Before the call it wasn't tainted, and it also shouldn't be tainted after the call.
+
+  // 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
+  //
+  // 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
+}