Construction and Analysis of Distributed Processes とは

CADP(分散プロセスの構築と分析)は、通信プロトコルと分散システムの設計のためのツールボックスです。 CADPは、INRIA Rhone-AlpesのCONVECSチーム(以前はVASYチームによって開発された)によって開発され、さまざまな補完的なツールに接続されていました。 CADPは、維持され、定期的に改善され、多くの産業プロジェクトで使用されます。
CADPツールキットの目的は、シミュレーション、迅速なアプリケーション開発、検証、およびテスト生成のためのソフトウェアツールとともに、正式な記述技術を使用して信頼性の高いシステムの設計を容易にすることです。
CADPは、非同期並行性、すなわち、インタリーブセマンティクスによって管理される一組の並列プロセスとして挙動をモデル化することができる任意のシステムに適用することができる。したがって、CADPは、ハードウェアアーキテクチャ、分散アルゴリズム、電気通信プロトコルなどの設計に使用できます。CADPで実装されている列挙型検証(明示的な状態検証とも呼ばれます)技術は、理論の証明はあまり一般的ではありませんが、複雑なシステムでの設計ミス
CADPには、フォーマルメソッドでの2つのアプローチの使用をサポートするツールが含まれています。どちらも信頼できるシステム設計に必要です。
 モデルは、並列プログラムと関連する検証問題の数学的表現を提供します。モデルの例は、オートマトン、通信オートマトンのネットワーク、ペトリネット、バイナリ決定図、ブール方程式系などである。理論的な観点から、モデルに関する研究は、特定の記述言語とは無関係の一般的な結果を求めている。実際には、モデルは複雑なシステムを直接記述するにはあまりにも基本的すぎる(これは退屈でエラーが起こりやすい)。高水準の記述を検証アルゴリズムに適したモデルに変換するコンパイラと同様に、プロセス代数またはプロセス計算と呼ばれるより高いレベルの形式が必要です。

FDR (software) とは

FDR(Failures-Divergences Refinement)とその後のFDR2は、CSP(Communicating sequential processes)で表現された正式なモデルをチェックするように設計された洗練チェックソフトウェアツールです。このツールはもともとFormal Systems(Europe)Ltd.が開発したもので、オックスフォード大学コンピュータサイエンス学科のBill Roscoe氏は、このツールで使用されているアルゴリズムの多くを考案し、Michael Goldsmith氏は実装に役立ちました。 FDR2は、オックスフォード大学コンピュータサイエンス学科によって開発されたもので、学術およびその他の非営利目的で自由に利用できます。
FDRは、しばしばモデルチェッカーと呼ばれますが、技術的には2つのCSPプロセス式をラベル付き遷移システム(LTS)に変換し、プロセスの1つが特定のセマンティック内で他のものを洗練するかどうかを決定するという点で、モデル(トレース、失敗、失敗/発散、その他の選択肢)。 FDR2は、詳細化検査中に探索されなければならない状態空間のサイズを縮小するために、様々な状態空間圧縮アルゴリズムをプロセスLTSに適用する。
FDR2は1995年にFDR1と呼ばれていた以前のツールを置き換え、多くのリリースを経ています.FDR3は、並列実行と統合型チェッカーを組み込んだ完全に書き直されたバージョンです。 FDR3はオックスフォード大学からもリリースされ、2008-12年にFDR2もリリースされました。 ProBE CSP AnimatorはFDR3に統合されています。今はFDR4に引き継がれています。

TAPAs model checker とは

