Checking Debian for Illegal File Overwrites

1  Introduction

A Debian installation has the concept of files owned by packages. If one tries to install a new package that would hijack a file owned by another package this will make (unless certain specific measures have been taken, see Section 3) the installation fail, like this:

Unpacking gcc-avr (from .../gcc-avr_1%3a4.3.0-1_amd64.deb) ...
dpkg: error processing /var/cache/apt/archives/gcc-avr_1%3a4.3.0-1_amd64.deb
 (--unpack):
 trying to overwrite `/usr/lib64/libiberty.a', which is also in package binutils
dpkg-deb: subprocess paste killed by signal (Broken pipe)
Errors were encountered while processing:
 /var/cache/apt/archives/gcc-avr_1%3a4.3.0-1_amd64.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

Our aim is to detect these errors by analyzing the debian distribution, hopefully before they actually occur on a user machine.

An obvious naïve solution would be to try to install together all pairs of packages that occur in the distribution. Debian amd64/testing has currently (May 12, 2008) about 21.000 Packages, that would make about 200.000.000 pairs of Packages to test, which clearly is not feasible.

2  Packages Sharing a File

A first idea towards a better solution is to only consider those pairs of packages that actually share at least one file. Luckily, the information which package contains which file is available in the file Contents of the distribution. This file contains stanzas like

...
bin/fbset                       admin/fbset
bin/fgconsole                   utils/console-tools,utils/kbd
...
etc/default/nvidia-kernel       contrib/x11/nvidia-kernel-common
...

In this file, information is indexed by path names of the files (omitting the initial slash). For every file a comma separated list of packages containing that file is given where packages are indicated with their section (a classification of packages by type, like games or admin), and probably the component if it is different from main (which can currently be contrib or non-free). For instance, the file /bin/fgconsole is provided by the packages console-tools and kbd which both are in Section utils. In fact the Contents file that can be found on a debian mirror may be slightly out of date as this file is generated only once per week.

The Contents file of amd64/testing (as of May 2008) contains about 2.300.000 entries. It is a trivial programming exercise to compute from this file a list of pairs of packages that share at least one file.

3  Sharing a File May Be OK

Sharing a file does not necessarily mean a bug. There a several reasons why it may be OK for two packages, say A and B, to share a file, say F:

1. The two packages are not co-installable by the package relationships declared in their distribution. In the simplest case that means that package A declares Conflicts: B in its control file (or vice versa for package B), in a more complicated case it could mean that both packages provide the same virtual package and that one of the two packages conflicts with that very virtual package. There may also be a “deep” conflict like A depending on C, B depending on D, C depending on E of version strictly smaller than n, and D depending on E of version at least n. Deep conflicts may be even more complex and involve alternatives.
2. One of the packages, say A, declares that it has the right to replace files owned by B, by having in its control file a stanza Replaces: B.
3. One of the packages, say B, diverts the file F that it shares with package A. This means that if package B is being installed on a system already containing packageA then A’s version of file F will be renamed; file F will be restored to its original name when package B will be removed. File diversions are declared by invoking the tool dpkg-divert from a maintainer script which will simply register the diversion request in a system-wide database. This database is consulted by dpkg when installing files.

   Diversions are not declared in the package control file. One reason for this is that file diversions might depend on the environment in which maintainer scripts are executed, see Section 4.

4  Detecting File Overwrites

We proceed in two stages in order to find the actual file overwrite problems:

1. Co-installability is checked with the pkglab tool coming from the EDOS project. This is the only tool that can detect “deep” conflicts between packages. This first phase gives us a reduced list of pairs of packages.
2. Knowing which files are diverted by a package poses different problems: Diversions are registered by the so-called postinst script of a package, one of the maintainer scripts that are executed during installation (or upgrade, or removal) of a package. This leads to two problems:
   1. Execution of the postinst script depends on the current state of the system, and can in general not be described by a simple list of files.

      This problem is illustrated by the following code snippet taken from the postinst script of the package dnsutils:

      for i in `dpkg-divert --list dnsutils | awk '{ print $3 }'`
          do
              rm -f $i.bind
              dpkg-divert --remove $i
          done
      

      Here, the list of packages diverted depends on the result of execting the command dpkg-divert --list dnsutils on the system.

   2. The postinst script is written in a Turing complete language (usually Posix shell or bash), which means that exact semantic properties are undecidable.

      This problem is illustrated by the following code snippet taken from the postinst script of the package module-init-tools:

      undivert_gen() {
        DEXT=${3:-modutils}
        dpkg-divert --remove --rename --package module-init-tools \
          --divert $2/$1.$DEXT $2/$1 > /dev/null
      }
      

      with subsequently several calls to this function.

   For this reason, we try in the second phase to install each of the pairs of packages remaining after the first phase in a chroot, using apt-get install. We then search the install log for file overwrite errors.

5  Results and Code

The following statistics is from the first run performed on April 16, 2008, on amd64/sid:

Checking co-installability with EDOS pkglab took 30 minutes and gave a 88% reduction of the search space. Testing the installation of the remaining 102 pairs of packages still took 2.5 hours. This measures where taken with a dual-core amd64 at 1.6GHz, using a local debian mirror access over a fast LAN.

Detected bugs are tracked in the Debian bug tracking system, and marked there with user treinen@debian.org und usertag edos-file-overwrite. The list of these bugs can be retrieved at

The code can be obtained from svn://scm.gforge.inria.fr/svn/sodiac in the directory examples/debian.

6  Acknowledgements

Thanks to Stefano “zack” Zacchiroli for discussions on this project, and suggestions for improvements of this document.

This document was translated from L^AT_EX by H^EV^EA.