テストケース圧縮器の多面的な活用と実践事例

テストケース圧縮器（Test-case reducers）は、広く知られるべきツールですが、その応用例や潜在的な「乱用」については十分に認識されていません。本稿では、実際の使用経験から得た知見をまとめます。

テストケースの圧縮：基本概念と実装

なぜ圧縮が必要か

• プログラムが大きな入力データでクラッシュした際、どの部分が原因か特定するのが困難です。
• 古典的なデバッグ手法（

  printf

  デバッガー、Sanitizer など）は有効ですが、入力のサイズを縮小するアプローチも極めて重要です。
• 入力が小さいほど、問題の原因を理解しやすくします。

手動圧縮の限界

• テキストエディタで入力データの一部を削除してクラッシュを確認する方法は存在しますが、非効率です。
• 人間は視覚的限界や飽きっぽさのため、多くの削減の可能性を見逃しがちです。
• 入力データを部分的に削除することでエラーが解消されたり、異なるエラーが発生したりするため、探索空間が膨大になります。

自動化ツールの効果

• テストケース圧縮器は、プログラムと「興味深さ判定テスト（interestingness test）」を受け取り、95〜99% の高圧縮率で入力を短縮します。
• これらはデバッグを劇的に容易にし、多くのプログラマーが「魔法」と感じている要因です。

自作圧縮器の試み

テストケース圧縮器の内部機構を理解するため、以下のような簡易実装を作成しました。

1. 興味深さ判定テスト: エラーが発生すれば

   0

   を返し、なければ

   1

   を返します。

   #!/bin/sh
   if python3 t.py "$1" | grep "Word too long" > /dev/null; then
     exit 0
   else
     exit 1
   fi
   

2. 圧縮器: 入力データの各行を順次削除し、テストが失敗する行を探します。

   #!/usr/bin/env python3
   import subprocess, sys, tempfile
   cur = [x.rstrip() for x in list(open(sys.argv[2]))]
   i = 0
   while i < len(cur):
     with tempfile.NamedTemporaryFile(mode="w") as p:
       cnd = cur[:]
       del cnd[i]
       p.write("\n".join(cnd))
       p.flush()
       # テスト実行
       if subprocess.run([sys.argv[1], p.name]).returncode == 0:
         cur = cnd
       else:
         i += 1
   print("\n".join(cur))
   

• 結果: 25 文字以上の単語を含む大きな辞書ファイルから、特定の単語（

  antidisestablishmentarianism

  ）を抽出できました。
• 洞察: 私自身もツールが「なぜ」そのような削減を行うか理解していなかったものの、それは非常に有用に機能しました。

高度な削減手法：Shrink Ray

市販のツール

Shrink Ray

# クラッチャー（最適化情報）なしで実行
pipx install shrinkray
shrinkray --no-clang-delta ./interesting.sh t.c

• 初期入力：78 行の C コード
• 圧縮後：54 行に削減（30% の削減）
• Shrink Ray は、整数値の削減やコメント削除など、非常に巧妙なルールを持っています。
• 実行時間を増やすことで、さらに高い削減率（99% など）を達成できます。

興味深さ判定テスト作成の注意点

圧縮器は単に「入力長を短くする」だけでなく、定義されたテストが満たされるまで削減を進めます。以下の 4 つの原則を注意深く設計する必要があります。

1. 過剰な削減を防ぐ

• テストケース圧縮器は文字通りテストを実行するため、意図しない条件も許容してしまうことがあります。
• 過剰な削減（入力がない場合でもエラーが出るなど）に注意し、明示的なチェックを行うことが推奨されます。

2. 実行速度の重要性

• テストケース圧縮器は数百回〜数百万回のテストを試すため、興味深さ判定テスト自体が高速であることが必須です。
• 最適化オプション（例：コアダンプ作成を無効化）を導入し、テスト速度を数倍に向上させます。

3. グローバルタイムアウトの管理

• 圧縮器は

  i-=1

  のようなループ継続条件を変更して終了しないプログラムを作成してしまう可能性があります。
• サブタイムアウトを設定し、非関心な入力を早期に検出する必要があります（通常、初期実行時間の 1.5〜2 倍を推奨）。

4. 並列実行への配慮

• Shrink Ray などのツールはテストケースを並列で実行するため、テストは一時ディレクトリ上で実行され、自動的にクリーンアップされます。

不決定性（非決定的なエラー）への対処

プログラムにおいて、ランダム関数や環境依存によりバグが頻繁に出現しない場合（確率 1/3 など）、デバッグは非常に困難です。

問題と解決

• 課題: 圧縮器が入力を短くすると、不決定性の条件（例：

  random.random() < 0.33

  ）が失われ、エラーが消えてしまいます。
• 解決策: 「入力の短さ」だけでなく、「エラーの再現性」を重視するテスト設計が必要です。

再現性を確保するテスト戦略

1. 「一度でも成功すれば OK」（緩い判定）

   • エラー発生頻度を上げる場合に有効です。
   • リスク: 不決定性のレベルが上昇することがあります。

2. 「連続成功」としての厳格化

   • n

     回の反復すべてでエラーが発生する入力を採用します。
   • これにより、不決定性の低い安定したバグを特定できます。

実用的なハイブリッド手法

• まず緩いテストで大量の削減を行い、エラー発生頻度を上げます。
• 次に、より厳格なテスト（連続 n 回のエラー）に切り替え、不決定性を減らします。
• このアプローチは、Shrink Ray が「幸運を呼び込む」瞬間を最大化する効果があります。

「グローバルカウンターとの比較」技法

Shrink Ray には直接「トレース長」や「実行時間」を削減指標にする原則がない場合でも、自前の興味深さ判定テストでこれを強制できます。

具体例：トレース長の削減

yk

#!/bin/sh
t="$(mktemp)"
YKD_LOG="$t:jit-asm" /path/to/interpreter "$1"

if [ "$?" -ne 139 ]; then # シグナル 139 (SIGSEGV) でない場合はエラー
  rm "$t"
  exit 1
fi

new_len="$(wc -l < "$t" | tr -d " ")"
# グローバルで最小の長さを保持する
if [ ! -f /tmp/global_best ]; then
  echo "$new_len" > /tmp/global_best
fi
old_len="$(cat /tmp/global_best)"

if [ "$new_len" -gt "$old_len" ]; then
  # 現在のトレースが過去に最小よりも大きければ、この入力は「不関心」
  rm "$t"
  exit 1
fi
echo "$new_len" > /tmp/global_best
rm "$t"

• 欠点: このコードは並列処理環境では不完全な挙動を示す可能性があります。
• 功績: 40K 行の出力を、10.1K 行に削減し、バグの原因理解を大幅に加速しました。
• 応用: 「実行時間の短縮」や「他の指標の最小化」など、入力サイズ以外の任意の特性を最適化対象とできます。

まとめ

テストケース圧縮器は、単なるコード短縮ツールではありません。以下のように多様な用途で活用可能です。

• デバッグの劇的加速: 膨大な入力を数行に減らし、バグのトリガーを即座に特定します。
• 不決定性の除去: ランダムなエラーや条件分岐を固定し、再現実装可能なテストケースを作成します。
• 代替指標の最適化: 入力サイズ以外の「実行時間」や「出力桁数」などを削減対象とすることで、新しい視点でのデバッグが可能です。

本稿で記述した手法は、コンパイラ作成者だけでなく、全てのプログラマーにとって生産性を向上させる強力な手段です。