遷移の選択が状態訪問回数で決まる有限状態機械対からなる通信系に対する生存性の検証

水野, 健太郎; 中田, 明夫; 東野, 輝夫; 谷口, 健一; 岡野, 浩三

このアイテムのアクセス数:36件（2019-10-14 08:46 集計）

このアイテムへのリンクには次のURLをご利用ください:http://hdl.handle.net/11094/50248

閲覧可能ファイル

ファイル	フォーマット	サイズ	閲覧回数	説明
ipij-jnl_39_3_750	pdf	1.18 MB	28	出版社版/publisher

論文情報

タイトル	遷移の選択が状態訪問回数で決まる有限状態機械対からなる通信系に対する生存性の検証
別タイトル	Verification of Liveness Property for C - FSM's with Transitions depending on State Visiting Numbers
タイトル (ヨミ)	センイ　ノ　センタク　ガ　ジョウタイ　ホウモン　カイスウ　デ　キマル　ユウゲン　ジョウタイ　キカイ　ツイ　カラ　ナル　ツウシンケイ　二　タイスル　セイゾンセイ　ノ　ケンショウ
著者	水野, 健太郎水野, 健太郎
	中田, 明夫中田, 明夫
	東野, 輝夫東野, 輝夫
	谷口, 健一谷口, 健一
	岡野, 浩三岡野, 浩三
著者の別表記	Mizuno, Kentaro
	Nakata, Akio
	Okano, Kozo
	Higashino, Teruo
	Taniguchi, Kenichi
著者 (ヨミ)	ミズノ, ケンタロウ
	ナカタ, アキオ
	オカノ, コウゾウ
	ヒガシノ, テルオ
	タニグチ, ケンイチ
抄録	本論文では，各状態からの遷移条件がその状態の訪問回数で決まる有限状態機械モデルの上で生存性の検証を機械的に行う1つの方法を提案する．通信プロトコルは有限状態機械（FSM）によってモデル化され検証される場合が多いが，一般にシーケンス番号などのパラメータ値の変化を直接状態で区別して表そうとするとFSMの状態数が多くなり，状態爆発が起こる．我々は各遷移の実行可能性がその遷移の開始状態の訪問回数で決まるような有限状態機械モデルFSM／Cを提案し，このFSM／Cモデルの上で整数線形計画法を用いることにより状態爆発を回避した生存性の検証法を提案する．FSM／Cモデルでいくつかの通信プロトコルの仕様を記述できる．また，この手法に基づき，FSM／Cからなる通信系の生存性を検証するシステムを作成した結果についても報告する.
抄録	Many communication protocols are modeled as finite state machines(FSM's).In general,since the size of states becomes large in order to treat parameter values such as sequence numbers,the state explosion problem may occur.In this paper,we will propose an FSM/C model where the execution of each transition may depend on the number that its starting state has been visited,and propose a technique for verifying a liveness property.In this model,a counter Csi holds the number that state si has been visited.Many communication protocols can be modeled in our FSM/C model.If two communicating FSM/C's eventually return to the pair of their initial states and the communication channels become empty,thenwe say that they have the liveness property.For verifying the liveness property,we use an integer linear programming technique so that the state explosion problem does not occur.
公開者	情報処理学会
公開者 (ヨミ)	ジョウホウ　ショリ　ガッカイ
掲載誌名	情報処理学会論文誌
巻	39
号	3
開始ページ	750
終了ページ	759
刊行年月	1998-03-15
ISSN	03875806
NCID	AN00116647
URL	http://hdl.handle.net/11094/50248
権利情報	ここに掲載した著作物の利用に関する注意本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
権利情報	Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan. Comments are welcome. Mail to address editj＠ipsj.or.jp, please.
言語	日本語
カテゴリ	学術雑誌論文 Journal Article

著者版フラグ	publisher
NII資源タイプ	学術雑誌論文
ローカル資源タイプ	学術雑誌論文
dcmi資源タイプ	text
DCTERMS.bibliographicCitation	情報処理学会論文誌.39(3) P.750-P.759
DC.title	遷移の選択が状態訪問回数で決まる有限状態機械対からなる通信系に対する生存性の検証
DCTERMS.alternative	Verification of Liveness Property for C - FSM's with Transitions depending on State Visiting Numbers
DC.creator	水野, 健太郎
	中田, 明夫
	東野, 輝夫
	谷口, 健一
	岡野, 浩三
DC.creator	Mizuno, Kentaro
	Nakata, Akio
	Okano, Kozo
	Higashino, Teruo
	Taniguchi, Kenichi
DC.publisher	情報処理学会
DC.language" scheme="DCTERMS.RFC1766	日本語
DCTERMS.issued" scheme="DCTERMS.W3CDTF	1998-03-15
DC.identifier" scheme="DCTERMS.URI	http://hdl.handle.net/11094/50248
DCTERMS.abstract	本論文では，各状態からの遷移条件がその状態の訪問回数で決まる有限状態機械モデルの上で生存性の検証を機械的に行う1つの方法を提案する．通信プロトコルは有限状態機械（FSM）によってモデル化され検証される場合が多いが，一般にシーケンス番号などのパラメータ値の変化を直接状態で区別して表そうとするとFSMの状態数が多くなり，状態爆発が起こる．我々は各遷移の実行可能性がその遷移の開始状態の訪問回数で決まるような有限状態機械モデルFSM／Cを提案し，このFSM／Cモデルの上で整数線形計画法を用いることにより状態爆発を回避した生存性の検証法を提案する．FSM／Cモデルでいくつかの通信プロトコルの仕様を記述できる．また，この手法に基づき，FSM／Cからなる通信系の生存性を検証するシステムを作成した結果についても報告する.
DCTERMS.abstract	Many communication protocols are modeled as finite state machines(FSM's).In general,since the size of states becomes large in order to treat parameter values such as sequence numbers,the state explosion problem may occur.In this paper,we will propose an FSM/C model where the execution of each transition may depend on the number that its starting state has been visited,and propose a technique for verifying a liveness property.In this model,a counter Csi holds the number that state si has been visited.Many communication protocols can be modeled in our FSM/C model.If two communicating FSM/C's eventually return to the pair of their initial states and the communication channels become empty,thenwe say that they have the liveness property.For verifying the liveness property,we use an integer linear programming technique so that the state explosion problem does not occur.
DC.rights	ここに掲載した著作物の利用に関する注意本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
DC.rights	Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan. Comments are welcome. Mail to address editj＠ipsj.or.jp, please.
citation_title	遷移の選択が状態訪問回数で決まる有限状態機械対からなる通信系に対する生存性の検証
citation_author	水野, 健太郎
	中田, 明夫
	東野, 輝夫
	谷口, 健一
	岡野, 浩三
citation_publisher	情報処理学会
citation_language	日本語
citation_date	1998-03-15
citation_journal_title	情報処理学会論文誌
citation_volume	39
citation_issue	3
citation_firstpage	750
citation_lastpage	759
citation_issn	03875806
citation_public_url	http://hdl.handle.net/11094/50248

閲覧可能ファイル

論文情報

論文詳細を表示