Zusammenfassung

  • Am 27. Oktober 1980 akzeptierten und verbreiteten ARPANET-IMPs immer wieder Routing-Updates mit den Nummern 8, 40 und 44: Der Sechs-Bit-Vergleich ließ jeden dieser Werte neuer als einen anderen erscheinen.
  • Eric Rosens wahrscheinliche Rekonstruktion in RFC 789 führt auf eine durch einen Hardwarefehler veränderte Wiederholung zurück. Die Schleife füllte Puffer, störte Leitungsprüfungen und machte das Netz selbst zu einem langsamen Kanal für den Wiederherstellungs-Patch.

Der Zugang antwortete, doch die IMPs erreichten einander nicht

Die ersten Symptome sahen nicht wie eine falsch berechnete Route aus. Manche Nutzer erreichten über eine Telefonleitung noch einen Terminal Interface Processor (TIP). Wollten sie jedoch einen Rechner an einem anderen Interface Message Processor (IMP) erreichen, erschien „net trouble“. Bestehende Verbindungen brachen ab. Der TIP konnte dem Nutzer am Telefon antworten, während zwischen den IMPs kein brauchbarer Pfad mehr bestand. Diese Unterscheidung lenkte die Fehlersuche von der lokalen Zugangsstelle auf das Netz zwischen den Knoten.

Eric C. Rosen rekonstruierte den Vorfall in RFC 789 unter anderem anhand von Speicherauszügen mehrerer IMPs. In fast allen füllten wartende Routing-Updates die Puffer. Sie schienen vom IMP 50 zu stammen. Dieses Gerät war kurz zuvor ausgefallen und während des Netzausfalls bereits vom Netz getrennt. Auch sein unmittelbarer Nachbar, IMP 29, hatte einen Hardwarefehler und verlor Bits. Ein Neustart benachbarter IMPs half nicht dauerhaft: Sobald sie wieder verbunden waren, erhielten sie dieselben Updates von ihren Nachbarn.

Ein Vergleich, der im Kreis lief

Jeder IMP verschickte regelmäßig Informationen über Leitungen und Verzögerungen. Die Updates wurden weitergeleitet, damit die Knoten ein gemeinsames Bild des Netzes behalten konnten. Jedes Update trug eine sechs Bit breite Sequenznummer, die modulo 64 erhöht wurde. Der Empfänger musste entscheiden, ob eine neue Nachricht desselben Ursprungs aktueller war als die zuvor akzeptierte.

Die Regel verwendete die Hälfte des Zahlenraums, um den Umlauf über null einzuordnen. Ein Wert galt als später, wenn er höchstens 32 Positionen vorauslag oder nach dem Umlauf um mehr als 32 Positionen versetzt war. Das war weder eine Datumsangabe noch eine Uhr. Bei den drei beobachteten Werten entstand jedoch ein Kreis: 44 war später als 40, 40 später als 8 und 8 später als 44.

In den Speicherauszügen standen die Updates in den Warteschlangen als 8, 40, 44 und dann wieder 8, 40, 44. Sie waren bis auf die Sequenznummer identisch. Jedes konnte ein anderes als „neuesten“ Stand verdrängen und erneut an die Nachbarn gesendet werden. Jeder IMP befolgte lokal die vorgesehene Regel. Der Fehler lag darin, dass Werte zusammentrafen, die der normale Erzeugungsprozess auseinanderhalten sollte.

Rosen stellte den Ursprung der drei Werte nicht als gesicherte Tatsache dar. Seine wahrscheinlichste Erklärung war, dass ein Update mit Nummer 44 aus gespeicherten Tabelleninformationen für eine Wiederholung rekonstruiert wurde und verlorene Bits die Nummer erst in 40, dann in 8 verwandelten. Übertragene Pakete hatten eine Prüfsumme; die Tabellen, aus denen eine Wiederholung neu erstellt wurde, wurden nicht ständig geprüft. Eine dauernde Prüfung hätte knappe Rechenzeit oder Speicher beansprucht. Rosen erwähnte auch die umgekehrte Möglichkeit: 8 könnte der Ursprungswert gewesen sein, dem Bits hinzugefügt wurden.

