Formal verification for pull requests, explained
By Steven Van ·
Graphify's per-repository toggle checks each changed function against its old version, returning one of five verdicts, and only one of them is a proof.
Graphify now checks each changed function in a pull request against its earlier version. The check either establishes that the two behave the same within a checked range, or produces a concrete input on which they give different results. Graphify's explainer describes what the check proves and how to act on each verdict. Formal verification in Graphify shipped on August 11 alongside pull request reviews, and on September 13 each repository gained its own setting to turn it on or off.
How to run it
- Connect the repository in Graphify.
- Open the repository's options menu and turn on Formal verification.
- Open or update a pull request.
- On Behavior checks, expand the pull request to see a row per changed function, each with its verdict and an explanation.
What the check compares
This is equivalence checking. The previous implementation is the reference, and the question is whether the new one computes the same result for the same inputs. It compares two versions with each other, not one version against a written specification. A proof therefore says a refactor preserved behaviour, not that the behaviour was right to begin with.
The post gives a clamp function as an example. max(lo, min(x, hi)) was refactored to min(hi, max(x, lo)). The two agree whenever lo = hi and disagree when the bounds are swapped: with x=-2, lo=-1, hi=-2, the old version returns -1 and the new one returns -2. Checking every combination from -2 to 2 finds 50 inputs that differ.
The five verdicts
- Behavior changed: the old and new versions gave different results on the same input.
- Proven same: the same result for every input in the range checked. This is the only proof.
- No change found: same results on every input tried, which is good evidence but not proof.
- Not checked: the function could not be compared, so it says nothing either way.
- Couldn't run: the check itself failed, which says nothing about the code.
A run marked Completed has finished, but that does not mean every function was proven the same. A run that verified no functions does not mean the change passed.
Acting on a behaviour change
If the change was intended, note it in the pull request so reviewers know. If not, use the distinguishing input to reproduce the difference and turn it into a regression test before fixing the code. The docs show whether the witness was reproduced in a sandbox or remains unconfirmed. Learning can tune advisory review findings, but it cannot change a proof verdict or hide a witness.
Availability
The toggle is per repository. The author turns it on where a silent behaviour change is expensive, such as billing, auth, parsers and shared libraries, and leaves it off for prototypes. Formal verification is not part of open-source Graphify. It runs in the hosted app on pull requests, while the open-source version provides the code graph and impact commands.
