From LaTeX and OCaml to LEAN4 and Executables: Lean-Checked Theorems and Generating Proof-Carrying Rust
本論文は、相互帰納型、符号付き整数演算、およびカーネルとその自己記述的方程式の相互実装検証を通じてシステムの妥当性を確認することに成功した、Lean 4によって検証された定理と証明付き契約を持つ実行可能なRustコードを同時に生成する、OCamlのサブセットに対するPythonベースのHindley–Milnerフロントエンドを提示する。
原論文は CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
ソフトウェアの世界には、コードをどのように書くかという点と、それがどのように安全であるかを知るという点の間に、絶え間ない緊張関係が存在します。プログラマーは、読みやすく管理しやすい方法で複雑なロジックを記述するために高レベル言語を使用しますが、このコードを実行するマシンは、より単純で厳格な言語を話します。これらの一方から他方へと移行するために、コンパイラは翻訳者として機能しますが、この翻訳プロセスこそがエラーが隠れやすい場所なのです。翻訳におけるミスは、安全な命令を危険なものに変え、プログラムのクラッシュや予測不能な挙動を引き起こす可能性があります。数十年にわたり、安全性を確保するための最も信頼できる方法は、最終的なマシンコードを検証することでしたが、これはプロセスの過程で元のプログラムの高レベルな意味が失われてしまうことが多いため、困難な作業でした。研究者が問い続けているのは、元の高レベル言語の明快さを維持しながら、最終的なマシン命令が意図した通りに正確に動作することを、絶対的な確信を持って証明できるのではないか、ということです。
ブレント・ハーツホーン（Brent Hartshorn）は、一つのコード片を同時に二つの異なるものとして扱うことで、この問いに答えるシステムを構築しました。数学的な証明としても、マシンのための命令セットとしても同時に読み取ることができる文書を想像してみてください。この新しい研究において、著者は、データの扱いに関する厳格なルールを持つことで知られるOCamlと呼ばれるプログラミング言語のサブセットを取り上げ、すべての定義に二つの異なる意味を与えています。第一に、コードは論理的な議論として読み取られ、プログラムの構造自体が、特定の条件が常に満たされることを示す証明として機能します。第二に、同じコードはRustと呼ばれる、速度と安全性を重視した別の言語へと翻訳され、コンピュータが実際に実行できるプログラムへとコンパイルされます。このアプローチの素晴らしさは、その検証プロセスにあります。論理的証明は小さく信頼できる数学的エンジンによってチェックされ、一方で実行中のプログラムは、コードをステップバイステップでシミュレートするリファレンス・インタプリタに対してチェックされます。もし両者が一致し、かつ論理的証明が成立していれば、その結果は、それ自体が安全性の証明書を備えたソフトウェアとなります。
研究者たちはまず、特定のOCamlのスライスを理解する翻訳器を構築することから始めました。Pythonで書かれたこの翻訳器は、一人の人間が読み解けるほど十分に小さく設計されています。これは、翻訳器自体が複雑すぎると、その出力に対する信頼が得られないため、極めて重要なことです。この翻訳器は、OCamlのコードを受け取り、それを二つの経路に分割します。証明の経路では、コードを数学的カーネルがチェックできる形式に変換します。このカーネルは、いかなる仮定も置かずに論理の妥当性を検証する、小さな「裁判官」のようなプログラムです。プログラムの経路では、翻訳器はコードをRustへと変換し、そこから高速なネイティブマシンコードへとコンパイルされます。翻訳が完璧であったことを確実にするため、チームは元のOCamlコードを直接実行するリファレンス・インタプリタも構築しました。そして、13種類の異なる例題プログラムを、コンパイルされたRustバージョンとインタプリタの両方に実行させました。あらゆるケースにおいて、コンパイルされたコードはインタプリタと全く同じ出力を生成しており、これにより、翻訳プロセスがプログラムの振る舞いを変えていないことが証明されました。
コードの翻訳に成功した後、チームはコンパイルされたRustバージョンに対して厳格な安全性チェックを実施しました。彼らは、コンパイルされたコードを一種の「契約」として扱い、プログラムがどのように振る舞うべきかという特定のルールを、数学的な定理として書き込みました。例えば、整数の計算が誤ってオーバーフローし、負の数へとラップアラウンド（循環）しないことを確認しました。これはソフトウェアにおける一般的なバグの原因です。調査の結果、ほとんどの安全性ルールは成立していましたが、ルールが破られる特定の境界事例が存在することが判明しました。11の異なるシナリオにおいて、ゼロから最小の数値を引く場合のように、整数計算がラップアラウンドを起こす地点にコンパイルされたコードが到達しました。システムはこれらを「オープンな義務（open obligations）」として正しく特定しました。つまり、コードはこれらの特定の既知の限界を除いては安全である、という意味です。例題プログラムに対して行われた合計90件の安全性チェックのうち、79件は完全に証明されましたが、残りの11件は、コンピュータが数値を扱う際の現実的な限界を表していたため、未解決のまま残されました。
このプロジェクトはさらに進み、コンピュータのリソースを管理する中核的なソフトウェアである、小さなオペレーティングシステム・カーネルにこの手法を適用しました。研究者たちは、以前にPythonとRustで書かれていたカーネルを取り上げ、それを彼らのOCamlサブセットで書き直しました。その後、この新しいバージョンをRustへと翻訳し、コンパイルしました。その結果、同じカーネルの第三の実装が得られました。これをオリジナルのPythonバージョンと比較したところ、新しいOCaml由来のバージョンは、236件すべてのテストケースにおいて正しく回答しました。チームはこの新しいカーネルの安全性を証明しようと試みました。彼らは236件中227件の安全性義務の証明に成功しました。証明できなかった数少ないケースは、コードのエラーではなく、複雑なループやカウンタの扱いに関する、チェックに使用した数学的ツールの不備によるものでした。これは、この手法が小さな例題から機能的なオペレーティングシステムのコンポーネントへとスケールできることを示しました。
おそらくこの研究の中で最も衝撃的な部分は、数学の方程式を直接、動作するプログラムへと変換できる能力です。研究者たちは、カーネルの振る舞いを記述した標準的な数学的表記による形式的な方程式を取り上げ、それをOCamlコードへと変換するツールに投入しました。このコードはコンパイルされ、実行されました。得られたプログラムは、元の方程式が記述している通りに動作し、あらゆる場面でオリジナルのPythonモデルの出力と一致しました。このプロセスは、高レベルの数学的記述が、その意味を失うことなく、検証済みの実行可能なバイナリへと変換できることを示しました。チームは、この方程式のコンパイルされたバージョンがほとんどの安全性契約を満たしていることを証明しましたが、より複雑な論理ステップについては、チェックツールのさらなる改良が必要であることが分かりました。
この研究の成果は、信頼性の高いソフトウェアを構築するための新しい道を提示しています。高レベルのソースコードを保持し、その論理的な意味とコンパイルされた形態の両方を検証することで、研究者たちは、最終的なプログラムの安全性が数学的証明によって裏付けられるシステムを作り上げました。この手法は、整数のオーバーフローといったコンピュータの数値処理における現実世界の限界を特定し、それらを実際のバグと明確に区別することに成功しました。このシステムは、最も複雑なカーネルの部分においてすべての安全性ルールを証明したわけではありませんが、大部分を証明しており、未解決となった箇所は、コード自体ではなく、チェックツールを改善すべき領域として明確に特定されていました。この成果は、高レベルのコードからマシン命令への翻訳プロセスを完全に制御し、最終的な実行ファイルが、それを生み出した論理と同じくらい厳格な安全性の証明書を携えていることを保証できることを実証しています。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。