[Analyzer][VLASizeChecker] Check for VLA size overflow.

[balazske]

Summary

Variable-length array (VLA) should have a size that fits into
a size_t value. According to the standard: "std::size_t can
store the maximum size of a theoretically possible object of
any type (including array)" (this is applied to C too).

The size expression is evaluated at the definition of the
VLA type even if this is a typedef.
The evaluation of the size expression in itself might cause
problems if it overflows.

[martong]

clang/test/Analysis/vla.c

107

I think we could make the arithmetic more clear here:
x = BIGINDEX 65536 (2^16) and char[x][x][x][x] would be the first to overflow.
And char[x][x][x][x-1] should not overflow.

And if we are at it, then size_t's range is target dependent, so I think we must extend the RUN line with -target.

[balazske]

Question: Is there a way to check for overflow in the symbolic domain (that is the ArrSize value)? Or get the maximal possible value of a SVal if it is constrained? (The ArrSize that is a multiplication of every dimension size can not be checked simply for too big value symbolically because calculation overflows are not detected.)

[martong]

Would it be possible to split this patch into two?

1. The refactoring part where you move code out from checkPreStmt to checkVLA. This should be an NFC.
2. Handling of the overflow.

Would be much cleaner I guess.

[balazske]

I do not know if it would me much cleaner.

• First part: Move calculation of ArraySize into checkVLA and rename checkVLASize to checkVLAIndexSize.
• Second part: Add the check for total array size to checkVLA.

The first part in itself does not make sense necessarily until we see why this change is needed (this is, because the total size is checked and that calculation needs the same data and the total size should be checked both places where checkVLA is used). The original code is not much better than after this "part 1" refactoring, computation of ArraySize is needed only once not at both places where checkVLAis called (but it is needed to implement "part 2").

[gamesh411]

With the minor adjustment in the one test case this LGTM.

clang/test/Analysis/vla.c

107

I would also find the extra comment and the extra passing test case helpful.

[balazske]

Added target dependent tests.

[Szelethus]

clang/test/Analysis/vla-overflow.c

10 ↗

