Differential D27710
[analyzer] Prohibit ExplodedGraph's edges duplicating Authored by ilya-palachev on Dec 13 2016, 5:54 AM.
Details Current implementation doesn't take care about the duplicates in edges This patch prohibits this situation, by checking whether the actual
Diff Detail Event Timeline
Comment Actions Are there any negative effects from having the duplicates in edges? When does this occur? It's a bit suspicious since we have a FromN, and a path is split at that node, resulting in successors that are the same. Is it possible that whoever split the state did not encode enough interesting info? Comment Actions Yes, you're right; in current implementation there seems to be no negative effects from this, since duplicate edges are quite rare, and they produce very small overhead on memory (just two additional pointers for each excessive edge).
Yes, this does occur (for one of our checkers on Android). Consider the checker that can emit warnings on multiple dead symbols (one warning for each buggy symbol). When the checker encounters such situation, it first emits a warning for the 1st symbol, then for the 2nd one. For the 2nd and other symbols the CheckerContext::addTransition returns `nullptr'. That means that the requested node already exists, because the State hasn't changed. And for each warning beginning from the 2nd, the additional edge is added for the ExplodedGraph. It can be even simply seen with DOT graph. Yes, this problem can be resolved with checker tags for nodes, but in this case we'll need to create new tag for each such warning (because ProgramPoint and ProgramState are equal for them all). Moreover, such cases can even lead to non-determinism in warnings. The checker stores a set(map/list...) of buggy symbols (regions...) in GDM. When checkDeadSymbols callback happens, this set is iterated, and the checker tries to emit a warning for each of them. But actually the order in which symbols are stored in the set depends on their order as pointers, and it's controlled by allocator. The allocator contains non-determinism by design, and region for symbol A can be greater (as a pointer) than the region for the symbol B in one analysis run, and smaller during the another run. That's why in such cases different warnings can be emitted from time to time. The discussed patch doesn't address this issue, but I'd like at least to discuss the situation. Comment Actions To deal with non-determinism, you can sort the results by non-pointer values, such as identifiers, before producing the warnings. It is not clear if you want to print all warnings or only the first one. Is it an option to list all dead symbols in one warning message? Do we support attaching multiple bug reports to the same node? Comment Actions I think MallocChecker should be (or should have been) affected by the problem you describe, so we can use it as an example. That's what MallocChecker does, and it works: void foo() {
void *x = malloc(1);
void *y = malloc(1);
(void)(y - x); // expected-warning{{'x'}} expected-warning{{'y'}}
}Comment Actions If this is a common mistake for checker writers, we could consider adding assertions that check for this situation. We should make sure that we do not to add any release builds overhead. Maybe we could put this check behind NDEBUG or ensure that whatever code is added to support the assertion is optimized away. As Artem points out, the checkers in tree do not create a node for every bug reported - there is no reason to do that. Comment Actions Thanks for review!
Yes... But why does generateNonFatalErrorNode return nullptr in case when the node already exists? Isn't it designed so that to prevent multiple reports being thrown for the same node? If so, then the code contains a lot of such checks. I don't understand why the following test passes, because each of two checkers: MallocChecker and SimpleStreamChecker are using generateNonFatalErrorNode method: // RUN: %clang_cc1 -analyze -analyzer-checker=unix.Malloc,alpha.unix.SimpleStream -analyzer-store region -verify %s
typedef struct _IO_FILE FILE;
extern FILE *fopen(const char *path, const char *mode);
extern int fclose(FILE *fp);
typedef __typeof(sizeof(int)) size_t;
void *malloc(size_t);
void free(void *);
void test() {
void *p = malloc(1);
void *r = fopen("foo", "r");
if (r) {
(void)(p - r);
// expected-warning@-1{{Potential leak of memory}}
// expected-warning@-2{{Opened file is never closed}}
}
else {
fclose(r);
free(p);
}
}Maybe it's possible to invent such a testcase when two checkers begin to conflict for the node. Or not? Comment Actions That's because error nodes generated by different checkers have different program point, because they have different program point tags, because their tag is the checker that throws the report. I'm referring to this funny code in Checker.h:473: class CheckerBase : public ProgramPointTag I do not have a certain answer (i.e. bugs me as well), but this behavior allows knowing if this checker has already reported a bug on a different path that leads to the same predecessor node and therefore to the same error node. So the use-case i'm a bit worried about is when a checker finds the same error node on a different path and suddenly wants to throw a different report (by bug kind). But i think it's normally impossible because the checker is never, in any callback, aware of the path it took before reaching the predecessor node, only the node itself. I think i lost track of the original question's discussion>< Do we still believe that duplicated edges are a problem? | ||||||
I prefer having the braces written in this case, but it is a minor nit.
Wouldn't using an algorithm like std::find work as well?