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

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Fangrui Song via cfe-dev
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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

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

Fangrui Song via cfe-dev
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.

On 4/7/20 6:48 PM, Balázs Benics via cfe-dev wrote:

> 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
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

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

Fangrui Song via cfe-dev
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 :|
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 <[hidden email]> ezt írta (időpont: 2020. ápr. 7., K, 19:35):
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.

On 4/7/20 6:48 PM, Balázs Benics via cfe-dev wrote:
> 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
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev