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.