Verifying a binary search

May 5, 2010 Comments off

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(const LinEntry* array table, size_t nElems, uint16_t key)
 post(result <= nElems);

Read more…

What are you trying to prove?

April 27, 2010 9 comments

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!

April 7, 2010 21 comments

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…

Verifying loops: proving termination

March 31, 2010 6 comments

If you’ve stuck with me so far in this mini-series on verifying loops, give yourself a pat on the back  before reading further. When it comes to formal verification of single-threaded software, loops are the most challenging constructs to verify. Read more…

Verifying loops – part 2

March 29, 2010 2 comments

Last time I showed how it was possible to analyse a loop-free and recursion-free program or function to determine its semantics (i.e. its weakest precondition and its postcondition), but that this didn’t work when we have loops. To make it possible to analyze loops thoroughly, Read more…

Verifying loops in C and C++ (intro)

March 22, 2010 1 comment

When it comes to formal verification of single-threaded programs, one of the hardest constructs to verify is the humble loop. If a function contains no loops and no function calls, then a static analyser can trace through the function, looking for constructs (such as indexing an array, or dividing one number by another) that have an implied precondition Read more…

Making sure variables are initialized

March 18, 2010 5 comments

One source of program bugs is use of variables before they have been initialized. In C/C++ all static variables get zero-initialized if they have no specified initialization, so it is only local variables we need to worry about. Bugs caused by use of uninitialized local variables can be particularly nasty, because the value of such a variable depends on whatever previously occupied the same stack location. Read more…