記号モデル検査を用いた自己安定アルゴリズムの検証法の提案
スポンサーリンク
概要
- 論文の詳細を見る
自己安定アルゴリズムとは,任意の初期状態から有限時間内で正常状態に遷移する分散アルゴリズムである.本論文では,このような自己安定アルゴリズムに対する自動検証について議論する.アルゴリズムの自己安定性を示すためには,定義上,全ての状態を初期状態として考慮する必要がある.従って,アルゴリズムの挙動を有限状態機械で表現する通常のモデル検査手法では,状態数が指数的に増大してしまい適用が不可能であった.本研究では,この問題を解決するため,記号モデル検査を用いて検証を行うことを提案する.記号モデル検査は,二分決定グラフ(BDD)を用いて状態空間を表現する検証法であり,このBDDは初期状態に依存しないという特色を持つ.具体的には,良く知られた記号モデル検査ツールであるSMVを用いた検証の枠組みを提案する.更に,実際に提案手法を用いてアルゴリズムの間違いを発見した例についても報告する.
- 社団法人電子情報通信学会の論文
- 1999-11-12
著者
-
菊野 亨
大阪大学大学院情報科学研究科
-
土屋 達弘
大阪大学大学院情報科学研究科
-
長野 伸一
(株)東芝研究開発センター
-
長野 伸一
(株)東芝
-
パイディ ロハユ
(株)マレーシア松下電器
-
菊野 亨
大阪大学大学院 情報科学研究科
関連論文
- 新年のご挨拶 : 2010年:新しい変化の年そして挑戦の年
- ラウンドモデルからの変換による非同期コンセンサスアルゴリズムの導出(ネットワーク環境でのディペンダビリティ)
- 大学院情報系学生に対する技術者倫理教育(技術者倫理・情報倫理教育の現状と課題,及び一般)
- 3状態相互排他アルゴリズムの安定時間の下限について
- 非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- ペアワイズテスト : ソフトウェアテストの効率化を求めて
- マルチエージェントを用いた無中断予備VP設定方式
- 5 組込みシステムにおけるソフトウェアプロダクトラインの導入(ソフトウェア再利用の新しい波-広がりを見せるプロダクトライン型ソフトウェア開発-)
- 年頭の挨拶 : 30年を振り返って,一歩一歩前進
- 揺りかごのような存在 : 屋久島の倒木の役割
- 情報処理・ソフトウェアの信頼性保証技術 : 10年の歩みを踏まえて
- 情報家電に期待すること : 安定した生活の立場から
- モデル検査入門
- モデル検査を用いたコンセンサスアルゴリズムの合意性検証(ネットワーク環境でのディペンダビリティ)
- Interpolantを利用したモデル検査による機能競合の検証(ネットワーク環境でのディペンダビリティ)
- 耐故障分散アルゴリズムに対するPROMELAモデルの生成(ディペンダブルコンピューティングシステム及び一般)
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- ホームネットワークシステムにおける連携サービスのモデル検査による検証
- モデル検査による分散システムにおける合意アルゴリズムの安全性の検証(ディペンダブルソフトウェアとネットワーク及び一般)
- 整数上の論理式の充足可能性判定に基づく限定モデル検査手法の提案(安全性及び一般)
- 整数上の論理式の充足可能性判定に基づく限定モデル検査手法の提案
- ペトリネットに対する充足可能性判定を利用した検証手法の提案(コンカレント工学一般)
- ペトリネットに対するSATを利用したモデル検査の効率化
- 充足可能性判定を用いたモデル検査ツールの実装
- ホームネットワークシステムにおけるサービス競合の分類と解消について
- ソフトウェアメトリクスのデータマイニングによる障害発生要因特定
- Webシステムにおけるコンテクストデータストア機構の設計とコンポーネントオブジェクト技術を利用した実装
- 5ZC-10 オブジェクト指向によるプロトタイピング開発のための工数見積もりの検討
- Javaプログラムのためのソフトウェアメトリクスの提案
- 仕様変更に伴うソースコード変更量の分析 : クラス機能特性に基づくメトリクスの適用
- 非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- 製品リリース履歴における論理的結合集合に基づいた横断フィーチャ分析法
- メソッド呼び出しに関する不具合修正での変更作業の分析
- ソフトウェアプロジェクト予測に用いるメトリクスの削減
- プログラム設計過程の定量的評価の試み-初期設計書の品質から見た評価-
- 機能モジュールに対する優先度に基づいた選択的ソフトウェアテスト手法の提案
- ベイズ識別器による不具合予測のための相関ルールマイニングを用いたメトリクス絞り込み
- ソフトウェア開発データに対する相関ルールマイニングを利用した不具合増加要因の調査
- ソフトウェアプロジェクト診断のためのチェックリスト導出(レビュー,品質(学生セッション))
- 企業横断的データからのプロジェクト改善案の相関ルールマイニングによる抽出
- 相関ルールマイニングによる企業横断データにおける不具合工数密度の分析
- 相関ルールマイニングの適用によるソフトウェア生産性の決定要因の分析(学生セッション C_開発プロセス)
- GPUを用いた状態可到達性解析の高速化(ネットワーク環境でのディペンダビリティ,及び一般)
- 欠損を含むプロジェクトデータからのプロジェクト成否予測のための特徴抽出
- Webアプリケーションの脆弱性検出を目的とした自動テストツールの性能評価(ネットワーク環境でのディペンダビリティ,及び一般)
- メソッドに対するコメント文記述の変更履歴とメソッドの不具合との関係に関する実証的考察 (ソフトウェアサイエンス)
- フォールトプローンモジュール検出手法間の精度比較 : Fault-pronenessフィルタリングとロジスティック回帰
- ソースコード中に含まれる不具合トークンをテキスト分類に基づいて推定するツールの試作と評価
- ソースコード中に含まれる不具合トークンをテキスト分類に基づいて推定するツールの試作と評価
- 相関ルールマイニングによるソフトウェア開発プロジェクト中のリスク要因の分析(推薦論文・ソフトウェア工学の基礎)
- ベイズ識別器による混乱予測に基づくソフトウェアプロジェクト管理支援ツールの試作(学生セッション C_開発プロセス)
- 汎用テキスト分類フィルタを利用した不具合を含むソースコードの予測
- ピアの近接性を考慮したスキップグラフの構築
- ピアの近接性を考慮したスキップグラフの構築
- ピアの近接性を考慮したスキップグラフの構築
- 1-2 スパムフィルタリングに基づくフォールトプローンモジュール検出器の開発(セッション1「プロジェクト管理・ソフト」)
- 5B-2 品質定量指標のための異なるプログラミング言語間での規模の比較の試み(プロジェクトの定量的管理,一般セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- ゴシップ型ブロードキャストの高信頼化のための適応的再送手法の提案(ネットワーク,SWoPP2006)
- スケールフリーネットワークに対するゴシップアルゴリズムの高信頼化手法の提案(データ工学, ディペンダビリティ, 一般)
- スケールフリーネットワークに対するゴシップアルゴリズムの高信頼化手法の提案(データ工学, ディペンダビリティ, 一般)
- ピアの近接性を考慮したスキップグラフの構築
- ピアの近接性を考慮したスキップグラフの構築
- 5B-1 相関ルールマイニングを利用したソフトウェアプロジェクト混乱要因の関連性に関する調査(プロジェクトの定量的管理,一般セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 記号モデル検査を用いた自己安定アルゴリズムの検証法の提案
- 記号モデル検査を用いた自己安定アルゴリズムの検証法の提案
- 通信プロトコルの回復処理における設計誤りのReal-Time Temporal Logic を用いた検出
- マルチエージェントを用いた無中断予備VP設定方式
- プロトコル検証シミュレータの開発とコネクション確立プロトコルへの適用
- 通信プロトコルのリスポンシブネス検証における仮想システム状態の導入効果の実験的評価
- 物理ネットワークの構造を反映したオーバーレイネットワークの構築と信頼性評価(データ工学, ディペンダビリティ, 一般)
- 物理ネットワークの構造を反映したオーバーレイネットワークの構築と信頼性評価(データ工学, ディペンダビリティ, 一般)
- C-010 アドホックネットワークに対するゴシップ型ブロードキャストプロトコルの信頼性の分析(C.アーキテクチャ・ハードウェア)
- システム特性を考慮したペアワイズテストの改良
- サーベイ論文「ペアワイズテスト-ソフトウェアテストの効率化を求めて-」に関する訂正と補足
- 情報家電システムの安全検証(「信頼性・保全性・安全性の事例:情報処理・ソフトウェア編」〜信頼性ハンドブック出版から10年を経て〜)
- 単一多数決器を用いたカスケード式TMRの最適構成の導出(ディペンダブルコンピューティングシステム及び一般)
- 単一多数決器を用いたカスケード式TMRの最適構成の導出(ディペンダブルコンピューティングシステム及び一般)
- 耐故障分散アルゴリズムに対するPROMELAモデルの生成(ディペンダブルコンピューティングシステム及び一般)
- コントロールフローグラフにおける辺のペアを考慮したコードカバレッジの提案と評価 (ソフトウェアサイエンス)
- テスト実行コストを考慮したペアワイズテストセット生成法の提案(DC-2テスト,インターネット環境でのデータ工学とディペンダビリティ,及び一般)
- テスト実行コストを考慮したペアワイズテストセット生成法の提案(DC-2テスト,インターネット環境でのデータ工学とディペンダビリティ,及び一般)
- 定量的プロジェクトマネジメント : メトリクスデータ利用の新技術(「ソフトウェア信頼性工学の新展開」)
- 複数の手法を用いたソフトウェア開発プロジェクトの混乱予測 : 手法間での精度比較実験
- ソフトウェア開発メンバーへのアンケートを利用したBaysian Classifierによるプロジェクト混乱予測
- リスク要因を考慮したシステムダイナミクスに基づくソフトウェアプロジェクトシミュレータの開発
- ベイジアンネットに基づくソフトウェア開発工程の最終品質予測モデルの提案
- 効果的なソフトウェア開発プロジェクト管理のためのシステムダイナミクスに基づくシミュレーションモデルの提案
- プロジェクトマネージャへのアンケートに対する因子分析に基づいたソフトウェア開発コスト推定モデルの提案
- フィールド不具合数を許容値以下に抑えるためのソフトウェアテスト工数の推定モデルの提案
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- オーバーレイネットワークにおける遠距離通信のホップ数削減の試み(インターネット環境でのデータ工学とディペンダビリティ)
- オーバーレイネットワークにおける遠距離通信のホップ数削減の試み(インターネット環境でのデータ工学とディペンダビリティ)
- ある企業におけるソフトウェアプロセス改善の効果に対する統計的分析
- Use Case Mapsを用いたサービス競合可能シナリオの導出と実験的評価(ネットワークオペレーションと資源管理論文)
- オープンソースを用いた実験環境でのプログラマブルVoIPサービスの意味誤りの評価(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- オープンソースを用いた実験環境でのプログラマブルVoIPサービスの意味誤りの評価(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- オープンソースを用いた実験環境でのプログラマブルVoIPサービスの意味誤りの評価
- サービス競合フィルタリングにおける競合可能シナリオの導出の評価