Malloc が Serenity の JPGLoader を壊した事件、あるいは: 宝くじ当選の秘訣 (2021)

 (sin-ack.github.io)
1 ポイント 投稿者 GN⁺ 2024-07-08 | 1件のコメント | WhatsAppで共有
  • SerenityOS の JPG の色異常 は RGB/BGR の引数順の問題のように見えたが、実際には JPGLoader が順序を必要とするコンポーネントを HashTable の反復順に任せていたことに端を発していた
  • AK+LibC に malloc_good_size() が導入されたことで、Vector と HashTable が実際の malloc チャンクサイズを活用するようになり、その結果 HashTable のバケット数 が変わって潜在バグが表面化した
  • 既存コードは JPG の Y、Cb、Cr コンポーネントを偶然正しい順序で読んでおり、int_hash の結果とバケット数がうまく噛み合っていたおかげで ハフマンストリーム 処理の不具合が隠れていた
  • 原因追跡は JPGLoader.cpp が最近変更されていない状態から始まり、1000 個のコミットを bisect する中で、AK の変更のために約 3400 ファイル規模の OS を何度もフルリビルドする必要があった
  • 最終的な修正はコンポーネントを 決定的な順序 で走査するようにすることであり、単に色の引数順だけを入れ替える応急処置では、次に順序が変わったとき同じ問題を再発させる可能性があった

RGB/BGR の取り違えのように見えた JPG の色異常

  • SerenityOS で JPG 画像を開くと、色が正しく表示されない問題が発生した
  • JPGLoader.cpp で Color コンストラクタの引数順を入れ替えると、画像は正常に見えた
    • 既存コード: Y、Cb、Cr の順で渡す
    • 一時的な変更: Cr、Cb、Y の順で渡す
  • しかし、最近の JPGLoader.cpp に対する最後の non-revert 変更は Git 上で 1 か月以上前であり、1〜2 週間前には JPG の背景画像が正常に見えていた記憶があった
  • そのため、単純な 色チャネル順の誤り ではなく、別の変更が既存のバグを露出させた可能性が高かった

AK の変更のせいで難しくなった bisect

  • SerenityOS は独自の標準ライブラリである AK (Agnostic Kit) を使っている
    • AK は C++ STL と似た役割を持つが、同じリポジトリ内で OS のコードと一緒に変更される
  • AK が変わると影響範囲が広い
    • 標準ライブラリはほぼすべてのコードから取り込まれる
    • C++ テンプレートは定義をヘッダに置く必要があるため、AK のヘッダ変更は広範囲な再コンパイルを引き起こす
  • AK の変更を含むコミットをまたぐたびに、OS 全体を再ビルドしなければならなかった
    • 執筆時点で約 3400 ファイル
    • 1000 個のコミット範囲を bisect する間、2011 年製 Sandy Bridge Mobile ノート PC でフルビルドを 4〜5 回実行した
  • ccache もこのケースには対応できず、SerenityOS プロジェクトの変更速度の速さのため、AK はおよそ 100 コミットごとに 1 回の割合で変更されていた

malloc_good_size() が露呈させた潜在的な問題

  • 1000 個のコミットを bisect した末に、JPG の色を壊した変更は JPGLoader ではなく AK+LibC 側にあると分かった
  • 問題を表面化させたコミットは f89e8fb71a4893911ee5125f34bd5bbb99327d33
    • タイトル: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
    • 作成時刻: 2021 年 5 月 15 日
  • このコミットでは macOS API である malloc_good_size() を実装した
    • 要求した割り当てサイズに対して、実際の割り当てサイズを返す
    • たとえば 35 バイト要求して内部的に 64 バイトのチャンクが使われるなら、余った 29 バイトを活用できる
  • 変更後、Vector、HashTable などは malloc チャンク内の利用可能メモリをより有効に使うようになった
  • 直前のコミットでは JPG 画像が正常に表示されていたため、この変更が既存の潜在バグを露出させたと絞り込めた

HashTable の容量に依存していたデコード

  • 当初は、JPGLoader や上位コードが Vector の容量に誤って依存し、直接書き込みをしている可能性を疑った
  • 関連する変更は HashTable と Vector の両方にあり、どちらも JPGLoader のコードで使われていた
  • 試しに HashTable 側の kmalloc_good_size() 適用行を削除して再ビルドすると、問題は消えた
    • 削除したコードは、新しいバケット容量を実際の割り当てサイズに合わせて調整する部分だった
  • この結果により、HashTable の バケット数の変化 が JPG デコード結果に影響していることが確認された
  • HashTable は連続したデータストリームのように使うコンテナではないため、容量や反復順に依存すべきではない構造だった

JPG コンポーネントが処理されていた方法

  • 従来の JPGLoader は JPG ファイルの Start of Frame セクションでコンポーネント情報を読み取り、Component 構造体に保存していた
  • 各 Component は JPG ファイル内での位置を表す serial_id を持っていた
    • JPG コンポーネントの順序は通常 Y、Cb、Cr であるべきだった
  • これらのコンポーネントは HashTable に保存されていた
    • その後、Start of Scan セクションのコンポーネント順と比較して、期待される順序かどうかを確認するために使われていた
  • デコード段階では、これらのコンポーネントを走査しながらマクロブロック変換に必要な情報を使っていた
  • 問題は、順序が重要なコンポーネントを HashTable に入れ、デフォルトのイテレータで走査していた点にあった

壊れたコミットと正常なコミットでの走査順の違い

  • 色が壊れるコミットでは、デバッグ出力はコンポーネントを次の順で走査していた
    • 0
    • 2
    • 1
  • 直前の正常なコミットでは順序が異なっていた
    • 0
    • 1
    • 2
  • この違いは、色チャネルが反転したように見える結果とつながっていた
  • CxByte と一緒にコンポーネント順を手動で入れ替えてみていたところ、次のエラーが発生した
    • Huffman stream exhausted. This could be an error!
    • Failed to build Macroblock 3277
  • このエラーは、JPG デコードが ストリーム順序 に敏感であることを示し、コンポーネントの走査順こそが核心的な原因であることを裏付けた

偶然うまく合っていた HashTable の順序

  • 根本原因は、順序を必要とするオブジェクトを HashTable に保存し、デフォルトのイテレータで走査していたことだった
  • JPG コンポーネント ID のハッシュが int_hash を通ってバケット選択に使われていた
  • 従来は 2 つの偶然が同時にうまく噛み合っていた
    • 0、1、2 の値に対する int_hash の結果が安定していた
    • AK::HashTable のバケット数が、コンポーネントが正しい順序に配置されるのにちょうどよかった
  • この偶然のおかげで、JPGLoader は各コンポーネントに対して正しい順序でハフマンストリームを読み取り、バグは初期の段階から隠れていた
  • malloc_good_size() の導入で HashTable のバケット数が変わると、コンポーネント順も変わり、赤と青のチャネルが入れ替わった画像が現れた

決定的な走査で直した最終修正

  • 約 10 時間のデバッグの末に修正コミットが作られた
  • 修正コミットは a10ad24c760bfe713f1493e49dff7da16d14bf39
    • タイトル: LibGfx: Make JPGLoader iterate components deterministically
    • 作成時刻: 2021 年 5 月 31 日
  • 修正の要点は、JPGLoader がコンポーネントを 決定的な順序 で走査するようにしたことだった
  • 単に Color の引数順を入れ替える方法でも当面は画像を正常に見せられたが、その後別の変更で走査順が再び変われば、また壊れる可能性があった
  • 小さな表示不具合のように見えた問題が、コンテナの走査順への誤った依存と割り当てサイズの変化が組み合わさることで表面化した事例だった

関連記事

1件のコメント

 
GN⁺ 2024-07-08
Hacker News のコメント

  • 多くのハッシュテーブル実装がアルゴリズムにランダム要素を入れる理由の一つがこれです。
    実行するたびに要素の順序が変わるので、うっかり順序に依存しているとすぐ問題が表面化します。
    ハッシュアルゴリズムが固定されていると、同じバケットに集中するキーを作ってサービス拒否攻撃に悪用できますが、こうしたセキュリティ問題もかなり防げます。

    • 最近は逆に、ハッシュテーブルが常に挿入順で走査されることを保証する実装も多いです。
      こちらのほうが好みです。ソート済みマップが必要なのか、未ソートのマップが必要なのかを毎回判断しなくて済むからです。
      未ソートのマップで十分だと思っていたら、微妙な理由で間違っていたことが何度かあります。
    • ランダム要素が強制的に指定・保存・ログ記録・再現できるシードなら問題ありません。
      そうでなければ、別の問題のデバッグをはるかに難しくするので、本当に悪い考えです。
      ランダム性は味方ではなく敵です。
      20年ほど前、Java の Web サーバーを攻撃する際に URL パラメータを操作して全部同じバケットに入るようにする手法があり、大規模なサービス拒否攻撃になりました。
      記憶が正しければ、PHP の Web サーバーもまったく同じセキュリティ問題を抱えていました。
      ハッシュテーブルにシードを入れて修正され、そのシードは当然開発者が制御できました。ランダム性は味方ではなく敵だからです。

  • これはむやみに二分探索式の bisectをするより、もう少しデバッグしていれば時間を節約できた事例に見えます。
    コンポーネントの順序を出力するログは、結局いずれ入れる必要がありました。

  • デバッグも良かったですが、コミットメッセージも素晴らしいです。
    原因と修正内容を数段落にうまく凝縮しています。

  • 長く待てば、C++ にも malloc_good_size に相当する機能が入る予定です。
    https://github.com/cplusplus/papers/issues/18

  • タイトルには [2021] が必要です。

  • これは Gunnar のせいではありません。問題は順序を持つデータをハッシュファイルに保存した側にあります。
    何十年もこの仕事をしていると、メモリ配置が変わったことで隠れていたバグが表面化する状況を何度も経験しました。
    そのたびにデバッグに数時間から数日かかります。
    プログラミングが難しくなければ、私たちは必要とされなかったでしょう。ただ、この文が大規模言語モデルの時代にどれだけ持ちこたえるかは分かりません。

    • その通りです。仮に Gunnar のせいだったとしても、コミットメッセージにわざわざ書く必要はなさそうです。
      Gunnar は何かを改善し、その過程で古い壊れたコードの問題が明らかになっただけです。
      なのにその努力の対価として “Gunnar, I like you, but please don't make me go through this again. :^)” のような言葉を受けることになります。
    • 大規模言語モデルがバグのあるコードで学習される限り、バグのあるコードを提案するでしょう。
    • その通りです。そしてタイトルとは違い、malloc() のせいでもありません。

  • SerenityOS には、テスト用リソースや PC を互いに助け合う人たちがいると認識しています。

  • 2011年の Sandy Bridge Mobile ノート PC で SerenityOS を最初から4〜5回ビルドしたというのは、Windows 3.1 と Windows 95 の間の時期に出たコンピューターで Windows Vista 開発をしようとするのに似ています。

    • 時間間隔としては合っていますが、実際の性能基準では違います。
      2011年以降、CPU は相対的にそこまで大きく変わっていませんが、Windows 3.1 から Vista の間には x64 が普及し、マルチコア CPU が一般化しました。
    • 良い比較です。開発者の CPU はおおよそ13年前のものです。
      Vista は2007年初めに国際リリースされたので、リリース時点で13年前の CPU なら1994年製で、初代 Pentium が出てから1年ほど経った時期です。
      当時はまだ、信頼できる 486 DX2-66 を使っている人も多くいました。
      13年前の CPU が今日のモダンなプロジェクト作業にも使えるというのは、かなり印象的です。当時は同じことを言うのは難しかったでしょう。
      今日発売される CPU も、2037年以降まで満足に使えることを願います。
    • この1年、メインのデスクトップとして2011年製 Lenovo i5 に Windows 11 を入れ、デュアルモニターで使ってきました。
      Visual Studio も問題なく動き、Photoshop もシステム内 AI ツールがごくわずかにもたつく程度です。
      Chrome タブはおそらく200個ほど開いていて、Slack、WhatsApp、テスト用ブラウザ3つも一緒に使っています。
      CapCut は 4K 編集のときにもう少し速ければと思いますが、複雑な 2K プロジェクトには十分耐えます。
      複雑な After Effects プロジェクトでだけ少し限界に当たりました。あれは嫌がっていました。
      アップグレードは必要ですが、実質的にゴミ箱から救い出したシステムとしてはかなり悪くありません。

  • “Alien Lenna” を見てデジャヴを感じましたが、やはり以前に見てコメントまでしていた記事でした。
    https://news.ycombinator.com/item?id=27374942 (2021)