about this paper

presentation award abstract bibitem

downloads

slides paper
Jérôme Feret.
The Arithmetic-Geometric Progression Abstract Domain.

In Proceedings of the Sixth International Conference on Verification, Model Checking and Abstract Interpretation, VMCAI'05. Paris, France, January 17 -- 19, 2005, R.Cousot (Ed.), Lecture Notes in Computer Science 3385, , pp 42--58.
© Springer-Verlag, Berlin, Germany.

This paper received the "Best Paper Award" at VMCAI'05.

Abstract: We present a new numerical abstract domain. This domain automatically detects and proves bounds on the values of program variables. For that purpose, it relates variable values to a clock counter. More precisely, it bounds these values with the i-th iterate of the function [X |-> aX+b] applied on M, where i denotes the clock counter and the floating-point numbers a, b, and M are discovered by the analysis. Such properties are especially useful to analyze loops in which a variable is iteratively assigned with a barycentric mean of the values that were associated with the same variable at some previous iterations. Because of rounding errors, the computation of this barycenter may diverge when the loop is iterated forever. Our domain provides a bound that depends on the execution time of the program.

@INPROCEEDINGS{feret:VMCAI05,
  author    = {J{\'e}r{\^o}me Feret},
  title     = {The Arithmetic-Geometric Progression Abstract Domain},
  booktitle = {Verification, Model Checking and Abstract Interpretation (VMCAI'05)},
  series    = {LNCS},
  number    =  {3385},
  year      = {2005},
  pages     = { 42--58},
  publisher = {Springer-Verlag},
  note      = {© Springer-Verlag}
}