Path invariants
- 10 June 2007
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 42 (6), 300-309
- https://doi.org/10.1145/1250734.1250769
Abstract
The success of software verification depends on the ability to find a suitable abstraction of a program automatically. We propose a method for automated abstraction refinement which overcomes some limitations of current predicate discovery schemes. In current schemes, the cause of a false alarm is identified as an infeasible error path, and the abstraction is refined in order to remove that path. By contrast, we view the cause of a false alarm -the spurious counterexample- as a full-fledged program, namely, a fragment of the original program whose control-flow graph may contain loops and represent unbounded computations. There are two advantages to using such path programs as counterexamples for abstraction refinement. First, we can bring the whole machinery of program analysis to bear on path programs, which are typically small compared to the original program. Specifically, we use constraint-based invariant generation to automatically infer invariants of path programs-so-called path invariants. Second, we use path invariants for abstraction refinement in order to remove not one infeasibility at a time, but at once all (possibly infinitely many) infeasible error computations that are represented by a path program. Unlike previous predicate discovery schemes, our method handles loops without unrolling them; it infers abstractions that involve universal quantification and naturally incorporates disjunctive reasoningKeywords
This publication has 31 references indexed in Scilit:
- The octagon abstract domainHigher-Order and Symbolic Computation, 2006
- Scalable Analysis of Linear Systems Using Mathematical ProgrammingLecture Notes in Computer Science, 2005
- Proving Program Invariance and Termination by Parametric Abstraction, Lagrangian Relaxation and Semidefinite ProgrammingLecture Notes in Computer Science, 2005
- What’s Decidable About Arrays?Lecture Notes in Computer Science, 2005
- Modular verification of software components in CIEEE Transactions on Software Engineering, 2004
- Parametric shape analysis via 3-valued logicACM Transactions on Programming Languages and Systems, 2002
- Symbolic execution and program testingCommunications of the ACM, 1976
- Affine relationships among variables of a programActa Informatica, 1976
- An axiomatic basis for computer programmingCommunications of the ACM, 1969
- Assigning meanings to programsProceedings of Symposia in Applied Mathematics, 1967