calculate extent size for memory regions allocated by C++ new expression

[dkrupp]

Summary

ArrayBoundChecker did not detect out of bounds memory access errors in case an array was allocated by the new expression.

1. MallocChecker.cpp was updated to calculate the extent size in Bytes similarly how it was done for memory regions allocated by malloc. The size constraint is added for arrays and non-arrays allocated by new.

2. ArrayBoundCheckerV2.cpp was updated to better handle accessing locations preceding a symbolic memory region (such as buf[-1] in test2(..) in out-of-bounds.cpp). So computeExtentBegin(..) was updated to assume that the extent of a symbolic region starts at 0 if we know the size of the extent (as is the case in case of malloc or new).

3. out-of-bounds.cpp contains the relevant test cases for C++.

[zaks.anna]

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1003

I am not sure this code belongs to the malloc checker since it only supports the array bounds checker. Is there a reason it's not part of that checker?

[xazax.hun]

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1003

I think it is part of the malloc checker because it already does something very very similar to malloc, see the MallocMemAux function. So in fact, for the array bounds checker to work properly, the malloc checker should be turned on.

[dkrupp]

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1003

Extent size is used by ArrayBoundChecker, ArrayBoundCheckerV2 and CStringChecker checkers currently. New expression in case of simple allocations (0 allocation) was already handled in Malloc checker , that's why I implemented it there. But I agree it feels odd that one has to switch on unix.Malloc checker to get the size of new allocated heap regions. Should I move this to ArrayBoundChecker or ArrayBoundCheckerV2?

[NoQ]

Thanks for the patch! Not sure why, but i always have warm feelings for the MallocChecker and wish it to improve.

Added minor style comments, joined the "where to put the code" debate.

lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

69

For ease of use, you no longer need to pass svalBuilder here - you can take it from the state->getStateManager().

81

Whitespace slightly off.

83

Perhaps you could consider the memory space of the region, it would look a bit less hacky to me.

In my dreams, i wish heap regions were no longer symbolic regions, and this hack would go away then.

Also, i recall there is a bug in isNull(): in the ConstraintManager class (this time i actually mean the abstract base class of RangeConstraintManager) this function boils down to assume(), but in RangeConstraintManager it is overridden to do a direct lookup into the constraint map; which means that in fact this function does not simplify symbolic expressions before answering. This code is probably unaffected because extents are always either concrete or atomic symbols, but i think i'd make a patch for that.

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

995

This code could use a bit more spaces around "=" and ",".

1003

1. Well, in my dreams, this code should be in the silent operator-new modelling checker, which would be separate from the stateless operator-new bug-finding checker. Then all the checkers that rely on extent would automatically load the modelling checker as a dependency.

2. Yeah, i think many checkers may consider extents, not just array bound; other checkers may appear in the future. This info is very useful, which is why we have the whole symbol class just for that (however, checker communication through constraints on this symbol class wasn't IMHO a good idea, because it's harder for the constraint manager to deal with symbols and constraints rather than with concrete values).

Just wanted to speak out, thoughts below might perhaps be more on-topic

3. The MallocChecker is not just unix.Malloc, but also cplusplus.NewDelete, etc., which makes a lot more sense to leave it here.

4. Consider another part of MallocChecker's job - modeling the memory spaces for symbolic regions (heap vs. unknown). For malloc(), this is done in the checker. For operator-new, it is done in the ExprEngine(!), because this is part of the language rather than a library function. Perhaps ExprEngine would be the proper place for that code as well.

1010

C.getLocationContext() is a bit shorter.

1017

You can castAs<> here. Generally, there's no point in using getAs<> unless you're going to check later.

1026

I think you're not using the fact that R is a SymbolicRegion. You could have as well written if (!isa<SymbolicRegion>(Region)) return.

This would also make variable names a bit more confusing.

1048

Here also you can extract the SValBuilder from the state.

test/Analysis/out-of-bounds.cpp

143

