ON INVARIANT CHECKING

ZHANG Zhihai , KAPUR Deepak

Journal of Systems Science & Complexity ›› 2013, Vol. 26 ›› Issue (3) : 470-482.

PDF(247 KB)
PDF(247 KB)
Journal of Systems Science & Complexity ›› 2013, Vol. 26 ›› Issue (3) : 470-482. DOI: 10.1007/s11424-013-1296-1
article

ON INVARIANT CHECKING

  • ZHANG Zhihai1 , KAPUR Deepak2
Author information +
History +

Abstract

Checking whether a given formula is an invariant at a given program location (especially,inside a loop) can be quite nontrivial even for simple loop programs, given that it is in general an undecidable property. This is especially the case if the given formula is not an inductive loop invariant, as most automated techniques can only check or generate inductive loop invariants. In this paper, conditions are identified on simple loops and formulas when this check can be performed automatically. A general theorem is proved which gives a necessary and sufficient condition for a formula to be an invariant under certain restrictions on a loop. As a byproduct of this analysis, a new kind of loop invariant inside the loop body, called inside-loop invariant, is proposed. Such an invariant is more general than an inductive loop invariant typically used in the Floyd-Hoare axiomatic approach to program verification. The use of such invariants for program debugging is explored; it is shown that such invariants can be more useful than traditional inductive loop invariants especially when one is interested in checking extreme/side conditions such as underflow, accessing array/collection data structures outside the range, divide by zero, etc.

Cite this article

Download Citations
ZHANG Zhihai , KAPUR Deepak. ON INVARIANT CHECKING. Journal of Systems Science and Complexity, 2013, 26(3): 470-482 https://doi.org/10.1007/s11424-013-1296-1

Funding

The first author is supported by NSFC-90718041, NKBRPC-2005C B321902, and China Scholarship Council in China, and the second author is supported by the National Science Foundation award CCF–0729097.

PDF(247 KB)

161

Accesses

0

Citation

Detail

Sections
Recommended

/