Verifying the Corresponding Source

(This post is a troll, don't take it too seriously!)

GNU GPL and some other software licenses require you to make the source available if you publish the covered software in the binary form. At first, this seems to be a very simple requirement. However, theoretically, as I will show below, it can create problems for you even if you comply. What matters for this post is whether you can prove the compliance, and this turns out to be unexpectedly hard. Please consider this (theoretical so far) danger when deciding to publish your own work under GPL or similar licenses.

Let's take Arch Linux as an imaginary victim. They distribute a lot of software in the binary form, and some of the software is covered by GNU GPL. Let's take GNU Bison as a simple example. At the time of this writing, the version of Bison distributed by Arch Linux is 2.5-3. Here is the x86-64 package, here are the purported machine-readable build instructions and patches, and the source can be fetched from gnu.org. Now imagine that someone makes a (false in this case) claim that the source, build instructions and patches do not correspond to the published binary package. How can this claim be refuted?

The obvious idea would be to rebuild the binary package from sources and compare its contents to the published binary package. For simplicity, let's limit this comparison to the /usr/bin/bison binary. Unfortunately, this simple idea fails. The published binary is 377456 bytes long, while my attempt to rebuild it in an up-to-date Arch resulted in a different length:

$ makepkg
<lots of output snipped>
$ tar tvf bison-2.5-3-x86_64.pkg.tar.xz | grep usr/bin/bison
-rwxr-xr-x root/root    377488 2012-04-29 17:41 usr/bin/bison

This mismatch means that the content of the resulting binary depends not only on what is distributed as the Corresponding Source, and that something has changed.

Of course, one of the changed factors is the compiler version. Different compilers implement different optimizations, and thus generate different code. The original bison binary in the original package is dated by November 9th, 2011. So, to remove this factor, we need the same compiler as was available on that day. Fortunately, Arch has a Rollback Machine that has every version of every package back to 2008. So, the next attempt to produce an identical binary: download and install gcc from the same date. This downgrade fails to produce a working gcc, because the run-time dependencies of gcc have to be downgraded too. This means cloog, gcc-libs, isl and ppl. Surprise: the downgraded gcc still doesn't produce the bison binary identical to the official one!

The other factor is that not only object code from bison's *.o files goes into the resulting bison binary. The linker also inserts code from /usr/lib/libc_nonshared.a which belongs to glibc. So, in order to cancel this factor, one would need to downgrade glibc, which is impossible to do safely: on today's Arch Linux there is a lot of software, including Bash, that depends on glibc >= 2.15.

The solution is to install another Arch Linux system into an initially-empty chroot, using the Rollback Machine instead of a mirror. I.e. with this line in /etc/pacman.d/mirrorlist:

Server = http://arm.konnichi.com/2011/11/09/$repo/os/$arch

The system installed this way produced the bison binary identical to the official one (MD5 sums matched).

So, in the end, I was able to prove that Arch Linux indeed distributes the source that corresponds to their bison binary. However, I would not have succeeded if they didn't have their Rollback Machine — i.e. essentially a way to reconstruct the whole build environment, far beyond what GPL seemingly requires.

Don't use old dtoa.c

A lot of projects use the dtoa.c file that bears the following copyright notice:

 * The author of this software is David M. Gay.
 *
 * Copyright (c) 1991, 2000, 2001 by Lucent Technologies.

If your software uses it, please take steps to update this file or stop using it. The reason is very simple: your program will compile just fine, but will work incorrectly when compiled with gcc-4.4.0 (not released yet). Here is a short testcase (save as test.c):

#include <stdio.h>

double strtod(const char *s00, char **se);

int main(int argc, char* argv[])
{
 double result = strtod(argv[1], 0);
 printf("%f\n", result);
 return 0;
}

Compile as follows: gcc-4.4 -O2 -Dstrtod=my_strtod -DIEEE_8087=1 -DHonor_FLT_ROUNDS=1 -DTrust_FLT_ROUNDS -DOmit_Private_Memory=1 -DNO_INFNAN_CHECK=1 -DNO_HEX_FP=1 dtoa.c test.c

The -Dstrtod=my_strtod flag is needed in order to make sure that the version of strtod() from dtoa.c, not from your system C library, is used. -O2 is the default optimization level used by many software projects. The rest of the flags are explained in the dtoa.c file.

The testcase converts its argument to a double-precision floating-point number, and then prints the result. So, when given a number, this testcase should print it back. let's try:

$ ./a.out 1.1
11.000000

The result is clearly incorrect. The reason (as one can see by appending -Wall to the compiler command line) is that strict aliasing rules are violated in dtoa.c. Indeed, if one adds the -fno-strict-aliasing flag to the compiler command line, the resulting program will behave correctly:

$ ./a.out 1.1
1.100000

Here is the formulation of the aliasing rules from ISO/IEC 9899:TC2, section 6.5:

An object shall have its stored value accessed only by an lvalue expression that has one of the following types:

• a type compatible with the effective type of the object,


• a qualified version of a type compatible with the effective type of the object,


• a type that is the signed or unsigned type corresponding to the effective type of the object,


• a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,


• an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or


• a character type.

dtoa.c does this:

typedef union { double d; ULong L[2]; } U;

#define word0(x) ((U*)&x)->L[1]
#define word1(x) ((U*)&x)->L[0]
#define dval(x) ((U*)&x)->d

So, it stores doubles, but reads this memory using lvalue expressions of the "ULong" type (and the other way round), contrary to the standard.

GCC allows such access only if the memory is accessed through a union type. The TC3 revision of the C99 standard also allows type punning through the union in the footnote in the section 6.5.2.3:

If the member used to access the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning".

In dtoa.c, the union is "invented" each time the code wants to reinterpret a double value as two ULongs. So, it doesn't make sense to speak about the member last used to store a value in the union, and the note above doesn't apply. I.e., instead of this code,

double a;
word0(a) = L;
word1(a) = 0;
return dval(a);

this should be used:

U a;
a.L[0] = L;
a.L[1] = 0;
return a.d;

Note that there are no pointer casts in the corrected code.

The topic of strict aliasing rules, with working and non-working examples, is explained in the GCC manual. An updated version of dtoa.c and the needed header are available in the sources of GCC itself.

Unexpected warning

Today I refactored a function in my C program in order to make it more readable and remove special-casing. What came unexpected is that I got a new warning in a function that I didn't touch. While this sounds strange, here is a very simple example that shows how it could happen.

This is the function that I didn't touch, but that will, at the end, get a warning:

extern const int db_to_add[32];

static int add_db(int a, int b)
{
 if (a < b) {
  int tmp = a;
  a = b;
  b = tmp;
 }
 if (a - b >= 32)
  return a;

 return a + db_to_add[a - b];
}

Here is a caller, just to make it sure that a static function is used:

int peak_db[32];
static int noise(int band1, int band2, int spectrum1, int spectrum2)
{
 /* actually a lot more complex, but the idea is that
    it takes two bands, except for special cases */
 int noise1 = peak_db[band1] + spectrum1;
 int noise2 = peak_db[band2] + spectrum2;
 return add_db(noise1, noise2);
}

int valid_use(int b, int s)
{
 /* a dummy warning-free function
    only for the purpose of this blog post */
 return noise(b, b + 1, 0, s);
}

With all of the above, there is no warning, even when "-O3 -Wall" flags are passed to gcc. Now add this (in the real program, this is the result of value propagation over various branches):

int trigger_warning()
{
 return noise(0, 0, 0, -200);
}

The intention is to attenuate the unneeded term enough so that it doesn't matter, and use the general two-band case. With gcc-4.3.1 -O3 -Wall, the result, referring to the line in add_db() where a is compared with b, is:

warning: assuming signed overflow does not occur when assuming that (X - c) > X is always false

So it looks like gcc inlined everything and attempted to test whether peak_db[0] < peak_db[0] - 200. Because C compilers are allowed to think that signed overflow never occurs, this is always false (as intended). However, tests of this form are often incorrectly used as security checks, that's why the warning.

gcc-4.3 troubles

After obtaining access to the CVS server at Yandex, I tried to build some internal utilities for daily use (e.g., for examining database contents) on my work laptop. The first attempt failed, because Debian Lenny comes with gcc-4.3.1, and the official build machines (that I was in fact supposed to use instead of the laptop) still use gcc-4.2.x.

First, some of the "known good" snapshots of external projects that are used by the to-be-built utilities have gcc-4.3 related issues. Fortunately, Debian's bug and package database was very helpful, and I was able to extract the needed patches.

Second, gcc-4.3 added some new warnings, and the build system is set up to use -Werror by default. While some of the new warnings are helpful, others are not. Try, e.g., compiling this simple function with g++ -Wconversion -c test.cpp:

typedef unsigned char uint8_t;
void grow(uint8_t & u)
{
        u *= 7;
}

Result:

test.cpp: In function 'void grow(uint8_t&)':
test.cpp:4: warning: conversion to 'unsigned char' from 'int' may alter its value

I.e., almost every in-place mathematical operation with shorts and chars results in warnings! With -Werror, this means errors in many files. Obviously, this isn't worth fixing, so I removed -Wconversion from the compiler flags in my checkout. Similar bugs are already recorded in GCC bugzilla.

Third, even after fixing fixable warnings and removing -Wconversion, I hit an internal compiler error. Since I found no similar reports (the error manifested itself on proprietary code, after all), I reduced the testcase and submitted it to GCC bugzilla.

After that, I gave up. I posted my changes to the internal code review list (just so that they don't get lost), switched the compiler to gcc-4.2 (it is available in Debian side-by-side with 4.3), and compiled what I needed without further problems.

BTW, Debian still uses gcc-4.1.2 for compiling their kernels. It would be interesting to know why.