要約

  • 1980年10月27日、ARPANETのIMPは番号8、40、44の経路更新を受け入れて再送し続けた。六ビットの比較規則が、三つの値をそれぞれ別の値より新しいと判定したためだ。
  • Eric RosenのRFC 789は、ハードウェア故障で再送データが変化した可能性を示す。更新の循環がバッファを使い切り、回線確認を妨げ、復旧用パッチの配送までネットワーク頼みで遅らせた。

端末には応答しても、IMP間はつながらない

最初に見えた症状は、経路表の単純な誤りではなかった。電話回線でTerminal Interface Processor（TIP）につながる利用者はいたが、別のInterface Message Processor（IMP）配下のホストへ接続しようとすると「net trouble」と表示された。すでに成立していた接続も切れた。TIPは利用者に応答できても、IMP間の経路が失われていたのである。この差が、障害の焦点を利用者側の入口からノード間の網へ移した。

Eric C. Rosenは、複数のIMPから採取されたメモリダンプなどを使い、事故をRFC 789にまとめた。ほぼすべてのダンプで、処理待ちの経路更新がバッファを埋めていた。更新はIMP 50から来たように見えた。IMP 50は障害直前から不調で、全網障害の間はネットワークから切り離されていた。その隣のIMP 29もビットを落とすなどのハードウェア不調を抱えていた。近くのIMPを再起動しても、接続し直すと隣接ノードから同じ更新を受け取ったため、状態はすぐ戻った。

8が44より新しいという循環

各IMPは回線の遅延などを示す経路更新を定期的に送り、網内へ伝播させていた。更新には六ビットのシーケンス番号が付き、64を法として増加した。受信側は、同じ発信元から以前受け取った更新より今回の方が新しいかを、値の半分の範囲を使って比較する。

これは日付や時計ではない。だが事故の三つの値には、44が40より新しく、40が8より新しく、8が44より新しいという関係が成立した。比較規則が一周してしまう。メモリダンプのキューには8、40、44がこの順で並び、同じ並びが続いていた。三つの更新はシーケンス番号以外は同一だった。各更新が別の更新を「最新」の位置から押し出し、再び近隣のIMPへ送られた。

Rosenは、三つの値が生じた経路を確定事項として述べていない。最もありそうな説明は、番号44の更新を再送時に内部テーブルから再構成し、失われたビットによって番号が40、さらに8へ変わったというものだ。送信パケットにはチェックサムがあったが、再送パケットは保持済みの表から作り直され、その表自体は常時チェックされていなかった。頻繁な照合にはCPU時間かメモリが必要だった。Rosenは逆の可能性、つまり8が元の値でビットが加わった可能性も記している。三つの値が循環したことはダンプに残るが、最初のビット障害は推定である。

経路ループから資源枯渇へ

経路更新の処理は高い優先度で実行された。更新が循環するにつれ、CPUとバッファの大部分がその処理に費やされた。IMPは、隣接回線が動作しているか確認するHELLOとI-HEARD-YOUのメッセージを受信するバッファも確保できなくなった。隣接確認が進まないと、ソフトウェアは回線を停止扱いにした。制御情報のループが、他のIMPが測ろうとしていたネットワーク構成を変えてしまったのである。

Rosenの説明は「ルーティングが誤った道を計算した」という単純な話ではない。経路とコードは定義された規則の範囲で整合していた。ハードウェア故障が通常想定されない状態を作り、規則どおりの処理が十分な抑制なしに資源を消費した。この事例は攻撃の証拠でも、現在のインターネットの経路制御を直接説明するものでもない。稼働中のシステムでは、破損した状態が再送で増幅され、局所的な故障が広域のサービス停止に変わり得ることを示す。

修復も故障中のネットワークを通った

運用者はIMP 50からの更新を無視するパッチをIMPに配布した。発信元であるIMP 50はすでに停止していたが、この措置で循環を断てた。平常時ならNetwork Control Centerから数分で全IMPへ配布できた。ところが、通常は無人のIMPを遠隔制御する経路そのものがネットワークだったため、障害時の配布には三、四時間かかることがあった。復旧の道筋が、復旧対象のインフラに依存していた。パッチは成功し、Rosenによれば停止以外に後遺症は残らなかった。

RosenはLATER比較の境界を狭める案、次世代C30ハードウェアによる単一ビット誤りの検出・訂正、そして高優先度プロセスの資源消費を監視してIMPを遠隔制御可能な状態へ移す案を示した。既知の循環を防ぐこと、物理故障を検知すること、ノードを回復可能にすることは、別々の対策である。どれも、あらゆる稀な故障を消し去る保証ではない。

証拠とその限界

Rosenの報告は1981年1月のSIGSOFT Software Engineering Notesに掲載され、RFC 789としても配布された。事故の主要資料であり、観察と推定を区別している。McQuillan、Richer、Rosenが1980年5月に発表した論文は、導入済み経路アルゴリズムを実網で試験した記録を含む。しかし、内部テーブルの破損とシーケンス番号の循環が重なる稀な条件まで試験済みだったとは示していない。Computer History Museumの短い記念記事は値を「タイムスタンプ」と呼ぶが、RFC 789は六ビットのシーケンス番号と説明する。

出典：RFC 789；McQuillan, Richer, Rosen, “The New Routing Algorithm for the ARPANET”；Computer History Museumの10月27日記事；1980年論文のIPCOMPRO掲載スキャン；Heng Luの「実行中のコードを優先する」論考は編集上の視点としてのみ参照。