どの言語でも使える C-Reduce の技法

 (bernsteinbear.com)
1 ポイント 投稿者 GN⁺ 2024-11-28 | 1件のコメント | WhatsAppで共有
  • C-Reduce は C コンパイラのバグ再現コードを縮小するツールだが、決定的な条件・高速な再現・変更可能なソースファイルがあれば、他の言語にも適用できる
  • 例として、RustPython で scrapscript を実行中に発生したバグを縮小する過程を示しており、interesting.sh が特定のエラーメッセージを探して再現可否を判定する
  • creduce --not-c interesting.sh scrapscript.py を実行するだけでファイルサイズは素早く小さくなり、序盤でほぼ 50% 縮小する進行を確認できる
  • --not-c は C 専用の縮小パスを避けるオプションであり、Python のような入力で不要な実行時間を減らすのに役立つ
  • バグが再現される条件を短いスクリプトにできるなら、C 以外の言語のバグレポートも C-Reduce でより小さく扱いやすくできる

C-Reduce を C 以外の入力に使う条件

  • C-Reduce は Regehr とその同僚が作った C コンパイラのバグ再現コード最小化 ツールである
  • 10,000 行の C ファイルが Clang のバグを引き起こすとき、巨大なファイルをそのまま送るのではなく、自動で縮小する用途に使える
  • C 専用ツールのように見えるが、次の条件があれば他言語の入力にも使える

    • 決定的な条件

      • 縮小速度に役立つ、比較的高速な再現方法
      • C-Reduce が縮小できる、1 つ以上の変更可能なソースファイル
      • 決定的な条件はループラッパーを使って確率的に模倣することもできる

RustPython バグ再現縮小の例

  • RustPython で scrapscript を実行していたところバグが発生し、これを報告するために interesting.sh スクリプトを書いた
  • スクリプトは RustPython バイナリの 絶対パス で scrapscript.py を実行した後、標準エラーを含む出力から次の文字列を探す
    • tried to push value onto stack but overflowed max_stackdepth
  • 実行コマンドは次のとおり
    • creduce --not-c interesting.sh scrapscript.py
  • C-Reduce は parallel で interestingness test を実行し、ファイルサイズを素早く縮小していく
    • 例の進行率は 0.5%、9.2%、18.1%、47.5% などと表示される
    • 数秒のうちにファイルをほぼ 50% 縮小
    • 記事を書き終える時点では 96.9% 縮小 に到達
  • --not-c を使わないと、C-Reduce は C 専用パスを多数使用する
    • Python 入力では、こうしたパスが実行時間を遅くする可能性がある
    • 結果そのものを実質的に変えることはない可能性が高い
  • 関連内容は後に Delta debugging ページへ移された

関連記事

1件のコメント

 
GN⁺ 2024-11-28
Hacker News の意見

  • 縮小後のファイルが共有されていなかったので自分で回してみた。RustPythonをビルドしてscrapscript.pyを取得し、interesting.shのパスを変えてnix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.pyで実行したところ、最終的に96.4%、7347バイトあたりで止まり、結果はhttps://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...にある

    • ふと思ったのだが、縮小の過程でプログラムが壊れてローカルマシン上で破壊的な操作をする可能性を心配している人がいた。縮小器をソース・ツー・ソースのNix derivationとして実行すれば、危険な動作を防ぎつつリモートビルダーにも簡単に配布できるのではないかと思う
    • ちなみにshrinkrayは10分ほど回すと162バイトまで縮む: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
      もっと長く置けば少し良くなるかもしれないが、ほぼ止まったように見えたので飽きて終了した

  • C-Reduceの作者であるJohn Regehrも、この用途にはShrinkrayを試してみるよう勧めている。Shrinkrayは形式に依存せず動作するよう作られており、C-Reduceが得意でない場合にも向いているツールだという: https://mastodon.social/@regehr/113489759789563570

  • John Regehrほかの著者が2012年に書いた、動作の仕組みを説明する論文がある: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

    • この論文を読んでも、どうやって可能なのかまだピンと来ない。任意のプログラミング言語についてトークン化、行の結合、トークン削除などを理解しているように見えるが、このアルゴリズムだけを別に説明した論文があるのか気になる
    • この論文はC-Reduce全体についてではなく、プロジェクトに追加されたドメイン特化のテストケース縮小器3つに関する内容である
      記憶では、C-Reduceのドメイン非特化の縮小の大半は単純な総当たりに近い

  • C-Reduceを今初めて知ったが、もう夢中になっている。初めてgit bisectを見つけた時に似ている
    いつか適した状況に出会ったときに使えるよう、頭の片隅に入れておきたい

    • 大学卒業後の最初の職場でC/C++コンパイラチームにいたとき、こういう作業を手作業でやっていた。同じことを自動化できるとはかなり驚きだ
    • 6502プロセッサ向けCコンパイラであるcc65で、コンパイラバグらしき問題に遭遇した。対象はC64、NES、Apple 1などだ
      設定してみようかと思う。VICEがホストOSのファイルへ「出力」する機能をサポートしているというので、エミュレータ上でテストを走らせられそうだ
    • ランダムなテスト入力ジェネレータと組み合わせると素晴らしい

  • デルタデバッグは新しい概念ではない: https://en.wikipedia.org/wiki/Delta_debugging
    私が作ったデルタデバッグ実装であるdeltaは19年以上前のものだ: https://github.com/dsw/delta
    Microsoftがオープンソースを「癌」と呼んでいた時代に、Microsoft Researchが私のオフィスまで人を送り、公開してほしいと依頼してきたのでオープンソースとしてリリースした。LatnerのLLVM紹介でも「標準的なdeltaデバッグツール」に言及しているので、かなりよく知られたツールである: https://aosabook.org/en/v1/llvm.html

    • C-Reduceは単純なデルタデバッグより少し洗練されている。2012年の論文「Test-Case Reduction for C Compiler Bugs」の要旨によると、C-Reduceの結果は、他の縮小器や従来コンパイラ開発者が最もよく使っていた縮小器より平均で25倍以上小さいという
      つまり、効果的なプログラム縮小には単純なデルタデバッグ以上のものが必要だという結論である。もちろんC-Reduceも今では12年もののツールだ
      同時に、リンクされているLLVMツールのBugPointはLLVM IR専用である一方、C-Reduceの方がより汎用的に見える。自動テストケース最小化ツールと手法は大多数の開発者にはまだなじみが薄いので、この分野で古くから知られているアイデアであっても、この記事は有用かもしれない

  • 前後の例がある記事を見つけた: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
    それでも各反復で何を削除するかをどうやって知るのかは、まだよく理解できない。ある程度のトークン化はあるはずだが、それが複数のプログラミング言語にわたってどう動くのかは分からない

  • creduceは素晴らしい
    私は難解なLLVMターゲットバックエンドを開発していたとき、CSmithでランダムなテストプログラムを何時間も生成するテストスクリプトを書いていた。クラッシュすると自動でC-Reduceを走らせ、調査用のファイルとして残してくれたので、本当に大いに助かった

  • SQL でもうまく動作する。実務で使っており、https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu... で知った

  • C 以外の言語でも動作する理由を説明しなければ信じにくい主張だ。嘘だとは思わないが、LLM なしでそれをやるというのは戸惑う

    • 短く言うと、一部の縮小パスは C 系言語にかなり一般化でき、そうしたパスが最も効果的な部類に入る
      例えば、C 方式で入力をトークン化したうえで長さ 1〜13 程度の塊をランダムに捨てる方法は、C に似た言語の大半が似たトークン化規則を持つため、不要な修飾子や属性を取り除くのによく効く。対応の取れた括弧 ()、{}、[] の単位を削除するパスも、ほぼすべての言語で有用だ。コメントと空白の削除も、多くの言語が C と同じ /* */、// スタイルを使うので効果的だ
      実際、完全に C/C++ 専用と言えるパスは多くない。経験上、creduce の大きな弱点の一つは、テンプレートを除去する縮小ステップ、つまり比較的自動化しやすそうに見える作業が本当に苦手な点だ
    • asmeurer がリンクした PLDI 論文に目を通すことを勧める。よく要約されている
      一部の変換は Clang フロントエンドを使うかなり C 特化のものだが、一部はかなり汎用的で、Algol 系言語ならおおむね動作する可能性が高い。モジュール式のツールなので、望むなら他の言語を理解する変換を追加することもできる
    • これは昔ながらの コンピュータサイエンスに近い。HN がもうそうした伝統的なコンピュータサイエンスを忘れてしまったのでないことを願う
      ここで言っているのはアルゴリズムのようなもので、不気味な機械学習ではない。Prolog を AI に使うようなものも含まれるが、AI を作る目的ではうまく機能しないという小さな欠点がある
    • 動作の仕組みを理解していないと、こういう形で使っても安全なのか分からない。creduce が変形された入力スクリプトを実行して、自分のファイルを消したり昼食を食べ尽くしたりすることもあり得るのだろうか？
    • 論文を見ずに推測すると、入力サイズを小さくする方向の変異を適用するファザーに似ている気がする

  • dustmite と比べるとどうなのか？ https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...