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

Authored by ebevhan on Wed, May 16, 7:32 AM.

Details

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.

Initialize the ArrayIndexTy to ssize_t and use it in
these instances to prevent overflow problems.

One test was allocating an array greater than half
of the address space, which causes problems with
signed sizes. The array size was lowered.

Diff Detail

ebevhan created this revision.Wed, May 16, 7:32 AM

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 added inline comments.Wed, May 16, 8:09 AM
test/Analysis/array-index.c
11 ↗(On Diff #147087)

Could you please give meaningful names to the tests?

ebevhan added inline comments.Wed, May 16, 8:41 AM
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 added inline comments.Wed, May 16, 8:57 AM
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 added inline comments.Wed, May 16, 10:34 AM
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 updated this revision to Diff 147738.Mon, May 21, 12:55 AM
ebevhan edited the summary of this revision. (Show Details)

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

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 added inline comments.Thu, May 24, 12:11 AM
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 added inline comments.Fri, May 25, 7:37 AM
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 added inline comments.Fri, May 25, 7:41 AM
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.