(On Diff #263151)

Let's not trim be checker name here.

Also, we could mention what the specific size is.

[Szelethus]

Variable-length array (VLA) should have a size that fits into a size_t value. At least if the size is queried with sizeof, but it is better (and more simple) to check it always

So creating VLA larger than sizeof(size_t) isn't a bug, bur rather a sign of code smell? Then we shouldn't create a fatal error node for it, unless we're trying to fit it in a variable that isn't sufficiently large. The fact that sizeofing it is a bug wasn't immediately obvious to me either, so a quote from the standard as comments would be appreciated:

§6.5.3.4.4, about operator sizeof: The value of the result is implementation-defined, and its type (an unsigned integer type) is size_t, defined in <stddef.h> (and other headers).

[martong]

In D79330#2026564, @balazske wrote:

I do not know if it would me much cleaner.

• First part: Move calculation of ArraySize into checkVLA and rename checkVLASize to checkVLAIndexSize.
• Second part: Add the check for total array size to checkVLA.

The first part in itself does not make sense necessarily until we see why this change is needed (this is, because the total size is checked and that calculation needs the same data and the total size should be checked both places where checkVLA is used). The original code is not much better than after this "part 1" refactoring, computation of ArraySize is needed only once not at both places where checkVLAis called (but it is needed to implement "part 2").

Alright, makes sense, so let's just disregard the refactoring comment.

[martong]

In D79330#2033990, @Szelethus wrote:

Variable-length array (VLA) should have a size that fits into a size_t value. At least if the size is queried with sizeof, but it is better (and more simple) to check it always

So creating VLA larger than sizeof(size_t) isn't a bug, bur rather a sign of code smell? Then we shouldn't create a fatal error node for it, unless we're trying to fit it in a variable that isn't sufficiently large. The fact that sizeofing it is a bug wasn't immediately obvious to me either, so a quote from the standard as comments would be appreciated:

§6.5.3.4.4, about operator sizeof: The value of the result is implementation-defined, and its type (an unsigned integer type) is size_t, defined in <stddef.h> (and other headers).

I am not sure if I can follow your concern here.
sizeof(size_t) is typically 8, so that is not a bug, neither a code smell to have char VLA[sizeof(size_t)];. The problem is when the size is bigger than the maximum value of size_t, that ix 0xff...ff, as we can see that in the new tests.
Besides, not having the size printed out in the warning is not a blocker for me, this looks good enough.

clang/test/Analysis/vla-overflow.c

10 ↗

(On Diff #263151)

Yes, that's a good idea to print the actual size of the VLA when we have that info. But I think we cannot just print that when it overflows! :D We can, however, print the maximum allowed value in case of the overflow.

[Szelethus]

In D79330#2034414, @martong wrote:

I am not sure if I can follow your concern here.
sizeof(size_t) is typically 8, so that is not a bug, neither a code smell to have char VLA[sizeof(size_t)];. The problem is when the size is bigger than the maximum value of size_t, that ix 0xff...ff, as we can see that in the new tests.
Besides, not having the size printed out in the warning is not a blocker for me, this looks good enough.

Silly me. The size would be nice, but if we don't explain how we calculated that size, it wouldn't make the bug report much better.

[balazske]

In D79330#2033990, @Szelethus wrote:

Variable-length array (VLA) should have a size that fits into a size_t value. At least if the size is queried with sizeof, but it is better (and more simple) to check it always

So creating VLA larger than sizeof(size_t) isn't a bug, bur rather a sign of code smell? Then we shouldn't create a fatal error node for it, unless we're trying to fit it in a variable that isn't sufficiently large. The fact that sizeofing it is a bug wasn't immediately obvious to me either, so a quote from the standard as comments would be appreciated:

§6.5.3.4.4, about operator sizeof: The value of the result is implementation-defined, and its type (an unsigned integer type) is size_t, defined in <stddef.h> (and other headers).

I was looking at CERT ARR32-C "Ensure size arguments for variable length arrays are in a valid range". The VLA should not have a size that is larger than std::numeric_limits<size_t>::max(), in other words "fit into a size_t value", or not?

Yes creating the too large VLA in itself is not a bug, only when sizeof is called on it because it can not return the correct size. A non-fatal error is a better option, or delay the check until the sizeof call. But probably the create of such a big array in itself is sign of code smell. The array actually does not need to be created to make the problem happen, only a sizeof call on a typedef-ed and too large VLA. (What does mean that "result of sizeof is implementation-defined"? Probably it can return not the size in bytes or "chars" but something other? In such a case the checker would be not correct.)

[balazske]

Is it worth to improve the checker by emitting a warning only if a sizeof is used on a typedef-ed VLA type where the size is too large (and at a VLA declaration with size overflow)? Or can this be done in a later change?

[whisperity]

clang/test/Analysis/vla-overflow.c

8 ↗

(On Diff #263151)

While it's generally true nowadays, instead of a comment, perhaps turn this (sizeof(size_t) >= 8) into an assert, or a condition.

[whisperity]

In D79330#2035850, @balazske wrote:

I was looking at CERT ARR32-C "Ensure size arguments for variable length arrays are in a valid range". The VLA should not have a size that is larger than std::numeric_limits<size_t>::max(), in other words "fit into a size_t value", or not?

Yes creating the too large VLA in itself is not a bug, only when sizeof is called on it because it can not return the correct size. A non-fatal error is a better option, or delay the check until the sizeof call. But probably the create of such a big array in itself is sign of code smell. The array actually does not need to be created to make the problem happen, only a sizeof call on a typedef-ed and too large VLA. (What does mean that "result of sizeof is implementation-defined"? Probably it can return not the size in bytes or "chars" but something other? In such a case the checker would be not correct.)

In D79330#2036340, @balazske wrote:

Is it worth to improve the checker by emitting a warning only if a sizeof is used on a typedef-ed VLA type where the size is too large (and at a VLA declaration with size overflow)? Or can this be done in a later change?

The result of sizeof is implementation-defined because the size of types is implementation-defined in the first place (obeying a few other rules). This covers the part that the standard does not say that the result value will be 5 or 7 or 92. The type which sizeof() returns is a size_t, which in itself is an implementation-defined type, depending on target architecture). This is why the result of sizeof is implementation-defined.

However, the following is said about size_t:

std::size_t can store the maximum size of a theoretically possible object of any type (including array). A type whose size cannot be represented by std::size_t is ill-formed (since C++14)

(The first sentence applies for C, too.)

I would reason from this that in case we know there is a type which cannot be reasoned about with sizeof then this type is bad. This conforms to what ARR32-C says.
The problem is that if you have an overflown sized array, at the point of allocation, the code generated will use this overflown size, which opens the door for a plethora of vulnerabilities.

I think we should aim for making the project safe and proper by eliminating bad code, instead of hunting purely the word of the law. If the intention visible in the code can lead to the system blowing up, let's keep the warning there where it is easiest to fix.

[balazske]

Rebase, added checker name to overflow test.

[NoQ]

https://bugs.llvm.org/show_bug.cgi?id=46128 looks like a crash caused by this patch.

[balazske]

Strange: Even if the assume for zero index size does not indicate problem (assume that index length is not zero) the getKnownValue returns 0 for it.

clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp

 using namespace ento;
 using namespace taint;
 
 namespace {
 class VLASizeChecker
     : public Checker<check::PreStmt<DeclStmt>,
                      check::PreStmt<UnaryExprOrTypeTraitExpr>> {
   mutable std::unique_ptr<BugType> BT;
-  enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative };
+  enum VLASize_Kind {
+    VLA_Garbage,
+    VLA_Zero,
+    VLA_Tainted,
+    VLA_Negative,
+    VLA_Overflow
+  };
 
   ProgramStateRef checkVLA(CheckerContext &C, ProgramStateRef State,
-                           const VariableArrayType *VLA,
-                           const VariableArrayType *&VLALast,
-                           llvm::SmallVector<const Expr *, 2> &VLASizes) const;
-  ProgramStateRef checkVLASize(CheckerContext &C, ProgramStateRef State,
+                           const VariableArrayType *VLA, SVal &ArraySize) const;
+  ProgramStateRef checkVLAIndexSize(CheckerContext &C, ProgramStateRef State,
                                     const Expr *SizeE) const;
 
   void reportBug(VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State,
                  CheckerContext &C,
                  std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const;
 
 public:
   void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
   void checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE,
                     CheckerContext &C) const;
 };
 } // end anonymous namespace
 
-ProgramStateRef
-VLASizeChecker::checkVLA(CheckerContext &C, ProgramStateRef State,
+ProgramStateRef VLASizeChecker::checkVLA(CheckerContext &C,
+                                         ProgramStateRef State,
                                          const VariableArrayType *VLA,
-                         const VariableArrayType *&VLALast,
-                         llvm::SmallVector<const Expr *, 2> &VLASizes) const {
+                                         SVal &ArraySize) const {
   assert(VLA && "Function should be called with non-null VLA argument.");
 
-  VLALast = nullptr;
+  const VariableArrayType *VLALast = nullptr;
+  llvm::SmallVector<const Expr *, 2> VLASizes;
+
   // Walk over the VLAs for every dimension until a non-VLA is found.
   // Collect the sizes in VLASizes, put the most inner VLA to `VLALast`.
   // In "vla[x][2][y][3]" this will be the array for index "y".
   // There is a VariableArrayType for every dimension (here "x", "2", "y")
   // until a non-vla is found.
   while (VLA) {
     const Expr *SizeE = VLA->getSizeExpr();
-    State = checkVLASize(C, State, SizeE);
+    State = checkVLAIndexSize(C, State, SizeE);
     if (!State)
       return nullptr;
     VLASizes.push_back(SizeE);
     VLALast = VLA;
     VLA = C.getASTContext().getAsVariableArrayType(VLA->getElementType());
   };
   assert(VLALast &&
          "Array should have at least one variably-modified dimension.");
 
+  ASTContext &Ctx = C.getASTContext();
+  SValBuilder &SVB = C.getSValBuilder();
+  CanQualType SizeTy = Ctx.getSizeType();
+  uint64_t SizeMax =
+      SVB.getBasicValueFactory().getMaxValue(SizeTy).getZExtValue();
+
+  // Get the element size.
+  CharUnits EleSize = Ctx.getTypeSizeInChars(VLALast->getElementType());
+  NonLoc ArrSize =
+      SVB.makeIntVal(EleSize.getQuantity(), SizeTy).castAs<NonLoc>();
+
+  // Try to calculate the known real size of the array in KnownSize.
+  uint64_t KnownSize = 0;
+  if (const llvm::APSInt *KV = SVB.getKnownValue(State, ArrSize))
+    KnownSize = KV->getZExtValue();
+
+  for (const Expr *SizeE : VLASizes) {
+    auto SizeD = C.getSVal(SizeE).castAs<DefinedSVal>();
+    // Convert the array length to size_t.
+    NonLoc IndexLength =
+        SVB.evalCast(SizeD, SizeTy, SizeE->getType()).castAs<NonLoc>();
+    // Multiply the array length by the element size.
+    SVal Mul = SVB.evalBinOpNN(State, BO_Mul, ArrSize, IndexLength, SizeTy);
+    if (auto MulNonLoc = Mul.getAs<NonLoc>())
+      ArrSize = *MulNonLoc;
+    else
+      // Extent could not be determined.
       return State;
+
+    if (const llvm::APSInt *IndexLVal = SVB.getKnownValue(State, IndexLength)) {
+      // Check if the array size will overflow.
+      // Size overflow check does not work with symbolic expressions because a
+      // overflow situation can not be detected easily.
+      uint64_t IndexL = IndexLVal->getZExtValue();
+      assert(IndexL > 0 && "Index length should have been checked for zero.");
+      if (KnownSize <= SizeMax / IndexL) {
+        KnownSize *= IndexL;
+      } else {
+        // Array size does not fit into size_t.
+        reportBug(VLA_Overflow, SizeE, State, C);
+        return nullptr;
+      }
+    } else {
+      KnownSize = 0;
     }
+  }
+
+  ArraySize = ArrSize;
 
-ProgramStateRef VLASizeChecker::checkVLASize(CheckerContext &C,
+  return State;
+}
+
+ProgramStateRef VLASizeChecker::checkVLAIndexSize(CheckerContext &C,
                                                   ProgramStateRef State,
                                                   const Expr *SizeE) const {
   SVal SizeV = C.getSVal(SizeE);
 
   if (SizeV.isUndef()) {
     reportBug(VLA_Garbage, SizeE, State, C);
     return nullptr;
   }
 
   // See if the size value is known. It can't be undefined because we would have
ProgramStateRef VLASizeChecker::checkVLAIndexSize(CheckerContext &C,
   SVal LessThanZeroVal = SVB.evalBinOp(State, BO_LT, SizeD, Zero, SizeTy);
   if (Optional<DefinedSVal> LessThanZeroDVal =
           LessThanZeroVal.getAs<DefinedSVal>()) {
     ConstraintManager &CM = C.getConstraintManager();
     ProgramStateRef StatePos, StateNeg;
 
     std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal);
     if (StateNeg && !StatePos) {
-      reportBug(VLA_Negative, SizeE, State, C); // FIXME: StateNeg ?
+      reportBug(VLA_Negative, SizeE, State, C);
       return nullptr;
     }
     State = StatePos;
   }
 
   return State;
 }
 
case VLA_Zero:
     os << "has zero size";
     break;
   case VLA_Tainted:
     os << "has tainted size";
     break;
   case VLA_Negative:
     os << "has negative size";
     break;
+  case VLA_Overflow:
+    os << "has too large size";
+    break;
   }
 
   auto report = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N);
   report->addVisitor(std::move(Visitor));
   report->addRange(SizeE->getSourceRange());
   bugreporter::trackExpressionValue(N, SizeE, *report);
   C.emitReport(std::move(report));
 }
