Compositional recurrence analysis

Abstract

This paper presents a new method for automatically generating numerical invariants for imperative programs. The procedure computes a transition formula which overapproximates the behaviour of a given input program. It is compositional in the sense that it operates by decomposing the program into parts, computing a transition formula for each part, and then composing them. Transition formulas for loops are computed by extracting recurrence relations from a transition formula for the loop body and then computing their closed forms. Experimentation demonstrates that this method is competitive with leading verification techniques based on abstraction refinement.