Page MenuHomePhabricator

[analyzer] Access stored value of a constant array through a pointer to another type
AbandonedPublic

Authored by ASDenysPetrov on Oct 1 2021, 5:34 AM.

Details

Summary

Use strict-aliasing rule for the type punning cases in which RegionStore is able to get a stored value of a constant array through a pointer of inappropriate type. Adjust RegionStoreManager::getBindingForElement to the C++20 Standard.
Example:

const int arr[42] = {1,2,3};
int x1 = ((unsigned*)arr)[0];  // OK
int x2 = ((short*)arr)[0]; // UB
int x3 = ((char*)arr)[0];  // OK
int x4 = ((char*)arr)[1];  // UB

Diff Detail

Unit TestsFailed

TimeTest
1,640 msx64 debian > AddressSanitizer-x86_64-linux-dynamic.TestCases::exitcode.cpp
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -shared-libasan -g -Wno-deprecated-declarations /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/exitcode.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxDynamicConfig/TestCases/Output/exitcode.cpp.tmp
2,180 msx64 debian > AddressSanitizer-x86_64-linux.TestCases::exitcode.cpp
Script: -- : 'RUN: at line 1'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang --driver-mode=g++ -fsanitize=address -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer -fno-optimize-sibling-calls -gline-tables-only -m64 -g -Wno-deprecated-declarations /var/lib/buildkite-agent/builds/llvm-project/compiler-rt/test/asan/TestCases/exitcode.cpp -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/compiler-rt/test/asan/X86_64LinuxConfig/TestCases/Output/exitcode.cpp.tmp

Event Timeline

ASDenysPetrov created this revision.Oct 1 2021, 5:34 AM
ASDenysPetrov requested review of this revision.Oct 1 2021, 5:34 AM
steakhal added a subscriber: shafik.Oct 1 2021, 7:20 AM

I'm pretty sure that int x4 = ((char*)arr)[1]; is supposed to be valid in your summary.
I think it's allowed by the standard to access any valid object via a char* - according to the strict aliasing rule.
@shafik WDYT?

ASDenysPetrov added a comment.EditedOct 1 2021, 8:21 AM

I'm pretty sure that int x4 = ((char*)arr)[1]; is supposed to be valid in your summary.
I think it's allowed by the standard to access any valid object via a char* - according to the strict aliasing rule.
@shafik WDYT?

As I found we can legaly treat char* as the object of type char but not as an array of objects. This is mentioned in http://eel.is/c++draft/basic.compound#3.4 For purposes of pointer arithmetic ... an object of type T that is not an array element is considered to belong to an array with one element of type T. That means that we can get only the first element of char*, otherwise it would be an UB. There is also a paper to overcome this constraint http://open-std.org/JTC1/SC22/WG21/docs/papers/2019/p1839r0.pdf

@aaron.ballman I would like you join the discussion, as we have similar one in D104285.

I'm pretty sure that int x4 = ((char*)arr)[1]; is supposed to be valid in your summary.
I think it's allowed by the standard to access any valid object via a char* - according to the strict aliasing rule.
@shafik WDYT?

As I found we can legaly treat char* as the object of type char but not as an array of objects. This is mentioned in http://eel.is/c++draft/basic.compound#3.4 For purposes of pointer arithmetic ... an object of type T that is not an array element is considered to belong to an array with one element of type T. That means that we can get only the first element of char*, otherwise it would be an UB. There is also a paper to overcome this constraint http://open-std.org/JTC1/SC22/WG21/docs/papers/2019/p1839r0.pdf

@aaron.ballman I would like you join the discussion, as we have similar one in D104285.

IIUC the object is const int arr[42] and the (char *)arr is an expression of pointer type and adding 1 to this is valid. The case you refer to in D104285 ended up being a pointer to an array of 2 ints and therefore accessing the third element was out of bounds.

Fixed a comment.

IIUC the object is const int arr[42] and the (char *)arr is an expression of pointer type and adding 1 to this is valid. The case you refer to in D104285 ended up being a pointer to an array of 2 ints and therefore accessing the third element was out of bounds.

You are right. According to http://eel.is/c++draft/expr.add#4, expression P + I is valid while 0 ≤ I ≤ n, UB otherwise. This is valid untill we try to dereference it. After that it becomes an UB. The UB's you and me are talking about have different origin.

