http://klee.llvm.org/は、シンボリック実行と制約解決によって機能するプログラム分析ツールで、プログラムをクラッシュさせる可能性のある入力を見つけて、テスト ケースとして出力します。これは非常に印象的なエンジニアリングであり、これまでに作成された中で最も徹底的にテストされたソフトウェアの一部と見なされていた Unix ユーティリティのオープンソース実装のコレクションで多数のバグを発見するなど、これまでにいくつかの良い結果を生み出してきました。
私の質問は: それは何をしませんか?
もちろん、そのようなツールには固有の限界があります。ユーザーの心を読み取って、出力がどうあるべきかを推測することはできません。しかし、原理的に不可能なことは別として、ほとんどのプロジェクトはまだ Klee を使用していないようです。現在のバージョンの制限は何ですか? まだ処理できないバグやワークロードの種類は何ですか?
http://llvm.org/pubs/2008-12-OSDI-KLEE.htmlを読んだ後に言えるように
大きなプログラムのすべての可能なパスをチェックすることはできません。sortユーティリティでも失敗しました。問題は停止問題（Undecidable problem）であり、KLEE はヒューリスティックであるため、限られた時間で一部のパスのみをチェックできます。
紙によると、高速には動作しません。COREUTILS で 141000 行のコード (libc コードが使用されている) のテストを生成するのに 89 時間かかりました。そして、最大の単一プログラムには、最大 10000 行しかありません。
浮動小数点、longjmp/setjmp、スレッド、asm については何も知りません。可変サイズのメモリ オブジェクト。
更新: /from llvm blog/ http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html
5. LLVM「Klee」サブプロジェクトは、記号分析を使用して、コードの一部を「すべての可能なパスを試行」し、コード内のバグを見つけ、テストケースを生成します。これは、大規模なアプリケーションで実行するのが実用的でないことによってほとんど制限されている、非常に小さなプロジェクトです。
Update2: KLEE はプログラムの修正が必要です。http://t1.minormatter.com/~ddunbar/klee-doxygen/overview.html
. シンボリック メモリは、KLEE への特別な呼び出し (つまり klee_make_symbolic) を挿入することによって定義されます。実行中、KLEE はシンボリック メモリのすべての使用を追跡します。
全体として、KLEE は学術研究用の非常に優れたシンボリック実行エンジンになるはずです。実際に使用する場合、次の側面によって制限される可能性があります。
[1] KLEE の LLVM IR インタープリターが使用するメモリ モデルは、メモリと時間を消費します。実行パスごとに、KLEE はプライベートな「アドレス空間」を維持します。アドレス空間は、ローカル変数の「スタック」と、グローバル変数および動的に割り当てられた変数の「ヒープ」を維持します。ただし、各変数 (ローカルまたはグローバル) は、MemoryObject オブジェクトにラップされます (MemoryObject は、開始アドレス、サイズ、割り当て情報など、この変数に関連するメタデータを保持します)。各変数に使用されるメモリのサイズは、元の変数のサイズに MemoryObject オブジェクトのサイズを加えたものになります。変数にアクセスする場合、KLEE はまず「アドレス空間」を検索して、対応する MemoryObject を見つけます。KLEE は MemoryObject をチェックし、アクセスが正当かどうかを確認します。もしそうなら、アクセスが完了し、MemoryObject の状態が更新されます。このようなメモリ アクセスは、明らかに RAM よりも低速です。このような設計は、シンボリック値の伝播を容易にサポートできます。ただし、このモデルは、テイント分析 (変数の記号状態のラベル付け) から学習することで単純化できます。
[2] KLEE にはシステム環境のモデルがありません。KLEE でモデル化された唯一のシステム コンポーネントは、単純なファイル システムです。ソケットやマルチスレッドなど、その他のものはサポートされていません。プログラムがこれらのモデル化されていないコンポーネントへのシステム呼び出しを呼び出すと、KLEE は (1) 実行を終了してアラートを生成するか、(2) 呼び出しを基盤となる OS にリダイレクトします (問題: シンボリック値を具体化する必要があり、一部のパスは異なる実行パスからのシステム コールが互いに干渉する可能性があります)。これが、前述の「スレッドを知らない」理由だと思います。
[3] KLEE はバイナリに対して直接作業することはできません。KLEE には、テストするプログラムの LLVM IR が必要です。一方、BitBlaze プロジェクトの S2E や VINE などの他のシンボリック実行ツールはバイナリで動作します。興味深いことに、S2E プロジェクトは、シンボリック実行エンジンとして KLEE に依存しています。
上記の回答に関して、私は個人的にさまざまな意見を持っています。まず、KLEE が大規模なプログラムを完全に処理できないのは事実ですが、どのシンボリック実行ツールが可能でしょうか? 経路の爆発は、技術的な問題というよりも、理論的な未解決の問題です。第 2 に、前述したように、KLEE はそのメモリ モデルが原因で実行が遅くなる可能性があります。ただし、KLEE は実行を無駄に遅くするわけではありません。保守的にメモリの破損 (バッファ オーバーフローなど) をチェックし、実行されたパスごとに一連の有用な情報をログに記録します (パスをたどる入力の制約など)。さらに、超高速で実行できる他のシンボリック実行ツールを知りませんでした。第三に、「浮動小数点、longjmp/setjmp、スレッド、asm; 可変サイズのメモリ オブジェクト」は単なるエンジニアリング作業です。例えば、http://srg.doc.ic.ac.uk/files/papers/kleefp-eurosys-11.pdf )。第 3 に、KLEE では、シンボリック変数にラベルを付けるために、プログラム上でインストルメンテーションを必ずしも必要としません。前述のように、シンボリック値はコマンド ライン経由でプログラムに入力できます。実際、ユーザーはファイルをシンボリックに指定することもできます。必要に応じて、ユーザーは単純にライブラリ関数をインストルメント化して入力をシンボリックにすることができます (一度だけ)。