## Verifying absence of integer overflow

One class of errors we need to guard against when writing critical software is arithmetic overflow. Before I go into detail, I invite you to consider the following program and decide what it prints:

#include<stdio.h>intmain(intargc,char*argv[]) {unsigned intx = 42;longy = -10; printf("%s\n", (x > y ? "Hello, normal world!" : "Hello, strange world!"));return0; }

## Specification with Ghost Functions

In my previous post I showed that the C expression sublanguage extended with quantified expressions (**forall **and **exists**) is insufficient to allow some specifications to be expressed. I presented this function (annotated with an incomplete specification) to average an array of data:

int16_t average(constint16_t *arrayreadings, size_t numReadings)pre(readings.lwb == 0; readings.lim == numReadings)pre(numReadings != 0)post(result== ?/* sum of elements of readings *//numReadings) {intsum = 0; size_t i;for(i = 0; i < numReadings; ++i)keep(i <= numReadings)keep(sum == ?/* sum of first i elements of readings */)decrease(numReadings - i) { sum += readings[i]; }return(int16_t)(sum/numReadings); }

## Expressing the Inexpressible

When writing preconditions, postconditions and other specifications for C programs, sometimes we need to write expressions that can’t be expressed in plain C. That’s why formal verification systems based on annotated programming languages almost always augment the expression sublanguage with **forall **and **exists **expressions. In previous posts, I’ve introduced ArC’s implementations of these. For example, the following expression yields **true **if all elements of the array *arr *are between 0 and 100 inclusive:

forallindinarr.indices :- arr[ind] >= 0 && arr[ind] <= 100

Here, *ind *is declared as a bound variable that ranges over the values in the expression that follows the keyword **in**, which in this case is all the indices into *arr*. Read more…

## Verifying a binary search, part 2

In my last entry I showed how to use a correct-by-construction approach to develop a binary search function. We got as far as specifying the function and the loop, but we left the loop body undefined. The function declaration looked like this: Read more…

## Verifying a binary search

In the last post, I covered some different levels of formal verification that you may be interested in, and showed how to add minimum annotation to the linearization example to allow ArC to prove predictable execution. The example provided a prototype for the binary search function it called, to which we added a minimal postcondition, so that it looked like this:

size_t bSearch(constLinEntry*arraytable, size_t nElems, uint16_t key)post(result<= nElems);

## What are you trying to prove?

If you’re thinking of using formal verification to increase the quality and reliability of your software, one of the first decisions you need to make is what you want to prove. Roughly speaking, you have three levels to choose from: Read more…

## Danger – unsigned types used here!

By way of a change from the last two posts on formal verification, this time I’m going to talk about using unsigned types in C/C++. Modern programming languages such as C# and Java don’t provide unsigned types, with good reason (actually, C# does have unsigned types, but only for the purpose of interfacing to COM objects written in other languages, and they are not used in the .NET Framework API).

To illustrate the dangers of using unsigned types, I invite you to consider this example Read more…