Bounds Checking for Open Source Code?

roarl asks: "Is anyone working on an Open Source bounds checking system? (A system that checks a program at runtime for array out of bounds access, reading uninitialized memory, memory leaks and so on). I've been using BoundsChecker for some time and believe me, there are situations where you know you are going to spend hours debugging unless you let BoundsChecker sort it out for you. But it annoys me that I have to transfer (and sometimes port) the buggy program to Windows each time. I'd much rather stay in Linux. Insure works on Linux. I haven't tried Insure for some time, but last time I tried I wasn't especially impressed. Purify seems still not to support Linux, but on other Unix platforms it works great. The problem with all of these products is that they are so da*n expensive. So it makes me wonder, are all Open Source programmers doing without them? If so, what can we expect of the quality of Open Source developed programs? If not, is there a free alternative?"

Comments

A simple answer to a simple question...

[RevAaron]

Need bounds checking for Linux? May I suggest the CMU Common Lisp interpreter and compiler (to machine code) or perhaps Smalltalk. :)

Electric Fence

[Urban Garlic]

The ever-resourceful Bruce Perens wrote a cool gizmo called "electric fence", which I have used on many occasions. It doesn't actually do bounds checking as such, what it does is provide a replacement "malloc" that allocates unwritable pages either above or below every memory allocation. Your application will then segfault when it misbehaves, and you can then use conventional debugging tools to track down the

It's very "non-invasive" -- all you have to do to use it is link against it, and maybe set a few environment variables.

Lots of almost-complete solutions

[devphil]

Of the top of my head, and with the help of my bookmarks:

• Bell Labs had a "libsafe" that provided versions of malloc et al: http://www.lucent.com/press/0400/000420.bla.html Unfortunately the link given in that press release no longer works.
• A quick scan through sorceforge and other open source project sites yields about 1.87E3 projects to replace Checker and StackGuard with kew1 Linux-only alternatives. (Why? Who knows.) Most of these projects seem not to have gotten any further than the project web page saying how 'leet they were going to be.
• One of the side branches in the GCC repository was the bounded pointers project, which was way cool. It was mostly working, too, until the author had to go work on something else.

• I personally had high hopes for the GCC BP project. If you feel like doing something that will earn you the admiration of millions, finish that code up. :-)

A general case

[big_hairy_mama]

Isn't bounds checking just a specialized case for checking any type of access to uninitialized memory? There are several tools that provide replacements for malloc() that can track *all* memory allocation, and some, like Valgrind, provide almost a virtual machine that tracks basically everything your program does. Any time you read, write, or allocate memory, Valgrind will track it, and tell you if it is in error. Like I said, array bounds checking is just a special case of this.

Re:A general case

[morcheeba]

Isn't bounds checking just a specialized case for checking any type of access to uninitialized memory?

That's a good chunk of it, but there are several cases of acces to initialized (and alloc'ed memory) that should also be detected:

- pointers to stale memory. Example: malloc, initialize, free, malloc again and get some reused memory that was left initialized before the free, and then attempted use of that data. (calloc zeros the memory, malloc doesn't)

- pointers exceeding array bounds. Example: int x[100][100], reading array element x[10][150] doesn't cause a segfault (but x[150][10] does)

- unexpected pointer alias (devious and borders between just a regular bug and a bounds-checkable bug). The function doesn't expect the two pointers passed to it to point to the same area of memory (example memcpy pointers can't overlap, memmove pointer can). Incidently, this assumption is usually a toggleable (& dangerous if you're not careful) optimization and can cause the compiler to generate 'bad' code - more limited languages (eg. Fortran 77, but not Fortran 90) that don't have pointers can be more agressively optimized! when I've got a function that could choke on this kind of thing, I usually code in a bunch of asserts to check for this case and raise a flag.

Bounds checking gcc compiler

[geog33k]

I like to use the bounds checking patches to gcc to check code. You recompile your code and it checks every array access, memory access, etc. http://web.inter.nl.net/hcc/Haj.Ten.Brugge/

Good Question - Some Answers

[4of12]

I've found that ccmalloc helped me to find a lot of problems in C code. The output is more verbose than Purify, but it showed me where some real problems lay with my code.

Check out this site by Ben Zorn on free and other tools for this.

Insure++

[vipw]

Insure++ is heavenly, I don't know how long it's been since you've used it, but it detects almost all errors. I think most open source people who use it have their company buy it for them though; it is very expensive. It does very good bounds checking for both reading and writing, but it's real amazing help is in tracking down bad or dangling pointers.

It also does very detailed tracking of memory leaks, but can get a little confused when you store the last referencing pointer in a hashtable.

I think other than its somewhat clunky UI, price is the big killer. it takes a pretty fast machine to be able to use it much and it has a large up front cost, plus maintainence(upgrades and support) fee. It's really too bad they don't have a program in place with someone like sourceforge to let people use Insure++ on the test machines because that would not only be great advertising for them, but also could really help the open source developers too.

Change languages.

[rjh]

Warning: I'm a language zealot, so be warned that I'm utterly irrational and unamenable to the Sweet Voice of Reason. That said... :)

