This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Fix the liveness of Symbols for values in regions referred by LazyCompoundVal
ClosedPublic

Authored by tomasz-kaminski-sonarsource on Sep 30 2022, 3:25 AM.

Details

Summary

To illustrate our current understanding, let's start with the following program:
https://godbolt.org/z/33f6vheh1

void clang_analyzer_printState();

struct C {
   int x;
   int y;
   int more_padding;
};

struct D {
   C c;
   int z;
};

C foo(D d, int new_x, int new_y) {
   d.c.x = new_x;       // B1
   assert(d.c.x < 13);  // C1

   C c = d.c;           // L

   assert(d.c.y < 10);  // C2
   assert(d.z < 5);     // C3

   d.c.y = new_y;       // B2

   assert(d.c.y < 10);  // C4

   return c;  // R
}

In the code, we create a few bindings to subregions of root region d (B1, B2), a constrain on the values (C1, C2, ….), and create a lazyCompoundVal for the part of the region d at point L, which is returned at point R.

Now, the question is which of these should remain live as long the return value of the foo call is live. In perfect a word we should preserve:

  1. only the bindings of the subregions of d.c, which were created before the copy at L. In our example, this includes B1, and not B2. In other words, new_x should be live but new_y shouldn’t.
  2. constraints on the values of d.c, that are reachable through c. This can be created both before the point of making the copy (L) or after. In our case, that would be C1 and C2. But not C3 (d.z value is not reachable through c) and C4 (the original value of`d.c.y` was overridden at B2 after the creation of c).

The current code in the RegionStore covers the use case (1), by using the getInterestingValues() to extract bindings to parts of the referred region present in the store at the point of copy. This also partially covers point (2), in case when constraints are applied to a location that has binding at the point of the copy (in our case d.c.x in C1 that has value new_x), but it fails to preserve the constraints that require creating a new symbol for location (d.c.y in C2).

We introduce the concept of lazily copied locations (regions) to the SymbolReaper, i.e. for which a program can access the value stored at that location, but not its address. These locations are constructed as a set of regions referred to by lazyCompoundVal. A readable location (region) is a location that live or lazily copied . And symbols that refer to values in regions are alive if the region is readable.

For simplicity, we follow the current approach to live regions and mark the base region as lazily copied, and consider any subregions as readable. This makes some symbols falsy live (d.z in our example) and keeps the corresponding constraints alive.

The rename Regions to LiveRegions inside RegionStore is NFC change, that was done to make it clear, what is difference between regions stored in this two sets.

Regression Test: https://reviews.llvm.org/D134941
Co-authored-by: Balazs Benics <benicsbalazs@gmail.com>

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald Transcript
tomasz-kaminski-sonarsource requested review of this revision.Sep 30 2022, 3:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 30 2022, 3:25 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
tomasz-kaminski-sonarsource edited the summary of this revision. (Show Details)

I like the approach of this patch and I think this is somewhat aligned with @NoQ's ideas about

a list of explicitly-live compound values

and

"weak region roots" that aren't necessarily live themselves but anything derived from them ... is live

Coupled with the new tests for regression cases in D134941, I think this is really good.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
586

Could you please incorporate the definition of lazily copied locations (regions) from the summary to here as a comment?

653

Could you please incorporate the definition of readable locations (regions) from the summary to here as a comment?

clang/lib/StaticAnalyzer/Core/RegionStore.cpp
2841–2842

Just a nit, I wonder if you might have a test case for this (which should fail for now).

clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
461

Just out of curiosity, do you have plans to tackle this todo sometime?

Included additional tests that corresponds to TODO.

tomasz-kaminski-sonarsource marked 3 inline comments as done.

Applied review suggestions.

Applied all review suggestions.

clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
461

We do not plan to takle it in near future.

Updated diff to be mergable.

Herald added projects: Restricted Project, Restricted Project, Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript

Fighting with arcanist.

martong accepted this revision.Oct 3 2022, 7:31 AM

Thanks for the updates. I am okay with it now. LGTM. But please wait for NoQ's approval. So, this is a gentle ping for you @NoQ :)

clang/test/Analysis/trivial-copy-struct.cpp
62
98
This revision is now accepted and ready to land.Oct 3 2022, 7:31 AM

Applied suggested comment updates.

If we end up going with this approach, I wonder if it would be a great time to update some of the docs here: https://clang.llvm.org/docs/analyzer/developer-docs/RegionStore.html
Usually, we are not doing a great job keeping these documentations up to date. I think the logic to determine which symbols and regions are live and how that logic interacts with the different types of memory regions might be important enough to have some documentation on it.

(Also, I think we should add link to the SA talks at the LLVM Dev Conf., but that is completely unrelated to this change.)

xazax.hun accepted this revision.Oct 3 2022, 9:35 AM

I also like the approach, but wait for @NoQ, he has the most experience in this area :)

NoQ added a comment.Oct 3 2022, 3:46 PM

Wow thanks!!

Yeah this matches my understanding of the problem. I still encourage you to test it on real-world code before committing, and carefully investigate every change in diagnostics, because symbol reaper is very convoluted and filled with insane cornercases.

clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
461

Could you add a negative/FIXME test for it?

