Skip to content

pHL while with strict variant fails to handle cases where the loop invariant is not satisfied #1103

Description

@oskgo

The pHL while variant in question proves termination of the while loop by proving that the provided variant decreases every iteration but is bounded below by 0, meaning that its initial value is a bound on the number of iterations.

The problem is that that the tactic derives the probability bound entirely from the probability of reaching the while statement with the invariant satisfied, failing to take into account the case where it is not satisfied.

MRE:

require import Real.

op b: bool.

module M = {proc p() = {while (b) {}}}.

lemma bad: phoare[M.p: true ==> true] = 0%r.
proof.
proc.
by while false 0.
qed.

This is unrelated to the recent issue with negative probabilities.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions