なぜ人々は形式手法を使わないのか?
Why Don't People Use Formal Methods? (hillelwayne.com)
要約
形式手法が広く普及しない理由として、歴史的な背景、用語の混乱、仕様定義の難しさ、コストなどが挙げられます。特に、人間が理解する概念を数学的に厳密な仕様に落とし込むことや、コードの正しさを証明するだけでなく、顧客の要求を満たしているか(検証)をどう確認するかが大きな課題です。これらの課題に対処するため、より実践的なアプローチが模索されています。
全文翻訳
なぜ人々は形式手法を使わないのか?
私はソフトウェアエンジニアリングのStack Exchangeで「形式手法の広範な採用を妨げている障壁は何ですか?」という質問を見かけました。この質問は意見ベースとして閉じられ、回答のほとんどは「高すぎる!!!」とか「ウェブサイトは飛行機ではない!!!」といったものでした。これらはある程度正しいですが、あまり多くを説明していません。この記事では、形式手法のより大きな歴史的背景、それらが実際にそれほど使われていない理由、そしてそれらが使われるようにするために私たちが何をしているのかを説明します。
始める前に、いくつかの用語を定義する必要があります。FMには、実際にはコミュニティと呼べるほどのものはなく、むしろ草原をさまよう小さな集団がいくつかいるだけです[1]。そのため、異なるグループが用語を異なる方法で使用しています。非常に大まかに言うと、FMには2つの領域があります:形式仕様は、正確で曖昧さのない仕様をどのように書くかという研究であり、形式検証は、物事が正しいことをどのように証明するかという研究です。しかし、「物事」にはコードと抽象的なシステムの双方が含まれます。両方を指定するための別々の手段を使用するだけでなく、それらを検証するためにも異なる手段をしばしば使用します。さらに混乱を招くことに、誰かが形式仕様を行っていると言った場合、彼らは通常、システムの両方を指定し検証することを意味し、誰かが形式検証を行っていると言った場合、彼らは通常、コードの両方を指定し検証することを意味します。
明確化のために、検証をコード検証(CV)と設計検証(DV)に分け、同様に仕様をCSとDSに分けます。これらは、より広いFMの世界で使われている用語ではありません。まずCSとCVについて話してから、DSとDVに進みます。
さらに、部分検証(仕様の一部のみを検証する)または完全検証(仕様全体を検証する)を行うことができます。これは、「クラッシュしない、または間違ったパスワードを受け入れない」と「クラッシュしない、または間違ったパスワードを受け入れない、そして3回間違ったパスワードを入力するとアカウントがロックされる」という証明の違いになり得ます。この歴史のほとんどは、完全検証を行っていると仮定します。
また、形式化するソフトウェアの種類を明確にする必要があります。ほとんどの人は、医療機器や航空機などの高信頼性ソフトウェアと、それ以外のすべてに暗黙的にソフトウェアを分割しています。人々は、前者では形式手法が広く使われており、後者には不要だと仮定しています。これは、もしあれば、楽観的すぎるかもしれません:高信頼性ソフトウェアのほとんどの人は形式手法を使用していません。代わりに「通常の」ソフトウェアに焦点を当てます。
最後に、免責事項:私は歴史家ではなく、デューデリジェンスを試みましたが、誤りがある可能性があります。また、私は形式仕様(DSとDV)を専門としているため、コード検証について私が言うことには誤りが含まれる可能性が高いです。もし間違いを見つけたら、私にメールしてください。修正します[2]。
コードの形式化
仕様の取得
コードが正しいことを証明する前に、「正しい」とは何かを知る必要があります。これは、コードが何をするべきかの仕様、またはスペック、つまり特定の出力がスペックに従っているかどうかを曖昧さなく言える形式のものを意味します。「リストがソートされている」と言うだけでは不明確です。何をソートしているのか、どの基準を使用しているのか、あるいは「ソート」の意味さえもわかりません。代わりに、「整数のリスト l は、任意の2つのインデックス i と j に対して、i < j ならば l[i] <= l[j] である場合、昇順にソートされている」と言うかもしれません。
コードのスペックは3つの主要なキャンプに分かれます:
- 最初のキャンプは、コードとは独立したステートメントとしてそれらを記述することです。ソート関数を記述し、別のファイルに「これはソートされたリストを返す」という定理を記述します。これはスペックの最も古い形式であり、現在でもIsabelleやACL2が行っている方法です[3]。
- 2番目のキャンプは、プリ/ポスト条件、アサーション、不変条件の形式でスペックをコードに埋め込みます。関数に「戻り値はソートされたリストである」というポスト条件を追加するかもしれません。アサーションベースのスペックは、元々ホア論理として形式化され、1970年代初頭にEuclidで初めてプログラミング言語に統合されました[4]。このスタイルは契約による設計(Design by Contract)とも呼ばれ、産業界で最も一般的な検証形式です[5]。
- 最後に、型システムがあります。カリー・ハワード対応により、任意の数学的定理や証明は依存型としてエンコードできます。「ソートされたリスト」の型を定義し、関数の型シグネチャを
[Int] -> Sorted [Int]と宣言します。
これらのすべてがどのように見えるかの例は、Let’s Prove Leftpadで見ることができます。HOL4とIsabelleは「独立した定理」スペックの良い例であり、SPARKとDafnyは「埋め込みアサーション」スペックを持ち、CoqとAgdaは「依存型」スペックを持っています[6]。
少し目を細めて見ると、これら3つのコードスペック形式が、自動的な正しさチェックの3つの主要な領域、つまりテスト、契約、型に対応していることがわかります。これは偶然ではありません。正しさはスペクトルであり、形式検証はそのスペクトルの1つの極端です。検証の厳密さ(と労力)を減らすにつれて、状態空間の探索を制限したり、弱い型を使用したり、検証を実行時にプッシュしたりするなど、より単純で狭いチェックが得られます。全仕様のあらゆる手段は、部分仕様の手段となり、その逆もまた然りです。多くの人がクリーンルームを形式検証技術と見なしており、これは主にコードレビューを人間ができることをはるかに超えるレベルまでプッシュすることによって機能します。
「正しいスペックとは?」
検証は、コードがそのスペックに一致することを証明します。これは、「正しいスペックをどのようにして得るのか?」という疑問を投げかけます。正しいスペックを見つけることは、形式手法における最大の課題の1つです。これも最もよく提起される異議の1つですが、懐疑論者がそれを意味する方法は、提唱者がそれを考える方法と正確には同じではありません。
部外者が「正しいスペックをどうやって得るのか?」と言うとき、彼らは通常検証(validation)を考えています。つまり、スペックが実際にクライアントの要求を満たしていることを示すことです。コードがリストをソートすることを形式的に証明しても、顧客が実際に求めているのがUber For Soups ™だった場合、あなたは単に多くの時間を無駄にしただけです。迅速なイテレーションと短いフィードバックサイクルによってのみ、要件を実際に検証できると人々は主張します。
コードを検証しても、コードが検証されるわけではないというのは事実です。しかし、この議論には2つの問題があります。1つ目は、FMの価値を完全に排除するのではなく、単に遅らせるだけだということです。迅速なイテレーションを行った後、顧客が何を求めているかのアイデアが得られたと仮定します。それからコードの検証を開始します。2つ目は、顧客が正確に何を求めているかはわかりませんが、彼らが求めていないと仮定できることがいくつかあります。彼らはソフトウェアがランダムにクラッシュすることを望んでいません。彼らはセキュリティホールを望んでいません。誰もがこの重要性を認識しています。結局のところ、イテレーション中に単体テストをスキップすべきだと言う人はいません。したがって、少なくとも、バージョン管理システムがユーザーの本の章をランダムに削除しないことを証明してください[7]。
正しいスペックを見つける問題は、より根本的です。私たちは、スペックが何であるべきかをしばしば知りません。私たちは、人間の言葉で要件を考え、数学的な言葉では考えません。「これは公園と鳥を区別すべきだ」と言った場合、私は何を言っているのでしょうか?公園と鳥の写真の束を与えることで、人間に説明できますが、それは単なる具体的な例であり、公園と鳥を区別するというアイデアを捉えていません。それを形式的なスペックに実際に翻訳するには、人間の概念を形式化できる必要があります。そして、それは深刻な課題です。
誤解しないでください。適切なスペックを見つけることは可能であり、専門家は常にそれを行っています。しかし、適切なスペックを書くことは、コーディングスキルを開発する必要があったのと同じように、開発する必要のあるスキルです。だからこそ、コード検証における最近の成功の多くは、私たちが望むことと、私たちが望むことを表現できることとの間に明確なマッピングがあるものです。例えば、CompCertは形式的に検証されたCコンパイラです。そこでのスペックは「これは決して誤ってコンパイルしない」ということです。
そして、これらはすべて検証部分ではありません。スペックを持ったら、コードがスペックに一致することを証明する必要があります。
スペックの証明
私たちが目にする最も初期のコード検証手段は、ディクストラ風の「それが真実である理由を深く考える」という方法であり、これは基本的にALGOLが支援するために設計されたものです。例えば、挿入ソートが機能することを「証明」するには、次のように主張するかもしれません。
- 基底ケース:空のリストがあり、それに1つの要素を追加した場合、それは唯一の要素になるため、ソートされます。
k個の要素を持つソートされたリストがあり、それに1つの要素を追加した場合、その要素を小さい数の後、大きい数の前に挿入するように挿入します。これはリストがソートされたままであることを意味します。- 帰納法により、挿入ソートはリスト全体をソートします。
明らかに、それはそれよりも厳密に見えるでしょうが、それが一般的な考え方です。ディクストラらはこのスタイルを使用して、多くの並行プリミティブを含む多くのアルゴリズムの正しさを証明しました。これはまた、Knuthの引用「上記のコードのバグに注意してください。私はそれを正しく証明しただけで、試してはいません」につながるスタイルでもあります。数学の証明を誰も気づかない方法で台無しにするのは非常に簡単であり、私は推定によると、公開された数学の証明の約20%に誤りがあるとのことです。Peter Guttmannは、証明されたコードがすぐにクラッシュするという証明コードがいかに滑稽になったかについての素晴らしいエッセイを書いています。
数学的定理を自動的に証明する方法を探求していたのと同時に、最初のそのような定理証明器が1967年に出現しました。Pascalコミュニティの研究者は、1970年代初頭にプログラムを検証するために定理証明器を使用し、1970年代半ばには専用の検証言語でプログラミングしていました。人々はコードのいくつかのプロパティを記述し、コードがそれらのプロパティを持っていることをチェック可能な証明を記述しました。初期の定理証明器は、人間が証明をチェックおよび検証するのを支援するだけでしたが、より洗練されたものは定理の一部を自分で証明できました。
これが次の問題につながります。
証明は難しい
証明は難しいです。非常に難しいです。「プログラミングをやめてサーカスに参加する」ほど難しいです。驚くべきことに、形式的なコード証明は、ほとんどの数学者が書く証明よりも厳密であることがよくあります!数学は非常に創造的な活動であり、最終的な答えは、作業を示した場合にのみ有効です。創造性、形式主義、そしてコンピューターは悪い組み合わせです。
上記の帰納法を見てください。どんな数学者でもそれを見て、帰納法が何であるか、それがどのように機能するか、そしてそれがこの場合にどのように有効であるかをすぐに知ることができます。これらはすべて、定理証明器で厳密に形式化する必要があるものです。背理法による証明、対偶による証明なども同様です。これに加えて、ほとんどの数学者が証明するのを気にしないようなすべての仮定を形式化する必要があります。例えば、加算は結合的です:a + (b + c) = (a + b) + c。定理証明器は、それが真であることを事前に知りません。それを証明する(難しい)、証明器が真と見なすことができる仮定として宣言する(危険)、またはそれをすでに証明した誰かから定理ライブラリを購入する(高価)必要があります。初期の証明支援ツールは、組み込み証明戦術とバンドルされた定理ライブラリの数で競合していました。最初に広く普及した証明チェッカーの1つであるSPADEは、完全な算術ライブラリを主要なセールスポイントとして宣伝していました。
次に、証明を実際に取得する必要があります。証明器に自分で見つけさせることができます。または、自分で書くことができます。一般的なケースでは、自動的に証明を推論することは決定不能です。命題論理やHM型チェックのような非常に制限されたケースでは、「のみ」NP完全です。ほとんどの場合、証明の大部分を自分で書き、コンピューターにそれが正しいことを検証させることになります。つまり、次の分野で強力な背景知識が必要です。
- 数学
- CS
- ハードウェアやコンパイラなどの作業しているドメイン
- プログラムとスペックの複雑さ
- 使用している定理証明器の複雑さ。これはそれ自体が専門分野です。
さらに悪いことに、コンピューターのプロパティは証明に多くの障害をもたらします。加算が結合的であると仮定することが危険であると言ったことを覚えていますか?一部の言語は結合的ではありません。C++にはINT_MAXがあります。((-1) + INT_MAX) + 1はINT_MAXです。-1 + (INT_MAX + 1)は未定義です。C++で結合的な加算を仮定すると、証明は間違っており、コードは壊れます。そのアサーションを避けるか、特定のコードスニペットに対してオーバーフローが発生しないことを証明する必要があります。
ここで、未定義の加算はバグであり、整数が制限されない言語を使用すべきだと言うかもしれません。しかし、ほとんどの言語には、証明を妨げる肯定的な特徴があります。次のコードスニペットを見てください。
a = true;
b = false;
f(a);
assert a;
それは常に真ですか?場合によります。おそらくfはaを変更します。おそらく別のスレッドの並行処理がaを変更します。おそらくbはaにエイリアスされており、それを変更するとaも変更されます[8]。もしこれらのいずれかがあなたの言語で可能であれば、それらが発生しないことを明示的に証明する必要があります。純粋性は、このケースでは役立ちますが、他のケースでは証明を台無しにする可能性があります。なぜなら、それを行うには再帰と高階関数を使用する必要があるからです。どちらも、ちなみに、良い関数型プログラムを書くための基礎です。コーディングに良いことが、証明には悪いのです![9]
形式検証ツールにはジレンマがあります:言語が表現力豊かであればあるほど、その中で何かを証明するのが難しくなります。しかし、言語が表現力に乏しければ乏しいほど、その中で何かを書くのが難しくなります。最初のプロダクション検証言語は、より表現力豊かな言語の非常に制限されたサブセットでした:ACL2はLispのサブセット、EuclidはPascalのサブセットなどでした。そして、これまで議論してきたことは、実際のプログラムを証明することには全く触れていません。これらはすべて、証明を書き始めるための単なる最低限の条件です。
証明は難しいです。しかし、改善されつつあります。証明支援ツールの研究者は、新しいヒューリスティック、定理ライブラリ、事前検証済みコンポーネントなどを追加し続けています。ハードウェアの改善も役立ちます:より高速なコンピューターは、より高速な検索を意味します。
SMT革命
今日、証明自動化の最も一般的なアプローチはSMTです[10]。非常に大まかに言うと、SMTソルバーは(一部の)定理を制約充足問題に変換できます。これにより、創造的な問題が計算的な問題に変わります。定理のステップとして中間問題(補題)を供給する必要があるかもしれませんが、それはすべてを自分で証明するよりはましです。スタンフォード大学は、1998年に最初の「モダン」SMTソルバーであるStanford Validity Checkerをリリースしました。彼らはそれを基にCVCを開発し、2002年にリリースしましたが、これは小規模なプロダクション利用にとどまりました[11]。
2006年頃、Microsoft ResearchがZ3をリリースしたことで状況は一変しました。Z3の大きな利点は、他のSMTよりもユーザーフレンドリーであったことです。正直なところ、それは大したことではありませんでした。MSRはそれを内部でWindowsカーネルのプロパティを証明するために使用しており、UXへの投資は最低限以上でした。Z3は、おそらくSMTを汎用自動証明のデフォルトの選択肢にしました。CVの多くのツールは現在SMTに依存しており、そのほとんどがデフォルトでZ3を備えています。
アクセス可能なSMTソルバーは、多くの単純な証明を自明にし、厄介な証明を扱いやすくしたため、形式検証コミュニティに大きな刺激を与えました。これにより、表現力豊かなステートメントの課題に対処する力が得られたため、人々はより表現力豊かな言語で物事を証明できるようになりました。この分野の信じられないほどの進歩は、IronFleetプロジェクトに明らかです。高度なSMTソルバーと最先端の検証言語を使用することで、Microsoftはわずか3.7人年で5,000行の検証済みDafnyコードを記述できました!これは、1日あたり4行という驚異的な速度です[12]。
証明は難しいです。
なぜわざわざやるのか?
ここで一歩立ち止まって「何のために?」と尋ねるのが良い時期でしょう。私たちはあるプログラムがあるスペックに準拠することを証明しようとしています。正しさはスペクトルです。検証の質問には2つの部分があります:プログラムが客観的に「正しい」程度と、その正しさをどの程度厳密に検証したかです。明らかに、検証度が高いほど良いですが、検証には時間とお金がかかります。パフォーマンス、市場投入までの時間、コストなどの複数の制約を最適化する場合、最適解は必ずしも「完全に証明された正しさ」ではありません。そうなると、「必要な最小限の検証は何か」そして「そこに至るのにいくらかかるか」という問題になります。ほとんどの場合、90%、95%、または99%の正しさで済ませることができます。最後の1%の正しさを得るよりも、UXの改善に時間を費やす方が良いかもしれません。
では、「90/95/99%の正しさは100%の正しさよりも大幅に安価か?」という質問です。答えは「はい」です。私たちは皆、コードベースをよくテストし、よく型付けすれば、本番環境でのいくつかの修正を除いてほとんど正しいと言えます。そして、私たちは1日あたり4行以上のコードを書いています。実際、分散システム障害の大部分は、もう少し包括的なテストで防止できた可能性があります。そしてそれは、単体テストの包括性だけであり、ファジング、プロパティベーステスト、またはモデルテストについては言うまでもありません。完全な証明に進むことなく、より単純なトリックで非常に遠くまで到達できます。
型とテストだけでは十分な検証が得られない場合はどうでしょうか?90%から99%への移行は、99%から100%への移行よりもはるかに簡単です。前述のように、クリーンルームは、包括的なドキュメント、慎重なフロー分析、および広範なコードレビューを含む開発者プラクティスです。証明なし、形式検証なし、単体テストさえなし。しかし、適切に行われた場合、クリーンルームは本番環境での欠陥密度を1バグ/kLoC未満に削減します[13]。それを使用するチームは、それを使用しないチームよりも同等または短い納期で納品できます。そして、クリーンルーム自体は、主流のソフトウェアプラクティスとコード検証の間に位置する多くの高信頼性技術の1つにすぎません。良いソフトウェアを書くため、あるいはほぼ完璧なソフトウェアを書くためでさえ、完全なコード検証を必要としません。それが必要なケースはありますが、業界のほとんどにとっては時間の無駄です。
しかし、それは形式手法全体が経済的でないという意味ではありません。前述の高信頼性技術の多くは、形式的に証明しないコードスペックの記述に依存しています。検証に関しては、業界で人々が利益を得る一般的な方法は2つあります。1つ目はコードではなく設計の検証であり、これは次のセクションで扱います。2つ目は部分的なコード検証であり、これは現在扱います。
部分的なコード検証
日常的なプログラミングで完全な検証を行うのは高すぎます。部分的な検証はどうでしょうか?コードの一部に関するいくつかのプロパティを証明することからまだ利益を得ることができます。ソート関数が常にソートすることを証明する代わりに、少なくとも無限ループしないこと、および境界外書き込みをしないことを証明できます。これだけでも多くのメリットが得られます。例えば、Cプログラムに関する基本的な証明を書くだけでも、膨大な量の未定義の動作を排除するのに役立ちます。
ここでの制限は利用可能性です。ほとんどの言語は、完全検証または検証なしのいずれかのために設計されています。前者の場合、より表現力豊かな言語の多くの便利な機能を欠いており、後者の場合、その概念に敵対的な言語で証明を行う方法が必要です。このため、部分検証に関するほとんどの研究は、CやJavaのようないくつかの高優先度言語に焦点を当てています。また、言語の制限されたサブセットを扱う人も多く見られます。例えば、SPARKはAdaの制限されたサブセットなので、クリティカルなものをSPARKで記述し、それほどクリティカルでないAdaコードと相互運用させることができます。しかし、そのような言語のほとんどはかなりニッチです。
より一般的には、人々は特定の種類の検証を言語のコア構造に組み込んでいます。プロダクション型システムは一般的な形式です。tailが常にテールを返すことは知らないかもしれませんが、少なくとも[a] -> [a]の型を持つことは知っています。また、メモリ安全性を証明するRustや、例外安全性を証明するPonyのようなケースもあります。これらは、SPARKやFrama-Cとは少し異なり、部分検証のみが可能であり、一部は部分検証、一部は完全検証というわけではありません。また、形式手法の専門家ではなく、プログラミング言語の専門家によって作られる傾向があります。これら2つの分野は多くの重複がありますが、同一ではありません。これが、RustやHaskellのような言語が実際には実用的である理由かもしれません。
設計仕様
これまではコード検証についてのみ話してきました。しかし、形式手法にはもう1つの側面があります。それは、さらに抽象的なレベルに上がり、設計自体を検証することです。これは十分に深く、形式仕様と同義です。もし誰かが形式仕様を行っていると言った場合、彼らは通常、設計を指定し検証することを意味します。
話したように、コードのすべての行を証明するのは非常に、非常に難しいです。しかし、プロダクションシステムでの多くの問題は、コードの行にあるのではなく、システムのコンポーネント間の相互作用にあります。実装の詳細を「鳥を識別できると仮定する」と言ってごまかすと、公園や鳥のような高レベルモジュールが全体の設計にどのように適合するかをより簡単に調べることができます。しかし、十分にズームアウトすると、実行時環境、人間の相互作用、または容赦ない時間の流れのような、実装できないものを記述することが可能(または少なくともはるかに容易)になります[14]。このスケールでは、コード行に対する意図ではなく、システム全体の意図を形式化しています。これは人間のレベルに非常に近く、設計と要件はコードレベルよりも曖昧である可能性があります。
例を挙げましょう。コードの手続きの仕様は「呼び出された場合、データをストレージに永続化するためのシステムコールを行い、システムエラーを処理する」というものです。検証する必要のあるプロパティは、困難ではありますが、ある程度単純です。データを正しくシリアライズしますか?不正な入力は私たちの保証に違反しますか?システムコールが失敗する可能性のあるすべての方法を処理しますか?次に、「すべてのメッセージがログに記録される」という仕様を持つ高レベルのロギングシステムと比較してください。あなたは今、次のような質問に答える必要があります。
- すべてのメッセージ、またはシステムに到達するすべてのメッセージですか?メッセージは一度ログに記録されますか、それとも正確に一度ログに記録されますか?
- メッセージはどのように送信されていますか?キューですか?転送媒体は一度配信しますか?順序通りに配信しますか?
- 「ログに記録される」とは、「永続的にログに記録される」という意味ですか?メッセージはログに記録され、後でログから削除されることが許可されますか?ログに記録される前に、ログに記録されたりされなかったりするのを繰り返すことが許可されますか?
- メッセージをログに記録している途中でサーバーが爆発したらどうなりますか?ジャーナリングが必要ですか?
- ストレージ媒体のプロパティで重要なものはありますか?「媒体がデータを失う」ことは、私たちの要件の範囲外ですか、それともそうではありませんか?
- GDPRについてはどうですか?
- その他、その他、その他。
形式的な設計の利点なしでは、実際にシステムに何を必要とするかを表現するのが難しくなります。何を必要とするかを表現できない場合、設計が実際にあなたが必要とするもの、または非常に異なる結果をもたらす似たようなものを提供しているかどうかを知る方法がありません。意図と設計を形式的に表現することで、実際に構築する必要のあるものを構築していることを確認しやすくなります。
コードを表すためにプログラミング言語を使用するのと同じように、設計を表すために仕様言語を使用します。仕様言語は通常、コード仕様ではなく設計仕様向けですが、一部の言語は両方に使用できます[15]。今後、混乱を最小限に抑えるために、仕様言語を設計言語(DL)と呼ぶことにします[16]。
最初の完全なDLは、おそらく1972年頃に出現したVDMでした。それ以来、さまざまな仕様言語が数多く登場しています。設計言語の空間は、コード検証言語よりもはるかに多様で断片的です。非常に大まかなステレオタイプとして、人々はDLを手段として発明しましたが、人々はCVLをそれ自体として発明しました。特定の問題領域に強く影響されているため、DLにはさまざまなアイデアとセマンティクスがあります。非常に、非常に簡単な初期設計言語のツアーを以下に示します。
| 言語 | モデル化 | 使用 |
|---|---|---|
| Z | ビジネス要件 | 関係代数 |
| Promela | メッセージング | CSP |
| SDL | 電気通信 | フローチャート |
| Harel Statecharts | コントローラー | オートマタ |
| Decision Tables | 決定 | テーブル |
人々は主に特定の問題を解決するためにDLを設計したため、ほとんどのDLには少なくとも2つまたは3つの実世界のケーススタディがあります。結果は一般的に非常に肯定的です。実務家によると、問題への洞察が得られ、ソリューションの探索が容易になるとのことです。長らく最大の支持者はPraxis(現Altran)であり、Z設計とSPARKコードを組み合わせた「構築による正しさ」“correct-by-construction”を使用して安全クリティカルなシステムを構築していました。彼らは、プロジェクトの後期段階で設計ミスを発見しないため、仕様を書くことでより迅速かつ安価に作業できると主張していました。
最近では、Pamela ZaveがAlloyをいじっていて、主要な分散ハッシュテーブルの1つであるChordが根本的に壊れていることを発見しました。さらに最近では、AWSはTLA+仕様を記述することで35ステップの重大なバグを発見し始めています。私の経験では、仕様を書くことを試みた人々は熱狂的なファンになります。
しかし、ファンの価値と部外者の価値の間には大きなミスマッチもあります。ファンにとって、最大の利点は、設計を書くという行為が、書いているものを理解することを強制することです。システムが何をするかを形式的に表現する必要がある場合、多くの微妙なエラーが痛ましいほど明白になります。これは部外者には全く説得力がありません。人々がDLを使ってみるように説得するには、設計が実際に望ましいプロパティを持っていることを検証する方法を提供する必要があります。
幸いなことに、これは多くの仕様作成者にとっても非常に重要であるため、設計検証は研究の大きな分野です。
モデルチェッカー
コードと同様に、定理を記述して設計を検証できます。幸いなことに、もう1つのトリックがあります:モデルチェッカーを使用できます。設計が正しいという証明を書く代わりに、状態空間を総当たりで調べ、到達可能な状態が間違っているかどうかを確認します。もし間違った状態が見つからなければ、うまくいったということです[17]。
モデルチェックには多くの利点があります。1つ目は、証明を書く必要がないことです。これは多くの時間と労力を節約します。2つ目は、証明の書き方を学ぶ必要がないため、スキル障壁がはるかに低くなります。3つ目は、設計が壊れている場合、モデルチェッカーは明示的な反例を提供します。これは、特にバグの再現に35ステップかかる場合、問題の修正をはるかに、はるかに楽にします。自分でそれを見つけるのは運次第です。
欠点もいくつかあります。1つは、それらが少し強力ではないことです。具体的には、無限の数の異なる状態がある無限モデルを扱っている可能性があります。例えば、メッセージキュープロセッサの仕様を記述している場合、10個のメッセージのリストが与えられた場合にそれが機能することはかなり単純です。しかし、メッセージの任意のリストに対してそれが機能することを確認する必要がある場合、それらは無限にあり、状態も無限にあります。ほとんどのモデルチェッカーは、同値クラスや対称性を特定するなど、これらを処理するためのさまざまなトリックを持っていますが、それは本当にケースバイケースです。
もう1つの大きな欠点は状態空間の爆発です。3つのプロセスがあり、それぞれが4つの逐次ステップを持ち、それらのステップを任意の順序でインターリーブできると想像してください。それらが互いの動作に影響を与えない場合、可能な実行(動作)の総数は (4*3)! / (4!)^3 = 34,650 です。各プロセスが5つの初期状態のいずれかを持つ場合、合計で4,300,000の動作があります。そして、モデルチェッカーはそれらすべてがうまく動作することを確認する必要があります。そしてこれは、それらが互いに相互作用しないと仮定した場合です!もし相互作用する場合、状態空間はさらに速く大きくなります。組み合わせ爆発は、モデルチェックの主要な課題と見なされており、これをより扱いやすくするための多くの作業が行われています。
しかし、その間、状態爆発に対処するもう1つの方法があります:より多くのハードウェアを投入することです。モデルチェックの最大の課題は「単なる」パフォーマンスの問題であり、私たちはパフォーマンスの問題を解決するのが非常に得意です。ほとんどの(すべてではない)モデルチェックは容易に並列化できます。モデルを最適化し、小さなパラメータでチェックした後、AWSクラスターを起動して大きなパラメータで実行できます。
実際には、多くの仕様作成者はモデルチェッカーを使用し、必要に応じて定理証明器に切り替えます[18]。さらに多くの仕様作成者はモデルチェッカーを使用し、限界に達したときに、より負荷の低い検証形式に切り替えます。
設計仕様の問題
したがって、設計検証はコード検証よりも簡単で高速であり、多くの目覚ましい成功を収めています。では、なぜ人々はそれを使用しないのでしょうか?DVの問題は、はるかに巧妙です。コード検証は技術的な問題ですが、設計検証は社会的な問題です。人々はポイントを見ません。
これの多くは、設計はコードではないという結果です。ほとんどの設計言語では、コードを生成する自動的な方法はありませんし、既存のコードが設計と一致することを検証する方法もありません[19]。プログラマーは、コードではない、またはコードと強制的に同期されていないソフトウェア成果物を信頼しない傾向があります。これは、ドキュメント、コメント、図、ウィキ、コミットメッセージがしばしば無視されるのと同じ理由です。
プログラマーはまた、仕様を記述するメリットがあるとは信じていないようです。少なくとも私の経験では、彼らは現在使用しているもの(擬似コード、図、TDD)が設計を正しく行うには十分すぎると想定しています。これが普遍的であるかどうかはわかりませんし、一般的な保守主義以外に良い説明もありません。私の推論は、私が知っているすべての方法論コミュニティが全く同じ不満を抱いているということです。TDDの支持者は、人々がTDDを試したがらないと不平を言い、Haskellerは人々が静的型付けを気にしないと不平を言うなど、など、など[20]。人々がすでにやっていないことについて人々を興奮させるのは非常に難しいです。たとえメリットに同意していてもです。
要約
コードの検証は難しい問題です。定理証明器とSMTソルバーがより洗練されるにつれて、ますます多くの人々が行うようになっています。今後しばらくは専門家向けのニッチなものとして残るでしょう。
設計の検証ははるかに簡単ですが、採用には文化的な障壁があります。しかし、これは変えることができると思います。20年前、自動テストとコードレビューはかなりニッチなものでしたが、最終的には主流になりました。しかし、コード契約はニッチなものであり、今でもそうです。
うまくいけば、これによりFMがなぜそれほどニッチなのかが、少なくとも通常の「ウェブは飛行機ではない」という議論よりもよく説明されているでしょう。もし私が犯した明らかな間違いがあれば、遠慮なく私に叫んでください。
あなたの職場で設計仕様を使用することに興味がありますか?私の本を購入するか、私を雇う!
フィードバックを提供してくれたNick P、Richard Whaling、Ron Pressler、およびJohn Regehrに感謝します。
- TLA+は、最も人気のある形式仕様言語の1つであり、世界中のすべてのTLA+専門家を大きなスクールバスに収めることができるでしょう。[戻る]
- そして開示:私は生計のためにTLA+とAlloyのワークショップを運営しているので、これら2つの言語に非常に偏っています。この歴史でそれを考慮に入れようとしましたが、ご存知のように、偏見は偏見です。[戻る]
- MLは元々この形式の仕様を書くのを助けるために発明されました。[戻る]
- Euclidの作業が最初に開始されたのか、SPVの作業が最初に開始されたのかは議論の余地がありますが、私の知る限り、Euclidの方が早く一般に公開されたと思います。[戻る]
- Design by Contractは、このエッセイで使用している意味での「設計」を使用しているわけではありません。それは、設計仕様ではなく、コード仕様として契約を使用することです。[戻る]
- ああ、もしあなたがまだ持っていない言語で形式検証を行っているなら、プルリクエストを作成しませんか?[戻る]
- 私が恨んでいるわけではありませんが。[戻る]
- エイリアシングは証明を書くのに非常に敵対的であるため、John C Reynoldsはそれを処理するために全く新しい論理である分離論理を作成する必要がありました。[戻る]
- 彼のチューリング賞講演で、Edmund Clarkeは検証が難しいプロパティのいくつかを示しました:「浮動小数点数、文字列、ユーザー定義型、プロシージャ、並行性、ジェネリクス、ストレージ、ライブラリ…」[戻る]
- SMTはSatisfiability Modulo Theoriesの略です:変数のいくつかが数学の方程式であるSAT問題を解くこと。[戻る]
- このセクションでは当初、最初のSMTソルバーは2004年頃に出現したと述べられていましたが、それは誤りです。それらはそれより10年近く古いものです。また、SMTが自動定理証明の最初の主要な試みであったかのように示唆していましたが、それはひどく間違っています。Don SymeとHeidi Khlaafにこれを指摘していただき感謝します。[戻る]
- 前の記録は、おそらくseL4であり、その開発者は1日あたり2行のCに相当するコードを記述しました。[戻る]
- これらの数値のほとんどは、StavelyのToward Zero-Defect Programmingの研究から来ています。いつものように、結果に懐疑的になり、元の論文を再読してください。[戻る]
- 形式手法を研究して学んだことが1つあるとすれば、それは時間が悪であり、私はそれを憎むということです。[戻る]
- 設計仕様をコード仕様にマッピングするプロセスはリファインメントと呼ばれます。[戻る]
- 前述のように、これは一般的な用語ではありません。ほとんどの人は「仕様言語」を使用しますが、コード仕様と設計仕様の違いを明確にしたいのです。[戻る]
- モデルチェッカーはコード検証にも使用されますが(例:JMBC)、モデルチェックは設計検証の割合よりもコード検証の割合の方がはるかに大きいです。[戻る]
- 「多くの仕様作成者」というのは、約10人だと考えてください。[戻る]
- 仕様からコードを生成することは合成と呼ばれます。良い入門コースについては、Nadia Polikarpovaの研究を参照してください。コードが仕様に一致すること(または一方の仕様がもう一方の仕様に一致すること)を証明することはリファインメントと呼ばれます。これらはいずれも活発な研究分野です。[戻る]
- 聞いた議論の1つは、アジャイルは事前の設計を拒否するため、誰も形式仕様を行いたがらないということです。これは貢献するかもしれませんが、私が会ったアジャイルを拒否する人々の多くは、アジャイリストと同じくらいFMを拒否しています。もう1つの議論は、歴史的に形式手法は一貫して過剰に約束し、約束を果たせなかったということです。これも貢献するかもしれませんが、ほとんどの人はFMを聞いたことさえなく、その歴史を知っているわけでもありません。[戻る]