Product Design, Manufacturing & Innovation Resources
» 形式検証

形式検証

1980
  • Edmund M. Clarke
  • E. Allen Emerson
  • Joseph Sifakis
オフィスで形式検証モデルをレビューするコンピュータ・サイエンス・エンジニア。.

(画像はイメージです)

フォーマル 検証 形式検証とは、数学的手法を用いて、システム設計の正しさを形式仕様に基づいて証明または反証することです。特定の入力に対してのみバグの存在を示すことができるテストとは異なり、形式検証はあらゆる入力に対してバグが存在しないことを証明できます。これには、システムの形式モデルを作成し、モデル検査や定理証明などの手法を用いることが含まれます。

形式検証は、システムの正当性を保証する最高レベルの手法です。このプロセスは、時相論理やプロセス代数などの数学的言語を用いてシステムの形式モデルを作成することから始まります。システムの要件から導き出された一連の特性も、形式言語で表現されます。検証プロセスでは、自動化されたツールを使用して、モデルのあらゆる状態を体系的に探索し、指定された特性が真であるかどうかを判断します。

主に2つの手法が用いられます。モデル検査と定理証明です。モデル検査は、有限状態モデルの状態空間全体を探索する自動化された手法です。特性が違反された場合、モデルチェッカーは反例、つまりその失敗を示す具体的な実行トレースを生成します。これは非常に効果的ですが、非常に複雑なシステムでは「状態空間爆発」の問題に悩まされる可能性があります。定理証明は、システムとその特性を論理式(定理)として表現し、自動化された、あるいは対話型の証明器を用いて正当性の形式的な証明を構築する手法です。この手法は無限状態システムにも対応できますが、多くの場合、専門家による相当な手作業が必要となります。

計算コストが高く、専門的な知識を必要とするものの、形式検証は、障害発生時の損失が極めて大きい安全性やセキュリティが重要なシステムにとって不可欠である。徹底的なテストが不可能なCPU浮動小数点演算装置、通信プロトコル、制御システムなどの正当性を検証するために、形式検証は既に有効に活用されている。

UNESCO Nomenclature: 1203
コンピュータサイエンス

タイプ

ソフトウェア/アルゴリズム

混乱

基礎

使用法

ニッチ/専門分野

前駆物質

  • 命題論理と述語論理
  • automata theory
  • ラムダ計算
  • プログラム意味論(例:ホア論理)
  • 計算複雑性理論

アプリケーション

  • マイクロプロセッサ設計(例:Intel Pentium FDIVのバグ修正)
  • 航空電子機器ソフトウェア(例:フライ・バイ・ワイヤ・システム)
  • 暗号プロトコルの分析
  • 鉄道信号システム
  • 重要なオペレーティングシステム用のソフトウェアドライバ

特許:

NA

潜在的なイノベーションのアイデア

ボットによるトラフィック(現在1日あたり4万件以上)を排除するため、このコンテンツはコミュニティメンバー限定となっています。
> ログイン < または > 登録 < (100%無料)でこれにアクセスできます。他のすべての制限付きコンテンツとツールも同様です。

関連分野:形式検証、モデル検査、定理証明、形式手法、正当性、ソフトウェア検証、ハードウェア検証、時相論理。

歴史的背景

形式検証

1970
1973
1980
1980
1980
1982-07-01
1988-06-01
1970
1970-01-01
1975-06-01
1980
1980
1980
1986-01-01
1990

(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)

関連する発明、革新、および技術原理

フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。