Die Schleife ist in den Auszügen dokumentiert; der konkrete Hardwarefehler bleibt eine Schlussfolgerung.

Aus einer Routing-Schleife wurde Ressourcenmangel

Die Updates wurden mit hoher Priorität verarbeitet. Während sie kreisten, beanspruchten sie Prozessorzeit und Puffer. Den IMPs fehlten dadurch Puffer für HELLO- und I-HEARD-YOU-Nachrichten, mit denen Nachbarknoten den Zustand einer Leitung prüften. Ohne diesen Austausch konnte das Leitungsprotokoll nicht arbeiten; die Software erklärte die Verbindungen für ausgefallen. Der Kontrollverkehr veränderte damit die Topologie, die andere IMPs zu messen versuchten.

„Das Routing berechnete einen falschen Weg“ trifft Rosens Diagnose nicht. Die Routen und der Code blieben im Rahmen der festgelegten Regeln konsistent. Der Hardwarefehler erzeugte einen unerwarteten Zustand; die regelkonforme Verarbeitung dieses Zustands verbrauchte dann zu viele Ressourcen, ohne ausreichend begrenzt zu werden. Der Vorfall beweist weder einen Angriff noch beschreibt er unmittelbar heutiges Internet-Routing. Er zeigt, wie fehlerhafte gespeicherte Daten durch Wiederholungen verstärkt werden und einen lokalen Defekt in einen größeren Ausfall verwandeln können.

Die Reparatur musste durch das gestörte Netz

Die Betreiber spielten einen Patch auf die IMPs, der Updates von IMP 50 verwarf, obwohl dieses Gerät bereits offline war. Normalerweise konnte das Network Control Center einen solchen Patch in wenigen Minuten verbreiten. Während des Ausfalls konnte die Fernsteuerung der meist unbesetzten IMPs drei bis vier Stunden dauern, weil sie über das Netz selbst lief. Der Wiederherstellungsweg war von der Infrastruktur abhängig, die er wiederherstellen sollte. Der Patch war erfolgreich; Rosen berichtete von keinen bleibenden Schäden über den Ausfall hinaus.

Rosen schlug vor, eine Grenze in LATER enger zu fassen, Fehlererkennung und -korrektur der nächsten C30-Hardware zu verbessern und einen übermäßig ressourcenhungrigen Hochprioritätsprozess zu erkennen, damit der IMP in einen fernsteuerbaren Zustand versetzt werden könne. Die Maßnahmen zielten auf unterschiedliche Ebenen: den bekannten Kreis verhindern, den Hardwarefehler erkennen und den Knoten wiederherstellbar machen. Keine versprach, alle seltenen Fehler auszuschließen.

Quellenlage und Grenzen

Rosen veröffentlichte den Bericht in der Januar-Ausgabe 1981 von SIGSOFT Software Engineering Notes und verbreitete ihn als RFC 789. Er ist die maßgebliche Quelle zum Vorfall und trennt Beobachtung von Vermutung. Der Artikel von McQuillan, Richer und Rosen vom Mai 1980 dokumentiert frühere Tests des neuen Algorithmus im laufenden Netz. Daraus folgt nicht, dass die seltene Verbindung aus beschädigten Tabellendaten und einer Sequenzschleife bereits getestet worden war. Eine kurze Gedenknotiz des Computer History Museum bezeichnet die Werte als Zeitstempel; RFC 789 nennt sie sechs Bit breite Sequenznummern.

Quellen: RFC 789; McQuillan, Richer und Rosen, „The New Routing Algorithm for the ARPANET“; Eintrag des Computer History Museum zum 27. Oktober; gehosteter Scan des Artikels von 1980 bei IPCOMPRO; Heng Lus Vorrang des laufenden Codes, nur als redaktionelle Perspektive.