[このブログ投稿はMediumでも試験的に公開しています: https://medium.com/antirez/a-short-tale-of-a-read-overflow-b9210d339cff]

長時間動き続けるプロセスがクラッシュするのは、まったく気分の良いものではありません。ましてや大量の状態をメモリ上に抱えているプロセスであればなおさらです。だからこそ私は、大きなパフォーマンスのオーバーヘッドなしに、ページ表示ごとに新しいインタプリタと新しい状態を作り、ページ生成の最後に使ったリソースをすべて解放できるウェブプログラミングのフレームワークが好きなのです。それは本質的により信頼性の高いプログラミングパラダイムで、メモリリークやディスクリプタリーク、時折起こるランダムなクラッシュさえも深刻な問題にはなりません。しかしRedisのようなシステムソフトウェアは、そのスペクトルのまったく反対側に位置しています。決してクラッシュしてはならないものたちが集う側です。

数か月前、同僚のDvir Volkからクラッシュレポートを受け取りました。彼はRediSearchというRedisモジュールを開発していたため、クラッシュがモジュール内部のプログラミングミスによるヒープ破壊なのか、それともRedis本体のバグなのかはすぐには判断できませんでした。しかし、それはどう見てもradix treeの実装に潜む本物の問題のように思えました。

=== REDIS BUG REPORT START: Cut & paste starting from here ===
# Redis 999.999.999 crashed by signal: 11
# Crashed running the instuction at: 0x7fceb6eb5af5
# Accessing address: 0x7fce9c400000
| Backtrace:
| redis-server *:7016 [cluster](raxRemoveChild+0xd3)[0x49af53]
| redis-server *:7016 [cluster](raxRemove+0x34f)[0x49b34f
| redis-server *:7016 [cluster](slotToKeyUpdateKey+0x1ad)[0x4415dd]

radix treeの実装はmemmove()呼び出しだらけで、Redisはちょうど末尾が奇妙にゼロで埋められたメモリアドレス、0x7fce9c400000にアクセスしようとしてクラッシュしていました。最初に思ったのは、きっと自分がどこかでメモリの移動を間違え、そのせいでアドレスがゼロで上書きされ、プログラムがそのアドレスを参照しようとしてクラッシュしたのだろう、ということでした。

私は自分のradix tree実装をかなり誇りに思っています。実装そのものがすごいからというわけではありません。確かに実装するのは複雑なデータ構造ですが、ロケットサイエンスというほどではありません。誇りに思っているのは、それに付属するファズテスターのほうです。このテスターはソースコード全体をカバーできるだけでなく（これは簡単なことです）、多くの非自明な状態までカバーできます（こちらのほうがずっと面白いところです）。このファズテスターは単にクラッシュを探すためのファジングを行うのではありません。radix treeの辞書やイテレータの実装を、ハッシュテーブルとqsortを使った参照実装と比較し、まったく同じセマンティクスになるかを検証します。参照実装は短く監査しやすいものです。クラッシュレポートを受け取った後、私はファズテスターを改良し、Valgrindあり・なしの両方で何日も実行し、追加のデータモデルを書き、1億件のキーを使ったテストまで作成しました。しかし、どれだけ努力してもクラッシュを再現できませんでした。数日後には、テストしていた実装にはそもそもバグがなかったのだとわかるのですが、そのときはまだそのことに気づいていませんでした。存在しないバグを見つけられるはずがありません。結局、再現に失敗した私は諦めました。

一週間前、ほぼ同じ内容のバグレポートをさらに2件受け取りました。そしてやはり、アドレスはゼロでパディングされていました。

Dvir crash: Accessing address: 0x7fce9c400000
Issue 4605: Accessing address: 0x7f2959e00000
Issue 4642: Accessing address: 0x7f0e9b800000

ソースコード中のmemmove、memcpy、reallocの呼び出しをすべて読み直し、ファズテスターがなぜか検出できなかった何か問題がないかを探すときでした。何も見つかりませんでした。しかしRedisのクラッシュレポートをよく見ていると、面白いことに気づきました。クラッシュ時、Redisはプロセスのメモリマップ領域を報告します。例えば次のようなものです。

*** Preparing to test memory region 7f0e8c400000 (255852544 bytes)

さて、0x7f0e8c400000に255852544を足すと、結果は0x7f0e9b800000になります。これはissue 4642で報告されたクラッシュ時のアクセス先アドレスとぴったり一致します。つまりプログラムはメモリアドレスが破損したからクラッシュしたのではなく、ヒープの終端のすぐ次のアドレスにアクセスしたためにクラッシュしていたのです。他のissueについても確認しましたが、すべてのケースで同じでした。基本的にヒープの末尾は、未マップ領域の開始境界に接しており、範囲外へのアクセスが行われると検出してクラッシュさせるメモリガードとして機能していたのです。これはかつて一部のC言語用メモリサニタイズツールが採用していた一般的な手法です。そうしたツールはmalloc()の差し替え実装を提供し、アクセス不可なメモリページの境界に配置されたアドレスを返します。そうすることで、あらゆるオーバーフローが即座に検出されるのです。

プログラムがクラッシュするのは、ヒープの末尾にあるradix treeノードを解放する場合に限られていたため、問題が読み取りオーバーフローであることはすぐにわかりました。読み取りオーバーフローは通常、決して検出できません。構造体の外側にあるデータにアクセスするだけですが、それはマップされたメモリの内側なので、バグは完全に無害で沈黙したままになります。ただし、マップ領域の末尾で同じ操作を行った場合だけは例外です。ようやくどこを見るべきかがはっきりしました。次のCコードの部分です。

/* 3. Remove the edge and the pointer by memmoving the remaining children pointer and edge bytes one position before. */
int taillen = parent->size - (e - parent->data) - 1;
debugf("raxRemoveChild tail len: %d\n", taillen);
memmove(e,e+1,taillen);
/* Since we have one data byte less, also child pointers start one byte before now. */
memmove(((char*)cp)-1,cp,(parent->size-taillen-1)*sizeof(raxNode**));
/* Move the remaining "tail" pointer at the right position
as well. */
size_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0;
memmove(((char*)c)-1,c+1,taillen*sizeof(raxNode**)+valuelen);
/* 4. Update size. */
parent->size--;

私はユーザーに、クラッシュレポートを生成したredis-serverバイナリを送ってもらいました。逆アセンブルしたコードを読むと、Redisのクラッシュレポートにも含まれている多くのCPUレジスタが、まだ上記の変数の値で埋まっていることがはっきりわかりました。なお、CPUレジスタのRDI、RSI、RDXはmemmoveの最初の3つの引数を渡すために使われます。あるクラッシュでは次のようになっていました。

parent = RBP = 7f2959dffff
Checking RDI, RSI, RDX we extract the memmove() arguments:
memmove(00007f2959dffff4,00007f2959dffffd,0000000000000008);
The memmove will go out of bound accessing up to 7f2959e00004.

これで証拠は揃いました。しかしそれだけではありません。他のレジスタを調べることでノードヘッダーも再構築でき、memmoveのカウント引数がどのように求められたかを理解できました。そこには明らかに何かがおかしかったのです。基本的に、逆アセンブルされた実行ファイルが、私が読んでいたCの関数と一致していなかったのです。どうしてそんなことがあり得るのでしょうか。バッファを越えた読み取りは本来起こるはずがありません。状態は正常だったのですから。クラッシュした個体でカウントだけが誤って計算されていたのです。夜のことで、私はこの忌々しい問題に2日間休みなく取り組んでいたので、gistを作成してTwitterに投稿し、どうしてこんなCコードがコンパイラによってこんなアセンブリに変換されるのか、誰か説明してくれないかと尋ねることにしました。

幸運なことに、Node.jsで知られる友人のFedor Indutnyが助けてくれることになりました。彼はすぐに、なぜCとアセンブリが一致しないのかは極めて明白だと気づきました。私が解析していたのは正しいCコードではなかったのです……新しいバージョンの同じ関数を見ていたのでした。Fedorは手元にGCC 5.4.0を持っており、それはバグを報告してくれたユーザーが使っていたのと同じコンパイラでした。そこで彼は古いバージョンのコードをそのコンパイラでコンパイルしてみたところ、今度は2つのバージョンの生成コードが完全に一致しました。彼は私に連絡し、これが本当に最近のRedisバージョンなのか確認してきました。私は完全に確信していました。Redis 4.0.6です。しかし次第に疑問が湧いてきて、RedisのunstableブランチとRedis 4.0の間でrax.cのdiffを取ってみました。そこでわかったのは、このバグは私がStreamsの実装の過程で約10か月前にすでに修正していたということです。unstableからRedis 4.0へバグ修正をバックポートするcherry-pick作業の際、その修正はstreamsに関するコミットの中に含まれていたため、私はずっとそれを飛ばし続けていたのです。ようやくすべてがはっきりしました。私は何日も、テストしていたバージョンには存在しないバグをデバッグしていたのです。

もしそれが単なる私のつまらないミスだっただけなら、なぜわざわざこのブログ投稿を書いたのでしょうか。それは、この一連の出来事から学べる教訓があると信じているからです。

一つ目の教訓は、Redisが出力できるようなクラッシュレポートが、システムソフトウェアにとって極めて重要な資産だということです。そうしたレポートがあれば、再現できず、しかも実際の環境でごく稀にしか発生しないバグの状態を再構築できます。バグ自体はすでに修正されていましたが、私はバグレポート、レジスタダンプ、違反アドレス、コールスタックを見るだけで、正確に何が起きていたかを理解できました。

二つ目の教訓は、システムプログラミングに携わりたいなら、今日からAMD64アセンブラを学ぶべきだということです。少なくともコンパイラが出力したコードを難なく読み、何が起きているかを追える程度には。ハイゼンバグで何が起きているかを理解するには、それがしばしば唯一の方法なのです。デバッガはあまり役に立ちません。GDBはクラッシュがparent->size--という命令で起きていると主張していましたが、もちろんそんなはずはありません。しかしGDBを責めることはできません。最適化を有効にした現代のコンパイラは、ソースコードにほとんど対応付けできないようなコードを生成するのです。

もう一つの教訓は、よくできたファズテストがいかに強力かということです。ファズテスターは壊れたバージョンのバグを即座に見つけました。同様に、はるか昔に修正されたこのバグ以外にradix treeのクラッシュが一度も観測されていないという事実が、それ自体を物語っています。radix treeの実装は非常に複雑ですが、ファズテストのおかげで、この新しく複雑な実装には今のところバグがないように見えます。ファジングは単にクラッシュを見つけるためだけに行うものではないという点を強調しておきたいと思います。それはゼロデイを探したいセキュリティ分野の人には有効でしょう。システムソフトウェアにおけるファジングは、健全な操作モデルに従ってランダムな操作を実行し、その結果を参照実装と比較すべきです。

そして最後に、私自身への明確な教訓があります。次回からは、機能ブランチで作業する際に、その機能ブランチに固有でない修正を行うときは、もっと慎重になる必要があります。私はすぐにすべてを4.0にマージするつもりで作業していました。しかし実際はそうならず、radix treeの更新をStream関連の実装と同じコミットに入れてしまったことが致命的なミスでした。

最後におまけですが、賢い友人に助けてもらうことも大切です :-) 私はその時点で少し途方に暮れていましたが、Fyodorの親切な助けのおかげでパズルの最後のピースがわかり、すぐに前に進むことができました。助けを求めることを恐れないでください。システムソフトウェアに携わるなら、それが他のプログラミング分野とは大きく異なることを覚えておいてください。単に作業をして物事を前に進めればよいというものではありません。なぜバグが起きたのかを理解するために何日も費やす覚悟が必要です。再現すらできないことも多いバグをです。なぜなら、ユーザーはクラッシュするようなソフトウェア以上のものを求めるに値するからです。