Doron Peled

Bell Labs


Automatic Verification of Message Sequence Charts

Room 2B-432
Thursday, December 4, 1997 at 12:30 PM

Abstract:

Communication systems may include thousands of protocols, aimed at providing a wide range of services. The development, integration and maintenance of such protocols become a non-trivial task. The formalism of message sequence charts (MSCs) was introduced for assisting in developing such systems. According to an international standard (Z120), MSCs have both a formal syntax and a graphical representation. The latter makes it popular among software engineers, as it allows to draw different scenarios (e.g., normal executions of the protocols, or executions under various rare conditions). Analyzing MSC helps reduce errors in the early design stages. Classical methods of analysis, such as model-checking, cannot directly be applied to systems described using the MSCs notation. The semantics of MSCs involves partially ordered sets of events that do not correspond to the regular-languages framework of most automatic validation techniques. I will present some algorithms and complexity results related to the analysis of MSCs.