[analyzer] Use sufficiently large types for index/size calculation.

[ebevhan]

Summary

RegionStoreManager::getSizeInElements used 'int' for size
calculations, and ProgramState::assumeInBound fell back
to 'int' as well for its index calculations. This causes
truncation for sufficiently large sizes/indexes.

Use ArrayIndexTy (long long) in these instances to prevent overflow
problems.

[a.sidorin]

This is a nice extension of D16063.

lib/StaticAnalyzer/Core/RegionStore.cpp

1344–1345

I think we should initialize SValBuilder::ArrayIndexTy with getSignedSizeType() instead of LongLongTy and use svalBuilder.getArrayIndexType() here instead.

test/Analysis/array-index.c

1 ↗

(On Diff #147087)

Can we place these tests into Analysis/index-type.c?

[a.sidorin]

test/Analysis/array-index.c

11 ↗

(On Diff #147087)

Could you please give meaningful names to the tests?

[ebevhan]

lib/StaticAnalyzer/Core/RegionStore.cpp

1344–1345

I made the change, but it caused a spurious out of bounds warning in index-type.c for the 32-bit case. Making the type signed means that anything above MAX/2 will break, and the test uses arrays of that size.

[a.sidorin]

lib/StaticAnalyzer/Core/RegionStore.cpp

1344–1345

Hm, yes. ssize_t is 32-bit on 32-bit targets but our indices can exceed it. Even if so, svalBuilder.getArrayIndexType() should be fine.

[ebevhan]

lib/StaticAnalyzer/Core/RegionStore.cpp

1344–1345

Well, the problem is that it's only enough for objects whose size is less than half of the range. If they're larger, the out of bounds calculation overflows and it thinks that we're trying to index outside the object (at a lower address).

The 64-bit test avoids this since its array is smaller. It's MAX/16 instead.

[ebevhan]

Made ArrayIndexTy into ssize_t, consolidated the tests and fixed the test that was failing.

[a.sidorin]

Hi Bevin,

Could you please address these comments?

include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h

89

As you correctly pointed, ssize_t is 32-bit on 32-bit systems. Therefore, it is too short. So, we can leave this line as-is.

test/Analysis/index-type.c

13

We don't need to fix the test - it is correct. We have to fix the type instead.

25

The comments should be normal sentences: "Not out of bounds."

[ebevhan]

include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h

89

But if it's hardcoded to LongLongTy, you have the same problem on 64-bit systems.

[a.sidorin]

include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h

89

Some reasons why LongLongTy is used here are listed in D16063. In brief, you just cannot create an array of size greater than SIZE_MAX/2 on 64-bit platforms.

[ebevhan]

include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h

89

I don't think that's limited to 64-bit platforms, it applies to 32-bit ones as well. I know that LLVM has issues with indexing arrays that are larger than half of the address space in general due to limitations of GEP.

[a.sidorin]

There are some results for clang and gcc max value for x86 and x64.
Source code:

const unsigned long long SIZE_MAX = (unsigned long long)(unsigned long)(-1);
const unsigned long long size = SIZE_MAX/2;
char arr[size+1];

Compiler output:

% g++ -c cast-comp.cpp -m32
cast-comp.cpp:6:16: error: size of array ‘arr’ is negative
 char arr[size+1];
                ^
% clang++-6.0 -c cast-comp.cpp -m32
% g++ -c cast-comp.cpp -m32        
cast-comp.cpp:6:16: error: size of array ‘arr’ is negative
 char arr[size+1];
                ^
% g++ -c cast-comp.cpp
cast-comp.cpp:6:16: error: size of array ‘arr’ is negative
 char arr[size+1];
                ^
% clang++-6.0 -c cast-comp.cpp
cast-comp.cpp:6:10: error: array is too large (9223372036854775808 elements)
char arr[size+1];
         ^~~~~~

So, clang accepts indices > SIZE_MAX/2 for x86.
For arr[size], only clang-x64 fails with error.
I think this means that we need to use LongLongTy as index type, not SizeType. @NoQ, what do you think?

[ebevhan]

Changed ArrayIndexTy back to LongLongTy and reverted the test change.

[ebevhan]

Ping.

[a.sidorin]

Hi Bevin,

The patch looks good to me. But let's wait for maintainers to approve it. @NoQ , could you take a look?

[NoQ]

Yep, this definitely looks safe and sound in the current shape.

I'm also very sorry for the lack of attention.

include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h

public:
   // handles loads from different bound value types.
   virtual SVal dispatchCast(SVal val, QualType castTy) = 0;
 
 public:
   SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
               ProgramStateManager &stateMgr)
       : Context(context), BasicVals(context, alloc),
         SymMgr(context, BasicVals, alloc), MemMgr(context, alloc),
-        StateMgr(stateMgr), ArrayIndexTy(context.LongLongTy),
+        StateMgr(stateMgr), ArrayIndexTy(context.getSignedSizeType()),
         ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
 
   virtual ~SValBuilder() = default;
 
   bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) {
     return haveSameType(Sym1->getType(), Sym2->getType());
   }
 

