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

Authored by ebevhan on May 16 2018, 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.

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

Diff Detail

Repository
rC Clang
ebevhan created this revision.May 16 2018, 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.May 16 2018, 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.May 16 2018, 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.May 16 2018, 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.May 16 2018, 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.May 21 2018, 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 ↗(On Diff #147738)

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.May 24 2018, 12:11 AM
include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
89 ↗(On Diff #147738)

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

a.sidorin added inline comments.May 25 2018, 7:37 AM
include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
89 ↗(On Diff #147738)

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.May 25 2018, 7:41 AM
include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
89 ↗(On Diff #147738)

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 added a subscriber: NoQ.May 29 2018, 6:51 AM

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?

george.karpenkov resigned from this revision.May 30 2018, 4:20 PM
george.karpenkov added a subscriber: george.karpenkov.
ebevhan updated this revision to Diff 149415.Jun 1 2018, 2:37 AM
ebevhan edited the summary of this revision. (Show Details)

Changed ArrayIndexTy back to LongLongTy and reverted the test change.

a.sidorin accepted this revision.Jun 26 2018, 4:45 AM

Hi Bevin,

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

This revision is now accepted and ready to land.Jun 26 2018, 4:45 AM
NoQ accepted this revision.Jun 27 2018, 5:06 PM
NoQ edited reviewers, added: NoQ; removed: dergachev.a.
NoQ removed a subscriber: NoQ.

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

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

This revision was automatically updated to reflect the committed changes.