void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
   else
     return;
 
   const VariableArrayType *VLA = Ctx.getAsVariableArrayType(TypeToCheck);
   if (!VLA)
     return;
 
   // Check the VLA sizes for validity.
-  llvm::SmallVector<const Expr *, 2> VLASizes;
-  const VariableArrayType *VLALast = nullptr;
 
-  State = checkVLA(C, State, VLA, VLALast, VLASizes);
+  SVal ArraySize;
+
+  State = checkVLA(C, State, VLA, ArraySize);
   if (!State)
     return;
 
-  if (!VD)
+  auto ArraySizeNL = ArraySize.getAs<NonLoc>();
+  if (!ArraySizeNL) {
+    // Array size could not be determined but state may contain new assumptions.
+    C.addTransition(State);
     return;
+  }
 
   // VLASizeChecker is responsible for defining the extent of the array being
   // declared. We do this by multiplying the array length by the element size,
   // then matching that with the array region's extent symbol.
 
-  CanQualType SizeTy = Ctx.getSizeType();
-  // Get the element size.
-  CharUnits EleSize = Ctx.getTypeSizeInChars(VLALast->getElementType());
-  NonLoc ArraySize =
-      SVB.makeIntVal(EleSize.getQuantity(), SizeTy).castAs<NonLoc>();
-
-  for (const Expr *SizeE : VLASizes) {
-    auto SizeD = C.getSVal(SizeE).castAs<DefinedSVal>();
-    // Convert the array length to size_t.
-    NonLoc IndexLength =
-        SVB.evalCast(SizeD, SizeTy, SizeE->getType()).castAs<NonLoc>();
-    // Multiply the array length by the element size.
-    SVal Mul = SVB.evalBinOpNN(State, BO_Mul, ArraySize, IndexLength, SizeTy);
-    if (auto MulNonLoc = Mul.getAs<NonLoc>()) {
-      ArraySize = *MulNonLoc;
-    } else {
-      // Extent could not be determined.
-      // The state was probably still updated by the validation checks.
-      C.addTransition(State);
-      return;
-    }
-  }
-
-  // Finally, assume that the array's size matches the given size.
+  if (VD) {
+    // Assume that the array's size matches the region size.
     const LocationContext *LC = C.getLocationContext();
     DefinedOrUnknownSVal DynSize =
         getDynamicSize(State, State->getRegion(VD, LC), SVB);
 
-  DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, ArraySize);
+    DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, *ArraySizeNL);
     State = State->assume(SizeIsKnown, true);
 
     // Assume should not fail at this point.
     assert(State);
