[clang][Analyzer] Handle flexible arrays better in ArrayBoundV2 checker.

[balazske]

Summary

This is an experimental fix for ArrayBoundV2 checker to handle "flexible arrays"
(incomplete array) better. If incomplete array is found to be indexed, the
used size (for out-of-bounds check) will be the dynamic size of base region,
with offset (of the incomplete array) taken into account.
In this was indexing of incomplete arrays is not reported as error,
if the array was allocated using a fixed size.

[martong]

The tests are really promising! :)

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

117

Do we need an overload perhaps in DynamicSize.h of

SVal getDynamicSizeWithOffset(ProgramStateRef State, const SVal &BufV)

that takes a MemRegion?

[balazske]

It works not reliable for all data types. If char is used instead of int (in the test), the allocated size may be larger than the intended size of the array, probably because memory alignment adjustments. In the following case it is possible to index "past the end" of the array for some first indices (until 12?).

struct S {
  int n;
  char x;
  char s[];
};
struct S *s = (struct S *)malloc(sizeof(struct S) + 10);
s.s[12] = 12;

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

117

If the change is accepted then yes, or have only the MemRegion version.

[martong]

In D99714#2663677, @balazske wrote:

It works not reliable for all data types. If char is used instead of int (in the test), the allocated size may be larger than the intended size of the array, probably because memory alignment adjustments. In the following case it is possible to index "past the end" of the array for some first indices (until 12?).

struct S {
  int n;
  char x;
  char s[];
};

struct S *s = (struct S *)malloc(sizeof(struct S) + 10);
s.s[12] = 12;

Then I suppose we have to consider the alignment info as well. Perhaps you could reuse some parts of the PlacementNewChecker's alignment checking implementation? (see https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp#L176 ) I'd do that only in second follow-up patch, because that is going to complicate things.

[martong]

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

117

I think this is the other way around, let's create the overload then we accept.

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) {
         break;
       }
     }
   }
 
   return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
 }
 
+namespace {
+SVal getDynamicSizeWithOffset(ProgramStateRef State, const MemRegion *MRegion) {
+  SValBuilder &SvalBuilder = State->getStateManager().getSValBuilder();
+  if (!MRegion)
+    return UnknownVal();
+  RegionOffset Offset = MRegion->getAsOffset();
+  if (Offset.hasSymbolicOffset())
+    return UnknownVal();
+  const MemRegion *BaseRegion = MRegion->getBaseRegion();
+  if (!BaseRegion)
+    return UnknownVal();
+
+  NonLoc OffsetInBytes = SvalBuilder.makeArrayIndex(
+      Offset.getOffset() /
+      MRegion->getMemRegionManager().getContext().getCharWidth());
+  DefinedOrUnknownSVal ExtentInBytes =
+      getDynamicSize(State, BaseRegion, SvalBuilder);
+
+  return SvalBuilder.evalBinOp(State, BinaryOperator::Opcode::BO_Sub,
+                               ExtentInBytes, OffsetInBytes,
+                               SvalBuilder.getArrayIndexType());
+}
+} // namespace
+
 void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad,
                                         const Stmt* LoadS,
                                         CheckerContext &checkerContext) const {
 
   // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping
   // some new logic here that reasons directly about memory region extents.
   // Once that logic is more mature, we can bring it back to assumeInBound()
   // for all clients to use.
   //
   // The algorithm we are using here for bounds checking is to see if the
   // memory access is within the extent of the base region.  Since we
   // have some flexibility in defining the base region, we can achieve
   // various levels of conservatism in our buffer overflow checking.
   ProgramStateRef state = checkerContext.getState();
 
   SValBuilder &svalBuilder = checkerContext.getSValBuilder();
   const RegionRawOffsetV2 &rawOffset =
     RegionRawOffsetV2::computeOffset(state, svalBuilder, location);
 
   if (!rawOffset.getRegion())
     return;
 
   NonLoc rawOffsetVal = rawOffset.getByteOffset();
 
+  bool IsIncompleteArray = false;
+  if (const auto *ASExpr = dyn_cast_or_null<ArraySubscriptExpr>(LoadS))
+    IsIncompleteArray = isa<IncompleteArrayType>(
+        ASExpr->getBase()->IgnoreParenImpCasts()->getType().getCanonicalType());
+
   // CHECK LOWER BOUND: Is byteOffset < extent begin?
   //  If so, we are doing a load/store
   //  before the first valid offset in the memory region.
 
   SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion());
 
   if (Optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
     if (NV->getAs<nonloc::ConcreteInt>()) {
if (Optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
     state = state_withinLowerBound;
   }
 
   do {
     // CHECK UPPER BOUND: Is byteOffset >= size(baseRegion)?  If so,
     // we are doing a load/store after the last valid offset.
     const MemRegion *MR = rawOffset.getRegion();
     DefinedOrUnknownSVal Size = getDynamicSize(state, MR, svalBuilder);
+
+    if (IsIncompleteArray) {
+      SVal DSWithOffset = getDynamicSizeWithOffset(state, MR);
+      if (auto Val = DSWithOffset.getAs<DefinedOrUnknownSVal>())
+        Size = *Val;
+    }
+
     if (!Size.getAs<NonLoc>())
       break;
 
     if (Size.getAs<nonloc::ConcreteInt>()) {
       std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
           getSimplifiedOffsets(rawOffset.getByteOffset(),
                                Size.castAs<nonloc::ConcreteInt>(), svalBuilder);
       rawOffsetVal = simplifiedOffsets.first;

clang/test/Analysis/array-bound-v2.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc,alpha.security.ArrayBoundV2 %s
+
+//#include <stdlib.h>
+//#include "Inputs/system-header-simulator-cxx.h"
+
+typedef __typeof(sizeof(int)) size_t;
+void *malloc(size_t);
+
+struct FlexArr {
+  int n;
+  int s0[2];
+  int s[];
+};
+
+struct Outer {
+  int n;
+  struct FlexArr FA;
+};
+
+void test_flex() {
+  struct FlexArr *p = (struct FlexArr *)malloc(sizeof(struct FlexArr) + sizeof(int) * 10);
+  p->n = 10;
+  p->s[0] = 0;
+  p->s[9] = 9;
+  p->s[10] = 10; // expected-waring{{Out of bound memory access}}
+}
+
+void test_simple() {
+  struct FlexArr *p = (struct FlexArr *)malloc(sizeof(struct FlexArr) + sizeof(int) * 10);
+  p->n = 10;
+  p->s0[0] = 0;
+  p->s0[1] = 1;
+  p->s0[2] = 2; // expected-waring{{Out of bound memory access}}
+}
+
+void test_outer_flex() {
+  struct Outer *p = (struct Outer *)malloc(sizeof(struct Outer) + sizeof(int) * 10);
+  p->FA.s[0] = 0;
+  p->FA.s[9] = 9;
+  p->FA.s[10] = 10; // expected-waring{{Out of bound memory access}}
+}
+
+void test_outer_simple() {
+  struct Outer *p = (struct Outer *)malloc(sizeof(struct Outer) + sizeof(int) * 10);
+  p->FA.s0[0] = 0;
+  p->FA.s0[1] = 1;
+  p->FA.s0[2] = 2; // expected-waring{{Out of bound memory access}}
+}