[analyzer] MallocOverflow should consider comparisons only preceding malloc

[steakhal]

Summary

MallocOverflow works in two phases:

1. Collects suspicious malloc calls, whose argument is a multiplication
2. Filters the aggregated list of suspicious malloc calls by iterating over the BasicBlocks of the CFG looking for comparison binary operators over the variable constituting in any suspicious malloc.

Consequently, it suppressed true-positive cases when the comparison check was after the malloc call.
In this patch, the checker will consider the relative position of the relation check to the malloc call.

E.g.:

void *check_after_malloc(int n, int x) {
  int *p = NULL;
  if (x == 42)
    p = malloc(n * sizeof(int)); // Previously **no** warning, now it
                                 // warns about this.

  // The check is after the allocation!
  if (n > 10) {
    // Do something conditionally.
  }
  return p;
}

[balazske]

clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

163

Is it safe to check for position in source code, instead of the execution path?

165

This is not a PredTrue any more.

[steakhal]

clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

163

I don't think so. But it's already better than outright suppressing any finding.

165

Oh sure, I'm gonna fix it!

[steakhal]

PredTrue -> PrecedesMalloc

[martong]

Okay, I think this change is aligned with the checker's original logic. I.e. we have a heuristic, so we do not warn if we see a check of the involved variable...
I was digging a bit and found a related SEI CERT rule. MEM35-C Perhaps this checker could warn on the second code example?

On the other hand, on the long term I'd like to see this checker completely removed without any trace. I mean, generally, we should be able to warn if the result of any binary operation may not be represented in the underlying type. I think, this should be handled with an orchestration of a clever constraint solver and the engine.

[steakhal]

In D107804#2950274, @martong wrote:

Okay, I think this change is aligned with the checker's original logic. I.e. we have a heuristic, so we do not warn if we see a check of the involved variable...
I was digging a bit and found a related SEI CERT rule. MEM35-C Perhaps this checker could warn on the second code example?

The checker in it's current form, would warn for the very first example, and only for that example:

void *alloc_blocks(size_t num_blocks) {
  if (num_blocks == 0)
    return NULL;
  unsigned long long alloc = num_blocks * BLOCKSIZE ;
  return (alloc < UINT_MAX) ? malloc(num_blocks * BLOCKSIZE ) : NULL;
  // expected-warning@-1 {{the computation of the size of the memory allocation may overflow}}
}

It wouldn't warn for the rest of the examples because those have some sort of comparison checks on the variable.

On the other hand, on the long term I'd like to see this checker completely removed without any trace. I mean, generally, we should be able to warn if the result of any binary operation may not be represented in the underlying type. I think this should be handled with an orchestration of a clever constraint solver and the engine.

We cannot have a witness for overflow if we calculate on unknown symbolic values, like top-level function parameters, etc. In that sense, the checker relaxes the bug condition to look for potential overflowing multiplications in a specific context, in malloc parameters. That being said, a smarter constraint solver wouldn't help much.

[martong]

clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

163

Do we somehow assure that the two locations are inside the same stack frame? I mean @balazske has a point and I think this solution is okay if we compare two locations inside the same function.

clang/test/Analysis/malloc-overflow.c

115–124

What happens if the check happens in an inlined function? The location is above the malloc in the TU, isn't it?

int check(int n) 
  return (n > 10);
}

void *check_before_malloc(int n, int x) {
  int *p = NULL;
  if (x == 42)
    p = malloc(n * sizeof(int)); // no-warning?

  if (check(n))
    return NULL;

  // Do some other stuff, e.g. initialize the memory.
  return p;
}

[steakhal]

Add a test using macros. It demonstrates that the source locations are properly resolved.
@martong Let me know if you have anything.

clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

163

I would assert this fact, but I'm not exactly sure how to acquire the enclosing function of a SourceLocation.

clang/test/Analysis/malloc-overflow.c

115–124

The checker conducts a simple AST-matching, thus it wouldn't resolve the check(n) call. So, the checker will fire regardless of where you put the check(n) call, before or after the malloc().

---

Even in case of macros, it still works. Check the updated test file.

[steakhal]

Pin the -triple to x86_64

[martong]

Upsz-upsz, something went terribly off here! Flexible array members related changes come in with the last diff. For example, the file flexible-array-members.c came in. It might be perhaps a rebase issue if the FAM related change had been commited already, could you please rebase this patch?

[steakhal]

The right diff this time :D

[martong]

Thanks, LGTM!

[steakhal]

Rebased. Removed the given limitation from the user-facing documentation, that this patch fixes.

[martong]

Probably it is too late, but the title of this change is misleading. I think is should be either MallocOverflow should consider comparisons AFTER malloc or MallocOverflow should NOT consider comparisons only preceding malloc.

clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

 #include <utility>
 
 using namespace clang;
 using namespace ento;
 using llvm::APSInt;
 
 namespace {
 struct MallocOverflowCheck {
+  const CallExpr *call;
   const BinaryOperator *mulop;
   const Expr *variable;
   APSInt maxVal;
 
-  MallocOverflowCheck(const BinaryOperator *m, const Expr *v, APSInt val)
-      : mulop(m), variable(v), maxVal(std::move(val)) {}
+  MallocOverflowCheck(const CallExpr *call, const BinaryOperator *m,
+                      const Expr *v, APSInt val)
+      : call(call), mulop(m), variable(v), maxVal(std::move(val)) {}
 };
 
 class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
 public:
   void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
                         BugReporter &BR) const;
 
   void CheckMallocArgument(
       SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
-    const Expr *TheArgument, ASTContext &Context) const;
+      const CallExpr *TheCall, ASTContext &Context) const;
 
   void OutputPossibleOverflows(
     SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
     const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
 
 };
 } // end anonymous namespace
 
 // Return true for computations which evaluate to zero: e.g., mult by 0.
 static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
   return (op == BO_Mul) && (Val == 0);
 }
 
 void MallocOverflowSecurityChecker::CheckMallocArgument(
     SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
-  const Expr *TheArgument,
-  ASTContext &Context) const {
+    const CallExpr *TheCall, ASTContext &Context) const {
 
   /* Look for a linear combination with a single variable, and at least
    one multiplication.
    Reject anything that applies to the variable: an explicit cast,
    conditional expression, an operation that could reduce the range
    of the result, or anything too complicated :-).  */
-  const Expr *e = TheArgument;
+  const Expr *e = TheCall->getArg(0);
   const BinaryOperator * mulop = nullptr;
   APSInt maxVal;
 
   for (;;) {
     maxVal = 0;
     e = e->IgnoreParenImpCasts();
     if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) {
       BinaryOperatorKind opc = binop->getOpcode();
void MallocOverflowSecurityChecker::CheckMallocArgument(
 
   if (mulop == nullptr)
     return;
 
   //  We've found the right structure of malloc argument, now save
   // the data so when the body of the function is completely available
   // we can check for comparisons.
 
-  // TODO: Could push this into the innermost scope where 'e' is
-  // defined, rather than the whole function.
-  PossibleMallocOverflows.push_back(MallocOverflowCheck(mulop, e, maxVal));
+  PossibleMallocOverflows.push_back(
+      MallocOverflowCheck(TheCall, mulop, e, maxVal));
 }
 
 namespace {
 // A worker class for OutputPossibleOverflows.
 class CheckOverflowOps :
   public EvaluatedExprVisitor<CheckOverflowOps> {
 public:
   typedef SmallVectorImpl<MallocOverflowCheck> theVecType;
void Erase(const T1 *DR,
           return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
         return false;
       };
       toScanFor.erase(std::remove_if(toScanFor.begin(), toScanFor.end(), P),
                       toScanFor.end());
     }
 
     void CheckExpr(const Expr *E_p) {
-      auto PredTrue = [](const MallocOverflowCheck &) { return true; };
       const Expr *E = E_p->IgnoreParenImpCasts();
+      const auto PrecedesMalloc = [E, this](const MallocOverflowCheck &c) {
+        return Context.getSourceManager().isBeforeInTranslationUnit(
+            E->getExprLoc(), c.call->getExprLoc());
+      };
       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
-        Erase<DeclRefExpr>(DR, PredTrue);
+        Erase<DeclRefExpr>(DR, PrecedesMalloc);
       else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
-        Erase<MemberExpr>(ME, PredTrue);
+        Erase<MemberExpr>(ME, PrecedesMalloc);
       }
     }
 
     // Check if the argument to malloc is assigned a value
     // which cannot cause an overflow.
     // e.g., malloc (mul * x) and,
     // case 1: mul = <constant value>
     // case 2: mul = a/b, where b > x
for (CFGBlock::iterator bi = block->begin(), be = block->end();
 
           // Get the name of the callee. If it's a builtin, strip off the prefix.
           IdentifierInfo *FnInfo = FD->getIdentifier();
           if (!FnInfo)
             continue;
 
           if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
             if (TheCall->getNumArgs() == 1)
-              CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
+              CheckMallocArgument(PossibleMallocOverflows, TheCall,
                                   mgr.getASTContext());
           }
         }
       }
     }
   }
 
   OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);

clang/test/Analysis/malloc-overflow.c

 }
 
 void * f14(int n)
 {
   if (n < 0)
     return NULL;
   return malloc(n * sizeof(int));  // expected-warning {{the computation of the size of the memory allocation may overflow}}
 }
+
+void *check_before_malloc(int n, int x) {
+  int *p = NULL;
+  if (n > 10)
+    return NULL;
+  if (x == 42)
+    p = malloc(n * sizeof(int)); // no-warning, the check precedes the allocation
+
+  // Do some other stuff, e.g. initialize the memory.
+  return p;
+}
+
+void *check_after_malloc(int n, int x) {
+  int *p = NULL;
+  if (x == 42)
+    p = malloc(n * sizeof(int)); // expected-warning {{the computation of the size of the memory allocation may overflow}}
+
+  // The check is after the allocation!
+  if (n > 10) {
+    // Do something conditionally.
+  }
+  return p;
+}