Constraint-based Linear Relations Analysis

Sriram Sankaranarayanan, Henny Sipma, Zohar Manna.

Linear-relations analysis of transition systems discovers linear invariant relationships among the variables of the system. These relationships help establish important safety and liveness properties. Efficient techniques for the analysis of systems using polyhedra have been explored, leading to the development of successful tools like HyTech. However, existing techniques rely on the use of approximations such as widening and extrapolation in order to ensure termination. In an earlier paper, we demonstrated the use of Farkas Lemma to provide a translation from the linear-relations analysis problem into a system of constraints on the unknown coefficients of a candidate invariant. However, since the constraints in question are non-linear, a naive application of the method does not scale. In this paper, we show that by some efficient simplifications and approximations to the quantifier elimination procedure, not only does the method scale to higher dimensions, but also enjoys performance advantages for some larger examples.

In Proc. 11th Static Analysis Symposium (SAS'2004), LNCS 3148, pp 53-68, Springer Verlag, 2004.

Postscript, PDF. © 2004, Springer Verlag.


© Henny Sipma / sipma@cs.stanford.edu
Last modified: Nov 19 14:40:50 PDT 2004