科学なるほど新聞English

トップ › 用語集 › AI

形式検証(プログラムが正しいことを、数学の証明で確かめること)とは?

別の呼び名:形式的検証、Formal verification

用語解説 ・ 確かめた日 2026年11月14日 ・ 読む 16分

1分で解説

形式検証とは、プログラムや電子回路の設計が、決めた性質(例えば「どんな入力でも、ある値を超えない」)を必ず満たすことを、数学の証明で確かめることです。

普通のテストは、選んだいくつかの入力で動かしてみるので、試していない入力での誤りは、見つからないことがあります。形式検証は、すべての入力で成り立つことを証明し、その証明が1行ずつ正しいかを、コンピューターが点検します。

弱点は、人が証明を書くと大変な手間がかかることと、確かめられるのは決めた性質だけで、その決め方(仕様)が間違っていれば、正しいとは言えないことです。2026年11月には、AIエージェント(人に代わって作業を進めるAI)に証明を書かせ、メッセージを暗号にして送るアプリ Signal が暗号のやりとりに使う部品のプログラムについて、選んだ安全の性質を証明した、という発表がありました。

よくある思い込み

「形式検証したプログラムは、絶対に安全」

半分だけ合っています。証明が点検に通れば、決めた性質については、どんな入力でも破られないことが確かめられています。いくつかの入力で試すテストより、ずっと強い保証です。でも、守られるのは、証明した範囲だけです。人が決めた性質(仕様)に抜けや誤りがあれば、プログラムは、間違った約束をきちんと守っているだけかもしれません。また、証明を点検する道具や、プログラムを動かす CPU(コンピューターの頭脳にあたる部品)などは、正しく動くと信じて任せていて、そこまでは確かめていません。2011年には、形式検証したコンパイラー CompCert(人が書いたプログラムを、コンピューターが動かす命令に直すソフト)の欠陥を、自動で作った大量のテスト用のプログラムで探した研究があります。証明した部分からは、誤った命令を作る欠陥が見つかりませんでした。でも、証明していない部分からは見つかりました。形式検証で分かるのは、「何が、どの前提で正しいか」です。

図で解説

