ソフトウェアにおける形式手法

形式手法は、ソフトウェアの仕様記述、開発、検証に数理論理学を適用するものであり、システムの特性をテストするだけでなく、証明することを可能にする。

Definition

形式手法とは、ソフトウェアシステムを仕様記述、開発、検証するための数学に基づいた技術であり、仕様は形式言語で表現され、特性は証明または網羅的な状態探索によって確立される。

Scope

このトピックでは、Z、B、TLA+などの形式仕様記述言語、プログラムの正当性を推論するための公理的意味論とHoare論理、有限状態システムおよび並行システムの検証のためのモデル検査、定理証明と証明支援系、そして安全性が高くセキュリティが重要なソフトウェアにおける形式手法の利用について扱う。

Core questions

• 形式言語でソフトウェアの振る舞いを曖昧さなく記述するにはどうすればよいか？
• 仕様に対してプログラムの正当性はいかに証明されるか？
• モデル検査は有限状態システムおよび並行システムをいかに網羅的に検証するか？
• 形式手法のコストと利点は、どのような場合にその使用を正当化するか？

Key theories

Hoare論理と公理的意味論

Hoareは、プログラム構成要素の正当性が公理と推論規則によって表現される、事前条件と事後条件の論理を導入し、プログラムがその仕様を満たすことを証明するための基礎を提供した。

モデル検査

モデル検査は、有限状態モデルの到達可能な状態を自動的かつ網羅的に探索し、時相論理の特性を検証することで、テストでは見逃されがちなデッドロックや違反を検出する。

Clinical relevance

形式手法は、利用可能な中で最も強力な正当性の保証を提供し、航空電子工学、鉄道信号、セキュリティプロトコル、ハードウェアなど、失敗が許されない分野で適用される。ただし、そのコストのため、システム全体ではなく、主に重要なコンポーネントに限定して使用される。

Evidence & guidelines

産業界の実践に関する調査では、安全性が重要な領域における形式手法の成功事例が記録されており、DO-178CやCommon Criteriaなどの標準では、最高の保証レベルにおいて形式手法が認められている。

History

プログラム検証は1960年代後半にFloydとHoareによって基礎が築かれ、モデル検査は1980年代初頭にClarke、Emerson、Sifakisによって開発され（チューリング賞を受賞）、それ以来、ツールと証明支援系によって形式検証は重要なシステムのための産業利用へと導入されてきた。

Debates

形式手法のスケーラビリティとコスト

形式手法が大規模な産業用ソフトウェアに対して経済的にスケーラブルであるか否かについては、継続的な議論がある。自動化と軽量形式手法の進歩により適用範囲は広がったが、大規模システムの完全な検証は依然として高コストである。

Key figures

• C. A. R. Hoare
• Edsger Dijkstra
• Edmund Clarke
• Leslie Lamport

Seminal works

• hoare1969
• clarke1999
• woodcock2009

Frequently asked questions

形式手法はテストに取って代わるのか？

一般的にはそうではない。形式手法はモデルや仕様について強力な保証を与えるが、仮定、環境、モデル化されていない側面については依然としてテストが必要である。実際には両者は補完的であり、形式手法は最も重要な特性に焦点を当てる。

なぜ形式手法はあらゆる場所で使われないのか？

形式手法は専門的な知識と労力を必要とし、ほとんどのソフトウェアでは、より低いコストで十分な信頼性を提供するテストの方が正当化されやすい。形式手法は、失敗の結果が投資を正当化するほど深刻な場合に集中して使用される。