HN 日本語サマリー

← 一覧へ戻る
プログラミング

形式検証は検証可能ではない

Formal Verification Is Not Verifiable (alperenkeles.com)

147 pointsby zdw53 コメント

要約

AIの進化により形式検証が主流になりつつありますが、その「検証可能性」には疑問符がつきます。形式検証は「すべての場合について」の主張を行いますが、その証明プロセス自体には、モデル、プロバー、コンパイラなどの信頼できるコンポーネントが多く存在し、それらにバグが含まれる可能性があります。テストは「存在する場合」の主張であり、人間が検証可能で、AIとの相性も良いと著者は論じています。

全文翻訳

AIは形式検証を主流にしています...

...と私は2025年12月に書きました。まあ、過去12ヶ月を経て、これに反論するのは難しいと信じています。AIは確かに形式検証を主流にしました。

形式検証のスタートアップの数が急増しただけでなく、Claudeは単一の検証プロジェクトのために10億行のRocqを書き、Claude Codeの作成者からVercel CEOまで、Codex/Cursorの主要開発者が形式検証について語っています。初期のスタートアップは、単に数学的証明を生成するだけでなく、ソフトウェアに経済的価値をもたらし始めています:AnthropicとのTheoremのバイナリ検証作業、HarmonicによるCプログラムとハードウェア設計の検証など。サイバーセキュリティのリスクが天井知らずになる中、形式検証は容易になっただけでなく、経済的価値も増しています。

人々が今尋ねる質問は「Xをどうやって証明するか」ではなく、「Xについて何を証明できるか」あるいは「証明できないものは何が残っているか」です。これらは良い質問です。私はこの投稿を、それらに答えるための一部として書いています。そして、昨年の投稿「テストは(単に)検証するな」のフォローアップとしています。結論を先に言うと、私は形式検証について非常に楽観的ですが、「形式的に検証された」と言うときに人々は多くの異なることを意味していると思います。それを私が楽観的または悲観的である部分に分解しようと思います。

タイトルの話から始めましょう。私はSFの人が言うところの「検証可能性に傾倒した」人間です。私は長い間(まあ、2年間)、検証可能性がAIが私たちに与えることができるレバレッジの限界であると主張してきました。私のラフな長期的な見解は、私たちのテクノロジースタックを、システム内のこれらの検証可能なコンポーネントのスパイクを中心に構築していくということです。今日、検証可能性が言及されると、形式検証がすぐに議論に飛び込んできます。しかし、どういうわけか、形式的に検証されたシステムでもバグが存在することがあり、誰かがシステムを形式的に検証したと聞くと、私はそのシステムの正確性に対する信頼感で満たされることはありません。一方で、誰かがシステムにバグを見つけたと聞くと、彼らがそうしたとかなり確信しています。これは、テストが検証可能であり、明確に定義された、レビュー可能で理解可能なオブジェクト、つまり昔ながらのバグレポートを生成するからです。テストは(人間によって)検証可能であり、UIコンポーネントは検証可能であり、だからこそAIとの相性も非常に良いのです。

一方、形式検証には、外部レビューを必要としない「検証済み」コンポーネント(証明)と、検証が難しいコンポーネント(定義自体、証明を行っているプロバー、事実を証明している対象のモデル)があります。形式検証の主張は非常に強力です――形式検証はすべての主張を行います。テストは存在する主張を行います――難しいコンポーネントのいずれかの間違いが、証明の崩壊につながる可能性があります。

形式検証をより「検証可能」にするためのいくつかの道があります。最も簡単なのは、信頼されるコンポーネントの量またはサイズを減らすことです。その素晴らしい例が、最近の「バイナリ検証」アプローチです。プログラム自体の事実を証明する代わりに、それらのプログラムのコンパイル済みバイナリの事実を証明します。これにより、(1)高水準プログラミング言語のセマンティクスをモデル化することを省略できます。代わりに、機械のセマンティクス(おそらくより単純なセマンティクス)をモデル化し、コンパイラの正確性への依存をなくすことができます(これは実際には良い考えではありません。コンパイラには多くのバグがあります)。(2)1つだけでなく多くの高水準言語のセマンティクスをモデル化することを回避できます。なぜなら、ソースレベル検証では各言語を個別にモデル化する必要がありますが、バイナリレベルではすべて同じモデルに収束するからです。

しかし、これは私の意見では、問題の一部しか解決しません。信頼されるサーフェスは依然として巨大です。信頼されたコンピューティングベースには、機械セマンティクスとLinuxプロセスセマンティクスの両方が含まれており、どちらも追加の検証が必要です。さらに重要なのは、「Xを形式的に検証する」という話は依然として間違いであり、具体的に正しい用語は「YのXプロパティを形式的に検証する」ということです。この用語の区別はかつては口語的に受け入れられていましたが、「CompCertは形式的に検証されたコンパイラです」とか「seL4は形式的に検証されたマイクロカーネルです」と聞いたとき、著者は空虚または些細なプロパティを検証しなかったと想定していました。なぜなら、検証作業自体が研究者の評判に大きく影響する高い基準に達していたからです。実際、これらの作業は広範なピアレビューを経ており、それらを基に他の形式的に検証されたシステムが構築されており、そしてバグがありました。しかし、AIがソフトウェアエンジニアリングにおけるコードレビューを揺るがしたように、証明エンジニアリングにも同様に、さらに積極的な影響を与えています。AIが世界のソフトウェアの量を10倍にしたとすれば、それはおそらく「形式的に検証されたソフトウェア」の量を1000倍にしたことになります。この民主化は、ほぼすべてのドメインにおける私たちの伝統的な検証戦略に影響を与えますが、元々ニッチであった分野ほど、この量の変化により深刻な影響を受けます。

私の意見では、私たちはできるだけ早く「形式的に検証されたソフトウェア」という概念を廃止しなければなりません。ニュアンスが必要です。形式検証のすべての議論には、注意点のリスト、何が信頼され、何が証明され、何が証明されていないかについての正確な理解が伴う必要があります。このうちいくつかはすでに存在しています。新しいLean証明は、LLMが悪用した可能性のあるカーネルの健全性バグの可能性の下で議論されており、comparatorは新しいLean証明を検証するための標準デバイスになりつつあります。Anthropic<>Theoremのクラッシュフリー検証やGoogle DeepMindのSignal検証のような主要な発表は、証明の限界と信頼されたコンピューティングベースの両方を述べています。

形式的に検証された属性を持つソフトウェアのバグに関する会話を発展させることも重要です。ソフトウェアにバグがあるのは普通のことです! これはソフトウェアエンジニアを非難するものではなく、ソフトウェアの固有の複雑さの結果です。複雑なソフトウェアシステムは、数百万または数十億ではなく、数兆もの異なる種類のイベントを扱います。エンジニアは抽象化の層を構築し、複雑な動作を管理可能で一般的な、よくテストされたプリミティブのパターンで捉えることによって、この複雑さを制約します。しかし、これらの層がユーザーに近づくにつれて、数学的に明確に定義された抽象化を作成するのは難しくなります。これを考える最も簡単な方法は、車のソフトウェアを想像することです。エンジンはデータベースに似ており、どちらもよく設計されており、単純なインターフェースを提供します。車のシートはユーザーインターフェースに似ています。それに対する数学的な公式はなく、一般的なガイドライン、ユーザーの要求、美的選択があります。最終的には、エンジンやデータベースのように「キキ」というよりは「ブーバ」のように感じられます。

[画像: エンジンとデータベースとラベル付けされたスパイク状の「キキ」形状、シートとユーザーインターフェースとラベル付けされた丸みを帯びた「ブーバ」形状、機械に近い方からユーザーに近い方への矢印]

ソフトウェアまたは特定のレイヤーが「ブーバ」であるほど、それが正しい理由について話すのが難しくなります。私たちは常にいくつかの正しい属性について話すことができますが、正確性の均一な概念について話すことは私の意見では不可能です。それは、ブーバソフトウェアを形式的に検証することについて話すことは絶望的な試みであり、「すべてを形式的に検証する」または「バグのないソフトウェア」という声明には大きなアスタリスクが必要であることを意味します。

ブーバソフトウェアを正しく証明することはできませんが、それについて多くのことを証明できます。ソフトウェアの一般的なプロパティについては、これらの事実が内側のキキレイヤーに現れるか外側のブーバレイヤーに現れるかに関わらず、それらを証明することに非常に楽観的です。特にシングルスレッドプログラムの文脈では、既存の証明フレームワークが、機械生成された証明の助けを借りて、大規模で実際のプロダクションシステムを証明する余地を与えてくれると考えています。私は以前、2030年までにシングルスレッドコード翻訳を解決するかもしれないという個人的な賭けをしました。今では、翻訳だけでなく、シングルスレッドプログラム検証も解決できると信じている段階です。プログラムの任意の一次述語論理の全称量化されたプロパティについて、プロパティベースのテストとして書くことができるものについては、それ自体が数百万時間のテストで検証されたアーキテクチャモデルに対して、バイナリレベルで証明を生成できると考えています。これをマルチスレッドプログラム、分散システム、高階プロパティ、非機能プロパティ、実際のデプロイメント設定に拡張する課題は、数千人の検証エンジニアと研究者にわたる、さらに何年もかかる作業です。

これらの課題を解決する上で、ランダムテストと一般的なランダム探索が貴重なツールとなるでしょう。テスト実行は測定であり、検証に使用するモデルを偽証、強化、検証するために利用できる実際の基盤システムに関する情報を提供します。テストの検証可能性は、その採用の大きな推進力であり続け、他の形式手法への入り口となり、ソフトウェアが「形式的に検証された」と聞いたときに、何が残されたのかを疑問に思ったり、誰かがそこにバグを見つけるのを待ったりするのではなく、信頼するのに役立つかもしれません。