本文へスキップ
hdknr blog
戻る

TLA+ のモデル検査器 TLC とは — 起こりうる全状態を総当たりして設計バグを見つける

「TLA+ の検査器」と言うとき、ふつうは TLC というモデル検査器を指します。TLC は、形式仕様記述言語 TLA+ で書いたシステムの設計を読み込むツールです。起こりうるすべての状態を総当たりで探索し、設計上のバグを自動で見つけます。

TLA+ は Leslie Lamport(2013 年のチューリング賞受賞者)が考案した言語で、AWS や Microsoft Azure などで、分散システムや並行処理の設計検証に使われてきました。数学的な手法でソフトウェアの正しさを確かめる形式手法の代表的な道具の 1 つです。

この記事では、TLC が何をしているのか、何を検証できるのか、どこに限界があるのかを、小さな例を使って整理します。

TLA+ と TLC の関係

最初に用語を分けておきます。

名前役割
TLA+仕様を書くための言語。システムの状態(変数)と、状態がどう変わりうるか(アクション)を数学的に書く
TLCTLA+ の仕様を読み込み、到達しうる状態を列挙して性質を検査するモデル検査器
TLAPSTLA+ Proof System。性質を数学的に証明するための対話的な証明系

TLC と TLAPS は、どちらも公式の tlaplus プロジェクトで提供されています。TLC は tla2tools.jar に含まれていて、TLA+ Toolbox(Eclipse ベースの IDE)や VS Code の拡張機能から呼び出せます。コマンドラインから直接実行することもできます(後述)。

なぜテストでは並行処理のバグを見つけにくいのか

単体テストや結合テストが確かめられるのは、人間が思いついた実行シナリオだけです。並行処理のバグは、複数の処理のステップが特定の順番で交互に実行されたとき(インターリーブ)にだけ起きることが多くあります。そうした順番をテストで思いつくのは困難です。運良く思いついても、実際にその順番で実行させるのはさらに困難です。

TLC は発想が逆です。順番を人間が選ぶのではなく、ありうる順番をすべて試します。

TLC の仕組み

TLC は次の流れで検査します。

  1. 初期状態の生成:仕様の Init を満たす初期状態をすべて作る
  2. 状態空間の探索:遷移ルール(Next アクション)を各状態に適用し、到達できる状態をすべて辿る。どのプロセスが次に動くかの組み合わせも、すべて別々の遷移として扱う
  3. 反例トレースの出力:検査する性質が破れる状態を見つけると、初期状態からその状態に至る手順(トレース)を出力して止まる

探索は既定で幅優先です。そのため、安全性の違反について TLC が返す反例は、その違反に至る最短の手順になります(複数のワーカースレッドで探索した場合は、厳密に最短とは限りません)。人間がトレースを読んで原因を理解するうえで、これは大きな利点です。

なお、探索の方式は変えられます。-dfid で反復深化の深さ優先探索、-simulate でランダムな実行を繰り返すシミュレーションモードになります。最初の違反で止めずに探索を続けたいときは -continue を付けます。

小さな例:在庫 1 個を 2 人が同時に買う

「在庫があるか確認してから、在庫を 1 つ減らす」という処理を考えます。確認と減算が別々のステップになっていると、2 人の購入者が同時に「在庫あり」と判断し、両方が減らしてしまう可能性があります。

これを TLA+ で書くと次のようになります。Atomic が FALSE のときは確認(Check)と減算(Buy)が別のステップ、TRUE のときは 1 ステップ(CheckAndBuy)で行います。

---- MODULE Stock ----
EXTENDS Integers

CONSTANTS Buyers, InitStock, Atomic

VARIABLES stock, pc

vars == <<stock, pc>>

Init ==
    /\ stock = InitStock
    /\ pc = [b \in Buyers |-> "check"]

\* 非アトミック版: 在庫を確認する
Check(b) ==
    /\ ~Atomic
    /\ pc[b] = "check"
    /\ pc' = [pc EXCEPT ![b] = IF stock > 0 THEN "buy" ELSE "done"]
    /\ UNCHANGED stock

