Goanna Static Analysis by Red Lizard Software

At Red Lizard Software, we care about providing the most accurate static analysis for your cpu cycle. Therefore, we spend a lot of our time thinking about the nature of false positives (when Goanna gives a warning about completely reasonable code) and how to avoid them.

One class of false positives we have noticed recently happens when you want to warn about an action that must occur on all execution paths. These properties might be expressed as “you must initialise all variables on all paths before accessing their values” for some definitions of initialise and access. A problem with these kinds of requirements appears when the initialisation of a variable is performed within a looping construct, and then access after the loop. This loop is usually designed to execute at least once (thus initialising the variable at least once) and so the programmer knows that the access after the loop is perfectly valid. Goanna has historically not been very good at identifying this false positive and will often warn anyway because there is an execution path that might not initialise the variable, the path where the condition evaluates to false. This is probably a case where the programmer should have used a do .. while loop to convey the desired semantics of the loop, but given that do .. while loops are not as popular as for loops, Goanna needs to be able to deal with this scenario.

There are two steps to making Goanna more intelligent about loops. The first step is identifying when a for or while loop should be represented as a do .. while, and the second is presenting this information to Goannas internal analysis engine.

In order to determine that a loop will execute at least once, it may be simpler to ask the inverse question. When will a loop not execute at least once? A sub question of this is when will we not know if a loop can execute at least once? This is actually much easier to answer because it can be boiled down to a structural condition. If the condition of the loop contains global variable references or function calls, then it is almost impossible to determine if a loop will execute only once. So what is left? Loops that contain only literals and local variable references. Parameters are a trickier issue since each call to the function is potentially different. With additional interprocedural analysis it may be possible to determine the boundaries of function parameters accurately but at present these loops can be ignored as well. The only thing left to do is to determine the state of the variables used in the loop condition right before it is evaluated and then evaluate the condition.

The analysis engine of Goanna works upon what is known as a control flow graph. This graph is created by looking at the source tree and determining which operations happen in which order. So the best way to present this modification of a for loop is through modifications to the control flow graph. Specifically we would like to create a copy of the control flow graph of the loops condition and wire up the rest of the graph such that there is a direct path through this path to the body of the for loop. The graph must also go into this new condition instead of into the old condition in order for the modification to be complete.

After implementing this change we have noticed that there is a small drop in the number of certain types of false positives, specifically in the SPC-uninit-var-some, with no impact on the runtime performance of the Goanna analysis engine. We hope to roll this improvement into the next release of the Goanna static analysis product line.

Most users will use Goanna integrated into their development environment, either Visual Studio or Eclipse. However, we also have a command line version called Goanna Central. Since I am mostly working on the analysis engine this is the version I use most often. And part of this entails to find open source projects and run Goanna over it. So, if you have an open source project, we might be watching you :)

Most open source projects provide configure scripts to generate makefiles. If that is the case using Goanna is a matter of configuring it with Goanna. There are two executables, goannacc and goannac++, that behave like gcc and g++. Configuring then just means to execute:

goanna@KITTYHAWK:~$ ./configure CC=goannacc CXX=goannac++

After this you can make you project as you are used to, with the difference that you will get feedback from Goanna.

Sometimes open source project do not provide a configure script. Last week I got my hands on an open source model checker - it is always some guilty pleasure to model check a model checker - and this project only included a makefile. Once all the necessary libraries were installed - the once provided were incompatible with my machine - such that the project could be build with g++, all that remained was to edit the makefile. It is always exciting to edit a file that says right at the top: Automatically-generated file. Do not edit!. To use Goanna required to find all occurrences of, in this case, g++ and replace them with goannac++. And then to make the project.

The output looks like this:

Building file: ../src/Ned.cpp
Invoking: GCC C++ Compiler
goannac++ -DDEBUG -I../include -O0 -g3 -Wall -c -fmessage-length=0 -Wextra -MMD -MP -MF”src/Ned.d”
Goanna - analyzing file ../src/Ned.cpp
Number of functions: 3
../src/Ned.cpp:28: warning: Goanna[COP-assign-op] Missing assignment operator for class `Ned’ which uses dynamic memory allocation
../src/Ned.cpp:28: warning: Goanna[COP-copy-ctor] Missing copy constructor for class `Ned’ which uses dynamic memory allocation
Total runtime : 6.65 seconds

That was about all it took. BTW: Kittyhawk is the name of my machine, and it is aptly named.

It is out! We just released a major upgrade to Goanna Studio version 2.0. There has been a lot of work going into the new version and some of the new key features include:

• Full (whole program) interprocedural analysis to track effects across functions and files
• Incremental analysis to minimize time for reanalyzing files/projects
• Around 100 classes of checks, up almost 70% compared to the previous release
• Much improved precision and elimination of some existing false positives
• Improved Path Simulator to display error traces
• New project reporting mechanism and export facilities

For existing customers:

• We are also happy to announce that all existing customers have the possibility to upgrade to 2.0 free of charge!
• If you were a trial user in the past and need a trial extension visit: http://redlizards.com/trial-extension

Overall, the new version is another leap forward and enables to detect more and deeper critical issues early in the development cycle.

We are happy to announce a new release of our Goanna static analysis solution. After a previous release for Visual Studio 2010 we are now bringing new technology with new benefits to all our products:

Some of the advances include:

• up to 300% speed improvement through improved core analysis engine
• even less false positives due to improved check accuracy
• updated output format to easier identify critical issues
• 32-/64-bit cross-compilation support in Visual Studio
• support of Visual Studio property sheets
• initial support of new C++0x standard (”auto” and other features)

If you like to test the new features and require a 30 day Trial Extension for your current Goanna version please complete this trial extension request form.

Another new Goanna feature is operational feedback. While Goanna is analyzing your source files, you can check to see exactly what is being done. Just select the new Goanna Statistics button from the Tool menu:

The next release of Goanna determines facts about your program from assertions. We can use this information to determine the bounds of variables and the nullity of pointers.

Goanna’s interval analysis can now catch this division by zero:

#include <assert.h>

int bad_div_of_8(int x)
{
  assert(x == 4);
  x -= 3;
  x--;
  return 8 / x;
}

Goanna for Visual Studio is out of beta. Version 1.0 is available for download now, for both Visual Studio 2008 and 2005. You can also watch a short introductory video on using Goanna here.

The forth beta release of Goanna for Visual Studio 2008 is now available. Get it here!

This release comes with some minor bug fixes, and a significant speed increase for C++ projects with large header files (like the Boost libraries). Hopefully we are nearing the end of our Beta period.

We have made Beta 3 of Goanna for Visual Studio 2008 available. There are many bug fixes and user interface enhancements, including:

• Right-click support for Solution Folders.
• A Goanna icon on the toolbar.
• Control-flow ordering of short-circuit operators (&& and ||).
• Solution-wide settings panel.
• Several common false positives have been eliminated.
• Auto-detection of less common MSVC macros in the build process.

You can download it now!

To make Goanna fast enough for the desktop, we have to keep our control flow models simple. In the past we combined short-circuit operators in our models into single events, which means we missed some bugs. But some new tricks mean we can have finer-grained control flow models.
(more…)