This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Fix leak false positives before no-return functions caused by incomplete analyses.
ClosedPublic

Authored by NoQ on Dec 21 2016, 5:56 AM.

Details

Summary

Consider an example:

void foo(int y) {
  void *x = malloc(1);
  assert(y); // macro that expands to "if (!y) exit(1);"
  free(x);
}

In CFG block corresponding to exit(1), variable x is dead, because both CFG and LivenessAnalysis are aware of no-return functions and realize that we don't ever reach the reference to x in free(x) from this block.

Because x is dead, its binding - symbol returned by malloc - is also dead, and MallocChecker reports a memory leak warning.

However, because such warning would not be particularly useful (nobody ever frees memory before assertion failures), MallocChecker's BugType has setSuppressOnSink(true), and this warning would be discarded later by BugReporter and never presented to the user.

Warnings with suppress-on-sink are discarded during FlushReports when BugReporter notices that all paths in ExplodedGraph that pass through the warning eventually run into a sink node.

Apart from suppressing false positives similar to the example above, this mechanism has a second purpose - to filter out non-fatal bugs when the path runs into a fatal bug. For that second purpose, the mechanism works perfectly.

However, suppress-on-sink fails to filter out false positives when the analysis terminates too early - by running into analyzer limits, such as block count limits or graph size limits - and the interruption hits the narrow window between throwing the leak report and reaching the no-return function call. In such case the report is there, however suppression-on-sink doesn't work, because the sink node was never constructed in the incomplete ExplodedGraph.

In a particular report i've been investigating, the false positive disappeared when i set -analyzer-config max-nodes to less than 149995 or more than 150105 (+/- 0.08% of the default value 150000).

Note that suppress-on-sink is an "all paths" problem - we're trying to detect an event that occurs on all execution paths after a certain point. Such problems should not be solved by exploring ExplodedGraph for this very reason - the graph is not guaranteed to even contain all paths. In some cases it is acceptable to behave conservatively when the graph is known to be incomplete, however in this case it would result in disproportional amounts of leak false-negatives.

This patch implements a very partial solution: also suppress reports thrown against a statement-node that corresponds to a statement that belongs to a no-return block of the CFG.

This solution is partial because no-return functions that we failed to reach may also be found in subsequent blocks or in a different function. However, for the simple implementation of the assert() macro (that expands to an if followed by a no-return function), this patch fixes the problem.

Diff Detail

Repository
rL LLVM

Event Timeline

NoQ updated this revision to Diff 82229.Dec 21 2016, 5:56 AM
NoQ retitled this revision from to [analyzer] Fix leak false positives before no-return functions caused by incomplete analyses..
NoQ updated this object.
NoQ added a subscriber: cfe-commits.
a.sidorin edited edge metadata.Dec 21 2016, 7:59 AM

Looks useful and mostly good. A small advice is in inline comments.

lib/StaticAnalyzer/Core/BugReporter.cpp
3294 ↗(On Diff #82229)

Maybe it is possible to use CFGStmtMap for search?

a.sidorin added inline comments.Dec 21 2016, 8:20 AM
lib/StaticAnalyzer/Core/BugReporter.cpp
3363 ↗(On Diff #82229)

I took a brief look and found that we have Domination analysis for clang CFG but not PostDomination analysis. However, llvm::DominatorTreeBase that is used internally in clang::DominatorTree may be constructed for post-domination analysis. Is it possible to implement such analysis quickly (or modify clang::DominatorTree to support it)? If the answer is no, don't mind.

dcoughlin accepted this revision.Dec 21 2016, 8:49 AM
dcoughlin edited edge metadata.

With the change Aleksei suggested (can you get the CFGStmtMap from the AnalysisDeclContext?), looks good to me.

I especially like the test!

lib/StaticAnalyzer/Core/BugReporter.cpp
3363 ↗(On Diff #82229)

Do you actually want a FIXME here? Are you certain it would it be a good use of some future contributor's time to rewrite this? If not then you might want to soften it to a normal comment. (New contributors often search the codebase for FIXMEs to address as their first patch -- so a FIXME is a recommendation that someone actually fix it, rather than an acknowledgement/documentation of some known limitation).

test/Analysis/max-nodes-suppress-on-sink.c
6 ↗(On Diff #82229)

Using "throw" is not correct here. I would suggest "emit" or"report".

27 ↗(On Diff #82229)

This is great.

This revision is now accepted and ready to land.Dec 21 2016, 8:49 AM
This revision was automatically updated to reflect the committed changes.