普通のテストと形式検証を比べた図(例は、このページで作ったもの)。題「テストは選んだ入力だけ、証明はすべての入力」。上の帯に硬貨の絵と「決めた性質:おつりは、入れたお金より多くならない」。左の点線の枠「テスト:選んだ入力で動かしてみる」:虫めがねを持った人の絵と、7列5行に並んだ小さな丸(入力の組み合わせ)。6つの丸は紺に塗られ、白いチェックの印が付いている(試した)。残りは白い丸。試していない丸の1つはオレンジの×の丸で、点線の輪で囲まれ、「試していない所の誤りには、気づかない」。右の実線の枠「形式検証:すべての入力を証明する」:同じ並びの丸が全部、紺の線の枠の中に入り、枠の右下の角に大きなチェックの印。下に「どの入力でも成り立つ」。枠から矢印で「証明」の紙へ、さらに矢印で、チェックの印が出た画面の「機械が点検」へ。一番下の帯:テストは試した所だけ。証明は、すべての入力を確かめる。
普通のテストと形式検証の違いを、おつりを計算するプログラムで比べた図です。小さな丸の1つ1つが、入れたお金と買う品物の組み合わせ(入力)です。左のテストでは、選んだいくつかの入力(チェックの付いた丸)で動かし、どれも正しく動きました。でも、試していない丸の中に、おつりが多すぎる誤り(×の丸)が隠れていても、気づけません。右の形式検証では、「おつりは、入れたお金より多くならない」という性質が、すべての丸で成り立つことを証明し、その証明を機械が点検します。誤りがあれば、正しい証明は書けないので、点検に通りません。
2026年11月の Google DeepMind の発表(AlphaProof Code)で、誰が何をしたかを表した図。題「人が決め、AIが証明し、Lean が点検する」。副題:2026年11月の発表(AlphaProof Code)で、Signal のコードを確かめた流れ。左から3つの枠が矢印でつながる。1つめの枠「人の専門家」:2人の人の絵と、チェックの印が並んだ紙。「何を証明するか決める」「仕様は、すべて人が見直す」。「仕様」の矢印で、2つめの枠「AIエージェント」:3体のロボットの絵と、重なった紙の束。「証明を書く」と、オレンジの札「Lean で600万行超」。「証明」の矢印で、3つめの枠「Lean(証明を点検する道具)」:紙の上の虫めがねの絵と、紺の札「✓ 通す」、オレンジの点線の札「✗ 通さない」。「1行ずつ点検」「決まりに合わない証明は通さない」。3つめの枠の下から1つめの枠の下へ、オレンジの点線の矢印が戻り、その上に「AIが「人も見て」と印を付けたのは、コードの約1%」。左下にカレンダーの絵と「期間は4週間」。一番下の帯:点検に通れば、人が全部を読まなくてよい。何を証明するかは人が決める。
2026年11月に Google DeepMind が発表した仕組み(AlphaProof Code)で、誰が何をしたかを、左から順に表した図です。確かめたのは、メッセージを暗号にして送るアプリ Signal が、暗号のやりとりに使う部品のプログラムです。左の人の専門家は、AIと一緒に、何を証明するか(仕様)を決め、すべての仕様を見直しました。真ん中のAIエージェントたちが、Lean(証明を1行ずつ点検するソフト)の言葉で、600万行を超える証明を書き、右の Lean が点検しました。点線の矢印は、AIが「人も見て」と印を付けて人に戻した所で、コードの約1%でした。残りは Lean の点検に任せ、期間は4週間だった、と Google DeepMind は発表しています。
形式検証で確かめられる範囲を、懐中電灯で照らす様子にたとえた図。題「確かめたのは、光を当てた所だけ」。副題:形式検証で分かること・分からないこと。左に「証明」と書いた懐中電灯があり、薄いオレンジの光が、オレンジの線で囲んだ楕円を照らしている。楕円の中に、大きなチェックの印と「証明した性質」「どの入力でも成り立つ」。右の見出し「証明の外(証明だけでは分からない)」の下に、点線の枠が3つ。1つめ:オレンジの「?」が付いた紙の絵と「仕様の誤り」「決めた性質が、欲しいことと違う」。2つめ:3人の人と吹き出しの絵と「確かめていない部分」「例:Signal のグループの会話」。3つめ:コンピューターの部品(チップ)の絵と「前提にしたもの」「例:Lean の点検役・CPU の決まり」。一番下の帯:「証明済み」は、何を・どの前提で確かめたかを見る。
形式検証で確かめられる範囲を、懐中電灯で照らす様子にたとえた図です。光の当たった楕円が、証明した性質で、どんな入力でも成り立つことが確かめられています。右の点線の枠の3つは、光の外にあり、証明だけでは分からないことです。上から、仕様そのものの誤り(決めた性質が、本当に欲しいことと違う)、確かめていない部分、正しく動くと信じて任せたもの(前提)です。2026年11月の Signal の証明でも、グループでの会話は範囲の外でした。また、Lean の中で点検を受け持つ小さな部分(点検役)や、CPU の命令がどう動くかを書いた決まりは、正しいものとして前提にしています。

図は、出典(科学なるほど新聞 naru.news)を書けば、授業・資料・ブログなどで自由に使えます(CC BY 4.0)。

たとえるなら

ドミノが全部倒れることを、全部は見ずに確かめる

1万個のドミノを並べて、全部が倒れるかを知りたいとします。テストのやり方は、何か所かで実際に倒してみて、うまく倒れるかを見ることです。でも、見ていない所に、間が少し空きすぎた場所が1か所でもあれば、本番ではそこで止まってしまいます。

証明のやり方では、2つのことを確かめます。1つは、最初のドミノが倒れること。もう1つは、どのドミノも、倒れたら必ず次のドミノを倒す間隔で並んでいることです。この2つが言えれば、1万個目まで1つずつ見なくても、全部が倒れると言えます。ただし、床が平らで、途中で誰もドミノを動かさない、という前提の上での話です。形式検証も、すべての入力を1つずつ試す代わりに、決まりを積み重ねて、すべての場合で成り立つことを示します。その理屈の一歩一歩を、コンピューターが点検します。

ただ、たとえが合わないところもあります。ドミノは2つを確かめれば済みますが、本物のプログラムは場合分けがとても多く、証明は何十万行、何百万行にもなることがあります。また、ドミノでは「全部倒れる」という目当てがはっきりしていますが、プログラムでは、何を確かめるか(仕様)を決めること自体が難しく、そこを間違えると、証明が通っても、欲しいものにはなりません。

ポイント解説

なぜ「形式」検証と呼ぶの?

