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.

Recovering a bricked D-Link router

Today my D-Link DSL-2600U ADSL/Wi-Fi router decided to die, without any obvious reason. Only the power and Ethernet LEDs were active, and the computer directly connected to it via Ethernet could not receive an IP address. Fortunately, I had an old ADSL router still around, and thus was able to find information that, in the end, allowed me to recover the DSL-2600U.

The first thing I thought, however, was that a problem is on my local computer. So I started tcpdump, only to find out that the router sends strange packets: a gratious ARP for 192.168.1.1, followed by ARP "Who has 192.168.1.159? Tell 192.168.1.1". It didn't respond to pings even from 192.168.1.2. At this point, it became obvious that it is broken or at least needs its settings to be reset, without any access to the web interface. Pressing the Reset button in the pinhole did not change anything.

When assigning my computer the IP 192.168.1.159, the conversation went a bit further, namely, there appeared a TFTP packet with a string "308nfs6358" in it. Googling for it (via the spare router) gave mostly results about reflashing that same router model that I had, via the COM port, as a last resort. They were useless, as adding a COM port to the router is not a modification that I wanted to do.

Still, I wanted to try to revive the router, and these pages also suggested that TFTP is involved somehow. They even told the reader to put the official firmware to 192.168.1.1 via TFTP after pinging it - but obviously this could not work at this stage.

So, as the router asked for the "308nfs6358" file, and also the I had to provide it via TFTP. On Linux, there is a tftp server, atftpd, so I set it up. It is actually easy. Just create the /tftpboot directory and chmod it to 777, then run:

atftpd --no-fork --daemon

However, it was not an obvious question what to put in that directory. I had a firmware file, downloaded from the official site. When unzipped, this yields DSL-2600U_3.12_6338_12_RU_1.25_20101129.img. However, the web pages containing the reference to the "308nfs6358" file also mentioned "bcm963xx_fs_kernel", so I assumed (maybe wrongly) that I had to split the original firmware file into two.

This OpenWRT page ended up being a useful resource. It contains a program to dump the firmware structure. As the program calculates and verifies CRC of various portions of the firmware file, I guessed that I could modify it to dump these portions. The implementation is obvious: there is a compute_crc32() function that receives the offset and length of the region being checksummed, and it is trivial to dump the bytes into a separate numbered file. So, I ended up with a short 256-byte header and two files. For the reference, here are the offsets and lengths:

rootfs: start=256, length=3063808
kernel: start=3064064, length=560856

As the router was broken anyway, and because I had no better idea, I decided to determine the correct file by trial and error. To be able to understand what happens, I started Wireshark and told it to sniff all packets on the eth0 interface of my computer. I copied one of the files (the shorter one) into /tftpboot/308nfs6358 and power-cycled the router. It downloaded the file via TFTP (as evidenced by Wireshark), and then nothing happened.

With the other file, I had better luck: the router not only downloaded it, but also changed its MAC address, sent some gratious ARP packets and became pingable for some time. Still, it didn't attempt to download anything else. OK, so it means that it waits for me to upload the second file to it, I thought. This didn't work. The correct thing to do was to upload the original unzipped firmware.

So here is the complete sequence of actions that worked:

1. Assign the IP address 192.168.1.159 to the computer.
2. Unzip the firmware, split it.
3. Copy the rootfs (the 3.6 MB part of the firmware) to /tftpboot/308nfs6358
4. Run atftpd as follows: atftpd --no-fork --daemon
5. Power-cycle the router
6. When it changes the MAC address, upload the firmware to it: atftp --no-source-port-checking -p -l  DSL-2600U_3.12_6338_12_RU_1.25_20101129.img -r bcm963xx_fs_kernel 192.168.1.1
7. Try again from the beginning, as the default timeouts are rather short.

This blog post has been sent through the revived router. Still, I guess it won't last long, and I need to buy a replacement.

Namespace issues in Apache

Some time ago I was given a task to write a Python WSGI script that handles all (really all!) URLs on a given Apache-based virtual host. Doesn't that sound easy? Here is the "obvious" part of the Apache configuration file for that virtual host:

WSGIScriptAlias / /path/to/script.wsgi

Except that it is slightly wrong. The problem is that the script really should handle all URLS, even "evil" ones, without any omissions. In the above form, it doesn't.