My concern is whether we do it correctly considering that dereferencing of type T through other types are UB in certain cases. Namely, http://eel.is/c++draft/basic.lval#11 and http://eel.is/c++draft/basic.compound#3.4 paragraphs tell us:

int arr[42];
// same type
auto x = ((int*)arr)[0]; // OK
auto x = ((int*)arr)[1]; // OK
auto x = ((int*)arr)[41]; // OK 

// opposite signedness
auto x = ((unsigned int*)arr)[0]; // OK
auto x = ((unsigned int*)arr)[1]; // UB
auto x = ((unsigned int*)arr)[41]; // UB

// for char*, unsigned char* and std::byte*
auto x = ((char*)arr)[0]; // OK
auto x = ((char*)arr)[1]; // UB
auto x = ((char*)arr)[41]; // UB

using T= AllTheRestTypes;
auto x = ((T*)arr)[0]; // UB
auto x = ((T*)arr)[1]; // UB
auto x = ((T*)arr)[41]; // UB
steakhal added inline comments.Oct 27 2021, 8:56 AM
clang/lib/StaticAnalyzer/Core/RegionStore.cpp
1639–1650

This is basically the strict-aliasing rule, we could probably mention this.
Although, I don't mind the current name.
You probably know about it, but Shafik made a fancy GitHub Gist about it.
The only thing I missed was checking type similarity according to basic.lval, but I'm not exactly sure if we should check that here.

1666–1680

I would rather Ctx.getCorrespondingUnsignedType() on both of the types and if they compare equal, that would mean that they differed only in signedness.
This is probably more costly, and that function will assert that it's a scalar type or something, so it would make sense to check OrigT == ThroughT separately earlier than this.

1681–1686

You should probably early return on this.

2006

If you already compute the canonical type why do you recompute in the canAccessStoredValue()?
You could simply assert that instead.

2007–2008

Even though I agree with you, I think it would be useful to hide this behavior behind an analyzer option.
There is quite a lot code out in the wild that violate the strict-aliasing rule and they probably pass the -fno-strict-aliasing compiler flag to accommodate this in codegen. AFAIK Linux is one of these projects for example.
So, I think there is a need to opt-out of this and/or bind the behavior to the presence of the mentioned compiler flag.

By not doing this, the user would get garbage value reports all over the place.
@NoQ @martong WDYT?

@steakhal I'll address all of your remarks. Thanks a lot!

clang/lib/StaticAnalyzer/Core/RegionStore.cpp
1639–1650

You probably know about it, but Shafik made a fancy GitHub Gist about it.

Yes, this is the one of those things which inspired me to take care of aliasing as a part of RegionStoreManager improvements.

2007–2008

There is quite a lot code out in the wild that violate the strict-aliasing rule

Agree.

By not doing this, the user would get garbage value reports all over the place.

Definitely.
Using the flag is a good option. But the question whether to use existing -fno-strict-aliasing or introduce a new one?

Adding @vabridgers as a subscriber, he might be interested in this.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp
1684

typo: untill -> until

2006

He removes the qualifiers there, but getting the canonical type is probably redundant here.

2007–2008

I think we could simply reuse the existing -fno-strict-aliasing.

Updated according to comments.
TODO: make the feature -fno-strict-aliasing dependent.

ASDenysPetrov marked 5 inline comments as done.Mon, Nov 1, 9:10 AM

Ping.
Does anyone know how to check the status of`-fno-strict-aliasing` flag from CSA side?

For testing this I would recommend using a separate test file.
That being said, you should avoid globals even in tests when you can. The distance between its declaration and use just makes it harder to comprehend and reason about.
You could have a parameter, and take its address to accomplish your reinterpret casts and type puns.

BTW your patch crashes on the test suite:
initialization.cpp:242:

void glob_array_typedef1() {
  clang_analyzer_eval(glob_arr8[0][0] == 1); // <-- crashes here
  // ...
}
clang: ../../clang/lib/AST/ASTContext.cpp:10230: clang::QualType clang::ASTContext::getCorrespondingUnsignedType(clang::QualType) const: Assertion `(T->hasSignedIntegerRepresentation() || T->isSignedFixedPointType()) && "Unexpected type"' failed.
Called by clang::ASTContext::getCorrespondingUnsignedType() from RegionStoreManager::canAccessStoredValue()
clang/lib/StaticAnalyzer/Core/RegionStore.cpp
1661

Maybe unwrapConstantArrayTypes()?

1790

Even though you are technically correct, how can you know that the pointer you try to dereference actually points to the beginning of the object?
Consider something like this:

void callback(void *payload) {
  // lets skip the first char object...
  int *num = (int*)((char*)payload + 1);
  clang_analyzer_dump(num); // Element{Element{SymRegion{payload}, 1, char}, 0, int}
}
1794–1795
clang/test/Analysis/initialization.cpp
295–299

I think it's not correct.

glob_arr2 refers to an object of dynamic type int[2].
And the pointer decayed from it is int *, which has similar type to unsigned * what you are using to access the memory.
Since they are similar, this operation should work for all the valid indices, thus ptr[0], ptr[1], ptr[2], ptr[3] should all be valid.

311–314

Please also try char8_t.

For testing this I would recommend using a separate test file.
That being said, you should avoid globals even in tests when you can. The distance between its declaration and use just makes it harder to comprehend and reason about.

I'll add a new tests file.

You could have a parameter, and take its address to accomplish your reinterpret casts and type puns.

Do you mean:

void foo(signed char * ptr) {
  ptr = (signed char *)glob_arr2;
}

instead of

void foo() {
  auto *ptr = (signed char *)glob_arr2;
}

?
If so, IMO it doesn't matter.

BTW your patch crashes on the test suite:
initialization.cpp:242:

I caught it. Thanks! I wonder how it slipped through unnoticed.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp
1661

I think about getConstantArrayRootType. IMO such name distinctly tells its intention and purpose.

1790

how can you know that the pointer you try to dereference actually points to the beginning of the object?

We look at the offset of the region. In your example it is 1. And it is UB. Unfortinatelly the Standard forbids to do such accesses due to the different strict access rules. I recommend this talk https://youtu.be/_qzMpk-22cc . I took inspiration from there.

clang/test/Analysis/initialization.cpp
295–299

glob_arr2 refers to an object of dynamic type int[2].

glob_arr2 has an extent of 4.

And the pointer decayed from it is int *, which has similar type to unsigned * what you are using to access the memory.

Yes, they are the same and it perfectly suits to http://eel.is/c++draft/basic.lval#11 . But still you can't access other element then the first one according to http://eel.is/c++draft/basic.compound#3 : For purposes of pointer arithmetic ([expr.add]) and comparison ([expr.rel], [expr.eq]), [...] an object of type T that is not an array element is considered to belong to an array with one element of type T.
unsigned int and int are different types according to http://eel.is/c++draft/basic.fundamental#2 . The object of type unsigned int is NOT an array, beacuse there is no array of type unsigned int. Hence you can only only access the first and a single element of type unsigned int.

311–314

Correct. We should check it. It should be a different type as well (http://eel.is/c++draft/basic.fundamental#9).

You could have a parameter, and take its address to accomplish your reinterpret casts and type puns.

Do you mean: ...
If so, IMO it doesn't matter.

I see. Sorry about the confusion I caused.

Does anyone know how to check the status of`-fno-strict-aliasing` flag from CSA side?

I think I know.
Within the AnalysisConsumer::AnalysisConsumer() you have access to the CompilerInstance object. Using that you can acquire the CI.getCodeGenOpts().RelaxedAliasing bool member, which represents exactly what we need, according to the clang/include/clang/Basic/CodeGenOptions.def:211:

CODEGENOPT(RelaxedAliasing   , 1, 0) ///< Set when -fno-strict-aliasing is enabled.

I think you should simply save a const reference to the CodeGenOptions object from the AnalysisConsumer.

clang/test/Analysis/initialization.cpp
295–299

Yes, glob_arr has 4 elements, sorry for this typo.


I disagree with the second part though. It seems like gcc disagrees as well: https://godbolt.org/z/5o7ozvPar

auto foo(unsigned (&p)[4], int (&q)[4]) {
    p[0] = 2;
    q[0] = 1;
    return p[0]; // memory read! thus, p and q can alias according to g++.
}

gcc still thinks that p and q can refer to the same memory region even if the -fstrict-aliasing flag is present.
In other circumstances, it would produce a mov eax, 2 instead of a memory load if p and q cannot alias.

@steakhal

I think I know.

Great! Thank you!

clang/test/Analysis/initialization.cpp
295–299

I disagree with the second part though. It seems like gcc disagrees as well: https://godbolt.org/z/5o7ozvPar

I see how all the compilers handle this. I've switched several vendors on Godbolt. They all have the similar behavior. You are right from compiler perspective, but it's not quite the same in terms of C++ abstract machine.
Your example is correct, it works OK and is consistent with the Standard:

p[0] = 2;
q[0] = 1;

This one also works as expected but goes against the Standard:

p[1] = 2;
q[1] = 1;

I want you watch this particular part about access via aliased pointers: https://youtu.be/_qzMpk-22cc?t=2623 For me it seems correct, at least I can't argue against of it now.

steakhal added inline comments.Thu, Nov 11, 9:20 AM
clang/test/Analysis/initialization.cpp
295–299

But in this example we have an array, thus pointer arithmetic should be fine according to the video.
Could you find the mentioned email discussion? I would be really curious.
BTW from the analyzer user's perspective, it would be 'better' to find strict aliasing violations which actually matter - now, and risking miscompilations.

ASDenysPetrov added inline comments.Fri, Nov 12, 7:26 AM
clang/test/Analysis/initialization.cpp
295–299

I'm not enough confident about that to debate now. As you can see we started arguing as well. That means that the Standard really leaves the subject for misinterpretation.
OK, let's bring it to the form in which compilers operate. I mean, let's legitimate indirections with a different offsets through aliased types: auto x = ((unsigened)arr)[42]; // OK.
I think it will be enough for this patch for now.

steakhal added inline comments.Fri, Nov 12, 7:34 AM
clang/test/Analysis/initialization.cpp
295–299

So, we agree that glob_cast_opposite_sign1() should have no warnings. At least for now. I would be okay with this direction.

NoQ added a comment.Tue, Nov 16, 6:04 PM

Taking advantage of strict aliasing is good as long as it produces strictly smaller analysis space (less paths, more constrained states). I.e., we can use it for eliminating possibilities, but not for discovering possibilities.

If we ever prove that strict aliasing is violated on a given execution path (while being enabled), the ideal thing to do is to terminate the analysis immediately by generating a sink. We can then optionally develop a checker that emits a warning in such cases.

For the cases where you eliminate possibilities through recognizing strict aliasing, I wonder if a note can be added to the bug report to notify the user that the strict aliasing rule was invoked to add a certain assumption.

@NoQ

If we ever prove that strict aliasing is violated on a given execution path (while being enabled), the ideal thing to do is to terminate the analysis immediately by generating a sink. We can then optionally develop a checker that emits a warning in such cases.

thinking about warnings I assume that the Store will produce UndefinedVals and Undef-related checkers will catch them. But yes, you're right. They wouldn't know anything about the origin of such UndefinedVals.

For the cases where you eliminate possibilities through recognizing strict aliasing, I wonder if a note can be added to the bug report to notify the user that the strict aliasing rule was invoked to add a certain assumption.

I didn't elaborate an idea with a checker yet but, I think, it can be the next step. What about a mechanism which would store the reason of UndefinedVal for existing checkers? It could make any checker more detailed and flexible.

@steakhal Please, read the discussion started from here D104285#2943449. It's directly relates to this patch and what we've been arguing about.

I'm still hesitating about this patch.
On one hand we have the fact that almost all compilers ignore some Standard's paragraphs about UB in terms of casts.
E.g. they consider next snippets as OK, but they are NOT according to the Standard:

  • int arr[1][2][3]; int *ptr = (int*)arr; ptr[4] = 42; // int(*)[2][3] can't be aliased by int*
  • int i; signed char *ptr = (signed char*)&i; ptr[2] = 42; // int* can't be aliased by signed char*
  • int arr[3][3]; int (*ptr)[8] = (int(*)[6])arr; ptr[1][1] = 42; // ptr[1] can't go further then aliased by int(*)[6]

I've checked all those examples on Godbolt
On the other hand introducing this patch will show unexpected warnings to users which they can't reproduce in a real life.

I can't choose the way to act.

ASDenysPetrov abandoned this revision.EditedTue, Nov 23, 10:17 AM

Temporary suspended this revision in favor of making a new checker StrictAliasingChecker, which would define an access to values through unpermited types as Undefined Behavior according to certain statements of the current Standard.