I think you should specify the target triple in the test run-line. Otherwise some buildbot with weird int size might fail (as the triple defaults to the current machine's triple).

[zaks.anna]

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1003

Well, in my dreams, this code should be in the silent operator-new modelling checker, which would be
separate from the stateless operator-new bug-finding checker. Then all the checkers that rely on extent
would automatically load the modelling checker as a dependency.

I agree. This sounds like the best approach! (Though it's not a must have to get the patch in.)

Consider another part of MallocChecker's job - modeling the memory spaces for symbolic regions (heap vs.
unknown). For malloc(), this is done in the checker. For operator-new, it is done in the ExprEngine(!), because
this is part of the language rather than a library function. Perhaps ExprEngine would be the proper place for
that code as well.

Interesting point. Can you clarify the last sentence?

1020

Please, be more explicit that this is not a size of allocation (as in not 1 byte)? Maybe call this ElementCount or something like that.

1021

A bit of code repetition from above. Please, add comments explaining why we need subregion in one case and super region in the other.

Are there test cases for this branch?

1049

This should probably be inline/have different name since it talks about ArrayIndexType and is not reused elsewhere.

test/Analysis/out-of-bounds.cpp

1

Let's use a more specific file name.

[dkrupp]

lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

83

Good point!
region->getMemorySpace() does a very similar recursion as the while loop in this function. So I guess the while loop can be refactored like this:

static SVal computeExtentBegin(SValBuilder &svalBuilder, 
const MemRegion *region) {
  const MemSpaceRegion *SR = region->getMemorySpace();
  if (SR->getKind() == MemRegion::UnknownSpaceRegionKind)
    return UnknownVal();
  else
    return svalBuilder.makeZeroArrayIndex();
 }

All test cases pass. Particularly it filters out this false positive from out-of-bounds.c :

// Don't warn when indexing below the start of a symbolic region's whose 
// base extent we don't know.
int *get_symbolic();
void test_index_below_symboloc() {
  int *buf = get_symbolic();
  buf[-1] = 0; // no-warning;
}

[dkrupp]

I tried to address all your comments.

1. computeExtentBegin() is greatly simplified.
2. addExtendSize() is simplified (scaleValue() function inlined)
3. new testcases added a) allocation and indexing of non-array element (int *ip =new int;) b) allocation of array with run-time size

[dkrupp]

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1017

MemRegion has now method called castAs<>, only getAs<>, so I stayed with it.

1026

I changed the type of Region to SubRegion, hope this is clearer this way.

1055

now inlined

[dkrupp]

issues fixed

[zaks.anna]

I do not have any more comments; however, let's wait for @NoQ to review this as well.
Thanks!

[NoQ]

Looks good!

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

291

Whitespace a bit strange.

1003

Perhaps ExprEngine would be the proper place for that code as well.

Interesting point. Can you clarify the last sentence?

I'm thinking that the standard operator new() should be properly modeled by the analyzer core; we are already doing this with respect to memory space of the region it returns, why not do that for extent as well, somewhere at the same place.

We could probably make a refactoring pass over MallocChecker to move things around and return it to a readable state.

1017

Ouch, i meant, cast<SubRegion>(State->getSVal(NE, LCtx).getAsRegion()) etc.

[dkrupp]

Thanks. Gabor, could you please merge this? I don't have commit right.

lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

static RegionRawOffsetV2 computeOffset(ProgramStateRef state,
                                          SValBuilder &svalBuilder,
                                          SVal location);
 
   void dump() const;
   void dumpToStream(raw_ostream &os) const;
 };
 }
 
 static SVal computeExtentBegin(SValBuilder &svalBuilder,
-                               const MemRegion *region) {
-  while (true)
+                               const MemRegion *region, ProgramStateRef state) {
+  while (true) {
     switch (region->getKind()) {
-      default:
-        return svalBuilder.makeZeroArrayIndex();
-      case MemRegion::SymbolicRegionKind:
-        // FIXME: improve this later by tracking symbolic lower bounds
-        // for symbolic regions.
+    case MemRegion::SymbolicRegionKind: {
+      DefinedOrUnknownSVal extentVal =
+          cast<SubRegion>(region)->getExtent(svalBuilder);
+      // If we known the symbolic region extent size
+      //(e.g. allocated by malloc or new)
+      // we can assume that the region starts at 0.
+      if (!state->isNull(extentVal).isConstrained()) {
         return UnknownVal();
-      case MemRegion::ElementRegionKind:
-        region = cast<SubRegion>(region)->getSuperRegion();
-        continue;
+      } else {
+        return svalBuilder.makeZeroArrayIndex();
+      }
+    }
     }
   }
+}
 
 // TODO: once the constraint manager is smart enough to handle non simplified
 // symbolic expressions remove this function. Note that this can not be used in
 // the constraint manager as is, since this does not handle overflows. It is
 // safe to assume, however, that memory offsets will not overflow.
 static std::pair<NonLoc, nonloc::ConcreteInt>
 getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent,
                      SValBuilder &svalBuilder) {
if (!rawOffset.getRegion())
     return;
 
   NonLoc rawOffsetVal = rawOffset.getByteOffset();
 
   // 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());
+  SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion(),state);
 
   if (Optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
     if (NV->getAs<nonloc::ConcreteInt>()) {
       std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
           getSimplifiedOffsets(rawOffset.getByteOffset(),
                                NV->castAs<nonloc::ConcreteInt>(),
                                svalBuilder);
       rawOffsetVal = simplifiedOffsets.first;

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
                                       const Expr *SizeEx, SVal Init,
                                       ProgramStateRef State,
                                       AllocationFamily Family = AF_Malloc);
   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
                                       SVal SizeEx, SVal Init,
                                       ProgramStateRef State,
                                       AllocationFamily Family = AF_Malloc);
 