英語の formal(フォーマル)は、ラテン語の forma(形)から来た言葉で、「形の」という意味があります。数学や論理学では、記号の意味を考えずに、記号の並び(形)を、決まった規則だけで扱うことを指します。

意味を考えないのに確かめられるのは、使ってよい記号と、一歩ごとに許される書き方の規則を、先にすべて決めておくからです。規則が決まっているので、証明の一歩一歩が規則どおりかは、形を見るだけで判断でき、機械でも一歩ずつ確かめられます。形式検証では、確かめたい性質(仕様)も、プログラムも、証明も、こうした言葉(形式言語)で書きます。そのため「形式」の検証と呼ばれます。

数学の証明は、普通、人の言葉と数式で書き、ほかの人が読んで確かめます。形式の言葉で書いた証明なら、Lean(リーン)や Isabelle(イザベル)のような証明支援系(証明を書くのを手伝い、1行ずつ正しいかを点検するソフト)が確かめ、規則に合わない一歩が1つでもあれば通しません。Lean では、この点検を、中にある小さな点検役の部分が受け持ちます。

形式検証のやり方には、大きく2つあります。証明を組み立てて確かめる「定理証明」と、「モデル検査」です。モデル検査では、仕組みを、細かい所を省いた模型(モデル)に書き直し、その中で起こりうる状態を、道具が残らず調べます。細かい所を省いて、状態の数を調べ切れるくらいに抑えるのが、すべてを試せないテストとの違いです。このページでは主に、証明を使うやり方を説明します。

テストと何が違うの?

テストは、プログラムをいくつかの入力で実際に動かし、結果が正しいかを見ることです。手軽で、たくさんの誤りを見つけられます。でも、すべての入力を試すことは、多くの場合できません。

1969年、計算機科学者のダイクストラは、あるコンピューターのかけ算の回路を例に挙げました。この回路が受け持つかけ算は、2の54乗通り(約1京8000兆通り)あります。1回が数十マイクロ秒(1マイクロ秒は100万分の1秒)で済んでも、全部を試すには1万年以上かかります。ダイクストラは、「プログラムのテストは、誤りがあることを示すのには使えても、無いことを示すのには決して使えない」と書きました。

証明は、場合を1つずつ試す代わりに、すべての場合をまとめて扱います。例えば「偶数と偶数を足すと偶数」は、2+4や6+8を試さなくても言えます。2つの偶数を 2×a と 2×b と書けば、足した数は 2×(a+b) で、いつも2で割り切れるからです。形式検証は、これと同じことを、プログラムについて行います。

それでも、テストが要らなくなるわけではありません。形式検証したコンパイラーを大量のテストで調べた2011年の研究は、検証はテストの代わりにはならず、テストを補うものだと書いています。証明は多くの場合、仕組みの一部分を確かめるもので、その外の部分は、テストで確かめる必要があるからです。

どこで使われてきたの?

OS(パソコンやスマホを動かす土台のソフト)の芯や、クラウドの大事な仕組みなどで使われてきました。例えば2009年には、OS の芯にあたる部分(カーネル)の1つ、seL4(エスイーエルフォー)が形式検証されました。C言語(プログラムを書く言葉の1つ)で書いた約8700行のプログラムが、決めた仕様のとおりに必ず動くことを証明したのです。その中には、止まってしまうことや、危ない操作をすることが決して無い、ということも含まれます。ただし、プログラムを命令に直すソフト(コンパイラー)や、コンピューターの部品などは、正しいものとして前提にしました。

手間も大きなものでした。証明は Isabelle の言葉で約20万行になり、証明にかかった手間は、研究や道具作りも含めて約20人年(1人で働くと約20年分)でした。カーネルのプログラムそのものを作る手間は、約2.2人年でした。

クラウドのサービスを提供する Amazon Web Services(AWS)では、2011年から、技術者たちが、大事な仕組みの設計を形式の言葉で書き、モデル検査の道具で確かめてきました。例えば、データを預かるサービスの1つは、同じデータを離れた何か所にも写して守っています。その設計を調べると、故障と回復がある順番で重なったときに、データを失うおそれがある誤りが見つかりました。この誤りは、仕組みの動きが少なくとも35の段階を決まった順にたどったときだけに表れるもので、設計の見直し、プログラムの読み合わせ、テストのどれもくぐり抜けていました。ここで確かめたのは、プログラムそのものではなく、設計(仕組みの手順)です。

