Stammtisch: Nachlese vom 3. November 2011
Reflections on trusting trust
Beim Treffen am 3. November hatte Konrad die Gedanken eines
Artikels von Ken
Thompson über Hintertüren in Compilern (Reflections on
trusting trust) mitgebracht. Die Idee ist grob die, dass der
Compiler so modifiziert wird, dass er (1) wenn er zum Beispiel
login übersetzt, Code einfügt, der den Zugang mit einem
bestimmten Passwort immer erlaubt. Und weiterhin (2) soll der
Compiler, wenn er einen Compiler übersetzt, in diesen den selben
Schadcode einfügen, sprich dieser soll sich fortpflanzen/ausbreiten.
Wenn ein solcher infizierter Compiler einmal in Umlauf kommt, wird er über die Zeit hin, alle Software infizieren. Dies zu erkennen, fällt allerdings nicht so leicht, weil der Schadcode nicht direkt im Quelltext steht, sondern erst beim Übersetzen hinzugefügt wird.
Wir haben den Abend über darüber philosophiert, wie man eventuell solch einen infizieren Compiler erkennen oder entlarven könnte und ob es überhaupt praktisch durchführbar ist. Die theoretische Machbarkeit basiert auf sogenannten Quines. Dies sind Programme, die ihren Quelltext ausgeben, sprich sich selbst replizieren können.
Ob dies aber praktisch umzusetzten geht, wurde von Jörg bezweifelt, da auch Compiler einer Entwicklung unterliegen und der einzuschleußende Code nur auf spezielle Versionen angepasst seien kann – außer der Programmieren kann in die Zukunft blicken – und somit wird sich der Schadcode irgendwann nicht mehr replizieren können. Es gab auch die Frage, in welcher Stufe des Compilers der Code am Besten eingeschleust wird, denn je später man ihn einfügt, desto mehr muss man die internen Datenstrukturen des Compilers kennen.
In der Diskussion sind wir auch zu der Frage gekommen, ob ein Programm immer die selbe Binärrepräsenation hat, wenn es mit den selben Werkzeugen (Toolchain) übersetzt wurde, eben auch auf unterschiedlichen Rechnern. Im Allgemeinen ist dem auch so, nur einige Programme fügen Informationen zur Übersetzungszeit, wie zum Beispiel das Datum, den Pfad oder den Rechnernamen, dynamisch in das Programm ein, womit eine exakte Reproduktion nicht möglich ist.
Dies führte dann zu der Frage, ob Compiler deterministisch arbeiten. Denkbar ist, dass einige Aufgaben, die NP‐schwer sind, wie zum Beispiel die Registerzuweisung, mit einem probabilistischen Algorithmus gelöst werden, der eben nicht immer das selbe Ergebnis liefert.
Allerdings sollten solche zufälligen Ereignisse doch eher vermieden werden, um wirklich reproduzierbare Ergebnisse zu erhalten, denn sonst wird eine Fehlersuche zum absolutes Stochern im Nebel.
Im gcc 3.4.3 gab es wohl die Option
-fno-guess-branch-probability, mit der genau diese solche
zufällige Optimierung deaktiviert werden konnte. Im aktuellen gcc 4.4
wurde diese Optimierung wahrscheinlich entschärft, denn die
Beschreibung dieser Option klingt jetzt anders, mehr danach, dass
anhand des Quelltexts gemutmaßt, aber eben reproduzierbar gemutmaßt
wird. Siehe dazu den Abschnitt Optimize
Options im Handbuch des GCC oder den Artikel
bei Quora.
In der Diskussion im Usenet äußerte Lutz das Gerücht, dass bis 1989 ein solcher Compiler überlebt habe. Nach seinen Worten sind deterministische Algorithmen die Voraussetzung für die gleiche Binärrepräsenation. Diese sind bei nahezu allen Compilern gegeben. Daher funktioniert der Three-Stage-Test:
- Compiliere den Compiler aus dem Source mit einem Drittwerkzeug
- Compiliere den Compiler aus dem Source mit dem Compiler aus 1
- Compiliere den Compiler aus dem Source mit dem Compiler aus 2
- Wenn die Binärfiles aus 2 und 3 gleich sind, ist alles ok.