  This paper presents a new method for automatically generating numerical
invariants for imperative programs. Given a program, our procedure computes a
binary input/output relation on program states which over-approximates the
behaviour of the program. It is compositional in the sense that it operates by
decomposing the program into parts, computing an abstract meaning of each part,
and then composing the meanings. Our method for approximating loop behaviour is
based on first approximating the meaning of the loop body, extracting
recurrence relations from that approximation, and then using the closed forms
to approximate the loop. Our experiments demonstrate that on verification
tasks, our method is competitive with leading invariant generation and
verification tools.
