This is an archive of the discontinued LLVM Phabricator instance.

[analyzer][NFCI] Allow clients of NoStateChangeFuncVisitor to check entire function calls, rather than each ExplodedNode in it
ClosedPublic

Authored by Szelethus on Aug 25 2021, 5:18 AM.

Details

Summary

D105553 added NoStateChangeFuncVisitor, an abstract class to aid in creating notes such as "Returning without writing to 'x'", or "Returning without changing the ownership status of allocated memory". Its clients need to define, among other things, what a change of state is.

For code like this:

f() {
  g();
}

foo() {
  f();
  h();
}

We'd have a path in the ExplodedGraph that looks like this:

             -- <g> -->
            /          \       
         ---     <f>    -------->        --- <h> --->
        /                        \      /            \
--------        <foo>             ------    <foo>     -->

When we're interested in whether f neglected to change some property, NoStateChangeFuncVisitor asks these questions:

                       ÷×~     
                -- <g> -->
           ß   /          \$    @&#*       
            ---     <f>    -------->        --- <h> --->
           /                        \      /            \
   --------        <foo>             ------    <foo>     -->

                           
Has anything changed in between # and *?
Has anything changed in between & and *?
Has anything changed in between @ and *?
...
Has anything changed in between $ and *?
Has anything changed in between × and ~?
Has anything changed in between ÷ and ~?
...
Has anything changed in between ß and *?
...

This is a rather thorough line of questioning, which is why in D105819, I was only interested in whether state *right before* and *right after* a function call changed, and early returned to the CallEnter location:

if (!CurrN->getLocationAs<CallEnter>())
  return;

Except that I made a typo, and forgot to negate the condition. So, in this patch, I'm fixing that, and under the same hood allow all clients to decide to do this whole-function check instead of the thorough one.

Diff Detail

Event Timeline

Szelethus created this revision.Aug 25 2021, 5:18 AM
Szelethus requested review of this revision.Aug 25 2021, 5:18 AM

I also added new dump methods -- I had a trouble before realizing that CallEnter's stack frame is actually the *caller's*, not the *callee's* stack frame. Changes in findModifyingFrames aim to make the function more readable, and make sure that the correct stack frame will be marked as modifying.

NoQ added a comment.Aug 26 2021, 9:57 AM

Would this work correctly when the property is changed but then reverted to its original state? This probably can't happen to MallocChecker (what has been freed cannot be unfreed) but it may happen to eg. PthreadLockChecker or to, well, Stores. In such cases it would be incorrect to say "returning without changing the state".

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
370

This is the right successor because we're in a heavily trimmed exploded graph, right?

Would this work correctly when the property is changed but then reverted to its original state? This probably can't happen to MallocChecker (what has been freed cannot be unfreed) but it may happen to eg. PthreadLockChecker or to, well, Stores. In such cases it would be incorrect to say "returning without changing the state".

It should! But you have a point, I don't have the code to prove it right away. Maybe if I factored out the symbol part into NoStateChangeToSymbolVisitor, as teased in D105553#2864318, it'd have an easier time to see it. With that said, I don't currently see how the current implementation would be faulty, but even if it is, the patch adds an option, and doesn't the take old one (that NoStoreFuncVisitor still uses) away.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
370

Should be, yes.

NoQ added a comment.Aug 26 2021, 2:01 PM

It should! But you have a point, I don't have the code to prove it right away. Maybe if I factored out the symbol part into NoStateChangeToSymbolVisitor, as teased in D105553#2864318, it'd have an easier time to see it. With that said, I don't currently see how the current implementation would be faulty, but even if it is, the patch adds an option, and doesn't the take old one (that NoStoreFuncVisitor still uses) away.

I mean, your implementation of findModifyingFrames() mostly boils down to:

return CallEnterN->getState()->get<State>(X) !=
     CallExitEndN->getState()->get<State>(X);

So if, say, X is a mutex and we're wondering whether it was unlocked in the function, but in reality it was unlocked and immediately locked again, then the above test would say "not modified" and you can't notice that it was modified temporarily without scanning all intermediate nodes. So if your note needs to make a distinction between "was not touched" and "was touched but reverted" you'll still need to do it the old way. I think this should be documented loudly in the comments.

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
369

Wait, no, I don't think this test is sufficient. You may run into a CallExitEnd of a nested stack frame before you reach the CallExitEnd of the stack frame in question:

-> CallEnter foo()       --->
  -> CallEnter bar()        |
  <- CallExitEnd bar()      <--- ???
<- CallExitEnd foo()

Nice work!

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
361

Why don't we add the stack frame here to FramesModifyingCalculated as well? If we are in a nested stack frame and we step back to a parent then it would be redundant to do the calculation again for the parent.

Ahh, to be honest, I think the idea of having both FramesModifying and FramesModifyingCalculated separated is prone to errors.
Why don't we have a simple map<StackFramContext, bool> with the boolean true meaning that the frame is modifying? And if the frame is not in the map that means it had never been calculated before.

370

Would it make sense to assert that there are no more than one successor ?

400

Using a for could simplify this loop and would eliminate the need to have a redundant loop variable bump both at line 420 and at 393.

martong added inline comments.Aug 27 2021, 6:56 AM
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h
675

You have no such parameter. But I guess we can get that from either of them.

Szelethus updated this revision to Diff 369935.Sep 1 2021, 8:24 AM
Szelethus marked 5 inline comments as done.
  • Make sure that the matching CallExitEnd is retrieved.
  • Add a unit test to neatly demonstrate how the visitor is intended to be used.
  • Fix the rest of the nits.
