[analyzer] Extend constraint manager to be able to compare simple SymSymExprs

Clang Frontend Static Analyzer
1

The constraint manager has limited functionality in comparing symbols to symbols.
Though, it wouldn’t be too hard to make it a bit smarter.

I would like to implement the following logic in the constraint manager class hierarchy:
Given a and b well-constrained symbols.
We should know that a less than b if the possible maximum value of a is still less than the minimum value of b.
In other words: maxOf(a) < minOf(b) => a < b

AFAIK RangedConstraintManager provides the interface to compare symbols to constants.
The RangeConstraintManager class only implements that interface.

Should I extend the RangedConstraintManager interface to be able to compare symbols to symbols?
Or, I could create another interface layer on top of RangedConstraintManager interface to provide the necessary functions.

Which approach should I prefer?

Balazs

2

These layers never made much sense to me. We only really need two: `ConstraintManager` as the abstract base class and `RangeConstraintManager` as the particular implementation that we use. If you destroy the two intermediate layers i wouldn't mind.

On the other hand, our constraint manager is very much pushed to its limits where it is almost impossible to reason about the correctness and algorithmic complexity of the code we're writing. We should really do something about this whole technical debt thing and come up with a better structure for our implementation before landing more large features. Everybody keeps saying "oh but it's just a tiny feature and it'll immediately make my use case better" but after a few dozen iterations it ends up being a mess that's almost impossible to debug when it causes a sudden performance drop.

3

If you destroy the two intermediate layers i wouldn’t mind.

Then I will just extend the abstract interface and implement this in that way.

On the other hand, our constraint manager is very much pushed to its
limits where it is almost impossible to reason about the correctness and
algorithmic complexity of the code we’re writing.

Definitely an issue.

We should really do something about this whole technical debt thing and come
up with a better structure for our implementation before landing more large features.

Unfortunately, I’m not qualified enough to guide this :expressionless:
The only thing I see is that really hard to strike the balance between accuracy and (time) complexity.

Everybody keeps saying “oh but it’s just a tiny feature and
it’ll immediately make my use case better” but…

It seems reasonable, but I think we really need to be able to compare symbols to symbols
(For now, only implemented for comparing pointers - I guess for modeling iterators).

In one of our previous emails you proposed the: ANALYZER_ASSERT(ANALYZER_EXTENT(buff) == size);
expressing hidden precondition assumptions to the analyzer.

Turns out the next obstacle is the constraint manager, which can not utilize this assumption, like in these cases:
void symbol_constraints1(char *src, int n) {
assert(clang_analyzer_getExtent(src) > 10);
if (0 <= n && n < 10) {
// should be always true
clang_analyzer_eval(n < clang_analyzer_getExtent(src));
}
}
void symbol_constraints2(char *src, int len, int n) {
assert(clang_analyzer_getExtent(src) == len);
if (0 <= n && n < len) {
// should be always true
clang_analyzer_eval(n < clang_analyzer_getExtent(src));
}
}

As my plan was to hoist the diagnostic parts of the GenericTaintChecker into eg. the CStringChecker, I can not do it in a backward-compatible way.
Since CStringChecker would warn for more cases, it would be fair to provide a way to suppress the new warnings. I think asserts like these, are the way forward.
But constraints are useless if the constraint manager can not utilize those.

Balazs

Artem Dergachev <noqnoqneo@gmail.com> ezt írta (időpont: 2020. ápr. 7., K, 19:35):