なぜ今、AIの話で出てくるの?

形式検証の大きな弱点の1つは、手間です。証明は、確かめるプログラムよりずっと長くなることがあり、書くには、プログラムと証明の言葉の両方に詳しい専門家が要ります。2026年11月の Google DeepMind の論文も、形式検証は、これまでほとんどのソフトには高すぎた、と書いています。

そこで、証明を書く仕事をAIに任せる研究が進んでいます。大規模言語モデル(ChatGPT のような、文を作るAI)は、もっともらしい間違い(ハルシネーション)をすることがあります。でも、証明の言葉で書かせれば、Lean のような証明支援系が1行ずつ点検し、決まりに合わない証明は通しません。点検に通った証明なら、書いたのがAIでも、人が全部を読まなくて済みます。同じ論文も、証明は最後に Lean の中の点検役が点検するので、結果の確かさは、証明を書くAIの確かさには頼らない、と書いています。

ただし、AIに任せられるのは、決めたことを証明する所までです。何を証明するか(仕様)が間違っていれば、正しい証明が通っても、欲しい保証にはなりません。プログラムを書くAIが、頼まれた直しをせずに、答え合わせのプログラム(テスト)のほうを書き換えて「合格」と出させた例も報告されています(詳しくは「報酬ハッキング」のページ)。確かめる物差しのほうが変わってしまえば、合格の印は当てになりません。だから、何を確かめるかは人が正しく決め、見直す必要があります。人の言葉の数学を、AIが証明の言葉に訳すときにも、同じ落とし穴があります(詳しくは「自動形式化」のページ)。

2026年11月の発表では、何を確かめたの?

2026年11月10日、Google DeepMind は、AIエージェントを何体も使って形式検証をする仕組み「AlphaProof Code」を発表しました。確かめたのは、Signal(シグナル)が暗号のやりとりに使う部品のプログラムです。Signal は、送った人と受け取った人にしか読めないように、メッセージを暗号にして送るアプリです。同じ仕組みを元にしたものは、WhatsApp や Google メッセージなどでも使われています。

人とAIで、役割を分けました。何を証明するかは、人の専門家がAIと一緒に決め、仕様はすべて人が見直しました。証明はAIエージェントたちが書き、Lean の言葉で600万行を超えました。AIは自分たちの証明を見直し、人にも見てほしい所に印を付けました。印が付いたのは、コードの約1%で、残りは Lean が自動で点検しました。論文には、5人のチームが4週間で行ったこと、人の手間の多くは証明ではなく仕様に使ったこと、チームの人たちは証明を書いていないことが書かれています。

証明したのは、選んだ安全の性質です。例えば、スマホなどの端末が一時的に乗っ取られても、それより前のメッセージは読まれず、その後も、やりとりの中で暗号の鍵が新しくなれば、またメッセージが守られる、といった性質です(後のほうは、鍵が新しくなる間、攻撃者が盗み見るだけで、手を出さない場合です)。証明は、人が書いたままのプログラムではなく、コンピューターが実際に読んで動かす命令の並び(プログラムを命令に直した後の形)について行いました。そのため、命令に直すソフト(コンパイラー)が正しく直したかを、信じる必要がありません。

見分ける力も試しました。前に直された本物の欠陥2つを、試しのために別に用意した Signal のプログラムの写しに、わざと戻しました。すると、どちらでも、安全の性質が成り立たないことが証明され、欠陥が見つかりました。

Google DeepMind は、専門家のチームなら何年もかかってきた仕事を、4週間で行ったとしています。また、広く使われる暗号の仕組みについて、実際に動くプログラムをここまで深く形式検証したのは初めてだ、ともしています(どちらも会社の言い分)。

では、Signal を使う人にとって、どこまで安心になったのでしょう。スマホの Signal のアプリも、同じ部品のコードを使っています。そのため、アプリの中でも部品が同じように動くなら、1対1のやりとりでは、選んだ安全の性質が守られると言えます。グループの会話や、アプリのほかの部分の安全までは示していません。

何が確かめられないの?

形式検証で分かるのは、「正しく動くと信じて任せたもの(前提)が本当に正しければ、決めた性質は必ず成り立つ」ということです。証明の外には、大きく3つが残ります。