Szelethus marked an inline comment as done.Sep 1 2021, 8:25 AM
Szelethus added inline comments.
clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
361

Yes, its stupid, but its just the one thing I didn't want to bother myself with. Though I agree it'd be better to drop these sets for something a lot more elegant. Btw mind that we insert into the calculated set each time we enter a new stack frame.

I'll leave a TODO, if you don't mind.

369

Good point. Added a bunch of asserts and changed to code to both retrieve, and ensure that the correct node is retrieved.

Szelethus added inline comments.Sep 2 2021, 2:42 AM
clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h
683–685

Whoops, this is wildly incorrect. Gotta fix that. The inlined function's stack frame is retrievable from the CallEnters first successor, or CallExitEnds first predecessor.

martong accepted this revision.Sep 2 2021, 3:42 AM

Thanks! My concerns are addressed, looks good to me!

This revision is now accepted and ready to land.Sep 2 2021, 3:42 AM
This revision was landed with ongoing or failed builds.Sep 2 2021, 7:57 AM
This revision was automatically updated to reflect the committed changes.
thakis added a subscriber: thakis.Sep 2 2021, 8:04 AM

This seems to break tests: http://45.33.8.238/linux/54991/step_7.txt

Please take a look and revert for now if it takes a while to fix.

Szelethus reopened this revision.Sep 2 2021, 8:28 AM
This revision is now accepted and ready to land.Sep 2 2021, 8:28 AM

I just reverted this again because of a bot failure here:

https://green.lab.llvm.org/green/job/clang-stage1-cmake-RA-incremental/23380/consoleFull

Please fix and recommit!

Szelethus reopened this revision.Sep 4 2021, 2:34 AM
This revision is now accepted and ready to land.Sep 4 2021, 2:34 AM

Hi @Szelethus
A couple of tests fail for me on trunk with this patch:

Failed Tests (3):
  Clang-Unit :: StaticAnalyzer/./StaticAnalysisTests/FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeDueToRefinedConstraintNoReport
  Clang-Unit :: StaticAnalyzer/./StaticAnalysisTests/FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
  Clang-Unit :: StaticAnalyzer/./StaticAnalysisTests/FalsePositiveRefutationBRVisitorTestBase.UnSatInTheMiddleNoReport

Details from one failure below:

seroius03977 [12:05] [uabelho/master-github/llvm] -> /repo/uabelho/master-github/llvm/build-all/tools/clang/unittests/StaticAnalyzer/./StaticAnalysisTests --gtest_filter=FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
Note: Google Test filter = FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from FalsePositiveRefutationBRVisitorTestBase
[ RUN      ] FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport
UnSatAtErrorNodeWithNewSymbolNoReport.cc:8:7: warning: REACHED_WITH_NO_CONTRADICTION [test.FalsePositiveGenerator]
      reachedWithNoContradiction();
      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 warning generated.
/repo/uabelho/master-github/clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp:162: Failure
Expected equality of these values:
  Diags
    Which is: "test.FalsePositiveGenerator: Assuming the condition is false | REACHED_WITH_NO_CONTRADICTION\n"
  "test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION\n"
UnSatAtErrorNodeWithNewSymbolNoReport.cc:8:7: warning: REACHED_WITH_NO_CONTRADICTION [test.FalsePositiveGenerator]
      reachedWithNoContradiction();
      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
UnSatAtErrorNodeWithNewSymbolNoReport.cc:9:7: warning: CAN_BE_TRUE [test.FalsePositiveGenerator]
      reportIfCanBeTrue(x == 0); // contradiction
      ^~~~~~~~~~~~~~~~~~~~~~~~~
2 warnings generated.
/repo/uabelho/master-github/clang/unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp:171: Failure
Expected equality of these values:
  Diags2
    Which is: "test.FalsePositiveGenerator: Assuming the condition is false | REACHED_WITH_NO_CONTRADICTION\ntest.FalsePositiveGenerator: Assuming the condition is false | CAN_BE_TRUE\n"
  "test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION\n" "test.FalsePositiveGenerator: CAN_BE_TRUE\n"
    Which is: "test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION\ntest.FalsePositiveGenerator: CAN_BE_TRUE\n"
With diff:
@@ -1,2 +1,2 @@
-test.FalsePositiveGenerator: Assuming the condition is false | REACHED_WITH_NO_CONTRADICTION
-test.FalsePositiveGenerator: Assuming the condition is false | CAN_BE_TRUE\n
+test.FalsePositiveGenerator: REACHED_WITH_NO_CONTRADICTION
+test.FalsePositiveGenerator: CAN_BE_TRUE\n

[  FAILED  ] FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport (41 ms)
[----------] 1 test from FalsePositiveRefutationBRVisitorTestBase (41 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (42 ms total)
[  PASSED  ] 0 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] FalsePositiveRefutationBRVisitorTestBase.UnSatAtErrorNodeWithNewSymbolNoReport

 1 FAILED TEST

I'll attend to this ASAP. Thanks for the heads up!

Hi @Szelethus
A couple of tests fail for me on trunk with this patch

Uh, that's my unittest :D
I suspect you are running some sort of CI where you set up Z3.

I suspect we should slightly modify the expected output then.

Hi @Szelethus
A couple of tests fail for me on trunk with this patch

Uh, that's my unittest :D
I suspect you are running some sort of CI where you set up Z3.

Yes, I have Z3 enabled.

Yes now it works.
Thank you!