Inferring Alias Contracts in VCC using Separation Analysis
Alexander Galkin · 2011
The main goal of this work is to enable an interplay between two different verification tool chains: Frama-C, developed concomitantly by Commissariat a l’Energie Atomique et aux Energies Alternatives and Inria, and the Verified C Compiler, developed by Microsoft Research. Both tools have a long history and contain powerful algorithms for static verification of C source code. Both tools address the problem of aliasing, where the memory representation of two or more variables overlap (partial aliasing) or even is shared entirely (full aliasing). Aliasing is a common problem in software verification, for it produces side effects during code analysis by changing the values of variables that were not explicitly (re-)assigned. This problem is apparent in weakly typed languages like C and requires special attention. The byte-level memory model of VCC is tuned narrowly to the verification of concurrent programs, but this memory model turns out not to be optimal for alias detection and memory safety checks. Frama-C and its plug-in Jessie, on the other hand, implement deductive verification using a region-based memory representation, which is better suited for separation and alias analysis. We use the memory safety analysis of Jessie to derive missing pre-conditions in our VCC specification that enforce memory safety. To implement the necessary constraints in VCC, we have to confine alias detection to aliases of primitive data types and consider only full aliasing. These assumptions allows us to express the aliasing condition in the form of pointer inequality: two variables are not aliased, if their pointers are unequal. The main contribution of this thesis is Jessifier, a command-line utility for automated inference of missing alias contracts implemented in C#. This utility uses the outcome of the analysis performed by Jessie to detect possibly missing VCC annotations and attempts to generate them automatically (to infer). This inference is only possible if aliases are directly present in function invocations in the source code. If not, the respective verification conditions turn into tautologies and eliminated by Jessie from the analysis output.