TAPASは、並行システムを特定および分析するためのツールであり、その目的はプロセス代数の教授をサポートすることです。システムはプロセス代数項として記述され、ラベル付き遷移システム(LTS)にマッピングされます。特性は、具体的なシステム記述と抽象的なシステム記述の間の等価性を検査することによって、または得られたLTS上の時間的な式(μ-計算法またはACTLとして表される)をモデル検査することによって検証することができる。特に教えることに適したTAPAsの重要な特徴は、グラフィカルでもテキストでも、各システムの一貫した二重表現を維持することです。図表表記が変更された後、直ちにテキスト表記が更新されますが、テキスト表記の変更が懸念される場合は、更新を強制する必要があります。
TAPAsでは、並行システムは、システム動作の非決定論的記述であるプロセスと、プロセス構成によって得られるプロセスシステムとによって記述される。特に、プロセスは、他のプロセスまたはプロセスシステムの観点から定義することができる。プロセスとプロセスシステムは、与えられたプロセス代数の演算子を使用して構成されます。現在、TAPAsでは、2つのプロセス代数:CCSPとPEPAとみなされます。
CCSP(= CCS + CSP)は、CSPの一部の演算子を考慮してCCSから得られます。実際には、CCSPプロセスシステムを作成した後、ユーザーは以下を使用して分析することができます。
 等価性チェッカー:等価性の多くの定義に関する自動化ペアを比較することができます(バイシミュレーション、分岐二乗、装飾トレース)モデルチェッカー:システムのモデルを与えられ、このモデルが指定された仕様を満たしているかどうかを自動的にテストします。シミュレータ:システムを介した1つの可能な実行パスに従い、その結果の実行トレースをユーザに提示する。
PEPA(Performance Evaluation Process Algebra)は、1990年代にJane Hillstonによって導入されたコンピュータと通信システムをモデリングするために設計された確率的プロセス代数です。この言語は、ミルナーのCCSやHoareのCSPなどの古典的なプロセス代数を、確率的な分岐と遷移のタイミングを導入することによって拡張します。レートは指数分布から引き出され、PEPAモデルは有限状態であり、確率過程、具体的には連続時間マルコフ過程(CTMC)を生じさせる。したがって、この言語は、スループット、利用率、応答時間、デッドロックの解消などの定性的特性など、コンピュータおよび通信システムのモデルの定量的特性を調べるために使用できます。この言語は、Gordon Plotkinによって発明されたスタイルの構造化された操作セマンティクスを使用して正式に定義されています。
TAPASはピサのIEI CNRによってJACKと呼ばれ、ピサのISTI-CNRによって継続されたツールの実現によって1990年に始まった共同作業の結果です。新しいTAPAsバージョンは、フィレンツェ大学のInformaticaのDipartimento Sistemi edで開発されました。

Romeo Model Checker とは

Roméoは、時間とともにモデル化されたリアルタイムシステムのモデル化、検証、検証のための統合ツール環境であり、パラメータで拡張されたPetri NetsまたはストップウォッチPetri Netsです。
このツールは、フランスのナントにあるIRCCyN研究所(Nantes、Nantes、CNRS)のReal-Time Systemsグループによって開発されました。

Libdmc とは

LibdmcはLIP6研究所で設計されたライブラリです。その目的は、既存のモデルチェッカーの配布を容易にすることです。また、C ++言語のおかげで、パフォーマンスを犠牲にすることなく最も汎用的なインターフェイスを提供するように設計されています。
モデル検査は、モデル化されたシステムの動作がプロパティを検証することによって正確であることを自動的に証明する方法を提供します。しかし、メモリの集中的な使用によって引き起こされる、いわゆる状態空間爆発の問題がある。この問題を克服するための多くの解決策が提案されているが(例えば、BDDのような意思決定図による記号表現)、これらの方法は、許容できない時間消費に迅速につながる可能性がある。
分散モデル検査は、専用クラスタの集約されたリソースを使用することによって、メモリと時間の両方を克服する方法です。しかし、モデルチェッカー全体を書き直すのは難しい作業なので、libdmcのアプローチはモデルチェッカーを構築するためのフレームワークを与えることです。

TAPAAL Model Checker とは

