hata retweeted
有名な形式検証、仕様記述言語の例を挙げると
■ Quintの仲間(システムのモデルを書いて検査する)
◆ TLA+
・Quintの元になった言語。Leslie Lamportが考案
・モデル検査器TLCやApalache、証明支援のTLAPSがある
・AWSがDynamoDBやS3の設計検証に使った事例が有名
◆ Alloy
・集合と関係でデータ構造や制約を記述し、SATソルバーで反例を探す
・「小さな範囲で全部試せば、たいていのバグは見つかる」という発想
・Alloy 6から時相論理も扱える
◆ P言語
・Microsoft発の、非同期にメッセージをやりとりする状態機械を書く言語
・AWSでも分散システムの設計検証に使われている
◆ Promela/SPIN
・並行プロセスとプロトコル検証の古典的なモデル検査器
◆ UPPAAL
・時間制約つきオートマトンを扱う。組込みやリアルタイム系向け
◆ Event-B/Bメソッド
・抽象的な仕様から段階的に詳細化し、各段階の正しさを証明していく手法
・パリ地下鉄14号線の制御ソフトでの適用が有名
◆ VDM(VDM-SL、VDM++)
・モデル指向の仕様記述言語
・日本ではFeliCaのICチップ開発での適用事例がよく知られている
◆ Z記法
・集合論にもとづく仕様記述の古典。証明より文書としての厳密さ寄り
■ LemmaScriptの仲間(実コードに契約を書いて証明する)
◆ Dafny
・検証機能つきのプログラミング言語。LemmaScriptの変換先の1つ
・事前・事後条件を書くと、SMTソルバー(Z3)で自動証明する
◆ SPARK
・Adaのサブセット。航空・鉄道・防衛など高信頼分野で実績が長い
◆ Frama-C(ACSL)
・C言語に注釈で契約を書いて検証する
◆ KeY(JML)
・Javaに契約を書くJMLを使って検証する
◆ Verus、Prusti、Kani
・Rust向け。Verus、Prustiは契約の証明、Kaniは有界モデル検査(AWS発)
◆ CBMC
・C/C++の有界モデル検査器
◆ Liquid Haskell、F*
・型に論理式を埋め込む篩型(refinement type)で性質を保証する
・F*は暗号ライブラリHACL*の検証で有名
■ 証明支援系(数学的に厳密な証明を人が組み立てる)
◆ Coq(Rocq)
・検証済みCコンパイラCompCertが代表例
◆ Isabelle/HOL
・OSカーネルseL4の完全な正しさの証明が有名
◆ Lean 4
・LemmaScriptのもう1つの変換先。数学の形式化(mathlib)でも広く使われる
・AWSの認可言語Cedarの検証でも使われている
◆ HOL4、ACL2、Agda
・HOL4は検証済みML処理系CakeML、ACL2はIntelなどのハードウェア検証で知られる
■ ざっくりした対応
・設計を確かめたい:TLA+、Quint、Alloy、P、Event-B
・コードを証明したい:Dafny、SPARK、Frama-C、Verus、LemmaScript
・とことん厳密にやりたい:Coq、Isabelle、Lean
■ Quintの仲間(システムのモデルを書いて検査する)
◆ TLA+
・Quintの元になった言語。Leslie Lamportが考案
・モデル検査器TLCやApalache、証明支援のTLAPSがある
・AWSがDynamoDBやS3の設計検証に使った事例が有名
◆ Alloy
・集合と関係でデータ構造や制約を記述し、SATソルバーで反例を探す
・「小さな範囲で全部試せば、たいていのバグは見つかる」という発想
・Alloy 6から時相論理も扱える
◆ P言語
・Microsoft発の、非同期にメッセージをやりとりする状態機械を書く言語
・AWSでも分散システムの設計検証に使われている
◆ Promela/SPIN
・並行プロセスとプロトコル検証の古典的なモデル検査器
◆ UPPAAL
・時間制約つきオートマトンを扱う。組込みやリアルタイム系向け
◆ Event-B/Bメソッド
・抽象的な仕様から段階的に詳細化し、各段階の正しさを証明していく手法
・パリ地下鉄14号線の制御ソフトでの適用が有名
◆ VDM(VDM-SL、VDM++)
・モデル指向の仕様記述言語
・日本ではFeliCaのICチップ開発での適用事例がよく知られている
◆ Z記法
・集合論にもとづく仕様記述の古典。証明より文書としての厳密さ寄り
■ LemmaScriptの仲間(実コードに契約を書いて証明する)
◆ Dafny
・検証機能つきのプログラミング言語。LemmaScriptの変換先の1つ
・事前・事後条件を書くと、SMTソルバー(Z3)で自動証明する
◆ SPARK
・Adaのサブセット。航空・鉄道・防衛など高信頼分野で実績が長い
◆ Frama-C(ACSL)
・C言語に注釈で契約を書いて検証する
◆ KeY(JML)
・Javaに契約を書くJMLを使って検証する
◆ Verus、Prusti、Kani
・Rust向け。Verus、Prustiは契約の証明、Kaniは有界モデル検査(AWS発)
◆ CBMC
・C/C++の有界モデル検査器
◆ Liquid Haskell、F*
・型に論理式を埋め込む篩型(refinement type)で性質を保証する
・F*は暗号ライブラリHACL*の検証で有名
■ 証明支援系(数学的に厳密な証明を人が組み立てる)
◆ Coq(Rocq)
・検証済みCコンパイラCompCertが代表例
◆ Isabelle/HOL
・OSカーネルseL4の完全な正しさの証明が有名
◆ Lean 4
・LemmaScriptのもう1つの変換先。数学の形式化(mathlib)でも広く使われる
・AWSの認可言語Cedarの検証でも使われている
◆ HOL4、ACL2、Agda
・HOL4は検証済みML処理系CakeML、ACL2はIntelなどのハードウェア検証で知られる
■ ざっくりした対応
・設計を確かめたい:TLA+、Quint、Alloy、P、Event-B
・コードを証明したい:Dafny、SPARK、Frama-C、Verus、LemmaScript
・とことん厳密にやりたい:Coq、Isabelle、Lean
★LemmaScriptとQuintの役割の違いと使い分け★
ひとことで言うと
・LemmaScript:1つの関数が正しく計算するかを証明する
・Quint:システム全体が正しく振る舞うかを確かめる
・境目は「1回の呼び出し」か「システムの全実行」か
■ 対象
◆ LemmaScript
・実際のTypeScriptコードそのもの
・I/Oのない、小さな純粋関数が中心
◆ Quint
・コードとは別に書く、抽象的なシステムのモデル
・複数の主体、順序、並行、障害を含む状態遷移が中心
■ 土台の論理
◆ LemmaScript
・ホーア論理(契約による設計の系統)
・時間の流れは扱わず、入口と出口の関係だけを見る
◆ Quint
・TLA(時相論理)
・状態がどう移り変わっていくか、その列全体を扱う
■ 書くもの
◆ LemmaScript
・関数ごとの事前条件・事後条件
・関数内部のループ不変条件
・.tsファイルの中に//@コメントとして書く
◆ Quint
・モデル:状態変数と、それを変えるアクション(実装の手本)
・性質:全状態で成り立つ不変条件(安全性)と、いつか必ず起きること(活性)
・.qntという別ファイルに書く。特定の関数に属さないので、コードの横には置けない
■ 確かめ方と保証の強さ
◆ LemmaScript
・DafnyやLean 4に変換して定理として証明する
・成功すれば、すべての入力について成り立つ
◆ Quint
・シミュレーション(quint run):ランダムに試す。反例探し向き
・モデル検査(quint verify):一定のステップ数までの全実行を網羅する
・保証されるのはモデルについてであって、コードについてではない
■ 見つけるバグ
◆ LemmaScript
・関数内部の計算や分岐の誤り
・例:境界値の「<」と「<=」の取り違え
◆ Quint
・設計そのものの誤り
・例:チェックの書き忘れ、処理順序による矛盾、デッドロック、処理が永遠に終わらない
■ コードとの関係
・LemmaScript:コードを直接証明するので、仕様と実装の隙間がない(ただし対応するTypeScriptはサブセット)
・Quint:モデルとコードの間に隙間がある。そこをquint-connectで、実装がモデルどおりかテストして埋める
■ 向く場所
・LemmaScript:お金や在庫の計算、認可判定、入力検証、不変条件の明確なアルゴリズム
・Quint:承認フロー、決済、予約、リトライやタイムアウトを含む処理、状態が散らばった機能
■ 組み合わせ
・競合しないので同じプロジェクトで併用できる
・システム全体をQuintで固め、その中の重要な関数をLemmaScriptで証明し、両者の間をquint-connectでつなぐ
・残りの関数はプロパティテストで補う
1
13
90
4,980
AI に Thank you を言おうぜとは DDH はじめたくさんの人がその意味を解説してくれてるけど、僕くらいになると仕事始める前に Ice Break や Small Talk をはさんでた。でもこれは意味なかった。似てるけど、 Thanks は片方向で成り立つのに Small Talk は双方向コミュニケーションだから。「今日は DC の調子が悪くて電圧が安定しなくて最悪だよ」とかは AI にはない。話して価値があるのはこっちの調子がどうか、というのだけ。
タスクに取り掛かる前に今はまだ寝起きだとか今日は何時に上りたいとかそういうのをさっと伝えて、一区切りつくときに感謝を伝える。それが一番効率良い気がしてる。
タスクに取り掛かる前に今はまだ寝起きだとか今日は何時に上りたいとかそういうのをさっと伝えて、一区切りつくときに感謝を伝える。それが一番効率良い気がしてる。
0
0
0
59





