Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BaseInvariant internal computations can overflow #1629

Open
sim642 opened this issue Nov 19, 2024 · 0 comments
Open

BaseInvariant internal computations can overflow #1629

sim642 opened this issue Nov 19, 2024 · 0 comments

Comments

@sim642
Copy link
Member

sim642 commented Nov 19, 2024

We have AnalysisState.executing_speculative_computations disabled in BaseInvariant, so overflow warnings are not produced from these computations, but that's not the whole story. With sem.int.signed_overflow being assume_top, it can still lead to imprecise results.

For example consider x + 1 <= 100 with intervals:

  1. BaseInvariant uses the inequality and its right argument to refine the left argument with ID.ending 100 = [min_int, 100].
  2. BaseInvariant then uses that value and the right argument of the addition to compute the refined left argument of the addition using ID.sub [min_int,100] [1,1] = [min_int-1,99].
  3. If sem.int.signed_overflow is assume_top/assume_wraparound, then this ID.sub handles the underflow and returns top ([min_int,max_int]) instead.

Thus x cannot be refined at all. And this is even when the program itself has no overflow in x + 1 because it may be bounded, e.g. x = [min_int,1000].
The overflow in BaseInvariant doing the subtraction (or whatever other operation) to do the backward evaluation is purely caused by itself: the way inequalities are refined by ID.ending constructs the interval with min_int lower bound (the program cannot refine this in any way) and performs ID.sub on that.

So just suppressing overflow warnings in BaseInvariant isn't enough. Instead its (speculative) computations should assume no overflows also in the values the domains compute. Although I have no idea if temporarily changing the option to assume_none is the right thing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant