KLEE : Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs

by syoyo

KLEE は LLVM を使ったシンボリック実行ツール.

http://klee.llvm.org/

シンボリック実行とは?

シンボリック実行(Symbolic execution)とは、論文によれば以下のようなシステムだそう.

Instead of running code on manually- or randomly-constructed input,
they run it on symbolic input initially allowed to be “anything.”
They substitute program inputs with symbolic values and replace
corresponding concrete program operations with ones that manipulate symbolic values.

このシステムの使い道として論文が述べているのは主に二つ.
カバレッジツールと、自動バグ発見ツールである.

カバレッジツール

シンボリック実行を行うことにより、KLEE が自動生成するテストデータでは 90% 以上と高いコードカバレッジを実現する.
たとえば Coreutils に対するカバレッジテストでは、KLEE はわずか 89 時間をかけることで、
15 年以上手動で積み上げられてきたテストスイートを上回るカバレッジを達成している.

自動バグ発見ツール

KLEE はバグ発見ツールとしても利用でき、Coreutils に 15 年潜んできた致命的なバグを発見できたという.

まとめ

KLEE およびシンボリック実行アルゴリズム、なかなかよさそうですね.
レンダラの検証にも使えないかなと思います.
たとえばシーンファイルのパーサに適用とか.

ただ、ちゃんとレンダラアプリの内部までのカバレッジをあげるには、coreutils のようなある意味テキスト操作系の
アプリとはまた違った戦略が必要になりますので、KLEE そのままの適用では難しいでしょうね.
そこらへん、新しくロジックを提案できないかなぁと思います.

Advertisements