フォーマル検証ツールにおける見逃されたアラームバグの探索
Looking for Missed Alarm Bugs in a Formal Verification Tool (blog.regehr.org)
要約
この記事は、YARPGenのようなツールや大規模オープンソースプログラムが、その完全な状態空間のどれだけを実際に探索しているかについての研究の現状を問うています。筆者は、どのような単一のアプローチでも、数学的な意味で「ほぼ全て」の状態空間を見逃す可能性が高いと推測しています。しかし、実際に使用されている部分がカバーされている限り、既存のアプローチのカバレッジを拡大するよりも、新しいアプローチに取り組む方がROI(投資収益率)が高いかもしれないと示唆しています。
全文翻訳
形式検証ツールの見逃しアラームバグを探す
(本稿は Vsevolod Livinskii との共著です。)
形式検証は、コンピュータシステムをより良くするために振りかける魔法の粉のようなものではありません。実際の形式検証には、他のシステムレベルのジョブと同様の、困難で厄介で地道なエンジニアリング作業が多く含まれます。さらに、検証ツール自体を正しく機能させることは非常に困難です。それらは多くの種類の欠陥の影響を受けやすく、他のソフトウェアよりもデバッグが難しい場合さえあります。それらを信頼するためには、厳密なテストが必要です。
Alive2は翻訳検証ツールです。LLVM IRで記述された関数の2つのバージョン(通常は、最適化が行われる前と後のコードに対応します)が与えられると、Alive2はその最適化が正しいことを証明するか、あるいは間違っていることを証明しようとします。Alive2はコンパイラエンジニアによって実用的に使用されており、600件以上のLLVMのissueが私たちのオンラインAlive2インスタンスにリンクされています。
クラッシュなどを除くと、Alive2の欠陥は大きく次のように分類できます。
- 偽アラーム:存在しないエラーをAlive2が検出する
- 見逃しアラーム:存在するエラーをAlive2が検出しない
最初の種類のエラー、偽アラームはテストするのがそれほど難しくありません。単純にAlive2に多数の最適化を検証するように依頼し、それが検出したエラーを注意深く調べます。そのようなエラーはすべて、LLVMまたはAlive2のバグの結果です。2番目の種類のエラー、つまり左下の象限にあるものは、テストするのがはるかに困難です。
[画像]
私たちが欠いているのは、見逃しアラームバグを引き起こす可能性のあるテストケースです。そのような各テストには、同じシグネチャを持つLLVM IRの関数のペアが必要ですが、それらは少なくとも1つの入力の選択肢に対して明らかに異なる動作をします。LLVMはそれほどバグの多いコンパイラではないため、これらのテストケースを作成するためにコンパイラバグに頼ることはできません!LLVMが行う最適化の大部分は正しいです。
見逃しアラームバグを見つけるために、私たちは2つの異なるアイデアを試しました。この記事の残りの部分で、それら両方を説明します。
まず、私たちはYARPGenから始めました。これは、多数のコンパイラバグを見つけるために使用されてきたランダムプログラムジェネレータです。YARPGenが提供する重要な保証は、生成されたCまたはC++関数が未定義の動作を含まないことです。この保証なしでは、異なるコンパイラが未定義の動作を異なる方法で悪用する傾向があるため、ランダムな差分テストを実際に行うことはできません。しかし、この保証は見逃しアラームバグを見つけるための十分な基盤ではないため、私たちはYARPGenを私たちの目的に合わせて変更しました。私たちの変更されたバージョンは、通常のランダム関数を生成し、次に新しいことを行います。それは、新しい関数も未定義の動作を含まないという保証を維持しながら、その関数をわずかにランダムに変異させます。
これで、互いに非常に似ており、未定義の動作を含まないことが保証された2つの関数が得られました。これは見逃しアラームバグを見つけるための基盤となるでしょうか?まだ完全ではありません。これらの関数が、少なくとも1つの入力セットに対して異なる結果を生成することを確認する必要があります。これを行うために、関数のペアをコンパイルして実行し、変異が観察可能な動作を変更しなかったペアはすべて破棄します。最後に、関数のペアをLLVM IRにコンパイルし、Alive2に一方の関数が他方をリファインするかどうかを尋ねます。構築により、このチェックは失敗する必要があります。Alive2がエラーを検出しない場合、私たちは元々探していたAlive2の見逃しアラームバグの種類を見つけたことになります。
私たちが持っている、見逃しアラームバグを探し出すためのもう一つの方法は、偶然たどり着いたものです。私たちは、Zhengyang LiuのLLVMスーパーオプティマイザであるMinotaurが、基本的にそれを使用するたびに、見逃しアラームバグをパッシブに探していることに気づきました。ここにMinotaurのソースコードがあり、ここにそれに関する論文があります。
最適化されているプログラムのLLVM命令ごとに、Minotaurはより安価な計算方法を見つけようとします。これは、その命令と、その命令のバックワードデータ、制御、およびメモリ依存関係の一部を、ターゲット命令によって計算された値を返す新しいLLVM関数に抽出することによって行われます。この新しい関数は、仕様を見つけるためのプログラム合成問題の仕様として機能します。目標は、仕様を計算するより安価な方法を見つけることです。MinotaurはAlive2を使用して新しい関数が古い関数をリファインすることを確認し、llvm-mcaを使用して新しい関数が古い関数よりも計算コストが安いことを確認します。
合成は、多数の部分的にシンボリックな候補を列挙することによって機能します。ここでは、命令は具体的に表されますが、リテラル定数はシンボリックに表されます。ZhengyangはAlive2を、候補に少なくとも1つのシンボリック定数が含まれている場合、それはexists-forallソルバークエリを発行するように変更しました。これはソルバーに次のように尋ねます。「候補内のシンボリック定数の値は存在しますか?それによって、候補は仕様をリファインしますか?」
Minotaurの合成手順の詳細はこの際あまり重要ではありません。重要な点は、候補が膨大にあり、その大部分が仕様をリファインしないため、Alive2に見逃す機会を数多く与えることになるということです。
しかし、MinotaurによってAlive2が呼び出されたときに見逃した場合、どうすればわかるでしょうか?さて、見逃しアラームとは、Alive2が候補が仕様をリファインすると主張したが、実際にはリファイン関係が存在しないことを意味することを思い出してください。リファインメントはオプティマイザの正しさの基準であるため、これらの失敗は定義上、誤コンパイルにつながります。Minotaurを使用して大規模なオープンソースプログラムをコンパイルし、その後テストスイートを実行することが日常的に行われているため、それが導入する誤コンパイルを見つける良い機会があるはずです。
私たちは、Alive2で見逃しアラームバグを探すために、ランダム検索を使用する方法と、小規模な網羅的検索を使用する方法という2つの異なる方法を見てきました。これまでのところ何が見つかったでしょうか?あまり多くはありません!Alive2とZ3が見逃しアラームの習慣を持っているようには見えません。これは、人々が実際にAlive2を実用的に利用していることを考えると、トップレベルの設計目標を達成していることを意味します。
では、これは物語の終わりでしょうか?Alive2が見逃しアラームをしないと確信できるでしょうか?残念ながら、確信はできません。私の疑いは、もし私たちが本当に見逃しアラームバグを見つけたいのであれば、YARPGenもMinotaurも興味深い方法でストレスをかけない関数属性や類似の構造に対するAlive2のサポートを見ることになるだろうということです。