Leanの定理が実装を縛っているかを、壊した実装を走らせて確かめるleanassayを作った
証明が通っていても、わざと壊した実装が同じ定理を満たしてしまうなら、その定理は実装について何も保証していないことになります。AIが証明を書いてくれるようになってきた今、気にするべきなのは証明が通るかどうかより、定理が実装をどこまで縛れているかのほうだと思っています。実際、JuliaをLeanに写したプロジェクトでは、「証明済み」の範囲チェック130件のうち128件が、添字が範囲内だと仮定していただけでした。
Leanは定理も実装も実行できるので、定理に出てくる関数をわざと壊して、壊したバージョンでも定理が成り立ってしまうかを実際に走らせて確かめる道具を作りました。試しに自分で証明を書いたlsp-touchstoneの定理に当ててみたところ、仕様に反する状態機械やUTF-16の幅を間違えた変換でも、すべての定理が成り立ってしまうことが分かりました。Leanで書いた関数をRustに変換して使っている自作のツール6つにも当ててみると、2つのツールで合わせて56の穴が見つかったので、定理を足してすべて塞いであります。
作った道具はleanassayで、リポジトリはconao3/lean-leanassay、ライセンスはApache-2.0です。この記事の結果は、Lean 4.35.0とleanassay 0.2.0で動かしたものです。
証明が通る壊れた実装
lsp-touchstoneはLSPの通信が仕様どおりかを判定する道具で、進捗の通知の状態の移り方をLeanで書いて、6つの定理を証明しています。
def step : TokenState → ProgressKind → Option TokenState
| .created, .begin => some .begun
| .begun, .report => some .begun
| .begun, .finish => some .ended
| _, _ => none
LSPの進捗は begin 、何回かの report 、 end の順に1回だけ進むのですが、ここに begun の状態で begin を受けて begun に留まる腕を1行足してみます。
| .begun, .begin => some .begun
この腕を足しても、6つの定理は元の証明のまま通ってしまいます。2回目の begin を禁じる定理を1つも書いていなかったからで、lsp-touchstoneはこの step で違反を判定しているので、この腕が入ると2回目の begin を見逃すことになります。
定理はどれも正しいし証明も通っているので、問題は書いていない定理のほうにあります。そして書いていない定理は、証明をいくら読み返しても見つかりません。
leanassayがすること
leanassayは、定理に出てくる関数を壊したバージョンを作って、そのバージョンで定理を実行します。証明は使わずに定理の前提と結論を具体的な入力で計算するので、定理が成り立たない入力が見つかればその壊し方は定理が弾いたことになり、どの入力でも成り立ってしまえば定理に穴があることになります。
壊し方は2種類あります。
- 関数全体を、明らかに間違った関数に置き換えます。いつも
defaultやnoneを返す関数、引数をそのまま返す関数、リストの引数の先頭1つだけを返す関数などです。 - 関数の本体を少しだけ変えます。比較や算術の演算子を替える、数のリテラルを1だけずらす、
takeとdropを入れ替える、パターンマッチの腕の結果を別の腕の結果に替える、どの腕にも書かれていない構築子の組み合わせに腕を足す、ifの分岐を入れ替える、といった変え方です。
壊したバージョンが試したすべての入力で元の関数と同じ値を返すなら、それは壊れていないとみなして報告から外し、出力が変わったのに定理を通ってしまったバージョンだけを穴として報告します。
入力はplausibleの生成器で作っていて、seedを固定しているので何回実行しても同じ結果になります。引数の型の値が少なければすべての組み合わせを試しますし、前提が成り立つ入力がまれな定理では、十分な数になるまで試す入力を増やします。
使い方
lakefile.tomlにleanassayを足して、監査したい関数を #assay に渡すだけです。
import Assay
import LspTouchstone.Progress
#assay proved.step
leanassayは、渡した関数が出てくる定理と、それを呼ぶ関数が出てくる定理を集めてきます。定理の結論が ∧ でつながっていれば項ごとに列を分けて、壊したバージョンごとにどの定理が弾いたかを表にします。
図は、出力の表から4行を抜き出して、壊し方の名前を短くしたものです。
✗ はその定理が成り立たない入力が見つかったこと、 · は試した入力で成り立ったこと、 ? は壊したバージョンでは定理の前提を満たす入力がほとんど見つからず、確かめられなかったことを表しています。19の壊し方のうち17は少なくとも1つの定理が弾いていて、 begun で begin を受ける腕を足した2つが穴として残りました。穴には元の関数と出力が違う入力を添えて警告を出すので、この穴なら begun の状態と begin の組で出力が違うと出ます。
set_option assay.failOnHole true を付けると穴をエラーとして報告するので、このファイルをビルドの対象に入れておけば、穴が残っている間は lake build が失敗するようになります。
lsp-touchstoneに当てた結果
lsp-touchstoneで証明している3つの部分に当ててみました。
| 部分 | 壊し方 | 弾いた | 穴 |
|---|---|---|---|
| 進捗の状態の移り方 | 19 | 17 | 2 |
| 位置の単位の変換 | 72 | 43 | 15 |
| 文書の範囲の置き換え | 12 | 12 | 0 |
位置の単位の変換で弾けなかった残りの14は、型が合わずに作れなかったものが12、試した入力で元と同じ値を返したものが1、前提を満たす入力が足りずに確かめられなかったものが1です。
位置の単位の変換では、1文字をUTF-8、UTF-16、UTF-32で何単位と数えるかを unitWidth で決めていて、たとえば 😀 はUTF-8では4、UTF-16では2、UTF-32では1と数えます。ところがこの幅を1以上のまま変えても、4つの定理はすべて成り立ってしまいました。定理が縛っていたのは幅が1以上であることだけで、UTF-16で2と数える文字がどれかは決めていなかったからです。実際leanassayは、UTF-16で2と数える境界の比較を < から ≤ に替えたバージョンや、UTF-16の幅をいつも1にしたバージョンを穴として報告してきました。
もう1つの穴は、位置が文字の途中を指すときの扱いでした。定理は「文字の途中を指すと判定したなら、その位置は本当に文字の途中である」とだけ述べていて、「文字の途中を指す位置はかならず文字の途中と判定される」という逆向きの定理がありませんでした。そのせいで、2文字目より後ろの文字の途中を指す位置を、文字の境界や行末と判定するバージョンもすべての定理を通っていました。
この結果をもとに、lsp-touchstoneに次の3つの定理を足しました。
begunの状態で受けられるのはreportとendだけ- 文字の途中を指す位置は、かならず文字の途中と判定される
- 1文字の幅は、UTF-8ではLeanの
Char.utf8Sizeと等しく、UTF-16ではUTF-8で4バイトの文字だけが2になり、UTF-32では1になる
定理を足したあとは、進捗の19、位置の72の壊し方のどれも穴として残っていません。定理を足したcommitと、足す前と後の監査の結果はリポジトリに置いてあります。
自作のツールに当てた結果
lsp-touchstoneのほかにも、Leanで書いた関数をleanfranでRustに変換して使っている自作のツールが6つあるので、Rustから呼んでいる関数すべてに #assay を当てて、 make check で監査するようにしました。
| ツール | 関数 | 壊し方 | 弾いた | 穴 |
|---|---|---|---|---|
| leanwisp (Leanのフォーマッタ) | 24 | 155 | 140 | 0 |
| leansail (Leanの言語サーバー) | 7 | 420 | 385 | 0 |
| leankeel (Leanのlinter) | 7 | 40 | 40 | 0 |
| leanwake (Leanの遅くなった宣言の検出) | 3 | 10 | 10 | 0 |
| ritsuryo (法令の期間と税額の計算) | 5 | 14 | 10 | 0 |
| ritsulint (法令のlinter) | 16 | 200 | 134 | 0 |
| 合計 | 62 | 839 | 719 | 0 |
弾いていない分は、型が合わずに作れなかったバージョンと、試した入力で元と同じ値を返したバージョンです。
当てる前は、leanwispに17、leansailに39の穴があって、定理が1つも触れていない関数もritsuryoに6つ、leanwispに4つ、leankeelに1つありました。
穴の多くは、上限だけや一方向だけを述べた定理のところに出ていました。たとえばleanwispの softblockIndent は字下げの幅を min indent.toNat (base + 2) で決める関数なのですが、定理は結果がどちらの値も超えないことしか述べていなかったので、いつも0を返すバージョンや + を - に替えたバージョンも通ってしまいました。結果がどちらかの値に等しいという定理を足したら、この穴はなくなりました。
leansailでは、言語サーバーの状態の移り方 transition に39の穴がありました。元の定理は「 running に移ったなら前の状態はこのどれかである」という含意の形で、前提を満たす入力が63のうち3つしかなく、壊したバージョンの多くを確かめられていませんでした。そこで ↔ の形に書き直して、移った先の状態ごとにも ↔ の定理を足したところ、39の穴はすべてなくなりました。
どの穴も定理の書き漏らしで、関数の定義のほうを直すことはありませんでした。今はどのツールも make check で穴がないことを確かめているので、たとえばleansailで足した initializing_iff_initialize を消すと、29の穴が出てビルドが失敗します。
証明が壊れるかで判定する道具との違い
Leanにも、関数を壊して定理の強さを測る道具はすでにあります。Mutate.leanは関数の本体を変えて、ファイルの証明が通らなくなるかで判定するもので、Microsoft CCFはこれを使ってLeanのモデルの穴を探しました。
ただ、証明が壊れるかで判定すると、結果が証明の書き方に左右されてしまいます。文字の途中を指す位置を文字の境界と判定するバージョンを手で作ると、場合分けした先で simp がゴールを閉じてしまって続く手が余るので、 resolve_splits の証明は通らなくなります。この基準だとこのバージョンは弾かれた扱いになって、逆向きの定理が欠けていることには気付けません。leanassayは定理の命題そのものを実行するのでこのバージョンが定理を満たすことを見つけられますし、証明をまだ書いていない sorry の定理にも使えます。
進捗の状態の移り方でも、Mutate.leanが作る型の合う壊し方は2つで、穴は見つかりませんでした。leanassayが見つけた穴は腕を足す壊し方によるもので、Mutate.leanはこの壊し方を作らないからです。
確かめられないこと
leanassayは、実行できる定理しか確かめられません。前提と結論が判定できる命題で、引数の型にplausibleの生成器がある必要があり、実数や無限の集合についての定理は実行できない定理として報告します。
また、試すのは入力の標本なので、穴が見つからなくても、試した入力では見つからなかったと言えるだけです。壊れていないとみなして報告から外すバージョンも、試した入力で元の関数と同じ値を返したというだけのことです。