UB Canaries

If you report an undefined behavior bug, a common reaction from software developers is “So what? Our code works just fine.” As a random example, here is a discussion I had with Rasmus Lerdorf about five years ago about some UBs in the PHP interpreter. One might point out that it wasn’t a very mature exchange but I wasn’t even 40 yet at the time. (Earlier I had an example here from OpenSSL but this one is more suitable.)

An idea I’ve kicked around for a long time, but only got around to implementing this week, is a collection of canaries for undefined behavior: little test programs that automate the process of determining whether a given compiler configuration is willing to exploit particular UBs. Here’s the UB-canary repo. The idea behind canaries is that since they’re easy to run, they provide a quick and easy way to figure out which UBs the users of a particular compiler should be especially worried about. The definition of “exploit” requires a bit of care: exploitation only makes sense in terms of an expectation held by a C/C++ programmer. For example, I might expect that when a negative number is shifted to the left, the result is the same as if the number had been cast to unsigned before being left-shifted. Of course we need to be completely clear with ourselves that any such expectation has nothing to do with the language standard and everything to do with what a particular compiler happens to do, either because the providers of that compiler are unwilling to exploit that UB or just because they have not gotten around to exploiting it yet. When no real guarantee from the compiler provider exists, we like to say that as-yet unexploited UBs are time bombs: they’re waiting to go off next month or next year when the compiler gets a bit more aggressive.

Below are some results from various versions of GCC and LLVM on Ubuntu Linux. Each compiler was tested at -O0, -O1, -O2, -Os, and -O3; the number in each part of the table indicates the number of optimization options at which the compiler was willing to exploit the UB. Most compilers were targeting x86 but for some of the older versions of GCC (4.0, 4.1, 4.2) I could no longer get that to work due to some sort of libc problem, so they were targeting x86-64. I doubt that affects the results much.

Here are the results for GCC:

4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9
addr-null 5 5 5 5 5 5 0 0 0 0
array-oob 0 0 0 0 0 0 0 0 0 0
dangling-pointer 4 4 4 4 4 4 4 4 4 4
int-min-mod-minus-1 5 5 5 5 5 5 5 5 5 5
memcpy-overlap 5 5 5 5 5 5 5 5 5 5
modify-string-literal 5 5 5 5 5 5 5 5 5 5
pointer-casts 4 4 4 4 4 0 0 0 0 0
shift-by-bitwidth 2 2 2 3 3 3 3 3 4 4
signed-integer-overflow 2 5 3 3 3 3 3 3 3 3
signed-left-shift 0 0 0 0 0 0 0 0 0 0
strict-aliasing 3 3 3 0 2 0 3 3 3 3
uninitialized-variable 0 0 0 1 1 1 1 1 1 1

And for LLVM:

2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6
addr-null 0 0 0 0 0 0 0 0
array-oob 0 0 0 0 0 0 0 0
dangling-pointer 3 3 3 3 3 3 3 3
int-min-mod-minus-1 5 5 5 5 5 5 5 5
memcpy-overlap 5 5 5 5 5 5 5 5
modify-string-literal 5 5 5 5 5 5 5 5
pointer-casts 5 5 5 5 5 5 5 5
shift-by-bitwidth 3 3 3 3 3 3 3 3
signed-integer-overflow 4 4 4 4 4 4 4 4
signed-left-shift 0 0 0 0 0 0 0 0
strict-aliasing 3 3 3 3 3 3 3 3
uninitialized-variable 4 4 4 4 4 4 4 4

Click on the links to see the corresponding assumptions. It is interesting that GCC shows a lot more variance in UB exploitation than LLVM; I suspect that this is simply because the GCC versions shown here span a longer period of time than the LLVM versions (~10 years vs. ~4 years). It is also interesting that UB exploitation is not getting (as one might have feared) uniformly worse. Although overlapping memcpy() calls were always exploited by the compilers tested here, that is not the case on my Mac. I believe there have been compilers that exploited the signed-left-shift UBs but either my canaries aren’t good enough to find them or else those behaviors did not happen to be seen in the releases I choose here. Modifying a string literal never works on a modern Linux machine but it continues to work on embedded platforms that lack memory protection (I just saw some code doing this the other day). The INT_MIN % -1 case is interesting since it has a sensible answer and also my reading of the C99 standard is that this construct is not undefined; it is explicitly undefined in the newer standards.

Please let me know if:

  • You notice a bug in any UB canary or in the (admittedly crappy) driver script.
  • You know of a compiler that exploits an UB but where I don’t have a canary detecting the exploitation. A pull request would be ideal.

Canary code comes from a variety of sources and I have tried to give credit in the individual files. UB canaries are related to several ongoing UB-protection efforts but I want to in particular mention the Cerberus C Survey that is being run by Peter Sewell’s research group at Cambridge. Their goal is to create a mechanized semantics for C as it is really used, as opposed to the somewhat fictitious language described in the standards. If you are a C/C++ developer who cares about UB, please take a few minutes to fill out the survey.

Inexpensive CPU Monster

Rather than using the commercial cloud, my group tends to run day-to-day jobs on a tiny cluster of machines in my office and then to use Emulab when a serious amount of compute power is required. Recently I upgraded some nodes and thought I’d share the specs for the new machines on the off chance this will save others some time:

processor Intel Core i7-5820K $ 380
CPU cooler Cooler Master Hyper 212 EVO $ 35
mobo MSI X99S SLI Plus $ 180
RAM CORSAIR Vengeance LPX 16GB (4 x 4GB) DDR4 SDRAM 2400 $ 195
SSD SAMSUNG 850 Pro Series MZ-7KE256BW $ 140
video PNY Commercial Series VCG84DMS1D3SXPB-CG GeForce 8400 $ 49
case Corsair Carbide Series 200R $ 60
power supply Antec BP550 Plus 550W $ 60

These machines are well-balanced for the kind of work I do, obviously YMMV. The total cost is about $1100. These have been working very well with Ubuntu 14.04. They do a full build of LLVM in about 18 minutes, as opposed to 28 minutes for my previously-fastest machines that were based on the i7-4770. I’d be interested to hear where other research groups get their compute power — everything in the cloud? A mix of local and cloud resources? This is an area where I always feel like there’s plenty of room for improvement.