First, if the URL contains a percent-encoded slash (e.g., as in http://example.org/foo%2fbar), Apache gives a 404 error by default, without even calling the script. Solution:

AllowEncodedSlashes On

Wait, there is more! Regular aliases have higher priority than our WSGIScriptAlias, and that there are some default aliases usually set by distributions. Due to that, http://example.org/icons/folder.gif will map to a static file, not to the WSGI script. There is a wishlist bug in Apache that one cannot easily remove aliases from the namespace.

The solution (or, more precisely, a bad hack) that I found is to use mod_rewrite. By adding some prefix to all URLs (and, of course, dealing with it in the script), one makes sure that the existing aliases are not hit:

AllowEncodedSlashes On

RewriteEngine On
RewriteRule ^/(.*)$ /dummyprefix/$1 [PT]

WSGIScriptAlias /dummyprefix /path/to/script.wsgi

Still, this doesn't work (gives a 404 error instead of calling the script) on URLs that include some bad characters such as newlines, e.g. http://example.org/foo%0abar . Removing the dollar sign from the pattern fixes the 404 error, calls the script, but it then receives a truncated PATH_INFO in the environment. Still, SCRIPT_URI is correct, so this may be enough. In fact, if the script doesn't care about PATH_INFO, even this works:

AllowEncodedSlashes On

RewriteEngine On
RewriteRule ^/ /dummyprefix [PT]

WSGIScriptAlias /dummyprefix /path/to/script.wsgi

The real cause of the issue with the original RewriteRule is that the "." metacharacter doesn't really match all characters. Indeed, it doesn't match a newline. So, in order to match the full URL, including the evil encoded newline in the middle, one has to write an explicit range covering all possible characters:

AllowEncodedSlashes On

RewriteEngine On
RewriteRule ^/([\x00-\xff]*)$ /dummyprefix/$1 [PT]

WSGIScriptAlias /dummyprefix /path/to/script.wsgi

Whoops. Now a typical sysadmin probably won't understand the need (or will forget the reason) behind such a complex configuration for a seemingly simple issue of passing all URLs to a single script. And I am still not 100% sure that all valid URLs are really handled by the script. Maybe I should have started with a different web server, the one that doesn't have a polluted namespace in virtual hosts by default.

Update: In the comments, the following was suggested:

AllowEncodedSlashes On
WSGIHandlerScript wsgi-handler /path/to/handler.wsgi
SetHandler wsgi-handler

Here handler.wsgi would be a typical WSGI script, except that it provides the "handle_request" callable object instead of "application".

This solution looks elegant and simple, but, if PHP is also installed on the same server, it is wrong (thus proving the complexity of the problem and the fragility of Apache URL namespace). It misses URLs that end in .php (even though the document root s empty). So, back to the ugly solution based on mod_rewrite.

Autoconf and defaults

Autoconf is based on a set of macros. these macros are put by developers into the configure.ac file, and the "autoconf" program generates a proper configure script from that. The configure script commonly accepts options such as --enable-foo and --with-foo. It is important that they behave in a sensible way.

The --with-foo argument is processed with the AC_ARG_WITH macro. It is documented as follows:

AC_ARG_WITH (package, help-string, [action-if-given], [action-if-not-given])

If the user gave configure the option --with-package or --without-package, run shell commands action-if-given. If neither option was given, run shell commands action-if-not-given. The name package indicates another software package that this program should work with. It should consist only of alphanumeric characters, dashes, plus signs, and dots.

The option's argument is available to the shell commands action-if-given in the shell variable withval, which is actually just the value of the shell variable named with_package, with any non-alphanumeric characters in package changed into ‘_’. You may use that variable instead, if you wish.

 Let's see what's wrong with this piece of configure.ac, found in lxdm-0.4.1:

AC_ARG_WITH(pam,AC_HELP_STRING([--without-pam],[build without pam]),
[],[AC_CHECK_LIB([pam], [pam_open_session])])

This does nothing if the --without-pam option is not given, and checks for the PAM library if the option is given. Looks right? No!

This also does nothing if the --with-pam option is given, thus, resulting in a build without PAM support!

Note that the documentation for AC_ARG_WITH even provides examples how to use the macro properly. Use them as a reference, and have the following checklist:

• Use the $withval or $with_package variable.
• Test it for values such as "yes", "no", "auto" and explicit path.
• Check the presence of the package unless it is explicitly disabled or the support is experimental.
• Fail if the external package is requested but not available.

Yes, this becomes verbose, but it is necessary for correctness.

The first point also applies to the AC_ARG_ENABLE macro:

AC_ARG_ENABLE(debug,         AS_HELP_STRING([--enable-debug],
                                  [Enable debugging (default: disabled)]),
                                [DEBUGGING=$enableval], [DEBUGGING=no])

I wrote a DTS encoder

Let me announce a piece of software that I have published a week ago: dcaenc, an open-source DTS encoder. The package contains sources for a shared library, a command-line tool and an ALSA plugin.

DTS is one of the compressed formats that allow transfer of multichannel (e.g., 5.1) audio over SPDIF connections. The other common format is AC3. The SPDIF standard does not define a method for passing more than two channels of uncompressed PCM audio, so compression has to be used. Both AC3 and DTS are also used in DVD sound tracks.

Open-source decoders for both AC3 and DTS already exist: liba52 and libdca (side note: please don't use libdca, it is a security risk, there are some files that crash it or are decoded improperly). FFmpeg can also decode these formats. However, useful open-source encoders existed only for AC3: one in FFmpeg, and the other one (aften) based on it. The DTS "encoder" in FFmpeg was ported by someone else from my old proof-of-concept code that served as a tool to understand the DTS subband transform. It could only encode stereo PCM files into a valid DTS bitstream of the same bitrate, which is useless for any practical purpose. Now dcaenc provides a useful encoder that accepts multichannel sound and encodes it to the bitrate specified by the command line parameter.

As already mentioned, there are the following use cases for my encoder:

• On-the-fly encoding of multichannel PCM audio produced by arbitrary ALSA applications (e.g. games) for transmission via SPDIF
• Creation of DVD soundtracks and DTS CDs.

Some people ask me why I didn't integrate my encoder into FFmpeg instead of releasing it as a standalone package. Indeed, there are faster implementations of the basic DSP building blocks in FFmpeg, and the criticism that I reinvented a lot of wheels is valid. Integration with FFmpeg is indeed a desired long-term goal.

There are still several reasons why I decided not to integrate right from the beginning. First, I don't think that my work is in the necessary shape for integration yet. E.g., in FFmpeg, floating-point codecs are preferred, while my library currently uses fixed-point (I thought it would be beneficial for porting to the ARM architecture). Second and the most important reason: when the encoder is standalone, users can get it immediately and use it, without the hassle of replacing the distribution-provided FFmpeg package and potentially breaking distribution-provided software such as VLC that depends on it. Third, if I know that I wrote all the code myself, I can sell LGPL exceptions.

While dcaenc already produces "transparent" output at 1411 or 1536 kilobits per second, there is still room for quality improvement at lower bitrates. This is because the library does not yet use all compression possibilities offered by the DTS standard. I am going to implement at least linear prediction (incorrectly called ADPCM in the specification) and channel coupling in the future versions. Stay tuned!

I am going to Desktop Summit 2011

I am going to Desktop Summit. Actually, I have already arrived in Berlin.

At the summit, I will mostly follow the Platform track (Rm2002) and then try to participate in BoFs.

The case of a non-raised exception

As you probably know, python uses exceptions for error handling. It is considered a good style to avoid adding error-handling code in the form of conditional statements. Instead, one should rely on the fact that an appropriate exception is raised once an error condition is detected, and caught when it can be dealt with.

So, let'a assume that you are given a task of downloading a file given the URL and the file name on disk, using Python. You may want to write the following code and hope that you don't have to add any error-handling because (as you think) all errors that can happen are either network errors or file write errors, and those two types of errors already raise exceptions for you.

#!/usr/bin/python

import urllib2
import sys
import socket

def download(url, fname):
    net = urllib2.urlopen(url)
    f = open(fname, "wb")
    
    while True:
        data = net.read(4096)
        if not data:
            break
        f.write(data)
    
    net.close()
    f.close()

if __name__ == "__main__":
    if len(sys.argv) != 3:
        print "Usage: download.py URL filename"
    
    url = sys.argv[1]
    fname = sys.argv[2]
    
    socket.setdefaulttimeout(30)
    
    download(url, fname)

Indeed, this code downloads existing files via HTTP just fine. Also, it provides sensible tracebacks for non-existing hosts, 404 errors, full-disk situations, and socket timeouts. So, it looks like the result of calling the download() fnction is either a successfully downloaded file, or an exception that the other part of the application will likely be able to deal with.

But actually, it only looks like this. Consider a situation when the HTTP server closes the connection gracefully at the TCP level, but prematurely. You can test this by starting your own Apache web server, putting a large file there, and calling "apache2ctl restart" while the client is downloading the file. Result: an incompletely downloaded file, and no exceptions.

I don't know if it should be considered a bug in urllib2 or in the example download() function above. In fact, urllib2 could have noticed the mismatch of the total number of bytes before the EOF and the value in the Content-Length HTTP header.

Here is a version of the download() function that detects incomplete downloads based on the Content-Length header:

def download(url, fname):
    net = urllib2.urlopen(url)
    contentlen = net.info().get("Content-Length", "")
    f = open(fname, "wb")
    datalen = 0
    
    while True:
        data = net.read(4096)
        if not data:
            break
        f.write(data)
 datalen += len(data)
    
    net.close()
    f.close()

    try:
        contentlen = int(contentlen)
    except ValueError:
        contentlen = None

    if contentlen is not None and contentlen != datalen:
        raise urllib2.URLError("Incomplete download")