13. SGCheck: an experimental stack and global array overrun detector

False negatives (missed errors): it follows from the description above (How SGCheck Works) that the first access by a memory referencing instruction to a stack or global array creates an association between that instruction and the array, which is checked on subsequent accesses by that instruction, until the containing function exits. Hence, the first access by an instruction to an array (in any given function instantiation) is not checked for overrun, since SGCheck uses that as the "example" of how subsequent accesses should behave.

It also means that errors will not be found in an instruction executed only once (e.g. because this instruction is not in a loop, or the loop is executed only once).

False positives (false errors): similarly, and more serious, it is clearly possible to write legitimate pieces of code which break the basic assumption upon which the checking algorithm depends. For example:

  { int a[10], b[10], *p, i;
    for (i = 0; i < 10; i++) {
       p = /* arbitrary condition */  ? &a[i]  : &b[i];
       *p = 42;
    }
  }

In this case the store sometimes accesses a[] and sometimes b[], but in no cases is the addressed array overrun. Nevertheless the change in target will cause an error to be reported.

It is hard to see how to get around this problem. The only mitigating factor is that such constructions appear very rare, at least judging from the results using the tool so far. Such a construction appears only once in the Valgrind sources (running Valgrind on Valgrind) and perhaps two or three times for a start and exit of Firefox. The best that can be done is to suppress the errors.

Performance: SGCheck has to read all of the DWARF3 type and variable information on the executable and its shared objects. This is computationally expensive and makes startup quite slow. You can expect debuginfo reading time to be in the region of a minute for an OpenOffice sized application, on a 2.4 GHz Core 2 machine. Reading this information also requires a lot of memory. To make it viable, SGCheck goes to considerable trouble to compress the in-memory representation of the DWARF3 data, which is why the process of reading it appears slow.

Performance: SGCheck runs slower than Memcheck. This is partly due to a lack of tuning, but partly due to algorithmic difficulties. The stack and global checks can sometimes require a number of range checks per memory access, and these are difficult to short-circuit, despite considerable efforts having been made. A redesign and reimplementation could potentially make it much faster.

Coverage: Stack and global checking is fragile. If a shared object does not have debug information attached, then SGCheck will not be able to determine the bounds of any stack or global arrays defined within that shared object, and so will not be able to check accesses to them. This is true even when those arrays are accessed from some other shared object which was compiled with debug info.

At the moment SGCheck accepts objects lacking debuginfo without comment. This is dangerous as it causes SGCheck to silently skip stack and global checking for such objects. It would be better to print a warning in such circumstances.

Coverage: SGCheck does not check whether the areas read or written by system calls do overrun stack or global arrays. This would be easy to add.

Platforms: the stack/global checks won't work properly on PowerPC, ARM or S390X platforms, only on X86 and AMD64 targets. That's because the stack and global checking requires tracking function calls and exits reliably, and there's no obvious way to do it on ABIs that use a link register for function returns.

Robustness: related to the previous point. Function call/exit tracking for X86 and AMD64 is believed to work properly even in the presence of longjmps within the same stack (although this has not been tested). However, code which switches stacks is likely to cause breakage/chaos.

Extend system call checking to work on stack and global arrays.

Print a warning if a shared object does not have debug info attached, or if, for whatever reason, debug info could not be found, or read.

Add some heuristic filtering that removes obvious false positives. This would be easy to do. For example, an access transition from a heap to a stack object almost certainly isn't a bug and so should not be reported to the user.

sg_main.c: Redesign and reimplement the basic checking algorithm. It could be done much faster than it is -- the current implementation isn't very good.

sg_main.c: Improve the performance of the stack / global checks by doing some up-front filtering to ignore references in areas which "obviously" can't be stack or globals. This will require using information that m_aspacemgr knows about the address space layout.

sg_main.c: fix compute_II_hash to make it a bit more sensible for ppc32/64 targets (except that sg_ doesn't work on ppc32/64 targets, so this is a bit academic at the moment).