テストケースリデューサは過小評価されているデバッグツール

 (tratt.net)
1 ポイント 投稿者 GN⁺ 5 시간 전 | 1件のコメント | WhatsAppで共有
  • 大きな入力で問題を引き起こしている箇所を見つけるとき、テストケースリデューサは入力を自動で縮小し、デバッグを容易にする
  • リデューサはプログラム、入力、興味性テストを受け取り、より短い候補入力が同じ問題を再現するかを繰り返し確認する
  • 単純な行削除リデューサでも、/usr/share/dict/words から長い単語を1つだけ残せるほか、Cの例では10秒未満で78行を54行に縮小できる
  • 興味性テストは、過度な縮小、遅い実行、無限実行、並列実行環境のため、正確かつ高速に書く必要がある
  • 入力長だけでなく、エラー発生頻度や実行トレース長のような指標を興味性テストに組み込むと、非決定的バグや大きなトレースログのデバッグに役立つ

テストケースの縮小

  • 大きな入力でプログラムがクラッシュし、入力のどの部分が原因かわからないときは、入力を縮小すると問題の原因を把握しやすくなる
  • 手動縮小は、テキストエディタで入力の一部を削除し、その後も同じクラッシュが維持されるか確認する方式である
  • 手動縮小では、人が多くの削除機会を見逃しやすく、削除後にプログラムが正常終了したり別の正常なエラーを出したりすることがある
  • 離れた位置にあるA部分とB部分を一緒に削除して初めて効果がある場合、探索空間は大きく増える

テストケースリデューサの基本構造

  • テストケースリデューサは、プログラム、入力、興味性テストを受け取り、入力をより短くするツールである
  • 興味性テストは、縮小された入力が注目しているエラーを再現した場合は0を返し、そうでなければ0以外の値を返す
  • テストケースリデューサでは95〜99%の縮小が珍しくなく、デバッグを大幅に容易にできる
  • リデューサは、入力のどの部分を取り除くべきかを意味的に理解していなくても動作する

  • 単純なリデューサの例

    • 例のプログラムはファイルから行を読み、長さが25を超える行があれば Word too long を出力する
    • 興味性テストは、プログラム出力に Word too long があれば0、なければ1を返す
    • 単純なPythonリデューサは入力を行単位で読み、1行を削除した候補入力を一時ファイルに書いたうえで興味性テストを実行する
    • 候補入力が興味深ければ現在の入力をその候補に置き換え、これ以上縮小できなければ結果を stdout に出力する
    • /usr/share/dict/words に対して実行した結果、antidisestablishmentarianism だけが残る

より強力なリデューサとShrink Ray

  • 78行のCプログラム例では、FAST=0 と FAST=1 の設定で異なる出力が出る問題を扱う
  • 興味性テストは2つの設定でコンパイルしたうえで、FAST=0 の出力が 0d754a56 であり、FAST=1 の出力がその値と異なる場合にのみ成功する
  • 単純なリデューサは、10秒未満で78行のC入力を54行に縮小し、行数ベースで約30%削減する
  • 興味深い候補を見つけるたびに先頭行から削除をやり直すよう i=0 を追加すると、実行時間はほぼ10倍になり、さらに3行減らせる
  • Shrink Ray は複数の縮小ルールと並列実行を提供し、--no-clang-delta を付けるとC向けの特別な知識を使わない
  • Shrink Rayは約15分後にバイト数ベースで60%超の縮小を達成し、別の事例では約20分後に90%縮小を見つけ、その後99%までさらに縮小した
  • Shrink Rayは標準的なコメント構文を理解して初期段階で削除を試みるほか、整数をより小さい値に縮める試行も行う

興味性テスト作成の難しさ

  • テストケースリデューサは興味性テストに文字どおり従うため、テストが誤って通ると、狙った地点よりさらに縮んでしまう 過度な縮小 が起こる
  • Shrink Rayは、興味性テストが空入力を受け入れるかどうかを明示的に検査しており、この状況はしばしば起こりうる
  • Cの例で単に2つの出力が違うかだけを確認すると、重要でない、あるいは誤解を招く出力差まで興味深い入力として分類されうる
  • test "$slow_out" = "0d754a56" という検査は、低速版が実際に期待どおり動作していることを確認し、過度な縮小の可能性を下げる

  • 速度とタイムアウト

    • 興味性テストが高速なら、リデューサは1秒あたり数百回実行できる
    • 中規模の例でも数十万回の縮小試行につながることがあり、興味性テストの最適化は全体時間に大きく影響する
    • 自動コアダンプ生成を無効化することで、興味性テストを約3倍高速化した事例がある
    • リデューサは i-=1 のような行を取り除き、終了するプログラムを無限実行するプログラムに変えてしまうことがある
    • プログラムが0.1秒で実行できるのにタイムアウトを60秒にすると、全体の縮小は大幅に遅くなる
    • 高速なプログラムでは timeout を1〜2秒に切り上げ、それ以外では初回実行時間の約1.5〜2倍に設定する方法が使われる

  • 並列実行

    • Shrink Rayのようなリデューサは、興味性テストを並列に実行する
    • Shrink Rayは各興味性テストを一時ディレクトリ内で実行し、そのディレクトリを自動的にクリーンアップする
    • 一時ディレクトリだけでは不十分な場合もあり、必要な対策はケースごとに異なる

興味性テストで決定性を誘導する

  • 例の断片では len([])==0 によりゼロ除算エラーが発生するが、random.random() < 0.33 条件のため、問題は実行の約3分の1でしか起きない
  • 非決定的バグでは、エラーがランダムに現れたり消えたりするため、仮説検証が難しくなり時間もかかる
  • リデューサが random.random() 呼び出しを削除したり条件式を変更したりすると、非決定的なエラーが決定的なエラーに変わることがある
  • 実際の非決定性は、入力の複数部分が不利に相互作用していることが多く、除去が難しい場合がある
  • テストケースリデューサは、入力長を「より良い」ことの代理指標として使うヒルクライミングアルゴリズムのように動作する
  • ヒルクライミング的なアプローチは局所最適に陥りやすく、短い入力が常にエラー探索に適しているとは限らない

  • 反復実行方式

    • 非決定的バグを扱うときは、興味性テストが入力を複数回実行し、注目するエラーが1回以上発生すればその入力を受け入れる方式が使われる
    • この方式はエラー発生頻度を高めるのに役立つことがある
    • 1回以上発生すれば通るテストは非決定的な入力も受け入れるため、縮小が進むにつれて非決定性がかえって増すことがある
    • より厳格な方式は、n 回の反復すべてでエラーが発生したときだけ入力を受け入れるテストである
    • 厳格なテストでは初期入力が通る確率が低く、Shrink Rayを開始しにくくなり、例の3回反復条件では初期通過確率は3.6%である
    • 実用的な回避策として、まず「n 回中1回以上エラー」のテストで始め、エラーがより頻繁に起きる縮小入力が得られたら「n 回連続でエラー」に切り替える方法がある

グローバルカウンタと他の目標指標

  • 手動介入は強力だが、Shrink Rayを見張っている必要があり、介入のタイミングを逃しやすい
  • 入力長ではない別の性質でリデューサを誘導したいなら、単一の興味性テストの中でその性質を強制できる
  • ykデバッグでは、入力長よりも実行トレース長、つまりプログラムが実行した命令数に近い値のほうが重要なことがある
  • YKD_LOG="$t:jit-asm" の出力は、テキストのトレースIRと機械語命令をファイルに書き出し、短い jit-asm 出力はデバッグを容易にする
  • wc -l はログファイルの行数を数え、トレース長に近い代理指標として使われる
  • 興味性テストは、現在のトレース行数が以前の最小行数より大きければその入力を興味深くないものとして扱い、最小値は /tmp/global_best に保存する
  • この方法は並列縮小では安全ではなく、リデューサの呼び出し方に関する仮定も含むが、使い捨てスクリプトとしては許容できる不完全さとみなされる
  • ykのセグフォルト事例では、通常の縮小では4万行のトレースが残ったが、この手法ではより大きい縮小入力の代わりに1.01万行のトレースを生成し、30分以内に根本原因のバグを突き止められた

要点の整理

  • テストケースリデューサはコンパイラ作者だけに有用な道具ではなく、コンパイラ以外の問題にも使える
  • 入力長を減らすという基本目的以外にも、エラー頻度、経過時間、非決定性の度合い、トレース長といった性質を興味性テストで誘導できる
  • 興味性テストの正確さ、実行速度、タイムアウト、並列実行時の安全性が、リデューサの実際の効果を左右する
  • リデューサは入力やプログラムの意味をほとんど理解していなくても、問題をより小さな形で保ち、デバッグの生産性を高められる

関連記事

1件のコメント

 
GN⁺ 5 시간 전
Lobste.rsの意見

  • 純粋に気になるのだけど、自動テストケース縮小の価値を認めない人なんているのだろうか？ 「過小評価」という言い方は、テストケース縮小を常に欲しいと思わない人がいるかのように聞こえる
    たとえバグをすぐ特定できるとしても、回帰テスト用には縮小されたケースが必要なのでは？

    • たいていの開発者は、これを手法として考えたことすらない気がする
    • 記事の1行目は「Test-case reducers are less well known than they should be, [...]」となっているが、ここ数年ずっと人にファジングとプロパティベースドテストを使うよう勧めてきた立場から見ても、まさにその通りだった
      どちらも失敗例の縮小、つまり “shrinking” のような仕組みをよく含んでおり、そのおかげではるかに実用的に使える
    • ファザーではだいたい知られている。ファザーが失敗例を見つけたあと自動で縮小してくれて、その部分はとてもよく動く
      ただ、ファジング全般、とくに AmericanFuzzyLop と AFL++ を使った経験では、設定があまりにも苦痛で、たいてい避けるようになってしまう
      それに私が遭遇するバグの大半は、「この入力ファイルを与えると誤動作する」というより、「どこかの何らかのユーザーに対して誤動作する」に近い。たまには「特定条件で一連の手順を踏むと誤動作する」まで絞り込めることもあるが、1) 「ユーザーが順番に何かを行うこと」に自動テストケース縮小器をどう適用すればいいのかよく分からないし、2) いったんローカルで再現する方法を見つけた時点で、デバッグの99%は終わったも同然だ
      たぶん筆者は、こういう私の態度を「過小評価」と見るのだと思う
    • テストケース縮小が何かを知っている人自体が少数派だと思う

  • この記事と例は、コンパイラ以外の状況でも縮小器がもっと広く使われるべきだと言いながら、かなりコンパイラ作者寄りの視点になっている
    ~silentbicycle が書いているように、ほとんどのテストケース縮小はファザーやプロパティベースドテストの文脈で起こり、より大きなフレームワークの中に縮小機能が組み込まれている。コンパイラは、独立したテストケース縮小器が有用な珍しい分野の一つだ。独立型の縮小器が役立つほかのケースがどれだけあるのかはよく分からない
    決定性の話も興味深い。例は、バグを引き起こす入力ファイル、つまりスクリプトによって決定性が生じるケースから始まっており、バグのあるプログラムであるインタプリタ自体の性質として決定的なわけではない。この記事が、「interestingness」手法は、バグのあるプログラム自体が非決定的なコンパイラ以外の状況でも通用する、という意味なのかは明確ではない
    テスト問題をファジングとテストケース縮小に適した形へ変える方法としては、番号付きの命令型コマンド群を作ることを勧めたい。各コマンドには、テスト失敗を検知できる軽量な整合性チェックを入れておき、即座にクラッシュしないケースも拾えるようにする。重い整合性チェックは別コマンドに分けたほうが、テスト速度をあまり落とさずに済む。単純なランダムテストでは、テストハーネスが何か壊れるまでコマンドをランダムに選び、あとでファザーハーネスに切り替えるときは、ファジング入力のバイトストリームによってコマンドを選ぶようにすればいい。そうすれば、決定的な回帰テストやテストケース縮小のような良いものを自動的に得られる
    libfuzzer に明示的にテストケースを減らすよう指示しても、あまり成果はなかった。おそらく libfuzzer が入力を生成する過程ですでに縮小していたからだと思う。そのため、汎用ファザーがテストケース縮小に役立つ interestingness チェックをさらに試してみようという動機にはならなかった。他の人はうまくいったことがあるのか気になる

    • 完全に同意する。こういうやり方はよく使う。状態を持つインターフェースの記号的表現を作り、たいていは switch-case や match ベースの単純なインタプリタを書き、それから操作列をランダム生成して実行し、事前条件・事後条件違反や内部破損を検出する assert を起こした入力を縮小する
      これをプロパティベースドテスト、ファジング、あるいは軽量モデル検査のどれと呼ぶにせよ、深いバグを見つけるのに驚くほど効果的なことがある。各操作は個別には正しくても、互いの前提が少しずつずれている状態付きインターフェースを私は数多く見てきたし、そうした操作が予想外の形で組み合わさると内部破損へと発展する
      操作列をインメモリのハッシュテーブルやリストベースの単純実装と並行して実行し、結果が一致するか確認するのも有用だ。差異が出た場合、それはたいていバグか、より明確に文書化すべき境界ケースである
    • たまに輸送最適化を扱うのだが、不変条件が壊れるかなり複雑なシナリオによく遭遇する。テストケース縮小器があれば本当に助かるだろうが、以前は手作業で縮めることで満足するしかなかった[0]
      残念ながらデータファイルが複雑すぎて、shrinkray で扱うのは難しそうだ。複数の異なる「ファイル」にまたがる表形式データを読み込み、長距離依存もあるので、縮小方法に関するドメイン知識を自分でエンコードする必要がありそうだ
      AI の進歩の速さを見ると、次にこういうシナリオが来たら専用の縮小器を書く気がする
      [0] 曖昧な存在論を持ち出すなら、最適化問題はコストを最小化する探索問題で、これは事実上コンパイラと同じなので、完璧な例ではない

  • これを pytest で書いたテストにどう適用するのか理解しようとして3回読んだ
    テストスイートの複雑さを減らしたいので、仕事していないときに4回目を読み返すつもりだ

    • Python を使っているなら、最初の一歩はテストケース縮小が組み込まれている Hypothesis を導入することだ

  • 去年、CI のテスト実行順序の問題を調べていたとき、テスト一覧を縮めるのに役立つツールを作った
    基本的には、行を半分ずつ削りながら実行してみる方式だった
    スクリプト自体にはかなりバグが多いが、5000件のテスト一覧が、自分の並行性バグを引き起こす4件ほどのテスト一覧に縮まったのは見事だった
    自分のケースで Shrink Ray がそのまま動いたのか、本当に気になる。「テストを基準に行集合を縮める」機能は、標準的なコマンドラインツール群に入っているべきだと本気で思う

  • この話題に関連して、プロパティベースドテストも、テストの反例を作るために生成された入力の状態空間を「縮小」する、かなり似たアプローチを使う
    プロパティベースドテストの利点は、探索空間を誘導し構造化できることだ。入力を、プログラムをモデル化する状態機械を駆動する遷移集合として表現できる
    この手法が、とくにデータベースや分散システムのような非常に相性のよい領域ですら、あまりにも使われていないのを見るたびに驚く。つい先週も $WORK でこの種のテストを数時間もかけずに作り、私たちのシステムが収束しないことを素早く発見した。テストは、同僚に見せればすぐ理解できるようなきれいなトレースを出力してくれた
    個人的には、複雑なシステムをデバッグするときの投資対効果が最も高いテスト手法だと思う