This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Implement a new checker for Strict Aliasing Rule.
Needs ReviewPublic

Authored by ASDenysPetrov on Nov 29 2021, 9:39 AM.

Details

Summary

StrictAliasingChecker implements checks on violation of the next paragraph (C++20 7.2.1 p11 [basic.lval]) of the C++20 Standard which is known as Strict Aliasing Rule. It operates on variable loads and stores. The checker compares the original type of the value with the type of the pointer with which the value is aliased.
Example:

int x = 42;
auto c = *((char*)&x); // The original type is `int`. The aliased type is `char`. OK. 
auto f = *((float*)&x); // The original type is `int`. The aliased type is `float`. UB.

At the moment the checker supports only C++20.

NOTE: Below are differences in strict aliasing rules between C, C++ Standard versions. Do we need to support defective items?

Evolution of C++ Standard

C++98C++11C++14C++17C++20 (Fixed Issue 2051)
If a program attempts to access the stored value of an object through a glvalue of other than one of the following types the behavior is undefined:---If a program attempts to access (3.1) the stored value of an object through a glvalue of other than whose type is not similar to one of the following types the behavior is undefined:
- the dynamic type of the object----
- a cv-qualified version of the dynamic type of the object---Removed as duplicated of similar type.
blank- a type similar to the dynamic type of the object--Moved to the paragraph's main text (first row).
- a type that is the signed or unsigned type corresponding to the dynamic type of the object----
- a type that is the signed or unsigned type corresponding to a cv-qualified version of the dynamic type of the object---Removed as duplicated of similar type.
- an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union)---Removed as a core defect (Issue 2051). This cannot arise in C++.
- a type that is a (possibly cv-qualified) base class type of the dynamic type of the object---Removed as a core defect (Issue 2051). This cannot arise in C++.
- a char, unsigned char--- a char, unsigned char, or std::byte type-

Paragraph from C Standard is true for all versions

C
An object shall have its stored value accessed only by an lvalue expression that has one of the following types:
- a type compatible with the effective type of the object
- a qualified version of a type compatible with the effective type of the object
- a type that is the signed or unsigned type corresponding to the effective type of the object
- a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object
- an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union)
- a character type

Differences are in the type concepts between C and C++

has concept?CC++
effective typeyesno
compatible typeyesno
dynamic typenoyes
similar typenoyes

Thus, the interpretation of the paragraph is different, depending on type concept meaning. E.g. the first statement "... similar to ... the dynamic type of the object" vs "a type compatible with the effective type of the object".

Diff Detail

Unit TestsFailed

Event Timeline

ASDenysPetrov created this revision.Nov 29 2021, 9:39 AM
ASDenysPetrov requested review of this revision.Nov 29 2021, 9:39 AM
ASDenysPetrov added a comment.EditedNov 29 2021, 9:45 AM

@rsmith, @aaron.ballman I kindly invite you to join the review process especially in a part of the Standard interpretation. Specifically @rsmith made proposals in this part of the Standard.

ASDenysPetrov edited the summary of this revision. (Show Details)Nov 29 2021, 9:47 AM
ASDenysPetrov edited the summary of this revision. (Show Details)
ASDenysPetrov edited the summary of this revision. (Show Details)Nov 29 2021, 9:55 AM
NoQ added a comment.Nov 29 2021, 12:57 PM

Awesome, I love it!

What would it take to enable this by default? Note that we can enable the checker without emitting any warnings; sinking exotic execution paths (on which strict aliasing is known to be violated) is valuable on its own.

Other than that, we'll probably need a bug visitor to add a note for where the original type comes from (it should probably be the place where the location becomes *live*), and then some real-world testing.

clang/lib/StaticAnalyzer/Checkers/StrictAliasingChecker.cpp
49–50

assert() it? Or maybe canonicalize defensively so that not to duplicate code in the caller, given that there's really only one correct way to do that?

81

The modern solution is

BugType BT{this, "...", "..."};
114

I suspect it might also be UnknownVal (?) It usually makes sense to protect against such scenarios with an early return.

142–146

You're basically running into https://bugs.llvm.org/show_bug.cgi?id=43364 here. The element region is not necessarily a consequence of a pointer cast; it may also be a legitimate array element access, and there's no way to figure out what it really was. So I suspect that you may fail the following test case:

void foo() {
  int x[10];
  int *p = &x[1];
  *p = 1; // int incompatible with int[10]
}