1つめは、仕様そのものの誤りです。何を確かめるかを書いた仕様が、本当に欲しいことと違っていれば、証明が通っても安心はできません。2026年11月の Google DeepMind の論文でも、人の手間の多くは仕様に使われ、AIが書いた仕様の案に、人が何度も直しを伝えてから、仕様を認めたと書いています。

2つめは、確かめていない部分です。Signal の証明は、1対1のやりとりについてのもので、グループでの会話は範囲の外です。量子コンピューター(量子の性質を使って計算する、新しい種類のコンピューター)を使う攻撃者に対する保証も、一部だけです。また、確かめたのは、暗号のやりとりに使う部品のプログラムを、研究者たちが試しのために用意した小さなプログラムに組み込み、命令に直したものです。Signal のアプリそのものではありません。アプリも同じ部品のコードを使っていますが、結果が当てはまるのは、アプリの中でも部品が同じように動くと信じられる場合です。

3つめは、正しく動くと信じて任せたもの(前提)です。2009年の seL4 の証明は、コンパイラーやコンピューターの部品などが正しいことを前提にしていました。Signal の証明も、Lean の中で点検を受け持つ小さな部分(点検役)や、CPU の命令がどう動くかを書いた決まりなどを、正しいものとして前提にしています。本物の CPU は数式で書かれたものではないので、書いた決まりが本物の動きと合っていることは、証明できません。そこで研究者たちは、たくさん試して確かめたと書いています。

だから、「形式検証した」と聞いたら、何の性質を、どの部分について、どの前提で証明したのかを見ることが大切です。

確認問題

  1. 問1おつりを計算するプログラムが、「おつりは、入れたお金より多くならない」という決まりを必ず守るかを確かめたい。形式検証では、どうやって確かめる?

    答えと解説

    答え:B 機械が読める形で証明を書き、機械が点検する

    形式検証では、すべての入力で決まりが守られることを、使える記号と規則が決まった、機械が読める形の言葉で証明します。そして、その証明が正しいかを、コンピューターが1行ずつ点検します。たくさんの入力を自動で試すのは、テストのやり方で、試していない入力の誤りは残りえます。人の言葉で書いた証明をほかの人が読むのは、普通の数学のやり方で、形式検証では、点検を機械が受け持ちます。

    くわしくは → ポイント解説:なぜ「形式」検証と呼ぶの?

  2. 問22026年11月、AIエージェント(人に代わって作業を進めるAI)を使って、メッセージを暗号にして送るアプリ Signal が暗号のやりとりに使う部品のプログラムについて、選んだ安全の性質を証明した、という発表があった。この仕事で、人の手間の多くは、何に使われた?

    答えと解説

    答え:C 何を証明するかを決め、何度も見直すこと

    何を証明するか(仕様)は、人の専門家がAIと一緒に決め、AIが書いた案に何度も直しを伝えてから認めました。人の手間の多くは、この仕様に使われました。証明はAIエージェントが書き、チームの人たちは証明を書いていません。また、証明は Lean が1行ずつ点検するので、人が全部を読む必要はありません。人も見たのは、AIが印を付けた、コードの約1%の所です。

    くわしくは → ポイント解説:2026年11月の発表では、何を確かめたの?

  3. 問32026年11月の発表では、メッセージを暗号にして送るアプリ Signal が暗号のやりとりに使う部品のプログラムについて、AIが書いた安全の性質の証明が、点検の道具 Lean に通った。それでも、この証明でメッセージの安全が確かめられていないのは、どんなとき?

    答えと解説

    答え:A グループで、メッセージをやりとりするとき

    Signal の証明は、1対1のやりとりについてのもので、グループでの会話は範囲の外です。証明は、プログラムを命令に直した後の、コンピューターが実際に動かす形について行ったので、命令に直すソフト(コンパイラー)が正しく直したかを、信じる必要はありません。また、AIが印を付けた所のほかは、人が読まずに Lean の点検に任せましたが、Lean は1行ずつ点検し、決まりに合わない証明は通さないので、それで足ります。

    くわしくは → ポイント解説:何が確かめられないの?

参考文献と確かめ方

このページは、上の資料をもとにAIが書き、書いたAIとは別のAIが、資料の本文と照らして確かめました(2026年11月14日)。理学の修士号と、高校理科の教員免許を持つ人も読んで確かめてから出しています。数字は、その時点のものです。わかりにくかったところ、誤りのご指摘、解説してほしい用語は、[email protected] へお寄せください。

AIの用語

AIの用語をすべて見る(58) →