\* 非アトミック版: 確認した結果を信じて 1 つ減らす
Buy(b) ==
    /\ pc[b] = "buy"
    /\ stock' = stock - 1
    /\ pc' = [pc EXCEPT ![b] = "done"]

\* アトミック版: 確認と減算を 1 ステップで行う
CheckAndBuy(b) ==
    /\ Atomic
    /\ pc[b] = "check"
    /\ stock' = IF stock > 0 THEN stock - 1 ELSE stock
    /\ pc' = [pc EXCEPT ![b] = "done"]

Done ==
    /\ \A b \in Buyers : pc[b] = "done"
    /\ UNCHANGED vars

Next ==
    \/ \E b \in Buyers : Check(b) \/ Buy(b) \/ CheckAndBuy(b)
    \/ Done

Spec == Init /\ [][Next]_vars /\ WF_vars(Next)

\* 安全性: 在庫はマイナスにならない
NonNegative == stock >= 0

\* 活性: いつかは全員の処理が終わる
AllFinish == <>(\A b \in Buyers : pc[b] = "done")
====

TLA+ では、変数の次の状態をプライム付き(stock')で書きます。各アクションは、割り込まれずに実行される 1 ステップを表します。Done は全員が終わったあとに何も変えないステップで、終了した状態をデッドロックと誤検出させないために置いています。

検査の条件は、別の設定ファイル(Stock.cfg)で与えます。購入者 2 人、在庫 1 個、非アトミック版という最小の構成です。

CONSTANTS
    Buyers = {b1, b2}
    InitStock = 1
    Atomic = FALSE

SPECIFICATION Spec
INVARIANT NonNegative
PROPERTY AllFinish

b1 と b2 は、設定ファイルの中で「モデル値」として扱われる、互いに異なるだけの値です。

TLC を実行する

tla2tools.jar は tlaplus/tlaplus の GitHub Releases から入手できます。Stock.tla と Stock.cfg を置いたディレクトリで、次のように実行します。

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

TLC が辿る状態

この構成で到達できる状態は、購入者 2 人それぞれの段階(pc)と在庫数の組み合わせで、図の 10 個です。

在庫 1 個を 2 人の購入者が同時に買う TLA+ モデルの状態遷移図。初期状態から、どちらの購入者が先に在庫を確認し、どちらが先に減らすかの組み合わせで状態が枝分かれする。2 人とも在庫 1 を確認してから順に減らす経路では在庫が -1 になり、不変条件 stock ≥ 0 に違反する。片方が減らしたあとにもう片方が確認する経路では、在庫 0 を見て正常に終了する

TLC は、この図を初期状態から幅優先で辿りながら、各状態で NonNegative を確かめます。そして、赤い経路のような手順で不変条件が破れたところで、そのトレースを報告して止まります。

手順起きることstock
1初期状態1
2b1 が在庫を確認する(在庫あり)1
3b2 が在庫を確認する(在庫あり)1
4b1 が 1 つ減らす0
5b2 も 1 つ減らす-1

実際の出力では、b1 と b2 のどちらが先に動くかが入れ替わることがあります。それでも、トレースの長さ(初期状態から 4 ステップ)は同じです。

アトミックにすると

Atomic = TRUE にして確認と減算を 1 ステップにすると、この順番は存在しなくなります。CheckAndBuy は在庫が 1 以上のときだけ減らすので、初期在庫が 0 以上である限り、購入者や在庫を増やしても在庫はマイナスになりません。実装でこのアトミック性を確保する手段の 1 つが分散ロックです。

この例は単純なので、人間でも図を描けば気づけます。しかし、ノードが 3 台、メッセージの再送あり、障害からの復旧あり、となると、状態の数は手で追えない規模に急増します。そこを機械的に全部見るのが TLC の役目です。

TLC で検証できる性質:安全性と活性

TLC が検査する性質は、大きく 安全性 と 活性 の 2 種類に分かれます。

安全性(Safety):悪いことが絶対に起きない

活性(Liveness):良いことがいつか必ず起きる

活性を検査するときは、公平性の仮定が必要になります。何も仮定しなければ、「システムがずっと何もしない(足踏みし続ける)」実行も許されてしまい、「いつか終わる」は成り立ちません。上の例の WF_vars(Next) は弱公平性の仮定です。「実行可能なステップがずっと実行可能なままなら、いつかは実行される」という意味です。

安全性の違反は「ここで壊れた」という有限の手順で示せます。一方、活性の違反は「この先ずっと良いことが起きない」ことを示す必要があるため、TLC は同じ状態に戻ってくるループを含むトレースを反例として返します。

AWS・Azure での TLA+ 活用事例

2015 年、AWS のエンジニアが論文「How Amazon Web Services Uses Formal Methods」を Communications of the ACM に発表しました。S3 や DynamoDB などのシステムの設計に TLA+ を使った経験が報告されています。DynamoDB の設計では、TLC が見つけたバグを示す最短の反例トレースが 35 ステップに及びました。

このような、長い手順の果てに特定の順番が揃ったときだけ起きる競合状態(race condition)を、コードを書く前の設計段階で見つけられるのが TLC の強みです。

同様に Microsoft も、Azure Cosmos DB が提供する 5 つの一貫性レベルの仕様を TLA+ で書き、Azure/azure-cosmos-tla として公開しています。

TLC のメリットと限界

項目内容
強み人間の直感では見落としがちな、長い手順の果てに起きるまれな競合状態を、実装前の設計段階で検出できる。違反は具体的な手順として返るので、原因を追える
限界(状態爆発)サーバー台数、バッファサイズ、メッセージ数などのパラメータが大きくなると、状態の数が組み合わせ的に増える(状態爆発)。検査ではモデルを有限かつ小さく抽象化する必要がある
限界(モデルと実装の差)TLC が検査するのは仕様(モデル)であって、実装のコードではない。仕様が正しくても、実装が仕様どおりとは限らない

状態爆発への対策には、次のようなものがあります。

「違反なし」の結果を疑う

TLC が違反を報告しなかったとき、それは指定した有限のモデルの範囲では違反がない、という意味です。さらに、モデルの書き方を間違えて、そもそも肝心の状態に到達していない可能性もあります。たとえば上の例で Buy のガード条件を誤って書き、誰も買えないモデルになっていれば、在庫は決してマイナスにならず、検査は「成功」します。

これを防ぐには、破られるべき性質をあえて置き、TLC が違反を報告することを確かめます(例:stock = InitStock を不変条件にして、在庫が実際に減ることを確認する)。検査が空振りしていないかの確認は、末尾で紹介する関連記事でも扱っています。

TLAPS との使い分け

TLC は、有限のモデルを総当たりするモデル検査器です。パラメータを有限に絞った範囲でしか保証できません。

任意の台数、任意の長さの実行について性質が成り立つことを示したい場合は、TLC ではなく、対話的な定理証明系である TLAPS(TLA+ Proof System) を使います。TLAPS では人間が証明の構造を書き、各ステップをバックエンドの自動証明器に検査させます。手間はモデル検査よりはるかに大きいため、まず TLC で設計の穴を潰し、特に重要な性質だけを TLAPS で証明する、という順番が現実的です。

まとめ

TLA+ と TLC を Claude Code と組み合わせて、実際にキャッシュ設計の競合を見つけた例は、形式手法を Claude Code で回す — Z3 と TLA+ で仕様の穴を見つけ、反例をテストに落とす で紹介しています。



前の記事
NVIDIA RE-USE — 9.6M パラメータの音声強調モデルを文字起こしの前処理に挟む
次の記事
弥生の Misoca API v3 を読む — OAuth2 で請求書・見積書・納品書を操作する