  In deductive verification and software model checking, dealing with certain
specification language constructs can be problematic when the back-end solver
is not sufficiently powerful or lacks the required theories. One way to deal
with this is to transform, for verification purposes, the program to an
equivalent one not using the problematic constructs, and to reason about its
correctness instead. In this paper, we propose instrumentation as a unifying
verification paradigm that subsumes various existing ad-hoc approaches, has a
clear formal correctness criterion, can be applied automatically, and can
transfer back witnesses and counterexamples. We illustrate our approach on the
automated verification of programs that involve quantification and aggregation
operations over arrays, such as the maximum value or sum of the elements in a
given segment of the array, which are known to be difficult to reason about
automatically. We formalise array aggregation operations as monoid
homomorphisms. We implement our approach in the MonoCera tool, which is
tailored to the verification of programs with aggregation, and evaluate it on
example programs, including SV-COMP programs.
