Communications - September 2011

touching a memory location that is not part of the source or destination string.

One example is FreeBSD’s libc, where the bcopy( 3)/memcpy( 3) implementation will move as much data as possible in chunks of “unsigned long,” typically 32 bits or 64 bits, and then “mop up any trailing bytes” as the comment describes it, with byte-wide operations. 2

If the source string is NUL terminated, however, attempting to access it in units larger than bytes risks attempting to read characters after the NUL. If the NUL character is the last byte of a VM page and the next VM page is not defined, this would cause the process to die from an unwarranted “page not present” fault.

Of course, it is possible to write code to detect that corner case before engaging the optimized code path, but this adds a relatively high fixed cost to all string moves just to catch this unlikely corner case—not a profitable trade-off by any means.

If we have out-of-band knowledge of the strings, things are different.

Compiler development cost. One thing a compiler often knows about a string is its length, particularly if it is a constant string. This allows the compiler to emit a call to the faster mem-cpy( 3) even though the programmer used strcpy( 3) in the source code.

Deeper code inspection by the compiler allows more advanced optimizations, some of them very clever, but only if somebody has written the code for the compiler to do it. The development of compiler optimizations has historically been neither easy nor cheap, but obviously Apple is hoping this will change with Low-level Virtual Machine (LLVM), where optimizers seem to come en gros.

The downside of heavy-duty compiler optimization—in particular, optimizations that take holistic views of the source code and rearrange it in large-scale operations—is that the programmer must be really careful that the source code specifies his or her complete intention precisely. A programmer who worked with the compilers on the Convex C3800 series supercomputers related his experience as “having to program as if the compiler was my ex-wife’s lawyer.”

Security costs. Even if your compiler does not have hostile intent, source code should be written to hold up to attack, and the NUL-terminated string has a dismal record in this respect. Utter security disasters such as gets( 3), which “assume the buffer will be large enough,” are a problem “we have relatively under control.” 3

Getting it under control, however, takes additions to compilers that would complain if the gets( 3) function were called. Despite 15 years of attention, over- and underrunning string buffers is still a preferred attack vector for criminals, and far too often it pays off.

Mitigation of these risks has been added at all levels. Long-missed no-execute bits have been added to CPUs’ memory management hardware; operating systems and compilers have added address-space randomization, often at high costs of performance; and static and dynamic analyses of programs have soaked up countless hours, trying to find out if the byzantine diagnostics were real bugs or clever programming.

Yet, absolutely nobody would be surprised if Sony’s troubles were revealed to start with a buffer overflow or false NUL-termination assumption.

slashdot sensation Prevention section

We learn from our mistakes, so let me say for the record, before somebody comes up with a catchy but totally misleading Internet headline for this article, that there is absolutely no way Ken, Dennis, and Brian could have foreseen the full consequences of their choice some 30 years ago, and they disclaimed all warranties back then. For all I know, it took at least 15 years before anybody realized why this subtle decision was a bad idea, and few, if any, of my own IT decisions have stood up that long.

In other words, Ken, Dennis, and Brian did the right thing.

But that Doesn’t solve the Problem
To a lot of people, C is a dead lan-
guage, and ${lang} is the language of
the future, for ever-changing transient
values of ${lang}. The reality of the
situation is that all other languages
today directly or indirectly sit on top
of Posix API and the NUL-terminated
string of C.

Related articles on queue.acm.org

Massively Multiplayer Middleware

Michi Henning

http://queue.acm.org/detail.cfm?id=971591

The Seven Deadly Sins of Linux Security

Bob Toxen

http://queue.acm.org/detail.cfm?id=1255423

B. Y.O.C. ( 1,342 Times and Counting)

Poul-Henning Kamp

http://queue.acm.org/detail.cfm?id=1944489

References

1. Computer business review. Partitioning and escon enhancements for top-end es/9000s (1992); http:// www.cbronline.com/news/ibm_announcements_71.

2. ViewVC. Contents of /head/lib/libc/string/bcopy.c (2007); http://svnweb.freebsd.org/base/head/lib/libc/ string/bcopy.c?view=markup.

3. Wikipedia. lifeboat sketch (2011); http://en.wikipedia. org/wiki/lifeboat_sketch.

Poul-henning Kamp ( phk@FreebsD.org) has programmed computers for 26 years and is the inspiration behind bikeshed.org. his software has been widely adopted as “under the hood” building blocks in both open source and commercial products. his most recent project is the Varnish httP accelerator, which is used to speed up large Web sites such as Facebook.