+  }
 
   // Remember our assumptions!
   C.addTransition(State);
 }
 
 void VLASizeChecker::checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE,
                                   CheckerContext &C) const {
   // Want to check for sizeof.
   if (UETTE->getKind() != UETT_SizeOf)
     return;
 
   // Ensure a type argument.
   if (!UETTE->isArgumentType())
     return;
 
-  const VariableArrayType *VLA =
-      C.getASTContext().getAsVariableArrayType(UETTE->getTypeOfArgument());
+  const VariableArrayType *VLA = C.getASTContext().getAsVariableArrayType(
+      UETTE->getTypeOfArgument().getCanonicalType());
   // Ensure that the type is a VLA.
   if (!VLA)
     return;
 
   ProgramStateRef State = C.getState();
-
-  llvm::SmallVector<const Expr *, 2> VLASizes;
-  const VariableArrayType *VLALast = nullptr;
-  State = checkVLA(C, State, VLA, VLALast, VLASizes);
+  SVal ArraySize;
+  State = checkVLA(C, State, VLA, ArraySize);
   if (!State)
     return;
 
   C.addTransition(State);
 }
 
 void ento::registerVLASizeChecker(CheckerManager &mgr) {
   mgr.registerChecker<VLASizeChecker>();
 }
 
 bool ento::shouldRegisterVLASizeChecker(const CheckerManager &mgr) {
   return true;
 }

clang/test/Analysis/vla.c

 }
 
 size_t check_VLA_sizeof() {
   int x = -1;
   size_t s = sizeof(int[x]); // expected-warning{{Declared variable-length array (VLA) has negative size}}
   return s;
 }
 
+#define BIGINDEX 65535U
+
+size_t check_VLA_overflow_sizeof(unsigned int x) {
+  if (x == BIGINDEX) {
+    size_t s = sizeof(int[x][x][x][x]); // expected-warning{{Declared variable-length array (VLA) has too large size}}
+    return s;
+  }
+  return 0;
+}
+
+void check_VLA_overflow_typedef() {
+  unsigned int x = BIGINDEX;
+  typedef int VLA[x][x][x][x]; // expected-warning{{Declared variable-length array (VLA) has too large size}}
+}
+
 // Multi-dimensional arrays.
 
 void check_zero_sized_VLA_multi1(int x) {
   if (x)
     return;
 
   int vla[10][x]; // expected-warning{{Declared variable-length array (VLA) has zero size}}
 }