+  static ProgramStateRef addExtentSize(CheckerContext &C,
+                                             const CXXNewExpr *NE,
+                                             ProgramStateRef State
+                                             );
+
+  // Scale a base value by a scaling factor, and return the scaled
+  // value as an SVal.
+  static SVal scaleValue(ProgramStateRef State,
+                                  NonLoc BaseVal, CharUnits Scaling,
+                                  SValBuilder &Sb);
+
   // Check if this malloc() for special flags. At present that means M_ZERO or
   // __GFP_ZERO (in which case, treat it like calloc).
   llvm::Optional<ProgramStateRef>
   performKernelMalloc(const CallExpr *CE, CheckerContext &C,
                       const ProgramStateRef &State) const;
 
   /// Update the RefState to reflect the new memory allocation.
   static ProgramStateRef
void MallocChecker::checkPostStmt(const CXXNewExpr *NE,
 
   ProgramStateRef State = C.getState();
   // The return value from operator new is bound to a specified initialization
   // value (if any) and we don't want to loose this value. So we call
   // MallocUpdateRefState() instead of MallocMemAux() which breakes the
   // existing binding.
   State = MallocUpdateRefState(C, NE, State, NE->isArray() ? AF_CXXNewArray
                                                            : AF_CXXNew);
+  State=addExtentSize(C,NE,State);
   State = ProcessZeroAllocation(C, NE, 0, State);
   C.addTransition(State);
 }
 