Use a different language. There are some things which C is appropriate for, but one of the things it's categorically not called for is when you have concerns about buffer-overflow conditions [*]. If this is a purely open-source, noncommercial project, do yourself and your career a favor: learn another language (one which doesn't have these sorts of problems) and write your app in that instead. You'll learn more, and you won't have to spend a dime on Purify or whatnot. If you go this route, I'd suggest Scheme; it's a beautiful LISP derivative.

If this is a commercial project, ask Management how married they are to C. In the overwhelming majority of cases, you can quietly substitute C++ without affecting the APIs one bit. Just wrap the external APIs in extern "C" and, inside the code, use C++'s beautiful vector instead of C-style arrays. Sure, you'll take a minor performance hit, but the increase in reliability will be well worth it.

Anyway, to try and give a (weak) answer to your question--instead of slapping a Band-Aid on the festering wound that is C memory management, you might want to think about doing away with the festering wound altogether. Use the right tool for the job--if C really is the right tool for the job, then fine, may God have mercy on your code. But if there are other, better, tools available... use them instead.

[*] OpenBSD manages to do pretty well with a C kernel, but that's because they're certifiably insane. It also impacts their dev cycle; they spend a great deal of time avoiding the pitfalls of C, so much so that it affects how much time they can devote to new development.

Re:Change languages.

[rjh]

Oh? Look at the at() method.

vector does do bounds checking, but since it results in a (minor) performance penalty, operator[] (the normal method of vector access) is unchecked. You want bounds checking, use at() .

95% of the time, it is simply bad software engineering practice to use operator[] within a vector . The only time it's really acceptable practice is when (a) you're operating under severe performance limitations and (b) you have some other guarantee you won't hit an out-of-bounds condition.

The solution to most of your debugging needs!

[ken_mcneil]

An excellent general solution I've found for problems of this nature can be found at "file:///usr/include/assert.h". Seriously,
preconditions, postconditions, and invariants are the best approach to avoiding such errors. Will a bounds-checker detect if you access an element that is out-of-bounds in a view (subarray) of a larger array? Also, if you are developing a library, using assertions will also greatly assist any end-users who are not using a bounds-checking tool.

Re:The solution to most of your debugging needs!

[0x0d0a]

Amen. I remember going through classes and having to churn out preconditions and postconditions and hating it...but then realizing that assert() is your best friend in code. If a data structure should or shouldn't have something true at a given point, but in an assert() to ensure that it's the way you think it is. It helps you understand your code, and most importantly, if you change something else that has a ripple effect through the program that causes a crash hours later, a good set of assert() calls will finger the initial cause in one minute instead of one week.

This is particularly important in open source projects. Bob writes code that produces and uses a data structure and makes some assumptions about it. Now John makes a few improvements to the program, has no idea what assumptions Bob (who lives a continent away) has made, and modifies the data structures in a way that breaks Bob's code. John doesn't know what single change broke Bob's code, and Bob doesn't know all the things that John did that might affect his data structures. Liberal use of assert() will cost you nothing at runtime (compile with -DNDEBUG), takes only a tiny bit of extra typing, and is one of the very best weapons against program-spanning nasty errors.

STL

[j_kenpo]

IMHO, you should do a mix of C and C++ and use the Standard Template Librarys vector, deque, or list classes instead of an array. Hell, even if you use an array, the STL functions and algorithms still work on them. You can even use the Queue and Stack wrappers if thats what your doing... Thats just my opinion though....

Re:Use scripting and VM languages, where possible.

[gerardrj]

Of course with PERL you could have the best of both worlds:

Develop in PERL with the flexibilty of the interpeter and all the garbage collection and neato stuff built-in.

When you hit a "stable" release version, use the O module to compule the code. either to Perl byte code for faster loading, or to one of two versions of C code. One just spits out calls to the perl/system libraries, the other is standard C code.