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

ERROR verdict for both branches dead in SV-COMP #1576

Closed
sim642 opened this issue Sep 26, 2024 · 4 comments · Fixed by #1579
Closed

ERROR verdict for both branches dead in SV-COMP #1576

sim642 opened this issue Sep 26, 2024 · 4 comments · Fixed by #1579
Assignees
Labels
bug sv-comp SV-COMP (analyses, results), witnesses unsound
Milestone

Comments

@sim642
Copy link
Member

sim642 commented Sep 26, 2024

Apparently there are SV-COMP tasks where we output the "both branches dead" unsoundness warning, but still happily give a true SV-COMP result. We've been lucky that this hasn't caused unsound verdicts.
In these cases the verdict should instead be something like ERROR (both branches dead).

We do this for fixpoint errors with ERROR (fixpoint).

@sim642 sim642 added bug unsound sv-comp SV-COMP (analyses, results), witnesses labels Sep 26, 2024
@sim642 sim642 added this to the SV-COMP 2025 milestone Sep 26, 2024
@sim642 sim642 self-assigned this Sep 26, 2024
@karoliineh
Copy link
Member

The example I stumbled upon was termination-restricted-15/IntPath.c

extern int __VERIFIER_nondet_int(void);

int main() {
    int i;
    int x;
    int y;
    i = __VERIFIER_nondet_int();
    x = 0;
    y = 0;
    
    if (i > 10) {
        x = 1;
    } else {
        y = 1;
    }
    while (x == y) { }
    
    return 0;
}

which yields:

...
[Error][Analyzer][Unsound] both branches over condition 'x == y' are dead (./termination-restricted-15/IntPath.c:18:12-18:18)
SV-COMP result: true
[Warning][Analyzer] Invariant Apron: cannot convert to cil var in overflow preserving manner: term18_5_id0#1998
[Info][Witness] witness generation summary:
  total generation entries: 1
[Error][Analyzer][Unsound] Both branches dead

@michael-schwarz
Copy link
Member

The example I stumbled upon was termination-restricted-15/IntPath.c

Looks like it may be an unsoundness in our apron bindings we only bump into for polyhedra, which are enabled for termination.

@sim642
Copy link
Member Author

sim642 commented Sep 27, 2024

Looks like it may be an unsoundness in our apron bindings we only bump into for polyhedra, which are enabled for termination.

It's not that, because it also happens with octagon. Anyway, I extracted the unsoundness itself to #1578.

@sim642
Copy link
Member Author

sim642 commented Sep 27, 2024

There's something else odd going on as well: even though termination is supposed to make us use polyhedra, it's actually still using octagon. Explicitly setting the domain from command line works.

EDIT: Forcing a single unroll and polyhedra, there's a state with

 [|2y#302-1=0; 2x#301-1=0; term18_5_id0#1998-1=0; -2i#300+2147483657>=0; 2i#300+2147483637>=0|]

which isn't bottom according to Apron and thus we don't make it dead.
Only when doing some subsequent operations, Apron realizes the contradiction (due to integer variables), so both branches are dead.
So it's not as simple as the predecessor being dead/bottom even.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug sv-comp SV-COMP (analyses, results), witnesses unsound
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants