ネットワークプロトコル実装における状態を考慮したテストケース最小化手法

ファジング技術の発展により，ソフトウェアのクラッシュを誘発するテストケースを自動かつ大量に生成可能になった．一方，膨大なクラッシュの中から真に有用なものを選別するトリアージ工程が，実運用上のボトルネックとなっている．特に，テストケースからクラッシュ再現に不要な要素を除去する最小化は，後続の解析作業の効率と精度を左右する重要な工程である．しかし，ネットワークプロトコル実装では既存の最小化手法は有効に機能しない．プロトコル実装における多くのクラッシュは特定のメッセージ列による状態遷移に依存するため，単一メッセージを前提とする既存手法では再現に必須な状態遷移まで破壊してしまう．そこで本研究では，プロトコルの状態遷移に着目した二段階テストケース最小化手法を提案する．本手法は，第一段階で応答コードを基に構築した状態遷移グラフを用いて不要なメッセージを削除し，第二段階で残存メッセージから不要なバイトを削減する．これにより，クラッシュの再現性を担保しつつ，トリアージの妨げとなる不要な状態遷移とコードパスを効果的に排除する．複数のプロトコル実装による評価の結果，提案手法はクラッシュ再現性を維持したままテストケースを削減することに成功した．また，状態遷移グラフを用いた手法では，状態遷移を必要とする複雑なテストケースに対して最小化に要する時間が，平均 36% 短縮された．

The advancement of fuzzing techniques has enabled the automatic generation of numerous test cases that trigger software crashes. However, triaging these crashes has become a significant bottleneck. Test case minimization, the process of removing unnecessary elements, is crucial for the efficiency and accuracy of subsequent analysis. Unfortunately, existing minimization methods are often ineffective for network protocol implementations. Most crashes in these implementations depend on specific state transitions caused by a sequence of messages. Existing methods, which typically assume a single message as input, can destroy the essential state transitions required to reproduce the crash. To address this challenge, we propose a state-aware two-stage test case minimization method. The first stage leverages a state transition graph, constructed from response codes, to remove entire messages that are not essential for reproducing the crash. The second stage then performs byte-level reduction on the remaining messages. This approach effectively preserves crash reproducibility while eliminating irrelevant state transitions and code paths that complicate the triage process. Our evaluation on multiple protocol implementations demonstrates that the proposed method reduces test case size without compromising crash reproducibility. In addition, leveraging the state transition graph reduced the average minimization time to 0.64 times for state-dependent test cases.