At a glance I suspect that this TODO is significantly less important for isLiveRegion() than it is for your new function, so I encourage you to explore the possibility of dropping getBaseRegion(), even if just a little bit and doesn't have to be in this patch.

If a smaller subregion is truly live, any value inside of the base region can theoretically be accessed through safe pointer arithmetic. It's very difficult to prove that it can't be accessed anymore. Every pointer escape will be a potential access.

In your case, however, if the superregion is neither live nor lazily copied, the information outside of the lazily copied subregion is truly lost, there's literally nothing the program can do to recover it.

clang/test/Analysis/trivial-copy-struct.cpp
98

Do you know what's causing this to not work? Is this a regression or just never worked?

int3 resigned from this revision.Oct 3 2022, 4:50 PM
clang/test/Analysis/trivial-copy-struct.cpp
98

This example never worked. We have an in-progress fix, that we are testing now.

First of all, thanks for the feedback!

If we end up going with this approach, I wonder if it would be a great time to update some of the docs here: https://clang.llvm.org/docs/analyzer/developer-docs/RegionStore.html
Usually, we are not doing a great job keeping these documentations up to date. I think the logic to determine which symbols and regions are live and how that logic interacts with the different types of memory regions might be important enough to have some documentation on it.

Yes, I'll post a patch addressing this. Thanks for noting.


Wow thanks!!

Yeah this matches my understanding of the problem. I still encourage you to test it on real-world code before committing, and carefully investigate every change in diagnostics, because symbol reaper is very convoluted and filled with insane cornercases.

That's true. We did a careful investigation and the numbers are promising even at large scale.
The upside is that even if it broke something, it does not have a significant impact. The downside is that we wished for greater improvement/impact by fixing this.

[...] carefully investigate every change in diagnostics, [...]

I investigated multiple cases, out of which I believe all of them were intentionally affected, hence improved.
Note that however, I did not investigate all the changes but only a handful of a (representative) set due to the nature of collecting, minimizing, and understanding the reports is really time-consuming.

I'd like to proceed with this patch as-is. And possibly land further incremental step(s) on top of this, such as D135136.
Other than D135136 though, we don't plan to push this area any further for the time being.

clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
461

Could you add a negative/FIXME test for it?

At a glance I suspect that this TODO is significantly less important for isLiveRegion() than it is for your new function, so I encourage you to explore the possibility of dropping getBaseRegion(), even if just a little bit and doesn't have to be in this patch.

So far we could not come up with a test case demonstrating this case.
Right now we don't plan to investigate this area either in the foreseeable future.

clang/test/Analysis/trivial-copy-struct.cpp
98

Fixed by D135136.

steakhal added inline comments.Oct 4 2022, 4:39 AM
clang/test/Analysis/trivial-copy-struct.cpp
59
tomasz-kaminski-sonarsource marked 2 inline comments as done.EditedOct 6 2022, 3:15 AM

As a result of our internal test on around ~170 projects (~20 Widnows, ~150 Linux) that are compromised of several hundreds of millions of lines of code, the impact on the files that parsed correctly was: 5 issues disappearing and 4 new issues. We investigated all of the reports, and the changes seemed justified:

  • removing issues from impossible paths, that are now correctly recognized due to preserved constraints
  • the value of location not being reported as garbage
  • undefined behavior for overflowing shift operation, as we preserve constrain of the bits
  • recognition of null pointer values
tomasz-kaminski-sonarsource retitled this revision from [analyzer] Fix liveness of Symbols for values in regions reffered by LazyCompoundVal to [analyzer] Fix the liveness of Symbols for values in regions referred by LazyCompoundVal.Oct 6 2022, 7:34 AM
tomasz-kaminski-sonarsource marked an inline comment as done.Oct 6 2022, 9:48 AM
tomasz-kaminski-sonarsource added inline comments.
clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
461

@NoQ We were banging our heads against this question, and we haven't been able to create or find any example when using base region would cause a problem. Moreover, we concluded that constructing an example, where the current approach would differ in reported issues, is probably impossible.

To illustrate this I’ll refer back to the example in the summary of this patch.
The side effect of our change is that for symbol reg_<d.z>, representing the falsely readable location, didn’t have any binding. isLive(reg_<d.z>) will return true. However, to observe the effect, either:
a) the code needs to be able to read the reg_<d.z>
b) we check if we should preserve constraint on the reg_<d.z>

If we consider option (a), that means that the code still has a reference/pointer to objects d, d.z, or to the copy of either of them. In these situations, the presence of such pointer/copy should make reg_<d.z> live - regardless of the existence of lazyCompoundVal to subregions of d, so isLive(reg_<d.z>) would return true anyway.

In the case of (b), we will preserve all constraints that refer to reg_<d.z>. If reg_<d.z> would be reachable/accessible, similar reasoning as for option (a) would conclude that it must be live anyway. In contrast, when the program can no longer reach/access the value of d.z, the presence of this constraint cannot impact the result of the analysis, hence it would do no harm.

Given the tradeoff between additional dormant constraints and the complexity (and cost) of additional checking in SymbolReaper, we believe that using the base region is the right choice, and we should simply replace TODO with an appropriate explanation.

What do you think @NoQ?

It seems like we are all aligned.
I'll land this tomorrow.