+// Sets the extent value of the MemRegion allocated by
+// new expression NE to its size in Bytes.
+//
+ProgramStateRef MallocChecker::addExtentSize(CheckerContext &C,
+                                             const CXXNewExpr *NE,
+                                             ProgramStateRef State) {
+  if (!State)
+    return nullptr;
+  SValBuilder &svalBuilder = C.getSValBuilder();
+  SVal Size;
+  const LocationContext *LCtx = C.getPredecessor()->getLocationContext();
+  const MemRegion *Region;
+  if (NE->isArray()) {
+    const Expr *SizeExpr = NE->getArraySize();
+    Size = State->getSVal(SizeExpr, C.getLocationContext());
+    Region = (State->getSVal(NE, LCtx))
+                 .getAsRegion()
+                 ->getAs<SubRegion>()
+                 ->getSuperRegion();
+  } else {
+    Size = svalBuilder.makeIntVal(1, true);
+    Region = (State->getSVal(NE, LCtx)).getAsRegion()->getAs<SubRegion>();
+  }
+  assert(Region);
+
+  // Set the region's extent equal to the Size parameter.
+  const SymbolicRegion *R = dyn_cast<SymbolicRegion>(Region);
+  if (!R)
+    return nullptr;
+
+  QualType ElementType = NE->getAllocatedType();
+  ASTContext &AstContext = C.getASTContext();
+  CharUnits TypeSize = AstContext.getTypeSizeInChars(ElementType);
+
+  if (Optional<DefinedOrUnknownSVal> DefinedSize =
+          Size.getAs<DefinedOrUnknownSVal>()) {
+    DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
+    NonLoc s = Size.castAs<NonLoc>();
+    SVal SizeInBytes = scaleValue(State, s, TypeSize, svalBuilder);
+    DefinedOrUnknownSVal extentMatchesSize = svalBuilder.evalEQ(
+        State, Extent, SizeInBytes.castAs<DefinedOrUnknownSVal>());
+    State = State->assume(extentMatchesSize, true);
+  }
+  return State;
+}
+// Scale a base value by a scaling factor, and return the scaled
+// value as an SVal.
+SVal MallocChecker::scaleValue(ProgramStateRef State, NonLoc BaseVal,
+                               CharUnits Scaling, SValBuilder &Sb) {
+  return Sb.evalBinOpNN(State, BO_Mul, BaseVal,
+                        Sb.makeArrayIndex(Scaling.getQuantity()),
+                        Sb.getArrayIndexType());
+}
+
 void MallocChecker::checkPreStmt(const CXXDeleteExpr *DE,
                                  CheckerContext &C) const {
 
   if (!ChecksEnabled[CK_NewDeleteChecker])
     if (SymbolRef Sym = C.getSVal(DE->getArgument()).getAsSymbol())
       checkUseAfterFree(Sym, C, DE->getArgument());
 
   if (!isStandardNewDelete(DE->getOperatorDelete(), C.getASTContext()))
     return;
 

test/Analysis/out-of-bounds.cpp

+// RUN: %clang_cc1 -std=c++11 -Wno-array-bounds -analyze -analyzer-checker=unix,core,alpha.security.ArrayBoundV2 -verify %s
+
+// Tests doing an out-of-bounds access after the end of an array using:
+// - constant integer index
+// - constant integer size for buffer
+void test1(int x) {
+  int *buf = new int[100];
+  buf[100] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+void test1_ok(int x) {
+  int *buf = new int[100];
+  buf[99] = 1; // no-warning
+}
+
+// Tests doing an out-of-bounds access after the end of an array using:
+// - indirect pointer to buffer
+// - constant integer index
+// - constant integer size for buffer
+void test1_ptr(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  p[101] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+void test1_ptr_ok(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  p[99] = 1; // no-warning
+}
+
+// Tests doing an out-of-bounds access before the start of an array using:
+// - indirect pointer to buffer, manipulated using simple pointer arithmetic
+// - constant integer index
+// - constant integer size for buffer
+void test1_ptr_arith(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  p = p + 100;
+  p[0] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+void test1_ptr_arith_ok(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  p = p + 99;
+  p[0] = 1; // no-warning
+}
+
+void test1_ptr_arith_bad(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  p = p + 99;
+  p[1] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+void test1_ptr_arith_ok2(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  p = p + 99;
+  p[-1] = 1; // no-warning
+}
+
+// Tests doing an out-of-bounds access before the start of an array using:
+// - constant integer index
+// - constant integer size for buffer
+void test2(int x) {
+  int *buf = new int[100];
+  buf[-1] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+// Tests doing an out-of-bounds access before the start of an array using:
+// - indirect pointer to buffer
+// - constant integer index
+// - constant integer size for buffer
+void test2_ptr(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  p[-1] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+// Tests doing an out-of-bounds access before the start of an array using:
+// - indirect pointer to buffer, manipulated using simple pointer arithmetic
+// - constant integer index
+// - constant integer size for buffer
+void test2_ptr_arith(int x) {
+  int *buf = new int[100];
+  int *p = buf;
+  --p;
+  p[0] = 1; // expected-warning {{Out of bound memory access (accessed memory precedes memory block)}}
+}
+
+// Tests doing an out-of-bounds access before the start of a multi-dimensional
+// array using:
+// - constant integer indices
+// - constant integer sizes for the array
+void test2_multi(int x) {
+  auto buf = new int[100][100];
+  buf[0][-1] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+// Tests doing an out-of-bounds access before the start of a multi-dimensional
+// array using:
+// - constant integer indices
+// - constant integer sizes for the array
+void test2_multi_b(int x) {
+  auto buf = new int[100][100];
+  buf[-1][0] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+// Tests doing an out-of-bounds access before the start of a multi-dimensional
+// array using:
+// - constant integer indices
+// - constant integer sizes for the array
+void test2_multi_c(int x) {
+  auto buf = new int[100][100];
+  buf[100][0] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+// Tests doing an out-of-bounds access before the start of a multi-dimensional
+// array using:
+// - constant integer indices
+// - constant integer sizes for the array
+void test2_multi_2(int x) {
+  auto buf = new int[100][100];
+  buf[99][100] = 1; // expected-warning{{Out of bound memory access}}
+}
+
+// Tests doing an out-of-bounds access before the start of a multi-dimensional
+// array using:
+// - constant integer indices
+// - constant integer sizes for the array
+void test2_multi_ok(int x) {
+  auto buf = new int[100][100];
+  buf[0][0] = 1; // no-warning
+}
+
+// Tests over-indexing using different types
+// array using:
+// - constant integer indices
+// - constant integer sizes for the array
+void test_diff_types(int x) {
+  int *buf = new int[10]; //40 Bytes allocated
+  char *cptr = (char *)buf;
+  cptr[sizeof(int) * 9] = 1;  // no-warning
+  cptr[sizeof(int) * 10] = 1; // expected-warning{{Out of bound memory access}}
+}