TLA+で検証できること・できないこと
What TLA+ can and can't check (buttondown.com)
要約
この記事は、形式検証ツールTLA+の能力と限界について解説しています。TLA+はシステムの安全性やライブネスといったプロパティを検証するのに優れていますが、特定の振る舞いの存在を証明する性質や、複数のステップにまたがる性質、ハイパープロパティなどは直接検証できません。これらの限界を理解することが、TLA+を効果的に活用する鍵となります。
全文翻訳
TLA+ で検証できること、できないこと
先週、Claude Code の開発者である Boris Cherny 氏が、Opus が TLA+1 を使ってコード内の競合状態を発見できたと述べました。
そして今、インターネット上の誰もが形式検証について語っています。
長年の教育者(1 2) および TLA+ の提唱者(2) として、これは本当にエキサイティングです! TLA+ は複雑な並行システムを設計し、それらがバグフリーであることを保証するのに優れています。しかし、冷静さを保つ提唱者として、この新しい熱狂は私を心配させます。形式手法がエージェント型ソフトウェア開発の問題を一度きりで解決するという意見を多く目にしますが、それはナンセンスです。
TLA+ が保証できることの弱点、例えば「正しい設計が自動的に正しいコードに翻訳されるわけではない」(3) といったことについては、すでに十分な言葉が費やされてきました。そこで、このニュースレターでは、別の制限に焦点を当てたいと思います。それは、ある性質を検証するためには、検証すべき性質が必要だということです! では、TLA+ では表現することすらできない性質とは何でしょうか?
(これは TLA+ の基本的な知識があることを前提としています。もしあなたが全くの初心者であれば、上記の [1] [2] をチェックするか、こちら を読んでください。)
TLA+ で検証できること
TLA+ はシステムを一連の振る舞いに分割します。各振る舞いは状態のシーケンスです。例えば、「ライト1が緑、次に黄色、次に赤」といった具合です。各状態では、「ライト4が緑」や「全てのライトが赤」といった通常のブール式を表現できます。また、3つの「時間論理」演算子で式を変更することもできます。
[]P(「常に P」)は、P が現在の状態 および 全ての将来の状態において真である場合に真となります。例:[](at_most_one_green)は、今後全ての状態において緑のライトが最大で1つしか存在しない場合に真となります。P'(「P プライム」)は、P が次の状態において真である場合に真となります。例:light="green" && light'="red"は、ライトが緑から赤に変わる場合に真となります。<>P(「やがて P」)は、P が現在の状態 または 少なくとも1つの将来の状態において真である場合に真となります。例:<>(light4 = "yellow")は、ライト4が黄色であるか、将来の状態のいずれかで黄色になる場合に真となります。
P がシステムの性質であると言うとき、それは全ての振る舞いの初期状態において真であることを意味します。したがって、[]P という性質をチェックする場合、それは「全ての振る舞いにおいて []P が真である」ことを意味し、これは「常に」の定義により、その初期状態からの全ての将来の状態において P が真であることを意味します。つまり、全ての振る舞いの全ての状態において真であることを意味します。これを 不変条件 (invariant) と呼び、TLA+ でチェックする最も基本的な性質の1つです。
[] をプライムと組み合わせることで、アクション性質 (action properties) や、変数の変化を追跡する性質を得ることもできます。[](x' >= x) は、x の新しい値が常に古い値以上である場合に真となります。もう一つ面白いのは [](P => P') です。これは、P が真になったら、二度と偽になることはないことを意味します。実際の TLA+ は、「スタッター不変性 (stutter-invariance)」と呼ばれるもののために少し複雑ですが、それは追加の詳細です。アクション性質と不変条件はどちらも 安全 (safety) 性質 であり、これは大まかに言うと「悪いことは決して起こらない」ということです。安全とライブネスに関する記事をここに書きました。
ちなみにライブネスとは、「良いことは常に起こる」ということです。全てのライブネス性質は <> に基づいています。単独では、<>P は「全ての振る舞いの少なくとも1つの状態において P が真である」ことを意味しますが、これは通常、システムの性質としては弱すぎます。しかし、組み合わせることで、より興味深いライブネス性質を作成できます。
[]<>Pは、全ての状態において、P が少なくとも1つの将来の状態において真である場合に真となります。これは、「ノードが新しいリーダー選挙を行った場合、最終的にリーダーに合意する」といった回復メカニズムを表すことができます。<>[]Pは、ある時点で P が真になり、その後ずっと真であり続ける場合に真となります。これは、アルゴリズムが正しい結果で終了することを示すのに役立ちます。[](P => <>Q)は、P が真である全ての状態において、Q が真である将来の状態が存在する場合に真となります。これは、P が最終的に Q を引き起こすこと、あるいは「キューに入れられた全てのメッセージが最終的にリーダーの履歴に現れる」ことを示すことができます。この式の解析は少し紛らわしいため、P ~> Q(P は Q を導く)という糖衣構文があります。
ENABLED や <<A>>_v のような他の演算子もあり、これらは他のトリックを可能にしますが、チェックするものの大部分は不変条件、アクション性質、ライブネスです。そして、リファインメント(安全とライブネスの組み合わせであり、それ自体がトピックです)です。
TLA+ でできないこと
明白なことから始めましょう。もしあなたの性質を論理式として表現する方法を知らなければ、TLA+ は助けになりません。他のどの形式手法も同様です。もし人間の「鳥」という概念を形式化できないなら、あなたのアプリが鳥を認識することを証明できません。そして残念ながら、私たちが気にする多くの重要な性質がこのカテゴリに分類されます。
次に、過度に具体的なもの。TLA+ の安全性質は、個々の状態(不変条件)または単一ステップ(アクション性質)のレベルで機能します。「削除」を押してから「元に戻す」を押すと元の状態に戻る」とか、「電源」が押されたらコンピューターが10ステップ以内に起動する」といった、2つ以上のステップにまたがる性質をネイティブに定義することはできません。また、浮動小数点演算に関する性質や、実時間ではなく論理時間に関する性質も定義できません。
次に、私が最も興味を持っている制限です。TLA+ の性質は、暗黙的に全ての振る舞いに量化されます。[]P をチェックすることは「全ての状態で P が真である」ことを意味すると言いましたが、実際には「全ての振る舞いについて、その振る舞いの初期状態において []P が真である」ことを意味します。TLA+ がシステムに対してチェックできる性質は、個々の振る舞いすべてに対して真である性質でなければなりません。
それは何を省略するのでしょうか? 予想以上に多くのものを省略します!
まず、「P が真である ような 振る舞いが存在する」ということはできません。したがって、実際に到達しなくても、P が可能であることを言うことができません。この例としては、ゲームが勝てることを証明することが挙げられます。これを 到達可能性性質 (reachability properties) と呼びます。より高度な到達可能性性質としては、「全ての初期状態から P が到達可能である」とか、「Q が真である任意の状態から P が到達可能である」といったものがあります。
また、振る舞いの 集合 に対する性質を定義することもできません。これは ハイパープロパティ (hyperproperty) と呼ばれます。例えば、電話のハードウェアをモデル化していて、省電力モードが常に通常モードよりも少ないエネルギーを使用することを検証したいとします。その性質は「アクションの任意のシーケンスは、省電力モードで通常モードよりも多くの電力を使用しない」ということです。これを反証するには、互いに同一であるが、一方は省電力モードで開始し、もう一方はそうでないという2つの振る舞いを私に与える必要があります。そして、通常モードの方が電力が少ないという結果になります。単一の振る舞いでは不十分なので、これは TLA+ で自然にチェックすることは不可能です。
ハイパープロパティはニッチに見えるかもしれませんが、多くのセキュリティ性質 や全ての統計的性質(「95パーセンタイル応答時間は5ms」)をカバーしています。
最後に、これは少し学術的ですが、状態空間全体に対する性質を定義することはできません。例えば、状態 X から Y へのパスが1つしかないと言うことはできません。これが実用上どれほど役立つかは分かりません。これらの「メタプロパティ」のほとんどは意味を持つ可能性があるように思えますが、具体的に何であるかは分かりません。
「TLA+」が「できる」こと
TLA+ がこれらのことをできないと言ったのは、少し単純化しすぎました。つまり、あなたが仕様を書いている場合、そしてその仕様が構築したいシステムに直接対応している場合、TLA+ はこれらの性質をシステムのものとして表現できません。しかし、補助変数 (auxiliary variables) を使って2ステップの性質を 模倣 (mimic) できます。例えば、全ての状態変更を state_history というシーケンスに格納し、そのシーケンスに対する不変条件として性質を定義します。また、自己構成 (self-composition) を使って一部のハイパープロパティを模倣できます。自己構成された仕様の各振る舞いは、実際のシステムの2つの振る舞いになります。主要な TLA+ モデルチェッカー (TLC) は、新しい REACHABLE キーワード で最も基本的な到達可能性性質をチェックでき、TLCGet で一部の状態空間性質をチェックできます。Andrew Helwer は、公平性と「マシンクロージャ」を使って「常に到達可能」を模倣する 驚くべき投稿 をしています。
これらは便利なハックですが、それでもハックです。それぞれに理解するための多くの工夫が必要であり、深刻な欠点が伴います。補助変数はリファインメントを台無しにし、自己構成は状態空間を指数関数的に増加させます。ハックは他の TLA+ の機能とよく組み合わされず、表現したい性質の全ての複雑さをカバーしません。そして最悪なことに、モデルが奇妙で乱雑に見え、実際のシステムに対応しなくなります。
異なるツールを異なる焦点で使用することもできます。CTL は到達可能性性質を、PRISM は確率的性質などを扱えます。これらは、TLA+ ができることに対しては劣るというトレードオフがありますが、もちろん、どれも論理的に表現できない性質を扱えません。
最終的に、TLA+ は多くの「低いところにある果実」を摘むのにかなり優れています。不変条件とライブネスは、私たちが気にする多くのことをカバーしており、TLA+ はそれらを表現しチェックするのに合理的に優れています。TLA+ を使って「雰囲気コード (vibe code)」をチェックすることには多くの可能性(そして多くの落とし穴 (4))があります。しかし、それを表現することすらできない、ましてやチェックできないことも多くあります。
プログラマーのための論理 オンライン講座
先週のライブストリームに参加してくださった皆さん、ありがとうございました! 全編は こちら で視聴できます。
- 「Temporal logic of actions」のことです。これは並行システムにおけるバグを見つけるために使用される仕様言語です。名前の由来の説明はこちら。↩
- (そして、形式手法についてこれほど熱心な人物がなぜテスト会社に参加したのかという問いに対しては、彼らのブログにそのうち記事が出るはずです。)↩
- (原文のリンクは
https://buttondown.com/hillelwayne/archive/what-if-the-spec-doesnt-match-the-code/ですが、提供された本文ではhttps://buttondown.com/hillelwayne/archive/what-if-the-spec-doesnt-match-the-code/となっています。原文のまま保持します。) - (原文のリンクは
https://buttondown.com/hillelwayne/archive/llms-are-bad-at-vibing-specifications/ですが、提供された本文ではhttps://buttondown.com/hillelwayne/archive/llms-are-bad-at-vibing-specifications/となっています。原文のまま保持します。)