Separately from that, ultimatetly you'll most likely have to handle regions with symbolic base separately. These regions are special because they are built when the information about the original type is not really unavailable. For now you're dodging this problem by only supporting VarRegions with element sub-regions. But in the general case you may encounter code like this

void foo(void *p) {
  int *x = p;
  float *y = x;
  *y = 1.0;
}

which may be valid if the original pointer p points to a float. But this can be delayed until later.

158

I suggest a fatal error node. Undefined behavior already occured, there's nothing interesting in the follow-up.

179–180

We should probably keep the checker disabled in these language modes until we're sure it works correctly (in a conservative sense, i.e. doesn't emit false positives).

Can we check whether -fstrict-aliasing is enabled here? That's probably appropriate.

xazax.hun added inline comments.Nov 29 2021, 1:03 PM
clang/lib/StaticAnalyzer/Checkers/StrictAliasingChecker.cpp
59

I'd love to see some detailed descriptions of the strict aliasing rule, what parts are we checking for and what parts we don't. E.g. it would be nice to document the differences between C and C++ aliasing rules. I do remember something about prefixes, i.e.: it would be well defined to access something with the dynamic type struct { int x, y; }; and read struct{ int x; }; from it. Does that not apply to C++?

ASDenysPetrov added inline comments.Nov 30 2021, 8:31 AM
clang/lib/StaticAnalyzer/Checkers/StrictAliasingChecker.cpp
49–50

Or maybe canonicalize defensively so that not to duplicate code in the caller,

We need canonical types in the bug report as well, so we have to get them on the caller side.

59

I'd love to see some detailed descriptions of the strict aliasing rule,

I've added a description in the header.

it would be nice to document the differences between C and C++ aliasing rules.

I need some time to gather those differences and will add them to the description as well.

it would be well defined to access something with the dynamic type struct { int x, y; }; and read struct{ int x; }; from it. Does that not apply to C++?

AFAIK it's UB if you do any access to the object which lifetime is not started in C++.

81

Got it.

114

I'll try to add some tests to model this.

142–146

Oh, unfortunately I've stumbled upon these representation issues:

int arr[2][8]
auto p1 = (int(*)[8])arr[0]; // &Element{arr,0 S64b,int[8]}
auto p2 = (int(*)[8])arr;    // &Element{arr,0 S64b,int[8]}
auto p3 = (int(*)[7])arr[0]; // &Element{arr,0 S64b,int[7]}
auto x = *p1; // OK
auto y = *p2; // UB
auto z = *p3; // UB

I think we need some sort of a new region CastRegion that we can store the provenance/origin and cast type separately (in a canonical form), like I did for integers in D103096. I can investigate it soon. And ElementRegion would be in charge of arrays only.
Or
We could modificate ElementRegion to be always in a canonical form which we could easily differentiate.

158

I suggest a fatal error node.

That's a big discussion what would be correct :-) since 98.99% of modern compilers treat e.g. *((short*)x) as a truncation and the following flow works as most users expect (who doesn't aware about UB). So here we could just warn about UB and explore the rest of the code for similar UB's without sinking. That's why I decided using non-fatal node.

179–180

Can we check whether -fstrict-aliasing is enabled here? That's probably appropriate.

Basically, I've already tried to do some preparations for using -fstrict-aliasing in D114006. But now it needs a bit modification. I'll update it.

We should probably keep the checker disabled in these language modes until we're sure it works correctly (in a conservative sense, i.e. doesn't emit false positives).

I did it for the testing purposes. Several extisting tests help to find uncovered cases (As you can see, those, which have failed in pre-merge checks).
Agree. I'll change the condition to LO.CPlusPlus20 || LO.CPlusPlus2b.

ASDenysPetrov edited the summary of this revision. (Show Details)Dec 2 2021, 8:34 AM

@xazax.hun Updated the summary for better undersanding differencies between the Standards.

ASDenysPetrov edited the summary of this revision. (Show Details)Dec 2 2021, 9:05 AM

Improved dynamic type recognition. Provided -fstrict-aliasing compiler flag dependency.
Still has issues with some cases (see it at the bottom of the test file). WIP.

ASDenysPetrov added inline comments.Dec 9 2021, 5:00 AM
clang/lib/StaticAnalyzer/Checkers/StrictAliasingChecker.cpp
114

'ExprEngine::evalLocation' has an early check for unknown, so Location is never be unknown.

Changed handler check:: functions. Reworked. Covered more cases.

Several cases left (marked as FIXME in the test file). For the glance some of them we can't handle because of (possibly) wrong symbolic modeling.

