本文へスキップ
hdknr blog

TLA+ と TLC

Leslie Lamport が考案した形式仕様記述言語 TLA+ と、そのモデル検査器 TLC。設計の到達しうる全状態を探索し、不変条件違反・デッドロック・活性の破れを反例トレースつきで返す。並行処理や分散システムの設計バグを実装前に見つける道具

概要

TLA+(Temporal Logic of Actions)は、Leslie Lamport(2013 年チューリング賞)が考案した形式仕様記述言語。システムの状態(変数)と、状態がどう変わりうるか(アクション)を数学的に書く。TLC はその仕様を読み込み、到達しうる状態をすべて列挙して性質を検査するモデル検査器で、「TLA+ の検査器」と言えばふつう TLC を指す。

テストが人間の思いついた実行順しか試さないのに対し、TLC はありうる実行順(インターリーブ)をすべて試す。並行処理・分散システムの競合状態を、コードを書く前の設計段階で見つけるのが役目。AWS や Microsoft Azure の設計検証で使われてきた。

詳細

道具の構成

名前役割
TLA+仕様を書く言語。型は持たない
TLC到達状態を列挙して性質を検査するモデル検査器。tla2tools.jar に含まれる
TLAPSTLA+ Proof System。性質を数学的に証明する対話的な証明系
TLA+ Toolbox / VS Code 拡張TLC を呼び出す IDE(Toolbox は Eclipse ベース)

いずれも公式の tlaplus プロジェクトが提供し、tla2tools.jar は tlaplus/tlaplus の GitHub Releases から入手できる。コマンドラインからは次のように実行する(仕様 .tla と、定数や検査する性質を書く設定 .cfg を渡す)。

java -cp tla2tools.jar tlc2.TLC -config Stock.cfg Stock.tla

書き方の要点

探索の仕組み

  1. Init を満たす初期状態をすべて作る
  2. Next を各状態に適用し、到達できる状態をすべて辿る。どのプロセスが次に動くかの組み合わせも別々の遷移として扱う
  3. 性質を破る状態を見つけたら、初期状態からの手順(トレース)を出して止まる

既定は幅優先なので、安全性の違反は最短の反例トレースとして返る(複数ワーカーでは厳密に最短とは限らない)。-dfid で反復深化の深さ優先、-simulate でランダムシミュレーション、-continue で最初の違反で止めずに続行する。

例:在庫 1 個を 2 人が「確認 → 減算」の 2 ステップで買うモデルでは、到達状態は 10 個。「b1 確認 → b2 確認 → b1 減算 → b2 減算」の 4 ステップで在庫が -1 になる反例を TLC が返す。確認と減算を 1 ステップ(アトミック)にすると、この実行順は存在しなくなる。

検証できる性質

種類意味指定反例の形
不変条件(安全性)どの実行順でも常に成り立つINVARIANT違反に至る有限の手順
デッドロック(安全性)どのアクションも実行できない状態既定で検査。-deadlock で外す止まった状態までの手順
活性いつか必ず良いことが起きる(<>P、P ~> Q)PROPERTY同じ状態に戻るループを含むトレース

活性の検査には公平性の仮定(WF_vars(Next) など)が要る。仮定がないと「ずっと足踏みする」実行が許され、「いつか終わる」が成り立たない。

実績

2015 年の論文「How Amazon Web Services Uses Formal Methods」(Communications of the ACM)は、S3 や DynamoDB の設計に TLA+ を使った経験を報告している。DynamoDB では、TLC が見つけたバグの最短反例が 35 ステップに及んだ。Microsoft は Azure Cosmos DB の 5 つの一貫性レベルの仕様を Azure/azure-cosmos-tla で公開している。

限界と対策

TLAPS との使い分け

TLC は有限のモデルを総当たりするので、保証は絞った範囲内に限られる。任意の台数・任意の長さで成り立つことを示すには TLAPS で証明する(人間が証明の構造を書き、各ステップを自動証明器に検査させる)。手間が大きいので、まず TLC で設計の穴を潰し、特に重要な性質だけを TLAPS で証明するのが現実的な順番。

Quint から使う

TLA+ と同じ論理をプログラマ向けの構文で書ける Quint は、quint verify --backend=tlc で仕様を TLA+ に変換して TLC に渡せる。在庫の例では TLA+ 版と同じ 10 状態を探索した。ただし Quint 経由の TLC は -deadlock 付きで起動されるのでデッドロックを検査しない。

エージェントの検査役として

要求仕様書作成ループの Claude Code プラグイン spec-loop では、仕様レビューの判定役 Formal Checker が、並行・リトライ・取り消しを含む業務フローの検査に TLC を使う。Java と tla2tools.jar が手元に無ければ判定役を起動せず、業務フローの検査を手作業の総当たりで代用することもしない。

TLC の起動コマンドは環境で違うので、spec-loop は付属の check-tlc.py で通るモデル(終了コード 0 と No error has been found)と違反するモデル(is violated)の 2 つを実際に検査させてから「TLC が使える」とみなす。後者は、起動コマンドを書き間違えて何も検査していないのに「エラーなし」と言う状態を弾く陽性対照。

ソフトウェア以外のモデル化:契約書

契約の状態(発効・履行中・停止・解除)と、通知・支払い・期限経過によるアクションを TLA+ で書くと、「解除後に新たな履行義務が発生しない」のような不変条件や、終了状態なのにアクションが要求されるデッドロックを反例つきで検出できる。期日や計算式の両立は SMT ソルバ の担当。

関連ページ

ソース記事