Two Years (and Thousands of Bugs) of Static Analysis

I’ve been running static code analysis on four large code bases for over two years now. After the initial work of looking through all of the warnings and fixing the serious bugs I put the projects into code analysis maintenance mode. In this mode a build machine compiles each project several times a day with /analyze or clang and reports on any new warnings.

It turns out that static analysis finds a lot of new bugs (a few dozen a week), and I thought I’d summarize the sorts of bugs that it typically finds, along with some details of how we use static analysis effectively.

Format strings

The top type of bug that /analyze finds is format string errors – mismatches between printf-style format strings and the corresponding arguments. Sometimes there is a missing argument, sometimes there is an extra argument, and sometimes the arguments don’t match, such as printing a float, long or ‘long long’ with %d.

In some cases these errors are benign, due to luck of the ABI, but in many cases they cause incorrect values to be printed. In more serious cases – especially those involving ‘%s’ in format strings – they lead to code that will crash if it is ever executed. Part of what inspired me to start doing static code analysis was a series of annoying crashes caused by format string errors. Thanks to static analysis those format string crashes have now completely gone away, and hundreds of lines of diagnostics will now print correct values when we need them.

One common type of error is to pass a string object (std::string or the moral equivalent) to a varargs function. This is illegal, and no amount of “operator char*()” can automatically fix it. For some string classes this code may actually ‘work’ in VC++, but it is still illegal and it is 100% guaranteed to cause crashes when compiled with gcc or clang. You need to explicitly request conversion to a built-in type when passing objects to a printf style function.

Writing format strings that work for both 32-bit and 64-bit code requires attention to detail. Pointers need to be printed with %p rather than 0x%08x. The size_t and ptrdiff_t types are trickier because there is no standard C++ printf format specifier for these types. gcc supports C99’s %zu and VC++ supports %Iu. The practical options are to cast your size_t and ptrdiff_t variables to void* and print with %p, or cast them to ‘long long’ and print with %llu. We’ve standardized on the latter. I’ve talked to Microsoft about this and they might add %zu support for some future VS version. Progress can be slow, but if you don’t ask it’s even slower.

Yes, <inttypes.h> is supposed to solve this, but that is for C99, and VC++ doesn’t support C99, and the inttypes.h format strings are ugly anyway, so we don’t use them.

I’m sure that some readers are scoffing at our use of format strings – aren’t all the cool kids using iostreams or templates or some other type-safe system? Well, perhaps. But, format strings are quite expressive and convenient, so we are sticking with them.

There are two possible conclusions you can take from the hundreds (thousands!) of format string errors that I have seen over the last two years. One conclusion is that you should never ever use format strings because people are error prone and will frequently get them wrong. Another possible conclusion is that you should never use format strings without static analysis to check them. As long as our static analysis tools are looking out for us – as long as they are configured to have zero tolerance towards this class of bugs (and they are) then we can be confident that format string bugs will not last long.

It’s important to realize that most static analysis tools will only analyze format strings if you tell them which function parameters are printf style format strings. We have hundreds of format function and I went through and annotated most of them so that static analysis would help us out:

• For VC++’s /analyze I put _Printf_format_string_ in front of the format string argument
• For gcc/clang I put this after the function declaration: __attribute__ (( format( __printf__, fmtargnumber, firstvarargnumber )))

Obviously we wrap _Printf_format_string and __attribute__ in appropriate preprocessor magic so that each compiler only sees its own annotations. The gcc/clang annotations are needed to catch Linux/OSX only bugs, and because gcc/clang’s -Wformat detects a few additional format string issues.

Our build machines are configured so that the format string warnings are treated as fatal errors – they are reported continually until they are fixed.

Variable shadowing

The other most common warning is variable shadowing. It is amazingly common to have the same variable reused in multiple nested scopes. I have even seen triply nested for loops that all use i as their index variable. I did a careful analysis of variable shadowing on one project and found that, on that project, 98% of the instances of variable shadowing were legal and correct code – if somewhat confusing. Of course that means that the other 2% were buggy.

However, the actual incidence of bugs caused by variable shadowing is higher than 2%. That 2% bug rate was on code that had been tested and shipped for years. When you have just written or just checked-in code the percentage of variable shadowing that causes bugs is far higher. I don’t have any statistics, but I know that last week /analyze found three instances of variable shadowing that were outright bugs, and two instances that were performance problems.

The most common form of variable shadowing is nested for loops that use the same index variable – in our code bases i is the most commonly shadowed variable. It’s surprising how frequently these nested loops are actually correct, but they always make me nervous.

Here’s another (artificial) example of a common way that variable shadowing can cause bugs – in a larger function the error can be much harder to see:

bool IsFooEnabled()
{
    bool result = true;
    if (Bar())
    {
        bool result = Shazam();
    }
    return result;
}

Our code bases have thousands of instances of variable shadowing. Fixing them all would probably fix a few dozen bugs, but would also probably introduce new bugs. It feels like a poor tradeoff. Right now our build machines are configured to warn once about new instances of variable shadowing. Some day I might configure them to treat new instances of variable shadowing as errors – last week’s results suggest that that might be a good idea.

Slow warnings are less useful

Format string errors and variable shadowing should be easy and fast for the compiler to detect – gcc and clang detect them as part of their normal compilation. Unfortunately, for historical reasons the only way to get VC++ to complain about these bugs is to turn on /analyze. That causes huge build slowdowns, so therefore developers have /analyze turned off for regular builds and they only find out about these bugs when the /analyze build machines complain a few hours later. This is sub-optimal. VC++ really needs to add a /analyze:fast mode that just does the quick types of static analysis. We would immediately enable that in all of our projects and suddenly far fewer bugs would get checked in. I have suggested this to Microsoft and I hope they recognize the value.

Update, April 2, 2014

Microsoft updated the variable shadowing bug that I filed to say “A fix for this issue has been checked into the compiler sources. The fix should show up in the next major release of Visual C++.”

Most excellent.

Logic bugs

There are many forms of logic bugs that static analysis can detect. Precedence problems with a?b:c, illogical combinations of ‘|’ and ‘||’, and various other peculiarities. Here’s one example (note that kFlagValue is a constant):

if ( SomeFunction() || SomeOtherFunction()->GetFlags() | kFlagValue )

The code above is an expensive and misleading way to go “if ( true )”. Visual Studio gave a clear warning that described the problem well:

warning C6316: Incorrect operator:  tested expression is constant and non-zero.  Use bitwise-and to determine whether bits are set.

Here’s another example:

float angle = 20.0f + bOnFire ? 5.0f : 10.0f;

This example is sufficiently subtle that many people don’t see the bug. It looks like this function will store 25.0f or 30.0f. That’s what they want you to think. In fact it always stores 5.0f. Yay precedence! These are the warnings that /analyze gives for this code:

warning C6336: Arithmetic operator has precedence over question operator, use parentheses to clarify intent.
warning C6323: Use of arithmetic operator on Boolean type(s).

Logic bugs are frustrating because we often find them in code that has been play-tested and shipped. In these cases we often end up adding parentheses to make the existing undesirable behavior explicit because the risk of changing the behavior is too great.

Signed, unsigned, and tautologies

This code looks innocuous enough:

result = max( 0, a – b )

This code would have been fine if both a and b were signed – but one of them wasn’t, making this operation nonsensical. Clang didn’t initially find this bug because max() was a macro and clang normally avoids peering too deeply into macros, to avoid excessive false positives. However if you use ccache to optimize build times then clang sees preprocessed source and then this warning pops up. It’s nice when faster builds find more bugs.

We had quite a few places where we were checking to see if unsigned variables were less than zero – now we have fewer.

Buffer overruns

Some of the most serious bugs in C/C++ code are buffer overruns. One common error that can cause buffer overruns is passing the wrong size to a string function – sizeof when ARRAYSIZE is wanted, or just an incorrect number. I highly recommend creating and using template based intermediaries that can take a reference to an array and can infer the array size. The only array size that is guaranteed to be correct is one that the compiler infers.

(see Stop using strncpy already! for examples of this technique)

Using template array-reference overrides is great for new code, but it doesn’t help find code that was written incorrectly in the first place. To find bugs in this code you need to annotate functions that take a pointer and a count so that /analyze knows that the count refers to the number of bytes or element in the passed in buffer.

We have also had a fair number of bugs where code writes one or two elements beyond the end of an array, using a constant index. This is a 100% repro buffer overrun and some of these have existed for most of a decade.

Annotations

Here are some of the macros that we use to annotate our function declarations. The _PREFAST_ define is set when running /analyze. The empty macros for other cases are omitted below to save space.

#ifdef _PREFAST_
// Include the annotation header file.
#include <sal.h>

// Tag all printf/scanf style format strings with these
#define PRINTF_FORMAT_STRING _Printf_format_string_
#define SCANF_FORMAT_STRING _Scanf_format_string_
// Various macros for specifying the capacity of the buffer pointed
// to by a function parameter. Variations include in/out/inout,
// CAP (elements) versus BYTECAP (bytes), and null termination (_Z).
#define IN_Z _In_z_
#define IN_CAP(x) _In_count_(x)
#define IN_BYTECAP(x) _In_bytecount_(x)
#define OUT_CAP(x) _Out_cap_(x)
#define OUT_Z_CAP(x) _Out_z_cap_(x)
#define OUT_BYTECAP(x) _Out_bytecap_(x)
#define OUT_Z_BYTECAP(x) _Out_z_bytecap_(x)
#define INOUT_BYTECAP(x) _Inout_bytecap_(x)
#define INOUT_Z_CAP(x) _Inout_z_cap_(x)
#define INOUT_Z_BYTECAP(x) _Inout_z_bytecap_(x)
// These macros are use for annotating array reference parameters used
// in template functions
#if _MSC_VER >= 1700
#define IN_Z_ARRAY _Pre_z_
#define OUT_Z_ARRAY _Post_z_
#define INOUT_Z_ARRAY _Prepost_z_
#else
#define IN_Z_ARRAY _Deref_pre_z_
#define OUT_Z_ARRAY _Deref_post_z_
#define INOUT_Z_ARRAY _Deref_prepost_z_
#endif // _MSC_VER >= 1700
#else // _PREFAST_
…

Here are some examples of how we use these macros:

int V_sprintf_count( OUT_Z_CAP(maxLenInChars) char *pDest, int maxLenInChars, PRINTF_FORMAT_STRING const char *pFormat, … ) FMTFUNCTION( 3, 4 );

template <size_t maxLenInChars> int V_sprintf_safe( OUT_Z_ARRAY char (&pDest)[maxLenInChars], PRINTF_FORMAT_STRING const char *pFormat, … ) FMTFUNCTION( 2, 3 );

They are a bit unreadable when squeezed into a narrow blog post but the details are there. OUT_Z_CAP says that pDest is an output buffer that is maxLenInChars characters in length that will be null-terminated by the function. PRINTF_FORMAT_STRING says that pFormat is a format string, The FMTFUNCTION macro tells gcc the same thing, by parameter number. OUT_Z_ARRAY says that pDest is an output array that will be null-terminated by the function. We almost never use V_sprintf_count in new code because it requires more typing and because it is error prone.

With these annotations static analysis can give far more and more accurate warnings. Recommended.

Policy

Using static analysis is rarely as simple as just running it. Microsoft’s /analyze is painfully slow so it is impractical for every developer to run it on their local machine. Instead we have build machines that do this. These build machines do full rebuilds a few times a day and they report on new warnings.

Not all warnings are created equal. Some warnings are so unreliable or irrelevant that we completely disable them. Some, like the format string warnings, are 100% reliable and always worth fixing. Our scripts have a zero-tolerance policy towards these warnings and a few others that we trust. Here is our Python dictionary of warnings that we treat as fatal, together with brief descriptions:

alwaysFatalWarnings = {
    4789 : “Destination of memory copy is too small”,
    6053 : “Call to function may not zero-terminate string”,
    6057 : “Buffer overrun due to number of characters/bytes mismatch”,
    6059 : “Incorrect length parameter”,
    6063 : “Missing string argument”,
    6064 : “Missing integer argument”,
    6066 : “Non-pointer passed as parameter when pointer is required”,
    6067 : “Parameter in call must be the address of the string”,
    6066 : “Non-pointer passed as parameter when pointer is required”,
    6209 : “Using sizeof when a character count might be needed.”,
    6269 : “Possible incorrect order of operations: dereference ignored”,
    6270 : “Missing float argument to varargs function”,
    6271 : “Extra argument: parameter not used by the format string”,
    6272 : “Non-float passed as argument <number> when float is required”,
    6273 : “Non-integer passed as a parameter when integer is required”,
    6278 : “array new [] paired with scalar delete”,
    6281 : “relational/bitwise operator precedence problem”,
    6282 : “Incorrect operator: assignment of constant in Boolean context”,
    6283 : “array new [] paired with scalar delete”,
    6284 : “Object passed as a parameter when string is required”,
    6290 : “Bitwise operation on logical result: precedence error”,
    6302 : “Format string mismatch: char* when wchar_t* needed”,
    6303 : “Format string mismatch:  wchar_t* when char* needed”,
    6306 : “Incorrect call to ‘fprintf*’: consider using ‘vfprintf*'”,
    6328 : “Wrong parameter type passed”,
    6334 : “Sizeof operator applied to an expression with an operator”,
    6336 : “Arithmetic/question operator precedence problem”,
    6522 : “Invalid size specification: expression must be of integral type”,
    6523 : “Invalid size specification: parameter ‘size’ not found”,
    }

Unfortunately the majority of the other warnings are unreliable. /analyze has improved a lot from VS 2010 to VS 2012 (I strongly recommend using VS 2012 for /analyze), but it still has room to improve, and static analysis always has to maintain a balancing act between having too many false positives and missing possible problems. The things that /analyze warns about range from psychically brilliant to provably impossible. Therefore our build machines are configured to report most warnings once, and then fold them into the background noise. Since I’ve had the most practice at looking at /analyze warnings and understanding their quirks I take a quick look at most of the new warnings. If I can quickly identify the warning as being spurious then I can save other developers from wasting time trying to see what the problem is. And if the warning identifies a real bug I can make sure it gets fixed.

(see VC++ /analyze Bug Finder Bug Fixed to get the crash-fix to VS 2012)

(see /analyze the Ugly for discussions of some spurious warnings)

Using VS 2012 for /analyze

Even if you are still building your code with VS 2010 you can still use VS 2012 for /analyze. This is important because VS 2012 finds more bugs, has fewer false positives, and has 64-bit support. Running /analyze using VS 2012 is relatively easy.

In addition to giving more accurate results, VS 2012 gives better warnings for format string mismatches. If I try to print a std::string using ‘%s’ then VS 2010 gives this warning:

warning C6284: Object passed as parameter ‘2’ when string is required in call to ‘printf’

The warning is accurate and helpful, but the VS 2012 warning is far better:

warning C6284: Object passed as _Param_(2) when a string is required in call to ‘printf’ Actual type: ‘const class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >’.

It’s hard to overstate the value of knowing not just what was expected but also what was actually passed.

You can load VS 2010 projects into VS 2012 – the profile file format is unchanged. In Properties-> Configuration Properties-> General you will find Platform Toolset that will let you specify which compiler toolset you want to build with. To the right you can see the huge number of options that I have from within VS 2013 Preview (not yet ready for prime-time).

When you are ready to automate this transformation it’s as simple as inserting this tag in the .vcxproj file XML:

<PlatformToolset>v110</PlatformToolset>

There may be a v100 tag in there already – remove that and replace it with v110 (VS 2012). Then set up your environment with:

“%VS110COMNTOOLS%..\..\VC\vcvarsall.bat”

Then invoke a command-line build as usual. You’ll find a bunch of new warnings, and probably some incompatibilities that you’ll have to work through, but at least the project file aspect is easy.

We also do a few tricks with the Executable Directories path (Properties-> Configuration Properties-> VC++ Directories) to redirect link.exe, lib.exe, and mt.exe to a nop.exe so that we avoid the link errors that we might otherwise hit – we are only concerned with compile warnings.

You should also be sure to update VS 2012 with Update 3 (released June 26, 2013) to make sure you get the fix to the annotation parser crash.

Summary

It is the nature of programmers to make mistakes. We write incorrect code all the time, and when reading code we see what we expect, regardless of what is actually there. Bugs slip into code for the same reason that speling errors slip into writing.

Static analysis will find bugs in your code if you give it a chance. Run it regularly, annotate your printf functions and buffer handling functions, generate reports on any new warnings, keep reporting on warnings that are reliable and worth fixing, and use coding techniques that naturally avoid dangerous patterns. Static analysis won’t find all of the bugs that you write – just like a spell checker misses mistakes – but in both cases if you don’t make use of the error-finding technologies that are available then you may end up looking foollish.

The reddit discussion of this post can be found here.

There’s a good discussion of how this post applies to the D language here.