lib/StaticAnalyzer/Core/ProgramState.cpp

ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx,
   // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
   // FIXME: This should probably be part of SValBuilder.
   ProgramStateManager &SM = getStateManager();
   SValBuilder &svalBuilder = SM.getSValBuilder();
   ASTContext &Ctx = svalBuilder.getContext();
 
   // Get the offset: the minimum value of the array index type.
   BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
-  // FIXME: This should be using ValueManager::ArrayindexTy...somehow.
   if (indexTy.isNull())
-    indexTy = Ctx.IntTy;
+    indexTy = svalBuilder.getArrayIndexType();
   nonloc::ConcreteInt Min(BVF.getMinValue(indexTy));
 
   // Adjust the index.
   SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add,
                                         Idx.castAs<NonLoc>(), Min, indexTy);
   if (newIdx.isUnknownOrUndef())
     return this;
 

lib/StaticAnalyzer/Core/RegionStore.cpp

if (Ctx.getAsVariableArrayType(EleTy)) {
     return UnknownVal();
   }
 
   CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
 
   // If a variable is reinterpreted as a type that doesn't fit into a larger
   // type evenly, round it down.
   // This is a signed value, since it's used in arithmetic with signed indices.
-  return svalBuilder.makeIntVal(RegionSize / EleSize, false);
+  return svalBuilder.makeIntVal(RegionSize / EleSize,
+                                svalBuilder.getArrayIndexType());
 }
 
 //===----------------------------------------------------------------------===//
 // Location and region casting.
 //===----------------------------------------------------------------------===//
 
 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
 ///  type.  'Array' represents the lvalue of the array being decayed

test/Analysis/index-type.c

 // RUN: %clang_analyze_cc1 -triple x86_64-apple-darwin10 -analyzer-checker=core,alpha.security.ArrayBoundV2 -verify %s
 // RUN: %clang_analyze_cc1 -triple i386-apple-darwin10 -analyzer-checker=core,alpha.security.ArrayBoundV2 -DM32 -verify %s
 // expected-no-diagnostics
 
 #define UINT_MAX (~0u)
 
 #ifdef M32
 
-#define X86_ARRAY_SIZE (UINT_MAX/2 + 4)
+#define X86_ARRAY_SIZE (UINT_MAX/4 + 4)
 
 void testIndexTooBig() {
   char arr[X86_ARRAY_SIZE];
-  char *ptr = arr + UINT_MAX/2;
+  char *ptr = arr + UINT_MAX/4;
   ptr += 2;  // index shouldn't overflow
   *ptr = 42; // no-warning
 }
 
+#define SIZE 4294967296
+
+static unsigned size;
+static void * addr;
+static unsigned buf[SIZE];
+
+void testOutOfBounds() {
+  // not out of bounds
+  buf[SIZE-1] = 1; // no-warning
+}
+
+void testOutOfBoundsCopy1() {
+  memcpy(buf, addr, size); // no-warning
+}
+
+void testOutOfBoundsCopy2() {
+  memcpy(addr, buf, size); // no-warning
+}
+
 #else // 64-bit tests
 
 #define ARRAY_SIZE 0x100000000
 
 void testIndexOverflow64() {
   char arr[ARRAY_SIZE];
   char *ptr = arr + UINT_MAX/2;
   ptr += 2;  // don't overflow 64-bit index