Highlights of Research Results 

Groupe de recherche en téléinformatique - Université de Montréal 

(September 1994)

Hewlett-Packard-CITI-NSERC Industrial Research Chair on Communications Protocols

Test suite development based on formal specifications: Testing is a crucial phase in development of software for distributed and concurrent systems. In the black-box testing paradigm, which is used for protocol conformance testing and many other applications, the internals of the system under test is not accessible, only its interface, and test cases are derived from the system's specification. In many cases, important aspects of the system behavior are specified using a finite state machine formalism. Our goal is to develop practical methods for automatically deriving a test suite from a given system specification. Another aspect of our concern is to enhance the testability of a system during its design phase; the objective is to obtain an end-product easy to test.  --   During the past years, we have developed several improved test derivation methods which yield test suites with well-defined fault coverage for a given system specification. While most existing methods work for completely specified, deterministic and minimal specifications which, in practice, represents a severe restriction, our group was the first to propose methods that work in the case of specifications including undefined situations, nondeterminism, and timing contraints, as well as taking into account realistic distributed test architectures. Some of these methods have been implemented in automated tools. Other results pertain to test derivation from specifications written in more powerful languages, such as formal description techniques (e.g. SDL or Estelle) and object-oriented systems. Tools for determining the fault coverage of existing test suites have also been developed.

Automated test result analysis:  A testing campaign usually involves the execution of a large number of test cases and the analysis of the resulting execution traces. In certain cases, the expected output from the system under test is defined by the test cases and any unexpected output is detected immediately. In other cases, such as for random testing or protocol interworking testing, the execution trace must be analysed for conformance with the system's specification. Additional analysis is required for diagnostic purposes.  --  During the last few years, we developed tools for the automatic analysis of test traces in respect to the system specification written in the Estelle or LOTOS specification languages. Our LOTOS tool, called TETRA, is part of an international collaboration for the development of a LOTOS toolset, including also tools for simulation and verification of specifications. Special attention was given to deal with the difficult problem of nondeterminism in the system specification. In addition, a tool for fault diagnosis based on finite state specifications has been developed.

 CITR (part of the Major Project "Broadband Services")

Quality of service (QoS) negotiation and adaptation: The premiss of QoS negotiation is that in the forseeable future,  multimedia information delivered through networks such as the Electronic Highway will be available in multiple quality/cost combinations. It will be up to the user to choose the most suitable alternative. Our goal is to develop multimedia applications that can adapt to changing QoS conditions in the underlying transport service and to develop methods for managing the resources needed for QoS adaptation in a distributed environment.  --  In the past year we identified the QoS requirements of the multimedia news target application and completed the design of a negotiation protocol between the application processes, the database servers and the underlying transport service. The protocol allows the dynamic re-negotiation of QoS parameters as a function of user requirements and the QoS actually available from the network. A QoS demonstrator has been developed which shows a possible interface arrangement enabling the user first to experience different available qualities of image, video, sound and text, and then to compose the desired combination.  

ESCORTE: Etude sur la synthèse de contrôle réparti en télématique (FCAR-BNR-NSERC research grant)

Methods for designing distributed algorithms for system control and communication gateways including real-time constraints: One of the difficulties of designing distributed systems is due to the concurrent nature of the different system components which makes their behavior much more difficult to understand and to test. Therefore the design of a new distributed algorithm should be verified before its implementation. Another approach is to derive distributed algorithms and protocols from a specification of the requirements in such a manner that they are correct "by construction". The objective of our research is the development of such derivation methods for various reactive systems applications, such as real-time distributed system control, communications gateways, and telecommunications networks management.  --   We have defined an automated algorithm for deriving a protocol specification which satisfies a given service specification, which describes in which order certain events should happen at different places within the distributed system. Recently, we have extended this approach to take into account real-time constraints of the service specification and the delays of the underlying communication network. Related work deals with the automatic derivation of a decentralized control algorithm which maintains certain specified properties of a distributed system which is to be controlled by several distributed controllers.  These methods have been applied to several example applications.    

 CITR Major Project on Communication Software (until summer 1993) and IGLOO project funded under the Québec Synergie program

Formal methods for object-oriented software development:  The phases of systems analysis and design are crucial for the development of reliable software. An object-oriented approach has been advocated for this purpose and many research activities explore the methods and notations best suited for the object-oriented analysis and design of distributed systems. It is hoped that an object-oriented approach may lead to more reuse of code and specifications, and to systems that are easier to adapt to evolving requirements.  --   We have defined a general framework, independent of any particular specification language, for considering formal relationships that correspond to different forms of refinement and specialization . Algorithms have been developed for deriving a new specifications which combines the behaviors of two existing specifications, and avoids any undesirable "feature interactions" between the two components. For software evolution, we have proposed a general framework in which appropriate constraints can be defined for controlling the appropriate changes during system evolution, and ensuring stable operating conditions for the system during these changes.

Distributed systems management - fault diagnostics and reconfiguration: As distributed systems become more and more complex, their operation and management becomes a major issue. In order to facilitate the operation and management of telecommunications systems made up from heterogeneous components, a number of international standards have been developed for network operations and management. While existing management systems provide means for collecting the pertinent information about the status and operations of the system, most fault recovery and reconfiguration decisions are still taken manually. There is presently much research activity internationally to develop ways in which some of these decisions could be taken automatically. The goal of our research is the automation of fault analysis including diagnostic testing, and reconfiguration management including hardware and the building of reconfigurable systems which are fault-tolerant and continuously running.  --  We have proposed a hierarchical and distributed approach in the area of fault management and a formal description of this approach has been developed. Using simulation studies we have tested different functions derived from this approach for simple faults, such as break faults.  Currently, an implementation of  this approach is underway on a network consisting of three interconnected LANs. In this context, we also study the interworking between the standards CMIS and SNMP using the OSIMIS implementation environment.