Skip to content

Assume loop conditions in loop bodies with sound loop havoc - #320

Open
CatarinaGamboa wants to merge 3 commits into
mainfrom
fix/306-loop-condition
Open

CatarinaGamboa wants to merge 3 commits into
mainfrom
fix/306-loop-condition

Conversation

@CatarinaGamboa

@CatarinaGamboa CatarinaGamboa commented Oct 2, 2026 •

Copy link
Copy Markdown
Collaborator

Problem

The verifier checked a loop body using values from before the loop. It could miss errors in later iterations and carry one iteration's facts past the loop. It also checked a for update before the body.

Example

int x = 3;
while (x > 0) {
    @Refinement("_ > 0") int y = x - 1; // Refinement Error
    x--;
}

Here x0, x1, etc. are symbolic versions of the same Java variable:

x0 = 3                       before the loop
x1 = fresh int               havoc before one arbitrary iteration; forget x0 = 3
assume x1 > 0                the guard holds on entry to the body
y = x1 - 1; require y > 0     fails when x1 = 1, because y = 0
x2 = x1 - 1                  the decrement, if checking continues
x3 = fresh int               havoc again after the loop

x1 = 1 is reachable: the successive loop-entry values are 3, 2, then 1. The previous verifier checked the body using the initial value 3 and accepted the program. The fresh x1 keeps only x's declared refinement, so this later iteration is now checked.

Change

  • Havoc values the loop may change before and after checking one arbitrary iteration. Assume a while or for guard in the body when it has no direct variable writes.
  • Check for initialization, condition, body, and update in execution order; account for continue. Handle do and for-each loops conservatively.
  • Discard facts learned inside the loop afterward. We do not infer !guard after exit, since break can leave while the guard is true. This loses precision but avoids an invalid assumption.

Tests cover later iterations, guard facts, loop order, continue, break, fields, and typestate. mvn test passes.

Known existing limit: alias and this typestate changes can still be accepted incorrectly. This PR addresses the loop reasoning above; it does not establish soundness for those cases.

Fixes #306.

CatarinaGamboa and others added 3 commits October 2, 2026 13:56
The condition of a while/for loop is now assumed in its body as a path
condition, like the condition of an if, so `while (n > 0) use(n)` verifies.

Loops were previously checked as if the body ran exactly once with the
pre-loop values, and the for update was visited before the body. To keep
the new assumption sound, a loop is now checked for one arbitrary
iteration:
- variables written in the loop are havocked (keep only their declared
  refinement, which every write re-checks) before the loop and after it;
- for loops visit init, condition, body, then update;
- do-while does not assume the condition in the body;
- path conditions added inside a loop (its condition, `if (..) break;`)
  are dropped after it;
- conditions that write variables (e.g. `(n = read()) > 0`) assume nothing.

Also drop path conditions on a variable when it is incremented or
decremented (`i++`), as already done for assignments: before,
`if (i < 10) { i++; use(i); }` wrongly assumed `i < 10` for the new value.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Review fixes for the loop-condition change (#306):
- a continue reaches the for update without the rest of the body, so when
  the body has one, the update no longer sees the body's path conditions
  or assignments (`for (..; ..; use(n)) { if (n <= 0) continue; ... }`
  was accepted)
- a loop also changes fields (through any call) and the state of objects
  it calls state-changing methods on; these are now havocked too, since
  the assumed condition could otherwise combine with their stale values
  (accepted programs that main rejected)
- drop the null check on the condition, dead since null literals carry no
  information (#311)
- move the i++ path-condition fix out (it is not needed for loops and is a
  separate pre-existing bug in if branches)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

@rcosta358 rcosta358 left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Really liked the havoc approach!

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

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

while loop condition is not assumed inside the loop body

2 participants