A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World (CACM)

It's too bad that we have tried to write a large, reliable and secure system in C / C++ using mere mortals as programmers, but given that reality there will be the occasional dumb bug. Mocking that bug only helps if it encourages a positive change in practices; I'm not sure what what the X developers could realistically have done differently. "Don't typo" is just silly and "formally audit all security code" has proven just too expensive. Our current focus on moving appropriate X server code into the kernel should help, as the X server can then mostly run without dangerous root privileges.

It's laudable to find bugs before the software product is put together. It's just as laudable to do your darndest to break it--cause your system and its parts to fail--long before a customer ever sees the product; this requires automated test systems.

I know Gürkan Sengün used to run rats over the Debian archive as part of lina, which is now discontinued unfortunately:

http://asdfasdf.debian.net/~tar/lina/

Which is true. Having worked in the software industry for many years, _nothing_ works like it does in the lab. The work in the lab ends up being 10% of the effort to make a reliable, maintainable product.

I'll also note that the solutions described in the paper describe a project that is a hack on top of a hack - in the bad sense. I can only imagine that their software is fragile and hard to maintain, likely needing many updates just to move forward with natural changes in language and library versions.

Finally, more power to them - software architecture and development is a complicated process, and building tools to simplify and validate that process are what raise the bar in software and system quality.

I did not find any, except old (and unmaintained?) simple ones.

As described in the article, they had sent us a tool that we trivially inserted into our build process (about 1 million lines of C++, normally compiled with GCC); as our build was based on GNU Makefiles it all worked fine, with the exception of a couple of compiler failures where we exploited some very dark corners of C++ and relied on GCC's specific behavior.

Before this, we had, gone through our bug database and created a file (coverity.cc) with a whole bunch of code snippets for bugs that we would have really liked to have been able to find automatically with such a tool. In our codebase, most of the low-hanging fruit had already been picked up by using -Wall and -Werror (command line flags to print all warnings and turn them into errors, so a warning would break the build), as well as idiomatic C++ usage that rarely had us dealing directly with memory management or paired operations (eg, lock() and unlock()). We also compiled with multiple versions of G++ on multiple architectures, which also uncovered a lot of potential bugs that were fixed as a matter of course. Finally, the code was run from end to end hundreds of times as part of testing each change, with extremely detailed metrics that allowed us to catch most problems early on before integration.

Their tool performed as advertised: it found about 50 or so errors in the codebase, of which 80% were real bugs, and of which a few could have been quite serious. We were obviously quite impressed.

However, when we asked, it had failed to find any bugs at all in the coverity.cc file. This was not that surprising; they were very idiomatic C++ errors (use of invalidated iterators, reference-taken-before-append, subtle deadlocks etc) that require detailed knowledge of the exact semantics of STL containers, and would be very difficult to trace through the implementation of the various methods (ie, they would need a higher level tool to be written to be useful). But it meant for us that it would not be worth paying for the tool.

The reaction of the Coverity guys was quite amusing. Once the (senior) sales guy heard the attempt of the (junior) sales engineer to explain it away (there was no explanation possible; we wanted a feature that they didn't yet have), he saw that a sale was slipping through their fingers. He immediately (and quite brutally) shut up the junior guy, said something about those features being on their roadmap, and proceeded to hand us all copious schwag including a real bug encased in plastic. 2 minutes later they were outside.

Overall, I was pretty impressed with their product, even if it couldn't take away much of our pain. Their visit also showed the value in many of the techniques (compiler warnings, multiple compiler versions, multiple platforms) that we already used. But mostly, I felt quite sorry for their field sales teams, who really had nearly everything lined up against them. To do that kind of meeting over and over again must have taken real guts: I salute them.

re Toyota. Recent experience of their totally closed systems and implications, and wishing for open systems in my car:

1. Wanted to be able to take out and replace at demand the 2nd row seats in Landcruiser 200; they have inbuilt airbags. Toyota absolutely refused to talk to potential customer re this. All information hidden. Even an elementary block-diagram of the electric circuits was said to be hidden behind 3 passwords, customer not allowed.

What I supposedly learnt from other sources in the industry (no responsibility for this!!):
a. you can reportedly fool the microprocessor by plugging in a resistor variously said on the quiet to be either 2.2 or 3.3 ohms, to make the car computer think the seat is still connected.
b. be careful; you might think disconnecting the seats makes them safe. Wrong; there are capacitors in the seat which actually fire the airbag out through the stitching; so you can trigger the seat in isolation - expensive and dangerous.
c. On another Toyota, not the LC200, the recommended way around this is said to be to disconnect the battery, then sit with your foot on the brake pedal for 20 sec to discharge the capacitors in the seats.
d. There is another trap; if you do it wrong, particularly with any power on the system, the computer "sets a code" which disables the vehicle and only Toyota themselves, not even a dealer, can clear this. Would have to do it with the computer completely unpowered.

2. Came to terms with all of this, just thinking it was "do-able", needed vacuum brakes for a trailer. No usable vacuum on the LC200, found a commercial 12volt unit to generate vacuum, it needed to be connected to the braking system. Word came back indirectly it couldn't be done, as would alter the vehicle braking. A sensible discussion would have elicited from the vacuum braking unit people the volume displacement of their braking connection, and then sensible discussion with toyota looked at same factors in their braking algorithm, to decide if it could be done or not. Needless to say they wouldn't even talk to the customer, let alone discuss such issues. Oh for open systems.

Didn't buy the Toyota, bought Subaru diesel instead, after reading a very forthright, open and honest multi-page Subaru document on their adventures and unexpected challenges in developing their diesel engine. Felt much more like the tone of open-source stuff. Liked it.

Will we ever see access to embedded systems like this. Even the voting system in USA I think now has source code release.

At the risk of sounding smug, I have to contrast this with Free Software. I love its quality and transparency. It's developed, and judged, using metrics that favour quality, rather than commercial success.

BTW, in reference to the Toyota sub-thread, I own one of the affected Prius models. While the media has definitely sensationalised a pretty minor issue, it does make me uncomfortable having the braking, steering, and even acceleration systems under control of some (somebody else's) code somewhere. I'm pretty sure we're going the wrong direction with this trend...

Languages such as Java and Eiffel initialize all variables, so there are no uninitialized variable bugs. They also do automatic memory management, eliminiting a whole class of bugs.

Languages that do array bounds checking eliminate one of the most common bugs in C/C++ which is buffer overflows.

If you have to rely on external tools to find such errors, that is a big hint that you are using the wrong language.

When I was working on a hard realtime embedded system, that had 512kb of memory, 99% was written in C, and 1% was written in assembly. That was the right mix for the conditions. There is very little justification for writing most code running on a modern processor with many hundreds of megabytes of memory in C or C++.

When I was working on another system, with tens of millions of lines of code, I knew it was doomed, as it was written in C++. There is no reasonably way to make such a large system reliable and secure when facing dedicated attackers.