著者

鍛 忠司 東野 輝夫 谷口 健一

雑誌

情報処理学会研究報告グループウェアとネットワークサービス(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.