著者

深田 敦史 鍛 忠司 東野 輝夫 谷口 健一 森 将豪

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.39, no.8, pp.2519-2527, 1998-08-15

---

本論文では,入力を奪い合いながら並行に動作するDFSM群(DFSMsの直積マシン)としてモデル化される通信プロトコルのあるサブクラスに対して,DFSM群の状態と遷移の数の和に比例する程度のコストで効率良く適合性試験を行うための1つの手法を提案する.提案する方法では,まず,Wp法を用いて単独に各DFSMの試験を行う場合に用いる特性集合の和集合をシステム全体(DFSM群)の試験を行うための特性集合とする.入力を奪いあう場合,与えられた各特性系列に対して正しく反応を返す可能性のある状態対は複数存在する可能性がある.このため,各DFSMの1つの状態sの存在を確認するために,まず一定の条件を満たすW集合を構成する.次にその状態sを含む適切な状態組を1つ選び,その状態組に対する特性系列の反応をチェックすることにより状態sの存在を確認する.In this paper,we propose an effective conformance testing method for a subclass of protocols modeled as a set of DFSMs.The cost in the proposed testing method is only proportional to the sum of the numbers of states and transitions in a given set of DFSMs.In our method,we find a characterization set for each DFSM,which is used to test the DFSM alone in Wpmethod,and the union of the characterization sets is used as a characterization set for the total system.For a set of DFSMs with common inputs,there may exist two or more tuples of states that have correct responses against a given characterization set.So,in order to identify each state s in a DFSM,we find a characterization set with some specific properties.Then,we select a suitable tuple of states containing the state s,and identify the state s by checking their response to the characterization set.

著者

鍛 忠司 東野 輝夫 谷口 健一

雑誌

情報処理学会研究報告グループウェアとネットワークサービス(GN)

巻号頁・発行日

vol.1996, no.12, pp.19-24, 1996-01-25

---

通信プロトコルに対する適合性試験は通信システムの信頼性を高めるために有効である,従来,適合性試験系列の生成に関する研究の多くは単一の有限状態機械(S)によってモデル化されるソフトウェアを対象としている.しかし,複数のチャネルを持つ通信プロトコルなどでは,一つのチャネルの制御部を一つの決定性FSM(FS)でモデル化し,システム全体を入力を奪い合いながら並行に動作するDFSM群(FSMsの直積マシン)としてモデル化することが自然である.このようなシステムは全体としてもとのDFSM群の状態数の積に比例する状態を持つ非決定性FSM(FS)になる.このため,通常のNFSMに対する試験法を用いた場合,試験系列長がもとのDFSM群の状態数の積に比例するオーダーになるという問題点があった.本稿では,そのような入力を奪い合いながら並行に動作する複数のDFSM群としてモデル化されるような通信プロトコルのある部分クラスに対して,DFSM群の状態数の和に比例する程度のコストで効率よく適合性試験を行えるようにするための一つの手法を提案する,提案する手法では,まず,W?法を用いて単独に各DFSMの試験を行う場合に用いる先行系列の集合からシステム全体の試験を行うための先行系列の集合を生成する.また,各DFSMに対する特性集合の和集合をシステム全体の試験を行うための特性集合とする.次に,与えられた各特性系列に対して正しく反応を返す可能性のある状態対をすべて列挙し,その関係を表す制約式を生成する.これらの制約式を満たす解(状態の組)が仕様として与えられたDFSM群の状態対のみならば,与えられた先行系列の集合と特性集合に対して正しい反応を示す実装は仕様のDFSM群と等価であることが保証される.Conformance testing for communication protocols is useful for developing a highly reliable communication systems. Many researches have been done for test generation of the software modeled as a single finite-state machine (FSM). However, it is natural that the protocol with several channels is considered as a couple of DFSMs each of which controls a channel and competes with the others for common inputs. For this model, the existing methods have a problem that the derived test suite is proportional to the product of the numbers of states of DFSMs. In this paper, we propose an effective method of conformance testing for a subclass of protocols modeled as those couples of DFSMs. In our method, we find a state cover set for each DFSM, which is used to test the DFSM alone in W-method, and derive a state cover set for the total system from those sets. The characterization set for the total system is the union of those for the DFSMs. Then, we construct constraints representing the relation among tuples of states that have correct responses against the characterization set. If these constraints have only one solution, we guarantee that an IUT modeled as a couple of DFSMs which has correct responses against the state cover and characterization set is equivalent to the given specification.