TAPAALは、デンマークのAalborg大学でコンピュータサイエンス学科で開発されたTimed-Arcペトリネットのモデリング、シミュレーション、検証のツールであり、Linux、Windows、Mac OS Xプラットフォームで使用できます。
Timed-Arc Petri Net(TAPN)は、古典的なペトリネットモデル(1962年のCarl Adam Petriのディスカバリーで導入された分散計算の一般的なグラフィカルモデル)の時間拡張です。 TAPNで考慮される時間延長は、ネットのトークン(各トークンは独自の年齢を有する)に関連するリアルタイムの明示的な処理を可能にし、場所からトランジションへのアークは、そのトークンの年齢を制限する時間間隔それぞれの遷移を起動するために使用することができます。 TAPAALツールでは、トランスポートアーク(これは、以前に検討されていたリードアークよりも表現力が豊富である)およびインヒビターアークを備えた、年齢不変のこのモデルのさらなる拡張が実装されています。
TAPAALツールは、TAPNモデルを描画するためのグラフィカルなエディタ、設計されたネットを実験するためのシミュレータ、CTLロジックのサブセット(本質的にEF、EG、AF、AGの入れ子式なしの式)で論理クエリに自動的に答える検証環境を提供します。また、ユーザは、所与のネットが所定の数kに対してkバウンドであるかどうかをチェックすることもできる。 TAPAALには、TAPAAL(継続時間と離散時間の1つ)と一緒に配布される独自の検証エンジンが装備されています。オプションで、ユーザーは自動的にTAPAALモデルをUPPAALに変換し、UPPAAL検証エンジンに依存することができます。

CHESS model checker とは

CHESSは、スレッドスケジュールの体系的な探索によって、マルチスレッドソフトウェアのエラー/ハイセンスバグを見つけるためのソフトウェアモデルチェッカーです。現在のテストツールでは、データ競合、デッドロック、ライブロック、データ破損によるアクセス違反などのエラーを検出することは非常に困難です。 CHESSがエラーを見つけると、それはエラーにつながるプログラムの完全な反復可能な実行を提供し、したがってデバッグプロセスを大きく助ける。
CHESSは、ストレステストの代替として、同時ソフトウェアのテストに使用できます。

PAT (model checker) とは

PAT(Process Analysis Toolkit)は、リアルタイムのシステムとその他の可能なドメインを構成、シミュレート、推論するための自己完結型のフレームワークです。ユーザーフレンドリーなインターフェイス、特長のモデルエディタ、アニメーションシミュレータが付属しています。最も重要なことに、PATは、デッドロックフリーネス、ダイバージェンスフリーネス、到達可能性、公平性を前提としたLTLプロパティ、リファインメントチェック、確率モデルチェックなど、さまざまなプロパティを扱うさまざまなモデルチェック手法を実装しています。良好な性能を達成するために、高度な最適化技術がPATに実装されている。部分順序削減、対称性減少、プロセスカウンタ抽象化。現在までに、PATには41の国と地域の302の組織から1350人の登録ユーザーがいます。

NuSMV とは

NuSMVは、BDD(Binary Decision Diagram)に基づく最初のモデル検査ツールであるSMVシンボリックモデルチェッカーの再実装と拡張です。このツールはモデル検査のためのオープンアーキテクチャとして設計されています。これは、他の検証ツールのバックエンドとして、また正式な検証技術のためのリサーチツールとして使用するために、工業規模のデザインの信頼性の高い検証を目的としています。
NuSMVは、ITC-IRST(イタリアのトレントにあるIstituto Trentino di Cultura)、カーネギーメロン大学、ジェノバ大学、トレント大学との共同プロジェクトとして開発されました。
NuSMVのバージョン2であるNuSMV 2は、NuSMVのすべての機能を継承しています。さらに、BDDベースのモデル検査とSATベースのモデル検査を組み合わせています。 ITC-IRSTの後継機関であるFondazione Bruno Kesslerによって維持管理されています。