Protocol validation using a pumping-based approach

Kuo Chung Tai, Hong Fa Ho, Gen Huey Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Although the pumping theorem for a finite state machine is well-known, it is interesting to us whether the pumping phenomenon exists for a network of Communicating Finite State Machines (CFSM's). In this paper we derive two pumping theorems for a network N of CFSM's. Each pumping theorem describes a set of conditions under which a feasible event sequence of N can be "pumped" to produce an infinite set of feasible event sequences of N. We show that if a feasible event sequence E satisfying the conditions in one pumping theorem does not result in a deadlock or unspecified reception, neither does any event sequence derived by "pumping" E. Based on these results, we develop a pumping-based approach for detecting deadlocks and unspecified receptions in a network of CFSM's. We also show the experimental results of applying this new approach to validate several communication protocols.

Original languageEnglish
Title of host publicationProceedings of the15th Annual International Computer Software and Applications Conference, CMPSAC 1991
PublisherIEEE Computer Society
Pages339-344
Number of pages6
ISBN (Electronic)0818621524
DOIs
Publication statusPublished - 1991
Event15th Annual International Computer Software and Applications Conference, CMPSAC 1991 - Tokyo, Japan
Duration: 1991 Sep 111991 Sep 13

Publication series

NameProceedings - International Computer Software and Applications Conference
ISSN (Print)0730-3157

Conference

Conference15th Annual International Computer Software and Applications Conference, CMPSAC 1991
Country/TerritoryJapan
CityTokyo
Period1991/09/111991/09/13

ASJC Scopus subject areas

  • Software
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Protocol validation using a pumping-based approach'. Together they form a unique fingerprint.

Cite this