[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 ↗

(On Diff #365386)

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

165 ↗

(On Diff #365386)

This is not a PredTrue any more.

[steakhal]

clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

163 ↗

(On Diff #365386)

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

165 ↗

(On Diff #365386)

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 ↗

(On Diff #365386)

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 ↗

(On Diff #365921)

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 ↗

(On Diff #365386)

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 ↗

(On Diff #365921)

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/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def

 ANALYZER_OPTION(bool, ShouldApplyFixIts, "apply-fixits",
                 "Apply the fix-it hints to the files",
                 false)
 
 ANALYZER_OPTION(bool, ShouldDisplayCheckerNameForText, "display-checker-name",
                 "Display the checker name for textual outputs",
                 true)
 
+ANALYZER_OPTION(
+    bool, ShouldConsiderSingleElementArraysAsFlexibleArrayMembers,
+    "consider-single-element-arrays-as-flexible-array-members",
+    "Consider single element arrays as flexible array member candidates. "
+    "This will prevent the analyzer from assuming that a single element array "
+    "holds a single element.",
+    false)
+
 //===----------------------------------------------------------------------===//
 // Unsigned analyzer options.
 //===----------------------------------------------------------------------===//
 
 ANALYZER_OPTION(unsigned, CTUImportThreshold, "ctu-import-threshold",
                 "The maximal amount of translation units that is considered "
                 "for import when inlining functions during CTU analysis. "
                 "Lowering this threshold can alleviate the memory burden of "

clang/lib/StaticAnalyzer/Core/MemRegion.cpp

 #include "clang/AST/PrettyPrinter.h"
 #include "clang/AST/RecordLayout.h"
 #include "clang/AST/Type.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/Support/BumpVector.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SmallString.h"
DefinedOrUnknownSVal MemRegionManager::getStaticSize(const MemRegion *MR,
   case MemRegion::FieldRegionKind: {
     // Force callers to deal with bitfields explicitly.
     if (cast<FieldRegion>(SR)->getDecl()->isBitField())
       return UnknownVal();
 
     QualType Ty = cast<TypedValueRegion>(SR)->getDesugaredValueType(Ctx);
     const DefinedOrUnknownSVal Size = getElementExtent(Ty, SVB);
 
-    // A zero-length array at the end of a struct often stands for dynamically
-    // allocated extra memory.
-    const auto isFlexibleArrayMemberCandidate = [this](QualType Ty) -> bool {
+    // We currently don't model flexible array members (FAMs), which are:
+    //  - int array[]; of IncompleteArrayType
+    //  - int array[0]; of ConstantArrayType with size 0
+    //  - int array[1]; of ConstantArrayType with size 1 (*)
+    // (*): Consider single element array object members as FAM candidates only
+    //      if the consider-single-element-arrays-as-flexible-array-members
+    //      analyzer option is true.
+    // https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
+    const auto isFlexibleArrayMemberCandidate = [this,
+                                                 &SVB](QualType Ty) -> bool {
       const ArrayType *AT = Ctx.getAsArrayType(Ty);
       if (!AT)
         return false;
       if (isa<IncompleteArrayType>(AT))
         return true;
 
       if (const auto *CAT = dyn_cast<ConstantArrayType>(AT)) {
         const llvm::APInt &Size = CAT->getSize();
         if (Size.isNullValue())
           return true;
+
+        // FIXME: Acquire the AnalyzerOptions in a simpler way.
+        const AnalyzerOptions &Opts = SVB.getStateManager()
+                                          .getOwningEngine()
+                                          .getAnalysisManager()
+                                          .getAnalyzerOptions();
+        if (Opts.ShouldConsiderSingleElementArraysAsFlexibleArrayMembers &&
+            Size.isOneValue())
+          return true;
       }
       return false;
     };
 
     if (isFlexibleArrayMemberCandidate(Ty))
       return UnknownVal();
 
     return Size;

clang/test/Analysis/analyzer-config.c

 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-expand-default-aggr-inits = false
 // CHECK-NEXT: cfg-implicit-dtors = true
 // CHECK-NEXT: cfg-lifetime = false
 // CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-rich-constructors = true
 // CHECK-NEXT: cfg-scopes = false
 // CHECK-NEXT: cfg-temporary-dtors = true
+// CHECK-NEXT: consider-single-element-arrays-as-flexible-array-members = false
 // CHECK-NEXT: core.CallAndMessage:ArgInitializedness = true
 // CHECK-NEXT: core.CallAndMessage:ArgPointeeInitializedness = false
 // CHECK-NEXT: core.CallAndMessage:CXXDeallocationArg = true
 // CHECK-NEXT: core.CallAndMessage:CXXThisMethodCall = true
 // CHECK-NEXT: core.CallAndMessage:FunctionPointer = true
 // CHECK-NEXT: core.CallAndMessage:NilReceiver = true
 // CHECK-NEXT: core.CallAndMessage:ParameterCount = true
 // CHECK-NEXT: core.CallAndMessage:UndefReceiver = true

clang/test/Analysis/flexible-array-members.c

 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c90
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c99
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c11
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c17
 
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c++98 -x c++
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c++03 -x c++
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c++11 -x c++
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c++14 -x c++
 // RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c++17 -x c++
 
+// RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c17 \
+// RUN:    -analyzer-config consider-single-element-arrays-as-flexible-array-members=true -DSINGLE_ELEMENT_FAMS
+// RUN: %clang_analyze_cc1 -triple x86_64-linux-gnu -analyzer-checker=core,unix,debug.ExprInspection %s -verify -std=c++17 -x c++ \
+// RUN:    -analyzer-config consider-single-element-arrays-as-flexible-array-members=true -DSINGLE_ELEMENT_FAMS
+
 typedef __typeof(sizeof(int)) size_t;
 size_t clang_analyzer_getExtent(void *);
 void clang_analyzer_dump(size_t);
 
 void *alloca(size_t size);
 void *malloc(size_t size);
 void free(void *ptr);
 

 }
 
 void test_single_element_array_possible_fam() {
   typedef struct FAM {
     char c;
     int data[1];
   } FAM;
 
+#ifdef SINGLE_ELEMENT_FAMS
+  FAM likely_fam;
+  clang_analyzer_dump(clang_analyzer_getExtent(&likely_fam));
+  clang_analyzer_dump(clang_analyzer_getExtent(likely_fam.data));
+  // expected-warning@-2 {{8 S64b}}
+  // expected-warning@-2 {{Unknown}}
+
+  FAM *p = (FAM *)alloca(sizeof(FAM));
+  clang_analyzer_dump(clang_analyzer_getExtent(p));
+  clang_analyzer_dump(clang_analyzer_getExtent(p->data));
+  // expected-warning@-2 {{8 U64b}}
+  // expected-warning@-2 {{Unknown}}
+
+  FAM *q = (FAM *)malloc(sizeof(FAM));
+  clang_analyzer_dump(clang_analyzer_getExtent(q));
+  clang_analyzer_dump(clang_analyzer_getExtent(q->data));
+  // expected-warning@-2 {{8 U64b}}
+  // expected-warning@-2 {{Unknown}}
+  free(q);
+#else
   FAM likely_fam;
   clang_analyzer_dump(clang_analyzer_getExtent(&likely_fam));
   clang_analyzer_dump(clang_analyzer_getExtent(likely_fam.data));
   // expected-warning@-2 {{8 S64b}}
   // expected-warning@-2 {{4 S64b}}
 
   FAM *p = (FAM *)alloca(sizeof(FAM));
   clang_analyzer_dump(clang_analyzer_getExtent(p));
   clang_analyzer_dump(clang_analyzer_getExtent(p->data));
   // expected-warning@-2 {{8 U64b}}
   // expected-warning@-2 {{4 S64b}}
 
   FAM *q = (FAM *)malloc(sizeof(FAM));
   clang_analyzer_dump(clang_analyzer_getExtent(q));
   clang_analyzer_dump(clang_analyzer_getExtent(q->data));
   // expected-warning@-2 {{8 U64b}}
   // expected-warning@-2 {{4 S64b}}
   free(q);
+#endif
 }