Automatic verification of pointer programs using monadic second-order logic
Jakob L. Jensen, Michael E. Jørgensen, Michael I. Schwartzbach et al. · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1997
We present a technique for automatic verification of pointer programs based on a decision procedure for the monadic second-order logic on finite strings.We are concerned with a while-fragment of Pascal, which includes recursively-defined pointer structures but excludes pointer arithmetic.We define a logic of stores with interesting basic predicates such as pointer equality, tests for nil pointers, and garbage cells, as well as reachability along pointers.We present a complete decision procedure for Hoare triples based on this logic over loop-free code. Combined with explicit loop invariants, the decision procedure allows us to answer surprisingly detailed questions about small but non-trivial programs. If a program fails to satisfy a certain property, then we can automatically supply an initial store that provides a counterexample.Our technique had been fully and efficiently implemented for linear linked lists, and it extends in principle to tree structures. The resulting system can be used to verify extensive properties of smaller pointer programs and could be particularly useful in a teaching environment.
Cited by 90 works. doi:10.1145/258915.258936
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Handbook of theoretical computer science
- Automata on Infinite Objects
- Efficient context-sensitive pointer analysis for C programs
- LCLint
- Efficient context-sensitive pointer analysis for C programs
- A safe approximate algorithm for interprocedural aliasing
- Interprocedural may-alias analysis for pointers
- Parallelizing programs with recursive data structures
- A safe approximate algorithm for interprocedural pointer aliasing