WIP.

I haven't checked the code, but only the tests and expectations for scalar values.
I'll dive deeper if we settled on those.

A couple of remarks:

  1. I would rather use top-level function parameters of the given type instead of declaring an instance of that type and taking the address of that object. I think it would reflect more a real-world scenario when we don't see the allocation of the object, thus we don't know the dynamic/effective type of that object.
  2. Using an alias or the underlying type does not matter in this context; You should not duplicate the tests for this reason. A single test demonstrating that the checker is able to look through type aliases (by using the canonical type) is enough.
  3. Marking signed an already signed type won't introduce new coverage. unlike for char you can be sure that short, int, long, long long are signed by default.
  4. Constness does not matter in this context, since type similarity effectively removes any CVR anyway. I would rather remove those test cases, and leave a single one demonstrating that we thought about them and it works the same way as without const.
  5. Please, also test when you have two pointers with a different number of indirections: long * and long **; gcc expects *p and *q not aliasing.
  6. Consider adding all the test cases from Detecting Strict Aliasing Violations in the Wild paper by Pascal Cuoq et al.

They cover a lot of really interesting cases. BTW in the paper, they already set up the godbolt links demonstrating their findings: https://godbolt.org/g/ggZzQo

I think if we are done with these, we can move on to the more complicated cases involving standard layout types with/without inheritance, unions with common prefixes, and other interesting cases like function pointers, pointers to members, pointers to arrays.


The test expectations for (int, Class), (int, ClassInt), (int, UnionUchar), (int, UnionInt), (int, std::byte), (int, std::OtherByte), (int, EnumInt), (int, char), (int, unsigned char), (int, signed char), (int, short), (int, unsigned short), (int, int), (int, volatile unsigned int), (int, long), (int, unsigned long), (int, long long), (int, unsigned long long), (int, float), (int, double), (int, long double), (int, unsigned), look right.

I'll continue the review when I can spare some time for this.

I would like to see this as an alpha.core checker displayed as two checkers: StrictAliasingModeling and StrictAliasingChecker. You could implement this as a single checker, similarly to how the CStringChecker does for example. Do the reporting only if the StrictAliasingChecker is enabled, but emit the sink node unconditionally, restricting the exploration space.
To get this checker into the core package we will need a couple of checker options, relaxing the strict-aliasing rules for unions and for example the signed char as well; since it seems like both gcc and clang respects aliasing involving them via extensions.

Lastly, I'd like to thank you for working on this. I'm really excited about covering these types of issues.

clang/test/Analysis/Checkers/StrictAliasingChecker/strict-aliasing.cpp
2 ↗(On Diff #394290)

I think fno-strict-aliasing should achieve this, by which the driver should transform that flag into the -relaxed-aliasing flag consumed by the backend.

@steakhal Thanks! I appreciate your comprehensive comment! I'll take everything you suggested into account.

clang/test/Analysis/Checkers/StrictAliasingChecker/strict-aliasing.cpp
2 ↗(On Diff #394290)

Yes, but here in the RUN line you should use a backend flag -relaxed-aliasing instead of -fno-strict-aliasing. -fno-strict-aliasing won't work here. I've tried.
P.S. Note that the checker works relying on the presentence of -relaxed-aliasing, so here the absense of -relaxed-aliasing is en equivalent of -fstrict-aliasing.

Improved AccessInferrer::isOppositeSign. Reworked tests.
TODO: Write more synthetic and real-world tests.

ASDenysPetrov updated this revision to Diff 395881.EditedDec 22 2021, 9:10 AM

Added more tests for records (classes, structs, unions). Improved AccessInferrer. Removed support of cast kinds such as DerivedToBase and BaseToDerived, since they are not implied in C++20 7.2.1 p11 paragraph.
TODO: White tests for multi-level casts, e.g.:

T1 a;              // a
auto* b = (T2*)&a; // {a, T2}
auto* c = (T3*)b;  // {{a, T2}, T3}
auto* d = (T4*)c;  // {{{a, T2}, T3}, T4}
auto e = *d;

TODO: Fix case with loc::ConcreteInt, e.g.:

T1 *a = nullptr;   // 0 loc
auto* b = (T2*)&a; // 0 loc
auto c = *d;       // We are not able to detect an original type and aliased type from ConcreteInt.
ASDenysPetrov edited the summary of this revision. (Show Details)Dec 22 2021, 9:53 AM

Improved the checker. Reworked tests.