Diffy: Inductive Reasoning of Array Programs using Difference Invariants
This addresses the problem of verifying array programs for researchers and practitioners in formal methods, offering a novel approach that simplifies proofs compared to classical techniques.
The paper tackles verifying properties of array programs with symbolic size parameters by introducing a technique that constructs two program versions and infers difference invariants between them, enabling inductive proofs without complex loop invariants. The method outperforms the 2021 SV-COMP winner in the Arrays sub-category, as demonstrated by a prototype tool called diffy.
We present a novel verification technique to prove interesting properties of a class of array programs with a symbolic parameter N denoting the size of arrays. The technique relies on constructing two slightly different versions of the same program. It infers difference relations between the corresponding variables at key control points of the joint control-flow graph of the two program versions. The desired post-condition is then proved by inducting on the program parameter $N$, wherein the difference invariants are crucially used in the inductive step. This contrasts with classical techniques that rely on finding potentially complex loop invaraints for each loop in the program. Our synergistic combination of inductive reasoning and finding simple difference invariants helps prove properties of programs that cannot be proved even by the winner of Arrays sub-category from SV-COMP 2021. We have implemented a prototype tool called diffy to demonstrate these ideas. We present results comparing the performance of diffy with that of state-of-the-art tools.