A Program Instrumentation Framework for Automatic Verification

Jesper Amilon, Zafer Esen, Dilian Gurov, Christian Lidström, Philipp Rümmer, Marten Voorberg · 2024

Read A Program Instrumentation Framework for Automatic Verification by Jesper Amilon, Zafer Esen, Dilian Gurov, Christian Lidström, Philipp Rümmer, Marten Voorberg (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06431.txt.

Introduction

Jesper Amilon and co-authors present a unifying frame for preparing programs so that automated checkers can verify them, in a 2024 paper. Some language features stump the solvers behind those checkers. A common fix is to rewrite the program into an equal form without the hard features. Past fixes were one-off tricks with no shared rules.

Their frame, program instrumentation, sets a clear test for when a rewrite is sound. It can run on its own, with no hand tuning. Proof hints and counterexamples can move back to the original program. They show the frame on sums and maxima over array ranges, which are known pain points. The work gives verification tools a firmer shared base.

Catalog record

CREATORJesper Amilon, Zafer Esen, Dilian Gurov, Christian Lidström, Philipp Rümmer, Marten Voorberg
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE7 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-06431

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Program Instrumentation Framework for Automatic Verification
Jesper Amilon, Zafer Esen, Dilian Gurov, Christian Lidström, Philipp Rümmer, Marten Voorberg

Abstract
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 this equivalent program instead. In this article, we propose program 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 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.



1
Introduction

Program specifications are often written in expressive, high-level languages: for instance, in temporal logic
[
DBLP:reference/mc/2018
]
, in first-order logic with quantifiers
[
DBLP:books/daglib/0022394
]
, in separation logic
[
DBLP:conf/lics/Reynolds02
]
, or in specification languages that provide extended quantifiers for computing the sum or maximum value of array elements
[
DBLP:books/daglib/p/LeavensBR99
,
acsl
]
. Specifications commonly also use a rich set of theories; for instance, specifications could be written using full Peano arithmetic, as opposed to bit-vectors or linear arithmetic used in the program. Rich specification languages make it possible to express intended program behaviour in a succinct form, and as a result reduce the likelihood of mistakes being introduced in specifications.

There is a gap, however, between the languages used in specifications and the input languages of automatic verification tools. Software model checkers, in particular, usually require specifications to be expressed using program assertions and Boolean program expressions, and do not directly support any of the more sophisticated language features mentioned. In fact, rich specification languages are challenging to handle in automatic verification, since satisfiability checks can become undecidable (i.e., it is no longer decidable whether assertion failures can occur on a program path), and techniques for inferring program invariants usually focus on simple specifications only.

To bridge this gap, it is common practice to
encode
high-level specifications in the low-level assertion languages understood by the tools. For instance, temporal properties can be translated to Büchi automata, and added to programs using ghost variables and assertions
[
DBLP:reference/mc/2018
]
; quantified properties can be replaced with non-determinism, ghost variables, or loops
[
DBLP:conf/sas/BjornerMR13
,
DBLP:conf/sas/MonniauxG16
]
; sets used to specify the absence of data-races can be represented using non-deterministically initialized variables
[
cell2010
]
. By adding ghost variables and bespoke ghost code to programs
[
DBLP:journals/fmsd/FilliatreGP16
]
, many specifications can be made effectively checkable.

The translation of specifications to assertions or ghost code is today largely designed, or even carried out, by hand. This is an error-prone process, and for complex specifications and programs it is hard to ensure that the low-level encoding of a specification faithfully models the original high-level properties to be checked. Mistakes have been found even in industrial, very carefully developed specifications
[
DBLP:conf/atva/PriyaZSVBG21
]
,
and can result in assertions that are vacuously satisfied by any program. Naturally, the manual translation of specifications also tends to be an ad-hoc process that does not easily generalise to other specifications.

This article proposes the first general framework to automate the translation of rich program specifications to simpler program assertions, using a process called
instrumentation.
Our approach models the semantics of specific complex operations using program-independent
instrumentation operators,
consisting of (manually designed) rewriting rules that define how the evaluation of the operator can be achieved using simpler program statements and ghost variables. The instrumentation approach is flexible enough to cover a wide range of different operators, including operators that are best handled by weaving their evaluation into the program to be analysed. While instrumentation operators are manually written, their application to programs can be performed in a fully automatic way by means of a search procedure. The soundness of an instrumentation operator can be shown formally, once and for all, by providing an
instrumentation invariant
that ensures that the operator can never be used to show correctness of an incorrect program.

Comparison to CAV paper

This article extends our previous work
[
amilon-et-al-cav23
]
by including new instrumentation operators, now covering the full set of extended quantifiers in the specification language ACSL
[
acsl
]
. Instrumentation operators for extended quantifiers are presented more systematically using monoid homomorphisms.
A more comprehensive correctness result is included, where
completeness
in the typical sense is shown for certain classes of programs. Several existing sections of the CAV paper have been extended by adding more thorough explanations or discussions.

Figure 1
:
Example program calculating the maximum voltage in a battery pack consisting of an array of batteries

⬇

1

typedef

struct

{

2

int

batt_volt
[10];

3

int

max_voltage
;

//Maximum

voltage

value

in

pack

4

}

BATTERY_PACK
;

5

6

extern

BATTERY_PACK

nondet_BATTERY_PACK
();

7

BATTERY_PACK

bpack
;

8

9

void

calc_pack_max
()

{

10

bpack
.
max_voltage

=

bpack
.
batt_volt
[0];

11

for

(
int

i

=

1;

i

<

10;

i
++)

12

if

(
bpack
.
batt_volt
[
i
]

>

bpack
.
max_voltage
)

13

bpack
.
max_voltage

=

bpack
.
batt_volt
[
i
];

14

}

15

void

main
()

{

16

bpack

=

nondet_BATTERY_PACK
();

//non-det

initialization

17

calc_pack_max
();

18

assert
(
bpack
.
max_voltage

==

\
max
(
bpack
.
batt_volt
,

0,

10));

19

}

1.1
Motivating Examples

We illustrate our approach on two simple examples.

Array Aggregation

Consider first the program shown in
Figure 1
, which operates on a battery pack powering the electric engine of a vehicle. Although this particular implementation is written by us, it is conceptually close to (significantly more complicated) code we encountered in collaborations with automotive companies. The battery pack is represented as a C struct, consisting of an array of batteries (representing the measured voltage at each battery) and a field for the maximum voltage value among the batteries. In the program, the
calc_pack_max
function calculates the maximum value by looping through the array, and in the main function, correctness of
calc_pack_max
is asserted by relying on the
\
max
operator. Intuitively,
\
max
(
a
,

l
,

u
)
extracts the maximum value of the array
a
in the interval [
l
,
u
).

\,\bm{\Omega}_{\mathit{max}}\textbf{

Read the complete text